基于改進(jìn)DBSCAN算法估計(jì)欠定混合矩陣的應(yīng)用研究

王霖郁，夏 敏，項(xiàng)建弘

（1.哈爾濱工程大學(xué)信息與通信學(xué)院，哈爾濱150001；2.哈爾濱工程大學(xué)先進(jìn)船舶通信與信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，哈爾濱150001）

引 言

欠定盲源分離（Underdetermined blind source separation，UBSS）［1］是盲源分離技術(shù)中最接近實(shí)際運(yùn)用的一種情況，其源信號的個(gè)數(shù)要多于觀測信號的個(gè)數(shù)，使得信號分離更加艱難，因而成為盲源分離領(lǐng)域的主要研究熱點(diǎn)和難點(diǎn)。目前UBSS大多數(shù)是在稀疏成分分析（Sparse component analysis，SCA）的基礎(chǔ)上進(jìn)行研究，其主要內(nèi)容分別為混合矩陣估計(jì)和源信號恢復(fù)。其中，混合矩陣估計(jì)的精度將直接影響源信號估計(jì)階段的最終效果。傳統(tǒng)聚類算法需要預(yù)先知道聚類中心的數(shù)量，并且具有對噪聲點(diǎn)和初始聚類中心敏感的問題，因而克服這一問題的基于密度的空間聚類（Density based spatial clustering of applications with noise，DBSCAN）［2］算法成為了研究混合矩陣估計(jì)的熱門方法之一。

針對數(shù)據(jù)分布不均勻的情況，利用基于分區(qū)DBSCAN算法處理高維數(shù)據(jù)和密度分布不均勻的集群，并在數(shù)據(jù)預(yù)處理階段，利用改進(jìn)的蟻群算法（Ant colony optimization，ACO）算法克服了對初始參數(shù)敏感的缺點(diǎn)，提升了算法的聚類效果［3］。針對DBSCAN算法魯棒性較差的問題，對信號進(jìn)行聚類分析來確定源信號的數(shù)目和數(shù)據(jù)分類，然后將分類后的數(shù)據(jù)利用Hough變換計(jì)算聚類中心，從而提高混合矩陣估計(jì)的精確度［4］。布谷鳥搜索算法（Cuckoo search，CS）［5］是一種模擬布谷鳥寄生在其他鳥類巢穴的育雛行為和Levy飛行策略的智能搜索算法［6］。針對CS算法穩(wěn)定性差的問題，提出一種基于自適應(yīng)參數(shù)調(diào)整的CS算法以加快算法向最優(yōu)解收斂［7］。為了解決CS算法全局搜索能力差的問題，引入了與差分進(jìn)化（Differential evolution，DE）算法相似的變異策略，通過步長參數(shù)的自適應(yīng)調(diào)整有效增強(qiáng)CS算法的搜索能力［8］。

稀疏信號進(jìn)行單源點(diǎn)檢測，得到信號的線性聚類特征，增強(qiáng)時(shí)頻域信號的稀疏性并濾除低能量點(diǎn)。通過歸一化處理將數(shù)據(jù)的線性聚類轉(zhuǎn)化為密度聚類，然后利用DBSCAN算法分析估計(jì)聚類中心的數(shù)目并進(jìn)一步濾除干擾點(diǎn)，得到初始的聚類中心。為了進(jìn)一步解決聚類中心求解易陷入局部最優(yōu)的問題，在DBSCAN基礎(chǔ)上提出布谷鳥自適應(yīng)搜索群優(yōu)化算法，將粒子群算法的向群體學(xué)習(xí)思想與CS算法的Levy飛行策略相結(jié)合，尋找最優(yōu)解；CS算法具有良好的全局搜索能力，使算法能夠順利脫離局部最優(yōu)。然而，算法迭代階段后期的局部搜索不夠詳細(xì)，導(dǎo)致算法精度降低。在CS算法的位置迭代過程中引入粒子群算法（Particle swarm optimization，PSO）算法的群體學(xué)習(xí)思想，提高算法對最優(yōu)解的精細(xì)搜索能力，避免了對最優(yōu)解的盲目搜索；然后將布谷鳥自適應(yīng)搜索群優(yōu)化算法（Cuckoo adaptive search swarm optimization，CASSO）引入DBSCAN聚類算法的聚類中心，可以有效地解決其易陷入局部最優(yōu)的問題，更準(zhǔn)確地估計(jì)欠定混合矩陣。

