软件学报  2014, Vol. 25 Issue (10): 2293-2311   PDF    
熵加权多视角协同划分模糊聚类算法
蒋亦樟, 邓赵红, 王骏, 钱鹏江, 王士同    
江南大学 数字媒体学院, 江苏 无锡 214122
摘要:当前,基于协同学习机制的多视角聚类技术存在如下两点不足:第一,以往构造的用于各视角协同学习的逼近准则物理含义不明确且控制简单;第二,以往算法均默认各视角的重要性程度是相等的,缺少各视角重要性自适应调整的能力.针对上述不足:首先,基于具有良好物理解释性的Havrda-Charvat熵构造了一个全新的异视角空间划分逼近准则,该准则能有效地控制异视角间的空间划分相似程度;其次,基于香农熵理论提出了多视角自适应加权策略,可有效地控制各视角的重要性程度,提高算法的聚类性能;最后,基于FCM框架提出了熵加权多视角协同划分模糊聚类算法(entropy weight-collaborative partition-multi-view fuzzy clustering algorithm,简称EW-CoP-MVFCM).在模拟数据集以及UCI数据集上的实验结果均显示,所提算法较之已有多视角聚类算法在应对多视角聚类任务时具有更好的适应性.
关键词多视角聚类     协同学习     Havrda-Charvat熵     香农熵     模糊C均值聚类    
Collaborative Partition Multi-View Fuzzy Clustering Algorithm using Entropy Weighting
JIANG Yi-Zhang, DENG Zhao-Hong, WANG Jun, QIAN Peng-Jiang, WANG Shi-Tong    
School of Digital Media, Jiangnan University, Wuxi 214122, China
Corresponding author: DENG Zhao-Hong, E-mail: dzh666828@aliyun.com
Abstract: There are two weaknesses of current multi-view clustering technologies based on collaborative learning. Firstly, the approximation-criteria of collaborative learning between each view is not clear for its physical meaning and is too simple to control the approximation-performance. Secondly, the existing algorithms assume that the significance of each view is equal, which is obviously inappropriate from the viewpoint of adaptively adjusting the importance of each view. In order to overcome the above shortcomings, a novel approximation-criteria of cluster partition based on the Havrda-Charvat entropy is proposed to control the similarity of cluster partition between each view. Then, an adaptive weighting strategy for each view based on the theory of Shannon entropy is presented to control the significance of each view and enhance the performance of the clustering algorithm. Finally, the collaborative partition multi-view fuzzy clustering algorithm using entropy weighting (EW-CoP-MVFCM) is provided. As demonstrated by extensive experiments in simulation data and UCI benchmark dataset, the proposed new algorithm shows the better adaptability than the classical algorithms on the multi-view clustering problems.
Key words: multi-view clustering     collaborative learning     Havrda-Charvat entropy     Shannon entropy     fuzzy C-means    

在实际生产或生活中经常会遇到同源异构的数据.所谓同源异构数据,即指数据的来源及采样的对象是一致的,但采样的视角(特征空间组成)存在一定的差异性.比如在测量人的血液时,可以从不同的测量指标(特征)切入对人的健康进行分析,目的在于最终从不同视角分析出趋于一致的更可靠的结果.由此诞生了一个新的技术领域——多视角技术,该技术的特色在于:通过对同一对象的不同特征所构造的数据样本进行分析,并利用各视角间的协同又称作交互式的处理模式找出视角间的相似性成分,进而得到一个趋于一致性的全局决策结果.由于该技术全面地考虑了被研究对象在各个视角下所存在的特征信息,因而在求同存异的指导思想下,所得到的决策结果要比传统的仅基于单一视角特征空间所得到的决策结果更为全面、可靠.这也使得近年来,多视角技术在机器学习等领域内得到了广泛的关注与应用,特别是在分类与聚类方面该技术均有着不俗的表现[1, 2, 3, 4].本文研究的重点将主要集中于多视角聚类领域.

正如我们熟知的那样,传统的聚类分析方法有K-means[5,6],Fuzzy C-means(FCM)[7,8],MEC[9,10]及PCM[11,12]等,均是围绕单一视角的聚类分析方法.那么,当上述算法遇到多视角聚类任务时,普遍的做法是先独立地考虑每一视角样本,将各视角样本看成一个独立的聚类任务进行处理,在获取每一视角对应的聚类结果后,再利用集成学习机制[13,14]选择一个合适的集成学习策略将多个聚类结果进行集成,进而得到最终的聚类结果.但此种人为地将每一视角割裂开来进行独立分析的多视角策略,极可能因某一视角下聚类结果存在明显的偏差或各个视角间的聚类结果差异性较大,造成集成学习所获取的全局划分结果较差又或者造成算法的性能不稳定.

因上述问题的存在,经过研究发现:将多视角技术引入传统的聚类分析方法,使得各视角在聚类过程中协同学习,被认为是一个有效的解决方案.近几年,基于上述策略提出了一些有效的多视角聚类方法,比较经典的工作有文献[15, 16, 17, 18].其中,文献[15]从概率的角度基于EM算法提出了可用于解决多视角问题的协同聚类算法——Co-EM算法,并通过文本类的数据集证明了该算法的有效性;文献[16]则首次在FCM算法中采用了协同聚类的思想,通过对各视角间的模糊划分进行控制,构造了划分协同控制函数,得到了Co-FC算法,该算法在多个数据集上均表现出了一定的优势;文献[17]针对高维数据处理较为困难的问题,提出了将高维数据通过一定方法投影到不同的低维空间上,再利用多视角聚类技术对这些低维的数据集进行分析,最终得到一个全局性的划分结果;在2009年,文献[18]参考了文献[16]的协同思想,同样以经典FCM算法作为基础模型,进一步提出了两种不同的多视角协同划分方法,并依此构造了全新的多视角模糊聚类算法Co-FKM.

虽然近几年多视角聚类技术得到了一定的发展,特别是基于经典FCM框架提出了一些有效的方法,如多视角Co-FKM算法[18],但通过对已有多视角聚类算法的研究可以发现,以往的模型普遍存在以下两点不足:

