首页 > 代码库 > 聚类算法:ISODATA算法

聚类算法:ISODATA算法

1. 与K-均值算法的比较
–K-均值算法通常适合于分类数目已知的聚类,而ISODATA算法则更加灵活;
–从算法角度看, ISODATA算法与K-均值算法相似,聚类中心都是通过样本均值的迭代运算来决定的;
–ISODATA算法加入了一些试探步骤,并且可以结合成人机交互的结构,使其能利用中间结果所取得的经验更好地进行分类。
 
2. ISODATA算法基本步骤和思路

(1)  选择某些初始值。可选不同的参数指标,也可在迭代过程中人为修改,以将N个模式样本按指标分配到各个聚类中心中去。

(2)  计算各类中诸样本的距离指标函数。

(3)~(5)按给定的要求,将前一次获得的聚类集进行分裂和合并处理((4)为分裂处理,(5)为合并处理),从而获得新的聚类中心。

(6)  重新进行迭代运算,计算各项指标,判断聚类结果是否符合要求。经过多次迭代后,若结果收敛,则运算结束。

3. ISODATA算法流程图:

4.ISODATA算法

第一步:输入$N$个模式样本$\{x_i, i = 1, 2, …, N\}$

           预选$N_c$个初始聚类中心$\{ z_1 ,z_2 , \ldots z_{N_c } \} $,它可以不等于所要求的聚类中心的数目,其初始位置可以从样本中任意选取。

           预选:$K$  = 预期的聚类中心数目;

                    $\theta_N$ = 每一聚类域中最少的样本数目,若少于此数即不作为一个独立的聚类;

                    $\theta_S$ = 一个聚类域中样本距离分布的标准差;

                    $\theta_c$= 两个聚类中心间的最小距离,若小于此数,两个聚类需进行合并;

                    $L$= 在一次迭代运算中可以合并的聚类中心的最多对数;

                    $ I$  = 迭代运算的次数。

第二步:将$N$个模式样本分给最近的聚类$S_j$,假若$D_j = \min \{ \left\| {x - z_i } \right\|,i = 1,2, \cdots N_c \} $

           ,即$||x-z_j||$的距离最小,则$x \in S_j $。

第三步:如果$S_j$中的样本数目SjN,则取消该样本子集,此时Nc减去1。

           (以上各步对应基本步骤(1))

 

第四步:修正各聚类中心

\[
\begin{array}{*{20}c}
{z_j = \frac{1}{{N_j }}\sum\limits_{x \in S_j } x ,} & {j = 1,2, \cdots ,N_c } \\
\end{array}
\]

第五步:计算各聚类域Sj中模式样本与各聚类中心间的平均距离

\[
\begin{array}{*{20}c}
{\bar D_j = \frac{1}{{N_j }}\sum\limits_{x \in S_j } {\left\| {x - z_j } \right\|} ,} & {j = 1,2, \cdots ,N_c } \\
\end{array}
\]

第六步:计算全部模式样本和其对应聚类中心的总平均距离

\[
\bar D = \frac{1}{N}\sum\limits_{j = 1}^N {N_j \bar D_j } 
\]

(以上各步对应基本步骤(2))

 

第七步:判别分裂、合并及迭代运算

  1. 若迭代运算次数已达到I次,即最后一次迭代,则置θc =0,转至第十一步。
  2. 若$N_c \le \frac{K}{2}$
    ,即聚类中心的数目小于或等于规定值的一半,则转至第八步,对已有聚类进行分裂处理。
  3. 若迭代运算的次数是偶数次,或$N_c \ge 2K$
    ,不进行分裂处理,转至第十一步;否则(即既不是偶数次迭代,又不满足$N_c \ge 2K$),转至第八步,进行分裂处理。

(以上对应基本步骤(3))

 

第八步:计算每个聚类中样本距离的标准差向量

\[
\sigma _j = (\sigma _{1j} ,\sigma _{2j} , \ldots ,\sigma _{nj} )^T 
\]

          其中向量的各个分量为

