K-search: Searching for clusters

This paper introduces the K-search algorithm, a method for locating an unknown number of well-separated multidimensional clusters from sampled data in the presence of outliers. K-search finds tightly packed point clouds, a characteristic of Gaussian data close to a mean value, to identify potential Gaussian means. Using this search strategy, the approximate locations of cluster means are found, automatically providing an estimate for the number of clusters, K. In experimental results,K-search can effectively identify the true number of well-separated Gaussian clusters and their locations in the presence of random background clutter (outliers). We use K-search to identify modal driving behaviors in a real vehicle track dataset in the presence of noisy tracks, and we compare results to other model based clustering methods that automatically determine K.