1) 不同视角间的协同学习准则,如空间划分逼近准则,过于简单且物理解释性较弱,这使得该类准则并不能充分探究出各视角间的关系,如相似性程度;

2) 已有的多视角聚类算法通常未能考虑到各视角重要性所存在的差异,只是简单地默认各视角的重要性是均衡的,这使得已有算法的聚类性能及适应能力还有待提高.

针对上述第2)点不足,需要指出的是,目前各算法所采用的视角重要性均衡化的处理方式与实际应用所面临的情况是不符的.例如,在实际应用中,各视角由于采样的特征空间不同,造成了各视角样本并不一定均具有良好的聚类特性,因而各视角的重要性很自然是不同的.大量的事实表明:类别划分并不明确的特征空间所对应的视角对整个多视角聚类分析任务而言并无太大的帮助,甚至会起负作用,因而在聚类过程中应尽量弱化此种视角的影响力.

针对上述挑战,本文首先基于Havrda-Charvat熵构造了全新的异视角空间划分逼近准则,利用熵良好的信息表征特性来控制各视角间的空间划分结果,使得各视角在协同学习时能够找到尽可能多的相似性信息,进而使得各视角的空间划分结果尽量一致,以获取一个较为稳定且更为全面的全局性空间划分结果.进一步地,本文引入香农熵和可能性概率权值对各视角进行了自适应加权处理,从而在聚类过程中有效地调节各视角间的权重关系,使得空间划分最为明确的视角所占的比重尽可能地大,同时使空间划分较模糊的视角所占比重尽可能地小,最终获取最优的空间划分结果.特别地,根据最终获取的概率权重,可以得到针对该多视角任务的最佳聚类视角,即,权重最大值所对应的视角.

通过引入上述技术,本文在经典FCM框架下探讨了具体的多视角聚类分析新算法,即,熵加权多视角协同划分模糊聚类算法(entropy weight-collaborative partition-multi-view fuzzy clustering algorithm,简称EW-CoP- MVFCM).由于该新目标函数在保证各视角样本空间划分趋于一致的前提下,更进一步凸显了最佳聚类视角的作用,从而使得其获取的空间划分结果较之以往的算法更为准确、合理.因而,该算法对整个聚类任务而言获取的结果具备更好的全局决策价值,同时,最佳视角的获取也为后期对研究聚类对象的全局性空间划分决策提供了一种新的集成策略.因此,通过上述两大机制进行多视角协同聚类,将确保本文算法在应对现实世界复杂多变的聚类任务时较之以往方法具有更好的数据分析与决策能力,亦增强了算法的适应性.

1 相关工作

在数据挖掘领域内,经常会面对同源异构的数据样本,即,具备多视角特性的样本集合,对于此类样本的聚类任务,一般可采用以下两种策略:

1) 利用经典的单视角聚类算法,如FCM算法,对每一个视角样本进行单独的聚类分析,而后,通过集成学习技术将每一视角对应的模糊划分结果经过某种集成策略形成一个全局性的决策解;

2) 利用当前较流行的多视角聚类算法,如文献[18]中提出的基于模糊聚类技术的Co-FKM算法,该算法通过所构造的不同视角间的空间逼近准则,使得每一视角在单独聚类过程中还需考虑其他视角的影响,通过找出各视角间的相似性,以使聚类结果尽可能地保持一致,最终根据集成学习策略得到一个全局性的决策解.

在上述两种多视角聚类技术方案中,对于最终的全局空间划分结果均依赖于集成学习机制,该技术的目的在于,选定某种集成规则,将各视角下的聚类结果有效集成以获取全局性的结果.

另外,与多视角具有一定相似性的聚类技术还有如下几个方向.

1) 多任务聚类

该方法将多个具有一定关联性的聚类任务通过多任务学习框架进行协同式学习,经典的工作有文献[19]中的LSSMTC算法.若我们将各视角看作单一任务,则在一些情况下可使用多任务聚类技术来处理多视角聚类任务.然而,这两类聚类技术在本质上是存在差异的:多任务聚类算法考虑的是任务之间的相似性,不同任务对应不同的聚类对象;而多视角聚类是不同视角对应相同的聚类对象,这使得多任务聚类技术用于多视角聚类通常不能得到理想的效果.另外,在多任务聚类中,对于各任务的样本特征数(维数)通常需要保持一致,这使得在面对各视角样本维数不一致的聚类任务时,该方法无法使用.

2) 组合聚类

该方法源于多任务的思想,它通过将多个任务组合成一个任务进行整体性的空间划分.较为有效的方法有文献[19]中的组合K-means算法(CombKM),该算法的思想同样也适用于多视角聚类,在利用该算法对多视角数据进行聚类分析时,考虑到多视角样本本质上是同源不同特征的组合形式,因此只需将这些不同特征下的样本合并成一个整体样本即可.但如此做法必定会破坏各视角的独立性特征,进而影响最终的空间划分结果.

3) 基于样本与特征空间的协同聚类

该方法在考虑对样本聚类的同时还引入了对特征划分的考虑,而对特征的划分结果本质上对应于多视角样本中每一视角对应的特征组合,该领域内较成功的工作有文献[20]中的Co-clustering算法.在使用该算法处理多视角聚类任务时,同样采用组合聚类的策略,先合并各视角样本再进行聚类分析.由于该算法采用了与组合聚类相同的策略,虽然其考虑了特征空间的划分,但该划分相对比较粗糙,因此利用该算法处理多视角聚类任务时效果也不甚理想.此外,该算法在计算时采用了矩阵求逆的运算,这使其在处理大样本或高维数据时常常会受到硬件条件的制约而不再适用.

除了如上的相关工作,本文将重点介绍与分析两种与本文算法有着紧密关联的多视角模糊聚类算法.首先介绍单视角FCM算法和集成学习策略相结合的多视角模糊聚类技术,然后介绍一种经典的基于协同学习技术的多视角聚类方法Co-FKM.

1.1 单视角FCM算法处理多视角问题

