聚类

什么是聚类？

• 是把数据对象集合按照相似性划分成多个子集的过程。
• 每个子集是一个簇（cluster），使得簇中的对象彼此相似，但与其他簇中的对象不相似。

聚类是无监督学习：给定的数据没有类标号信息

数据挖掘对聚类的要求

1. 处理噪声数据的能力
   • 很多数据库都包含了孤立点，缺失或错误的数据
   • 而一些聚类算法对于这样的数据敏感，可能导致低质量的聚类结果
2. 对输入数据的顺序不敏感和增量聚类
   • 同一个数据集合，以不同的次序提交给同一个算法，应该产生相似的结果
   • 能将新加入的数据合并到已有聚类中
3. 高维度
   • 许多聚类算法擅长处理低维数据，可能只涉及两到三维
   • 而数据库或者数据仓库可能包含若干维或属性

划分方法：将有n 个对象的数据集D划分成k个簇，并且$k\le n$，满足如下的要求：

• 每个簇至少包含一个对象
• 每个对象属于且仅属于一个簇

基本思想

• 首先创建一个初始k划分(k为要构造的划分数)
• 然后不断迭代地计算各个簇的聚类中心并依新的聚类中心调整聚类情况，直至收敛

目标

• 同一个簇中的对象之间尽可能“接近”或相关
• 不同簇中的对象之间尽可能“远离”或不同

启发式方法 $E=\sum _{i=1}^n{\sum }_{p\in C_i}(d(c_i){)}^2$

• k-均值(k-means)

  • 每个簇用该簇中对象的均值来表示
  • 基于质心的技术

• k-中心点(k-medoids)

  • 每个簇用接近簇中心的一个对象来表示
  • 基于代表对象的技术

适用性

• 这些启发式算法适合发现中小规模数据库中的球状聚类
• 对于大规模数据库和处理任意形状的聚类，这些算法需要进一步扩展

K-means

• 优点
  • 聚类时间快
  • 当结果簇是密集的，而簇与簇之间区别明显时，效果较好
  • 相对可扩展和有效，能对大数据集进行高效划分
• 缺点
  • 用户必须事先指定聚类簇的个数
  • 常常终止于局部最优
  • 只适用于数值属性聚类(计算均值有意义)
  • 对噪声和异常数据也很敏感
  • 不同的初始值，结果可能不同
  • 不适合发现非凸面形状的簇

如何确定最优的聚类数K
肘部法是一种通过观察聚类误差（簇内平方和，SSE）的变化来选择 K值的方法。其原理是随着 K增加，聚类误差逐渐减少，但在某个K值之后，误差的减少速度会大幅放缓。此时，图形上会出现一个“肘部”，该点对应的K值通常被认为是最优聚类数


由于聚类算法是无监督学习，所以我们可能不知道原始数据到底是几类别，从而无法确定k的值。有一种方法——肘部法则，我们需要尝试一系列的k值，并绘制图像。 如上图，我们发现k=3处，曲线有弯曲且下降速度较快，称为肘部，之后下降缓慢。 此时取k=3较为合适。而对于右图，很多时候图像是平缓的，所以无法确定肘部，我们一般选择可行范围的最大值。

优点：简单直观，适合大多数情况。
缺点：对于某些数据集，肘部可能不明显，难以精确定位。

KNN VS K-means

K-Nearest Neighbors (KNN) 和 K-means 是两种在机器学习中常用的算法，但是大家经常将他们两个混淆，但它们的应用场景、工作原理和目标完全不同。下面介绍一下这两种算法的对比：

K-Nearest Neighbors (KNN)

类型: 监督学习（Supervised Learning）

用途: 主要用于分类问题，也可以用于回归问题。

工作原理:

• 在训练阶段，KNN 算法并不“学习”模型参数，而是存储训练数据集。
• 在预测阶段，对于一个新的输入实例，KNN 会在训练数据集中找到与该实例最相似的 K 个邻居（基于某种距离度量，如欧氏距离），然后根据这些邻居的多数类别来决定新实例的类别（对于分类任务）或者取平均值（对于回归任务）。

特点:

• 非参数化方法：不需要假设数据分布。
• 计算成本较高：尤其是在大型数据集上进行预测时。
• 对特征缩放敏感：因此通常需要标准化或归一化数据。

K-means

类型: 无监督学习（Unsupervised Learning）

用途: 用于聚类分析，即将数据点分组到不同的簇中，使得同一个簇内的成员比其他簇的成员更相似。

工作原理:

• 随机选择 K 个中心点（centroid）作为初始簇中心。
• 将每个数据点分配给最近的中心点，形成 K 个簇。
• 重新计算每个簇的中心点（通常是簇内所有点的均值）。
• 重复上述步骤，直到簇中心不再显著变化或达到最大迭代次数。

特点:

• 基于划分的方法：试图最小化簇内误差平方和。
• 对初始中心点的选择敏感：可能导致局部最优解。
• 不需要标签信息：因为是无监督学习算法。

总结

1. 监督 vs. 无监督: KNN 是一种监督学习算法，而 K-means 是一种无监督学习算法。
   目的不同: KNN 用于预测未知数据点的类别或数值，而 K-means 旨在发现数据中的自然分组。
