分类属性数据聚类算法HABOS

工程科学学报，第38卷，第7期：1017-1024,2016年7月 Chinese Journal of Engineering,Vol.38,No.7:1017-1024,July 2016 D0l:10.13374/j.issn2095-9389.2016.07.018;http:/journals.ustb.edu.cn 分类属性数据聚类算法HABOS 武森四，姜丹丹，王蔷 北京科技大学东凌经济管理学院，北京100083 ☒通信作者，E-mail:wusen(@manage.stb.edu.cn 摘要CABOSFV._C是一种针对分类属性高维数据的高效聚类算法，该算法采用集合稀疏差异度进行距离计算，并采用稀 疏特征向量实现数据压缩.该算法的聚类效果受集合稀疏差异度上限参数的影响，而该参数的选取没有明确的指导.针对该 问题提出基于集合稀疏差异度的启发式分类属性数据层次聚类算法(heuristic hierarchical clustering algorithm of categorical data based on sparse feature dissimilarity,HABOS),该方法从聚结型层次聚类思想的角度出发，在聚类数上限参数的约束下，应用新 的内部聚类有效性评价指标(clustering validation index based on sparse feature dissimilarity,CVISFD)进行启发式度量，从而实 现对聚类层次的自动选取.UCI基准数据集的实验结果表明，HABOS有效地提高了聚类准确性和稳定性. 关键词数据挖掘：聚类算法：分类数据：属性 分类号TP311 HABOS clustering algorithm for categorical data WU Sen,JIANG Dan-dan,WANG Qiang Donlinks School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:wusen@manage.ustb.edu.cn ABSTRACT The clustering algorithm based on sparse feature vector for categorical attributes (CABOSFV_C)is an efficient high-di- mensional clustering method for categorical data.Sparse feature dissimilarity (SFD)is used to calculate the distance and sparse fea- ture vector is used to achieve data compression.However,CABOSFV_C algorithm is dependent upon SFD upper limit parameter for which there is no guidance for configuration.Aimed at solving the problem that CABOSFVC algorithm is sensitive to this parameter, a new heuristic hierarchical clustering algorithm of categorical data based on SFD (HABOS)was proposed in this paper.With the con- straint of the upper limit number of clusters,this algorithm applied agglomerative hierarchical clustering and the new internal clustering validation index based on SFD (CVISFD)which was used to measure the results heuristically to achieve the best choice of the cluste- ring level.Three UCI benchmark data sets were used to compare the improved algorithm with the traditional ones.The empirical tests show that HABOS increases the clustering accuracy and stability effectively. KEY WORDS data mining:clustering algorithms:categorical data:attributes 聚类分析是数据挖掘的重要组成部分，它是一种法、BIRCH算法、DBSCAN算法、PAM算法及其改进算 将物理或抽象对象的集合分成相似的对象类，使得同 法-.此外，现实世界中还存在大量分类属性数据， 一类内数据对象之间的相似度较高，不同类的数据对处理分类属性数据的聚类算法有CABOSFV C算 象之间相似度较低的过程0.聚类算法可应用在客户 法同、K-modes算法、COBWEB算法m等. 群划分、孤立点检测、模式识别、文档归类等领域.针 CABOSFV_C算法是一种处理分类属性数据的高 对数值型聚类算法的研究较为深入，例如K-means算 维数据聚类方法，它应用集合稀疏差异度(sparse fea- 收稿日期：20160105 基金项目：国家自然科学基金资助项目(71271027)：高等学校博士学科点专项科研基金资助项目(20120006110037)

工程科学学报，第 38 卷，第 7 期: 1017--1024，2016 年 7 月 Chinese Journal of Engineering，Vol． 38，No． 7: 1017--1024，July 2016 DOI: 10． 13374 /j． issn2095--9389． 2016． 07． 018; http: / /journals． ustb． edu． cn 分类属性数据聚类算法 HABOS 武 森，姜丹丹，王 蔷 北京科技大学东凌经济管理学院，北京 100083  通信作者，E-mail: wusen@ manage． ustb． edu． cn 摘 要 CABOSFV_C 是一种针对分类属性高维数据的高效聚类算法，该算法采用集合稀疏差异度进行距离计算，并采用稀 疏特征向量实现数据压缩． 该算法的聚类效果受集合稀疏差异度上限参数的影响，而该参数的选取没有明确的指导． 针对该 问题提出基于集合稀疏差异度的启发式分类属性数据层次聚类算法( heuristic hierarchical clustering algorithm of categorical data based on sparse feature dissimilarity，HABOS) ，该方法从聚结型层次聚类思想的角度出发，在聚类数上限参数的约束下，应用新 的内部聚类有效性评价指标( clustering validation index based on sparse feature dissimilarity，CVISFD) 进行启发式度量，从而实 现对聚类层次的自动选取． UCI 基准数据集的实验结果表明，HABOS 有效地提高了聚类准确性和稳定性． 关键词 数据挖掘; 聚类算法; 分类数据; 属性 分类号 TP311 HABOS clustering algorithm for categorical data WU Sen ，JIANG Dan-dan，WANG Qiang Donlinks School of Economics and Management，University of Science and Technology Beijing，Beijing 100083，China  Corresponding author，E-mail: wusen@ manage． ustb． edu． cn ABSTＲACT The clustering algorithm based on sparse feature vector for categorical attributes ( CABOSFV_C) is an efficient high-di￾mensional clustering method for categorical data． Sparse feature dissimilarity ( SFD) is used to calculate the distance and sparse fea￾ture vector is used to achieve data compression． However，CABOSFV_C algorithm is dependent upon SFD upper limit parameter for which there is no guidance for configuration． Aimed at solving the problem that CABOSFV_C algorithm is sensitive to this parameter， a new heuristic hierarchical clustering algorithm of categorical data based on SFD ( HABOS) was proposed in this paper． With the con￾straint of the upper limit number of clusters，this algorithm applied agglomerative hierarchical clustering and the new internal clustering validation index based on SFD ( CVISFD) which was used to measure the results heuristically to achieve the best choice of the cluste￾ring level． Three UCI benchmark data sets were used to compare the improved algorithm with the traditional ones． The empirical tests show that HABOS increases the clustering accuracy and stability effectively． KEY WOＲDS data mining; clustering algorithms; categorical data; attributes 收稿日期: 2016--01--05 基金项目: 国家自然科学基金资助项目( 71271027) ; 高等学校博士学科点专项科研基金资助项目( 20120006110037) 聚类分析是数据挖掘的重要组成部分，它是一种 将物理或抽象对象的集合分成相似的对象类，使得同 一类内数据对象之间的相似度较高，不同类的数据对 象之间相似度较低的过程［1］． 聚类算法可应用在客户 群划分、孤立点检测、模式识别、文档归类等领域． 针 对数值型聚类算法的研究较为深入，例如 K-means 算 法、BIＲCH 算法、DBSCAN 算法、PAM 算法及其改进算 法［2--4］． 此外，现实世界中还存在大量分类属性数据， 处理 分 类 属 性 数 据 的 聚 类 算 法 有 CABOSFV _ C 算 法［5］、K-modes［6］算 法、COBWEB 算法［7］等． CABOSFV_C 算法是一种处理分类属性数据的高 维数据聚类方法，它应用集合稀疏差异度( sparse fea-

·1018 工程科学学报，第38卷，第7期 ture dissimilarity,SFD)进行差异度计算，并采用稀疏 个类：x表示一个划分中的某一数据对象；c,和c分别 特征向量来存储数据对象，数据被有效压缩.该聚类 为类i和类j的类中心：d(x,y)表示对象间的距离，而 算法不仅能够处理分类属性数据，而且还能够处理高 维数据，聚类效果也较优.然而CABOSFV_C算法存在 距离的度量方法则可根据实际情况而定：二∑d(x, n: 两个不足：一是对数据输入顺序敏感，不同的输入顺序 c)表示类内距离：d(c:,c)表示两个类的类间距离.对 可能会得到不同的聚类结果；二是需要人为给定集合 于分类属性数据，可以采用集合稀疏差异度SFD来度 稀疏差异度上限参数，该参数直接影响最终的聚类 量类内距离：并且采用两个类中任意两对象之间的最 结果. 小差异度SFD来度量类间距离.由此，本文提出新的 此外，聚类分析的应用还涉及到对聚类结果的评 聚类内部有效性评价指标CVISFD,具体定义如下： 价问题，即聚类有效性评价，聚类相关的研究和应用需 1 -SFD,+sFD, 要一种客观公正的质量评价方法来评判聚类结果的有 1 n CVISFD(ne)= 效性.有效性评价包括外部聚类有效性评价、内部 min SFD.. 聚类有效性评价和相对聚类有效性评价@，其中内部 (2) 聚类有效性评价不借助于类标识、参数等外部信息 式中：SD:为第i类中所有数据对象的集合稀疏差异 由于在实际应用聚类分析时所面对的数据并不都含有 度指数，代表类内总距离；min SFD,为计算类C,中 类标签，因此内部聚类有效性评价被认为是聚类分析 的每个对象x和非C,中的每个对象y的集合稀疏差异 中一个重要而又较难解决的问题.内部聚类有效性评 度，并选择最小的SFD,作为类C,与其他类的类间 价所使用的指标通常被称为内部指标，大多数内部指 距离 标主要针对数值型数据，针对分类属性数据的内部指 CVISFD值越小，表示类内的差异度越小，且类与 标较少. 类之间的差异度越大，从而对应最佳的聚类结果 因此，本文从应用和改进聚类内部有效性评价方 举例说明CVISFD指标评价的过程.假设某聚类 法的角度出发，提出适合CABOSFV_C算法及其改进 结果为三个划分，每个划分中有五个数据对象，如图1 算法的基于SFD的有效性评价指标(clustering valida-- 所示.图中以距离代表对象与对象的差异度以及类内 tion index based on sparse feature dissimilarity,CVIS- 的集合稀疏差异度SFD,距离越远，对象之间差异度越 FD).结合聚结型层次聚类思想，针对CABOSFV_C聚 大，也表明类内紧密度越差.图1(a)中，对类2来说， 类算法的不足，试图消除集合稀疏差异度上限参数对 除其自身外，类1的类内紧密度最差，即类1的类内差 聚类结果的影响，提出相应的改进算法一基于集合 异度SFD,最大，因此关于类2的CVISFD公式的分子 稀疏差异度的启发式分类属性数据层次聚类算法 就是类2的类内平均差异度与类1的类内平均差异度 (heuristic hierarchical clustering algorithm of categorical data based on sparse feature dissimilarity,HABOS). 之和，即Com,-)sD,+SD,类2中的对象x与 章最后进行了改进算法的聚类实验及CVISFD指标的 类3中对象y的距离较类2中各个对象与其他非类2 有效性实验 对象的距离最小，因此类2的类间差异度（类间距离） 1内部有效性指标CVISFD 为对象x与对象y的距离Sp2=SFD,其结果构成 CVISFD公式的分母.于是，类2的CVISFD评价值可 现有的内部有效性评价指标大多主要针对的是数 值型数据，鲜有专门针对分类属性数据的内部有效性 以米出，即为CVISFD,一等，同理可得到其他各类的 评价指标.本文以内部有效性评价指标DBW的改进 CVISFD值.最后，聚类结果的CVISFD评价值是所有 指标DB☒为基础，结合集合稀疏差异度SFD,定义 新的聚类内部有效性评价指标CVISFD,以适应分类属 类的CISD平均值，即CVISFD=号A.CVIsPD.. 性数据的聚类算法对有效性评价的需要 对图1(b)中类2来说，除自身外，类3拥有最大 内部有效性评价指标DB具体计算公式如下： 类内差异度，图1(b)中类2的CVISFD公式的分子是 DB'(nc)= 类2的类内平均差异度与类3的类内平均差异度之 [∑d(x,c)+∑dx,e 和，而图1(b)中类3的类内平均差异度小于图1(a) 1 ni iec 中类1的类内平均差异度，由此可得图1(b)中类2的 CVISFD公式的分子所得小于图1(a),即Com;< (1) Com,而图1(b)中类2的类间差异度与图1(a)一样 式中：nc为聚类结果的类个数：C,表示聚类结果的第i 即关于类2的CVISFD公式的分母不变.分子变小，分

工程科学学报，第 38 卷，第 7 期 ture dissimilarity，SFD) 进行差异度计算，并采用稀疏 特征向量来存储数据对象，数据被有效压缩． 该聚类 算法不仅能够处理分类属性数据，而且还能够处理高 维数据，聚类效果也较优． 然而 CABOSFV_C 算法存在 两个不足: 一是对数据输入顺序敏感，不同的输入顺序 可能会得到不同的聚类结果; 二是需要人为给定集合 稀疏差异度上限参数，该参数直接影响最终的聚类 结果． 此外，聚类分析的应用还涉及到对聚类结果的评 价问题，即聚类有效性评价，聚类相关的研究和应用需 要一种客观公正的质量评价方法来评判聚类结果的有 效性［8--9］． 有效性评价包括外部聚类有效性评价、内部 聚类有效性评价和相对聚类有效性评价［10］，其中内部 聚类有效性评价不借助于类标识、参数等外部信息． 由于在实际应用聚类分析时所面对的数据并不都含有 类标签，因此内部聚类有效性评价被认为是聚类分析 中一个重要而又较难解决的问题． 内部聚类有效性评 价所使用的指标通常被称为内部指标，大多数内部指 标主要针对数值型数据，针对分类属性数据的内部指 标较少． 因此，本文从应用和改进聚类内部有效性评价方 法的角度出发，提出适合 CABOSFV_C 算法及其改进 算法的基于 SFD 的有效性评价指标( clustering valida￾tion index based on sparse feature dissimilarity，CVIS￾FD) ． 结合聚结型层次聚类思想，针对 CABOSFV_C 聚 类算法的不足，试图消除集合稀疏差异度上限参数对 聚类结果的影响，提出相应的改进算法———基于集合 稀疏差异度的启发式分类属性数据层次聚类算法 ( heuristic hierarchical clustering algorithm of categorical data based on sparse feature dissimilarity，HABOS) ． 文 章最后进行了改进算法的聚类实验及 CVISFD 指标的 有效性实验． 1 内部有效性指标 CVISFD 现有的内部有效性评价指标大多主要针对的是数 值型数据，鲜有专门针对分类属性数据的内部有效性 评价指标． 本文以内部有效性评价指标 DB［11］的改进 指标 DB* ［12］为基础，结合集合稀疏差异度 SFD，定义 新的聚类内部有效性评价指标 CVISFD，以适应分类属 性数据的聚类算法对有效性评价的需要． 内部有效性评价指标 DB* 具体计算公式如下: DB* ( nc) = 1 nc ∑ nc i = 1 max j，j≠ [ i 1 ni ∑x∈Ci d( x，ci ) + 1 nj ∑x∈Cj d( x，cj ] ) min l = 1，2，…，nc，l≠i d( ci，cl ) ． ( 1) 式中: nc 为聚类结果的类个数; Ci表示聚类结果的第 i 个类; x 表示一个划分中的某一数据对象; ci和 cj分别 为类 i 和类 j 的类中心; d( x，y) 表示对象间的距离，而 距离的度量方法则可根据实际情况而定; 1 ni ∑x∈Ci d( x， ci ) 表示类内距离; d( ci，cj ) 表示两个类的类间距离． 对 于分类属性数据，可以采用集合稀疏差异度 SFD 来度 量类内距离; 并且采用两个类中任意两对象之间的最 小差异度 SFD 来度量类间距离． 由此，本文提出新的 聚类内部有效性评价指标 CVISFD，具体定义如下: CVISFD( nc) = 1 nc ∑ nc i = 1 max j，j≠ ( i 1 ni SFDi + 1 nj SFDj ) min x∈Ci ，yCi SFDx，y ． ( 2) 式中: SFDi 为第 i 类中所有数据对象的集合稀疏差异 度指数，代表类内总距离; min x∈Ci ，yCi SFDx，y为计算类 Ci中 的每个对象 x 和非 Ci中的每个对象 y 的集合稀疏差异 度，并选择最小的 SFDx，y 作为类 Ci 与其他类的类 间 距离． CVISFD 值越小，表示类内的差异度越小，且类与 类之间的差异度越大，从而对应最佳的聚类结果． 举例说明 CVISFD 指标评价的过程． 假设某聚类 结果为三个划分，每个划分中有五个数据对象，如图 1 所示． 图中以距离代表对象与对象的差异度以及类内 的集合稀疏差异度 SFD，距离越远，对象之间差异度越 大，也表明类内紧密度越差． 图 1( a) 中，对类 2 来说， 除其自身外，类 1 的类内紧密度最差，即类 1 的类内差 异度 SFD1最大，因此关于类 2 的 CVISFD 公式的分子 就是类 2 的类内平均差异度与类 1 的类内平均差异度 之和，即 Com2 = 1 5 SFD2 + 1 5 SFD1 ． 类 2 中的对象 x 与 类 3 中对象 y 的距离较类 2 中各个对象与其他非类 2 对象的距离最小，因此类 2 的类间差异度( 类间距离) 为对象 x 与对象 y 的距离 Sep2 = SFDxy，其结果构成 CVISFD 公式的分母． 于是，类 2 的 CVISFD 评价值可 以求出，即为 CVISFD2 = Com2 Sep2 ，同理可得到其他各类的 CVISFD 值． 最后，聚类结果的 CVISFD 评价值是所有 类的 CVISFD 平均值，即 CVISFD = 1 3 i = ∑1，2，3 CVISFDi ． 对图 1( b) 中类 2 来说，除自身外，类 3 拥有最大 类内差异度，图 1( b) 中类 2 的 CVISFD 公式的分子是 类 2 的类内平均差异度与类 3 的类内平均差异度之 和，而图 1( b) 中类 3 的类内平均差异度小于图 1( a) 中类 1 的类内平均差异度，由此可得图 1( b) 中类 2 的 CVISFD 公式的分子所得小于图 1 ( a ) ，即 Comb 2 ＜ Coma 2，而图 1( b) 中类 2 的类间差异度与图 1( a) 一样 即关于类 2 的 CVISFD 公式的分母不变． 分子变小，分 · 8101 ·

