点击显示 收起
1 迭代自组织的数据分析算法
迭代自组织的数据分析算法（Iterative selforganizing Data Analysis Techniques Algorithm）所以又称ISODATA算法 ［2］ 。但ISODATA算法还加入一些试探步骤和人机交互功能，能自动地进行类的合并和分裂，能吸取中间结果所得到的经验，主要是在迭代过程中可将一类一分为二，亦可能二类合二为一，亦即”自组织”，从而得到类数较合理的聚类结果。这种算法已具有启发式的特点 ［3］ 。
（1）下面我们给出ISODATA算法ISODATA算法的步骤其基本步骤为:
①选择某些初始值 可选不同指标，也可在迭代运算过程中人为修改，以将N个模式样本按指标分配到各个聚类中心去。
②计算各类中诸样本的距离函数等指标。
③～⑤按给定的要求，将前一次获得的聚类集进行分裂和合并处理（④为分裂处理，⑤为合并处理），以获得新的聚类中心。
⑥再次迭代运算，重新计算各项指标，判别聚类结果是否符合要求，经过多次迭代运算后，如结果收敛，运算结束。
（2）ISODATA算法的具体步骤
已知样本集为｛x 1 ，x 2 ，…，x N ｝，将N个模式样本｛x 1 ，x 2 ，…，x N ｝读入。预选N c 个初始聚类中心｛Z → 1 ，Z → 2 ，…，Z → N c ｝，它可以不必等于所要求的聚类中心的数目，其初始位置亦可从样本中任选一些代入。
第一步:规定下列控制参数预选:K=期望得到的聚类数，也即预期的聚类中心数目;Q N =一个聚类中的最少样本数，即如少于此数就不作为一个独立的聚类;
Q s =一个聚类域中样本距离分布的标准偏差参数;Q c =合并参数; L=每次迭代允许合并的最大聚类对数;I=允许迭代的次数。设初始的聚类数c和初始的聚类中心w i ，i=1，2，...，c.
第二步:按照下述关系若‖x-w i ‖<‖x-w j ‖，j=1，2，…，c.j≠i 则x∈R i 将所有样本分到各个聚类中去。R i 是第Ⅰ个聚类，其中心为w i
第三步:若有任何一个R i ，其基数Q i <Q N ，则舍去R i ，并令c=c-1
第四步:按照下列关系w i =1N∑ x∈Ri x，i=1，2，…，c.计算更新的均值向量。式中N i 是第Ⅰ个聚类的样本数目（基数）。
第五步:计算R i 中的所有样本距其相应的聚类中心w i 的平均距离D i D i =1N∑ x∈Ri ‖x-w i ‖，i=1，2，...，c.
第六步:计算所有样本距离其相应的聚类中心的平均距离 D=1N∑ c i=1 N i D i
第七步:（a）若这是最后一次迭代（由参数Ⅰ确定），则置θ c =0，转第（11）步;（b）若c≤K/2，，转第（8）步;（c）若是偶数次迭代，或若是c≥2K，则转第（11）步。否则，往下进行。
第八步:对每一个聚类R i ，用下列公式求标准差σ i =σ i1 ，σ i2 ，…，σ in ） T σ ij = 1N∑xk∈Ri （x kj -w ij ） 2 式中，x kj 是第k个样本的第j个分量;w ij 是第I个聚类中心的第j个分量;σ ij 是第I个聚类的标准偏差的第j个聚类的标准差的第j个分量;n是样本x的维数。
第九步:对每一个聚类，求出具有最大标准偏差的分量σ imax ，i=1，2，...，c.
第十步:若对任一个，i=1，2，...，c，存在σ imax >θ s ，并且有:（a）D i >D且N i >2（θ N +1）;或（b）c≤K/2则把R i 分裂成两个聚类，其中心相应为w i+ 和w i- ，把原来的w i 取消，且令c=c+1。w +i 和w i- 的计算如下:给定一个α值，0<α≤1，令r i =ασ imax ，则w i+ 和w i- 的距离不同，但又应使R i 中的样本仍然在这两个新的集合中。
第十一步:对于所有的聚类中心，计算两两之间的距离D ij =‖w i -w j ‖，i=1，…，c-1j=i+1，i+2，…，c
第十二步:比较D ij 和θ c ，将D ij <θ c 的值按上升次序排列:D i 1 j 1 <D i 2 j 2 <…<D i l j l ，1≤L
第十三步:从最小D i 1 j 1 的开始，将距离为D i 1 j 1 的两个聚类中心w i l 和w j l 合并，得新的聚类中心w 1 = 1N i 1 +N j 1 ［N i 1 +w i 1 +N j 1 w j 1 ］，并令c=c-1。
第十四步:若这是最后一次迭代，则算法终止。否则，若根据经验需要改变参数，则转第（1）步;若不需要改变参数，则转第（2）步。本步中，还应将迭代计数器加1。本算法完毕。
2 应用动态自适应模板法识别疾病
QRS波形分类可采用叠代自组织数据分析方法，即将每一个QRS波样本与已存的模板一一进行相似性度测量，取距离最小或相关系数最大者归类。为了适应心电图中QRS波形缓慢变化和出现新异常QRS心电波形，本文提出了动态自适应模板法。该方法的基本思想是原有模板在聚类过程中不断更新，并且允许在聚类分析过程中构成新的模板。具体说来如下。
（1）原有模板在聚类过程中不断更新意思是指当某一 形态类别t增添了新样本时，则以下面的递推公式对模板进行刷新:M t，k+1 = 1N t，k+1 （N t，k *M t，k +X k ）式中M t，k 是第K次更新的模板向量，N t，k 是归入第T类样本ALL总数，所得的新模板是该类样本的平均值。从统计学的观点看，平均值更接近于真值。
（2）允许在聚类分析过程中构成新的模板的意思是对相似性测量的届果设定一个阈值，当新的QRS波的样本与原有所有模板的距离均大于这个阈值时，则证明它不属于已有的任一形态集，算法将以表达该QRS波的向量构造一个新的模板。
定义一个QRS波的特征向量X为:x=［A（1），A（2），V（1），V（2），V（3），V（4），QRS d ，T（1）T］ T 式中A为面积，V为电压幅值，QRSd为波形宽度，T为平均QRS波间隔，T（1）为该QRS波与前一个QRS波之间的间隔。
各个特征向量元素的定义如图1所示
图1 QRS波各特征元素的定义 略
下面图2是用该方法分类检测出的疾病。
图2 用本文的方法识别的室性早博（竖线较长者，标V者） 略
从图2可见用本文的方法识别疾病能取得较好的效果。
参考文献
1 张仰森.人工智能原理与应用.北京:高等教育出版社，2004，346-348.
2 杨福生，高上凯，生物医学信号处理.北京:高等教育出版社，1998，332-334.
3 李雄飞，数据挖掘与知识发现.北京:高等教育出版社，2003，105-160.
基金项目:北京市科委项目和北京市组织部优秀人才资助项目资助（编号:KM200410016002）
作者单位:100044北京建筑工程学院
（收稿日期:2004-10-14）