1 欠定盲源分離模型

UBSS的主要內(nèi)容是在發(fā)送端的源信號及其在傳輸信道中的混合模式都不知道的情況下，僅依靠接收端的觀測信號來重構(gòu)源信號并估計(jì)混合矩陣，其數(shù)學(xué)模型為

式 中：x(t)=[x1(t)，x2(t)，…，xm(t)]T為m路 觀 測 信 號；s(t)=[s1(t)，s2(t)，…，sn(t)]T為n路 源 信號；A∈Rm×n為m×n(m

稀疏分量分析對信號的稀疏性要求較高，其稀疏程度能夠直接影響混合矩陣的估計(jì)效果［10］。在實(shí)際情況中，需要將時(shí)域中大部分不稀疏的信號進(jìn)行短時(shí)傅里葉變換（Short time Fourier transform，STFT），得到強(qiáng)稀疏的時(shí)頻域信號［11］。若信號在時(shí)頻域中某一采樣時(shí)刻只有一個(gè)源信號起著主導(dǎo)作用，將式（1）進(jìn)行STFT變換，可以得到如下時(shí)頻域表達(dá)式為

式 中：X(t，f)=[X1(t，f)，X2(t，f)，…，XM(t，f)]為 觀 測 信 號 在 時(shí) 頻 點(diǎn)(t，f)的STFT復(fù) 數(shù) 系 數(shù)，S(t，f)=[S1(t，f)，S2(t，f)，…，SN(t，f)]為源信號在時(shí)頻點(diǎn)(t，f)的STFT復(fù)數(shù)系數(shù)，an為混合矩陣A的第n個(gè)列向量。將式（2）進(jìn)行STFT變換，可得

為了提高信號的稀疏性，可以通過單源點(diǎn)（Single source point，SSP）檢測法去除偏離規(guī)定范圍時(shí)頻點(diǎn)和防止噪聲造成的小能量點(diǎn)。判斷某一時(shí)頻點(diǎn)(t，f)是否為單源點(diǎn)的條件為：觀測信號向量在某一時(shí)頻點(diǎn)(t，f)上的實(shí)部與虛部之間夾角的絕對值必須小于閾值Δθ，其判斷公式為

式中：|·|為絕對值；‖·‖為模長。

在時(shí)頻域中，稀疏數(shù)據(jù)將分布在若干條穿過原點(diǎn)的直線及其周圍，利用相關(guān)的聚類算法確定直線的方向向量就能實(shí)現(xiàn)對混合矩陣列向量的估計(jì)［12］。然后將數(shù)據(jù)進(jìn)一步處理，通過歸一化的方法將數(shù)據(jù)的線性聚類特征轉(zhuǎn)變?yōu)閱挝粓A（或單位球）正方向上的密度聚類特征。

2 改進(jìn)的DBSCAN算法

2.1 DBSCAN算法

DBSCAN算法利用空間中數(shù)據(jù)分布的緊密性進(jìn)行劃分，濾除噪聲點(diǎn)和密度連通域外的點(diǎn)［13］。此算法主要有兩個(gè)影響因素：聚類半徑Eps和最小聚類數(shù)目Mpts，并且其參數(shù)值全局唯一確定［14］，相關(guān)定義如下：

（1）以數(shù)據(jù)集D中任意一點(diǎn)p為球心，以Eps為半徑的區(qū)域叫作點(diǎn)p的Eps鄰域。

（2）若點(diǎn)p的鄰域內(nèi)含有超過Mpts個(gè)數(shù)據(jù)點(diǎn)，那么則稱p為核心對象。

（3）如果一個(gè)點(diǎn)q在p的Eps鄰域，并且p假如是核心對象。則目標(biāo)點(diǎn)q對目標(biāo)點(diǎn)p密度直達(dá)。

（4）假設(shè)數(shù)據(jù)集D中有n個(gè)樣本序列p1，p2，…，pn，并且，p1=p，pn=q，i=1，2，…，n-1，如果pi與pi+1密度直達(dá)，則根據(jù)傳遞關(guān)系，p和q密度可達(dá)。

（5）在數(shù)據(jù)集D中，若存在數(shù)據(jù)點(diǎn)o對p和q都是密度可達(dá)，則稱點(diǎn)p和點(diǎn)q是密度相連。

