机器学习 K-means聚类算法

机器学习 K-means聚类算法

七月 30, 2020

夜间观看请点

Machine Learning K-means Clutstering Part 1

K-means聚类是unsupervised learning->clustering问题当中的常见算法。

聚类即给一定组数据,将类似的数据进行分组, 组内成员的相似性根据算法而变化,一般取决于坐标,距离等。K-means聚类是通过单个点类内中心(kernel)的距离来进行分类。

image-20200730183733908

其基本思路如下:

首先确定集群的数量(即:我要把这些数据分成几类?)算法特点

以下图为例,假设需要初始化3个中心,则随机设置3个点(通常从数据当中选)

image-20200730184340107

每个点都计算并判断距离自己最近的中心点,从而每个点都被分类到了一个集群当中

例如离我最近的中心点是2号中心点,那么此时我被归类到2号集群当中

image-20200730184605350

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

image-20200730184800330

每个点再次计算距离自己最近的中心点,并重新聚类

可以看出,每个点所归属的类别是可能随着中心点发生改变而改变的。

重复【移动中心点】-> 【聚类】一直到中心点不再移动(收敛)数学证明收敛有必然性,此处略

image-20200730185629996

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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个点到聚类中心点距离的平均值,也就是说平均每个点到聚类中心点的距离,以此来衡量聚类效果的好坏。

image-20200730200626782

1
2
3
4
5
6
7
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(但这样就失去了聚类的意义)

image-20200730202029274

K值并不是越大越好,一方面K值过大会失去聚类的意义,另一方面K值增大也会增加计算量。因此需要选择一个恰当的K,如果J-K曲线当中存在一个明显的拐点(Elbow,因为像人的手臂),那么一半选择这个点的K值作为结果。但很多时候,J-K曲线可能更像右图一些…

回到主页