面向大规模数据的快速多代表点仿射传播算法

针对原始的仿射传播(affinity propagation,AP)聚类算法难以处理多代表点聚类,以及空间和时间开销过大等问题,提出了快速多代表点仿射传播(multi-exemplar affinity propagation using fast reduced set density estimator,FRSMEAP)聚类算法。该算法在聚类初始阶段,引入快速压缩集密度估计算法(fast reduced set density estimator,FRSDE)对大规模数据集进行预处理,得到能够充分代表样本属性的压缩集;在聚类阶段,使用多代表点仿射传播(multi-exemplar affinity propagation,MEAP)聚类算法,获得比AP更加明显的聚类决策边界,从而提高聚类的精度;最后再利用K-邻近(K-nearest neighbor,KNN)算法分配剩余点得到最终的数据划分。在人工数据集和真实数据集上的仿真实验结果表明,该算法不仅能在大规模数据集上进行聚类,而且具有聚类精度高和运行速度快等优点。     

一种基于同类约束的半监督近邻反射传播聚类方法

以近邻反射传播 (Affinity propagation, AP) 聚类算法为基础, 提出了一种基于同类约束的半监督近邻反射传播聚类方法 (Semi-supervised affinity propagation clustering method with homogeneity constraints, HCSAP).该方法在聚类目标函数中引入同类约束项, 以保证聚类结果与同类集先验信息一致.利用最大和信任传播 (Max-sum belief propagation) 优化过程对目标函数进行求解, 导出同类约束下的吸引度 (Responsibility) 和归属度 (Availability) 的迭代方程.人工数据集和真实数据集上的实验结果表明本文所提方法的有效性.     

迁移近邻传播聚类算法

在目标域可利用数据匮乏的场景下,传统聚类算法的性能往往会下降.在该场景下,通过抽取源域中的有用知识用于指导目标域学习以得到更为合适的类别信息和聚类性能,是一种有效的学习策略.借此提出一种基于近邻传播的迁移聚类（transfer affinity propagation,简称TAP）算法,在源域和目标域数据分布相似的情况下,通过引入迁移学习机制来改善近邻传播聚类（affinity propagation,简称AP）算法在数据匮乏场景下的聚类性能.为保证迁移的有效性,TAP在综合考虑源域和目标域的统计特性及几何特征的基础上改进AP算法中的消息传递机制使其具备迁移能力,从而达到辅助目标域学习的目的.此外,通过TAP对应的因子图,亦可说明TAP可以以类似AP的消息传递机制,在目标域数据匮乏的情况下进行高效的知识迁移,为最终所获得的聚类结果提供了保证.在模拟数据集和真实数据集上的仿真实验结果显示,所提出的算法较之经典AP算法在处理非充分数据聚类任务时具有更佳的性能.     

基于近邻传播算法的半监督聚类

提出了一种基于近邻传播(affinity propagation,简称AP)算法的半监督聚类方法.AP是在数据点的相似度矩阵的基础上进行聚类.对于规模很大的数据集,AP算法是一种快速、有效的聚类方法,这是其他传统的聚类算法所不能及的,比如:K中心聚类算法.但是,对于一些聚类结构比较复杂的数据集,AP算法往往不能得到很好的聚类结果.使用已知的标签数据或者成对点约束对数据形成的相似度矩阵进行调整,进而达到提高AP算法的聚类性能.实验结果表明,该方法不仅提高了AP对复杂数据的聚类结果,而且在约束对数量较多时,该方法要优于相关比对算法.     

基于文本双表示模型的微博热点话题发现

微博作为当代生活中信息传播的重要平台,对其进行热点话题挖掘成为当今重要的研究方向之一。针对传统的热点话题发现方法在处理微博文本时存在文本表示缺乏语义信息、挖掘热点话题效果差等问题,本文提出一种基于频繁词集和BERT语义的文本双表示模型（Text dual representation model based on frequent word sets and BERT semantics, FWS-BERT）,通过该模型计算加权文本相似度对微博文本进行谱聚类,进一步基于改进相似性度量的affinity propagation (AP)聚类算法进行微博话题挖掘,最后通过引入文献计量学中的H指数提出一种话题热度评估方法。实验表明,本文提出的方法在轮廓系数及Calinski-Harabasz（CH）指标值上均高于基于频繁词集的单一文本表示方法和K-means方法,并且能准确地对微博数据进行话题表示和热度评估。     

