蟻群聚類的欠定盲源分離方法

王放，何選森

湖南大學 信息科學與工程學院，長沙 410082

蟻群聚類的欠定盲源分離方法

王放，何選森

湖南大學 信息科學與工程學院，長沙 410082

1 引言

盲源分離（Blind Source Separation，BSS）是數據分析及信號處理的強有力工具，在許多領域都得到廣泛的應用，如生物醫學信號處理、數據挖掘、語音信號處理、模式識別以及無線通信等[1-3]。

所謂盲分離，是指在源信號數目、位置、混合過程等先驗信息未知的情況下，僅根據傳感器信號來估計源信號。其數學模型為：

其中X(t)=[x1(t)，x2(t)，…，xm(t)]T為觀測信號向量，A為未知的m×n維混疊矩陣，S(t)=[s1(t)，s2(t)，…，sn(t)]T為源信號向量，N(t)=[n1(t)，n2(t)，…，nm(t)]T為噪聲向量。盲分離就是在A和S(t)均未知的情況下，僅由X(t)恢復出S(t)。當觀測信號個數m小于源信號個數n時，就稱之為欠定盲源分離。

對于欠定盲源分離問題，一般將求解過程分解為估計混疊矩陣A和恢復源信號S(t)兩步。第一步主要采取聚類算法估計混疊矩陣，常用的方法有：勢函數法[4]、K-均值聚類法[5]、模糊K-均值聚類[6-7]等；第二步主要是利用估計出的混疊矩陣采取線性規劃法或最短路徑法等來恢復源信號。而在兩步法中，估計混疊矩陣最為重要。Bofill等人率先提出應用勢函數的方法進行分離，但由于分離過程中參數設置缺乏理論指導，且易受實驗者主觀影響，其應用范圍有限；另一種應用較廣泛的是利用K-均值聚類算法估計混疊矩陣，但該方法需事先確定聚類數目，且估計精度有限。

本文針對上述算法的缺陷提出一種估計混疊矩陣的新方法。首先利用稀疏源信號的直線聚類特性，通過標準化將直線聚類轉變成致密聚類[8]，再采用蟻群聚類算法進行聚類搜索，根據搜索得到的聚類中心的個數得到源信號的個數，同時估計出混疊矩陣。本文的方法不需要事先確定聚類數目，就能估計出混疊矩陣；同時基于勢函數的方法在三路或三路以上觀測信號情況下是無法進行估計的，而本文的方法能有效地實現這類情況下的盲源分離。

2 蟻群聚類算法原理

螞蟻在覓食過程中會在其經過的路徑上釋放信息素，同時信息素也會隨著時間的流逝而揮發。螞蟻在運動過程中能夠感知路徑上的信息素及其強度，并傾向于朝著信息素濃度高的方向移動。因此某一路徑上經過的螞蟻越多，在該路徑上累積的信息素就越多，后來的螞蟻也更傾向于選擇該路徑，整個蟻群的行為表現出信息正反饋現象。如果將數據視為具有不同屬性的螞蟻，聚類中心是螞蟻所尋找的“食物源”，那么數據聚類過程就可以看做螞蟻尋找食物源的過程[9-10]。

假設數據對象為X={X|Xi=(xi1,xi2,…,xim),i=1,2,…,N}，設Xi與Xj之間的加權歐氏距離為dij，當螞蟻從位置i移動到位置j時，計算路徑i→j上的信息素τij[11]：

若Xi與Xj之間的加權歐氏距離dij小于或等于某一閥值r，則設定該路徑上的信息素為1，代表螞蟻會經過該路徑，否則其信息素為0。同時由于信息素的揮發，在一次搜索周期結束后，路徑上的信息素需要進行更新。設τij(t)代表第t次搜索過程中路徑i→j上的信息量，則該次搜索結束后信息素更新為[11]：

τij(t+1)=(1-ρ)τij(t)+Δτij（3）

ρ為揮發系數，Δτij為信息素的增量，其值為在該次搜索周期內所有螞蟻在該路徑上釋放的信息素的總和。在搜索周期中，螞蟻根據轉移概率進行合并，轉移概率[12]為：

其中ηij稱為能見度，大小為1/dij，α和β為調節因子，用來控制信息素和能見度的影響，S={Xs|dsj≤r，s=1，2，…，N}為可行路徑的集合。從式（4）可見轉移概率與能見度成正比，即與歐式距離成反比，也即兩數據點間距離越大，合并的概率越小。如果pij(t)大于閥值p0，則Xi與Xj合并成一類，求出各類數據的算術平均值即為各聚類中心。

3 混疊矩陣估計與信源恢復

3.1 觀測信號初始化

當源信號為稀疏信號時，混合信號具有線性聚類特性，如果忽略噪聲的影響，將式（1）展開為：

