机器学习 K-means聚类算法
Machine Learning K-means Clutstering Part 1
K-means聚类是unsupervised learning->clustering问题当中的常见算法。
聚类即给一定组数据,将类似的数据进行分组, 组内成员的相似性根据算法而变化,一般取决于坐标,距离等。K-means聚类是通过单个点类内中心(kernel)的距离来进行分类。

其基本思路如下:
首先确定集群的数量(即:我要把这些数据分成几类?)算法特点
以下图为例,假设需要初始化3个中心,则随机设置3个点(通常从数据当中选)

每个点都计算并判断距离自己最近的中心点,从而每个点都被分类到了一个集群当中
例如离我最近的中心点是2号中心点,那么此时我被归类到2号集群当中

计算每个集群的重心, 然后将中心点移动到重心处

每个点再次计算距离自己最近的中心点,并重新聚类
可以看出,每个点所归属的类别是可能随着中心点发生改变而改变的。
重复【移动中心点】-> 【聚类】一直到中心点不再移动(收敛)数学证明收敛有必然性,此处略

K-means的特性是聚类结果根据随机设置的中心点的位置而发生改变,即初始值会影响终态
另一个特性则是前面提到过的需要提前确定好将数据分成几类
具体算法:
模型假设:
假设一共有要分成K类
一共有m个数据$${x^1,x^2,x^3,x^4…x^m}$$每个数据为n维,即$$x^i \in \mathbb{R^n} $$
一共有K个中心点(分成K类)$$\mu_1,\mu_2,\mu_3…\mu_K$$这些中心点从数据中随机选择(randomly initialized)
Ci 定义为距离点 Xi 最近的中心点编号,例如:点 X2 距离中心点 U1 最近,那么 C2 =1.
1 | while(not converged yet) |
Cost Function:
该算法的Cost Function如下定义,变量为Ci和Uk ,计算的是m个点到聚类中心点距离的平均值,也就是说平均每个点到聚类中心点的距离,以此来衡量聚类效果的好坏。
1 | for i = 1 to 100 //not necessarily 100, just a large number |
由于初始值的选择会影响最终聚类的结果,因此我们需要不断随机初始值,并最终获得一个最小的J。
关于K值的选择:
根据需求,譬如服装厂商需要根据二维数据(身高体重),将用户尺码分为S,M,L三个尺寸(也可以更多),此时K = 3, 如果需要更加细分, 增加XS, XL之后, K = 5。
从Cost Function的定义当中可以看出,通常来说,在初值正常选择的情况下,分的类越多(K越大),那么Cost Function的值会越小, 当K = m时,J = 0(但这样就失去了聚类的意义)
K值并不是越大越好,一方面K值过大会失去聚类的意义,另一方面K值增大也会增加计算量。因此需要选择一个恰当的K,如果J-K曲线当中存在一个明显的拐点(Elbow,因为像人的手臂),那么一半选择这个点的K值作为结果。但很多时候,J-K曲线可能更像右图一些…