子空间聚类算法44页PPT

3
聚类图示
聚类中没有任何指导信息，完全按照数据的分布进行类别划分
4
什么是分类?
• 数据集合D a ta ，类别标记集合 C
x D a ta , C la ss(x ) C
• 数据集合： 训练数据 TrainData 待分类数据 ClassData
• 已知 x T r a i n D a t a ; k o n w C l a s s ( x ) & & C l a s s ( x ) C • 问题： t C la s s D a ta ;C la s s (t) ？ • 方法：根据训练数据获得类别划分标准 f ( x )
14
Rand
• Set any two data in testing corpus as a pair-point; • If testing corpus has n data, there is n*(n-1)/2 pair-points • a) One pair-point is in same cluster in testing corpus, and in
属于不同维度的特征的关系以 Semantic(Aim,Ajn)表示
• Unbalance Similarity
r
U nbalance(A i,A j) w m (A imA jm )2 m 1
不同特征在数据相似度计算中的作用不同
10
聚类有效性函数（一）
• 最小误差（J e ）:
c个 类 别 ， 待 聚 类 数 据 x， m i为 类 别 Ci的 中 心 ，
• Precision and Recall • Purity • Rand Value • Intra-cluster similarity

在整堂课的教学中，刘教师总是让学 生带着 问题来 学习， 而问题 的设置 具有一 定的梯 度，由 浅入深 ，所提 出的问 题也很 明确
Outlines
聚类的思想 常用的聚类方法 实例分析：层次聚类
在整堂课的教学中，刘教师总是让学 生带着 问题来 学习， 而问题 的设置 具有一 定的梯 度，由 浅入深 ，所提 出的问 题也很 明确
3. 实例分析：层次聚类算法
定义：对给定的数据进行层次的分解
第4 步
➢
凝聚的方法（自底向上）『常用』
思想：一开始将每个对象作为单独的
第3 步
一组，然后根据同类相近，异类相异 第2步 的原则，合并对象，直到所有的组合
并成一个，或达到一个终止条件。 第1步
a, b, c, d, e c, d, e d, e
X3 Human（人） X4 Gorilla（大猩猩） X5 Chimpanzee（黑猩猩） X2 Symphalangus（合趾猿） X1 Gibbon（长臂猿）
在整堂课的教学中，刘教师总是让学 生带着 问题来 学习， 而问题 的设置 具有一 定的梯 度，由 浅入深 ，所提 出的问 题也很 明确
离差平方和法（ ward method ）：
各元素到类中心的欧式距离之和。
Gp
Cluster P
Cluster M
Cluster Q
D2 WM Wp Wq
G q
在整堂课的教学中，刘教师总是让学 生带着 问题来 学习， 而问题 的设置 具有一 定的梯 度，由 浅入深 ，所提 出的问 题也很 明确
凝聚的层次聚类法举例
Gp G q
Dpq max{ dij | i Gp , j Gq}
在整堂课的教学中，刘教师总是让学 生带着 问题来 学习， 而问题 的设置 具有一 定的梯 度，由 浅入深 ，所提 出的问 题也很 明确

混合变量相异度计算
p
d(f) ij
d (i, j) 1
p
其中
d
( ij
f
) 为单个类型变量定义的距离；
p为变量的个数。
聚类分析中的数据类型
向量对象的距离算法
0 1 2 2
在某些应用中，如信息
0
4
3
0
检索，文本文档聚类，生 .......... .........
物学分类中，需要对大量
主要聚类方法的分类
划分聚类方法
划分方法将给定的数据集划分成k份，每份为一个簇。 划分方法通常采用迭代重定位技术，尝试通过对象 在簇之间的移动在改进划分。
主要聚类方法的分类
层次聚类方法
层次聚类方法创建给定数据 对象集的层次分解。一般可 以分为凝聚法与分裂法。
凝聚法：也称为自底向上的 方法，开始将每个对象形成 单独的簇，然后逐次合并相 近的对象或簇，直到满足终 止条件。
计算欧几里得距离与曼哈顿距离
聚类分析中的数据类型
二元变量
0 1
属性的取值仅为0或1， 0表示该变量不会出现，
1
1
..........
1表示该变量出现。
..........
设二q元为变对量象相i与异j度都计取算1的变量的 ..个.....数...
0 1
0
0
.........
.........
(6) UNTIL E不再明显地发生变化。
k-means算法
1. 初始化聚类中心 (k=3)；
2. 根据每个样本到各个中 心的距离，计算k个簇。
3. 使用每个簇的样本，对 每个簇生成新的中心。
.......
4

