论文部分内容阅读
聚类分析作为数据挖掘的一个重要研究领域,可以有效地帮助我们分析数据的分布、了解数据的特征、确定所感兴趣的数据类,寻找隐藏在数据中的结构,以便作进一步分析和利用。本文针对现有某些聚类算法存在的不足,结合粒子群优化等方法对现有某些聚类算法存在的需要人工设置算法初始参数及提高聚类性能等问题进行了探讨并提出了解决方案。研究了成对约束先验信息如何扩展和指导聚类以提高聚类质量。针对文本数据高维稀疏的特性,对如何提高文本聚类效果进行了研究。本文研究具有一定的理论研究价值与现实的应用意义。具体研究内容包括以下几个方面:1)提出了一种简单有效的粒子编码方法,采用新的粒子编码方法的粒子群优化K均值算法有效地解决了已有粒子群优化聚类算法当样本维数较大及样本各维的取值范围变化较大时,造成粒子群搜索空间过大,在有限次迭代搜索时影响算法的收敛速度和聚类效果,且在搜索过程中样本各维的值在一定范围内变化时可能会取到不符合样本实际情况的数值而出现空簇的情况等问题。当数据集较大时,通过将凝聚层次聚类、K均值算法与粒子群优化有机结合提出了一种两阶段混合聚类方法,通过凝聚层次聚类获得若干纯度较高的子簇作为下一阶段粒子群优化聚类的初始聚类中心搜索空间,并引入混沌思想保持粒子群的多样性,以避免粒子群优化算法可能出现的早熟现象。在多个UCI数据集和文本数据集上的实验结果表明新方法对初始聚类中心敏感性较小、收敛速度快、能有效抑制早熟现象,聚类结果的精度和稳定性显著增加。2)提出了一种利用粒子群优化自动搜索合适的算法初始参数,同时获得对应的聚类划分的方法,解决了一些聚类算法需要人工设定初始参数,而参数选择不当将严重影响聚类性能的问题。通过将模糊C均值算法(FCM)与粒子群优化有机结合,同时对初始聚类中心和加权指数m进行编码与搜索,解决了FCM算法对初始聚类中心敏感和需要人工设置加权指数m值的问题。DBSCAN算法能够发现任意形状的类簇,但对邻域半径Eps与邻域内样本数MinPts这两个输入参数敏感。根据DBSCAN类簇扩展的特点,以DBSCAN聚类结果类簇数目与输入的预期聚类个数的符合情况作为粒子群优化适应度值,通过粒子群优化搜索,寻找最优的Eps值,同时生成预期聚类个数的聚类划分结果,解决了DBSCAN算法对输入参数Eps与MinPts敏感的问题。在已有的粒子群优化聚类算法和聚类有效性指标研究的基础上,设计了一个基于粒子群优化聚类的聚类有效性验证框架,同时对聚类个数和初始聚类中心进行编码,将聚类有效性函数作为粒子群优化适应度函数进行自动搜索,能自动确定聚类划分的最佳类簇数目,同时可以用于对不同的聚类有效性指标进行测试比较。在多个UCI数据集上比较了Sil、DB和IGP等聚类有效性指标的性能。3)提出了一种半监督粒子群优化聚类算法。采用改进的Floyd最短路径算法对初始加入的Must-link和Cannot-link成对约束信息同时进行扩展,用扩展后的成对约束信息对相异度矩阵中相关样本间的相异度值进行修正,结合简化的粒子编码方法和融合先验信息的相异度矩阵进行粒子群优化聚类,最后将样本间的成对约束信息融合在聚类结果适应度函数的计算中,根据聚类结果中违反成对约束的情况来指导粒子群优化搜索。在多个UCI数据集上的实验结果表明本方法加入少量的成对约束先验信息就能获得聚类准确率的较大提升,聚类效果优于半监督近邻传播算法。4)提出了一种新的初始聚类中心选择方法。通过在聚类过程中动态统计已划分和未划分的数据集合的相关信息,将这些统计信息应用到下一步类簇的划分中,逐步探测数据集中未划分归属类簇部分的相对密集区域,若此密集区域与已划分类簇覆盖度小于一定阈值,则将此区域作为一个初始聚类中心。寻找到K个初始聚类中心集合后,将剩余未划分的数据划分到最相似的类簇中,最后通过准则函数对聚类结果进行进一步优化。目前典型的聚类算法都需要不同程度人工选择阈值,而阈值选择的优劣将直接影响聚类效果。本文提出的文本聚类算法中阈值均通过在聚类过程中对数据集划分情况进行动态统计得到,避免了根据经验对不同数据集阈值设定的盲目性。该方法能够很好地排除类边缘点和噪声点的影响,能够适应数据集中各个实际类别大小及密度分布不平衡的情况。与著名的CLUTO聚类工具集的比较实验表明该方法在不同数据集上聚类效果更好,鲁棒性更强。在提出的文本聚类算法基础上进一步研究了将成对约束监督信息进行扩展并指导文本聚类,提出了一种半监督文本聚类方法。通过将成对约束嵌入文档相似度矩阵,在初始聚类中心选择、剩余文档划分及聚类结果优化过程中充分利用成对约束先验信息改进文本聚类效果。