Spark数据挖掘-基于 K 均值聚类的网络流量异常检测(2): 模型优化

原创
2015/11/13 15:18
阅读数 1.9K

Spark数据挖掘-基于 K 均值聚类的网络流量异常检测(2): 模型优化

上一节:Spark数据挖掘-基于 K 均值聚类的网络流量异常检测(1): 数据探索模型初步实验

前言

通过上一节的介绍,已经对数据集长什么样子,模型如何工作的有了一个基本的了解,本节重点就是探讨如何优化 K-means 聚类模型。

1 K-means 聚类算法的 K 如何选择

首先探讨的第一个问题是 K-means 的类别 K 该如何确定?为了回答这个问题,需要先回答下面的问题:

  1. 如何量化模型的效果?

第一个想到的答案就是:当K确定下来之后,模型得到K个类中心,每个样本也归属到自己的类,那么每个样本距离类中心的距离也是知道的,将所有样本距离类中心的距离相加, 这个总距离数值越小越好(当然看总距离的平均值也是一样的,因为样本数量是相同的)。
这似乎很有道理,但是细细一想就发现,这个有点不靠谱,为什么?当你的类别数目等于样本数量的时候每一个样本都是类中心,那这个距离相加为0,是不是最小的?也就是说 这个总距离会随着类个数增加而减少。那这个K值如何取?
很简单,取总距离下降拐点处的 K 值。因为总距离随着 K 值的增加而减少但是减少的幅度不是每次都会很大,总会有一个K值之后,距离下降趋于平缓,这个点就是拐点。
这个思路其实和主成份分析找主成份的思路是一致的:也是找碎石图中的拐点。
下面将会以实战的方式,来具体求出这个最佳的 K 值,具体含义代码都有相应注释:

 /**
  * 欧几里德距离计算
  * zip 先将两个相同长度的向量按照对应的索引位置合为一个
  * 计算(a - b)的 平方和在求根
  * @param a 向量a
  * @param b 向量b
  * @return
  */
 def distance(a: Vector, b: Vector): Double = {
   val s = a.toArray.zip(b.toArray).map(p => p._1 - p._2)
   .map(d => d * d).sum
   Math.sqrt(s)
 }

 /**
  * 计算每一个数据点离类中心的距离
  * @param datum
  * @param model
  */
 def distToCentroid(datum: Vector, model: KMeansModel): Double = {
   val cluster = model.predict(datum)
   val centroid = model.clusterCenters(cluster)
   distance(datum, centroid)
 }
 /**
  * 重新指定聚类的个数重新聚类
  * @param data 训练样本
  * @param k 聚类类别个数
  */
 def clusteringScore(data: RDD[Vector], k: Int): Double = {
   val kmeans = new KMeans()
   kmeans.setK(k)
   val model = kmeans.run(data)
   //计算每一个点离中心点的距离
   data.map {
     datum =>
       distToCentroid(datum, model)
   }.mean()
 }

 //驱动代码:对不同K值计算总距离平均值
 (5 to 40 by 5).map(k => (k, clusteringScore(data, k))).sortBy(_._2).foreach(println)

上面的结果每次运行都有可能不一样,因为 K-means 算法是随机初始化类中心的,下面是某次运行的结果:

(5,1938.858341805931)
(10,1689.4950178959496)
(15,1381.315620528147)
(20,1318.256644582388)
(25,932.0599419255919)
(30,594.2334547238697)
(35,829.5361226176625)
(40,424.83023056838846)

从上面的结果中可以发现,随着 K 值的增加,总距离确实是在减少,但是 35 这个 K 值对应的距离却比 30 对应的距离大,这是为什么? 其实 K 均值聚类算法并不会尝试去找到全局最优,它还受到其他参数的影响,请看下面的分析。

2 参数选择

实际上 Spark 实现的是 K-means|| 初始质心选择算法。 K-means++ and K-means|| 都是尽可能选择 多样的分离的初始类中心的算法的变体,目的都是为了得到更加可靠的好的聚类结果。但是它们里面还是存在 随机的因素,导致得不到全局最优解,而在某个局部最优解就提前停止了计算。当然可以调整其他参数使得小狗狗更好, 下面分布介绍另外几个重要的参数:

  • setRuns 设置同一个 K 运行聚类算法的次数,取其中效果最好的一次(当然这个数值越大消耗资源也越大)
  • setEpsilon 这个是控制迭代停止条件的参数。当前后两次迭代的类中心小于这个值,算法认为类中心已经稳定,遂停止。减少这个值会增加迭代的次数。

下面重新调整参数,并且增加测试的次数,为了增加测试速度,每一个参数可以并行启动,而不是等另一个结束才启动, 这就是分布式上的分布式,下面直接给出代码:

 /**
  * 重新指定聚类的个数重新聚类
  * @param data 训练样本
  * @param k 聚类类别个数
  */
 def clusteringScore(data: RDD[Vector], k: Int): Double = {
   val kmeans = new KMeans()
   kmeans.setRuns(10)
   kmeans.setEpsilon(1.0e-6)
   kmeans.setK(k)
   val model = kmeans.run(data)
   data.map {
     datum =>
       distToCentroid(datum, model)
   }.mean()
 }
 //驱动代码
 (30 to 100 by 10).par.map(k => (k, clusteringScore(data, k)))
  .toList.sortBy(_._2).foreach(println)

3 参考资料

K-means 算法原理

个人微信公众号

欢迎关注本人微信公众号,会定时发送关于大数据、机器学习、Java、Linux 等技术的学习文章,而且是一个系列一个系列的发布,无任何广告,纯属个人兴趣。
Clebeg能量集结号

展开阅读全文
打赏
0
5 收藏
分享
加载中
更多评论
打赏
0 评论
5 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部