聚类算法中最具代表性的是k-means，k-modes，k-prototype算法，其中，k-means[1]主要用于对数值型数据进行聚类.现实中，分类型属性数据也常见.1998年Huang[2]提出了k-modes算法，该算法用简单匹配计算2个对象间的距离，用modes代替means，基于频率来更新类中心.2001年Chaturvedi等人[3]改进了k-modes算法，提出了k-modes-CGC算法，有效地运用非参数方法对分类型数据进行聚类.随后，Huang等人[4]证明了二者的等价性.此外，在初始类中心的选取上，Ying等人[5]考虑将迭代求精法与k-modes算法结合；在相异性度量的选取上，Ng等人[6]和San等人[7]基于属性频率计算相似度，Li等人[8]基于生物特征计算距离.Liang等人[9-14]也基于不同度量提出了多种k-modes的改进算法.

以上种种算法在考虑类别归属时，其隶属度只考虑了0，1这2个值，即只能划分到确定的某一类中，属于硬划分.而数据的不同属性重要度会给部分数据的真实类别归属带来模糊性.粗糙集[15]和模糊集[16]理论的提出为数据在数据集中的位置提供了有利的基础，软划分应运而生.Bezdek提出的fuzzy c-means(FCM)算法[17]是软划分聚类的典例.1999年Huang等人[18]在FCM算法的基础上引进模糊因子、隶属度矩阵等，进一步提出fuzzy k-modes算法.2004年Kim等人[19]用模糊集对类中心的模糊化刻画分类数据中类的不确定性，提出了具有模糊类中心的Fuzzy k-modes算法.2005年Li等人[20]提出了基于特征加权的模糊聚类新算法(novel feature weighted clustering algorithm, NFWFCA).2007年Cai等人[21]结合局部空间和灰度信息，提出了快速通用的聚类算法(fast generalized fuzzy c-means, FGFCM).2016年Zhou等人[22]结合多目标优化算法与模糊中心点聚类，提出一种新颖的多目标模糊聚类算法.总之，k-modes算法对后续众多的拓展算法起到了积极的铺垫作用.

已有的聚类算法普遍使用X={X1,X2,…,Xn}的数据表示模式，X表示由n个对象组成的对象集， Xi=(Xi1,Xi2,…,Xim)表示每个对象由m个属性特征描述，每个属性特征有且仅有唯一的取值.然而实际应用中，对象的每个属性特征可能有不同的取值.例如顾客购物时，可能同时购买多个产品，这就容易产生矩阵对象数据[23].若利用已有的聚类算法处理该类数据，需用先验知识来选取其中一条记录，这会严重损失信息并破坏数据的原始性，且违背了以数据总体来做数据分析的初衷.因此，为了利用多条消费记录发现客户的消费喜好，从而做出更具针对性的推荐[23]，有必要研究基于矩阵对象数据的聚类算法.Cao等人[24]首先提出基于集值对象的Set-Value k-modes (SV-k-modes)算法和fuzzy Set-Value k-modes(fuzzy SV-k-modes)算法[25].之后，Cao等人又提出基于矩阵对象的k-multi-weighted-modes(k-mw-modes)聚类算法[23].该算法在考虑类别归属的同时，其隶属度也仅仅考虑了0，1这2个值.由于数据集中属性重要度的不同，常常会给部分数据的真实类别归属带来模糊性.本文兼顾模糊集引入模糊因子，提出一种基于矩阵对象数据的模糊聚类算法(matrix-object data fuzzy k-modes, MD fuzzy k-modes).本文的主要贡献有4个方面：

1) 结合模糊集的概念提出了一种更新类中心启发式算法；

2) 提出了基于分类型矩阵对象数据的MD fuzzy k-modes聚类算法；

3) 实验验证了MD fuzzy k-modes算法的有效性；

4) 分析了模糊因子β与隶属度w的关系.

1 回顾fuzzy k-modes算法

设X={X1,X2,…,Xn}是由n个对象、m个属性描述的分类型数据集，则Xi与Xj间的相异性度量定义为

