PAM聚类算法的分析与实现

毕业论文（设计）论文（设计）题目：PAM聚类算法的分析与实现系别：专业：学号：姓名：指导教师：时间：毕业论文（设计）开题报告系别:计算机与信息科学系专业:网络工程学号姓名高华荣论文（设计）题目PAM聚类算法的分析与实现命题来源□√教师命题□学生自主命题□教师课题选题意义(不少于300字):随着计算机技术、网络技术的迅猛发展与广泛应用，人们面临着日益增多的业务数据，这些数据中往往隐含了大量的不易被人们察觉的宝贵信息，为了得到这些信息，人们想尽了一切办法。数据挖掘技术就是在这种状况下应运而生了。而聚类知识发现是数据挖掘中的一项重要的内容。在日常生活、生产和科研工作中，经常要对被研究的对象经行分类。而聚类分析就是研究和处理给定对象的分类常用的数学方法。聚类就是将数据对象分组成多个簇，同一个簇中的对象之间具有较高的相似性，而不同簇中的对象具有较大的差异性。在目前的许多聚类算法中，PAM算法的优势在于：PAM算法比较健壮，对“噪声”和孤立点数据不敏感；由它发现的族与测试数据的输入顺序无关；能够处理不同类型的数据点。研究综述(前人的研究现状及进展情况，不少于600字):PAM（PartitioningAroundMedoid,围绕中心点的划分）算法是是划分算法中一种很重要的算法，有时也称为k-中心点算法，是指用中心点来代表一个簇。PAM算法最早由Kaufman和Rousseevw提出，Medoid的意思就是位于中心位置的对象。PAM算法的目的是对n个数据对象给出k个划分。PAM算法的基本思想：PAM算法的目的是对成员集合D中的N个数据对象给出k个划分，形成k个簇，在每个簇中随机选取1个成员设置为中心点，然后在每一步中，对输入数据集中目前还不是中心点的成员根据其与中心点的相异度或者距离进行逐个比较，看是否可能成为中心点。用簇中的非中心点到簇的中心点的所有距离之和来度量聚类效果，其中成员总是被分配到离自身最近的簇中，以此来提高聚类的质量。由于PAM算法对小数据集非常有效，但对大的数据集合没有良好的可伸缩性，就出现了结合PAM的CLARA（ClusterLARgerApplication）算法。CLARA是基于k-中心点类型的算法，能处理更大的数据集合。CLARA先抽取数据集合的多个样本，然后用PAM方法在抽取的样本中寻找最佳的k个中心点，返回最好的聚类结果作为输出。后来又出现了CLARNS（ClusterLargerApplicationbaseduponRANdomizedsearch,也称随机搜索聚类算法），CLARNS是另外一种k-中心点方法，它将采样技术和PAM结合起来，对CLARA的聚类质量和可伸缩性进行了改进。不像CLARA那样每个阶段选取一个固定样本，CLARANS在搜索的每一步都带一定随机性地选取一个样本。研究的目标和主要内容（不少于400字）对PAM聚类算法的基本思想、PAM聚类算法的替换代价和PAM聚类算法的性能等进行分析，根据PAM算法描述，使用matlab软件编写PAM聚类算法代码，实现PAM聚类算法。使用编写好的代码运用到一个实例中，使同一个簇中的对象越近越好，而不同簇中的对象越远越好，对实例中的数据进行聚类后，把聚类后的结果作为进一步进行分析的基础。本选题研究的主要内容如下：(1)PAM聚类算法的分析，分析PAM聚类算法的主要内容如下：1)PAM聚类算法的基本思想：了解PAM聚类算法的基础，能够让人简单的了解PAM聚类算法的整个过程，对于最后的算法实现有很重要的意义。2)PAM聚类算法的替换代价：分四种情况计算替换代价，通过最后的总代价，来分析是否要进行替换的根据。3)PAM聚类算法的算法描述：使用matlab软件编写PAM聚类算法的代码的根据。4)PAM聚类算法的性能：包含了PAM聚类算法的优点和缺点。(2)PAM聚类算法的实现，实现PAM聚类算法的主要内容如下：1)算法实现：根据PAM聚类算法描述，使用matlab软件编写PAM聚类算法代码。2)把编写好PAM聚类算法的代码运用到一个实例中。拟采用的研究方法在指导老师的指导下，查找并阅读相关资料，利用相关资料对PAM算法进行详细分析，从而根据分析实现PAM算法。使用matlab软件来编写代码。研究工作的进度安排2010年11月20号－11月29号，与指导老师沟通交流，完成毕业论文选题；2010年11月29号－12月31号，收集整理资料，完成文献综述和开题报告；2011年01月—2011年03月，继续整理资料；2011年03月—2011年04月，完成初稿；2011年04月—2011年05月，对初稿进行检查和修改；2011年05月—2011年06月，完成（论文）撰写、装订，参加答辩参考文献目录（作者、书名或论文题目、出版社或刊号、出版年月日或出版期号）[1]毛国君，等.数据挖掘原理与算法（第二版）[M].北京：清华大学出版社,2007.12[2]JiaweiHan,MichelineKamber.数据挖掘：概念与技术[M].北京：机械工业出版社，2001.[3]陈京民，等.数据仓库与数据挖掘技术[M].北京：电子工业出版社，2002.[4]刘同明，等.数据挖掘技术及其应用[M].北京:国防工业出版社，2001.[5]DavidHand,等.数据挖掘原理[M].张银奎，等译.北京:机械工业出版社，中信出版社，2004.指导教师意见签名：年月日教研室主任意见签名：年月日目录摘要………………………………………………………………………………1关键词…………………………………………………………………………………1Abstract…………………………………………………………………………1Keywords……………………………………………………………………………1引言………………………………………………………………………………11PAM聚类算法分析…………………………………………………………………21.1数据挖掘相关知识……………………………………………………………21.1.1数据挖掘简介…………………………………………………………21.1.2聚类…………………………………………………………………21.1.3聚类分析概述…………………………………………………………31.2PAM算法分析…………………………………………………………………51.2.1PAM算法详细论述……………………………………………………51.2.2PAM算法描述…………………………………………………………71.2.3PAM算法性能分析……………………………………………………72PAM聚类算法的实现………………………………………………………………72.1简要说明……………………………………………………………………72.2matlab简介…………………………………………………………………82.2.1matlab基本功能……………………………………………………82.3算法实现……………………………………………………………………82.4PAM聚类算法在学生成绩中的应用…………………………………………133小结……………………………………………………………………………14致谢………………………………………………………………………………14参考文献……………………………………………………………………………141PAM聚类算法分析与实现网络工程专业高华荣指导教师：吴启明[摘要]“物以类聚，人以群分”。当有一个分类指标时，分类比较容易。但是当有多个指标，要进行分类就不是很容易了。对于多指标分类，由于不同的指标项对重要程度或依赖关系是相互不同的，所以也不能用平均的方法，因为这样会忽视相对重要程度的问题。所以需要进行多元分类，即聚类分析。本文主要介绍一种聚类分析算法，它就是PAM聚类算法。首先是数据挖掘简介包括数据挖掘的基本概念，说明聚类是数据挖掘的一个很重要的功能。同时进一步解释什么是聚类分析。然后详细分析PAM聚类算法，最后给出了一个实现PAM聚类算法的例子。[关键词]：PAM聚类算法；中心点；聚类分析；代价PAMClusteringAlgorithmAnalysisandImplementationMajor：NetworkengineeringGaoHuarongSupervisor：WuQiming[Abstract]Birdsofafeatherflocktogether.Whenthereisaclassificationindex,classificationiseasier.Butwhenmorethanoneindex,wanttoundertakeclassificationisnotveryeasy.Formulti-indexclassification,duetothedifferentindexstudyofimportantdegreeordependentrelationshipismutualdifferent,soalsocannotuseaveragemethod,becausethatwillignoretherelativeimportance.Sotheneedofmultipleclassification,namelyclusteringanalysis.Thispapermainlyintroducesakindoftheclusteranalysisalgorithm,itisPAMclusteringalgorithm.Firstintroducesthebasicconceptofdataminingthatclusteringisanimportantdataminingthefunction.Andfurtherexplainedwhatclusteringanalysisis.ThendetailedanalysisofPAMclusteringalgorithm,andfinallypresentsarealizingexamplesofPAMclusteringalgorithm.[Keywords]PAMclusteringalgorithm；center；Clusteringanalysis；cost引言如今数据挖掘的理论越来越广泛的应用在商业、制造业、金融业、医药业、电信业等等许多领域。数据挖掘的目标之一是进行聚类分析。聚类就是把一组个体按照相似性归成若干类别，它的目的是使得属于同一类别的个体之间的差别尽2可能的小，而不同种类别上的个体间的差别尽可能的大。PAM聚类算法是众多聚类算法的之一。PAM算法的优势在于：PAM算法比K-平均算法更健壮，对“噪声”和孤立点数据不敏感；它能够处理不同类型的数据点；它对小的数据集非常有效。1PAM聚类算法的分析1.1数据挖掘相关知识1.1.1数据挖掘简介数据挖掘是一个多学科交叉研究领域，它融合了数据库技术、人工智能、机器学习、统计学、知识工程、面向对象方法、信息检索、高性能计算以及数据可视化等最新技术的研究成果。经过十几年的研究，产生了许多新概念和新方法。特别是最近几年，一些基本概念和方法趋向于清晰，它的研究正向着更深入的方向发展。数据挖掘之所以被称为未来信息处理的骨干技术之一，主要在于它以一种全新的概念改变着人类利用数据的方式。20世纪，数据库技术取得了决定性的成果并且已经得到广泛的应用。但是，数据库技术作为一种基本的信息储存和管理方式，仍然以联机事务处理为核心应用，缺少对决策、分析、预测等高级功能的支持机制。众所周知，随着数据库容量的膨胀，特别是数据仓库以及Web等新型数据源的日益普及，联机分析处理、决策支持以及分类、聚类等复杂应用成为必然。面对这一挑战，数据挖掘和知识发现技术应运而生，并显示出强大的生命力。数据挖掘和知识发现使数据处理技术进入了一个更更高级的阶段。它不仅能对过去的数据进行查询，并且能够找出过去数据之间的潜在联系，进行更高层次的分析，以便更好地做出理想的决策、预测未来的发展趋势等。通过数