找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

机器学习-K-Means算法

admin 2019-10-10 09:25 89人围观 C++相关


概述

   

    K-Means是学习的第一个无监督算法,相对于需要人工标记的有监督学习,无监督算法在数据处理中的工作量会少很多。

    有一个很有趣的例子:

    从前有一群猴子,过着简单而快乐的生活。有一天,其中两只猴子因为小事争吵起来,最终一发不可收拾,两个猴子势不两立。从此这两只猴子开始拉帮结派,把觉得和自己合得来的猴子拉拢到一起,于是猴群分裂成了两拨。第一波猴子里面带头的猴子统治的很顺利,第二波猴子里面突然又有一只猴子崛起了,打败了原来的猴王,成了新的猴王,最终猴群的派系和管理层都稳定了下来,划分成了两拨猴子,完成了聚类,这就是个K-Means算法的案例。

    K-Means算法是最为经典的基于划分的聚类方法,他的中心思想是:以空间中K个点为中心进行聚类,通过迭代的方法,逐次更新聚类中心的值,直至得到最好的聚类结果。

    上述猴子拉帮结派的过程通过K-Means算法为:


  1. 首先,选择k个随机的点,作为聚类中心。

  2. 然后对于数据集中的每一个数据,按照距离k个聚类中心的距离,将其与距离最近的中心关联起来,与同一个中心点关联的所有点聚成一类。(簇分配)

  3. 计算每个类数据的平均值,将该类所关联的中心点移动到平均值的位置。(移动聚类中心)

  4. 重复步骤2-3直至中心点不再变化。


图形化详解

    假设我有如下图所示的无标签的数据集,并且想将其分为两个簇即k=2.



    1. 第一步随机生成两点(k=2),这两点被称为聚类中心。



    2. 遍历每个样本,然后根据样本到两个不同的聚类中心的距离哪个更近,来将每个数据点分配给两个聚类中心之一。



    3. 将聚类中心分别移动到各自簇的中心处。



    4. 重复2-3过程,直至聚类中心不再移动。



随机初始化和K的选择

    K-Means的一个问题在于他有可能会停留在一个局部最小值的位置,而这取决于初始化的情况,如下图:



    假如随机初始化K-means算法100 (一般是50-1000) 次之间,每次都使用不同的随机初始化方式,然后运行K-means算法,得到100种不同的聚类方式,都计算其损失函数,选取代价最小的聚类方式作为最终的聚类方式。

    这种方法在 K 较小的时候(2–10)还是可行的,但是如果 K 较大,这么做也可能不会有明显地改善。(不同初始化方式得到的结果趋于一致)

    其中,损失函数为每个样本到其所属簇的中心的距离和的平均值。



    上图中的c(i)为每个样本所属簇的编号,μk为每个簇中心的坐标,这两个都是在聚类过程中不断变化的变量,此代价函数也被称为畸变函数(Distortion function)

    对于图形化详解中的步骤2实际上就是优化上述的代价函数J,即在μk固定的条件下调整c(1),c(2)...c(n)的值以使损失函数的值最小。

    对于图形化详解中的步骤3实际上是在c(1),c(2)...c(n)固定的条件下调整μk的值以使损失函数的值最小。



    随机初始化遵循法则:


  1. 聚类中心点的个数要小于训练集数据的数量。

  2. 随机选择k个训练实例,然后令k个聚类中心分别于这k个训练实例相等。



    通常K-Means聚类是为下一步操作做准备,例如:市场分割,社交网络分析,网络集群优化 ,下一步的操作都能给你一些评价指标,那么决定聚类的数量更好的方式是:看哪个聚类数量能更好的应用于后续目的。

    肘部法则:

  • 改变聚类数K,然后进行聚类,计算损失函数,拐点处即为推荐的聚类数 (即通过此点后,聚类数的增大也不会对损失函数的下降带来很大的影响,所以会选择拐点)





  • 但是也有损失函数随着K的增大平缓下降的例子,此时通过肘部法则选择K的值就不是一个很有效的方法了(下图中的拐点不明显,k=3,4,5有类似的功能)。




Hello K-Means

    这里我们先用sklearn的make_blobs聚类数据生成器,make_blobs会根据用户指定的特征数量、中心点数量、范围等来生成几类数据,这些数据可用于测试聚类算法的效果。
    #scikit中的make_blobs方法常被用来生成聚类算法的测试数据.#直观地说,make_blobs会根据用户指定的特征数量、中心点数量、范围等来生成几类数据,这些数据可用于测试聚类算法的效果。from sklearn.datasets import make_blobsimport matplotlib.pyplot as pltfrom sklearn.cluster import KMeansif __name__ == '__main__': N = 400 centers = 4# n_samples是待生成的样本的总数。# n_features是每个样本的特征数。# centers表示类别数。# cluster_std表示每个类别的方差,例如我们希望生成2类数据,其中一类比另一类具有更大的方差,可以将cluster_std设置为[1.0,3.0]。    data, y = make_blobs(n_samples=N, n_features=2, centers=centers,cluster_std=[0.2,0.2,0.2,0.2]) plt.scatter(data[:, 0], data[:, 1], c="green") plt.show()


        接下来我们用K-Means开始聚类,分别选择簇的个数k为2,3,4,5

      from sklearn.cluster import KMeans#设置簇的个数为2yy = KMeans(n_clusters=2).fit_predict(data)#按照yy的值给图中数据上色。plt.scatter(data[:, 0], data[:, 1], c=yy)


        from sklearn.cluster import KMeans#设置簇的个数为3yy = KMeans(n_clusters=3).fit_predict(data)#按照yy的值给图中数据上色。plt.scatter(data[:, 0], data[:, 1], c=yy)


          from sklearn.cluster import KMeans#设置簇的个数为4yy = KMeans(n_clusters=4).fit_predict(data)#按照yy的值给图中数据上色。plt.scatter(data[:, 0], data[:, 1], c=yy)


            from sklearn.cluster import KMeans#设置簇的个数为5yy = KMeans(n_clusters=5).fit_predict(data)#按照yy的值给图中数据上色。plt.scatter(data[:, 0], data[:, 1], c=yy)




            ----------------------------------------------------------------------------------------------------------------------
            我们尊重原创,也注重分享,文章来源于微信公众号:小啦的学习笔记,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
            ----------------------------------------------------------------------------------------------------------------------

            鲜花

            握手

            雷人

            路过

            鸡蛋

            yafeilinux和他的朋友们微信公众号二维码

            微信公众号

            专注于Qt嵌入式Linux开发等。扫一扫立即关注。

            Qt开源社区官方QQ群二维码

            QQ交流群

            欢迎加入QQ群大家庭,一起讨论学习!

            我有话说......