\[
\sigma _{ij} = \sqrt {\frac{1}{{N_j }}\sum\limits_{k = 1}^{N_j } {(x_{ik} - z_{ij} )^2 } } 
\]

          式中,i = 1, 2, …, n为样本特征向量的维数,j = 1, 2, …, Nc为聚类数,Nj为Sj中的样本个数。

第九步:求每一标准差向量{σj, j = 1, 2, …, Nc}中的最大分量,以{σjmax, j = 1, 2, …, Nc}代表。

第十步:在任一最大分量集{σjmax, j = 1, 2, …, Nc}中,若有σjmaxS ,同时又满足如下两个条件之一:

  1. $\bar D_j > \bar D$和Nj > 2(θN + 1),即Sj中样本总数超过规定值一倍以上,
  2. $N_c \le \frac{K}{2}$

       则将zj 分裂为两个新的聚类中心和,且Nc加1。 中对应于σjmax的分量加上kσjmax,其中;中对应于σjmax的分量减去kσjmax

       如果本步骤完成了分裂运算,则转至第二步,否则继续。

      (以上对应基本步骤(4)进行分裂处理)

 

第十一步:计算全部聚类中心的距离

                  \[D_{ij} = || z_i - z_j ||,i = 1, 2, …, N_c-1 ,j =i+1, …, N_c\]

第十二步:比较Dij 与θc 的值,将Dij <θc 的值按最小距离次序递增排列,即

\[
\{ D_{i_1 j_1 } ,D_{i_2 j_2 } , \ldots ,D_{i_L j_L } \} 
\]

             式中$D_{i_1 j_1 } < D_{i_2 j_2 } < \ldots < D_{i_L j_L } $。

第十三步:将距离为$D_{i_kj_k}$的两个聚类中心$Z_{i_k}$和$Z_{j_k}$合并,得新的中心为:

              \[z_k^\ast= \frac{1}{{N_{i_k } + N_{j_k } }}[N_{i_k } z_{i_k } + N_{j_k } z_{j_k } ],k = 1,2, \cdots ,L\]

              式中,被合并的两个聚类中心向量分别以其聚类域内的样本数加权,使$Z_k^\ast$为真正的平均向量。

             (以上对应基本步骤(5)进行合并处理)

 

第十四步:如果是最后一次迭代运算(即第I次),则算法结束;否则,若需要操作者改变输入参数,转至第一步;若输入参数不变,转至第二步。

              在本步运算中,迭代运算的次数每次应加1。

 [算法结束]

5.例子:试用ISODATA算法对如下模式分布进行聚类分析:

\[\{x_1(0,0),x_2(3,8),x_3(2,2),x_4(1,1),x_5(5,3),x_6(4,8),x_7(6,3),x_8(5,4),x_9(6,4),x_{10}(7,5)\}\]

 

我们可以知道,N=10,n=2。假设取初始值$N_c=1$,z1=x1=(0 0)T,则运算步骤如下:

(1)   设置控制参数

            取K=3,θN=1,θS=1,θc=4,L=1,I=4

(2)   按最小距离原则将模式集(xi)中每个模式分到某一类中。

          由于此时只有一个聚类中心,因此S1={x1, x2, …, x10},N1=10

(3)   因N1N ,无子集可抛

(4)   修改聚类中心

\[
z_1 = \frac{1}{{N_1 }}\sum\limits_{x \in S_1 } {x = \left( {\begin{array}{*{20}c}
{3.9} \\
{3.8} \\
\end{array}} \right)} 
\]

(5)   计算模式样本与聚类中心间的平均距离$\bar D_1 $

\[
{\bar D_1 = \frac{1}{{N_1 }}\sum\limits_{x \in S_1 } {\left\| {x - z_1 } \right\|} = 3.0749}
\]

(6)   计算全部模式样本和其对应聚类中心的总平均距离

\[
\bar D = \bar D_1 = 3.0749
\]

(7)   因不是最后一次迭代,且$N_c<K/2$,进入(8)

(8)   计算S1中的标准差向量