（6）給定Eps和Mpts，所有滿足密度可達(dá)和密度相連的數(shù)據(jù)點(diǎn)劃分成一個(gè)聚類。不滿足以上所有條件的點(diǎn)叫作干擾點(diǎn)。

DBSCAN算法流程如下：

（1）初始化參數(shù)：聚類半徑Eps，最小聚類數(shù)目Mpts，數(shù)據(jù)集D；

（2）隨機(jī)選取點(diǎn)p，根據(jù)Mpts判斷是否為核心對象；

（3）若p是核心對象，則在p的Eps鄰域內(nèi)找到與其密度直達(dá)的點(diǎn)形成一個(gè)類；

（4）若p不是核心對象，則判定為干擾點(diǎn)，退出循環(huán)；

（5）將所有樣本點(diǎn)都進(jìn)行篩選；

（6）若算法滿足迭代要求，則輸出聚類結(jié)果，反之重復(fù)步驟（3～6）。

2.2 基于CASSO優(yōu)化的DBSCAN算法

在欠定盲源分離的混合矩陣估計(jì)中，利用DBSCAN算法根據(jù)空間的緊密程度劃分?jǐn)?shù)據(jù)并進(jìn)一步篩除干擾點(diǎn)，得到分類后的聚類數(shù)目。利用分類后的數(shù)據(jù)計(jì)算聚類中心，但是此單一方法的聚類中心求解易陷入局部最優(yōu)解，得到的混合矩陣估計(jì)精度不高。針對這一問題，本文提出了CASSO優(yōu)化DBSCAN算法對聚類中心進(jìn)行估計(jì)，得到的混合矩陣更接近原混合矩陣。

CASSO基本思想是利用PSO算法向群體學(xué)習(xí)思想［15］對CS算法中的鳥巢位置更新（式（6））進(jìn)行優(yōu)化，改進(jìn)后的位置更新公式如式（7）所示，鳥巢前期的位置更新主要是Levy飛行機(jī)制占主導(dǎo)作用。隨著群體學(xué)習(xí)能力(Pg-xi(t))逐漸占據(jù)主導(dǎo)地位，使得算法后期在最優(yōu)解附近區(qū)域來回搜尋，實(shí)現(xiàn)算法的局部精細(xì)尋優(yōu)。為了提高算法的優(yōu)化效果并將其應(yīng)用到混合矩陣估計(jì)的聚類分析中，本文在算法迭代過程中，將固定發(fā)現(xiàn)概率進(jìn)行自適應(yīng)調(diào)節(jié)，加快了算法的收斂速度，定義公式為

式中：Pamin與Pamax分別代表最小發(fā)現(xiàn)概率值與最大發(fā)現(xiàn)概率值；t為當(dāng)前迭代次數(shù)；T為設(shè)定的最大迭代次數(shù)。在算法的前期迭代過程中，為了使算法盡快向最優(yōu)解收斂，可以在廣泛的搜索范圍內(nèi)加快大部分鳥窩被丟棄的概率；當(dāng)進(jìn)入后期的迭代過程時(shí)，解的搜尋范圍逐漸減小，使得剩余的少量解更接近最優(yōu)解。此時(shí)，可以以較小的概率找到鳥巢，更加有效地保留算法的最優(yōu)解，從而提高算法的整體優(yōu)化效率。

CS算法的鳥窩更新如下

式中：a為步長因子，一般令a=1；“⊕”表示點(diǎn)乘；xi(t)表示第i個(gè)鳥窩在第t次迭代中的位置；L(λ)表示服從Levy分布的隨機(jī)性搜尋路線，即L(s，λ)=s-λ，1<λ≤3。

在鳥窩位置更新式（7）的基礎(chǔ)上改進(jìn)得到

式中：i=1，2，…，n（n為鳥窩數(shù)量）；t為當(dāng)前迭代次數(shù)；T為設(shè)定的最大迭代次數(shù)；Pg表示所有鳥窩的最好位置。

DBSCAN算法主要通過密度連通的概念將數(shù)據(jù)劃分類別，并利用同類中的數(shù)據(jù)點(diǎn)到聚類中心的歐式距離來修正聚類中心，該算法的目標(biāo)適應(yīng)度函數(shù)公式為

式中：N為信號的個(gè)數(shù)；C為信號的維度；為第i點(diǎn)到第j個(gè)聚類中心的歐式距離。

