K-Means

• 什么是无监督学习？
  • 聚类
  • 降维
  • 话题分析
  • 图分析
• 什么是 K 均值聚类
  • 模型
  • 策略
  • 算法
• 算法特点
• K-Means 和 KNN 有关系么？
• Python实现
• K-Means相关面经和其他资料
• 小结

什么是无监督学习？

之前我们介绍了许多监督学习算法，例如逻辑回归、支持向量机、朴素贝叶斯等等，虽说他们各有各的特点，但是他们都属于监督学习算法。简单来说，监督学习研究的事标签数据和特征之间的某种函数关系，或者说求得标签数据关于特征的条件概率，但是实际上，要得到大规模的标签数据是很困难的，成本也是相当高，那么无监督学习就是在没有标签数据的情况下，在现有已知的特征里寻找数据的“潜在结构”（pattern），所以比起监督学习，无监督学习要更难一些。接下来，让我们来了解一些代表性的无监督学习方法吧！

聚类

聚类（clustering）算是比较常用且实用的无监督学习方法了！它主要用于数据分析，也用于监督学习的预处理（pre-proprecessing），聚类可帮助我们发现数据中的一些规律。说白了，聚类算法就是根据特定规则，把数据分类，输入只有数据的特征（无 label），而输出则是分类标签，我们要讨论的 K-Means 就是一种最常见的聚类算法。

降维

降维同样在数据分析和预处理上占有很重要的位置，帮助我们解析高维数据，例如我们接下来要具体讲的主成分分析（PCA）和奇异值分解（SVD）。我们可以把高维数据进行降维转换，得到在新的二维（或更高）的实数空间里的新特征，从而再利用聚类或者其他手段去发现数据的规律。

话题分析

话题分析涵盖在文本分析之中，大家都知道机器学习在文本分析上的应用十分广泛，也表现相当优异，话题分析自然也很受欢迎，其在于发现文本集合中每个文本的话题，而话题由单词的集合表示（假设我们有足够多的文本）。话题分析可以转换成概率模型估计问题或者降维问题。

图分析

很多情况下，数据是以图的形式存在，图数据表示实体之间的联系，包括有向图、无向图、超图等。图分析在于发掘隐藏在图中的统计规律和潜在结构，例如 PageRank 算法，给定一个有向图，定义在图上的马尔科夫链（随机游走），其在有向图上随机跳转，到达一个结点后以等概率跳转到链接出去的结点，不断持续下去，PageRank 算法是求解马尔科夫链（Markov Chain）的平稳分布（stationary distribution）的算法。

简单介绍一下，根据图中的结点，PageRank 算法通过迭代求出结点的 PageRank 值。首先，对每个结点的概率值初始化，表示各个结点的到达概率（假设等概率），接下来，各个结点的概率是上一步各个结点可能跳转到该节点的概率之和，不断迭代，各个结点的到达概率分布趋近于平稳分布。

什么是 K 均值聚类？

K 均值聚类是基于样本集合划分的聚类方法。K 均值聚类把样本集合划分为 K 个子集， 构成 K 个类，将 n 个样本分到 K 个类中，每个样本到其所属类的中心距离最小。每个样本只能属于一个类，所以其属于硬聚类算法。

模型

给定 n 个样本的集合 $X = \{x_1,x_2,\cdots,x_n\}$，每个样本由特征向量表示，并且维度为 m。K-Means 是将 n 个样本分到 k 个不同的类或者簇中，假设 k < n。k 个类形成对样本集合的划分，其中每个类之间没有交集，并且他们的并集是整个集合，用 C 表示划分，一个划分对应一个聚类结果。

策略

K-Means 归结为样本集合的划分，或者从样本到类的函数的选择问题。K 均值聚类的策略是通过损失函数的最小化选取最优的划分！

先采取欧式距离来定义样本之间的距离：

$d(x_i,x_j) = \sum_{k=1}^{m}(x_{ki}-x_{kj})^2=||x_i-x_j||^2$

然后，定义样本和其所属类的中心的距离的总和为损失函数：

$W(C) = \sum_{l=1}^{k}\sum_{C(i)=l}||x_i-\overline x_l||^2$

其中，$\overline x_l = (\overline x_{1l}, \overline x_{2l}, \cdots, \overline x_{ml} )^T$ 是第 $l$ 个类的均值或中心，$\sum_{C(i)=l}||x_i-\overline x_l||^2$ 代表属于 $l$ 类的所有点到中心的集合。

那么 K 均值聚类就是求解最优化问题：

$arg \min_C \sum_{l=1}^{k}\sum_{C(i)=l}||x_i-\overline x_l||^2$

但是由于我们要把 n 个样本分到 k 类，所有可能分法的数目是：

$S(n,k) = \frac{1}{k!}\sum_{l=1}^{k}(-1)^{k-l}C(n,k)k^n$

这个指数级数字是可怕的，现实中要用迭代法求解。

算法

K 均值聚类的迭代算法包括两个步骤。

• 选择 k 个类的中心，将样本逐个派到与其最近的中心的类中，得到一个聚类结果；
• 然后更新每个类的样本均值，作为类的新中心；
• 重复直到收敛为止

输入：n 个样本的集合 X
输出：样本集合的聚类 C

（1） 初始化。令 t = 0，随机选择 k 个样本点作为初始聚类中心 $m^{(0)} = (m^{(0)}_1, \cdots, m^{(0)}_l, \cdots, m^{(0)}_k)$。

