基于加權改進模糊C均值聚類的欠定混合矩陣估計

孫建軍，徐 巖

（蘭州交通大學電子與信息工程學院，蘭州 730070）

（?通信作者電子郵箱346206395@qq.com）

0 引言

在信號處理技術中，當原始信號難以獲知，僅利用觀測信號來恢復原始信號的技術，稱為盲源分離（Blind Source Separation，BSS）［1］。近年來，隨著該技術的迅猛發展，其已成為醫學、圖像處理等領域不可或缺的部分。欠定盲源分離（Underdetermined BSS，UBSS）一直是盲源分離技術研究的難點和熱點。基于信號的稀疏分析是目前解決欠定盲源分離問題的首選方法，該方法可簡要概括為兩步，即：首先估計出混合矩陣值，然后進行原始信號恢復。由此可見，準確估計出混合矩陣對于整個問題的良好解決是至關重要的［2］。近年來，模糊C均值聚類（Fuzzy C-Means clustering，FCM）算法是解決混合矩陣估計問題的熱門方法之一。然而，該算法存在對初始聚類中心敏感、聚類數目需手動給出、易陷入局部最優解，并且受噪聲點對聚類的影響等問題。面對以上諸多缺陷，Yang 等［3］提出基于魯棒學習的FCM 算法，通過構造一個FCM算法學習框架，使其獲得健全的自主學習搜尋能力，但該算法計算復雜度過高，不易于實際應用。Yang 等［4］提出用差分進化算法來優化FCM，首先利用FCM算法獲得初始結果，然后用差分進化算法優化，最后再利用FCM算法得到最終結果，雖然取得了一定的效果，但由于該算法在首次運用FCM算法時，并未考慮FCM算法對初始值敏感的問題，導致聚類效果不佳。

本文針對FCM 算法的上述缺陷，提出了一種基于加權的進化規劃（Evolutionary Programming，EP）與FCM 相結合的改進算法（improved WEighted FCM algorithm based on EP，WEFCM），即將進化規劃（EP）算法強大的搜索能力與FCM 算法的收斂能力相融合，得到基于進化規劃的FCM 算法（FCM algorithm based on EP，EP-FCM），后利用局部離群點檢測（Local Outlier Factor，LOF）算法對EP-FCM 中的目標函數進行加權操作，以達到自適應確定初始聚類中心和克服噪聲對聚類影響的目的，并將其運用于混合矩陣估計。該算法有效地提高了FCM 算法的收斂能力，改善了FCM 算法對初始聚類中心過于敏感的情況，提高了混合矩陣估計的魯棒性。

1 欠定盲源分離問題描述

通常情況下，欠定盲源分離的線性數學模型可描述為：

式中：x(t)=[x1(t)，x2(t)，…，xM(t)]T表示M個觀測信號；s(t)=[s1(t)，s2(t)，…，sN(t)]T表示N個原始信號；A∈RM×N為混合矩陣，A=[a1，a2，…，aN]，ai表示A的第i個列向量；t表示觀測點時刻；T表示觀測點數目。當源信號稀疏分布時，信號的絕大部分采樣點都為零或非常接近于零［5］。換言之，同一時刻，有且僅有一個源信號的取值不為零，即：

由于在非理想情況下，許多信號難以達到充分稀疏的條件，因此通常會采用短時傅里葉變換（Short-Time Fourier Transform，STFT）的方法將信號轉換到頻域，增加采樣點的數目，使得采樣點呈現出明晰的方向性［6］，則式（1）的STFT 表達式為：

式中：X(t，ω)和Si(t，ω)分別是x(t)和si(t)的STFT。式（2）可改寫為：

2 本文方法

2.1 模糊C均值聚類算法

FCM 算法是一種基于劃分的模糊聚類算法［7］，該算法通過隸屬度確定數據的分類。設有樣本集合為X={x1，，x2，…，xn}，將其分為c類，其聚類中心為C={c1，c2，…，cc}，并使給定的目標函數式（5）趨于最小。

FCM算法具體如下：

步驟1 給定預設參數：閾值ε，聚類中心c，模糊系數m，最大迭代次數T，隸屬度矩陣U0。

步驟2 檢查隸屬度是否滿足歸一化規定。

步驟3 利用式（7）、（8）分別更新聚類中心和隸屬度矩陣［8］。

步驟4 若目標函數J(U，C)＜ε或已迭代到最大次數T，則停止，輸出結果；否則繼續返回步驟3。

FCM算法迭代中，由于目標函數極值點的不確定性，在許多情況下，預設的初始聚類中心往往只會盲目地集中在某些極值點周圍，而漏掉了其余極值點，導致算法收斂效果不佳，因此如何準確確定初始聚類中心是算法研究的重中之重。

2.2 進化規劃算法

