基于聚类K-Means算法的分析与应用研究.pdf

基于聚类K-Means算法的分析与应用研究.pdf

《基于聚类K-Means算法的分析与应用研究.pdf》由会员分享，可在线阅读，更多相关《基于聚类K-Means算法的分析与应用研究.pdf（67页珍藏版）》请在冰点文库上搜索。

硕士学位论文基于聚类K_Means算法的分析与应用研究作者：

石云平指导老师：

辛大欣副教授申请学位学科：

计算机应用技术西安工业大学20064基于聚类卜啪ans算法的分析与应用研究学科：

计算机应用技术研究生躲乏i夺指导老师签名：

荡以彩，摘要数据挖掘（DataMining），又称为数据库中的知识发现（简称KDD），是从大量数据中提取可信的、新颖的、有效的并能被人们理解的模式的处理过程。

它是一门新兴的交叉学科，汇集了来自机器学习、模式识别、数据库、统计学、人工智能等各领域的研究成果。

聚类分析是数据挖掘中的一个重要研究领域。

它将数据对象分组成为若干个类或簇，使得在同一个簇中的对象比较相似，而不同簇中的对象差别很大。

Kmeans算法是一种基于划分的聚类算法，它把N个对象划分成K个类，其中聚类数目K是输入参数。

该算法是通过不断地迭代来进行聚类，当算法收敛到一个结束条件时，就终止迭代过程，输出一个聚类结果。

但是由于Kmeans算法在选择初始聚类中心时是随机选取K个点，因此一旦这K个点选取不合理将会误导聚类过程，得到一个不合理的聚类结果。

论文在分析聚类结果对初值依赖性的基础上，对初值选取方法进行了分析和研究，并提出了一种有效的改进方法，通过试验证明了改进算法的有效性。

同时对该算法中对于计算聚类簇中心对孤立点敏感性这一问题也提出了改进措施，理论和实验都证明了改进方法的有效性。

本论文的另一个重要目的是将数据挖掘中的聚类技术应用到对学生成绩的分析中，根据学生的学习成绩对学生进行聚类同时分析影响每一簇成员学习成绩的主要因素。

在此应用中对数据的预处理采用统计学中的标准分技术，该技术解决了在利用原始分进行分析学生学习情况时的弊端，即只根据学生学习成绩的高低来衡量一个学生的学习好坏，而没有考虑到因试题的难易程度等原因而造成的成绩结果。

关键词：

数据挖掘；划分方法；聚类；KmeansAnalysisandApplicationBasedonmeClusteringK-meallsAlgoritllIIlDiscipline：

ComputerApplicationTechn0109yStudentSignature5ksuper。

is。

rsignature：

X江M1D弘voABSTRCTDataMining，alsocalledasknowledgediscoVeryofdatabases（KDD），isaprocessingprocedureofextractingcredible，novel，effectiveandunderstandableDatternsfromdatabasesAsarisingcrossoversubject，datamininginvolVesanintegrationoftechniquesfrommultipledisciplinessuchasmachine1earning，patternrecognition，databasetechnology，statisticsandartificialintelligenceC1usteringanalysisisanimportanttechnologyindatamining，whichgroupsthedataintoclassesorclusterssothatobjectswithinaclusterhavehighsimilarityinco叩arisontooneanother，butareVerydissimilartoobjectsinotherclustersKMeansisapartitioningalgorithmthatconstructsapartitionofadatabaseofNobjectsintoasetofKclusterswhereKisaninputparameterClusteringuseaninterativeprocedureifthisalgorithmconvergestooneofnumerouslocalminima，thenitterminatesandoutputsresultS0itisobviousthatoutputsareespeciallysensitivetoinitialstartingconditionforrandomselectionsaboutKinitialstartingpoints，whichwillleadtobads01utions，sothequalityofclusterrelysontheinitialpoints0nthebasisofanalysingtheclusteringresult1hichrelysonthestartingvalue，thepaperstudythewayofthestartingValueselection，propOseaneffectiveiprovementmethod，andithasproventheimprovementalgorithmvaliditythroughtheexperimentMeanwhi1ethepaperalsoproposeanimprovementmeasureinregardingthecomputationoftheclusteringcenterwhichissensitivetotheis01atedpointsThetheoryandtheexperimenthasa11proventheimprovementmethodvalidityAnotherimportantgoalofthepaperisapplyingakindofdataminingclusteringtechn0109ytothestudentscoreItalsoclustertostudentaccordingtostudentsacademicrecordandanalysethepriaryfactorwhichaffecttheacademicrecordofeveryclusteringmemberThepaperusesastandardminutetechn0109yinstatisticsinthisapplicationtothedatapretreatmentThistechnologyhassolVedthemalpracticecarriedonwhenweuseprimitiveminutetoanalysethestudentstudiedsituation，namelyonlyweighedastudentsstudyqualityaccordingtothestudentaeademicrecordheight，buthasnotconsideredtheresultbecauseofthedifficultydegreeofthetestpaperI（eyWords：

