Kmeans聚类算法评估足球比赛

一、实验介绍

1.1 内容介绍

K-means 算法采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为类簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。它是数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。K-means 算法以欧式距离作为相似度测度，它是求对应某一初始聚类中心向量V最优分类，使得评价指标最小。算法采用误差平方和准则函数作为聚类准则函数。本节课首先讲解Kmeans 算法思想，然后再用Kmeans 分析足球赛事。

1.2 实验知识点

• Scala 基础编程
• Spark Mlib 的 Kmeans 算法应用

1.3 实验环境

• Ubuntu14.04
• Spark2.1.1
• Xfce终端

1.4 适合人群

该项目难度一般，属于中等偏下难度，该项目适合有一定的 Spark 基础,对 MLib 有一定的了解，并热爱机器学习。

二、K-means 算法

2.1 问题引入

K-Means 算法主要解决的问题如下图所示。图中有一些散乱的点，用肉眼隐约可以看到大致有三个点集。但是我们怎么通过计算机程序找出这几个点群来呢？于是就出现了我们的 K-Means 算法(Wikipedia链接)。

我们希望根据这些不同的点的分布，分为几个簇，把这些点就近划分到不同的簇，这些簇就是接下来我们说的 K 值，下图是我用圆圈标上了这些点可能属于的簇集，更醒目一些，当然这里K值取值不是唯一的如图：

2.2 算法思想

通过不断的迭代来寻找 k 值，形成一种划分方式，使得用这k个类簇的均值来代表相应各类样本时所得的总体误差最小。同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。k-means 算法的基础是最小误差平方和准则，

其函数是：

上式中中，μc(i) 表示第i个聚类的均值。划分到各类簇内的样本越相似，其与该类均值间的误差平方越小，然后对所有类计算所得到的误差平方再次累加求和，即我们希望 J 值越小越好。

2.3 算法实现步骤

k-means 算法是将样本聚类成 k 个簇中心，这里的 k 值是我们给定的，也就是我们希望把数据分成几个类别，具体算法描述如下：

1) 为需要聚类的数据，随机选取 k 个聚类质心点

2) 求每个点到聚类质心点的距离，计算其应该属于的类，迭代直到收敛于某个值 {

对于每一个样例 i，：

​

对于每一个类 j，重新计算该类的质心，从而确定新的簇心，一直迭代到某个值或达到要求：

​

三、项目实现

接下来，我们进入实现阶段，进行实际操作给大家讲解相应的知识。

3.1 进入开发环境

进入到实验环境，双击桌面上的 Xfce，效果如下图

3.2 数据集介绍

实验中数据参考根据张洋的算法杂货铺，并做适当的修改。

序号    国别  2006年世界杯    2007年亚洲杯    2010年世界杯

1       韩国       17           3               15
2       沙特       28           2               40
3       卡塔尔     50           9               40
4       泰国       50           9               50 
5       越南       50           5               50
6       中国       50           9               50
7       巴林       40           9               40 
8       阿联酋     50           9               40 
9       伊朗       25           5               40 
10      日本       28           4               9

根据图片可以得知这 15 支球队在 2006 年~ 2010 年的比赛情况，其中包括两次世界杯和一次亚洲杯。图片中的数据做了如下预处理：对于亚洲杯，前四名取其排名，十六强赋予 9，八强赋予 5，预选赛没出现的赋予 17。对于世界杯，进入决赛圈则取其最终排名，没有进入决赛圈的，打入预选赛十强赛赋予 40，预选赛小组未出线的赋予 50。这样做方便我们接下来使用数据。

根据图片中的数据，我们可以把图片上的数据存储为 data.txt

首先，我们打开桌面上的 Xfce终端 ，切换到hadoop用户下：

su -l hadoop #密码为hadoop

使用 vi 命令创建 data.txt

sudo vi data.txt

添加如下内容，字段之间用空格分隔，并保存。

使用 more 命令显示内容。

more data.txt

3.3 启动 spark shell

请在终端中输入如下代码：

spark-shell

进入到 Spark 的 REPL 环境，相当于就是 Spark 的 Console。

3.4 导入数据并转换数据

下面我们就进入到实验的关键位置，进行数据的导入。

3.4.1 导入数据

拓展：Spark textFile 进行数据的导入，将外部数据导入到 Spark 中来，并将其转换成 RDD。

键入如下命令：

val dataset = sc.textFile("/home/hadoop/data.txt")

从图中我们可以看到我们引入了 /home/hadoop 下面的 data.txt 文件。在最后我们也了解到了当前的数据格式为 RDD[ String ] 类型的数据。

现在我们可以看看当前 dataset 的数据样式。我们查看 dataset 的前十五行数据。

拓展：这里使用到 RDD Action 操作，take(num)函数，take 的作用就是获取 RDD 中下标 0 到 num-1 的元素。foreach 遍历，并打印

键入命令：

dataset.take(10).foreach(println)

3.4.2 使用 import 命令导入依赖：

import org.apache.spark.mllib.linalg.Vectors
import org.apache.spark.mllib.clustering.KMeans

然后我们将这些数据以空格分割开，拆分数据，将其转换 Vector 格式。

val data = dataset.map  {
        l =>
            Vectors.dense(l.split(' ').map(_.toDouble))
    }

由于需要多次使用该数据，用 cache 进行缓存,用 collect 查看数据。

data.cache()
data.collect

结果如下图：

划分子集，及迭代次数，这里选择 3 次，迭代次数根据机器状况决定，这里选择 100 次。

val km = KMeans.train(data,3,100)

分别打印这三个子集的质心

km.clusterCenters.foreach { println }

3.4.3 打印数据及对应的子集

data.foreach {
     p =>
     println(p + " belongs to subset: " + km.predict(p))
        }

由质心，数据及对应的子集，知道 3 个子集的索引分别是 0、1、2，如果对数据排序， 应该是2、0、1。显然在子集[ 2 ]中有 2 个国家，分别是沙特，伊朗，这两个国家足球水平较好点，接着在子集[ 0 ]中也有两个国家，分别为韩国，日本，这两个国家足球水平一般，最后在在子集[ 1 ]剩下 8 个国家，其中包含中国[ 50, 50, 9 ]，说明中国足球有点差，不太理想，需要加油，至此实验就结束啦。

注意:本实验仅仅为了演示，实验结果不代表任何政治立场。

3.5 算法总结

K-Means 算法必须先确定K值，K 值的选定是非常难以估计的,在一定程度上影响结果。而 K-Means++ 算法给出了解决这个问题的方案，有兴趣的可以看一下。

本节课主要讲解了 K-Means，并基于算法进行一个简单案例讲解。

四、参考文档

• http://coolshell.cn/articles/7779.html
• https://en.wikipedia.org/wiki/K-means_clustering