進化規劃（EP）算法［9］是進化算法的分支。該算法側重于求解預測問題，并將正態分布運用于變異操作中。與其他進化算法相比，進化規劃算法只著眼于進化過程。由于在選擇算子時，不使用個體交叉算子和重組算子，因此其搜索過程更平穩，收斂速度更快，子代產生也更簡單，不會因結構不穩定而受到影響［10］。該算法基本實現過程為：

1）初始化種群。

2）適應度函數選擇。個體的適應度函數表示為F(x)，F(x)是由相應的目標函數進行適當變換得到。

3）變異。利用高斯變異算子進行變異，個體變異是唯一的最優搜索操作，這也是進化規劃算法的特點。

4）選擇。進化規劃算法采用一種隨機q競爭選擇方式，即會從N個父代和N個子代組成的集合中選擇最優的N個個體，作為下一代群體。

2.3 基于EP-FCM的聚類算法

基于EP-FCM的聚類算法的具體實現步驟如下：

步驟1 設置參數：最大迭代次數T，初始種群的個數P，隨機q選擇中的個數q，閾值ε1。

步驟2 確定適應度函數［11］。設聚類數目為N，si為每一類i(i=1，2，…，N)的個體數，則每一類的聚類中心可表示為：

步驟3 變異。利用式（11）對每個個體進行變異操作：

式中：t為迭代次數；F為適應度函數；δ為高斯變異算子，服從N（0，1）分布；α和β為預設參數，一般設為1和0。

步驟4 選擇。采用隨機q競爭選擇法生成新一代個體。具體過程為：

1）從父代群體N和子代群體N'組成的集合H=N∪N'中隨機選擇q個個體。

2）將q個個體的Fj(j∈(1，2，…，q))與xi的Fxi逐個進行比較，計算q個個體中比xi差的個體總數bi(bi∈(1，2，…，q))，并將bi記作xi的得分。

3）H個個體逐一比較后，將分數在前N的個體選為下一代。

步驟5 更新聚類中心。若滿足F＜ε1，則按式（9）更新聚類中心；否則跳到步驟2。

步驟6 當滿足停止條件時，按照式（9）再次更新聚類中心，輸出最終解。

步驟7 將所得聚類中心作為FCM 算法初始聚類中心完成FCM聚類。

2.4 局部離群點檢測算法

局部離群點檢測（LOF）算法［12］是基于密度的離群點檢測算法中比較有代表性的算法之一。該算法會對數據集中的每個點計算一個離群因子LOFk(p)，通過判斷LOFk(p)是否接近于1 來判定該點是否為離群點。若LOFk(p)遠大于1，則認為該點是離群點；若接近于1，則為正常點。為了敘述LOF 算法，首先引入以下定義。

定義1記樣本中點p與點o之間的歐氏距離為d(p，o)。

定義2記dk(p)為點p的第k距離（k-distance），若滿足以下兩個條件：

1）聚類內至少有不包括p在內的k個點a，使d(p，a) ≤d(p，o)；

2）聚類內至多有不包括p在內的k-1個點a，使d(p，a) ＜d(p，o)。則認為dk(p)=d(p，o)。定義Nk(p)為點p的第k鄰域，表示p的第k距離內所有點，因此p的第k鄰域點個數為：|Nk(p)|≥k。

定義3記rech-distk(p，o)為點o到點p的第k可達距離，滿足：

定義4局部可達密度（local reachable density），記作Irdk(p)，表示為：

定義5局部離群因子（記作LOFk(p)）表示為：

如果所得局部離群因子值小于1，說明p的密度大于其鄰域點密度，p為聚類點；若該值接近1，p與鄰域屬同一聚類；若該值大于1，說明p密度小于其鄰域密度，p為噪聲點。通過這種方式，在樣本空間數據分布不均勻的情況下也可以準確發現離群點。

2.5 WE-FCM優化算法

由于噪聲點的影響，FCM 算法所得類中心的位置往往不在合理區域，因此本文將LOF 算法加權策略［13］與EP-FCM 結合，提出WE-FCM，克服FCM算法對噪聲點敏感的缺陷。

記Lp=LOFk(p)。將Lp作為動態加權系數應用到FCM 目標函數及EP算法的適應度函數中。式（5）可展成式（15）：

式（10）可展成式（16）：

通過上述加權策略，使得算法的目標函數在樣本密度小的區域變大，無法收斂，而在樣本密度大的區域變小，快速收斂，從而有效改善噪聲點對聚類結果的影響。

算法步驟如下：

步驟1 對樣本點進行預處理。

步驟2 利用LOF算法確定Lp（這里k=20）。

步驟3 用EP算法估計初值。

步驟4 將得到的初值進行FCM 聚類，得到混合矩陣估計值。

3 仿真實驗與結果分析

3.1 混合矩陣評價準則

采用兩種性能指標對混合矩陣進行評價［14］，分別是：

