当前位置:文档之家› 聚类分析算法研究

聚类分析算法研究

北京邮电大学

硕士学位论文

聚类分析算法研究

姓名:杨璐

申请学位级别:硕士专业:管理工程与科学指导教师:舒华英

20030501

摘要

随着信息社会中数据库技术的迅速发展以及数据库管理系统(DBMS)的广泛应用,数据供给能力和数据分析能力间的矛盾日益突出。迫切需要一种能够对数据进行深层次加工的自动化技术。数据挖掘技术(或称KDD技术)应运而生。

聚类分析是数据挖掘技术中一种应用广泛的重要分析方法。与其他聚类分析算法相比较.k—means算法能够有效处理大规模的数据集,这一特点使k—means算法尤其适合KDD的数据挖掘任务。但是,k—means算法采用了原始的搜索方式致使算法处理大数据量的效率较低,这一缺陷严重限制了该算法的更广泛应用。为了研究和解决这些问题,进一步提高算法的效率和应用范围,本文做了三个方面的工作:首先从两个层次上提出了基于kd-树的过滤搜索算法和信息可传递的过滤搜索算法;其次,运用概率论和更严格的BBD.树结构对上述算法的时间复杂度和空间复杂度进行了理论的分析和论证;最后,通过大量的实验性能比较和分析从另一方面验证了本文提出的算法的高效性。

首先在绪论部分介绍了数据库中知识发现(KDD)技术的概貌、聚集分析的重要研究意义和算法概况。界定了本文研究的问题是对k—means算法的搜索方法进行研究,以及当前国际上对于该问题的研究成果和不足。简要论述了概率论对于本文研究的意义。此外,为了确保论文的完整性简单介绍了k—means算法的思想。

在kd.树和BBD.树的预备知识基础上,研究了两种基于kd.树的提高k—means算法效率的搜索算法——过滤搜索算法和信息可传递的过滤搜索算法。它们利用特殊的数据结构将数据对象存储起来,并采用新的搜索策略和信息传递策略,大大改进了原有算法的效率。此外,本文通过理论分析对算法的复杂度进行了上限的估计,提出并证明了有关结论,为后面章节的实验分析提供有利的理论依据。

最后,本文通过大量实验测试验证了本文提出的算法高效性并证实了对于算法的理论分析:本文算法在数据的自然聚集性较好的情况下具有更高的效率;并且随着数据点数目的增加,算法复杂度基本里线性增加,但是比起原始算法其增加的幅度要小得多;算法随着数据维度的增加复杂度增加并将超过原始算法的效率,但是算法在20维以下的情况下仍然保持很好的效率;传递算法采用简洁的思想在过滤算法的基础上又有一定的提高。

本文的创新体现在;

1.提出了基于替代定理的过滤搜索策略,能够更加有效地过滤非后选中心点;

2.提出了基于最小半径保存策略的信息传递思想,使得过滤算法的效率进一步得到提高。关键词:女一Ⅲeans聚类kd一树聚类分析知识发现数据挖掘

l-1.2.KDD的流程

从定义中可以看出,KDD是一个高级的处理过程,它从数据集中识别出以模式来表示的知识。高级的处理过程是指一个多步骤的处理过程,多步骤之间相互影响、反复调整,每一个步骤一旦与预期目标不符,都要回到前面的步骤,重新调整,重新执行,从而形成一种螺旋式上升的过程,如图1-1所示。

图1一1.KDD流程图

KDD通常包含以下步骤:

1.数据准备

KDD处理的对象是大量的数据。但这些原始数据往往不适合直接用于知识挖掘。因此,需要对这些原始数据做前期的准各工作,其中包括数据的清洗(消除噪音、冗余数据,填补缺失数据,纠正不一致)、集成(合并多个数据源)、选择(选择相关的数据)、转换(通过聚集、概化及规范化等处理将数据转换成适合知识发现的形式)、数据缩减(在保持原有数据特征的前提下减少数据量)。数据准备是KDD的第~个步骤,也是比较重要的一个步骤,因为它将影响到数据挖掘的效率和准确度以及最终模式的有效性。

2,数据挖掘

