·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 ·