engleski

Interpretation and optimization of the k-means algorithm

The paper gives a new interpretation and a possible optimization of the well known k-means algorithm for searching for a locally optimal partition of the set A={; ; 𝑎_𝑖 ⋲Rn: 𝑖=1, …, 𝑚}; ; which consists of k disjoint non empty subsets 𝜋1, , ..𝜋𝑘, 1≤k≤m. For this purpose, a new divided k-means algorithm was constructed as a limit case of the known smoothed k-means algorithm. It is shown that the algorithm constructed in such way coincides with the k-means algorithm if during the iterative procedure no data points appear in the Voronoi diagram. If in the partition obtained by applying the divided k-means algorithm there are data points lying in the Voronoi diagram, it is shown that the obtained result can be improved further.

Clustering; Data mining; k-means; Voronoi diagram

nije evidentirano