文档介绍：第6章聚类分析
本章目标
辩别类有不同表示法和相似度的不同量度标准。
比较凝聚聚类和分区聚类算法的基本特征。
用相似度的单链接或全链接度量标准实现凝聚算法。
推导分区聚类的K-平均法并分析其复杂性。
解释增量聚类算法的实现和它的优缺点。
聚类分析是依据样本间关联的量度标准将其自动分成几个群组,且使同一群组内的样本相似,而属于不同群组的样本相异的一组方法。聚类分析的一个附加的结果是对每个类的综合描述,这种结果对于更进一步深入分析数据集的特征是尤其重要。
聚类概念
聚类的样本是用度量指标的一个向量表示,或更正式的说法是,用多维空间的一个点来表示。同类中的样本比属于不同类的样本彼此具有更高的相似性。聚类方法尤其适合用来探讨样本间的相互关联关系从而对一个样本结构做一个初步的评价。人们能够对一维、二维或三维的样本进行聚类分析,但是大多数现实问题涉及到更高维的聚类。
例如:下表是一个简单聚类例子,包含了9个顾客的信息,分三类,两个特征值(数量,价格)
类1:购少量高价商品,类2:购大量的高价品,类3:购小量的低价商品。
聚类是一个非常难的问题,因为在一个n维的样本空间数据可以以不同的形状和大小揭示类。
下面基于欧几里得二维空间的聚类过程的一个示例。
上面数据可以分类三个类也可以分为四个类,类的数量的任意性是聚类过程中的主要问题。
另一方面,上面的类是能够直接观察到的。对于高维欧几里得空间里的一组点,就无法从视觉上观察到。
聚类分析输入可以用一组有序数对(X,s)或(X,d)表示。聚类系统的输出是一个分区∧={G1,G2,…,GN},其中Gk(k=1,…,N)是X的子集。
G1,G2,…,GN称为类,每一个类用一些特征描述。聚类结果是类和它的特征或描述。
规范化的描述有以下几种图式:
(边界)点表示n维空间的一类点。
2. 使用聚类树中节点图形化地表示一个类。
。
现有的用于数据挖掘的聚类方法分为四类:分割法,分层法,密度法和网格法。
分割聚类法一般是通过优化一个评价函数把数据分割成K个部分,主要有两种方法:K-means聚类法和K--means法在处理海量数据库方面很有效,特别是对数值属性处理。K-prototypes是结合K-means和K-modiod的优点,可以同时处理数值与符号属性和聚类法
分层聚类法是由不同层次的分割聚类组成,层次之间的分割具有嵌套关系。分层聚类法不必事先输入聚类块数K,基于模糊相似关系的模糊聚类属于这种聚类法。
密度聚类法是利用数据密度函数进行聚类。
网格聚法利用空间量子化方法把数据分到有限个单元进行聚类,这种方法效率高,与数据大小无关,仅与单元数有关。
值得注意的是:没有哪一种聚类技术对揭示多维数据集中的构造种类是普遍适用的。使用者对问题的理解和与其相应的数据类型是选择合适方法的最好标准,大多数聚类算法基于下面两种常见方法:
层次方法按群组的嵌套顺序组织数据,以树状图或树形结构来表示。
平方误差分区算法试图得到一个使类内分散最小而类间分散最大的分区。它是非层次的。