给定数据样本X={x1,…,xN}ÎRNxD(N为样本总量,D为样本维数),U=[mij]ÎRCxN为样本X上的模糊划分矩阵(C表示所需聚类的类别总数),V=[vi]ÎRCxD为样本的类中心.

根据上述定义,经典的FCM算法目标函数可表示为如下形式:

(1)

其中,vi=(vi1,…,vik)为第i类的中心点;mij表示第j个样本属于i类的隶属度,其中,模糊指数m必须满足m>1;xj表示第j个样本点.根据相关的优化理论,通过拉格朗日的极值求解方法可以得到类中心vi以及隶属度mij的迭代表达式:

(2)

(3)

根据以上两式迭代优化终止后,所获取的隶属度矩阵U在去模糊化之后得到空间划分矩阵,根据该矩阵可获取每一个样本xj所对应的类别信息.

通过上述优化策略最终可以获得模糊划分矩阵U,那么在面对多视角聚类任务时,若不考虑各视角间的相似性,则最直接的方法,即,将每一视角对应的样本集代入到目标函数公式(1)中得到各自的空间划分矩阵Uk (1<k<K),k表示视角个数.然而,为了得到全局性的决策解,此时需要引入集成学习技术,将各视角下的[U1,…,UK]整合成一个具有全局描述能力的空间划分矩阵该种方法的工作原理如图 1所示.

Fig. 1 Principle of processing the multi-view clustering task by using the traditional FCM algorithm图 1 传统FCM算法处理多视角聚类任务的工作原理图

根据图 1所示之工作原理可以发现,该多视角聚类技术因人为地将各视角割裂开来进行独立的聚类分析,未能考虑到聚类过程中各视角间的协同学习(挖掘相似性成分).虽然最后引入了集成学习,策略得到了全局性的空间划分结果,但是由于各视角并无协同学习,其视角与视角之间的关联性(相似性)未得到合理的运用,这极易造成最终获取的全局性空间划分结果因某一视角存在严重误分而导致算法性能的下降.

1.2Co-FKM算法

为了解决单一视角算法面对多视角聚类任务时遇到的难题,文献[18]以经典FCM算法作为多视角聚类模型构建的基础,提出了多视角模糊聚类算法(Co-FKM).该算法的主要贡献在于:通过引入协调各视角间空间划 分的隶属度约束项,保证在算法收敛时得到的各视角空间划分结果尽可能地一致,从而实现聚类过程中各视角的协同学习.Co-FKM算法的目标函数可表示如下:

(4-1)

(4-2)

将公式(4-2)代入公式(4-1),经过化简最终可得到如下的目标函数:

(5)

公式(5)中,,其中,参数h为调控各视角隶属度划分的协同学习参数,而则表示为当前视角下的隶属度与其余各视角隶属度之间的加权平均值.

根据经典FCM算法的优化策略,同样通过拉格朗日极值求解方法,可以得到隶属度mij,k以及中心点vi,k的优化迭代公式如下:

(6)

(7)

在上述迭代策略的基础上,最终可以获取各视角下对应的模糊隶属度划分矩阵.那么,为了求得一个具备全局性考量的模糊划分标准,文献[18]利用各视角下所获取的模糊隶属度的几何平均值来体现整体的划分结果,其具体的表达如下所示:

(8)

利用式(8)所得结果,在去模糊化之后,即可获取用以表征整个事物/对象的空间划分结果,为后期进一步对事物进行决策提供了有力的空间划分参考.

多视角模糊聚类算法的工作机制如图 2所示.

Fig. 2 Principle of processing the multi-view clustering task by using Co-FKM algorithm图 2 Co-FKM算法处理多视角聚类任务的工作原理图

虽然上述算法成功地在每一视角的聚类过程中融入了不同视角间的空间划分逼近准则,实现了各视角间的协同学习,使得该算法在面对多视角聚类任务时较之传统单视角集成聚类技术展示出了更为有效的聚类性能,但其依然存在诸多问题,其中迫切需要改进的即为本文引言部分所述的两点不足.本文将针对这两个不足,在下一节给出一种全新的多视角模糊聚类方法.

2 熵加权多视角协同划分模糊聚类算法(EW-CoP-MVFCM)

针对前面所述的当前多视角聚类方法所存在的两点不足,本文基于熵理论引入如下两大新技术以对当前方法进行有效改进.

· 首先,提出了基于Havrda-Charvat熵的异视角空间划分逼近准则.如我们所知,在信息论中,熵理论经常被用来描述随机变量的不确定性,而模糊聚类算法中的模糊隶属度也被用以描述样本点xj归属的不确定性.因此,本文选用Havrda-Charvat熵构造出新的异视角空间划分逼近准则,试图利用熵理论寻找出各视角间的最大相似性成分,从而在提高算法性能的同时也从熵的角度给予了异视角空间划分逼近准则新的物理意义;

· 其次,提出了基于香农熵的多视角自适应加权策略.鉴于以往的算法对视角的重要性程度存在弱化的问题,本文提出了熵加权的多视角聚类技术,通过给每一个视角加以权重,从而在迭代优化过程中自适应地找出最佳视角,同时获取最优的模糊划分结果.为了对该权重进行有效调控,本文引入香农熵理论对各视角的重要性程度进行掌控.

通过上述两大改进策略的共同作用,即得到了本文所提到的熵加权多视角协同划分模糊聚类算法(entropy weight-collaborative partition-multi-view fuzzy clustering algorithm,简称EW-CoP-MVFCM),该算法具有更好的样本适应性,相应的工作原理如图 3所示.另外,在第2.1节、第2.2节还将分别对上述两大策略的构造及其物理意义进行详细的解释与说明.

Fig. 3 Principle of processing the multi-view clustering task by using EW-CoP-MVFCM algorithm图 3 EW-CoP-MVFCM算法处理多视角聚类任务的工作原理图
2.1 基于Havrda-Charvat熵的异视角空间划分逼近准则