武森等：分类属性数据聚类算法HABOS ·1019· (a) 类1 类2 类3 fe 类1 类2 类3 图1 CVISFD指标评价.(a)第1种聚类结果：(b)第2种聚类结果：(c)第3种聚类结果 Fig.I CVISFD index evaluation:(a)the first clustering results;(b)the second clustering results:(c)the third clustering results 母不变，则整体变小，所以图1(b)中类2的CVISFD评 定义2.1（最小SFD集合对）假设数据集的属性 价值小于图1(a),即CVISFDSep?,因此图1(c)中 两个集合X,X,u,vCX,u≠v称为最小SFD集合对， 类2的CVISFD公式的分母所得大于图1(a).又因为 以集合的形式记为{X.,X,}. 图1(c)中关于类2的CVISFD公式的分子与图1(a) 规则2.1（多类合并规则）在聚结型层次聚类过 一样.分子不变，分母变大，则整体变小，所以图1() 程中，假设当前分类属性数据集的划分为X={X,,X2, 中类2的CVISFD小于图1（a),即CVISFD5< …,X},即包含n个类，集合稀疏差异度作为差异度 CVISFD,仅对类2来说，图1(c)中的聚类效果优于 度量方法，任意两个类合并之后的集合稀疏差异度记 图1(a). 为SFD(X.UX),集合XC={X,X,},{X,X,}, 2基于集合稀疏差异度的启发式分类属性 化X,…,{XX}(1≤s≤2)为s个取得最 数据层次聚类算法 小集合稀疏差异度SFD的集合对，则规定合并步骤 2.1算法概念基础 如下. 传统层次聚类算法通过计算两两类间的差异度 (1)定义集合X:=⑦为最终应予以合并的类的 (或距离)，选择最相似的两个类进行合并，其中两个 集合，令k=1. 类之间距离的度量方法主要包括相似性度量方法和联 (2)任意选择一个最小SFD集合对{X:,X}C 接规则.本文提出的算法采用集合稀疏差异度SFD作 XC,将该集合对记为X,令XC=XC-{X,X}; 为差异度计算方法，以获得集合稀疏差异度（即差异 (3)若此时XC≠O,则遍历XC中的最小SFD集 度)最小的类，将其合并.然而在实际应用中，取得最 合对. 小集合稀疏差异度的类组合可能会多于1组，因此本 ①当存在其他某一最小SD集合对{X:,X}C 文在定义最小SFD集合对（定义2.1）的基础之上，提 XC中的任一类元素出现在X中，即IXU{X,X,}I< 出多类合并规则（规则2.1）. IXI+I{X,X}1,则将该最小SD集合对{X,X,}

