基于标签传播的半监督聚类算法研究

发布时间：2021-11-22 16:33

　　聚类分析是数据挖掘中的一项重要技术,已被用来探索实际应用中各种数据的潜在类结构。由于数据的复杂性,聚类结果并不一定能满足用户期望。半监督聚类利用少量的先验信息指导聚类过程,使得聚类结果尽可能的满足用户期望。本文以如何利用和传播先验信息为主题,针对标签传播算法和成对约束的扩充算法进行了系统的研究,主要研究内容如下:（1）本文对标签传播算法进行了扩展,提出了基于成对约束的标签传播算法。在该算法中,我们将先验信息保存到成对关系矩阵中,并且通过计算成对关系与聚类结果之间的差异来代替划分矩阵之间的差异。同时,我们通过构建一种新的最优化模型,将标签传播算法的最优化问题转化为谱聚类问题,并通过特征值分解方法得到最优解。该算法不仅可以解决标签传播过程中存在的非对齐问题,同时还可以处理成对约束先验信息。最后,将该算法与8种半监督聚类算法在11个基准数据集上进行了比较。实验结果表明,所提出的算法相比其他算法更有效。（2）成对约束的数量是影响半监督聚类结果有效性的重要因素。然而,在现实应用中,成对约束的获取需要耗费大量的成本。因此,本文提出了一种基于安全性的成对约束扩充方法。该算法通过统计传递闭包中最大局部... 

【文章来源】：山西大学山西省

【文章页数】：65 页

【学位级别】：硕士

【部分图文】：

类标签和簇标签之间存在的非对齐现象

基于标签传播的半监督聚类算法研究8根据以上，和的定义，我们可以按照先验信息类型的不同来定义成对关系矩阵，如下所示：={,先验信息为正标签,11(),先验信息为负标签,,先验信息为成对约束,(2-9)其中和11()分别是和的成对关系表示，表示数据集的聚类数量。由于仅根据两个数据对象的负标签无法判断两个数据对象是否属于同一类。因此，我们使用11来反映两个数据对象属于同一类的概率。根据成对关系矩阵的定义，我们重新定义了标签传播算法的代价函数′()如下所示：′()=‖‖2,(2-10)其中是的成对关系表示，′()表示预先给定的成对关系和聚类得到的成对关系之间存在的差异。新的代价函数可以解决预先给定的类标签和聚类得到的簇标签之间存在的非对齐问题。延续图2.1中的示例，在图2.2中我们展示了新代价函数′()的优势。由图2.2可知，完全等价于。因此使用成对关系矩阵可以克服非对齐问题。图2.2将划分矩阵转化为成对关系矩阵的过程此外，我们修改了标签传播算法的最优化问题，如下所示：

第二章基于成对约束的标签传播算法13聚类性能的影响。在分析中，我们考虑了三种情况，即正标签，成对约束，正负标签分别作为先验信息时算法的聚类性能。我们将约束的数量固定为25%，其中对应数据集中数据对象的数量。我们以0.1为步长在[0,1]区间内测试了不同值所对应提出算法的聚类结果。根据这些图可以发现，参数对不同数据集的影响是不同的。这表明很难为每个数据集选择合适的来执行所提出的算法。为了进一步分析参数的影响，我们在图2.4和图2.6中展示了每个值对算法在所有测试的数据集上得到的平均评价指标。根据平均线我们可以发现当在某种程度上增加时，所提出算法的平均聚类性能相对稳定。(a)正标签为先验信息(b)成对约束为先验信息(c)正负标签为先验信息图2.3参数对NLPPC算法NMI值的影响(a)正标签为先验信息(b)成对约束为先验信息(c)正负标签为先验信息图2.4参数在所有数据集上对NLPPC算法NMI平均值的影响(a)正标签为先验信息(b)成对约束为先验信息(c)正负标签为先验信息图2.5参数对NLPPC算法ARI值的影响

【参考文献】：
期刊论文
[1]密度敏感的半监督谱聚类[J]. 王玲,薄列峰,焦李成.  软件学报. 2007(10)



本文编号：3512067