\[
\sigma _1 = \left( {\begin{array}{*{20}c}
{2.2113} \\
{2.5219} \\
\end{array}} \right)
\]

(9) $\sigma_{1\max}$  中的最大分量是2.5219,因此 $\sigma_{1\max}= 2.5219$。

(10)因$\sigma_{1\max}>\theta_s$ 且$N_c<\frac{K}{2}$,可将z1分裂成两个新的聚          类。设$r_j = 0.5\sigma _{1\max } \approx 1.261$.则

\[
z_1^ + = \left( {\begin{array}{*{20}c}
{3.9} \\
{5.061} \\
\end{array}} \right),z_1^ - = \left( {\begin{array}{*{20}c}
{3.9} \\
{2.539} \\
\end{array}} \right)
\]

           为方便起见,将$z_1^+$和$z_1^-$表示为z1和z2,Nc加1 ,$N_c=2$.

(11)   重新进行分类

样本点

特征值

到z1的距离

到z2的距离

聚类结果

X1

0

0

6.3893

4.6537

S2

X2

3

8

3.0737

5.5347

S1

X3

2

2

3.6027

1.975

S2

X4

1

1

4.9902

3.2831

S2

X5

5

3

2.3362

1.1927

S2

X6

4

8

2.9407

5.4619

S1

X7

6

3

2.9424

2.15

S2

X8

5

4

1.5283

1.8288

S1

X9

6

4

2.3528

2.5582

S1

X10

7

5

3.1006

3.9581

S1

\[
{\rm{S}}1 = \{ {\rm{x2,x6,x8,x9,x10\} ,N}}_1 = 5
\]

\[
{\rm{S2 = \{ x1,x3,x4,x5,x7\} ,N}}_2 = 5
\]

(12)   因N1N 且N2N,无子集可抛。

(13)   修改聚类中心

\[
{z_1 = \frac{1}{{N_1 }}\sum\limits_{x \in S_1 } {x = \left( {\begin{array}{*{20}c}
5 \\
{5.8} \\
\end{array}} \right)} }
\]

\[
{z_2 = \frac{1}{{N_2 }}\sum\limits_{x \in S_2 } {x = \left( {\begin{array}{*{20}c}
{2.8} \\
{1.8} \\
\end{array}} \right)} }
\]

(14)   计算模式样本与聚类中心间的平均距离$\bar D_j ,j=1,2$

\[
{\bar D_1 = \frac{1}{{N_1 }}\sum\limits_{x \in S_1 } {\left\| {x - z_1 } \right\|} = {\rm{ 2}}{\rm{.2806}}}
\]

\[
{\bar D_2 = \frac{1}{{N_2 }}\sum\limits_{x \in S_2 } {\left\| {x - z_2 } \right\|} = {\rm{2}}{\rm{.4093}}}
\]

(15)   计算全部模式样本和其对应聚类中心的总平均距离$\bar D$

\[
\bar D = \frac{1}{N}\sum\limits_{j = 1}^N {N_j \bar D_j } = \frac{1}{{10}}\sum\limits_{j = 1}^2 {N_j \bar D_j = {\rm{2}}{\rm{.345}}} 
\]

(16)   因是偶数次迭代,所以进行合并

(17)   计算聚类对之间的距离

\[
{D_{12} = \left\| {z_1 - z_2 } \right\| = {\rm{4}}{\rm{.5651}}}
\]

(18)   比较$D_{12}$ 与θc ,$D_{12}$>θc,所以聚类中心不发生合并

(19)   没有达到所需的聚类数,所以继续进行,重新分类

样本点

特征值

到z1的距离

到z2的距离

聚类结果

X1

0

0

7.6577

3.3287

S2

X2

3

8

2.9732

6.2032

S1

X3

2

2

4.8415

0.82462

S2

X4

1

1

6.2482

1.9698

S2

X5

5

3

2.8

2.506

S2

X6

4

8

2.4166

6.3151

S1

X7

6

3

2.9732

3.4176

S1

X8

5

4

1.8

3.1113

S1

X9

6

4

