Fuzzy BC-k-modes：一种分类矩阵对象数据的聚类算法

李顺勇 余 曼 王改变

(山西大学数学科学学院 山西 太原 030006)

0 引 言

对于数据进行划分时,目前基本上分为两种划分。第一种是硬划分,考虑其类别归属时,一般只考虑0、1这两个值,也就是只能把数据划分到某一个确定的类别中。数据一般可分为三类：数值型数据、分类型数据和混合型数据。与其相对应数据的硬划分的聚类算法具有代表性的是k-means、k-modes和k-prototype算法。对于数值型数据,一般采用k-means[1]算法计算均值,然后对其聚类。Zhou等[2]2015年提出一种基于代数图论的聚类方法,可用来求解大规模谱聚类的近似加权核k-means算法。Li等[3]利用和改进k-means聚类技术,提出了一种新的文本聚类算法。对于分类型数据,由于其数据类型是离散并且无序的,故而不能直接用数值型数据的聚类算法去进行聚类。很多学者对此进行了研究,主要有以下几种聚类算法：Huang等[4]1998年提出了k-modes算法对分类数据进行聚类,主要思想是用modes代替means,是一种简单的匹配不相似度量的聚类算法；林强等[6]综合考虑有序型分类数据中的属性值之间顺序关系、无序型分类数据中不同属性值间的相似性以及考虑各属性间的关系，提出一种适用于混合型分类数据的改进的聚类算法；Ng等[7]2007年提出基于属性的频率计算相似度的方法；Cao等[19]提出了k多权重模式算法对分类矩阵对象数据进行聚类,通过定义两个分类对象数据之间的距离,提出了一种多权重模式的聚类原型的表示方法。由于不同数据在数据库中占有不同的比例,软划分由此产生。Huang等[20]1999年提出了模糊集的概念,引入了关于模糊因子和隶属度矩阵的概念,进一步提出了fuzzy k-modes算法。随后,李顺勇等[21]通过引入模糊因子,定义了矩阵对象之间的相异性度量,提出一种对于矩阵对象数据的MD fuzzy k-modes聚类算法。对于混合型数据，李顺通等[24]提出了一种带权的混合数据确定算法。

本文的研究思路和内容为：1) 引入簇间信息，即不同类中的对象到其他类中心的距离。2) 利用簇间信息及模糊因子构建新目标函数;导出隶属度原型以及聚类中心的更新公式。3) 提出Fuzzy BC-k-modes算法。4) 在四个真实数据集上进行了实验,验证所提算法的有效性。

1 Fuzzy BC-k-modes聚类算法

面向1对1对象数据之间的度量一般采用0-1匹配来度量它们之间的距离,然而本文所研究的分类矩阵对象数据中每一个属性对应着多个分类值,用0-1匹配度量具有局限性,因此,本文引入文献[19]中所提的差异性度量。

1.1 对象间的相异性度量

定义1x={x1,x2,…,xn}是由m个分类属性{a1,a2,…,am}所描述的一组n个分类型矩阵对象数据集,其中xi={xi1,xi2,…,xim},1≤i≤n。xi和xj之间的不相似度量为：

(1)

其中：

(2)

(3)

基于该距离度量的目标函数为：

(4)

其中：

f(·,·)是一个函数,当两个参数值相等,取值为1,否则取值为0。|·|表示一个值的绝对值。

要最小化式(4),需要迭代求解两个子问题：

(5)

式中：1≤i≤n,1≤l≤k。

由文献[20]可知,Z计算如下：

(6)

上述W和Z的更新公式仅仅依赖于簇内信息,然而,一个好的聚类结果应当具有簇内相似度高以及簇间相似度低。上述更新公式忽略了簇间相似性,导致簇间分离较弱。下面从两方面分析其重要性。

1) 固定Z计算W若只考虑簇内信息,如图1所示,可以看到d(xi,z1)=d(xi,z2)

图1 簇间信息固定Z计算W

2) 固定W计算Z若只考虑簇内信息基于每一个分类值在聚类中的频率去表示聚类的中心,将会导致集群中分类值出现的频率起决定作用,然而分类值出现的频率很可能被高估,因为分类值在其他簇中也可能会出现较高的频率。例如：表1展示了三个簇中的属性分布,由表1可以看出,分类值A在Cluster2中出现的频率最高,并且在其他簇中出现频率较低,故可以用分类值A表示Cluster2的中心,但分类值B在Cluster3中出现的频率最高,但在Cluster1中出现的频率也相对较高,相比较而言,虽然分类值C在Cluster3的频率低于分类值B的频率,但分类值C集中出现在Cluster3中,因此,用分类值C表示Cluster3的中心更好。这表明如果仅仅只考虑频率最高作为聚类的中心,将产生不太好的结果。

表1 簇间信息固定W计算Z

