基于Nystrm密度值逼近的减法聚类  

Density value approximation for subtractive clustering based on Nystrm method

作　　者：孙志海[1] 孔万增[1] 

机构地区：[1]杭州电子科技大学计算机学院,杭州310018

出　　处：《中国图象图形学报》2013年第7期790-798,共9页Journal of Image and Graphics

基　　金：国家自然科学基金项目(61102028);浙江省自然科学基金项目(Y1100086)

摘　　要：针对大规模数据集减法聚类时间复杂度高的问题,提出一种基于Nystrm密度值逼近的减法聚类方法。特别适用于大规模数据集的减法聚类问题,可极大程度降低减法聚类的时间复杂度。基于Nystrm逼近理论,结合经典减法聚类样本密度值计算的特点,巧妙地将Nystrm理论用于减法聚类未采样样本之间密度权值矩阵的逼近,从而实现了对所有样本的密度值逼近,最后沿用经典减法聚类修正样本密度值的方法,实现整个减法聚类过程。将本文算法在人工数据、标准彩色图像及UCI数据集上进行了实验,详细说明了本文算法利用少数采样样本逼近多数未采样样本密度权值、密度值以及进行减法聚类的详细过程,并给出了聚类准确率、耗时及算法性能加速比。实验结果表明,与经典的减法聚类相比,本文算法在不影响聚类结果的情况下,对于较大规模数据集,可显著降低减法聚类的时间复杂度,极大程度地提高减法聚类的实时性能。Subtractive clustering based methods have been well known for data clustering problems. However, due to the computational demands of these approaches, clustering for large scale datasets, such as spatio-temporal data and images, have been slow to appear. A novel subtractive clustering method based on Nystrom approximation is proposed. The pro- posed method is based on the famous Nystrom method. Combined with the density value computation characteristics for each sample of the classical subtractive clustering method, we apply Nystrom theory to approximate the density value for each da- ta point which has not been sampled. Finally, we complete the whole clustering procedure using classical subtractive cluste- ring method in modifying the density values in each circulation. The proposed method substantially reduces the computa- tional requirements of subtractive clustering based algorithms, making it feasible to use subtractive clustering to large scale subtraetive clustering problems. Density value of samples could be approximated quickly using only a small number of sam- ples. The experiment results on artificial datasets, color images, and UCI machine learning repository show efficiency in comparing with classical subtractive clustering method.

关 键 词：减法聚类 Nystrom 密度值逼近 时间复杂度 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]