datamining；partitioningmethod；clustering；Kmeans；l。

1引言1绪论近几十年来，人们利用信息技术生产和搜集数据的能力以惊人的速度在增长，千千万万的数据库被用于商业管理、学校、政府办公、科学研究及工程开发等等。

与此同时随着各个机构内部局域网的建立和互连网的飞速发展，人们已被铺天盖地的信息所淹没，于是新的挑战被提出来了，这就迫切要求能够对海量数据进行更高层次的分析，而目前的数据库系统虽然可以进行如查询、录入、统计等功能，但无法发现数据中存在的关系和规则。

同样，传统的统计技术也面临着极大的挑战，这就急需有新的方法来处理这些海量般的数据。

于是，人们结合统计学、数据库、机器学习等技术，提出数据挖掘来解决这一难题，数据挖据技术便应运而生，并显示出前所未有的强大生命力，并且逐渐成为研究的热点，吸引了很多人进行研究。

而作为数据挖掘技术之一的聚类分析也越来越受到研究者的关注。

数据挖掘是一个交叉学科领域，受多个学科的影响如图11所示，包括数据库系统、统计学、机器学习、可视化和信息科学等。

此外，依赖于所用的数据挖掘方法，以及可以使用的其他学科的技术，如神经网络、模糊和，或粗糙集理论、知识表示、归纳逻辑程序设计或高性能计算机。

依赖于所挖掘的数据类型或给定的数据挖掘应用，数据挖掘系统也可能集成空间数据分析、信息检索、模式识别、图像分析、信号处理、计算机图形学、web技术、经济、商业、生物信息学或心理学领域的技术【IJ。

图11数据挖掘与其它学科的关系数据挖掘（DataMining）就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。

与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。

这个定义包括好几层含义：

数据源必须是真实的、大量的、含噪声的：

发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；不要求发现放之四海皆准的知识，仅支持特定的发现问题。

12论文选题的目的和意义目前我们面对的教务处学生成绩数据库是一个多维的关系数据库，它不仅有学生的高考入学成绩还有各学期的考试成绩信息，而且近几年随着学生数量的增加存储的成绩信息也在不断增长，我们急切需要从这些海量数据中发现潜在的有用信息来帮助决策部门掌握更多的学生信息。

本课题的主要目的是对聚类Kmeans算法进行分析，并将该算法应用到对学生的分类中以及根据分类的结果来分析影响学生学习成绩的主要因素。

如果我们用传统的统计分析方法对学生进行分类（例如相关分析），则会因为数据点极多而变得非常复杂，况且也不能得到令人满意的结果，这是因为传统的统计方法涉及的主要是二维以下的数据。

然而数据挖掘技术的出现却能解决我们所面临的问题，可以使用聚类划分方法来完成，但数据挖掘不是为了替代传统的统计分析技术，相反，它是统计分析方法学的延伸和扩展。

所谓数据挖掘是指从大型数据库或数据仓库中自动提取隐含的、未知的、有价值的复合信息，并通过预测未来趋势和行为模式，为决策者作出前瞻的、基于知识的决策。

聚类分析在数据挖掘中占有重要的地位，它所要解决的就是如何在没有先验知识的前提下，实现满足要求的类的聚合。

数据挖掘技术与统计学的比较如下：

（1）对于传统的统计学来说，它所处理的数据量是中小型的，但是随着数据量的增加传统统计学就不能满足实际需求，然而数据挖掘技术的产生却恰恰弥补了这一缺点，它能对海量数据进行处理。

（2）面对数据库中复杂的数据，它已不仅仅是符合一定的标准（例如独立同分布），可能只有一小部分是符合统计模型的。

对数据挖掘技术来说它能处理这样的复杂数据，而统计模型就显示了极大局限性，不符合现代对复杂数据类型的分析。

（3）数据挖掘主要研究的数据类型为数值型、文本型、图象型、声音型甚至是web型数据，而统计学主要研究的是数值型数据。

（4）在数据挖掘建模时，强调的是模型对数据的拟合程度，而不是代表决定这些数据产生的理论模型，这也正是实际中所需要的。

