摘要: 【摘要】 為了適應心電圖中QRS波形緩慢變化和出現新異常QRS波形,本文提出了動態自適應模板法。該方法的基本思想是原有模板在聚類過程中不斷更新,并且允許在聚類分析過程中構成新的模板。 【Abstract】 The dynamic self-adaptation model method is developed in the paper,in order to suit low change of QRS of e......
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)