模式识别：聚类.ppt

《模式识别：聚类.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6讲：聚类6.1什么是聚类6.2聚类算法的评估标准6.3聚类分析简介6.4数据挖掘对聚类算法的要求6.5聚类分析中的数据类型6.6聚类算法的分类6.7本讲小结6.1什么是聚类聚类就是将对物理或抽象对象的集合分组成为由类似的对象组成的多个簇的过程。聚类生成的组称为簇（Cluster），簇是数据对象的集合。簇内部的任意两个对象之间具有较高的相似度，而属于不同簇的两个对象间具有较高的相异度。相异度可以根据描述对象的属性值计算，对象间的距离是最常采用的度量指标。6.2聚类算法的评估标准分类精度：聚类的准确程度loglikelihood6.3聚类分析简介聚类分析是数据分析中的一种重要技术，它的

2、应用极为广泛。许多领域中都会涉及聚类分析方法的应用与研究工作，如数据挖掘、统计学、机器学习、模式识别、生物学、空间数据库技术、电子商务等。聚类分析简介（续）从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中，如SPSS、SAS等。聚类分析简介（续）从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程。与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自

3、动确定标记，而分类学习的实例或数据对象有类别标记。聚类是观察式学习，而不是示例式的学习。聚类分析简介（续）从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。就数据挖掘功能而言，聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合作进一步地分析。聚类分析还可以作为其他数据挖掘任务（如分类、关联规则）的预处理步骤。数据挖掘领域主要研究面向大型数据库、数据仓库的高效实用的聚类分析算法。6.4数据挖掘对聚类算法的要求数据挖掘对聚类算法的典型要求包括：可伸缩性处理不同类型属性的能力发现任意形状的聚类用于决定输入参数的领域知识最小化处理噪声数据的能力对输入记

4、录顺序的不敏感性高维性基于约束的聚类聚类结果的可解释性和实用性6.5聚类分析中的数据类型聚类分析主要针对的数据类型包括区间标度变量、二元变量、标称变量、序数型变量、比例标度型变量，以及由这些变量类型构成的复合类型。一些基于内存的聚类算法通常采用数据矩阵和相异度矩阵两种典型的数据结构。数据矩阵（DataMatrix）设有n个对象，可用p个变量（属性）描述每个对象，则np矩阵称为数据矩阵。数据矩阵是对象-变量结构的数据表达方式。相异度矩阵（DissimilarityMatrix）按n个对象两两间的相异度构建n阶矩阵（因为相异度矩阵是对称的，只需写出上三角或下三角即可）：其中d(i,j)表

5、示对象i与j的相异度，它是一个非负的数值。当对象i和j越相似或“接近”时，d(i,j)值越接近0；而对象i和j越不相同或相距“越远”时，d(i,j)值越大。显然，d(i,j)=d(j,i)，d(i,i)=0。相异度矩阵是对象-对象结构的一种数据表达方式。对象间距离的计算设两个p维向量xi=(xi1,xi2,…,xip)T和xj=(xj1,xj2,…,xjp)T分别表示两个对象，有多种形式的距离度量可以采用。闵可夫斯基（Minkowski）距离曼哈坦（Manhattan）距离欧几里得（Euclidean）距离切比雪夫（Chebyshev）距离马哈拉诺比斯（Mahalanobis）距离6.

6、6聚类算法的分类从大体上来看，聚类算法可以划分为如下五种类型：1)基于划分的方法2)基于层次的方法3)基于密度的方法4)基于网格的方法5)基于模型的方法基于划分的方法对于一个给定的n个对象或元组的数据库，采用目标函数最小化的策略，通过迭代把数据分成k个划分块，每个划分块为一个簇，这就是划分方法。划分方法满足两个条件：（1）每个分组至少包含一个对象；（2）每个对象必属于且仅属于某一个分组。常见的划分方法有k-均值方法和k-中心点方法。其他方法大都是这两种方法的变形。基于划分的方法（续）k-均值算法k-均值聚类算法的核心思想是通过迭代把数据对象划分到不同的簇中，以求目标函数最小化，从而使生

7、成的簇尽可能地紧凑和独立。首先，随机选取k个对象作为初始的k个簇的质心；然后，将其余对象根据其与各个簇质心的距离分配到最近的簇；再求新形成的簇的质心。这个迭代重定位过程不断重复，直到目标函数最小化为止。k-均值算法（续）输入期望得到的簇的数目k，n个对象的数据库。输出使得平方误差准则函数最小化的k个簇。方法选择k个对象作为初始的簇的质心；repeat计算对象与各个簇的质心的距离，将对象划分到距离其最近的簇；重新计算每个新簇的均值；until簇的