属性样本同步粒化的AP熵加权软子空间聚类算法

仿射传播（Affinity propagation,AP）聚类算法是将所有待聚类对象作为潜在的聚类中心,通过对象之间传递的可靠性和有效性信息找到合适的聚类中心,从而计算出相应的聚类结果,但不适用子空间聚类。将粒度计算引入到仿射传播聚类算法中,提出属性与样本同步粒化的AP熵加权软子空间聚类算法（Entropy weighting AP algorithm for subspace clustering based on asynchronous granulation of attributes and samples,EWAP）。EWAP首先去除冗余属性,然后在每次聚类的迭代过程中修改属性的权重值。在满足一定条件迭代终止时,就会得到构成各兴趣度子空间的属性权重值,从而得到属性集的粒化结果以及相应的子空间聚类结果 。理论与实验证明EWAP算法既保留了AP算法的优点,又克服了该聚类算法不能进行子空间聚类的不足。     

基于MapReduce的分布式近邻传播聚类算法

随着信息技术迅速发展,数据规模急剧增长,大规模数据处理非常具有挑战性.许多并行算法已被提出,如基于MapReduce的分布式K平均聚类算法、分布式谱聚类算法等.近邻传播(affinity propagation,AP)聚类能克服K平均聚类算法的局限性,但是处理海量数据性能不高.为有效实现海量数据聚类,提出基于MapReduce的分布式近邻传播聚类算法——DisAP.该算法先将数据点随机划分为规模相近的子集,并行地用AP聚类算法稀疏化各子集,然后融合各子集稀疏化后的数据再次进行AP聚类,由此产生的聚类代表作为所有数据点的聚类中心.在人工合成数据、人脸图像数据、IRIS数据以及大规模数据集上的实验表明:DisAP算法对数据规模有很好的适应性,在保持AP聚类效果的同时可有效缩减聚类时间.     

多维空间可调整的近邻传播聚类算法*

针对近邻传播算法不适合处理多重尺度和任意形状数据的问题,提出了一种基于多维空间可变换的MSAAP(multidimensional similarity adaptive affinity propagation)算法。首先,通过熵值法计算数据样本点的属性权重;然后,根据属性权重构造出一种新型计算相似性矩阵的方法;最后,根据属性权重的优先级将样本点的空间划分成若干个空间块,并计算空间块的吸引度和归属度之和,进而调整样本点的空间分布。通过13个不同形状的UCI数据集和3个人脸数据库进行对比实验,从准确率、算法时间、聚类个数3个维度去分析,最终实验结果证明所提出的MSAAP算法聚类效果更优。     

基于密度与近邻传播的数据流聚类算法

针对现有算法聚类精度不高、处理离群点能力较差以及不能实时检测数据流变化的缺陷,提出一种基于密度与近邻传播融合的数据流聚类算法.该算法采用在线/离线两阶段处理框架,通过引 入微簇衰减密度来精确反映数据流的演化信息,并采用在线动态维护和删减微簇机制,使算法模型更 符合原始数据流的内在特性.同时,当模型中检测到新的类模式出现时,采用一种改进的加权近邻传播聚类（Weighted and hierarchical affinity propagation,WAP）算法对模 型进行重建,因而能够实时检测到数据流的变化,并能给出任意时间的聚类结果.在真实数据集和人工 数据集上的实验表明,该算法具有良好的适用性、有效性和可扩展性,能够取得较好的聚类效果.     

基于消息传递的谱聚类算法

谱聚类将数据聚类问题转化成图划分问题,通过寻找最优的子图,对数据点进行聚类。谱聚类的关键是构造合适的相似矩阵,将数据集的内在结构真实地描述出来。针对传统的谱聚类算法采用高斯核函数来构造相似矩阵时对尺度参数的选择很敏感,而且在聚类阶段需要随机确定初始的聚类中心,聚类性能也不稳定等问题,本文提出了基于消息传递的谱聚类算法。该算法采用密度自适应的相似性度量方法,可以更好地描述数据点之间的关系,然后利用近邻传播（Affinity propagation,AP）聚类中“消息传递”机制获得高质量的聚类中心,提高了谱聚类算法的性能。实验表明,新算法可以有效地处理多尺度数据集的聚类问题,其聚类性能非常稳定,聚类质量也优于传统的谱聚类算法和k-means算法。