«上一篇 下一篇»
  山东大学学报(工学版)  2016, Vol. 46 Issue (2): 29-34  DOI: 10.6040/j.issn.1672-3961.0.2015.101
0

引用本文 

江峰, 杜军威, 刘国柱, 眭跃飞. 基于加权的K-modes聚类初始中心选择算法[J]. 山东大学学报(工学版), 2016, 46(2): 29-34. DOI: 10.6040/j.issn.1672-3961.0.2015.101.
JIANG Feng, DU Junwei, LIU Guozhu, SUI Yuefei. A weight-based initial centers selection algorithm for K-modes clustering[J]. Journal of Shandong University(Engineering Science), 2016, 46(2): 29-34. DOI: 10.6040/j.issn.1672-3961.0.2015.101.

基金项目

国家自然科学基金资助项目(60802042, 61273180);山东省自然科学基金资助项目(ZR2011FQ005);山东省高等学校科技计划资助项目(J11LG05)

作者简介

江峰(1978— ),男,江西彭泽人,副教授, 博士,主要研究方向为数据挖掘,粗糙集.E-mail: jiangkong@163.net

通讯作者

文章历史

收稿日期:2015-04-15
网络出版日期:2015-12-18 15:11:04
基于加权的K-modes聚类初始中心选择算法
江峰1, 杜军威1, 刘国柱1, 眭跃飞2    
1. 青岛科技大学信息科学与技术学院, 山东 青岛 266061;
2. 中国科学院计算技术研究所, 北京 100190
摘要: 针对现有的K-modes聚类初始化方法没有考虑不同的属性具有不同的重要性这一问题,提出一种基于加权密度与加权重叠距离的初始中心选择算法Ini-Weight。Ini-Weight算法通过计算每个对象的密度以及对象之间的距离来选择初始中心。在计算对象的密度以及对象的距离时,Ini-Weight算法根据每个属性的重要性为不同的属性赋予不同的权值。最后,在UCI数据集上将Ini-Weight与现有的方法进行了比较,结果表明,Ini-Weight算法可以有效地区分不同的属性,而且提高了初始中心选择的准确性。
关键词: K-modes聚类    粗糙集    加权平均密度    加权重叠距离    初始中心    
A weight-based initial centers selection algorithm for K-modes clustering
JIANG Feng1, DU Junwei1, LIU Guozhu1, SUI Yuefei2    
1. College of Information Science & Technology, Qingdao University of Science and Technology, Qingdao 266061, Shandong, China;
2. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
Abstract: The current initialization methods for K-modes clustering do not consider the case in which various attributes have different significances. To solve this problem, a weighted density and weighted overlap distance-based initial center selection algorithm (called Ini-Weight) was proposed. In algorithm Ini-Weight, initial centers were selected by calculating the density of each object and the distance between any two objects. In Ini-Weight, when calculating the density of each object and the distance between any two objects, different weights were assigned to different attributes according to the significance of each attribute. Finally, Ini-Weight was compared with the current methods on UCI data sets. The results showed that Ini-Weight algorithm could effectively distinguish different attributes and improve the accuracy for selecting initial centers.
Key words: K-modes clustering    rough sets    weighted average density    weighted overlap distance    initial centers    
0 引言

聚类是数据挖掘的一个重要研究方向[1, 2, 3]。传统的基于划分的聚类(如K-means)算法只能处理数值型数据 [4, 5]。为了处理分类型数据,HUANGZX 提出了K-modes算法[6],并采用简单重叠距离来度量对象的不相似性。近年来,K-modes聚类的初始中心选择(即初始化)问题引起了广泛关注[7, 8, 9, 10]。目前,针对K-means的初始化已经提出了很多方法[11, 12, 13, 14],然而这些方法不能直接应用于K-modes聚类。HUANG Z X提出了两种K-modes聚类初始中心选择方法[6],其中第一种方法选择最开始的K个对象作为初始中心;第二种方法则通过计算所有类别相对于所有属性的频率,并且均等地分配最频繁的类别到K个初始中心。这两种方法都存在一些问题,例如,前者只有在K个初始中心恰好来自K个不同的簇时才有效,而后者并没有给出一个统一的标准来选择初始中心。WU S等提出了一种基于密度的初始中心选择方法[7]。为了降低计算开销,该方法首先随机选择一个子样本集,然后在子样本集上选择初始中心。然而,随机选择子样本集将导致结果的随机性和不可重复性。CAO F Y等提出一种基于密度和距离的初始中心选择方法[8]。另外,BAI L等提出了一种初始化方法,能够同时确定簇的个数并选择初始中心[9]

