5. 非监督学习

数据聚类；特征变量关联

5.1 K-means 聚类 ****

• 代价函数：样本距离所属簇中心 误差平方和

• 具体步骤

  • 预处理，e.g. 归一化，离群点处理（欧氏距离 / 非凸 -> 核函数）

  • 随机选取 K 个簇中心（elbow method, gap statistic）

  • 定义代价函数 $J(c,\mu)=\min_\mu\min_c\sum_{i=1}^M ||x_i-\mu_{c_i}||^2$

  • 迭代直至收敛：分配到最近 + 重新计算簇中心

• 优缺点

  • 缺点：初始点 和 离群点 影响，局部最优，无法解决分布差异较大，不适合离散分类

  • 优点：可伸缩 和 高效 $O(NKt)$

• 缺点改进

  • 缺点：预先确定 K，局部最优，噪声敏感，样本只能被划分到单一簇

  • K-means++：距离当前 n 个聚类中心越远的点，有更高可能被选为第 n+1 个聚类中心

  • ISODATA：迭代自组织数据分析法，K-means + 分裂 + 合并

    • 预期的聚类中心数目 $K_0$，每类最少样本数 $N_{min}$，最大方差 $\sigma$，聚类中心间最小距离 $D_{min}$

• 收敛性证明

  • 本质：EM算法（Expectation-Maximization algorithm）

  • 函数单调有界必收敛，但只保证收敛到 local optimum

5.2 GMM 高斯混合模型 **

• 同样使用 EM 算法迭代计算，GMM 理论上可以拟合任意类型分布

• $p(x)=\sum_{i=1}^K \pi_i N(x|\mu_i,\Sigma_i)$，是生成模型，需要提前指定 K 值

  • E-step：计算每个点由每个分模型生成的概率

  • M-step：改进每个分模型的 均值、方差、权重

• GMM 与 K-means

  • 相同：聚类，指定 K 值，EM 算法求解，局部最优

  • 优点：给出样本属于某类的概率，聚类 & 概率密度估计，可以生成新的样本点

5.3 SOM 自组织映射神经网络 ***

• 两层神经网络，竞争学习，输入层 和 输出层（竞争层）== 聚类个数，有拓扑关系

• 子过程：初始化，竞争，合作，适应，迭代

• 与 K-means 的区别：不需要指定 K，受噪声影响小 但 准确率低，可视化为拓扑关系图

• 超参数

  • 输出层神经元数量：样本类别数，或者尽可能多、再减少

  • 输出层节点的排列：实际需要，一维 / 二维

  • 初始化权值：从训练集中抽取 m 个输入样本作为初始权值

  • 设计拓扑领域：使得领域不断缩小

  • 设计学习率：学习率下降

5.4 聚类算法的评估 ***

• 常见的数据簇特点：中心（球形分布）、密度（稠密）、连通（图结构）、概念（共同性质）

• 聚类评估子任务

  • 估计聚类趋势（是否存在非随机的簇结构）

    • 随着 N 增加，聚类误差没有剧烈变化，则不存在非随机簇结构

    • 霍普金斯统计量（Hopkins Statistic）样本点最近距离 v.s. 随机生成点最近距离

  • 判定数据簇数：elbow method, gap statistic

  • 测定聚类质量

    • 轮廓系数 $s(p)=\frac{b(p)-a(p)}{\max\{a(p),b(p)\}}$

      • $a(p)$ 是簇内其他店平均距离，反映簇紧凑程度
      • $b(p)$ 是最小的其他簇平均距离，反映与其他簇分离程度
    • 均方根标准误差 $RMSSTD=\{\frac{\sum_i\sum_{x\in C_i}||x-c_i||^2}{P\sum_i(n_i-1)}\}^{\frac12}$，可以看作归一化的标准差
    • $R-squared=\frac{\sum_{x\in D} ||x-c||^2 - \sum_i\sum_{x\in C_i} ||x-c_i||^2}{\sum_{x\in D} ||x-c||^2}$，代表聚类后 平方误差和 的改进幅度
    • 改进的 Hubert $\Gamma$ 统计，通过数据对的不一致性来评估聚类的差异

      • $\Gamma=\frac{2}{n(n-1)}\sum_{x\in D}\sum_{y\in D}d(x,y)d_{x\in Ci, y\in C_j}(c_i,c_j)$
• 人工构造数据集

  • 聚类误差是否随 N 增加而单调变化

  • 聚类误差对实际聚类结果的影响

  • 邻近数据簇的聚类准确性

  • 密度较大差异的数据簇的聚类效果

  • 样本数量较大差异的数据簇的聚类效果