An Initial Seed Selection Algorithm for K-means Clustering of
  Georeferenced Data to Improve Replicability of Cluster Assignments for
  Mapping Application
  K-means is one of the most widely used clustering algorithms in various
disciplines, especially for large datasets. However the method is known to be
highly sensitive to initial seed selection of cluster centers. K-means++ has
been proposed to overcome this problem and has been shown to have better
accuracy and computational efficiency than k-means. In many clustering problems
though -such as when classifying georeferenced data for mapping applications-
standardization of clustering methodology, specifically, the ability to arrive
at the same cluster assignment for every run of the method i.e. replicability
of the methodology, may be of greater significance than any perceived measure
of accuracy, especially when the solution is known to be non-unique, as in the
case of k-means clustering. Here we propose a simple initial seed selection
algorithm for k-means clustering along one attribute that draws initial cluster
boundaries along the 'deepest valleys' or greatest gaps in dataset. Thus, it
incorporates a measure to maximize distance between consecutive cluster centers
which augments the conventional k-means optimization for minimum distance
between cluster center and cluster members. Unlike existing initialization
methods, no additional parameters or degrees of freedom are introduced to the
clustering algorithm. This improves the replicability of cluster assignments by
as much as 100% over k-means and k-means++, virtually reducing the variance
over different runs to zero, without introducing any additional parameters to
the clustering process. Further, the proposed method is more computationally
efficient than k-means++ and in some cases, more accurate.
