结合FCS的多视图模糊聚类算法

刘永利，郭呈怡，刘 静，吴 岩

(河南理工大学 计算机科学与技术学院，河南 焦作 454000)

聚类技术能够在无监督的条件下揭示出数据背后隐藏的知识和结构，故而在大数据的时代背景下备受关注。按照隶属度取值范围的不同，聚类技术可划分为硬聚类和模糊聚类两种。在硬聚类算法中，一个样本只能完全隶属于一个簇；模糊聚类则将隶属度取值范围从硬聚类的0和1二值扩展至实数区间[0,1]，即允许一个样本以一定概率同时隶属于多个簇。考虑到样本主题的多样化特点，以模糊C均值聚类(Fuzzy C-Means, FCM)算法[1]为代表的模糊聚类算法在聚类准确率方面更具优势。然而，该算法及其衍生算法对噪声数据较为敏感，导致算法的有效性易受影响。为了提高算法的鲁棒性，文献[2]提出了模糊紧致性分离性聚类算法(Fuzzy Compactness and Separation, FCS)，该算法将类间距离作为惩罚项加入到目标函数中，实验效果较为理想。文献[3]提出了一种嵌入隐马尔科夫随机场的中智C聚类算法，并在此基础上，引入核函数将欧式空间的样本映射至高维空间，提出了核空间隐马尔科夫随机场的中智C聚类算法。

上述模糊聚类算法的聚类对象通常只具有单一表示或单一视图。然而，现实世界的数据日臻复杂，多视图的特点日渐突出，即从不同的角度观察同一个样本，观察结果可能大相径庭。多视图数据具有多种表示，且不同表示之间可以相互补充。虽然从每一种表示出发都可以对数据进行聚类，但是结果比较片面；只有对数据的多种表示协同聚类，才能形成对数据的完整认识。

大多数多视图聚类算法通过协同方式或正则化方式完成多视图聚类任务，前者利用每个视图的信息直接获得一致聚类结果，后者则是减小每个视图的聚类结果与一致聚类结果的差异。文献[4-5]结合谱聚类算法，提出了基于协同的多视图谱聚类算法和基于联合正则化的多视图谱聚类算法。文献[6]提出了一种处理关系数据的多视图模糊聚类算法，聚类过程中选取样本作为每个簇的质心。文献[7]提出了一种基于特征加权和非负矩阵分解的多视角聚类算法，该算法通过最小化每个视角的系数矩阵与一致矩阵的差异完成聚类目的。在非负矩阵分解过程中，往往忽视了样本空间的局部结构，针对此问题，文献[8]提出的一种基于非负矩阵分解的模糊聚类算法，引入了流型正则化项。文献[9-10]基于K-Means算法和非负矩阵分解提出的两种多视图聚类算法，考虑了样本的权重。文献[11]提出了一种鲁棒的多视图均值聚类(Robust Multi-view K-Means Clustering, RMKMC)算法，可以有效处理大规模数据。文献[12]提出一种多视图模糊聚类算法，可以识别每个视图的重要性。文献[13]为了减小冗余特征对聚类结果的影响，提出了一种基于特征选择的多视图聚类算法。文献[14]提出了一种基于模糊C均值聚类算法的极小化极大值优化算法(Minimax optimization based on Fuzzy C-Means, MinimaxFCM)，该算法使用极小化极大值算法降低高权重视图的权重，达到各视图间聚类结果的平衡。文献[15]提出了使用粒子群优化双权重的多视图聚类算法，在每次迭代中通过粒子群优化寻找质心。上述多视图聚类算法通过综合数据的不同表示产生一致聚类结果，有助于提高聚类的准确率；然而，噪声数据并未引起重视，因此，当噪声出现时，这些算法在更新质心时易受干扰，进而影响聚类有效性。

基于以上分析，笔者提出了一种多视图模糊紧致性分离性算法(Multi-view Fuzzy Compactness and Separation, MvFCS)，将模糊紧致性分离性算法应用到多视图数据处理中，可以有效解决多视图聚类问题。该算法根据各视图的重要性为其赋予不同权重，对不同视图协同聚类易于提高聚类的准确率；同时，继承模糊紧致性分离性算法的鲁棒性优势，有助于降低噪声对各质心的影响。

1 模糊紧致性分离性算法

鉴于模糊C均值聚类算法对于噪声数据较为敏感，文献[2]提出了模糊紧致性分离性算法，该算法同时考虑了类内紧致性和类间分离性，有助于增强算法的鲁棒性。设数据集X包含N个样本，X={x1,…,xN}，其特征维度为D，v1,…,vK为K个质心，用U表示K×N的隶属度矩阵，V为质心矩阵，其目标函数及约束可分别表示为

(1)

(2)

(3)

