Zephon Blog
0%

数模-K-means

发表于 更新于 分类于
本文字数： 3.3k 阅读时长 ≈ 3 分钟

K-means

原理

聚类分析是在数据中发现数据对象之间的关系，将数据进行分组，组内相似性越大，组间的差别越大，则聚类效果越好。

K-means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。K-means算法是无监督的聚类算法，它实现起来比较简单，聚类效果也不错，因此应用很广泛。

如果用数据表达式表示，假设簇划分为(C1,C2,...,Ck),则我们的目标是最小化平方误差E：\(E=\sum_{i=1}^k\sum_{x\in C_i}||x-\mu_i||_2^2\) ，其中\(\mu_i\)是簇Ci的均值向量，有时也称为质心，表达式为：\(\mu_i=\frac{1}{|C_i|}\sum_{x\in C_i}x\) ，如果我们想直接求上式的最小值并不容易，这是一个NP难(没有直接能求的一个式子)的问题，因此只能采用启发式的迭代方法。

K-means采用的启发式：

选择K个点作为初始质心

repeat

将每个点指派到最近的质心，形成K个簇

重新计算每个簇的质心

until 簇不发生变化式达到最大迭代次数

使用方法和适用范围

K-means算法的要点

  1. 对于K-means算法，首先要注意的是k值的选择，一般来说，我们会根据对数据的先验经验选择一个合适的k值，如果没有什么先验知识，则可以通过交叉验证选择一个合适的k值
  2. 在确定了k的个数后，我们需要选择k个初始化的质心。由于我们是启发式方法，k个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的k个质心，最好这些质心不能太近。

K-means算法的步骤

输入是样本集\(D={x_1,x_2,...x_m}\),聚类的簇树k，最大迭代次数N

输出是簇划分\(C={C_1,C_2,...C_k}\)

  1. 从数据集D中随机选择k个样本作为初始的k个质心向量：\({\mu_1,\mu_2,...\mu_k}\)
  2. 对于n=1,2,...,N
    1. 将簇划分C初始化为\(C_i=\empty （t=1,2...k）\)
    2. 对于i=1,2,...m,计算样本\(x_i\)和各个质心向量\(\mu_j(j=1,2,...,k)\)的距离：\(d_{ij}=||x_i-\mu_j||_2^2\)，将\(x_i\)标记最小为\(d_{ij}\)所对应的类别\(\lambda_i\)。此时更新\(C_{\lambda_i}=C_{\lambda_i}\cup {\{ x_i\}}\)
    3. 对于 j=1,2,...,k，对\(C_j\)中所有的样本点重新计算新的质心\(\mu_j=\frac{1}{|C_j|}\sum_{x\in C_j}x\)
    4. 如果所有的k个质心向量都没有发生变化，则转到步骤3（外）
  3. 输出簇划分\(C={C_1,C_2,...C_k}\)

适用范围

主要是解决分类问题，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇，也就是分成K类。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

可以解决的问题有：

  1. 星系区分
  2. 区域分划
  3. 样本分类

...

MATLAB调用

K-means聚类算法采用的是将N×P的矩阵X划分成K个类，使得类内对象之间的距离最大，而类之间的距离最小。

使用方法 ：

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
27
28
Idx=kmeans(X,K)

[Idx,C]=kmeans(X,K)

[Idx,C,sumD]=kmeans(X,K)

% X:N*P的数据矩阵
% K:表示将X划分为几类，为整数
% Idx:N*1的向量，存储的是每个点的聚类标号
% C:K*P的矩阵，存储的是K个聚类质心位置
% sumD:1*K的和向量，存储的是类间所有点与该类质心之间距离之和
% D:N*N的矩阵，存储的是每个点与所有质心的距离
[Idx,C,sumD,D]=kmeans(X,K)

% Param1、Param2等，主要可以设置如下：
% 'Distance' (距离测度)
% 'sqEuclidean' 欧式距离(默认时采用此距离方式)
% 'cityblock' 绝对误差和，又称：L1
% 'cosine' 针对向量
% 'correlation' 针对有时序关系的值
% 'Hamming' 只针对二进制数据
% ’start' (初始质心为位置选择方法)
% 'sample' 从X中随机选取K个质心点
% 'uniform' 根据X的分布范围均匀的随机生成K个质心
% 'cluster' 初始聚类阶段随机选择10%的X的子样本(此方法初始使用'sample'方法)
% 'Replicates' (聚类重复次数) 整数
% 'emptyaction' (空簇处理方法):'drop'
[...]=kmeans(...,'Param1',Val1,'Param2',Val2,...)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
%% 
% test
clear;clc;
x=[1 1;1 2;2 1;2 2];
x=[x;x+10;x+20;x+30;x+40];
[Idx,C,sumD,D]=kmeans(x,5);
plot(x(find(Idx==1),1),x(find(Idx==1),2),'*');
hold on;
plot(x(find(Idx==2),1),x(find(Idx==2),2),'*');
hold on;
plot(x(find(Idx==3),1),x(find(Idx==3),2),'*');
hold on;
plot(x(find(Idx==4),1),x(find(Idx==4),2),'*');
hold on;
plot(x(find(Idx==5),1),x(find(Idx==5),2),'*');

评价和结果分析

  1. 通过调用MATLAB中的kmeans函数可以实现聚类过程，返回得到质心和各个数据点的类别
  2. 接下来要做的就是通过画图将结果呈现出来。我们可以将不同类别采用不同的颜色或形状将数据点区分开来。
  3. 可以较为直观的观察出分类的效果，区分明显则说明分类效果较好，否则调整参数重新聚类分析。

聚类的衡量指标

均一性(一个簇只包含一个类别的样本)

完整性(同类别样本被归类到相同簇中)

V-measure(均一性和完整性的加权平均)

ARI

AMI

轮廓系数

优点和改进方法

优点

  1. 是解决聚类问题的一种经典算法，简单、快速
  2. 对处理大数据集，该算法保持可伸缩性和高效性
  3. 当簇接近高斯分布时，它的效果较好

缺点

  1. 在簇的平均值可被定义的情况下才能使用,可能不适合某些应用
  2. 在K-means算法中,K是事先给定的,这个K值的选定是非常难以估计的.很多时候,事先并不知道给定的数据集应该分成多少类别最合适
  3. 在K-means算法中,首先需要根据初始聚类中心来确定一个初始划分,然后对初始划分进行优化.这个初始聚类中心的选择对聚类结果有较大的影响,一旦初始值选择的不好,可能无法得到有效的聚类结果.
  4. 该算法需要不断地进行样本分类调整,不断地计算调整后的新的聚类中心,因此当数据量非常大时,算法的时间开销非常大;
  5. 若簇中含有异常点,将导致均值偏离严重(即:对噪声和孤立点数据敏感)
  6. 不适用于发现非凸形状的簇或大小差别很大的簇

改进

  1. 很多时候,事先并不知道给定的数据集应该分成多少类别才最合适.通过类的自动合并和分裂,得到较为合理的类型数目K,例如ISODATA算法
  2. 针对上述3,可选用二分K-均值聚类;或多设置一些不同的初值,对比最后的运算结果,一值到结果趋于稳定结束
  3. 针对上述5,改成求点的中位数,这种聚类方式即K-Mediods聚类(K中值)