TY - GEN

T1 - A pillar algorithm for k-means optimization by distance maximization for initial centroid designation

AU - Barakbah, Ali Ridho

AU - Kiyoki, Yasushi

PY - 2009/7/20

Y1 - 2009/7/20

N2 - Clustering performance of the K-means greatly relies upon the correctness of the initial centroids. Usually the initial centroids for the K-means clustering are determined randomly so that the determined centroids may reach the nearest local minima, not the global optimum. This paper proposes a new approach to optimizing the designation of initial centroids for K-means clustering. This approach is inspired by the thought process of determining a set of pillars' locations in order to make a stable house or building. We consider the pillars' placement which should be located as far as possible from each other to withstand against the pressure distribution of a roof, as identical to the number of centroids amongst the data distribution. Therefore, our proposed approach in this paper designates positions of initial centroids by using the farthest accumulated distance between them. First, the accumulated distance metric between all data points and their grand mean is created. The first initial centroid which has maximum accumulated distance metric is selected from the data points. The next initial centroids are designated by modifying the accumulated distance metric between each data point and all previous initial centroids, and then, a data point which has the maximum distance is selected as a new initial centroid. This iterative process is needed so that all the initial centroids are designated. This approach also has a mechanism to avoid outlier data being chosen as the initial centroids. The experimental results show effectiveness of the proposed algorithm for improving the clustering results of K-means clustering.

AB - Clustering performance of the K-means greatly relies upon the correctness of the initial centroids. Usually the initial centroids for the K-means clustering are determined randomly so that the determined centroids may reach the nearest local minima, not the global optimum. This paper proposes a new approach to optimizing the designation of initial centroids for K-means clustering. This approach is inspired by the thought process of determining a set of pillars' locations in order to make a stable house or building. We consider the pillars' placement which should be located as far as possible from each other to withstand against the pressure distribution of a roof, as identical to the number of centroids amongst the data distribution. Therefore, our proposed approach in this paper designates positions of initial centroids by using the farthest accumulated distance between them. First, the accumulated distance metric between all data points and their grand mean is created. The first initial centroid which has maximum accumulated distance metric is selected from the data points. The next initial centroids are designated by modifying the accumulated distance metric between each data point and all previous initial centroids, and then, a data point which has the maximum distance is selected as a new initial centroid. This iterative process is needed so that all the initial centroids are designated. This approach also has a mechanism to avoid outlier data being chosen as the initial centroids. The experimental results show effectiveness of the proposed algorithm for improving the clustering results of K-means clustering.

UR - http://www.scopus.com/inward/record.url?scp=67650501922&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67650501922&partnerID=8YFLogxK

U2 - 10.1109/CIDM.2009.4938630

DO - 10.1109/CIDM.2009.4938630

M3 - Conference contribution

AN - SCOPUS:67650501922

SN - 9781424427659

T3 - 2009 IEEE Symposium on Computational Intelligence and Data Mining, CIDM 2009 - Proceedings

SP - 61

EP - 68

BT - 2009 IEEE Symposium on Computational Intelligence and Data Mining, CIDM 2009 - Proceedings

T2 - 2009 IEEE Symposium on Computational Intelligence and Data Mining, CIDM 2009

Y2 - 30 March 2009 through 2 April 2009

ER -