（2） 对样本进行聚类。对固定的类中心 $m^{(t)} = (m^{(t)}_1, \cdots, m^{(t)}_l, \cdots, m^{(t)}_k)$，其中 $m^{(t)}_l$ 为类 $G_l$ 的中心，计算每个样本到类中心的距离，将每个样本指派到与其最近的中心的类中，构成聚类结果 $C^{(t)}$。

（3）计算新的类中心。对聚类结果 $C^{(t)}$，计算当前各个类中的样本均值，作为新的类中心 $m^{(t+1)} = (m^{(t+1)}_1, \cdots, m^{(t+1)}_l, \cdots, m^{(t+1)}_k)$。

（4）如果迭代收敛或符合停止条件，输出 $C = C^{(t)}$，否则，令 $t = t + 1$，返回步骤（2）。

算法的复杂度是 $O(mnk)$，其中 m 是样本维数，n 是样本个数，k 是类别个数。

算法特点

1. 总体特点
   K 均值聚类是基于划分的聚类方法；类别数 k 需要先指定；以欧式距离来度量样本间距离；以样本和其所属类的中心之间距离的总和为目标函数；算法是迭代算法，不能保证全局最优。
2. 收敛性
   K 均值聚类算法的初始中心的选择会影响迭代结果，不能保证全局最优，虽然类中心会随着聚类过程而移动，但是往往这种移动不会太大。
3. 初始类的选取
   不同初始中心，聚类结果不同，要注意合适的选择初始中心。
4. k 的选择
   k 需要预先指定，而在实际当中最优的 k 值是未知的，我们可以尝试不同的 k，检验得到的结果来进行推测。通常用于比较不同 K 值的结果的度量之一是数据点与其聚类质心之间的平均距离。一般来说，类别数变小时，平均直径增加；类别数变大超过某个值以后，平均直径会不变；这个值就是最优 k 值。

K-Means 和 KNN 有关系么？

我们知道 K 近邻也是类似于 K-Means 这种以样本集数据点之间的距离作为度量依据的算法，并且也要尝试不同的 k 值来优化结果，那么他们有联系么？

KNN	K-Means
分类算法	聚类算法
监督学习	无监督学习
使用标签数据	使用无标签数据
不需要训练过程	需要训练过程

如需要更详细了解或者回顾 KNN 的相关内容，请点击这里。

Python实现

import matplotlib.pyplot as plt 
from matplotlib import style
style.use('ggplot')  
import numpy as np

X = np.array([[1,  2],  
			  [1.5,  1.8],  
			  [5,  8  ],  
			  [8,  8],  
			  [1,  0.6],  
			  [9,11]]) 

plt.scatter(X[:,0], X[:,1], s=150) 
plt.show() 
colors =  10*["g","r","c","b","k"]  
class K_Means:  
	def __init__(self, k=2, tol=0.001, max_iter=300): 
		self.k = k
        self.tol = tol
        self.max_iter = max_iter 
	
	def fit(self,data): 
		self.centroids =  {}  
		for i in range(self.k):
			self.centroids[i]  = data[i]  
						
		for i in range(self.max_iter):
			self.classifications =  {} 
			 
			for i in range(self.k):
				self.classifications[i]  =  []  
			for featureset in data:
				distances =  [np.linalg.norm(featureset-self.centroids[centroid])  for centroid in self.centroids] 
				classification = distances.index(min(distances))
				self.classifications[classification].append(featureset) 
			prev_centroids = dict(self.centroids)  
			for classification in self.classifications: 
				self.centroids[classification]  = np.average(self.classifications[classification],axis=0)
			optimized = True
			
			for c in self.centroids: 
				original_centroid = prev_centroids[c] 
				current_centroid = self.centroids[c]  
				if np.sum((current_centroid-original_centroid)/original_centroid*100.0)  > self.tol:  
					print(np.sum((current_centroid-original_centroid)/original_centroid*100.0)) 
					optimized =  False
				if optimized:
					break
	def predict(self,data): d
		istances =  [np.linalg.norm(data-self.centroids[centroid])  for centroid in self.centroids] 
		classification = distances.index(min(distances))  
		return classification

clf = K_Means() 
clf.fit(X)  

for centroid in clf.centroids:
	plt.scatter(clf.centroids[centroid][0], clf.centroids[centroid][1], marker="o", color="k", s=150, linewidths=5)  

for classification in clf.classifications:
	color = colors[classification]  
	for featureset in clf.classifications[classification]: 
		plt.scatter(featureset[0], featureset[1], marker="x", color=color, s=150, linewidths=5) 

plt.show()

–> 代码下载

• Sklearn kmeans
• Real Python kmeans

相关面经和其他资料

• Kmeans聚类算法原理 刘建平
• TensorFlow实现kmeans算法（字节跳动面试题）
• 机器学习面试题汇总(K-means，KNN相关)
• Kmeans优缺点

小结

聚类算法依据数据的特性，将其归于到若干个类里面，一个类是样本的一个自己，相似样本聚类。聚类要预先确定三个因素：距离或者相似度；合并规则；终止条件。

k 均值聚类是非常常用的聚类算法，首先选择 k 个类的中心，将样本分到与中心最近的类中，得到一个聚类结果；然后计算每个类的样本均值，作为类的新中心，重复直到收敛为止。