當某一時刻只有一個源信號（如只有si(t)）起作用時，上式可轉化為：

它在m維空間中是一條經過原點的直線，直線方向取決于混疊矩陣的第i個列矢量(a1i，a2i，…，ami)T。基于此，n個源信號si(t)，i∈(1，2，…，n)將確定n條直線，因此，A的估計就轉化為觀測空間中直線方向的估計。采用和文獻[4]中相同的語音數據，三路長笛聲音源信號經采樣后，左乘以隨機產生的2×3維混疊矩陣得到兩路觀測信號，混疊信號散點圖如圖1所示。

圖1 三路源信號混疊散點圖

由圖1可見，三路源信號確定了三條直線。由于三路源信號比較稀疏，所得散點圖上三條直線比較清晰，相互之間重疊干擾部分較少，當源信號不太稀疏時，可以先對源信號進行傅氏變換等使其稀疏化，然后在變換域中進行盲源分離。

3.2 估計混疊矩陣

由于n路源信號經混疊后的散點圖表現為經過原點的n條直線，同時各直線的方向對應于混疊矩陣的各列向量。通過聚類算法將觀測信號按散點圖中各直線所在方向進行分類，每一類對應一條直線，每個聚類中心表示的方向近似散點圖中一條直線的方向，即對應混疊矩陣的某個列向量，這樣通過聚類就可以獲得對混疊矩陣的估計。

本文考慮將直線聚類轉變成致密聚類，因此首先對觀測信號進行標準化處理包括尺度歸一化和方向鏡像[13]。對觀測信號X(t)的尺度歸一化為：

其中‖X(t)‖表示X(t)的Euclid范數。方向鏡像就是將下半平面向量映射到上半平面。進行標準化時，由于位于原點附近的數據點存在重疊現象或為噪聲點，可去掉這部分數據點，通過去除這部分數據可以有效降低計算量和提高估計精度。經過標準化后的觀測信號均位于上半圓周上，如圖2所示。

圖2 標準化處理后的觀測信號

標準化后的觀測數據點聚集于單位圓上形成球形簇，酷似蟻群聚集成堆。在每個數據堆中均存在某一數據點所表示的方向最能代表散點圖中對應直線的方向。因此獲得各數據堆中關鍵數據點（聚類中心）就能獲得對該直線方向的精確估計。故本文提出采用蟻群聚類算法尋找各類中心，確定源信號的個數和混疊矩陣。設標準化后的信號數據點X'(t)=[x1'(t)，x2'(t)，…，xm'(t)]T，t=1，2，…，N，將各數據點看成一只螞蟻，共有N只螞蟻，結合蟻群算法進行聚類。首先尋找初始聚類中心，計算各數據點X'(i)和X'(j)之間的加權歐氏距離dij：

其中m為信號的維數，p和pk為加權因子，因為各維數據影響力一樣，故本文中pk均取值為1。利用式（2）計算各路徑上的初始信息素τij，這樣將得到一個N×N維的初始信息素矩陣，矩陣中每個元素均為0或者1，其中值為1的元素τij代表X'(i)與X'(j)之間的加權歐氏距離dij小于或等于r。因此選擇一個適當的r值，只有屬于同一類的數據點之間的加權歐式距離才會小于或等于r，對應的τij才等于1。這樣屬于同一類的數據點，其初始信息素矩陣中所在行的所有元素必都相等。例如：假設X'(1)與X'(a)、X'(b)(a≠b≠1)屬于同一類，則除與自身外X'(1)只與X'(a)、X'(b)兩個數據點之間的歐式距離d1a、d1b小于等于r，則初始信息素矩陣中第一行所有元素中只有τ11、τ1a、τ1b三個元素為1，其余均為0；對于數據X'(a)，也只與X'(1)、X'(b)兩個數據點之間的歐式距離da1、dab小于等于r，所以初始信息素矩陣中第a行中只有τa1、τaa、τab為1，其余也均為0。這樣整個初始信息素矩陣中有第1、a、b三行元素相等，即X'(1)、X'(a)、X'(b)屬于同一類，再取這三個數據的算術平均值，即得到了第一個初始聚類中心，同理可以得到所有其他初始聚類中心。關于r的選擇，如果源信號數目較多，導致單位圓上數據點較密集，可以在第一步的標準化時將數據點歸一化到半徑大于1的圓周上，這樣數據分得較開，r可供選擇的范圍也較大。尋找到初始聚類中心后進行蟻群搜索，設尋找到的初始聚類中心為C(k)= [x1(k)，x2(k)，…，xm(k)]T，k=1，2，…，K，按式（8）計算各螞蟻到初始聚類中心的歐式距離，按式（2）計算螞蟻到各聚類中心路徑上的信息素。計算螞蟻轉移到初始聚類中心的概率：如果dij=0，則pij=1，否則根據式（4）計算pij。每只螞蟻根據計算出來的轉移概率進行合并，如果pij大于閥值p0，則X'(i)與該初始聚類中心合并成一類，并根據式（3）更新路徑上的信息素；如果pij小于p0，則讓其等待下次循環。令CJ={X'(i)|pij＞p0，i=1，2，…，N，j∈(1，2，…，K)}，CJ表示所有歸并到C(j)一類的數據集合，則理想聚類中心為：

