聚类算法

Report
小组成员:金玮、沈扬东、吴柏宏、刘承谕、张梦轩、卢勇潮
聚类算法
主要内容
1、定义及主要方法
2、K-Means聚类算法
3、层次聚类算法
4、基于密度的聚类方法
5、聚类评价方法
定义
 聚类是一种无监督的学习,其任务是按照
给定的相似性将数据分组,使得同组数据
彼此相似而不同组数据不相似。
解释
 聚类不等于分类。聚类与分类的不同在于,
聚类所要求划分的类是未知的。
 聚类的要求:高度的组内同质性、高度的
组间异质性
 聚类分析中“类”的特征:
 聚类所说的类不是事先给定的,而是根据数据
的相似性进行划分
 聚类的数目和结构都没有事先假定
主要方法
 1、划分方法(partitioning methods)
 构建K个分组,每一个分组就代表一个聚类
 2、层次方法(hierarchical methods)
 对给定的数据集进行层次式的分解
 3、基于密度的方法(density-based methods)
 不以距离作为划分的标准而是以密度
 4、基于网格的方法(grid-based methods)
 将数据空间划为有限个单元
 5、基于模型的方法(model-based methods)
 给每一个聚类假定一个模型,然后去寻找能够很好
满足这个模型的数据集
主要方法
 1、划分方法(partitioning methods)
 构建K个分组,每一个分组就代表一个聚类
 2、层次方法(hierarchical methods)
 对给定的数据集进行层次式的分解
 3、基于密度的方法(density-based methods)
 不以距离作为划分的标准而是以密度
 4、基于网格的方法(grid-based methods)
 将数据空间划为有限个单元
 5、基于模型的方法(model-based methods)
 给每一个聚类假定一个模型,然后去寻找能够很好
满足这个模型的数据集
K-Means算法
基本思路
具体算法
具体例子
优势及不足
改进方式
基本思路
 采用对象之间的距离作为相似性的指标,
认为距离越小,相似性越大。
 要求对象集合、聚类个数K以及初始的中心
点;
 通过迭代收敛的方式得到合适的聚类
具体算法(1)
 以二维的对象(点集)为例:
1、对于点的集合{(x1,y1),(x2,y2)……(xn,yn)}:
给定要聚成的类的数量K,以及初始聚类中心点
的位置(m1,n1),(m2,n2),……(mk,nk);
2、对应于每一个初始的中心点,给出一个集合,
共给出k个集合。对于每一个点,分析它的坐标
与这k个点的距离。假定某个点与其中的(mi,ni)距
离最小,则将其归到第i个集合中。
3、如此,对于所有的点,都有了自己所属的一
个集合,比如对于第i个集合,可能有如下元素:
{(xp,yp),(xq,yq)……(xr,yr)}
具体算法(2)
 请注意,这时第i个集合中的所有点
(xp,yp),(xq,yq)……(xr,yr),都是在和k个初始中
心点的距离中,和mi的距离最小的点。
4、以每个集合中的点生成新的中心:第i个集
合{(xp,yp),(xq,yq)……(xr,yr)},计算它的质心
(x,y),将其作为新的第i个中心(mi’,ni’)
5、根据新的k个中心,重复第2-4步的过程,
若结果收敛或达到聚类次数的阈值,则算法
结束。
具体例子
以鸢尾花数据集合为例子:
通过观测三种鸢尾花每种50个、共150个样
本来得到的数据集合。令花瓣宽度为横坐标,花
瓣长度为纵坐标,绘制如下图形。每种颜色是一
类鸢尾花。
1
1
2
2
3
3
对于K-Means的评价
 K-Means聚类停止的前提是不再有点被重新
分组,也即质心稳定。
 优点:
 算法非常简单,易于理解及代码设计
 效率很高,时间复杂度为O(NKt),其中N是数据
对象的数目,K是要聚成的类的个数,t是迭代
的次数,数量级为N的一次方。
对于K-Means的评价
 缺点:
人为指定的因素太多。
 1、K需要人工给出,然而事实上K难以估计
 2、初始中心点的坐标对聚类结果影响很大。
 3、受异常值或者极端值的影响很大(过拟合)
正确(排除异常值)
实际(未排除异常值)
对于K-Means算法的改进
 1、K值的确定(略过)
 分离系数
 分离熵
 紧致与分离性效果函数
由于复杂度问题、函数的非线性特征等等自身的
缺陷,聚类效果并不好
对于K-Means算法的改进
 1、K值的确定
 给定一个合适的类簇指标,比如平均半径或直径,只
