msr (version 0.4.4)

msc.nn: Nearest Neighbor Morse Smale Complex

Description

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/).

Usage

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)

Arguments

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).

Value

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

References

[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/

See Also

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

Examples

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])