数据挖掘中聚类算法比较研究

1、第 24卷 第 5期 2001年 10月鞍 山 钢 铁 学 院 学 报Journal of Anshan Institute of I. &S. T echnologyV ol. 24N o. 5 Oct. ,2001数据挖掘中聚类算法比较研究张红云 , 石 阳 , 马 垣(鞍山钢铁学院 计算机科学与工程学院 , 辽宁 鞍山 114002摘 要 :聚类算法是数据挖掘中的核心技术 , 虽然聚类算法已被广泛深入的研究 , 但其应用在数据挖掘领域 时间不长 , 其间产生了许多不同的适用于数据挖掘的聚类算法 , 但这些算法仅适用于特定的问题及用户 . 为了 更好的使用这些算法 , 综合提出了评

2、价聚类算法好坏的 5个标准 , 基于这 5个标准 , 对数据挖掘中近几年提出 的常用聚类方法作了比较分析 , 以利于人们更容易 、 .关键词 :数据挖掘 ; 聚类算法 ; 数据库中图分类号 :TP182 文献标识码 :A 文章编号 : 0364 , (无监督 、 聚合和分 割 、 剖析 、 , 不同类别间距离尽可 能大 . , 长期以来 , 人们从不同角度提出了近百种聚类方法 . 典型的有 K -menas 方法 , K -medoids 方法 、 C LARAN 方法 、 BIRCH 方法 、 DBSC AN 方法和 C URE 方法等 . 这 些算法仅适用于特定的问题及用户 . 为了更好的

3、使用这些算法 , 本文综合提出了评价聚类算法好坏的 5个标准 , 基于这 5个标准 , 对数据挖掘中近几年提出的常用聚类方法作了比较分析 , 以利于人更容易 、 更 快速的找到一种适用于特定问题及用户的聚类算法 .1 数据挖掘中聚类研究及比较框架 现存的聚类算法一般分为分割和分层两种 . 分割聚类算法通过优化一个评价函数把数据集分割为 K 个部分 (K 为聚类个数 , 需要 K 作为输入参数 . 典型的分割聚类算法有 K -means 算法 、 K -medoids 算 法 、 C LARANS 算法 (K -medoids 算法的改进 ; 分层聚类是由不同层次的分割聚类组成 , 层次之间的分

4、割 具有嵌套的关系 , 不需要 K 作为输入参数 . 这是优于分割聚类算法的一个明显的优点 , 缺点是终止条件 必须被具体指定 , 典型的分层聚类算法是 BIRCH 算法 、 DBSC AN 算法和 C URE 算法 . 在数据挖掘中 , 最近提出的一阶逻辑决策树可用作分层聚类 , 一个层次上的所有节点定义了一个例 子的分布 , 并且一个节点的所有子节点定义了相应于那个节点的所有例子的分布 . 本文对聚类各方法的比较研究基于以下 5个标准 :(1 是否适用于大数据量 , 算法的效率要满足大 数据集的大数据量 、 高复杂性 、 高增量的要求 ; (2 是否能应付不同的数据类型 , 至少能处理数值

5、属性和 符号属性 ; (3 是否能发现不同类型的聚类 ; (4 是否能应付脏数据或异常数据 ; (5 是否对数据的输入 顺序不敏感 . 下面将在该框架下对各聚类方法作分析比较 .2 数据挖掘领域中常用的聚类方法211 BIRCH 算法 (平衡迭代削减聚类法 BIRCH 算法的核心是用一个聚类特征三元组 CF 总结了一个簇个体的有关信息 , 从而使一簇点的 表示可以用对应的聚类特征 , 而不必用具体的一组点来表示 , 通过构造满足分支因子和簇直径限制的聚收稿日期 :2001-06-28.作者简介 :张红云 (1973- , 女 , 江苏常州人 , 讲师 . 类特征树来求聚类 . 描述如下 : 对

6、于一具有 N 个 d 维数据点的类 x i (i =1, 2, , N , 它的聚类特征向量定义为 :CF =(N , LS SS (1 其中 N 为类中点的个数 ; LS N 个点的线性和 Ni =1x i , 反映了类的重心 , SS 为 N 个点的平方和 N i =1 x i 2, 反映了类直径大小 . 此外 , . 定理 1 假设 CF 1=(N 1, LS 1, SS 1 与 CF 2=(N 2, LS 2, SS 2 分别为两个类的聚类特征 , 则两个类合 并后形成的新类特征为CF 1+C F 2=N 1+N 2, LS 1+LS 2, SS 1+SS 2(2 该算法通过聚类特征可

7、以方便地进行中心、 半径 、 . T . 分枝因子规定了树 , , 即这些点在多大范围内可以 聚为一类 , , 可以根据这些关键字进行插入索引 , 它总结了其子 女的信息 . 聚类特征树可以动态构造 , 因此不要求所有数据读入内存 , 而可在外存上逐个读入数据项 . 新的数 据项总是插入到树中与该数据距离最近的叶子中 . 如果插入后使得该叶子的直径大于类直径 T , 则把该 叶子节点分裂 . 其它叶子结点也需要检查是否超过分枝因子来判断其分裂与否 , 直至该数据插入到叶子 中 , 并且满足不超过类直径 , 而每个非叶子节点的子女个数不大于分枝因子 . 可以通过改变类直径大小 , 修改特征树大小

8、来控制其占内存容量 . BIRCH 算法通过一次扫描就可以进行较好的聚类 , 由此可见 , 该算法适合于大型数据库 . 对于给定 的 M 兆内存空间 , 其空间复杂度为 O (M , 时间复杂度为 O dNB ln B P , 其中 d 为维数 , N 为节点数 ,P 为内存页的大小 , B 为由 P 决定的分支因子 , I/O 花费与数据库成线性关系 . 但 BIRCH 算法只适用于 类的分布呈凸形及球形等情况 , 并且由于 BIRCH 算法需提供正确的聚类个数和簇直径限制 , 对不可视 的高维数据是不行的 .212 C URE 算法 (使用代表点的聚类方法 该算法首先把每个数据点看成一类

9、, 然后再合并距离最近的类直至聚类个数为所要求的个数为止 . 它对传统聚类方法中对类的表示方法进行了改进 , 回避了用所有点或简单地用中心和半径这样单一条 件来表示一个类 , 而是从每个类中抽取固定数量 、 分布较好的点作为描述此类的代表点 , 并将这些点乘 以一个适当的收缩因子 , 使它们更靠近类的中心点 . 将一个类用多个代表点来表示 , 就使得聚类的外延 可以向非球形的形状扩展 , 从而可调整聚类的形状以表达那些非球形的类 . 另外 , 收缩因子的使用减小 了噪音对聚类的影响 . 同时 ,C URE 算法采用随机抽样与分割相结合的办法来提高算法的空间和时间效 率 , 并且在该算法中用了堆

10、和 K -d 树结构来提高算法效率 .213 DBSC AN 算法 (基于高密度的聚类算法 该算法利用类的高密度连通性可以快速发现任意形状的类 . 其基本思想是 :对于一个类中的每个对 象 , 在其给定半径的领域中包含的对象不能少于某一给定的最小数目 . 在 DBSC AN 中 , 发现一类的过程 是基于这样的事实 :一个类能够被其中的任意一个核心对象所确定 . 为了发现一个类 ,DBSC AN 先从对 象集 D 中找到任意一对象 P , 并查找 D 中关于 R 和 P min 的从 P 密度可达的所有对象 (其中 R 为半径 , P min 为最小对象数 . 如果 P 是核心对象 , 也就是

11、说 , 半径为 R 的 P 的领域中包含的对象不少于 P min , 则 根据算法 , 可以找到一个关于参数 R 和 P min 的类 . 如果 P 是一个边界点 , 则半径为 R 的 P 领域包含的对 563 第 5期 张红云 , 等 :数据挖掘中聚类算法比较研究 象数小于 P min , 则没有对象从 P 密度可达 , P 被暂时标注为噪声点 , 然后 , DBSC AN 处理数据库 D 中的 下一个对象 . 密度可达对象的获取是通过不断执行区域查询来实现 . 一个区域查询返回指定区域中的所有对象 . 为了有效地执行区域查询 , DBSC AN 算法使用了空间查询中 R 3树结构 . 在进

12、行聚类前 , 必须建立针对 所有数据的 R 3树 . 另外 , DBSC AN 要求用户指定一个全局参数 R (为了减少计算量 , 预先确定参数 P min , 为了确定 R 值 , DBSC AN 计算任意对象与它的第 k 个最临近的对象之间的距离 . 然后 , 根据求得 的距离由小到大进行排序 , 并给出排序后的图 , 称做 k -dist 图 . k -dist 图中的横坐标表示数据对象与它的 第 k 个最近的对象间的距离 ; 纵坐标则为对应于某一 k -dist 距离值的数据对象的个数 . R 3树的建立 k -dist 图的绘制是非常消耗时间的过程 . 此外 , 为了得到较好的聚类结

13、果 , 用户必须根据 k -dist 图 , 通过试 探选定一个比较合适的 k -dist 值 , 即 R 值 . 再就是 ,DBSC AN 不进行任何的预处理而直接对整个库进行 聚类操作 . 当数据库非常大时 , 就必须有大内存量支持 ,I/O . O (N log N (N 为数据库中包含对象数目 , . 对 R 及 P min 非常 敏感 , 且这两个参数很难确定 .214 K K -means 方法改进的能够处理符号属性的 K -m odes 方法 . K -po 2totypes 算法如下 : (1 X , Y 其属性为 A r 1, A r 2, , A r p , A c p +

14、1, , A c m , 其中属性 A r 1, A r 2, , A r p 为数值属性 , A c p +1, , A c m 为符号属性 , 则测量它们不相似性的度量如下d (X , Y = P j =1(x j -y j 2+ mj =p+1(x j , y j (3前一部分基于欧式距离 , 后一部分基于海明距离 , 从而既可处理数值属性又可处理符号属性 . (2 给定一个例子的集合 Z 和一个整数 k (k n , 该算法将 Z 分割为 k 个聚类并使得在每个聚类 中所有值与该聚类中心距离的总和最小 . (每个聚类的聚类中心是每个聚类的均值 . 该过程可以被描述 为如下数学问题min

15、 Q P (W , Q =k l =1 n i =1w i , l p j =1(z i , j -q l , j 2+ n i =1w i , l mj =p+1(z i , j , q l , j (4其中 为平衡 K -means 和 K -m odes 的一个参数 , W 是一个 N ×K 分割矩阵 , 用以表示每个例子在哪个聚 类中 , 通常它的每一行和为 1, Q =Q 1, Q 2, , Q K 是聚类结果的集合 .215 C LARANS 算法 (随机搜索聚类算法 C LARANS 算法是一种分割而非分层的聚类方法 . 它首先随机选择一个点作为当前点 , 然后随机检

16、查它周围不超过参数 Maxneighbor 个的一些邻接点 , 假如找到一个比它更好的邻接点 , 则把它移入邻接 点 , 否则把该点作为局部最小量 . 然后 , 再随机选择一个点来寻找另一个局部最小量 , 直到所找到的局部 最小量数目达到用户要求为止 . 该算法要求聚类的对象必须预先都调入内存 , 并且需扫描多次数据库 , 这对大型数据库而言 , 无论从时间复杂度还是空间复杂度而言 , 都是不太适用的 . 虽后来通过引入 R 3树结构对其性能进行改善 , 使之能够处理基于磁盘的大型数据库 , 但 R 3树的构造和维护代价太大 . 虽 然该算法对脏数据和异常数据不敏感 , 但对数据输顺序异常敏感

17、 , 且只能处理凸形或球形边界聚类 . 216 C LI QUE 算法 (自动子空间聚类算法 C LI QUE 算法利用自顶向上方法求出各个子空间的聚类单元 . C LI QUE 算法主要用于找出高维数据 空间中存在的低维聚类 . 为了求出 d 维空间聚类 , 则必须组合给出所有 d -1维子空间的聚类 , 导致其 算法的空间和时间效率都较低 , 而且要求用户输入两个参数 :数据聚值空间等间隔距离 和密度阈值 . 这些数据与样本数据紧密相关 , 用户一般难以确定 . 但它对数据的不同顺序不敏感 .663 鞍 山 钢 铁 学 院 学 报 第 24卷 3 结 论 基于上述分析 , 得到聚类各个方法

18、的比较结果 , 如表 1所示 .表 1 聚类算法比较T ab. 1 Clustering Method C om paris on算法效率适合的数据 类型 发现的聚类 类型 对脏数据开异常 数据的敏感性 对数据输入顺序 的敏感性 BIRCH高 数值 凸形或球形 不敏感 不太敏感 DBSCAN一般 数值 任意形状 敏感 敏感 CURE较高 数值 任意形状 不敏感 不太敏感 K -prototypes 一般 数值和符号凸形或球形 敏感 一般 C LARANS 较低 数值C LIQUE较低 不敏感 由表 1虑 ,BIRCH ; (2 ,C C LARANS 脏数据或异常数据的不敏感性 , 但只能发现

19、凸形或 球形的聚类 ; (3 K -prototypes 能处理数值和符号的数据 ; (4 DBSC AN 和 C UREC 能发现任意形状 的类 . 由于每个方法都有其优缺点和不同的适用领域 , 在数据挖掘中 , 用户应该根据实际需要选择恰当的 聚类算法 .参 考 文 献 :1 ZH ANG T ,RAM AK RISH NAN R ,LI VNYM. BIRCH :AnE fficient Data Clustering Method for very Large DatabaseA.In :Procofthe AC M SIG M OD Int s C on f on Managemen

20、t of DataC.M ontreal Canada :ACM Press ,1996. 83-94.2 S ANDER F ,ESTER M ,K RIEGE L HP ,X UX. The Alg orithm G DBSC AN and its Applications. Data M ining and K nowledge Discov 2eryJ.K LUWER Academic Publishers ,1998,2:178-192.3 Ng RT ,C A LBERS ON J. E fficient and E ffective Clustering Methods for

21、S patial Data M iningA.In :Porc of the V LDB C on ferenceC.Santiag o ,Chile ,1994. 144-155.4 边肇祺 , 张学工 . 模式识别 (第二版 . 聚类技术 M.北京 :清华大学出版社 ,1999. 235-247.5 GEHRKE J ,AG RAW A L R , G UNOPU LOS D. Automatic Subspace Clustering of High Dimensional Data for Data M ining Appli 2caitonsJ.AC M SI M OD ,1998,

22、72(2 :94-105.6 CHRIST OPHER J ,PHI LIP K. Chan ,Systems for K nowledge Discovery in Databases IEEE T tansJ.On K nowledge and Data Engi 2neering ,1993,5(6 :903-913.7 BET UR V ,DAS ARAEHY. Data M ining and K nowledge Discovery :Theory , T ool ,and T echnology A .Orlando , Florida 2000SPIE -The Interna

23、tional S ociety for Optical EngineeringC,2000. 259-264.8 K RZY SZT OF J Cios , WIT O LD Pedrycz , ROM AN W S wingiarski. Data M ining Mehods for K nowledge Discovery M .London :K LUWER AC DE MIC ,1998. 1-20.9 M ARTI N Ester ,H ANS -PETER K riegel ,JORG Sander. Incremental Clustering for M ining in a

24、 Data Warehousing EnvironmentA.Ahsish G upta ,Oded Shmueli ,Jennifer Widom. Proceedings of the T wenty -F ourth Internatal C on ference on Very Large DatabsesC.NEW Y ork :NYUS A ,1998. 323-333.10 ESTER M ,K RIEGE L H -P ,S ANDER J. A Density -Based Alg orithm for Discovery Clusters in Large S patial

25、 Databases with N oiseA.Proc 2nd Int C on f On K nowledge Discovery and Data M iningC.P ortland OR ,1996. 226-231.下转第 371页 763 第 5期 张红云 , 等 :数据挖掘中聚类算法比较研究 各方格的填挖土方量见图 3, 汇总结果V e =285m 3V f =-291m3V =285-291=6m 3填挖方基本平衡 . 实践证明 , 利用上述公式进行设计面为斜坡面的场地平整时的重心高程和重心定位 , 是有效的实用 公式 , 对减少土方施工时的盲目性极为有效 , 而一般资料未见

26、说明 , 所以值得推广 .参 考 文 献 :1 工厂建设测量手册编写组 . 工厂建设测量手册 M.北京 :,1990. 363-2 邵自修 . 工程测量 M.北京 :冶金工业出版社 ,1992. 83-85.3 石世支 . 非平行断面的土方量计算 J.测绘通报 8-Construction Field under LevellingY ANG Tie-li , BAI Ping(High Professional Institute ,Anshan Institute of I. &S. T echnology ,Anshan 114002,China Abstract :In ord

27、inary case ,it si not enough to determined the elevation and position of construction field s center of gravity for regular shape yard has been considered only. The paper described the theory with determined the irregular shape construction field s elevation and the center of gravity for inclined plane yard with coordinating and each square s area with weigh ,at last ,the paper give examles of using method of this theory.K ey Words :sm oothen field ;incline plane ;center of gravity(R eceived July 11, 2001上接第 367页 Comparison