动态聚类法的应用与优势分析

动态聚类法要解决的问题是，如果有n个样本点，要把它们分成K类，使得每一类内的元素都是聚合的，并且类与类之间还能很好地区分开来。特别对于大型数据表的聚类分析问题，动态聚类法就会显得更方便、更实用。

1.动态聚类法工作过程

图7-11　动态聚类法的工作过程

（a）空间的点群；（b）任取两个聚核；（c）第一次分类；（d）求各类重心；（e）第二次分类

下面介绍在动态聚类法中，怎样衡量分类结果是否合理、结论是否稳定的问题。

定义

2.计算方法

首先，以每一类的重心为聚核，给出动态聚类法的计算过程。称Ai为第i类的聚核，有

式中：ni为Pi类中的点的数目。

第一步：随机选取K个点作为K个聚核（为计算收敛更快起见，实际操作时可以根据经验或直观判断选取更有利的K个聚核），记为

根据L0，可以把Ω中的点分为K类，记为

其中

第二步：由P0出发，计算新的聚核L1

由L1出发，做新的分类

以此类推，重复以上过程。

定义

式中：ε是一个充分小的允许误差。

3.更一般的情形

除重心外，聚核还可以是一组点、一条线等。在此类情况下，动态聚类算法的步骤如下。

若有n个样本点集合Ω，要将它们分成K类，可以构造两个递推集合：聚核集合L＝（A1，A2，…，AK）和分类集合P＝（P1，P2，…，PK）。

（4）重复以上步骤，即循环计算，有Ln＝g（Pn-1）和Pn＝f（Ln），由此得到一个分类结果序列Vn＝（Ln，Pn）。(www.xing528.com)

定义

当分类结果逐渐稳定时，应有un值逐渐稳定。因此，算法的终止判断条件是

式中：ε是一个充分小的允许误差。

理论上可以证明，当计算次数n逐渐增大时，un将单调下降。而显然un≥0是有下界的，所以，un会随着循环计算而逐步趋于稳定，因此，分类结果Vn＝（Ln，Pn）也逐步稳定。简言之，动态聚类法的算法是具有收敛性的。