（计算机应用技术专业论文）基于密度和网格的数据流聚类研究与实现.pdf

大连理工大学硕士学位论文 摘要 随着科学技术的飞速发展，人类获取知识能力越来越强。近些年来随着无线传感器 网络、路由器等设备的出现，人们获取数据的能力得到了极大的提高。出现了一种新的 数据模型一数据流模型。 该模型中待处理的数据不再被静态、固定地存储在可多次、随机访问的介质中，而 是以一种动态、流式的形式出现。访问数据的方法被限定为进行顺序的、一次或有限次 的访问。目前关于数据流挖掘的研究主要有数据流聚类、分类、频繁模式挖掘等等。本 文通过研究传统的基于密度和基于网格的聚类方法，发现传统的基于密度的聚类方法要 求多次访问数据，并且不能动态地生成聚类结果；而传统的基于网格的聚类算法虽然能 一次读取数据，并且能很快的处理数据，但它降低了簇的质量和精确性。传统的基于网 格和基于密度的聚类算法均不能满足数据流聚类的要求。 本文结合传统聚类算法的一些方法提出了一种采用树型概要结构的密度网格树数 据流聚类算法d g t r e e ( d e n s i t ya n dg r i d t r e ea l g o r i t h m ) 。该算法利用数据流聚类算法 c l u s t r e a m 中的处理框架，把聚类分为微聚类和宏聚类两个过程。在微聚类过程中，通 过把数据流按属性值分配到一棵树中，消除了空网格对聚类结果的影响，同时针对数据 流聚类中，近期的数据往往比久远的数据更受关注的特点，引入了时间衰退模型；在宏 聚类过程中，对微聚类中生成的树中的叶子节点进行密度聚类，通过设立噪音密度阀值 函数和更新周期，不仅可以有效的发现噪音叶子节点，还减少了密度聚类中对叶子节点 密度更新的计算量，减少了算法的时间消耗。通过在k d dc u p9 9 数据集上的实验表明， 相比d b s c a n 算法和c l u s t r e a m 算法，d g t r e e 算法在时间效率上有很大提高。 关键词：数据流；聚类；网格；密度 基于密度和网格的数据流聚类研究与实现 r e s e a r c ha n di m p l e m e n t a t i o no f d a t as t r e a mc l u s t e rb a s e do nd e n s i t y a n dg r i d a b s t r a c t w i mt h er a p i dd e v e l o p m e n to fs c i e n c ea n d t e c h n o l o g y t h ea b i l i t yt oa c q u i r ek n o w l e d g e b e c o m em o r ea n dm o r es t r o n g e r i nr e c e n ty e a r s ，a sw i r e l e s ss e n s o rn e t w o r k s ，t o u t e r sa n do t h e r e q u i p m e n te m e r g e n c e ，p e o p l eh a sm o r ea b i l i t yt og e td a t a a n dw eh a v ean e wd a t am o d e l ：d a t a s t r e a m t m sm o d e ld e a l sw i t hd a t an ol o n g e rs t a t i ca n dp e r m a n e n t l ys t o r e di nm u l t i p l e t b i s m o d e ld e a l sw i t hd a t ai naw a yt h a tv i s i td a t ai no r d e ra n do n eo ral i m i t e dt i m e st ov i s i t n o w r e s e a r c ho nd a t as t r e a mm i n i n g m a i n l yh a sc l u s t e r , c l a s s i f i c a t i o na n df r e q u e n tp a t t e r nm i n i n g a n ds oo n i nt h i sp a p e rw er e s e a r c ht r a d i t i o nc l u s t e r i n gm e t h o db a s e do nd e n s i t ya n dg r i d f o u n dt h a t , t r a d i t i o nc l u s t e r i n gm e t h o db a s e do nd e n s i t yh a st ov i s i td a t am a n yt i m e s a n d t r 乱l i t i o nc l u s t e r i n gm e t h o db a s e do ng r i da l t h o u g hv i s i td a t aat i m ea n dc o u l dq u i c k l y p r o c e s s t h ed a t a , b u ti th a sp o o ra c c u r a c y s ot h et r a d i t i o nc l u s t e r i n gm e t h o db a s e do nd e n s i t ya n d 面d c a r ln o ts a t i s f yt h er e q u i r e m e n t so fd a t as t r e a mc l u s t e r i n g i nt h i sp a p e rw ec o m b i n eo fs o m eo ft h et r a d i t i o n a lc l u s t e r i n ga l g o r i t h m s ，a n da n a l g o r i t h mn a m e dd g t r e e ( d e n s i t ya n dg r i d - t r e ea l g o r i t h m ) i sp r o p o s e d ，w h i c hi sb a s e do n t r e es y n o p s i ss t r u c t u r e t h e r ea r et w op r o c e d u r e si nt h i sa l g o r i t h m ，am i c r o - c l u s t e rc o m p o n e n t a n dam a c r o c l u s t e rc o m p o n e n t i nt h em i c r o c l u s t e rc o m p o n e n tp a r t ，i tm a p se a c hi n p u td a t a r e c o r di n t oat r e e i te l i m i n a t e st h ee f f e c ti m p a c to nt h ec l u s t e r i n gr e s u l t sb yt h ee m p t yg r i d s b e c a u s eo fd a t as t r e a mc l u s t e ro f t e nc o n c e r na b o u tn e w l yd a t a , w ei n 臼o d u c et h et i m ed e c l i n e m o d e l w h i c hc o u l df m dn e w l yc l u s t e ri n f o r m a t i o n 硼1 em a c r o c l u s t e rc o m p o n e n tc o m p u t e s t h et r e e sl e a f n o d e sd e n s i t ya n dc l u s t e r st h el e a f n o d e sb a s e do nt h ed e n s i t y i tc o u l df i n dn o i s e n o d e sb ys e t t i n gn o i s ed e n s i t yt h r e s h o l df u n c t i o na n dr e d u c et h ec o m p u t a t i o nb ys e t t i n gu p d a t e c y c l e e x p e r i m e n t so nd a t as e tk d dc u p9 9e v a l u a t i o nh a v es h o w nt h a tt h i sa l g o r i t h mi sm o r e e f f i c i e n c yt h a nd b s c a na n dc l u s t r e a m k e yw o r d s ：d a t as t r e a m ；c l u s t e r ；g r i d ；d e n s i t y i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：基王蜜廑塑圆整数数握流鬈娄珏究生塞丑 作者签名：至叠纽： 日期：迎2年上l 月互l 日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：基王蜜度塑圆整鲍数握流鐾娄盟究皇塞塑 作者签名：圣氢纽日期：迎2年j 尘月j 坠日 导癖签名： 亟墨 日期：生2 年卫月兰l 日 大连理王大学硕士学位论文 1 绪论 1 。1 研究背景及意义 近些年来，数据挖掘引起了信息产业界的极大关注，其主要原因是因为存在大量的 数据，可以广泛使用，并且迫切的需要将这些数据转换成为有用的信息和知识。获取的 信息和知识能广泛的应用于各种应用。 数据挖掘包括了关联分析、分类和预测、聚类分析、孤立点分析、演变分析等等方 面。其中的聚类分析是一种探查数据结构的工具。聚类分析的核心是聚类疆j ，鄄将对象 划分为簇，使得同一个簇的对象相似，而不同簇的对象相异。对象可以通过某些度量( 如 属性、特征) 或与其他对象的关系( 铡如，题离、相似性) 来攒述。聚类过程将物理或抽象 对象的集合划分成为了类似的元素组成的多个簇，簇里包含了所有相似的元素，这些元 素与同个簇中的元素彼此相似，与其他簇中的元素相异。 聚类分析是种重要的人类行为。聚类分析于分类和预测不同，聚类分析数据对象， 而不考虑已知的簇标记。一般情况下，训练数据中不提供簇标记，因为不知道从何开始。 聚类可以属于产生这种标记。对急捌增长的数据加以组织和从数据中学习有价值信息的 需要，使得聚类成为一个非常活跃的研究领域。聚类分析已经广泛地用在许多应用中， 包括人工智能、生物学、客户关系管理、数据压缩、数据挖掘、信息检索、图像处理、 机器学习、市场营销、模式识别、心理学和统计学等。数据聚类正在蓬勃发展，在商务 上，聚类能帮组市场分析人员从客户的基本库中发现不同的客户群，并且用购买模式开 刻画不同的客户群的特征。在生物学领域，聚类被用来依据五种特征舀动建立物种分类， 对基因进行分类，获得对种群中固有结构的认识。聚类分析也能用于对w e b 上的文档 进行分类，越发现信息。作力一个数据挖掇的功能，聚类分析裁作为一个独立的工具来 获得数据分布的情况，观察每个簇的特点，集中对特定的某些簇做进一步的分析。 科学技术的飞速发展的今天，人类所能获褥的知识和信息越来越多。近些年来随着 无线传感器网络、路由器等设备的蹴现，人们所能得到的数据量是越来越多成倍增长。 在现实生活中，人们经常需要处理海量的数据，一般情况下，这些数据以很快的速度无 体丘地产生。例如，一个大型的超市，每天都能收到上百万条的交易记录和物晶买卖记 录，而电讯电话公司大型交换机上每天记录的通话记录高达几千万条。对于这些数量巨 大，产生的速度很快的数据，对其按照传统的数据瘴应用模式进行处理，即完整、详细 地收集这些数据，将其清洗后储存在数据库中，再交由计算机仔细处理已不再可能。为 了分析管理这种数据，人们提出了新的数据模型。这种数据模型被命名为数据流 基于密度和网格的数据流聚类研究与实现 ( d a t a s t r e a m ) 。数据模型最大的特点是：待处理的数据不再被静态、固定地存储在可多 次、随机访问的介质中，而是以一种动态、流式的形式出现。访问数据的方法被限定为 进行顺序的、一次或有限次的访问。因此数据流可以被定义为实时的，连续的并且有序 的数据记录序歹u t 2 1 。所以原来许多成熟的数据挖掘、数据分析和数据查询技术在数据流 上便得不再适用了，需要提出新的解决方法。因此，数据流的问题一出现马上引起了研 究界的重视，出现了很多研究成果，对数据流从管理、查询、分析与挖掘等多个方面进 行了研究。数据流挖掘技术作为数据挖掘领域的新问题，很多挖掘算法需要针对数据流 进行改造。流聚类分析作为数据流挖掘的一个重要研究方向，同样面临着巨大的挑战， 也引起了研究者们的广泛关注。 目前大都认可的提出了处理数据流的算法的一般标准【3 j ： ( 1 ) 对数据流中每条记录的处理必须在很小的固定时间内。 ( 2 ) 处理过程中对内存的占用必须是有限的，与算法已经读入的数据量记录没有关 系。 ( 3 ) 只能对数据进行一次扫描；因为在大多数应用中，数据是连续的，到来的速度 很快，根本没有时间去访问以前的数据。 ( 4 ) 它必须能在处理的任何一个阶段输出一个可用的得数据进行描述的模型。 ( 5 ) 在任何时间点上，模型都必须是最新的，必须能够实时地反映数据集当前的最 新变化。 ( 6 ) 它还要在用户需要的时候进行演化分析。 其中前两个标准是最为重要并且最难做到的，大多数己有的方法面临着效率和可扩 展性的挑战。这些算法的内存需求量是随数据量增加而增大的，并且计算复杂性远超过 线性，这样的算法无法用于数据流领域，因为在某一时刻内存将会耗尽或者处理过程将 落后于数据的到来，导致算法失效。因此人们开始致力于设计新的适用于数据流模型的 算法。 1 2 国内外研究现状 作为数据挖掘的延伸，面向数据流的数据挖掘( 简称为数据流挖掘) 已成为当前研究 的热点问题，在网络监控，交通工程，电信记录管理与分析，商业交易管理与分析，金 融信息监控等众多领域有着广泛的应用前景，具有非常重要的现实意义。数据流聚类是 数据流挖掘的一个重要的研究方向。与国外相比，国内的研究仍处于起步阶段。 大连理工大学硕士学位论文 目前关于数据流挖掘的研究方向主要有数据流聚类算法的研究、数据流分类算法的 研究、数据流频繁项挖掘的研究和多数据流关联分析的研究。 ( 1 ) 数据流的聚类算法研究 第一个以数据流为分析对象的聚类算法是由s u d i p t og u h a 等提出的s t r e a m t 4 】算 法。这种算法根据分治原理，使用一个不断迭代过程实现有限空间对数据流进行k - m e a n s 聚类。但上述算法无法处理演化的数据流。a g g a r w a i 在总结上述方法本质缺陷的基础上 提出了一个数据流聚类框架c l u s t r e a m 5 1 。其核心思想是将聚类过程分为在线和离线两个 阶段。在线部分的任务是存储数据流的汇总结果，生成一种称为微聚类的信息存储结构， 并按金字塔式时间结构将中间结果进行保存。离线部分既是根据用户指定的观察时段及 聚类数量，快速生成聚类结果的过程。 近年来许多学者围绕c l u s t r e a r n 框架进行了大量的研究。a g g a r w a d 等后续提出了专 门针对高维连续属性数据流的h p s t r e a m l 6 算法。该算法引入了子空间聚类，并提出了具 有遗忘特性的聚类结构。c a o 等人提出了基于密度的两阶段聚类方法。o r d o n e z 提出了 k _ m e a n s t j 算法的变体以聚类二元数据流。o n g 等人根据c l u s t r e a m 提出了用标属性频度 作为微聚类描述处理属性的算法。最近，y a n g 等人提出了一种针对混合属性数据流的 聚类算法。 ( 2 ) 数据流分类算法研究 数据流分类算法主要是p d o m i n g s 和g h u l t e n 的研究成果一种是改造的h o e f f d i n g 决策树分类算法v f d t 8 1 ，使用恒定的内存大小和时间处理每个样本，有效地解决了时间、 内存和样本对数据挖掘，特别是高速数据流上的挖掘的限制。v f d t 使用信息熵选择属 性，通过建立h o e f f d i n g 树来进行决策支持，并使用h o e f f d i n g 约束来保证高精度地处理数 据流。既可连续处理数据，也可通过二次抽样，重新扫描数据集，因此可以处理非常庞大 的数据集。另一种对v f d t 算法引入了滑动窗口技术，提出了c v f d t t g l 算法。保留了 v f d t 算法在速度上和精度上的优点，增加了对数据产生过程中变化趋势的监测，使算 法更好的适应对高速、随时间变化数据流的分类。 ( 3 ) 数据流频繁项挖掘 m a n k u 等人提出一个近似的数据流频繁项挖掘算法，该算法采用的是数据流的界标 模型，在整个数据流上进行计算。g i a n n e l l a 等人将其扩展到数据流的时间窗口模型上， 实现了多时间粒度的频繁项挖掘。 ( 4 ) 多数据流关联分析 关联度计算。关联度计算指在多条数据流中，计算每对数据流之间的关联系数， 从而发现具有高的正关联或负关联的数据流对。z h u 等人实现的s t a s t r e a m 系统通过使 基于密度和网格的数据流聚类研究与实现 用离散傅立叶变换的保距特性与系数的对称特性，推导出数据流对傅立叶变换系数之间 的距离与关联系数之间的关系。s a k u r a i 等人提出了一种滞后关联的计算。 主分量计算。g u h a 对多条数据流组成的矩阵作奇异植分解( s v d ) 分析来计算主 分量。p a p a d i m i t r i o u s 提出了基于自适应过滤技术来实现一个增量式的主分量获取算法。 多数据流聚类。多数据流聚类就是对多条数据流进行聚类分析，发现彼此间相似 的数据流。y a n g 采用数据流的界标模型讨论了如何减少每个时刻需要计算的数据流对 之间的距离。d a i 提出了一个滑动窗口模型下的多数据流聚类方法。 1 3 本文的工作 本文研究的是基于网格密度的数据流聚类。首先，对各种数据流聚类模型做详细的 介绍，其次，针对不同的概要数据结构优缺点，提出了一种树形概要数据结构。然后对 基于密度和网格的数据流聚类模型进行详细介绍。在树型概要结构的基础上提出了密度 网格树数据流聚类算法d g t r e e ( d e n s i t ya n dg r i d t r e ea l g o r i t h m ) 。该算法利用数据流 聚类算法c l u s t r e a m 中的处理框架，把聚类分为微聚类和宏聚类两个过程。在微聚类过 程中，通过把数据流按属性值分配到一棵树中，消除了空网格对聚类结果的影响，同时 针对数据流聚类中，近期的数据往往比久远的数据更受关注的特点，引入了时间衰退模 型；在宏聚类过程中，对微聚类中生成的树中的叶子节点进行密度聚类，通过设立噪音 密度阀值函数和更新周期，不仅可以有效的发现噪音叶子节点，还减少了密度聚类中对 叶子节点密度更新的计算量，减少了算法的时间消耗。 1 4 论文的组织 第l 章，对数据流的起源、发展现状和趋势进行了全面的介绍。指出了传统数据流 聚类的缺陷和当前的研究状况。 第2 章，研究了现有的聚类算法。分析各个聚类的特点，比较各个聚类算法的优缺 点。 第3 章，通过研究现有的数据流挖掘的概要数据结构的优缺点，提出一种树形结构 的数据概要结构。 第4 章，在第三章提出的树形概要结构的基础上，提出了d g t r e e 数据流聚类算法， 并给出算法的具体描述和实现。 第5 章，通过算法的性能分析和实验数据的分析，验证d g t r e e 算法有很大的实际 应用性。 大连理工大学硕士学位论文 2 数据流聚类技术 2 1 数据流模型 数据流是一个以一定速度连续到达的数据项序列，x ，f ，”, x n ，这个数据项序 列只能按下标f 的递增顺序读取一次。数据流是现象驱动的，其速度与数据项到达的次 序无法被控制。数据流通常具有潜在无限的体积，且数据可能的取值是无限的，处理数 据流的系统无法保存整个数据流。而数据流的在线处理要求又使系统无法进行代价昂贵 的磁盘存取。因此，数据流中的数据项在被读取一次之后，就被丢弃，以后不可能再读 到。在实际应用中，某些超大型的静态数据集要求处理算法只能进行一次线性扫描以降 低算法的处理代价。此时，算法的输入也可看作是一种数据流。 目前，在数据流研究领域中存在许多种不同的数据流模型。不同的数据流模型适用 于不同的场合，需要设计不同的处理算法。可以分别按照数据流中的数据描述现象的方 式和算法处理数据流时采用的时序范围对这些模型进行划分。 设数据流中的数据项研，丸而，依次按下标顺序到达，它们描述了一个信号彳。 按x ，描述信号彳的方式数据流模型可以分为以下几类【1 0 】： ( 1 ) 时序( t i m es e r i e s ) 模型：么吲= x i 。此时，数据流中的每一个数据项都代表一个 独立的信号。 ( 2 ) 现金登记( c a s hr e g i s t e r ) 模型：令x f = 妣) ，且五 = o ，则a ，叨= 么卜，叨+ 五。此时， 数据流中的多个数据项增量式地表达一个彳阴。 ( 3 ) 十字转门( t u m s t n e ) 模型：令x i = 抗砩) ，则a i f j = a 扣，们+ 以。其中，“可以为正 数，也可以为负数。此时，数据流中的多个数据项表达一个爿阴。彳阴随着数据的流入， 可能会增加，也可能会减小。 在这3 种模型中，t u r n s t i l e 是最具一般性的数据流模型，其适用范围最广，也最难 处理。数据流分类与聚类通常使用的时序模型，它们将数据流中的每一数据项看作一个 独立的对象。若将4 阴记为信号，出现的次数，则数据流频繁模式挖掘通常使用的是c a s h r e g i s t e r 模型，只允许数据的插入。也有算法研究了同时存在数据插入和删除时的数据 流频繁模式挖掘问题。 2 2 常用的聚类算法 图2 1 展示了常用聚类算法之间的层次关系。 基于密度和网格的数据流聚类研究与实现 图2 1常用聚类算法之间的层次关系 f i g 。2 1 t h eh i e r a r c h yo f c o m m o nc l u s t e r i n ga l g o r i t h m s 下面将对常用的聚类算法做简单的介绍。 ( 1 ) 基于划分的算法 划分方法：给定一个拧个对象或元组的数据库，一个划分方法构建数据的k 个划分， 每个划分表示一个簇，并且舡嘲。也就是说，它将数据划分成为k 个组，同时满足如下 要求： 第一，每个簇至少包含一个对象。 第二，每个对象必须属于且仅属于一个簇。 划分聚类在一步中就产生所有的簇，而不要几个步骤。虽然在算法内部可以产生几 个不同的簇，但划分聚类的结果只产生一个簇集。由于仅有一个簇集作为输出，所以用 户必须事先给出聚类的数目k ，还需要用度量函数或者准则函数来判定所给出的解的优 劣程度。 给定要创建的划分的数目k ，首先创建一个初始划分；然后利用一个循环定位技术 通过将对象从一个划分移动到另一个划分来改善划分质量。典型的划分方法包括：k 均 值、肛m e d o i d s 【l l 】、c l a r a f l 甜、c l a _ r a n s f l 3 】等。算法流程如图2 2 算法 输入 输出 方法 肛均值。划分的k 均值算法基于簇中对象的平均值。 簇的数目k 和包含栉个对象的数据库。 k 个簇，使得平方误差准则最小。 s t e p l ：任意选择k 个对象作为初始聚类的簇中心； 大连理工大学硕士学位论文 s t e p 2 ：根据簇中对象的平均值，将每个对象( 重新) 赋给最类似的簇； s t e p 3 ：更新簇的平均值，即计算每个簇中对象的平均值； s t e p 4 - 如果每个簇中对象的平均值还发生变化，r e p e a ts t e p 2 ； s t e p 5 ：算法结束。 图2 2 基于划分的聚类算法思想 f 远2 2 t h e t h i n k i n go fc l u s t e r i n ga l g o r i t h mb a s e do np a r t i t i o n i n gm e t h o d 划分算法一般要求所有的数据都装入内存，限制了它们在大规模数据集上的应用； 它们还要求用户预先指定聚类的个数，但在大多数实际应用中，最终的聚类个数是未知 的；另外，划分算法只使用某一固定的原则来决定聚类，这就使得当聚类的形状不规则 或者大小差别很大时，聚类的效果不是很好。 g u h a 等扩展了珏平均算法来处理数据流。他们提出的算法仅仅使用单遍扫描，并 且需要存储空间相对较少。算法的时间复杂度和空间复杂度分别为o ( n k ) 和o ( r z ) ，其中 n 是数据元素的个数、k 是簇中心点的个数，e ：q ) 。 j _ i * l 从统计学的观点来看，聚类特征是对给定子聚类的统计汇总：子聚类的0 阶矩，1 阶矩，以及2 阶矩。它记录了计算聚类和有效利用存储的关键度量，因为它汇总了关于 子聚类的信息，而不是存储所有的对象。 一个c f 树是高度平衡的树，它存储了层次聚类的聚类特征。根据定义，树中的非 叶子节点有后代或“孩子，它们存储了其孩子的c f 的总和，即汇总了关于其孩子的 聚类信息。一个c f 树有两个参数：分支因子召，和阀值兀分支因子定义了每个非叶 子节点孩子的最大数目，而阀值参数给出了存储在树的叶子节点中的子聚类的最大直 径。这两个参数影响了结果树的大小 b i r c h 算法工作包括两个阶段： 阶段一：b i r c h 扫描数据库，建立一个初始存放于内存的c f 树，它可以被看作数 据的多层压缩，试图保留数据内在的聚类结构。 大连理工大学硕士学位论文 阶段二：b i r c h 采用某个聚类算法对c f 树的节点进行聚类。 在阶段一，随着对象被插入，c f 树被动态地构造。所以这个方法支持增量聚类。 一个对象被插入到最近的叶子条目( 子聚类) 。如果在插入后存储在叶子节点中的子聚类 的直径大于阀值，那么该叶子节点即可能有其他节点被分裂。如果存储c f 树需要的内 存大于主存的大小，可以定义一个较小的阀值，并重建c f 树。重建过程从旧树的叶子 节点建一个新树。这样，重建树的过程不需要重读所有的对象。这类似于b + 树构建中 的插入和节点分裂。因此，为了建树，只需要读次数据。采用一些启发式规则和方法， 通过额外的数据扫描来处理孤立点和改进c f 树的质量。 b i r c h 试图利用可用的资源来生成最好的聚类结果。给定有限的主存，一个重要 的考虑是最小的i o 时间。b i r c h 采用了一种多阶段聚类技术：数据集合的单边扫描产 生了一个基于的聚类，一或多遍的额外扫描可以进一步的改进聚类质量。这个算法的计 算复杂性事o ( 聆) ，这里的胛是对象的数目。 ( 3 ) 基于密度的算法 基于密度的方法以空间中的一点为中心，单位体积内点的个数称为该点的密度。从 直观上来看，聚类内部点的密度较大，而聚类边界上点的密度较小。基于密度的聚类根 据空间密度的差别，把聚类相似密度的相邻的点作为一个聚类。与其他方法的一个根本 区别是：它不是基于各种各样距离的而是基于密度的。这样就能克服基于距离的算法只 能发现“圆形 类的缺点，以发现任意形状的聚类结果。代表算法有d b s c a n i s 】算法， o p t i c s 1 6 j 算法，d e n c l u e t l 。7 】算法等。 d b s c a n 算法是一个基于密度的聚类算法。该算法将具有足够高密度的区域划分为 簇，并可以在带有噪音的空间数据库中发现任意形状的聚类。它定义类为密度相连的点 的最大集合，在这个算法中使用了e p s 和m i n p t s 两个全局变量。d b s c a n 算法利用类的 密度连通性可以快速发现任意形状的类。对于一个类中的每个对象都是相应的密度可达 对象。密度可达对象的获取是通过不断执行区域查询来实现的。为了有效地执行区域查 询，d b s c a n 算法使用了空间查询r 幸树结构。r 奉树的建立非常消耗时间。当数据量非 常大时，就必须有大内存量支持，i o 消耗也非常大。其时间复杂度为o ( n l o g n ) ( n 为数 据量) ，聚类过程的大部分时间用在区域查询操作上，并且对于参数的设置通常是依靠 经验，难以确定。尤其是对于真实的高维数据集合而言o p t i c s 算法克服了d b s c a n 算 法的缺点，是一种顺序聚类的方法。o p t i c s 没有显式地产生一个数据集合，它为自动 和交互的聚类分析计算一个类秩序。这个秩序代表了数据的基于密度的聚类结构。它包 含的信息，等同于从一个宽广的参数设置范围所获得的基于密度的聚类。 d e n c l u e 是基于一组密度分布函数的聚类算法。该算法主要基于下面的想法【l 】： 基于密度和网格的数据流聚类研究与实现 每个数据点的影响可以用一个数学函数来形式化地模拟，它描述了一个数据点 在邻域内的影响，被称为影响函数。 数据空间的整体密度可以被模型化为所有数据点的影响函数的总和。 然后聚类可以通过确定密度吸引点来得到，这里的密度吸引点是全局密度函数 的局部最大。 ( 4 ) 基于网格的算法 基于网格【l8 】的方法是采用了一个多分辨率的网格数据结构。它首先将数据空间量化 为有限个单元，这些单元形成了的网格结构所有的处理都在网格上进行。这样处理的 主要优点就是处理速度块，通常这是与目标数据库中记录的个数无关的，只与把数据空 间分成多少个单元有关。代表算法有s t i n g 挎博法、c l i q u e 算法、w a v e 。c l u s t e r 2 0 】 算法。 s t i n g 算法是一种基于网格的多分辨率的聚类技术【l 】，它将空间区域划分成为矩形 单元，针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层 次结构、高层的每个单元被划分为多个低一层的单元，关于每个网格单元属性的统计信 息被事先计算和存储，这些统计参数对于查询处理是有用的。 s t i n g 有几个优点： 由于存储在每个单元中的统计信息提供了单元中的数据不依赖与查询的汇总信 息，所以基于网格的计算是独立于查询的： 网格结构有利于并行处理和增量更新： 该方法的主要优点是效率很高，s t i n g 扫描数据库一次来计算单元的统计信息， 因此产生聚类的时间复杂度是o ( n ) ，其中r l 是对象的数目。在层次结构建立后，查询处 理时间是d ( 妙，这里g 是最低层网格单元的数目，通常远小于刀。 由于s t i n g 采用了一个多分辨率的方法来进行聚类分析，s t 烈g 聚类的质量取决 于网格结构的最低层的粒度。如果粒度比较细，处理的代价会显著增加：但是如果网格 结构最低层的粒度太粗，将会降低聚类分析的质量。而且，s t i n g 在构建一个父亲单元 的时候没有考虑孩子单元和其相邻单元之间的关系。因此，结果簇的形状是i s o t h e t i c ， 即所有的聚类边界或者是水平的，或者是竖直的，没有对角的边界。尽管该技术有快速 的处理速度，但可能降低簇的质量和精确性。 c l i q u e 可以自动地发现最高维的子空间，高密度聚类存在于这些子空间中。 c l i q u e 对元组的输入顺序不敏感，无需假设任何规范的数据分布，它随输入数据的大 大连理工大学硕士学位论文 小线性地扩展。当数据的维数增加时具有良好的可伸缩性，但是，由于方法大大简化， 聚类结果的精确性可能会降低。 w a v e c l u s t e r 是一种多分辨率的聚类算法，它首先通过在数据空间上强加一个 多维网格结构来汇总数据，然后采用一种小波变换来变换原特征空间，在变换后的空间 中找到密集区域。在该方法中，每个网格单元汇总了一组映射到该单元的点的信息，这 种汇总信息适合于在内存中进行多分辨率小波变换使用，以及随后的聚类分析。 ( 5 ) 基于模型的方法 基于模型的聚类方法试图优化给定的数据和某些数学模型之间的适应性。这样的方 法经常基于这样的假设：数据是根据潜在的概率分布生成的。基于模型的方法主要有两 大类：统计学方法和神经网络方法【2 1 1 。 概念聚类【l 】是机器学习中的一种聚类方法，是用描述对象的一组概念取值复合表达 式将数据划分为不同的类，而不是基于几何距离来实现数据对象之间的相似性度量。概 念聚类的特点在于能够对输出的不同类确定其属性特征的覆盖( 称作外延) ，并对聚类结 果给予概念解释( 称作内涵) 。根据对概念属性范化和特化处理的程度不同，可以得到概 念的多个层次描述。另外，概念聚类还适用于处理增量式数据挖掘，当有大量新的数据 加入时，不需要对原有的数据重新进行聚类处理。 概念聚类的绝大多数方法采用了统计学的途径，在决定概念或聚类时使用概率度 量。概率描述用于描述导出的概念。 c o b w e b 是一种流行的简单增量概念聚类算法。它的输入对象用于分类属性值对 来描述。c o b w e b 以一个分类树的形式创建层次聚类。 神经网络方法将每一个簇描述为一个标本，标本不一定对应一个特定的数据对象。 根据某些距离度量，新的对象可以被分配给标本与其最相似的簇。被分配给一个簇的对 象的属性可以根据该簇的标本的属性来预测。神经网络聚类的两个比较著名的方法一个 事竞争学习( c o m p e t i t i v el e a r n i n g ) 和自组织特征映射。 竞争学习【l 】，采用了若干个单元的层次结构，他们以一种w i n n e r - t a k e a l l 的方式对 当前系统中的数据对象进行竞争。在一个簇中获胜的单元称为活跃的，而其它的是不活 跃的。在某个给定层次中的单元可以接收来自低一层次所有单元的输入，并且同一层次 中的单元彼此之间存在竞争，簇中只能有一个单元是活跃的，这就是“w i n n e r - t a k e a j l ” 的意思。获胜的单元修正它与簇中其它单元连接上的权重，以便未来它能够对当前一样 或相似的对象做出反应。如果将一个权重看作一个定义一个标本，那么新的对象被分配 给具有最近标本的簇。在聚类过程结束后，每个簇可被看作一个新的特征，它检测对象 的某种规律性。这样，产生的结果簇可以被看作一个低层向高层特征的映射。 基于密度和网格的数据流聚类研究与实现 自组织特征映射聚类也是通过若干个单元竞争当前对象来进行的。权重向量最接近 当前对象的单元成为获胜的或者活跃的单元。为了更接近输入对象，对获胜单元及其最 近的邻居的权重进行调整。自组织特征映射假设在输入对象中存在一些拓扑结构或顺 序，单元将在空间中呈现这种结构。单元的组织形成一个特征映射。自组织特征映射被 认为类似于大脑的处理过程，对二维或三维空间中可视化高维数据是有用的。 神经网络聚类方法与实际的大脑处理有很强的理论联系。由于较长的处理时间和数 据的复杂性，需要进行进一步的研究来使它适用于大型数据库。 2 3 几种常用聚类算法的比较 对于上述聚类算法可以从六个方面对其性能进行比较。 ( 1 ) 可伸缩性 一些算法在处理小规模的数据集上有很好的聚类效果和较少的时间消耗，但在大规 模的数据集上却不能得到很好的聚类效果，因此能否满足大数据集的聚类要求也是是考 察算法性能的一个方面。 ( 2 ) 处理不同类型属性的能力 现在的一些聚类算法对二维数据有很好的聚类效果，但换到其它类型的数据集( 如 混合数据集、序数型据集) 后却得不到很好的聚类效果。由于聚类算法的应用范围不断 地增大，也要求其能处理不同类型属性的数据。 ( 3 ) 发现任意形状的簇 某些基于距离的聚类算法只能发现具有相近尺度的球状簇，而算法能否发现其它形 状的簇是非常重要的，因此能否发现任意形状的簇也是聚类算法一个重要的性能。 ( 4 ) 处理噪声数据的能力 实际应用中经常会在数据集中发现一些和有效信息数据不相关联的噪音数据，包括 孤立点、空缺、未知数据或错误等，一个聚类算法能否剔除这些噪音数据对聚类的干扰， 从而获得正确的聚类结果也是一个评价聚类算法性能的标准。 ( 5 ) 对输入顺序的敏感性 对输入数据顺序的敏感性，是指算法能否与顺序无关，即无论以什么样的顺序输入 数据，都能得到正确的聚类结果。 ( 6 ) 处理高维数据的能力 大连理工大学硕士学位论文 随着数据挖掘的发展，特别是数据流这一数据类型的出现。聚类算法越来越多地处 理一些高维的数据集，这些数据集通常面临维度高而且非常稀疏等特点。能否处理这种 类型数据，是体现一个聚类算法应用范围是否宽泛的因素。 ( 7 ) 许多算法需要用户在聚类前输入一些和聚类结果密切相关的参数，往往这些参 数都很难确定。通常只能按照经验来输入，特别是包含高维对象的数据集。这不仅构成 了用户的负担，而且也使得聚类质量难以控制。因此需要由用户决定的输入参数的多少 也是聚类算法性能需要考虑的一点。比较各种聚类算法的性能如表2 1 所示。 表2 1 聚类算法比较 t a b 2 1 c o m p a r i s o no fc l u s t e r i n ga l g o r i t h m s 2 4 几种常用的聚类质量评价方法 评价一个聚类算法结果好坏的度量方法主要有两个。一个是紧密度，它指的是簇内 成员相靠的紧密程度。一个簇内的成员应该尽可能的相互靠近。另外一个度量方法是分 离度。分离度要求簇与簇之间的距离尽可能的远。簇与簇之间的距离越远则聚类的结果 就越好。大多数评价聚类质量的方法都是基于这两个原则。目前聚类质量的度量方法大 致可分为外部度量、内部度量和相对度量3 大类圈。对以这几种度量方法都有其适用的 范围，其中使用最广泛的度量方法就是内部度量方法。 ( 1 ) 内部度量 基于密度和网格的数据流聚类研究与实现 如果一个数据集原本的结构不知道的话，聚类结果的评价就只能仅仅从所得的结果 中来考察评价。对结果的考察只能通过考察期紧密度和分离度两个参数来度量。此外还 要考虑单个簇的大小以达到均衡较好的解。一般来说，使用簇内方差来评价聚类的质量。 用簇内方差即误差平方或最小方差标准，寻求簇内距离最小化。定义为公式( 2 2 ) 。 y ( c ) = 艿( f ，七) 2 ( 2 2 ) 其中c 为所有的簇，七从是簇c 的质心，万( f ，i ) 为距离函数，计算数据点f 与 其对应的簇中心的距离。簇内方差最小值取决于簇的数目，最佳聚类质量的期望为零， 即其值越小，聚类质量越好。 ( 2 ) 外部度量 是指聚类分析对数据集的结构有一个正确的了解，所得到的簇的个数和每个簇里所 包含的数据的个数同的正确的聚类的簇个数和每个簇内正确的数据点的个数相比较。在 这种情况下忽略划分的期望特征，只注重所得簇的分配的有效性，评价变得很直接。 如果已知数据的结构，那么能否得到正确数目的簇个数将是算法性能考虑的首要因 素。现在许多聚类算法需要将簇的数目作为算法的输入参数，而且所输入的簇的数目会 极大地影响聚类分析性能的度量。目前普遍使用的规则是c 一甩，c 雠是最大聚类 数，力为数据集中的数据对象数。 下面两个度量所产生的簇与正确的簇进行比较，评价簇的纯净度与完整度。 簇g 的纯净度定义为：根据已知正确簇标识f r ，标识为该簇的数据点个数占 整个簇数据点个数的比例，即公式( 2 3 ) 。 a 暇回= 嗍等 ( 2 3 ) 其中k 是簇c k 的大小，盹是该簇中表示为f 的数量。整个聚类的纯净度尸( c ) 是 所有簇的纯净度的均值，其范围为 o ，l 】，期望为最大化，即纯净度越高，聚类质量越 好。 划分的相对随机性程度可以用聚类熵来评价。聚类考虑各个簇的分布情况，比 考虑使用纯净度更为广泛。一个聚类熵定义为公式( 2 4 ) 。 删一上l o g ( n ) 蒜n k ) ( 2 4 ) 、7 智 一m 。 大连理工大学硕士学位论文 其中整个熵e ( c ) 是所有簇集合的均值，其范围( 0 ，1 】，1 表示各个簇内是均匀分布 的，0 表示各个簇是完全由一个簇内数据组成的纯净簇。最优化分期望划分后得到的熵 能够最小化。 ( 3 ) 相对度量 相对度量是在确定聚类算法的基础上，采用预定义的评价标准，针对该算法不同的 参数设置进行算法测试，最终选择最优的参数设置和聚类模式。常用的方法是：簇内和 簇间的距离度量的线性组合，定义为公式( 2 5 ) 。 s d ( c ) = o s c a t ( c ) + d i s ( c )( 2 5 ) 其中曰是加权参数，s c a t 是簇的平均分散度，d i s ( c ) 是簇件总体分离度。分别定义 为公式( 2 6 ) 和公式( 2 7 ) 。 s c a t (