武 森等: 分类属性数据聚类算法 HABOS 图 1 CVISFD 指标评价． ( a) 第 1 种聚类结果; ( b) 第 2 种聚类结果; ( c) 第 3 种聚类结果 Fig． 1 CVISFD index evaluation: ( a) the first clustering results; ( b) the second clustering results; ( c) the third clustering results 母不变，则整体变小，所以图 1( b) 中类 2 的 CVISFD 评 价值小于图 1( a) ，即 CVISFDb 2 ＜ CVISFDa 2，仅对类 2 来 说，图 1( b) 中的聚类结果优于图 1( a) ． 图 1( c) 中类 2 的类间距离变为对象 x 和对象 z 之 间的集合稀疏差异度 Sepc 2 = SFDxz，较图 1( a) 中类 2 的 类间差异度有所增加，即 Sepc 2 ＞ Sepa 2，因此图 1( c) 中 类 2 的 CVISFD 公式的分母所得大于图 1( a) ． 又因为 图 1( c) 中关于类 2 的 CVISFD 公式的分子与图 1( a) 一样． 分子不变，分母变大，则整体变小，所以图 1( c) 中 类 2 的 CVISFD 小 于 图 1 ( a ) ，即 CVISFDc 2 ＜ CVISFDa 2，仅对类 2 来说，图 1 ( c) 中的聚类效果优于 图 1( a) ． 2 基于集合稀疏差异度的启发式分类属性 数据层次聚类算法 2. 1 算法概念基础 传统层次聚类算法通过计算两两类间的差异度 ( 或距离) ，选择最相似的两个类进行合并，其中两个 类之间距离的度量方法主要包括相似性度量方法和联 接规则． 本文提出的算法采用集合稀疏差异度 SFD 作 为差异度计算方法，以获得集合稀疏差异度( 即差异 度) 最小的类，将其合并． 然而在实际应用中，取得最 小集合稀疏差异度的类组合可能会多于 1 组，因此本 文在定义最小 SFD 集合对( 定义 2. 1) 的基础之上，提 出多类合并规则( 规则 2. 1) ． 定义 2. 1( 最小 SFD 集合对) 假设数据集的属性 为分类变量，其划分为 X = { X1，X2，…，Xn } ，共有 n 个 类划分，计算任意两个集合合并后的集合稀疏差异度 SFD( Xi∪Xj ) ，i，j = 1，2，…，n，i≠j，得到最小集合稀疏 差异度 SFDmin，将得到最小集合稀疏差异度 SFDmin的 两个集合 Xu，Xv，u，vX，u≠v 称为最小 SFD 集合对， 以集合的形式记为{ Xu，Xv} ． 规则 2. 1( 多类合并规则) 在聚结型层次聚类过 程中，假设当前分类属性数据集的划分为 X = { X1，X2， …，Xn } ，即包含 n 个类，集合稀疏差异度作为差异度 度量方法，任意两个类合并之后的集合稀疏差异度记 为 SFD( Xu ∪Xv ) ，集合 XC = { { Xi1 ，Xi2 } ，{ Xi3 ，Xi4 } ， { Xi5 ，Xi6 } ，…，{ Xi2s － 1 ，Xi2s ( } } 1≤s≤ n ) 2 为 s 个取得最 小集合稀疏差异度 SFDmin的集合对，则规定合并步骤 如下． ( 1) 定义集合 X'c = 为最终应予以合并的类的 集合，令 k = 1． ( 2) 任意选择一个最小 SFD 集合对{ Xi a ，Xi b }  XC，将该集合对记为 X'c k ，令 XC = XC － { Xi a ，Xi b } ; ( 3) 若此时 XC≠，则遍历 XC 中的最小 SFD 集 合对． ① 当存在其他某一最小 SFD 集合对{ Xi c ，Xi d }  XC 中的任一类元素出现在 X'ck 中，即| X'ck ∪{ Xi c ，Xi d } | ＜ | X'c k | + | { Xi c ，Xi d } | ，则将该最小 SFD 集合对{ Xi c ，Xi d } · 9101 ·

