机器学习面试必知：K均值聚类

假设我们有一个数据集{x1,...,xN}\left\{x_{1},...,x_{N} \right\}{x1​,...,xN​}&＃xff0c;它由D维欧几里得空间中的随机变量$x$的$N$次观测组成。引入一组$D$维向量uk,k&＃61;1,...,Ku_{k},k&＃61;1,...,Kuk​,k&＃61;1,...,K,对于每个数据点xnx_{n}xn​,我们引入一组对应的二值指示向量rnk∈{0,1}r_{nk}\in \left\{0,1 \right\}rnk​∈{0,1},只有当xnx_{n}xn​被分配到uku_{k}uk​中&＃xff0c;rnk&＃61;1r_{nk}&＃61;1rnk​&＃61;1。那么很容易地我们就得到了这样一个目标函数又是也会被称为目标度量J&＃61;∑n&＃61;1N∑k&＃61;1Krnk∣∣xn−uk∣∣2J&＃61;\sum_{n&＃61;1}^{N}\sum_{k&＃61;1}^{K}r_{nk}||x_{n}-u_{k}||^{2}J&＃61;n&＃61;1∑N​k&＃61;1∑K​rnk​∣∣xn​−uk​∣∣2它表示每个数据点与它被分配的向量uku_{k}uk​之间的距离的平方和。我们可以用迭代的方法来最小化这个目标函数。

1. 我们初始化uku_{k}uk​
2. 保持uku_{k}uk​不变&＃xff0c;我们改变rnkr_{nk}rnk​来最小化$J$
3. 保持rnkr_{nk}rnk​不变&＃xff0c;我们改变uku_{k}uk​来最小化$J$
4. 不断重复2,3步骤直到收敛

整体来看&＃xff0c;更新rnkr_{nk}rnk​和更新uku_{k}uk​的两个阶段分别对应于EM算法中的E&＃xff08;期望&＃xff09;步骤和M&＃xff08;最大化&＃xff09;步骤。
先来看第二步&＃xff0c;很好理解&＃xff0c;通俗易懂的来说就是把xnx_{n}xn​分配到离它最近的uku_{k}uk​上。从公式上看也很好理解&＃xff0c;$J$是rnkr_{nk}rnk​的一个线性函数,求其求导得到∣∣xn−uk∣∣2||x_{n}-u_{k}||^{2}∣∣xn​−uk​∣∣2。也就是说我们要对每个xnx_{n}xn​分配到离它最近的uku_{k}uk​上&＃xff0c;这样才能使∣∣xn−uk∣∣2||x_{n}-u_{k}||^{2}∣∣xn​−uk​∣∣2最小。用公式可以这样表示rnk&＃61;{1ifk&＃61;argminj∣∣xn−uj∣∣20otherwiser_{nk}&＃61;\left\{\begin{matrix} 1 \qquad if \quad k&＃61;arg \ min_{j}||x_{n}-u_{j}||^{2}\\0 \qquad otherwise \qquad \qquad\quad\quad\quad\quad \end{matrix}\right.rnk​&＃61;{1ifk&＃61;arg minj​∣∣xn​−uj​∣∣20otherwise​再来看第三步&＃xff0c;对uku_{k}uk​求导&＃61;0即∑n&＃61;1Nrnk(xn−uk)&＃61;0\sum_{n&＃61;1}^{N}r_{nk}(x_{n}-u_{k})&＃61;0n&＃61;1∑N​rnk​(xn​−uk​)&＃61;0uk&＃61;∑nrnkxn∑nrnku_{k}&＃61;\frac{\sum_{n}r_{nk}x_{n}}{\sum_{n}r_{nk}}uk​&＃61;∑n​rnk​∑n​rnk​xn​​这个结果也个简单的含义即令uku_{k}uk​等于类别$k$中所有数据点的均值。

python代码如下

import numpy as np
import matplotlib.pyplot as pltx&＃61;1&＃43;np.random.randn(20,1)
y&＃61;2&＃43;np.random.randn(20,1)
z1&＃61;np.concatenate((x,y),axis&＃61;1)
x&＃61;-3-np.random.randn(20,1)
y&＃61;1&＃43;np.random.randn(20,1)
z2&＃61;np.concatenate((x,y),axis&＃61;1)
x&＃61;-4-np.random.randn(20,1)
y&＃61;-6-np.random.randn(20,1)
z3&＃61;np.concatenate((x,y),axis&＃61;1)
x&＃61;1&＃43;np.random.randn(20,1)
y&＃61;-4-np.random.randn(20,1)
z4&＃61;np.concatenate((x,y),axis&＃61;1)
z&＃61;np.concatenate((z1,z2,z3,z4),axis&＃61;0)
z5&＃61;z.T
plt.scatter(z5[0],z5[1])
plt.show() def distEclud(vecA,vecB):return np.sqrt(np.sum(np.power(vecA-vecB,2)))
def Randcenter(dataset,k):data&＃61;dataset.Tn&＃61;dataset.shape[1]centoids&＃61;np.mat(np.zeros((k,n)))xmax,xmin&＃61;max(data[0]),min(data[0])ymax,ymin&＃61;max(data[1]),min(data[1])dx,dy&＃61;(xmax-xmin)/(k&＃43;1),(ymax-ymin)/(k&＃43;1)for i in range(k):centoids[i,0]&＃61;xmin&＃43;dx*(i&＃43;1)centoids[i,1]&＃61;ymin&＃43;dy*(i&＃43;1)return centoids
def KMeans(dataset,k,distMeans&＃61;distEclud,creatCen&＃61;Randcenter):m&＃61;dataset.shape[0]n&＃61;dataset.shape[1]clusterAssment &＃61; np.mat(np.zeros((m,1)))centoids&＃61;creatCen(dataset,k)flag&＃61;Truecount&＃61;0while flag:count&＃43;&＃61;1print(&＃39;第%d次迭代&＃39;%count)flag&＃61;Falseclusternum&＃61;np.mat(np.zeros((k,1)))newcentoids&＃61;np.mat(np.zeros((k,n)))for i in range(m):minDist&＃61;np.infminIndex&＃61;-1for j in range(k):temp_dist&＃61;distMeans(centoids[j],dataset[i])if temp_dist<minDist:minDist&＃61;temp_distminIndex&＃61;jclusterAssment[i]&＃61;minIndexnewcentoids[minIndex]&＃43;&＃61;dataset[i]clusternum[minIndex]&＃43;&＃61;1print(centoids)for cnt in range(k):newcentoids[cnt]/&＃61;clusternum[cnt]if distMeans(centoids[cnt],newcentoids[cnt])>1e-10:flag&＃61;Truecentoids&＃61;newcentoidsreturn newcentoids,clusterAssmentcenters,asse&＃61;KMeans(z,4)