（计算机应用技术专业论文）处理海量数据的聚类算法关键技术研究.pdf

处理海量数据的聚类算法关键技术研究 抗要 摘要 数据挖掘是从大规模的数据库中抽取非平凡的、隐含的、未知的、有潜在使一 用价值的信息的过程。数据挖掘的快速增长和商业数据库的空前增长速度是分不 开的，它是支持企业决策，处理大量信息的关键步骤之一。聚类分析是数据挖掘一， 中的一项重要技术，它用来发现数据分布和模式。聚类分析是一个无示教的学习 过程。聚类分析在空间数据处理、卫星照片分析、医疗图像自动检测等领域有着 广泛的应用。 本文的贡献主要分为以下几个方面少7 y ，支持度( s u p p o r t ) 为a ，可信度( c o n f i d e n c e ) 为b ，的关 联规则，可以解释为“数据库中的元组有a 满足x 条件，而在这些满足x 条件的元组中有6 0 也满足y 条件。 3 分类 分类( c l a s s i f i c a t i o n ) ，准确地说应该是分类器构造，就是根据训练集 中数据的特征和相应的类标识发现数据特征和类标识之间的关系，构造分类 器的过程。构造的分类器可以应用于以后的分类问题，即对于其它不包括类 标识的数据，分类器可以通过数据的特征决定数据所应具有的类标识。分类 是一个“示教学习”( s u p e r v i s e dl e a r n i n g ) 的过程。分类器可以用多种形 式表示，如分类规则，判定树，数学公式或神经网络。 4 聚类 聚类分析( c l u s t e r i n ga n a l y s i s ) 是数据挖掘中用来发现数据分布和模 式的一项重要技术。聚类是将数据点集合分成若干类( 称为簇，c l u s t e r ) ， 使得每个簇中的数据点之间最大程度的相似，而不同簇中的数据点最大程度 的不同。和分类不同，聚类分析没有训练数据，是一个无示教的学习过程。 5 离群点分析 离群点( o u t l i e r ) 是这样的一些数据对象，它们与数据集具有的一般特性 或模型不一致。然而在一些应用中，它们恰恰是要发现的重要信息，如欺骗 检测，就是要发现这些不同寻常的数据。 6 演变分析 演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的规律或趋势，并 对其建模。它可能包括了上面提到的这些技术，然而演变分析的侧重点在于 时间序列数据分析，或周期模式匹配和基于类似性的数据分析。 处理海量数据的聚类算法关键技术研究 引言 由于数据挖掘涉及了机器学习，统计学，模式识别等学科的数据分析技术， 因此在上面提到的这些挖掘操作中经常会用到以下的技术 b s 9 7 ： 基于统计的方法如贝叶斯方法，贝叶斯网方法等； 决策树方法很多分类算法都采用决策树方法： 神经元网络方法按照生理神经网络结构的模型，通过学习进行模式识别， 有些分类算法使用神经元网络方法； 最近邻方法包括很多聚类算法； 遗传算法基于进化理论，并采用遗传结合，遗传变异以及自然选择等设计 方法的优化技术，遗传算法一般被用来发现最优的模型； 规则归纳方法很多链接分析方法都是规则归纳方法。 1 4 有待解决的问题 考虑挖掘方法，处理性能，能够处理的数据类型等各方面，现有的数据挖掘 方法还存在以下的一些问题： 算法的有效性和可伸缩性数据挖掘要处理的对象可能是g b 级甚至t b 级的 数据，对于大型数据库，数据挖掘算法的运行时间必须是可以预计和可以接受的， 因此挖掘算法必须能够高效地处理存在于数据库系统或者数据仓库中的数据； 复杂数据的处理实际应用中，数据挖掘所要处理的数据质量不能保证，数 据的形式可能不规则，维数可能很高，某些值可能缺失，挖掘方法必须能够对实 际运用中出现的复杂数据进行处理； 多粒度的挖掘用户可能需要从不同的抽象层上观察数据和发现模式； 挖掘结果的表示挖掘方法可以利用可视化工具提供直观，简洁的机制表示 大量的挖掘结果信息，如图，表，规则，树，曲线等等，这有助于利用知识进行 进一步的分析； 数据挖掘任务的自动化执行许多挖掘方法需要用户指定些参数，在用户 对数据集不了解的情况下这些参数的值是较难给出的，而这些方法往往对参数比 较敏感，参数的选值很大程度上影响了聚类的结果。因此希望能够在一定程度上 处理海量数据的聚类算法关键技术研究 弓l 言 实现数据挖掘的自动化； 数据挖掘操作的集成很多研究者将数据挖掘算法综合成为集成工具，多种 挖掘操作的结合使用有助于发现有用的模式； 新的数据挖掘操作随着应用的改变，用户可能对不同类型的知识感兴趣， 对数据挖掘操作提出一些新的要求。例如，离群点发现、例外规则的发现等； 数据挖掘工具和数据库管理系统、o l a p 工具、数据仓库系统的集成大量数 据存放在数据库系统或者数据仓库中，在这些系统中已经存在了很多数据管理工 具，利用这些工具可以加速数据挖掘的速度，减小数据移植的代价。 针对不同类型数据的处理在空间数据库、多媒体数据库、面向对象数据库、 w e b 数据库中，数据形式、质量都和传统数据库不同，需要研究针对这些特殊数 据类型的挖掘方法； 处理噪声和不完全数据存放在数据库中的数据可能存在不完全数据或者噪 声。这些对象会影响数据分析过程，导致发现的模式精确性会降低。因此需要考 虑处理这些特殊情况的方法。 1 5 本文组织 本文第一章简要介绍了数据挖掘的背景，第二章是对聚类分析研究的综述， 给出了聚类的基本概念，从各个角度介绍分析了现有的聚类算法。第三，四，五 章则是作者的工作。第三章提出了考虑密度和距离综合因素的聚类算法，使得聚 类算法可以识别任意形状的簇，在聚类的质量上得到提高。第四章提出了聚类树 的概念，以及自动聚类的算法m a c t 。第五章在m a c t 算法的基础上提出了具 有良好可伸缩性的s a c t 算法。文章最后在第六章进行了总结和展望。 竺里塑墨塑塑塑窭耋兰堡差壁垫查堕窒 ：墨i茎!查 2 1 聚类定义 第二章聚类综述 聚类是数据挖掘中用来发现数据分布和模式的一项重要技术。聚类问题可以 这样描述：将数据点集合分成若干类( 称为簇，c l u s t e r ) ，使得每个簇中的数据 点之间最大程度地相似，而不同簇中的数据点最大程度地不同。即： 定义：给定一数据集合矿，v z , ，其中n “= lz ，称为数据 点，根据数据点间的相似程度将数据集合分成k 组：以，巳，( ， c j = v i 27v i ? v i i t i = i 2 k ) a u 。k c ? = v ，讯过程舔为弓襄 类，c 。( i = 1 2 ，k ) 酶为镁， 聚类分析在空间数据处理、卫星照片分析、医疗图像自动检测等领域有着广 泛的应用 s c z 9 8 。 和一些数据挖掘技术不同，在进行聚类分析前用户一般并不知道数据集的特 征。于是，从某种角度看，聚类分析是一种无示教的( u n s u p e r v i s e d ) 学习过程。 所以，在一个广义的数据挖掘过程中，聚类分析往往被作为最初的步骤，用于获 得对于数据分布和聚合特性的初步了解，以在此基础上进行其它数据挖掘操作 ( 例如分类器构造) 。因此，聚类结果的准确性会直接影响到数据挖掘结果的质 量。和其它数据挖掘技术一样，除了准确性以外，聚类分析还要求具有高效性和 良好的可伸缩性( s c a l a b i l i t y ) 。 一个好的聚类分析算法应该具有以下特点： 不依赖于预先的知识 - 发现任意形状的簇 - 参数容易设定 一 聚类分析结果准确 - 处理快速 -良好的可伸缩性 处理海量数据的聚类算法关键技术研究 聚类综述 2 2 聚类算法研究综述 聚类分析是数据挖掘中一项非常重要的技术，研究者们开发了大量的聚类算 法f k r 9 0 ，n h 9 4 ，e k s x 9 6 ，z r l 9 6 ，w y m 9 7 ，a g g r 9 8 ，g r s 9 8 ，h k 9 8 ，h k k m 9 8 ， h u a 9 8 ，s c z 9 8 ，s e k x 9 8 ，t b 9 8 ，x e k s 9 8 ，a b k 9 9 ，b g g + 9 9 ，g r s 9 9 ，h k 9 9 ， k h k 9 9 ，s b g 0 0 】。 我们可以从多个方面对这些聚类分析方法进行分类。下面依次按照聚类分析 所采用的尺度、簇的表示，以及聚类算法的框架这三个方面介绍现有的一些聚类 研究工作。 2 2 1 聚类分析依据的尺度 聚类分析的基础是确定“相似”的概念。这包含两方面的内容： 1 数据点之间的相似概念 2 数据集合之间的相似概念 聚类所使用的尺度可以分为三类：基于距离的，基于密度的和基于连接，超 图的。前两种通常用于欧几里得空间数据的分析，而基于连接的聚类算法通常运 用于多维空间的聚类分析。 基于距离的聚类 基于距离的聚类方法根据数据点之间的距离确定相似概念。数据集合之间的 相似性有以下几种的定义： s i m i l a r i t y ，pt c j c j ) = d i s t a n c e ( f e p i , r e p f ll q s i j a i l a r i t y 。g ( c ：? c i ) = 1 ( n ? 棚i ) e ，j a i s t a n c e ( v ? ? y i ) 0 2 b s i m i l a r it y 。t c i c i ) ：m x d i s t a h o e ( v 。v j ) | v i c i ? v 3 c i t 裔 s i m i l a r i t y 。i ，i c 一? c i ) ：m i n d i s t a n c e ( v 。v i ) lv j c ：? v i c i t 4 、 在( 1 ) 中，r e p ；，r e p j 分别为簇c 。，c ，的代表点，v 。v ，为簇c ，c ，中的数据点。 数据集的代表点通常为它的重心，如k - m e a n s 算法 m a c 6 7 。单个代表点算法中 簇的相似性通常使用定义1 ，可以看到定义2 ，3 ，4 的时间复杂度都为0 ( 1 i g1 ) ，对于大数据量，这三种定义显然是非常低效的。因此虽然后面的三种定 处理海量数据的聚类算法关键技术研究 聚类综述 义更加全局化，但是通常它们并不直接运用到簇之间相似度的定义上。一般在使 用多个代表点表示簇的算法中，可以利用表示簇的代表点r e p 。，r e p ，来代替定义 2 ，3 ，4 中的v 。，v 。 基于距离的方法的优点在于相似性的定义比较容易理解和计算，然而这种方 法对于噪声数据或者离群点( o u t l i e r s ) 比较敏感。而且要计算每一对分属不同 簇的数据点之间的距离，代价较高。一些方法利用多代表点来代替簇，可以减小 计算量，例如c u r e g r s 9 8 。 典型的基于距离的方法有 c u r e g r s 9 8 、b i r c h z r l 9 6 等。 基于密度的聚类 基于密度的聚类方法认为簇是具有相同密度的连通区域。基于密度的方法需 要定义计算密度的单元，并且还都需要定义“高密度区域”的阈值。基于对于密 度的不同计算方法，基于密度的聚类方法又可以进一步分为近邻算法( n n ) 和小方 格算法。 近邻方法如果一个数据点在半径为e ( 用户指定) 的超球范围内有多于k ( 用户指定) 个邻居，那么近邻算法认为该数据点处在高密度区域。由于每一点 的邻居都需要被计算，所以这类方法需要利用空间索引结构，如r 树，x 树， 支持区域查询，计算超球区域内的密度。因为索引结构在维数上的限制，这些方 法通常在维数上没有良好的伸缩性。另外，如果数据量非常大，则会导致频繁的 i 0 。不过，对大多数多维数据集来说，这些方法还是有效的。传统的近邻方法 有d b s c a n e k s x 9 6 、o p t i c s a b k s 9 9 等 小方格方法一些基于密度的方法将数据空间划分为小方格区间，例如 s t i n g w y m 9 7 、w a v e c l u s t e r s c z 9 8 、d e n c l u e h k 9 8 、c l i q u e a g g r 9 8 、 o p t i g r i d h k 9 9 、d b c l a s d x e k s 9 8 等。这些方法一般使用小方格的并来近似表 示簇，因此它只是密度区域的一个近似，从而可能会丧失一些准确性。 基于密度的方法的优点在于对于噪声数据或者离群点( o u t li e r s ) 不敏感。 然而它不能识别一些特殊形状的簇。一个典型的例子是哑铃形状的簇的识别。 处理海量数据的聚类算法关键技术研究 聚类综述 基于连接、超图的聚类 一些应用当中，聚类的对象存在于高维空间，所以就不能够像在多维空间中 那样定义聚类对象之间的距离关系或者计算聚类对象所处区域的密度。很多算法 针对这种数据定义数据之间的相似度，有：连接( r o c k g r s 9 9 、 c h a m e l e o n k h k 9 9 ) 、超图( a r h p h k k 9 8 ，b o g + 9 9 、p d d p b g g + 9 9 、s t i r r g k r 9 8 ) 等。 基于连接，超图的聚类方法把聚类对象映射为图模型或者超图模型，然后根 据边或者超边寻找高连通度的节点集合。图模型和超图模型的差别在于图模型反 映了节点对之间的相似性，而超图通常反映了某些节点一起出现的信息。r o c k 和c h a m e l e o n 算法使用了图模型，而a r h p ，p d d p ，s t i r r 算法使用了超图模型。 基于连接，超图的聚类方法的结果依赖于对连接或者是超边的定义。由于效 率的关系，一般图超图模型方法总是会去掉那些权重较小的边超边，所以得到 的图超图是疏散的。可以看到，为了效率上有所提高，可能会损失一定的精确 度。 对于种属属性数据或者不定长数据，基于连接或者超图的聚类方法能够较好 地反映数据之间的相关程度。但是，这类方法需要把原来的数据映射为图超图 模型，不同的映射方法导致聚类的效果差异很大。 2 2 2 簇的表示 聚类的目的是识别簇，每一个算法都用某种形式代表簇，虽然把每个数据点 都标上一个簇的i d 是一个直接的方法，但是显然这是一个低效的方法。对于簇， 每个聚类算法都会有自己的表示形式。分析现有的各种聚类方法，可以将簇的表 示技术分为四类作讨论，分别是代表点，高密度区域，方格，概率。 代表点 很多基于距离的聚类算法使用一些点来代表簇，这些点称为代表点。代表点 可以是簇中存在的数据点，或者是数据库中不存在的点，如数据集的重心。代表 点技术又可以分为两种：1 ) 单个代表点，通常用簇的重心作为代表点，如k - m e a n s 算法，但是这个计算出来的重心可能在数据集中并不存在，另外还有一种用数据 库中存在的离重心最近的点作为代表点，如k - m e d o i d s 算法。然而单个代表点只 处理海量数据的聚类算法关键技术研究 聚类综述 能定义凸型的簇，另外在小簇旁边的大簇往往会被分割开。因此这种方法不能识 别复杂的簇。2 ) 多个代表点技术，c u r e 使用多代表点来表示一个簇，从而可以 识别复杂形状的簇。c u r e 通过寻找簇中距离当前最近代表点最远的点作为下一 个代表点。这种方法使得代表点能够准确地勾勒出簇的形状。但是，随着簇的复 杂度的提高，代表点的个数也需要增加。而代表点个数的确定仍需要依靠经验， 代表点个数和簇复杂度之间的关系仍然是个要研究的问题。这种方法的优点是只 需要存储远小于整个数据库大小的数据即可表示发现的簇。 高密度区域 一些基于密度的聚类方法使用高密度区域来表示簇，例如d b s c a n e k s x 9 6 、 o p t i c s a b k s 9 9 等。这种方法需要计算核心点( c o r ep o f n t ) ，所谓核心点是指在 一个给定区域中近邻的数据点多于指定阈值的那个点。因此，核心点被用来扩张 一个子簇，算法直到不能够在这些核心点上扩张为止。 高密度区域方法可以发现任意形状的簇，然而计算核心点的代价较高，通常 需要特殊的索引结构，在数据量较大的情况下，会导致效率的降低和频繁的i o 。 方格 也有一些基于密度的聚类方法利用小方格计算密度，同时，它们使用小方格 来近似表示簇。另外一些方法使用小方格得到必要的统计信息，在此基础上作进 一步的处理，它们也使用小方格作为簇的表示的基本单位。使用小方格的方法包 括：s t i n g w y m 9 7 ，w a v e c l u s t e r s c z 9 8 ，c l i q u e a g g r 9 8 ，d b c l a s d x e k s 9 8 和o p t i g r i d h k 9 9 等。 由于这种方法用小方格代表簇，小方格个数远小于数据点个数，所以处理的 数据量大大的减少了，这使得使用这种方法的算法具有可伸缩性；另外，与发现 高密度区域比较，计算小方格的代价要少得多，这是由于小方格是数据无关的， 而高密度区域则依赖于数据分布；另外，像高密度区域一样，小方格可以反映一 定区域内的数据分布信息，虽然这种信息是近似的。 小方格方法能够简洁地表示簇。但是由于小方格本身是对原始数据的近似， 所以这种方法只能在某种精度范围内表示簇，即会丧失某些准确率。另外，当维 数增加的时候，具有近邻关系的数据量会指数级上升，因此使用近邻信息的小方 格方法通常在高维情况下效率很低。 o 处理海量数据的聚类算法关键技术研究 聚类综述 概率 一些方法使用数据点属于簇的概率来表示簇。包括e m d l r 7 7 ，l a u 9 5 、 h u t o c l a s s c s 9 6 等。还有一些方法允许一个数据点属于多个簇，这种方法被称 为软聚类或者模糊聚类，但是这种方法在运行效率上仍不能令人满意 b b 9 8 。 2 2 3 聚类算法的框架 聚类算法的框架一般决定了算法的时间复杂度以及所需要的参数，另外算法 的框架也会影响到聚类所要使用的预处理技术。聚类算法的框架可以分为以下三 种。 优化方法 优化方法通常试图优化某一个特定的尺度。比较典型的优化方法是分区的聚 类方法。分区的方法通过把数据分成高度内聚的组来达到聚类的目的。 其中最具有代表性的k - m e a n s ( 包括它的变体k - m o d e s h u a 9 8 ， k - p r o t o t y p e s h u a 9 8 ) m a c 6 7 ， 和k - m e d o i d s ( 包括p a m k r 9 0 ，c l a r a k r 9 0 c l a r a n s n h 9 4 等) 。 这些算法根据某种原则( 通常是最佳满足某个标准函数) 把数据点分成k 个部分，每个部分就是一个簇。算法要求用户指定最终簇的个数k ，而且k 的准 确度直接决定了聚类结果的质量。但是，在大多数实际的应用里，最终簇的个数 是未知的。另外，这些算法使用某一固定的原则( 比如方差) 来决定簇，这就使 得当聚类对象中存在差别很大( 比如大小，密度等) 的簇时，聚类的结果不能令 人满意。而且，这些聚类方法得到的解往往是局部最优解。 聚合的层次聚类方法 聚合聚类方法属于层次聚类方法，它的聚类过程是从下往上的。 聚合聚类方法通常在聚类开始的时候将数据点或者预处理后的亚簇看作是 子簇，然后不断地合并这些子簇直到得到最终的簇。 聚合聚类方法包括：b i r c h z r l 9 6 ，c u r e g r s 9 8 ，s t i n g w y m 9 7 ， r o c k g r s 9 9 ，c h a m e l e o n k h k 9 9 等。 处理海量数据的聚类算法关键技术研究 聚类综述 聚合聚类方法的时间复杂度至少为0 ( n 2 ) ，其中n 为聚类分析的数据对象规 模。由于在这些方法中，聚类的过程是不断合并子簇的过程，而合并的次数依赖 于聚类开始时的对象个数，所以为了保证处理效率，聚合聚类算法一般不在原始 数据集上进行聚类操作，而是采用取样或者数据分区的预处理技术来减少对象个 数。比如c u r e ，s t i n g 和c h a m e l e o n 在合并操作前都使用了数据分区的技术。另 外一种加速处理的方法是使用特殊的索引结构。b i r c h 使用了c f 树汇总关于子 簇的特征信息；c u r e 使用了k - d 树和堆；r o c k 则使用了t w o l e v e l 堆，等等。 多数情况下，聚合聚类方法不需要用户指定最终簇的个数( k 值) ( 除c u r e 外) 。但是它们大都需要用户指定某个阈值，作为聚类的终止条件。 分裂的层次聚类方法 分裂的聚类方法也属于层次聚类，与聚合聚类方法不同的是，它聚类的过程 是从上往下的。一开始将整个数据集中的数据看作是一个大的簇，然后根据不相 似性不断地分割簇，直到满足终止条件。a r h p h k k m 9 8 ，b g g + 9 9 ，p d d p b g g + 9 9 和o p t i g r i d h k 9 9 都属于这一类。h r h p 使用超图模型，f i t n e s s 大于给定阈值 的子超图被分割出来。而p d d p 和o p t i g r i d 算法则使用超平面分割簇。 同聚合聚类算法相同，分裂方法也需要用户指定终止条件。分裂方法的优点 在于对于图超图模型，已经存在一些成熟的研究成果可以利用 k a k s 9 7 。 处理海量数据的聚类算法关键技术研究 考虑综合因素的聚类算法 第三章考虑综合因素的聚类算法 从第二章的综述分析可以看到，现有的聚类算法各有各的优缺点。由于这些 算法大都只根据一个固定的原则来识别簇，它们往往只能处理某种特定的数据集 合，而对其它数据集合的处理则效果不佳。但是在现实的应用中，数据集合中的 簇之间往往存在着很大的差异，使用单一的相似性原则进行识别往往不能得到理 想的效果。 这一章将介绍一个考虑综合因素的聚类算法，这个算法的特点在于1 ) 综合 考虑了距离和密度进行相似性的度量，因此这个算法可以识别任意形状的簇；2 ) 可以自动消除噪音，识别离群点；3 ) 使用了统计信息，比之传统的聚合聚类算 法，在保持聚类质量的同时大大节省了聚类的时间，算法具有良好的伸缩性：4 ) 用户不必指定最终簇的个数，k ，对于并不了解数据集特性的用户来说k 的指定 通常是困难的。 3 1 两种尺度：密度和距离 密度和距离是聚类分析中最常用的两种尺度，考虑综合因素的算法正是建立 在这两种方法的基础上，并将其有机地结合在起。下面首先简要分析一下这两 种尺度各自的特点。 基于密度的算法，从识别簇的能力上看，它善于识别各种形状的单一密度簇 ( 但不能识别类似哑铃形状的簇，这是由于哑铃中间的连通部分密度相对较小造 成的) 。由于噪声的密度相对要小得多，因此这种方法能够很方便地消除噪声的 影响。然而它需要扫描整个数据库，当数据量大的时候，整个扫描过程将非常耗 时，并且为了存储所有的数据以及密度信息，算法必须使用一些复杂的数据结构， 这些都将引起大量的系统开销和i 0 交换。另外，基于密度的算法需要用户给定 一个计算密度的单元以及某个密度阈值。 而基于距离的算法从识别簇的能力上看，由于可以方便地使用多代表点技 术，它善于识别各种形状的簇。但是随着簇形状的复杂性提高以及数据空间维数 处理海量数据的聚类算法关键技术研究 考虑综合因素的聚类算法 的增加，所需的代表点越来越多。这种方法对噪声数据比较敏感。另外，由于它 的判别原则严格依赖于距离，所以在一些特殊情况下可能会产生错误的结果。例 如，会出现两个簇由于距离较近被合并为一个簇，或者出现一个大的簇被分割开 的情况。基于距离的方法的时间复杂度通常为o ( n z * l o g n ) ( c u r e ) 0 r s 9 8 ，其中 1 3 为聚类操作开始时所要处理的数据量。一般算法在一开始通过取样技术来减少 数据量，然而当数据集增加到超大规模数据库特别是数据仓库时，通过取样得到 的初始子簇数量依然十分大，导致聚类所需要的计算时间是不能接受的。另外， 这种方法用户需要给出终止条件，如最终簇的个数等，而这些对用户来说应该是 透明的。 3 2 h y b r i d 算法 3 2 1 算法框架 h y b r i d 算法采用自底向上的聚合聚类的框架，综合考虑了簇之间的距离和 某个区域内数据点的密度来决定簇的合并。簇的表示使用多代表点技术，算法的 结束取决于用户定义的距离和密度参数。 同时，由于聚合聚类算法对初始数据量的敏感性，算法采取了多重措施来减 小初始亚簇的个数。首先，该方法对所有数据进行随机采样，取样的结果能够比 较完整地体现原来数据集合中的簇特征。然后，根据索引和统计信息，算法把相 对比较集中的数据点划分成小的单元( u n i t ) ，并借此消除噪声( n o i s e s ) 。这些 单元和其它既非噪声又不是很密集的数据点一起构成初始的亚簇。通过随机的取 样和根据统计信息的划分之后，算法要处理的初始亚簇的数目通常远小于原始数 据集中的数据量。 在给出算法之前，先介绍一些在算法中用到的参数和相关定义。算法有三个 参数：m - d i s t a n c e ，m d e n s i t y 和m - d i a m e t e r ，用于定义单元的 i ，相关的一些 定义如下： 定义1 ：两个簇之间的距离是它们的最近的代表点之间的距离 定义2 ：一个簇的直径是簇中最远的两个数据点之间的距离 定义3 ：妒d i s t a n c e 是两个簇之间可能的最小距离 处理海量数据的聚类算法关键技术研究 考虑综合因素的聚类算法 定义4 ：m - d i a m e t e r 是数据集合中掰有簇中最小的瘫径 定义5 ：一个小方格麓数据空间中对角线长度小于m i n i 2 * m d i s t a n c e ， m - d i a m e t e r ) 的方格和其中的数据点。 定义6 ：当一个小方格c 中的所真数据点都属于个簇a 的时候，称小方格c 属 于簇a ，表示为：c a 。 定义7 ：一个小方掺敬密度怒小方撂中的数据点的数量。 定义8 ：m - d e n s i t y 是数据集合中数据点的平均密度。 定义9 ：噪声是密度小于m d e n s i t y 的小方格中的数据点。 葵法的主要步骤是：取榉划分攀元消除噪声专合著簇浚别离群点专标 迎数据，首先绘瞧聚类分振过程中关键的步骡，印簇熬会著，镑码如下： ij c l u s t e r ( m - d i s t a n c e m d e n s i t y ) 2 3 s o r tt h es u b c l u s t e r si nh e a p ； 4 f o fe a c hs u b c l u s t e riw i t hm i n i m u md i s t a n c eb e t w e e nia n di c l o s e s t 5 ， 6 i f ( d i s t a n c e ( i ，i c l o s e s t ) m + m - d e n s i t y ) b e g i n 9 s t o r et h ec e l la sas u bc l u s t e r ；e n d i f 1 0 e l s eb e g i n 1 1 s t o r ee a c hd a t a p o i n ti nc e l la sas u b c l u s t e r ；e n d i f 1 2 e n d f o r 1 3 e n d p r o c 函数第l 、第2 行划分小方格，并计算需要的统计信息( 主要是密度) 。第5 行消除噪声。第6 行到第1 2 行的循环逐个地检查每一个小方格是否是一个单元。 蛭理海量数据韵聚类算法关键技术研究 考虑综合嚣素的聚娄算法 如暴小方掺是单元，鹱壹接把这单元 乍为一个亚簇存款，肇元的存款是睦 构成单 元这一豫簇的代表点组戏。在随后的合著过程中则可以利眉单元的统计信息，扶 恧减小了蔫要处理的数撰量。当小方格不是单元时，蘧数把小方揍中豹每一个数 据点都作为独立的亚簇存放，这些亚簇的代表点就是其中瞧一的数据点。 识掰荜元静过程结束之螽就产生了所有的豫簇，聚类过程就是在这些亚簇的 纂磷土不断送 亍合并，以产生最终煞簇。需要指出的是，需器进行聚类分析酌维 发往往是数据疼中跑较羹要熬维度，丽虽大多是经常查询的维霞。所以往往已经 在这些维度上建立了索弓 。剃用索弓| ，划分小方格秘计算统计信怠的过程可以快 速地完成。 数据标记 出予算法采耀多个代表点来代表一个簇，掰以奁聚类算法结束后，往往瑟求 知道一个数撼点( 除了代表点之夕 ) 是属于冁一个簇瓣，所以需要标记不是代表 点鲍鄄些数攒。 很多算法都有标记数据的过程。传统的标记方法逐个识别每一个数据点是属 予哪一个簇的，占用了大量的时间。和大多数算法不同，由于这个算法使用了小 方格，所以只需要知道小方格所属的簇，就可以标记小方格中的所有的数据瘸于 那个簇，衙小方格中的数据可戬由索日i 信息快速魄得到。同时标记一个小方格中 的所有数据煮可叛极大施提商标记的速度。 3 2 2 棚似性的判定 算法综合考虑了距离和密度作为相似性判定的尺度，距离作为尺度的衡量方 法较为直观，明了，在此不住赘述，在这里麓重介绍h y b r i d 算法是如何在棚似 性判定中运用密度因素的。可以从伪码的第l1 行看到算法通过判断甄个亚簇是 否连通决定是否将它们合并到一起。判断连通与否需要使用小方格的密度信息。 为了解释和说明算法的连通判断方法，首先给出以下甄个定理： 定理l ：一个小方穆中匏数据点不可能属于两个不曩救簇；一个小方格中不可麓 包含蔡个簇中的艨套数攒点。 证明：由小方格静定义得到以上结论。 妊蓬海量数据煎聚类算法关键技术研究 考虑综合因素的聚类算法 定理2 ：小方撂j 属于簇8 ，且帮小方格歹提邻，d e n s i t y o ) k i 媳g - d e v s t l y , 那 么小方格歹也麟予簇8 。 证萌：崮定理l ，小方格j 中的数据点不可能属于两个不同的簇。又由小方格的 定义，小方格j 和中的任意两个数耀点之间的鹾离也小于m - d i s t a n c e ， 所以这擅数据点也不可毹满于两个不同钓簇。又由于密度大于m m d e n s i t y 的小方格歹是鼙元，从丽茭中豹数据点属子菜个簇，所以氇属于簇盘。 根据以上两个定理，判断连通的方法的伪码形式如下： 1t p r o c e d u r ec o n n e c t i v i t y ( c l u s t e ri ，c l u s t e rj ，m d e n s i t y ) 2 b e g i n 3 q u e u e q ； 4 f o re a c hc e l lki nc l u s t e r _ ib e g i n 5 q a d d ( 玲；e n d f o r 6 f o r e a c h n e i g h b o r c e l l l o f c e l l s i nqa n d l n o t i n q 7 b e g i n 8 i f ( d e n s i t y ( 1 ) m + m d e n s i t y ) b e g i n 9 i f ( 1 b e l o n g t o2 = c l u s t e r _ j ) b e g i n 10 r e t u r nt r u e ；e n d i f 1 1 e l s e 1 2 。 b e g i n 1 3 碡。a d d 1 4 。 m e r g e c l u s t e r _ ，1 b e l o n g t o ) ； t5 f o re a c hc e l l 瑚i n b e l o n g t o b e g i n 1 6 q a d d 汹) ；e n d f o r 1 7 e n d e l s e 1 8 e n d f o r 19 r e t u r nf a l s e ； 2 0 e n d p r o c 1 判叛贬簇连邋艇馊用戆主凑数据结梅歪个器天襄窜( 第3 行) ，溺数一开始 憋熙鸯属予亚蔟c l u s t e ：i 豹，l 、方捂敦到驮烈墨藜去。第6 到第1 8 行潮断连通。 处理海量数据鹩聚类算法蓑键技术研究 考虑综台圆索韵聚类算法 投摆定理2 进行刿凝，如暴发玟了一令与队列中小方格楣邻镌小方格，并且它鼹 于c l u s t e r _ 5 , 就波明c l u s t e f l i 秘c i u s c e r 连递，返凰t r u e ( 第1 0 行) 。在 此过程中，不螈合势连通的小方格鞭属螅亚簇( 篱1 4 行) ，以提裹浆类簿法款效 率。如粜检测完所有与队列中期邻盼小方揍，依然没有发现属于c l j s t e rj 蕊，l 、 方格，函数返回f a l s e ( 第1 9 行) 。 3 。3 实验及分析 3 。3 。1 箨法分毒厅 h y b r i d 这个考虑综合因素瓣聚类算法摄撂诱令殛簇之阕翡距离和它们之溺 的遣通关系( 密度) 张判凝是否应该合并。襁是察以蓠翡密发方法不同，在诧通 过麓单地判题小方接的密度来测试逡逶憷，瑟不是搜用复杂翡数据结梅( 如r 霉 树) 或者求最小覆盖。这秘方法楚建立在鼹户对聚类j 砉象兹已有了群稻蒸于距离 的方法同时作用的基础上鲍。由予基于蹬离蛇方法对蔟熬形状蛉准确识别，密度 判断不用顾及有关形状缨节的识别；露瞪利趔怒户对予簇鲍了解，密度判龋窍了 一定的依据，所以在这个算法中的密度判叛蹩一謦中筵化了的密度刿麟，避免了复 杂的数撼结构的维护( 仅仅像存小方格的密度信息) 靼繁琐懿用于决定形状鳃节 的计算。 歪是瀣予对于密度判断的篱佑，使褥整个算法静时阊复杂度为o ( m 2 * l o gi n ) 。 稳当于普运载聚合聚类方法。m e 氇 g e 龋数豹复杂魔为o ( i ) ：测试连通度的算法的 复杂凄为o ( ，其中m 为聚类开始辩亚簇静个数。渔予在算法的开始阶段使用 了统计售息，搏对初始数据遴行了划分和簿逸，使得算法掰娶处壤的数据量院原 媲数据点的个数要少褥多。 3 3 2 实验 实验的目的楚为了测试算法对于特殊数掇集合的处理以及算法的性能和可 伸缩憔。 2 0 处理海量数据音寸聚类簿法关键技术研究 考虑综合因素的聚黉算穗 在大援模数据瘁，特裂是数据仓痒中，数据集的矮模可能会菲常大，数据粲 瓣复杂程度会增加，可憨具有不同的密发，大小和形状，另岁 数据集中存在於嗓 声秘离臻点会影响聚类麴结果。下霹列爨了算法对这些情援懿处理。 对予大数据爨的数据集会的处理 为了减小大数据量对算法效率靛影赡，算法采取了髓橇敬祥和糕嗣绕许信息 的双重方法。睫搴且取样可以鸯效地从整个数据瘁申摄取反映浆来数据集特征瓣数 据。当然，对于取样的数据，在攮行算法豹时候嚣要对恩户提供豹参数静力量您f 搿 傲相应的变换。 然丽，对于特大数攒库或者数描仓库，取样后的数据量还建很大，丽迸一步 酌取样会影褊聚类的结柒。为了继续减少初始数据，在算法中使用统计信息来得 到耪始的亚簸。逶过筒擎的统计，初始豫簇豳取样数据变为单元，由于大多数数 据集中焱簇中，一个初始的甄簇往往包含了许多原始韵数据点。显然单元的个数 将运远小于取样点的个数，这极大魂提离了箨法的逮度。 此外，聚类结束之后在数据库中标记数据也是很花时间的一个过程。算法通 过利用索引的标记加快了这过程。 辫手奚寿特殊彩状静簇的数据集台的处疆 多个代表点技术可以准确地识别特殊形状的簇，在算法中，簇的表示使用多 个代表点。在数据库或者数粥仓库中，存在各种形状的数据粲合。传统的考虑单 个相似度的方法往往不能够覆盖所有的情况，而考虑综合因素的算法能够有效地 识剐这些簇。 _ _ _ _1 i w ia h 。 ， ：。， 。 潦 圈3 + l ：存在哑铃形簇的数据集合 铡热程铃形( 露罄3 ，1 ) ，密凄算法通常不麓准确谖掰它们e e k s x 9 6 j 。而在 考虑了距离懿毽素磊，它船棱正确识剐为一个簇。又知空心的簇( 如图3 2 ) ， ，羹矗，瓣：器 妊理海量数据的聚类算法关键技术研究 考虑综合因素的聚类算法 c u r e 算法慰为仅汉邋过距离来消除螓声署丞寓群点，掰以代袭点必缀收筑，不能 识别这静彩状的簇。嚣h y b r i d 算法中消除噪声敷毫群点懿识别是鸯动邀抒豹， 不嚣要运过代表点熬收缨，涨以代表点依然霹以准确地勾勒蹬簇躲形状。 嗨。 蕊黪；。黎 j ，期 晡斛 ( b ) 考虑综合因素的算法 圈3 2 ：存在空心簇的数据集合 虽然算法使用了小方格、单元来表示初始的旺簇，并且在整个聚类过程中使 嗣了统计信息，考虑综合因素的算法识剐的簇是准确的。这和某些同样使用统计 信息( s t i n g ( 秆矾9 7 ) 的算法是不同的，那些算法使用统计倍息加快速度是阻牺 程识掰的簇的精度为代价的。如图3 3 ，原来的簇的形状如a ，s t i n g 的识剃结 槊如b ( 斜边都交成了垂直边) ，而考虑综合因素的算法的识别结果就是a 。 ( a ) 考虑综合因素的算法( b ) s t i n g 图3 。3 。存在商斜边的簇的数据集合 警数据集合中存在多种形状豹簇的嚣寸候，考惑综合因素静算法仍然能够准确 港汉剩它们( 摇灏3 4 ) 。 图3 ：存在器耱形状熬簇浆数据集会 处理海量数据的聚类算法关键技术研究 考虑综合因素的聚类算法 对于同时存在具有巨大差异的簇的数据集合的处理 单一的基于距离的算法或者基于密度的算法对于存在具有巨大差异的簇的 数据集合往往无能为力。考虑综合因素的算法对于两者缺点都有所抑制( 如图 3 5 ) ，这是由于算法中的合并过程综合使用了密度和距离的判断。对于图a 这样 密度不同的簇，可以用亚簇之间的距离进行判别。对于图b 这样大小不同又离得 较近的簇，可以使用密度准确判别。 ( a ) 密度不同的簇( b ) 大小不同的簇 图3 5 ：存在具有差异的簇的数据集合 对于具有噪声和离群点的数据集合的处理 噪声是那些稀疏的，随机分布的数据点，它们影响了数据集中簇的清晰性， 而离群点是那些相对集中却规模很小的簇中的数据。在聚合聚类的算法中通常需 要额外的步骤用来消除噪声和离群点。 本章介绍的方法可以自动的发现噪声，并消除；而对于离群点，算法识别出 它们，但由于在聚类应用中，有可能对这些离群点产生兴趣，所以算法并不消除 它们。对于噪声，主要在初始化亚簇的时候消除。由噪声的定义可以知道噪声的 分布是稀疏的，因此对于那些密度远小于某个密度尺度的小方格，可以认为它里 面的数据都是噪声，在算法开始合并子簇之前就可以将之消除掉。 离群点是那些远离其他数据但是内部相对集中的小规模的数据点集，所以按 照距离判定它们不会被合并到其他簇中，在合并过程中会把它们认为是簇。在合 并完成后，那些直径小于m - d i a m e t e r 的簇中的数据就是离群点。 处理海量数据的聚类算法关键拽术研究 考虑综合因紫的聚类算法 性能和可伸缩性实验 上文已经说明了考虑综合因素的聚类算法能够有效地识别各种簇。在这部 分将藩重魄较该算法帮d b s c a n 、c u r e 黪速度豢雾。测试环辘是一台p t l 3 5 0 双c p u 、5 1 2 m 内存、9 6 g 硬盘运行m sw i n d o w sn t4 0 的p c 服务器。 雷3 。6 ：和c u r e 豹院较 图3 6 跑较了姿取榉数量铁2 0 0 0 裂6 0 0 0 交化露，考意综会嚣素熬算法衽 c u r e 的运行时间。可以着到，在速度上，考虑综合因素的算法远快于c u r e 。这 是鑫予算法秘霜了统计信息静缘故。 图3 。7 ：代袭点个数对于算法速度的影响 代表点个数直接影响了使用距离判断合并的簇的识别，在图3 7 中绘出了代 表点个数增加对算法藐彳亍时间豹影响。从中可以看磁，一个簇的代表点数量对于 算法速度的影响是线性的。 实验还比较了考虑综合因素的算法和d b s c a n 、c u r e 对于大数据量的处 理能力( 觅黼3 8 ) 。数据羹献3 0 ，0 0 0 弱i ，0 0 0 ，0 0 0 ，d b s c a n 的逡行时间没有锶 括它建立r + 树的时间，c u r e 算法和h y b r i d 算法的运行时间没有包括取样时阁。 从中可以看到考虑综合因索的算法在处理大数据量的能力上具有明显优势。这怒 虫于算法通过使用统计信惑减小了算法对于源数握羹戆敏感蛙，极大地掇毫了冀 法能够处理的数据擞。 处理海鼍数措的聚类算法关键技术研究考虑综合囡索的聚娄算法 鼹3 。8 ：处避大数据曩这壤院较 处理豫量数据的聚类算法关键技术研究 聚类树的自动构造 4 1 聚类树 第四章聚类树的自动构造 现在已有的许多聚类算法的结果是一个簇的集合，形成的这些簇是“平面” 的，从结果中并不能看到簇的不同粒度。然而，在真实的应用中，聚合而形成的 簇并不是“平面的”。用户以不同的粒度为要求，得到的聚类分析结果往往各不 相同。为了能够体现聚类分析过程中的多粒度问题，以及在多粒度情况下，不同 粒度的簇之间的相互关系，提出了聚类树的概念。 聚类树的构造基于自底向上的聚合聚类算法。自底向上的聚合聚类就是从 单独的数据点或者经过预处理的亚簇( 聚类的中间结果) 开始，根据亚簇的相似 程度，不断地合并亚簇直到达到终止条件、形成作为最终结果的簇的过程。可以 看到如果将聚合聚类分析的