从零开始的K均值聚类

动机

机器学习的主要思想是创建一个可以根据先前数据提供合理决策而无需显式编程的广义模型。机器学习问题可以是监督或无监督的。本文关注的是一种无监督机器学习算法，称为“K均值”聚类。

当谈到无监督机器学习时，我通常在进行机器学习课程时向我的学生提供一个示例。

假设你被给予一些玩具，如鸭子、蛇、牛、鸽子、山羊、母鸡、船、鳄鱼等。不幸的是，你不知道这些玩具的名称。如果有人要求你将这些动物分成不同的群组，你会怎么做？

如果你进行合理思考，基于它们的外观可能的群组将是群组1：鸭子、母鸡、鸽子；群组2：山羊、牛、船；群组3：鳄鱼、蛇。尽管确切的名称是未知的，但你可能会将这些动物分组。因此，基于相似特征的聚类被称为无监督机器学习算法。

对于基于相似性的数据分组，无监督机器学习非常适用。

无监督学习概述

无监督学习，也被称为无监督机器学习，使用机器学习算法来分析和聚类未标记的数据集。这些算法可以发现隐藏的模式或数据分组，无需人类干预[1]。

假设你是一名硕士研究生，有一个论文导师。你的导师会指导你完成论文，因为他知道如何进行研究和最终目标。监督机器学习算法以相同的方式工作。每个输入都有一个目标值，算法试图从标记的数据中优化其参数以预测一个新实例。无监督学习方法与监督学习正好相反。这些方法处理未标记的数据。无监督学习的主要目的是找出潜在的隐藏模式和见解[2]。通常，这些算法用于解决聚类问题。

无监督机器学习算法有两种类型，如下所示 —

作者提到的文章只关注聚类算法（K均值）。聚类意味着将具有相似特征的数据点分组。有时，无监督学习算法的作用非常重要。

一些优点已经被提出[2] —

• 无监督学习有助于从数据中找到有价值的见解。
• 无监督学习与人类非常相似。我们通过自己的经验学会思考，这使得它更接近真正的人工智能。
• 无监督学习适用于未标记和未分类的数据，这使得无监督学习更为重要。
• 在现实世界中，我们并不总是有具有相应输出的输入数据，因此需要无监督学习来解决这种情况。

K均值的坐标距离计算

• 欧几里得距离

欧几里得距离是计算两个坐标点之间距离的最常用方法。它计算了一对对象的坐标之间的差的平方的平方根[4]。它是两个数据点之间的直线距离。

欧几里得距离可以用以下方程来衡量。这个公式用x和y表示两个点。K是维度的数量（在数据科学中，每个数据集的特征被视为一个维度）。

• 曼哈顿距离

曼哈顿距离计算一对对象的坐标之间的绝对差异[4]。

曼哈顿距离是坐标的绝对距离的总和。可以描述如下。

这里，x和y是两个坐标点，“k”是维度/特征的数量。

• 切比雪夫距离

切比雪夫距离也称为最大值距离，它计算了一对对象的坐标之间的差的绝对值的大小[4]。它是最大坐标值。

x和y代表两个坐标点。它们的切比雪夫距离可以通过在坐标之间找到最大距离来计算。k表示特征的数量。

假设我们有两个点，x(1, 3) 和 y(5,10)。x坐标值是 |1–5| = 4，y坐标值是 |3–10| = 7。因此，max (4, 7) 等于 7。这意味着切比雪夫距离为7。

• 闵可夫斯基距离

闵可夫斯基距离是一种统一的距离公式。使用这个距离公式，我们可以通过改变一个参数来获得上面的所有距离。

距离可以用以下公式计算。两点之间的距离，x和y，k是特征的数量。P是一个唯一的参数，它可以转换方程以计算不同的距离。

请注意，当p=2时，距离变为欧几里得距离。当p=1时，它变成了曼哈顿距离。切比雪夫距离是闵可夫斯基距离的一种变体，其中p=∞（取极限）[4]。

[为了描述这些距离，研究论文[4]和文章[5]对我帮助很大。]

研究结果表明，欧几里得距离是计算K均值聚类算法中数据点之间距离的最佳方法。

K均值聚类算法概述

K均值聚类是一种流行的无监督聚类机器学习算法之一。让我们解释一下它是如何工作的。

步骤1：在最开始，我们需要选择K的值。K表示你想要的聚类数。

步骤2：随机选择每个聚类的质心。

假设对于上面的数据点，我们想创建3个聚类。所以，K=3，而方形着色的数据点是3个随机选择的质心。

步骤3：计算数据点到质心的距离，并根据最小距离将数据点分配到聚类。

从上图中，我们可以清楚地看到每个质心分配了一些数据点，根据不同的颜色表示最小距离。

步骤4：计算每个聚类的均值，并将新的质心重新居中到均值位置。

图像描述了将质心居中到根据均值计算的新位置。

步骤5：重复步骤3和步骤4，直到质心收敛。

重复步骤3和步骤4后，我们得到了上面的聚类。对于下一次迭代，我们得到了以下的聚类。

下一次迭代怎么样？让我们看看。

最后两个聚类和质心是相同的。我们可以说质心收敛，达到了我们的最终目标。

K均值的最佳聚类数

对于K均值聚类算法来说，选择最佳聚类数是一个重要问题。如果你不知道最佳聚类数，你应该应用“肘部法”来找出它。为了保持文章的精确和适度，我将简要解释这种方法。

应用“肘部法”后，我们会得到上面图像中显示的一条折线图。从图中，我们需要找出肘部点以及相应的聚类数。它将被视为最佳的聚类数。对于上图，最佳的聚类数是4。肘部法的详细解释可以在这里找到。

