基于加權(quán)改進(jìn)模糊C均值聚類(lèi)的欠定混合矩陣估計(jì)

孫建軍，徐 巖

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

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

0 引言

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

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

1 欠定盲源分離問(wèn)題描述

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

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

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

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

2 本文方法

2.1 模糊C均值聚類(lèi)算法

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

FCM算法具體如下：

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

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

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

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

FCM算法迭代中，由于目標(biāo)函數(shù)極值點(diǎn)的不確定性，在許多情況下，預(yù)設(shè)的初始聚類(lèi)中心往往只會(huì)盲目地集中在某些極值點(diǎn)周?chē)┑袅似溆鄻O值點(diǎn)，導(dǎo)致算法收斂效果不佳，因此如何準(zhǔn)確確定初始聚類(lèi)中心是算法研究的重中之重。

2.2 進(jìn)化規(guī)劃算法

進(jìn)化規(guī)劃（EP）算法［9］是進(jìn)化算法的分支。該算法側(cè)重于求解預(yù)測(cè)問(wèn)題，并將正態(tài)分布運(yùn)用于變異操作中。與其他進(jìn)化算法相比，進(jìn)化規(guī)劃算法只著眼于進(jìn)化過(guò)程。由于在選擇算子時(shí)，不使用個(gè)體交叉算子和重組算子，因此其搜索過(guò)程更平穩(wěn)，收斂速度更快，子代產(chǎn)生也更簡(jiǎn)單，不會(huì)因結(jié)構(gòu)不穩(wěn)定而受到影響［10］。該算法基本實(shí)現(xiàn)過(guò)程為：

1）初始化種群。

2）適應(yīng)度函數(shù)選擇。個(gè)體的適應(yīng)度函數(shù)表示為F(x)，F(xiàn)(x)是由相應(yīng)的目標(biāo)函數(shù)進(jìn)行適當(dāng)變換得到。

3）變異。利用高斯變異算子進(jìn)行變異，個(gè)體變異是唯一的最優(yōu)搜索操作，這也是進(jìn)化規(guī)劃算法的特點(diǎn)。

4）選擇。進(jìn)化規(guī)劃算法采用一種隨機(jī)q競(jìng)爭(zhēng)選擇方式，即會(huì)從N個(gè)父代和N個(gè)子代組成的集合中選擇最優(yōu)的N個(gè)個(gè)體，作為下一代群體。

2.3 基于EP-FCM的聚類(lèi)算法

基于EP-FCM的聚類(lèi)算法的具體實(shí)現(xiàn)步驟如下：

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

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

步驟3 變異。利用式（11）對(duì)每個(gè)個(gè)體進(jìn)行變異操作：

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

步驟4 選擇。采用隨機(jī)q競(jìng)爭(zhēng)選擇法生成新一代個(gè)體。具體過(guò)程為：

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

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

3）H個(gè)個(gè)體逐一比較后，將分?jǐn)?shù)在前N的個(gè)體選為下一代。

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

步驟6 當(dāng)滿足停止條件時(shí)，按照式（9）再次更新聚類(lèi)中心，輸出最終解。

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

2.4 局部離群點(diǎn)檢測(cè)算法

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

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

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

1）聚類(lèi)內(nèi)至少有不包括p在內(nèi)的k個(gè)點(diǎn)a，使d(p，a) ≤d(p，o)；

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

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

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

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

如果所得局部離群因子值小于1，說(shuō)明p的密度大于其鄰域點(diǎn)密度，p為聚類(lèi)點(diǎn)；若該值接近1，p與鄰域?qū)偻痪垲?lèi)；若該值大于1，說(shuō)明p密度小于其鄰域密度，p為噪聲點(diǎn)。通過(guò)這種方式，在樣本空間數(shù)據(jù)分布不均勻的情況下也可以準(zhǔn)確發(fā)現(xiàn)離群點(diǎn)。

2.5 WE-FCM優(yōu)化算法

由于噪聲點(diǎn)的影響，F(xiàn)CM 算法所得類(lèi)中心的位置往往不在合理區(qū)域，因此本文將LOF 算法加權(quán)策略［13］與EP-FCM 結(jié)合，提出WE-FCM，克服FCM算法對(duì)噪聲點(diǎn)敏感的缺陷。

記Lp=LOFk(p)。將Lp作為動(dòng)態(tài)加權(quán)系數(shù)應(yīng)用到FCM 目標(biāo)函數(shù)及EP算法的適應(yīng)度函數(shù)中。式（5）可展成式（15）：

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

