,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‚…‚ ａｍ｝为描述对象的分类属性集合；Ｖ＝∪ａ∈Ａ Ｖａ 为属性 值集‚Ｖａ 为属性 ａ的值域；ｆ是函数‚即对∀ｘｉ∈Ｘ‚ ∀ａｌ∈Ａ‚有 ａｌ（ｘｉ）＝ｆ（ｘｉ‚ａｌ）∈Ｖａｌ‚ｉ＝1‚2‚…‚ｎ‚ｌ＝ 1‚2‚…‚ｍ．对于 Ｘ的子集 Ｙ‚｜Ｙ｜为集合 Ｙ中包含的 对象数目‚ＥＡ（Ｙ）＝｛ａｌ｜∀ｘｉ∈Ｙ‚ｘｊ∈Ｙａｌ（ｘｉ） ＝ａｌ（ｘｊ）｝ 为 Ｙ中所有对象取值都相同的属性的集合‚则定义 ＳＤ（Ｙ）＝（ｍ—｜ＥＡ（Ｙ）｜）／（ ｜Ｙ｜×｜ＥＡ（Ｙ）｜） 为 Ｙ集合内对象间的集合差异度‚简称集合差异 度． 集合差异度 ＳＤ（Ｙ）反映了 Ｙ集合内所有对象 间的总体差异程度．ＳＤ（Ｙ）越小‚表明 Ｙ集合内所 有对象间越相似；ＳＤ（Ｙ）越大‚表明 Ｙ集合内所有对 象间越不相似． 定义 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·