聚类算法

  • 完美聚类算法的三大特点

      1. 同比例缩放数据，聚类结果不变
      1. 同组距离变小，组间距离变大，聚类结果不变
      1. 需要灵活包括所有聚类的可能性
    • 但是没有一种算法可以同时满足以上三点

  • 距离问题

    • 有序属性

      • 闵可夫斯基距离 distmk⁡(xi,xj)=(Σ∣xiu−xju∣p)1p\operatorname{dist_{mk}}(x_i,x_j) = (\Sigma|x_{iu} - x_{ju}|^p)^{\frac{1}{p}}

        • p=1p = 1 是曼哈顿距离
        • p=2p=2 是欧几里得距离

    • 无序属性

      • VDMp(a,b)=Σi∣mu,a,imu,a−mu,b,imu,b∣VDM_p (a,b) = \Sigma_i|\frac{m_{u,a,i}}{m_{u,a}} - \frac{m_{u,b,i}}{m_{u,b}}|

        • mu,am_{u,a} 表示属性 u 上取值为 a 的样本数
        • i 表示样本簇（或者叫聚类）的编号
        • 整个公式计算了属性u的a类和b类距离

    • 混合属性

      • MinkovDM⁡p(xi,xj)=(Σ∣xiu−xju∣p+ΣVDM⁡p(xiu,xju))1p\operatorname{MinkovDM}_p(x_i,x_j) = (\Sigma|x_{iu} - x_{ju}|^p + \Sigma \operatorname{VDM}_p(x_{iu},x_{ju}))^{\frac 1 p}

  • K 均值算法 K Means

    • 通过事先设置类的个数 (K 值) 然后设置类别中心，通过到最近点的方差向小迭代得到较好结果

    • 不符合第三点对“灵活”的要求（要提前设置 K 的值）

    • 确定 K 的值：肘方法 elbow method

      • 一般增大 k 的值最优方差值会先锐减后缓慢变化
      • 我们只要找到肘关节的位置 (图中的 4) 就可以确定了

  • DBSCAN 算法 (密度聚类算法)

    • 对应问题：点呈现环状特征
    • 参数 ϵ\epsilon 和 minimum points，即从某点出发半径为 ϵ\epsilon 的圆的范围内，当数据点的数量大于等于minimum points 的时候就能构成一个聚类集合。然后平移这个圆我们可以纳入新的点集，得到完整的集合
    • 无法参与聚类的点称为噪声
    • 由于有明确 ϵ\epsilon 的半径限制，不满足完美聚类算法的第一条限制

  • Mean Shift 算法

    • 先随便定义一个点集，然后向各个方向平移看点的数量是否增大，如果增大则说明接近质心了，通过迭代我们可以找到最接近质心的位置形成一个质心圆
    • 不需要提供 K 的值，也就是类别数量，模型会自动计算
    • 数据量大的时候不适合

  • AGNES 算法

    • 自下而上的算法，能保证最近的两点归于同一组
    • 通过设置一个聚类的距离临界值，大于临界值就不算一类