PAM聚类算法的分析与实现
毕业论文（设计）论文（设计）题目：PAM聚类算法的分析与实现
系别：
专业：
学号：
姓名：
指导教师：
时间：
毕业论文（设计）开题报告
系别:计算机与信息科学系专业:网络工程
学号姓名高华荣
论文（设计）题目PAM聚类算法的分析与实现
命题来源□√教师命题□学生自主命题□教师课题
选题意义(不少于300字):
随着计算机技术、网络技术的迅猛发展与广泛应用，人们面临着日益增多的业务数据，这些数据中往往隐含了大量的不易被人们察觉的宝贵信息，为了得到这些信息，人们想尽了一切办法。数据挖掘技术就是在这种状况下应运而生了。而聚类知识发现是数据挖掘中的一项重要的内容。
在日常生活、生产和科研工作中，经常要对被研究的对象经行分类。而聚类分析就是研究和处理给定对象的分类常用的数学方法。聚类就是将数据对象分组成多个簇，同一个簇中的对象之间具有较高的相似性，而不同簇中的对象具有较大的差异性。
在目前的许多聚类算法中，PAM算法的优势在于：PAM算法比较健壮，对“噪声”和孤立点数据不敏感；由它发现的族与测试数据的输入顺序无关；能够处理不同类型的数据点。
研究综述(前人的研究现状及进展情况，不少于600字):
PAM（Partitioning Around Medoid,围绕中心点的划分）算法是是划分算法中一种很重要的算法，有时也称为k-中心点算法，是指用中心点来代表一个簇。PAM算法最早由Kaufman和Rousseevw提出，Medoid的意思就是位于中心位置的对象。PAM算法的目的是对n个数据对象给出k个划分。PAM算法的基本思想：PAM算法的目的是对成员集合D中的N个数据对象给出k个划分，形成k个簇，在每个簇中随机选取1个成员设置为中心点，然后在每一步中，对输入数据集中目前还不是中心点的成员根据其与中心点的相异度或者距离进行逐个比较，看是否可能成为中心点。用簇中的非中心点到簇的中心点的所有距离之和来度量聚类效果，其中成员总是被分配到离自身最近的簇中，以此来提高聚类的质量。
由于PAM算法对小数据集非常有效，但对大的数据集合没有良好的可伸缩性，就出现了结合PAM的CLARA（Cluster LARger Application）算法。CLARA是基于k-中心点类型的算法，能处理更大的数据集合。CLARA先抽取数据集合的多个样本，然后用PAM方法在抽取的样本中寻找最佳的k个中心点，返回最好的聚类结果作为输出。后来又出现了CLARNS（Cluster Larger Application based upon RANdomized
search,也称随机搜索聚类算法），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] Jiawei Han,Micheline Kamber.数据挖掘：概念与技术[M].北京：机械工业出版社，2001.
[3] 陈京民，等.数据仓库与数据挖掘技术[M].北京：电子工业出版社，2002.
[4] 刘同明，等.数据挖掘技术及其应用[M].北京:国防工业出版社，2001.
[5] David Hand,等.数据挖掘原理[M].张银奎，等译.北京: 机械工业出版社，中信出版社，2004. 指导教师意见
签名：年月日教研室主任意见
签名：年月日
目录
摘要 (1)
关键词 (1)
Abstract (1)
Key words (1)
引言 (1)
1 PAM聚类算法分析 (2)
1.1 数据挖掘相关知识 (2)
1.1.1 数据挖掘简介 (2)
1.1.2 聚类 (2)
1.1.3 聚类分析概述 (3)
1.2 PAM算法分析 (5)
1.2.1 PAM算法详细论述 (5)
1.2.2 PAM算法描述 (7)
1.2.3 PAM算法性能分析 (7)
2 PAM聚类算法的实现 (7)
2.1简要说明 (7)
2.2 matlab简介 (8)
2.2.1 matlab基本功能 (8)
2.3 算法实现 (8)
2.4 PAM聚类算法在学生成绩中的应用 (13)
3 小结 (14)
致谢 (14)
参考文献 (14)
PAM聚类算法分析与实现
网络工程专业高华荣指导教师：吴启明
[摘要]“物以类聚，人以群分”。当有一个分类指标时，分类比较容易。但是当有多个指标，要进行分类就不是很容易了。对于多指标分类，由于不同的指标项对重要程度或依赖关系是相互不同的，所以也不能用平均的方法，因为这样会忽视相对重要程度的问题。所以需要进行多元分类，即聚类分析。本文主要介绍一种聚类分析算法，它就是PAM聚类算法。首先是数据挖掘简介包括数据挖掘的基本概念，说明聚类是数据挖掘的一个很重要的功能。同时进一步解释什么是聚类分析。然后详细分析PAM聚类算法，最后给出了一个实现PAM聚类算法的例子。
[关键词]：PAM聚类算法；中心点；聚类分析；代价
PAM Clustering Algorithm Analysis and
Implementation
Major：Network engineering Gao Huarong Supervisor：Wu Qiming
[Abstract] Birds of a feather flock together.When there is a classification index,classification is easier.But when more than one index, want to undertake classification is not very easy.For multi-index classification, due to the different index study of important degree or dependent relationship is mutual different, so also cannot use average method, because that will ignore the relative importance.So the need of multiple classification, namely clustering analysis.This paper mainly introduces a kind of the cluster analysis algorithm, it is PAM clustering algorithm.First introduces the basic concept of data mining that clustering is an important data mining the function.And further explained what clustering analysis is. Then detailed analysis of PAM clustering algorithm, and finally presents a realizing examples of PAM clustering algorithm.
[Key words] PAM clustering algorithm；center；Clustering analysis；cost
引言
如今数据挖掘的理论越来越广泛的应用在商业、制造业、金融业、医药业、电信业等等许多领域。数据挖掘的目标之一是进行聚类分析。聚类就是把一组个体按照相似性归成若干类别，它的目的是使得属于同一类别的个体之间的差别尽
可能的小，而不同种类别上的个体间的差别尽可能的大。PAM聚类算法是众多聚类算法的之一。PAM算法的优势在于：PAM算法比K-平均算法更健壮，对“噪声”和孤立点数据不敏感；它能够处理不同类型的数据点；它对小的数据集非常有效。
1 PAM聚类算法的分析
1.1 数据挖掘相关知识
1.1.1数据挖掘简介
数据挖掘是一个多学科交叉研究领域，它融合了数据库技术、人工智能、机器学习、统计学、知识工程、面向对象方法、信息检索、高性能计算以及数据可视化等最新技术的研究成果。经过十几年的研究，产生了许多新概念和新方法。特别是最近几年，一些基本概念和方法趋向于清晰，它的研究正向着更深入的方向发展。
数据挖掘之所以被称为未来信息处理的骨干技术之一，主要在于它以一种全新的概念改变着人类利用数据的方式。20世纪，数据库技术取得了决定性的成果并且已经得到广泛的应用。但是，数据库技术作为一种基本的信息储存和管理方式，仍然以联机事务处理为核心应用，缺少对决策、分析、预测等高级功能的支持机制。众所周知，随着数据库容量的膨胀，特别是数据仓库以及Web等新型数据源的日益普及，联机分析处理、决策支持以及分类、聚类等复杂应用成为必然。面对这一挑战，数据挖掘和知识发现技术应运而生，并显示出强大的生命力。数据挖掘和知识发现使数据处理技术进入了一个更更高级的阶段。它不仅能对过去的数据进行查询，并且能够找出过去数据之间的潜在联系，进行更高层次的分析，以便更好地做出理想的决策、预测未来的发展趋势等。通过数据挖掘，有价值的知识、规则或高层次的信息就能从数据库的相关数据集合中抽取出来，从而使大型数据库作为一个丰富、可靠的资源为知识的提取服务。
1.1.2 聚类
聚类是把一组个体按照相似性归成若干类别，它的目的是使得属于同一类别的个体之间的差别尽可能的小，而不同类别上的个体间的差别尽可能的大。数据挖掘的目标之一是进行聚类分析。通过聚类技术可以对源数据库中的记录划分为
一系列有意义的子集，进而实现对数据的分析。聚类与分类技术不同，前者总是在特定的类标识下寻求新元素属于哪个类，而后者则是通过对数据的分析比较生成新的类标识。聚类分析生成的类标识刻画了数据所蕴含的类知识。当然，数据挖掘中的分类和聚类技术都是在已有的技术基础上发展起来的，它们互有交叉和补充。
目前，数据挖掘研究中的聚类技术研究也是一个热点问题。1999年，Jain 等给出了聚类研究中的主要问题和方法。聚类技术主要是以统计方法、机器学习、神经网络等方法为基础的。作为统计学的一个重要分支，聚类分析已经被广泛地研究和应用。比较有代表性的聚类技术是基于几何距离度量的聚类方法，如欧式距离、曼哈坦距离、明考斯基距离等。在很多情况下，聚类的结果是形成一个概念，即当一组数据对象可以由一个概念来描述时，就形成一个簇。因此，有的文献中又称其为概念聚类。所以，一些问题可能不再是传统统计方法中的几何距离所能描述的，而是根据概念的描述来确定。
1.1.3 聚类分析概述
聚类分析源于许多研究领域，包括数据挖掘、统计学、机器学习、模式识别等。它是数据挖掘中的一个功能，但也能作为一个独立的工具来获得数据分布的情况，概况出每个簇的特点，或者集中注意力对特定的某些簇作进一步的分析。此外，聚类分析也可以作为其他分析算法的预处理步骤，这些算法在生成的簇上进行处理。
数据挖掘技术的一个突出的特点是处理巨大的、复杂的数据集，这对聚类分析技术提出了特殊的挑战，要求算法具有可伸缩性、处理不同类型属性的能力、发现任意形状的类的能力、处理高维数据的能力等。根据潜在的各项应用，数据挖掘对聚类分析方法提出了不同要求。典型要求可以通过以下几个方面来刻画。
1．可伸缩性
可伸缩性是指聚类算法不论对于小数据集还是对于大数据集，都应是有效的。在很多聚类算法当中，数据对象小于几百个的小数据集合上鲁棒性很好，而对于包含上万个数据对象的大规模数据库进行聚类时，将会导致不同的偏差结果。研究大容量数据集的高效聚类方法是数据挖掘必须面对的挑战。
2．具有处理不同类型属性的能力
既可处理数据型数据，又可处理非数据型数据，既可以处理离散数据，又可以处理连续域内的数据，如布尔型，序数型，枚举型或这些数据类型的混合。
3．能够发现任意形状的聚类
许多聚类算法经常使用欧几里得距离来作为相似性度量方法，但基于这样的距离度量的算法趋向于发现具有相近密度和尺寸的球状簇。但对于一个簇可能是任意形状的情况，提出能发现任意形状簇的算法是很重要的。
4．输入参数对领域知识的弱依赖性
在聚类分析当中，许多聚类算法要求用户输入一定的参数，如希望得到的簇的数目。聚类结果对于输入的参数很敏感，通常参数较难确定，尤其是对于含有高维对象的数据集更是如此。要求用人工输入参数不但加重了用户的负担，也使得聚类质量难以控制。一个好的聚类算法应该对这个问题给出一个好的解决方法。
5．对于输入记录顺序不敏感
一些聚类算法对于输入数据的顺序是敏感的。例如，对于同一个数据集合，以不同的顺序提交给同一个算法时，可能产生差别很大的聚类结果。研究和开发对数据输入顺序不敏感的算法具有重要的意义。
6．挖掘算法应具有处理高维数据的能力
既可处理属性较少的数据，又能处理属性较多的数据。很多聚类算法擅长处理低维数据，一般只涉及两到三维，人类对两三维数据的聚类结果很容易直观地判断聚类的质量。但是，高维数据聚类结果的判断就不是直观了。数据对象在高维空间的聚类是非常具有挑战性的，尤其是考虑到这样的数据可能高度偏斜并且非常稀疏。
7．处理噪声数据的能力
在现实应用中绝大多数的数据都包含了孤立点、空缺、未知数据或者错误的数据。如果聚类算法对于这样的数据敏感，将会导致质量较低的聚类结果。
8．基于约束的聚类
在实际应用当中可能需要在各种约束条件下进行聚类。既要找到满足特定的约束，又要具有良好聚类特性的数据分组是一项具有挑战性的任务。
9．挖掘出来的信息是可理解的和可用的
这点是容易理解的，但在实际挖掘中有时往往不能令人满意。
聚类分析在数据挖掘中的应用主要有以下几个方面：
1．聚类分析可以作为其他算法的预处理步骤
利用聚类进行数据预处理，可以获得数据的基本概况，在此基础上进行特征抽取或分类就可以提高精确度和挖掘效率。也可将聚类结果用于进一步关联分析，以进一步获得有用的信息。
2．可以作为一个独立的工具来获得数据的分布情况
聚类分析是获得数据分析情况的有效方法。例如，在商业上，聚类分析可以帮助市场分析人员从客户基本库当中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。通过观察聚类得到的每个簇的特点，可以集中对特定的某些簇作进一步分析。这在诸如市场细分、目标顾客定位、业绩评估、生物种群划分等方面具有广阔的应用前景。
3．聚类分析可以完成孤立点挖掘
许多数据挖掘算法试图使孤立点影响最小化，或者排除它们。然而孤立点本身可能是非常有用的。如在欺诈探测中，孤立点可能预示着欺诈行为的存在。
1.2 PAM算法分析
1.2.1 PAM算法详细论述
PAM（Partitioning Around Medoid,围绕中心点的划分）是聚类分析算法中划分法的一个聚类方法，是最早提出的k-中心点算法之一。PAM聚类算法的基本思想为：选用簇中位置最中心的对象，试图对n个对象给出k个划分；代表对象也被称为是中心点，其他对象则被称为非代表对象；最初随机选择k个对象作为中心点，该算法反复地用非代表对象来代替代表对象，试图找出更好的中心点，以改进聚类的质量；在每次迭代中，所有可能的对象对被分析，每个对中的一个对象是中心点，而另一个是非代表对象。对可能的各种组合，估算聚类结果的质量；一个对象O
i
可以被使最大平方-误差值减少的对象代替；在一次迭代中产生的最佳对象集合成为下次迭代的中心点。
为了判定一个非代表对象O
h 是否是当前一个代表对象O
i
的好的替代，对于
每一个非中心点对象O
j
，下面的四种情况被考虑：
第一种情况：假设O i被O h代替作为新的中心点，O j当前隶属于中心点对
象O
i 。如果O
j
离某个中心点Om最近，i≠m，那么O
j
被重新分配给Om。
●第二种情况：假设O i被O h代替作为新的中心点，O j当前隶属于中心点对
象O
i 。如果O
j
离这个新的中心点O
h
最近，那么O
j
被分配给O
h
。
●第三种情况：假设O i被O h代替作为新的中心点，但是O j当前隶属于另
一个中心点对象O
m ，m≠i。如果O
j
依然离O
m
最近，那么对象的隶属不发
生变化。
●第四种情况：假设O i被O h代替作为新的中心点，但是O j当前隶属于另
一个中心点对象O
m ，m≠i。如果O
j
离这个新的中心点O
h
最近，那么O
i
被重新分配给O
h
。
每当重新分配发生时，平方-误差E所产生的差别对代价函数有影响。因此，如果一个当前的中心点对象被非中心点对象所代替，代价函数计算平方-误差值所产生的差别。替换的总代价是所有非中心点对象所产生的代价之和。如果总代
价是负的，那么实际的平方-误差将会减小，O
i 可以被O
h
替代。如果总代价是正
的，则当前的中心点O
i
被认为是可接受的，在本次迭代中没有变化。
PAM算法需用簇中位置最靠近中心的对象作为代表对象，然后反复地用非代表对象来代替代表对象，试图找出更好的中心点，在反复迭代的过程中，所有可能的“对象对”被分析，每个对中的一个对象是中心点，另一个是非代表对象。一个对象代表可以被最大平方-误差值减少的对象代替。
一个非代表对象O
h 是否是当前一个代表对象O
i
的一个好的替代，对于每个
非中心点对象O
j
，有以下四种情况需要考虑：
（1） O
j 当前隶属于O
i
，如果O
i
被O
h
替换，且O
j
离另一个Om最近，i！=m，
那么O
j 被分配给O
m
，则替换代价为C
jih
=d(j,m)-d(j,i)。
（2）O
j 当前隶属于O
i
，如果O
i
被O
h
替换，且O
j
离O
h
最近，那么O
j
被分配给
Oh，则替换代价为C
jih
=d(j,h)-d(j,i)。
（3）O
j 当前隶属于O
m
，m！=i，如果O
i
被O
h
替换，且O
j
仍然离O
m
最近，那
么O
j 被分配给O
m
，则替换代价为C
jih
=0。
（4） O
j
当前隶属于O
m
，m！=i，如果O
i
被O
h
替换，且O
j
离O
h
最近，那么
O j 被分配给O
h
，则替换代价为C
jih
=d(j,h)-d(j,m)。
1.2.2 PAM算法描述
输入：簇的数目k和包含n个对象的数据库
输出：k个簇，使得所有对象与其最近中心点的相异度总和最小（1）任意选择k个对象作为初始的簇中心点
（2） Repeat
（3）指派每个剩余对象给离他最近的中心点所表示的簇（4） Repeat
（5）选择一个未被选择的中心点O
i
（6） Repeat
（7）选择一个未被选择过的非中心点对象O
h
（8）计算用O
h 代替O
i
的总代价并记录在S中
（9） Until 所有非中心点都被选择过
（10） Until 所有的中心点都被选择过
（11） If 在S中的所有非中心点代替所有中心点后的计算出总代价有小于0的存在，then找出S中的用非中心点替代中心点后代价最小的一个，并用该非中心点替代对应的中心点，形成一个新的k个中心点的集合；
（12） Until 没有再发生簇的重新分配，即所有的S都大于0.
1.2.3 PAM算法性能分析
(1) 消除了k-平均算法对于孤立点的敏感性。
(2) K-中心点方法比k-平均算法的代价要高
(3) 必须指定k
(4) PAM对小的数据集非常有效，对大数据集效率不高。特别是n和k 都很大的时候。
2PAM算法的实现
2．1 简要说明
通过一个实例来描述PAM聚类算法的实现过程，实例中使用matlab工具来编写PAM聚类算法的实现过程代码。使用excel数据作为模拟数据。通过导入模拟数据然后进行聚类。
2．2 matlab简介
MATLAB是矩阵实验室（Matrix Laboratory）的简称，是美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。2．2．1 matlab基本功能
MATLAB是由美国mathworks公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式程序设计语言（如C、Fortran）的编辑模式，代表了当今国际科学计算软件的先进水平。
MATLAB和Mathematica、Maple并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。MATLAB可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域。
2.3 算法实现
自定义一个函数
function [result,c,s,index,label]=kpam(data,k);
result表示聚类结果
c表示聚类最后的中心点
index表示随机排列的行号
label表示数据每一行属于第几个中心点
随机选着k个中心点
[N,n]=size(data);
index=randperm(N);
v=data(index(1:k),:);
for t=1:100
指派每个剩余的对象个离它最近的中心点所代表的簇
if k==1
for j=1:N
label(j)=1;
end
else
for i=1:k
label(index(i))=i;
end
for j=k+1:N
for i=1:k
dist(:,i)=sqrt(sum((data(index(j),:)-v(i,:)).^2));
end
[m,l]=min(dist');
label(index(j))=l;
end
end
for i=1:k
c(i,:)=v(i,:);
end
所有非中心点被选择过，所有的中心点被选择过
for i=1:k
for h=k+1:N
for j=1:N
c(i,:)=data(index(h),:);
dist1=sqrt(sum((data(j,:)-c(i,:)).^2));
for z=1:k
dist2(z)=
sqrt(sum((data(j,:)-c(z,:)).^2));
end
for y=1:k
dist4(y)=sqrt(sum((data(j,:)-v(y,:)).^2));
end
dist3= sqrt(sum((data(j,:)-v(i,:)).^2));
if label(j)==i
if dist1==min(dist2)
cjih(j,:)=dist1-dist3;
else
cjih(j,:)=min(dist2)-dist3;
end
else
if dist1==min(dist2)
cjih(j,:)=dist1-min(dist4);
else
cjih(j,:)=0;
end
end
c(i,:)=v(i,:);
s1(j,:)=cjih(j,:);
end
一个非中心点代替一个中心点的总代价s
s((h-k),:,i)=sum(cjih(:,:),1);
end
end
if min(min(s))==0
for i=1:k
for h=k+1:N
if s((h-k),:,i)==min(min(s))
s((h-k),:,i)=1;
end
end
end
end
If 在S中的所有非中心点代替所有中心点后的计算出总代价有小于0的存在，then找出S中的用非中心点替代中心点后代价最小的一个，并用该非中心点替代对应的中心点，形成一个新的k个中心点的集合
if min(min(s))<0
for i=1:k
for h=k+1:N
if s((h-k),:,i)==min(min(s))
v(i,:)=data(index(h),:);
break;
end
end
if data(index(i),:)~=data(index(h),:)
if v(i,:)==data(index(h),:)
break;
end
end
end
a=index(i);
b=index(h);
index(i)=b;
index(h)=a;
end
所有的s都大于0则聚类完成
if min(min(s))>0
break;
end
end
for i=1:k
for j=1:N
if label(j)==i
result(j,:,i)=data(j,:);
end
end
end
模拟数据导入与调用自定义函数程序
clear all;
[filename, pathname]= uigetfile('*.xls');
file=[pathname filename];
x=xlsread(file);
data=x(:,:);
[N,n]=size(data);
k=input('Enter the number of cluster you want to have:'); for d=1:100
if k>=N
k=input('您输入的值应小于N请重新输入:');
end
if k break; end end [result,c,s,index,label]=kpam(data,k); 对于result 还要出理下这里就不给出代码了。 2.4 PAM 聚类算法在学生成绩中的应用 学生成绩是评估教学质量的重要依据，也是评价学生是否掌握好所学知识的重要标志。因此，如何科学、准确、公平、公正地给学生评定成绩，是教学的一项重要的工作。为了成为以后对成绩进行各种分析的基础，本文使用PAM 聚类算法对学生成绩进行聚类。 表1所示是33个学生的某科成绩（取部分学生成绩显示） 表1 序号 成绩 1 2 3 4 83 83 89 81 随机选取5个中心点，图1表示聚类完成后中心点集 图1 图2表示聚类结果 图2 通过PAM聚类后可以发现74-76有5个人，80-85有11个人，57-64有4个人，66-71有5个人，87到91有8个。这样比较合理地给学生成绩划分等级，比较科学、公正、合理地反应学生对此门课程掌握情况以及此门课的教学效果。 3 小结 PAM聚类算法对于小的数据集非常有效，但对于大数据集其效率不高。因为在替换中心点时每个点的替换代价都可能计算，因此，当n和k很大时，这样的计算代价相当高。 致谢 本论文最终得以成功完成，非常感谢我的指导老师。正是他给予我尽心尽力的指导，才使论文能够最终完成。严谨的治学态度深深的影响着我，对我今后的学习、工作、生活必将产生影响。借此机会，特向老师表示最诚挚的感谢。 大学本科的学习生活即将结束，在此，我要感谢所有曾经教导过我的老师和关心过我的同学，他们在我成长过程中给予了我很大的帮助。 参考文献： [1]毛国君，等.数据挖掘原理与算法（第二版）[M].北京：清华大学出版社,2007.12 [2] Jiawei Han,Micheline Kamber.数据挖掘：概念与技术[M].北京：机械工业出版社， 2001. [3] 陈京民，等.数据仓库与数据挖掘技术[M].北京：电子工业出版社，2002. [4] 刘同明，等.数据挖掘技术及其应用[M].北京:国防工业出版社，2001. [5] David Hand,等.数据挖掘原理[M].张银奎，等译.北京: 机械工业出版社，中信出 版社，2004. 毕业论文（设计）论文（设计）题目：PAM聚类算法的分析与实现 系别： 专业： 学号： 姓名： 指导教师： 时间： 毕业论文（设计）开题报告 系别:计算机与信息科学系专业:网络工程 学号姓名高华荣 论文（设计）题目PAM聚类算法的分析与实现 命题来源□√教师命题□学生自主命题□教师课题 选题意义(不少于300字): 随着计算机技术、网络技术的迅猛发展与广泛应用，人们面临着日益增多的业务数据，这些数据中往往隐含了大量的不易被人们察觉的宝贵信息，为了得到这些信息，人们想尽了一切办法。数据挖掘技术就是在这种状况下应运而生了。而聚类知识发现是数据挖掘中的一项重要的内容。 在日常生活、生产和科研工作中，经常要对被研究的对象经行分类。而聚类分析就是研究和处理给定对象的分类常用的数学方法。聚类就是将数据对象分组成多个簇，同一个簇中的对象之间具有较高的相似性，而不同簇中的对象具有较大的差异性。 在目前的许多聚类算法中，PAM算法的优势在于：PAM算法比较健壮，对“噪声”和孤立点数据不敏感；由它发现的族与测试数据的输入顺序无关；能够处理不同类型的数据点。 研究综述(前人的研究现状及进展情况，不少于600字): PAM（Partitioning Around Medoid,围绕中心点的划分）算法是是划分算法中一种很重要的算法，有时也称为k-中心点算法，是指用中心点来代表一个簇。PAM算法最早由Kaufman和Rousseevw提出，Medoid的意思就是位于中心位置的对象。PAM算法的目的是对n个数据对象给出k个划分。PAM算法的基本思想：PAM算法的目的是对成员集合D中的N个数据对象给出k个划分，形成k个簇，在每个簇中随机选取1个成员设置为中心点，然后在每一步中，对输入数据集中目前还不是中心点的成员根据其与中心点的相异度或者距离进行逐个比较，看是否可能成为中心点。用簇中的非中心点到簇的中心点的所有距离之和来度量聚类效果，其中成员总是被分配到离自身最近的簇中，以此来提高聚类的质量。 由于PAM算法对小数据集非常有效，但对大的数据集合没有良好的可伸缩性，就出现了结合PAM的CLARA（Cluster LARger Application）算法。CLARA是基于k-中心点类型的算法，能处理更大的数据集合。CLARA先抽取数据集合的多个样本，然后用PAM方法在抽取的样本中寻找最佳的k个中心点，返回最好的聚类结果作为输出。后来又出现了CLARNS（Cluster Larger Application based upon RANdomized 数据挖掘聚类问题(Plants Data Set)实验报告 1.数据源描述 1.1数据特征 本实验用到的是关于植物信息的数据集，其中包含了每一种植物(种类和科属)以及它们生长的地区。数据集中总共有68个地区，主要分布在美国和加拿大。一条数据(对应于文件中的一行)包含一种植物(或者某一科属)及其在上述68个地区中的分布情况。可以这样理解，该数据集中每一条数据包含两部分内容，如下图所示。 图1 数据格式 例如一条数据:abronia fragrans,az,co,ks,mt,ne,nm,nd,ok,sd,tx,ut,wa,wy。其中abronia fragrans是植物名称(abronia是科属，fragrans是名称)，从az一直到wy 是该植物的分布区域，采用缩写形式表示，如az代表的是美国Arizona州。植物名称和分布地区用逗号隔开，各地区之间也用逗号隔开。 1.2任务要求 聚类。采用聚类算法根据某种特征对所给数据集进行聚类分析，对于聚类形成的簇要使得簇内数据对象之间的差异尽可能小，簇之间的差距尽可能大。 2.数据预处理 2.1数据清理 所给数据集中包含一些对聚类过程无用的冗余数据。数据集中全部数据的组织结构是：先给出某一科属的植物及其所有分布地区，然后给出该科属下的具体植物及其分布地区。例如： ①abelmoschus,ct,dc,fl,hi,il,ky,la,md,mi,ms,nc,sc,va,pr,vi ②abelmoschus esculentus,ct,dc,fl,il,ky,la,md,mi,ms,nc,sc,va,pr,vi ③abelmoschus moschatus,hi,pr 上述数据中第①行给出了所有属于abelmoschus这一科属的植物的分布地区，接下来的②③两行分别列出了属于abelmoschus科属的两种具体植物及其分布地区。从中可以看出后两行给出的所有地区的并集正是第一行给出的地区集 实验三 K-Means聚类算法 一、实验目的 1) 加深对非监督学习的理解和认识 2) 掌握动态聚类方法K-Means 算法的设计方法 二、实验环境 1) 具有相关编程软件的PC机 三、实验原理 1) 非监督学习的理论基础 2) 动态聚类分析的思想和理论依据 3) 聚类算法的评价指标 四、算法思想 K-均值算法的主要思想是先在需要分类的数据中寻找K组数据作为初始聚类中心，然后计算其他数据距离这三个聚类中心的距离，将数据归入与其距离最近的聚类中心，之后再对这K个聚类的数据计算均值，作为新的聚类中心，继续以上步骤，直到新的聚类中心与上一次的聚类中心值相等时结束算法。 实验代码 function km(k,A)%函数名里不要出现“-” warning off [n,p]=size(A);%输入数据有n个样本，p个属性 cid=ones(k,p+1);%聚类中心组成k行p列的矩阵,k表示第几类，p是属性 %A(:,p+1)=100; A(:,p+1)=0; for i=1:k %cid(i,:)=A(i,:); %直接取前三个元祖作为聚类中心 m=i*floor(n/k)-floor(rand(1,1)*(n/k)) cid(i,:)=A(m,:); cid; end Asum=0; Csum2=NaN; flags=1; times=1; while flags flags=0; times=times+1; %计算每个向量到聚类中心的欧氏距离 for i=1:n for j=1:k dist(i,j)=sqrt(sum((A(i,:)-cid(j,:)).^2));%欧氏距离 end %A(i,p+1)=min(dist(i,:));%与中心的最小距离 [x,y]=find(dist(i,:)==min(dist(i,:))); [c,d]=size(find(y==A(i,p+1))); if c==0 %说明聚类中心变了 flags=flags+1; A(i,p+1)=y(1,1); else continue; end end i flags for j=1:k Asum=0; [r,c]=find(A(:,p+1)==j); cid(j,:)=mean(A(r,:),1); for m=1:length(r) Asum=Asum+sqrt(sum((A(r(m),:)-cid(j,:)).^2)); end Csum(1,j)=Asum; end sum(Csum(1,:)) %if sum(Csum(1,:))>Csum2 % break; %end Csum2=sum(Csum(1,:)); Csum; cid; %得到新的聚类中心 end times display('A矩阵，最后一列是所属类别'); A for j=1:k [a,b]=size(find(A(:,p+1)==j)); numK(j)=a; end numK times xlswrite('data.xls',A); 聚类分析算法解析 一、不相似矩阵计算 1.加载数据 data(iris) str(iris) 分类分析是无指导的分类，所以删除数据中的原分类变量。 iris$Species<-NULL 2. 不相似矩阵计算 不相似矩阵计算，也就是距离矩阵计算，在R中采用dist()函数，或者cluster包中的daisy()函数。dist()函数的基本形式是 dist(x, method = "euclidean", diag = FALSE, upper = FALSE, p = 2) 其中x是数据框（数据集），而方法可以指定为欧式距离"euclidean", 最大距离"maximum", 绝对值距离"manhattan", "canberra", 二进制距离非对称"binary" 和明氏距离"minkowski"。默认是计算欧式距离，所有的属性必须是相同的类型。比如都是连续类型，或者都是二值类型。 dd<-dist(iris) str(dd) 距离矩阵可以使用as.matrix()函数转化了矩阵的形式，方便显示。Iris数据共150例样本间距离矩阵为150行列的方阵。下面显示了1~5号样本间的欧式距离。 dd<-as.matrix(dd) 二、用hclust()进行谱系聚类法（层次聚类） 1.聚类函数 R中自带的聚类函数是hclust()，为谱系聚类法。基本的函数指令是 结果对象 <- hclust（距离对象, method=方法） hclust()可以使用的类间距离计算方法包含离差法"ward"，最短距离法"single"，最大距离法"complete"，平均距离法"average"，"mcquitty"，中位数法 "median" 和重心法"centroid"。下面采用平均距离法聚类。 hc <- hclust(dist(iris), method="ave") 2.聚类函数的结果 聚类结果对象包含很多聚类分析的结果，可以使用数据分量的方法列出相应的计算结果。 str(hc) 下面列出了聚类结果对象hc包含的merge和height结果值的前6个。其行编号表示聚类过程的步骤，X1，X2表示在该步合并的两类，该编号为负代表原始的样本序号，编号为正代表新合成的类；变量height表示合并时两类类间距离。比如第1步，合并的是样本102和143，其样本间距离是0.0，合并后的类则使用该步的步数编号代表，即样本-102和-143合并为1类。再如第6行表示样本11和49合并，该两个样本的类间距离是0.1，合并后的类称为6类。 head (hc$merge,hc$height) 聚类算法的种类： --------------------------------------------------------- 几种常用的聚类算法从可伸缩性、适合的数据类型、高维性（处理高维数据的能力）、异常数据的抗干扰度、聚类形状和算法效率6个方面进行了综合性能评价，评价结果如表1所示： --------------------------------------------------------- 目前聚类分析研究的主要内容： 对聚类进行研究是数据挖掘中的一个热门方向，由于以上所介绍的聚类方法都 存在着某些缺点，因此近些年对于聚类分析的研究很多都专注于改进现有的聚 类方法或者是提出一种新的聚类方法。以下将对传统聚类方法中存在的问题以 及人们在这些问题上所做的努力做一个简单的总结： 1 从以上对传统的聚类分析方法所做的总结来看，不管是k-means方法，还是CURE方法，在进行聚类之前都需要用户事先确定要得到的聚类的数目。然而在 现实数据中，聚类的数目是未知的，通常要经过不断的实验来获得合适的聚类 数目，得到较好的聚类结果。 2 传统的聚类方法一般都是适合于某种情况的聚类，没有一种方法能够满足各 种情况下的聚类，比如BIRCH方法对于球状簇有很好的聚类性能，但是对于不 规则的聚类，则不能很好的工作；K-medoids方法不太受孤立点的影响，但是 其计算代价又很大。因此如何解决这个问题成为当前的一个研究热点，有学者 提出将不同的聚类思想进行融合以形成新的聚类算法，从而综合利用不同聚类 算法的优点，在一次聚类过程中综合利用多种聚类方法，能够有效的缓解这个 问题。 3 随着信息时代的到来，对大量的数据进行分析处理是一个很庞大的工作，这 就关系到一个计算效率的问题。有文献提出了一种基于最小生成树的聚类算法，该算法通过逐渐丢弃最长的边来实现聚类结果，当某条边的长度超过了某个阈值，那么更长边就不需要计算而直接丢弃，这样就极大地提高了计算效率，降 低了计算成本。 4 处理大规模数据和高维数据的能力有待于提高。目前许多聚类方法处理小规 模数据和低维数据时性能比较好，但是当数据规模增大，维度升高时，性能就 会急剧下降，比如k-medoids方法处理小规模数据时性能很好，但是随着数据 量增多，效率就逐渐下降，而现实生活中的数据大部分又都属于规模比较大、 维度比较高的数据集。有文献提出了一种在高维空间挖掘映射聚类的方法PCKA （Projected Clustering based on the K-Means Algorithm），它从多个维度中选择属性相关的维度，去除不相关的维度，沿着相关维度进行聚类，以此对 高维数据进行聚类。 5 目前的许多算法都只是理论上的，经常处于某种假设之下，比如聚类能很好 的被分离，没有突出的孤立点等，但是现实数据通常是很复杂的，噪声很大， 因此如何有效的消除噪声的影响，提高处理现实数据的能力还有待进一步的提高。 对数据进行聚类分析实验报告 1.方法背景 聚类分析又称群分析，是多元统计分析中研究样本或指标的一种主要的分类方法，在古老的分类学中，人们主要靠经验和专业知识，很少利用数学方法。随着生产技术和科学的发展，分类越来越细，以致有时仅凭经验和专业知识还不能进行确切分类，于是数学这个有用的工具逐渐被引进到分类学中，形成了数值分类学。近些年来，数理统计的多元分析方法有了迅速的发展，多元分析的技术自然被引用到分类学中，于是从数值分类学中逐渐的分离出聚类分析这个新的分支。结合了更为强大的数学工具的聚类分析方法已经越来越多应用到经济分析和社会工作分析中。在经济领域中，主要是根据影响国家、地区及至单个企业的经济效益、发展水平的各项指标进行聚类分析，然后很据分析结果进行综合评价，以便得出科学的结论。 2.基本要求 用FAMALE.TXT、MALE.TXT和/或test2.txt的数据作为本次实验使用的样本集，利用C均值和分级聚类方法对样本集进行聚类分析，对结果进行分析，从而加深对所学内容的理解和感性认识。 3.实验要求 （1）把FAMALE.TXT和MALE.TXT两个文件合并成一个，同时采用身高和体重数据作为特征，设类别数为2，利用C均值聚类方法对数据进行聚类，并将聚类结果表示在二维平面上。尝试不同初始值对此数据集是否会造成不同的结果。 （2）对1中的数据利用C均值聚类方法分别进行两类、三类、四类、五类聚类，画出聚类指标与类别数之间的关系曲线，探讨是否可以确定出合理的类别数目。 （3）对1中的数据利用分级聚类方法进行聚类，分析聚类结果，体会分级聚类方法。。（4）利用test2.txt数据或者把test2.txt的数据与上述1中的数据合并在一起，重复上述实验，考察结果是否有变化，对观察到的现象进行分析，写出体会 4.实验步骤及流程图 根据以上实验要求，本次试验我们将分为两组：一、首先对FEMALE 与MALE中数据组成的样本按照上面要求用C均值法进行聚类分析，然后对FEMALE、MALE、test2中数据组成的样本集用C均值法进行聚类分析，比较二者结果。二、将上述两个样本用分即聚类方法进行聚类，观察聚类结果。并将两种聚类结果进行比较。 （1）、C均值算法思想 一、层次聚类 1、层次聚类的原理及分类 1）层次法（Hierarchical methods）先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后，再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成了一个类。其中类与类的距离的计算方法有：最短距离法，最长距离法，中间距离法，类平均法等。比如最短距离法，将类与类的距离定义为类与类之间样本的最短距离。 层次聚类算法根据层次分解的顺序分为：自下底向上和自上向下，即凝聚的层次聚类算法和分裂的层次聚类算法（agglomerative和divisive），也可以理解为自下而上法（bottom-up）和自上而下法（top-down）。自下而上法就是一开始每个个体（object）都是一个 类，然后根据linkage寻找同类，最后形成一个“类”。自上而下法就是反过来，一开始所有个体都属于一个“类”，然后根据linkage排除异己，最后每个个体都成为一个“类”。这两种路方法没有孰优孰劣之分，只是在实际应用的时候要根据数据特点以及你想要的“类”的个数，来考虑是自上而下更快还是自下而上更快。至于根据Linkage判断“类” 的方法就是最短距离法、最长距离法、中间距离法、类平均法等等（其中类平均法往往被认为是最常用也最好用的方法，一方面因为其良好的单调性，另一方面因为其空间扩张/浓缩的程度适中）。为弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位。 2）Hierarchical methods中比较新的算法有BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies利用层次方法的平衡迭代规约和聚类）主要是在数据量很大的时候使用，而且数据类型是numerical。首先利用树的结构对对象集进行划分，然后再利用其它聚类方法对这些聚类进行优化；ROCK（A Hierarchical Clustering Algorithm for Categorical Attributes）主要用在categorical的数据类型上；Chameleon（A Hierarchical Clustering Algorithm Using Dynamic Modeling）里用到的linkage是kNN（k-nearest-neighbor）算法，并以此构建一个graph，Chameleon的聚类效果被认为非常强大，比BIRCH好用，但运算复杂度很高，O(n^2)。 2、层次聚类的流程 凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。这里给出采用最小距离的凝聚层次聚类算法流程： (1) 将每个对象看作一类，计算两两之间的最小距离； (2) 将距离最小的两个类合并成一个新类； (3) 重新计算新类与所有类之间的距离； (4) 重复(2)、(3)，直到所有类最后合并成一类。 1.聚类定义 “聚类是把相似的对象通过静态分类的方法分成不同的组别或者更多的子集（subset）,这样让在同一个子集中的成员对象都有一些相似的属性”——wikipedia “聚类分析指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程。它是一种重要的人类行为。聚类是将数据分类到不同的类或者簇这样的一个过程，所以同一个簇中的对象有很大的相似性，而不同簇间的对象有很大的相异性。”——百度百科 说白了，聚类（clustering）是完全可以按字面意思来理解的——将相同、相似、相近、相关的对象实例聚成一类的过程。简单理解，如果一个数据集合包含N个实例，根据某种准则可以将这N 个实例划分为m个类别，每个类别中的实例都是相关的，而不同类别之间是区别的也就是不相关的，这个过程就叫聚类了。 2.聚类过程: 1) 数据准备:包括特征标准化和降维. 2) 特征选择:从最初的特征中选择最有效的特征,并将其存储于向量中. 3) 特征提取:通过对所选择的特征进行转换形成新的突出特征. 4) 聚类(或分组):首先选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量;而后执行聚类或分组. 5) 聚类结果评估:是指对聚类结果进行评估.评估主要有3 种:外部有效性评估、内部有效性评估和相关性测试评估. 3聚类算法的类别 没有任何一种聚类技术(聚类算法)可以普遍适用于揭示各种多维数据集所呈现出来的多种多样的结构，根据数据在聚类中的积聚规则以及应用这些规则的方法,有多种聚类算法.聚类算法有多种分类方法将聚类算法大致分成层次化聚类算法、划分式聚类算法、基于密度和网格的聚类算法和其他聚类算法,如图1 所示 的4 个类别. 聚类分析K-means算法综述 摘要：介绍K-means聚类算法的概念，初步了解算法的基本步骤，通过对算法缺点的分析，对算法已有的优化方法进行简单分析，以及对算法的应用领域、算法未来的研究方向及应用发展趋势作恰当的介绍。 关键词：K-means聚类算法基本步骤优化方法应用领域研究方向应用发展趋势 算法概述 K-means聚类算法是一种基于质心的划分方法，输入聚类个数k，以及包含n个数据对象的数据库，输出满足方差最小标准的k个聚类。 评定标准：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算。 解释：基于质心的划分方法就是将簇中的所有对象的平均值看做簇的质心，然后根据一个数据对象与簇质心的距离，再将该对象赋予最近的簇。 k-means 算法基本步骤 （1）从n个数据对象任意选择k 个对象作为初始聚类中心 （2）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分 （3）重新计算每个（有变化）聚类的均值（中心对象） （4）计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤（2） 形式化描述 输入：数据集D，划分簇的个数k 输出：k个簇的集合 （1）从数据集D中任意选择k个对象作为初始簇的中心； （2）Repeat （3）For数据集D中每个对象P do （4）计算对象P到k个簇中心的距离 （5）将对象P指派到与其最近（距离最短）的簇； （6）End For （7）计算每个簇中对象的均值，作为新的簇的中心； （8）Until k个簇的簇中心不再发生变化 对算法已有优化方法的分析 (1)K-means算法中聚类个数K需要预先给定 这个K值的选定是非常难以估计的，很多时候,我们事先并不知道给定的数据集应该分成多少个类别才最合适，这也是K一means算法的一个不足"有的算法是通过类的自动合并和分裂得到较为合理的类型数目k，例如Is0DAIA算法"关于K一means算法中聚类数目K 值的确定，在文献中，根据了方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分嫡来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵RPCL算法，并逐步删除那些只包含少量训练数据的类。文献中针对“聚类的有效性问题”提出武汉理工大学硕士学位论文了一种新的有效性指标：V(k km) = Intra(k) + Inter(k) / Inter(k max)，其中k max是可聚类的最大数目,目的是选择最佳聚类个数使得有效性指标达到最小。文献中使用的是一种称为次胜者受罚的竞争学习规则来自动决定类的适当数目"它的思想是：对每个输入而言不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法使之远离输入值。 (2)算法对初始值的选取依赖性极大以及算法常陷入局部极小解 不同的初始值，结果往往不同。K-means算法首先随机地选取k个点作为初始聚类种子，再利用迭代的重定位技术直到算法收敛。因此，初值的不同可能导致算法聚类效果的不稳定，并且，K-means算法常采用误差平方和准则函数作为聚类准则函数(目标函数)。目标函数往往存在很多个局部极小值，只有一个属于全局最小，由于算法每次开始选取的初始聚类中心落入非凸函数曲面的“位置”往往偏离全局最优解的搜索范围，因此通过迭代运算，目标函数常常达到局部最小，得不到全局最小。对于这个问题的解决，许多算法采用遗传算法(GA)，例如文献中采用遗传算法GA进行初始化，以内部聚类准则作为评价指标。 (3)从K-means算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时,算法的时间开销是非常大 所以需要对算法的时间复杂度进行分析，改进提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的候选集，而在文献中，使用的K-meanS算法是对样本数据进行聚类。无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。 K-均值聚类算法报告 摘要 K-均值是聚类方法中长用的一种划分方法，有很多优点，本文主要对K-均值是聚类方法的产生，工作原理，一般步骤，以及它的源码进行简单的介绍，了解K-均值是聚类！！！ （一）课题名称：K-均值聚类(K-means clustering) （二）课题分析： J.B.MacQueen 在 1967 年提出的K-means算法[22]到目前为止用于科学和工业应用的诸多聚类算法中一种极有影响的技术。它是聚类方法中一个基本的划分方法，常常采用误差平方和准则函数作为聚类准则函数，误差平方和准则函数定义为： K-means 算法的特点——采用两阶段反复循环过程算法，结束的条件是不再有数据元素被重新分配： ① 指定聚类，即指定数据到某一个聚类，使得它与这个聚类中心的距离比它到其它聚类中心的距离要近。 ② 修改聚类中心。 优点：本算法确定的K 个划分到达平方误差最小。当聚类是密集的，且类与类之间区别明显时，效果较好。对于处理大数据集，这个算法是相对可伸缩和高效的，计算的复杂度为O(NKt)，其中N是数据对象的数目，t是迭代的次数。一般来说，K< （1）从 n个数据对象任意选择 k 个对象作为初始聚类中心； （2）循环（3）到（4）直到每个聚类不再发生变化为止； （3）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分； （4）重新计算每个（有变化）聚类的均值（中心对象） k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 （三）总体检索思路： 利用goole，百度，搜狗等搜索引擎及校内的一些数据库进行相关内容的检索。主要检索内容为K-均值聚类算法的工作原理，一般步骤，源码。 （四）检索过程记录： 关键词：K-均值聚类算法 搜索引擎：百度 检索内容：①K-均值聚类算法工作原理 ②K-均值聚类算法的一般步骤 ③K-均值聚类算法的源码 嵌入式方向工程设计实验报告 学院班级：130712 学生学号：13071219 学生姓名：杨阳 同作者：无 实验日期：2010年12月 聚类算法分析研究 1 实验环境以及所用到的主要软件 Windows Vista NetBeans6.5.1 Weka3.6 MATLAB R2009a 2 实验内容描述 聚类是对数据对象进行划分的一种过程，与分类不同的是，它所划分的类是未知的，故此，这是一个“无指导的学习” 过程，它倾向于数据的自然划分。其中聚类算法常见的有基于层次方法、基于划分方法、基于密度以及网格等方法。本文中对近年来聚类算法的研究现状与新进展进行归纳总结。一方面对近年来提出的较有代表性的聚类算法，从算法思想。关键技术和优缺点等方面进行分析概括；另一方面选择一些典型的聚类算法和一些知名的数据集，主要从正确率和运行效率两个方面进行模拟实验，并分别就同一种聚类算法、不同的数据集以及同一个数据集、不同的聚类算法的聚类情况进行对比分析。最后通过综合上述两方面信息给出聚类分析的研究热点、难点、不足和有待解决的一些问题等。 实验中主要选择了K 均值聚类算法、FCM 模糊聚类算法并以UCI Machine Learning Repository 网站下载的IRIS 和WINE 数据集为基础通过MATLAB 实现对上述算法的实验测试。然后以WINE 数据集在学习了解Weka 软件接口方面的基础后作聚类分析，使用最常见的K 均值（即K-means ）聚类算法和FCM 模糊聚类算法。下面简单描述一下K 均值聚类的步骤。 K 均值算法首先随机的指定K 个类中心。然后： （1）将每个实例分配到距它最近的类中心，得到K 个类； （2）计分别计算各类中所有实例的均值，把它们作为各类新的类中心。 重复（1）和（2），直到K 个类中心的位置都固定，类的分配也固定。 在实验过程中通过利用Weka 软件中提供的simpleKmeans （也就是K 均值聚类算法对WINE 数据集进行聚类分析，更深刻的理解k 均值算法，并通过对实验结果进行观察分析，找出实验中所存在的问题。然后再在学习了解Weka 软件接口方面的基础上对Weka 软件进行一定的扩展以加入新的聚类算法来实现基于Weka 平台的聚类分析。 3 实验过程 3.1 K 均值聚类算法 3.1.1 K 均值聚类算法理论 K 均值算法是一种硬划分方法，简单流行但其也存在一些问题诸如其划分结果并不一定完全可信。K 均值算法的划分理论基础是 2 1 min i c k i k A i x v ∈=-∑∑ （1） 其中c 是划分的聚类数，i A 是已经属于第i 类的数据集i v 是相应的点到第i 类的平均距离，即 各种聚类算法的比较 聚类的目标是使同一类对象的相似度尽可能地小；不同类对象之间的相似度尽可能地大。目前聚类的方法很多，根据基本思想的不同，大致可以将聚类算法分为五大类：层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法。摘自数据挖掘中的聚类分析研究综述这篇论文。 1、层次聚类算法 1.1聚合聚类 1.1.1相似度依据距离不同：Single-Link:最近距离、Complete-Link：最远距离、Average-Link：平均距离 1.1.2最具代表性算法 1）CURE算法 特点：固定数目有代表性的点共同代表类 优点：识别形状复杂，大小不一的聚类，过滤孤立点 2）ROCK算法 特点：对CURE算法的改进 优点：同上，并适用于类别属性的数据 3）CHAMELEON算法 特点：利用了动态建模技术 1.2分解聚类 1.3优缺点 优点：适用于任意形状和任意属性的数据集；灵活控制不同层次的聚类粒度，强聚类能力 缺点：大大延长了算法的执行时间，不能回溯处理 2、分割聚类算法 2.1基于密度的聚类 2.1.1特点 将密度足够大的相邻区域连接，能有效处理异常数据，主要用于对空间数据的聚类 1）DBSCAN：不断生长足够高密度的区域 2）DENCLUE：根据数据点在属性空间中的密度进行聚类，密度和网格与处理的结合 3）OPTICS、DBCLASD、CURD：均针对数据在空间中呈现的不同密度分不对DBSCAN作了改进 2.2基于网格的聚类 2.2.1特点 利用属性空间的多维网格数据结构，将空间划分为有限数目的单元以构成网格结构； 1）优点：处理时间与数据对象的数目无关，与数据的输入顺序无关，可以处理任意类型的数据 2）缺点：处理时间与每维空间所划分的单元数相关，一定程度上降低了聚类的质量和准确性 2.2.2典型算法 1）STING：基于网格多分辨率，将空间划分为方形单元，对应不同分辨率2）STING+：改进STING，用于处理动态进化的空间数据 3）ＣＬＩＱＵＥ：结合网格和密度聚类的思想，能处理大规模高维度数据4）WaveCluster：以信号处理思想为基础 2.3基于图论的聚类 2.3.1特点 转换为组合优化问题，并利用图论和相关启发式算法来解决，构造数据集的最小生成数，再逐步删除最长边 1）优点：不需要进行相似度的计算 2.3.2两个主要的应用形式 1）基于超图的划分 2）基于光谱的图划分 2.4基于平方误差的迭代重分配聚类 2.4.1思想 逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获最优解 K-means聚类算法分析应用研究 发表时间：2011-05-09T08:59:20.143Z 来源：《魅力中国》2011年3月上作者：李曼赵松林 [导读] 本文浅谈了数字图像处理的发展概况、研究背景并对彩色图像K-means算法进行分析。 李曼赵松林 （商丘职业技术学院河南商丘，476000） 中图分类号：TP39 文献标识码：A 文章编号：1673-0992（2011）03-0000-01 摘要：本文浅谈了数字图像处理的发展概况、研究背景并对彩色图像K-means算法进行分析.主要详细谈论了是对K-means算法的一些认识，并且介绍K-means聚类的算法思想、工作原理、聚类算法流程、以及对算法结果进行分析，得出其特点及实际使用情况。 关键字：数字图像处理；K-means算法；聚类 一、数字图像处理发展概况及边缘的概念 数字图像处理（Digital Image Processing）即计算机图像处理，就是利用计算机对图像进行去除噪声、增强、复原、分割、特征提取、识别等处理的理论、方法和技术[1]。最早出现于20世纪50年代，它作为一门学科大约形成于20世纪60年代初期。它以改善图像的质量为对象，以改善人的视觉效果为目的。在处理过程中，输入低质量图像，输出质量高图像，图像增强、复原、编码、压缩等都是图像处理常用的方法[1]。数字图像处理在航天、航空、星球探测、通信技术、军事公安、生物工程和医学等领域都有广泛的应用，并取得了巨大的成就。 边缘就是图像中灰度有阶跃变化或屋顶变化的像素的集合，边缘是图像最重要的特征之一，它包含了图像的大部分信息。实质上边缘检测就是采用算法提取图像中对象与背景间的交界线。在目标与背景、目标与目标、区域与区域、基元与基元之间都存在边缘，这是图像分割所依赖的最重要的特征之一。根据灰度变化的剧烈程度，边缘可以分为两种：一种是屋顶边缘，一种为阶跃性边缘。对于屋顶状边缘，二阶导数在边缘初取极值，而对阶跃性边缘，二阶导数在边缘处零交叉；。 二、彩色图像的K-means聚类算法 （一）K-means聚类 聚类就是把数据分成几组，按照定义的测量标准，同组内数据与其他组数据相比具有较强的相似性。K-means聚类就是首先从n个数据对象任选k个对象作为初始聚类中心；剩下的其它对象，则根据它们与这些聚类中心的距离（相似度），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；一直重复此过程直至标准测度函数收敛为止。通常都采用均方差作标准测度函数。k个聚类有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 聚类的用途是很广泛的。在商业上，聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式或者说习惯。它作为数据挖掘中的一个模块，可以作为一个单独的工具以发现数据库中分布的一些深层的信息，并且概括出每一类的特点，或者把注意力放在某一个特定的类上以作进一步的分析；并且，聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。 （二）算法思想分析 输入：聚类个数k，以及包含 n个数据对象的彩色图片。 输出：满足方差最小标准的k个聚类。 处理流程： (1)从 n个数据对象任意选择 k 个对象作为初始聚类中心； (2)根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分； (3)重新计算每个（有变化）聚类的均值（中心对象）； (4)循环(2)到(3)直到每个聚类不再发生变化为止。 首先设置K值，也就是确定若干个聚类中心。使用rand函数随机获得K个颜色值，存放在矩阵miu中，第一次对每个像素点中的K种颜色进行迭代运算，得到最小的颜色矩阵的2范数，同时标记该颜色，依次相加的到各点的颜色矩阵总值。再次迭代得到K中颜色的各个矩阵均值。最后提取出标记的各个颜色，依次对各个点进行颜色赋值，使每个像素点的颜色归类。得到聚类后的图像。 （三）算法的数学描述 （四）算法过程分析 设置K值为8，读入一幅图片后计算图像上所有的像素点个数为N，即令N=size(X,1)*size(X,2)，令颜色矩阵R为矩阵[N,K]并清零。随机获得颜色聚类中心为Miu=fix(255*rand(K,3))。 聚类分析法 先用一个例子引出聚类分析 一、聚类分析法的概念 聚类分析又叫群分析、点群分析或者簇分析，是研究多要素事物分类问题的数量，并根据研究对象特征对研究对象进行分类的多元分析技术，它将样本或变量按照亲疏的程度，把性质相近的归为一类，使得同一类中的个体都具有高度的同质性，不同类之间的个体都具有高度的异质性。 聚类分析的基本原理是根据样本自身的属性，用数学方法按照某种相似性或差异性指标，定量地确定样本之间的亲疏关系，并按这种亲疏关系程度对样本进行聚类。 描述亲属程度通常有两种方法：一种是把样本或变量看出那个p维向量，样本点看成P 维空间的一个点，定义点与点之间的距离；另一种是用样本间的相似系数来描述其亲疏程度。有了距离和相似系数就可定量地对样本进行分组，根据分类函数将差异最小的归为一组，组与组之间再按分类函数进一步归类，直到所有样本归为一类为止。 聚类分析根据分类对象的不同分为Q型和R型两类，Q--型聚类是对样本进行分类处理，R--型聚类是对变量进行分类处理。 聚类分析的基本思想是，对于位置类别的样本或变量，依据相应的定义把它们分为若干类，分类过程是一个逐步减少类别的过程，在每一个聚类层次，必须满足“类内差异小，类间差异大”原则，直至归为一类。评价聚类效果的指标一般是方差，距离小的样品所组成的类方差较小。 常见的聚类分析方法有系统聚类法、动态聚类法（逐步聚类法）、有序样本聚类法、图论聚类法和模糊聚类法等。 二、对聚类分析法的评价 聚类分析也是一种分类技术。与多元分析的其他方法相比，该方法较为粗糙，理论上还不完善，但应用方面取得了很大成功。与回归分析、判别分析一起被称为多元分析的三大方法。 聚类的目的：根据已知数据，计算各观察个体或变量之间亲疏关系的统计量（距离或相关系数）。根据某种准则（最短距离法、最长距离法、中间距离法、重心法），使同一类内的 聚类算法: 1. 划分法：K-MEANS算法、K-M EDOIDS算法、CLARANS算法； 1）K-means 算法： 基本思想是初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值。 K-Means聚类算法主要分为三个步骤： (1)第一步是为待聚类的点寻找聚类中心 (2)第二步是计算每个点到聚类中心的距离，将每个点聚类到离该点最近的聚类中去 (3)第三步是计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心 反复执行(2)、(3)，直到聚类中心不再进行大范围移动或者聚类次数达到要求为止 下图展示了对n个样本点进行K-means聚类的效果，这里k取2： (a)未聚类的初始点集 (b)随机选取两个点作为聚类中心 (c)计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去 (d)计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心 (e)重复(c),计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去 (f)重复(d),计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心 优点： 1.算法快速、简单; 2.对大数据集有较高的效率并且是可伸缩性的; 3.时间复杂度近于线性，而且适合挖掘大规模数据集。 缺点： 1. 在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。 2. 在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响。 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.docsj.com/doc/0115113498.html, Journal of Software, Vol.19, No.7, July 2008, pp.1683?1692 https://www.docsj.com/doc/0115113498.html, DOI: 10.3724/SP.J.1001.2008.01683 Tel/Fax: +86-10-62562563 ? 2008 by Journal of Software. All rights reserved. ? 一种基于K-Means局部最优性的高效聚类算法 雷小锋1,2+, 谢昆青1, 林帆1, 夏征义3 1(北京大学信息科学技术学院智能科学系/视觉与听觉国家重点实验室,北京 100871) 2(中国矿业大学计算机学院,江苏徐州 221116) 3(中国人民解放军总后勤部后勤科学研究所,北京 100071) An Efficient Clustering Algorithm Based on Local Optimality of K-Means LEI Xiao-Feng1,2+, XIE Kun-Qing1, LIN Fan1, XIA Zheng-Yi3 1(Department of Intelligence Science/National Laboratory on Machine Perception, Peking University, Beijing 100871, China) 2(School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, China) 3(Logistics Science and Technology Institute, P.L.A. Chief Logistics Department, Beijing 100071, China) + Corresponding author: E-mail: leiyunhui@https://www.docsj.com/doc/0115113498.html, Lei XF, Xie KQ, Lin F, Xia ZY. An efficient clustering algorithm based on local optimality of K-Means. Journal of Software, 2008,19(7):1683?1692. https://www.docsj.com/doc/0115113498.html,/1000-9825/19/1683.htm Abstract: K-Means is the most popular clustering algorithm with the convergence to one of numerous local minima, which results in much sensitivity to initial representatives. Many researches are made to overcome the sensitivity of K-Means algorithm. However, this paper proposes a novel clustering algorithm called K-MeanSCAN by means of the local optimality and sensitivity of K-Means. The core idea is to build the connectivity between sub-clusters based on the multiple clustering results of K-Means, where these clustering results are distinct because of local optimality and sensitivity of K-Means. Then a weighted connected graph of the sub-clusters is constructed using the connectivity, and the sub-clusters are merged by the graph search algorithm. Theoretic analysis and experimental demonstrations show that K-MeanSCAN outperforms existing algorithms in clustering quality and efficiency. Key words: K-MeanSCAN; density-based; K-Means; clustering; connectivity 摘要: K-Means聚类算法只能保证收敛到局部最优,从而导致聚类结果对初始代表点的选择非常敏感.许多研究 工作都着力于降低这种敏感性.然而,K-Means的局部最优和结果敏感性却构成了K-MeanSCAN聚类算法的基 础.K-MeanSCAN算法对数据集进行多次采样和K-Means预聚类以产生多组不同的聚类结果,来自不同聚类结果的 子簇之间必然会存在交集.算法的核心思想是,利用这些交集构造出关于子簇的加权连通图,并根据连通性合并子 簇.理论和实验证明,K-MeanScan算法可以在很大程度上提高聚类结果的质量和算法的效率. 关键词: K-MeanSCAN;基于密度;K-Means;聚类;连通性 中图法分类号: TP18文献标识码: A ? Supported by the National High-Tech Research and Development Plan of China under Grant No.2006AA12Z217 (国家高技术研究发 展计划(863)); the Foundation of China University of Mining and Technology under Grant No.OD080313 (中国矿业大学科技基金) Received 2006-10-09; Accepted 2007-07-17PAM聚类算法的分析与实现
数据挖掘聚类算法课程设计报告
实验三 K-均值聚类算法实验报告
聚类分析算法解析.doc
聚类算法总结
对数据进行聚类分析实验报告
(完整word版)各种聚类算法介绍及对比
(完整版)聚类算法总结
聚类分析K-means算法综述
k均值聚类报告
聚类算法分析报告汇总
各种聚类算法的比较
K-means聚类算法分析应用研究
聚类分析法总结
聚类算法比较
一种基于K-Means局部最优性的高效聚类算法