要我们假设的类簇的数目等于或者高于真实的类簇的
数目时,该指标上升会很缓慢,而一旦试图得到少于
真实数目的类簇时,该指标会急剧上升。
 类簇的直径是指类簇内任意两点之间的最大距离,类簇的半径
是指类簇内所有点到类簇中心距离的最大值。

(参考《大数据-互联网大规模数据挖掘与分布式处理》AnandRajaraman,
JeffreyDavidUllman著,王斌译。)
对于K-Means算法的改进
图是K取值从2到9时的类簇指标的变化曲线,此处选择类簇指标是K个类簇的平均质
心距离的加权平均值。从上图中可以明显看到,当K取值5时,类簇指标的下降趋势
最快,所以K的正确取值应该是5。
对于K-Means算法的改进
 2、选择初始中心点方式的改进
 方法1:选择彼此距离最远的K个点
 首先随机选出一个点,然后选取离这个点距离最
大的点作为第二个点,再选出离这两个点距离最
小值最大的点作为第三个点,以此类推选出K个点。
 方法2:选用层次聚类或者Canopy算法进行初始
聚类,然后利用这些类簇的中心点作为KMeans
算法初始类簇中心点。
对于K-Means算法的改进
 3、消除脏数据和异常数据的影响
脏数据代表一种类边缘的数据,虽然出现在数据集中,但本
身是错误的,不能反映数据及特征,影响聚类效果
 K-MEDOIDS算法
 1,任意选取K个对象作为medoids(O1,O2,…Oi…Ok)。
 2,将余下的对象分到各个类中去(根据与medoid最相近的原
则);
 3,对于每个类(Oi)中,顺序选取一个Or,计算用Or代替Oi后
的消耗—E(Or)。选择E最小的那个Or来代替Oi。这样K个
medoids就改变了,再回到第2步。
 4,这样循环直到K个medoids固定下来。
 不一样的地方在于中心点的选取,在K-means中,我们将中
心点取为当前cluster中所有数据点的平均值,在K-medoids
算法中,我们将从当前cluster中选取这样一个点——它到其
他所有(当前cluster中的)点的距离之和最小——作为中心
点。
对于K-Means算法的改进
 3、消除脏数据和异常数据的影响
 K-MEDOIDS算法
 这种算法对于脏数据和异常数据不敏感,但计算量显
然要比K均值要大,复杂度是O(n2d)(计算各点的两两
距离)及O(kn)(指定类),一般只适合小数据量。
 也与初始点有关
 是局部最优解
 通常随机选择多组初始点,选择拥有最低TSD(总平
方距离)的那一组。
 在K-MEDOIDS算法的基础上,利用实际数据的抽样
代替整个样本——Clara算法,同样也要多次试验。
层次聚类方法
凝聚的层次聚类
SL层次聚类
CL层次聚类
AL层次聚类
简介
 层次聚类方法对给定的数据集进行层次的分解,直到某
种条件满足为止。具体又可分为“凝聚”,“分裂”的两种方
案。
 1、凝聚的层次聚类是一种自底向上的策略,首先将每个
对象作为一个簇,然后合并这些原子簇为越来越大的簇,
直到所有的对象都在一个簇中,或者某个终结条件被满
足,绝大多数层次聚类方法属于这一类,它们只是在簇
间相似度的定义上有所不同。
 2、分裂的层次聚类与凝聚的层次聚类相反,采用自顶向
下的策略,它首先将所有对象置于同一个簇中,然后逐
渐细分为越来越小的簇,直到每个对象自成一簇,或者
达到了某个终止条件。分裂的标志是,两类最近的距离
最远
聚类原理
 给定要聚类的N的对象以及N*N的距离矩阵(或
者是相似性矩阵), 层次式聚类方法的基本步骤
如下:
 1.将每个对象归为一类, 共得到N类, 每类仅包含一个
对象. 类与类之间的距离就是它们所包含的对象之间
的距离.
 2.找到最接近的两个类并合并成一类, 于是总的类数
少了一个.
 3.重新计算新的类与所有旧类之间的距离.
 4.重复第2步和第3步, 直到最后合并成一个类为止
(此类包含了N个对象).
三种不同的定义距离方式
 根据聚类原理步骤3的不同, 可将层次式聚
类方法分为几类:
 single-linkage(SL)
 类间距离等于两类对象之间的最小距离,若用相