8/21/2024
25
1.2.2 动态聚类分析法
1.2 聚类分析的种类
（3）分类函数
按照修改原则不同，动态聚类方法有按批修改法、逐个修改法、混合法等。 这里主要介绍逐步聚类法中按批修改法。按批修改法分类的原则是，每一步修 改都将使对应的分类函数缩小，趋于合理，并且分类函数最终趋于定值，即计 算过程是收敛的。
8/21/2024
23
1.2.2 动态聚类分析法
1.2 聚类分析的种类
（2）初始分类 有了凝聚点以后接下来就要进行初始分类，同样获得初始分类也有不同的
方法。需要说明的是，初始分类不一定非通过凝聚点确定不可，也可以依据其 他原则分类。
以下是其他几种初始分类方法： ①人为分类，凭经验进行初始分类。 ②选择一批凝聚点后，每个样品按与其距离最近的凝聚点归类。 ③选择一批凝聚点后，每个凝聚点自成一类，将样品依次归入与其距离
8/21/2024
14
1.2 聚类分析的种类
（2）系统聚类分析的一般步骤 ①对数据进行变换处理； ②计算各样品之间的距离，并将距离最近的两个样品合并成一类； ③选择并计算类与类之间的距离，并将距离最ቤተ መጻሕፍቲ ባይዱ的两类合并，如果累的个
数大于1，则继续并类，直至所有样品归为一类为止； ④最后绘制系统聚类谱系图，按不同的分类标准，得出不同的分类结果。
8/21/2024
18
1.2 聚类分析的种类
（7）可变法
1 2 D kr
2 （8）离差平方和法
(D k 2 pD k 2 q)D p 2q
D k 2 rn n ir n n p i D i2 pn n ir n n q iD i2 qn rn in iD p 2 q
8/21/2024

右图是识别子空间聚类的示意图在由年龄和 工资两维构成的原始空间中没有密集区域，但是在 其由工资一维构成的子空间中，存在两个密集区域 ， 形 成 两 个 类 （ 1000≤ 工 资 ≤ 3000 和 5000≤ 工 资 ≤6000）而在由年龄一维构成的子空间中没有密集 区域，不形成任何聚类。
为了规范事业单位聘用关系，建立和 完善适 应社会 主义市 场经济 体制的 事业单 位工作 人员聘 用制度 ，保障 用人单 位和职 工的合 法权益
❖ 子空间聚类算法是指把数据的原始特征空间分割为不同的特征子集，从不同的子空间角度 考察各个数据簇聚类划分的意义，同时在聚类过程中为每个数据簇寻找到相应的特征子空 间。
为了规范事业单位聘用关系，建立和 完善适 应社会 主义市 场经济 体制的 事业单 位工作 人员聘 用制度 ，保障 用人单 位和职 工的合 法权益
为了规范事业单位聘用关系，建立和 完善适 应社会 主义市 场经济 体制的 事业单 位工作 人员聘 用制度 ，保障 用人单 位和职 工的合 法权益
自顶向下子空间聚类算法
❖ 自顶向下子空间聚类算法主要是基于数据投影技术，运用迭代搜索策略进行的子空间聚类 方法。具体而言，首先将整个样本集划分为 C 个数据簇，对于每个数据簇赋予相同的权值 ，并为每一类的各个特征赋予不同权重。然后利用迭代策略对这些初始划分不断进行改进 和更新，产生新的权重和聚类划分。由于在大规模数据集中，多次迭代所需的计算复杂度 相当高，因此，这类算法通常利用采样技术提高其算法的性能。
为了规范事业单位聘用关系，建立和 完善适 应社会 主义市 场经济 体制的 事业单 位工作 人员聘 用制度 ，保障 用人单 位和职 工的合 法权益
熵加权软子空间聚类算法
❖ 同样，Jing 等人将信息熵引入软子空间聚类方法中，利用熵表示第 k 个数据特 征对于第 i 个数据簇的不确定程度，提出了熵加权软子空间聚类算法（Entropy WeightingSubspace Clustering，EWSC）。定义一般化的 EWSC 目标函数：

根据某种模型进行聚类，如高斯混合 模型、神经网络聚类等。
基于网格的聚类算法
将数据空间划分为网格，然后在网格 上进行聚类，如STING算法、 CLIQUE算法等。
02
K-means聚类算法
K-means算法的原理
K-means算法是一种基于距离的聚 类算法，通过迭代过程将数据点划分 为K个聚类，使得每个数据点与其所 在聚类的中心点之间的距离之和最小 。
DBSCAN算法的步骤
01 扫描所有点，标记为核心点、边界点和噪 声点。
02 对于每个核心点，以其为起点，扩展与其 密度相连的区域。
03
将扩展的区域内的所有点标记为同一簇。
04
重复上述步骤，直到所有点都被处理。
DBSCAN算法的优缺点
01
优点
02
对异常值具有较强的鲁棒性。
能够发现任何形状的簇。
03
互信息
总结词
衡量聚类结果与真实类别之间相似度的指标，值越大表示聚 类效果越好。
详细描述
互信息是一种衡量聚类结果与真实类别之间相似度的指标， 其计算方法为聚类结果与真实类别之间的熵值之差。如果聚 类效果好，则聚类结果与真实类别之间的相似度会较高，熵 值之差会较小，因此互信息值会较大。
调整兰德指数
总结词
步骤2
重复以下步骤，直到满足终止条件
• 步骤2.1
将每个数据点与最近的簇中心点合并，形成新的 簇中心点。
• 步骤2.2
更新簇中心点为新合并的簇中所有点的平均值或中 心点。
• 步骤2.3
重复步骤2.1和步骤2.2，直到所有数据点都归入某 个簇或达到预设的簇数量。
输出聚类结果。
步骤3
层次聚类算法的优缺点
DBSCAN算法的优缺点

