【www.zhangdahai.com--其他范文】
李 嫚,王立宏
(烟台大学计算机与控制工程学院,山东 烟台 264005)
数据聚类是一种经典的无监督学习技术,它在机器学习及数据挖掘等领域得到了广泛应用。聚类旨在通过某种相似度计算方法将数据集划分为多个不同的簇,使同一簇内的数据对象之间具有较高的相似度,不同簇内的数据对象之间相似度较小。在过去的几十年中,已经提出了许多成功的聚类方法,但是没有一种聚类算法可以解决所有不同形状、密度或者包含噪声的簇的聚类问题。研究人员发现,集成学习将多个学习器的结果进行组合,可以获得比单个学习器更好的效果,因此将集成的思想引入到数据聚类中。2002年,STREHL和GHOSH[1]正式提出聚类集成的概念,通过组合多个不同的基聚类结果得到一个性能更佳、鲁棒性更强的聚类结果。
聚类集成已经成为机器学习领域的研究热点之一。学者们将博弈论[2-4]、粒度计算[5-6]、随机游走[7-12]等思想与聚类相结合,开创新的聚类集成算法。FELDMAN等[3]引入了hedonic games(享乐博弈)思想处理聚类问题,SANDES等[4]在其基础上,对博弈理论进行了更深入的分析,并应用于聚类集成中,提出了基于享乐博弈的聚类集成算法HGCE(Hedonic Game based Clustering Ensemble)。XU等[6]从粒度计算的角度出发,引入粒度距离度量基聚类成员之间的相似性,提出基于粒度计算的聚类集成算法CEGC(Clustering Ensemble based on Granular Computing)。2006年,PONS等[7]提出了一种基于随机游走的节点相似性度量方法Walktrap,通过随机游走轨迹量化网络节点之间的结构相似性,进而有效计算网络中的社区结构。2012年,金弟等[8]根据马尔可夫随机游走思想,结合网络聚类,提出一种新的网络聚类算法——基于随机游走的蚁群算法,并通过实验证实该算法能够准确得到网络的真实聚类簇数且具有较高的聚类精度。2013年,FU等[9]提出了CD-Trandwalk算法,与采用随机游走计算节点相似度的算法不同的是,该算法首先选择活动节点作为种子节点,通过设定随机游走者的阈值来检测核心社区,剩余的非核心节点根据策略分配到核心社区中。
2016年,HUANG等[10]以微簇(各基分区基簇的交集)为对象,提出了精英邻居选择策略,通过局部自适应阈值识别不可靠的链接,构造K-ENG(K-Elite Neighbor Graph)图。在K-ENG图上进行随机游走,将随机游走的概率轨迹作为相似性矩阵,进而采用层次聚类算法得到聚类结果。
本文提出了以hedonic games生成的簇为对象,簇间社会福利值为边权值构造博弈簇相似图,在博弈簇相似图上随机游走的聚类集成算法CERW。在生成基聚类成员时,采用了熵正则化软子空间聚类算法ERKM(Entropy Regularization K-Means),利用熵系数的不确定性生成多样化的基聚类成员,然后采用基于hedonic games的算法HGCE得到博弈簇,最后采用基于随机游走的聚类集成算法CERW得到共识划分结果。在实验部分,本文提出的算法与基于单个节点、微簇节点、以及基簇节点随机游走的算法在20个数据集上进行了性能对比。
1.1 熵正则化的软子空间聚类
为了解决传统聚类算法在处理高维数据时容易受到“维度灾难”的影响问题,提出了子空间聚类算法。子空间聚类可以分为硬子空间聚类和软子空间聚类,本文关注一类基于熵正则化的软子空间聚类算法[13-15],以ERKM算法为例。
2019年,XIONG等[15]提出了ERKM算法,该算法旨在最小化簇内数据点与簇中心点之间的加权距离和的同时最大化不同簇间数据点的加权距离和,且所有的子空间都共用一个特征加权向量,其目标函数如下:
F(U,W,V)=
(1)
假设数据集X={xij}N×D表示数据集具有N个数据对象,D个属性值。U={uki}K×N为隶属度矩阵,V={vkj}K×D表示K个簇中心的向量矩阵。目标函数的第一项表示加权的簇内距离和;第二项为熵正则化项,参数γ>0控制每个维中权值的分布;第三项表示加权的簇间距离和,η>0是一个控制簇内距离和簇间距离的平衡参数。
熵正则化项中含有的参数γ取值范围广,且对于不同的数据集,在算法运行前难以确定系数的具体取值。此处采用ERKM算法生成基聚类主要是利用系数的波动以生成多样性的基聚类成员参与集成,期望得到更好的聚类结果。
1.2 聚类集成
一般而言,聚类集成包括两个关键步骤:一是生成基聚类成员,二是设计组合函数。在生成基聚类成员时,一般采用两种方法:(1)采用同一个聚类算法,通过设置不同的参数或初始值来获得多样性的基聚类集合。由于K-means算法实现简单且对初始值敏感,常被用来作为基分区生成器[4,16]。(2)采用不同的聚类算法[17],便于从多个角度了解数据集的结构。通过这两种方法就可以得到泛化能力强且具有一定差异性的基聚类成员。
得到基聚类成员后,对于基聚类的表示也有不同的方式,目前常用的基聚类表示方式主要分为三种:联合矩阵[18]、二元矩阵[16]、超图[1]。通常,联合矩阵用来衡量两个数据对象之间的相似度,二元矩阵用来衡量一个数据对象对一个聚类的簇隶属度,超图用来衡量数据对象关于簇的隶属度。
共识函数实质上是一种方法,它将聚类成员进行合并(或称为集成),得到一个统一的聚类结果。目前已经提出了许多聚类集成设计方法,概括分为基于关联矩阵CA(Co-Association)的方法、投票方法、信息论方法、图方法以及混合模型方法等[19]。
1.3 Hedonic games
在合作博弈中,数据对象被视为参与者,簇集被视为联盟,则基划分CS={Ck|k=1,2,…,K}为一个联盟结构。假设vi表示参与者xi的偏好函数,vij表示参与者xi对参与者xj的效用值,则vij=vi(j)=vj(i)=vji。参与者xi对联盟Ck的偏好可表示为vi(Ck)=∑j∈Ckvij。
给定联盟结构CS,联盟的效益为联盟结构内所有参与者效用值的总和,即
(2)
如果参与者xi离开当前的联盟CSi到另一个联盟Ck,则新的联盟结构CS′关于CS的社会福利差异为
v(CS′)-v(CS)=vi(Ck)-vi(CSi),
(3)
如果vi(Ck)>vi(CSi),则联盟结构CS′相比于CS会得到一个更高的社会福利值。因此,若当前联盟结构内的所有参与者的偏好值达到最大,且不再向其他联盟移动时,hedonic games 达到纳什均衡,即当前的联盟结构对于联盟内的所有参与者而言是纳什稳定的。
SANDES等[4]通过定义参与者xi对联盟Ck的偏好,提出了基于享乐博弈的聚类算法HGCE。偏好函数定义如下:
(4)
(5)
在社区发现中,各节点随机访问下一个节点,当一个节点重复访问同一个节点的次数足够大时,则该节点被访问的频率逐渐趋于稳定。用频率代替概率,便可以得到每个节点被访问的概率。在数据聚类中,根据不同节点的概率轨迹,可以探索数据集的全局结构信息,发现数据结构之间的潜在关联。
2016年,HUANG等[10]提出了基于微簇节点随机游走的方法,该方法通过随机游走的概率轨迹衡量微簇节点之间的相似性。
2021年,HUANG等[11]又以基簇为对象,以Jaccard系数为边权值构造基簇相似度图,在相似度图的基础上进行随机游走,得到基簇间的转移概率矩阵作为新的相似度矩阵,然后映射到数据对象层ECA(Enhanced Co-Association)矩阵中进行聚类。
受此启发,我们以hedonic games算法生成的簇为对象,簇之间的社会福利值为边加权构造初始相似图,定义如下:
G=(V′,L),
(6)
V′是通过hedonic games算法生成的簇节点集,其基数为N′,L为图的边集,定义簇节点之间的边权值为簇之间的参与者效用值的和,计算公式为
wij=v(Ci)+v(Cj),
(7)
由于Ci和Cj同为簇节点,即一个联盟,则v(Ci)、v(Cj)的计算同公式(2)。
得到初始相似图后,为了发现图中的簇结构信息,采用随机游走技术,通过分析不同节点的随机游走概率轨迹来探索图节点之间的潜在关系。在构造初始相似图时,不同算法对图节点的定义是有区别的。假设参与集成聚类的三种基聚类如图1所示,不同算法基于图1基聚类得到的随机游走节点间的主要差异如图2所示。
图1 基聚类
图2 不同算法随机游走节点对比
观察图2可以发现,不同算法参与随机游走的节点不同。图2(a)是文献[10]的节点示意图,它以微簇为图节点,微簇在基聚类中聚类在同一簇时的次数累积为边加权构造簇关联矩阵,以此构成相似度图。根据定义,在所有的基聚类中,均聚类在同一簇中的数据点定义为一个微簇。图2(b)是文献[11]的节点示意图,以基簇为图节点,以Jaccard系数为边加权构造基簇相似度图。图2(c)是一般的单点游走算法,其中每个数据点都是一个图节点,相似性定义采用CA矩阵,即数据点在基聚类中成对出现的频率。图2(d)是本文的CERW算法,其中的节点是通过hedonic games算法生成的博弈簇,相似性定义为簇间社会福利值。
根据HUANG的观点[10],在链接加权图中,一个节点到邻居节点的转移概率通常与链接权值成正比。由于随机游走节点为簇节点,簇内的数据对象存在隐含信息,转移概率考虑到簇的大小,定义节点Ci到节点Cj的转移概率Pij如下:
(8)
Pij表示一步转移概率矩阵P的第(i,j)项,其中nj表示簇Cj中的数据对象数。则S步随机游走的转移概率矩阵定义为
(9)
(10)
根据上式,得到簇节点之间基于概率轨迹的相似性度量准则。节点Ci和Cj之间基于概率轨迹的相似度定义为
Sim(Ci,Cj)=
(11)
此处采用余弦相似度定义了节点之间基于随机游走概率轨迹的相似性,<-,->表示向量的点积,由此可以得到新的簇级相似度,以新的簇级相似度矩阵为输入,采用常用的聚类算法如层次聚类等进行聚类集成得到最终集成结果。
3.1 数据集和评价指标
在本节,采用UCI机器学习数据库中的Iris等16个数据集和4个合成数据集对CERW算法的性能进行测试,各数据集的详细信息如表1所示。此外,采用聚类准确率ACC[21](Accuracy)、归一化互信息NMI[22](Normalized Mutual Information)和调整兰德系数ARI[23](Adjusted Rand Index)三个聚类评价指标对共识聚类的质量进行了评估。ACC与NMI的取值范围为[0,1],ARI的取值范围为[-1,1],三者的数值越高,表明共识聚类结果越准确。
表1 实验数据集描述
3.2 实验方案
本节选择的对比算法有三种:以微簇为对象,构造微簇-微簇相似度图进行精英选择及随机游走的PTA[10]算法;以基簇为对象,构造基簇-基簇相似度图进行随机游走的ECPCS-HC[11]算法;以博弈簇为对象,构造博弈簇-博弈簇相似度图进行随机游走的本文CERW算法。通过对比,可以观察以不同节点开始游走的随机游走轨迹,挖掘不同簇之间的关联信息。
以上三种算法都是基于簇节点的随机游走,我们测试了基于数据点的随机游走实验,记作EAC算法,各算法随机游走节点的区别如图2所示。上述算法分别从数据点、簇的层次参与聚类集成,另一个对比算法WEAC[24]算法则以基聚类为对象,依据提出的NCAI指标评估基聚类的质量,进而根据聚类有效性对基聚类进行加权。
对于每个数据集,所有的算法均运行30次,并记录30次运行结果的平均值。表2—4显示了所有算法的ACC、NMI和ARI的平均值。每个数据集采用不同算法得到的最优值以粗体显示,次优值以斜体显示。W/T/L (Wins/Ties/Losses)记录算法达到最优值/等于最优值/非最优值的次数。
3.3 实验结果及分析
在聚类集成时,所有算法均采用聚合层次聚类,包括单连接、全连接和组平均三种方式,每次实验保留所有方法中的最大值。记录了聚类集成在数据集得到真实簇数时的各项指标值,分别如表2—4所示。此外,还记录了各种算法关于不同指标的得分情况,计算得出平均秩(Avg. Rank)。Avg.Rank值表明了算法优越性的排序情况,Avg.Rank值越低越好,平均排名最低的算法是性能最佳的算法。
表2 不同集成聚类算法得到的平均ACC值
表2(续)
表3 不同集成聚类算法得到的平均NMI值
表4 不同集成聚类算法得到的平均ARI值
观察表2可知,参与实验的数据集共20个,我们提出的CERW算法有10个数据集取得最优ACC值,其余取得最佳值的数据集离散分布在其他算法上。且CERW算法取得最低的Avg.Rank值(2.275),表现更优越。
表3是不同集成聚类方法的平均NMI值,CERW算法取得最优值的数据集个数是13。表4给出了不同集成聚类方法的平均ARI值,CERW算法关于取得最优值的数据集个数为11,其余算法取得最优值的数据集个数比较均匀,且CERW算法在NMI和ARI上都有最低的Avg.Rank值(1.825,1.925)。综上所述,在聚类结果得到数据集的真实簇数时,与其他对比算法相比,我们提出的CERW算法能够表现出更好的性能。
软子空间聚类算法是传统特征加权方法的扩展,能权衡各维度对簇的重要性,更精确描述各簇所在的子空间,因而越来越得到重视。随机游走已经被证明是发现簇结构的有力工具,本文提出的CERW算法以软子空间聚类算法ERKM的结果为基簇,通过享乐博弈得到的簇为节点,簇之间的社会福利值为边加权构造相似图,通过随机游走轨迹发现簇之间的结构关系。并与以基簇、微簇、数据点随机游走的算法进行了对比实验,实验结果表明了CERW算法在聚类集成时的表现更为优越。
猜你喜欢 聚类矩阵概率 一种傅里叶域海量数据高速谱聚类方法北京航空航天大学学报(2022年8期)2022-08-31概率统计中的决策问题中学生数理化(高中版.高考数学)(2022年3期)2022-04-26概率统计解答题易错点透视中学生数理化(高中版.高考数学)(2022年3期)2022-04-26基于知识图谱的k-modes文本聚类研究南京理工大学学报(2022年1期)2022-03-17一种改进K-means聚类的近邻传播最大最小距离算法计算机应用与软件(2021年7期)2021-07-16概率与统计(1)中学生数理化·高三版(2021年3期)2021-05-14概率与统计(2)中学生数理化·高三版(2021年3期)2021-05-14基于模糊聚类和支持向量回归的成绩预测华东师范大学学报（自然科学版）(2019年5期)2019-11-11多项式理论在矩阵求逆中的应用读与写·教育教学版(2017年10期)2017-11-10矩阵南都周刊(2015年4期)2015-09-10本文来源：http://www.zhangdahai.com/shiyongfanwen/qitafanwen/2023/0429/591150.html