为了解决现有方法的问题,提出一种基于加权重叠距离与加权平均密度的初始中心选择算法Ini-Weight。该算法分为3个部分:(1) 计算属性的权值,并根据权值来计算每个对象的加权平均密度,然后选择密度最大的对象作为第1个中心c1;(2) 计算每个候选对象xc1的加权重叠距离,并选择密度与距离乘积最大的候选对象作为第2个中心;(3) 生成剩余的初始中心。假设当前选中的中心为c1,…,cq,对任意候选对象x,分别计算xc1,…,cq的加权重叠距离,将这些距离与x的密度相乘,并从这些乘积中选择最小值作为x成为初始中心的可能性。最后,选择可能性最大的候选对象作为新的中心。Ini-Weight采用加权重叠距离来代替传统的简单重叠距离,充分考虑到属性间的差异性,因而更符合客观实际。另外,在计算对象的平均密度时,也考虑到属性的差异性,即引入了加权平均密度的概念。Ini-Weight利用信息熵来计算每个属性的重要性[15],并根据重要性来为每个属性赋予一个权值。越重要的属性权值越大,相应地,它在计算对象的距离以及密度时所发挥的作用就越大。为了验证Ini-Weight的性能,采用多个UCI数据集来开展试验。结果表明,与现有的初始中心选择方法相比,采用Ini-Weight来为K-modes聚类进行初始化可以获得更好的聚类结果。

1 基本概念

定义 1  信息表是一个四元组IS=(U,A,V,f),其中[15]:

(1) U是一个非空有限的对象集;

(2) A是一个非空有限的属性集;

(3) V是所有属性论域的并,即 V=$\underset{a\in A}{\mathop{\cup }}\,$Va,其中Va 为属性a的值域;

(4)f: U×AV是一个信息函数,使得对任意aA以及xU,f(x,a)∈Va

定义 2 (不可区分关系)  给定信息表IS=(U,A,V,f),对任意B$ \subseteq $A,定义由B所决定的一个不可区分关系IND(B)为:IND(B)={(x,y)∈U×U: ∀a∈B (f (x,a)=f (y,a))}。

对任意 x,yU,如果(x,y)∈IND(B),则称xy关于B是不可区分的。IND(B)是U上的一个等价关系,将U划分成多个等价类,所有等价类的集合就构成U的一个划分,记为U/IND(B)。对任意x∈U,令[x]B={y∈U | (x,y)∈IND(B)}表示U/IND(B)中包含x的等价类[15]

近年来,信息熵被广泛应用于粗糙集[16],并出现了很多新的信息熵模型[17, 18, 19, 20, 21]。例如,JIANG F等定义了相对决策熵模型,并提出一种基于相对决策熵的特征选择方法[20]。下面,将采用DÜNTSCH I和GEDIGA G提出的信息熵模型来计算属性重要性[17]

定义 3  给定信息表IS=(U,A,V,f),对任意B$ \subseteq $A,令U/IND(B)={B1,…,Bp}表示不可区分关系IND(B)对U的划分,IND(B)的信息熵[17]

$E\left( B \right)=-\sum\limits_{i=1}^{p}{\frac{\left| {{B}_{i}} \right|}{\left| U \right|}}{{\log }_{2}}\frac{\left| {{B}_{i}} \right|}{\left| U \right|},$
其中,|Bi|/|U| 表示任意对象xU在等价类Bi中出现的概率,1≤ip

定义 4  给定信息表IS=(U,A,V,f),对任意aA,属性a在IS中的重要性

$Sig\left( a \right)=\frac{E\left( A \right)-E\left( A-\left\{ a \right\} \right)}{E\left( A \right)},$
其中,对任意B$ \subseteq $A,E(B)表示IND(B)的信息熵。

2 加权重叠距离与加权平均密度