大数据下kmeans算法的并 行策略
单挑OR群殴？！
VS
大数据下kmeans算法的并 行策略
面对海量数据时，传统的聚类算法存在着单位时 间内处理量小、面对大量的数据时处理时间较长、 难以达到预期效果的缺陷以上算法都是假设数据都 是在内存中存储的，随着数据集的增大，基于内存 的ＫＭｅａｎｓ就难以适应．ＭａｐＲｅｄｕｃｅ 是一个为并行处理大量数据而设计的编程模型。
Love ,not time,heals all wounds. 治愈一切创伤的并非时间,而是爱.
Life is tough,but I'm tougher. 生活是艰苦的,但我应更坚强.
Kmeans算法详解（1）
步骤一：取得k个初始初始中心点
Kmeans算法详解（3）
步骤三：重新计算中心点
Min of three due to the EuclidDistance
带canopy预处理的kmeans 算法的优点
canopy可以自动帮我我们确定k值。
• 有多少canopy，k值就选取多少。 Canopy可以帮我们去除“坏点”。
• 去除离群的canopy
带canopy预处理的kmeans 算法的新挑战
Canopy预处理这么好， 我们以后就用它好了！
我看不见得，它虽然解决 kmeans当中的一些问题， 但其自身也引进了新的问题： t1、t2的选取。
主要内容：
聚类算法简介 Kmeans算法详解 Kmeans算法的缺陷及若干改进 Kmeans的单机实现与分布式实现策略
Kmeans实战
聚类算法简介
1
聚类的目标：将一组向量分成若干组，组内数据是相似的， 而组间数据是有较明显差异。
2 与分类区别：分类与聚类最大的区别在于分类的目标事先已 知，聚类也被称为无监督机器学习

14
❖ 1. 绝对距离（Block距离）
p
dij 1 xik xjk k1
❖ 2. 欧氏距离(Euclidean distance)
1
dij 2 p (xikxjk)2 2
k1
精选ppt
15
❖ 3. 明考斯基距离(Minkowski)
❖ 4. 兰氏距离
1
dij
p
(xik xjk)q
k1
n
n
(xki xi )2 (xkj xj )2
k1
k1
❖ 2. 夹角余弦
n
xkixkj
Cij
k 1
1
n xk2i n xk2j 2
k 1 k 1
精选ppt
18
计数变量(Count)（离散变量）的聚类统计量
❖ 对于计数变量或离散变量，可用于度量样本 （或变量）之间的相似性或不相似性程度的 统计量主要有卡方测度（Chi-square measure） 和Phi方测度（Phi-square measure）。
应聘者 1 2 3 4 5 6 7 8 9 10 X 28 18 11 21 26 20 16 14 24 22 Y 29 23 22 23 29 23 22 23 29 27 Z 28 18 16 22 26 22 22 24 24 24
精选ppt
8
精选ppt
9
精选ppt
10
聚类分析根据一批样本的许多观测 指标，按照一定的数学公式具体地计算 一些样本或一些指标的相似程度，把相 似的样本或指标归为一类，把不相似的 归为一类。
精选ppt
19
二值(Binary)变量的聚类统计量
精选ppt
20

4.pearson correlation
皮尔逊相关系数(R)
5.chebychev
切比雪夫距离
dx,yMxa iyix i
毛本清 2019.08.27
6.block 绝对值距离
dx,y i xiyi
7.minkowski 明考斯基
1
d
x,
yi xiyi
q
毛本清 2019.08.27
毛本清 2019.08.27
Plot
树状结构图 冰柱图
冰柱的方向
毛本清 2019.08.27
Vertical Icicle
Number
Case
of
clust X X X X X X X X
ers
75 4 3 6 8 2 1
1
XXXXXXXXXXXXXXX
2
XXXXXXXXXXXXX X
见（一）聚类方法 见（ 二）各种距离和相似系数
毛本清 2019.08.27
Method
亲疏关系指标 标准化变换
聚类方法
毛本清 2019.08.27
（一）聚类方法
1.Between-groups linkage 类间平均法
两类距离为两类元素两两之间平均平方距离
2.Within-groups linkage 类内平均法
Agglomeration Schedule
Cluster Combined
Cluster 1 Cluster 2
3
8
14
15
9
16
3
5
6
12
7
13
9
11
4
10
3
7
4
14