（管理科学与工程专业论文）聚类分析算法研究.pdf

摘要 随着信息社会中数据库技术的迅速发展以及数据库管理系统( d b m s ) 的广泛应用，数 据供给能力和数据分析能力间的矛盾日益突出。迫切需要一种能够对数据进行深层次加工的 自动化技术。数据挖掘技术( 或称k d d 技术) 应运而生。 聚类分析是数据挖掘技术中一种应用广泛的重要分析方法。与其他聚类分析算法相比 较k m e a n s 算法能够有效处理大规模的数据集，这一特点使k m e a n s 算法尤其适合 k d d 的数据挖掘任务。但是，k m e a n s 算法采用了原始的搜索方式致使算法处理大数据 量的效率较低，这一缺陷严重限制了该算法的更广泛应用。为了研究和解决这些问题，进一 步提高算法的效率和应用范围，本文做了三个方面的工作：首先从两个层次上提出了基于 k d - 树的过滤搜索算法和信息可传递的过滤搜索算法；其次，运用概率论和更严格的b b d 树结构对上述算法的时间复杂度和空间复杂度进行了理论的分析和论证；最后，通过大量的 实验性能比较和分析从另一方面验证了本文提出的算法的高效性。 首先在绪论部分介绍了数据库中知识发现( k d d ) 技术的概貌、聚集分析的重要研究 意义和算法概况。界定了本文研究的问题是对k m e a n s 算法的搜索方法进行研究，以及当 前国际上对于该问题的研究成果和不足。简要论述了概率论对于本文研究的意义。此外，为 了确保论文的完整性简单介绍了k m e a n s 算法的思想。 在k d 树和b b d 树的预备知识基础上，研究了两种基于k d 树的提高k m e a n s 算法效 率的搜索算法过滤搜索算法和信息可传递的过滤搜索算法。它们利用特殊的数据结构将 数据对象存储起来，并采用新的搜索策略和信息传递策略，大大改进了原有算法的效率。此 外，本文通过理论分析对算法的复杂度进行了上限的估计，提出并证明了有关结论，为后面 章节的实验分析提供有利的理论依据。 最后，本文通过大量实验测试验证了本文提出的算法高效性并证实了对于算法的理论分 析：本文算法在数据的自然聚集性较好的情况下具有更高的效率；并且随着数据点数目的增 加，算法复杂度基本里线性增加，但是比起原始算法其增加的幅度要小得多；算法随着数据 维度的增加复杂度增加并将超过原始算法的效率，但是算法在2 0 维以下的情况下仍然保持 很好的效率；传递算法采用简洁的思想在过滤算法的基础上又有一定的提高。 本文的创新体现在； 1 提出了基于替代定理的过滤搜索策略，能够更加有效地过滤非后选中心点； 2 提出了基于最小半径保存策略的信息传递思想，使得过滤算法的效率进一步得到提高。 关键词：女一e a n s 聚类k d 一树聚类分析知识发现数据挖掘 a b s t r a c t t h ew i d ea p p l i c a t i o n so fi n f o r m a t i o nt e c h n o l o g i e ss u c ha sd a t a b a s e sa n dd b m sm a k et h e c o n f l i c tb e t w e e nt h ep o w e rt os u p p l ya l lk i n d so f d a t aa n dt h ea b i l i t yt oa n a l y z et h e ma p p a r e n t d a t a m i n i n gt e c h n o l o g yc a m eo n t ot h es t a g ei nt h e s ec a s e s a so n eo f t h em o s ti m p o r t a n ta n a l y s i sm e t h o d s ，c l u s t e r i n ga n a l y s i si sw i d e l yu s e di nt h ef i e l do f d a t am i n i n g a m o n gc l u s t e r i n gf o r m u l a t i o n st h a ta r eb a s e do nm i n i m i z i n gaf o r m a lo b j e c t i v e f u n c t i o n p e r h a p st h em o s tw i d e l yu s e da n ds t u d i e di sk m e a n sc l u s t e r i n ga l g o r i t h ms i n c ei ts u i t s t h ep r o c e s so fl a r g ed a t as e tm u c hb e t t e r o n eo f t h em o s tp o p u l a rh e u r i s t i c sf o rs o l v i n gt h en p h a r d k m e a n sp r o b l e mi sb a s e do nas i m p l ei t e r a t i v es c h e m ef o rf i n d i n gal o c a l l ym i n i m a ls o l u t i o n h o w e v e r , as t r a i g h t f o r w a r di m p l e m e n t a t i o no ft h i sn a v ea l g o r i t h mc a nb eq u i t es l o w t h i si s p r i n c i p a l l yd u et ot h ec o s to f c o m p u t i n gn e a r e s tc e n t e rf o re a c hd a t an o d e i nt h i sp a p e r ，w ep r e s e n t t w os i m p l ea n de f f i c i e n ti m p l e m e n t a t i o n so fn a i v ek m e a n sa l g o r i t h m ，w h i c ha r cc a l l e dt h e f i l t e r i n ga l g o r i t h ma n di n f o r m a t i o n - p a s s e df i l t e r i n ga l g o r i t h m m o r e o v e r , b a s e do np r o b a b i l i t y t h e o r ya n db b d - t r e e ，ac o m p l e x i t ya n a l y s i so ft h e s ea l g o r i t h m s r u n n i n gt i m ea n ds p a t i a lc o s ti s p r e s e n t e d f i n a l l y , an u m b e ro fe m p i r i c a ls t u d i e so ns y n t h e t i c a l l yg e n e r a t e dd a t af u r t h e rp r o o ft h e e f f i c i e n c yo f a l g o r i t h ma n dt h ea b o v et h e o r ya n a l y s i s i ns e c t i o n1 ，w ei n t r o d u c et h eb a s i ck n o w l e d g eo f k d d ，t h ei m p o r t a n c eo f c l u s t e r i n ga n a l y s i s a n da l g o r i t h m si nt h i sf i e l d t h er e s e a r c hf o c u so f t h i sp a p e ri se m p h a s i z e da n dt h er e l a t i v ei d e a so n t h i sp r o b l e ma r ed i s c u s s e d t h ei m p l i c a t i o no fp r o b a b i l i t yt h e o r yt ot h i sr e s e a r c hi sa l s ob r i e f l y p r e s e n t e d f o rc o m p l e t e n e s s w ei n t r o d u c et h eb a s i ci d e ao f n a f v ej | 一m e a n sa l g o r i t h m i ns e c t i o n2 ，b a s e do nt h es u m m a r yo fd a t as t r u c t u r ek d - t r e ea n db b d t r e e ，t w ok d - t r e eb a s e d f i l t e r i n ga l g o r i t h m s a r ep r e s e n t e d a sm e n t i o n e de a r l i e r , t h e ya r eb o t hb a s e do ns t o r i n gt h e m u l t i d i m e n s i o n a ld a t ap o i n t si nak d - t r e ea n du s i n gn e wf i l t e r i n gm e t h o da sw e l l a s i n f o r m a t i o n p a s s e dm e t h o dt h a tm a k et h ea l g o r i t h mm o r ee f f i c i e n t l y m o r e o v e r , s e v e r a lc o n c l u s i o n s t h a tq u a n t i f yt h ea l g o r i t h m se f f i c i e n c ya r cp r o o f e d t h e yp r o v i d ev a l u a b l eg u i d et ot h ef o l l o w i n g e x p e r i m e n t s ， i ns e c t i o n3 ，b yal a r g en u m b e ro fe x p e r i m e n t s ，w ef u r t h e rp r o o f e dt h ee f f i c i e n c ya n dt h e t h e o r e ma n a l y s i so ft h e s ea l g o r i t h m sw h i c hs h o wt h a t ，a st h es e p a r a t i o nb e t w e e nc l u s t e r si n c r e a s e s ， t h ea l g o r i t h mr u n sm o r ee f f i c i e n t l y ；w i t ht h ei n c r e a s eo ft h en u m b e ro fd a t a , t h ec o s to fa l g o r i t h m i n c r e a s el i n e a r l yw i t hm u c hs l o w e rs l o p et h a nn a i v ea l g o r i t h m ；w i t ht h ei n c r e a s eo fd i m e n s i o no f d a t a ，t h er u n n i n gt i m eo ff i l t e r i n ga l g o r i t h m sa r ee x p o n e n t l yi n c r e a s e d ，b u tt h ef i l t e r i n ga l g o r i t h m s p e r f o r m a n c eb e l o wd i m e n s i o n2 0a r ec o n s i d e r a b l yb e 廿e n n e wc o n t r i b u t i o n so f t h i sp a p e ra r ea sf o l l o w s ： 1 p r o p o s e dan e wf i l t e r i n gm e t h o db a s e do ns u b s t i t u t i o nt h e o r e mt oi m p r o v et h ee f f i c i e n c yo f 2 f i l t e r i n gc a n d i d a t ec e n t e r s ； 2 p r o p o s e dan e wi n f o r m a t i o n p a s s e di d e ab a s e do t 3m i n i m a lr a d i u st of u r t h e ri m p r o v et h e e f f i c i e n c yo f t h ef i l t e r i n ga l g o r i t h m k e yw o r d s - k m e a n sc l u s t e r i n g ，k d - t r e e ，c l u s t e r i n ga n a l y s i s ，k n o w l e d g ed i s c o v e r y , d a t a m i n i n g 3 第一章绪论 聚类分析是数据挖掘技术中一种应用广泛的重要分析方法。与其他聚类分析算法相比 较，k m e a n s 算法能够有效处理大规模的数据集，这一特点使k m e a n s 算法尤其适合 k d d 的数据挖掘任务。但是，k m e a n s 算法采用了原始的搜索方式致使算法处理大数据 量的效率较低，这一缺陷严重限制了该算法的更广泛应用。为了研究和解决这些问题，进一 步提高算法的效率和应用范围，本文改进和设计了k m e a n s 算法并进行了大量的实验分 析。作为全文的绪论，本章介绍了数据库中知识发现( k d d ) 技术的概貌、聚集分析的研 究意义和算法概况、本文研究的问题以及当前国际上对于该问题的研究状况和本文内容安 排。 1 1 数据库中知识发现( k d d ) 1 1 。1 。k d d 概述 随着信息社会中数据库技术的迅速发展以及数据库管理系统( d b m s ) 的广泛应用，积 累的各种数据呈爆炸式增长，已经远远超出了人们分析它们并从中提取有用信息的能力。虽 然数据库系统可以高效地实现数据的录入、查询、简单统计等功能，但却无法发现数据中存 在的关系和规则，无法根据现有的数据预测未来的发展趋势。这使得数据供给能力和数据分 析能力间的矛盾日益突出，迫切需要一种能够对数据进行深层次加工的自动化技术。 数据库中的知识发现k d d ( k n o w l e d g e d i s c o v e r y i n d a t a b a s e s ) 技术就在这样的背景下 诞生了。它将数据库管理系统和人工智能中机器学习两种技术相结合，用数据库管理系统来 存储数据，用机器学习的方法来分析数据，自动发现大量数据中隐含的知识。数据库中的知 识发现是- - f q 交叉性学科。涉及到机器学习、模式识别、统计学、智能数据库、知识获取、 数据可视化、高性能计算、专家系统等多个领域。从数据库中发现出来的知识可以用在信息 管理、过程控制、科学研究、决策支持等许多方面。 从1 9 9 8 年第1 】届国际人工智能联合会议专题讨论会上首次提出k d d 到现在，k d d 的定义随着人们研究的不断深入也在不断完善。日前比较公认的是f a y y a d 等给出的定义： 定义1 1 ：k d d 是一个从数据集中识别出有效的、新颖的、潜在有用的以及最终可理解的模 式的高级处理过程。 l - 1 2 k d d 的流程 从定义中可以看出，k d d 是一个高级的处理过程，它从数据集中识别出以模式来表示 的知识。高级的处理过程是指一个多步骤的处理过程，多步骤之间相互影响、反复调整，每 一个步骤一旦与预期目标不符，都要回到前面的步骤，重新调整，重新执行，从而形成一种 螺旋式上升的过程，如图1 - 1 所示。 图1 一1 k d d 流程图 k d d 通常包含以下步骤： 1 数据准备 k d d 处理的对象是大量的数据。但这些原始数据往往不适合直接用于知识挖掘。因此， 需要对这些原始数据做前期的准各工作，其中包括数据的清洗( 消除噪音、冗余数据，填补 缺失数据，纠正不一致) 、集成( 合并多个数据源) 、选择( 选择相关的数据) 、转换( 通过 聚集、概化及规范化等处理将数据转换成适合知识发现的形式) 、数据缩减( 在保持原有数 据特征的前提下减少数据量) 。数据准备是k d d 的第个步骤，也是比较重要的一个步骤， 因为它将影响到数据挖掘的效率和准确度以及最终模式的有效性。 2 ，数据挖掘 数据挖掘是k d d 过程中核心的步骤，是采用机器学习、统计等方法进行知识学习的阶 段。人们往往不严格区分数据挖掘和k d d ，把两者混淆使用。一般在科研领域中称为k d d ， 而在j j ：程领域则称为数据挖掘。由于数据挖掘算法的好坏直接影响到所发现知识的质量，目 前大多数的研究都集中在数据挖掘算法和应j 【：f j 上。数据挖掘根据k d d 的分析目标，选取相 戍的分折算法提取有用的数据模式。采用较多的挖掘技术有决策树、统计聚类、粗糙集、神 经网络、遗传算法等。 3 评估、解释模式模型 上面得到的模式，有可能是没有实际意义或没有实用价值的，也有可能是不能准确反映 数据的真实意义。甚至在某些情况下是与事实相反的。因此，为了有效地发现对于给定用户 有价值的模式，需要对这些模式进行评估。评估可以根据用户多年的经验，有些模式也可以 直接用数据来检验其准确性。这个步骤还包括把模式以易于理解的方式呈现给用户。 4 巩固知识 用户理解的、并被认为是符合实际和有价值的模式形成了知识。同时还需要对知识做一 致性检查，解决与以前得到的知识互相冲突、矛盾的地方，使知识得到巩固。 5 运用知识 发现知识是为了运用，如何使知识能被运用也是k d d 的步骤之一。运用知识有两种方 法：一种是运用知识本身所描述的关系或结果对决策提供支持，这种知识模式即是下一节所 提到的描述型模式；另一种是要求对新的数据运用知识，由此可能产生新的问题而需要对 知识做进一步的优化，这种知识模式也称为预测型模式。 定义1 ，2 ：数据库中的知识发现是过程，它从特定格式的数据集合中发现隐藏的、有使用 价值的模式。 事实上，数据库中的知识发现是一个以人为中心的，需要人的指导和干预的过程。它 的各个环节：挖掘目标( 知识发现的范围) 的确定、挖掘方法的选择和调整、挖掘结果的评 估和应用都将由人进行。 1 1 3 k d d 的目标模式 k d d 的任务是从数据中发现各种模式。按其功能，模式可分为两大类：预测型 ( p r e d i c t i v e ) 和描述型( d e s c r i p t i v e ) 。预测型模式通过分析当前数据，建立一个或一组模 型对新的数据集进行预测。描述型模式则以简洁概括的方式刻画数据的一般特征。 通常，根据其实际作用，模式可细分为以下几种： 1 概念描述 概念描述是指提供给定数据集的概貌，或将它与对比类相区别，从而产生数据的特征化 和比较描述。对于存放在数据库中的大量数据，能够以简洁的形式在更抽象的层次上描述数 据能够帮助用户考察数据的一般行为。概念描述的典型应用是概念层次树，即按照某种偏序 关系建立一种描述数据的结构。 2 关联分析 关联分析是指寻找给定数据集中数据项之间的有趣联系。它，。泛应j j 于购物篮或事务数 据分沂。关联规则的形式定义如表达式1 - 1 ： a la a 2 a ，j 蜀 b 2 或 1 - ! 其中，a ，( f 1 ，m ) 和b ，( - ， 1 ，聆 ) 表示属性或谓词 式l 一1 用支持度和置信度两个参数来评估其兴趣度。 根据蕴涵表达式中属性或谓词的维度，关联规则可以分为多维关联规则和单维关联规 则。 3 分类 分类模式是指通过训练数据集导出描述并区分数据类的模型或函数，用于预测新的数据 集。一般在建立分类模型时，使用一部分数据作为训练样本，用另一部分数据来检验、校正 模型。由于在建立模型之前，训练样本的结果是已知的，模型的产生是在受监督的情况下进 行的，因此分类模式属于有监督的学习。导出模型可以表现为多种形式。如决策树、数学公 式或神经元网络等。 4 聚类分析 聚类分析是指把数据划分到不同的组中，使得不同组之间的差异性尽可能大，同一组内 的相似性尽可能高。根据不同的应用，对差异性有不同的数学定义。与分类模式不同，进行 聚类之前并不知道数据要划分成几个组以及划分成什么样的组。因此，聚类分析在模型建立 前结果是未知的，属于必型的非监督学习。本文将在后续章节详细讨论聚类分析。 1 2 k d d 中的聚类分析 1 2 1 k d d 聚类分析的研究意义 作为独立的k d d 目标模式，聚类分析将大量数据划分为性质相同的子类，便于了解数 据的分布情况。因此，它广泛应用于模式识别、图像处理、数据压缩等许多领域，例如： 1 在市场分析中，通过聚类分析能帮助决策者识别不同特征的客户群以及各客户群的行为 特征： 2 在生物工程研究中，聚类分析能够用于推导动植物的分类，按照功能对基因进行划分并 获取种群中的固有结构特征： 3 在非关系数据库领域( 如空间数据库领域) ，聚类分析，能够识别具有相同地理特征的 区域以及该区域的环境和人的特征： 4 在w e b 信息检索领域，聚类分析能够对w e b 文档进行分类提高检索效率。 此外聚类分析的另一个研究价值在于将它作为其他分析模式( 如概念描述、分类等) 的预处理技术能够提高其他模式的分析效果。例如，在建立概念层次树时，聚类分析能够根 据数据的分布自动生成或调整概念层次，消除了人为划分的不合理因素，使得概念层次的划 分更加科学合理。因而，聚类分析在k d d 领域得到非常厂泛的研究和应川。 1 2 2 主要算法概述 目前，在聚类分析领域，根据具体不同的应用已经研究出了大量的算法。了解聚类算法 的分类有利于明确本论文研究的范围以及当前该领域研究的概况。许多算法为了提高效率和 聚类结果的质量，往往继承了许多其他聚类方法的思想，很难将它们单独划归为哪一类。因 此，对于算法的分类也是仁者见仁、智者见智。 通常，根据算法模型的主要思想，聚类算法可以分为两大类：k 代表点算法和层次算法。 为了与具体的算法名称相区别。本文在后续章节中将t 代表点算法的研究统称为k 一e 口船 聚类问题。 j i a w e ih a r t 则对聚类算法有更细致的分类爨： 1 划分方法( p a r t i t i o n i n gm e t h o d ) 该方法将珂个对象划分到k 个组中且膏 ，使其满足： 1 ) 每个组至少包含一个对象： 2 ) 每个对象必须属于且只属于某一个组。 比较常用的划分方法包括k m e a n s 算法、k m e d o i & 算法等。h a n 所谓的划分方法 可以对应为上述的k 一搬翻埘聚类问题，本文将在后续章节进行深入讨论。 2 层次方法( h i e r a r c h i c a lm e t h o d ) 该方法将给定的数据对象集合进行层次的分解，根据分解的方向，层次方法分为自底向 上的( 凝聚的) 方法和自顶向下的( 分裂的) 方法。层次方法的最大缺陷在于，某一步分裂 或合并一旦完成，就不能更改。这一严格的规定导致错误约分裂或合并无法更正，有可能严 重影响聚类的结果。 通过综合其他聚类方法可以对层次方法进行改进，目前主要有两种改进方法： 1 ) 综合层次凝聚方法和划分算法中的迭代技术。首先用自底向上的层次算法，然后用迭代 技术来改进聚类结果，例如，由z h a n g 、r a m a k r i s h n a n 、l i n w 提出的b i r c h 算法明 中首先通过建立描述数据统计特征的c f 树对数据进行层次聚类，然后再采用迭代技术 对结果进行修正。 2 ) 在层次分析中，通过连接分析或最近邻居分析来执行。例如，g u h a 、r a s t o g i 、s h i m 提 出的c u r e 算法”】和r o c k 算法哪，以及k a r y p i “h a r t 、k u m a r 提出的c h a m e l e o n 算 。法【， 3 基于密度的方法( d e n s i t y b a s e dm e t h o d l 基于密度的方法很好的弥补了绝大多数算法在发现非球状聚类上的缺陷。其主要思想是 如果临近区域的给定密度函数值超过了某个阈值，就继续合并周围的点，即是用密度低的点 来分割高密度区域。该方法的优点是能够发现任意形状的聚类，并且有效处理孤立点数据。 比较经典的基于密度的算法有：e s t e r 、k r i e g e l 、s a n d e r 、x u 提出的基于高密度连接区域的 密度聚类算法d s s c a n i q ；a n k e r s t 、b r e u n i g 、k r i e g e i 、s a n d e r 提出了一个通过对象排序进 行聚类的算法o p t i c s i ! ，解决了d b s c a n 需要提供参数的不足：此外，h i n n e b u r g 、k e i m 提出了基于密度分布函数的d e n c l u e 算法嘤。 4 基于网格的方法( g r i d b a s e dm e t h o d ) 基于网格的方法把对象空间量化成有限数目的单元，形成一个网格结构，将所有的聚类 操作都在这个网格上进行。这种方法的主要优点是处理速度很快，其处理时间独立于数据对 象的数目，只与量化空间中每一维的单元数据有关。属于该类方法的经典算法有：w a n g 、 y a n g 、m u n t z 提出的基于网格的多分辨率算法s t r n g 憋 s h e i k h o l e s l a m i 、c h a t t e r j e e 、z h a n g 提出的一个通过小波变换来转换原始特征空间的多分辨率聚类算法w a v e c l u 5 t e r t 2 q ；以及 a g r a w a l 、g e h r k e 、g u n o p u l o s 、r a 曲8 v a n 提出的一个综合了基于密度和基于网格方法的聚类 算法c l i q u e t i i 。 5 基于模型的方法( m o d e l - b a s e dm e t h o d ) 基于模型的方法为每个聚类假定一个模型并找出数据对于给定模型的最佳拟合，其目的 在于优化给定数据和某些数学模型之间的关系。该方法通常假定数据符合潜在概率分布。基 于模型的方法主要分两类：统计学方法和神经元网络方法。m i e h a l s k i 、s t e p p 提出的概念聚 类 ，f i s h e r 提出的c o b w e b 黝g e n n a r i 、l a n g l e y 、f i s h e r 提出的c l a s s l t h 噜都属于 统计聚类方法：r u m e l h a r t 、z i p s e r 提出的竞争学习黧和k o h o n e n 提出的s o m ( s e l f - o r g a n i z i n g f e a t u r em a p s ) 等方法则属于神经元网络方法。 综上所述。在聚类分析研究领域存在各种各样的算法，它们采用了不同的模型对数据进 行了假定，并选择不同的最优判定准则来寻找聚类，因而它们针对不同的数据分布各有所长。 总体来说有以下特点： 1 ) 以k m e a n s 算法为代表的划分方法采用启发式方法来寻找k 个组的代表点，具有较高 的效率和良好的可扩展性，适合于发现较大规模数据集中豹球状聚类： 2 ) 层次算法通过定义聚类之间的距离阈值来合并或分裂数据集，其算法本身虽然有不能更 正错误选择的缺陷。但是通过改进，该类算法的效率和聚类质量有较大提高； 3 ) 基于密度的算法能处理任意形状的聚类，但是需要预先定义密度函数； 4 ) 而基于网格的算法由于在规则的量化空间中处理数据，因而具有较高的处理效率。但是 在数据点的分布稀疏的空间中无法节省开销。 1 2 3 k m e a n s 算法 定义1 3 ：在d 维空间中，聚类中心点定义为属于该组的所有数据对象的平均值，即 c ，= ：；。数据对象所属分组的聚类中心点称为该对象的归属中心点。 p e q t m e a n s 算法以k 为参数，将n 个d 维数据对象划分为k 个组。使得各组内有较高的 相似度，而各组之间的相似度较低( 本论文将相似度定义为各数据对象间的欧氏距离) 。每 6 个组用其聚类中心点即一个j 维点q ( f o ，七d 来表示。矢量c 0 ，f 2 ，巳) 则确定了数 据对象集的k 个分组的状态。 定义1 4 ：在d 维空间中，定义判定聚类质量的标准即最优评价函数为各数据对象到其归属 2 中心点的距离平方和，即平方误差准则e = p c 。i 。 i = lp e c j 定理11 ：在d 维空阃申，点c 为该组对象的备维的平均值即重心耐平方误差e 为最小。 算法首先随机选取k 个初始中心点，将各数据对象划归到其中心点离该对象最近的组， 重新计算各组对象的平均值以更新中心点的位置。算法的目的是要寻找到使得上述最优评价 函数为最小值时的聚类状态。由定理2 1 可得，如果经过重新计算，中心点的位置不变则表 明最优评价函数已经达到最优，此时的聚类状态就是算法所要寻找的结果。k m e a n s 算法 是一种寻找局部虽优解的启发式方法它通常不能得到全局最优解。 k 一所e 口埘算法的主要流程如表2 i 所示。从该流程可以看出，算法的复杂度是 o ( n k d t l ，其中聆为所有对象的数目，k 为分组的数目，d 为维度，r 为迭代的次数。通常， k ，t n ，且算法常以局部最优解结束，由于本论文研究的算法是针对每次迭代过 程中搜索效率的提高，因此，论文中只考虑每次迭代的复杂度，即o ( k d j 。 表2 - 1 ：k m e a n s 算法流程 7 为了更加形象地说明k m e a n s 算法的实现过程，本节将给出一个算法实施的小例子。 假定某数据对象集合，其分布如图1 2 a 所示。令k = 3 ，且任意选择三个初始中心点，在图 中用。表示。根据离中心点的距离大小，将每个数据对象分配给最近的一个组，则形成了 图1 2 a 中虚线所描绘的图形。 经过这样的分组以后，聚类中心通常会改变，因此需要重新计算各组的中心点位置。然 后依据新的中心点，将数据对象重新分配到各组中，形成了图i 2 b 中新增虚线所描绘的图 形。重复以上过程，直到各对象不再被重新分配即中心点位置不变时结束算法，得到图1 2 c 中实线所描绘的图形，聚类过程结束。 图卜2 a 初始聚类及分组状态图1 2 b 迭代过程 1 3 本论文的研究范围及当前研究状况 1 3 1 论文研究范围 图卜2 c 最终聚类状态 如1 2 2 节所示，聚类算法研究领域中已经有诸多研究成果。这些方法有基于分裂和合 并的( 例如i s o d a t a 等) ，随机选点的( 例如c l a r a 、c l a r a n s 等) ，也有向大型数据 库扩展的算法( 例如d b s c a n 、b i r c h 等) 。许多成果着重于对经典问题的研究及应用上。 著名的k m e a n s 聚类问题就是聚类分析领域中广泛研究和应用的热点。该问题假定一个数 据集合。在实数域率含有疗个d 维数据对象，其目标是对于给定的整数k ，寻找k 个代表各 组的中心点并使得各组内的数据对象的平均距离满足所定义的最优条件。 k m e a n s 聚类问题是一个n p 问题，它与其他诸多的聚类彝) 位置问题息息相关。关于 k m e a n s 问题最著名的启发式算法称为k m e a n s 算法，它通过重定位技术米寻找局部最 优解，对犬数据量有良好的扩展性，这一特点使k m e a n s 算法尤其适合k d d 的数据挖掘 任务。 该算法虽然开辟了一条解决k m e a n s n p 问题的新思路，但是直接执行原始算法却有 以下的缺点： i 算法需要用户指定参数k 的值，而不同的七值对聚类分析的效率和结果有较大影响； 2 ，算法的初始中心点选择与算法的运行效率密切相关，而随即选取中心点有可能导致迭代 次数很大或者限于某个局部最优状态； 3 只擅长于处理球状分布的数据； 4 对异常偏离的数据敏感： 5 算法只适合处理数值属性的数据，对于分类属性的数据处理效果不佳； 6 搜索策略效率低，面对大型数据库的处理该算祛的开销大； 本论文主要就是针对经典的一l ? t e a n s 算法最后个方面的缺陷进行深入的研究。下面 一节将论述当前该方向上的研究成果和局限。 1 3 2 聚类算法搜索效率的研究 由于数据挖掘的对象主要是针对海量数据，因此对于算法效率的研究一直是热点问题。 虽然与其他聚类分析算法相比较，k m e a n s 算法能够有效处理大规模的数据集，但是随着 数据量的增大+ 算法的运行开销仍然很大。其主要原因在于k m e a n s 采用了原始的遍历搜 索算法。改进k m e a n s 聚类算法搜索效率的一个新思想由m o o r e 在评价混合聚类模型参 数时提出。他采用了k d - 树结构来存储数据对象，有效实现了e m 算法i 卿。a l s a b t i 、p e l l e g 等人也分别提出了基于k d 树的改进算法。它们不是种新的聚类算法，而是提高 k m e o n s 算法效率的非常有价值的搜索算法。 这些算法的共同思想是：首先，利用k d 树来存储数据点，然后在执行k m e a n s 算法 的每个阶段，白上而下为k d 一树的节点筛选出后选中心点。通过筛选算法，能够迅速排除掉 一些非后选中心点，将k d 树某节点内所有数据对象的归属中心点的搜索范匿限定在后选中 心点集台中，这样大大减少了分别为每个数据点从个中心点中寻找归属中心点的开销 o g 槲) 。 这些算法也各有不同之处：a i s a b t i 提出的过滤方法瞧于分别计算后选中心点集 c l ，c 2 ，、，c f 到给定节点的最短距离 r n i n j ，m i n2 ，r n i n ，j 和最长距离 m a x l ，i t l a x 2 ，m a x ， 。找出最长距离的最小疽m i n m a x ，删除其最短距离大于m i n m a x 的后选中心点，即ki r a i n ， m i n m a x 。该方法的过滤条件比较弱，例如对图l - 3 a 中的情 况则无能为力，因而需要搜索的节点数量大，计算效率很低。 p e l l e z 和m o o r 提出的方法i 2 0 l 将到给定节点内数据对象的距离最近的聚类中心点定义 为后选归属中心点( o w n e r ) ，通过超平分面作为判断删除后选中心点的依据。该方法的过滤 条件比a i s 。b t i 方法中的条件要强，能够排除更多的非后选中心点。但是，该方法要求得出 9 剑1 7 点超矩形内数据对象的距离，田此计算复杂度高；同时i 该方法仍然不能处理某惶情况， 例如图1 3 b 中所示的倚况：此外，在有两个后选中心点同时位，铮点内的时候无法确定后 选门属中心点。 剀卜3 a图卜3 b k a n u n g o 等人提山了更加简洁的方法【2 ”，将距离树1 y 点矩形中心最近的聚类中心点定义 为 属中心点，同样采用超平分面作为判断是否删除厉选中心点的依据。该方法有效解决了 p e l l e g 和m o o r e 方法的不足，但是他口j 没有提i 出在迭代的各个阶段有效地传递有川信息的方 法。这一缺陷在聚类进行剑中后阶段，各个聚类中心点位置变动不人的时候会导致人量的重 复计算。 表1 - 1 当前研究成果的比较 名称方法 优点不足 a i s a b t i 以距离树诲点的最大最小距离为方法简单，对算法效过滤条件弱，许多情 基准，删除最小值人于该基准的率有提高况f 不能有效排除后 后选中心点。选中心点。 p e l l e g & 以距离树节点中数据对象距离最过滤条件比a l s a b t i方法复杂，计算量犬。 m o o r e 小的点为基准。然后依据超平分方法强 面删除后选中心点 k a n u n g o以距离树二声点的中心位置距离最过滤条件比a s a b t j算发在迭戗各个阶段 近的点为基准，依据超平分面删 和p e l l e g & m o o r e 方 不能进行有效的信息 除后选中心点法强传递。 o 1 3 3 概率论对于本论文研究的意义 高维空间中的数据分布与算法中数据结构的建立和算法的效率有密切的关系。然而，数 据在高维空间中的分布非常复杂。从k m e a n s 算法的目的可得知，算法是要发现数据集中 的k 个聚类分组的中心，根据中心点的定义也即是发现属于该聚类分组的平均值。概率论中 描述随机变量分布状况的参数均值和方差能够有效刻画数据的分布状况。在本文后面的章节 中可以看出，著名的m a r k o v 不等式在算法分析中起到重要作用。 1 4 论文的内容安排 本文提出了基于k m e a n s 的简洁高效的过滤搜索算法和信息可传递的过滤搜索算法。 不同于以往的研究，该方法运用了k d ，树的存储结构，提出了较强的过滤条件预先删除不可 能成为数据对象归属点的聚类中心，并通过预先存储k d 一树节点中数据对象的统计特性保存 其有用的信息，从而大大缩减了k m e a n s 算法执行时的搜索空间，使算法的效率得到较大 提高。同时，本文在更进个层次上提出了信息可传递的过滤搜索算法，提出了信息可传递 的保存策略，使得在算法进入稳定期后不必重新访阀靠近聚类中心的数据节点，此外。本文 还通过算法的时间和空间复杂度分析，从理论上得出并证明了关于算法复杂度的有用结论。 同时，通过模拟数据集进行实验仿真，验证了上述理论分析的结论，证实了算法的高效性和 实用性。 按照这一思路，后续章节的内容安排如下：第二章在算法预备知识的基础上提出了过滤 搜索算法和信息可传递的过滤搜索算法并在提出的假设前提下分别对时间复杂度和空间复 杂度进行了分析，提出和证明了有关结论；第三章通过实验分析分别应用模拟数据集对算法 效率进行了验证，并与其他研究成果进行了比较。第四章总结了本文的研究以及今后研究工 作的主要问题。 第二章基于j - - m e 伽的过滤搜索算法 随着聚类分析广泛应用于知识发现、数据压缩和矢量计算以及模式识别和分类，聚类分 析成为了一个研究的重要问题。其中，聚类问题的一个重要分支是七一m e a n s 问题：它在给 定的疗维空间且4 和整数七的条件下，发现r 4 中的七个点，即聚类中心点，使得各个数据 点到它的最近聚类中心点的距离之和最小。k m e a n s 聚类问题与其他聚类问题很相似，比 如| i 一m e 西d 邶问题等。 解决露一m e a n s 问题的最著名的启发式算法称为k m e a n s 算法1 1 6 1 。然而该算法在处理 大量高维数据时却需要很大的开销。导致算法在处理大量数据花费时间长的原因主要有两 个： 1 算法通常处理高维空间的数据，而在这样的空间中有效地计算最近点是一个很复杂的问 题； 2 算法通常需要经过多次迭代才能最终达到终止状态。 针对上述问题，本文从两个层次提出了对于算法效率改进的过滤搜索算法。由于所研究 的算法采用k d 树存储结构，因此为了便于对本文过滤搜索算法的理解，首先简单介绍一下 算法所涉及的重要知识。 2 1 预备知识 2 1 1 k d 树 定义2 2 ：空间盒是指在矗维空间r 。率，一个具有d 维禽性轴g l ，口2 ，a d ) 且平行与各属 性轴的超矩形( h y p e r r e c t a n g ie ) 。包含集台中所有数据对象的最小空间盒称为该数据集 的约束空间盒( b o u n d i n gb o x ) 。 k d 树是一种用于存储多维数据对象的简单有效的数据结构，它与众不同的建树思想是 将数据集合中所有对象的分布空间用一个空间盒( b o x ) 来描述。为了更加准确地描述空间盒 中的数据对象，k d 树在建立的时候通常采用数据对象集的约束空间盒( b o u n d i n gb o x ) 。 定义2 2 ：分裂超平面是指在d 维空间中鼢，钆) i 口，= 彳且4 r 。j 。 k d 树是棵二叉树，树的各层次关系通过具有多维属眭轴的超平面分裂各空间盒而形 成。根节点的索引指向所有数据对象集的空间盒，其非叶子：悼点指向被分裂平面划分成的子 1 2 空间盒，叶子节点则指向具体的数据对象。分裂超平面