Machine Learning-聚类(Clustering)(一)-K均值算法

点击量:288

之前机器学习系列的所有文章讲得都是监督学习(supervised learning),今天我们来讲一讲无监督学习(unsupervised learning)。本文覆盖Coursera Machine Learning Week 8的内容,将会介绍一个无监督学习算法-K均值聚类算法(K-means Algorithm for clustering)

K-means Algorithm
无监督学习和监督学习最大的不同是他不需要对样本数据集打标签,而是只根据样本数据分析其内在规律而自动进行簇分类。直观意义上的理解:比如我们有这样一堆样本数据,他的分布如下图:
clustering_1
事先我们并没有对样本数据打标签以标识它属于哪个分类,通过聚类算法,我们希望这堆看上去很容易被分开的数据能够自动分类。那么具体怎么做呢?

对于K个分类的聚类算法而言,步骤如下:

  • 1).首先,我们先随机选取K个样本点,我们称之为“簇中心”(cluster centroids),如下图所示:
    clustering_2
  • 2).对每一个簇中心(1-K),我们找到所有离该中心最近的样本点,并且给它涂上不同的颜色,如下图所示:
    clustering_3
  • 3).更新簇中心的位置:对于每一个簇中心点,计算出所有属于该簇的样本点的平均距离,然后移动簇中心到该点。
    clustering_4
  • 4).重复步骤二和步骤三,不断调整簇中心的位置,直到位置不再变化(收敛)。具体过程如下:
    clustering_5
  • 5).最终收敛的形态:
    clustering_6
  • 根据上述描述,我们形式化地总结下K均值算法:
    输入:
    k_means_alogrithm_input_2

    算法:
    k_means_alogrithm

    Optimization Objective(优化目标)
    遇到优化问题我们总是得先找一个优化目标函数,然后不断降低该函数的值,最后得到最优解。那么K均值算法的目标函数是什么呢?

    我们先定义一组变量:

  • \(c^{\left ( i \right )}\) = index of cluster\(\left ( 1,2,…,k \right )\) to which example \(x^{\left ( i \right )}\) is currently assigned.
  • \(\mu _{k}\)= cluster centroid \(k\) (\(\mu _{k}\in \mathbb{R}^{n}\)).
  • \(\mu _{c^{\left ( i \right )}}\)=cluster centroid of cluster to which example \(x^{\left ( i \right )}\) has been assigned.
  • 于是我们定义目标函数:
    $$J(c^{\left ( 1 \right )},…,c^{\left ( m \right )},\mu _{1},…\mu _{k}) = \frac{1}{m} \sum_{i=1}^{m}\left \| x^{\left ( i \right )} – \mu _{c^{\left ( i \right )}} \right \|^{2}$$
    那么我们的优化目标就是求得该值的最小值:
    $$min _{c^{\left ( 1 \right )},…,c^{\left ( m \right )},\mu _{1},…\mu _{k}}J(c^{\left ( 1 \right )},…,c^{\left ( m \right )},\mu _{1},…\mu _{k})$$
    上面的各种变量公式看似复杂,其实就是一个目的:求得所有样本点到其所属簇的距离的平方和最小。

    Random Initialization(随机初始化)
    该算法的第一步是随机初始化K个簇中心点,具体地,我们可以随机选取K个样本作为簇中心点。此外,最后的分类结果跟初始簇中心点的选择有关系,所以我们可以多次随机以获得最小的目标函数。random_initialization

    如何选择簇的数量?(Choosing the Number of Clusters)
    在现实工作中,簇数K的选择往往是不确定的,但是我们可以通过一些辅助的方法来帮助我们做决定。这里介绍一种方法:“肘部法则(Elbow Method)”。具体地,画出代价J关于簇数K的函数图,如下图所示:
    elbow_method
    在左图中,我们很明显地看到了一个“肘点”,那么我们可以选择K=3。但是更多时候我们得到的可能是右边的函数图像,并不存在明显的肘点,所以这种方法也仅仅是辅助参考,并不能完全决定如何选取K的值。



    课后编程作业已经上传至本人GitHub,如有需要可以参考,但请遵守课堂准则,不要抄袭。

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注