通俗的解释如下: 现有两位学生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),根据身高体重的信息来判断体型的相似程度。
定义一个聚类准则函数,使其转化为最优化问题,比如距离平方和:
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:样本均值向量
选择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})<d(x,C_{j}) \ j\neq i
x∈Ci,ifd(x,Ci)<d(x,Cj)j=i
更新
z
i
{z_{i} }
zi最小化代价函数,即:
z
i
=
1
N
∑
C
i
x
=
m
i
z_{i}=\frac{1}{N}\sum\limits_{C_{i}}x=m_{i}
zi=N1Ci∑x=mi
根据新聚类中心更新样本类别
直到聚类中心无改变
1.5.3 实例
1.5.4 K均值聚类优点
1.方法简单 方法简单。 2.如果 k 精确且聚类数据可分性好,很容易获得好的聚类效果。
1.5.5 K均值聚类缺点
1.如果k值的选取不正确,那么聚类错误。 2.高度依赖于初始值选取,如下图:
3.更适用“球形”分布的数据,难处理非球形聚类。
1.6 评估指标
聚类的性能评估指标有很多,这里我们着重介绍一种:轮廓系数
轮廓系数的公式如下:
S
(
i
)
=
b
(
i
)
−
a
(
i
)
m
a
x
(
a
(
i
)
,
b
(
i
)
)
S(i)=\frac{b(i)-a(i)}{max({a(i),b(i)})}
S(i)=max(a(i),b(i))b(i)−a(i) 其中,
a
(
i
)
a(i)
a(i)代表样本点的内聚度,公式如下:
a
(
i
)
=
1
N
−
1
∑
j
≠
i
n
d
(
x
i
,
x
j
)
a(i)=\frac{1}{N-1}\sum\limits_{j\neq i}^{n}d(x_{i},x_{j})
a(i)=N−11j=i∑nd(xi,xj) 即为样本i与其所属类内其它样本的距离平均值。
b
(
i
)
b(i)
b(i)为样本i与除其所属类外其它类的样本间距离均值的最小值,即:
b
(
i
)
=
m
i
n
(
b
1
(
i
)
,
b
2
(
i
)
,
⋯
,
b
m
(
i
)
)
b(i)=min(b_{1}(i),b_{2}(i),\cdots,b_{m}(i))
b(i)=min(b1(i),b2(i),⋯,bm(i))
故有:
当
a
(
i
)
<
b
(
i
)
a(i)<b(i)
a(i)<b(i)时,即类内的距离小于类间距离,则聚类结果更紧凑。S的值会趋近于1。越趋近于1代表轮廓越明显。
相反,当
a
(
i
)
>
b
(
i
)
a(i)>b(i)
a(i)>b(i)时,类内的距离大于类间距离,说明聚类的结果很松散。S的值会趋近于-1,越趋近于-1则聚类的效果越差。