(1)

其中，

Q是X的类中心，如果Q能最小化

(2)

fuzzy k-modes算法用迭代方式将数据分为k类， 此算法的目的是最小化目标函数：

(3)

其中，W为隶属度矩阵.

2 MD fuzzy k-modes聚类算法

经典的k-type算法[1-2]主要由3部分组成：相异性度量的定义、类中心的表示和类中心的更新过程.本文提出的MD fuzzy k-modes算法也从这3方面考虑.

2.1 矩阵对象间的相异性度量

用简单0-1匹配、属性频率等相异性度量来计算数据间的距离适用于1对1对象数据，而矩阵对象数据每个属性有多于一个的属性值，这些相异性度量对矩阵对象数据有一定的局限性，由于k-mw-modes算法[23]中定义了2个矩阵对象间的相异性度量，本文直接引用此相异性度量.

定义1. 相异性度量.给定矩阵对象Xi,Xj，每个对象由m个分类型属性{A1,A2,…,Am}来描述，则Xi与Xj的相异性度量定义为

(4)

其中：

δ(Xis,Xjs)=

(5)

(6)

式(5)中表示矩阵对象Xi在属性As上的所有属性值,即值域.12是标准化因子，因为0≤δ(Xis,Xjs)≤2，当=时，δ(Xis,Xjs)=0；当∩=∅时，δ(Xis,Xjs)=2.

可以验证该相异性度量满足非负性、对称性和三角不等式性，的确是一个距离.

例1. 表1是某一矩阵对象数据集的描述，其中X={X1,X2}，A={A1,A2}，计算X1,X2间的距离.

在属性A1上，在属性A2上，所以，X1,X2间的距离

2.2 类中心的定义及启发式更新过程

聚类目的使是“类内距离最小，类间距离最大”，即同类中每个对象到类中心的距离最小，不同类中的对象到其他类中心的距离最大.因此，聚类过程中类中心的表示是必需的.针对一个集合的mode[2]，集合X′={x1,x2,…,xn}的mode是一个向量Q′=(q1,q2,…,qm)，使得目标函数最小化.也就是说，qs(1≤s≤m)是集合X关于第s个属性出现最频繁的值，使得向量Q′是一个mode.本文在k-mw-modes算法的基础上引入了模糊因子β和隶属度w.这样，目标函数在考虑距离的同时也应兼顾模糊隶属度.

定义2. 类中心.如果Ql能使目标函数达到最小:

(7)

则Ql是X的类中心.

要求类中心Ql，即要最小化D(X,Ql)，根据定义1，仅需要最小化设属性As的属性个数为|Vs|，那么，其类中心Qls属性值的个数只能从1到|Vs|中选，若要从|Vs|中选us个作为Qls的属性值，则有种情况，而us的取值范围也是1到|Vs|，根据多项式理论，类中心在属性As上的选择有2|Vs|-1种，需要遍历每种情况求再按降序排列，才能更新出在属性As上的类中心.同理，其他属性的类中心也可更新出来.

这种全局性更新类中心算法的时间复杂度为O(nmtk×2|V′|)，n表示对象数，m表示属性个数，k表示分类个数，t表示迭代次数，|V′|=max{|Vs|,1≤s≤m}.由此可知，全局性更新类中心的算法时间复杂度随着对象个数、属性个数、分类数及迭代次数的增多呈线性增长，属性值的个数呈指数增长.

当矩阵对象数据中属性值个数过多时，全局更新类中心的算法计算量过大，耗时增强，故本文提出了启发式更新类中心算法.首先分析

(8)

这里记称作Xi的属性值的权重.

由式(8)可知，要想使最小，则需使最大.

假设第l类中属性Aj的值域是计算并按降序排列.若Qlj有rj个值，则有3种情形.

1) 当rj=1时，若

则Qlj={}；若有多于一个的最大值，则随机取一个.

2) 当时，则取全部值作为类中心.

3) 当时，有3种情形：

① 若选前rj个值作为类中心.

