聚类算法讲解精品PPT课件

第七讲 数据聚类

一、 数据聚类的基本概念

1、 数据聚类的定义：

聚类是指在模式空间S中，给定N个样本，按照样本间的相似程度，将S划分为k个决策区域Si（i＝1，2，…..，k）的过程，该过程使得各样本均能归入其中一个类，且不会同时属于两个类。

即 S1∪S2∪S3∪……∪Sk＝S， Si∩Sj＝0，i≠j

聚类Clustering；

聚类分析：Clustering Analysis

讨论：

聚类是对整个样本集的划分，而不是对单个样本的识别；

聚类的依据是“样本间的相似程度”；

聚类结果是“无遗漏”、“无重复”的。

2、 数据聚类的特点：

特点一：聚类是典型的无监督学习

没有预先分好类的样本集

没有已知的分类决策规则

由待分类样本特征的内在规律来驱动分类过程

特点二：聚类结果多样化

受特征选取和聚类准则的影响

受相似度度量标准的影响

受各特征量纲标尺的影响

3、 数据聚类的应用：

（1）数据聚类的应用目标 学习过程

模式采集 预处理 分类器设计

分类决策 特征提取和特征选择 识别过程

有监督学习

无监督学习 线性分类器

贝叶斯分类器

数据拟合

主成分分析

聚 类 区别：样本集是否具有类别标签

学习过程 2 获得初始的训练样本集，启动分类器的设计

揭示样本间的内在联系，获得数据中隐藏的知识和规律

对样本集中的大量样本进行合并和删减，以降低问题的复杂度

（2）数据聚类的具体应用领域

思考题：你能找到数据聚类在社会生活中的更多应用实例吗？

4、 数据聚类的完整过程

（1） 选取特征

聚类任务的需求

特征对聚类的有效性

维度和算法效率

（2）确定相似性度量标准

样本间的相似度

绝对值距离：

nkjkikijXXd1||

欧几里德距离：

nkjkikijXXd12

明考夫斯基距离

