跳至主要內容

kMeans

原创Xenny约 787 字大约 3 分钟机器学习机器学习无监督学习kMeans

kMeans

  • kMeans是一种无监督学习聚类算法,也就是给样本分簇。是一种适合用在数据分布未知时的聚类算法,聚类的目的是最大化簇的内聚性(同一簇距离近),最小化簇间的耦合性(不同簇距离远)。

    kMeans算法过程
    kMeans算法过程

工作流程

  1. 首先随机确定kk个初始点作为簇心;
  2. 查询数据集每个点距离最近的簇心点,分配到该簇中;
  3. 将簇心更新为该簇所有点的特征均值;
  4. 重复上述流程直到所有点都距离它对应簇心最近时结束(收敛)。

评价指标

  • 在线性回归中我们使用MSE来评价性能并以此为目标进行优化,在kMeans中使用**误差平方和SSE(Sum of Squared Error)**来进行评价

    SSE=minid(xi,c(xi)) \mathrm{SSE} = \min{\sum_i^{d(x_i, c(x_i))}}

    其中c(xi)c(x_i)代表第ii个对象xix_i所处的簇中心(特征均值),当然这里还涉及到距离的计算,在回归篇中已经介绍了多种距离算法,这里不再赘述。

和kNN的对比

  • 我们会发现kMeans也是使用距离度量对样本进行“抱团”。同时k的值也会严重影响算法的结果,因为选取不当很有可能只收敛到局部最优解。

    对于kMeans来说,其更适合“球形”数据,即每一簇都较为集中,在各个维度呈圆形分布在簇心周围。如果离群点较多的话,对kMeans的质心计算影响较大。

二分kMeans算法

  • 在介绍kMeans时提到其可能只收敛到局部最优解,此时我们可以合并最近的簇心或者合并两个使得SSE增幅最小的簇心,除此之外我们还可以使用一种新的kMeans算法:二分kMeans算法

    该算法按照如下规则操作:

    1. 将所有点看成一个簇;
    2. 当簇数目小于kk时,对每一个簇计算总误差,并单独对于该簇的样本选择参数k=2k=2进行kMeans聚类,得到两个子簇,再计算将该簇一分为二之后的总误差;
    3. 选择上述操作中误差最小的簇划分为子簇;
    4. 回到第二步,直到簇数目等于kk为止。

    另一种做法给定m>km>k个簇,选择SSE最大的簇进行划分,直到簇数目达到kk个为止。因为每次都会固定增加/减少一个簇,所以可以在指定次数内收敛到kk个簇。

    相比kMeans而言,在大规模数据集上效率更高,因为它不需要每次迭代重新计算所有样本点的距离,同时也弱化了初始簇心的选取对最终聚类效果的影响。不过它依然需要手动进行参数选择,也就是kk的值,同样也会由于kk的值过大/过小导致各类问题。