② 若则先选前rj-1个值Q″={,,…,}作

为Qlj的一部分.若则Qlj={}∪Q″；若

则Qlj={}∪Q″，若则随机取一个.

③ 若

则先选前rj-p′-1个属性值作为类中心的一部分，记为Q″={,,…,},再从接下来的p′+p+1个属性值中选p′+1个作为剩余部分.假设Qj是剩余属性值的所有组合的集合，Rt是Qj中每个组合的频率和，若

矩阵对象数据中每个属性有多于一个的属性值，类中心的属性个数rj取多少恰当也是一个值得研究的课题.为了增加算法的有效性，本文令根据以上启发式更新算法，属性Aj的类中心可以更新出来.同理，其他属性的类中心也能找到.

2.3 MD fuzzy k-modes聚类算法

k-means算法、k-modes算法、k-mw-modes算法的聚类目的是找到隶属度矩阵W和类中心Q，并使目标函数最小化；拓展的fuzzy k-means，fuzzy k-modes算法的聚类目的也是找到W和Q，使目标函数最小.

本文在k-mw-modes算法的基础上，引入模糊因子并改进了类中心的表示及更新过程，提出了MD fuzzy k-modes算法.

定义3. 最小化目标函数.将一矩阵对象数据集X={X1,X2,…,Xn}划分为k类，则需最小化目标函数:

(9)

且满足:

wli∈[0,1], 1≤l≤k, 1≤i≤n,

(10)

(11)

(12)

其中，Q=(Q1,Q2,…,Qk)中的元素Ql表示第l类的中心，Ql=(Ql1,Ql2,…,Qlm);W=(wli)是一个k×n维的隶属度矩阵，wli=1表示Xi被分到l类.

为使F′(W,Q)达到最小，要通过多次迭代过程使其收敛：1) 初始化类中心Qt；2) 固定Qt，找出使F′(W,Q)最小的Wt；3) 固定Wt，用启发式更新算法找出Qt+1使F′(W,Q)达到最小；4) 重复步骤1)2)3)，直到类中心不变或目标函数小于阈值为止.

其中，隶属度矩阵W由定理1计算而来，类中心Q的更新由启发式更新算法而来.

定理1. 固定Q，在式(10)～(12)的限制下使F′(W,Q)最小，则W的更新为

(13)

MD fuzzy k-modes算法的基本步骤：

1) 随机选取k个对象作为初始类中心；

2) 根据2.1节，计算每个对象到k个中心的距离，将对象分配到与其距离最小的类中；

3) 根据2.2节，计算每个对象到k个中心的隶属度，并更新k个类的类中心；

4) 重复步骤2)3)，直到类中心或目标函数不变为止.

算法1. MD fuzzy k-modes算法.

输入：X为由m个属性描述的n维矩阵对象数据,k为需要聚类个数,ε为阈值,idCenters为k个初始类中心的标签,β为模糊因子；

输出：cid是聚类后所有对象的标签,num是迭代次数.

① Q是初始类中心，value=0，num=0；

② while num<100 do

③ newvalue=0;

④ for i=1 to n do

⑤ for l=1 to k do

⑥ 计算第i个对象到第l个中心的距离d(Xi,Ql)(用式(4))；

⑦ end for

⑧ end for

⑨ for i=1 to n do

⑩ for l=1 to k do

计算第i个对象到第l个中心的隶属度wli(用式(13))；

end for

end for

if |newvalue-value|≤ε

break;

else

value=newvalue且num=num+1；

end if

for l=1 to k do

更新类中心Q(用启发式更新算法)；

end for

end while

3 实验分析

