基于目标函数优化的无向加权图粗糙模糊聚类算法

何文倩, 刘士虎,宋 敏, 杨昔阳

(1.云南民族大学 数学与计算机科学学院,云南 昆明 650504;2.泉州师范学院 数学与计算机科学学院,福建 泉州 362000)

随着数据库技术的快速发展和数据库管理系统的广泛应用，积累数据和掌控技术的用户越来越多[1].数据爆炸的背后隐藏着重要信息，人们希望通过更高层次的分析来更好地利用数据[2].图是一种重要的数据结构，可用于描述复杂网络的拓扑结构，如社交网络[2]、疫情传播网络[3]，传感器网络和蛋白质网络[4]等.图数据聚类可以帮助检测出含有重要信息的类结构，此外，还可以帮助研究者更好地理解图数据的特征和功能[5].

图数据聚类是根据图的拓扑信息和属性信息将一个大图划分为若干个子图的过程，使得同子图内的顶点连接紧密而不同子图内的顶点连接稀疏，并且相似顶点应划分到相同子图内，不相似顶点应划分到不同子图内[4-5].研究者已经提出许多相关算法，并成功地应用于各种图数据中.比如，基于结构相似性的图数据聚类算法利用结构相似性来发现图数据中无重叠的子图类[5].Walktrap算法利用随机游走技术检测复杂图数据中的类[6].此外一些算法还使用归一化割方法、最小割方法和最大流最小割方法来进行图数据聚类反演.这些算法均基于边连接权值对图数据进行聚类，但它们需要从所有顶点中选择权值最小的边，这是一个较难的问题.还存在一些算法，要么需要预先输入少量信息，要么只考虑图数据的拓扑信息和属性信息中的一个.针对这些问题，Tian等[7]提出了一种基于属性信息的关系对图数据进行聚类的算法，它将同一维度的属性分组到同一个类中.不幸的是，该算法忽略了聚类内的拓扑结构.Zhou等[8]提出了一种图数据中统一的距离度量方法，该方法通过在原始图中添加带属性的顶点来生成属性增广图，然后使用随机游走方法计算顶点之间的距离.该算法得到的属性增广图中顶点数大于原始图中的顶点数，但是算法运行时间不尽人意[9]，并且当属性较多时，算法的时间复杂度会很高[10].Javed等[11]提出了一种综合考虑拓扑和属性的图数据聚类算法，这种算法被广泛应用并且是一种基于描述驱动思想的聚类方法，目标是简单地聚类社交图数据，其中每个顶点都用附加信息进行注释.

目前，众多模糊聚类算法也已被提出来处理图数据聚类问题.模糊C均值聚类是最常用的模糊聚类技术[12]，由于模糊C均值在某些方面的不足，许多改进算法也已经被提出.在文献[13]中，Naderipour引入了一种基于邻近性的两阶段图数据模糊聚类方法.随后，一种基于抑制性因子的模糊聚类算法[14]被提出，在保证聚类效果的前提下，利用抑制因子提高算法收敛速度.此外，为了处理模糊C均值聚类算法的噪声和较低收敛速度问题，文献[14]提出了一种基于粗糙集思想的改进聚类算法版本，由此可知粗糙集思想已经不断被广泛应用于图数据的模糊聚类中[15].在目前的研究中，基于图数据结构信息和属性信息的相似性度量来聚类是一项基础任务[16].图数据的多样性，如其形状、大小、密度以及噪声的存在，这些都使得对图数据的聚类更加困难[17].因此，研究这样1种全面的聚类方法具有重要意义.在面对任何图数据时，如果直接对图数据进行处理以确定聚类方向，则必须将图数据中所有信息都考虑在内,以达到类内高相似性和类间低相似性的理想目标[18].

通过对以上问题进行分析，本文在前人研究基础上，提出了一种基于目标函数优化的无向加权图粗糙模糊聚类算法.论文基于顶点的综合结构相似性和属性相似性建立无向加权图数据的聚类算法模型.引入粗糙集的上下近似集思想分别设计了类的上近似集和下近似集的模糊中心，并以此建立目标函数迭代优化机制，使得算法能够处理一定的噪声问题，拓宽算法的应用范围，还可以通过选择实验有效性指标的最小值，确定聚类的最佳个数.