CS算法和CASSO算法的目標(biāo)適應(yīng)度函數(shù)進(jìn)化曲線分別如圖1和圖2所示。通過多次實(shí)驗(yàn)仿真得到，當(dāng)最大迭代次數(shù)Miter=100時(shí)，CASSO算法相比于CS算法能夠更快地達(dá)到預(yù)先設(shè)定的適應(yīng)度函數(shù)閾值e=10-6，且CASSO算法在優(yōu)化DBSCAN算法的聚類中心求解過程中能夠更快地收斂，使得算法后期在最優(yōu)解附近區(qū)域來回搜尋，實(shí)現(xiàn)算法的局部精細(xì)尋優(yōu)。使得解更趨近于最優(yōu)解，提升混合矩陣估計(jì)精度，算法詳細(xì)流程如圖3所示。

圖1 CS算法目標(biāo)適應(yīng)度進(jìn)化曲線圖Fig.1 CS algorithm target fitness evolution figure

圖2 CASSO算法目標(biāo)適應(yīng)度進(jìn)化曲線圖Fig.2 CASSO algorithm target fitness evolution figure

圖3 本文算法流程圖Fig.3 Flow chart of the proposed algorithm

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

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

（1）歸一化均方誤差

式中：a?ij為估計(jì)出的混合矩陣元素；aij為原混合矩陣元素。NMSE越小，效果越好。

（2）偏離角度

3.2 實(shí)驗(yàn)仿真與分析

為了證明本文算法是否可行，下面在MATLAB R2018b環(huán)境下進(jìn)行兩組實(shí)驗(yàn)仿真。將該算法與基于遺傳模擬退火優(yōu)化模糊C均值聚類算法（Simulated annealing genetic algorithm of fuzzy C-means，SAGAFCM）算法、PSO-Kmeans算法、DBSCAN聚類和層次聚類（Hierarchical clustering，HC）算法進(jìn)行對比，得到實(shí)驗(yàn)數(shù)據(jù)并分析，本文實(shí)驗(yàn)語音數(shù)據(jù)來自CMU（卡耐基梅隆大學(xué)）開源語音包。

假設(shè)實(shí)驗(yàn)將4路語音信號通過混合矩陣A進(jìn)行混合得到2路觀測信號，其中采樣頻率f=16 kHz，選取的混合矩陣A為

4路源信號如圖4所示。

圖4 4路源信號Fig.4 Four-channel source signals

2路觀測信號如圖5所示。在信號預(yù)處理階段，為了使信號盡可能的稀疏化，選用窗口長度K=512的Hanning窗，將時(shí)域信號進(jìn)行STFT變換得到時(shí)頻域散點(diǎn)圖，如圖6所示。對數(shù)據(jù)進(jìn)行單源點(diǎn)（Single source point，SSP）檢測使其更加稀疏，取Δθ=0.8°，然后再通過歸一化處理得到如圖7所示的具有致密特性的數(shù)據(jù)。

圖5 2路觀測信號Fig.5 Two-channel observation signals

圖6 4路語音信號STFT變換后散點(diǎn)圖Fig.6 Scatter diagram of four-channel speech signals after STFT transformation

圖7 單源點(diǎn)檢測并歸一化后散點(diǎn)圖Fig.7 Scatter diagram after single source point detection and normalization

3.2.1 混合矩陣估計(jì)算法精度對比

實(shí)驗(yàn)參數(shù)：最大迭代次數(shù)Miter=100，適應(yīng)度函數(shù)閾值e=10-4，為了盡可能符合實(shí)際應(yīng)用，在仿真時(shí)加入加性高斯白噪聲（Additive white Gaussian noise，AWGN），信噪比為SNR=20 dB。鳥巢數(shù)量為N=100，Eps=0.4，Mpts=10，發(fā)現(xiàn)概率的最大值和最小值分別為Pamax=0.75和Pamin=0.1。幾種聚類算法分別估計(jì)結(jié)果如下：

（1）HC算法估計(jì)的混合矩陣

（2）PSO-Kmeans算法估計(jì)的混合矩陣

（3）DBSCAN算法估計(jì)的混合矩陣

（4）SAGAFCM算法估計(jì)的混合矩陣

（5）本文算法估計(jì)的混合矩陣

