第九章聚类算法

第九章聚类算法思维导图，聚类算法基本概念，聚类方法(K-均值算法、密度聚类、层次聚类)，聚类算法性能评估。

第九章 聚类算法

• 基本概念
  • 目标
    • 将数据集中的样本划分为若干个通常不相交的子集，即簇C
  • 意义
    • 用于寻找数据内部的分布特征
    • 作为分类等其他学习任务的数据预处理
    • 应对大数据的有效方式
  • 聚类类别
    • 描述尺度
      • 基于距离的聚类算法
        • 用各式各样的距离来衡量数据对象之间的相似度
      • 基于密度的聚类算法
        • 依据合适的密度函数
      • 基于互连性的聚类算法
        • 基于图或超图模型，高度连通的数据聚为一类
    • 主要思路
      • 划分法
        • 基于一定标准，构建数据的划分
      • 层次法
        • 对给定的数据对象集合进行层次划分
      • 密度法
        • 基于数据对象的相连密度评价
      • 网格法
        • 将数据空间划分为有限个单元的网格结构，基于网格结构进行聚类
      • 模型法
        • 给每个簇假定一个模型，然后去寻找能够很好的满足这个模型的数据集
• 聚类方法
  • 划分聚类算法
    • 定义
      • E值在一定程度上刻画了簇内样本围绕簇均值向量的紧密程度，E值越小，则簇内样本相似度越高
    • 算法框架
    • 实际应用
      • 最优性是一个NP难问题，通常利用贪心思想，依赖初始值
      • 算法较快停止，但在某些情况下复杂度高
      • K值选择可以基于Loss-k曲线
    • K-means++
      • 标准K-means的不足
        • 依赖初始值，计算复杂度过高
      • 实现
        • 初始化环节，添加seed节点迭代随机筛选
      • 效果
        • 极大降低时间复杂度，提高准确度
  • 密度聚类
    • 基本思想
      • 从样本密度的角度来考察样本之间的可连接性，基于可连接样本不断扩展聚类簇来获得最终的聚类结果
    • 应用场景
      • 聚类结构能通过样本分布的紧密程度来确定
    • DBSCAN算法
      • 基本思想
        • 基于一组邻域参数来刻画样本分布的紧密程度
      • 基本概念
      • 算法框架
  • 层次聚类
    • 基本思想
      • 在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集划分既可采用自底向上的聚合策略，也可采用自顶向下的分拆策略
    • 算法框架
      • 两个聚类簇的距离度量方式
        • Ward距离：
• 聚类算法评估
  • 有效性指标
    • 类内相似度高，类间相似度低
  • 性能度量
    • 外部指标
      • 定义
        • 将聚类结果与某个参考模型进行比较
      • 几种指数
        • Jaccard系数
        • Rand指数
    • 内部指标
      • 定义
        • 直接考察聚类结果而不用任何参考模型
      • 几种指数
        • DB指数
        • Dunn指数
• a+b+c+d=m(m+1)/2，a为TP，b为FP，c为FN，d为TN