迭代自组织分析聚类(ISODATA)

发表于 | 分类于 ， | | 本文总阅读数 次
| 字数统计: 2k | 阅读时长 ≈ 8
ISODATA

迭代自组织分析聚类方法

原理解读

  ISODATA(Iterative Selforganizing Data Analysis) :在k-均值算法的基础上，增加对聚类结果的合并和分裂两个操作，当聚类结果某一类中样本数太少，或两个类间的距离太近，或样本类别远大于设定类别数时，进行合并，当聚类结果某一类中样本数太多，或某个类内方差太大，或样本类别远小于设定类别数时，进行分裂。

核心思想

  1. 初始常量(c0,n0,dmin,dmax,T)
    c0：希望得到的聚类数
    n0：每类的样本数
    dmin：最小类间距离
    dmax：最大类内距离
    T：最大迭代次数

  2. 最小类间距离
$$d_{min}=\underset{C_i,C_j \subseteq C}{min}{d( \overline {C_i},\overline {C_j} )} \ , \ 其中\overline {C_i}=\frac {1}{\lvert C_i \rvert}\underset{x_i \in C_i}{\sum}{x_i}$$

  3. 最大类内距离
$$d_{max}=\underset{C_i \subseteq C}{max} \ \frac {1}{\lvert {C_i} \rvert}\underset{x_i \in C_i}{\sum}{d( x_i,\overline C_i )} \ , \ 其中\overline {C_i}=\frac {1}{\lvert C_i \rvert}\underset{x_i \in C_i}{\sum}{x_i}$$

初始时刻状态
第一次迭代后
第二次迭代后
第三次迭代后
第四次迭代后
第五次迭代后

  4. 判断是否达到分裂条件

  • 当前类别数是否小于希望得到聚类数的一半
  • 当前每一类的数目是否大于每类样本数的二倍
  • 当前类内距离是否大于最大类内距离

  5. 分裂不满足条件的类别，回到步骤2，直到满足某个终止条件

  6. 判断是否达到合并条件

  • 当前类别数是否大于希望得到聚类数的二倍
  • 当前每一类的数目是否小于每类样本数的一半
  • 当前类间距离是否小于最小类间距离

  7. 合并不满足条件的类别，回到步骤2，直到满足某个终止条件

算法流程

ISODATA



代码实战

代码中所用数据集可以查看相关文档，数据集(Data Set)

ISODATA_main.m

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
clear;clc;close all;
load('..\\cluster_gauss.mat');
%输入x的矩阵
x=data;
randIndex = randperm(size(x,2));
x=x(:,randIndex);
%希望划分的类别数
hope_class_num=3;
%希望每一类的数目
hope_num=20;
%设定类内的最大距离,小一点
max_class_inner_distance=0.1;
%设定类间的最小距离,小一点
min_class_between_distance=0.1;
%最多迭代次数
times=100;
%样本数
sample_num=size(x,2);
%特征数目
feat_num=size(x,1);
%尺度缩放到0-1
x_scale=zeros(size(x));
for i=1:feat_num
    x_scale(i,:)=(x(i,:)-min(x(i,:)))/(max(x(i,:))-min(x(i,:)));
end
[y,class_num,class_center]=ISODATA_classify(x_scale,sample_num,hope_class_num,hope_num,max_class_inner_distance,min_class_between_distance,times);
%样本中心尺度复原
for i=1:feat_num
    class_center(i,:)=(max(x(i,:))-min(x(i,:)))*class_center(i,:)+min(x(i,:));
end
%如果数据的特征是二维的，可以绘图表示
if feat_num==2
    ISODATA_display(x,y,class_center,sample_num,class_num);
else
    disp('The Feature Is Not Two-Dimensional');
end

