分类属性数据聚类算法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),即CVISFD<CVISFD;,仅对类2来 为分类变量，其划分为X={X,X2,…,X},共有n个 说，图1(b)中的聚类结果优于图1(a). 类划分，计算任意两个集合合并后的集合稀疏差异度 图1(c)中类2的类间距离变为对象x和对象z之 SD(X,UX),ij=1,2,…,n,i≠j,得到最小集合稀疏 间的集合稀疏差异度Sep=SFDa,较图1(a)中类2的 差异度SD,将得到最小集合稀疏差异度SFDn的 类间差异度有所增加，即Sep>Sep?,因此图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 ·