聚类（Clustering）-划分法
• 使用这个基本思想的算法有：
K-MEANS算法
Fuzzy C-Means算法
K-MEDOIDS算法
Clara算法
CLARANS算法
Vehicle Example
Vehicle
V1 V2 V3 V4 V5 V6 V7 V8 V9
Top speed
(km/h)
220 230 260 140 155 130 100 105 110
K-means的归属矩阵
K
KN
wji 1,j 1,..., N;
wji N
i 1
i1 j1
（2）
w ji
1,
if X j Ci X j Cm ,
m j
0,
otherwise
（3）
数据点 Xj
1 0 1 0 0 0 1 0 0 W 0 1 0 1 0 1 0 0 0 聚类Ci
0 0 0 0 1 0 0 1 1
• 基于模型的方法给每一个聚类假定一个模 型，然后去寻找能个很好的满足这个模型 的数据集
• 它的一个潜在的假定就是：目标数据集是 由一系列的概率分布所决定的
聚类（Clustering）-划分法
• 给定一个有N个元组或者纪录的数据集，构 造K （ K < N）个分组，每一个分组就代表 一个聚类
（1）每一个分组至少包含一个数据纪录
K-Means聚类法（C-Means）
– 将N个数据依照其数据特征聚类为K类的聚类算法， K为一正整数
– 目标在于求各个数据与其对应聚类中心点距离平方 和的最小值
K
KN
2
J Ji
wji X j Ci
i 1
i1 j1
（1）
– Ji 为第 i 类聚类的目标函数 – K为聚类个数
– Xj为第 j 个输入向量 – Ci为第 i 个聚类中心（向量） – wji 为权重 （Xj 是否属于聚类Ci）
• 这样就能克服基于距离的算法只能发现 “类圆形”的聚类的缺点
聚类（Clustering）-基于网格的方法
• 这种方法首先将数据空间划分成为有限个 单元（Cell）的网格结构,所有的处理都是 以单个的单元为对象的
• 这么处理的一个突出的优点就是处理速度 很快
聚类（Clustering）-基于模型的方法
• （A）for j=1,......,N
– （i）计算各数据点到聚类中心的距离
d (t) ij
X j Ci(t1) ; i 1,...K
–
（ii）计算数据点属于哪一聚类（隶属度矩阵）wji
1, Biblioteka argmin iK1{d
} (t )
ji
0, otherwise
N
w(t) ji
X
j
• （B）更新聚类中心 Cit j1
聚类（Clustering）-层次法
• 这种方法对给定的数据集进行层次似的分解，直 到某种条件满足为止
• 具体又可分为“自 底向上”和“自顶向 下”两种方案。
聚类
数据1 数据2 数据3 数据4 数据5
聚类（Clustering）-基于密度的方法
• 基于密度的方法与其它方法的一个根本区 别是：它不是基于各种各样的距离的，而 是基于密度的
2
1
0
log(intensity) 557 Hz
-1
-2
-3
-4
-5
-6
-7
-8
-8
-6
-4
-2
log(intensity) 475 Hz
1. Compute the new centre of each class 2. Move the crosses (x)
0
2
Iteration 2
log(intensity) 557 Hz
2
1
0
log(intensity) 557 Hz
-1
-2
-3
-4
-5
-6
-7
-8
-8
-6
-4
-2
0
2
log(intensity) 475 Hz
Iteration 10
Tiles data: o = whole tiles, * = cracked tiles, x = centres
22 2 11 1 11 1
Cluster 1: mean=35 Cluster 2: mean=230
蝴蝶型数据集
很明确的属于 Cluster 1
属于Cluster 1 or 2 ? 很明确的属于Cluster 2
蝴蝶型数据集
聚类中心
*
*
蝴蝶型数据集
Fuzzy C-Means聚类法
Dunn 利用 Ruspini 提出的模糊划分的概念, 将硬聚类推广到模糊聚类, 1973年 Jim Bezdek 将 Dunn 的工作推广到基于模糊度 m 的一般 Fuzzy C-Means 形式，其目标函数定义如同K-
K-Means & Fuzzy C-Means
报告人：马宝秋
聚类（Clustering）
• “物以类聚，人以群分”
• 是对于静态数据分析的一门技术，在许多 领域受到广泛应用，包括机器学习，数据 挖掘，模式识别，图像分析以及生物信息
聚类（Clustering）
• 聚类是把相似的对象通过静态分类的方法分 成不同的组别或者更多的子集（Subset）， 这样让在同一个子集中的成员对象都有相似 的一些属性
Colour
red black red gray blue white black red gray
Air resistance 0.30 0.32 0.29 0.35 0.33 0.40 0.50 0.60 0.55
Weight Kg 1300 1400 1500 800 950 600 3000 2500 3500
Tiles data: o = whole tiles, * = cracked tiles, x = centres
2
1
0
-1
-2
-3
-4
-5
-6
-7
-8
-8
-6
-4
-2
0
2
log(intensity) 475 Hz
Iteration 5
Tiles data: o = whole tiles, * = cracked tiles, x = centres
wji 1, j 1, ..., n, wji n
i 1
i1 j1
（3） （2）
K-means实现步骤
3. 由（1）式计算目标函数 J，如果 J 保持不变，代表聚 类结果已经稳定不变，则可结束此迭代方法，否则进 入步骤4
k
kn
2
J Ji
w ji X j Ci
i 1
i 1 j 1
-1
-2
-3
-4
-5
-6
-7
-8
-8
-6
-4
-2
0
2
log(intensity) 475 Hz
1. Place two cluster centres
2. Assign a fuzzy membership to each data point depending on distance
Tiles data: o = whole tiles, * = cracked tiles, x = centres
N ;i 1,...K
w(t) ji
j 1
1. （C）计算收敛准则，若 E(t) J (t) J (t1) 算，否则进行下一轮迭代 E(t)= C(t) C(t1)
成立则停止运
使用K-Means聚类法
• 需事先确定聚类的数目K
• 若初始聚类中心位置不理想，使得目标 函数 J 落入局部解，最后分类出来的群 集将不甚理想
K-means实现步骤
1. 随机选取k个数据点Ci，i=1，…，k，并将之分 别视为各聚类的初始中心
2. 决定各数据点所属之聚类，若数据点Xj判定属 于第 i 聚类，则权重值wji = 1，否则为 0
w ji
1,
if X j Ci X j Cm ,
m j
0,
otherwise
且满足：
k
kn
Object or data point
3500
3000
Lorries
2500 2000 1500 1000
cluster
label
Medium market cars
Sports cars
500 100
150
200
250
Top speed （km/h）
feature
feature space
300
Means聚类法，但其权重矩阵 W 不再是二元矩 阵，而是应用了模糊理论的概念，使得每一输
入向量不再仅归属于某一特定的聚类，而以其 归属程度来表现属于各聚类的程度
/~jbezdek/
Fuzzy C-Means聚类法
目标函数 J 为（5）式
J
K
Ji
E(t) J (t) J (t1)
4. 重新计算权重矩阵W如（8）式，并回到步骤 2 进行运算
wji
1
2
K
X j Ci
m1
s1 X j Cs
（8）
Tiles data: o = whole tiles, * = cracked tiles, x = centres
2
1
0
log(intensity) 557 Hz