k means algorithm

k 均值算法

这是 k-means 算法的 Python 实现，包括肘部方法和轮廓方法，用于选择最佳 K

K-means 是一种流行的聚类算法，用于将数据划分为 K 个簇。它的工作原理是迭代地将每个数据点分配给最近的聚类质心，然后根据分配给它的数据点重新计算每个聚类的质心。重复该过程直到收敛。

算法

• 从数据点中随机选择 K 个初始簇质心。
• 将每个数据点分配给最近的聚类质心。
• 根据分配给每个簇的数据点重新计算其质心。
• 重复步骤 2-3 直到收敛（即当簇分配不再改变时）。

目标函数

k 均值的目标是最小化每个数据点与其指定的簇质心之间的距离平方和。目标函数可以写为： $$J = sum_{j=1}^K sum_{i=1}^N||x_i^j - mu_j||^2$$在哪里 $x_i^j$是簇j内的i-th数据点， μj是簇j的质心， N是数据点的总数。

弯头法

Elbow 方法是一种启发式方法，用于确定 K 均值聚类中的最佳聚类数。该方法将每个观测值与其指定质心之间的平方距离之和绘制为聚类数量的函数。图上的“弯头”点表示添加额外簇不会导致平方距离总和显着减少的簇数。

Elbow 方法可以概括为以下步骤：

• 对一系列 k 值运行 K 均值聚类
• 计算每个 k 值的距离平方和
• 绘制距离平方和作为 k 的函数
• 识别绘图上的“肘部”点

剪影法

Silhouette 方法是另一种启发式方法，用于确定 K 均值聚类中的最佳聚类数。该方法通过计算其轮廓系数来衡量每个观测的聚类分配的质量。 Silhouette 系数的范围从 -1 到 1，其中值 1 表示观测值聚类良好，值 -1 表示观测值分类错误。数据点i的轮廓系数计算公式为： $$s(i) = frac{(b(i) - a(i))}{max(a(i), b(i))}$$其中a(i)是i与其聚类中所有其他数据点之间的平均距离， b(i)是i与所有其他聚类（即具有下一个最近质心的聚类）之间的最小平均距离。整个聚类的轮廓系数是所有数据点的轮廓系数的平均值。

Silhouette方法可以概括为以下步骤：

• 对一系列 k 值运行 K 均值聚类
• 对于每个观测值，计算轮廓系数
• 计算每个k值的平均轮廓系数
• 将平均轮廓系数绘制为 k 的函数
• 识别平均轮廓系数最高的k值