现有的K-modes算法大多采用简单重叠距离来度量对象的不相似性[6]。简单重叠距离的定义简单而且直观,但它在实际应用中还存在一些问题[22]。例如,它假设所有属性在计算距离时发挥的作用是一样的。然而,在很多实际情况下,不同的属性对距离计算的影响很可能是不同的。因此,有必要为每个属性分配一个权值,并通过权值的大小来体现属性对于距离计算贡献的大小。接下来,在简单重叠距离的基础上,将提出一种加权重叠距离。

定义 5 (加权重叠距离)  给定信息表IS=(U,A,V,f),对任意x,yU,xy的加权重叠距离

wd(x,y)=$\sum\limits_{a\in A}^{{}}{{}}$weight(aδa(x,y),
其中,δa(x,y)表示xy在属性a上的简单重叠距离(即如果f (x,a)=f (y,a)则δa(x,y)=0,否则δa(x,y)=1),weight(a)表示a的权值,定义如下:
$weight\left( a \right)=\left\{ \begin{matrix} \frac{2}{3d},ifSig\left( a \right)=0; \\ 1+Sig\left( a \right),ifSig\left( a \right)>0, \\ \end{matrix} \right.$
其中d是一个给定的参数 23<d< 1。

对任意aA,weight(a)代表了a在信息表IS中的重要性,即a在计算加权重叠距离时所发挥的作用大小。weight(a)与Sig(a)成正比,即Sig(a)越大,则weight(a)也越大。定义5之所以不直接将Sig(a)作为a的权值,是因为可能A中有很多属性的重要性等于0。在计算加权重叠距离时,如果将这些属性的权值赋值为0,即完全忽略它们的作用是不合适的,因为有可能出现这样的情形,即A中大多数属性的重要性都等于0。因此,定义5 在计算加权重叠距离时,对于重要性为0的属性,统一赋予一个较小的权值(小于1),使得这些属性所发挥的作用较小,而对于重要性大于0的属性,则赋予一个较大的权值(大于1)。

CAO F Y等提出了平均密度的概念[8],并基于平均密度来选择初始中心。

定义 6 (平均密度)  给定信息表IS=(U,A,V,f),对任意xU,x的平均密度

$Dens\left( x \right)=\frac{\sum\limits_{a\in A}^{{}}{Den{{s}_{a}}\left( x \right)}}{\left| A \right|},$
其中,对任意aA,Densa(x)表示x在属性a上的密度,定义为

$Den{{s}_{a}}\left( x \right)=\frac{\left| \left\{ y\in U\left| f\left( x,a \right)=f\left( y,a \right) \right. \right\} \right|}{\left| U \right|}.$

与简单重叠距离的定义类似,定义6也没有考虑属性间的差异性,而是假设A中每个属性在计算Dens(x)时所发挥的作用是一样的。因此,有必要为每个属性分配一个权值,通过权值来体现出该属性对于Dens(x)的影响。接下来,在定义6的基础上,提出一种加权平均密度。

定义 7 (加权平均密度)  给定信息表IS=(U,A,V,f),对任意xU,x的加权平均密度

$WDens\left( x \right)=\frac{\sum\limits_{a\in A}^{{}}{weight\left( a \right)\times Den{{s}_{a}}\left( x \right)}}{\left| A \right|}.$
在定义7中,WDens(x)越大,则表明x周围的对象越多,因此x成为初始中心的可能性就越大。基于上述考虑,在选择初始中心时,将计算每个候选对象的加权平均密度,并尽量选择密度大的对象。除了考虑密度,还要考虑初始中心之间的距离,如果两个初始中心离得太近,则它们可能来自同一个簇[8]。因此,不仅要考虑对象的加权平均密度,而且还要考虑该对象与每个已有初始中心的加权重叠距离。下面,在计算候选对象x成为初始中心的可能性时,将综合考虑这两方面的因素。

定义 8  给定信息表IS=(U,A,V,f),令C={c1,c2,…,cq}表示当前已有的初始中心集合,对任意候选对象xU-C,x成为初始中心的可能性

Pos-Center(x)=$\underset{i=1}{\mathop{\min }}\,$(wd(x,ci)×WDens(x)),
其中:wd(x,ci)表示x与中心ci之间的加权重叠距离,1≤iq

在定义8中,如果C=Φ,则对任意xU,令Pos-Center(x)=WDens(x),即选择加权平均密度最大的对象作为第1个初始中心。

通过定义8可以看出,如果x的加权平均密度越大,则x成为初始中心的可能性就越大;另外,如果x与最近初始中心(指在C中距离x最近的那个元素)的距离越远,则x成为初始中心的可能性也越大。

3 初始中心选择算法Ini-Weight

输入: 信息表IS=(U,A,V,f),其中U={x1,…,xn},A={a1,…,am};预先给定的簇数K

输出: K个初始中心

初始化:C=Φ,其中C表示当前已经选中的初始中心集

(1) 采用计数排序的方法计算IND(A)对U的划分U/IND(A)[23];

(2) 计算IND(A)的信息熵E(A);

(3) 对任意aA,反复执行

(3.1) 采用计数排序的方法分别计算划分U/IND(A-{a})和U/IND({a});

(3.2) 计算IND(A-{a})的信息熵E(A-{a});

(3.3) 计算a的重要性Sig(a),并由此得到a的权值weight(a);

(3.4) 对任意xU,根据U/IND({a})来计算 |[x]{a|,并令Densa(x)=$\frac{\left| {{\left[ x \right]}_{\left\{ a \right\}}} \right|}{\left| U \right|}$

(4) 对任意xU,计算WDens(x);

(5) 从U中选择加权平均密度最大的对象y作为第1个初始中心,并令C=C ∪{y};

(6) 如果|C| < K,则转步骤(7),否则转步骤(10);

(7) 假设C={c1,c2,…,cq},对任意xU-C,反复执行:

(7.1) 计算xci的加权重叠距离wd(x,ci),其中ciC,1≤iq;

(7.2) 计算Pos-Center(x);

(8) 从U-C中选择成为初始中心可能性最大的对象y作为新的初始中心,并令C=C∪{y};

(9) 如果|C| < K,则转步骤(7),否则转步骤(10);

(10) 返回C中的K个初始中心。

通常,计算U/IND(A)的时间复杂度为O(|U|2)。Ini-Weight采用了一种基于计数排序的方法来计算U/IND(A),时间复杂度仅为O(|U|×|A|)[23]

在最坏的情况下,Ini-Weight中第(1)~(5)步的时间复杂度为O(|A|2×|U|),第(6)~(10)步的时间复杂度为O(K2×|A|×|U|),其中K为簇的个数。因此,在最坏的情况下,该算法的时间复杂度为O(K2×|A|×|U|+|A|2×|U|),空间复杂度为O(|A|×|U|)。

4 试验分析

为了评估Ini-Weight的性能,采用5个分类型UCI数据集进行试验: (1) Soybean;(2) Zoo; (3) Breast Cancer(简称Breast); (4) Mushroom; (5) Lung。这5个数据集的基本信息如表1所示。

表1 UCI数据集 Table 1 UCI data sets

Ini-Weight分别与4个现有的初始中心选择方法进行了比较:(1) 随机方法[6];(2) CAO F Y等的算法(简称CAO)[8];(3) WU S等的算法(简称WU)[7];(4) KHAN S S和AHMAD A的算法(简称KHAN)[10]。试验步骤如下:首先,使用不同的算法来选择初始中心;其次,基于上一步所选择的初始中心进行K-modes聚类(采用HUANG Z X提出的经典K-modes算法进行聚类[6]);最后,比较不同的初始化算法所对应的聚类结果。

Ini-Weight在计算属性的权值时,需要预先设置参数d的值,其中,23<d< 1。关于d的取值,需要在每个数据集上通过不断地尝试和试验才能最终确定。具体而言,对任意一个数据集,首先根据经验为参数d设置一个初始值,并验证初始值对应的聚类结果;其次,不断调整d的取值,并验证调整后的试验结果,直到得到一个满意的聚类结果。

为了评估聚类结果的好坏,采用三种聚类结果度量指标: Precision(PR)、 Recall(RE)和Accuracy(AC),具体定义如下[7]: 假设当前数据集有K个簇C1,…,CK,利用给定的算法进行聚类,令ai表示被正确分到簇Ci的对象数,令bi表示被错误分配到簇Ci的对象数,令ci表示本来应该分配到簇Ci,但被错误分配到其他簇的对象数,其中1≤iK。PR、RE和AC分别定义为

$\begin{align} & PR=\frac{\sum\limits_{i=1}^{K}{\frac{{{a}_{i}}}{{{a}_{i}}+{{b}_{i}}}}}{K}; \\ & RE=\frac{\sum\limits_{i=1}^{K}{\frac{{{a}_{i}}}{{{a}_{i}}+{{c}_{i}}}}}{K}; \\ & AC=\frac{\sum\limits_{i=1}^{K}{{{a}_{i}}}}{\left| U \right|}. \\ \end{align}$

表2~6分别给出了5个UCI数据集上不同算法所对应的K-modes聚类结果。

表2 Soybean上的试验结果 Table 2 Test results on Syobean
表3 Zoo上的试验结果 Table 3 Test results on Zoo
表4 Breast上的试验结果 Table 4 Test results on Breast
表5 Mushroom上的试验结果 Table 5 Test results on Mushroom
表6 Lung上的试验结果 Table 6 Test results on Lung

表2~6可以看出,Ini-Weight的性能要优于随机方法,这是因为在Soybean、Breast、Mushroom和Lung这4个数据集上,Ini-Weight的AC、PR和RE都要超过随机方法。在Zoo上,尽管Ini-Weight的PR比随机方法要略差,但它的AC和RE都明显优于随机方法。此外,随机方法每次得到的聚类结果都是不一样的,而Ini-Weight能够得到稳定的聚类结果。

虽然CAO、WU这2种方法也都优于随机方法,但Ini-Weight却要优于它们。在Soybean、Breast、Mushroom和Lung上,Ini-Weight的AC、PR和RE都要高于或等于这2种方法。在Zoo上,尽管Ini-Weight的PR比CAO、WU这2种方法要低,但它的AC和RE都要高于它们。另外,Ini-Weight的性能也优于KHAN的方法。

表2~6还可以看出,Ini-Weight的RE始终高于其他方法。这表明,Ini-Weight可以严格控制一个簇中的对象不被错分到其他簇。另外,Ini-Weight在Zoo上的PR比Cao、Wu这2种方法以及随机方法要差,但AC却比它们要好。这是因为PR和AC是两个不同的性能度量标准。在Ini-Weight所得到的聚类结果中,有一个簇的正确率为零(即没有对象被正确分配到这个簇中),从而使得Ini-Weight的PR比较低。然而,尽管该簇的正确率为零,Zoo中属于这个簇的对象数很少,因此Ini-Weight的AC仍然要高于其他方法。

5 结论

提出了一种新的K-modes聚类初始中心选择算法Ini-Weight。该算法充分考虑到不同属性在计算对象密度以及对象距离时重要性是不同的这一客观事实,通过为每个属性赋予一个权值来区分不同的属性,从而提高了初始中心选择的准确性。试验表明,相对于现有方法,Ini-Weight能够获得更好的聚类结果。

Ini-Weight主要针对类别型数据,然而现实生活中存在大量的混合型数据[1],因此,下一步工作计划对Ini-Weight进行扩展,使得其可以处理混合型数据,从而可以为K-prototype算法选择初始中心[6]。另外,还可以利用Ini-Weight来为fuzzy K-modes算法选择初始中心[24]

参考文献
[1] HAN J W, KAMBER M. Data mining: concepts and techniques[M]. 2nd edition. Burlington, USA: Morgan Kaufmann Publishers, 2006.(2)
[2] JAIN A K, MURTY M N, FLYNN P J. Data clustering: a review[J]. ACM Computing Surveys, 1999, 31(3):264-323.(1)
[3] 陈文强, 林琛, 陈珂,等. 基于GraphLab的分布式近邻传播聚类算法[J]. 山东大学学报(工学版), 2013, 43(5):13-18.
CHEN Wenqiang, LIN Chen, CHEN Ke, et al. Distributed affinity propagation clustering algorithm based on GraphLab[J]. Journal of Shandong University(Engineering Science), 2013, 43(5):13-18.(1)
[4] ANDERBERG M R. Cluster analysis for applications[M]. New York: Academic Press, 1973.(1)
[5] BAI L, LIANG J Y, SUI C, et al. Fast global K-means clustering based on local geometrical information[J]. Information Sciences, 2013, 245:168-180.(1)
[6] HUANG Z X. 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.(6)
[7] WU S, JIANG Q S, HUANG Z X. A new initialization method for clustering categorical data[C]//Proceedings of the 11th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Nanjing, China: Springer, 2007:972-980.(4)
[8] CAO F Y, LIANG J Y, BAI L. A new initialization method for categorical data clustering[J]. Expert Systems with Application, 2009, 36(7):10223-10228.(5)
[9] BAI L, LIANG J Y, DANG C Y. An initialization method to simultaneously find initial cluster centers and the number of clusters for clustering categorical data[J]. Knowledge-Based Systems, 2011, 24(6):785-795.(2)
[10] KHAN S S, AHMAD A. Cluster center initialization algorithm for K-modes clustering[J]. Expert Systems with Applications, 2013, 40(18):7444-7456.(2)
[11] BRADLEY P S, FAYYAD U M. Refining initial points for K-means clustering[C]//Proceedings of the 15th International Conference on Machine Learning. San Francisco, USA: Morgan Kaufmann, 1998:91-99.(1)
[12] CAO F Y, LIANG J Y, JIANG G. An initialization method for the K-means algorithm using neighborhood model[J]. Computers and Mathematics with Applications, 2009, 58(3):474-483.(1)
[13] 王守强, 朱大铭, 史士英. K-means聚类问题的改进近似算法[J]. 山东大学学报(工学版), 2011, 41(4):125-132.
WANG Shouqiang, ZHU D M, SHI Shiying. Improved approximation algorithm for the K-means clustering problem[J]. Journal of Shandong University(Engineering Science), 2011, 41(4):125-132.(1)
[14] 夏战国, 万玲, 蔡世玉,等. 一种面向入侵检测的半监督聚类算法[J]. 山东大学学报(工学版), 2012, 42(6):1-7.
XIA Zhanguo, WAN Ling, CAI Shiyu, et al. A semi-supervised clustering algorithm oriented to intrusion detection[J]. Journal of Shandong University(Engineering Science), 2012, 42(6):1-7.(1)
[15] PAWLAK Z. Rough sets: theoretical aspects of reasoning about data[M]. Dordrecht, Netherlands: Kluwer Academic Publishers, 1991.(3)
[16] SHANNON C E. The mathematical theory of communication[J]. Bell System Technical Journal, 1948, 27(3-4):373-423.(1)
[17] DNTSCH I, GEDIGA G. Uncertainty measures of rough set prediction[J]. Artificial Intelligence, 1998, 106(1):109-137.(3)
[18] 苗夺谦, 胡桂荣. 知识约简的一种启发式算法[J]. 计算机研究与发展, 1999, 36(6):681-684.
MIAO Duoqian, HU Guirong. A heuristic algorithm for reduction of knowledge[J]. Computer Research and Development, 1999, 36(6):681-684.(1)
[19] LIANG J Y, SHI Z Z. The information entropy, rough entropy and knowledge granulation in rough set theory[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2004, 12(1):37-46.(1)
[20] JIANG F, SUI Y F, ZHOU L. A relative decision entropy-based feature selection approach[J]. Pattern Recognition, 2015, 48(7):2151-2163.(1)
[21] 江峰, 王莎莎, 杜军威,等. 基于近似决策熵的属性约简[J]. 控制与决策, 2015, 30(1):65-70.
JIANG Feng, WANG Shasha, DU Junwei, et al. Attribute reduction based on approximation decision entropy[J]. Control and Decision, 2015, 30(1):65-70.(1)
[22] 梁吉业, 白亮, 曹付元. 基于新的距离度量的K-modes聚类算法[J]. 计算机研究与发展, 2010, 47(10):1749-1755.
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.(1)
[23] 徐章艳, 刘作鹏, 杨炳儒,等. 一个复杂度为max(O(|C||U|), O(|C|2|U/C|)) 的快速属性约简算法[J]. 计算机学报, 2006, 29(3):391-399.
XU Zhangyan, LIU Zuopeng, YANG Bingru, et al. A quick attribute reduction algorithm with complexity of max(O(|C||U|), O(|C|2|U/C|))[J]. Chinese Journal of Computers, 2006, 29(3):391-399.(2)
[24] HUANG Z X, NG M K. A fuzzy K-modes algorithm for clustering categorical data[J]. IEEE Transactions on Fuzzy Systems, 1999, 7(4):446-452.(1)