其中X'(i)∈CJ，J為C(j)類中元素個數。計算各聚類中心的距離，如果距離小于給定的閥值r，則合并相應的兩類。重復上述過程直至達到最大迭代次數M，最后得到的聚類中心的個數就代表源信號的個數，每個聚類中心分別代表混疊矩陣的一個列向量，這樣就估計出混疊矩陣。

3.3 源信號的恢復

估計出混疊矩陣后，可通過最短路徑法進行源信號的恢復。由文獻[4]可知，稀疏信號盲分離歸結為以下優化問題：

其中σ2為噪聲的方差，第一項為重構誤差平方和，第二項為非稀疏項。在不考慮噪聲的前提下，由于混疊矩陣A已估計出來，則上式等效為：

由上式可知，每個時刻t確定一個優化問題，從而可估計出源信號。

3.4 欠定盲分離算法步驟

通過上述分析，本文的欠定盲分離算法步驟如下。

（1）對觀測信號進行標準化處理。

（2）初始化設定r、α、β、p0等參數，將每個數據點看成一只螞蟻，利用式（8）計算每只螞蟻到其他數據點間的加權歐氏距離dij，求出初始聚類中心。

（3）計算每只螞蟻到初始聚類中心的加權歐氏距離。

（4）計算各螞蟻到初始聚類中心路徑上的信息量τij和轉移概率pij。

（5）如果pij≥p0成立，則合并螞蟻到該初始聚類中心，并更新信息素矩陣。

（6）根據式（9）計算各聚類中心Cˉ。

（7）計算各聚類中心間的距離，如果距離小于給定的閥值r，則合并聚類重新計算各聚類中心，否則返回到（3）重新計算。

（8）循環迭代直至最大次數，輸出聚類個數和各自聚類中心。

（9）利用求出的聚類中心即對應混疊矩陣A，采用最短路徑法恢復源信號。

當存在多路觀測信號時，同樣可以采用上述算法思想，在多維空間中進行聚類估計。標準化后的觀測信號數據點在多維空間中聚集成堆，然后進行蟻群聚類。

4 仿真實驗及分析

實驗仿真均在Matlab 7.0環境下進行，實驗數據采用和文獻[4]中相同的語音數據。為了檢驗對混疊矩陣的估計精度，采用角度偏差進行測算[14]：

表1 三種方法的a和的角度偏差比較表

表1 三種方法的a和的角度偏差比較表

a1與a1 ^ a2與a2 ^ a3與a3 ^ K-均值法勢函數法本文算法0.731 7 0.367 6 0.137 3 1.065 1 1.161 3 0.337 6 0.921 8 1.233 0 0.321 4

對比實驗表明本文算法有更高的估計精度。源信號與恢復后的信號之間的相關系數，如表2所示。

表2 源信號與恢復后信號之間的相關系數表

從表2看出每行每列有且只有一個元素接近1，其余均接近0，說明恢復信號和源信號之間相似度高，應用本文算法估計恢復出源信號效果比較理想。源信號以及恢復后的信號如圖3、4所示。

由圖看出本文算法能比較精確恢復出源信號。調用Matlab函數wavwrite（）將恢復后的源信號保存成.wav文件。通過試聽恢復后的語音信號，本文方法較上文其他兩種方法所恢復的信號，語音清晰度得到較好的提高，連貫性得到改善，能清晰分辨出3個長笛聲音，試聽效果很接近于源信號。

實驗2 m=3，n=4，即三路觀測信號，四路源信號的情況。隨機產生混疊矩陣：

信號散點圖以及歸一化處理后，見圖5、6。

圖3 三路源信號

圖4 三路恢復信號

圖5 四路源信號三路觀測信號散點圖

同實驗1設定相同的r、α、β、p0等參數，通過本文算法得到混疊矩陣的估計為：

由此計算出來的角度偏差如表3。

圖6 混疊信號歸一化到上半單位球

表3 原混疊矩陣與估計的混疊矩陣的角度偏差表

可以看出混疊矩陣各列向量之間的角度偏差均很小，混疊矩陣的估計精度較高。圖7、8給出了源信號以及恢復的源信號，對比可以看出四路源信號得到精確分離，實際試聽效果較好，有效實現了存在多路觀測信號情況下的盲源分離。

圖7 四路源信號

