聚类综述

相似性度量
聚类算法即是先定义一个合适的度量， 然后计算任意两个样本之间的距离。当两个 样本之间的欧几里德距离小于某个阈值d0时， 这两个样本就属于同一类。距离阈值d0影响 簇的数量和大小，d0越小，每个簇就越小， 簇的数目就越多。如果d0太大，则所有样本 将会被分为同一簇；如果d0太小，每个样本 又会单成一类。
结论：
1 k Nk
x
xk
k
1 Nk
2 k
T ( x )( x ) k k k k xk
Nk k N
特别注意 k 是个 向量，而 2是个 k 数值。

EM算法
而实际问题是：观察数据x属于哪个高斯分布是未知的，所以要 用EM算法来解决这种实际问题。
EM算法过程：
基于网格的聚类方法
基于网格的方法采用一个多分辨率的网格单元数据结构。它将空间量 化为有限数目的单元（cell）,这些单元形成了网格结构，相对于之前 的几种方法，基于网格的方法不以单个数据点为处理对象，所有的聚 类都在网格单元上进行。
每个层次对应样本 的一个分辨率
基于网格的聚类算法之STING
从某层开始 对于这一层的每个单元 格计算查询相关属性值 根据属性值和约束条件将每 个单元标注成相关or不相关 NO 这层是否为底层？ YES 查询结果是否满 足条件？ YES 停止 NO 恢复数据到相关单元格 进一步处理以得到满足 转下一层 第1 层 第(i-1) 层 第i 层
对数据对象{a,b,c,d,e}的凝聚和分裂层次聚类
基于密度的聚类方法
以数据集在空间分布上的 稠密度为依据进行聚类，无 需预先设定簇的数量，因此 特别适合对于未知内容的数 据集进行聚类。
代表性算法：DBSCAN,OPTICS 举例：DBSCAN算法 DBSCAN目的是找到密度相连对象的最大集合。
基于密度的聚类方法之DBSCAN
图4 MinPts=5
5、密度相连：对象p和q都 是从o关于ε和MinPts密度可 达的，那么对象p和q是关 于ε和MinPts密度相连的
p
q
DBSCAN目的是找到密度相连对象的最大集合。 o
图5 MinPts=5
DBSCAN伪代码
输入： Eps——半径 MinPts——给定点在Eps邻域内成为核心对 象的最小邻域点数。 D——集合。 输出： 目标类簇集合 方法： Repeat: 1） 判断输入点是否为核心对象 2） 找出核心对象的Eps邻域中的 所有直接密度可达点。 Until 所有输入点都判断完毕 Repeat: 针对所有核心对象的Eps邻域内所有直接密 度可达点找到最大密度相连对象集合(中间 涉及到一些密度可达对象的合并)。 Until 所有核心对象的Eps邻域都遍历完毕
合并为一个聚类或满足一定 终止条件
…
每个类只有一个单独的对象 或满足一定终止条件
…
凝聚的层次聚类算法之AGNES
AGNES（Agglomerative NESting）算法 1、算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步 步地合并 2、两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度 来确定 3、聚类的合并过程反复进行直到所有的对象最终满足簇数目
基于模型的聚类方法
1、期望最大化方法（EM）
2、概念聚类
3、神经网络方法
EM算法是基于模型的聚类算法,是极大似然估计的 一种经典算法。主要用于解决数据量不足和似然函 数中含有隐形变量的情形 假设我们想要估计A和B两个参数，在开始状 态下二者都是未知的，并且知道了A的信息就可以 得到B的信息，反过来知道了B也就得到了A。可以 考虑首先赋予A某种初值，以此得到B的估计值， 然后从B的当前值出发，重新估计A的取值，这个 过程一直持续到收敛为止。
几个名词解释：
ε q
1、ε(Eps)邻域：以给定对象为 圆心，半径为ε的邻域为该对象 的ε邻域
2、核心对象：若ε邻域至少包含 MinPts个对象，则称该对象为核心 对象 3、直接密度可达：如果p在q的ε邻 域内，而q是一个核心对象，则说对 象p从对象q出发是直接密度可达的
图1
核心 对象 ε
q
图2 MinPts=5
q
p
图3
基于密度的聚类方法之DBSCAN
几个名词解释： p4 p1=q pn=p p3 p2
4、密度可达：如果存在一个对象链p1 , p2 , … , pn , p1=q, pn=p, 对于pi ∈D(1<= i <=n), pi+1 是从 pi 关于ε和MinPts直接密度 可达的，则对象p是从对象q关于ε和MinPts 密度可达的
最近的簇距离 最近的两个簇 1 1 {1}、{2}
合并后的新簇 {1、2}、{3}、{4}、{5}、{6}、{7}、{8} {1、2}、{3、4}、{5}、{6}、{7}、{8} {1、2}、{3、4}、{5、6}、{7}、{8}
{3}、{4}
{5}、{6}
3
4 5 6
1
1 1 1
{7}、{8} {1、2}、{3、4}
DBSCAN优缺点
1、不需要事 先知道要形成 的簇类的数量 2、可以发现 任意形状的簇 类 3、可以识别 出噪声 4.对数据库中 样本点的顺便 不敏感 1、聚类质量 依赖于距离公 式的选取，实 际应用中常用 的是欧式距离 ，但在高维数 据中效果一般 2、不适合数 据集中密度差 异较大的情况 ，参数选取比 较麻烦
EM算法
1、用随机函数初始化K个高斯分布的参数，同时保证