似度衡量,则是各类中的任一对象与另一类中任
一对象的最大相似度。
 complete-linkage (CL)
 组间距离等于两组对象之间的最大距离。
 average-linkage (AL)
 组间距离等于两组对象之间的平均距离。
划分
 一旦运行了聚类方法,结果通常被绘制成一个称作“系统图树”的
层次结构。树形图中的树叶对应实例,按照它们合并的次序分组
树可以在任意水平截断,得到期望个数的分组。
基于密度的聚类方法
DBSCAN算法
定义
1、E领域:给定对象半径E内的区域称为E领域
2、核心对象:如果给定对象E领域内的样本点书大于
MinPts,则称点为核心对象
3、直接密度可达:对于样本集合D、如果样本点q在p的E
领域内,且p为核心对象,则成为q到p直接密度可达
4、密度可达:如果对于样本集合D,给定一串样本点p、
p1、p2……pn,pn = q如果对于任意的Pi,都能从Pi-1直接密
度可达,则称p到q密度可达
5、密度相连:对于样本集合中的任意一点O如果存在对象
P到对象O密度可达,对象Q到对象O密度可达,则成P到Q
密度相连
一个例子
假设半径E =3,MinPts = 3
点p的E领域中有点{m,p,p1,p2,o}
点m的E领域中有点{m,q,p,m1,m2}
点q中的E领域有{q,m}
点o的E领域中有{o,p,s}
点s的E领域中有{o,s,s1}
那么核心对象有p,m,o,s
m从p直接密度可达,因为m在p的E领域内且p为核心
q从p密度可达,因q从m直接密度可达,
且m从点p直接密度可达
q到点s密度相连,因为q到p密度可达,s从p密度可达
算法描述
1、输入半径E、最小点数目要求MinPts以及点的集合D
2、重复以下过程:
(1)判断输入点是否为核心对象
(2)找出核心对象E领域中所有直接密度可达的点
3、重复以下过程
(1)针对所有核心对象的E领域所有直接密度可达
点,找到最大的密度相连对象的集合
(2)返回步骤2.
直到所有核心对象的E领域都遍历完毕
没有划分进类的点称为噪声点
评论
复杂度:如果使用了空间索引,复杂度是O(nlgn);
否则,复杂度是O(n^2)
优势:可以划分出形状不规则的类
劣势:算法相对复杂,且有可能将分散的一系列点聚
成不同的集合
注:空间索引:空间索引是指依据空间对象的位置和形状或空间
对象之间的某种空间关系按一定的顺序排列的一种数据结构,其
中包含空间对象的概要信息,如对象的标识、外接矩形及指向空
间对象实体的指针。
聚类评价方法
通用标准
聚类评价标准
外部度量
内部度量
相对度量
通用标准
 可伸缩性
 许多聚类算法在小于200个数据对象的小数据集合上工作得很好,
但是,一个大规模数据库可能包含几百万个对象。在这样的大数
据集样本上进行聚类可能会导致有偏差的结果。
 处理不同类型属性的能力
 许多算法被设计用来对数值类型的数据进行聚类。但是应用可能
要求对其它类型的数据聚类如二元类型分类/标称类型序数型数据
或者这些数据类型的混合。
 发现任意形状的聚类的能力
 许多聚类算法基于欧几里德距离或者曼哈顿距离度量来进行聚类。
基于这样的距离度量的算法趋向于发现具有相近大小和密度的球
状簇(K-Means等)。但是一个簇可能是任意形状的因而提出能发
现任意形状簇的算法也是很重要的。
 对确定输入参数的领域知识的依赖性
 许多聚类算法在聚类分析中要求用户输入一定的参数例如希望产
生的簇的数目而且聚类结果对于输入参数十分敏感。然而参数通
常很难确定由于人对高维数据的认识能力的限制对于高维数据有
关聚类参数更难确定。因此聚类算法应尽量减少需要依赖领域知
识的由数据拥有者主观决定的参数。
通用标准
 处理噪声数据的能力
 绝大多数现实世界中的数据库都包含了孤立点空缺未知数据或者
错误的数据。一些聚类算法对于这样的数据敏感可能会导致低质
量的聚类结果。
 对于数据的输入顺序的敏感性
 一些聚类算法对于输入数据的顺序是敏感的。例如同一数据集以
不同的顺序提交给同一个算法时可能生成差别很大的聚类结果。
 处理高维数据的能力
 一个数据库或者数据仓库可能包含若干维或属性。许多聚类算法