2.0591

3.8833

S1

X10

7

5

2.1541

5.2802

S1

\[
{\rm{S}}1 = \{ {\rm{x2,x6,x7,x8,x9,x10\} ,N}}_1 = 6
\]

\[
{\rm{S2 = \{ x1,x3,x4,x5\} ,N}}_2 = 4
\]

(20)   因N1N 且N2N,无子集可抛。

(21)   修改聚类中心

\[
{z_1 = \frac{1}{{N_1 }}\sum\limits_{x \in S_1 } {x = \left( {\begin{array}{*{20}c}
{{\rm{5}}{\rm{.1667}}} \\
{{\rm{5}}{\rm{.3333}}} \\
\end{array}} \right)} }
\]

\[
{z_2 = \frac{1}{{N_2 }}\sum\limits_{x \in S_2 } {x = \left( {\begin{array}{*{20}c}
2 \\
{1.5} \\
\end{array}} \right)} }
\]

(22)   计算模式样本与聚类中心间的平均距离,$\bar D_1,j=1,2$

\[
{\bar D_1 = \frac{1}{{N_1 }}\sum\limits_{x \in S_1 } {\left\| {x - z_1 } \right\|} = {\rm{2}}{\rm{.2673}}}
\]

\[
{\bar D_2 = \frac{1}{{N_2 }}\sum\limits_{x \in S_2 } {\left\| {x - z_2 } \right\|} = {\rm{1}}{\rm{.868}}}
\]

(23)   计算全部模式样本和其对应聚类中心的总平均距离$\bar D$

\[
\bar D = \frac{1}{N}\sum\limits_{j = 1}^N {N_j \bar D_j } = \frac{1}{{10}}\sum\limits_{j = 1}^2 {N_j \bar D_j = {\rm{ 2}}{\rm{.1076}}} 
\]

(24)   此次是奇数次迭代,并且$N_c>\frac{K}{2}$,所以进行分裂操作

(25)   计算${\rm{S}}1 = \{ {\rm{x2,x6,x7,x8,x9,x10\} }}$

和$S21 = \{ x1,x3,x4,x5\} $

的标准差

\[
\sigma _1 = \left( {\begin{array}{*{20}c}
{1.3437} \\
{1.972} \\
\end{array}} \right),\sigma _2 = \left( {\begin{array}{*{20}c}
{1.8708} \\
{1.118} \\
\end{array}} \right)
\]

(26)${\rm{\sigma }}_{{\rm{1max}}} {\rm{ = 1}}{\rm{.972,\sigma }}_{{\rm{2max}}} {\rm{ = 1}}{\rm{.8708}}$

(27)此时,$\sigma_{1\max}=1.972>\theta_s,N_1=6>2(\theta_N+1)=4$且$\bar D_1>\bar D $,所以满足分裂的条件,将S1进行分裂。

设$\r_j=0.5\sigma_{1\max}\approx 0.986$,则

\[
{z_1^ + = \left( {\begin{array}{*{20}c}
{{\rm{5}}{\rm{.1667}}} \\
{{\rm{6}}{\rm{.3193}}} \\
\end{array}} \right),z_1^ - = \left( {\begin{array}{*{20}c}
{{\rm{5}}{\rm{.1667}}} \\
{{\rm{4}}{\rm{.3473}}} \\
\end{array}} \right)}
\]

 为方便起见,将$Z_1^+$和$Z_^-$表示为$Z_{11}$和$Z_{12}$,$N_c$加1,$N_c=3$.

(28)重新进行分类

样本点

特征值

到的距离

到的距离

到的距离

聚类结果

X1

0

0

8.1626

6.7523

2.5

S2

X2

3

8

2.7421

4.247

6.5765

S11

X3

2

2

5.3558

3.9418

0.5

S2

X4

1

1

6.7569

5.3447

1.118

S2

X5

5

3

3.3235

1.3576

3.3541

S12

X6

4

8

2.046

3.8345

6.8007

S11

X7

6

3

3.4223

1.5842

4.272

S12

X8

5

4

2.3253

0.38524

3.9051

S12

X9

6

4

2.4645

0.90278

4.717

S12

X10

7

5

2.2587

1.946

6.1033

S12

\[S11=\{x2,x6\},N_{11}=2\]

\[S12=\{x5,x7,x8,x9,10\},N_{12}=5\]

(29)   因N11N 且N12N且N2N,无子集可抛

(30)   修改聚类中心

\[S2=\{x1,x3,x4\},N_2=3\]

\[
{z_{11} = \frac{1}{{N_{11} }}\sum\limits_{x \in S_{11} } {x = \left( {\begin{array}{*{20}c}
{3.5} \\
8 \\
\end{array}} \right)} }
\]

\[
{z_{12} = \frac{1}{{N_{12} }}\sum\limits_{x \in S_{12} } {x = \left( {\begin{array}{*{20}c}
{5.8} \\
{3.8} \\
\end{array}} \right)} }
\]

\[
{z_2 = \frac{1}{{N_2 }}\sum\limits_{x \in S_2 } {x = \left( {\begin{array}{*{20}c}
1 \\
1 \\
\end{array}} \right)} }
\]

(31)   计算模式样本与聚类中心间的平均距离$\bar D_j$

\[
{\bar D_{11} = \frac{1}{{N_{11} }}\sum\limits_{x \in S_{11} } {\left\| {x - z_{11} } \right\|} = {\rm{ 0}}{\rm{.5}}}
\]

\[
{\bar D_{12} = \frac{1}{{N_{12} }}\sum\limits_{x \in S_{12} } {\left\| {x - z_{12} } \right\|} = {\rm{ 0}}{\rm{.9521}}}
\]

\[
{\bar D_2 = \frac{1}{{N_2 }}\sum\limits_{x \in S_2 } {\left\| {x - z_2 } \right\|} = {\rm{0}}{\rm{.94281}}}
\]

(32)   计算全部模式样本和其对应聚类中心的总平均距离$\bar D$

\[
\bar D = \frac{1}{N}\sum\limits_{}^{} {N_j \bar D_j } = \frac{1}{{10}}\sum\limits_{}^{} {N_j \bar D_j = {\rm{0}}{\rm{.85889}}} 
\]

(33)   因是偶数次迭代,所以进行合并

(34)   计算聚类对之间的距离

 

 Z11Z12 Z13 
 Z11

0

4.7885

7.433

Z12 

4.7885

0

5.557

Z2 

7.433

5.557

0

所以

\[
{D_{1112} = \left\| {z_{11} - z_{12} } \right\| = {\rm{4}}{\rm{.7885 > }}\theta _c = 4}
\]

\[
{D_{112} = \left\| {z_{11} - z_2 } \right\| = 7.433{\rm{ > }}\theta _c = 4}
\]

\[
{D_{122} = \left\| {z_{12} - z_2 } \right\| = 5.557{\rm{ > }}\theta _c = 4}
\]

            故没有可以合并的类

(35)   最后一次迭代,算法结束。

             最终的聚类结果是

\[
S_1 = \{ x_2 ,x_6 \} ,S_2 = \{ x_5 ,x_7 ,x_8 ,x_9 ,x_{10} \} ,S_3 = \{ x_1 ,x_3 ,x_4 \} ,N_2 = 3
\]

6 .聚类结果的评价
     迅速评价聚类结果,在上述迭代运算中是很重要的,特别是具有高维特征向量的模式,不能直接看清聚类效果,因此,可考虑用以下几个指标来评价聚类效果:
    –聚类中心之间的距离
          •距离值大,通常可考虑分为不同类
    –聚类域中的样本数目
          •样本数目少且聚类中心距离远,可考虑是否为噪声
    –聚类域内样本的距离方差
          •方差过大的样本可考虑是否属于这一类
 
     模式聚类目前还没有一种通用的放之四海而皆准的准则,往往需要根据实际应用来选择合适的方法。

 

该资料整理于国科大《模式识别》讲稿和作业。

聚类算法:ISODATA算法