通過(guò)上述加權(quán)策略，使得算法的目標(biāo)函數(shù)在樣本密度小的區(qū)域變大，無(wú)法收斂，而在樣本密度大的區(qū)域變小，快速收斂，從而有效改善噪聲點(diǎn)對(duì)聚類(lèi)結(jié)果的影響。

算法步驟如下：

步驟1 對(duì)樣本點(diǎn)進(jìn)行預(yù)處理。

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

步驟3 用EP算法估計(jì)初值。

步驟4 將得到的初值進(jìn)行FCM 聚類(lèi)，得到混合矩陣估計(jì)值。

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 混合矩陣評(píng)價(jià)準(zhǔn)則

采用兩種性能指標(biāo)對(duì)混合矩陣進(jìn)行評(píng)價(jià)［14］，分別是：

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

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

2）偏離角度。

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

3.2 結(jié)果分析

為驗(yàn)證本文所提算法的有效性，進(jìn)行了兩個(gè)實(shí)驗(yàn)仿真，源信號(hào)為NOIZEUS語(yǔ)音庫(kù)中的信號(hào)，采樣頻率為8 kHz。

1）實(shí)驗(yàn)一：隨機(jī)取三路語(yǔ)音信號(hào)，根據(jù)式（1）將其變成兩路觀測(cè)信號(hào)。

混合矩陣A隨機(jī)確定如下：

所得的兩路觀測(cè)信號(hào)時(shí)域波形如圖1所示。

圖1 兩路觀測(cè)信號(hào)時(shí)域波形Fig.1 Time domain waveforms of two-way observation signals

由圖1 難以獲知觀測(cè)信號(hào)方向聚集性的強(qiáng)弱，需要對(duì)觀測(cè)信號(hào)進(jìn)行STFT。本文選用Hanning 窗，窗口長(zhǎng)度設(shè)定為512，疊合長(zhǎng)度為256。經(jīng)過(guò)變換后的觀測(cè)信號(hào)時(shí)頻域散點(diǎn)圖如圖2所示。

圖2 兩路觀測(cè)信號(hào)時(shí)頻域散點(diǎn)圖Fig.2 Time-frequency domain scatter plots of two-way observation signals

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

圖3 兩路觀測(cè)信號(hào)預(yù)處理后的散點(diǎn)圖Fig.3 Pre-processed scatter plots of two-way observation signals

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

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

K-means算法得到的估計(jì)矩陣為：

本文算法得到的估計(jì)矩陣為：

上述各算法所得混合矩陣估計(jì)值的性能指標(biāo)評(píng)價(jià)結(jié)果如表1所示。

表1 三路源信號(hào)時(shí)各算法性能對(duì)比Tab.1 Performance comparison of various algorithms when using three source signals

2）實(shí)驗(yàn)二：隨機(jī)取四路語(yǔ)音信號(hào)根據(jù)式（1）將其變成三路觀測(cè)信號(hào)。

混合矩陣A隨機(jī)確定如下：

所得的三路觀測(cè)信號(hào)時(shí)域波形如圖4 所示。以下各步驟操作與實(shí)驗(yàn)一相仿，其處理結(jié)果如圖5～圖6。

圖4 三路觀測(cè)信號(hào)時(shí)域波形Fig.4 Time domain waveforms of three-way observation signals

圖5 三路觀測(cè)信號(hào)時(shí)頻域散點(diǎn)圖Fig.5 Time-frequency domain scatter plots of three-way observation signals

圖6 三路觀測(cè)信號(hào)預(yù)處理后的散點(diǎn)圖Fig.6 Pre-processed scatter plots of three-way observation signals

K-means算法得到的估計(jì)矩陣為：

本文算法得到的估計(jì)矩陣為：

上述各算法所得矩陣估計(jì)值的性能指標(biāo)評(píng)價(jià)結(jié)果如表2。

表2 四路源信號(hào)時(shí)各算法性能對(duì)比Tab.2 Performance comparison of various algorithms when using four source signals

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

4 結(jié)語(yǔ)

對(duì)于FCM 算法在混合矩陣估計(jì)中存在的對(duì)初值敏感、魯棒性差、易受噪聲點(diǎn)干擾的問(wèn)題，本文提出了一種基于WEFCM 的混合矩陣估計(jì)的優(yōu)化算法。實(shí)驗(yàn)仿真結(jié)果表明，在源信號(hào)數(shù)N=3、N=4 時(shí)，本文算法在算法穩(wěn)定性及矩陣估計(jì)精度方面相較經(jīng)典的K-means、K-Hough、GAFCM、FDP-FCM 都有較大提高，對(duì)混合矩陣的估計(jì)是可行和有效的。在后續(xù)研究中，可以關(guān)注更多維數(shù)據(jù)的處理，進(jìn)一步提升算法的實(shí)用性。