由于现有的多视角聚类算法对模糊隶属度的控制过于简单且控制项的物理含义也不明确,因此,本文利用熵常被用以描述随机变量的不确定性程度的性质,并根据模糊聚类算法中模糊隶属度也被用以描述样本点xj隶属于第i类空间的模糊程度的理论,自然地将熵理论引入到模糊聚类算法中,用来控制并更好地解释模糊隶属度.经过上述的研究与分析,本文构造了基于第k视角下的样本点xj,k的Havrda-Charvat熵[21],其具体定义如下:

(9)

很明显,若将模糊隶属度矩阵看作概率矩阵,那么当满足的约束条件时,G(m)(xj,k)的值为0.这直观地说明了该视角的样本集Xk中的样本点xj,k隶属于各个划分的不确定性达到最小;也即说明,当目标函数取得最优解时,该视角下的隶属度mij,k的Havrda-Charvat熵相应地也取得最小值.同时,样本集Xk中的各样本点所具有的Havrda-Charvat熵总量亦达到最小.

虽然公式(9)可以保证划分的不确定性达到最小,但还只限于单视角框架,为了将其拓展至多视角领域,本文参照文献[18]的相关策略,将公式(9)改造为如下形式:

(10-1)

将上式整理后可得:

(10-2)

观察公式(10-2)可以发现:在保证相异的视角空间(即对应于每一个视角)下隶属度mij对应的Havrda- Charvat熵达到最小值的前提下,通过参数h的取值,可以有效调控当前视角与其余各视角隶属度划分的权重关系(h需满足0<h<1且一般取h=(K-1)/K),从而得到当前视角下的隶属度加权平均值.该策略能够促使各视角的隶属度划分尽可能地趋向一致,从而获取更具全局性的空间划分结果.

2.2 基于香农熵的多视角自适应加权策略

本节针对现有的多视角聚类算法中,几乎默认了同一种前提假设,即,每一视角对最终聚类结果的贡献是均等的.实际上,由于某些视角往往存在严重的空间重叠现象而不具可分性,对于这些视角而言,若在整体的聚类过程中给予其与其他具备较好可分性的视角同等的重要性程度,而这显然是不合乎逻辑的.合理的处理方式应是:根据视角的可划分特性给予其不同的重要性程度,这样所得到的整体性聚类结果才能达到最佳.但人为地给定重要性权重显然也是不合理的,为此,本文基于香农熵理论[9,22]提出了具备多视角技术特征的自适应加权项,再引入视角权重系数wk,并根据wk≥0的条件重新构造了目标函数式.

此外,为了对视角权重系数wk加以调控,本文在wk≥0的条件下,将视角权重看作概率分布,则可用香农熵表示为

(11)

通过上述手段引入熵技术,使得目标函数在达到最优的同时熵尽可能地大,这也便是经典的极大熵原理.而熵的极大化又会导致各概率分量尽可能地趋于均衡[9],而目标函数的极大化则使得视角权重更加趋向于某一分量即某一视角,从而将最具聚类效果(空间划分最为鲜明)的视角凸显出来.由于在各个视角上引入了自适应极大熵加权的概念,这使得该算法能够有效地降低那些聚类特性较差的视角对算法优化迭代时的干扰,从而获取更为理想的空间划分结果,同时也增强了算法的有效性.

2.3EW-CoP-MVFCM算法

根据第2.1节和第2.2节有关异视角空间划分逼近准则及多视角自适应加权策略的定义,本文仍以经典FCM算法框架为基础,重新构造了具备多视角聚类能力的目标函数如下:

(12)

上式中,共包含两个部分.

· 第1部分为基于Havrda-Charvat熵理论的多视角协同聚类部分:

其本质是:通过异视角空间划分逼近准则找出各视角间尽可能多的相似性成分,最终使得各视角的空间划分结果趋于一致;

· 第2部分为基于极大熵理论的自适应视角加权部分:

利用此部分,可自适应调控各视角在多视角聚类过程中的权重关系,最终在算法达到最优时,根据视角的权重矩阵W进而获得最佳视角划分结果.

其中,协同学习参数h的取值参照文献[18],取h=(K-1)/K,而正则化平衡因子l1l2的取值则参照文献[23],利用网格寻优获取.

同样,为获取具备全局特性的空间划分结果,本文摒弃了文献[18]中的集成策略,即公式(8),根据新获取的视角划分权重矩阵W=[w1,w2,…,wK]重新定义了新的集成学习方法,即全局性加权视角空间划分集成法,具体形式如下:

(13)

因最终迭代优化终止时,最佳视角所占的比重往往较大(最佳视角即最易划分的视角),因此,由此得到的空间划分结果较之以往的算法更为理想.

2.3.1 各参数优化推导

本节将利用经典的优化理论,通过拉格朗日极值求解的相关策略,对目标函数公式(12)进行优化,为了得到目标函数的最优解,本节给出如下几个定理.

定理1. 在给定第k个视角的隶属度划分矩阵Uk以及视角权重矩阵Wk后,目标函数公式(12)取得极值时应满足如下必要条件:

(14)

证明:利用给定的第k个视角的隶属度划分矩阵Uk以及视角权重矩阵Wk,对目标函数JEW-CoP-MVFCM(Vk)求偏导,并令,可得.至此,定理1得证.证毕.

定理2. 在给定第k个视角的类中心矩阵Vk以及视角权重矩阵Wk后,目标函数公式(12)取得极值时应满足如下必要条件:

(15)

证明:利用给定第k个视角的类中心矩阵Vk以及视角权重矩阵Wk,根据约束条件,引入拉格朗日乘子aj,k,得到相应的优化目标函数式如下:

(16)

上式中,

分别对mij,k,aj,k求偏导,并令偏导数为0.

根据可得:

(17)

可得:

(18)

联立公式(17)及公式(18),消去aj,k,即可得到:

定理3. 在给定第k个视角的类中心矩阵Vk以及隶属度划分矩阵Uk后,目标函数公式(12)取得极值时应满足如下必要条件:

(19)

证明:仿照定理2的证明过程,利用拉格朗日极值求解方法及约束项即可证得定理3.

2.4EW-CoP-MVFCM算法描述

根据第2.3节相关优化理论及迭代公式推导所获取的参数学习规则,本节将给出EW-CoP-MVFCM算法的具体步骤如下:

输入:多视角样本集View={view1,…,viewK}共K个视角(1≤kK),而任意一个视角对应的样本集为viewk={X1,…,XN},聚类数目C(2≤C<N),迭代阈值e,模糊指数m,迭代次数f,最大迭代次数L,协同学习参数h,正则化平衡因子l1,l2;

输出:各视角聚类中心点vi,k,全局性的模糊划分矩阵U,各视角权重wk.

Step 1. 初始化随机产生中心点集vi,随机产生归一化的模糊隶属度矩阵mij,随机产生归一化的视角权重wk;

Step 2. 根据公式(14)更新各视角下的中心点vi,k;

Step 3. 根据公式(15)更新各视角下的隶属度mij,k;

Step 4. 根据公式(19)更新各视角的权重wk;

Step 5. 如果||Jk+1-Jk||<e或者f>K,则算法结束,跳出循环;否则,跳回Step 2;

Step 6. 算法收敛后,输出各视角下的聚类中心点vi,k、各视角下的模糊隶属度mij,k以及各视角权重wk;

Step 7. 根据Step 6所获取的各视角权重wk及各视角下的模糊隶属度mij,k,根据公式(13)可获取具备全局特性的模糊空间划分矩阵另外,根据max(W)可找出最佳聚类视角.

3EW-CoP-MVFCM全局收敛性分析

在文献[24]中,经典的FCM算法的收敛性早已得到证明.而本文提出的EW-CoP-MVFCM算法虽然依旧采用经典FCM算法的结构框架,但由于引入了具有多视角特性的异视角空间划分逼近准则以及多视角自适应加权策略,使得该算法的收敛性有必要进行再次的证明与分析.

为了对本文算法的收敛性进行判断,我们根据文献[25,26]的相关收敛性理论可知,若需对一种算法的全局收敛性进行判断,只需确定该算法是否满足Zangwill收敛性定理的3个充要条件即可.为了便于后续进一步对本文算法的收敛性进行判断,这里首先给出Zangwill的收敛性定理如下.

引理1(Zangwill收敛性定理). 假设点z(0)ÎV,由点-集映射A:V®P(V)定义的迭代算法产生迭代序列{z(t)},解集WÌV.如果:

(1) {z(t)}ÌGÍV,其中,G表示为一个紧集;

(2) 存在连续函数f:V®R,满足:

(a) 若zÏW,则对于任意yÎA(z),f(y)<f(z);

(b) 若zÎW,算法终止,或对于任意yÎA(z),f(y)≤f(z);

(3) 若zÏW,映射Az处是闭的,

则算法终止于解集W,或{z(t)}的任一收敛子序列的极限是解集W的一个点.

满足上述引理1中条件(2)的函数f被称为是AV上的Zangwill函数.

3.1EW-CoP-MVFCM全局收敛性证明

本节将主要对EW-CoP-MVFCM算法的收敛性进行验证,同时为了方便证明,我们首先给出如下几个定义及相关的一些定理,具体描述可参见下文.

定义1. 设A:V®P(V)表示为一个点-集映射,那么在点x*ÎX处,若有{x(t)}ÌX,x(t)®x*,y(t)ÎA(x(t)),y(t)®y*,使得y*ÎA(x*),则可称点-集映射Ax*ÎX处是闭的;如果它在X中的每一点是闭的,则称点-集映射AX上是闭的.

定义2a. 在k视角下,定义映射关系

G1,k(Wk,Uk)=Vk=(v1,k,v2,k,…,vc,k)T (20)

其中有类中心vi,k=(vi1,k,vi2,k,…,vid,k)TÎRd,i=1,2,...,c,可通过公式(14)求得.

定义2b. 在k视角下,定义映射关系

G2,k(Wk,Vk)=Uk (21)

其中有模糊矩阵Uk=[mij,k]cxn,可通过公式(15)计算而得.

定义2c. 在k视角下,定义映射关系

G3,k(Vk,Uk)=Wk (22)

其中有视角权重值Wk,k=1,2,...,K,可通过公式(19)求得.

定义3. 在k视角下,定义映射关系其集合表述形式如下:

定义4. 如果存在t表示当前的迭代次数,t=2,3,....这里, 中的任意值,则序列称为EW-CoP-MVFCM算法的优化迭代序列.

定理4. 设k视角下的数据样本Xk={x1,k,x2,k,…,xn,k},定义上的函数,其中,m>1,0<h<1,l1>0,l2>0为定值.当且仅当时,VkF在视角k上的关于的全局最小值点.

定理5. 设k视角下的数据样本Xk={x1,k,x2,k,…,xn,k},定义上的函数,其中,m>1,0<h<1,l1>0,l2>0为定值.当且仅当时,UkL在视角k上的关于的全局最小值点.

定理6. 设k视角下的数据样本Xk={x1,k,x2,k,…,xn,k},定义上的函数,其中,m>1,0<h<1,l1>0,l2>0为定值.当且仅当时,WkW在视角k上的关于上的全局最小值点.

定理7(EW-CoP-MVFCM收敛定理). 设k视角下的数据样本Xk={x1,k,x2,k,…,xn,k}包含至少c个独立的点,c<n,定义:

(23)

为EW-CoP-MVFCM算法对应的最优化问题的第k个子解集:

其中,关于minJEW-CoP-MVFCM的详细计算策略见公式(12).令为当前第k视角下,根据映射Gm,k进行迭代的起始解,且满足则优化迭代过程所产生的序列对应于第k个视角可表示为其中,t=1,2,….该序列终止于解集Jk中的一个点或存在上述序列相应的一个子序列同样收敛于解集Jk中的一个点.

证明:为了证明EW-CoP-MVFCM算法的全局收敛性,即需证得EW-CoP-MVFCM算法满足引理1的三大条件即可,所以本证明部分将分别从这三大条件的满足性入手,给出本文算法的收敛性分析.

(a) 紧集

根据凸包的定义,设k视角下的数据样本存在:

为数据集Xk上的凸包.根据公式(14)的相关表述易知:

进而可得Vk=(v1,k,v2,k,…,vc,k)Î[conv(Xk)]T.因此,显然存在:

均为存在上下界的闭集,因此根据紧集的定义可知,它们均为紧集;

亦满足紧集定义,视为紧集.

(b) 连续性

对于第k视角,则有fm,kGm,kXk上的Zangwill函数.由于,根据定理4,有:

同理,根据定理5,有:

根据定理6,可得如下不等式:

根据上述3个不等式,可得到如下不等关系:

(24)

故,在第k视角下的fm,k函数是Gm,kXk上的Zangwill函数.

(c) 闭映射

根据定义2的有关描述,对于第k个视角,显然存在如下两个连续映射:

·

·

为了证明为闭映射,不妨设定如下假设条件:

1) t®¥;

2) t®¥;

3) t®¥.

根据:

(25)

又有:

(26)

进而可得:

(27)

因此,我们可以得到:为一闭映射;

同时,易证得亦为闭映射.

综合条件(a)~条件(c)的证明,因每一视角下的fm,k(Wk,Vk,Uk)均为Zangwill函数,即,均为凸函数,因此,由其求和所得的EW-CoP-MVFCM算法亦满足Zangwill收敛定理,具备全局收敛性.至此,定理7得证. 

4 实验研究 4.1 实验设置

为了验证本文方法对多视角聚类任务的有效性及自适应视角权重划分的效果,本节将分别通过人工合成数据集以及UCI标准数据库数据(http://archive.ics.uci.edu/ml)对EW-CoP-MVFCM算法进行分析与评估.有关人工合成数据以及UCI标准数据库数据的详细描述分别于第4.2节和第4.3节中给出.此外,为对本文所提EW- CoP-MVFCM算法聚类性能做出评判,将于第4.2节及第4.3节给出与当前最新的多视角模糊聚类算法Co-FKM[18]、基于多任务学习框架的LSSMTC算法[19]、基于多任务的组合K-means算法(CombKM)[19]及基于样本与特征空间协同聚类的Co-clustering算法[20]在人工集与标准集上进行性能比较的聚类结果,并对此结果进行适当的分析与解释.

为了公正地对各聚类算法的聚类性能做出合理的评价,本文采用如下两种评价指标进行算法的性能分析.

1) 归一化互信息(normalized mutual information,简称NMI)[6,23]:

(28)

其中,Ni,j表示第i个聚类与类j的契合程度,Ni表示第i个聚类所包含的数据样本量,Nj表示类j所包含的数据样本量,而N表示整个数据样本的总量大小;

2) 芮氏指标(rand index,简称RI)[23,27]:

(29)

其中,f00表示数据点具有不同的类标签并且属于不同类的配对点数目,f11则表示数据点具有相同的 类标签并且属于同一类的配对点数目,而N表示整个数据样本的总量大小.

以上两种方法,其取值范围均为[0,1],且均随着数值的增大,显示出算法的性能更为优越.

在本文实验部分,各可调参数的设置遵循文献[18,23]的计算策略,具体见表 1.本文的实验结果均为10次算法完整运行下的均值及方差所组成.

Table 1 Definition and settings of the related notations 表 1 参数定义和设置

实验环境:实验硬件平台为Intel Core i5-2410Mx2 CPU,其主频为2.3GHz,内存为2GB.编程环境为MATLAB 7.0.

4.2 人工合成数据集实验

为了充分验证本文方法的多视角特性及自适应视角权重划分的效果,在人工合成数据集部分,本文首先构造具有3维特性的数据集A(x,y,z)用来表示待分析的事物/对象,而后,根据投影的原则选取了3个视角,分别为:

· view_1=(x,y),由A事物向特征x与特征y方向投影得到;

· view_2=(y,z),由A事物向特征y与特征z方向投影得到;

· view_3=(x,z),由A事物向特征x与特征z方向投影得到.

对于每一个视角而言都包含3类样本,每一类样本由200个点对构成共600个样本.有关对象A的示意图及各视角下的样本组成如图 4所示.

Fig. 4 Original dataset and the corresponding datasets under different图 4 原始数据集及其在不同视角下的对应数据集

观察图 4可以发现:对于事物A从不同的方位所投影得到的3个视角样本,其中只有视角1具备非常清晰的聚类特性,而视角2及视角3的样本类别之间均存在一定程度的重叠;特别是视角2,其中两类的重叠性非常高.如若使用现有的多视角技术对此类聚类任务进行分析,所得到的聚类结果必定会受到视角2及视角3的影响,从而破坏了整体的可分性.为了验证上述观点,本文在该人工合成数据集上进行了相应的实验验证并与有关算法进行了比较,实验结果如表 2图 5所示.

Table 2 Comparison of performance indices NMI & RI of several algorithms on the synthetic datasets 表 2 各种算法在模拟数据集上的性能比较

Fig. 5 Weight of each views for target A with EW-CoP-MVFCM algorithm图 5 EW-CoP-MVFCM算法获取的事物A各视角权重情况

根据表 2图 5的结果分析,可得到如下结论.

1) 与非多视角聚类算法比较.

表 2的前3列结果进行分析可以发现,无论是多任务的LSSMTC算法和CombKM算法,还是基于样本空间与特征空间协同分析的Co-clustering算法,聚类结果均表现一般.分析其原因主要在于:针对多任务聚类算法而言,虽然该类算法具备多任务协调工作的能力,但由于其关注的重点局限于样本本身,而多视角聚类任务其本质就是将一个事物A通过不同的特征空间抽样得到不同的样本集合,其重点考虑的是各视角下的特征因素,因此,多任务算法得到了一般的聚类效果也是可以理解的;而对于具备样本空间与特征空间协同分析能力的Co-clustering算法而言,该算法仍是基于单视角框架下的聚类技术,因此在处理数据时只可将多个视角合并为一个样本集合再进行处理,而原本的每一视角在此样本集合中则变成了此整体样本的特征子集.由于视角2和视角3为较难聚类的视角,它们的存在使得Co-clustering算法在面对此类聚类任务时效果也并不理想;较之上述算法,无论是经典的Co-FKM算法还是本文的EW-CoP-MVFCM算法,因均采用了多视角技术,即,各视角的空间划分尽可能地逼近,从而使得上述两种多视角聚类算法获得了更好的聚类效果.这也印证了多视角聚类技术的有效性;