nkjkikqijXXqqd1||1)(

第13章 聚类算法II：层次算法

1 3.1 引言

 层次聚类算法与前一章描述的算法有所不同。具体地说，它不产生单聚类，而是产生层次聚类。

 在描述基本思想之前，假设X={,1,...,}iiN=x是将要聚类的l维向

量集。回忆聚类的定义＝{,1,...,}jCjm=其中jCXÍ。

如果1中的每一聚类都是2中集合的子集，则包含k聚类的1嵌套在包含()rk

 层次聚类算法产生一个嵌套聚类的层次。这些算法包含N步，

与数据向量的数量一样多。在第t步，要在前t -1步的聚类基础上生成新聚类。有两种不同的算法：合并和分裂层次算法:

(1)合并算法中，初始聚类0由N个聚类组成，每个聚类仅包含X中的一个元素。第一步生成聚类1，它包含N-1个集合，如0Ì1。重复此过程直到产生最后一个聚类N-1，它只包含一个单个的聚类集合。即数据集X。因而得到聚类的层次为

0Ì1Ì…ÌN-1

(2)分裂算法与合并算法的思路恰好相反。在这种算法中，初始聚类0仅包括一个集合X。第一步产生聚类1。，它由2个集合组成，如1Ì0。重复此过程直到产生最后一个聚类N-1，它包含N个集合，每个集合仅包含X中的一个元素。在这种情况下可得

N-1Ì1Ì…Ì0

下面详细介绍合并算法。分裂算法将在13．4节中简单地介绍。

13.2 合并算法

令(,)ijgCC为所有可能的X聚类对的函数，此函数用于测量iC和jC之间的近邻性，用t表示当前聚类的层次级别。因此，通用合并方法（GAS）为：

－2.2．在t-1的所有可能聚类对(,rSCC)中找一组(,ijCC)，满足

－2.3定义qiCC=jCI，并产生新聚类。

 直到所有向量全被加入到一个聚类中。

很明显，采用此方法可以构造N个聚类的一个层次，每个聚类嵌套在它的后继聚类中，即对于t 1< t 2，t2 =1，…，N -1，有t1 ? t2。另外，如果两个向量一起加入t层次的同一聚类中，我们认为它们的后继聚类相同。这是检验嵌套性质的另一种方法。嵌套性质的缺点是不能从一个“坏”聚类中恢复，“坏”聚类可能产生在更早的层次上.

1 例：有一混合样本集，如下图所示，试用ISODATA进行聚类分析。

解：如下图所示，样本数目8n，取类型数目初始值1c，执行ISODATA算法：

⑴ 给定参数（可以通过迭代过程修正这些参数）：

4,0,4,1,2,2ILKcsn

预选1x为聚合中心，即：TZ)0,0(1。令1J，迭代次数。

⑵ 聚类：因只有一个聚合中心TZ)0,0(1，故},..,,{:82111xxxXw，81n。

⑶ 因nn81，没有子集抛弃。

⑷ 计算新聚合中心：

1811XxxZT)75.2,38.3()858621,8610821(

⑸ 计算类内平均距离：

1||||1111XxZxnD

22222222)82()85()86()811()814()819()822()827([8122222222)818()821()810()813()810()85()82()813(

26.2

⑹ 计算类内总平均距离：26.21DD。

⑺ 不是最后一次迭代，且2kc转⑻ 2 ⑻ 计算聚合1X中的标准偏差1：

T),(12111

jXxjiJZx2111))((81

])8276()8275()8274()8275()8274()8272()8271()8270[(8122222222 =3.98=1.99

56.1])818()810()810()822()82()86()814()822[(812222222212

T)56.1,99.1(1

⑼ 1中的最大偏差分量为99.111，即99.1max1。

⑽ 因为smax1，且2Kc。所以把聚合分裂成两个子集，5.0K，则：Tr)0,1(1，故新的聚合中心分别为：

聚类分析（ClusterAnalysis）

（一）什么是聚类

聚类，将相似的事物聚集在一起，将不相似的事物划分到不同的类别的过程。是将复杂数据简化为少数类别的一种手段。

（二）聚类的基本思想：

• 有大量的样本。

• 假定研究的样本之间存在程度不同的相似性，可以分为几类；相同类别的样本相似度高，不同类别的样本相似度差。

• 用一些数据指标来描述样本的若干属性，构成向量。

• 用某种方法度量样本之间或者类别 之间的相似性（或称距离），依据距离来进行分类。

• 根据分类来研究各类样本的共性，找出规律。

（三）聚类的应用

• 商业领域-识别顾客购买模式，预测下一次购买行为，淘宝商品推荐等。

• 金融领域-股票市场板块分析

• 安全和军事领域

•

o 破解GPS伪随机干扰码和北斗系统民用版的展频编码密码

o 识别论坛马甲和僵尸粉

o 追溯网络谣言的源头

• 生物领域

•

o 进化树构建

o 实验对象的分类

o 大规模组学数据的挖掘

o 临床诊断标准 • 机器学习

•

o 人工智能

（四）聚类的对象

设有m个样本单位，每个样本测的n项指标（变量），原始资料矩阵：

image.png

指标的选择非常重要：

必要性要求：和聚类分析的目的密切相关，并不是越多越好

代表性要求：反映要分类变量的特征

区分度要求：在不同研究对象类别上的值有明显的差异

独立性要求：变量之间不能高度相关（儿童生长身高和体重非常相关）

散布性要求：最好在值域范围内分布不太集中

（五）数据标准化

在各种标准量度值scale差异过大时，或数据不符合正态分布时，可能需要进行数据标准化。

（1） 总和标准化。 分别求出各聚类指标所对应的数据的总和，

以各指标的数据除以该指标的数据的总和。

image.png

这种标准化方法所得到的的新数据满足：

image.png

（2）标准差标准化，即：

image.png

这种标准化方法得到的新数据，各指标的平均值为0，标准差为1，即有：