utils.epsilon_graph¶

utils.epsilon_graph(X, epsilon=None, percentile=0.05)

Construct an epsilon-neighborhood graph, represented by an adjacency list. Two vertices are connected by an edge if they are within ‘epsilon’ distance of each other, according to the Euclidean metric. The implementation is a brute-force computation of all O(n^2) pairwise distances of the rows in X.

Parameters: X : 2D numpy array The rows of ‘X’ are the observations which become graph vertices. epsilon : float, optional The distance threshold for neighbors. percentile : float, optional If ‘epsilon’ is unspecified, this determines the distance threshold. ‘epsilon’ is set to the desired percentile of all (n choose 2) pairwise distances, where n is the number of rows in ‘X’. neighbors : numpy array Each row contains the nearest neighbors of the corresponding row in ‘X’, indicated by row indices.

Examples

>>> X = numpy.random.rand(100, 2)
>>> neighbors = debacl.utils.epsilon_graph(X, epsilon=0.2)