为了评价MD fuzzy k-modes算法的有效性，本文考虑了5个真实数据集：Market Basket，Micro-soft Web，Musk，MovieLens，Alibaba.Market Basket记录了1 001个顾客的交易记录，每条记录由用户ID、交易时间、产品名称和产品ID这4个属性描述；Microsoft Web来自UCI数据集，记录了1998年1月份某周内32 711个匿名用户的网页浏览情况，每个用户由用户ID和网页ID这2个属性描述；Musk也来自UCI数据集，包括92个对象，每个对象由167个属性描述；MovieLens从MovieLens网站上下载，本文只使用其中的ratings数据，它记录了6 040个观众对3 900部电影的1 000 209条评分情况，每条记录由用户ID、电影ID、用户评分和提交评价的时间这4个属性描述;Alibaba是884个用户浏览某些品牌的182 880条记录，也由4个属性描述.这5个数据集均为矩阵对象数据集.为了增强聚类效果，本文对各数据集的属性做了相应的预处理,预处理后的数据形式如表2所示：

3.1 评价标准

本文采用精度(AC)、纯度(PR)、召回率(RE)、兰德指数(ARI)、归一化互信息(NMI)这5个评价指标对所提算法进行了有效性评价.AC表示分类正确的比例;PR表示预测为正的样本中有多少是对的;RE表示样本中的正例有多少被预测正确;ARI和NMI用来衡量2个数据分布的吻合程度.AC，PR，RE，ARI，NMI的值越大，聚类结果越接近于数据集的真实划分，聚类效果越好.

设X是一矩阵对象数据集，C={C1,C2,…,Ck}是X的聚类结果，P={P1,P2,…,Pk′}是真实标签，聚类个数为k，真实类别数为k′.假定k=k′，5种评价指标定义为

(14)

(15)

(16)

ARI=

),

(17)

(18)

其中，nCi和nPj分别是Ci和Pj中对象的个数，表示正确分到i类中的对象个数.如果聚类结果越接近于数据集的真实划分，那么AC，PR，RE，ARI，NMI的值就越大，最大值为1.换句话说，实验结果在这5个评价标准上的值越大，聚类质量越好，算法越有效.

3.2 启发式与全局性更新类中心算法的比较

为了评价启发式更新类中心算法的有效性，本节在用MD fuzzy k-modes算法聚类的过程中，分别采用启发式(HAMF)和全局性算法(GAMF)更新类中心，对比了实验结果与运行时间.以Market Basket为例，运行10次，结果如表3和表4所示.其中,表3的“±”前后分别表示均值和标准差.

Table 4 Running Time of the MD fuzzy k-modes Algorithms

with GAMF and HAMF

表4 MD fuzzy k-modes算法中用GAMF和HAMF更新

类中心的运行时间

Notes: The bold value represents that the running time of the MD fuzzy k-modes algorithm with HAMF is much shorter than GAMF.

从表3和表4可以看出，用全局性算法更新类中心的聚类效果要好于启发式更新算法，但耗时长达96 h.而启发式更新算法在聚类效果相似的情况下只需耗时160 s.因此，在用MD fuzzy k-modes算法进行聚类时，选用本文提出的启发式更新算法更有效.

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

本文选SV-k-modes，k-mw-modes，fuzzy k-modes，fuzzy SV-k-modes这4种算法与MD fuzzy k-modes算法进行比较，其中，fuzzy k-modes算法必须把矩阵数据转换为单值属性值形式，SV-k-modes，fuzzy SV-k-modes算法需把矩阵数据转换为集值数据形式.在与SV-k-modes，k-mw-modes算法比较时，由于这2种算法不含模糊因子β，本文假定MD fuzzy k-modes算法中的β=1.1.在与fuzzy k-modes，fuzzy SV-k-modes算法进行比较时，由于在fuzzy k-type聚类算法[17-21]中，初始类中心的选取和模糊因子β对聚类结果有重要的影响，不同的初始化类中心和不同的β取值会导致聚类结果不同.本文从这2方面验证MD fuzzy k-modes算法的有效性.在β的取值上，目前很多学者研究这一问题.Pal和Bezdek[26]在fuzzy k-means算法中设置β∈[1.5,2.5]，Zhou等人[27]认为β的最优区间是[2.5,3]，Huang等人[18]设置最小值β=1.1.由于β的取值没有公认的准则，目前研究的最小值为1.1，最大值为3.本文设置β∈[1.1,2.9]，步长为0.2.在初始类中心的选择上，本文随机初始化类中心30次，即2种算法在不同的β取值下分别运行30次，通过计算平均聚类质量来验证MD fuzzy k-modes算法的有效性.数据集Market Basket，Microsoft Web，Musk，MovieLens，Alibaba在这5种评价标准上的实验结果如表5～9所示.其中，“±”前后分别表示30次实验结果的均值和标准差.