·1020· 工程科学学报，第38卷，第7期 与X合并，即X:=XU{X:,X},并且有XC=XC- {X,X}: SFD=SFD ②当不存在重复类元素时，X:=X:U{X},k= k+1,转步骤(2). SFD=SFD (4)若XC=O,则X:=X:U{X}.将X:中的每 SFD=SFD, 一个集合进行合并. a( 举例来说，假设当前数据集X有10个类，其划分 -SFD SFD=SFD 可以表示为X={a},{b},{c},{d},{e},{f},{g}, h},{i},j},计算类与类的稀疏差异度SD.已知 ○d Oh 类a和b、a和c、b和e、f和gi和j的稀疏差异度SFD 图2多最小SFD情况举例 同时取最小值，即XC={{a,b},{a,c},{b,e},{f,g}, Fig.2 Example for more than one minimum SFD {i,j}}.该最小值也可能为0，取值为0意味着两个类 的稀疏特征值完全相同，应予以合并.假设该数据集 当前的划分情况如图2所示.为了形象地表示多类合 并的情况，图中用距离表示集合稀疏差异度.多类合 并的情况意味着其分别合并的优先级同时是最高的， 理应同时进行合并. 首先选择第1个最小SFD集合对X={a,b},在 剩余集合XC=-XC-{a,b}={{a,c},{b,e},{E,g}, {i,j}}中搜索，发现最小SFD集合对{a,c}中类a出现 图3多最小SFD极端情况举例 在X中，因此将X与{a,c}合并，形成X={a,b,c}. Fig.3 Extreme example for more than one minimum SFD 然后重新在集合XC=XC-{a,c}={b,e},{f,g}, 建立一个类，形成层次0.然后计算任意两个类合并后 {i,j}}中搜索，发现最小SFD集合对{b,e}中的类b 的集合稀疏差异度SFD,根据规则2.1（多类合并规 出现在X中，因此将X与{b,e}合并，形成X={a, 则)将得到最小集合稀疏差异度的类进行合并，形成 b,c,d}.此时集合XC=XC-{b,e}={f,g},{i,j}} 层次1.重新计算当前层次中任意两个类之间的集合 中已无与X:有交集的最小SFD集合对，因此在集合 稀疏差异度，再次根据多类合并规则将取得最小集合 XC中再次任意选择一个最小SFD集合对{f,g},令 稀疏差异度的类合并，形成新的层次，反复操作，直到 X,={E,g}.然而在集合XC=XC-{,g}={{i,j}中 所有的类被合并到唯一类中，或者类与类之间不能再 没有与X,相交集的最小SFD集合对，所以转向集合 合并（即任意两个类都不存在取值全为1的属性）为 XC中下一个最小SFD集合对{i,j}.令X={i,j},此 止.该过程示意图如图4所示 时集合XC=XC-{i,j}=⑦，已无可搜索的集合对，最 层次0 层次1 层次2 层次3 层次4 终形成的应合并类的集合为X={X,X,X}={a, b,c,d},{f,g},{i,j}}. 因此，根据多类合并规则，图中类g和「、类i和j ah ah ah 应同时合并.对于多组最小SFD集合对中出现重复的 abede 问题，如图2中的类a、b、c和e,根据多类合并规则，应 将取最小SFD值集合对中涉及到重复类的组合全部 ede 合并在一起，即将类a、b、c和e一次性合并为一个类. de 若考虑极端特殊情况，假设当前有七个类划分，若 类a、b、c,d,e、f和g中任意两个类合并后的集合稀疏 差异度最小值为d,此时根据多类合并规则产生的最 SFD=SFD SFD=SFD 终合并集合为X={a,b,c,d,e,f,g}},如图3所示， SFD=SFD SFD=SFD 该情况下将任何类与其他类分开都是没有依据的.因 此，按照本文多类合并规则，此时会将所有对象归入同 图4 HABOS算法聚类过程示意图 一个类中 Fig.4 Clustering process of HABOS algorithm 2.2 HABOS算法过程 HABOS聚类过程结束后，关键在于如何选取最优 进入HABOS聚类过程，算法首先为每个数据对象 的聚类层次结果.本文采用专门针对分类属性数据设