从上面的分析可以看出,簇间信息有助于在迭代过程中获得更好的W和Z。因此,我们将给出簇间信息的定义,并提出新的聚类算法,同时考虑簇间信息及簇内信息。

1.2 簇间信息

定义2zl表示第l个簇原型,zh表示第h个簇原型,h和l不相等,则zl和zh之间的相似性度量为：

(7)

定义3zl表示第l个簇原型,由zl表示的第l个簇与其他簇之间的相似性度量为：

(8)

定义4基于簇间分离的目标函数为：

(9)

要最小化式(8),需要迭代求解以下两个子问题：

(10)

基于此,对簇间分离目标函数进行评价：

(11)

(12)

式中：1≤j≤m,1≤l≤k。

1.3 启发式更新类中心

定义5如果Zl能使下面的目标函数Fn(W,Zl,γ)达到最小,则称Zl是W的类中心。

Fn(W,Zl,γ)=F′(W,Zl)+γB(W,Zl)=

(13)

参数γ用来调整簇内信息以及簇间信息对于目标函数最小化的影响。

1) 当γ>0时,B(W,Z)对Fn(W,Z,γ)的最小化起到重要作用,聚类过程尝试将这些点分配到离A相对较远的一个聚类中,使簇间相似度减少,当对象的位置固定时,为了使簇间相似度减少,聚类过程会将聚类原型移动到离A代表点较远的位置。然而,γ的值不应该太大,这是因为若γ很大时,簇间相似项会占主导地位,聚类原型会被移动到的离群值。

2) 当γ=0时,B(W,Z)对Fn(W,Z,γ)的最小化不起任何作用,聚类过程将使簇内分离最小。

3) 当γ<0时,聚类过程会将聚类原型移动A到代表点位置,这与聚类原始思想矛盾,因此γ不能小于0。

基本算法步骤描述如下：

1) 令Γ={γ1,γ2,…,γo}是这样一个序列,其中γ1>γ2>…>γo,选择一个初始点集Ze⊆R,设置e=1。

(14)

(15)

1.4 Fuzzy BC-k-modes聚类算法

基于此,提出一种Fuzzy BC-k-modes聚类算法。首先给出了一个新目标函数：

Fn(W,Z,γ)=F′(W,Z)+γB(W,Z)=

(16)

要最小化目标函数式(13),需要迭代求解以下两个子问题：

(17)

对于1≤i≤n,1≤l≤k。

(18)

(19)

是非负并且独立的,令：

(20)

(21)

式中：1≤j≤m,1≤l≤k。

算法1Fuzzy BC-k-modes算法

输入：n：每个集群中对象的数量;k：聚类个数;α：模糊因子;ε：阈值;X：由m个属性描述的n个矩阵对象数据;idcenters：k个初始类中心的标签。

输出：cid：聚类后对象标签;num：迭代次数。

1.Method：

2.Z按照索引在idcenters中存储k个初始中心,value=0,num=0;

3.whilenum≤100 do

4.newvalue=0;

5.fori=1 tondo

6.forl=1 tondo

7.通过式(1)计算第i个对象到第l个聚类中心的距离;

8.通过式(8)计算第l个簇与其他簇之间的相似性度量;

9.通过式(18)计算第i个对象到第l个聚类中心的隶属度;

10.end for

11.end for

13.if |newvalue-value|≤ε,break；

elsevalue=newvalue且num=num+1;

14.forl=1 tokdo

15.使用1.3节启发式更新类中心;

16.end for

17.end while

2 真实数据实验

本节主要在Market basket data(Data website下载),Microsoft web data(UCI数据集下载),Movielens data(Movielens website下载),Alibaba data(competition website下载)四个数据集上进行了实验。首先对四组数据进行了数据预处理,接着利用五个评价指标进行了有效性分析,最后,将该算法与其他算法进行比较,并且讨论了模糊因子与隶属度之间的关系。

2.1 数据预处理

为了获得给定数据集的结构,使用了多维缩放技术来可视化数据,该技术主要目标是通过n×n的距离矩阵去得到一个n行,p列的结构。从MATLAB传递到函数,n个点之间的欧氏距离近似于n×n距离矩阵中对应的不相似点的单调变换,因此,可以可视化n个点来反映数据的分布。为了使数据可视化,设置p=2。四个真实数据集的预处理结果如表2所示。

表2 预处理后的数据集

2.2 评价标准

为了去评价所提出算法的有效性,我们采用了以下的五个外部指标：(1)ARI(兰德指数,衡量两个数据分布的吻合程度);(2)AC(精度,表示正确分类的测试实例的个数占测试实例总数的比例);(3)PR(纯度,也叫查准率,表示正确分类的正例个数占分类为正例的实例个数的比例);(4)RE(召回率,也叫查全率,表示正确分类的正例个数占实际正例个数的比例);(5)NMI(归一互化信息,衡量两个数据分布的吻合程度)。可以明显看出,五个评价指标值越大,聚类结果越好。

