msc.nn: Nearest Neighbor Morse Smale Complex
In msr: Morse-Smale Approximation, Regression and Visualization

Description Usage Arguments Value Author(s) References See Also Examples

Compute a hierarchy of Morse-Smale complex of the scattered data x using a neareast neighbor based approach at the requested persistence levels. The persistence is a threshold for merging neighboring extrema. If the difference of lower function value of the extrema and the saddle connecting them is below persistence the extrema are merged. The msc.nn.svm and msc.nn.kd construct Morse-Smale complex that allow probabilistic preditcion (using predict) pf the partion assignment of unseen data points, see also predict.msc. The nearest neighbor computation uses the ANN library by David M. Mount and Sunil Arya (http://www.cs.umd.edu/~mount/ANN/).

  msc.nn(y, x, knn = ncol(x), pLevelP = 0.2, pLevel, 
         nLevels, type = 1, smooth = FALSE, eps=0.01) 
  msc.nn.kd(y, x, knn = ncol(x)*3, pLevelP = 0.2, pLevel, nLevels, 
            bw, type = 1, smooth = FALSE, eps=0.01) 
  msc.nn.svm(y, x, knn = 3*ncol(x), pLevelP = 0.2, pLevel, nLevels, 
             cost = 1,  type = 1, smooth=FALSE, precompute = FALSE, eps=0.01 ) 
  msc.graph(y, x, knn, knnd, nLevels, smooth = FALSE)

`y`	Function values at observations x. A numeric vector is expected.
`x`	Observations, a numeric marix is expected.
`knn`	Number of nearest neighbors for graph computation or matrix with nn indicies
`knnd`	Squared nearest nieghbor distances has to be same size as knn
`pLevel`	Compute the Morse-Smale complex for a single persistence level given by pLevel. Here, extrema with persistence less than `pLevel` are ignored.
`pLevelP`	Same as pLevel, but instead of an absolute persistence value, the persistence level is expressed as a percentage of `max(y) - min(y)`
`nLevels`	If specified computes a hierarchical sequence of Morse-Smale complicies for 2 to `nLevels`$+1$ extrema. I.e. from the highest persistence level with a single minimum and maximum to a persitence level with `nLevels`$+1$ extrema

`type`	If 1 use classical persistence for merging based on function value difference at saddle points. For other valuse use R^2 measure, i.e. merge partitions that results in the most increase in adj. R^2 value.
`smooth`	If the data is very noise many extrema are introduced. If `smooth` is set to true the steepest ascent/descent is not computed based on the raw function values y but based on the function value obtained by averaging the function values of the k neareast neighbors. Effectively, a smoothing of the observed function.
`eps`	The knn computation is based on an approximation. The parameter `eps` specifices how close the approximation should be, i.e, the ratio of distance to approximate neareast neighbor to true neareast neigbor is at most $1 + $ `eps` (see the ANN webpage for more details http://www.cs.umd.edu/~mount/ANN/)
`bw`	Bandwidth for kernel density estimation in each partition.
`precompute`	Indicates for each level the SVM should be computed and stored. This is useful for speedup if repeated predictions at different levels are required.
`cost`	Cost for svm for partition classification (see also svm).

An object of class "msc", "msc.kd" or "msc.svn" with the following components:

`level`	Containing the Morse-Smale complex at each persistence level.
`persistence`	Sorted persistence levels at which two extrema merge.
`predictLevel`	For the plot.msc, predict.msc methods the persistence level of the Morse-Smale hierarchy at which prediction/plotting is done
`nLevels`	number of persistence levels computed, if pLevel or pLevelP is specified this will be 1.

with "msc$level" the following components:

`mins`	Indicies into x of mimima for each partition.
`maxs`	Indicies into x of maxmima for each partition.
`partition`	Partition assignment for each observation in x
`partitionSize`	Number of points in each partition

Samuel Gerber

[1] Samuel Gerber and Kristin Potter The Morse-Smale Complex for Data Analysis, Journal of Statistical Software, 2012, vol. 50, no. 2, pp 1-22

[2] Samuel Gerber, Oliver Ruebel Peer-Timo Bremer, Valerio Pascucci, Ross Whitaker, Morse-Smale Regression, Journal of Computational and Graphical Statistics, 2012

[3] Samuel Gerber, Peer-Timo Bremer, Valerio Pascucci, Ross Whitaker, Visual Exploration of High Dimensional Scalar Functions, IEEE Transactions on Visualization and Computer Graphics, vol. 16, no. 6, pp 1271-1280, Nov.-Dec. 2010.

David M. Mount and Sunil Arya ANN library http://www.cs.umd.edu/~mount/ANN/

predict.msc plot.msc msc.lm msc.elnet msc.slm, msc.slm.elnet,

data(fourpeaks)
d <- fourpeaks()

#build Morse-Smale complex of m
ms <- msc.nn(y=d[,1], x=d[, 2:3], pLevel=0.1, knn = 15)
ms.kd <- msc.nn.kd(y=d[,1], x=d[, 2:3], pLevel=0.1, knn = 15, bw=0.1)
ms.svm <- msc.nn.svm(y=d[,1], x=d[, 2:3], pLevel=0.1, knn = 15)

#predict partition assignments
p1 <- predict(ms.kd, d[, 2:3])
p2 <- predict(ms.svm, d[, 2:3])