圖8 四路恢復信號

5 結論

本文提出了一種估計欠定盲源分離混疊矩陣的新方法，結合蟻群聚類算法，解決了源信號數目未知情況下的盲源分離問題，并且該方法適合于存在多個觀測信號的情況。實驗結果表明了本文方法的可行性與有效性。

[1]Cardoso J F.Blind signal separation：statistical principles[J]. Proc of IEEE：Special Issue on Blind Identification and Estimation，1998，90（10）：2009-2026.

[2]趙敏，謝勝利，肖明.欠定和非完全稀疏的盲源恢復[J].華南理工大學學報，2010，38（6）：19-23.

[3]Theis F J，Jung A，Puntonet C G，et al.Linear geometric ICA：fundamentals and algorithms[J].Neural Computation，2003，15：419-439.

[4]Bofill P，Zibulevsky M.Underdetermined blind source separation using sparse representations[J].Signal Process，2001，81（11）：2353-2362.

[5]Li Y，Andrzej C，Amari S.Analysis of sparse representation and blind source separation[J].Neural Computation，2004，16（6）：1193-1234.

[6]Sun T Y，Lan L E，Liu C C，et al.Mixing matrix identification for underdetermined blind signal separation：using hough transformandfuzzyk-meansclustering[C]//Proceedingsof IEEE International Conf on Systems，Man and Cybernetics，2009：1621-1626.

[7]Tan Beihai，Yang Zuyuan，Zhang Yuanjian.An underdetermined blind separation algorithm based on fuzzy clustering[C]//Proceedings of the 3rd International Conference on Innovative Computing Information and Control，Dalian，Liaoning，China，2008：404-408.

[8]王詠平，高俊.未知數量稀疏源的盲分離方法[J].華中科技大學學報，2007，35（12）：46-49.

[9]Dorigo M，Blum C.Ant colony optimization theory：a survey[J]. Theoretical Computer Science，2005，344：243-278.

[10]Colomi A，Dorigo M，Maniezzo V.Distributed optimization by ant colonies[C]//Proceedings of European Conference on Artificial Life.Paris，France：Elsevier，1991：134-142.

[11]Han Yanfang，Shi Pengfei.An improved ant colony algorithm for fuzzy clustering in image segmentation[J].Neurocomputing，2007，70：665-671.

[12]Marco D，Gianni D C，Luca M G.Ant algorithms for discrete optimization[J].Artificial Life，1999，5（2）：137-172.

[13]He Zhaoshui，Xie Shengli，Fu Yuli.Sparse representation and blind source separation of ill-posed mixtures[J].Science in China：Series F Information Sciences，2006，49（5）：639-652.

[14]譚北海，謝勝利.基于源信號數目估計的欠定盲分離[J].電子與信息學報，2008，30（4）：863-867.

WANG Fang,HE Xuansen

College of Information Science and Engineering,Hunan University,Changsha 410082,China

Taking advantage of the straight line clustering of the sparse source signals in underdetermined blind separation,a method of the mixing matrix estimation is proposed.The aliasing signals are standardized and the aliasing signals are formed spherical cluster,so the linear cluster is turned into density cluster.And then the clustering center is searched and obtained by using the ant clustering algorithm.The aliasing matrix and the source signals are accurately evaluated.The proposed algorithm can separate the source signals in which the number is unknown and it is also effective to separate three or more observed signals. The simulation results of speech signals show that this method can precisely separate and restore the original signals.

underdetermined blind separation;ant colony clustering;aliasing matrix

利用欠定盲源分離情況下稀疏源信號具有直線聚類的特點，提出了一種估計混疊矩陣的新方法。通過對混疊信號進行標準化處理，使混疊信號形成球形簇，將線性聚類轉變成致密聚類；利用蟻群聚類算法對其進行搜索得到聚類中心，從而獲得對混疊矩陣的精確估計。該方法能實現源信號數目未知情況下的欠定盲源分離，且能推廣到三路或更多路觀測信號的情況。對語音信號的仿真結果證明，該方法能精確地分離和恢復原始信號。

欠定盲分離；蟻群聚類；混疊矩陣

A

TN911.7

10.3778/j.issn.1002-8331.1110-0350

WANG Fang,HE Xuansen.Underdetermined blind separation based on ant colony clustering.Computer Engineering and Applications,2013,49（13）：211-215.

王放（1985—），男，碩士研究生，研究領域為盲源分離，隨機信號處理；何選森（1958—），男，副教授，研究領域為隨機信號處理，盲源分離，信息安全技術。E-mail：wangfang4227@163.com

2011-10-18

2012-01-02

1002-8331（2013）13-0211-05

CNKI出版日期：2012-03-21http://www.cnki.net/kcms/detail/11.2127.TP.20120321.1734.013.html

◎工程與應用◎