而在统计建模中，强调模型的代表性，也可理解为数据对模型的适应程度。

（5）统计学强调理论的严谨性，即只有在理论或方法经过严格的证明后才可以使用。

而在实际中，我们发现一种方法能够带来所要的结果，但由于统计学的严谨性而无法实旋使用该方法。

显然，传统的统计学缺乏必要的冒险精神。

综上所述，显然数据挖掘技术是统计分析方法学的延伸和扩展。

根据我们所要完成的任务，选用数据挖掘技术很适合，而且数据挖掘正因为有这方面的优势而迅速发展，可见该选题是一种值得重视的研究方向，也正得到越来越广泛的应用。

13聚类方法现状综述131聚类简介“3“聚类”顾名思义是要将相近相似的对象聚成一类，为此需要确切地描述与度量有关的属性，并从中比较对象间的相似程度，把最接近的对象归并成类。

从统计学的角度来看，在聚类分析中常把对象称为样本或个体，把它们的属性称为定量或指标。

定量的描述可以是定性的或定量的。

若用连续的实型量度量，称为间隔度量；若用有序的等级表示，称为有序尺度；也可用一些只有名字，而无等级和数量关系得类别来描述，称为名义尺度。

从模式识别或空间的角度来看，对象就是数据点。

聚类是数据挖掘中的一种主要技术，是把一组个体按照相似性归成若干类别即“物以类聚”。

它的目的是使得属于同一类别的个体之间的距离尽可能的小而不同类别上的个体间的距离尽可能的大。

聚类和分类根本不同的是：

分类问题中我们知道训练例的分类属性，而在聚类中就需要我们在训练例中找到这个分类属性值。

聚类方法包括统计方法、机器学习方法、神经网络方法和面向数据库的方法。

在统计方法中，聚类称聚类分析，它是多元数据分析的三大方法之一（其它两种是回归分析和判别分析），它主要研究基于几何距离的聚类，如欧式距离、明考斯基距离等。

传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。

在机器学习中聚类称作无监督或无归纳学习。

因为和分类学习相比，分类学习的例子或数据对象有类别标记，而要聚类的例子则没有标记，需要由聚类学习算法来自动确定。

机器学习领域中的概念聚类算法通过符号属性来进行聚类，并得出聚类的概念描述，当聚类对象可以动态增加时，概念聚类则称是概念形成。

概念聚类由两部分组成：

（1）发现合适的类；

（2）形成对每个类的描述。

在神经网络中，有一类无监督学习方法：

自组织神经网络方法；如Kohonen自组织特征映射网络、竞争学习网络等等。

神经网络中的sOM方法通过反复的学习来聚类数据，它由输入层和竞争层组成。

输入层由N个输入神经元组成，竞争层由M个输出神经元组成，且形成一个二维平面阵列。

输入层各神经元与竞争层各神经元之间实现互连接。

矢量量化VQ方法中的LEG方法只能对数值属性进行聚类，通常的做法是将所有要识别矢量的集合分成若干子集，各子集中的矢量具有相似特征，因而能用一个具有代表性的矢量来表示。

该具有代表性的矢量称为码字，全部码字的集合称为码本。

聚类分析问题可描述为：

给定m维空间R中的n个向量，把每个向量归属到S聚类中的某一个，使得每个向量与其聚类中心的距离最小。

聚类分析问题的实质是一个全局最优问题，在这里m可认为是样本参与聚类的属性个数，n是样本的个数，s是由用户预先设定的分类数目。

定义对于m维空间时中的向量x。

=x，X，X，。

），X，=XmXm，X。

）向量X，与X，之间的距离为：

儋k也）2数据聚类正在蓬勃发展，有贡献的研究领域包括数据挖掘、统计学、机器学习、空间数据库技术、生物学以及市场营销，由于数据库中收集了大量的数据，聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。

132聚类挖掘的研究现状聚类与分类不同，对于聚类来说，需要划分的类是未知的，聚类将数据对象分组为多个类或簇，使同一个簇中的对象之间的相似度最高，而不同簇中的对象其相似度最低。

由于大型数据库中存放了大量的数据，聚类分析已经成为数据挖掘研究领域一个非常活跃的研究课题。

常用的聚类方法有统计学方法、模式识别、机器学习和数据库的方法。

作为统计学的一个分支，聚类分析已经研究了许多年，主要集中于基于距离的聚类分析，基于K一均值、K一中心点和其他方法的聚类分析工具已在许多聚类分析应用中实现。

在机器学习领域，聚类是无监督的学习，是观察式学习，不是示例性学习。

在概念聚类中，一组对象可以被一个概念描述时才形成一个聚类。

