8 X. Wu et al.
Fig. 2 Effect of an inferior initialization on the k-means results
extent by running the algorithm multiple times with different initial centroids, or by doing
limited local search about the converged solution.
2.2 Limitations
In addition to being sensitive to initialization, the k-means algorithm suffers from several
other problems. First, observe that k-means is a limiting case of fitting data by a mixture of
k Gaussians with identical, isotropic covariance matrices ( = σ
2
I), when the soft assign-
ments of data points to mixture components are hardened to allocate each data point solely
to the most likely component. So, it will falter whenever the data is not well described by
reasonably separated spherical balls, for example, if there are non-covex shaped clusters in
the data. This problem may be alleviated by rescaling the data to “whiten” it before clustering,
or by using a different distance measure that is more appropriate for the dataset. For example,
information-theoretic clustering uses the KL-divergence to measure the distance between two
data points representing two discrete probability distributions. It has been recently shown that
if one measures distance by selecting any member of a very large class of divergences called
Bregman divergences during the assignment step and makes no other changes, the essential
properties of k-means, including guaranteed convergence, linear separation boundaries and
scalability, are retained [3]. This result makes k-means effective for a much larger class of
datasets so long as an appropriate divergence is used.
123
我的内容管理
展开
