Title: Fast kNN mode seeking clustering applied to active learning,
Abstract: A significantly faster algorithm is presented for the original kNN mode
seeking procedure. It has the advantages over the well-known mean shift
algorithm that it is feasible in high-dimensional vector spaces and results in
uniquely, well defined modes. Moreover, without any additional computational
effort it may yield a multi-scale hierarchy of clusterings. The time complexity
is just O(n^1.5). resulting computing times range from seconds for 10^4 objects
to minutes for 10^5 objects and to less than an hour for 10^6 objects. The
space complexity is just O(n). The procedure is well suited for finding large
sets of small clusters and is thereby a candidate to analyze thousands of
clusters in millions of objects.
The kNN mode seeking procedure can be used for active learning by assigning
the clusters to the class of the modal objects of the clusters. Its feasibility
is shown by some examples with up to 1.5 million handwritten digits. The
obtained classification results based on the clusterings are compared with
those obtained by the nearest neighbor rule and the support vector classifier
based on the same labeled objects for training. It can be concluded that using
the clustering structure for classification can be significantly better than
using the trained classifiers. A drawback of using the clustering for
classification, however, is that no classifier is obtained that may be used for
out-of-sample objects.