工程科学学报，第 38 卷，第 7 期 与 X'c1 合并，即 X'c k = X'c k ∪{ Xi c ，Xi d } ，并且有 XC = XC － { Xi c ，Xi d } ; ② 当不存在重复类元素时，X'c = X'c∪{ X'c k } ，k = k + 1，转步骤( 2) ． ( 4) 若 XC = ，则 X'c = X'c∪{ X'c k } ． 将 X'c 中的每 一个集合进行合并． 举例来说，假设当前数据集 X 有 10 个类，其划分 可以表示为 X = { { a} ，{ b} ，{ c} ，{ d} ，{ e} ，{ f} ，{ g} ， { h} ，{ i} ，{ j} } ，计算类与类的稀疏差异度 SFD． 已知 类 a 和 b、a 和 c、b 和 e、f 和 g、i 和 j 的稀疏差异度 SFD 同时取最小值，即 XC = { { a，b} ，{ a，c} ，{ b，e} ，{ f，g} ， { i，j} } ． 该最小值也可能为 0，取值为 0 意味着两个类 的稀疏特征值完全相同，应予以合并． 假设该数据集 当前的划分情况如图 2 所示． 为了形象地表示多类合 并的情况，图中用距离表示集合稀疏差异度． 多类合 并的情况意味着其分别合并的优先级同时是最高的， 理应同时进行合并． 首先选择第 1 个最小 SFD 集合对 X'c1 = { a，b} ，在 剩余集合 XC = XC － { a，b} = { { a，c} ，{ b，e} ，{ f，g} ， { i，j} } 中搜索，发现最小 SFD 集合对{ a，c} 中类 a 出现 在 X'c1 中，因此将 X'c1 与{ a，c} 合并，形成 X'c1 = { a，b，c} ． 然后重新在集合 XC = XC － { a，c} = { { b，e} ，{ f，g} ， { i，j} } 中搜索，发现最小 SFD 集合对{ b，e} 中的类 b 出现在 X'c1 中，因此将 X'c1 与{ b，e} 合并，形成 X'c1 = { a， b，c，d} ． 此时集合 XC = XC － { b，e} = { { f，g} ，{ i，j} } 中已无与 X'c1有交集的最小 SFD 集合对，因此在集合 XC 中再次任意选择一个最小 SFD 集合对{ f，g} ，令 X'c2 = { f，g} ． 然而在集合 XC = XC － { f，g} = { { i，j} } 中 没有与 X'c2相交集的最小 SFD 集合对，所以转向集合 XC 中下一个最小 SFD 集合对{ i，j} ． 令 X'c3 = { i，j} ，此 时集合 XC = XC － { i，j} = ，已无可搜索的集合对，最 终形成的应合并类的集合为 X'c = { X'c1 ，X'c2 ，X'c3 } = { { a， b，c，d} ，{ f，g} ，{ i，j} } ． 因此，根据多类合并规则，图中类 g 和 f、类 i 和 j 应同时合并． 对于多组最小 SFD 集合对中出现重复的 问题，如图 2 中的类 a、b、c 和 e，根据多类合并规则，应 将取最小 SFD 值集合对中涉及到重复类的组合全部 合并在一起，即将类 a、b、c 和 e 一次性合并为一个类． 若考虑极端特殊情况，假设当前有七个类划分，若 类 a、b、c、d、e、f 和 g 中任意两个类合并后的集合稀疏 差异度最小值为 d，此时根据多类合并规则产生的最 终合并集合为 X'c = { { a，b，c，d，e，f，g} } ，如图 3 所示， 该情况下将任何类与其他类分开都是没有依据的． 因 此，按照本文多类合并规则，此时会将所有对象归入同 一个类中． 2. 2 HABOS 算法过程 进入 HABOS 聚类过程，算法首先为每个数据对象 图 2 多最小 SFD 情况举例 Fig． 2 Example for more than one minimum SFD 图 3 多最小 SFD 极端情况举例 Fig． 3 Extreme example for more than one minimum SFD 建立一个类，形成层次 0． 然后计算任意两个类合并后 的集合稀疏差异度 SFD，根据规则 2. 1 ( 多类合并规 则) 将得到最小集合稀疏差异度的类进行合并，形成 层次 1． 重新计算当前层次中任意两个类之间的集合 稀疏差异度，再次根据多类合并规则将取得最小集合 稀疏差异度的类合并，形成新的层次，反复操作，直到 所有的类被合并到唯一类中，或者类与类之间不能再 合并( 即任意两个类都不存在取值全为 1 的属性) 为 止． 该过程示意图如图 4 所示． 图 4 HABOS 算法聚类过程示意图 Fig． 4 Clustering process of HABOS algorithm HABOS 聚类过程结束后，关键在于如何选取最优 的聚类层次结果． 本文采用专门针对分类属性数据设 · 0201 ·

武森等：分类属性数据聚类算法HABOS ·1021· 计的内部有效性评价指标CVISFD来对聚类结果的层 步骤3根据多类合并原则（规则2.1），将产生 次进行有效地评价，从而启发式地选择最佳划分.所 SFD最小值的类进行合并： 谓启发式，就是借助于数据本身特征或对问题的具体 步骤4如果此时聚类个数nc在2到nc范围 分析，从而得到问题满意解 内，即l<nc≤ncx,则计算CVISFD评价指标值，记为 由于聚类开始阶段的层次结果大多以一个数据对 CVISFD: 象作为一个类，而在实际应用中，类个数c远远小于 步骤5重复步骤2、3和4，直至所有类被合并为 数据个数n,即nc<<n,因此HABOS算法需要人工输 一个类，或各类之间已经不能够再合并，即任意两个类 入一个所能接受的聚类数上限cx·对于那些聚类个 合并后没有同时为1的属性值为止： 数大于nc的层次，算法将不考虑对其进行相关评 步骤6选择取得最小CVISFD指标值的聚类层 价，从而节省大量运算资源.当一个数据作为一个类 次结果为算法最终聚类结果，认为该结果为最佳划分 时，类内差异度全部为O,使得CVISFD指标值取最小 2.3 HABOS算法时间复杂度分析 值0，而正确层次的CVISFD值一般会大于0，这也是算 假设数据集有n个对象，采用HABOS算法对其进 法需要引入聚类数上限的原因之一.当层次的聚类个 行聚类，若每层次只合并两个对象，则此时的类个数递 数小于或等于聚类数上限nc时，算法将应用CVIS- 减速度最慢，进而产生最大的计算量.HABOS算法除 FD指标对此时的聚类结果进行评价，并给出评价指标 首次计算任意两个类的集合稀疏差异度外，其余层次 值.另外，值得注意的是，由于聚类分析的目的在于将 只需计算与上一层次产生变化的类与其他类之间的集 n个数据划分为组，在实际应用中若将所有数据划分 合稀疏差异度，其他没有发生改变的类之间的集合稀 为一个类则丧失聚类的意义，因此本文也将不考虑对 疏差异度保持不变，因此在实现HABOS算法时可以通 形成一个类的层次进行评价.HABOS评价过程的示 过存储减少计算量.第0层需要进行C?次计算以获 意图如图5所示，图中假设聚类数上限nc=3. 得两两类合并后的集合稀疏差异度，从下一层开始只 nc=3 需要计算最新合并的类与其他n-2个类合并后的集 合稀疏差异度，而其他元素不变.下一层次同理，直到 层次4 abede 合并后的类个数为1为止.于是，最不理想状态的计 算次数为C2+(n-2)+(n-3)+…+2+1,即n2- 2n+1.可知HABOS算法的计算复杂度在最不理想的 层次3 CVISFD(ne=2) 状态下为O(n2),与原算法CABOSFV_C的计算复杂 度O(n)相比有所增加，因为HABOS算法需要进行全 局性搜索 层次2 CVISFD(ne=3) 3实验分析 3.1实验设计 本文实验选取的三个UCI基准数据集分别是Vot- 层次1 ah ing、Soybean(small)和Balloon(adult+stretch),见表 1.实验采用HABOS算法、CABOSFV C算法和经典K- modes聚类算法分别进行聚类操作，并对聚类结果进 行相关分析. 层次0 本文采取随机排序的实验方式，用不同算法对各 数据集进行聚类操作，具体实验规则如下： 图5 HABOS算法评价过程示意图 (1)所有算法执行前，对各数据集进行随机排序， Fig.5 Evaluation process of HABOS algorithm 共计1O0次随机实验，每次实验采用HABOS、CABOS- 综上所述，本文假设X是具有n个对象的数据集， FV_C和K-modes三种算法在相同的随机数据集顺序 每个对象共有m个属性，nc为聚类数上限，算法的 下进行聚类操作 整体操作过程如下： (2)设置HABOS算法的聚类数上限nc为9. 步骤1为每一个对象建立一个集合，即每一对 (3)使用CABOSFV._C算法进行聚类时，每次实 象就是一个类： 验的稀疏差异度上限参数都设定在某个范围内，如 步骤2计算任意两个类之间的集合稀疏差异度 D.1,10.0],在该范围内，以某一步长为增长量，如 指数SFD: 0.1,进行多次实验，选择取得聚类结果最好的参数值

武 森等: 分类属性数据聚类算法 HABOS 计的内部有效性评价指标 CVISFD 来对聚类结果的层 次进行有效地评价，从而启发式地选择最佳划分． 所 谓启发式，就是借助于数据本身特征或对问题的具体 分析，从而得到问题满意解． 由于聚类开始阶段的层次结果大多以一个数据对 象作为一个类，而在实际应用中，类个数 nc 远远小于 数据个数 n，即 nc ＜ ＜ n，因此 HABOS 算法需要人工输 入一个所能接受的聚类数上限 ncmax ． 对于那些聚类个 数大于 ncmax 的层次，算法将不考虑对其进行相关评 价，从而节省大量运算资源． 当一个数据作为一个类 时，类内差异度全部为 0，使得 CVISFD 指标值取最小 值0，而正确层次的 CVISFD 值一般会大于0，这也是算 法需要引入聚类数上限的原因之一． 当层次的聚类个 数小于或等于聚类数上限 ncmax时，算法将应用 CVIS￾FD 指标对此时的聚类结果进行评价，并给出评价指标 值． 另外，值得注意的是，由于聚类分析的目的在于将 n 个数据划分为组，在实际应用中若将所有数据划分 为一个类则丧失聚类的意义，因此本文也将不考虑对 形成一个类的层次进行评价． HABOS 评价过程的示 意图如图 5 所示，图中假设聚类数上限 ncmax = 3． 图 5 HABOS 算法评价过程示意图 Fig． 5 Evaluation process of HABOS algorithm 综上所述，本文假设 X 是具有 n 个对象的数据集， 每个对象共有 m 个属性，ncmax 为聚类数上限，算法的 整体操作过程如下: 步骤 1 为每一个对象建立一个集合，即每一对 象就是一个类; 步骤 2 计算任意两个类之间的集合稀疏差异度 指数 SFD; 步骤 3 根据多类合并原则( 规则 2. 1) ，将产生 SFD 最小值的类进行合并; 步骤 4 如果此时聚类个数 nc 在 2 到 ncmax范围 内，即 1 ＜ nc≤ncmax，则计算 CVISFD 评价指标值，记为 CVISFDnc ; 步骤 5 重复步骤 2、3 和 4，直至所有类被合并为 一个类，或各类之间已经不能够再合并，即任意两个类 合并后没有同时为 1 的属性值为止; 步骤 6 选择取得最小 CVISFD 指标值的聚类层 次结果为算法最终聚类结果，认为该结果为最佳划分． 2. 3 HABOS 算法时间复杂度分析 假设数据集有 n 个对象，采用 HABOS 算法对其进 行聚类，若每层次只合并两个对象，则此时的类个数递 减速度最慢，进而产生最大的计算量． HABOS 算法除 首次计算任意两个类的集合稀疏差异度外，其余层次 只需计算与上一层次产生变化的类与其他类之间的集 合稀疏差异度，其他没有发生改变的类之间的集合稀 疏差异度保持不变，因此在实现 HABOS 算法时可以通 过存储减少计算量． 第 0 层需要进行 C2 n 次计算以获 得两两类合并后的集合稀疏差异度，从下一层开始只 需要计算最新合并的类与其他 n － 2 个类合并后的集 合稀疏差异度，而其他元素不变． 下一层次同理，直到 合并后的类个数为 1 为止． 于是，最不理想状态的计 算次数为 C2 n + ( n － 2) + ( n － 3) + … + 2 + 1，即 n2 － 2n + 1． 可知 HABOS 算法的计算复杂度在最不理想的 状态下为 O( n2 ) ，与原算法 CABOSFV_C 的计算复杂 度 O( n) 相比有所增加，因为 HABOS 算法需要进行全 局性搜索． 3 实验分析 3. 1 实验设计 本文实验选取的三个 UCI 基准数据集分别是 Vot￾ing、Soybean( small) 和 Balloon( adult + stretch) ，见表 1． 实验采用 HABOS 算法、CABOSFV_C 算法和经典 K￾modes 聚类算法分别进行聚类操作，并对聚类结果进 行相关分析． 本文采取随机排序的实验方式，用不同算法对各 数据集进行聚类操作，具体实验规则如下: ( 1) 所有算法执行前，对各数据集进行随机排序， 共计 100 次随机实验，每次实验采用 HABOS、CABOS￾FV_C 和 K-modes 三种算法在相同的随机数据集顺序 下进行聚类操作． ( 2) 设置 HABOS 算法的聚类数上限 ncmax为 9． ( 3) 使用 CABOSFV_C 算法进行聚类时，每次实 验的稀疏差异度上限参数都设定在某个范围内，如 ［0. 1，10. 0］，在该范围内，以某一步长为 增 长 量，如 0. 1，进行多次实验，选择取得聚类结果最好的参数值 · 1201 ·

·1022 工程科学学报，第38卷，第7期 作为该次算法的最终输入参数，该结果为该次算法的 ig数据集的对象个数为435，因此对该数据集的实验 最终结果 采用的聚类数上限参数值为2,3,4，，30：Soybean (4)K-modes算法初始聚类数将直接选择各数据 数据集的对象个数为47，因此该数据集实验的聚类数 集实际的类个数作为输入参数. 上限参数值为2~20：Balloon数据集的对象个数为20， (5)HABOS算法采用多类合并规则，该方法不受 因此设定实验需要的聚类数上限参数值为2,3,4， 数据输入顺序影响，因此该算法运行100次的结果是 …,15. 唯一的.其他两个算法不论是受到数据输入顺序影响 表2列出CVISFD指标对三个数据集聚类结果各 还是初始随机性的影响，各算法运行100次的结果不 层次的评价值及其实际准确率，CVISFD指标值保留小 是唯一的.实验采用平均值作为算法最终的结果. 数点后两位数字，准确率保留小数点后一位数字（下 表1数据集描述 同).多数情况下，CVISFD值越小，算法的正确率越 Table 1 Dataset description 高，但是针对Balloon数据集而言，由于Balloon数据集 二值属性分类属性 对象个数较少以及对象间相似度相对较大，所以在最 数据集 样本个数类个数 个数个数 大簇个数的条件下，算法将数据集聚为两个簇，满足终 Voting 435 2 16 止条件后只产生一个可供评价的层次，因此HABOS算 Soybean(small) 47 4 12 9 法中CVISFD有效性评价指标只有唯一选择，而该层 Balloon (adult stretch) 20 0 表2 CVISFD指标对各聚类结果层次的评价值及准确率 Table 2 Evaluation values and accuracy of CVISFD indexes on the re- 此外，聚类结果的正确率也是衡量算法有效性的 sults of clustering 一个重要依据.本文实验选用Micro-p圆作为评价聚 Voting数据集 Soybean数据集 Balloon数据集 类结果的正确率指标.该方法将每个类中得到正确聚 CVISFD正确率/%CVISFD正确率/%CVISFD正确率/% 类的对象个数与数据样本总数相除，从而得到该算法 聚类结果的正确率。该正确率计算方法的具体表述 0.21 57.4 2499.84100.0 如下. 0.11 78.7 假设X为数据集，已知该数据集有m个类，其类 0.09 100.0 标识分别记为C,C2,…,Cm,采用某聚类算法后，得 5 0.15 97.9 到n个类的聚类结果，将其分别标记为P,P2,…, 65.91 93.8 0.57 93.6 P。,A是类P中属于类C,的对象个数，则可以得到如 72.77 93.8 017 93.6 下矩阵： 8 1.93 93.8 010 91.5 Ap AB Aim 9 1.65 0.1 89. 10 87 A3m 11 24 74 12 0.8 130.01 15 14 r= 15 1X1 (3) 16 由此可以得到聚类正确率的计算公式（式(3）)， 17 0.01 07 其中IXI为整个数据集中的对象个数.该r值越大，则 0.38 表明通过算法得到的聚类结果越接近已知类标识，聚 8 类质量越好 0.45 3.2实验结果分析 20 上节提到根据经验预先将聚类数上限参数ncx 0.44 定义为9，为了验证聚类数上限参数取值对聚类结果 24 0.45 的影响，本小节实验将设定不同的聚类数上限值，分别 0.45 使用Voting数据集、Soybean数据集和Balloon数据集 27 0.51 86. 进行HABOS聚类操作.本文根据数据集所包含的数 280.40 86.7 据个数不同，设置不同的参数值范围.具体来说，V- 30

