[工学]C6：聚类.ppt

2003-11-1 高等教育出版社 第6讲：聚类 6.1 什么是聚类 6.2 聚类算法的评估标准 6.3 聚类分析简介 6.4 数据挖掘对聚类算法的要求 6.5 聚类分析中的数据类型 6.6 聚类算法的分类 6.7 本讲小结 6.1 什么是聚类 聚类就是将对物理或抽象对象的集合分组成为由类似的对象组成的多个簇的过程。 聚类生成的组称为簇（Cluster），簇是数据对象的集合。簇内部的任意两个对象之间具有较高的相似度，而属于不同簇的两个对象间具有较高的相异度。 相异度可以根据描述对象的属性值计算，对象间的距离是最常采用的度量指标。 6.2 聚类算法的评估标准 分类精度：聚类的准确程度 log likelihood 6.3 聚类分析简介 聚类分析是数据分析中的一种重要技术，它的应用极为广泛。许多领域中都会涉及聚类分析方法的应用与研究工作，如数据挖掘、统计学、机器学习、模式识别、生物学、空间数据库技术、电子商务等。 聚类分析简介（续） 从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中，如SPSS、SAS等。 聚类分析简介（续） 从机器学习的角度讲，簇相当于隐藏模式。聚类是有哪些信誉好的足球投注网站簇的无监督学习过程。与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。聚类是观察式学习，而不是示例式的学习。 聚类分析简介（续） 从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。 就数据挖掘功能而言，聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合作进一步地分析。 聚类分析还可以作为其他数据挖掘任务（如分类、关联规则）的预处理步骤。 数据挖掘领域主要研究面向大型数据库、数据仓库的高效实用的聚类分析算法。 6.4 数据挖掘对聚类算法的要求 数据挖掘对聚类算法的典型要求包括： 可伸缩性 处理不同类型属性的能力 发现任意形状的聚类 用于决定输入参数的领域知识最小化 处理噪声数据的能力 对输入记录顺序的不敏感性 高维性 基于约束的聚类 聚类结果的可解释性和实用性 6.5 聚类分析中的数据类型 聚类分析主要针对的数据类型包括区间标度变量、二元变量、标称变量、序数型变量、比例标度型变量，以及由这些变量类型构成的复合类型。 一些基于内存的聚类算法通常采用数据矩阵和相异度矩阵两种典型的数据结构。 数据矩阵（Data Matrix） 设有n个对象，可用p个变量（属性）描述每个对象，则n?p矩阵 称为数据矩阵。数据矩阵是对象-变量结构的数据表达方式。 相异度矩阵（Dissimilarity Matrix） 按n个对象两两间的相异度构建n阶矩阵（因为相异度矩阵是对称的，只需写出上三角或下三角即可）： 其中d (i, j)表示对象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,…, xi p)T和xj=(xj1, xj2,…, xj p)T分别表示两个对象，有多种形式的距离度量可以采用。 闵可夫斯基（Minkowski）距离 曼哈坦（Manhattan）距离 欧几里得（Euclidean）距离 切比雪夫（Chebyshev）距离 马哈拉诺比斯（Mahalanobis）距离 6.6 聚类算法的分类 从大体上来看，聚类算法可以划分为如下五种类型： 1) 基于划分的方法 2)基于层次的方法 3)基于密度的方法 4)基于网格的方法 5)基于模型的方法 基于划分的方法 对于一个给定的n个对象或元组的数据库，采用目标函数最小化的策略，通过迭代把数据分成k个划分块，每个划分块为一个簇，这就是划分方法。 划分方法满足两个条件： （1）每个分组至少包含一个对象； （2）每个对象必属于且仅属于某一个分组。 常见的划分方法有k-均值方法和k-中心点方法。其他方法大都是这两种方法的变形。 基于划分的方法（续） k-均值算法 k-均值聚类算法的核心思想是通过迭代把数据对象划分到不同的簇中，以求目标函数最小化，从而使生成的簇尽可能地紧凑和独立。 首先，随机选取k个对