基于共协关系矩阵的聚类集成算法研究
发布时间：2020-12-16 05:56
聚类分析作为数据挖掘领域的重要研究方向之一,已经受到研究者的广泛关注。近年来,许多有效的聚类算法已经被提出,并且在数据聚类上表现出很好的性能,但是单个聚类算法很难适应复杂结构的数据。为了解决这一问题,聚类集成被提出并得到快速发展。聚类集成的目标是通过集成多个基聚类结果提高聚类算法的稳定性、鲁棒性以及精度。在众多的聚类集成方法中,基于共协关系矩阵的聚类集成是一个重要的研究方向,也是该领域研究热点之一。因此,本文选择基于共协关系矩阵的聚类集成为对象开展研究工作,主要研究内容如下:（1）提出了基于样本对加权共协关系矩阵的聚类集成算法。该算法利用k-means算法产生多个基聚类,然后对于基聚类中的每个类再利用k-means算法产生多个样本簇,并通过去掉某个样本对所在样本簇后类的不确定性变化程度,评价共协关系矩阵中该对样本的重要性,实现基于样本对加权共协关系矩阵的聚类集成,实验结果表明了提出算法的有效性。（2）提出了基于度量学习的聚类集成算法。该算法利用共协关系矩阵构造样本对之间的必连约束集合和勿连约束集合,并给出相应的度量学习算法,进而根据学得的度量产生新的基聚类,再利用基聚类构造新的共协关系...
【文章来源】：山西大学山西省
【文章页数】：57 页
【学位级别】：硕士
【部分图文】：
聚类集成过程示意图
基于共协关系矩阵的聚类集成算法研究8个类中，值为1，否则，值为0，ijm代表着对象ix和对象jx在这M个基聚类中出现的频率。图2.2举例简单解释共协关系矩阵是如何得到的。图2.2两个基聚类结果及其对应的共协关系矩阵EAC算法描述如下：算法2.1：EAC算法输入：数据集},...,,{21nxxxX，聚类个数K输出：将数据集X划分成K个簇的结果；步骤1：在数据集X上利用k-means算法得到M个基聚类结果；步骤2：利用公式(2.1)得到共协关系矩阵；步骤3：通过层次聚类算法得到最后的聚类结果。(2)基于图的聚类集成基于图的聚类集成[14-18]将得到的基聚类结果构造成图，利用图聚类的算法来得到最后的聚类结果。Strehl等人[14]提出了CSPA、HGPA和MCLA三种超图集成算法。CSPA算法在共协关系矩阵的基础上构建的图，顶点代表对象，边代表的是对象与对象之间的相似度，即共协关系矩阵中该对对象对应位置的值，最后利用METIS算法得到最后的聚类结果。CSPA是最简单的一种图算法，易于实现，但是复杂度较高，也十分占用空间，处理大规模数据就会很吃力。HGPA算法构建一个超图，顶点代表数据样本，一个闭合的曲线是一个超边代表一个簇。MCLA算法通过考虑类与类之间的关系来构建图，顶点代表类，边代表类与类之间的相似度，然后利用METIS算法将类划分成k个簇，最后将每个对象依次放入出现频率最高的簇中。Fern和Brodley等人[15]提出了HBGF算法，改进了之前算法的问题，考虑了类与对象之间的关系，利用基聚类结果构建二度图，顶点代表对象和类，若对象属于该类，则有连边，若
第三章基于样本对加权共协关系矩阵的聚类集成算法15),(|jitxxC代表类tC去掉ix和jx所在的小类中的所有样本之后的类。若ix和jx被分在同一个小类里，就去掉一个小类，被分到不同的小类中，就去掉两个小类。由于去掉了与ix和jx在同一小类中的样本，类tC的不确定性度量会有所减小，只不过有的减少的多，有的减少的少，所以由公式(3.4)可以看出(,,)tijHCxx的取值范围是[0,∞]，并且若(,,)tijHCxx越大，则从tC中去掉样本ix和jx所在的小类后，类tC的不确定性减小的程度就越大，也就是说，去掉样本ix和jx所在小类后使得类tC的不确定性变小的程度很大，因此样本对ix和jx的权值应该越校基于此，我们给出样本对ix和jx的权重如下：(,,)exp((,,)/())tijtijwCxxHCxxM(3.5)其中，参数θ>0，是用来调节样本对的不稳定性对于最后的权值的影响。由公式(3.5)可以看出权值),,(jitwxxC的取值范围是[0,1]，样本对导致类不确定性变化的程度越大，给的权值就越校图3.1给出了不同的参数对于权值的影响，可以看到当θ<1时，随着(,,)tijHCxx的增加),,(jitwxxC会显著的减少，当θ>4时，随着(,,)tijHCxx的增加),,(jitwxxC减少的速度会很缓慢。根据公式(3.5)，可以定义基于样本加权的共协关系矩阵WCM为：NNij}{mWCM(3.6)其中，MmmijmijijwMm11，),),((jiimijwxxxClsw，otherwisexxClsClsjmimmij,0)()(,1，mijw代表样本ix和jx对于所在的类tC的权值。图3.1对于不同参数，权值与样本对不稳定程度之间的相关性
本文编号：2919657
【文章来源】：山西大学山西省
【文章页数】：57 页
【学位级别】：硕士
【部分图文】：
聚类集成过程示意图
基于共协关系矩阵的聚类集成算法研究8个类中，值为1，否则，值为0，ijm代表着对象ix和对象jx在这M个基聚类中出现的频率。图2.2举例简单解释共协关系矩阵是如何得到的。图2.2两个基聚类结果及其对应的共协关系矩阵EAC算法描述如下：算法2.1：EAC算法输入：数据集},...,,{21nxxxX，聚类个数K输出：将数据集X划分成K个簇的结果；步骤1：在数据集X上利用k-means算法得到M个基聚类结果；步骤2：利用公式(2.1)得到共协关系矩阵；步骤3：通过层次聚类算法得到最后的聚类结果。(2)基于图的聚类集成基于图的聚类集成[14-18]将得到的基聚类结果构造成图，利用图聚类的算法来得到最后的聚类结果。Strehl等人[14]提出了CSPA、HGPA和MCLA三种超图集成算法。CSPA算法在共协关系矩阵的基础上构建的图，顶点代表对象，边代表的是对象与对象之间的相似度，即共协关系矩阵中该对对象对应位置的值，最后利用METIS算法得到最后的聚类结果。CSPA是最简单的一种图算法，易于实现，但是复杂度较高，也十分占用空间，处理大规模数据就会很吃力。HGPA算法构建一个超图，顶点代表数据样本，一个闭合的曲线是一个超边代表一个簇。MCLA算法通过考虑类与类之间的关系来构建图，顶点代表类，边代表类与类之间的相似度，然后利用METIS算法将类划分成k个簇，最后将每个对象依次放入出现频率最高的簇中。Fern和Brodley等人[15]提出了HBGF算法，改进了之前算法的问题，考虑了类与对象之间的关系，利用基聚类结果构建二度图，顶点代表对象和类，若对象属于该类，则有连边，若
第三章基于样本对加权共协关系矩阵的聚类集成算法15),(|jitxxC代表类tC去掉ix和jx所在的小类中的所有样本之后的类。若ix和jx被分在同一个小类里，就去掉一个小类，被分到不同的小类中，就去掉两个小类。由于去掉了与ix和jx在同一小类中的样本，类tC的不确定性度量会有所减小，只不过有的减少的多，有的减少的少，所以由公式(3.4)可以看出(,,)tijHCxx的取值范围是[0,∞]，并且若(,,)tijHCxx越大，则从tC中去掉样本ix和jx所在的小类后，类tC的不确定性减小的程度就越大，也就是说，去掉样本ix和jx所在小类后使得类tC的不确定性变小的程度很大，因此样本对ix和jx的权值应该越校基于此，我们给出样本对ix和jx的权重如下：(,,)exp((,,)/())tijtijwCxxHCxxM(3.5)其中，参数θ>0，是用来调节样本对的不稳定性对于最后的权值的影响。由公式(3.5)可以看出权值),,(jitwxxC的取值范围是[0,1]，样本对导致类不确定性变化的程度越大，给的权值就越校图3.1给出了不同的参数对于权值的影响，可以看到当θ<1时，随着(,,)tijHCxx的增加),,(jitwxxC会显著的减少，当θ>4时，随着(,,)tijHCxx的增加),,(jitwxxC减少的速度会很缓慢。根据公式(3.5)，可以定义基于样本加权的共协关系矩阵WCM为：NNij}{mWCM(3.6)其中，MmmijmijijwMm11，),),((jiimijwxxxClsw，otherwisexxClsClsjmimmij,0)()(,1，mijw代表样本ix和jx对于所在的类tC的权值。图3.1对于不同参数，权值与样本对不稳定程度之间的相关性
本文编号：2919657
本文链接：https://www.wllwen.com/shoufeilunwen/xixikjs/2919657.html
