机器学习 |
您所在的位置:网站首页 › 聚类算法有哪些相似度度量准则 › 机器学习 |
目录
理论部分1.1 聚类概念1.1.1 定义1.1.2 与分类的区别
1.2 相似度测量1.2.1 欧式距离1.2.2 马氏距离
1.3 聚类准则1.3.1 试探方法1.3.2 聚类准则法
1.4 常见聚类方法1.5 K均值聚类1.5.1 K均值聚类思想1.5.2 K均值聚类流程1.5.3 实例1.5.4 K均值聚类优点1.5.5 K均值聚类缺点
1.6 评估指标1.7 K的选取与肘部法则
代码部分2.1 K均值代码实现2.2 评估指标代码实现2.3 整体实现
理论部分
1.1 聚类概念
1.1.1 定义
定义: 对一批没有标出类别的模式样本集,按照样本之间的相似程度分类,相似的归为一类,不相似的归为另一类,这种分类称为聚类,也称为无监督分类。 一个通俗的例子如下: 注意聚类并不等于分类,分类问题中样本标签事前已知,而聚类问题中样本标签事前并不清楚。分类问题属于监督学习,聚类问题属于无监督学习。
前面我们提到了聚类是根据样本间的相似性测度进行划分的,那么这里的相似性一般是以样本点间的距离来衡量的。具体来说:把整个模式样本集的特征向量看成是分布在特征空间中的一些点,点与点之间的距离即可作为模式相似性的测量依据。 通俗的解释如下: 现有两位学生A和B,希望根据他们的身高和体重进行相似度聚类。假设A的身高和体重分别为1.7m,70kg。B的身高和体重分别为1.8m,80kg。那么A和B这两个样本就称为模式, A = [ 1.7 , 70 ] T A=[1.7,70]^{T} A=[1.7,70]T与 B = [ 1.8 , 80 ] T B=[1.8,80]^{T} B=[1.8,80]T分别称为样本A与样本B的特征向量,特征向量所处的二维空间就称为特征空间。衡量样本间的相似性就是通过衡量样本对应特征向量间的距离来决定的。 下面介绍几种常见的距离 1.2.1 欧式距离定义:欧式距离又称欧几里得距离,是最常用的距离测度。假设两个样本
x
,
y
x,y
x,y的特征向量分别为
x
=
[
x
1
,
x
2
,
⋯
,
x
n
]
T
x=[x_{1},x_{2},\cdots,x_{n}]^{T}
x=[x1,x2,⋯,xn]T,
y
=
[
y
1
,
y
2
,
⋯
,
y
n
]
T
y=[y_{1},y_{2},\cdots,y_{n}]^{T}
y=[y1,y2,⋯,yn]T。则它们的欧式距离定义如下: 马氏距离计算公式如下: d = ( x − y ) T Σ − 1 ( x − y ) d=\sqrt{(x-y)^{T}\Sigma^{-1}(x-y)} d=(x−y)TΣ−1(x−y) • 马氏距离将协方差考虑进来,排除了样本之间的相关性。 • 马氏距离与欧氏距离相比,就中间多了一项。当协方差为单位矩阵时,马氏距离和欧氏距离相同。 • 欧式距离中,完全是各样本中对应分量相乘,再相加得到,如果某一项的值非常大,那么其值就会掩盖值小的一项所起到的作用,这是欧式距离的不足,当采用马氏距离,就可以屏蔽这一点。因为相关性强的一个分量,对应于协方差矩阵C中对角线上的那一项的值就会大一些。再将这一项取倒数,减小该影响。 • 马氏距离与原始数据的测量单位无关。 一个通俗的例子如下: 如果我们以厘米为单位来测量人的身高,以克(g)为单位测量人的体重。每个人被表示为一个两维向量,如一个人身高 173 c m 173cm 173cm,体重 50000 g 50000g 50000g,表示为 ( 173 , 50000 ) (173,50000) (173,50000),根据身高体重的信息来判断体型的相似程度。 我们已知小明 ( 160 , 60000 ) (160,60000) (160,60000);小王 ( 160 , 59000 ) (160,59000) (160,59000);小李 ( 170 , 60000 ) (170,60000) (170,60000)。根据常识可以知道小明和小王体型相似。但是如果根据欧几里得距离来判断,小明和小王的距离要远远大于小明和小李之间的距离,即小明和小李体型相似。这是因为不同特征的度量标准之间存在差异而导致判断出错。 以克(g)为单位测量人的体重,数据分布比较分散,即方差大,而以厘米为单位来测量人的身高,数据分布就相对集中,方差小。马氏距离的目的就是把方差归一化,使得特征之间的关系更加符合实际情况。 下图(a)展示了三个数据集的初始分布,看起来竖直方向上的那两个集合比较接近。在我们根据数据的协方差归一化空间之后,如图(b),实际上水平方向上的两个集合比较接近。 聚类准则的选取通常有以下两种: 1.3.1 试探方法依据经验选择测度和阈值来判别分类,并可以选择一定的训练样本来检验测度和阈值的可靠程度。凭直观感觉,针对实际问题定义一种相似性测度的阈值,然后按最近邻规则指定某些模式样本属于某一个聚类类别。 例如对欧氏距离,它反映了样本间的近邻性,但将一个样本分到不同类别中的哪一个时,还必须规定一个距离测度的阈值作为聚类的判别准则. 1.3.2 聚类准则法定义一个聚类准则函数,使其转化为最优化问题,比如距离平方和: J = ∑ i = 1 c ∑ x ∈ S i ∣ ∣ x − m i ∣ ∣ 2 J=\sum\limits_{i=1}^{c}\sum\limits_{x\in S_{i}}||x-m_{i}||^{2} J=i=1∑cx∈Si∑∣∣x−mi∣∣2 x {x} x:模式样本集 S i : i = 1 , 2 , 3 , ⋯ , c {S_{i}:i=1,2,3,\cdots,c} Si:i=1,2,3,⋯,c: 模式类别 m i : m_{i}: mi:样本均值向量 定义如此的聚类函数,将聚类问题转换为求确定函数的最优化问题。 1.4 常见聚类方法常见的聚类方法有分层聚类法,K-means聚类法,基于密度峰值的聚类方法,均值漂移聚类,凝聚层次聚类等。本篇主要介绍K-means聚类。 1.5 K均值聚类 1.5.1 K均值聚类思想• 基本思想 1.首先选择若干个样本点作为聚类中心,再按某种聚 类准则(通常采用最小距离准则)使样本点向各中 心聚集,从而得到初始聚类; 2.然后判断初始分类是否合理,若不合理,则修改分 类; 3.如此反复进行修改聚类的迭代算法,直至合理为止。 所用的聚类准则函数是聚类集中每一个样本点到该类中心的距离平方之和,并使其最小化。 1.5.2 K均值聚类流程 选择k个聚类中心 z 1 , … , z k {z _{1} ,…, z_{k}} z1,…,zk把样本点分配给最近聚类,即: x ∈ C i , i f d ( x , C i ) < d ( x , C j ) j ≠ i x\in C_{i},if \ \ d(x,C_{i}) |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |