OK聚类分析及其应用

《OK聚类分析及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、聚类分析及其应用信息学院蒋盛益Email:jiangshengyi@163.com大纲¢什么是聚类？¢聚类分析的应用¢聚类分析研究的主要内容¢聚类算法的性能评价¢聚类方法的分类¢面临的挑战¢我们的相关工作¢总结一、什么是聚类？¢聚类(Clustering)是将数据集划分为若干相似对象组成的多个组（group）或类(cluster)的过程，使得同一组中对象间的相似度最大化，不同类中对象间的相似度最小化。¢聚类分析中“类”的特征：ß聚类所说的类不是事先给定的，而是根据数据的相似性和距离来划分ß聚类的数目和结构都没有事先假定¢聚类与分类的区别聚类问题是

2、无指导的：没有预先定义的类。分类问题是有指导的：预先定义有类。¢聚类方法的目的是寻找数据中：潜在的自然分组结构和感兴趣的关系。聚类分析示例(1)¢什么是自然分组结构?¢我们看看以下的例子：¢有16张牌¢如何将他们分为一组一组的牌呢？AKQJ聚类分析示例(2)¢分成四组¢每组里花色相同¢组与组之间花色相异AKQJ花色相同的牌为一副聚类分析示例(3)¢分成四组¢符号相同的牌为一组AKQJ符号相同的的牌聚类分析示例(4)¢分成两组¢颜色相同的牌为一组AKQJ颜色相同的配对聚类分析示例(5)¢分成两组¢大小程度相近的牌分到一组AKQJ大配对和小配对聚类分

3、析示例(6)¢这个例子告诉我们，分组的意义在于我们怎么定义并度量“相似性”SimilarA¢因此衍生出一系列度量相似性的算法KQJ大配对和小配对二、聚类的应用领域¢聚类分析广泛应用于模式识别，数据分析、图象处理、市场分析等领域，典型应用包括：ß基因分类和动植物分类ß商务上对客户群体的分类ß科学研究数据的探索ß地理数据的分析,有助于资源分析和城市规划，如确定自动提款机ATM的安放位置ß信息检索与文本挖掘ß入侵检测ß……三、聚类分析研究的主要内容典型的聚类分析任务包括下面五步：(1)模式表示(包括特征提取和/或选择)；(2)适合于数据领域的模式亲近度

4、度量定义；(3)聚类或划分算法；(4)数据摘要；(5)输出结果的评估。四、聚类算法的性能评价¢1.聚类结果质量的评估准则内部质量评价准则是通过计算聚类内部平均相似度、聚类间平均相似度或整体相似度来评价聚类效果，与聚类算法有关。外部质量评价准则是基于一个已经存在的人工分类数据集(已经知道每个对象的类别)进行评价的。外部质量评价准则与聚类算法无关。¢2.数据挖掘对聚类的典型要求(1)可伸缩性(Scalability)(2)处理不同类型属性的能力(3)发现任意形状的聚类(4)用于决定输入参数的领域知识最小化(5)对于输入记录顺序不敏感(6)高维性(7)

5、处理噪音和异常数据的能力(8)基于约束的聚类(9)可解释性五、聚类方法分类¢根据数据的类型、实际问题的特点以及聚类的目的等，提出了许多聚类方法。这些方法可分为：划分方法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法、基于小波变换的方法。1.划分方法¢给定需划分的聚类个数k，首先得到k个初始划分的集合，然后采用迭代重定位技术，通过将对象从一个簇移到另一个簇来改进划分的质量。典型的划分方法包括k-means算法及其变体(k-prototype,k-mode)。¢k-means算法的特点(1)描述容易、实现简单、快速;(2)只能处理数值属性

6、的数据集;(3)不能发现非凸形状的聚类，或具有各种不同大小的聚类;(4)对噪音和异常数据敏感。K-means算法示例1010998877665544332211000123456789100123456789101010998877665544332211000123456789100123456789102.层次聚类方法¢层次聚类方法是通过将数据组织为若干组并形成一个相应的树来进行聚类的。层次聚类方法可分为自顶向下和自下而上层次聚类两种。¢自下而上聚合层次聚类方法。最初将每个对象（自身）作为一个聚类，然后将这些聚类进行聚合以构造越来越大的聚类，

7、直到所有对象均聚合为一个聚类，或满足一定终止条件为止。¢改进的层次聚类方法，如BRICH,BURE,ROCK,Chameleon•自顶向下分解层次聚类方法。首先将所有对象看成一个聚类的内容，然后不断分解使其变成越来越小但个数越来越多的小聚类，直到所有对象均独自构成一个聚类，或满足一定终止条件为止。示例1Step0Step1Step2Step3Step4聚合(AGNES)aabbabcdeccdeddee分解Step4Step3Step2Step1Step0(DIANA)示例2AGNES(AgglomerativeNesting)101010999

8、888777666555444333222111000012345678910012345678910012345678910DIANA