计算智能——K-means聚类算法学习_k-means clustering algorithm

计算智能——K-means聚类算法学习

定义

k均值聚类算法（k-means clustering algorithm）是一种迭代求解的聚类分析算法，其步骤是随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。

算法

1.在点阵中随机找k个类的中心点
2.算出点阵中的若干点与各中心点的距离，根据距离将点归类
3.归类后重新找合适的中心点，迭代若干次

注意： 1.避免随机在整个空间生成散点，尽量以某几个点为中心点在其附近随机生成点
2.可以有多个类

算法流程图

代码实现

clear
clc
%%输入数据
%首先输入数据，这里采用均值+方差*随机矩阵的方式构造初始点阵，避免点阵过于零散，然后判断数据中是否含有异常值
data1 = 0.05 + sqrt(0.01) * randn(20,2)
data2 = 0.6 + sqrt(0.01) * randn(15,2)
data3 = 0.9 + sqrt(0.01) * randn(10,2)
data = [data1;data2;data3]
figure(1)
plot(data(:,1),data(:,2),'*') 
%%判断数据中是否含有错误数据或非法字符
isNAN = any(isnan(data),2); 
 %any表示有非0元素时返回为1,any(A,2)表示矩阵的行向量进行判断
hadNAN=any(isNAN);          %表示数据中含有坏数据
if hadNAN
    disp('kmeans:MissingDataRemoved');
    disp(['missaddress is located ' num2str(find(isNAN==1))])
    data = data(~isNAN,:);
end
%%设置聚类类别k
k=3;
%配置K-means参数，包括聚类类别K、设置距离方式以及最大迭代次数和偏差等。
%%设置距离方式
%距离选择
%欧式距离：'euclidean'，标准欧式距离：'seuclidean'
%曼哈顿距离(城市区块距离)：'cityblock'
%闵可夫斯基距离：'minkowski'
%切比雪夫距离：'chebychev'
%夹角余弦距离：'cosine'
%相关距离：'correlation'
%汉明距离：'hamming'
distanceSize='euclidean'; 
%%设置最高迭代次数step和偏差
step=10;
maxdeviation=1e-5;

%开始kmeans聚类
[m,n]=size(data);         %数据个数为m个，维度为n维
center = zeros(k,n+1);    %聚类中心
center(:,n+1) =1:k ;      %生成聚类的类别
dataSize=zeros(m,1);      %生成数据类别
for j=1:k
    center(j,1:n)=data(randi([1,m]),:);  %随机产生k个中心
end
  for i=1:step
    %%第二步，分别计算各个点到中心的距离，并将离中心距离近的点归为一类
    %计算距离
    for j=1:k
        distance(:,j)=pdist2(data,center(j,1:n),distanceSize);
    end
    %取距离最小的点归为一类
    [~,temp]=min(distance,[],2);
    dataSize=temp;
    oldcenter=center;
    %%更新中心点
    for j=1:k
        center(j,1:n)=mean(data(dataSize==j,:));
    end
    deviation=sum(abs(center-oldcenter));  %残差
    if deviation<maxdeviation
        break;
    end
    %输出每一步迭代的结果
    figure(i+10)
    for i=1:k
        scatter(data(dataSize==i,1),data(dataSize==i,2));
    hold on
    end
    plot(center(:,1),center(:,2),'x','MarkerSize',10);
    hold off
    end
    %画出各个类别
figure(2)
for i=1:k
    scatter(data(dataSize==i,1),data(dataSize==i,2));
    hold on
end
plot(center(:,1),center(:,2),'x','MarkerSize',10);
hold off

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

运行结果

初始点阵：

聚类后：

k-means算法的优劣

K-means具有如下优点：
（1）算法简单，特别对于类球型分布的数据效果特别好。
（2）收敛速度快，往往只需要5~6步即可达到收敛。
（3）算法复杂度为O(t,k,n)。其中t为迭代次数，k为分类的个数，n为数据点的个数。
当然，K-means也有一些缺点。
（1）由于聚类算法为无监督学习，人们事先无法确定到底需要分多少个簇，也就是说k值无法提前确定。
（2）同很多算法一样，它可能会收敛到局部最优解。而这和初始点的选取有关，我们可以采用多次选取初始点，最后选择效果最好的结果。
（3）对噪声影响敏感。我们可以看出K-means中means表示平均值，而平均值往往对噪声敏感，一个离群点往往会对整个结果造成很大影响。
（4）不适合某些非球类数据分布。

参考

https://blog.csdn.net/u010936286/article/details/79995982