K-均值最小化问题,是要最小化所有的数据点与其所关联的聚类中心点之间的距离之和
K-均值的代价函数(又称畸变函数 Distortion function)为:
J ( c ( 1 ) , . . . , c ( m ) , μ 1 , . . . , μ K ) = 1 m ∑ i = 1 m ∥ X ( i ) − μ c ( i ) ∥ 2 J(c^{(1)},...,c^{(m)},μ_1,...,μ_K)=\dfrac {1}{m}\sum^{m}_{i=1}\left\| X^{\left( i\right) }-\mu_{c^{(i)}}\right\| ^{2} J(c(1),...,c(m),μ1,...,μK)=m1i=1∑m∥ ∥X(i)−μc(i)∥ ∥2
μ c ( i ) {{\mu }_{{{c}^{(i)}}}} μc(i)代表与 x ( i ) {{x}^{(i)}} x(i)最近的聚类中心点
我们的的优化目标便是找出使得代价函数最小的
c
(
1
)
c^{(1)}
c(1),
c
(
2
)
c^{(2)}
c(2),…,
c
(
m
)
c^{(m)}
c(m)和
μ
1
μ^1
μ1,
μ
2
μ^2
μ2,…,
μ
k
μ^k
μk:
在K-均值算法的迭代实现过程中,算法第一个循环用于减小 c(i) 引起的代价,而第二个循环则是用于减小 μi 引起的代价。算法会在每一次迭代都减小代价函数,不然便说明存在错误
选择
K
<
m
K
随机选择 K K K个训练实例,然后令 K K K个聚类中心分别与这 K K K个训练实例相等
K-means的一个问题在于,如果初始化不好,有可能会停留在一个局部最小值处(局部最优解)
解决局部最优问题就是多次随机初始化,找到最好的解(畸变函数最小,即代价最小):通常需要运行多次 K-means算法,每一次都重新随机初始化,最后比较多次运行 K-means的结果,选择代价函数最小的结果
肘部法则——选择聚类数目的一个方法
肘部法则的具体内容:我们所需要做的是改变 K K K值,也就是聚类类别数目的总数。用一个聚类来运行K均值聚类方法。这就意味着,所有的数据都会分到一个聚类里,然后计算成本函数或者计算畸变函数 J J J。 K K K代表聚类数字
肘部法则具体例子:
(1). 闵可夫斯基距离Minkowski/(其中欧式距离: p = 2 p=2 p=2)
d i s t ( X , Y ) = ( ∑ i = 1 n ∣ x i − y i ∣ p ) 1 p dist(X,Y)={{\left( {{\sum\limits_{i=1}^{n}{\left| {{x}_{i}}-{{y}_{i}} \right|}}^{p}} \right)}^{\frac{1}{p}}} dist(X,Y)=(i=1∑n∣xi−yi∣p)p1
(2). 杰卡德相似系数(Jaccard):
J ( A , B ) = ∣ A ∩ B ∣ ∣ A ∪ B ∣ J(A,B)=\frac{\left| A\cap B \right|}{\left|A\cup B \right|} J(A,B)=∣A∪B∣∣A∩B∣
(3). 余弦相似度(cosine similarity):
n n n维向量 x x x和 y y y的夹角记做 θ \theta θ,根据余弦定理,其余弦值为:
c
o
s
(
θ
)
=
x
T
y
∣
x
∣
⋅
∣
y
∣
=
∑
i
=
1
n
x
i
y
i
∑
i
=
1
n
x
i
2
∑
i
=
1
n
y
i
2
cos (\theta )=\frac{{{x}^{T}}y}{\left|x \right|\cdot \left| y \right|}=\frac{\sum\limits_{i=1}^{n}{{{x}_{i}}{{y}_{i}}}}{\sqrt{\sum\limits_{i=1}^{n}{{{x}_{i}}^{2}}}\sqrt{\sum\limits_{i=1}^{n}{{{y}_{i}}^{2}}}}
cos(θ)=∣x∣⋅∣y∣xTy=i=1∑nxi2i=1∑nyi2i=1∑nxiyi
(4). Pearson皮尔逊相关系数:
ρ
X
Y
=
cov
(
X
,
Y
)
σ
X
σ
Y
=
E
[
(
X
−
μ
X
)
(
Y
−
μ
Y
)
]
σ
X
σ
Y
=
∑
i
=
1
n
(
x
−
μ
X
)
(
y
−
μ
Y
)
∑
i
=
1
n
(
x
−
μ
X
)
2
∑
i
=
1
n
(
y
−
μ
Y
)
2
{{\rho }_{XY}}=\frac{\operatorname{cov}(X,Y)}{{{\sigma }_{X}}{{\sigma }_{Y}}}=\frac{E[(X-{{\mu }_{X}})(Y-{{\mu }_{Y}})]}{{{\sigma }_{X}}{{\sigma }_{Y}}}=\frac{\sum\limits_{i=1}^{n}{(x-{{\mu }_{X}})(y-{{\mu }_{Y}})}}{\sqrt{\sum\limits_{i=1}^{n}{{{(x-{{\mu }_{X}})}^{2}}}}\sqrt{\sum\limits_{i=1}^{n}{{{(y-{{\mu }_{Y}})}^{2}}}}}
ρXY=σXσYcov(X,Y)=σXσYE[(X−μX)(Y−μY)]=i=1∑n(x−μX)2i=1∑n(y−μY)2i=1∑n(x−μX)(y−μY)
(1). 均一性: p p p
(2). 完整性: r r r
(3). V-measure: 均一性和完整性的加权平均
V = ( 1 + β 2 ) ∗ p r β 2 ∗ p + r V = \frac{(1+\beta^2)*pr}{\beta^2*p+r} V=β2∗p+r(1+β2)∗pr
(4). 轮廓系数
样本 i i i的轮廓系数: s ( i ) s(i) s(i)
簇内不相似度:计算样本 i i i到同簇其它样本的平均距离为 a ( i ) a(i) a(i),应尽可能小。
簇间不相似度:计算样本 i i i到其它簇 C j C_j Cj的所有样本的平均距离 b i j b_{ij} bij,应尽可能大。
轮廓系数: s ( i ) s(i) s(i)值越接近1表示样本 i i i聚类越合理,越接近-1,表示样本 i i i应该分类到 另外的簇中,近似为0,表示样本 i i i应该在边界上;所有样本的 s ( i ) s(i) s(i)的均值被成为聚类结果的轮廓系数。
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)
(5). ARI
X = { X 1 , X 2 , . . . , X r } , Y = { Y 1 , Y 2 , . . . , Y s } X=\{{{X}_{1}},{{X}_{2}},...,{{X}_{r}}\},Y=\{{{Y}_{1}},{{Y}_{2}},...,{{Y}_{s}}\} X={X1,X2,...,Xr},Y={Y1,Y2,...,Ys}
a = { a 1 , a 2 , . . . , a r } , b = { b 1 , b 2 , . . . , b s } a=\{{{a}_{1}},{{a}_{2}},...,{{a}_{r}}\},b=\{{{b}_{1}},{{b}_{2}},...,{{b}_{s}}\} a={a1,a2,...,ar},b={b1,b2,...,bs}
记: n i j = ∣ X i ∩ Y i ∣ {{n}_{ij}}=\left| {{X}_{i}}\cap {{Y}_{i}} \right| nij=∣Xi∩Yi∣
A R I = ∑ i , j C n i j 2 − [ ( ∑ i C a i 2 ) ⋅ ( ∑ i C b i 2 ) ] / C n 2 1 2 [ ( ∑ i C a i 2 ) + ( ∑ i C b i 2 ) ] − [ ( ∑ i C a i 2 ) ⋅ ( ∑ i C b i 2 ) ] / C n 2 ARI=\frac{\sum\limits_{i,j}{C_{{{n}_{ij}}}^{2}}-\left[ \left( \sum\limits_{i}{C_{{{a}_{i}}}^{2}} \right)\cdot \left( \sum\limits_{i}{C_{{{b}_{i}}}^{2}} \right) \right]/C_{n}^{2}}{\frac{1}{2}\left[ \left( \sum\limits_{i}{C_{{{a}_{i}}}^{2}} \right)+\left( \sum\limits_{i}{C_{{{b}_{i}}}^{2}} \right) \right]-\left[ \left( \sum\limits_{i}{C_{{{a}_{i}}}^{2}} \right)\cdot \left( \sum\limits_{i}{C_{{{b}_{i}}}^{2}} \right) \right]/C_{n}^{2}} ARI=21[(i∑Cai2)+(i∑Cbi2)]−[(i∑Cai2)⋅(i∑Cbi2)]/Cn2i,j∑Cnij2−[(i∑Cai2)⋅(i∑Cbi2)]/Cn2