K均值算法原理

K均值（K-means）算法属于无监督学习中的聚类算法；聚类是根据样本特征向量之间的相似度或距离，将样本数据划分为若干个样本子集，每个子集定义为一个类；相似的样本聚集在相同的类，不相似的样本分散在不同的类。由上面的定义可知，聚类算法只使用了样本的特征向量 $x$ ，并没有使用样本的标签 $y$ ，故聚类算法属于无监督学习

样本距离
样本距离越小，样本的相似性越大。K均值聚类使用欧式距离的平方作为样本距离，计算公式如下：
$d(x_{i},x_{j})=\sum_{k=1}^{m}(x_{ki}-x_{kj})^{2}=||x_{i}-x_{j}||_{2}^{2}$
$x_{i}=[x_{1i},x_{2i},...,x_{mi}]^{T},x_{j}=[x_{1j},x_{2j},...,x_{mj}]^{T}$
如上所述，先计算向量对应元素的差值，然后取平方，最后求和；这个计算过程还可以表示为：先对两个样本的特征向量作差，然后求二范数的平方。

K均值聚类使用欧氏距离的平方表示样本之间的距离或相似度。除此之外，欧氏距离、相关系数、夹角余弦等也可以用来表示两个样本特征向量之间的距离或相似度。

聚类中心
聚类得到的结果是若干样本子集，对样本子集中的特征向量求均值可以得到类中心：
$\overline{x}_{G}=\frac{1}{|G|}\sum_{i=1}^{|G|}x_{i},x_{i}\in G$
其中， $x_{i}$ 为样本特征向量， $∣ G ∣$ 为类别 $G$ 的样本个数；

算法流程

1.随机选取 $K$ 个样本点作为初始聚类中心；
2.计算样本特征向量 $x_{i}$ 和每个聚类中心 $c_{j}$ 的距离，计算公式如下：
$d(x_{i},c_{j})=\sum_{k=1}^{m}(x_{ki}-c_{kj})^{2}$
$x_{i}=[x_{1i},x_{2i},...,x_{mi}]^{T},c_{j}=[c_{1j},c_{2j},...,c_{mj}]^{T}$
$i\in \left \{1,2,...,n \right \},j\in \left \{1,2,...,K \right \}$ ， $n$ 为数据集的样本数， $K$ 为聚类的类别数；
3.将样本 $x_{i}$ 划分到离他最近的聚类中心所对应的类中；
4.使用样本特征向量的均值，更新各个聚类中心，均值的计算公式如下：
$\overline{x}_{G}=\frac{1}{|G|}\sum_{i=1}^{|G|}x_{i},x_{i}\in G$
其中， $x_{i}$ 为样本特征向量， $∣ G ∣$ 为类别 $G$ 的样本个数；
5.重复步骤 2~4，直到聚类中心不再变化

K均值算法的改进：K-means++

K 均值聚类的算法流程，由于原理简单、实现方便、模型的可解释性较强，所以比较常用。K均值聚类是通过最小化样本与其所属类中心的距离总和来进行算法迭代，具体做法是：先随机初始化类中心，将样本划分到离他最近的类中心，然后更新类中心，重复上述步骤，直到聚类中心不再变化。

但是K均值算法并不能保证收敛到全局最优，初始类中心的选择会直接影响到聚类的结果。一般来说：相同类中的样本距离较近，不同类中的样本距离较远。因此，初始的各个聚类中心应该越远越好。

K-means++ 算法原理
基于上述观点，K-means++算法针对初始聚类中心的选择做了优化和改进，具体步骤如下：

