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