正在加载图片...
第8期 武森等：分类属性高维数据基于集合差异度的聚类算法 .1087. 个已经创建的类，仅保留集合精简表示，而不必保留 进行并入后集合精简表示的计算以完成聚类过程， 每个对象的信息，算法具体步骤如下所述 因此，算法的计算时间复杂度是0(k),在实际数 输入：数据表(XAV,6(IX|=n为对象数 据挖掘应用中，一般k远小于n可以认为CABOSD 目)：集合差异度上限b 的计算时间复杂度是接近线性的 输出：类C,C2,…,C,k预先未知. 该算法定义的集合差异度反映了一个集合内所 步骤1C={a; 有对象间的总体差异程度，在一次数据扫描的过程 步骤2计算SR(CU{): 中，算法总是将扫描到的当前对象并入满足阈值的 如果SD(CU{})≤b 要求且使得并入后集合差异度最小的类中，使得每 {C=,e: 个集合内的所有对象间的总体差异程度尽可能的 类的数目k=1 小，即每个集合内的所有对象间尽可能的相似，从而 否则， 达到聚类的目的. 创建新类C2={e 类的数目k=2:{ 3算法实例 步骤3.=3， 采用UCI中的soybean(mall)数据集进行CA- 步骤4：6=1t=2计算SR(CU{x}): BOSD算法检验，soybean(mall)数据集被广泛用于 步骤5计算SR(CU{x}): 聚类算法的有效性检验，其中共有47个对象、35个 步骤6，如果SD(CU{x)≤sD(CUx) 属性，各属性的值都统一用从“0”开始的数字符号 6=【 表示，有14个属性在各对象中取值都相同，所有对 步骤7：如果k 象分为四类，每一类对应一种黄豆作物病害。将该 {=t+1 数据集中的47个对象随机排序，在仅考虑各对象取值 转步骤5} 不全相同的21个属性的情况下，聚类结果见表1与 步骤8如果SD(CU1x{)≤b soybean(mall数据集中类的归属完全一致.为具体说 ICo=CU x 明CAB0SD的特点，表2和表3进一步针对随机排序 否则， 后的前六个对象给出了完整数据表及聚类过程 创建新类C+1={x; 表3中(*)表示：如果将当前扫描到的对象并 类的数目k=k十1：} 入已经创建的各类，集合差异度最小的情况，如果 步骤9.如果n 其大于b则创建新类，仅包含当前对象；否则，将当 }=计1 前对象并入使得并入后集合差异度最小的类中，根 转步骤4} 据该聚类过程可知，CABOSD仅需一次数据扫描，每 步骤10.C,=1,2…,k为最终聚类结果 个扫描到的对象至多与k个类进行并入后集合精简 从上述计算步骤可知：CABOSD对n个对象仅 表示的计算以完成聚类过程.这与算法的计算时间 需一次数据扫描，扫描到的每个对象至多与k个类 复杂度0(nk)是一致的 表1应用CAB0SD进行聚类的结果(b=Q450) Table 1 Chstering result by CABOSD (b=0.450) 集合精简表示 聚类结果 lYI EAV(Y) SD(Y) (20)(32),(41)(121)(21.3),(231)(24,1) C1=g,Xg,6,为gq:,9,90 Q237 (250),(260)(27,0),(280),(350) (20),(30),(81)(121),(21.0),(223)(230) C2=为83,02，刘7,91456,9 10 0195 (240),(250),(262),(27,1),(280)(35,0) C3=2,9,5,g7,,3,g1,80e4,s} 9 1(32),(40),(71)(21,1)(221)(230) Q348 (241)(260)(27,0),(283)1 C4=x0,47,831,X43,87,X45886 17 1(21)(121)(222),(230)(250),(26,0), 0323 X2X的？X40?1345X2X4} (27,0)(283)(35,1)}第 8期 武 森等： 分类属性高维数据基于集合差异度的聚类算法 个已经创建的类仅保留集合精简表示而不必保留 每个对象的信息．算法具体步骤如下所述． 输入：数据表〈ＸＡＶｆ〉（｜Ｘ｜＝ｎ为对象数 目 ）；集合差异度上限 ｂ． 输出：类 Ｃ1Ｃ2…Ｃｋｋ预先未知． 步骤 1：Ｃ1＝｛ｘ1｝； 步骤 2：计算 ＳＲ（Ｃ1∪｛ｘ2｝）； 如果 ＳＤ（Ｃ1∪｛ｘ2｝）≤ｂ ｛Ｃ1＝｛ｘ1ｘ2｝； 类的数目 ｋ＝1；｝ 否则 ｛创建新类 Ｃ2＝｛ｘ2｝； 类的数目 ｋ＝2；｝ 步骤 3：ｉ＝3； 步骤 4：ｔ0＝1ｔ＝2计算 ＳＲ（Ｃｔ0∪｛ｘｉ｝）； 步骤 5：计算 ＳＲ（Ｃｔ∪｛ｘｉ｝）； 步骤 6：如果 ＳＤ（Ｃｔ∪｛ｘｉ｝）≤ＳＤ（Ｃｔ0∪｛ｘｉ｝） ｔ0＝ｔ； 步骤 7：如果 ｔ＜ｋ ｛ｔ＝ｔ＋1； 转步骤 5；｝ 步骤 8：如果 ＳＤ（Ｃｔ0∪｛ｘｉ｝）≤ｂ ｛Ｃｔ0 ＝Ｃｔ0∪｛ｘｉ｝；｝ 否则 ｛创建新类 Ｃｋ＋1＝｛ｘｉ｝； 类的数目 ｋ＝ｋ＋1；｝ 步骤 9：如果 ｉ＜ｎ ｛ｉ＝ｉ＋1； 转步骤 4；｝ 步骤 10：Ｃｔｔ＝12…ｋ为最终聚类结果． 从上述计算步骤可知：ＣＡＢＯＳＤ对 ｎ个对象仅 需一次数据扫描扫描到的每个对象至多与 ｋ个类 进行并入后集合精简表示的计算以完成聚类过程． 因此算法的计算时间复杂度是 Ｏ（ｎｋ）．在实际数 据挖掘应用中一般 ｋ远小于 ｎ可以认为 ＣＡＢＯＳＤ 的计算时间复杂度是接近线性的． 该算法定义的集合差异度反映了一个集合内所 有对象间的总体差异程度．在一次数据扫描的过程 中算法总是将扫描到的当前对象并入满足阈值的 要求且使得并入后集合差异度最小的类中使得每 个集合内的所有对象间的总体差异程度尽可能的 小即每个集合内的所有对象间尽可能的相似从而 达到聚类的目的． 3 算法实例 采用 ＵＣＩ中的 ｓｏｙｂｅａｎ（ｓｍａｌｌ）数据集进行 ＣＡ- ＢＯＳＤ算法检验．ｓｏｙｂｅａｎ（ｓｍａｌｌ）数据集被广泛用于 聚类算法的有效性检验其中共有 47个对象、35个 属性各属性的值都统一用从 “0”开始的数字符号 表示有 14个属性在各对象中取值都相同．所有对 象分为四类每一类对应一种黄豆作物病害．将该 数据集中的47个对象随机排序在仅考虑各对象取值 不全相同的 21个属性的情况下聚类结果见表 1与 ｓｏｙｂｅａｎ（ｓｍａｌｌ）数据集中类的归属完全一致．为具体说 明 ＣＡＢＯＳＤ的特点表 2和表 3进一步针对随机排序 后的前六个对象给出了完整数据表及聚类过程． 表 3中 （∗ ）表示：如果将当前扫描到的对象并 入已经创建的各类集合差异度最小的情况．如果 其大于 ｂ则创建新类仅包含当前对象；否则将当 前对象并入使得并入后集合差异度最小的类中．根 据该聚类过程可知ＣＡＢＯＳＤ仅需一次数据扫描每 个扫描到的对象至多与 ｋ个类进行并入后集合精简 表示的计算以完成聚类过程．这与算法的计算时间 复杂度 Ｏ（ｎｋ）是一致的． 表 1 应用 ＣＡＢＯＳＤ进行聚类的结果 （ｂ＝0．450） Ｔａｂｌｅ1 ＣｌｕｓｔｅｒｉｎｇｒｅｓｕｌｔｂｙＣＡＢＯＳＤ （ｂ＝0．450） 聚类结果 集合精简表示 ｜Ｙ｜ ＥＡＶ（Ｙ） ＳＤ（Ｙ） Ｃ1＝｛ｘ8ｘ9ｘ3ｘ6ｘ5ｘ2ｘ1ｘ4ｘ7ｘ10｝ 10 ｛（20）（32）（41）（121）（213）（231）（241） （250）（260）（270）（280）（350）｝ 0．237 Ｃ2＝｛ｘ18ｘ13ｘ20ｘ12ｘ17ｘ14ｘ11ｘ15ｘ16ｘ19｝ 10 ｛（20）（30）（81）（121）（210）（223）（230） （240）（250）（262）（271）（280）（350）｝ 0．195 Ｃ3＝｛ｘ22ｘ29ｘ25ｘ27ｘ28ｘ23ｘ21ｘ30ｘ24ｘ26｝ 10 ｛（32）（40）（71）（211）（221）（230） （241）（260）（270）（283）｝ 0．348 Ｃ4＝｛ｘ36ｘ47ｘ33ｘ41ｘ43ｘ37ｘ45ｘ38ｘ46 ｘ32ｘ39ｘ40ｘ31ｘ34ｘ35ｘ42ｘ44｝ 17 ｛（21）（121）（222）（230）（250）（260） （270）（283）（351）｝ 0．323 ·1087·