1）歸一化均方誤差（Normalized Mean Square Error，NMSE）。

式中：M、N為混合矩陣的行列數；aij和是混合矩陣A和其估計值的第i行、第j列。所得NMSE 值越小，則說明混合矩陣的估計越精確，算法的魯棒性越好。

2）偏離角度。

式中：ai是混合矩陣A的第i列；是其估計值的第i列。所得偏離角度值越小，則說明混合矩陣的估計越精確，算法的魯棒性越好。

3.2 結果分析

為驗證本文所提算法的有效性，進行了兩個實驗仿真，源信號為NOIZEUS語音庫中的信號，采樣頻率為8 kHz。

1）實驗一：隨機取三路語音信號，根據式（1）將其變成兩路觀測信號。

混合矩陣A隨機確定如下：

所得的兩路觀測信號時域波形如圖1所示。

圖1 兩路觀測信號時域波形Fig.1 Time domain waveforms of two-way observation signals

由圖1 難以獲知觀測信號方向聚集性的強弱，需要對觀測信號進行STFT。本文選用Hanning 窗，窗口長度設定為512，疊合長度為256。經過變換后的觀測信號時頻域散點圖如圖2所示。

圖2 兩路觀測信號時頻域散點圖Fig.2 Time-frequency domain scatter plots of two-way observation signals

觀察圖2 可見觀測信號未呈現出明晰的方向性，需要對信號點做進一步處理，本文首先利用單源時頻點處理，使信號呈現出明晰的方向性，然后設定ε=0.15 進行邊緣能量點的篩除［15］，最后將剩余信號做歸一化處理，如圖3所示。

圖3 兩路觀測信號預處理后的散點圖Fig.3 Pre-processed scatter plots of two-way observation signals

所涉及各預設參數為：T=100，m=3，ε=1E -6，N=3，ε1=0.04。

為方便對所提算法做準確直觀的評估，本文選取了四種具有代表性的混合矩陣估計算法進行比對，分別是經典的K均值（K-means）聚類算法［16］、基于霍夫變換的K-Hough 算法［17］、基于遺傳算法的FCM 算法（FCM algorithm based on Genetic Algorithm，GAFCM）［18］、基于密度峰值的FCM 算法（FCM algorithm based on Find Density Peaks，FDP-FCM）［19］。

K-means算法得到的估計矩陣為：

本文算法得到的估計矩陣為：

上述各算法所得混合矩陣估計值的性能指標評價結果如表1所示。

表1 三路源信號時各算法性能對比Tab.1 Performance comparison of various algorithms when using three source signals

2）實驗二：隨機取四路語音信號根據式（1）將其變成三路觀測信號。

混合矩陣A隨機確定如下：

所得的三路觀測信號時域波形如圖4 所示。以下各步驟操作與實驗一相仿，其處理結果如圖5～圖6。

圖4 三路觀測信號時域波形Fig.4 Time domain waveforms of three-way observation signals

圖5 三路觀測信號時頻域散點圖Fig.5 Time-frequency domain scatter plots of three-way observation signals

圖6 三路觀測信號預處理后的散點圖Fig.6 Pre-processed scatter plots of three-way observation signals

K-means算法得到的估計矩陣為：

本文算法得到的估計矩陣為：

上述各算法所得矩陣估計值的性能指標評價結果如表2。

表2 四路源信號時各算法性能對比Tab.2 Performance comparison of various algorithms when using four source signals

分析表1和表2可知，與K-means、K-Hough、GAFCM、FDPFCM 四種算法相比：當源信號數N=3 時，WE-FCM 的NMSE 值較其余四種算法至少減小了4.519 1 dB，偏離角度值最多可減小0.578 3°；當源信號數N=4 時，WE-FCM 的NMSE 值較其余四種算法至少減少了2.108 4 dB，偏離角度值最多可減小2.346 6°。觀察表1 和表2 中各列向量的偏離角度值發現，WE-FCM 的偏離角度值最小且最穩定，表明文中所提的LOF加權策略可有效降低噪聲點對算法估計精度的影響。因此，源信號數N=3、N=4 時，相較于K-means、K-Hough、GAFCM、FDP-FCM，WE-FCM 的性能是最好的，即混合矩陣估計的魯棒性是最好的。

4 結語

對于FCM 算法在混合矩陣估計中存在的對初值敏感、魯棒性差、易受噪聲點干擾的問題，本文提出了一種基于WEFCM 的混合矩陣估計的優化算法。實驗仿真結果表明，在源信號數N=3、N=4 時，本文算法在算法穩定性及矩陣估計精度方面相較經典的K-means、K-Hough、GAFCM、FDP-FCM 都有較大提高，對混合矩陣的估計是可行和有效的。在后續研究中，可以關注更多維數據的處理，進一步提升算法的實用性。