为了行文简洁及后文叙述的需要，这里简单阐述与文中相关的一些基本概念，如无向加权图数据、粗糙集和模糊C均值聚类算法.更详细的描述参考文献[9,12,15].

一般地，一个无向加权图数据G可以表示为一个三元组G=(X,E,W)，其中非空有限集合X={x1,x2,…,xn}表示所有顶点的集合.如果每个顶点被m个属性所刻画，那么对应地可表示为xi=(xi1,xi2,…,xim).从矩阵的角度而言，此时X可以采用如下表示

(1)

在无向加权图数据中，E={(xi,xj)|xi,xj∈X}表示边集合，其中(xi,xj)表示图数据中任意2个顶点xi,xj之间的边.W={wij|i,j=1,2,…,n}表示图数据边的权重集合，其中wij为任意两个顶点xi,xj之间边的权重，如果边(xi,xj)∉E，那么wij=0.

粗糙集作为一种处理不精确性和不确定性的软计算工具，其数学描述可以用一对所谓的下近似集和上近似集来表示.给定一个知识库K=(U,R)，其中U表示论域，R表示U上的等价关系.对于任意有限集合X⊆U，{Xi|i=1,2,…,c}是由模糊聚类过程中产生的聚类结果构成的划分，所有类中心的集合为{vi|i=1,2,…,c}，且类中心vi与类Xi是一一对应的，则类Xi关于R的下近似集、上近似集和边界域为

(2)

X的每个类Xi关于等价关系R的近似分类精度aR和粗糙度rR为

(3)

一个集合的不精确性是由其边界域的存在而引起的，并且边界域越大集合的精确性就越低.

进一步，类划分{Xi|i=1,2,…,c}关于R的近似分类精度AR和质量QR为

(4)

近似分类精度描述的是当使用等价关系R聚类时，所有可能的类中被正确聚类的数据所占的百分比，即所有类的下近似集数据在上近似集中的百分比.分类质量表示的是应用R能被确切地分于{Xi|i=1,2,…,c}中类的数据在论域中所占百分比，即所有类的下近似集中数据占论域的百分比，由此分析确定在论文中将近似分类精度和分类质量分别作为下近似集和边界域的计算权重.

模糊C均值聚类算法是数据分析的有用工具，该算法将聚类问题转化成带约束的目标函数最优化问题，因此可借助数学领域中的非线性规划理论进行求解.此算法的目标函数为

(5)

其约束条件为

(6)

公式(5)所描述目标函数的优化过程具体是通过更新以下形式的uij和vi

(7)

(8)

其中uij表示xj关于第i个类的模糊隶属度.m表示模糊因子，用于调整模糊隶属矩阵的模糊程度.‖xj-vi‖2表示xj与第i个类中心vi之间的欧氏距离.

针对无向加权图数据聚类问题，本文从拓扑信息和属性信息角度出发，利用粗糙集思想构建了基于目标函数优化的模糊聚类算法.该算法从以下2个步骤对图数据进行相似性度量和模糊聚类.首先基于共享邻居的结构相似性和边权重贡献构造了无向加权图数据中顶点的综合结构相似性，通过论域上的等价关系R设计出顶点的属性相似性度量方法.其次，通过引入粗糙集思想分别提出模糊类的上近似集和下近似集的类中心表示，并以此为基础建立聚类算法的隶属函数和目标函数优化机制.算法执行过程是基于目标函数优化机制对无向加权图数据进行模糊聚类.

2.1 权重归一化处理

(9)

2.2 综合结构相似性度量

在一个无向加权图数据G=(X,E,W)中，将与顶点xi之间直接由边连接的顶点称为xi的一阶邻居，由所有一阶邻居组成的集合叫作xi的结构邻域，并表示为N[xi]，其集合表达形式为N[xi]={xj∈X|(xi,xj)∈E}.此外，顶点xi的度数记作d[xi]=|N[xi]|，即为一阶邻域中元素的个数.

对于无向加权图数据G=(X,E,W)中任意2个顶点xi和xj，定义其结构相似性为2个顶点的结构邻域N[xi]和N[xj]中共同顶点的数量与它们度数的几何平均数的比值，即

(10)

