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
,1086, 北京科技大学学报 第32卷 性通过定义稀疏特征向量实现高维数据聚类过程， 1.2相关定理 仅需一次数据扫描，计算时间复杂度降低到0(k), 根据集合差异度和集合精简表示的定义，易知 k为类的数目，但仅适用于二值属性，RBRP算 下述两个定理成立（证明略） 法[将高维数据聚类的计算时间复杂度降低到 定理1在数据表(XAV中，对于X的子集 0(nogn),但仍然需要两次数据扫描，且主要用于 Y IEA(Y)I=EAV(Y) 孤立点的发现 根据定理1，Y中所有对象取值相同的属性数目 与上述算法不同，本文提出的基于集合差异度 与Y中所有对象取值相同的属性对应的（属性序 的聚类算法（clustering algorithm based on set dissin i 号、属性值)）二元组的数目是一致的.因此，集合差 larity CABOSD)针对分类属性高维数据定义了集合 异度也可以通过下式计算： 差异度计算方法及数据的集合精简表示，在不损失 SD(Y)=(m-lEAV(Y)1/Y IX lEAV(Y)1). 聚类所需信息的情况下对数据进行高度压缩，不仅 在计算集合差异度的上式中，由于属性数目m 不需计算两两对象间的距离，计算量明显减少，并且 是已知常数，Y和EAV(Y)是包含在集合精简表示 只需1次数据扫描就能得到聚类结果，算法的计算 中的前两个分量，所以集合精简表示概括了一个对 时间复杂度接近线性 象集合内计算集合差异度所需的全部对象信息· CABOSD在聚类过程中只存储集合精简表示，而不 1定义与定理 存储该集合中所有对象的信息，这使得在处理大数 1.1集合差异度与集合精简表示 据集时数据处理量大规模减少 定义1（集合差异度）在数据表(XAV6 定理2在数据表(XAV,中，对于X的子集 中，X={,,…,x为对象集合；A={a,,, Y1和Y2,且Y∩当2=功，有 a为描述对象的分类属性集合；V=VV为属性 SR(YUY2)= 值集，V,为属性a的值域；是函数，即对Hx∈X UY I EAV(YUY2),SD(YUY2)), Ha∈A有a(x)=f代a)V=l2…,n1= 式中 YUY2l=Y+2↓ 1,2…,m对于X的子集YY伪集合Y中包含的 对象数目，EA(Y)=aHf￥5ra()=a(s) EAV(YUY)=EAV(Y)0EAV(Y). SD(YUY)=(m-EAV(Yi )n EAV(Y2))/ 为Y中所有对象取值都相同的属性的集合，则定义 Y Y2 IX lEAV(Y EAV(Y2)) SD(Y)=(m-lEA(Y)/J Y IX lEA(Y) 定理2表明，两个不相交的对象集合进行合并 为Y集合内对象间的集合差异度，简称集合差异 时，可以根据集合精简表示精确地计算合并后的集 度 合差异度，因此，集合精简表示不仅可以在处理大 集合差异度SD(Y)反映了Y集合内所有对象 数据集时大规模降低数据存储量和计算量，同时可 间的总体差异程度，SD(Y)越小，表明Y集合内所 以保证在集合进行合并时集合差异度计算的精确 有对象间越相似；SD(Y)越大，表明Y集合内所有对 性，也使得只需一次数据扫描完成聚类成为可能 象间越不相似. 定义2（集合精简表示）在数据表〈XA,∮ 2算法描述 中，对于X的子集Y,Y为集合Y中包含的对象数 CABOSD采用的是自底向上的聚结型聚类策 目，EAV(Y)=i(Ia(x)la∈EA(Y),Hx∈Y} 略.与一般聚结型聚类的多层结构不同，CABOSD 为Y中所有对象取值都相同的属性对应的（属性序 只有底层和顶层，没有中间层，底层将每个对象作 号，属性值)二元组的集合，$D(Y)为集合差异度，则 为一个类，顶层为最终聚成的类.在一次数据扫描 定义 过程中，直接完成顶层新类的创建及底层对象到顶 SR(Y)=(YL EAV(Y),SD(Y)) 层类的归并，得到聚类结果，是否创建新类取决于 为Y集合内所有对象聚类相关信息的集合精简表 预先指定的集合差异度上限b如果将当前扫描到 示向量，简称集合精简表示， 的对象并入任何一个已经创建的类都会使得并入后 特别地，当Y=1时，不妨记Y=iy,则 的集合差异度大于集合差异度上限b则创建一个 R(iy)=(L,(1m(y))(2(y), 新类，仅包含当前扫描到的对象：否则，将当前对象 (ma(y))i,0) 并入使得并入后集合差异度最小的类中，对于每一
北 京 科 技 大 学 学 报 第 32卷 性通过定义稀疏特征向量实现高维数据聚类过程 仅需一次数据扫描计算时间复杂度降低到Ｏ（ｎｋ） ｋ为类的数目但仅适用于二值属性．ＲＢＲＰ算 法 ［10］将高维数据聚类的计算时间复杂度降低到 Ｏ（ｎｌｏｇｎ）但仍然需要两次数据扫描且主要用于 孤立点的发现． 与上述算法不同本文提出的基于集合差异度 的聚类算法 （ｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｓｅｔｄｉｓｓｉｍｉ- ｌａｒｉｔｙＣＡＢＯＳＤ）针对分类属性高维数据定义了集合 差异度计算方法及数据的集合精简表示在不损失 聚类所需信息的情况下对数据进行高度压缩不仅 不需计算两两对象间的距离计算量明显减少并且 只需 1次数据扫描就能得到聚类结果算法的计算 时间复杂度接近线性． 1 定义与定理 1．1 集合差异度与集合精简表示 定义 1（集合差异度 ） 在数据表〈ＸＡＶｆ〉 中Ｘ＝｛ｘ1ｘ2…ｘｎ｝为对象集合；Ａ＝｛ａ1ａ2… ａｍ｝为描述对象的分类属性集合；Ｖ＝∪ａ∈Ａ Ｖａ 为属性 值集Ｖａ 为属性 ａ的值域；ｆ是函数即对∀ｘｉ∈Ｘ ∀ａｌ∈Ａ有 ａｌ（ｘｉ）＝ｆ（ｘｉａｌ）∈Ｖａｌｉ＝12…ｎｌ＝ 12…ｍ．对于 Ｘ的子集 Ｙ｜Ｙ｜为集合 Ｙ中包含的 对象数目ＥＡ（Ｙ）＝｛ａｌ｜∀ｘｉ∈Ｙｘｊ∈Ｙａｌ（ｘｉ） ＝ａｌ（ｘｊ）｝ 为 Ｙ中所有对象取值都相同的属性的集合则定义 ＳＤ（Ｙ）＝（ｍ—｜ＥＡ（Ｙ）｜）／（ ｜Ｙ｜×｜ＥＡ（Ｙ）｜） 为 Ｙ集合内对象间的集合差异度简称集合差异 度． 集合差异度 ＳＤ（Ｙ）反映了 Ｙ集合内所有对象 间的总体差异程度．ＳＤ（Ｙ）越小表明 Ｙ集合内所 有对象间越相似；ＳＤ（Ｙ）越大表明 Ｙ集合内所有对 象间越不相似． 定义 2（集合精简表示 ） 在数据表〈ＸＡＶｆ〉 中对于 Ｘ的子集 Ｙ｜Ｙ｜为集合 Ｙ中包含的对象数 目ＥＡＶ（Ｙ）＝｛（ｌａｌ（ｘｉ））｜ａｌ∈ＥＡ（Ｙ）∀ｘｉ∈Ｙ｝ 为 Ｙ中所有对象取值都相同的属性对应的 （属性序 号属性值 ）二元组的集合ＳＤ（Ｙ）为集合差异度则 定义 ＳＲ（Ｙ）＝（｜Ｙ｜ＥＡＶ（Ｙ）ＳＤ（Ｙ）） 为 Ｙ集合内所有对象聚类相关信息的集合精简表 示向量简称集合精简表示． 特别地当｜Ｙ｜＝1时不妨记 Ｙ＝｛ｙ｝则 ＳＲ（｛ｙ｝）＝（1｛（1ａ1（ｙ））（2ａ2（ｙ））… （ｍａｍ （ｙ））｝0）． 1．2 相关定理 根据集合差异度和集合精简表示的定义易知 下述两个定理成立 （证明略 ）． 定理1 在数据表〈ＸＡＶｆ〉中对于 Ｘ的子集 Ｙ｜ＥＡ（Ｙ）｜＝｜ＥＡＶ（Ｙ）｜． 根据定理1Ｙ中所有对象取值相同的属性数目 与 Ｙ中所有对象取值相同的属性对应的 （属性序 号、属性值 ）二元组的数目是一致的．因此集合差 异度也可以通过下式计算： ＳＤ（Ｙ）＝（ｍ—｜ＥＡＶ（Ｙ）｜）／（ ｜Ｙ｜×｜ＥＡＶ（Ｙ）｜）． 在计算集合差异度的上式中由于属性数目 ｍ 是已知常数｜Ｙ｜和 ＥＡＶ（Ｙ）是包含在集合精简表示 中的前两个分量所以集合精简表示概括了一个对 象集合内计算集合差异度所需的全部对象信息． ＣＡＢＯＳＤ在聚类过程中只存储集合精简表示而不 存储该集合中所有对象的信息．这使得在处理大数 据集时数据处理量大规模减少． 定理2 在数据表〈ＸＡＶｆ〉中对于 Ｘ的子集 Ｙ1和 Ｙ2且 Ｙ1∩Ｙ2＝●有 ＳＲ（Ｙ1∪Ｙ2）＝ （｜Ｙ1∪Ｙ2｜ＥＡＶ（Ｙ1∪Ｙ2）ＳＤ（Ｙ1∪Ｙ2）） 式中 ｜Ｙ1∪Ｙ2｜＝｜Ｙ1｜＋｜Ｙ2｜ ＥＡＶ（Ｙ1∪Ｙ2）＝ＥＡＶ（Ｙ1）∩ＥＡＶ（Ｙ2） ＳＤ（Ｙ1∪Ｙ2）＝（ｍ—｜ＥＡＶ（Ｙ1）∩ＥＡＶ（Ｙ2）｜）／ （ ｜Ｙ1｜＋｜Ｙ2｜×｜ＥＡＶ（Ｙ1）∩ＥＡＶ（Ｙ2）｜）． 定理 2表明两个不相交的对象集合进行合并 时可以根据集合精简表示精确地计算合并后的集 合差异度．因此集合精简表示不仅可以在处理大 数据集时大规模降低数据存储量和计算量同时可 以保证在集合进行合并时集合差异度计算的精确 性也使得只需一次数据扫描完成聚类成为可能． 2 算法描述 ＣＡＢＯＳＤ采用的是自底向上的聚结型聚类策 略．与一般聚结型聚类的多层结构不同ＣＡＢＯＳＤ 只有底层和顶层没有中间层．底层将每个对象作 为一个类顶层为最终聚成的类．在一次数据扫描 过程中直接完成顶层新类的创建及底层对象到顶 层类的归并得到聚类结果．是否创建新类取决于 预先指定的集合差异度上限 ｂ．如果将当前扫描到 的对象并入任何一个已经创建的类都会使得并入后 的集合差异度大于集合差异度上限 ｂ则创建一个 新类仅包含当前扫描到的对象；否则将当前对象 并入使得并入后集合差异度最小的类中．对于每一 ·1086·
第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·
,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·
第8期 武森等：分类属性高维数据基于集合差异度的聚类算法 .1089. for categorical attributes Pmceedings of Intemational Confernce 123 of Data Engineering Sydney 1999.512 [8]Shan S M.W ang X Y.Zhang X C Chstering algorithm form n- [5]Shnin N.Tishby N.Document chstering using wod chsters via ing subspace clusters n categorical data sets J Chin Comnput Syst the infomation bottleneck method Pmceed ings of the23 Annual 200930(10):2016 In temational ACM SIRR Confernce on Research and Development (单世民，王新艳，张宪超，高维分类属性的子空间聚类算法 in Infomation Retrieval A thens 2000.208 小型微型计算机系统，200930(10)：2016) [6]Badbam D.Li Y.Couto J COOLCAT:an entmopybased algo- [9]Wu S Gao X D.CABOSFV algorithm for high dinensional sparse ritm for categorical clusterng/Pmceedings of the 11 th Intema- data chustering J Univ SciTechnol Beijing 2004.11(3):283 tional Conference on Infomation and Know ledge Management [10]Ghoting A.Parthasarathy S Otey M E Fastm ning of distance- McLean 2002 582 based outliers n high diensional datasets Data M in Knowl [7]Andritsos P.Tsaparas P Miller R J et al LMBO:scalabl Die200816(3):349 chstering of categorical data//Proceedings of 9th Intemational [11]Almnad A.Dey L A kmean chisterng akorithm for m ixed nu- Conference on Extending Database Technobogy Heraklion 2004. meric and categorical dats Data KnowlEng 2007.63.503 (上接第1077页) tems for steel strip MPTMetallP lant Technol Int 1990.13(1): [5]Acaden ic Camm ittee for Hot Rolling Plate and Strip of The Chi 70 nese society formetals Chinese Rolling M ill and P roduction Tech- [8]Hong W K.YiJ J Flamess contml using a contact type of sha- nology for Hot W ide Strip Beijng Metallurgical Industry Press peneter for continuous hot strip mlling Steel Timne Int 2000.24 2004 (6):28 (中国金属学会热轧板带学术委员会·中国热轧宽带钢轧机 [9]Hong W K.YiJJ Apparatus forM casuring the Strip F lamess US 及生产技术.北京：冶金工业出版社，2004) Patent6427507.2002-08-06 [6]Fabian W.W ladka H.TappeW,etal On-line flatnessmeasure- [10]LiM W,Bian XX.Chen G.et al Strip Flamess Measurment ment and control of hot w ide strip MPT Metall P lantTechnol Int Device of Looper Type China Patent 201034548 2008-3-12 19858(4):68 (李谋渭，边新孝，陈工，等.活套辊式平坦度检测装置：中国 [7]Kopineck H J Tappe W.New on-line measuring and esting sys 专利，2010345482008-3-12)
第 8期 武 森等： 分类属性高维数据基于集合差异度的聚类算法 ｆｏｒｃａｔｅｇｏｒｉｃａｌａｔｔｒｉｂｕｔｅｓ∥ＰｒｏｃｅｅｄｉｎｇｓｏｆＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ ｏｆＤａｔａＥｎｇｉｎｅｅｒｉｎｇ．Ｓｙｄｎｅｙ1999：512 ［5］ ＳｌｏｎｉｍＮＴｉｓｈｂｙＮ．Ｄｏｃｕｍｅｎｔｃｌｕｓｔｅｒｉｎｇｕｓｉｎｇｗｏｒｄｃｌｕｓｔｅｒｓｖｉａ ｔｈｅｉｎｆｏｒｍａｔｉｏｎｂｏｔｔｌｅｎｅｃｋｍｅｔｈｏｄ∥Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ23ｒｄＡｎｎｕａｌ ＩｎｔｅｒｎａｔｉｏｎａｌＡＣＭＳＩＧＩＲＣｏｎｆｅｒｅｎｃｅｏｎＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔ ｉｎＩｎｆｏｒｍａｔｉｏｎＲｅｔｒｉｅｖａｌ．Ａｔｈｅｎｓ2000：208 ［6］ ＢａｒｂａｒａＤＬｉＹＣｏｕｔｏＪ．ＣＯＯＬＣＡＴ：ａｎｅｎｔｒｏｐｙ-ｂａｓｅｄａｌｇｏ- ｒｉｔｈｍｆｏｒｃａｔｅｇｏｒｉｃａｌｃｌｕｓｔｅｒｉｎｇ∥Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ11ｔｈＩｎｔｅｒｎａ- ｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＩｎｆｏｒｍａｔｉｏｎａｎｄＫｎｏｗｌｅｄｇｅＭａｎａｇｅｍｅｎｔ． ＭｃＬｅａｎ2002：582 ［7］ ＡｎｄｒｉｔｓｏｓＰＴｓａｐａｒａｓＰＭｉｌｌｅｒＲ Ｊｅｔａｌ．ＬＩＭＢＯ：ｓｃａｌａｂｌｅ ｃｌｕｓｔｅｒｉｎｇｏｆｃａｔｅｇｏｒｉｃａｌｄａｔａ∥ Ｐｒｏｃｅｅｄｉｎｇｓｏｆ9ｔｈＩｎｔｅｒｎａｔｉｏｎａｌ ＣｏｎｆｅｒｅｎｃｅｏｎＥｘｔｅｎｄｉｎｇＤａｔａｂａｓｅＴｅｃｈｎｏｌｏｇｙ．Ｈｅｒａｋｌｉｏｎ2004： 123 ［8］ ＳｈａｎＳＭＷａｎｇＸＹＺｈａｎｇＸＣ．Ｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｆｏｒｍｉｎ- ｉｎｇｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｓｉｎｃａｔｅｇｏｒｉｃａｌｄａｔａｓｅｔｓ．ＪＣｈｉｎＣｏｍｐｕｔＳｙｓｔ 200930（10）：2016 （单世民王新艳张宪超．高维分类属性的子空间聚类算法． 小型微型计算机系统200930（10）：2016） ［9］ ＷｕＳＧａｏＸＤ．ＣＡＢＯＳＦＶａｌｇｏｒｉｔｈｍｆｏｒｈｉｇｈｄｉｍｅｎｓｉｏｎａｌｓｐａｒｓｅ ｄａｔａｃｌｕｓｔｅｒｉｎｇ．ＪＵｎｉｖＳｃｉＴｅｃｈｎｏｌＢｅｉｊｉｎｇ200411（3）：283 ［10］ ＧｈｏｔｉｎｇＡＰａｒｔｈａｓａｒａｔｈｙＳＯｔｅｙＭＥ．Ｆａｓｔｍｉｎｉｎｇｏｆｄｉｓｔａｎｃｅ- ｂａｓｅｄｏｕｔｌｉｅｒｓｉｎｈｉｇｈ-ｄｉｍｅｎｓｉｏｎａｌｄａｔａｓｅｔｓ．ＤａｔａＭｉｎＫｎｏｗｌ Ｄｉｓｃ200816（3）：349 ［11］ ＡｈｍａｄＡＤｅｙＬ．Ａｋ-ｍｅａｎｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｆｏｒｍｉｘｅｄｎｕ- ｍｅｒｉｃａｎｄｃａｔｅｇｏｒｉｃａｌｄａｔａ．ＤａｔａＫｎｏｗｌＥｎｇ200763：503 （上接第 1077页 ） ［5］ ＡｃａｄｅｍｉｃＣｏｍｍｉｔｔｅｅｆｏｒＨｏｔＲｏｌｌｉｎｇＰｌａｔｅａｎｄＳｔｒｉｐｏｆＴｈｅＣｈｉ- ｎｅｓｅｓｏｃｉｅｔｙｆｏｒｍｅｔａｌｓ．ＣｈｉｎｅｓｅＲｏｌｌｉｎｇＭｉｌｌａｎｄＰｒｏｄｕｃｔｉｏｎＴｅｃｈ- ｎｏｌｏｇｙｆｏｒＨｏｔＷｉｄｅＳｔｒｉｐ．Ｂｅｉｊｉｎｇ：ＭｅｔａｌｌｕｒｇｉｃａｌＩｎｄｕｓｔｒｙＰｒｅｓｓ 2004 （中国金属学会热轧板带学术委员会．中国热轧宽带钢轧机 及生产技术．北京：冶金工业出版社2004） ［6］ ＦａｂｉａｎＷＷｌａｄｉｋａＨＴａｐｐｅＷｅｔａｌ．Ｏｎ-ｌｉｎｅｆｌａｔｎｅｓｓｍｅａｓｕｒｅ- ｍｅｎｔａｎｄｃｏｎｔｒｏｌｏｆｈｏｔｗｉｄｅｓｔｒｉｐ．ＭＰＴＭｅｔａｌｌＰｌａｎｔＴｅｃｈｎｏｌＩｎｔ 19858（4）：68 ［7］ ＫｏｐｉｎｅｃｋＨＪＴａｐｐｅＷ．Ｎｅｗｏｎ-ｌｉｎｅｍｅａｓｕｒｉｎｇａｎｄｔｅｓｔｉｎｇｓｙｓ- ｔｅｍｓｆｏｒｓｔｅｅｌｓｔｒｉｐ．ＭＰＴＭｅｔａｌｌＰｌａｎｔＴｅｃｈｎｏｌＩｎｔ199013（1）： 70 ［8］ ＨｏｎｇＷ ＫＹｉＪＪ．Ｆｌａｔｎｅｓｓｃｏｎｔｒｏｌｕｓｉｎｇａｃｏｎｔａｃｔｔｙｐｅｏｆｓｈａ- ｐｅｍｅｔｅｒｆｏｒｃｏｎｔｉｎｕｏｕｓｈｏｔｓｔｒｉｐｒｏｌｌｉｎｇ．ＳｔｅｅｌＴｉｍｅＩｎｔ200024 （6）：28 ［9］ ＨｏｎｇＷ ＫＹｉＪＪ．ＡｐｐａｒａｔｕｓｆｏｒＭｅａｓｕｒｉｎｇｔｈｅＳｔｒｉｐＦｌａｔｎｅｓｓ：ＵＳ Ｐａｔｅｎｔ6427507．2002--08--06 ［10］ ＬｉＭＷＢｉａｎＸＸＣｈｅｎＧｅｔａｌ．ＳｔｒｉｐＦｌａｔｎｅｓｓＭｅａｓｕｒｅｍｅｎｔ ＤｅｖｉｃｅｏｆＬｏｏｐｅｒＴｙｐｅ：ＣｈｉｎａＰａｔｅｎｔ201034548．2008--3--12 （李谋渭边新孝陈工等．活套辊式平坦度检测装置：中国 专利201034548．2008--3--12） ·1089·