数据挖掘中聚类分析算法研究

1、第 26 卷第 2 期2005 年 3 月通 化 师 范 学 院 学 报j o u rn al o f ton gh u a t ea c h ers col l e gevol . 26 2ma r .20053数据挖掘中聚类分析算法研究赵法信1 ,王国业2(1 . 通化师院教务处 ,吉林 通化 134002 ;2 . 沈阳建筑大学科技产业处 ,辽宁 沈阳 110168)摘 要 :聚类分析是数据挖掘的一个主要研究方向 ,目前其研究已深入到数据库 、数据挖掘 、统计等领域并取得了很大的成就 1 本文介绍了聚类分析的应用及数据挖掘对聚类算法的典型要求 ,并对现有的传统聚类算法进行了分析 与评估

2、1 最后介绍了聚类分析最新的研究方向 - - 流数据聚类分析 1关键词 :数据挖掘 ;聚类算法分析 ;流数据中图分类号 : tp311 . 13 文献标识码 : a 文章编号 :1008 - 7974 ( 2005) 02 - 0011 - 031概述在企业 ( 如零售 、金融 、电信) 的大型数据库中蕴含的有用的信息资源促进了知识发现和数据挖掘的蓬勃发展 1 聚类作为 数据挖掘中一个重要的组成部分 , 主要用于在潜在的数据中发现有价值的数据分布和数据模式 1 目前其研究已深入到数据 库 、数据挖掘 、统计等领域并取得了很大的成就 1聚类问题可以定义如下 :给定 d 维空间的 n 个数据点 ,

3、 把这 n 个点分成 k 个组 , 即满足最大的组内相似性和最小的组间相似性 , 使得不同聚类中的数据尽可能地不同 , 而同一聚类中的数据尽可能地相似 1 1聚类已经作为一种基本的数据挖掘方法广泛地应用于相似搜索 、顾客划分 、模式识别 、趋势分析等领域中 1 聚类算法在金 融投资 、地理信息系统 、卫星图象和信息检索等领域有着广泛的应用 1 例如 :在交易数据库中 , 顾客一次购买的商品 ( 数据项) 构成了一条交易 , 将经常同时购买的数据项聚类到一起有利于改善商品的布置 , 提高销售利润 ; 将具有相似的购买模式的顾 客聚类到一起 , 分析每一类顾客的特征 , 有利于对特定的顾客群进行特

4、定商品的宣传和销售 1 类似地 , 电子商务在每天的日常 业务中 , 都会产生大量的数据 1 这些信息被 web 服务器自动收集并存储在访问日志中 , 经过处理转换为交易数据库 1 分析这 些信息能帮助销售商确定相对固定的顾客群 , 制定商品的销售方案 , 评价各种促销活动的有效性 , 以及发现 web 空间最有效 的逻辑结构 1 在信息检索领域中 , 聚类分析对文档进行分类 , 改善信息检索的效率 , 或者发现某一领域文献的组成结构 1 在医 疗分析中 , 通过对一组新型疾病聚类 , 得到每类疾病的特征描述 , 就可以对这些疾病进行识别 , 提高治疗的功效 1 聚类还能帮 助医生发现不属于正

5、常类别的特殊病例 , 例如识别组织结构的病变细胞 1 聚类还用于发现空间趋势 , 即空间数据库中一个或 多个非空间属性的变化模式 1 在天文学上 , 研究人员利用聚类分析宇宙仿真系统得到的数据 , 更好地理解黑洞形成和进化的 物理过程 12数据挖掘算法对聚类的典型要求聚类是一个富有挑战性的研究领域 , 它的潜在应用提出了各自特殊的要求 , 因而每一种算法都是针对不同的情况而设计的 , 在数据挖掘领域对聚类算法的要求主要有以下几个方面 2 :可伸缩性 . 聚类算法对小数据集和大规模数据集要同样有效 .处理不同类型属性的能力 . 实际应用要求算法能够处理不同类型的数据 .能发现任意形状的聚类 .

