D0L:10.13374.issn1001-053x.2013.08.016 第35卷第8期 北京科技大学学报 Vol.35 No.8 2013年8月 Journal of University of Science and Technology Beijing Aug.2013 考虑加权排序的分类数据聚类算法 武森凶，王蔷，姜敏，魏青 北京科技大学东凌经济管理学院，北京100083 ☒通信作者，E-mail:wusen@manage.ustb.cdu.cn 摘要针对部分聚类算法对数据输入顺序敏感的问题，定义了不干涉序列指数，提出了应用不干涉序列指数对分类 数据进行加权排序的方法，并基于该方法对受数据输入顺序影响的CABOSFV.C分类数据高效聚类算法进行改进，提 出了考虑加权排序的聚类算法(CABOSFV_CSW),消除了算法对数据输入顺序的敏感性.采用UCI基准数据集进行实 验，发现应用加权升序排序的CABOSFV_CSW算法在处理分类数据时，聚类质量较原始CABOSFV_C算法和其他受 数据输入顺序影响的算法在准确性上有改善，在稳定性上有显著提高. 关键词数据挖掘：聚类算法：排序：分类数据 分类号TP311 Clustering algorithm of categorical data in consideration of sorting by weight WU Sen✉，WANG Qiang,JIANG Min,WEI Qing DonglingSchool of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:wusen@manage.ustb.edu.cn ABSTRACT Aimed at solving the problem that part of clustering algorithms are sensitive to the data input order, a non-interference sequence index was defined,and an approach applying the non-interference sequence was proposed to sort categorical data by weight.Based on this approach,a new clustering algorithm considering sorting by weight (CABOSFV_CSW)was presented to improve CABOSFV_C,which is an efficient clustering algorithm for categorical data but sensitive to the data input order.This approach eliminates sensitivity to the data input order.UCI benchmark data sets were used to compare the proposed CABOSFV_CSW algorithm with traditional CABOSFV_C algorithm and other algorithms sensitive to the data input order.Empirical tests show that the new CABOSFV_CSW clustering algorithm for categorical data improves the accuracy and increases the stability effectively. KEY WORDS data mining:clustering algorithm;sorting:categorical data 聚类是数据挖掘领域中常用的方法之一，被广其稳定性却不高.主要原因在于：有些算法受初始 泛应用于众多领域.针对数值型数据的聚类分析点随机性影响，使得聚类结果不唯一，如k-modes 研究已取得许多成果，如经典k-means、.QIDBSCAN和k-means算法；有些算法则是受数据输入顺序影 和PAM算法及改进与发展2-4.除数值型数据响，不同的数据输入顺序会得到不同的聚类结果， 外，现实世界中还存在大量分类属性的数据，针 如CABOSFV_C、COBWEB和BIRCHIO算法，其 对解决分类数据聚类问题的算法包括k-mods算 中CABOSEV C和COBWEB算法主要适用于分类 法-61、CABOSFV.C算法可、COBWEB算法8等. 属性数据，BIRCH算法大多适用于数值型数据. 然而，不论是针对数值型数据还是面向分类型数据， 目前，大部分解决聚类算法稳定性问题的研究 部分算法的聚类结果虽在准确性上有较好表现，但 都集中在受初始点随机性影响的算法上0-1山，而 收稿日期：2012-09-03 基金项目：国家自然科学基金资助项目(71271027)：中央高校基本科研业务费专项(FRF-TP-10-006B)
第 35 卷 第 8 期 北 京 科 技 大 学 学 报 Vol. 35 No. 8 2013 年 8 月 Journal of University of Science and Technology Beijing Aug. 2013 考虑加权排序的分类数据聚类算法 武 森 ，王 蔷，姜 敏，魏 青 北京科技大学东凌经济管理学院，北京 100083 通信作者，E-mail: wusen@manage.ustb.edu.cn 摘 要 针对部分聚类算法对数据输入顺序敏感的问题，定义了不干涉序列指数，提出了应用不干涉序列指数对分类 数据进行加权排序的方法，并基于该方法对受数据输入顺序影响的 CABOSFV C 分类数据高效聚类算法进行改进，提 出了考虑加权排序的聚类算法 (CABOSFV CSW)，消除了算法对数据输入顺序的敏感性. 采用 UCI 基准数据集进行实 验，发现应用加权升序排序的 CABOSFV CSW 算法在处理分类数据时，聚类质量较原始 CABOSFV C 算法和其他受 数据输入顺序影响的算法在准确性上有改善，在稳定性上有显著提高. 关键词 数据挖掘；聚类算法；排序；分类数据 分类号 TP311 Clustering algorithm of categorical data in consideration of sorting by weight WU Sen , WANG Qiang, JIANG Min, WEI Qing DonglingSchool of Economics and Management, University of Science and Technology Beijing, Beijing 100083, China Corresponding author, E-mail: wusen@manage.ustb.edu.cn ABSTRACT Aimed at solving the problem that part of clustering algorithms are sensitive to the data input order, a non-interference sequence index was defined, and an approach applying the non-interference sequence was proposed to sort categorical data by weight. Based on this approach, a new clustering algorithm considering sorting by weight (CABOSFV CSW) was presented to improve CABOSFV C, which is an efficient clustering algorithm for categorical data but sensitive to the data input order. This approach eliminates sensitivity to the data input order. UCI benchmark data sets were used to compare the proposed CABOSFV CSW algorithm with traditional CABOSFV C algorithm and other algorithms sensitive to the data input order. Empirical tests show that the new CABOSFV CSW clustering algorithm for categorical data improves the accuracy and increases the stability effectively. KEY WORDS data mining; clustering algorithm; sorting; categorical data 聚类是数据挖掘领域中常用的方法之一，被广 泛应用于众多领域[1] . 针对数值型数据的聚类分析 研究已取得许多成果，如经典 k-means、QIDBSCAN 和 PAM 算法及改进与发展 [2−4] . 除数值型数据 外，现实世界中还存在大量分类属性的数据，针 对解决分类数据聚类问题的算法包括 k-modes 算 法[5−6]、CABOSFV C 算法[7]、COBWEB 算法[8] 等. 然而，不论是针对数值型数据还是面向分类型数据， 部分算法的聚类结果虽在准确性上有较好表现，但 其稳定性却不高. 主要原因在于：有些算法受初始 点随机性影响，使得聚类结果不唯一，如 k-modes 和 k-means 算法；有些算法则是受数据输入顺序影 响，不同的数据输入顺序会得到不同的聚类结果， 如 CABOSFV C、COBWEB 和 BIRCH[9] 算法，其 中 CABOSFV C 和 COBWEB 算法主要适用于分类 属性数据，BIRCH 算法大多适用于数值型数据. 目前，大部分解决聚类算法稳定性问题的研究 都集中在受初始点随机性影响的算法上[10−11]，而 收稿日期：2012–09–03 基金项目：国家自然科学基金资助项目 (71271027)；中央高校基本科研业务费专项 (FRF-TP-10-006B) DOI:10.13374/j.issn1001-053x.2013.08.016
·1094 北京科技大学学报 第35卷 针对受数据输入顺序影响的聚类算法稳定性问题的 属性值k时，C=1,而C=0(s=1,2,,t 研究较少.文献[12提出了一种根据对象稀疏性指 且s≠k.设X'为数据集X中分类属性全部映 数对数据进行排序的方法(CABOSFV_CS),其中对 射到二值属性后的数据集，新属性分别为D1,D2 象稀疏性指数是二值属性和分类属性转化为二值属 ,D,p=m1+空，对象工的属性值分别为 t=1 性中取值为1的属性个数.该方法在一定程度上提 d1(x),d2(x),…,dp(x)(dr(x)=0或1，f=1,2,…,p), 高了聚类结果的准确率，然而对象稀疏性指数相同 则对象x的不干涉序列指数定义为 但属性值1的位置不同的非同类对象很可能被纳入 同一类，从而影响聚类结果的准确性.此外，该方 q(,M)=di()M1+d2()M2 +...+dp()Mp. 法虽在很大程度上提升了聚类结果的稳定性，但并 没有完全消除 其中(M1,M2,·,M)为某选定的不干涉序列 M=(M1,M2,·,M,…)的前p项 本文从数据排序的角度出发，提出考虑加权 由定义2可知，不干涉序列指数适用于二值数 排序的分类数据聚类算法(CABOSFV considering 据，也适用于分类数据 sorting by weight,CABOSFV.CSW),借鉴不干涉 系数数列的思想定义不干涉序列指数，应用不 2加权排序 干涉序列指数实现对分类数据的加权排序，并用该 2.1加权排序概念 加权排序方法对CABOSFVC算法进行改进.实 定义3（基于不干涉序列指数的加权排序）将 验表明，考虑加权排序的分类数据聚类算法CA- 二值或分类属性数据集X中的数据按照不干涉序 BOSFV_CSW可以消除算法对数据输入顺序的敏感 列指数升序或降序进行排列，分别称为基于不干涉 性，并且改善了聚类结果的准确性 序列指数的加权升序排序和加权降序排序 1不干涉序列指数 引理1对于二值或分类属性数据集X中任 意两个对象x和，分类属性全部映射到二值属性 1.1不干涉序列 后的属性值分别为d1(r),d2(z),·,dp(x)和d1(), 定义1（不干涉序列）当一个正整数数列M= d2(),…,dn()(dr(x)=0或1，dr(y)=0或1，f=1, (M,M2,…,M,…)的第n项大于前n-1项的 和时，即山n>分山，n≥2，将这个数列称为不 2,…,p),记 i=1 干涉序列. x=(d1(x),d2(x),…,dp(x) 不干涉序列M=(M1,M2,…,M,…)可以通 y=(d(),d2(y),…,dn(y) 过下述方式来构造： M1=任意正整数： 应用任意不干涉序列M=(M1,M2,M3,··, M2=任意正整数且大于M1: M,…)得到不干涉序列指数分别为 M3=M1+M2+1: q(,M)=di()M1+d2()M2 +...+dp()Mp, M=2M-1(i>3) 例如： g(y,M)di(y)Mi+d2(y)M2+...+dp(y)Mp. 1,2,4,8,16.32,64,: 则有： 1,3,5,10,20,40,80,: (1)若q(x,M)=q(y,M),则x= 1,4.6,12,24.48,96.·. (2)若q(z,M>q(y,M)或q(x,M)<q(y,M), 1.2不干涉序列指数 则x卡 定义2（不干涉序列指数）设一个数据集X 证明： 有n个对象，每个对象共有m个属性，其中包含 (1)采用归纳法 m1个二值属性，m2个分类属性，分别记为B1,B2, ①首先证明若q(z,M=q(y,M),即 ·,Bm1,C,C2,…,Cm2,m1+m2=m.设分 d1(x)M1+d2(x)M2+…+d,(x)Mp=d山1(g)M+ 类属性Ct(t=1,2,·,m2)共有t个属性值，分 d2(y)M2+…+dn(y)Mp,则dn(x)=dn(y). 别为{1,2，…，h:},则该分类属性C:映射到 用反证法： 二值属性后的属性为C1,C2:·,Ch,当对象 假设dp(x)≠dp(y),则dp(a)=0且dp()=1, x在属性C:上取第k(k∈{1,2，…，ht})个分类 或dp(x)=1且dn(g)=0
· 1094 · 北 京 科 技 大 学 学 报 第 35 卷 针对受数据输入顺序影响的聚类算法稳定性问题的 研究较少. 文献 [12] 提出了一种根据对象稀疏性指 数对数据进行排序的方法 (CABOSFV CS)，其中对 象稀疏性指数是二值属性和分类属性转化为二值属 性中取值为 1 的属性个数. 该方法在一定程度上提 高了聚类结果的准确率，然而对象稀疏性指数相同 但属性值 1 的位置不同的非同类对象很可能被纳入 同一类，从而影响聚类结果的准确性. 此外，该方 法虽在很大程度上提升了聚类结果的稳定性，但并 没有完全消除. 本文从数据排序的角度出发，提出考虑加权 排序的分类数据聚类算法 (CABOSFV considering sorting by weight, CABOSFV CSW)，借鉴不干涉 系数数列的思想[13] 定义不干涉序列指数，应用不 干涉序列指数实现对分类数据的加权排序，并用该 加权排序方法对 CABOSFV C 算法进行改进. 实 验表明，考虑加权排序的分类数据聚类算法 CABOSFV CSW 可以消除算法对数据输入顺序的敏感 性，并且改善了聚类结果的准确性. 1 不干涉序列指数 1.1 不干涉序列 定义 1(不干涉序列) 当一个正整数数列 M= (M1, M2, · · · , Mi , · · ·) 的第 n 项大于前 n−1 项的 和时，即 Mn > nP−1 i=1 Mi , n > 2，将这个数列称为不 干涉序列. 不干涉序列 M=(M1, M2, · · · , Mi , · · ·) 可以通 过下述方式来构造： M1= 任意正整数； M2= 任意正整数且大于 M1； M3 = M1 + M2+ 1； Mi=2Mi−1 (i >3). 例如： 1, 2, 4, 8, 16, 32, 64, · · ·； 1, 3, 5, 10, 20, 40, 80, · · ·； 1, 4, 6, 12, 24, 48, 96, · · · . 1.2 不干涉序列指数 定义 2 (不干涉序列指数) 设一个数据集 X 有 n 个对象，每个对象共有 m 个属性，其中包含 m1 个二值属性，m2 个分类属性，分别记为 B1, B2, · · · , Bm1 , C1, C2, · · · , Cm2 , m1 + m2 = m. 设分 类属性 Ct (t=1, 2, · · · , m2) 共有 ht 个属性值，分 别为{vt1, vt2, · · · , vtht }，则该分类属性 Ct 映射到 二值属性后的属性为 C 0 t1 , C 0 t2 , · · · , C 0 tht，当对象 x 在属性 Ct 上取第 k (k ∈ {1, 2, · · · , ht}) 个分类 属性值 vtk 时，C 0 tk=1，而 C 0 ts=0 (s=1, 2, · · · , ht, 且 s 6= k. 设 X0 为数据集 X 中分类属性全部映 射到二值属性后的数据集，新属性分别为 D1, D2, · · · , Dp (p = m1 + mP2 t=1 ht)，对象 x 的属性值分别为 d1(x),d2(x), · · · , dp(x) (df (x)=0 或 1, f=1, 2, · · · , p)， 则对象 x 的不干涉序列指数定义为 q(x, M) = d1(x)M1 + d2(x)M2 + · · · + dp(x)Mp. 其中 (M1, M2, · · · , Mp) 为某选定的不干涉序列 M=(M1, M2, · · · , Mi , · · ·) 的前 p 项. 由定义 2 可知，不干涉序列指数适用于二值数 据，也适用于分类数据. 2 加权排序 2.1 加权排序概念 定义 3(基于不干涉序列指数的加权排序) 将 二值或分类属性数据集 X 中的数据按照不干涉序 列指数升序或降序进行排列，分别称为基于不干涉 序列指数的加权升序排序和加权降序排序. 引理 1 对于二值或分类属性数据集 X 中任 意两个对象 x 和 y，分类属性全部映射到二值属性 后的属性值分别为 d1(x), d2(x), · · · , dp(x) 和 d1(y), d2(y), · · · , dp(y) (df (x)=0 或 1, df (y)=0 或 1, f=1, 2, · · · , p)，记 x = (d1(x), d2(x), · · · , dp(x)), y = (d1(y), d2(y), · · · , dp(y)). 应用任意不干涉序列 M=(M1, M2, M3, · · · , Mi , · · ·) 得到不干涉序列指数分别为 q(x, M) = d1(x)M1 + d2(x)M2 + · · · + dp(x)Mp, q(y, M) = d1(y)M1 + d2(y)M2 + · · · + dp(y)Mp. 则有: (1) 若 q(x,M) = q(y,M)，则 x = y; (2) 若 q(x,M) > q(y,M) 或 q(x,M) < q(y,M)， 则 x 6= y. 证明： (1) 采用归纳法. ① 首先证明若 q(x,M) = q(y,M)， 即 d1(x)M1 + d2(x)M2+· · · +dp(x)Mp = d1(y)M1 + d2(y)M2+· · · +dp(y)Mp，则 dp(x) = dp(y). 用反证法： 假设 dp(x) 6= dp(y)，则 dp(x)= 0 且 dp(y)= 1， 或 dp(x)= 1 且 dp(y) = 0
第8期 武森等：考虑加权排序的分类数据聚类算法 .1095· 当dp(c)=0且d2(y)=1时，有 干涉序列进行加权升序排序后数据排序结果保持不 变：使用不同的不干涉序列进行加权降序排序后数 d1()M1+d2(x)M2+…+dp-1(z)Mp-1= 据排序结果保持不变. d1(y)M1+d2(g)M2+…+dp-1(y)Mp-1+Mp- 该定理表明，对于二值或分类属性数据集X 中任意两个对象x和，及任意两个不干涉序列 根据已知条件dr(z)和df(g)(f=1,2,…,p)只 能取值为0或1，并且根据不干涉序列的定义，山1， M=(M,M2,…,M,…)和N=(Ni,N2,N3,…, N,…),有： M2,·,M2皆为正整数，Mp大于前p-1项的和， 则有 (1)若q(x,M)=q(,M,则q(x,N)=q(y, N): d1(y)M1+d2(y)M2+…+dp-1(y)Mp-1≥0. (2)若q(x,M)>q(y,M),则q(z,N)>q(y,N): (3)若q(x,M) 证明： d1(x)M1+d2(z)M+…+dp-1(a)Mp-1= (1)若q(x,M)=q(y,M),根据引理1有x=y, di(x)Mi d2(x)M2 +...+dp(x)Mp 则q(x,N)=q(,N) (2)若q(z,M)>q(y,M),根据引理1有x≠y, 那么不等式左右两边相加，则 设k为使d(e)≠dr(g)(f∈{1,2，…，p)的最大 di(y)Mi d2(y)M2+...+dp(y)Mp 足标. ①对于k=1,则 d1(x)M1+d2(x)M2+…+d2(x)Mp 与已知q(z,M)=q(y,M)矛盾，所以d2(x)=d2(y) q(,M)-q(y,M)=di(x)Mi -di(y)Mi= 类似可以证明当d2(x)=1且dp(g)=0时， dn(x)=dp()也成立. Mi(di(x)-di(y)). ②再证明若d(x)=d(),i=k+1,k+2,…,p, 因为M为正整数，且q(红，M)>q(g,M),所以 k≥1，则d(z)=d(). d1(x)-d1(y)>0,则d山1(x)=1且d1(y)=0,则 若d(x)=d(y),i=k+1,k+2,…,p,k≥1， 则 q(,N)-q(y,N)=di(z)N1-di(y)N1=N1 >0. di()M1 +d2()M2 +...+dk()Mk q(x,N)>q(y,N)得证. d1(y)M1+d2()M2+·+d(g)Mk. @对于2>k≥p,若q(x,M)>q(g,M), 则d(x)=1且dk(y)=0.否则，如果d(x)=0且 采用①的方法同理可证dk(x)=d(). d()=1,则 综合①和@，若q(x,M)=q(g,M),则x= (2)采用反证法. q(,M)-q(y,M) d(c)M+d()M 已知q(x,M)>q(y,M)或q(z,Mq(y, 能取值为0或1，并且根据不干涉序列的定义，Mk M)或q(z,M)q(y,M)或q(x,M)<q(,M),则x≠. 定理1（基于不干涉序列指数的加权排序不变 定理)对于二值或分类属性数据集，使用不同的不 ∑d(回)-do)M≤∑M<M. =1
第 8 期 武 森等：考虑加权排序的分类数据聚类算法 1095 ·· 当 dp(x)= 0 且 dp(y)= 1 时，有 d1(x)M1 + d2(x)M2 + · · · + dp−1(x)Mp−1 = d1(y)M1 + d2(y)M2 + · · · + dp−1(y)Mp−1 + Mp. 根据已知条件 df (x) 和 df (y) (f=1, 2, · · · , p) 只 能取值为 0 或 1，并且根据不干涉序列的定义，M1, M2, · · · , Mp 皆为正整数，Mp 大于前 p–1 项的和， 则有 d1(y)M1 + d2(y)M2 + · · · + dp−1(y)Mp−1 > 0. dp(y)Mp = Mp > M1 + M2 + . . . + Mp−1 > d1(x)M1 + d2(x)M2 + · · · + dp−1(x)Mp−1 = d1(x)M1 + d2(x)M2 + · · · + dp(x)Mp 那么不等式左右两边相加，则 d1(y)M1 + d2(y)M2 + · · · + dp(y)Mp > d1(x)M1 + d2(x)M2 + · · · + dp(x)Mp. 与已知 q(x,M) = q(y,M) 矛盾，所以 dp(x) = dp(y). 类似可以证明当 dp(x)=1 且 dp(y)=0 时， dp(x) = dp(y) 也成立. ②再证明若 di(x) = di(y), i = k+1, k+2, · · · , p, k > 1，则 dk(x) = dk(y). 若 di(x) = di(y), i = k+1, k+2, · · · , p, k > 1， 则 d1(x)M1 + d2(x)M2 + · · · + dk(x)Mk = d1(y)M1 + d2(y)M2 + · · · + dk(y)Mk. 采用①的方法同理可证 dk(x) = dk(y). 综合①和②，若 q(x,M) = q(y,M)，则 x = y. (2) 采用反证法. 已知 q(x,M) > q(y,M) 或 q(x,M) q(y, M) 或 q(x, M) q(y, M) 或 q(x, M) q(y, M)，则 q(x, N) > q(y,N)； (3) 若 q(x, M) q(y, M)，根据引理 1 有 x 6= y， 设 k 为使 df (x) 6= df (y)(f ∈{1, 2, · · · , p}) 的最大 足标. ① 对于 k=1，则 q(x, M) − q(y, M) = d1(x)M1 − d1(y)M1 = M1(d1(x) − d1(y)). 因为 M1 为正整数，且 q(x, M) > q(y,M)，所以 d1(x) − d1(y) >0，则 d1(x)=1 且 d1(y)=0，则 q(x, N) − q(y, N) = d1(x)N1 − d1(y)N1 = N1 > 0. q(x, N) > q(y, N) 得证. ②对于 2> k > p，若 q(x, M) > q(y,M)， 则 dk(x) =1 且 dk(y)=0. 否则，如果 dk(x) =0 且 dk(y)=1，则 q(x, M) − q(y, M) = ÃnX−1 i=1 di (x) Mi + dk (x) Mk ! − ÃnX−1 i=1 di (y) Mi + dk (y) Mk ! = ÃnX−1 i=1 (di (x) − di (y)) Mi ! − Mk < 0. 这是因为根据 di(x) 和 di(y)(i=1, 2, · · · , k) 只 能取值为 0 或 1，并且根据不干涉序列的定义，Mk 大于前 k−1 项的和，有 nX−1 i=1 (di (x) − di (y)) Mi 6 nX−1 i=1 Mi < Mk
.1096 北京科技大学学报 第35卷 q(z,M)-q(g,M)q(y 94=1×1+1×3+1×5+1×10+0×20+ M)矛盾，所以d,(x)=1且dk(y)=0成立 0×40=19: 1 q5=1×1+1×3+1×5+1×10+0×20+ q(z,N)-q(y,N)= ∑4回N:+dk(N- 1×40=59. 1 根据不干涉序列指数对原对象集合进行排序， d()+de ( 此处采用升序排序，结果如表2所示 表2加权排序后的对象集合 a-4） +Nk>0. Table 2 Objectset after being sorted by weight 对象 9 a1 a3 a4 as a6 这是因为根据d(x)和d(y)(i=1,2,…,)只 6 1 0 1 0 0 0 能取值为0或1，并且根据不干涉序列的定义，Nk 9 1 1 0 0 0 19 1 0 0 大于前k-1项的和，有 59 1 1 1 0 1 59 1 1 0 回-4≥->-M 5 1 由表2可以看出，经过加权升序排序后，对象 所以q(x,N)>q(y,N) 集合中相似的甚至相同的对象被排列在了一起.其 (3)采用(2)的方法同理可证：若q(x,M)<q(y, 中1和x5两个对象由于其在所有属性上的取值均 相同，因而不干涉序列指数相等.本文将这样多个 M),则q(x,N)<q(y,N) 2.2算例 在所有属性上的取值都完全相同的对象视为一个整 受数据输入顺序影响的算法，例如CA- 体.对整个对象集合而言，这个整体内部对象的顺 序可能不同，但所采用的任何顺序都是等价的.以 BOSFV_C算法、BIRCH算法和COBWEB算法， 其大多都是动态、增量式的聚类，因此容易将相临 表2为例，即认为x3,x2,x4,x1,x6与x3,2,x4, 近但不属于同一类的数据聚到相同类.本文提出应 5,c1是同一个排序结果.因此在升序或降序确定 用不干涉序列进行加权排序的方法可以将相似度高 的情况下，这种基于不干涉序列指数的加权排序只 有唯一结果，这就使得那些受数据输入顺序影响的 的对象排到一起且结果唯一，从而消除算法对数据 算法可以选择这种唯一的输入顺序 输入顺序的敏感性 假设一数据集共有五个对象x1,2,…,x5,每 3应用加权排序的CABOSFV_CSW算法 个对象有六个属性A1,A2,·,A6,其属性值均为 3.1 CABOSFV_CSW算法思想 二值数据，分别为a1,a2,·,a6,使用不干涉序列 CABOSFV.C算法是专门针对分类变量的聚类 1,3,5,10,20,40,80·,如表1所示. 算法，该算法提出了集合的稀疏特征差异度的计算 表1对象集合 方法，在集合稀疏差异度上限参数α的约束下，将 Table 1 Object set n个待聚类的对象自底向上、增量式地生成l个类 对象 a2 a3 a4 a5 a6 CABOSFV.CSW算法基于不干涉序列加权排 T1 1 1 1 1 0 1 序对CABOSFV_C算法进行改进，聚类过程如下： t2 1 0 0 0 I3 1 0 1 0 0 o 步骤1根据定义2计算数据集合X中每个 T4 1 1 1 1 0 0 对象的不干涉序列指数q: 1 0 步骤2按照对象的不干涉序列指数q对数据 不干涉序列指数q计算过程如下： 集中的对象进行升序或降序排序，得到排序后的数 q1=1×1+1×3+1×5+1×10+0×20+ 据集合Y; 1×40=59: 步骤3对加权排序后的数据集合Y采用传统 92=1×1+1×3+1×5+0×10+0×20+ CABOSFV_C算法进行聚类. 0×40=9: 3.2实验分析 9g=1×1+0×3+1×5+0×10+0×20+ 为了验证CABOSFV_CSW算法聚类结果的准 0×40=6: 确性与稳定性，本文将选取UCI数据集中的三个真
· 1096 · 北 京 科 技 大 学 学 报 第 35 卷 q(x,M) − q(y, M) q(y, M) 矛盾，所以 dk(x) =1 且 dk(y)=0 成立. q(x, N) − q(y, N) = ÃnX−1 i=1 di (x) Ni + dk (x) Nk ! − ÃnX−1 i=1 di (y) Ni + dk (y) Nk ! = ÃnX−1 i=1 (di (x) − di (y)) Ni ! + Nk > 0. 这是因为根据 di(x) 和 di(y)(i=1, 2, · · · , k) 只 能取值为 0 或 1，并且根据不干涉序列的定义，Nk 大于前 k−1 项的和，有 nX−1 i=1 (di (x) − di (y)) Ni > − nX−1 i=1 Ni > −Nk. 所以 q(x,N) > q(y,N). (3) 采用 (2) 的方法同理可证：若 q(x, M) < q(y, M)，则 q(x, N) < q(y,N). 2.2 算例 受数据输入顺序影响的算法， 例如 CABOSFV C 算法、BIRCH 算法和 COBWEB 算法， 其大多都是动态、增量式的聚类，因此容易将相临 近但不属于同一类的数据聚到相同类. 本文提出应 用不干涉序列进行加权排序的方法可以将相似度高 的对象排到一起且结果唯一，从而消除算法对数据 输入顺序的敏感性. 假设一数据集共有五个对象 x1, x2, · · · , x5，每 个对象有六个属性 A1, A2, · · · , A6，其属性值均为 二值数据，分别为 a1, a2, · · · , a6，使用不干涉序列 1, 3, 5, 10, 20, 40, 80, · · ·，如表 1 所示. 表 1 对象集合 Table 1 Object set 对象 a1 a2 a3 a4 a5 a6 x1 1 1 1 1 0 1 x2 1 1 1 0 0 0 x3 1 0 1 0 0 0 x4 1 1 1 1 0 0 x5 1 1 1 1 0 1 不干涉序列指数 q 计算过程如下： q1=1×1 + 1×3 + 1×5 + 1×10 + 0×20 + 1×40=59； q2=1×1 + 1×3 + 1×5 + 0×10 + 0×20 + 0×40=9； q3=1×1 + 0×3 + 1×5 + 0×10 + 0×20 + 0×40=6； q4=1×1 + 1×3 + 1×5 + 1×10 + 0×20 + 0×40=19； q5=1×1 + 1×3 + 1×5 + 1×10 + 0×20 + 1×40=59. 根据不干涉序列指数对原对象集合进行排序， 此处采用升序排序，结果如表 2 所示. 表 2 加权排序后的对象集合 Table 2 Objectset after being sorted by weight 对象 q a1 a2 a3 a4 a5 a6 x3 6 1 0 1 0 0 0 x2 9 1 1 1 0 0 0 x4 19 1 1 1 1 0 0 x1 59 1 1 1 1 0 1 x5 59 1 1 1 1 0 1 由表 2 可以看出，经过加权升序排序后，对象 集合中相似的甚至相同的对象被排列在了一起. 其 中 x1 和 x5 两个对象由于其在所有属性上的取值均 相同，因而不干涉序列指数相等. 本文将这样多个 在所有属性上的取值都完全相同的对象视为一个整 体. 对整个对象集合而言，这个整体内部对象的顺 序可能不同，但所采用的任何顺序都是等价的. 以 表 2 为例，即认为 x3, x2, x4, x1, x5 与 x3, x2, x4, x5, x1 是同一个排序结果. 因此在升序或降序确定 的情况下，这种基于不干涉序列指数的加权排序只 有唯一结果，这就使得那些受数据输入顺序影响的 算法可以选择这种唯一的输入顺序. 3 应用加权排序的CABOSFV CSW算法 3.1 CABOSFV CSW 算法思想 CABOSFV C 算法是专门针对分类变量的聚类 算法，该算法提出了集合的稀疏特征差异度的计算 方法，在集合稀疏差异度上限参数 a 的约束下，将 n 个待聚类的对象自底向上、增量式地生成 l 个类. CABOSFV CSW 算法基于不干涉序列加权排 序对 CABOSFV C 算法进行改进，聚类过程如下： 步骤 1 根据定义 2 计算数据集合 X 中每个 对象的不干涉序列指数 q； 步骤 2 按照对象的不干涉序列指数 q 对数据 集中的对象进行升序或降序排序，得到排序后的数 据集合 Y ； 步骤 3 对加权排序后的数据集合 Y 采用传统 CABOSFV C 算法进行聚类. 3.2 实验分析 为了验证 CABOSFV CSW 算法聚类结果的准 确性与稳定性，本文将选取 UCI 数据集中的三个真
第8期 武森等：考虑加权排序的分类数据聚类算法 1097. 实数据集，即Voting、Soybean(small)和Postoper- 次，每次运行的初始数据均是随机排序，每种算 ative Patient Data数据集进行实验，具体数据集描 法皆选取聚类效果最好的参数.另外，选取CA- 述见表3. BOSFV_C算法、CABOSFV.CS算法、k-modes算 表3数据集描述 法和COBWEB算法作为实验参照，对各种算法在 Table 3 Description of data sets 聚类结果的准确性和稳定性上进行比对.其中，虽 样本 二态属 分类属 然k-modes算法结果的不稳定性是由于k个随机初 数据集 类个数 个数 性个数 性个数 始点产生的，但该算法是分类数据聚类领域比较经 Voting 435 2 16 0 典的著名算法，有着实际应用的广泛性，因此也将 Soybean(small) 47 4 12 9 Postoperative 其作为参照与本文算法进行比较 87 3 0 8 Patient Data 由表4可以看出，采用加权升序排序的CA- Soybean(small)有35个属性，因为14个属性 BOSFV_CSW算法在聚类结果准确率上远远高于采 在47个样本中的取值都相同，所以仅保留了剩余 用加权降序排序的结果.产生该现象的原因与加权 的21个属性.对Postoperative Patient Data数据集 排序的特性有关，即：在现实数据中，不干涉序列 中原本有三条各缺失一个属性值的数据，由于其在 指数较小的数据对象经常比不干涉序列指数较大的 整体数据集中所占比例较小，因此该数据集的缺失 数据对象拥有的属性值1少，因此采用加权升序时 值处理方法是剔除有缺失值的数据，实验中进行聚 排在前面的数据对象出现属性值不全为1的概率 类的是84个样本，文章分别采用加权升序排列和加 小，集合稀疏差异度SFD的计算也比较敏感.这 权降序排列对三个数据集进行聚类，以验证加权升 样在进行聚类时，就更容易首先将相似程度高的 序排序和加权降序排序对算法聚类质量的影响.评 数据对象聚到一起，避免把不属于同一类的数据 价聚类结果的指标选用聚类准确率14 对象归到同一类中，从而聚类质量较好.因此，采 为了更好地验证加权排序对数据输入顺序敏 用加权升序的聚类结果一般优于加权降序的聚类 感性的积极作用，每种算法在相同条件下运行100 结果 表4 不同算法聚类结果比较 Table 4 Clustering result comparison of different algorithms Voting Soybean (small) Postoperative Patient Data 算法 准确率（平均）/% 方差 准确率（平均）/% 方差 准确率（平均）/% 方差 CABOSFV.CSW算法（升序） 90.3 0 100.0 0 71.3 0 CABOSFV_CSW算法（降序） 53.1 0 100.0 0 63.2 0 CABOSFV.CS算法 83.0 0.001087 95.3 0.003078 67.3 0.001543 CABOSFV_C算法 81.5 0.002372 89.3 0.007905 66.7 0.002669 k-modes算法 86.6 0.000034 80.1 0.026034 54.7 0.000915 COBWEB算法 41.8 0.087028 42.6 0.003311 61.2 0.078154 此外，加权升序排序的CABOSFV.CSW算法 COBWEB算法以及受随机初始点影响的k-nodes 的准确率优于原始CABOSFV.C算法、CABO- 相比，CABOSFV_CSW算法在处理分类属性数据 SFV_CS算法及受数据输入顺序影响的COBWEB 时有较好的聚类效果. 算法和经典分类数据聚类算法k-modes.另外，由 4结论 方差数据可知，受数据输入顺序或初始点随机性 影响，这几种作为参照实验的算法对不同的输入 定义了不干涉序列指数，通过应用不干涉序列 顺序产生的聚类结果有一定的波动性，而CA- 指数对CABOSFV_C聚类算法进行加权排序处理， BOSFV_CSW算法的聚类结果则是唯一的，从而避 解决了算法受数据输入顺序影响的问题，既保证了 免了由于不同输入顺序而造成的聚类结果质量不高 聚类结果的唯一性，又提高了算法的聚类质量.真 和不唯一的问题，在聚类结果上具有稳定性.因 实数据实验结果表明，在通常情况下，考虑加权升 此采用加权升序排序的CABOSFV_CSW算法结果 序排序的CABOSFV_CSW算法在处理分类属性数 在稳定性和精确性上较原始CABOSFV_C及其改 据时在聚类结果的准确性上有改善，在稳定性上有 进算法有了提升，并且和受数据输入顺序影响的 显著提高，消除了算法对数据输入顺序的敏感性
第 8 期 武 森等：考虑加权排序的分类数据聚类算法 1097 ·· 实数据集，即 Voting、Soybean(small) 和 Postoperative Patient Data 数据集进行实验，具体数据集描 述见表 3. 表 3 数据集描述 Table 3 Description of data sets 数据集 样本 个数 类个数 二态属 性个数 分类属 性个数 Voting 435 2 16 0 Soybean(small) 47 4 12 9 Postoperative Patient Data 87 3 0 8 Soybean(small) 有 35 个属性，因为 14 个属性 在 47 个样本中的取值都相同，所以仅保留了剩余 的 21 个属性. 对 Postoperative Patient Data 数据集 中原本有三条各缺失一个属性值的数据，由于其在 整体数据集中所占比例较小，因此该数据集的缺失 值处理方法是剔除有缺失值的数据，实验中进行聚 类的是 84 个样本. 文章分别采用加权升序排列和加 权降序排列对三个数据集进行聚类，以验证加权升 序排序和加权降序排序对算法聚类质量的影响. 评 价聚类结果的指标选用聚类准确率[14] . 为了更好地验证加权排序对数据输入顺序敏 感性的积极作用，每种算法在相同条件下运行 100 次，每次运行的初始数据均是随机排序，每种算 法皆选取聚类效果最好的参数. 另外，选取 CABOSFV C 算法、CABOSFV CS 算法、k-modes 算 法和 COBWEB 算法作为实验参照，对各种算法在 聚类结果的准确性和稳定性上进行比对. 其中，虽 然 k-modes 算法结果的不稳定性是由于 k 个随机初 始点产生的，但该算法是分类数据聚类领域比较经 典的著名算法，有着实际应用的广泛性，因此也将 其作为参照与本文算法进行比较. 由表 4 可以看出，采用加权升序排序的 CABOSFV CSW 算法在聚类结果准确率上远远高于采 用加权降序排序的结果. 产生该现象的原因与加权 排序的特性有关，即：在现实数据中，不干涉序列 指数较小的数据对象经常比不干涉序列指数较大的 数据对象拥有的属性值 1 少，因此采用加权升序时 排在前面的数据对象出现属性值不全为 1 的概率 小，集合稀疏差异度 SFD 的计算也比较敏感. 这 样在进行聚类时，就更容易首先将相似程度高的 数据对象聚到一起，避免把不属于同一类的数据 对象归到同一类中，从而聚类质量较好. 因此，采 用加权升序的聚类结果一般优于加权降序的聚类 结果. 表 4 不同算法聚类结果比较 Table 4 Clustering result comparison of different algorithms 算法 Voting Soybean (small) Postoperative Patient Data 准确率 (平均)/% 方差 准确率 (平均)/% 方差 准确率 (平均)/% 方差 CABOSFV CSW 算法 (升序) 90.3 0 100.0 0 71.3 0 CABOSFV CSW 算法 (降序) 53.1 0 100.0 0 63.2 0 CABOSFV CS 算法 83.0 0.001087 95.3 0.003078 67.3 0.001543 CABOSFV C 算法 81.5 0.002372 89.3 0.007905 66.7 0.002669 k-modes 算法 86.6 0.000034 80.1 0.026034 54.7 0.000915 COBWEB 算法 41.8 0.087028 42.6 0.003311 61.2 0.078154 此外，加权升序排序的 CABOSFV CSW 算法 的准确率优于原始 CABOSFV C 算法、 CABOSFV CS 算法及受数据输入顺序影响的 COBWEB 算法和经典分类数据聚类算法 k-modes. 另外，由 方差数据可知，受数据输入顺序或初始点随机性 影响，这几种作为参照实验的算法对不同的输入 顺序产生的聚类结果有一定的波动性， 而 CABOSFV CSW 算法的聚类结果则是唯一的，从而避 免了由于不同输入顺序而造成的聚类结果质量不高 和不唯一的问题，在聚类结果上具有稳定性. 因 此采用加权升序排序的 CABOSFV CSW 算法结果 在稳定性和精确性上较原始 CABOSFV C 及其改 进算法有了提升，并且和受数据输入顺序影响的 COBWEB 算法以及受随机初始点影响的 k-modes 相比，CABOSFV CSW 算法在处理分类属性数据 时有较好的聚类效果. 4 结论 定义了不干涉序列指数，通过应用不干涉序列 指数对 CABOSFV C 聚类算法进行加权排序处理， 解决了算法受数据输入顺序影响的问题，既保证了 聚类结果的唯一性，又提高了算法的聚类质量. 真 实数据实验结果表明，在通常情况下，考虑加权升 序排序的 CABOSFV CSW 算法在处理分类属性数 据时在聚类结果的准确性上有改善，在稳定性上有 显著提高，消除了算法对数据输入顺序的敏感性
.1098· 北京科技大学学报 第35卷 CABOSFV_CSW算法的不足在于：如果数据集的 tributes /Proceedings of International Conference on 属性顺序发生变化，数据集的聚类结果会受到影响. Logistics Systems and Intelligent Management.Harbin, 文中所有实验采用的都是原始数据集的属性顺序 2010:973 如何消除数据集的属性顺序对聚类结果的影响还有 [8]Fisher D H.Knowledge acquisition via incremental con- 待更深入的研究. ceptual clustering.Mach Learn,1987,2(2):139 (9]Zhang T.Ramakrishnan R,Livny M.BIRCH:an efficient data clustering method for very large databases//Pro- 参考文献 ceedings of the 1996ACM SIGMOD International Con- ference on Management of Data.Montreal,1996:103 [1]Han J W,Kamber M,Pei J.Data Mining:Concepts and [10]Zhang C,Xia S X.K-means clustering algorithm with Techniques.3rd Ed.Beijing:China Machine Press,2012 improved initial center //Proceedings of Second Interna- (韩家炜，坎伯，裴健.数据挖掘：概念与技术.3版.北京 tional Workshop on Knowledge Discoveryand Data Min- 机械工业出版社，2012) ing.Moscow,2009:790 [2]Onoda T,Sakai M,Yamada S.Careful seeding method [11]Han L B,Wang Q,Jiang Z F,et al.Improved k-means based on independent components analysis for k-means initial clustering center selection algorithm.Comput Eng clustering.J Emerg Technol Web Intell,2012,4(1):51 Appl,2010,46(17):150 [3]Tsai CF,HuangT W.QIDBSCAN:a quick density-based (韩凌波，王强，蒋正锋，等.一种改进的k-means初始聚 clustering technique//International Symposium on Com- 类中心选取算法.计算机工程与应用.2010,46(17)：150) puter,Consumer and Control.Taichung,2012:638 [12]Wu S,Wang J,Tan Y S.Improved CABOSFV clustering [4]Zhang L S,Yang M J,Lei D J.An improved PAM clus- considering data sort.Comput Eng Appl,2011,47(34): tering algorithm based on initial clustering centers.Appl 127 Mech Mater,.2012,135/136:244 (武森，王静，谭一松.考虑数据排序的改进CABOSFV聚 [5]Huang Z X.Extensions to the k-means algorithm for clus- 类.计算机工程与应用，2011,47(34)：127) tering large data sets with categorical values.Data Min- [13]Xue H C.Management Information Systems.2nd Ed. Knowl Discov,1998,2(3):283 Beijing:Tsinghua University Press,1993 [6]He Z Y,Xu X F,Deng S C.Attribute value weighting (薛华成.管理信息系统.2版.北京：清华大学出版社， in k-modes clustering.Expert Syst Appl,2011,38(12): 1993) 15365 [14 Ahmad A,Dey L.A k-mean clustering algorithm for [7]Wu S,Wei G Y.High dimensional data clustering algo- mixed numeric and categorical data.Data Knowl Eng, rithm based on sparse feature vector for categorical at- 2007,63(2):503
· 1098 · 北 京 科 技 大 学 学 报 第 35 卷 CABOSFV CSW 算法的不足在于：如果数据集的 属性顺序发生变化，数据集的聚类结果会受到影响. 文中所有实验采用的都是原始数据集的属性顺序. 如何消除数据集的属性顺序对聚类结果的影响还有 待更深入的研究. 参 考 文 献 [1] Han J W, Kamber M, Pei J. Data Mining: Concepts and Techniques. 3rd Ed. Beijing: China Machine Press, 2012 (韩家炜, 坎伯, 裴健. 数据挖掘：概念与技术. 3 版. 北京: 机械工业出版社, 2012) [2] Onoda T, Sakai M, Yamada S. Careful seeding method based on independent components analysis for k-means clustering. J Emerg Technol Web Intell, 2012, 4(1): 51 [3] Tsai C F, Huang T W. QIDBSCAN: a quick density-based clustering technique //International Symposium on Computer, Consumer and Control. Taichung, 2012: 638 [4] Zhang L S, Yang M J, Lei D J. An improved PAM clustering algorithm based on initial clustering centers. Appl Mech Mater, 2012, 135/136: 244 [5] Huang Z X. Extensions to the k-means algorithm for clustering large data sets with categorical values. Data MinKnowl Discov, 1998, 2(3): 283 [6] He Z Y, Xu X F, Deng S C. Attribute value weighting in k-modes clustering. Expert Syst Appl, 2011, 38(12): 15365 [7] Wu S, Wei G Y. High dimensional data clustering algorithm based on sparse feature vector for categorical attributes // Proceedings of International Conference on Logistics Systems and Intelligent Management. Harbin, 2010: 973 [8] Fisher D H. Knowledge acquisition via incremental conceptual clustering. Mach Learn, 1987, 2(2):139 [9] Zhang T, Ramakrishnan R, Livny M. BIRCH: an efficient data clustering method for very large databases // Proceedings of the 1996ACM SIGMOD International Conference on Management of Data. Montreal, 1996: 103 [10] Zhang C, Xia S X. K-means clustering algorithm with improved initial center //Proceedings of Second International Workshop on Knowledge Discoveryand Data Mining. Moscow, 2009: 790 [11] Han L B, Wang Q, Jiang Z F, et al. Improved k-means initial clustering center selection algorithm. Comput Eng Appl, 2010, 46(17): 150 (韩凌波，王强，蒋正锋，等. 一种改进的 k-means 初始聚 类中心选取算法. 计算机工程与应用, 2010, 46(17): 150) [12] Wu S, Wang J, Tan Y S. Improved CABOSFV clustering considering data sort. Comput Eng Appl, 2011, 47(34): 127 (武森, 王静, 谭一松. 考虑数据排序的改进 CABOSFV 聚 类. 计算机工程与应用, 2011, 47(34): 127) [13] Xue H C. Management Information Systems. 2nd Ed. Beijing: Tsinghua University Press, 1993 (薛华成. 管理信息系统. 2 版. 北京: 清华大学出版社, 1993) [14] Ahmad A, Dey L. A k-mean clustering algorithm for mixed numeric and categorical data. Data Knowl Eng, 2007, 63(2): 503