8.2 基于划分的聚类（一）在线视频

基于划分的聚类

首先给出基于划分的聚类的

形式化定义

给定 n个数据对象的数据集 D

以及要生成的簇数 k

划分算法把数据对象组织成

k (k≤n) 个分区

其中每个分区代表一个簇

这些簇的形成

旨在优化一个客观划分准则

如基于距离的相异性函数

根据数据集的属性

使得在同一个簇中的对象是“相似的”

而不同簇中的对象是“相异的”

基于划分的聚类

主要介绍

K-均值算法和K-中心点算法

k-均值（k -Means）算法

是一种基于距离的聚类算法

采用距离作为相似性的评价指标

即认为两个对象的距离越近

其相似度就越大

该算法认为簇是由距离靠近的对象组成的

因此将得到紧凑且独立的簇作为最终目标

有多种距离度量方法

最常用的是欧几里得距离

假设数据集D

包含n个欧氏空间中的对象

划分方法把数据集D中的对象

分配到k个簇

Cˇ1, Cˇ2, … , Cˇk中

使得对于

1≤i, j≤ k, Cˇi∈D

且Cˇi∩Cˇj=∅

使用一个目标函数来评估划分的质量

使得簇内对象相互相似

而与其他簇中的对象相异

即该目标函数

以簇内高相似性和簇间低相似性为目标

在k-均值算法中

每个聚簇都用数据集中的一个点来代表

这k个聚簇代表被称为聚簇质心

采用欧几里得距离

最小化的目标是

聚簇中的

每个对象和离它最近的聚簇

代表之间的欧几里得距离

即误差的平方和最小

平方误差准则函数E如公式所示

其中

Cˇi为第i个簇

o为簇Cˇi中的对象

Cˇi为簇Cˇi的质心

是簇Cˇi中所有对象的平均值

如公式所示

Cˇi等于Cˇi的长度分之一

乘以∑o属于CˇiO

式中

Cˇi的长度是簇Cˇi中的对象个数

k值是k-均值算法的一个关键的输入

确定k值的典型做法是依据某些先验知识

例如

集合中实际存在的

或当前应用所预期的聚簇数量

当然也可以通过测试不同的k值

进行探查聚簇的类型信息

从而最终选定合适的k值

k-均值算法的基本过程分为以下几步

①首先输入k的值

即具有n个对象的数据集

D=｛oˇ1,oˇ2,…,oˇn｝

经过聚类将得到k个分类或分组

②从数据集D中

随机选择k个对象作为簇质心

每个簇质心代表一个簇

得到的簇质心集合为

Centroid=｛cˇ1,cˇ2,…,cˇk｝

③对D中每一个对象oˇi

计算oˇi与cˇi的距离

其中i=1,2,…,k

得到一组距离值

选择最小距离值对应的簇质心cˇs

则将对象oˇi

划分到以cˇs为质心的簇中

④根据每个簇所包含的对象集合

重新计算簇中

所有对象的平均值

得到一个新的簇质心

返回步骤③

直到簇质心不再变化

例 使用k-均值算法进行聚类

数据对象集合D如表所示

作为一个聚类分析的二维样本

要求的簇的数量k=2

数据分布如图所示

解

①任意选择oˇ1 (0,2)

oˇ2 (0,0)

为簇Cˇ1和Cˇ2初始的簇质心

即cˇ1=oˇ1=(0,2)

cˇ2=oˇ2=(0,0)

②对剩余的每个对象

根据其与各个簇质心的距离

将它赋给最近的簇

对于oˇ3

d(cˇ1,oˇ3)

等于

根号下

（0-1.5）^2+(2-0)^2

等于2.5

d(cˇ2,oˇ3)

等于根号下

（0-1.5）^2+(0-0)^2

等于1.5

显然 d(cˇ1,oˇ3)>d(cˇ2,oˇ3)

故将oˇ3分配给Cˇ2

对于oˇ4

d(cˇ1,oˇ4)

等于根号下

（0-5）^2+(2-0)^2

等于√29

d(cˇ2,oˇ4)

等于根号下

（0-5）^2+(0-0)^2

等于5

显然

d(cˇ1,oˇ4)>d(cˇ2,oˇ4)