其中，m为控制模糊程度的参数，uci表示第i个对象对第c个簇的隶属度。式(1)分为两项，第1项表示类内距离；第2项表示类间分离性，前取负号表示类间分离性对目标函数的贡献呈负性；x为所有样本中心；η为一个K维向量。在聚类过程中，模糊紧致性分离性算法兼顾类内距离和类间距离，即该算法通过减小类内距离和增大类间距离优化目标函数JFCS，有效降低了噪声数据造成的影响。

为了实现多视图数据聚类，并降低对噪声数据的敏感程度，将模糊紧致性分离性算法与多视图模糊聚类相结合，提出了多视图模糊紧致性分离性算法。该算法为每个视图赋予不同的权重，综合各视图的结果进行协同聚类。在聚类过程中，使用极小化极大值算法优化权重最高的视图，从而实现各个视图间隶属度矩阵的一致性。

2 多视图模糊紧致性分离性算法

2.1 算法的目标函数

对于有P个视图和N个对象的多视图数据集X={X(1),…,X(P)}，定义V={V(1),…,V(P)}，为多视图数据集X的质心矩阵。算法的目标函数可表示为

(4)

其中，

(5)

(6)

(7)

(8)

算法通过优化如式(4)所示的目标函数，产生多视图的聚类结果。在聚类过程中，首先利用视图权重α(p)整合不同视图的信息，然后用隶属度矩阵U返回不同视图一致的聚类结果。

2.2 算法的优化

在待求解变量中，ηc(p)的求解公式已经给出(如式(8)所示)，隶属度矩阵U、质心矩阵V和权重向量α的表达式采用拉格朗日乘数法求解。构造的拉格朗日函数为

(9)

2.2.1 固定质心和权重并求解隶属度

将质心和权重视为常量，隶属度视为变量，对式(9)关于uci求偏导，并令偏导数等于0，可得

(10)

(11)

对于某一对象xi，如果存在一个质心vc使得

(12)

即式(11)的分子小于或者等于0，那么uci=1，且对任意的t(t∈{1,2,…,K},t≠c)，有uti=0。

2.2.2 固定权重和隶属度并求解质心

将权重和隶属度视为常量，质心视为变量，对式(9)关于vc(p)求偏导，并令偏导数等于0，可得

(13)

由式(13)可得到vc(p)的更新公式，即

(14)

2.2.3 固定质心和权重并求解隶属度

将隶属度和质心视为常量，权重向量α(p)视为变量，对式(9)关于α(p)求偏导，并令偏导数等于0，可得

(15)

由式(15)和式(7)可得到权重α(p)的更新公式为

(16)

在聚类过程中，对式(8)、(11)、(14)和(16)迭代更新，可得算法的聚类结果。

2.3 算法的步骤

算法与极小化极大值优化算法[14]的更新顺序一致，即先初始化α和V，再更新η和U。

算法1多视图模糊紧致性分离性算法。

输入 多视图数据集X={X(1),…,X(P)}，簇数目K，参数γ、m和β，最大迭代次数T，阈值参数ξ。

输出 聚类结果向量q。

① 初始化每个视图的质心矩阵V(p)，得到数据集X的质心矩阵V；

② 初始化权重向量α(p)=1/P；

③ 初始化当前迭代次数t=0；

repeat{

④ forp=1:P

⑤ forc=1:K

⑥ 利用式(8)更新ηc(p)；

⑦ end for

⑧ end for

⑨ forc=1:K

}until‖Ut+1-Ut║<ξ或者t>T

算法的时间复杂度主要取决于更新η、隶属度矩阵、质心矩阵和视图权重向量4部分，其中更新一次η的时间复杂度为O(PK2)，更新一次隶属度矩阵、质心矩阵、视图权重向量的时间复杂度均为O(PNK)，所以算法总的时间复杂度为O(t(3PNK+PK2))，t为迭代次数。

3 实验分析

实验的环境为操作系统Windows 7，CPU型号Inter i3-4150，频率3.50GHz，内存4GB，编译软件为MATLAB R2016a。

实验中参数的取值：K的值由聚类数目决定，参数m、γ和β需要在实验中选取最优值，默认输入m=1.5，γ=0.5，β=0.4，最大迭代次数T=1 000，阈值参数ξ=10-5。

在每个视图中，随机挑选K个样本作为初始质心。为了保证实验结果的有效性，对每个算法运行10次，取这10次运行结果的平均值作为算法的实验结果。

3.1 实验准备

为了验证算法的有效性，选取4个多视图数据集进行了实验，各数据集的信息见表1。

为便于比较，实验选取了3个对比算法，分别为模糊紧致性分离性算法(FCS)、鲁棒的多视图均值聚类算法(RMKMC)和极小化极大值优化算法(MinimaxFCM)。其中，模糊紧致性分离性算法为单视图聚类算法，其他两种算法为多视图聚类算法。实验过程首先用模糊紧致性分离性算法对每个视图进行单独聚类，得到每个视图的聚类结果，记录最差单视图结果为FCS 1，记录最好单视图结果为FCS 2，然后将每个视图的特征放到一起进行模糊紧致性分离性聚类，结果记为FCS。实验结果使用准确率(Accuracy)、F度量(F-Measure)和标准化互信息(Normalized Mutual Znformation,NMI)这3个指标进行评价。

表1 多视图数据集的详细信息

为了评估多视图模糊紧致性分离性算法的鲁棒性，在原始数据集上完成聚类后，在每个数据集中添加10%～15%的噪声数据，并再次比较各算法的聚类效果。各数据集上添加的噪声样本数如表1所示。

3.2 实验结果

实验数据包括未添加噪声数据和添加噪声数据两部分，并据此组织两组实验。对于未添加噪声数据的实验，讨论多视图聚类算法和单视图聚类算法的效果，并比较多视图模糊紧致性分离性算法、鲁棒的多视图均值聚类算法和极小化极大值优化算法这3种多视图聚类算法的性能；对于添加噪声数据部分的实验，则验证算法的鲁棒性。

IS、MF、MMKSD和Cal这4个数据集上的实验结果分别如表2～表5所示，每个表包含了未添加噪声数据和添加噪声数据的两部分实验结果。

表2 在有无噪声两种情况下IS数据集上的准确率对比

表3 在有无噪声两种情况下MF数据集上的准确率对比

表4 在有无噪声两种情况下MMKSD数据集上的准确率对比

表5 在有无噪声两种情况下Cal数据集上的准确率对比

表2给出了IS数据集上的实验结果。当未添加噪声数据时，FCS 2的准确率为58.09%，FCS的准确率为60%，而3种多视图聚类算法的最低准确率(鲁棒的多视图均值聚类算法)为62.38%，最高(多视图模糊紧致性分离性算法)为66.19%。该结果说明，相较于单视图算法，多视图聚类算法通常可以获得更高的聚类准确率；同时，相较于鲁棒的多视图均值聚类算法和极小化极大值优化算法这两种多视图聚类算法，多视图模糊紧致性分离性算法可以更有效地完成聚类任务。当添加噪声数据后，FCS算法展现出优秀的噪声抵抗能力，多视图模糊紧致性分离性算法继承了模糊紧致性分离性算法的优点，准确率上升了0.47%，所受影响甚微，而鲁棒的多视图均值聚类算法的准确率下降了4.29%，极小化极大值优化算法的准确率下降了7.14%，这两种算法受到的影响相对较大。各算法在MF、MMKSD和Cal数据集上也有相似表现。

从上述数据集的实验结果可以得出两个结论：①相较于单视图聚类算法，多视图聚类算法可以更有效地完成聚类任务；②相比较鲁棒的多视图均值聚类和极小化极大值优化两种多视图聚类算法，多视图模糊紧致性分离性算法不但在未添加噪声数据时具有较高准确率，而且在添加噪声数据后展现出较高鲁棒性。

3.3 参数讨论

算法中存在m、γ和β这3个参数。为了评估参数对算法的影响，在实验数据集上进行了实验。实验结果如图1～图4所示，纵坐标Acc表示聚类准确率。

图1 IS数据集上参数对聚类结果的影响

图2 MF数据集上参数对聚类结果的影响

图3 MMKSD数据集上参数对聚类结果的影响

图4 Cal数据集上参数对聚类结果的影响

从图1～图4可以得出参数m、γ和β对聚类结果的影响：①参数β最为稳定，对准确率的影响也最小；②参数γ稳定性在数据集IS、MMKSD和Cal数据集上表现较好，在MF数据集上比较敏感；③聚类结果对参数m的取值最为敏感，这与极小化极大值优化算法对参数m的分析一致。

从图1～图4可以得出以下结论：①参数m、γ和β对聚类结果存在一定影响，尤其是参数m的取值对聚类准确率影响较大；②相对于聚类准确率，参数m、γ和β对算法鲁棒性的影响较小，即无论参数m、γ和β如何取值，当数据集中加入一定比例的噪声时，准确率的变化均较小。

4 结束语

在数据规模日趋庞大的同时，更多的噪声掺杂其中，数据的结构和形式也愈加复杂多样。更全面、稳定地发现数据背后潜藏的知识，是研究多视图聚类算法以及聚类鲁棒性的初衷。

文中提出了一种多视图模糊紧致性分离性算法。该算法一方面保持了多视图聚类算法的特点，聚类时根据不同视图的重要性协同聚类，有助于提高聚类准确率；另一方面继承了模糊紧致性分离性算法综合考虑类内紧致性和类间分离性的优点，能够增强算法的鲁棒性。在聚类过程中，该算法通过权重来调整每个视图之间聚类结果的一致性，且能够自动学习并更新权重。为了对算法进行评估，选取了4个多视图数据集进行了实验，并分为未添加噪声数据和添加噪声数据两种情况。实验结果表明，文中算法在聚类准确率和鲁棒性方面的表现均优于对比算法。