擅长处理低维的数据可能只涉及两到三维。人类最多在三维的情
况下能够很好的判断聚类的质量。在高维空间中聚类数据对象很
难,特别是考虑到这样的数据可能非常稀疏而且高度偏斜。
 可解释性和可用性
 用户希望聚类结果是可解释的可理解的和可用的。也就是说聚类
可能需要和特定的语义解释和应用相联系。
聚类评价指标
 一个良好的聚类,归根结底需要满足两个
要求:
 紧密度:类中的成员尽可能靠近;
 分离度:类间的成员尽可能远离;
 当前的度量方式大致分为三类:
 外部度量 – (**:Rand index)
 内部度量
 相对度量
聚类评价指标-外部度量
 1、外部度量
 (1)类的数目:保证K< ,其中是聚类的数目, 
是样本点数
 (2)与正确的分类相比较的方式:
 纯净度
 根据正确的类的标志,标志为该类的占所有数据的比例
 聚类熵
 评价划分的相对随机程度,在[0,1]之间取值
 整个熵是各个类的均值,1代表完全均匀分布,0代表完全纯净,聚
类划分期望熵最小化。
聚类评价指标-外部度量
 (2)与正确的分类相比较的方式:
 F-Measure,利用了查准率Prec(t,Ck)、查全率
Rec(t,Ck) 其中将数据本身所属的类t看作是集合Nt中等待查
询的项
 由算法产生的Ck是集合Nk中检索到的项
 Ntk是Ck中t的数量,则:
 F(C)即为整个划分的F值,期望其尽可能大
 这个值和检索评价中的F值含义相同,其中的b代表R
的重要性是P的b倍
聚类评价指标-外部度量
 (3)划分之间的比较指标
 计算划分的一致性(Rand Index)
 经过聚类成的结果包括簇1、簇2…簇m(cluster)
 真实的分类包括类1、类2…类n;(class)
对于文档集中 每一个 文档对(Pi,Pj),将这个 文档
对 归入到如下四中不同的类中的一个去:
(共n*(n-1)/2对文档)
之后,计算TP、FN、FP、TN中的类数目,作为它的值。
同簇(cluster)
不同簇
同类(class)
True positives(TP)
False negatives(FN)
不同类
False positives(FP) True negatives(TN)
聚类评价指标-外部度量
(3)划分之间的比较指标
 TP和TN计算两个划分的一致性,FP和FN计算偏
差:
 Rand index
 Rand Index =( TP+TN)/(TP+TN+FP+FN)其中:
 总文档对个数 = TP+TN+FP+FN。R在[0,1]范围取值
 R越大,表示与真实划分差别越小,也即文档多分
在正确的类中,表示聚类结果越好。
 变种:Jacard系数
 Jacard = ( TP)/(TP+TN+FP)
一个例子
簇1
现在假使对于如下文档(17篇):
 聚类成为三个簇(用圆圈表示划分)
 实际上真实分为三类(用形状表示)
则:计算其纯度及Rand Index:
Cluster 1:Max{Classj in Cluster1} = 5
Cluster 2:Max{Classj in Cluster2} = 4
Cluster 3:Max{Classj in Cluster3} = 3
Purity = 5+4+3 / (17) = 0.71
簇2
簇3
一个例子
簇1
现在假使对于如下文档:
 聚类成为三个簇(用圆圈表示划分)
 实际上真实分为三类(用形状表示)
则:计算Rand Index
TP=C52+C42+C32+C22 = 20
FP=(C62+C62+C52)-20 = 20
FN=(C51C11+C11C41+C51C21+C11C21+C11C31)
=24
簇2
簇3
TN=17*(17-1)/2 –TP –FP – TN = 72
TP同簇同类、FP同簇不同类、FN不同簇同类、TN不同簇不同类
∴Rand Index = ( TP+TN)/(TP+TN+FP+FN)≈0.68
聚类评价指标-内部度量
 2、内部度量
 如果数据集结构未知,那么评价结果仅仅能够依赖
数据集自身的特征和量值。
 此时,聚类评价依赖于:
 紧密度
 分离度
 单个类的大小
 (1)类内方差:误差平方和最小:
 K-Means算法就是基于此概念。
 方差最小值取决于数据和类的数目,期望于接近0。
聚类评价指标-内部度量
 (2)层次聚类模式的度量
 适用于层次聚类的算法
 Pc(i,j)是数据xi和xj首次在同一个类中出现的临近层,