6、聚类特征的未知性决定聚类算法要能发现球形的 、嵌套的 、中空的等任意复杂形状和结构的 聚类 .最少的参数和确定参数值的领域知识 . 聚类算法要尽可能地减少用户估计参数的最佳取值所需要的领域知识 .有效地识别噪声数据 . 聚类算法要能处理现实世界的数据库中普遍包含的孤立点 , 空缺或者错误的数据 .对于输入纪录的顺序不敏感 . 聚类算法对不同的次序的记录输入应具有相同的聚类结果 .高维性 . 聚类算法不仅要擅长处理低维的数据集 , 还应能处理高维 、数据可能非常稀疏且高度偏斜的数据集 .基于约束的聚类 . 聚类结果既要满足特定的约束 , 又要具有良好聚类特性 .可解释性和可用性 . 聚类应与特定

7、的语义解释和应用相联系 .nk函数是 6mind ( x i , m j ) , 其中 m j 是 c j 的中心 ( k - mea ns 算法) 3 , 或者是 cj 中离中心最近的一个对象 ( k -median) 4 1j = 1i = 1的划分方法有 pa m 、cl a ra 、cl a ra n s 等 1 下图描述了划分算法的基本框图 , 其中前三个步骤都有各种方法 , 通过组以得到不同的划分算法 1图 1 划分聚类算法的框图划分算法一般要求所有的数据都装入内存 , 限制了它们在大规模数据上的应用 1 它们还要求用户预先指定聚类的个但在大多数实际应用中 , 最终的聚类个数是未知

8、的 1 另外 , 划分算法只使用某一固定的原则来决定聚类 , 这就使得当聚类状不规则或者大小差别很大时 , 聚类的结果不能令人满意 13 . 2 基于层次的聚类层次聚类方法递归地对对象进行合并或者分裂 , 直到满足某一终止条件 1 根据层次的分解如何形成 , 层次聚类方法 为凝聚层次聚类和分裂层次聚类两种 1 凝聚层次聚类采用自底向上策略进行聚类 , 它从单成员聚类开始 , 把它们逐渐合 更大的聚类 , 在每一层中 , 相距最近的两个聚类被合并 1 相反 , 分裂层次聚类则采用自顶向下的策略 , 从包含所有对象的 聚类开始 , 把它逐渐分解成更小的聚类 5 1 典型的层次方法有 b irc h

9、 、cub e 、roc k、cha meleo n 、a gn es 、d ia na 等 1 描述了一个凝聚的层次聚类方法和一个分裂的层次聚类方法在包含五个对象的数据集合 a , b , c , d , e 上的处理过程 1网格文件 6 把 1 维空间的哈希方法扩展到 d 维空间 , 用来组织和管理多维空间的数据 1 它采用一个多分辨率的网格数据结构 , 将数据空间划分为若干单元 , 每一维上分割点的位置信息存储在数组中 , 分割线贯穿整个空间 1 典型的基于网格的聚类 方法有 s t in g、wavecl uster 和 cl iq u e1基于网格的聚类方法的共同之处是首先把数据空间

10、划分成一定数目的单元 , 以后所有的操作都是对单元进行的 1 但是所有的网格聚类算法都存在量化尺度的问题 1 一般来说 , 划分太粗糙造成不同聚类的对象被划分到同一个单元的可能性增加( 量化不足) 1 相反 , 划分太细致会得到许多小的聚类 ( 量化过度) 1 通常的方法是采用先从小单元开始寻找聚类 , 再逐渐增大单 元的体积 , 重复这个过程直到发现满意的聚类为止 1基于网格的聚类方法的主要优点是处理速度快 , 其处理时间独立于数据对象的数目 , 仅依赖于量化空间中每一维上的单元数目 13 . 5 基于模型的聚类基于模型的方法为每个簇假定了一个模型 , 寻找数据对给定模型的最佳拟合 1 一个

11、基于模型的算法可能通过构建反映数 据点空间分布的密度函数来定位聚类 1 它也基于标准的统计数字自动决定聚类的数目 , 考虑“噪声”数据或孤立点 , 从而产生健壮的聚类方法 1 典型的基于模型的聚类方法包括统计学方法 ( 如 cob w eb 、cl a ssi t 和 a uto cla ss) 或神经网络方法 ( 例如 有竞争学习和自组织特征图) 14新的对象的聚类算法近年来 , 越来越多的应用产生流数据 , 它不同于传统的存储在磁盘上的静态的数据 , 而是一类新的数据对象 , 它是连续的 、有序的 、快速变化的 、海量的数据 1 典型的流数据包括网络与道路交通监测系统的监测信息数据 、电信

