K-means算法小记
K-means算法是聚类算法。即给定一个数据集,利用K-means算法可将其分为K类。
算法思想:
- 随机从数据集中选取k个数据点作为k个分类的质心
- 遍历其余所有数据点,对每个数据点作这样的操作:计算数据点到每个质心的欧式距离,选取距离最小值的质心与其归为一类。这一步完成之后,得到的结果就是初始分类。
- 重新计算每个分类的质心。一般是按维度来计算均值。
- 对于重新得到的质心,运行第二步操作。
- 不断重复2,3直到收敛。
![K-means算法小记](https://img.it610.com/image/info10/b955420b627e4a74be5b8d36a9d37868.jpg)
文章图片
参数c是分类的标签,类别1,类别2,类别三3...,第二个参数是每一类的质心所在坐标。J所求就是每个样本到它的质心的距离平方和。K-means的优化利用的是EM思想。固定质心,改变样本标签c来减小j,固定标签c,改变质心来减小J。
用专业一些的话来说,E步估计隐含类别y的期望值,M步调整其他参数使得在给定类别c的情况下,极大似然估计P(x,c)最大。
极大似然的概念,我总忘,在这里记录一个博客地址:http://blog.csdn.net/zouxy09/article/details/8537620 当时看EM算法的时候看到的,通俗易懂。
在K-means里,这个极大似然估计是怎么样的。
在男生女生的例子中,我们的未知参数假设为在学校中男生比例为p,假如男生出现30次女生出现70次,那么也就是求p30×(1-p)70
的最大值。这是它的似然函数。我们只需要求导就能得到使得似然函数达到最大的p值。
那么在K-means中,那么这里的未知参数应该是c的坐标。然后求J的最小值,这是一种EM思想的一种体现。
K-means的主要应用,第一个想到的是对淘宝用户数据进行聚类,得出这个用户属于哪个分类,然后进行针对性的推荐?感觉这个只是聚类而已,不一定要用到K-means吧。略微搜了一下,没有搜到“K-means算法的应用场景”之类的相关文章,明天再说。
K-means的缺点:再补
K-means的python实现:http://blog.csdn.net/taoyanqi8932/article/details/53727841
参考了如下博客:
【K-means算法小记】http://blog.csdn.net/csqazwsxedc/article/details/52225759
推荐阅读
- 画解算法(1.|画解算法:1. 两数之和)
- 私通和背叛,他怎么看(——晨读小记)
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- 日更小小记
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器(Swift)
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列