(22)

(23)

(24)

(25)

(26)

2.3 MD fuzzy k-modes算法与其他算法的比较

选取SV-k-modes、k-mw-modes、fuzzy k-modes、fuzzy SV-k-modes、MD fuzzy k-modes这五种算法与Fuzzy BC-k-modes算法进行比较。与SV-k-modes、k-mw-modes比较时,由于这两种算法里不含有模糊因子,因此将新提出的算法的模糊因子设为1.1。在与fuzzy k-modes、fuzzy SV-k-modes和MD fuzzy k-modes这三种算法比较时,不同的模糊因子对于聚类结果存在不同的影响,很多学者已经研究过这一问题,Huang[20]设置模糊因子的最小值为1.1,Zhou[28]认为模糊因子的最优区间[2.5,3],Pal等[29]在fuzzyk-means算法中建议采取[1.5,2.5],Yu等[26]提出了模糊因子的理论上界。在这个实验中设置选取序列Γ={γ1,γ2,…，γo}，设置γ1=1,γ0=0且γe+1=γe-0.1，设置1≤e

表3 在五个数据集上三种算法比较

表3显示,在不考虑模糊因子的情形下,与SV-k-modes算法相比说明Fuzzy BC-k-modes算法在Market Basket data、Microsoft Web data、Movielens data上的AC、PR、RE值有15%～25%的提高,ARI、NMI的值有20%～40%的提高。在Alibaba data数据集上AC、RE、ARI、NMI的值有10%左右的提高。与k-mw-modes算法相比，Fuzzy BC-k-modes算法在四个真实数据集的五个评价指标上的值有约3%的提高,最高提高8%,说明Fuzzy BC-k-modes算法的聚类效果要优于k-mw-modes算法。

从表4-表7可以看出,当考虑模糊因子时,与fuzzy k-modes算法相比, Fuzzy BC-k-modes算法在Market Basket data上和Microsoft Web data上的AC、PR、RE值有30%～35%的提高,ARI、NMI的值有60%的提高,在Movielens data上和Alibaba data上,虽然RE值有所下降,但AC、PR值有10%的提高,ARI、NMI的值有15%的提高,说明Fuzzy BC-k-modes算法的聚类效果要优于fuzzy k-modes算法。与fuzzy SV-k-modes算法相比,Fuzzy BC-k-modes算法在Market Basket和Microsoft Web data上AC、PR、RE值有10%的提高,ARI、NMI的值有20%的提高,在Movielens data和Alibaba data上AC、PR、RE、ARI、NMI的值有约4%的提高,说明Fuzzy BC-k-modes的算法的聚类效果要优于fuzzy SV-k-modes。与MD fuzzy k-modes算法相比,Fuzzy BC-k-modes算法在四个真实数据集的五个评价指标上的值有3%的提高,说明Fuzzy BC-k-modes算法的聚类效果要优于MD fuzzy k-modes算法。

表4 在Market Basket data数据集上四种算法的对比

续表4

表5 在Microsoft Web data数据集上四种算法的对比

表6 在MovieLens data数据集上四种算法的对比

续表6

表7 在Alilibaba data数据集上四种算法的对比

2.4 α与W的关系

模糊因子的大小影响到对象分配到不同集群的隶属度,因此研究模糊因子与隶属度之间的关系是非常有必要的。实验分析了四个数据集上模糊因子与隶属度之间的关系,模糊因子的值从1.1到2.9,步长为0.2,由于所要研究的数据集中对象个数过多,在2.1节已经对数据进行预处理,因此只在每个数据集可视化前十个对象作为其研究对象,分别在四个数据集上进行了30次实验,取其平均值,实验结果如图2-图5所示。

图2 在Market Basket数据集上α与W的关系图

图3 在Microsoft Web数据集上α与W的关系图

图4 在MovieLens数据集上α与W的关系图

图5 在Alibaba数据集上α与W的关系图

图2-图5显示了隶属度与模糊因子α之间确实存在关系。随着模糊因子α的增大,曲线越平缓,即隶属于同一类的可能性越大。

3 结 语

本文对于矩阵对象数据提出了一种新的聚类算法：Fuzzy BC-k-modes算法。在Fuzzy BC-k-modes算法中,首先给出矩阵对象之间的差异性度量,其次引入了簇间信息,集成了簇内信息和簇间信息,提出了新的目标函数,通过修改目标函数的方法解决矩阵对象数据的聚类问题,然后,提出了一种Fuzzy BC-k-modes算法。最后在四个数据集上进行了实验,验证了Fuzzy BC-k-modes算法的有效性。与此同时，本文提出的算法对未来解决包含各种复杂簇结构的问题，以及考虑如何融入簇间差距的问题上将会有较好的启发作用。