12、部门的通话记录数据 、由传感器传回的各种监测数据 、股票交易所的股票价格信息数据以及环境温度的监测数据等 1 由于数据流的广泛应用 , 对 它的研究已经成为一个热点问题 1 相应地 , 流环境下的流聚类问题研究也成为热点方向之一 1, x n 的一个有序的序列 , 它只能被按顺序访问 , 而且仅能被扫描一次或有限的几次 7 1 流数据流数据是数据点 x1 , x2 ,是快速变化的 , 因而流聚类算法要能够跟上流的速度并抓住流的特征 ; 流数据是连续的 , 因而对流数据聚类要能随时间而不断地进行 ; 流数据是海量而有序的 , 不可能保证存贮整个数据集 , 只能分析一定范围内的数据 , 因而要有效

13、地利用有限的空间 与时间 1流数据本身所具有的特征使得传统的聚类算法不可能直接应用于 ( 甚至不能应用于) 流数据聚类1 因而 , 与传统的聚类算法相比 , 数据流聚类算法还应当具有以下特点 8 :一遍扫描 :在满足聚类要求的情况下 , 要尽可能少的扫描数据集 , 最好是一遍扫描 1有限的内存及存贮空间 :由于数据流具有无限连续性 , 不可能存贮如此海量的数据 , 因而要对流数据进行概化或有选 择的舍弃 1实时性 :每一个记录的处理时间要尽可能的少 , 要能够跟上流的速度 15结论聚类分析作为数据挖掘的重要组成部分 , 现在已广泛应用于各个领域 1 尽管目前已经提出了各种各样的聚类算法 , 不

14、同的算法有各自的特点 1 基于划分的算法适用于类数固定 、偏好球形的聚类 , 基于层次的算法能得到不同粒度上的多层次聚类结构 , 基于密度的算法可以在带有“噪声”的空间数据库中发现形状任意 、个数不定的聚类 , 基于网格的聚类算法处理速度快 ,处理时间独立于数据对象的数目 , 基于模型的方法则适用于数据分布已知的聚类 1 因此 , 在实际应用中应该根据具体问题具 体分析 , 选择使用或设计最佳聚类方法 1 同时 , 新数据对象的产生和广泛应用对传统的聚类算法提出了新的挑战 , 聚类分析将 随着应用的需求及新技术的出现而得到很大的发展 1参考文献 : 1 tho ma s rei na rtz

15、. focu si ng sol utio ns fo r dat a mi ni ng : a nal ytical st udie s a nd exp erient al re sult s i n real - wo rl d do mai n s c . ber2li n : sp ri nger , 1999 . 2 j iawei ha n , micheli ne ka mber . dat a mi ni ng co ncep t s a nd technique s m . mo r gan kauf mann publi sher s. inc . 2001 . 3 r

16、. o . duda , p. e. ha rt . pat t er n cla ssificatio n a nd scene a nal ysi s m . new yo r k : j o hn wiley and so ns , 19731 4 k l . ka uf ma n , p. j . ro u sseeuw . fi ndi ng gro up s i n dat a : a n i nt ro ductio n to cl ust er a nal ysi s m . j o hn wiley & so n s , 19901 5 a . k. j ai n ,

17、 r . c. dube s. al go rit h m fo r cl u st eri ng dat a c . prentice hall , 19881 6 j . niever gel t , h . hi nt er ber ger , k. c. sevci k . t he grid file : a n adap t a ble , symmert ric multi key file sti nct ure c . a cm tra n s. on dat aba se syst e ms , vol . 9 , no . 1 , 1984 , pp 38 - 711 7

18、 s. gu ha , n . mi shra , r . mo t wa ni , l . ocallagha n . cl u st eri ng dat a st rea ms c . i e ee fo cs co nf erence , 2000 . 8 m . ga rof ala ki s , j . gehr ke , a nd r . ra sto gi . q uer yi ng a nd mi ni ng dat a st rea ms : yo u o nl y get o ne loo k c . si gmod 20021stndy of focusing sol utions f or data min ingz h a o fa - xi n et al( t on g h u a t e ac he rs col l a ge , t on g h u a , j i l i n g , 134002)abstract : thi s p ap e r i nt ro duce s t he app licatio n of foc u si ng sol utio n s