D01:10.13374/i.issn1001t63x.2010.08.045 第32卷第8期 北京科技大学学报 Vol 32 No 8 2010年8月 Journal of Un iversity of Science and Technology Beijing Aug 2010 分类属性高维数据基于集合差异度的聚类算法 武森魏桂英白尘张桂琼 北京科技大学经济管理学院，北京100083 摘要提出基于集合差异度的聚类算法·算法通过定义的集合差异度和集合精简表示，直接进行一个集合内所有对象总体 差异程度的计算，而不必计算两两对象间的距离，并且在不影响计算精确度的情况下对分类属性高维数据进行高度压缩，只 需一次数据扫描即得到聚类结果·算法计算时间复杂度接近线性·实例表明该算法是有效的· 关键词聚类：高维空间：集合；差异度：数据挖掘 分类号P311 C lustering algorithm based on set dissi ilarity for high di ensionaldata of cate- gorical attr ibu tes WU Sen WEIGuiying BAI Chen ZHANG Gui-qiong School of Econan ics and Managament University of Seience and Technolgy Beijing Beijing 100083 China ABSTRACT A custering algorithm is proposed based on set dissi ilarity Through defining set dissi ilarity and set reduction it does not calculate the distance between each pair of objects but camputes the general dissi ilarity of all the objects in a set directly re- duces highdmensional categorical data enomously without lss of computation accuracy and gets the clustering result by only once data scanning The tine complexity of the algorithm is amost linear An example of real data shows that the clustering algorithm is effec- tive KEY W ORDS clustering high dinensional space sets dissin ilarity data m ining 高维数据聚类一直是数据挖掘山、复杂网络分 据集.信息瓶颈方法基于互信息采用聚结型聚类 析和生物信息学)等领域具有挑战性的研究课 策略，成功地应用于文档聚类中，该算法的计算时间 题之一，传统的聚类算法主要是针对连续属性低维 复杂度为0(m)同样不适用于处理大数据集[)， 数据提出的，并不适用于高维数据的情况，而且，由 COOLCAT算法[1基于熵进行分类属性数据聚类； 于连续属性的差异度计算方法不适用于分类属性， LMBO算法[)采用信息瓶颈框架来度量分类属性 基于分类属性的高维数据聚类就更加困难 元组的距离，同时还给出了分类属性值的距离计算 近十年来，分类属性高维数据聚类得到研究者 方法，既可以对元组聚类，也可以对属性值聚类；P 的广泛关注，并取得了许多成果，但算法的计算时间 SUB算法[⑧将分类属性高维数据聚类问题转化为 复杂度普遍较高，且一般需要两次或更多次数据扫 最大频繁项集（即聚类子空间）挖掘问题，然后再进 描、ROCK算法针对传统的聚类算法主要适用于 行子空间聚类，FPSUB算法的计算效率优于COOL~ 连续属性的情况，提出了适用于分类属性的链来度 CAT和LMBO],但子空间聚类没有从根本上解决 量数据对象之间的相似度，并进一步提出了聚结型 计算时间复杂度较高的问题，且FPSUB算法同 层次聚类算法，但计算时间复杂度超过了 COOLCAT和LMBO一样仍然需要两次数据扫描. 0(nogn),其中n是对象数目，不适用于处理大数 CABOSFV算法[)针对特定的分类属性一二值属 收稿日期：2010-01-18 基金项目：国家自然科学基金资助项目(N。70771007) 作者简介：武森(l97-),女，教授，博士，E maik wuser@manage ustb edu cn第 32卷 第 8期 2010年 8月 北 京 科 技 大 学 学 报 ＪｏｕｒｎａｌｏｆＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＢｅｉｊｉｎｇ Ｖｏｌ．32Ｎｏ．8 Ａｕｇ．2010 分类属性高维数据基于集合差异度的聚类算法 武 森 魏桂英 白 尘 张桂琼 北京科技大学经济管理学院‚北京 100083 摘 要 提出基于集合差异度的聚类算法．算法通过定义的集合差异度和集合精简表示‚直接进行一个集合内所有对象总体 差异程度的计算‚而不必计算两两对象间的距离‚并且在不影响计算精确度的情况下对分类属性高维数据进行高度压缩‚只 需一次数据扫描即得到聚类结果．算法计算时间复杂度接近线性．实例表明该算法是有效的． 关键词 聚类；高维空间；集合；差异度；数据挖掘 分类号 ＴＰ311 Ｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｓｅｔｄｉｓｓｉｍｉｌａｒｉｔｙｆｏｒｈｉｇｈｄｉｍｅｎｓｉｏｎａｌｄａｔａｏｆｃａｔｅ- ｇｏｒｉｃａｌａｔｔｒｉｂｕｔｅｓ ＷＵＳｅｎ‚ＷＥＩＧｕｉ-ｙｉｎｇ‚ＢＡＩＣｈｅｎ‚ＺＨＡＮＧＧｕｉ-ｑｉｏｎｇ ＳｃｈｏｏｌｏｆＥｃｏｎｏｍｉｃｓａｎｄＭａｎａｇｅｍｅｎｔ‚ＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＢｅｉｊｉｎｇ‚Ｂｅｉｊｉｎｇ100083‚Ｃｈｉｎａ ＡＢＳＴＲＡＣＴ Ａｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄｂａｓｅｄｏｎｓｅｔｄｉｓｓｉｍｉｌａｒｉｔｙ．Ｔｈｒｏｕｇｈｄｅｆｉｎｉｎｇｓｅｔｄｉｓｓｉｍｉｌａｒｉｔｙａｎｄｓｅｔｒｅｄｕｃｔｉｏｎ‚ｉｔ ｄｏｅｓｎｏｔｃａｌｃｕｌａｔｅｔｈｅｄｉｓｔａｎｃｅｂｅｔｗｅｅｎｅａｃｈｐａｉｒｏｆｏｂｊｅｃｔｓｂｕｔｃｏｍｐｕｔｅｓｔｈｅｇｅｎｅｒａｌｄｉｓｓｉｍｉｌａｒｉｔｙｏｆａｌｌｔｈｅｏｂｊｅｃｔｓｉｎａｓｅｔｄｉｒｅｃｔｌｙ‚ｒｅ- ｄｕｃｅｓｈｉｇｈ-ｄｉｍｅｎｓｉｏｎａｌｃａｔｅｇｏｒｉｃａｌｄａｔａｅｎｏｒｍｏｕｓｌｙｗｉｔｈｏｕｔｌｏｓｓｏｆｃｏｍｐｕｔａｔｉｏｎａｃｃｕｒａｃｙａｎｄｇｅｔｓｔｈｅｃｌｕｓｔｅｒｉｎｇｒｅｓｕｌｔｂｙｏｎｌｙｏｎｃｅｄａｔａ ｓｃａｎｎｉｎｇ．Ｔｈｅｔｉｍｅｃｏｍｐｌｅｘｉｔｙｏｆｔｈｅａｌｇｏｒｉｔｈｍｉｓａｌｍｏｓｔｌｉｎｅａｒ．Ａｎｅｘａｍｐｌｅｏｆｒｅａｌｄａｔａｓｈｏｗｓｔｈａｔｔｈｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｉｓｅｆｆｅｃ- ｔｉｖｅ． ＫＥＹＷＯＲＤＳ ｃｌｕｓｔｅｒｉｎｇ；ｈｉｇｈ-ｄｉｍｅｎｓｉｏｎａｌｓｐａｃｅ；ｓｅｔｓ；ｄｉｓｓｉｍｉｌａｒｉｔｙ；ｄａｔａｍｉｎｉｎｇ 收稿日期：2010--01--18 基金项目：国家自然科学基金资助项目 （Ｎｏ．70771007） 作者简介：武 森 （1971— ）‚女‚教授‚博士‚Ｅ-ｍａｉｌ：ｗｕｓｅｎ＠ｍａｎａｇｅ．ｕｓｔｂ．ｅｄｕ．ｃｎ 高维数据聚类一直是数据挖掘 ［1］、复杂网络分 析 ［2］和生物信息学 ［3］等领域具有挑战性的研究课 题之一．传统的聚类算法主要是针对连续属性低维 数据提出的‚并不适用于高维数据的情况．而且‚由 于连续属性的差异度计算方法不适用于分类属性‚ 基于分类属性的高维数据聚类就更加困难． 近十年来‚分类属性高维数据聚类得到研究者 的广泛关注‚并取得了许多成果‚但算法的计算时间 复杂度普遍较高‚且一般需要两次或更多次数据扫 描．ＲＯＣＫ算法 ［4］针对传统的聚类算法主要适用于 连续属性的情况‚提出了适用于分类属性的链来度 量数据对象之间的相似度‚并进一步提出了聚结型 层 次 聚 类 算 法‚但 计 算 时 间 复 杂 度 超 过 了 Ｏ（ｎ 2ｌｏｇ2ｎ）‚其中 ｎ是对象数目‚不适用于处理大数 据集．信息瓶颈方法 ［5］基于互信息采用聚结型聚类 策略‚成功地应用于文档聚类中‚该算法的计算时间 复杂度为 Ｏ（ｎ 3 ）‚同样不适用于处理大数据集 ［5］． ＣＯＯＬＣＡＴ算法 ［6］基于熵进行分类属性数据聚类； ＬＩＭＢＯ算法 ［7］采用信息瓶颈框架来度量分类属性 元组的距离‚同时还给出了分类属性值的距离计算 方法‚既可以对元组聚类‚也可以对属性值聚类；ＦＰ- ＳＵＢ算法 ［8］将分类属性高维数据聚类问题转化为 最大频繁项集 （即聚类子空间 ）挖掘问题‚然后再进 行子空间聚类．ＦＰＳＵＢ算法的计算效率优于 ＣＯＯＬ- ＣＡＴ和 ＬＩＭＢＯ ［8］‚但子空间聚类没有从根本上解决 计算时间复杂度较高的问题‚且 ＦＰＳＵＢ算法同 ＣＯＯＬＣＡＴ和 ＬＩＭＢＯ一样仍然需要两次数据扫描． ＣＡＢＯＳＦＶ算法 ［9］针对特定的分类属性———二值属 DOI :10．13374／j．issn1001—053x．2010．08．045