工程科学学报，第 38 卷，第 7 期 作为该次算法的最终输入参数，该结果为该次算法的 最终结果． ( 4) K-modes 算法初始聚类数将直接选择各数据 集实际的类个数作为输入参数． ( 5) HABOS 算法采用多类合并规则，该方法不受 数据输入顺序影响，因此该算法运行 100 次的结果是 唯一的． 其他两个算法不论是受到数据输入顺序影响 还是初始随机性的影响，各算法运行 100 次的结果不 是唯一的． 实验采用平均值作为算法最终的结果． 表 1 数据集描述 Table 1 Dataset description 数据集 样本个数 类个数 二值属性 个数 分类属性 个数 Voting 435 2 16 0 Soybean( small) 47 4 12 9 Balloon( adult + stretch) 20 2 0 4 此外，聚类结果的正确率也是衡量算法有效性的 一个重要依据． 本文实验选用 Micro-p［13］作为评价聚 类结果的正确率指标． 该方法将每个类中得到正确聚 类的对象个数与数据样本总数相除，从而得到该算法 聚类结果的正确率． 该正确率计算方法的具体表述 如下． 假设 X 为数据集，已知该数据集有 m 个类，其类 标识分别记为 C1，C2，…，Cm，采用某聚类算法后，得 到 n 个类的聚类结果，将其分别标记为 P1，P2，…， Pn，Aij是类 Pi中属于类 Cj的对象个数，则可以得到如 下矩阵: A11 A12 A13 … A1m A21 A22 A23 … A2m A31 A32 A33 … A3m … … … … … An1 An2 An3 … A               nm ， r = ∑ m j = 1 maxAij | X | ． ( 3) 由此可以得到聚类正确率的计算公式( 式( 3) ) ， 其中| X| 为整个数据集中的对象个数． 该 r 值越大，则 表明通过算法得到的聚类结果越接近已知类标识，聚 类质量越好． 3. 2 实验结果分析 上节提到根据经验预先将聚类数上限参数 ncmax 定义为 9，为了验证聚类数上限参数取值对聚类结果 的影响，本小节实验将设定不同的聚类数上限值，分别 使用 Voting 数据集、Soybean 数据集和 Balloon 数据集 进行 HABOS 聚类操作． 本文根据数据集所包含的数 据个数不同，设置不同的参数值范围． 具体来说，Vot￾ing 数据集的对象个数为 435，因此对该数据集的实验 采用的聚类数上限参数值为 2，3，4，…，30; Soybean 数据集的对象个数为 47，因此该数据集实验的聚类数 上限参数值为 2 ～ 20; Balloon 数据集的对象个数为 20， 因此设定实验需要的聚类数上限参数值为 2，3，4， …，15． 表 2 列出 CVISFD 指标对三个数据集聚类结果各 层次的评价值及其实际准确率，CVISFD 指标值保留小 数点后两位数字，准确率保留小数点后一位数字( 下 同) ． 多数情况下，CVISFD 值越小，算法的正确率越 高，但是针对 Balloon 数据集而言，由于 Balloon 数据集 对象个数较少以及对象间相似度相对较大，所以在最 大簇个数的条件下，算法将数据集聚为两个簇，满足终 止条件后只产生一个可供评价的层次，因此 HABOS 算 法 中 CVISFD 有效性评价指标只有唯一选择，而该层 表 2 CVISFD 指标对各聚类结果层次的评价值及准确率 Table 2 Evaluation values and accuracy of CVISFD indexes on the re￾sults of clustering nc Voting 数据集 Soybean 数据集 Balloon 数据集 CVISFD 正确率/% CVISFD 正确率/% CVISFD 正确率/% 2 — — 0. 21 57. 4 2499. 84 100. 0 3 — — 0. 11 78. 7 — — 4 — — 0. 09 100. 0 — — 5 — — 0. 15 97. 9 — — 6 5. 91 93. 8 0. 57 93. 6 — — 7 2. 77 93. 8 0. 17 93. 6 — — 8 1. 93 93. 8 0. 19 91. 5 — — 9 1. 65 93. 8 0. 18 89. 3 — — 10 1. 42 93. 8 0. 19 87. 2 — — 11 1. 28 93. 8 0. 24 74. 5 — — 12 0. 83 93. 8 — — — — 13 0. 01 93. 8 — — 0. 09 45. 0 14 — — 0. 64 63. 8 — — 15 — — 0. 64 61. 7 — — 16 — — 0. 68 57. 4 ∕ ∕ 17 0. 01 92. 9 0. 70 51. 1 ∕ ∕ 18 0. 38 92. 6 0. 70 48. 9 ∕ ∕ 19 0. 45 86. 7 0. 71 46. 8 ∕ ∕ 20 — — 0. 69 46. 8 ∕ ∕ 23 0. 44 86. 7 ∕ ∕ ∕ ∕ 24 0. 45 86. 7 ∕ ∕ ∕ ∕ 25 0. 45 86. 7 ∕ ∕ ∕ ∕ 27 0. 51 86. 7 ∕ ∕ ∕ ∕ 28 0. 40 86. 7 ∕ ∕ ∕ ∕ 30 — — ∕ ∕ ∕ ∕ · 2201 ·