对于任意2个顶点，如果其结构邻域中的共同顶点越多，则它们之间的结构相似性就越大.以图1中的顶点x1和x2为例不难发现，这2个顶点的共同邻居为x3、x4、x5和x7，即共同邻居的个数为4，由此可计算得2个顶点的度数分别为d[x1]=5，d[x2]=5，进而可根据公式(10)计算顶点x1和x2的结构相似性为S12=0.8.

图1 无向加权图数据

一般地，对于大多数真实无向加权图数据来说，除了具有重要价值的拓扑和属性信息被考虑之外，各个边上带有的权重也不容忽略.权重是对任意2个顶点之间的关联性重要程度的定量分配，对于图数据的聚类仍然具有较大参考价值[19].基于以上对无向加权图数据中顶点的结构相似性讨论，为了发现潜在的具有高相似性的类，下面综合考虑顶点的结构相似性和经过归一化处理后的边权重信息，统一计算两者对无向加权图数据聚类的贡献.

给定G=(X,E,W)，为了有效均衡顶点的结构相似性和边权重的贡献，引入一个均衡参数α∈(0,1)，在实验中取α=0.6.则任意2个顶点xi和xj之间基于结构相似性和边权重的综合结构相似性为

(11)

算法通过综合考虑无向加权图数据的拓扑结构和边的权重，使类内顶点连接紧密的同时使具有较大权重的顶点被划分到一类，而类间顶点之间连接稀疏.这样，既保证具有较大权重边连接的顶点不被分开，同时使类内顶点间连接紧密.

2.3 目标函数优化机制建立

在传统的数据聚类中，顶点只能属于某个特定的类.在模糊聚类中，顶点可以按照一定的隶属程度属于多个类.模糊聚类所获得的聚类结果具有不确定性和模糊化，这种模糊程度由隶属度函数来决定.

给定图数据G=(X,E,W)，其中顶点集为X={xj|j=1,2,…,n}.假设X中顶点被划分到c个类，c个类中心为{vi|i=1,2,…,c}，其类中心与类一一对应.则定义顶点xj关于第i个类的隶属度函数uij为

(12)

基于模糊C均值聚类的类中心更新公式(8)，对于任意X⊆U，{Xi|i=1,2,…,c}是模糊聚类结果构成的一个划分，类中心集合为{vi|i=1,2,…,c}，且每一个类中心vi对应一个类Xi.定义无向加权图数据每个类的类中心计算方式为

(13)

由于顶点隶属度的存在导致每个类表示缺乏确定性，因此引入粗糙集思想使得类可用其一对下近似集和上近似集来表示，针对上近似集和下近似集自然会产生一个表示中心.接下来分别建立类的上下近似集的模糊中心表示.给定知识库K=(U,R)，对于任意X⊆U，对应为G=(X,E,W)中的顶点集X={xj|j=1,2,…,n}，{Xi|i=1,2,…,c}是由模糊聚类过程中产生的聚类结果构成的划分.建立每个划分类的下近似集的模糊中心表示vl和上近似集的模糊中心表示vu.

(14)

其中，vl为划分类Xi下近似集的模糊中心，vu是Xi上近似集的模糊中心.aR和rR为上面已定义的近似精度和粗糙度，AR和QR为近似分类精度和质量.在这里aR代表下近似集的权重并且rR代表上近似集的权重，且有aR+rR=1,aR≥rR.类划分{Xi|i=1,2,…,c}关于R的属性相似性为

(15)

在模糊聚类中，当隶属度约束条件放松时，顶点的隶属度可能大于1.那么每个类中顶点的隶属度就大不相同.换句话说，一些顶点对于每个类可能具有较高隶属度，而其它顶点对于每个类可能具有较低隶属度.如果顶点在一个类中具有较高隶属度，则最终类可能只包含这一个顶点[14]，也就是说，噪声会被聚到单个类，会导致聚类结果不理想.在我们的聚类算法设计中，给出一个可在uij基础上快速提高的隶属度函数

(16)

基于对类上下近似集中心表示和隶属度函数的论述，对给定的图数据G=(X,E,W)，本文尝试构建基于目标函数的模糊聚类方法.其模型的目标函数为

(17)

其中，d(vl,vu,xj)表示图数据中基于类的上近似集和下近似集的模糊中心与所有顶点之间的距离度量，其基于粗糙集思想的数学定义为

(18)

