论文部分内容阅读
近邻传播算法(AP)是近年出现的一种在数据挖掘领域极具竞争力的聚类算法,相比较于传统聚类算法,AP算法能够在较短时间内完成大规模多类别数据集的聚类,且该算法能够很好地解决非欧空间问题。因此,AP算法自提出以来,受到了广泛的关注和应用。尽管如此,AP算法仍然存在两个主要缺陷:1)AP算法只适合处理紧致的超球形结构的数据聚类问题,当数据集分布松散或结构复杂时,该算法不能给出理想的聚类结果;2)AP算法是一种无监督的学习方法,不能直接适用于有约束条件的聚类问题。本文针对上述问题展开专门研究。论文从改进相似度矩阵入手,首先针对部分聚类数据密度不同以及线性不可分的问题,提出核共享近邻传播(KSAP)算法;进而针对任意形状任意结构的簇的聚类问题,提出基于流形距离的近邻传播(APMD)算法和混合核模型的APMD算法(MKAPMD);最后,针对约束聚类问题,提出基于成对约束的半监督近邻传播(SAP-PC)算法。本文的主要创新点包括:1)提出核共享近邻传播算法。针对传统基于欧式距离的相似性度量只能聚类紧致结构数据集的缺点,利用数据间共享最近邻数量对局部密度不敏感的特性,设计了一种基于高斯核的共享近邻相似性度量,并据此提出了核共享近邻传播算法。仿真结果证明:该算法能够解决密度不均匀和部分简单线性不可分的数据集聚类问题。2)提出基于流形距离的近邻传播算法。针对现有AP算法只能发现超球形聚类的缺点,依据聚类的局部一致性和全局一致性假设,设计了一种局部保持的流形距离度量方法,据此提出了APMD算法,该算法可以发现任意形状的类簇。在此基础上提出了一种快速APMD算法,该算法在保持聚类性能的同时大大提高了算法运算速度。仿真结果证明:所提算法有效解决了非凸形数据集聚类问题。3)提出混合核模型的APMD算法。针对单核模型的APMD算法不适合混合分布的数据集聚类问题,提出了混合核模型的APMD算法。根据数据的流形结构信息建立多核模型,并利用流形边界自动调整核参数,通过多个核函数更好地拟合数据集结构。仿真结果证明:该算法能够解决多种流形混叠的数据集聚类问题,拓宽了近邻传播算法的应用范围。4)提出基于成对约束的半监督近邻传播算法。针对AP算法无法直接适用于有约束条件的聚类问题,提出了SAP-PC算法。在流形距离矩阵的基础上,利用成对约束的传播特性使约束在特征空间传播开来,并通过修改距离矩阵的方法将其展现,从而解决了约束条件对近邻传播算法应用的限制。此外,通过对成对约束进行开操作和闭操作选出闭包中心,用闭包中心代替约束对,从而解决了成对约束的违反问题。仿真结果证明:该算法可以有效提高聚类精度。