正在加载图片...
,1088, 北京科技大学学报 第32卷 表2随机排序的前六个对象数据表 Table 2 Data table of the first six objects of the randam sequence 序号对象a郎 a5a6asa胸a10a12a2021 22324a25a26272835 1 302 1 0 0 2 1 2 1 0 3 0 1 1 0 0000 8 5 0 0 2 1 2 2 0 2 1 0 3 0 0 0 2 1 0 0 3 322 2 2 0 0 3 1 2 0 1 0 0 0 0 3 0 2 1 0 0 0 0 0 0 3 1 5 X47 0 2 0 0 0 0 3 1 6 02 0 0 0 0 0 0 表3应用CAB0S③D进行聚类的过程(b=Q450) Table 3 Chustering pmocess by CABOSD (b=Q 450) 序号 扫描 对象 lyI lEAV(Y)I SD(Y)=2-EAV()L X lEAV(Y)I 新类的创建及对象到类的归并 1 1x 新类C1=g{ 2 CiU Ixs 2 6 1768>b(%) 新类C2=s CU Ix21 2 9 Q943>b(*) 3 C2U Ixz2 新类Cs=2{ 2 4 3005 CiU Ixoos1 2 10 0778 CaU xos1 2 4 3005 新类C,={肠{ CaU xos1 2 12 0530>b(%) GU{x！ 2 9 0943 C=CU Ix7 I=1x6.x7: CaU 1x7 2 1.414 sR(C4)=(21(21)(32),(41),(50).(7,1) 7 CaU Ix7I 2 13 0435 (121),(200),(222),(230),(240),(25,0), CaU Ix7 2 15 0283≤b(*) (26,0),(27,0),(283),(35,1),0283) CUx 2 16 022≤b(%) CI=GU Ix1=1: C2Uo1 2 6 1.768 sR(C)=(21(20),(32)(4,1)(50),(7,0,(91) CU1}2 11 0643 (121),(20,0),(21,3),(231,(24,1),(250), CaUx 3 8 0938 (260),(27,0),(280),(35,0).0221) 进行20次对象随机排序的聚类实验，每次实验 着b的逐渐增加，会使类的数目减少而类内的对象 都调整阈值b使得聚类达到最佳效果，在考虑各对 数目增加，因此通过b可以调整类的规模和大小. 象取值不全相同的21个属性和全部35个属性的情 CABOSD的聚类结果还受数据输入顺序的影响，在 况下，聚类平均正确率分别是94.89%和96.91%. 数据输入顺序不同的情况下，聚类结果趋同，但不一 其中，正确率定义为正确聚类的对象数占全部对象 定完全一致， 数的比率山 参考文献 4结论 [1]Han JW,KaberM.Data M ining Concepts and Techniues Bei 高维数据聚类一直是数据挖掘领域研究的难点 jing China Machine Press 2006 [2]Yang B Li D Y.Lu JM.etal Complex network clustering al 和重，点之一，本文提出的CABOSD针对分类属性高 gorithms J Sofwam 2009 20(1):54 维数据，通过定义的集合差异度和集合精简表示对 (杨博，刘大有，LmJM,等.复杂网络聚类方法.软件学报， 数据进行高度压缩，不损失聚类所需信息，保证了计 200A20(1):54) 算的精确性·在聚类过程中，不需计算两两对象间 [3]Carvaho LE Law rence C E Centroi estination n diserete high 的距离，根据集合差异度直接完成新类的创建及对 dinensional spaces w ith applications in bolgy Pmcdings of the National Academy of Sciences of the United States of America 象到类的归并，仅需一次数据扫描，计算时间复杂度 2008105(9):3209 接近线性，CABOSD的聚类结果受阈值b影响，随 [4]Guha S RastogiR.Shin K.ROCK:a mobust clstering algorithm北 京 科 技 大 学 学 报 第 32卷 表 2 随机排序的前六个对象数据表 Ｔａｂｌｅ2 Ｄａｔａｔａｂｌｅｏｆｔｈｅｆｉｒｓｔｓｉｘｏｂｊｅｃｔｓｏｆｔｈｅｒａｎｄｏｍｓｅｑｕｅｎｃｅ 序号 对象 ａ1 ａ2 ａ3 ａ4 ａ5 ａ6 ａ7 ａ8 ａ9 ａ10 ａ12 ａ20 ａ21 ａ22 ａ23 ａ24 ａ25 ａ26 ａ27 ａ28 ａ35 1 ｘ8 3 0 2 1 0 1 0 2 1 2 1 0 3 0 1 1 0 0 0 0 0 2 ｘ18 5 0 0 2 1 2 2 1 0 2 1 1 0 3 0 0 0 2 1 0 0 3 ｘ22 2 1 2 0 0 3 1 2 0 1 0 0 1 1 0 1 0 0 0 3 0 4 ｘ36 1 1 2 1 0 0 1 2 1 1 1 0 2 2 0 0 0 0 0 3 1 5 ｘ47 0 1 2 1 0 3 1 1 0 2 1 0 1 2 0 0 0 0 0 3 1 6 ｘ9 6 0 2 1 0 3 0 1 1 1 1 0 3 1 1 1 0 0 0 0 0 表 3 应用 ＣＡＢＯＳＤ进行聚类的过程 （ｂ＝0．450） Ｔａｂｌｅ3 ＣｌｕｓｔｅｒｉｎｇｐｒｏｃｅｓｓｂｙＣＡＢＯＳＤ （ｂ＝0．450） 序号 扫描 对象 Ｙ ｜Ｙ｜ ｜ＥＡＶ（Ｙ）｜ ＳＤ（Ｙ）＝ 21—｜ＥＡＶ（Ｙ）｜ ｜Ｙ｜×｜ＥＡＶ（Ｙ）｜ 新类的创建及对象到类的归并 1 ｘ8 ｛ｘ8｝ — — — 新类 Ｃ1＝｛ｘ8｝ 2 ｘ18 Ｃ1∪｛ｘ18｝ 2 6 1．768＞ｂ（∗ ） 新类 Ｃ2＝｛ｘ18｝ 3 ｘ22 Ｃ1∪｛ｘ22｝ 2 9 0．943＞ｂ（∗ ） 新类 Ｃ3＝｛ｘ22｝ Ｃ2∪｛ｘ22｝ 2 4 3．005 Ｃ1∪｛ｘ36｝ 2 10 0．778 4 ｘ36 Ｃ2∪｛ｘ36｝ 2 4 3．005 新类 Ｃ4＝｛ｘ36｝ Ｃ3∪｛ｘ36｝ 2 12 0．530＞ｂ（∗ ） 5 ｘ47 Ｃ1∪｛ｘ47｝ 2 9 0．943 Ｃ2∪｛ｘ47｝ 2 7 1．414 Ｃ3∪｛ｘ47｝ 2 13 0．435 Ｃ4∪｛ｘ47｝ 2 15 0．283≤ｂ（∗ ） Ｃ4＝Ｃ4∪｛ｘ47｝＝｛ｘ36ｘ47｝； ＳＲ（Ｃ4）＝（2｛（21）（32）（41）（50）（71） （121）（200）（222）（230）（240）（250） （260）（270）（283）（351）｝0．283） 6 ｘ9 Ｃ1∪｛ｘ9｝ 2 16 0．221≤ｂ（∗ ） Ｃ2∪｛ｘ9｝ 2 6 1．768 Ｃ3∪｛ｘ9｝ 2 11 0．643 Ｃ4∪｛ｘ9｝ 3 8 0．938 Ｃ1＝Ｃ1∪｛ｘ9｝＝｛ｘ8ｘ9｝； ＳＲ（Ｃ1）＝（2｛（20）（32）（41）（50）（70）（91） （121）（200）（213）（231）（241）（250） （260）（270）（280）（350）｝0．221） 进行 20次对象随机排序的聚类实验每次实验 都调整阈值 ｂ使得聚类达到最佳效果．在考虑各对 象取值不全相同的 21个属性和全部 35个属性的情 况下聚类平均正确率分别是 94∙89％和 96∙91％． 其中正确率定义为正确聚类的对象数占全部对象 数的比率 ［11］． 4 结论 高维数据聚类一直是数据挖掘领域研究的难点 和重点之一．本文提出的 ＣＡＢＯＳＤ针对分类属性高 维数据通过定义的集合差异度和集合精简表示对 数据进行高度压缩不损失聚类所需信息保证了计 算的精确性．在聚类过程中不需计算两两对象间 的距离根据集合差异度直接完成新类的创建及对 象到类的归并仅需一次数据扫描计算时间复杂度 接近线性．ＣＡＢＯＳＤ的聚类结果受阈值 ｂ影响随 着 ｂ的逐渐增加会使类的数目减少而类内的对象 数目增加因此通过 ｂ可以调整类的规模和大小． ＣＡＢＯＳＤ的聚类结果还受数据输入顺序的影响在 数据输入顺序不同的情况下聚类结果趋同但不一 定完全一致． 参 考 文 献 ［1］ ＨａｎＪＷＫａｍｂｅｒＭ．ＤａｔａＭｉｎｉｎｇＣｏｎｃｅｐｔｓａｎｄＴｅｃｈｎｉｑｕｅｓ．Ｂｅｉ- ｊｉｎｇ：ＣｈｉｎａＭａｃｈｉｎｅＰｒｅｓｓ2006 ［2］ ＹａｎｇＢＬｉｕＤＹＬｉｕＪＭｅｔａｌ．Ｃｏｍｐｌｅｘｎｅｔｗｏｒｋｃｌｕｓｔｅｒｉｎｇａｌ- ｇｏｒｉｔｈｍｓ．ＪＳｏｆｔｗａｒｅ200920（1）：54 （杨博刘大有ＬｉｕＪＭ等．复杂网络聚类方法．软件学报 200920（1）：54） ［3］ ＣａｒｖａｌｈｏＬＥＬａｗｒｅｎｃｅＣＥ．Ｃｅｎｔｒｏｉｄｅｓｔｉｍａｔｉｏｎｉｎｄｉｓｃｒｅｔｅｈｉｇｈ- ｄｉｍｅｎｓｉｏｎａｌｓｐａｃｅｓｗｉｔｈａｐｐｌｉｃａｔｉｏｎｓｉｎｂｉｏｌｏｇｙ∥Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ ＮａｔｉｏｎａｌＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓｏｆｔｈｅＵｎｉｔｅｄＳｔａｔｅｓｏｆＡｍｅｒｉｃａ 2008105（9）：3209 ［4］ ＧｕｈａＳＲａｓｔｏｇｉＲＳｈｉｍＫ．ＲＯＣＫ：ａｒｏｂｕｓｔｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ ·1088·