2. 对数据的要求: KNN 可以直接应用于分类和回归任务，而 K-means 主要用于聚类分析，且它对数据的预处理（如缺失值处理、异常值检测等）要求更高，因为它依赖于数据点之间的距离度量。

K中心算法

首先为每个簇随意选择一个代表对象，剩余的对象根据其与代表对象的距离分配给最近的一个簇；然后，迭代地用非代表对象来替代代表对象，以改进聚类的质量（找更好的代表对象）；聚类结果的质量用一个代价函数来估算，该函数评估了对象与其参照对象之间的平均相异度。

PAM算法

PAM算法试图对n个对象给出K个划分，代表对象也被称为是中心点（Medoids），其他对象则被称为非代表对象。最初随机选择K个对象作为中心点，该算法反复地用非代表对象来代替代表对象，试图找出更好的中心点，以改进聚类的质量。

PAM算法关键步骤

1. 初始化：随机选择K个对象作为初始中心点。

2. 分配：将剩余对象分配给最近的中心点，形成K个簇。

3. 迭代优化：

   • 对于每个中心点，对于每个非中心点：
     • 交换中心点和非中心点，重新计算损失（损失值的大小为：所有点到中心点的距离和）。
     • 如果总的损失增加则不进行交换。

4. 结果输出：输出最终的K个簇中心和簇成员

K-modes算法——解决数据敏感的问题

• K-means的改进算法主要区别在于：
  • 初始k均值选择
  • 相异度计算
  • 计算均值方法
• 处理分类变量:K-modes
  • 针对分类数据
  • 用众数代替均值
  • 使用新的相异性度

KMeans++算法 ——解决初始点选择问题

基本原理：
① 从输入的数据点集合中随机选择一个点作为第一个聚类中心
② 对于数据集中的每一个点X，计算其与聚类中心的距离D（X）
③ 选择一个D（X）最大的点作为新的聚类中心
④ 重复2和3步直到K个聚类中心被选出
⑤ 利用K个初始聚类中心运行K-Means

K-中心点

• 选用簇中位置最中心的实际对象即中心点作为参照点
• 基于最小化所有对象与其参照点之间的相异度之和的原则来划分(使用绝对误差标准)

层次方法

• 层次方法
  • 对给定数据对象集进行层次的分解
  • 使用距离矩阵作为聚类标准
  • 不需要输入聚类数目k，但需要终止条件
• 两种层次方法
  • 自底向上方法（凝聚）
    • 初始将每个对象作为单独的一个簇，然后相继的合并相近的对象或簇，直到所有的簇合并为一个，或者达到一个终止条件
    • 代表算法：AGNES算法
  • 自顶向下方法（分裂）
    • 初始将所有的对象置于一个簇中，在迭代的每一步，一个簇被分裂为多个更小的簇，直到最终每个对象在一个单独的簇中，或达到一个终止条件
    • 代表算法：DIANA算法

AGNES算法——最小距离

单链接

• 其每个簇可以用簇中所有对象代表，簇间的相似度用属于不同簇中最近的数据点对之间的相似度来度量
• 也称为最短距离法，定义簇的邻近度为取自不同簇的两个最近的点之间的邻近度
• 设$d_{ij}$表示样本$X(i)$ 和$X(j)$之间的距离，$D_{ij}$表示类$G_i$和$G_j$之间距离

全链接

取自不同簇中的两个最远的点之间邻近度作为簇的邻近度

平均链接

• 类间所有样本点的平均距离
• 该法利用了所有样本的信息，被认为是较好的系统聚类法

聚类评估

• 估计在数据集上进行聚类的可行性和被聚类方法产生的结果的质量
• 聚类评估的任务
  • 估计聚类趋势：评估数据集是否存在非随机结构，如霍普金斯统计量
  • 确定数据集中的簇数：在聚类之前，估计簇数，如肘部（Elbow）方法
  • 测定聚类质量：聚类之后，评估结果簇的质量
    • 有监督：用某种聚类质量度量对聚类结果和基准进行比较
    • 无监督：通过考察簇的分离情况和簇的紧凑情况来评估聚类，如轮廓系数

K均值和K中心点的优缺点

1. k-均值

   • 优点:高效，k-均值算法复杂度为 O(tkn)，n是对象数目，k是聚类数目，t是迭代次数，一般的 k, t<< n;
   • 缺点:
     • 局部最优解;
     • 只适用于连续的固定的n维数据
     • 需要先确定聚类数目k;
     • 对噪音和离群点比较敏感:
     • 只适用于凸型数据聚类。

2. k-中心点：

   • 优点:
     • 可适用于范围可变的数据:
     • 能够处理对噪声或离群点
   • 缺点:
     • 局部最优解
     • 只适用于数据集较小的数据集，对较大的数据集不适用(计算的复杂性)算法复杂度为 O(k(n-k)2)。
     • 需要先确定聚类数目k;
     • 只适用于凸型数据聚类

层次化聚类的优缺点

• 优点:没有局部极小问题或是很难选择初始点的问题
• 缺点:计算存储的代价昂贵