k 1
K
k
1
Expectation 2、依次取观察数据x，比较x在K个高斯函数中概率的大 小，把x归类到这K个高斯中概率最大的一个。（最大似然估计法的思 想：用使概率达到最大的参数值来估计未知参数）
Maximum 3、 用最大似然估计，使观察数据是x的概率最大，因为已 经在第2步中分好类了，所以，即简单问题的求法。
聚类综述
汇报人：魏苗苗
目录
研究背景
相似性度量方法介绍
聚类方法介绍
参考文献
背景
计算机技术、网络技术和信息技术的迅速发展,人们生产 和搜集数据的能力的大幅度提高,使得数据处理成为可能,同 样也推动了数据库技术的极大发展,但是面对不断增加的数据, 人们不再满足于数据库的查询功能,提出了深层次问题:能不 能从数据中提取信息或者知识为决策服务,就数据库技术而言 己经显得无能为力了。同样,传统的统计技术也面临着极大的 挑战。 这就急需有新的方法来处理这些海量的数据。
AGNES算法例题
序号 属性1 属性2
1 2
3 4 5 6 7 8 步骤 1 2
1 1
2 2 3 3 4 4
1 2
1 2 4 5 4 5
1：根据初始簇计算每个簇之间的距离，随机找出距离 最小的两个簇进行合并，最小距离为1，合并1,2两个 点合并为一个簇。 2：对上一次合并后的簇计算簇间距离，找出距离最近 的两个簇进行合并，合并后3,4两个点成为一个簇 3：重复第2步，5,6点成为一个簇。 4：重复第2步，7,8点成为一个簇。 5：合并{1,2}、{3,4}，使之成为一个包含4个点的簇。 6：合并{5,6}、{7,8}，由于合并后的簇的数目达到用户 输入的终止条件，程序终止。
4、返回第2步用第3步新得到的参数来对观察数据x重新分类。 直到下式概率（最大似然函数）达到最大。
迭代
计算对象x的簇隶属概率， 这些概率是对象x的“期望”
利用前面得到的概率重新 估计（或求精）模型参数
E
M
Text
ATART 初始化参数
似然函数达到最 大化 END
EM优缺点
1、简单且易 实现
1、不好的参 数初始值的设 置，可能陷进 局部最优。 2、收敛速度 慢
STING优缺点
1、粒度大小 难把握，粒度 太小聚类代价 增大，粒度太 大降低聚类质 量 2、所有的聚 类边界要么是 水平的要么是 竖直的，没有 斜的分界线 3、快速处理 以聚类的精确 率为代价
1、计算独立 于查询 2、有利于并 行处理和增量 更新 3、效率高
基于模型的聚类方法
模型是对一个数据集的高层次、全局性的表示。 一个简单的模型，如Y=aX+c,其中Y和X是变量，a和c 是模型中的参数，通过这个模型可以看出，他重点描 绘的并不是某一个数据的部分，而是对整个数据空间 做出了表示。
划分方法：k-means, k-medoids
层次方法: AGNES,DIANA
聚类方法
基于密度的方法: DBSCAN,OPTICS 基于网格的方法:STING
基于模型的方法:EM
其他方法:模糊聚类，约束聚类等
划分法：k-means, k-medoids,大型 数据库划分法
层次法
凝聚的方法 分裂的方法
聚类
所谓聚类就是按照一定的要求和规律,把事 物聚集成若干类或簇(cluster),使类内相似性尽可 能大,类间的相似性尽可能小。 聚类是一个无监督的学习过程,它同分类的 根本区别在于:分类算法是一个有监督的学习过程, 它需要对标注数据集合进行训练;聚类算法则不需 要“教师”的指导，因此被称为无监督的学习或 自动学习。
{5、6}、{7、8}
{1、2}、{3、4}、{5、6}、{7、8} {1、2、3、4}、{5、6}、{7、8}
{1、2、3、4}、{5、6、7、8}
层次法
step0 step1 step2 step3 step4
AGNES abΒιβλιοθήκη c ab abcdecde
d de e DIANA step4 step3 step2 step1 step0
聚类评价方法
聚类评价指标 Purity RI (rand index) F-score
举例说明
x o x x
x
x
x
o o o o
x x
cluster1
cluster2
cluster3
评价方法之purity
评价方法之RI
F-measure
参考文献
EM算法
给定一些观察数据x,假设x符合如下高斯分布：
p ( x) k N ( x k , )
k 1 2 k
K
求混合高斯分布的三组参数：
k
2 k k
EM算法
简单问题：假设该混合高斯分布一共有K个分布，并且对于每个观察 到的x，如果我们同时还知道它属于K中的哪一个分布， 则我们可以根据最大似然估计求出每个参数。
相似性度量
相似函数或距离函数在计算机中一般用一个相异 度或相似度矩阵来表示:
其中、s(i,j)表示对象i和对象 j之间的相似程度。通常s(i,j) 为一个[0,1]之间的数;当对 象i和对象j非常相似或彼此 “接近”时,该数值接近1;该 数值越小,就表示对象i和对 象j越不相似。
nxn
相似性度量
相似性度量
所有聚类技术的根本问题是两个对象间的距离或相 似度度量的选择，选择适当的相似性度量是保证聚类质 量的重要问题。 刻画样本点之间的相似性主要有以下两类函数: 1.相似函数:描述两个样本之间的相似程度,两个样 本越相似,则相似值越接近1;两个样本越不相似,则相似值 越接近0;
2.距离函数:两个样本点越相似,则距离越小,距离 函数值越小;两个样本点越不相似,则距离越远,距离函数 值越大