2) 与多视角聚类算法比较.

通过对表 2的后两列进行分析可知,本文的方法明显优于Co-FKM算法.分析其原因主要在于,本文前几节一直强调的视角重要性不均等的理论.观察图 4可清晰地看出,视角1具备非常优秀的空间划分特性,而视角2和视角3的空间划分特性并不明显,特别是在类别的区分面上存在严重的交叠现象,因此,当Co-FKM这类假设空间划分重要性均等的算法遇到上述各视角重要性不均衡的聚类任务时,算法的有效性必定会受到一定的影响;而本文的EW-CoP-MVFCM方法因采用了独有的多视角自适应加权技术,使得优化终止时最佳视角的权重突出,如图 5所示.由于视角1具备很好的空间划分特性,因此在熵加权技术的帮助下,我们最终获取的视角权重系数也与真实的情况趋于一致,从而获取了更为合理的聚类效果,提高了算法的适用性.

4.3UCI数据集实验分析

为了对EW-CoP-MVFCM算法的聚类性能及实际应用价值作进一步的探讨与分析,本节将分两部分对EW-CoP-MVFCM算法进行探讨:(1) 基于UCI数据库中的经典数据集IRIS,对本文方法寻找各视角权重划分并找出最佳视角的能力做出进一步的评判,具体实验设置见第4.3.1节;(2) 利用UCI数据库中的经典多视角数据集Multiple Features、Image Segmentation及Water Treatment Plant对本文所提算法的性能做出更加充分的评价,同时与相关算法进行比对分析.本节所用数据的基本信息见表 3.

Table 3 Classic UCI datasets 表 3 UCI经典数据集
4.3.1 IRIS实验分析

由于IRIS每一维(属性特征)对应的样本分布具有很好的最佳视角解释性,其每一维特征对应的数据分布如图 6所示.基于上述原因,本文选用此数据集,并将其每一维特征看作一个视角,即,将原本的IRIS数据样本拆分成4个视角样本集合,从而利用本文算法进行聚类分析,其聚类结果如图 7表 4所示.

Fig. 6 Datasets of each views for IRIS图 6 IRIS各视角数据直观图

Fig. 7 Weight of each views for IRIS with EW-CoP-MVFCM algorithm图 7 EW-CoP-MVFCM算法获取的IRIS各视角权重情况

Table 4 Comparison of performance indices NMI & RI of several algorithms on the IRIS datasets 表 4 各种算法在IRIS数据集上的性能比较

根据表 4图 7的结果可以发现,其与人工合成数据集的实验结果是一致的.同样,由于本文算法有效地利用了最佳视角,使得最佳视角的权重达到了最大化,从而获取了更为合理的空间划分结果.从NMI和RI两大评价指标上也可以看出,本文算法较之其余的几种方法显得更为有效.同时,图 7的视角权重比更加有力地证明了:本文算法能够通过新目标函数寻找到最优的视角权重划分结果,并与真实的视角重要性程度保持一致.

4.3.2 多视角真实数据集实验分析

本节将采用经典机器学习数据库UCI中的3种具备多视角特性的数据集:1) MF数据集;2) IS数据集;

3) WTP数据集.通过利用上述数据集,考察本文所提EW-CoP-MVFCM算法在处理真实多视角聚类任务时其性能的有效性.为了对这3种数据集所包含的视角有更为直观的印象,本文将给出这三大数据集的各视角特征组成,详见表 5.同时,针对这3种真实数据集的算法性能比对结果可见表 6.

Table 5 Description of MF-dataset,IS-dataset and WTP-dataset and the construction of each view 表 5 MF,IS及WTP数据集简介及两者的各视角组成

Table 6 Comparison of performance indices NMI & RI of several algorithms on the datasets of MF,IS and WTPt 表 6 各种算法在MF,IS及WTP数据集上的性能比较

由于LSSMTC算法需要保证各聚类任务的维数一致,因此在面对MF,IS及WTP等各视角维数均不相等的样本时便无法使用.另外,通过观察其余各算法对MF数据集的聚类结果可以发现,基于多视角的Co-FKM及本文的算法有着较大的聚类优势,但是,因MF数据并无任何视角存在明显的可分性,即,各视角的重要性程度较均衡,上述原因使得本文所提算法与Co-FKM算法的聚类结果从NMI及RI两大指标的均值上看较为接近,而从方差上分析依旧是本文的方法较为稳定.究其原因在于:本文所采用的基于Havrda-Charvat熵构造的异视角空间划分逼近准则具有良好的物理解释性,能够充分挖掘视角间的相似性成分,这一特性保证了本文方法每次运行得到的结果偏差不大,较为稳定;而对于IS数据集,本文方法优势明显,进一步说明了EW-CoP-MVFCM算法的有效性;最后,通过对WTP数据集的实验结果分析,同样也可得到与上述两大数据集一致的结论.综上,通过在真实多视角数据集上的实验与分析,我们可以得到一个较明确的结论,即,多视角聚类算法在处理具备多视角特性的聚类任务时一般均优于非多视角聚类算法,而具有更强协同学习能力及视角选择性的EW-CoP-MVFCM算法又要优于以往的多视角聚类算法.至此,本文算法的性能得到了充分的验证与肯定.

5 结 论

本文基于多视角聚类技术,在经典FCM算法的基础上引入了基于Havrda-Charvat熵构造的异视角空间划分逼近准则.由于该准则由熵理论构造得到,因而具有良好的物理解释性,这使得本文方法在运用该准则时能够更好地找出视角间的相似性成分,进而得到更具指导意义的全局性空间划分结果.此外,本文另一大贡献在于重新审视了视角的重要性程度,摒弃了以往默认的各视角重要性一致的结论.通过对极大熵相关理论的理解,提出了基于香农熵的多视角自适应加权策略,并成功地将该策略引入到最新的多视角模糊聚类技术中.在新获取的目标函数取得最优解时,我们进一步根据各视角最终所占的权重关系评价出视角的重要性程度,藉此提出了一种全新的多视角集成方法,即,全局性加权视角空间划分集成法.通过在模拟数据集以及UCI真实数据集的实验结果,均显示出了本文方法较之以往多视角算法及相关算法具有更好的聚类性能.但因本文仍然采用经典的FCM框架,对于欧氏距离的使用,致使本文算法在面对高维多视角聚类问题时其算法性能将面临一定的考验,该问题的解决将是今后研究的重点.