步骤1：从数据集 $X$ 中随机选择一个样本点作为第一个初始类中心 $c_{1}$ ；
步骤2：计算 $X$ 中的每个样本点 $x_{i}$ 和已有聚类中心的最近样本距离 $d(x_{i})$ ；
假如已经初始化了 3 个聚类中心，则分别计算该样本点和这 3 个聚类中心的样本距离，取其中的最短距离作为计算结果，用数学公式表示如下：
$d(x_{i})=min_{j\in \left \{1,2,3 \right \}}||x_{i}-c_{j}||_{2}^{2}$
样本距离是欧氏距离的平方，和 K-means 算法保持一致；
步骤3：计算每个样本点作为聚类中心的概率 $p(x_{i})$ ，公式如下：
$p(x_{i})=\frac{d(x_{i})}{\sum_{j=1}^{n}d(x_{j})}$
步骤4：根据 $p(x_{i})$ 从样本数据中随机选择聚类中心，距离已有聚类中心越远的样本点越有可能称为下一个初始聚类中心；
步骤5：重复步骤 2~4，直到初始聚类中心的数量达到 $K$ 。

除了初始聚类中心的选择，K-means++ 其余部分与 K-means 算法的流程一致；

K-means++ 算法关于初始聚类中心的选择实现如下：

import numpy as np # 欧氏距离的平方
def distance(u,v):'''u,v: 一维 numpy 数组表示的特征向量'''return sum((u-v)**2)def center_init(data,k):'''data: numpy array,样本特征向量集合k: int,聚类中心的个数'''# 用来保存聚类中心center = []# 随机选择一个样本特征向量的索引index = np.random.choice(range(len(data)))# 根据索引获得第一个聚类中心center.append(data[index])# 获取剩余 k-1 个聚类中心for _ in range(k-1):# 样本被选为聚类中心的概率prob = []# 遍历每个样本数据for x in data:# 根据步骤 2 的公式计算样本与最近类中心的距离d = min([distance(x,c) for c in center])prob.append(d)# 计算每个样本的被选概率prob = np.array(prob)/sum(prob)# 根据被选中的概率随机选择一个样本特征向量的索引i = np.random.choice(a=range(len(data)),p=prob)# 根据索引添加一个聚类中心center.append(data[i])# 返回 k 个初始化的聚类中心return np.array(center)

除了初始聚类中心，K值的选择以及样本距离计算方法的选择也会影响到聚类的结果。其中，K值属于超参数，需要根据实际聚类结果来调节

numpy实现K-means

定义函数distance计算样本距离：

def distance(u,v):'''u,v: 一维 numpy 数组表示的特征向量'''# 返回欧氏距离的平方return sum((u-v)**2)

初始化聚类中心：

import numpy as np# 从 data 中随机选择 k 个样本特征向量，作为初始聚类中心
def center_init(data,k):'''data: 存放样本特征向量的 numpy arrayk: 聚类中心的个数'''# 设置随机种子np.random.seed(2021)# 随机选择 k 个样本特征向量的索引index = np.random.choice(a=range(len(data)),size=k)# 根据索引获得 k 个聚类中心return data[index]

样本聚类：

def predict(x,center):'''x: 一维数组表示的样本特征向量center: 存放 k 个聚类中心的数组'''# 输入的样本 x 必须为一维数组，否则触发异常assert np.array(x).ndim==1# 返回距离样本 x 最近的聚类中心索引return np.argmin([distance(x,c) for c in center])

获取聚类中心对应的样本子集：

def cluster(data,center):'''data: 存放样本特征向量的 numpy arraycenter: 存放 k 个聚类中心的数组'''# 存放各类样本子集的字典：key = 聚类中心索引; value = data 子集center_data = dict()# 遍历样本特征向量for x in data:# 获取样本 x 的聚类索引i =  predict(x,center)# 将 x 添加到聚类索引对应的样本子集中"""D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in DD.get(k[,d]) -> D[k] if k in D, else d.  d defaults to None."""center_data.setdefault(i,[])center_data[i].append(x)# 返回各聚类中心对应的样本子集return center_data

聚类可视化，二维空间可视化：

