K均值（KMeans）

概念

• 无监督
• 相似数据分组
• 要得到簇的个数，需要指定簇的个数k
• 质心：数据集的质心，即数据集的均值C
• 距离：欧式距离、余弦相似度 (先数据标准化)
• 优化目标$\min \sum_{i=1}^{k} \sum_{x∈C_i} ||x - c_i||^2$
• 优点：
  • 简单直观：原理易于理解，实现流程清晰
  • 高效实用：适合常规数据集（如明显可分的数据分布）
  • 参数简单：只需确定k值即可开始聚类
• 缺点：
  • k值敏感：最优k值难以确定
  • 计算复杂度：与样本量呈线性关系（每次迭代需计算所有样本点到质心距离）
  • 形状限制：仅能发现凸形簇（环绕状、交叉、缠绕等复杂簇结构效果差）
  • 受初始点影响大，多次选择初始点取均值

原理

1. 随机选择k个样本点作为初始质心C1,C2,C3,...,Ck
2. 计算每个样本点到质心的距离，将样本点分配给距离最近的质心所属的簇
3. 更新质心的位置：将簇内所有样本点的均值作为新的质心位置
4. 重复步骤2和步骤3，直到质心的位置不再变化或者达到最大迭代次数为止

参数

• 初始中心点的选取
  • K-means++：初始聚类中心距离尽可能远
  • 二分K-means：选择误差最大的聚类，进行二分分裂
• 空簇处理
  • 其他簇心的均值
  • 删除该簇
  • 最远离聚类中心的点
• 特征工程
  • 类别特征不适用K-means：无法基于距离
  • 大数值特征不适用K-means：该算法对于异常值敏感，比如年龄、金额

评估

把 SSE（Sum of Squared Errors，误差平方和） 与轮廓系数（Silhouette Coefficient）结合使用，评估聚类模型的效果

实现

import numpy as np
from matplotlib import pyplot


class K_Means(object):
    # k是分组数；tolerance‘中心点误差’；max_iter是迭代次数
    def __init__(self, k=2, tolerance=0.0001, max_iter=300):
        self.k_ = k
        self.tolerance_ = tolerance
        self.max_iter_ = max_iter

    def fit(self, data):
        self.centers_ = {}
        for i in range(self.k_):
            self.centers_[i] = data[i]

        for i in range(self.max_iter_):
            self.clf_ = {}
            for i in range(self.k_):
                self.clf_[i] = []
            # print("质点:",self.centers_)
            for feature in data:
                # distances = [np.linalg.norm(feature-self.centers[center]) for center in self.centers]
                distances = []
                for center in self.centers_:
                    # 欧拉距离
                    # np.sqrt(np.sum((features-self.centers_[center])**2))
                    distances.append(np.linalg.norm(feature - self.centers_[center]))
                classification = distances.index(min(distances))
                self.clf_[classification].append(feature)

            # print("分组情况:",self.clf_)
            prev_centers = dict(self.centers_)
            for c in self.clf_:
                self.centers_[c] = np.average(self.clf_[c], axis=0)

            # '中心点'是否在误差范围
            optimized = True
            for center in self.centers_:
                org_centers = prev_centers[center]
                cur_centers = self.centers_[center]
                if np.sum((cur_centers - org_centers) / org_centers * 100.0) > self.tolerance_:
                    optimized = False
            if optimized:
                break

    def predict(self, p_data):
        distances = [np.linalg.norm(p_data - self.centers_[center]) for center in self.centers_]
        index = distances.index(min(distances))
        return index


if __name__ == '__main__':
    x = np.array([[1, 2], [1.5, 1.8], [5, 8], [8, 8], [1, 0.6], [9, 11]])
    k_means = K_Means(k=2)
    k_means.fit(x)
    print(k_means.centers_)
    for center in k_means.centers_:
        pyplot.scatter(k_means.centers_[center][0], k_means.centers_[center][1], marker='*', s=150)

    for cat in k_means.clf_:
        for point in k_means.clf_[cat]:
            pyplot.scatter(point[0], point[1], c=('r' if cat == 0 else 'b'))

    predict = [[2, 1], [6, 9]]
    for feature in predict:
        cat = k_means.predict(feature)
        pyplot.scatter(feature[0], feature[1], c=('r' if cat == 0 else 'b'), marker='x')

    pyplot.show()

改进

缺点	改进
k值不好选取	ISODATA
对初始聚类中心敏感	k-means++
对于非凸数据集难收敛	DBSCAN
数据类型不平衡，效果不佳	CUSBoost
迭代得到的是局部最优解	二分k-means
对噪音、异常点敏感	K-Mediods