优化子空间的高维聚类算法
摘要:针对当前大多数典型软子空间聚类算法未能考虑簇类投影子空间的优化问题,提出一种新的软子空间聚类算法。该算法将最大化权重之间的差异性作为子空间优化的目标,并提出了一个量化公式。以此为基础设计了一个新的优化目标函数,在最小化簇内紧凑度的同时,优化每个簇所在的软子空间。通过数学推导得到了新的特征权重计算方法,并基于kmeans 算法框架定义了新聚类算法。实验结果表明,所提算法对子空间的优化降低了算法过早陷入局部最优的可能性,提高了算法的稳定性,并且具有良好的性能和聚类效果,适合用于高维数据聚类分析。
关键词:高维数据;聚类;子空间优化;特征权重;差异
中图分类号: tp181
文献标志码:a
0引言
聚类作为数据挖掘研究的一种重要手段,目的是将给定的一个数据集划分成多个簇,使得同一簇内的样本尽量相似,而与其他簇中的样本相异较大[1-2]。目前,聚类分析已经在许多领域获得广泛应用,如模式识别、文本挖掘、机器学习、网络搜索、基因表达、顾客区分和图像处理等。
随着大数据时代的来临,人们在实际应用过程中经常处理的数据不再是几维或几十维的低维数据,而是几百、几千甚至上万维的高维数据。例如,文本挖掘中由向量空间模型(vector space model , vsm)[3]表示的文档向量可能具有几百甚至上千个特征。对于高维数据而言,其数据表现具有以下两方面现象:随着维数的增加,数据索引的维护效率急剧下降[4];在高维空间中数据点之间近似等间距[5]。以上两方面现象泛指高维数据的“维度效应(curse of dimensionality )”。由于传统聚类方法一般使用欧氏距离等函数度量数据之间的相似性,受“维度效应”的影响,传统聚类方法在高维数据中的聚类性能往往大为降低或聚类精度大幅度下降[6]。在2005年10月的ieee 数据挖掘国际会议上,高维数据的处理被认为是当前数据挖掘研究领域中十大挑战性课题之一[7]。
表2和表3列出了5种算法在真实数据集上获得的聚类结果,即各表所列为在相同的初始簇中心及其他环境相同的情况下,各算法在对应数据集上独立运行100次的平均聚类结果,以“均值±1个方差”形式提供。表2和表3所报告的聚类精度均值反映了各个聚类算法的总体性能,而判断各个算法聚类性能的稳定性可以依据所报告的方差。聚类精度方差越小,说明算法聚类性能的稳定性越好。针对表2中所列的每行聚类结果,将最大的指标值加黑显示。
从表2和表3可以看出,与其他4种对比算法相比,soc 算法在大部分真实数据集上均获得较高的聚类结果,尤其在样本数较多的classic4和相对高维的cacmcisi 数据集上,说明新算法对数值型数据集具有良好的适应性。从表2~3中还可以看出,asc 和soc 这两种算法采用不同方式优化子空间,与未考虑子空间优化的软子空间算法相比,它们在大部分数据集上均获得较好的聚类效果,这表明对子空间的优化有助于提升算法的聚类质量。以实验数据集中最高维数据cacmcisi 为例,由于类kmeans 算法容易陷入局部最优[1],使得该类算法的聚类结果容易受初始簇中心的影响,导致聚类结果反差很大。目前,还没有一种有效的机制解决高维数据初始中心点的选择问题。图3给出了cacmcisi 数据集上各算法从100组随机的不同初始状态出发,独立运行后获得的聚类精度分布,横坐标序号代表各算法第几次运行,纵坐标是以fscore 指标衡量各次聚类获得的聚类结果。为了能公平、合理地比较各算法在cacmcisi 数据集上的聚类性能,实验测试中各算法每次执行均选择相同的初始中心。 以上实验结果表明,soc 算法在大部分真实数据集上的聚类结果具有较高的准确性及良好的适应性,这主要来源于算法对子空间的优化。根据soc 算法的执行过程来看,每一次迭
代划分数据集后,soc 算法依据权重计算公式更准确地估计出各簇类所在的子空间,在一定程度上避免了算法过早地陷入局部最优,从而提高了算法的聚类性能。
4结语
针对现有软子空间聚类算法对高维数据聚类效果不佳的现状,本文提出一种新的高维数据软子空间聚类算法(soc )。与目前主要通过模糊加权或熵加权的软子空间聚类算法相比,本文从另一个角度出发,通过分析投影子空间的优化目标并提出一个量化公式,结合子空间中簇内紧凑度的度量,定义了一个新算法。该算法在聚类过程中最小化簇内紧凑度的同时,优化各簇类所在的子空间。经过多个真实数据集的实验验证,与现有其他软子空间聚类算法相比,soc 算法在实验数据上的聚类质量获得较为明显的改善。下一步的主要研究方向是寻找一种能够根据数据集本身离散程度自动确定平衡参数h 的方法及解决高维数据聚类初始簇中心点的选择问题,以进一步提高算法的聚类质量。