机器学习 K-means聚类算法

七月 30, 2020

机器学习

夜间观看请点

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.

while(not converged yet)
{
for(i = 1 to m)
 {
  distance = (Xi-U1)^2
  index = 1
  
  for(k = 1 to K)
      {
      temp = (Xi-Uk)^2
      
      if(temp < distance)
      {distance = temp
      index = k}
      
      } // gets the index of kernel U when distance (Xi-Uk)^2 reaches minimum
      
  Ci = k 
 }
 
 for(k = 1 to K)
   {
   Uk = sum(Xi)/n
   } 
 
 }//After each repeat, Ci = closet kernel's index, each Uk moves to new place

Cost Function：

该算法的Cost Function如下定义，变量为Ci和Uk ，计算的是m个点到聚类中心点距离的平均值，也就是说平均每个点到聚类中心点的距离，以此来衡量聚类效果的好坏。

for i = 1 to 100 //not necessarily 100, just a large number
{
randomly initialize Uk
Run K-means, Get Ci and Uk
Compute Cost Function J //also called distortion
Get min(J)
}

由于初始值的选择会影响最终聚类的结果，因此我们需要不断随机初始值，并最终获得一个最小的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曲线可能更像右图一些…

回到主页

加载评论