参考文献
[1] Li GX, Chang KY, Hoi SCH. Multi-View semi-supervised learning with consensus. IEEE Trans. on Knowledge and Data Engineering, 2012,24(11):2040-2051 .
[2] Li GX, Hoi SCH, Chang KY. Two-View transductive support vector machines. In: Parthasarathy S, Liu B, Goethals B, Pei J, Kamath C, eds. Proc. of the 10th SIAM Int’l Conf. on Data Mining. 2010. 235-244.
[3] Bickel S, Scheffere T. Multi-View clustering. In: Proc. of the 4th IEEE Int’l Conf. on Data Mining. Washington: IEEE Computer Society, 2004.19-26 .
[4] Jain AK, Murty MN, Flynn PJ. Data clustering: A review. ACM Computing Surveys, 1999,31(3):264-323 .
[5] Yu S, Tranchevent LC, Liu XH, Glanzel W, Suykens JAK, De Moor B, Moreau Y. Optimized data fusion for kernel k-means clustering. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2012,34(5):1031-1039 .
[6] Jing LP, Ng MK, Huang JZ. An entropy weighting k-means algorithm for subspace clustering of high-dimensional sparse data. IEEE Trans. on Knowledge and Data Engineering, 2007,19(8):1026-1041 .
[7] Zhu L, Chung FL, Wang ST. Generalized fuzzy C-means clustering algorithm with improved fuzzy partitions. IEEE Trans. on Systems Man and Cybernetics: Part B, 2009,39(3):578-591 .
[8] Hall LO, Goldgof DB. Convergence of the single-pass and online fuzzy C-means algorithms. IEEE Trans. on Fuzzy Systems, 2011, 19(4):792-794 .
[9] Deng ZH, Wang ST, Wu XS, Hu DW. Robust maximum entropy clustering algorithm RMEC and its outlier labeling. Engineering Science, 2004,6(9):38-43 (in Chinese with English abstract).
[10] Karayiannis NB. MECA: Maximum entropy clustering algorithm. In: Proc. of the 3rd IEEE Conf. on Fuzzy Systems. Orlando: IEEE Press, 1994. 630-635 .
[11] Krishnapuram R, Keller JM. A possibilistic approach to clustering. IEEE Trans. on Fuzzy Systems, 1993,1(2):98-110 .
[12] Krishnapuram R, Keller JM. The possiblistic means algorithms: Insights and recommendation. IEEE Trans. on Fuzzy Systems, 1996,4(3):385-393 .
[13] Asur S, Parthasarathy S, Ucar D. An ensemble framework for clustering protein interaction networks. Bioinformatics, 2007,23(13): i29-i40 .
[14] Wang HJ, Shan HH, Banerjee A. Bayesian cluster ensembles. Statistical Analysis and Data Mining, 2011,4(1):54-70 .
[15] Yamanishi Y, Vert JP, Kanehisa M. Protein network inference from multiple genomic data: A supervised approach. Bioinformatics, 2004,20(1):i363-i370 .
[16] Pedrycz W. Collaborative fuzzy clustering. Pattern Recognition Letter, 2002,23(14):1675-1686 .
[17] Chaudhuri K, Kakade SM, Livescu K, Sridharan K. Multi-View clustering via canonical correlation analysis. In: Proc. of the 26th Annual Int’l Conf. on Machine Learning. New York: ACM Press, 2009.1-8 .
[18] Cleuziou G, Exbrayat M, Martin L, Sublemontier JH. CoFKM: A centralized method for multiple-view clustering. In: Proc. of the 9th IEEE Int’l Conf. on Data Mining (ICDM 2009). 2009.752-757 .
[19] Gu Q, Zhou J. Learning the shared subspace for multi-task clustering and transductive transfer classification. In: Proc. of the 9th IEEE Int’l Conf. on Data Mining. 2009.159-168 .
[20] Gu Q, Zhou J. Co-Clustering on manifolds. In: Proc. of the 15th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. 2009. 359-368 .
[21] Havrda JH, Charvat F. Quantification methods of classification processes: Concepts of structural a-entropy. Kybernetica, 1967,3(1): 30-35.
[22] Wang XZ, An SF. Research on learning weights of fuzzy production rules based on maximum fuzzy entropy. Journal of Computer Research and Development, 2006,43(4):673-687 (in Chinese with English abstract) .
[23] Deng ZH, Choi KS, Chung FL, Wang ST. Enhanced soft subspace clustering integrating within-cluster and between-cluster information. Pattern Recognition, 2010,43(3):767-781 .
[24] Bezdek JC, Hathaway RJ, Sabin MJ, Tucker WT. Convergence theory for fuzzy C-means: Counterexamples and repairs. IEEE Trans. on Systems Man and Cybernetics, 1987,17(5):873-877 .
[25] Zangwill W. Convergence conditions for nonlinear programming algorithms. Management Science, 1969,16(1):1-13 .
[26] Luenberger DG, Ye YY. Linear and Nonlinear Programming. 3rd ed., New York: Springer-Verlag, 2008. 201-208 .
[27] Liu J, Mohammed J, Carter J, Ranka S, Kahveci T, Baudis M. Distance-Based clustering of CGH data. Bioinformatics, 2006,22(16): 1971-1978 .
[9] 邓赵红,王士同,吴锡生,胡德文.鲁棒的极大熵聚类算法RMEC及其例外点标识.中国工程科学,2004,4(9):38-45 .
[22] 王熙照,安素芳.基于极大模糊熵原理的模糊产生式规则中的权重获取方法研究.计算机研究与发展,2006,43(4):673-687 .