將原始混合矩陣A與各種聚類算法估計(jì)出來的混合矩陣中各列向量代入和NMSE的定義式中，計(jì)算結(jié)果如表1所示。由表1數(shù)據(jù)可以看出，在歸一化均方誤差方面，本文算法相比HC、PSOKmeans，DBSCAN和較先進(jìn)的SAGAFCM，NMSE值最小，這說明該算法估計(jì)出的效果最好，誤差值最?。辉谄x角度方面，本文算法相較于其他4種聚類算法，估計(jì)出的與A各個(gè)列向量之間的平均偏離角度值最小，其中HC算法的平均偏離角度達(dá)到了0.815 5，而本文算法計(jì)算出來的平均角度偏差只有0.168 3，證明了算法的有效性和準(zhǔn)確性。

表1 5種方法的偏離角度和NMSETable 1 Deviation angle and NMSE of five methods

由上面5種算法得到的NMSE和平均偏離角度數(shù)據(jù)可知：傳統(tǒng)的HC算法的混合矩陣估計(jì)精度最低；PSO-Kmeans算法的估計(jì)精度雖然有所提升，但是效果不是很明顯；利用遺傳模擬退火算法優(yōu)化FCM算法能夠明顯改善估計(jì)精度；但是這3種算法必須預(yù)先確定源信號的個(gè)數(shù)。而DBSCAN算法則可以克服這一缺點(diǎn)但精度較低，所以本文提出了基于CASSO優(yōu)化的DBSCAN聚類算法，且估計(jì)出的精確度更高，算法性能更優(yōu)。

3.2.2 不同SNR條件下的算法精度對比

在不同信噪比的條件下，將本文算法與HC、PSO-Kmeans、DBSCAN和SAGAFCM進(jìn)行比較。因?yàn)閷?shí)際環(huán)境中，噪聲是無法避免的，所以驗(yàn)證在有噪聲條件下的混合矩陣的估計(jì)更加符合實(shí)際情況，對算法來說也是一種挑戰(zhàn)。本次實(shí)驗(yàn)方案為在5～25 dB的加性高斯白噪聲條件下，進(jìn)行100次的蒙特卡洛獨(dú)立實(shí)驗(yàn)來求歸一化均方誤差值。由圖8的數(shù)據(jù)對比可知，本文算法與其他4種混合矩陣估計(jì)算法相比，在不同信噪比的情況下得到的歸一化均方誤差值都是最低的，并且在低SNR的情況下具有較好的效果，進(jìn)一步證明了算法的有效性。由圖8可以看出，隨著SNR的不斷增大，NMSE值不斷減小，即混合矩陣估計(jì)算法的精度也不斷提升。這是因?yàn)椋涸诘蚐NR的情況下，由于噪聲大幅度地增加，混合矩陣的各項(xiàng)指標(biāo)都在下降，所以此時(shí)的估計(jì)精度也下降了很多，沒有辦法達(dá)到一個(gè)好的估計(jì)精度；在高SNR的情況下，由于大部分的時(shí)頻點(diǎn)擾動相對較小，使得聚類算法估計(jì)的聚類中心更加準(zhǔn)確，因此，在高SNR條件下可以很好地估計(jì)混合矩陣的估計(jì)精度。

圖8 5種算法不同信噪比下的NMSE對比圖Fig.8 NMSE comparison of five algorithms with different SNRs

4 結(jié)束語

混合矩陣估計(jì)是UBSS技術(shù)中必不可少的部分，也是源信號能否成功分離的前提。由于DBSCAN算法估計(jì)聚類中心過程容易陷入局部最優(yōu)解，使得混合矩陣估計(jì)效果降低。針對此問題，在DBSCAN的基礎(chǔ)上提出一種布谷鳥自適應(yīng)搜索群優(yōu)化算法。該算法將PSO算法中的群體學(xué)習(xí)思想與CS算法中Levy飛行策略相結(jié)合進(jìn)行尋優(yōu)并進(jìn)行參數(shù)調(diào)整，使得CASSO算法在后期迭代過程中大幅度提升了局部精細(xì)搜索能力。為了進(jìn)一步調(diào)整CASSO算法的動態(tài)適應(yīng)性，對發(fā)現(xiàn)概率進(jìn)行自適應(yīng)調(diào)節(jié)，加快了算法向最優(yōu)解收斂的速度，有效地改善了DBSCAN算法在估計(jì)聚類中心時(shí)易陷入局部最優(yōu)的問題。由兩組仿真實(shí)驗(yàn)數(shù)據(jù)對比表明，所提算法可以有效地改善混合矩陣估計(jì)精度和魯棒性低的問題。后續(xù)將對智能語音分離技術(shù)進(jìn)行更深層次的研究。