共计 3207 个字符，预计需要花费 9 分钟才能阅读完成。
K-means 算法是最罕用的聚类算法之一，本文将对该算法进行解析和 numpy 复现代码。
K-means 解析
定义
K-means 基于的一个假如是同类样本点会在特色空间造成簇。在 K -means 算法中，会给定样本集 X 的 n 个数据点，簇的个数 k。每个簇都有一个类别核心 c。K-means 的优化指标如下式，
式子的意思是让所有数据点离它们所属的类别核心（最近的核心）的欧式间隔之和最小。
求解步骤
求解这个方程个别用上面步骤求解：
- 随机选取 k 个类别核心 C = {c1, c2,···, ck}。
- 把每个数据点归到其最近的类别核心的簇，即给每个点打上假标签。失去 k 个簇集。
- 通过步骤 2 失去的 k 个簇集，从新计算类别核心，计算形式为，
- 反复步骤 2 和步骤 3 直到类别核心不再更新为止。
能够看出 K -means 的求解非常简略，其关键在于类别核心的初始化。最简略的初始化是随机选取 k 个点当作类别核心，但可能会遇到下图状况。下图四个簇对应四个类，当初始点（星）如下图所示时，类别核心无奈收敛到正确的地位上。
k-means++ 算法 [1] 就是为解决这个问题所提出的。
K-means++ 选取初始类别核心步骤为：
- 随机选取第一个类别核心。
- 计算所有样本点与其最近的类别核心的间隔 D(x)，以下式概率
从样本集 X 中选取下一个类别核心。 - 反复步骤 2，直到选取到 k 个类别核心。
关键点在步骤 2，其实质是当一个点属于已选取的类别核心的簇的概率越大，它被选取的概率越小。其目标是使得算法尽可能不在同一簇里不选取两个类别核心。不过算法以概率的模式选取，也无奈保障不呈现上图的状况。因而，个别 K -means 算法会运行屡次，选取指标函数最小的类别核心。
算法代码
初始化形心
应用的是 K -means++ 的形式：
def ini_centers(self,x):
cs = np.array([x[np.random.randint(0, len(x), size = 1).item()]])
for j in range(self.class_num - 1):
for i, c in enumerate(cs):
d = np.sqrt(np.sum((x - c) ** 2, 1).reshape(-1, 1))
if i == 0:
dist = d
else:
dist = np.concatenate((dist, d), 1)
# n, class_num
dist = dist.min(1)
dist = dist**2/sum(dist**2)
index = np.random.choice(np.arange(len(x)), p=dist.ravel())
new_c = x[index]
cs = np.concatenate((cs,[new_c]), 0)
return cs打标签和从新计算类别核心
cnt = 0
flag = True
while flag and cnt < self.max_iter:
# predict
label, score = self.predict(x,cs)
# update
new_cs = np.array([x[label==i].mean(0) for i in range(self.class_num)])
if (cs == new_cs).all(): flag = False
cs = new_cs
cnt+=1预测函数
def predict(self,x,cs):
for i,c in enumerate(cs):
d = np.sqrt(np.sum((x - c)**2,1).reshape(-1,1))
if i == 0:
dist = d
else:
dist = np.concatenate((dist,d),1)
label = dist.argmin(1)
score = dist.min(1).sum()
return label, score屡次计算
def fit(self,x):
sc = float("inf")
for t in range(self.n_init):
cs = self.ini_centers(x)
# initial
cnt = 0
flag = True
while flag and cnt < self.max_iter:
# predict
label, score = self.predict(x,cs)
# update
new_cs = np.array([x[label==i].mean(0) for i in range(self.class_num)])
if (cs == new_cs).all(): flag = False
cs = new_cs
cnt+=1
if score < sc:
sc = score
self.cluster_centers_ = cs
return self.cluster_centers_总体函数
class my_Kmeans():
def __init__(self, class_num, max_iter=300, n_init=10):
self.class_num = class_num
self.cluster_centers_ = None
self.max_iter = max_iter
self.n_init = n_init
def ini_centers(self,x):
cs = np.array([x[np.random.randint(0, len(x), size = 1).item()]])
for j in range(self.class_num - 1):
for i, c in enumerate(cs):
d = np.sqrt(np.sum((x - c) ** 2, 1).reshape(-1, 1))
if i == 0:
dist = d
else:
dist = np.concatenate((dist, d), 1)
# n, class_num
dist = dist.min(1)
dist = dist**2/sum(dist**2)
index = np.random.choice(np.arange(len(x)), p=dist.ravel())
new_c = x[index]
cs = np.concatenate((cs,[new_c]), 0)
return cs
def fit(self,x):
sc = float("inf")
for t in range(self.n_init):
cs = self.ini_centers(x)
# initial
cnt = 0
flag = True
while flag and cnt < self.max_iter:
# predict
label, score = self.predict(x,cs)
# update
new_cs = np.array([x[label==i].mean(0) for i in range(self.class_num)])
if (cs == new_cs).all(): flag = False
cs = new_cs
cnt+=1
if score < sc:
sc = score
self.cluster_centers_ = cs
return self.cluster_centers_
def predict(self,x,cs):
for i,c in enumerate(cs):
d = np.sqrt(np.sum((x - c)**2,1).reshape(-1,1))
if i == 0:
dist = d
else:
dist = np.concatenate((dist,d),1)
label = dist.argmin(1)
score = dist.min(1).sum()
return label, score
def fit_predict(self,x):
self.fit(x)
label, score = self.predict(x,self.cluster_centers_)
return label上述代码经试验基本功能齐备，然而成果跟效率要差于 sklearn 库。有能够改良的中央欢送跟我交换。
[1] Arthur, David and Sergei Vassilvitskii.“k-means++: the advantages of careful seeding.”SODA ’07 (2007).
正文完
