再免费多看一章--k-means++

在k-means算法里开始选取的聚类中点是随机的,每次都会照成不同的聚类结果。有一个解决方案叫做k-means++,可以有效的选择初始聚类中心点。参考 http://theory.stanford.edu/~sergei/papers/kMeansPP-soda.pdf

在《白话大数据与机器学习》里使用了sklearn里的KMeans来处理数据, 默认使用的就是k-means++: 训练模型 clf = KMeans(n_clusters=3, init=’k-means++’).fit(x, y)


这里我们来实现一下k-means++算法,看看该算法具体是如何实现的。

1 训练模型 使用kmeans++算法初始化聚类中点: 假设有一个数据集合X,里面有N条记录。

[x1, x2, x3, x4, x5, x6, ...]

第一次从X中随机取一条记录xi,当做聚类的第一个中心点。 然后重复以下步骤: 对每条记录,计算其与最近的一个中点之间的距离D(xn)并保存到一个数据组里,计算距离公式有很多,欧式距离,曼哈顿距离等。

D(x) = [D(x1), D(x2), D(x3), D(x4), D(x5), D(x6), ...]

对计算得到的距离加和

Sum(D(x))

然后再用D(x)里的各条记录分别除以距离加和值 D(xn)/Sum(D(x))

[D(x1)/Sum(D(x)),   
 D(x2)/Sum(D(x)),  
 D(x3)/Sum(D(x)),   
 D(x4)/Sum(D(x)),  
 D(x5)/Sum(D(x)),   
 D(x6)/Sum(D(x)),   ... ...]

得到下面这样的概率分布数组

[P(x1), 
 P(x2), 
 P(x3), 
 P(x4), 
 P(x5), 
 P(x6), 
 ...]

接着计算累加和

[P(x1),  
 P(x1) + P(x2),  
 P(x1) + P(x2) + P(x3),  
 P(x1) + P(x2) + P(x3) + P(x4),  
 P(x1) + P(x2) + P(x3) + P(x4) + P(x5),  
 P(x1) + P(x2) + P(x3) + P(x4) + P(x5) + P(x6),  
 ... ...]

从该数组中随机取一条记录,用它的下标在记录X中取值 当做下一个聚类中心点。

当聚类中心点初始完毕之后接下来就是使用k-means算法,聚拢各类: 计算所有点和各个中心点之间的距离,取离自己最近的中心点归为那个聚类。

{0: [x1, x2, x3],  
 1: [x4, x5, x6],  
 ......}

重新计算各个簇的中点,取各个特征列的均值,得到新的中心点。

[(x1 + x2 + x3) / 3, 
 (x4 + x5 + x6) / 3, 
 ...]

重复上述步骤 直到没有中心点移动。

完整代码可以访问https://github.com/azheng333/Ml_Algorithm.git进行下载。

原文发布于微信公众号 - 奇点(qddata)

原文发表时间:2016-08-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

深度学习框架之一:Theano | Lasagne简单教程

参考Lasagne官网(http://lasagne.readthedocs.io/en/latest/)tutorial进行总结而来。 01 简介 Lasag...

5025
来自专栏码云1024

编程英语之KNN算法

1304
来自专栏锦小年的博客

MNIST数据集的格式转换

以前直接用的是sklearn或者TensorFlow提供的mnist数据集,已经转换为矩阵形式的数据格式。但是sklearn体用的数据集合并不全,一共只有300...

4395
来自专栏闪电gogogo的专栏

tensorflow

3411
来自专栏FD的专栏

10种深度学习算法的TensorFlow实现

这个 repository 是使用 TensorFlow 库实现的多种深度学习算法的实现。这个软件包的目标是作为一种命令行实用程序——你可以将其用来快速训练和评...

1684
来自专栏数据结构与算法

P1032 字串变换

题目描述 已知有两个字串 A, B 及一组字串变换的规则(至多6个规则):      A1 -> B1      A2 -> B2 规则的含义为:在 A$中的子...

3396
来自专栏weixuqin 的专栏

深度学习之 TensorFlow(二):TensorFlow 基础知识

3845
来自专栏北京马哥教育

python实现拼写检查器21行轻松搞定

除了这段代码外,作为机器学习的一部分,肯定还应该有大量的样本数据,准备了big.txt作为我们的样本数据。

1654
来自专栏北京马哥教育

python实现拼写检查器21行轻松搞定

引入 大家在使用谷歌或者百度搜索时,输入搜索内容时,谷歌总是能提供非常好的拼写检查,比如你输入 speling,谷歌会马上返回 spelling。 下面是用...

3584
来自专栏深度学习那些事儿

Pytorch中Tensor与各种图像格式的相互转化

在pytorch中经常会遇到图像格式的转化,例如将PIL库读取出来的图片转化为Tensor,亦或者将Tensor转化为numpy格式的图片。而且使用不同图像处理...

4.5K6

扫码关注云+社区

领取腾讯云代金券