为什么选择K均值？

K均值是最流行的聚类算法。它是一种简单的聚类算法，在大型数据集上表现良好。相对而言，它比其他聚类算法更快。它始终保证收敛到最终的聚类，并且很容易适应新的数据点[3]。

K均值的挑战

在前面的部分中，我们看到K均值聚类算法中初始聚类质心是随机分配的，导致了随机迭代和执行时间。因此，在算法中选择初始质心点是一个关键问题。你可以阅读下面的文章，它介绍了一种系统选择初始质心的技术。

https://towardsdatascience.com/efficient-k-means-clustering-algorithm-with-optimum-iteration-and-execution-time-9358a794406c

该算法对于复杂分布的数据效果不佳。

逐步操作实现

本节将展示从零开始实现K均值聚类算法的逐步操作。对于任何机器学习模型，我们首先需要加载数据集。为了演示目的，我使用了mall_customer数据集。这是一个流行的数据集。

[注意：我使用的是mall_customer数据集，这是一个在“CC0：公有领域”许可下的公开数据集。]

• 导入必要的库

import pandas as pd
import numpy as np 
import matplotlib.pyplot as plt 
import seaborn as sns

• 加载数据集和一些预处理

df=pd.read_csv('/work/Mall_Customers.csv')
df.head()

数据集的信息

df.info()

<class 'pandas.core.frame.DataFrame'>
RangeIndex: 200 entries, 0 to 199
Data columns (total 5 columns):
 #   Column                  Non-Null Count  Dtype 
---  ------                  --------------  ----- 
 0   CustomerID              200 non-null    int64 
 1   Gender                  200 non-null    object
 2   Age                     200 non-null    int64 
 3   Annual Income (k$)      200 non-null    int64 
 4   Spending Score (1-100)  200 non-null    int64 
dtypes: int64(4), object(1)
memory usage: 7.9+ KB

客户ID和性别不是那么重要，所以我已经丢弃了这些列。

df_new=df[['Age', 'Annual Income (k$)','Spending Score (1-100)']]

将数据框转换成NumPy数组。

values_of_data=df_new.values

提取列和行数。

no_of_row=values_of_data.shape[0] 
no_of_column=values_of_data.shape[1] 

• 选择聚类数

K=3 # number of clusters

• 随机选择质心

定义特征大小的空数组。

import numpy as np
C=np.array([]).reshape(no_of_column,0) 

C.shape

(3, 0)

随机选择3个质心用于3个聚类。

import random as rd
for i in range(K):
    random=rd.randint(0,no_of_row-1)
    C=np.c_[C,values_of_data[random]]

print(C)

[[33. 27. 21.]
 [42. 46. 30.]
 [60. 51. 73.]]

• 下面的代码实现了K均值聚类概述部分中提到的步骤3、步骤4和步骤5。

dif=1

while(dif>0):
    C1=C.copy() #Cloning the centroids

    #creating empty array for holding the distances from the centroids 
    E=np.array([]).reshape(no_of_row,0)

    for k in range(K):
        #distance calculation from centroids using euclidean formula. 
        temp=(df_new - np.array(C[:,k])).pow(2).sum(1).pow(0.5)
        E=np.c_[E,temp]

    #assigning cluster elements based on minimum distance
    cluster_index=np.argmin(E,axis=1)+1

    #Generating clusters 
    cluster={}
    for clus in range(K):
        cluster[clus+1]=np.array([]).reshape(3,0)
    for i in range(no_of_row):
        cluster[cluster_index[i]]=np.c_[cluster[cluster_index[i]],values_of_data[i]]

    for clus in range(K):
        cluster[clus+1]=cluster[clus+1].T

    #mean calculation and recentering the centroids 
    for clus in range(K):
        C[:,clus]=np.mean(cluster[clus+1],axis=0)

    ''' Comparing centroids and checking whether the centroids are changing or not. 
    If it doesn't change, the program will terminate.'''

    if (C1==C).all():
        break

我在上面的代码中添加了一些命令，以便更容易理解功能。

• 可视化聚类

# Import libraries
from mpl_toolkits import mplot3d
import matplotlib.pyplot as plt
import seaborn as sns

fig = plt.figure(figsize = (10, 7))
ax = plt.axes(projection ="3d")

clr=['#F3174F', '#258474', '#FF220C']

# Creating plot
for i in range(K):
    ax.scatter3D(cluster[i+1][:,0],cluster[i+1][:,1], cluster[i+1][:,2],s=120, color =clr[i])



plt.title("Cluster 3D scatter plot")


# show plot
plt.show()

在3D空间中，每个聚类用不同的颜色表示。

结论

K均值聚类算法简单易用。在实施算法之前，我们需要谨慎考虑算法的用例和底层工作原理。对于非常复杂的分布数据，该算法效果不佳。

参考资料

1. What is Unsupervised Learning? | IBM
2. https://www.javatpoint.com/unsupervised-machine-learning
3. k-Means Advantages and Disadvantages | Machine Learning | Google Developers
4. Singh, A., Yadav, A., & Rana, A. (2013). K-means with three different distance metrics. International Journal of Computer Applications, 67(10).
5. https://towardsdatascience.com/9-distance-measures-in-data-science-918109d069fa
6. Zubair, M., Iqbal, M.A., Shil, A. et al. An Improved K-means Clustering Algorithm Towards an Efficient Data-Driven Modeling. Ann. Data. Sci. (2022). https://doi.org/10.1007/s40745-022-00428-2