关键词: 方差, 标准差, 邻域, 初始聚类中心, K-medoids聚类

Abstract: To overcome the deficiencies of fast K-medoids clustering algorithm of its computational load in computing the density of points and its initial seeds may locating in a same cluster, and to overcome the disadvantages of neighborhood-based K-medoids algorithm of its arbitrary in selecting a coefficient to adjust the radius of its neighborhood, this paper proposes two new variance based K-medoids clustering algorithms. These new algorithms respectively choose the mean distance between instances and the standard deviation of a specific instance as the radius of a neighborhood, and select the instances with minimum variance as initial seeds one by one where the distance between initial seeds is at least the radius of the neighborhood, so that the expected number of initial seeds have been got. This paper tests the proposed algorithms on the real datasets from UCI machine learning repository and on the synthetically generated datasets, and compares their performance in terms of many popular criteria for clustering. The experimental results demonstrate that the proposed new K-medoids clustering algorithms can obtain better clustering in short time, and they are scalable to cluster a comparable large scale dataset.

Key words: variance, standard deviation, neighborhood, initial seeds; K-medoids clustering