概念聚类由发现簇和描述簇两个部分组成。

数据挖掘中的聚类研究主要集中在大型数据库中的聚类分析方法的构成。

活跃的方向是聚类算法可伸缩性的研究、各种聚类方法对聚类复杂形状和复杂类型数据的有效性、高维的聚类分析技术的研究、大型数据库中混合了数值数据和分类数据的聚类算法研究。

目前，改善聚类算法性能大多采用的是层次技术和样本化的技术，用于提高聚类算法效率的技术主要集中在样本化技术、聚集的优化技术、多维索引技术和基于压缩的技术等方面。

同时聚类技术也已广泛地用于wEB数据的处理和挖掘上，如对顾客行为的聚类、wEB访问路径的聚类、文档聚类等。

聚类的应用是十分广泛的。

在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征；在生物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得对各种群中固有结构的认识；聚类在地球观测数据库中对相似地区的确定，汽车保险单持有者的分组以及根据房子的类型、价值和地理位置对一个城市中房屋的分组上也可以发挥作用；聚类也能用于对wEB文档进行分类，以发现有用信息。

在文献。

1中，聚类用来实现学生成绩的聚类；在文献“3种，聚类分析方法用来进行房地产市场的市场场细分和进行目标市场的选择，这样应用后，就可以选择要开发物业的细分市场，找准目标顾客，针对不同的目标顾客来满足他们的需求。

另一方面，聚类还可以用于大型复杂信息系统设计中”3。

聚类技术被应用于软件工程中，用于系统设计和规划的主要有企业规划法中的uc矩阵聚类法和启发式聚类方法。

在进行系统的功能模块设计时，应用聚类算法对数据项进行聚类，从而确定系统的功能模块类。

文献”1中，对各条新闻按照主题使用Kmean算法进行聚类，并定义了一种相似度度量准则。

另外，聚类在其他领域也有着广泛的应用，例如：

模式识别、图像处理”1等领域中。

作为数据挖掘的功能之一，聚类分析能作为一个独立的工具来获得数据分布的基本情况，观察每个类的特点，集中对特定的某些类做进一步的分析。

此外，聚类分析也可以作为其他算法的预处理步骤，这些算法再在生成的聚类上进行处理。

133聚类研究的方向19聚类，是一个富有挑战性的研究领域，它的研究工作集中在为大型数据库的有效和实际的聚类分析寻求适当的方法，目前的研究方向包括下列几个方面：

（1）算法的可伸缩性：

在很多聚类算法中，数据对象小于200个的小数据集合上鲁棒性执行多种数据模型；面对于包含几百万个数据对象的大规模数据库进行聚类时，将会导致有不同的偏差结果，这就需要聚类算法具有高度的可伸缩性，能有效地处理海量数据。

（2）处理不同类型属性的能力：

对于设计的很多算法用于聚类数值类型的数据。

但在实际应用中可能要求聚类其它类型的数据。

如分类标称类型（categoricalnominal），序数型（ordinal），二元（binary）数据，或者这些数类型的混合。

（3）发现任意形状的聚类：

许多聚类算法是基于欧几里德距离或者曼哈坦距离，趋向于发现具有相近密度和尺寸的球状簇。

但一个簇可能是任意形状的。

提出能发现任意形状簇的算法非常重要。

（4）用于决定输入参数的领域知识最小化：

在聚类分析中，许多聚类算法要求用户输入一定的参数，如希望簇的数目。

聚类结果对于输入参数很敏感，通常参数较难确定，尤其是对于含有高维对象的数据集更是如此。

要求人工输入参数不但加重了用户的负担，而且也使聚类质量难以控制。

（5）对于输入记录顺序不敏感：

一些聚类算法对于输入数据的顺序是敏感的。

如对于同一个数据集合，以不同的顺序提交给同一个算法时，可能产生差别很大的聚类结果。

研究和开发对数据输入顺序不敏感的算法具有重要的意义。

（6）高维性：

一个数据库可能含有若干维或者属性。

很多聚类算法擅长处理低维数据，一般只涉及两到三维。

通常最多在三维的情况下能够很好地判断聚类的质量。

聚类数据对象在高维空间是非常有挑战性的，尤其是考虑到这样的数据可能高度偏斜，非常稀疏。

（7）处理噪声数据的能力：

在现实应用中绝大多数的数据都包含了孤立点，空缺、未知数据或者错误的数据。

有些聚类算法对于这样的数据敏感，将会导致质量较低的聚类结果。

（8）基于约束的聚类：

在实际应用中有可能需要在各种约