机器学习-聚类算法Kmeans【手撕】

聚类算法

在训练时，使用没有标签的数据集进行训练，希望在没有标签的数据里面可以发现潜在的一些结构。
其中使用范围较广的是，聚类算法。聚类算法的目的是将数据划分成有意义或有用的组（或簇）。这种划分可以基于我们的业务需求或建模需求来完成，也可以单纯地帮助我们探索数据的自然结构和分布。比如在商业中，如果我们手头有大量 的当前和潜在客户的信息，我们可以使用聚类将客户划分为若干组，以便进一步分析和开展营销活动，最有名的客户价值判断模型RFM，就常常和聚类分析共同使用。再比如，聚类可以用于降维和矢量量化（vector quantization），可以将高维特征压缩到一列当中，常常用于图像，声音，视频等非结构化数据，可以大幅度压缩数据量。

Kmeans

作为聚类算法的典型代表，KMeans可以说是最简单的聚类算法没有之一。
在聚类算法中，有两个概念非常重要：簇和质心
聚类算法将一组$N$个样本的特征矩阵$X$划分为$K$个无交集的簇，直观上来看是簇是一组一组聚集在一起的数据，在一个簇中的数据就认为是同一类。簇就是聚类的结果表现。簇中所有数据的均值通常被称为这个簇的“质心”（centroids）。在一个二维平面中，一簇数据点的质心的横坐标就是这一簇数据点的横坐标的均值，质心的纵坐标就是这一簇数据点的纵坐标的均值。同理可推广至高维空间。
Kmeans算法中，步骤可以分为四步：
（1）数据预处理。主要是标准化，异常点过滤
（2）随机选取K个中心，计为${\mu }_1^{(0)}$, ${\mu }_2^{(0)}$,…, ${\mu }_k^{(0)}$
（3）定义损失：$J(c,\mu )=min{\sum }_{i=1}^M||x_i-{\mu }_{c_i}|{|}^2$
（4）令$t=0,1,2,...,k$为迭代步数，重复如下过程直至$J$收敛：
（4.1）对于每一个样本$x_i$，将其分配到距离最近的中心：$c_i^t<-argmin||x_i-{\mu }_k^t|{|}^2$
（4.2）对于每个类中心点$k$，重新计算该类的中心：${\mu }_k^{(t+1)}<-argmin{\sum }_{i:c_i^t=k}^k||x_i-\mu |{|}^2$

KMeans最核心的部分就是先固定中心点，调整每个样本所属的类别来减少$J$；再固定每个样本的类别，调整中心点继续减小$J$ 。两个过程交替循环，$J$单调递减直到最（极）小值，中心点和样本划分的类别同时收敛。

聚类算法如何评价

聚类算法聚出的类有什么含义呢？这些类有什么样的性质？我们认为，被分在同一个簇中的数据是有相似性的，而不同簇中的数据是不同的，当聚类完毕之后，我们就要分别去研究每个簇中的样本都有什么样的性质，从而根据业务需求制定不同的商业或者科技策略。这个听上去和我们在上周的评分卡案例中讲解的“分箱”概念有些类似，即我们分箱的目的是希望，一个箱内的人有着相似的信用风险，而不同箱的人的信用风险差异巨大，以此来区别不同信用度的人，因此我们追求“组内差异小，组间差异大”。聚类算法也是同样的目的，我们追求“簇内差异小，簇外差异大”。而这个“差异“，由样本点到其所在簇的质心的距离来衡量。

对于一个簇来说，所有样本点到质心的距离之和越小，我们就认为这个簇中的样本越相似，簇内差异就越小。而距离的衡量方法有多种，令$x$表示簇中的一个样本点，$\mu$表示该簇中的质心，$n$表示每个样本点中的特征数目，$i$表示组$x$成点的每个特征，则该样本点到质心的距离可以由以下距离来度量：

欧式距离：
$$d(x,\mu )=\sqrt{\sum _{i=1}^n(x_i-\mu {)}^2}$$
曼哈顿距离：
$$d(x,\mu )=\sum _{i=1}^n(|x_i-\mu |)$$
余弦距离：
$$cos\theta =\frac{{\sum }_1^n(x_i\ast \mu )}{\sqrt{{\sum }_{i=1}^n(x_i{)}^2}\ast \sqrt{{\sum }_{i=1}^n(\mu {)}^2}}$$

如我们采用欧几里得距离，则一个簇中所有样本点到质心的距离的平方和为：
$$\begin{gathered} ClusterSumofSquare(CSS)=\sum _{j=0}^m\sum _{i=1}^n(x_i-{\mu }_i{)}^2 \\ TotalClusterSumofSquare=\sum _{l=1}^{k}CS{S}_l \end{gathered}$$
其中，$m$为一个簇中样本的个数，$j$是每个样本的编号。这个公式被称为簇内平方和（cluster Sum of Square），又叫做Inertia。而将一个数据集中的所有簇的簇内平方和相加，就得到了整体平方和（Total Cluster Sum of Square），又叫做total inertia。Total Inertia越小，代表着每个簇内样本越相似，聚类的效果就越好。因此KMeans追求的是，求解能够让Inertia最小化的质心。实际上，在质心不断变化不断迭代的过程中，总体平方和是越来越小的。我们可以使用数学来证明，当整体平方和最小的时候，质心就不再发生变化了。如此，K-Means的求解过程，就变成了一个最优化问题。

代码

import numpy as np
import matplotlib.pyplot as plt
 
# 生成随机数据
np.random.seed(0)
X = np.random.rand(100, 2)
 
# 定义K值和迭代次数
K = 3
max_iterations = 100
 
# 随机初始化簇中心点
centers = X[np.random.choice(X.shape[0], K, replace=False)]
 
# 迭代更新簇中心点
for _ in range(max_iterations):
    # 计算每个数据点到每个簇中心点的欧氏距离
    distances = np.linalg.norm(X[:, np.newaxis, :] - centers, axis=2)
    
    # 分配每个数据点到最近的簇
    labels = np.argmin(distances, axis=1)
    
    # 更新簇中心点为每个簇的平均值
    new_centers = np.array([X[labels == k].mean(axis=0) for k in range(K)])
    
    # 如果簇中心点不再改变，结束迭代
    if np.all(centers == new_centers):
        break
    
    centers = new_centers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

参考

【手撕】K-measn算法及python代码实现及改进_k-means手撕代码-CSDN博客
菜菜的scikit-learn课堂