Adaptive Initialization Method for K-means Algorithm
  The K-means algorithm is a widely used clustering algorithm that offers
simplicity and efficiency. However, the traditional K-means algorithm uses the
random method to determine the initial cluster centers, which make clustering
results prone to local optima and then result in worse clustering performance.
Many initialization methods have been proposed, but none of them can
dynamically adapt to datasets with various characteristics. In our previous
research, an initialization method for K-means based on hybrid distance was
proposed, and this algorithm can adapt to datasets with different
characteristics. However, it has the following drawbacks: (a) When calculating
density, the threshold cannot be uniquely determined, resulting in unstable
results. (b) Heavily depending on adjusting the parameter, the parameter must
be adjusted five times to obtain better clustering results. (c) The time
complexity of the algorithm is quadratic, which is difficult to apply to large
datasets. In the current paper, we proposed an adaptive initialization method
for the K-means algorithm (AIMK) to improve our previous work. AIMK can not
only adapt to datasets with various characteristics but also obtain better
clustering results within two interactions. In addition, we then leverage
random sampling in AIMK, which is named as AIMK-RS, to reduce the time
complexity. AIMK-RS is easily applied to large and high-dimensional datasets.
We compared AIMK and AIMK-RS with 10 different algorithms on 16 normal and six
extra-large datasets. The experimental results show that AIMK and AIMK-RS
outperform the current initialization methods and several well-known clustering
algorithms. Furthermore, AIMK-RS can significantly reduce the complexity of
applying it to extra-large datasets with high dimensions. The time complexity
of AIMK-RS is O(n).
