TD 1 - Clustering via Mode Seeking

The goal of this lab session is to implement the graph-based hill-climbing algorithm of Koontz et al., together with its variant ToMATo based on topological persistence. Both were presented during the lecture.

Graph-based hill-climbing

Class Point

• a field double[] coords, to store the coordinates of the point,
• a method static sqDist(Point p, Point q), which computes the squared Euclidean distance between two points,
• a method toString() for pretty printing on the console... :-)

Point(Scanner sc){
	String line = sc.nextLine();
	String[] tokens = line.replaceFirst("[ |\\t]+", "").split("[ |\\t]+");
	int d = tokens.length;  // number of dimensions
	coords = new double[d];
	for (int i=0; i<d; i++)
		coords[i] = Double.parseDouble(tokens[i]);
}

Class HillClimbing

• static ArrayList<Point> cloud, to store the data points,
• static ArrayList<Integer[]> neighbors, to store the indices of the neighbors the data points in the neighborhood graph (one array Integer[] per data point),
• static ArrayList<Double> density, to store the density values at the data points (one value per data point),
• static ArrayList<Integer> parent, to store the parent of each data point in its cluster tree,
• static ArrayList<Integer> label, to store the cluster label of each data point.

• void readData (String filename), to read the data points from a file,
• void computeNeighbors (int k), to compute and store the k-NN graph of the data points. For this you can apply a naive strategy and compute all the pairwise distances (watch out that a point does not belong to its k-NN set).
• void computeDensity (int k), to compute and store a density estimate at every data point. For this you can use the so-called distance to measure, defined as the average of the squared distances of the data point to its k nearest neighbors. The value of the density estimate is then the inverse of the square root of that quantity:
  
  f(p) = 1 / sqrt(1/k * sum_{q in k-NN(p)} |p-q|^2)
  
• void computeForest (int k), to connect each data point to its parent, which is its neighbor in the k-NN graph with highest density value among the ones with strictly higher density (if they exist) or itself (otherwise).
• void computeLabels(), to extract the clusters' labels from the array of parents. Note that the labels do not have to be contiguous nor to start at 0. Hence, you can simply take the index of the root of the tree for each cluster.

Tests

new ClusteringWindow(cloud, label, neighbors, k);

We recommend you test your code on the data set test first, to have fast runs and easy debugging. Then you can proceed with crater (takes a few dozens of seconds to handle on a decent machine), and then finally spirals (takes about half an hour). Try the following sets of parameters:

// parameters for test.xy
kDensity = 10;
kGraph = 5;

// parameters for crater.xy
kDensity = 50;
kGraph = 15;

// parameters for spirals.xy
kDensity = 100;
kGraph = 30;

ToMATo

• void computePersistence (int k), which sorts the data points by decreasing estimated density values, then computes the 0-dimensional persistence of the superlevel sets of the density estimator via a union-find on the k-NN graph. At this stage you do not have to implement a full-fledged union-find, just use the trees stored in the field parent to do the merges. Whenever a cluster C is to be merged into another cluster C', simply hang the root of the tree of C to the root of the tree of C'.

• computePersistence (int k, double tau), which merges only the clusters whose corresponding density peaks have prominence less than tau.

// parameters for test.xy
String filename = "test.xy";
kDensity = 10;
kGraph = 5;
tau = 0.35;

// parameters for crater.xy
String filename = "crater.xy";
kDensity = 50;
kGraph = 15;
tau = 2;

// parameters for spirals.xy
kDensity = 100;
kGraph = 30;
tau = 0.03;

Optimizations

1. Implement your own data structure for efficient proximity queries, kd-tree for instance. For this you can refer to Section 1 of the following TD from INF562 for building and queryig a kd-tree, and if you have more time you can even do the whole TD which is about Mean-Shift, the other mode-seeking algorithm mentioned in today's lecture. :-)
2. If your data points lie in 2D or 3D, then you can build their Delaunay triangulation. Then, the k-NN of each data point are found among its neighbors, their own neighbors, etc. within the triangulation, hence by a simple graph traversal. For this you can refer to the session on Delaunay triangulations in the course INF562.
3. You can also convert your code to C++ and use one of the existing libraries for NN search, such as ANN (which is based on a variant of the kd-trees and is extremely efficient in low and medium dimensions). This is probably the best option for optimizing this part of you code.