Hi All,
In constructing the kNN graph in project 2, one needs to chose a weight kernel (e.g. the Gaussian or the algebraic kernels) to convert distances (dissimilarities) to edge weights (similarity). Here are some tips in the construction:
Tips 1 (choice of hyper parameter):
Consider Gaussian kernel as example, the choice of sigma (SD of the Gaussian) can significantly affect the resulting kNN graph. A too large sigma results in weights all having the same value, whereas a too small sigma results in extremely small weights for most kNN edges. Here is one possible choice of sigma: construct the histogram (i.e. distribution) of the kNN distances, and set sigma to the median of the distribution of the kNN distances. Can you see why this could prevent sigma be too large or to small?
Tips 2 (Monitor the distribution of the kNN distances and edge weights):
Always monitor the kNN-distance distribution (to ensure there are not too many short cuts for a given k, the existence of outliers and background noise points, etc.), and the edge-weight distribution (to ensure that the small amount of long edges (short cuts) connecting faraway clusters do not have too small weights due to e.g, the use of Gaussian kernel, etc.)
Tips 3: (Choice of k and sigma)
The choice of k only depends on whether the whole kNN graph is a single connected component, so the fixing of k only need the adjacency matrix with 1 and 0 as elements, and the edge weights are not needed. Therefore, the fixing of k and sigma should be carried out sequentially, i.e, first find k, then for the chosen k, fix sigma using the tips 1 and 2 above, instead of performing a grid search of k and sigma simultaneously.
Best,
Chun
Best,
Chun