第10章-聚类方法ppt课件.pptx

《第10章-聚类方法ppt课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章聚类方法10.1聚类概述10.2基于划分的聚类算法10.3基于层次的聚类算法10.4基于密度的聚类算法10.5基于网格的聚类算法10.6基于模型的聚类算法10.7离群点分析分类和聚类是两个容易混淆的概念，事实上它们具有显著区别。在分类中，为了建立分类模型而分析的数据对象的类别是已知的，然而，在聚类时处理的所有数据对象的类别都是未知的。因此，分类是有指导的，是通过例子（训练样本集）学习的过程，而聚类是无指导的，是通过观察学习的过程。10.1聚类概述10.1.1什么是聚类聚类是将数据对象的集合分成相似的对象类的过程。使得同一个簇（或类）中的对象之间具有较高的相似性，而不同簇中的

2、对象具有较高的相异性。定义10.1聚类可形式描述为：D={o1，o2，…，on}表示n个对象的集合，oi表示第i（i=1，2，…，n）个对象，Cx表示第x（x=1，2，…，k）个簇，CxD。用sim(oi，oj)表示对象oi与对象oj之间的相似度。若各簇Cx是刚性聚类结果，则各Cx需满足如下条件：其中，条件①和②表示所有Cx是D的一个划分，条件③表示簇内任何对象的相似度均大于簇间任何对象的相似度。聚类簇1簇2簇3（a）原来的点（b）3个簇10.1.2相似性测度1.距离相似性度量曼哈坦距离欧几里得距离闵可夫斯基距离通常相似度与距离成反比，在确定好距离函数后，可设计相似度函数如下：2

3、.密度相似性度量密度是单位区域内的对象个数。密度相似性度量定义为：density(Ci，Cj)=

4、di－dj

5、其中di、dj表示簇Ci、Cj的密度。其值越小，表示密度越相近，Ci、Cj相似性越高。这样情况下，簇是对象的稠密区域，被低密度的区域环绕。3.连通性相似性度量数据集用图表示，图中结点是对象，而边代表对象之间的联系，这种情况下可以使用连通性相似性，将簇定义为图的连通分支，即图中互相连通但不与组外对象连通的对象组。也就是说，在同一连通分支中的对象之间的相似性度量大于不同连通分支之间对象的相似性度量。某种距离函数4.概念相似性度量若聚类方法是基于对象具有的概念，则需要采用概念相似

6、性度量，共同性质（比如最近邻）越多的对象越相似。簇定义为有某种共同性质的对象的集合。狗鸡猫苹果葡萄语义上的相似性10.1.3聚类过程数据准备属性选择属性提取某种聚类算法结果评估10.1.4聚类算法的评价一个好的聚类算法产生高质量的簇，即高的簇内相似度和低的簇间相似度。通常估聚类结果质量的准则有内部质量评价准则和外部质量评价准则。1.内部质量评价准则例如，CH指标的定义如下：其中：traceB表示簇间距离，traceW表示簇内距离，CH值越大，则聚类效果越好。为整个数据集的均值为簇Ci的均值【例10.1】如图10.2（a）所示的数据集有图10.2（b）、（c）、（d）三种聚类结果，这

7、里n=16，距离函数采用欧几里得距离。采用CH指标判断聚类结果的好坏。CH=5.39CH=6.25625CH=3.962.外部质量评价准则常用的外部质量评价指标有聚类熵等。对于簇Ci，其聚类熵定义为：整体聚类熵定义为所有聚类熵的加权平均值：显然，E越小，聚类效果也越好，反之亦然。E＝0E＝0.58例如(P274)：10.1.5聚类方法的分类按照聚类的尺度，聚类方法可被分为以下三种：基于距离的聚类算法：用各式各样的距离来衡量数据对象之间的相似度。基于密度的聚类算法：相对于基于距离的聚类算法，基于密度的聚类方法主要是依据合适的密度函数等。基于互连性的聚类算法：通常基于图或超图模型。高度

8、连通的对象聚为一类。按照聚类分析方法的主要思路，可以被归纳为如下几种。划分法：基于一定标准构建数据的划分。层次法：对给定数据对象集合进行层次的分解。密度法：基于数据对象的相连密度评价。网格法：将数据空间划分成为有限个单元的网格结构，基于网格结构进行聚类。模型法：给每一个簇假定一个模型，然后去寻找能够很好的满足这个模型的数据集。10.1.6聚类分析在数据挖掘中的应用①聚类分析可以用于数据预处理。②可以作为一个独立的工具来获得数据的分布情况。③聚类分析可以完成孤立点挖掘。10.1.7聚类算法的要求①可伸缩性。②具有处理不同类型属性的能力。③能够发现任意形状的聚类。④需要（由用户）决定的

9、输入参数最少。⑤具有处理噪声数据的能力。⑥对输入记录顺序不敏感。⑦具有处理高维数据的能力。⑧支持基于约束的聚类。⑨聚类结果具有好的可解释性和可用性。10.2基于划分的聚类算法划分聚类算法预先指定聚类数目或聚类中心，通过反复迭代运算，逐步优化目标函数的值，当目标函数收敛时，得到最终聚类结果。划分后每个类中的数据点到该类中心的距离最小10.2.1k-均值算法k-均值（k-means）算法的基本过程如下：首先输入k的值，即希望将数据集D={o1，o2，…，on}经过聚类得到