在传统模糊聚类算法中，用一般欧式距离作为顶点之间的相似性或距离度量，且每个类皆用单个类中心来表示.在本文算法中，首先通过引入聚类基于上下近似集的粗糙表示，产生关于上下近似集的模糊中心表示，然后针对这3种模糊中心的表示提出一种特殊的距离度量方式，确定3种模糊类中心vl、vu和vi.

算法通过引入粗糙集中上下近似集的思想，分别设计了相应的类上下近似集的模糊中心表示.针对无向加权图数据，算法综合考虑其拓扑结构信息和边权重得到一种综合结构相似性度量方法.在聚类过程中，以初始化的模糊隶属度矩阵出发，算法通过不断对类中心和模糊隶属度矩阵进行更新迭代，直到目标函数达到稳定值或满足停止阈值，此时便可获得最终的模糊聚类结果.参考算法最终输出的模糊隶属度矩阵，对顶点依据每个类的隶属度进行划分.具体步骤可参考算法 1.

众所周知，模糊聚类算法对初始化聚类中心较敏感，往往会得到显著误差.我们在算法中通过寻找最小指标值对应的类数来确定最优聚类数，以确定类中心.

算法1基于目标函数优化的无向加权图粗糙模糊聚类算法

输入：
无向加权图数据G(X,E,W).

输出：
隶属度矩阵U和类中心V.

过程：

第一步 根据公式(9)归一化处理图数据中边权重.

第二步 初始化算法相关参数：类数c、m=2、ε=0.001、T=0、α=0.6、U0.

第三步 根据公式(11)计算顶点的综合结构相似性.

第四步 根据公式(15)计算顶点的属性相似性.

第五步 根据公式(13)和(14)分别计算类中心vi，上近似集模糊中心vu和下近似集模糊中心vl.

第七步 如果|J(T+1)-J(T)|≤ε，则转到步骤7，否则转到步骤5.

第八步 根据步骤4和步骤5得到U和V，计算算法各项指标值.

第九步 求有效性指标的最小值，选择对应的c作为最佳聚类数.

针对无向加权图数据，本文结合了基于顶点拓扑信息与边权重贡献的综合结构相似性和基于等价关系R的属性相似性度量，提出一种基于目标函数优化的粗糙模糊聚类算法，并且算法通过隶属度函数和类中心的不断更新迭代来记录目标函数的变化趋势.

为了测试算法的聚类性能，实验使用了UCI数据库中的真实数据集，将我们的聚类算法与4种经典聚类算法进行对比.实验环境均为Win10 64位操作系统、Matlab软件、8G内存、Intel(R) Core(TM) i5-10210U CPU.

4.1 实验数据集

本实验将论文提出的聚类算法与其它4种经典的聚类算法分别在4种无向加权图数据集进行比较分析，对比算法分别为近邻传播算法(AP)、近似模糊C均值聚类(AFCM)、基于核的改进模糊C均值聚类(KFCM)和模糊C均值聚类(FCM).表1列出图数据信息并且已进行了标准化处理.

表1 数据集

4.2 评价指标

为验证论文所提出算法模型的有效性，实验共采用了10种常见聚类有效性指标，除了表2已列出的5种指标外还有聚类准确率、召回率、标准化互信息、聚类模块度和运行时间效率.

聚类有效性指标需要突出反映类内紧密度和类之间的分离度[8].划分系数(PC)[3]和划分熵(CE)[3]是聚类模糊性的一种度量指标.PC值越大，CE值越小，表明聚类越明显，算法效果越好.划分指数(SC)[8]是类内紧致性与类间分离度的比值，Davies-Bouldin指数(DBI)[16]和分离指数(S)[16]是类间分离度与类内紧致性的比值.因此，SC值越大表明算法的聚类性能越好；
对于DBI和S来说，情况正好相反.表2为5个聚类有效性指标的简要描述.

表2 有效性指标描述

此外，准确率(Acc)和召回率(Re)的具体公式为

(19)

(20)

其中，ai表示正确划分到类bi的顶点数，bi表示本该属于类bi但被错误划分到其它类的顶点数.

标准化互信息(NMI)的计算方式为

(21)

其中，I(X,Y)为划分类X和Y之间的互信息，H(X)是X的熵，具有如下的表示形式

(22)

其中，H(Y)的计算类似于H(X)，p(i)表示从X中随机选取的顶点在类Xi的概率.

