聚类算法属于无监督学习:训练数据只有输入变量 x 而没有输出变量 y 。

无监督学习的目的是将这些训练数据潜在的结构或者分布找出来,以便于我们对这些数据有更多的了解。

1. KNN(K-Nearest Neighbor)

1.1 基本思想

  • 训练数据包括样本的特征向量(x)和标签(y);
  • k 是一个常数,由用户来定义;
  • 一个没有标签的样本进入算法后,首先找到与它距离最近的 k 个样本,然后用它这 k 个最近邻居的标签来确定它的标签。
  • 1.2 算法步骤

  • 算距离
    给定未知对象,计算它与训练集中的每个样本的距离——特征变量是连续的情况下,将欧氏距离作为距离度量;若特征是离散的,也可以用重叠度量或者其他指标作为距离,这要结合具体情况分析。
  • 找近邻
    找到与未知对象距离最近的 k 个训练样本。
  • 做分类/回归
    在这 k 个近邻中出现次数最多的类别作为未知对象的预测类别(多数表决法),或者是取 k 个近邻的目标值平均数,作为未知对象的预测结果。
  • 注: 超参数 —— k 的取值大小,直接影响着KNN 算法的结果。
    在这里插入图片描述
    当取 k=3 时,根据多数选举法,预测结果为 B;但当 k=6 时,依然是根据多数选举法,预测结果就成为了 A。

    k 是 KNN 算法唯一的超参数,因此,它对于 KNN 尤其重要。这一点和 KMeans 的 k 参数之于 KMeans,颇为神似。

    2. 聚类(Clustering)

    聚类技术,一句话概括:聚类就是通过对样本静态特征的分析,把相似的对象分到同一个子集,属于一种无监督式学习算法。

    所以这在本质上回到了不同样本之间的 相似性度量 (Similarity Measurement)。这时通常采用的方法就是计算样本间的 “距离” (distance)。

    可参考之前的文章: 距离度量和范数
    或者 机器学习中的相似性度量

    3. K-means

    3.1 本质和概要

    核心:把样本分配到离它最近的类中心所属的类,类中心由属于这个类的所有样本确定
    本质:K代表的是K类,means代表的是中心。 K-means的本质就是确定K类的中心点 ,当找到了这些中心点也就完成了聚类。

    K-means 是通过迭代的方式寻找K个簇(Cluster)的一种划分方案,使得聚类结果对应的代价函数最小。

    K-Means算法实施需要满足两个前提:

  • 根据分布的先验概率,求得K

  • 种子点的选取要cunning,尽量地远一点

  • 设置 K 个种子点;
  • 遍历每个点,将其归属为与之距离最近的种子点,这就是它所属的
  • 遍历结束后,重新计算 K 个种子点的位置( 簇中心点 );
  • 重复 Steps 2 and 3,直到 K个种子点的位置不再改变。
  • 3.2 损失/目标函数

    代价函数可以定义为各个样本距离所属簇中心点的误差平方和:
    在这里插入图片描述
    其中x i 代表第i个样本,c i 是x i 所属于的簇,μ ci 代表簇对应的中心点,M 是样本总数。

    3.3 优化算法:期望最大化(EM)

  • EM 算法
    期望最大化(expectation-maximization,E-M)是一种非常强大的算法,应用于数据科学的很多场景中。k-means 是该算法的一个非常简单并且易于理解的应用。

  • EM 步骤
    在这里插入图片描述

  • 4. 缺点

  • EM 可能不会达到全局最优结果
    解决:用不同的初始值尝试很多遍

    在 Scikit-Learn 中通过 n_init 参数(默认值是 10)设置执行次数。

  • 必须提前告诉算法簇的数量(K 值)

    解决:合理选择 K 值—— 手肘法

  •