在聚类问题中,给我们的训练样本是 $ \left{x^{(1)}, \ldots, x^{(m)}\right}, \quad x^{(i)} \in \mathbb{R}^{n}
,
K
−
m
e
a
n
s
算法是将样本聚类成
,K-means算法是将样本聚类成
,K−means算法是将样本聚类成k$个簇(cluster),具体算法描述如下:
随机选取
k
k
k个聚类质心点(cluster centroids)为
μ
1
,
μ
2
,
…
,
μ
k
∈
R
n
\mu_{1}, \mu_{2}, \ldots, \mu_{k} \in \mathbb{R}^{n}
μ1,μ2,…,μk∈Rn_
重复下面过程直到收敛:
对于每一个样例i,计算其应该属于的类:
c
(
i
)
:
=
arg
min
j
∥
x
(
i
)
−
μ
j
∥
2
c^{(i)}:=\arg \min _{j}\left\|x^{(i)}-\mu_{j}\right\|^{2}
c(i):=argminjx(i)−μj2
对于每一个类j,重新计算该类的质心:
μ
j
:
=
∑
i
=
1
m
1
{
c
(
i
)
=
j
}
x
(
i
)
∑
i
=
1
m
1
{
c
(
i
)
=
j
}
\mu_{j}:=\frac{\sum_{i=1}^{m} 1\left\{c^{(i)}=j\right\} x^{(i)}}{\sum_{i=1}^{m} 1\left\{c^{(i)}=j\right\}}
μj:=∑i=1m1{c(i)=j}∑i=1m1{c(i)=j}x(i)
K是我们事先给定的聚类数,
c
(
i
)
c^{(i)}
c(i) 距离最近的那个类,
c
(
i
)
c^{(i)}
c(i)的值是1到k中的一个。质心
μ
j
\mu_{j}
μj 代表我们对属于同一个类的样本中心点的猜测,拿星团模型来解释就是要将所有的星星聚成k个星团,首先随机选取k个宇宙中的点(或者k个星星)作为k个星团的质心,然后第一步对于每一个星星计算其到k个质心中每一个的距离,然后选取距离最近的那个星团作为
c
(
i
)
c^{(i)}
c(i),这样经过第一步每一个星星都有了所属的星团;第二步对于每一个星团,重新计算它的质心
μ
j
\mu_{j}
μj(对里面所有的星星坐标求平均)。重复迭代第一步和第二步直到质心不变或者变化很小。
下图展示了对n个样本点进行K-means聚类的效果,这里k取2。
K-means面对的第一个问题是如何保证收敛,前面的算法中强调结束条件就是收敛,可以证明的是K-means完全可以保证收敛性。下面我们定性的描述一下收敛性,我们定义畸变函数(distortion function)如下:
J
(
c
,
μ
)
=
∑
i
=
1
m
∥
x
(
i
)
−
μ
c
(
i
)
∥
2
J(c, \mu)=\sum_{i=1}^{m}\left\|x^{(i)}-\mu_{c^{(i)}}\right\|^{2}
J(c,μ)=i=1∑mx(i)−μc(i)2
J
J
J函数表示每个样本点到其质心的距离平方和。K-means是要将J调整到最小。假设当前J没有达到最小值,那么首先可以固定每个类的质心
μ
j
\mu_{j}
μj,调整每个样例的所属的类别
c
(
i
)
c^{(i)}
c(i) 来让J函数减少。同样,固定
c
(
i
)
c^{(i)}
c(i),调整每个类的质心
μ
j
\mu_{j}
μj也可以使J减小。这两个过程就是内循环中使J单调递减的过程。当J递减到最小时,
μ
\mu
μ和
c
c
c也同时收敛。(在理论上,可以有多组不同的
μ
\mu
μ和
c
c
c值能够使得J取得最小值,但这种现象实际上很少见)。
由于畸变函数J是非凸函数,意味着我们不能保证取得的最小值是全局最小值,也就是说k-means对质心初始位置的选取比较感冒,但一般情况下k-means达到的局部最优已经满足需求。但如果你怕陷入局部最优,那么可以选取不同的初始值跑多遍k-means,然后取其中最小的J对应的
μ
\mu
μ和
c
c
c输出。
Gap
(
K
)
=
E
(
log
D
k
)
−
log
D
k
\operatorname{Gap}(K)=\mathrm{E}\left(\log D_{k}\right)-\log D_{k}
Gap(K)=E(logDk)−logDk
其中
D
k
D_{k}
Dk 为损失函数,这里
E
(
log
D
k
)
E\left(\log D_{k}\right)
E(logDk) 指的是
log
D
k
\log D_{k}
logDk 的期望。这个数值通常通过蒙特卡洛模拟产生,我们在样本里所在的区域中按照均匀分布随机产生和原始样本数一样多的随机样本,并对这个随机样本做 K-Means,从而得到一个
D
k
D_{k}
Dk。如此往复多次,通常 20 次,我们可以得到 20 个
log
D
k
\log D_{k}
logDk。对这 20 个数值求平均值,就得到了
E
(
log
D
k
)
E\left(\log D_{k}\right)
E(logDk) 的近似值。最终可以计算 Gap Statisitc。而 Gap statistic 取得最大值所对应的 K 就是最佳的 K。
对于数据集中的每一个点
x
i
x_i
xi,计算它与已选择的聚类中心中最近聚类中心的距离:
D
(
X
i
)
=
a
r
g
m
i
n
∣
∣
x
i
−
μ
r
∣
∣
2
2
r
=
1
,
2
…
…
k
s
e
l
e
c
t
e
d
D(X_i)=arg\; min||x_i-μ_r||^2_2 \qquad r=1,2……k_selected
D(Xi)=argmin∣∣xi−μr∣∣22r=1,2……kselected
选择一个新的数据点作为新的聚类中心,选择的原则是:
D
(
x
)
D(x)
D(x)较大的点,被选取作为聚类中心的概率较大
坐标点的X, Y 坐标,其实是一种向量,是一种数学抽象。现实世界中很多属性是可以抽象成向量的,比如,我们的年龄,我们的喜好,我们的商品,等等,能抽象成向量的目的就是可以让计算机知道某两个属性间的距离。如:我们认为,18岁的人离24岁的人的距离要比离12岁的距离要近,鞋子这个商品离衣服这个商品的距离要比电脑要近,等等。只要能把现实世界的物体的属性抽象成向量,就可以用K-Means算法来归类了。