GAO提出评价重叠聚类结果质量的模块度函数(Q)[5]

(23)

其中，kj表示顶点xj的度数，Aij表示图数据的邻接矩阵，m表示图中边个数.

4.3 实验结果

本次实验通过不断增加聚类数和迭代尝试，记录实验所得数据对比结果.下面将5种算法分别在4个图数据上的各类指标对比结果进行展示和分析.

图2展示了所有对比算法分别在4个数据集上的收敛性曲线及对比结果.从整体可以看出，所提出的算法(红色曲线表示)在4个图数据集上都表现出明显的收敛性.随着迭代次数的不断增加，对应的目标函数值都逐渐减小并最终趋于一个稳定的常数值，且收敛于稳定状态经过了较少的迭代次数，这也表明了算法花费较少的运行时间.从单个图数据集上来看，论文提出算法的目标函数趋于稳定过程中的速度基本快于其它对比算法，但因受到不同数据集本身差异的影响，算法在个别迭代次数时的收敛性出现轻微波动，表现为曲线下降的不光滑现象.总体来说，依然可表明我们算法的良好收敛性且较优于其它算法.

图2 算法的收敛性对比

图3分别给出了4个图数据上5种算法聚类结果的指标(仅表2所示指标)对比结果，其中5种颜色分别代表5种指标，横坐标表示5种算法.从图3整体看出，文中算法聚类结果的PC、SC 值较其它算法大，同时CE、S、DBI值较其它算法更小，说明算法整体上具有更明显的正向算法优势.依据指标评价标准，论文提出算法在Cumulative networks数据集上具有更好表现.

表5 算法NMI %

从单个图数据来看，文中的算法在Cumulative networks数据集(图3(a))上相对于其它图数据集获得较小的S值为0.21、 最大的PC值为1.82和最大的SC值为1.51.已知SC是类内紧致性与类间分离度的比值，PC是聚类模糊性的一种度量指标，S是类间分离度与类内紧致性的比值.因此，SC和PC值最大意味着算法聚类性能最好，S值越小聚类越明显，算法效果越好.从3个指标值对比可知，文中算法在Cumulative networks数据集上的聚类效率都明显优于在其它图数据上.

在Les Miserables数据集(图3(b))上，论文所提出算法的最终聚类结果获得了最低的DBI值为0.03、最小的CE值0.2.已知CE是聚类模糊性的一种重要度量指标，DBI是类间分离度与类内紧致性的比值.故由最小的CE和DBI值可以说明所得聚类划分结果越明显，类的模糊性就越低，类间的分离度越大，类内顶点间更紧致，表明算法聚类效果越好.

图3 单个数据集上的PC、CE、SC、S、DBI指标对比

在Netscience数据集(图3(c))上本文算法较其它图数据获得最小CE值为0.2，获得S值为0.32且明显大于算法在Cumulative networks数据集上的结果.S是类间分离度与类内紧致性的比值.因此，S值较小表现出较强聚类性能且聚类越明显.所以仅在Netscience数据集上，算法的S指标值结果不是理想的较小或最小值，说明算法在此数据集上基于S指标表现不明显，而基于CE指标的结果较好.除此之外，指标PC、SC和DBI在此数据集上的数值变化处于中等偏上水平，总体可认为算法在Netscience数据集上基于指标的聚类效果略优于其它图数据，但是相差不大.

在Neural network数据集(图3(d))上，本文算法获得CE值为0.21，较Les Miserables和数据集Netscience仅大0.01.算法获得了最小的S值为0.13，这与Les Miserables数据集上获得的指标值之间的最大差值为0.19.已知S是类间分离度与类内紧致性的一个平衡指标.因此，最小的S值意味着算法聚类结果具有较高类间分离度和类内紧致性.基于算法效率而言，这体现出较其它算法最强的聚类性能和最佳的聚类结果.另外，算法的PC和DBI在此图数据集上的表现不具有很明显的优势.各项聚类效率指标值的对比分析表明我们的算法在单个Neural network数据集相对于其它算法和图数据表现稳定，具有较好聚类性能.

为了更直观地比较算法的优劣，图4分别展示了各个算法分别在4个图数据上聚类结果的Acc、Re、NMI和Q对比情况.相应地，表3～5分别给出Acc、Re和NMI的具体数值.