武森等：分类属性数据聚类算法HABOS ·1023· 次取得较好的准确率.本文认为该结果较好主要归功 情况.对于Balloon数据集，当聚类数上限参数值小于 于HABOS算法的聚类过程，而CVISFD指标对该数据 等于12时，算法均取得了最好准确率100.0%，当聚类 集的聚类有着较小的贡献，所以CVISFD指标并不是 数上限参数值大于12时，准确率有了较大的波动，但 针对所有数据集都有绝对的指导意义. 由于该数据集对象个数仅为20，若将对象聚为十几个 由于算法使用多类合并规则，因此会有个别类个 类，则丧失了聚类的意义，因此本文认为该波动在实际 数不存在的情况，文中以”表示.对于Soybean和 应用中可以利用人的经验有效地避免 Balloon数据集聚类数上限范围以外非实验内容的情 综上所述，在人为理性的参数值设定下，不同的聚 况，表中以“”表示（下同）： 类数上限参数值对HABOS算法的聚类结果准确率影 从表3中可以看出，对于Voting数据集，聚类数上 响不大，该算法在大部分情况下能够得到聚类效果最 限参数nc的取值变化对聚类结果的影响很小，聚类 好的层次结果.HABOS算法虽然需要人为地输入 结果的准确率没有变化，均选择了效果最好的层次结 nc参数值，但是集合稀疏差异度上限参数对聚类结 果.对于Soybean数据集，当聚类数上限参数取值为2 果的敏感性要远远大于参数ncmm对结果的影响，因此 或3时，将实际最佳聚类个数4排除在外，因此聚类效 HABOS算法对参数ncm较不敏感. 果不佳.但是，当聚类数上限参数值大于等于4时，算 表4为HABOS算法、CABOSFV_C算法与经典K- 法均选择了聚类效果最好的层次，即聚类个数为4的 modes算法基于三个数据集的聚类结果准确率比较. 表3类个数上限参数对聚类结果准确率的影响 表4聚类结果准确率比较 Table 3 Influence of the upper limit parameter of cluster number on the Table 4 Comparison of the accuracy of clustering results accuracy of clustering results Voting数据集 Soybean数据集 Balloon数据集 HABOS CABOSFV_C K-modes 数据集 正确率/% 正确率/% 正确率/% 平均准确率/% 平均准确率/% 平均准确率/% 57.4 100.0 Voting 93.80 81.10 86.60 78.7 100.0 Soybean 100 89.30 80.10 100.0 100.0 Balloon 100 64.60 69.30 5 100.0 100.0 93.8 100.0 100.0 4 结论 7 93.8 100.0 100.0 本文针对CABOSFV._C算法对集合稀疏差异度上 8 93.8 100.0 100.0 限参数具有一定依赖性，从聚结型层次聚类思想的角 9 93.8 100.0 100.0 度出发，结合CVISFD内部评价指标，提出改进算法 10 93.8 100.0 100.0 HABOS.算法首先通过计算任意两个类合并后的集合 11 93.8 100.0 100.0 稀疏差异度，根据多类合并规则将得到集合稀疏差异 12 度最小的类进行合并，然后继续根据多类合并规则将 93.8 100.0 100.0 取得最小集合稀疏差异度的类进行合并，直至所有类 13 93.8 100.0 45.0 被合并成一个类或不能再合并为止.算法还需人为地 14 93.8 100.0 45.0 给定聚类数上限参数ncax,对于聚类个数小于ncmx的 15 93.8 100.0 45.0 层次结果，利用CVISFD评价方法进行启发式度量，自 16 93.8 100.0 动地选择聚类效果最优的结果.该算法可以有效地消 17 93.8 100.0 除集合稀疏差异度上限对聚类结果的影响，从全局角 18 93.8 100.0 度选择最合适的类进行合并 19 93.8 100.0 真实数据实验结果表明：新的内部评价指标 20 93.8 100.0 CVISFD能够较好地进行启发式度量，选择HABOS算 23 法在聚类数上限约束下所能达到的最好聚类结果： 93.8 24 938 HABOS算法的聚类结果对聚类数上限参数nc的敏 感性较低，该参数的选取对聚类结果的影响较小： 25 93.8 HABOS算法在三个数据集上的聚类结果准确率高于 27 93.8 CABOSFV._C算法和经典K-modes算法，且HABOS算 28 93.8 法聚类结果的稳定性也高于其他对比算法

