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

作者：孙志海; 孔万增

来源：中国图象图形学报, 2013, (07): 790-798.

• 减法聚类
• Nystrm
• 密度值逼近
• 时间复杂度 subtractive clustering
• Nystrm
• density value approximation
• time complexity

针对大规模数据集减法聚类时间复杂度高的问题,提出一种基于Nystrm密度值逼近的减法聚类方法。特别适用于大规模数据集的减法聚类问题,可极大程度降低减法聚类的时间复杂度。基于Nystrm逼近理论,结合经典减法聚类样本密度值计算的特点,巧妙地将Nystrm理论用于减法聚类未采样样本之间密度权值矩阵的逼近,从而实现了对所有样本的密度值逼近,最后沿用经典减法聚类修正样本密度值的方法,实现整个减法聚类过程。将本文算法在人工数据、标准彩色图像及UCI数据集上进行了实验,详细说明了本文算法利用少数采样样本逼近多数未采样样本密度权值、密度值以及进行减法聚类的详细过程,并给出了聚类准确率、耗时及算法性能加速比。实验结果表明,与经典的减法聚类相比,本文算法在不影响聚类结果的情况下,对于较大规模数据集,可显著降低减法聚类的时间复杂度,极大程度地提高减法聚类的实时性能。

• 单位
  杭州电子科技大学