从表5可以看出，在不考虑模糊因子β的情况下，新提出的MD fuzzy k-modes算法比SV-k-modes算法、k-mw-modes算法在5种评价标准上的值高，说明聚类效果更好.

表6～9显示，考虑模糊因子β时， MD fuzzy k-modes算法相较fuzzy k-modes算法在5种评价标准上的值有明显提高.尤其是Market Basket和Microsoft Web数据集上，AC，PR，RE，ARI，NMI值有30%～60%的提高，这说明MD fuzzy k-modes算法要比fuzzy k-modes算法的聚类效果好得多.在MovieLens数据集上RE值虽有所下降，但在其他评价标准上有20%左右的提高；Musk数据集的实验结果虽然没有前3个数据集的效果明显，但仍比fuzzy k-modes算法的值高.再者，相较fuzzy SV- k-modes算法，5种评价标准上的值也有所提高.在Market Basket和Microsoft Web数据集上，AC，PR，RE，ARI，NMI值有10%～20%的提高，在Musk，MovieLens数据集上的值相近，但比fuzzy SV-k-modes算法的值高，也说明聚类效果好.

上述实验结果充分验证了MD fuzzy k-modes算法对矩阵对象数据进行聚类具有较好的可行性与有效性.

Notes: The bold values represent that the highest value obtained by the MD fuzzy k-modes algorithm.

Notes: The bold values represent that the highest value obtained by the MD fuzzy k-modes algorithm.

Notes: The bold values represent that the highest value obtained by the MD fuzzy k-modes algorithm.

Notes: The bold values represent that the highest value obtained by the MD fuzzy k-modes algorithm.

Notes: The bold values represent that the highest value obtained by the MD fuzzy k-modes algorithm.

3.4 β与w的关系

由于β的取值直接影响矩阵对象归属到每个类别的隶属度，因此有必要分析模糊因子β与隶属度w的关系.由于数据集的对象数过多，本文只取前10个对象作为研究对象.经过30次实验后求平均，Market Basket，Microsoft Web，Musk，MovieLens这4个数据集的实验结果分别如图1～4所示.其中，“○”表示矩阵对象分到第1类，“★”表示矩阵对象分到第2类，“□”表示矩阵对象分到第3类，“+”表示矩阵对象分到第4类.

由图1～4可知：隶属度w明显受模糊因子β的影响.随着β的增大，w的值呈递减(或递增)形式变化.β的值越大，曲线越平缓，即隶属同一类别的可能性越趋于一致.

4 结 论

实际应用中，大多数数据都是矩阵对象数据，为了对这类数据进行聚类，本文提出了一种新的聚类算法——MD fuzzy k-modes算法.首先，引用了矩阵对象间的相异性度量；其次，给出类中心的表示及启发式更新算法；再次，提出了MD fuzzy k-modes算法；最后通过在Market Basket，Microsoft Web，Musk，MovieLens，Alibaba这5个数据集上的实验分析，验证了本文所提出的MD fuzzy k-modes算法在聚类效果上的有效性并分析了模糊因子β与隶属度w之间的关系.大数据时代，通过MD fuzzy k-modes算法对多条记录进行聚类，能更易发现客户的消费喜好，从而做出具有针对性的推荐.

参考文献

[1]Macqueen J. Some methods for classification and analysis of multivariate observations[C] //Proc of the 5th Berkeley Symp on Mathematical Statistics and Probability. Oakland, CA: University of California Press, 1967: 281-297