import matplotlib.pyplot as pltdef visualization_2D(center,center_data):'''center: 存放 k 个聚类中心的数组center_data: 聚类中心对应的样本子集的集合'''# 设置画布大小plt.figure(figsize=(8,6))# 设置可选颜色：红、绿、蓝color = ['r','g','b']# 遍历每个聚类中心的索引for i in center_data:# 根据索引，取该聚类中心对应的样本第一列特征x = np.array(center_data[i])[:,0]# 根据索引，取该聚类中心对应的样本第二列特征y = np.array(center_data[i])[:,1]# 绘制当前聚类的样本散点图，s 控制大小，c 控制颜色plt.scatter(x,y,s=30,c=color[i])# 遍历每个聚类中心 c 和对应的索引 ifor i,c in enumerate(center):# 在二维平面上绘制聚类中心，alpha 控制透明度plt.scatter(x=c[0],y=c[1],s=200,c=color[i],alpha=0.2)# 显示图片plt.show()

三维空间可视化：

from mpl_toolkits import mplot3ddef visualization_3D(center,center_data):'''center: 存放 k 个聚类中心的数组center_data: 聚类中心对应的样本子集'''# 取第一个聚类的样本子集，若样本的特征维数小于 3if np.array(center_data[0]).shape[1] < 3:# 则返回空值，放弃三维可视化return None# 设置画布大小plt.figure(figsize=(10,8))# 设置可选颜色：红、绿、蓝color = ['r','g','b']# 创建三维空间直角坐标系ax = plt.axes(projection='3d')# 遍历每个聚类中心的索引for i in center_data:# 根据索引，取该聚类中心对应的样本第一列特征x = np.array(center_data[i])[:,0]# 根据索引，取该聚类中心对应的样本第二列特征y = np.array(center_data[i])[:,1]# 根据索引，取该聚类中心对应的样本第三列特征z = np.array(center_data[i])[:,2]# 绘制当前聚类的样本散点图，s 控制大小，c 控制颜色ax.scatter3D(x,y,z,s=30,c=color[i])# 遍历每个聚类中心 c 和对应的索引 ifor i,c in enumerate(center):# 在三维空间中绘制当前聚类中心，alpha 控制透明度ax.scatter3D(xs=c[0],ys=c[1],zs=c[2],s=200,c=color[i],alpha=0.2)# 显示图片plt.show()

算法迭代：

def fit(data,k,visualization=None):'''data: 存放样本特征向量的 numpy arrayvisualization： 可视化选项，默认为 None，不对聚类过程做可视化'''# 初始化聚类中心center = center_init(data,k)# 循环迭代while True:# 根据已有的聚类中心将样本划分到不同的聚类集合中center_data = cluster(data,center)# 当前聚类中心和样本特征向量在二维空间的可视化 if visualization == '2d':visualization_2D(center,center_data)# 当前聚类中心和样本特征向量在三维空间的可视化 if visualization == '3d':visualization_3D(center,center_data)# 保存上一次迭代的聚类中心old_center = center.copy()# 遍历各个聚类中心的索引for i in center_data:# 更新每一个聚类中心：样本子集特征向量的均值center[i] = np.mean(center_data[i],axis=0)# 循环迭代的停止条件：最近两次迭代，聚类中心的位置不再变化if sum([distance(center[i],old_center[i]) for i in range(k)]) == 0:breakreturn center,center_data

算法实例：

x1 = [1,2,4,5,7,8,9,3,6]
x2 = [2,2,5,7,1,3,5,2,6]
data = np.array([i for i in zip(x1,x2)])
"""
array([[1, 2],[2, 2],[4, 5],[5, 7],[7, 1],[8, 3],[9, 5],[3, 2],[6, 6]])
"""# 聚类簇数
k = 3
# 获取最终的聚类中心和对应的样本子集，并对聚类过程可视化
center,center_data = fit(data,k,visualization='2d')
# 聚类中心和样本特征向量在二维空间的最终可视化 
visualization_2D(center,center_data)