图4 算法Acc、Re、NMI、Q对比

表3 算法Acc %

从图4(a)和表3来看，本文算法获得最高的Acc值，比其它算法都具有明显地提高.但是AP算法在4个数据集上均获得最低Acc值，这是由于当AP聚类算法被应用于一个图数据时，如果归属同类的顶点相似性很高而不同类的顶点相似度很小，那么这类算法不具有优势.但对于类与类间边界不清晰的图数据来说，我们的算法则更加适用.从单个数据集观察来看，AP算法在Cumulative networks数据集上的聚类结果依然表现最差，而算法与其余3种算法获得了相同且最高的Acc值为90.60%.在Les Miserables数据集上，算法仅与KFCM算法获得相同最高的Acc值，表明2个算法的最高聚类效率.在其余2个图数据上，算法均取得了最高的Acc值，更加说明了我们算法的聚类效果.

通过观察图4(b)和表4发现，本文提出算法依然获得最高Re值，而AP算法获得最低值.从单个图数据来看，算法与对比算法AFCM和KFCM在Cumulative networks数据集上的聚类结果最佳，Re达到最高值90.70%，但是AP算法对于Cumulative networks数据集的Re最低，聚类结果仍然最差.在Les Miserables数据集上，本文算法与KFCM算法取得相同最高Re值为88.00%，而在另外2个图数据上，算法均获得最高值说明了算法在此图数据上的聚类效果最好.

表4 算法Re %

从图4(c)和表5的NMI来看，本文算法依然在单个图数据上均获得最高值.NMI用来衡量2个变量之间的相关性，是一种常见的评价聚类指标.实验中用指标NMI来衡量顶点的实际类别与实验结果是否一致，而最高的值直接说明了算法聚类效率很大程度符合实际结果.从单个图数据来看，算法对于Cumulative networks数据集的聚类结果最佳，标准化互信息达到92.30%，而AP算法获得最低值，算法较之明显提高了7.20%.但在图数据集Les Miserables上，本文算法与KFCM取得相同最高NMI为76.00%.综上分析得本文算法的聚类效率具有明显的优势.同时可通过选择最小指标值找到正确合理的聚类数.

为了进一步证明算法效率，对比算法聚类结果的Q值.已知Q大小取决于聚类情况，其值越接近1表示类结构强度越强，聚类质量越好.图4(d)给出对比结果，从图整体发现，论文提出算法(绿色柱状)在生成高质量聚类的Q值明显大于等于其它算法.在第一个图数据集上，算法同FCM、AFCM和KFCM获得相同且最高的Q为90.70%.在单个的数据集Les Miserables上，算法同KFCM算法获得相同且较高Q值为88.00%，但仅较对比算法AFCM高0.02%，在其余图数据上仅我们的算法获得最高Q值.综上分析表明，本文方法的类识别能力较好.基于获得Q值可以通过选择最高模块度值确定算法的最佳聚类结果.

图5为所有对比算法分别在4个图数据集上的运行时间对比情况，结果同样可证明算法的有效性.从单个数据集来看，在Cumulative networks数据集上，算法较其它算法的运行时间最短，且较KFAM算法运行时间短 0.018 s.在其它数据集上我们算法的运行时间依然是最短的.特别地，在Neural network数据集上，AP、FCM和AFCM算法的运行时间较我们算法更久.从实验结果得出，论文提出的算法继承了模糊C均值算法的时间优势，运行时间比其它算法花费更少，因此在运行时间和内存消耗上都具有优势.这是因为算法不但考虑了图的结构相似性和属性相似性，还考虑了顶点之间边的权重贡献，在聚类数量增多时，顶点间的权重也会增大，此时算法聚类效果更明显.

图5 算法时间效率对比

针对无向加权图数据聚类问题，本文提出了一种考虑图数据属性信息和拓扑信息的粗糙模糊聚类算法.提出一种结合拓扑信息与边权重的综合结构相似性度量方法和一种由等价关系R诱导的属性相似性，并通过结合这2种相似性构建了算法聚类具有快速提高性质的隶属度函数.算法进一步引入粗糙集思想，建立了聚类的上下近似集的模糊中心表示，并以此为基础构建了参与算法迭代的目标函数.实验结果表明，本文提出的算法具有更高效的聚类性能.