[2]Huang Zhexue. Extensions to the k-means algorithm for clustering large data sets with categorical values[J]. Data Mining and Knowledge Discovery, 1998, 2(3): 283-304

[3]Chaturvedi A, Green P E, Caroll J D. K-modes clustering[J]. Journal of Classification, 2001, 18(1): 35-55

[4]Huang Zhexue, Ng M K. A note on k-modes clustering[J]. Journal of Classification, 2003, 20(2): 257-261

[5]Ying Sun, Zhu Qiuming, Chen Zhengxin. An iterative initial-points refinement algorithm for categorical data clustering[J]. Pattern Recognition Letters, 2002, 23(7): 875-884

[6]Ng M K, Li Mark Junjie, Huang Joshua Zhexue, et al. On the impact of dissimilarity measure in k-modes clustering algorithm[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2007, 29(3): 503-507

[7]San O M, Huynh V N, Nakamori Y. An alternative extension of the k-means algorithm for clustering categorical data[J]. International Journal of Applied Mathematics & Computer Science, 2004, 14(2): 241-247

[8]Li Cen, Biswas G. Unsupervised learning with mixed numeric and nominal data[J]. IEEE Transactions on Knowledge & Data Engineering, 2002, 14(4): 673-690

[9]Liang Jiye, Bai Liang, Cao Fuyuan. K-modes clustering algorithm based on a new distance measure[J]. Journal of Computer Research and Development, 2010, 47(10): 1749-1755 (in Chinese)(梁吉业, 白亮, 曹付元. 基于新的距离度量的K-modes聚类算法[J]. 计算机研究与发展, 2010, 47(10): 1749-1755)

[10]Bai Liang, Liang Jiye. The k-modes type clustering plus between-cluster information for categorical data[J]. Neurocomputing, 2014, 133(133): 111-121

[11]Cao Fuyuan, Liang Jiye, Bai Liang, et al. A framework for clustering categorical time-evolving data[J]. IEEE Transactions on Fuzzy Systems, 2010, 18(5): 872-882

[12]Cao Fuyuan, Liang Jiye. A data labeling method for clustering categorical data[J]. Expert Systems with Applications, 2011, 38(3): 2381-2385

[13]Cao Fuyuan, Liang Jiye, Li Deyu, et al. A dissimilarity measure for the k-modes clustering algorithm[J]. Knowledge-Based Systems, 2012, 26(9): 120-127

[14]Cao Fuyuan, Liang Jiye, Li Deyu, et al. A weighting k-modes algorithm for subspace clustering of categorical data[J]. Neurocomputing, 2013, 108(5): 23-30

[15]Pawlak Z. Rough Sets: Theoretical Aspects of Reasoning about Data[M]. Dordrecht, Netherland: Kluwer Academic Publishers, 1992

[16]Lehmann I, Weber R, Zimmermann H J. Fuzzy set theory[J]. Operations-Research-Spektrum, 1992, 14(1): 1-9

[17]Bezdek J C, Ehrlich R, Full W. FCM: The fuzzy c-means clustering algorithm[J]. Computers & Geosciences, 1984, 10(2/3): 191-203

[18]Huang Zhexue, Ng M K. A fuzzy k-modes algorithm for clustering categorical data[J]. IEEE Transactions on Fuzzy Systems, 1999, 7(4): 446-452

[19]Kim D W, Lee K H, Lee D. Fuzzy clustering of categorical data using fuzzy centroids[J]. Pattern Recognition Letters, 2004, 25(11): 1263- 1271

[20]Li Jie, Gao Xinbo, Jiao Licheng. A new feature weighted fuzzy clustering algorithm[C] //Proc of the Int Workshop on Rough Sets. Berlin: Springer, 2005: 412-420

[21]Cai Weiling, Chen Songcan, Zhang Daoqiang. Fast and robust fuzzy c-means clustering algorithms incorporating local information for image segmentation[J]. Pattern Recognition, 2007, 40(3): 825-838

[22]Zhou Zhiping, Zhu Shuwei, Zhang Daowen. Multiobjective clustering algorithm with fuzzy centroids for categorical data[J]. Journal of Computer Research and Development, 2016, 53(11): 2594-2606 (in Chinese)(周治平, 朱书伟, 张道文. 分类数据的多目标模糊中心点聚类算法[J]. 计算机研究与发展, 2016, 53(11): 2594-2606)

[23]Cao Fuyuan, Yu Liqin, Huang Joshua Zhexue, et al. k-mw-modes: An algorithm for clustering categorical matrix-object data[J]. Applied Soft Computing, 2017, 57: 605-614

[24]Cao Fuyuan, Huang Joshua Zhexue, Liang Jiye, et al. An algorithm for clustering categorical data with set-valued features[J]. IEEE Transactions on Neural Networks & Learning Systems, 2018, 29(10): 4593-4606

[25]Cao Fuyuan, Huang Joshua Zhexue, Liang Jiye, et al. A fuzzy SV-k-modes algorithm for clustering categorical data with set-valued attributes[J]. Applied Mathematics & Computation, 2017, 295: 1-15

[26]Pal N R, Bezdek J C. On cluster validity for the fuzzy c-means model[J]. IEEE Transactions on Fuzzy Systems, 1995, 3(3): 370-379

[27]Zhou Kaile, Fu Chao, Yang Shanlin. Fuzziness parameter selection in fuzzy c-means: The perspective of cluster validation[J]. Science China Information Sciences, 2014, 57(11): 1-8

A MD fuzzy k-modes Algorithm for Clustering Categorical Matrix-Object Data

Li Shunyong1, Zhang Miaomiao1, and Cao Fuyuan2

1(School of Mathematical Sciences, Shanxi University, Taiyuan 030006)2(School of Computer and Information Technology, Shanxi University, Taiyuan 030006)

Abstract Traditional algorithms generally cluster single-valued attributed data. However, in practice, each attribute of the data object is described by more than one feature vector. For example, customers may purchase multiple products at the same time as they shop. An object described by multiple feature vectors is called a matrix object and such data are called matrix-object data. At present, the research work on clustering algorithms for categorical matrix- object data is relatively rare, and there are still many issues to be settled. In this paper, we propose a new matrix-object data fuzzy k-modes (MD fuzzy k-modes) algorithm that uses the fuzzy k-modes clustering process to cluster categorical matrix-object data. In the proposed algorithm, we introduce the fuzzy factor β with the concept of fuzzy set. The dissimilarity measure between two categorical matrix-objects is redefined, and the heuristic updating algorithm of the cluster centers is provided. Finally, the effectiveness of the MD fuzzy k-modes algorithm is verified on the five real-world data sets, and the relationship between fuzzy factor β and membership w is analyzed. Therefore, in the era of big data, clustering multiple records by using the MD fuzzy k-modes algorithm can make it easier to find customers’ spending habits and preferences, so as to make more targeted recommendation.

Key words matrix-object data; MD fuzzy k-modes algorithm; dissimilarity measure; cluster centers; clustering

(lisy75@sxu.edu.cn)

DOI:10.7544/issn1000-1239.2019.20180737

收稿日期：2018-11-01；修回日期：2019-04-09

基金项目：国家自然科学基金项目(61573229)；山西省基础研究计划项目(201701D121004)；山西省回国留学人员科研资助项目(2017-020)；山西省高等学校教学改革创新项目(J2017002)

This work was supported by the National Natural Science Foundation of China (61573229), the Shanxi Provincial Basic Research Foundation of China (201701D121004), the Shanxi Scholarship Council of China (2017-020), and the Shanxi Provincial Teaching Reform and Innovation Program in Higher Education (J2017002).

中图法分类号 TP391

Li Shunyong, born in 1975. PhD, associate professor and master supervisor. His main research interest is statistical machine learning.

Zhang Miaomiao, born in 1993. Master candidate. Her main research interest is statistical machine learning.

Cao Fuyuan, born in 1974. Professor and PhD supervisor. Member of CCF. His main research interests include data mining and machine learning.