前言

作为该系列的第一篇文章，也是我正式步入机器学习的第一篇学习日记，想说几句话，机器学习跟普通编程不一样，门槛对于大多数人来说都是算比较高的。曾经我也在惊叹和好奇中望而却步，现在在大佬的推动下也是鼓起勇气正式开始学习，完成这个系列也是我2019的目标。

由于公司用的是Spark，所以从Spark MLlib开始学起，不积硅步无以至千里，在这个系列我也会从简单一点地基础开始，一点点切实地去学习，希望看到这篇文章地小伙伴也能下定决心，一起攻克机器学习。

K-Means 聚类算法原理

K-Means算法流程

关于原理呢，我直接引用《使用Spark MLlib做K-mean聚类分析》里面的资料好了：

聚类分析是一个无监督学习 (Unsupervised Learning) 过程, 一般是用来对数据对象按照其特征属性进行分组，经常被应用在客户分群，欺诈检测，图像分析等领域。K-means 应该是最有名并且最经常使用的聚类算法了，其原理比较容易理解，并且聚类效果良好，有着广泛的使用。
和诸多机器学习算法一样，K-means 算法也是一个迭代式的算法，其主要步骤如下:

第一步，选择 K 个点作为初始聚类中心。

第二步，计算其余所有点到聚类中心的距离，并把每个点划分到离它最近的聚类中心所在的聚类中去。在这里，衡量距离一般有多个函数可以选择，最常用的是欧几里得距离 (Euclidean Distance), 也叫欧式距离,公式如下：

$$D(C,X) = \sqrt{\sum_{i=1}^n(c_i - x_i)^2}$$

其中 C 代表中心点，X 代表任意一个非中心点。

第三步，重新计算每个聚类中所有点的平均值，并将其作为新的聚类中心点。

最后，重复 (二)，(三) 步的过程，直至聚类中心不再发生改变，或者算法达到预定的迭代次数，又或聚类中心的改变小于预先设定的阀值。

光这么看有点不是很直观，其实就是不断换聚类中心以求达到“最合理”的分类的过程，下面我贴一张数据可视化的图，更直观地描述这个过程：
k-means过程可视化
如图，k-means算法在每一次迭代中，选择了更靠谱的红蓝中心点，试图让分类更合理，跟均匀。

欧式距离

欧几里得公式的含义还是比较简单的，但是一开始看还是有点懵，在这里我稍微提一下自己的理解，如果不对的话欢迎留言指正=。=首先我们先回顾一下那个公式，那个n代表的是什么呢？
$$D(C,X) = \sqrt{\sum_{i=1}^n(c_i - x_i)^2}$$
我们先来看看欧式距离在二维和三维中的展开：
欧式距离2维3维展开
是不是觉得很熟悉咧，就是求坐标之间的距离嘛，以此类推，在4维空间5维空间或者更高维度的空间中怎么算两点坐标距离呢？那就是原版的欧式距离公式啦！n在我看来，就是代表所求的维度数嘛，对应到实际应用中，这个“维度”对应的就是我们想要聚类的对象的参数（特征）。当n个参数可以确定一个唯一（或近似）的对象，我们通过欧式距离公式计算这个对象坐标的距离，把最后n维空间坐标相近的对象聚到同一个类别里，就完成了K-Means聚类算法要做的工作了。

聚类测试数据

在本文中，我们所用到目标数据集是来自UCI Machine Learning Repository的Wholesale customer Data Set。UCI是一个关于机器学习测试数据的下载中心站点，里面包含了适用于做聚类，分群，回归等各种机器学习问题的数据集。

Wholesale customer Data Set是引用某批发经销商的客户在各种类别产品上的年消费数。为了方便处理，本文把原始的CSV格式转化成了两个文本文件，取前面20行作为测试集，其余的数据作为训练集。如图：

代码样例

看注释就好了，基本就是处理好数据，然后调用spark-lib包里面的kmeans方法去做训练就ok了，源码分析大概会在做完这个系列之后再考虑要不要做。。。

值得注意的是：val clusters:KMeansModel = KMeans.train(parsedTrainingData, numClusters, numIterations,runTimes)这行代码，我来介绍一下这几个参数：

parsedTrainingData： 处理好的训练数据集
numClusters： 聚类的个数。这个值的选取有点学问，K的选择是K-means算法的关键，Spark MLlib在KMeansModel类里提供了computeCost方法，我的demo中也有该方法调用例子。该方法通过计算所有数据点到其最近的中心点的平方和来评估聚类的效果。一般来说，同样的迭代次数和算法跑的次数，这个值越小代表聚类的效果越好。但是在实际情况下，我们还要考虑到聚类结果的可解释性，不能一味的选择使computeCost结果值最小的那个K
numIterations： K-means算法的迭代次数
runTimes： K-means算法run的次数

完整代码如下：

/**
  * @author Chenyl
  * @date 2019/1/23 15:57
  */
import org.apache.spark.{SparkContext, SparkConf}
import org.apache.spark.mllib.clustering.{KMeans, KMeansModel}
import org.apache.spark.mllib.linalg.Vectors
object KMeansClustering {
  def main (args: Array[String]) {

    val trainingPath = "src/main/resources/Wholesale customers data_training.txt"  //训练数据集文件路径
    val testPath = "src/main/resources/Wholesale customers data_test.txt" //测试数据集文件路径

    val numClusters = 8  //聚类的个数
    val numIterations = 30  //K-means 算法的迭代次数
    val runTimes = 3   //K-means 算法 run 的次数

    val conf = new SparkConf().setAppName("Spark MLlib Exercise:K-Means Clustering")
    conf
      //TODO: 生成打包前，需注释掉此行
      .setMaster("local[*]")
      .set("spark.serializer", "org.apache.spark.serializer.KryoSerializer")

    val sc = new SparkContext(conf)
    sc.setLogLevel("ERROR")  //设置日志级别，info会有很多运行日志出现，也可以打开看看

    /**
      *Channel Region Fresh Milk Grocery Frozen Detergents_Paper Delicassen
      * 2 3 12669 9656 7561 214 2674 1338
      * 2 3 7057 9810 9568 1762 3293 1776
      * 2 3 6353 8808 7684 2405 3516 7844
      */
    val rawTrainingData = sc.textFile(trainingPath) //加载测试数据

    //去表头处理
    val parsedTrainingData = rawTrainingData.filter(!isColumnNameLine(_)).map(line => {
      Vectors.dense(line.split("\t").map(_.trim).filter(!"".equals(_)).map(_.toDouble))
    }).cache()

//    findK(parsedTrainingData)

    // Cluster the data into two classes using KMeans

    var clusterIndex:Int = 0
    //使用K-Means训练
    val clusters:KMeansModel = KMeans.train(parsedTrainingData, numClusters, numIterations,runTimes)

    println("Cluster Number:" + clusters.clusterCenters.length)
    println("Cluster Centers Information Overview:")
    clusters.clusterCenters.foreach(x => {
      println("Center Point of Cluster " + clusterIndex + ":")
      println(x)
      clusterIndex += 1
    })

    //begin to check which cluster each test data belongs to based on the clustering result
    val rawTestData = sc.textFile(testPath) //加载测试数据
    val parsedTestData = rawTestData.map(line =>{
      Vectors.dense(line.split("\t").map(_.trim).filter(!"".equals(_)).map(_.toDouble))
    })

    parsedTestData.collect().foreach(testDataLine => {
      val predictedClusterIndex: Int = clusters.predict(testDataLine) //使用训练好的模型进行分类
      println("The data " + testDataLine.toString + " belongs to cluster " +predictedClusterIndex)
    })
    println("Spark MLlib K-means clustering test finished.")



  }

  private def isColumnNameLine(line:String):Boolean = {
    if (line != null && line.contains("Channel")) true
    else false
  }

  /**
    * 查看最佳的K值
    * @param parsedTrainingData
    */
  private def findK(parsedTrainingData:org.apache.spark.rdd.RDD[org.apache.spark.mllib.linalg.Vector]): Unit ={
    val ks:Array[Int] = Array(3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)
    ks.foreach(cluster => {
      val model:KMeansModel = KMeans.train(parsedTrainingData, cluster,30,1)
      val ssd = model.computeCost(parsedTrainingData)
      println("sum of squared distances of points to their nearest center when k=" + cluster + " -> "+ ssd)
    })
  }
}

K-Means应用场景

适用场景

常用的场景是在不清楚用户有几类时，尝试性的将用户进行分类，并根据每类用户的不同特征，决定下步动作。一个典型的应用场景是CRM管理中的数据库营销。举例，对于一个超市/电商网站/综合零售商，可以根据用户的购买行为，将其分为“年轻白领”、“一家三口”、“家有一老”、”初得子女“等等类型，然后通过邮件、短信、推送通知等，向其发起不同的优惠活动。

明尼苏达州一家塔吉特门店被客户投诉，一位中年男子指控塔吉特将婴儿产品优惠券寄给他的女儿 —— 一个高中生。但没多久他却来电道歉，因为女儿经他逼问后坦承自己真的怀孕了。塔吉特百货就是靠着分析用户所有的购物数据，然后通过相关关系分析得出事情的真实状况。

在这个案例中，那个高中生少女明显是被聚到了孕妇那一类，因为她的行为模式与孕妇是很相近的。

总的来说，聚类算法大多用在用户画像、客户分群之类的，也可用于图像分析（色块相近聚集，后续会有一篇文章介绍kmeans在图像分析上的应用）
另外附上一篇《K-Means算法的10个有趣用例》,有兴趣的可以详细看看

不适用场景

每一种算法都不是放之四海而皆准的，下面是 K-Means 算法不适用的两个场景：

这种情况如果由人来聚类，分分钟搞定，但是 K-Means 算法是这样做的：

下面这种情况更微妙一些，各个子集的密集程度相差很大：

看看 K-Means 算法是怎样做的：

好吧，的确是差成渣了，但这真的不是算法的问题，而是我们人类对算法的选择问题。

结束语

k-means算法无论是原理还是代码MLlib的使用都是较为简单，但是在某些领域其效果却是出奇的好，作为入门机器学习的第一步，K-means也向我们掀开了机器学习世界神秘面纱的一角，给我们这些初学者极大的信心。

k-means只是机器学习中的一个算法工具，更多算法，将会在后续的日子中一一学习掌握，我也会即时把学习的一些心得写成系列文章，与君共勉。

Spark-MLlib学习日记1：K-means聚类分析

前言