k-means算法公式原理

k-means算法是一种常见的无监督学习算法，用于将数据集划分为k个簇。其基本原理如下：

1. 随机选择k个初始质心，每个质心代表一个簇。

2. 将每个样本点分配给距离它最近的质心所代表的簇，形成k个簇。

3. 对于每个簇，重新计算质心，即将簇内所有点的均值作为新的质心。

4. 重复步骤2和3，直到质心不再发生变化，或达到预设的迭代次数。

k-means算法的核心在于簇内平均误差最小化（SSE，Sum of Squared Errors），即最小化每个样本点与它所属簇的质心之间的距离平方和。其数学公式如下：

$$
SSE=\sum_{i=1}^{k}\sum_{\boldsymbol{x}\in C_i}\left\|\boldsymbol{x}-\boldsymbol{\mu_i}\right\|^2
$$

其中，$k$为簇的个数，$C_i$为第$i$个簇中所有样本组成的集合，$\boldsymbol{\mu_i}$为第$i$个簇的质心。

k-means算法的时间复杂度为$O(kn)$，其中$n$为样本数量。由于k-means算法对初始质心的选择敏感，因此常常使用k-means++算法来初始化质心，以提高聚类效果。

相关问题

K-Means 聚类算法原理数学公式

### K-Means聚类算法工作原理

K均值聚类是一种无监督学习方法，用于将一组未标记的数据划分为多个簇（cluster）。该算法的目标是在最小化各簇内样本之间的差异的同时最大化不同簇间的差异。

#### 初始化阶段
首先随机选取 \( k \) 个初始质心作为各个簇的核心位置[^1]。这些质心可以被看作是代表各自簇特性的点，在多维空间中表示出来。

#### 分配与更新循环
对于每一个数据点计算其到所有质心的距离并将其分配给最近的那个质心所对应的簇；接着重新计算每个簇的新质心坐标直到满足停止条件为止。这个过程可以通过下面两个主要步骤来描述：

- **E步 (Expectation Step)**: 对于所有的观测向量 \( x_i \)，找到离它最近的当前估计出来的中心 \( c_j^{(t)} \)，并将此观测归属于第 j 类。

\[ argmin_{j} ||x_i - c_j^{(t)}||^2 \]

其中\( t \) 表示迭代次数，而 \( c_j^{(t)} \) 则是指在第 t 次迭代时第 j 组群组的心脏位置。

- **M步 (Maximization Step)** : 更新每一群体内的平均数即新的心脏位置:

\[
c_j^{(t+1)}=\frac{\sum\nolimits _{i=1}^{n}\delta(j,i)x_i}{\sum\nolimits _{i=1}^{n}\delta(j,i)}
\]

这里的 δ 函数定义如下：
当且仅当 xi 属于类别 cj 的时候取值为 1 否则为零。

上述两步构成了EM算法框架下的单次迭代操作，整个流程持续重复直至达到收敛标准或最大允许迭代次数结束。

#### 数学优化视角下目标函数
从数学角度出发,K-means试图解决的是一个组合最优化问题,具体来说就是寻找最优解使得总误差平方和(Sum of Squared Errors,SSE)最小化.

设 n 是总的样本数量,k 是预设好的分类数目，则SSE可表达成如下形式:

\[
J(C)=\sum_{j=1}^{k}\sum_{x_i\in C_j}||x_i-\mu_j||^2
\]

这里 μj 表达了对应子集Cj内部成员坐标的算术平均值也就是所谓的“质心”。通过不断调整各类别中的对象构成以及相应质心的位置从而逐步逼近全局极小值点以期获得较为理想的分割效果[^4].

import numpy as np

def kmeans(data_points, k, max_iters):
    centroids = data_points[np.random.choice(len(data_points), size=k)]
    
    for i in range(max_iters):
        cluster_assignments = assign_clusters(data_points, centroids)
        
        new_centroids = update_centroids(data_points, cluster_assignments, k)

        if np.allclose(new_centroids, centroids): break
        
        centroids = new_centroids
    
    return centroids, cluster_assignments


def assign_clusters(X, centers):
    distances = euclidean_distances(X, centers)
    closest_centers_indices = np.argmin(distances, axis=1)
    return closest_centers_indices


def update_centroids(X, labels, num_clusters):
    updated_centers = []
    for label in set(labels):
        mask = (labels == label).reshape(-1, 1)
        center = X[mask].mean(axis=0)
        updated_centers.append(center.flatten())
    return np.array(updated_centers)


def euclidean_distances(a,b):
    a_squared=np.sum(np.square(a),axis=-1)[...,None]
    b_squared=(np.sum(np.square(b),axis=-1))
    ab=-(2*np.dot(a,np.transpose(b)))
    result=a_squared+b_squared+ab
    return np.sqrt(result.clip(min=0))

data_points = [[...], [...]] # Your dataset here.
final_centroids, final_cluster_assignments = kmeans(data_points=data_points, k=3, max_iters=10)

k-means++算法公式原理

k-means++算法是一种改进的k-means聚类算法，它通过改变初始质心的选择方式，避免了传统k-means聚类算法对初始质心敏感的问题。

k-means++算法的质心初始化过程如下：

1. 随机选择一个样本作为第一个质心。

2. 对于每个样本$x_i$，计算它与已经选取的质心之间的最短距离$d(x_i)^2$。

3. 选择一个新的质心，使得它被选作新的质心的概率与它与已有质心的最短距离$d(x_i)^2$成正比。

4. 重复步骤2和3，直到选取k个质心。

k-means++算法的核心在于第3步的随机选择，它保证了新的质心距离已有质心的距离更远，从而能够更好地代表不同的簇。此外，k-means++算法的时间复杂度和传统k-means算法相同，都是O(kn)。