机器学习周志华聚类推导

### 周志华《机器学习》中的聚类算法推导

#### K均值聚类算法的推导

K均值聚类是一种无监督学习方法，旨在将数据集划分为若干簇，使得同一簇内的对象相似度尽可能高，而不同簇之间的对象相似度尽可能低。具体来说，给定一组未标记的数据点 \( \{x_1, x_2, ..., x_n\} \)，其中每个 \( x_i \in R^d \)，目标是找到 k 个中心点 \( c_j (j=1,...,k) \)，使所有数据点到最近中心的距离平方和最小化。

定义代价函数 J 如下：

\[ J(C)=\sum_{i=1}^{n}\left \| x_i-c_{z(i)} \right \|^2 \]

这里 \( z(i)\in {1,\ldots,k } \) 表示第 i 个样本所属类别编号；\( C=\{c_1,c_2,…,c_k\} \) 是指由这 k 类质心组成的集合[^1]。

为了求解上述最优化问题，可以采用迭代的方式更新簇分配以及重新计算新的质心位置直到收敛为止。每次迭代过程中先固定当前得到的一组质心去划分各个实例归属哪个簇，再依据新形成的各簇调整其对应的质心坐标。此过程不断重复直至满足停止条件，比如达到最大循环次数或是前后两次变化幅度小于设定阈值等。

import numpy as np

def k_means(X, k, max_iters=100):
    # 随机初始化质心
    centroids = X[np.random.choice(range(len(X)), size=k, replace=False)]
    
    for _ in range(max_iters):
        clusters = [[] for _ in range(k)]  # 存储每轮迭代后的簇
        
        # 将每个点分配至离它最近的那个质心所在的簇中
        for point in X:
            distances = [np.linalg.norm(point - centroid)**2 for centroid in centroids]
            cluster_idx = np.argmin(distances)
            clusters[cluster_idx].append(point)

        new_centroids = []
        
        # 更新质心的位置为对应簇内所有成员坐标的平均值
        for idx, cluster in enumerate(clusters):
            if not cluster: continue  # 如果某一轮某个簇为空，则跳过
            
            mean_point = sum(cluster)/len(cluster)
            new_centroids.append(mean_point.tolist())
            
        # 判断是否已经收敛
        if np.allclose(new_centroids, centroids): break
                
        centroids = new_centroids
    
    return centroids, clusters

对于其他类型的聚类算法如基于密度的方法DBSCAN，在面对具有不同密度区域的数据分布时可能会遇到困难，因为这类算法通常依赖于一致性的邻域半径参数设置来发现紧密相连的对象群组[^4]。