数据挖掘是KDD过程中核心的步骤,是采用机器学习、统计等方法进行知识学习的阶段。人们往往不严格区分数据挖掘和KDD,把两者混淆使用。一般在科研领域中称为KDD,而在jJ:程领域则称为数据挖掘。由于数据挖掘算法的好坏直接影响到所发现知识的质量,目前大多数的研究都集中在数据挖掘算法和应J【:fj上。数据挖掘根据KDD的分析目标,选取相戍的分折算法提取有用的数据模式。采用较多的挖掘技术有决策树、统计聚类、粗糙集、神经网络、遗传算法等。

个组用其聚类中心点.即一个J维点q(f∈O,七D来表示。矢量c0,,f2,..,巳)则确定了数据对象集的k个分组的状态。

定义1.4:在d维空间中,定义判定聚类质量的标准即最优评价函数为各数据对象到其归属

中心点的距离平方和,即平方误差准则E=∑∑p—c。I。

i=lpecj

定理11:在d维空阃申,点c.为该组对象的备维的平均值即重心耐平方误差E为最小。

算法首先随机选取k个初始中心点,将各数据对象划归到其中心点离该对象最近的组,重新计算各组对象的平均值以更新中心点的位置。算法的目的是要寻找到使得上述最优评价函数为最小值时的聚类状态。由定理2.1可得,如果经过重新计算,中心点的位置不变则表明最优评价函数已经达到最优,此时的聚类状态就是算法所要寻找的结果。k—means算法是一种寻找局部虽优解的启发式方法.它通常不能得到全局最优解。

k一所e口埘算法的主要流程如表2.I所示。从该流程可以看出,算法的复杂度是O(nkdtl,其中聆为所有对象的数目,k为分组的数目,d为维度,r为迭代的次数。通常,k<<",t<<n,且算法常以局部最优解结束,由于本论文研究的算法是针对每次迭代过程中搜索效率的提高,因此,论文中只考虑每次迭代的复杂度,即O(.kdJ。

表2-1:k—means算法流程

以下的缺点:

I.算法需要用户指定参数k的值,而不同的七值对聚类分析的效率和结果有较大影响;2,算法的初始中心点选择与算法的运行效率密切相关,而随即选取中心点有可能导致迭代次数很大或者限于某个局部最优状态;

3.只擅长于处理球状分布的数据;

4.对异常偏离的数据敏感:

5.算法只适合处理数值属性的数据,对于分类属性的数据处理效果不佳;

6.搜索策略效率低,面对大型数据库的处理该算祛的开销大;

本论文主要就是针对经典的≈一l?teans算法最后~个方面的缺陷进行深入的研究。下面一节将论述当前该方向上的研究成果和局限。

1.3.2.聚类算法搜索效率的研究

由于数据挖掘的对象主要是针对海量数据,因此对于算法效率的研究一直是热点问题。虽然与其他聚类分析算法相比较,k—means算法能够有效处理大规模的数据集,但是随着数据量的增大+算法的运行开销仍然很大。其主要原因在于k~means采用了原始的遍历搜索算法。改进k—means聚类算法搜索效率的一个新思想由Moore在评价混合聚类模型参数时提出。他采用了kd-树结构来存储数据对象,有效实现了EM算法I卿。Alsabti、Pelleg等人也分别提出了基于kd.树的改进算法。它们不是~种新的聚类算法,而是提高k—meons算法效率的非常有价值的搜索算法。

这些算法的共同思想是:首先,利用kd.树来存储数据点,然后在执行k—means算法的每个阶段,白上而下为kd一树的节点筛选出后选中心点。通过筛选算法,能够迅速排除掉一些非后选中心点,将kd.树某节点内所有数据对象的归属中心点的搜索范匿限定在后选中心点集台中,这样大大减少了分别为每个数据点从≈个中心点中寻找归属中心点的开销oG槲)。

这些算法也各有不同之处:AIsabti提出的过滤方法瞧于分别计算后选中心点集cl,c2,.、,cf}到给定节点的最短距离{rninJ,min2,..,rnin,j和最长距离{maxl,iTlax2,..,max,}。找出最长距离的最小/疽MinMax,删除其最短距离大于MinMax的后选中心点,即kIrain,<MinMax}。该方法的过滤条件比较弱,例如对图l-3a中的情况则无能为力,因而需要搜索的节点数量大,计算效率很低。

Pellez和MooR提出的方法i20l将到给定节点内数据对象的距离最近的聚类中心点定义为后选归属中心点(Owner),通过超平分面作为判断删除后选中心点的依据。该方法的过滤条件比AIs。bti方法中的条件要强,能够排除更多的非后选中心点。但是,该方法要求得出

相关主题
相关文档 最新文档