P是临近矩阵,度量Pc与P的相似性
 其中,M=N(N-1)/2,μp和μc分别是矩阵P与Pc的均
值;dij,cij分别是P与Pc的元素(i,j)
 取值范围为[-1,1]接近0时说明这两个矩阵有大的
相关性
聚类评价指标-相对度量
 3、相对度量
 在确定聚类算法的基础上,采用预定义的评价标准,针对该算法
不同的参数设置进行算法测试,最终选择最优的参数设置和聚类
模式
 (1)簇内和簇间距离度量的线性组合
 SD-有效性指标
 SD(C) = α * Scat(C) + Dis(C) ;α是加权项,相对重要性

 Dmax/Dmin是C中簇的最大与最小距离的比,δ(C)是数据项与其
分配簇中心的标准偏差, δ(Ck)是簇Ck的标准偏差,Nk是分配到
簇Ck的数据项数目
聚类评价指标-相对度量
 (2)簇类和簇间距离度量的非线性组合
 Dunn及Dunn指标
 度量簇距离与簇直径之间的比例:
 簇Ck的直径簇diam(Cm)为簇内的最大距离
 这个指标对于直径的计算做了更多改进,对噪音数
据更为健壮
聚类评价指标-相对度量
 (3)模糊聚类度量
 SD与Dunn指标作用的是无重叠的聚类模式
 模糊聚类需要定义某个数据项Xi属于一个簇J的程度,利
用隶属矩阵U = [uij]进行模糊划分。指标分为两类,涉及
隶属度矩阵的:
 1、划分系数PC:
 取值范围[1/K,1],PC越接近1,划分月清晰,反之则越模糊
 2、划分熵系数PE:
 取值范围[0,logak],PE取值希望尽可能小,以便获得清晰
的划分,若PE接近logak,则说明算法无法提出聚类
聚类评价指标-相对度量
 (3)模糊聚类度量
 另一类同时涉及隶属度矩阵和数据集
 Xie-Beni指标,为:
 Dmin是簇间最短距离,π是簇i的平均误差:
 Ni是属于簇i的数据量。
 同样地,希望XB的值尽可能小,以得到簇类紧密,簇间分离的聚
类
练习!(1)
 1、利用K-Means算法将如下的八个点聚成三个类:
 A1(2,10)、A2(2,5)、A3(8,4)、A4(5,8)
 A5(7,5)、A6(6,4)、A7(1,2)、A8(4,9)
 距离矩阵如下图:
A1
A2
A3
A4
A5
A6
A7
A8
A1
A2
A3
A4
A5
A6
A7
A8
0
25
72
13
50
52
65
5
0
37
18
25
17
10
20
0
25
2
4
53
41
0
13
17
52
2
0
2
45
25
0
29
29
0
58
0
练习!(1)
 假设如下的如下的八个点中,设置:
A1(2,10)、A2(2,5)、A3(8,4)、A4(5,8)
A5(7,5)、A6(6,4)、A7(1,2)、A8(4,9)
 A1、A4、A7 为初始的聚类点;对于每一次的迭代,计
算如下内容:
1、新的一类包含的点
2、新聚类的中心
3、以10×10的坐标图画出所有点及他们的聚类
4、需要多少次迭代才能稳定?最后的聚类结果?
A1
A2
A3
A4
A5
A6
A7
A8
A1
A2
A3
A4
A5
A6
A7
A8
0
25
72
13
50
52
65
5
0
37
18
25
17
10
20
0
25
2
4
53
41
0
13
17
52
2
0
2
45
25
0
29
29
0
58
0
新的聚类点:
1:{A1} 2:{A3,A4,A5,A6,A8} 3:{A2,A7}
第二次迭代:
1:{A1,A8} 2:{A3,A4,A5,A6} 3:{A2,A7}
C1:(3,9.5); C2:(6.5,5.25); C3:(1.5,3.5)
第三次迭代:
1:{A1,A4,A8} 2:{A3,A5,A6} 3:{A2,A7}
C1(3.66,9); C2:(7,4.33) ; C3:(1.5,3.5)
练习!(2)
 1、利用层次聚类算法将如下的四个点聚类,距离矩阵
如下图:
要求:利用Single-linkage 和 Complete-linkage 算法分别
计算聚类结果。
练习!(2)
 1、Single-Link
练习!(2)
 2、Complete-Link
练习!(2)
 2、Complete-Link
谢谢欣赏!

similar documents