故将oˇ4分配给Cˇ2

对于oˇ5

d(cˇ1,oˇ5)等于

√（0-5）^2+(2-2)^2

等于5

d(cˇ2,oˇ5)等于

√（0-5）^2+(0-2)^2

√29

显然

d(cˇ1,oˇ5)>d(cˇ2,oˇ5)

故将oˇ5分配给Cˇ1

更新得到两个簇

Cˇ1包括{oˇ1,oˇ5}

Cˇ2包括{oˇ2,oˇ3,oˇ4}

计算每个簇的平方误差准则

Eˇ1等于

(0−0)^2+(2−2)^2

+(5−0）^2+(2−2)^2 =25

同理计算Eˇ2

计算结果为27.25

E=Eˇ1+Eˇ2=52.25

形成的两个簇如图所示

其中红色点为簇质心

③计算新簇质心

Cˇ1等于

【0+5/2，2+2/2】

等于（2.5，2）

Cˇ2等于

【0+1.5+5/30+0+0/3】

等于（2.17，0）

④重复②

对每个对象

根据其与各个簇新质心的距离

将它赋给最近的簇

对于oˇ1

d(cˇ1,oˇ1)

计算结果为2.5

d(cˇ2,oˇ1)

计算结果为2.95

显然

oˇ1距cˇ1的距离

小于oˇ1距cˇ2的距离

故将oˇ1分配给Cˇ1

对于oˇ2

d(cˇ1,oˇ2)

结果为3.20

d(cˇ2,oˇ2)

结果为2.17

显然

oˇ2距cˇ1的距离

大于cˇ2距oˇ2的距离

故将oˇ2分配给Cˇ2

对于oˇ3

d(cˇ1,oˇ3)

结果为2.24

d(cˇ2,oˇ2)

结果为0.67

显然

显然oˇ3距cˇ1距离

大于oˇ3距cˇ2的距离

故将oˇ3分配给Cˇ2

对于oˇ4

d(cˇ1,oˇ4)

结果为3.20

d(cˇ2,oˇ4)

结果为2.83

显然

oˇ4距cˇ1的距离

大于oˇ4距cˇ2的距离

故将oˇ4分配给cˇ2

oˇ5

d(cˇ1,oˇ5)

对于oˇ5

d(cˇ1,oˇ5)

计算结果为2.5

d(cˇ2，oˇ5)

计算结果为3.47

显然

oˇ5距cˇ1的距离

小于oˇ5距cˇ2的距离

故将oˇ5分配给cˇ1

更新得到两个新簇

Cˇ1包括oˇ1 oˇ5

Cˇ2包括oˇ2 oˇ3 oˇ4

计算每个簇的平方误差准则

Eˇ1

等于（0-2.5）^2+(2-2)^2

+(5-2.5)^2+(2-2)^2

结果为12.5

同理计算Eˇ2

结果为13.17

E=Eˇ1+Eˇ2

结果为25.67

形成的两个簇如图所示

其中红色点为簇质心

由以上计算可以看出

第二次迭代后

簇中对象没有变化

簇没聚心没有变化

且平方误差准则函数值

由52.25锐减到25.67

所以停止迭代过程

算法停止

k-均值聚类算法的优点主要有

擅长处理球状分布的数据

当结果聚类是密集的

而且类和类之间的区别比较明显时

k-均值聚类算法的效果比较好

对于处理大数据集

是相对可伸缩的和高效的

它的复杂度是O(nkt)

n是对象的个数

k是簇的数目

t是迭代的次数

相比其他的聚类算法

k-均值聚类算法比较简单

容易掌握

k-均值聚类算法的缺点主要有

初始质心的选择

与算法的运行效率密切相关

随机选取质心有可能导致

迭代次数很大

或者限于某个局部最优状态

通常k远远小于n

且t远远小于n

所以算法经常以局部最优收敛

其次

k-均值聚类算法的最大问题是

要求用户必须事先给出k的个数

k的选择一般都基于

一些经验值和多次试验的结果

对于不同的数据集

k的取值没有可借鉴性

另外

k-均值聚类算法

对离群点数据是敏感的

当离群点分配到某个簇中

它可能严重扭曲簇的平均值

少量的这类数据就能对

平均值造成极大的影响