ISODATA_classify.m

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
function [y,class_num,class_center]=ISODATA_classify(x_scale,sample_num,hope_class_num,hope_num,max_class_inner_distance,min_class_between_distance,times)
%给每一个样本都视为0类
y=zeros(1,sample_num);
%将前class_num个样本分为class_num类
y(1:hope_class_num)=1:hope_class_num;
%目前的类别数
class_num=hope_class_num;
k=0;
while 1
    class_center=zeros(2,class_num);
    for i=1:class_num
        %更新类别的中心
        class_center(:,i)=sum(x_scale(:,y==i),2)/sum(y==i);
    end
    %采用最近邻进行分类
    for i=1:sample_num
        distance=sum((class_center-repmat(x_scale(:,i),1,class_num)).^2);
        y(i)=find(distance==min(distance),1);
    end
    for i=1:class_num
        %更新类别的中心
        class_center(:,i)=sum(x_scale(:,y==i),2)/sum(y==i);
    end
    %如果迭代次数大于times，则停止迭代
    if k>=times
        break;
    end
    each_class_num=zeros(1,class_num);
    distance_between_class=zeros(class_num);
    %统计每一类的个数,并求出类间距离
    for i=1:class_num
        each_class_num(i)=sum(y==i);
        distance_between_class(i,:)=sum((class_center-repmat(class_center(:,i),1,class_num)).^2);
        distance_between_class(i,i)=inf;
    end
    %统计类内距离
    distance_class_inner=zeros(1,class_num);
    for i=1:class_num
        temp=x_scale(:,y==i);
        distance_class_inner(i)=sum(sum((temp-repmat(class_center(:,i),1,sum(y==i))).^2))/sum(y==i);
    end
    %如果类内距离最大的一类的类内距离大于设定值，则分裂两类
    if max(distance_class_inner)>max_class_inner_distance
        tem=find(distance_class_inner==max(distance_class_inner),1);
        %temp为该类别的样本
        temp=x_scale(:,y==tem);
        %distance(i,j)指第i个样本到第j个样本的距离
        distance=zeros(size(temp));
        for i=1:sum(y==tem)
            distance(i,:)=sum((temp-repmat(temp(:,i),1,sum(y==tem))).^2);
        end
        %找到距离最远的两个样本
        [row,col]=find(distance==max(max(distance)),1);
        %分别找到这个两个样本的所在位置
        temp=find(y==tem);
        row=temp(row);
        col=temp(col);
        %类别数+1
        class_num=class_num+1;
        %令该类别撤销
        y(y==tem)=0;
        %添加两个新类别，一个覆盖原类别，另一个类别为原类别数+1
        y(row)=tem;
        y(col)=class_num;
        k=k+1;
        continue;
    end
    %如果两类之间的最小距离小于设定阈值，则合并两类
    if min(min(distance_between_class))<min_class_between_distance
        %找到距离最近的两个类别
        [row,col]=find(distance_between_class==min(min(distance_between_class)),1);
        %类别数-1
        class_num=class_num-1;
        %将col类合并到row类中
        y(y==col)=row;
        %调整类别序号
        y(y>col)=y(y>col)-1;
        k=k+1;
        continue;
    end
    %如果某一类的最小数量小于等于希望数量的一半
    if min(each_class_num)<=hope_num/2
        %找到该类别
        tem=find(each_class_num==min(each_class_num),1);
        %令该类别撤销
        y(y==tem)=0;
        %重新调整类别序号
        y(y>tem)=y(y>tem)-1;
        %类别数-1
        class_num=class_num-1;
        continue;
    end
    %如果某一类的最小数量大于等于希望数量的2倍
    if max(each_class_num)>=hope_num*2
        %找到该类别
        tem=find(each_class_num==max(each_class_num),1);
        %temp为该类别的样本
        temp=x_scale(:,y==tem);
        %distance(i,j)指第i个样本到第j个样本的距离
        distance=zeros(size(temp));
        for i=1:sum(y==tem)
            distance(i,:)=sum((temp-repmat(temp(:,i),1,sum(y==tem))).^2);
        end
        %找到距离最远的两个样本
        [row,col]=find(distance==max(max(distance)),1);
        %分别找到这个两个样本的所在位置
        temp=find(y==tem);
        row=temp(row);
        col=temp(col);
        %类别数+1
        class_num=class_num+1;
        %令该类别撤销
        y(y==tem)=0;
        %添加两个新类别，一个覆盖原类别，另一个类别为原类别数+1
        y(row)=tem;
        y(col)=class_num;
        continue;
    end
    %如果现有类别数小于等于希望类别数的一半，拆分类内距离最大类别
    if class_num<=hope_class_num/2
        tem=find(distance_class_inner==max(distance_class_inner),1);
        %temp为该类别的样本
        temp=x_scale(:,y==tem);
        %distance(i,j)指第i个样本到第j个样本的距离
        distance=zeros(size(temp));
        for i=1:sum(y==tem)
            distance(i,:)=sum((temp-repmat(temp(:,i),1,sum(y==tem))).^2);
        end
        %找到距离最远的两个样本
        [row,col]=find(distance==max(max(distance)),1);
        %分别找到这个两个样本的所在位置
        temp=find(y==tem);
        row=temp(row);
        col=temp(col);
        %类别数+1
        class_num=class_num+1;
        %令该类别撤销
        y(y==tem)=0;
        %添加两个新类别，一个覆盖原类别，另一个类别为原类别数+1
        y(row)=tem;
        y(col)=class_num;
        continue;
    end
    %如果现有类别数大于等于希望类别数的二倍，合并类间距离最小的两类
    if class_num>=hope_class_num*2
        %找到距离最近的两个类别
        [row,col]=find(distance_between_class==min(min(distance_between_class)),1);
        %类别数-1
        class_num=class_num-1;
        %将col类合并到row类中
        y(y==col)=row;
        %调整类别序号
        y(y>col)=y(y>col)-1;
        continue;
    end
    %添加样本类内间距最大值
    break;
end

ISODATA_display.m

1
2
3
4
5
6
7
8
9
10
11
12
13
function ISODATA_display(x,y,class_center,sample_num,class_num)
color_bar=zeros(class_num,3);
hold on;
for i=1:class_num
    color_bar(i,:)=[rand(1),rand(1),rand(1)];
    %绘制样本中心，用*表示
    plot(class_center(1,i),class_center(2,i),'color',color_bar(i,:),'marker','*')
end
for i=1:sample_num
    %绘制数据集，用o表示
    plot(x(1,i),x(2,i),'color',color_bar(y(i),:),'marker','o');
end
hold off;



实验结果

ISODATA

性能比较

  • 优点：
    • 大数据集时，对噪声数据不敏感
    • 可以动态调整类别个数和类别中心
    • 在先验知识不足的情况下有较好的分类能力
  • 缺点：
    • 对初始中心点敏感
    • 算法复杂，分类速度较慢
    • 只适合分布呈凸型或者球形的数据集
    • 对于高维数据，距离的度量并不是很好
-------------本文结束感谢您的阅读-------------
© 2023 USTCcoder
本站访客数 人 本站总访问量 次
0%