武 森等: 分类属性数据聚类算法 HABOS 次取得较好的准确率． 本文认为该结果较好主要归功 于 HABOS 算法的聚类过程，而 CVISFD 指标对该数据 集的聚类有着较小的贡献，所以 CVISFD 指标并不是 针对所有数据集都有绝对的指导意义． 由于算法使用多类合并规则，因此会有个别类个 数不存在的情况，文中以“—”表示． 对于 Soybean 和 Balloon 数据集聚类数上限范围以外非实验内容的情 况，表中以“/”表示( 下同) ． 从表 3 中可以看出，对于 Voting 数据集，聚类数上 限参数 ncmax的取值变化对聚类结果的影响很小，聚类 结果的准确率没有变化，均选择了效果最好的层次结 果． 对于 Soybean 数据集，当聚类数上限参数取值为 2 或 3 时，将实际最佳聚类个数 4 排除在外，因此聚类效 果不佳． 但是，当聚类数上限参数值大于等于 4 时，算 法均选择了聚类效果最好的层次，即聚类个数为4的 表 3 类个数上限参数对聚类结果准确率的影响 Table 3 Influence of the upper limit parameter of cluster number on the accuracy of clustering results ncmax Voting 数据集 正确率/% Soybean 数据集 正确率/% Balloon 数据集 正确率/% 2 — 57. 4 100. 0 3 — 78. 7 100. 0 4 — 100. 0 100. 0 5 — 100. 0 100. 0 6 93. 8 100. 0 100. 0 7 93. 8 100. 0 100. 0 8 93. 8 100. 0 100. 0 9 93. 8 100. 0 100. 0 10 93. 8 100. 0 100. 0 11 93. 8 100. 0 100. 0 12 93. 8 100. 0 100. 0 13 93. 8 100. 0 45. 0 14 93. 8 100. 0 45. 0 15 93. 8 100. 0 45. 0 16 93. 8 100. 0 ∕ 17 93. 8 100. 0 ∕ 18 93. 8 100. 0 ∕ 19 93. 8 100. 0 ∕ 20 93. 8 100. 0 ∕ 23 93. 8 ∕ ∕ 24 93. 8 ∕ ∕ 25 93. 8 ∕ ∕ 27 93. 8 ∕ ∕ 28 93. 8 ∕ ∕ 情况． 对于 Balloon 数据集，当聚类数上限参数值小于 等于12 时，算法均取得了最好准确率100. 0% ，当聚类 数上限参数值大于 12 时，准确率有了较大的波动，但 由于该数据集对象个数仅为 20，若将对象聚为十几个 类，则丧失了聚类的意义，因此本文认为该波动在实际 应用中可以利用人的经验有效地避免． 综上所述，在人为理性的参数值设定下，不同的聚 类数上限参数值对 HABOS 算法的聚类结果准确率影 响不大，该算法在大部分情况下能够得到聚类效果最 好的 层 次 结 果． HABOS 算法虽然需要人为地输入 ncmax参数值，但是集合稀疏差异度上限参数对聚类结 果的敏感性要远远大于参数 ncmax对结果的影响，因此 HABOS 算法对参数 ncmax较不敏感． 表 4 为 HABOS 算法、CABOSFV_C 算法与经典 K￾modes 算法基于三个数据集的聚类结果准确率比较． 表 4 聚类结果准确率比较 Table 4 Comparison of the accuracy of clustering results 数据集 HABOS 平均准确率/% CABOSFV_C 平均准确率/% K--modes 平均准确率/% Voting 93. 80 81. 10 86. 60 Soybean 100 89. 30 80. 10 Balloon 100 64. 60 69. 30 4 结论 本文针对 CABOSFV_C 算法对集合稀疏差异度上 限参数具有一定依赖性，从聚结型层次聚类思想的角 度出发，结合 CVISFD 内部评价指标，提出改进算法 HABOS． 算法首先通过计算任意两个类合并后的集合 稀疏差异度，根据多类合并规则将得到集合稀疏差异 度最小的类进行合并，然后继续根据多类合并规则将 取得最小集合稀疏差异度的类进行合并，直至所有类 被合并成一个类或不能再合并为止． 算法还需人为地 给定聚类数上限参数 ncmax，对于聚类个数小于 ncmax的 层次结果，利用 CVISFD 评价方法进行启发式度量，自 动地选择聚类效果最优的结果． 该算法可以有效地消 除集合稀疏差异度上限对聚类结果的影响，从全局角 度选择最合适的类进行合并． 真实数据实验结果表明: 新 的 内 部 评 价 指 标 CVISFD 能够较好地进行启发式度量，选择 HABOS 算 法在聚类数上限约束下所能达到的最好聚类结果; HABOS 算法的聚类结果对聚类数上限参数 ncmax的敏 感性较 低，该 参 数 的 选 取 对 聚 类 结 果 的 影 响 较 小; HABOS 算法在三个数据集上的聚类结果准确率高于 CABOSFV_C 算法和经典 K-modes 算法，且 HABOS 算 法聚类结果的稳定性也高于其他对比算法． · 3201 ·

·1024· 工程科学学报，第38卷，第7期 参考文献 ring for privacy preservation in cloud DB querying.Procedia Comput Sci,2015.50:363 [Han J W,Kamber M,Pei J.Data Mining:Concepts and Tech- [8]Zhou K L,Yang S L.Ding S,et al.On cluster validation.Syst niques.3rd Ed.San Francisco:Morgan Kaufmann Publishers, Eng Theory Pract,2014,34(9):2417 2011 (周开乐，杨善林，丁帅，等.聚类有效性研究综述.系统工 Baughman A K,Gao J.Pan J Y,et al.Multimedia Data Mining 程理论与实践，2014,34(9)：2417) and Analytics.Springer Intemational Publishing,2015 Granichin 0,Volkovich Z,Toledano-Kitai D.Randomised Algo- B]Verma M,Srivastava M,Chack N,et al.A comparative study of rithms in Automatic Control and Data Mining.New York:Spring- various clustering algorithms in data mining.Int J Eng Res Appl, er Berlin Heidelberg,2014 2014,2(3):1379 [10]Cui H Y,Xie M Z,Cai Y L,et al.Cluster validity index for 4]Kushwah S PS,Rawat K,Gupta P.Analysis and comparison of adaptive clustering algorithms.IET Commun,2014,8(13): efficient techniques of clustering algorithms in data mining.Int 2256 Innovative Technol Explor Eng,2012,1(3):2278 [11]Maulik U,Bandyopadhyay S.Performance evaluation of some [5]Wu S,Wei G Y.High dimensional data clustering algorithm clustering algorithms and validity indices.IEEE Trans Pattern based on sparse feature vector for categorical attributes //2010 In- Anal Mach Intell,2002,24(12):1650 ternational Conference on Logistics Systems and Intelligent Manage- [12]Kim M,Ramakrishna R S.New indices for cluster validity as- ment.Harbin,2010,2:973 sessment.Pattern Recognit Lett,2005,26(15):2353 6]Bishnu PS,Bhattacherjee V.A modified K-Modes clustering al- [13]Ahmad A,Dey L A k-mean clustering algorithm for mixed nu- gorithm.Lect Notes Comput Sci,2013,8251:60 meric and categorical data.Data Knowl Eng,2007,63 (2): Mulani N,Pawar A,Mulay P,et al.Variant of COBWEB cluste- 503

工程科学学报，第 38 卷，第 7 期 参 考 文 献 ［1］ Han J W，Kamber M，Pei J． Data Mining: Concepts and Tech￾niques． 3rd Ed． San Francisco: Morgan Kaufmann Publishers， 2011 ［2］ Baughman A K，Gao J，Pan J Y，et al． Multimedia Data Mining and Analytics． Springer International Publishing，2015 ［3］ Verma M，Srivastava M，Chack N，et al． A comparative study of various clustering algorithms in data mining． Int J Eng Ｒes Appl， 2014，2( 3) : 1379 ［4］ Kushwah S P S，Ｒawat K，Gupta P． Analysis and comparison of efficient techniques of clustering algorithms in data mining． Int J Innovative Technol Explor Eng，2012，1( 3) : 2278 ［5］ Wu S，Wei G Y． High dimensional data clustering algorithm based on sparse feature vector for categorical attributes / / 2010 In￾ternational Conference on Logistics Systems and Intelligent Manage￾ment． Harbin，2010，2: 973 ［6］ Bishnu P S，Bhattacherjee V． A modified K-Modes clustering al￾gorithm． Lect Notes Comput Sci，2013，8251: 60 ［7］ Mulani N，Pawar A，Mulay P，et al． Variant of COBWEB cluste￾ring for privacy preservation in cloud DB querying． Procedia Comput Sci，2015，50: 363 ［8］ Zhou K L，Yang S L，Ding S，et al． On cluster validation． Syst Eng Theory Pract，2014，34( 9) : 2417 ( 周开乐，杨善林，丁帅，等． 聚类有效性研究综述． 系统工 程理论与实践，2014，34( 9) : 2417) ［9］ Granichin O，Volkovich Z，Toledano-Kitai D． Ｒandomized Algo￾rithms in Automatic Control and Data Mining． New York: Spring￾er Berlin Heidelberg，2014 ［10］ Cui H Y，Xie M Z，Cai Y L，et al． Cluster validity index for adaptive clustering algorithms． IET Commun，2014，8 ( 13 ) : 2256 ［11］ Maulik U，Bandyopadhyay S． Performance evaluation of some clustering algorithms and validity indices． IEEE Trans Pattern Anal Mach Intell，2002，24( 12) : 1650 ［12］ Kim M，Ｒamakrishna Ｒ S． New indices for cluster validity as￾sessment． Pattern Ｒecognit Lett，2005，26( 15) : 2353 ［13］ Ahmad A，Dey L． A k-mean clustering algorithm for mixed nu￾meric and categorical data． Data Knowl Eng，2007，63 ( 2 ) : 503 · 4201 ·