K-Means

$K-Means$ 是一个 无监督 的聚类算法

什么是聚类

俗话说"物以类聚，人以群分"，扯远了扯远了，这是考试复习

聚类算法 试图将相似对象归入同一簇，将不相似对象归到不同簇

是一种无监督学习( $unsupervised learning$ )，简单地说就是把相似的对象归到同一簇中。簇内的对象越相似，聚类的效果越好。

基本思想

~~个人觉得可以跳过，直接看算法步骤~~

在数据集中根据一定策略选择 $K$ 个点作为每个簇的 初始中心，然后观察剩余的数据，将数据划分到距离这 $K$ 个点最近的簇中，也就是说将数据划分成K个簇完成一次划分，但形成的新簇并不一定是最好的划分，因此生成的新簇中，重新计算每个簇的中心点，然后在重新进行划分，直到每次划分的结果保持不变。

在实际应用中往往经过很多次迭代仍然达不到每次划分结果保持不变，甚至因为数据的关系，根本就达不到这个终止条件，实际应用中往往采用变通的方法设置一个最大迭代次数，当达到最大迭代次数时，终止计算。

样本点间的距离（99%

详见 $KNN$ 中 “样本点间距离的选取”

欧氏距离（99%

$E(X, Y) = \sqrt{\sum^n_{i=1}(x_i - y_i)^2}$

算法步骤

选择初始化的 $k$ 个样本作为初始聚类中心 $a = a_1, a_2, \dots, a_k$ ；
针对数据集中每个样本 $x_i$ 计算它到 $k$ 个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中；
针对每个类别 $a_j$ ，重新计算它的聚类中心 $ a_ {j} $ = $ \frac {1}{|c_ {i}|} $ $ \sum _ {x\in c_ {i}} $ （即属于该类的所有样本的质心）；
重复上面 2 3 两步操作，直到达到某个中止条件（迭代次数、最小误差变化等）。

收敛证明（跳过吧

首先看一下 $K-Means$ 的目标函数（损失函数）

$J= \sum _ {i=1}^ {c} \sum _ {i=1}^ {N} r_ {ij} \cdot \nu ( x_ {j} , \mu _ {i} )$

其中：

$\nu\left(x_{j}, \mu_{i}\right)=\left\|x_{j}-\mu_{i}\right\|^{2}, \quad r_{n k}=\left\{\begin{array}{ll} 1 & \text { if } x_{n} \in k \\ 0 & \text { else } \end{array}\right.$

为了求极值，我们令损失函数求偏导数且等于 0：

$\frac{\partial J}{\partial \mu_{k}}=2 \sum_{i=1}^{N} r_{i k}\left(x_{i}-\mu_{k}\right)=0$

$k$ 是指第 $k$ 个中心点，于是我们有：

$\mu_{k}=\frac{\sum_{i=1}^{N} r_{i k} x_{i}}{\sum_{i=1}^{N} r_{i k}}$

可以看出，新的中心点就是所有该类的质心。

算法的缺点就是，容易陷入局部极小值，这也是 $K-Means$ 有时会得到局部最优解的原因。

代码实现、手搭（99%

计算训练集到质心的欧氏距离

def calcDis(dataSet, centroids, k):
    """计算训练集到质心的欧拉距离

    Args:
        dataSet (array): 训练集
        centroids (array): 质心
        k (int): 质心个数

    Returns:
        array: 训练集到各个质心的距离
    """    
    clalist=[]
    for data in dataSet:
        diff = np.tile(data, (k, 1)) - centroids  #相减   (np.tile(a,(2,1))就是把a先沿x轴复制1倍，即没有复制，仍然是 [0,1,2]。 再把结果沿y方向复制2倍得到array([[0,1,2],[0,1,2]]))
        squaredDiff = diff ** 2     #平方
        squaredDist = np.sum(squaredDiff, axis=1)   #和  (axis=1表示行)
        distance = squaredDist ** 0.5  #开根号
        clalist.append(distance) 
    clalist = np.array(clalist)  #返回一个每个点到质点的距离len(dateSet)*k的数组
    return clalist

更新质心

def classify(dataSet, centroids, k):
    """更新k个质心

    Args:
        dataSet (array): 训练集
        centroids (array): 初始质心
        k (int): 质心个数

    Returns:
        array, array: 质心变化量，新质心
    """    
    # 计算样本到质心的距离
    clalist = calcDis(dataSet, centroids, k)
    # 分组并计算新的质心
    minDistIndices = np.argmin(clalist, axis=1)    #axis=1 表示求出每行的最小值的下标
    newCentroids = pd.DataFrame(dataSet).groupby(minDistIndices).mean() #DataFrate(dataSet)对DataSet分组，groupby(min)按照min进行统计分类，mean()对分类结果求均值
    newCentroids = newCentroids.values
    # 计算变化量
    changed = newCentroids - centroids
    return changed, newCentroids

使用 $K-Means$ 进行迭代计算

def kmeans(dataSet, k):
    """使用k-means进行分类

    Args:
        dataSet (array): 训练集
        k (int): 质心个数

    Returns:
        array, array: 质心， 分类结果
    """    
    # 随机取质心
    centroids = random.sample(dataSet, k)
    # 更新质心 直到变化量全为0
    changed, newCentroids = classify(dataSet, centroids, k)
    while np.any(changed != 0):
        changed, newCentroids = classify(dataSet, newCentroids, k)
    centroids = sorted(newCentroids.tolist())   #tolist()将矩阵转换成列表 sorted()排序
    # 根据质心计算每个集群
    cluster = []
    clalist = calcDis(dataSet, centroids, k) #调用欧拉距离
    minDistIndices = np.argmin(clalist, axis=1)  
    for i in range(k):
        cluster.append([])
    for i, j in enumerate(minDistIndices):   #enumerate()可同时遍历索引和遍历元素
        cluster[j].append(dataSet[i])
    return centroids, cluster