摘要
针对欠定盲源分离问题, 提出了增强信号稀疏性的方法,并把具有噪声的基于密度空间聚类与寻找密度峰值聚类相结合用于估计混合矩阵。首先,把时域观测信号变换成时频域的稀疏信号,通过单源点检测突出信号的线性聚类特性,并采用镜像映射将线性聚类转变成致密聚类以便于进行密度基的聚类分析;然后,利用密度空间聚类搜寻密集数据堆中高密度的点和与之相应的邻域,以自动形成聚类簇的数量和初步聚类中心;最后,把获得的聚类数量作为密度峰值聚类的输入参数,在数据簇的范围内搜索其密度峰值以实现对聚类中心位置的进一步修正。以上方法不仅可提高混合矩阵的估计精度,而且估计量具有较高的一致性。
在信源和传输信道均未知的情况下,仅利用传感器采集获得的观测信号来分离信源的过程称为盲源分离(Blind source separation, BSS
近些年,利用群体智能算法解决UBSS问题成为国内外学者的研究热点,主要包括蚁群优化算
对于时域BSS模型x(t)=As(t),两边取短时傅里叶变换(Short⁃time Fourier transform, STFT),则
(1) |
式中:X(t, k)=[X1(t, k), X2(t, k), …, XN(t, k)
对于任意一个时频点(t, k),观测信号X(t, k)的实部和虚部分别为
; | (2) |
这二者之间的夹角θ为
(3) |
如果信源各分量的实部与虚部之比是相等的,即满足以下关系
(4) |
则它们之间的夹角θ=0°或θ=π(180°)。这时,就称该时频点(t, k)是SSP。
在实际应用中,恒等式(4)成立的条件是很苛刻的。为此可采用另一个判断条
(5) |
式中:|z|表示z的绝对值,而||Z||=(
通过SSP检测之后,由于剔除了MSP,则观测信号的数据分布凸显出了明确的方向性。由所有SSP的数据点组成的集合记为Xssp。
一般地,经过原点的直线方向可以被两个方向相反的向量来表示。例如,在三维空间中同一条直线可被方向向量(1, 1, 1)或(-1, -1, -1)来描述。为了用唯一的方向向量描述直线,采用镜像映
(6) |
从式(6)可知,镜像映射是把线性聚类转换成致密聚类,便于利用基于密度聚类方法搜索到密集数据堆中的关键数据点(聚类中心)。该数据点的方向就是稀疏信号线性聚类的直线方向,即混合矩阵的列向量。因此,通过对数据
在众多聚类方法中,DBSCAN作为基于密度聚类的典型代表,能够在有噪声的数据中发现各种形状和各种大小的数据簇。DBSCAN的核心思想是在数据堆中找到密度较高的数据点,再通过搜索邻近的其他高密度数据点,逐步将高密度数据点连成一片,从而生成各种形状的数据簇。
DBSCAN算法是利用参数(eps, MinPts)来描述邻域的样本分布紧密程度。首先,以每个数据点为圆心,以邻域eps为半径画个圆圈,落在该圈内的数据点数就是该点的密度值。然后,利用密度阈值MinPts判断数据点的密度级别,若圆圈内数据点数小于MinPts,则其圆心的数据点是低密度点,而点数大于或等于MinPts的圆心数据点为高密度点(核心点Core point)。若某个低密度数据点落在高密度点的圆圈内,则把低密度点连到最邻近的高密度点上,并称它为高密度点的边界点。不在任何高密度点圈内的低密度点为异常点(噪声)。
若某个样本点y在点x的eps邻域内,且x为核心点,则称y从x直接密度可达。假设给定一连串数据样本点x1, x2, …, xn且x=x1, y=xn,若xi+1从xi (i∈[1, n])直接密度可达,则称y从x密度可达。对于样本点xi和xj,若存在核心点xk,使xi和xj都可以由xk密度可达,则称样本点xi和xj密度相连。由密度可达关系得到的最大密度相连的样本集合,即为聚类分析最终得到的一个类别(簇)。
DBSCAN 的聚类效果取决于参数eps和MinPts的选取。MinPts的选取原则是:MinPts≥D+1,其中D为待聚类数据的维度;一般地,MinPts必须选择大于等于3的值。参数eps的选择也要适中:若eps值太小,会造成大部分数据不能聚类;若eps值过大,会使多个数据簇被合并到同一个簇中。eps选择可通过绘制K⁃距离曲线来实现,在曲线的明显拐点位置对应于合适的eps参数值。
与传统的K⁃均值聚类相比,DBSCAN算法的优势主要体现在: (1)可以对任意形状的稠密数据集进行聚类,而K⁃均值仅适用于凸数据集; (2)可以自动获得聚类的数量,而K⁃均值需事先给定聚类数; (3)在聚类的同时还能找出异常(噪声)点; (4)聚类的结果没有偏移,而K⁃均值的初始值对聚类结果影响很大。
然而,由于使用全局的密度阈值参数MinPts, DBSCAN只能发现密度值不少于MinPts的数据点所组成的簇,而很难发现不同密度的数据簇。为此,本文采用可视化的CFSFDP算法对DBSCAN产生的初步聚类中心进行修正,以提高关键数据的定位精度。CFSFDP的基本思想是:由于每个数据簇都有一个最大密度的数据点作为簇中心,在它的周围都是密度比它低的数据点;使得不同的数据簇的中心相距较远,从而可区分出不同密度的数据簇。显然,CFSFDP弥补了DBSCAN算法仅适合于稠密数据集的缺陷。
假设观测数据集为X={xi|i=1, 2, …, n},数据点xi和xj之间距离为dij=dist(xi, xj),该距离可以采用欧氏距离、马氏距离、汉明距离和曼哈顿距离等。对于数据集X中的任何点xi,定义它的两个基本属性:局部密度ρi以及它与最近的高密度数据点的距离δi。ρi的计算方式有两种: Cut⁃off kernel和Gaussian kernel,其中Cut⁃off kernel方式的计算公式
(7) |
而χ函数定义为
(8) |
参数dc>0为截断距离,需要用户提前设置,且CFSFDP算法对截断距离不敏感。由定义式(7)可以看出,局部密度ρi是数据集X中与xi之间距离小于dc的数据点的个数。
局部密度ρi的Gaussian kernel方式的计算式
(9) |
比较定义式(7)和式(9)可知, Cut⁃off kernel方式的计算结果为离散值, Gaussian kernel方式的计算结果为连续值。因此,在Gaussian kernel的结果中,发生不同数据点具有相同局部密度值的概率会更小。
设qi(i=1,2,…,n)是ρi(i=1,2,…,n)的一个降序排列的序列,即,则点qi与高密度数据点的距离定义
(10) |
显然,δi表示数据集X中任一点xi和所有局部密度大于它密度的点之间的最小距离;当xi的局部密度是最大时,δi是其他所有聚类中最大的一个。局部密度最大的点一定也是一个数据簇的聚类中心。
对数据集X中每个点xi,计算出二元对(ρi, δi),以ρi为横坐标,δi为纵坐标画出(ρi, δi)的决策图,在该图中,同时具有较大ρi和δi值的数据点会脱颖而出,这些点就可以看作是聚类中心;而ρi值很小且δi值很大的数据点就是离群点。显然,利用决策图确定聚类中心属于定性分析而非定量分析,需要人为干预。为了减少人为因素的影响,定义一个综合考虑ρi与δi值的量
(11) |
ξi的值越大,则所对应的数据点xi越有可能是聚类中心。
CFSFDP算法中截断距离dc的确定方法如下。分配给每个点的平均邻居数量约为数据点总数的1%~2%,所谓邻居就是指某点在dc距离范围内的数据点。对数据集X中每个点,它与其他的n-1个点都有一个距离,总共有n(n-1)个距离。因为每个点对应的距离都被计算了两次,因此这些距离有一半是重复的。为此,把距离dij(i<j)按升序排列为d1≤d2≤…≤dM。若取dc=dk(k=1,2,…,M),则在所有n(n-1)个距离中,小于dc的距离所占的比例约为t=k/M,即大约有(k/M)n(n-1)个距离小于dc。比值t就是选取参数dc的重要指标。
参数dc值的选取决定着CFSFDP的聚类效果。若dc值过大,会使每个数据点的ρi值都很大,导致聚类的区分度不高;在极端情况下dc=dM,则所有的数据点都归属于一个簇。若dc值太小,同一聚类中就可能被拆分成多个簇;在极端的情况下dc<d1,则每一个数据点都单独成为一个簇。选取dc值是依赖于具体问题的。通过采取比例值t来确定参数dc的策略,可降低对具体问题的依赖性。
从以上分析可知,DBSCAN是单独以密度为指标选择聚类的类别,而CFSFDP综合考虑了密度和距离两个指标作为选择聚类的类别。因此,CFSFDP能够区分出两个密度值很接近的不同的两个聚类。在利用聚类分析估计混合矩阵过程中,本文首先把计算得到的ξi(i=1, 2, …, n)值按降序排列,然后从大到小截取由算法DBSCAN得到聚类中心数量相对应的ξi值的数据点作为聚类中心。这意味着,把DBSCAN获得的聚类数量作为CFSFDP的输入参数,通过CFSFDP进一步搜索密度峰值以修正DBSCAN的聚类中心位置;同时DBSCAN也弥补了CFSFDP需要人为干预的不足,使两种算法扬长补短,得到最佳的组合。
本文方法的基本流程如

图1 本文提出方法的基本流程图
Fig.1 Basic flow chart of the proposed method
在利用聚类方法获得混合矩阵的估计之后,采用最短路径方
为了验证本文方法的有效性,在混合矩阵估计和信源分离两个方面进行仿真测试。特别地,把K⁃means算
仿真的PC平台: Intel(R) Celeron(R) 1007U⁃1.5 GHz的CPU, 4 GB内存,操作系统Windows 10,所有仿真都是运行在MATLAB 9(R2016a)上。用于测试的信源为SixFlutes数据

图2 6路音乐源信号的时域波形
Fig.2 Time domain waveforms of six music source signals
为了测试算法对混合矩阵的估计精度,采用角度偏
(12) |
式中:a为原始混合矩阵A的列向量, b为估计出混合矩阵B的列向量, 〈a,b〉表示向量a与b的内积。如果角度偏差d(a,b)的值越小,说明混合矩阵的估计精度越高。另外,采用均方误差(Mean square error, MSE)作为测度混合矩阵估计的另一个技术指标,表达式为
(13) |
式中:ak为原始混合矩阵A的第k个列向量, bk为估计出混合矩阵B的第k个列向量, ak和bk都是归一化的向量。ak和bk的方向越接近,其|a
在混合矩阵被估计出来之后,利用最短路径法即可分离(恢复)源信号。为了度量原始的信源与估计的信源之间的相似性,采用相关系
(14) |
式中:si(t)为时域中第i个信源, rj(t)为时域中第j个恢复的信源, T为时域中信号的样本数。如果恢复的信源与原始的信源越相似,其相关系数ρii就越接近于1或-1,而ρij (i≠j)越接近于0。
在下面的仿真中,首先在时域中把6个信源随机地混合成3路观测信号;然后利用STFT把时域信号变换到时频域中进行混合矩阵的估计,在进行STFT操作时,利用Hanning窗截断来实现对信号的分帧,每一帧的长度为L=8 192,两个连续帧的重叠率为60%;最后将恢复出的源信号通过逆STFT再变换到时域中,在时域中进行相关系数的计算。这里对STFT的参数选择说明如下。对于音频信号的处理,一般来说是需要进行分帧的;为了避免信号所含信息的损失,要求连续两帧之间的样本要重叠。由于每个信号的样本长度为65 536,要将信号分成整数帧(一般为2的整数次幂,本文取
仿真中,混合矩阵是利用MATLAB命令A=rand(3, 6)随机产生,即
3路观测信号x(t)=[x1(t), x2(t), x3(t)

图3 3路观测信号的时域波形
Fig.3 Time domain waveforms of three observed signals

图4 3路观测信号的时域散点图
Fig.4 Time domain scatter plot of three observed signals

图5 3路观测信号的时频域散点图
Fig.5 Time⁃frequency domain scatter plot of three observed signals
从

图6 经SSP检测后观测信号的散点图
Fig.6 Scatter plot of observed signals after SSP detection
为了应用密度基的聚类算法对观测数据进行分析,本文通过镜像映射方式(归一化处理)把线性聚类的数据Xssp转变为致密聚类的数据

图7 经过归一化处理后观测信号的散点图
Fig.7 Scatter plot of observed signals after normalization
从
在利用数据集
经过本文方法、K⁃means算法和HC算法估计出的混合矩阵(记作B1,B2,B3)分别为
把原始混合矩阵A和各种方法估计得到的混合矩阵Bk (k=1, 2, 3)中各列向量代入到角度偏差d(a,b)和均方误差MSE的定义式中,计算得到结果如
方法 | 角度偏差 | 均方误差 | |||||
---|---|---|---|---|---|---|---|
第1列 | 第2列 | 第3列 | 第4列 | 第5列 | 第6列 | ||
K⁃means | 2.363 8 | 0.057 5 | 71.692 0 | 0.549 6 | 0.081 7 | 0.199 9 | -16.481 3 |
HC | 2.363 8 | 0.057 5 | 63.274 3 | 0.549 6 | 0.146 5 | 0.014 0 | -15.962 4 |
本文算法 | 0.026 9 | 0.027 5 | 0.028 0 | 0.205 1 | 0.014 0 | 0.012 6 | -46.404 0 |
由
本文方法在获得混合矩阵之后,利用最短路径
在以上的仿真中,仅仅做了一次实验。为了进一步测试各种算法对欠定混合矩阵的平均估计性能,在下面的仿真中,对类似的实验反复进行了15次。
在每次实验中,首先利用MATLAB函数rand(3, 6)随机地生成一个3×6的混合矩阵A从而得到时域观测信号x(t)=As(t);然后通过STFT把时域信号转换成时频域的信号X(t, k),并对其进行SSP检测和归一化处理,得到观测信号
方法 | 角度偏差 | 均方误差 | |||||
---|---|---|---|---|---|---|---|
第1列 | 第2列 | 第3列 | 第4列 | 第5列 | 第6列 | ||
K⁃means | 0.624 4 | 0.121 6 | 10.954 1 | 13.757 6 | 5.610 1 | 0.561 9 | -36.799 5 |
HC | 3.096 5 | 0.567 4 | 14.059 0 | 11.740 1 | 18.043 4 | 0.515 8 | -27.954 7 |
本文算法 | 0.018 5 | 0.023 3 | 0.069 8 | 0.380 7 | 0.027 1 | 0.019 0 | -46.683 5 |
从
在重复进行的15次实验中,对3种方法估计的混合矩阵,利用最短路径法分离(恢复)出信源,并对3种不同的方法,分别计算出每个源信号与对应的恢复信号的相似度。

图8 每次实验中3种方法估计的信号相关系数
Fig.8 Signal correlative coefficients estimated by three methods in each experiment
从
从以上的实验结果可以看出,本文提出的算法具有较好的欠定混合矩阵的估计性能。而算法在对噪声、信源相关性及欠定程度的适应性方面,具有以下的特性。
(1) 在实际应用中,利用传感器采集信源的过程,不可避免地会使观测信号中包含有噪声。在UBSS中,噪声分为传感器噪声和信号源噪声两类,一般的BSS模型考虑的是传感器噪
(2) 盲信源分离的主要方法是独立分量分析(Independent component analysis, ICA
(3) 对于欠定盲信源分离问题,传感器数量决定了BSS的欠定程度。本文算法的仿真实验中,在信源数量为6的情况下,分别取传感器数量为4, 3, 2, 1进行了相应的实验。在传感器为4, 3, 2这3种环境下算法对混合矩阵的估计均取得很好的性能。而当传感器数量为1时,即单通道UBSS,本文算法对混合矩阵的估计性能急剧下降,恢复的信源产生了较大的误差。因此,本文算法对欠定程度的容忍度是要求最少有2个传感器。
(4) 盲源分离中的信源一般是非高斯分布。在实际应用中,所遇到的非高斯信源,根据信号的峭度值可分为亚高斯信源和超高斯信源。本文讨论的音频信号属于典型的超高斯信源,而一些图像信号可能属于亚高斯信源。本文的BSS算法既可以分离超高斯信源,也可以分离亚高斯信源。对于属于亚高斯的图像信号盲分离应用,在文献[
本文基于稀疏信号的UBSS问题,首先研究了增强信号稀疏性的方法,利用STFT把观测信号从时域变换到时频域,并采用SSP检测剔除多源点数据,通过镜像映射把稀疏信号的直线聚类转变成致密聚类;然后,采用聚类分析的方法在密集的数据堆中寻找代表其方向的关键数据。为了克服K⁃means算法需要预先设置聚类数目的缺点,本文采用DBSCAN算法实现对数据的自动分类从而得到源信号数目以及初始的聚类中心;在此基础上,利用CFSFDP算法对DBSCAN获得的聚类中心进一步进行修正,以提高混合矩阵的估计精度。由于把DBSCAN的聚类数量作为CFSFDP的输入参数,也克服了CFSFDP需要人为干预的缺陷。
参考文献
Comon P, Jutten C. Handbook of blind source separation: Independent component analysis and applications [M]. Oxford, UK: Academic, 2010.
Adalı T, Jutten C, Yeredor A, et al. Source separation and applications [J]. IEEE Signal Processing Magazine, 2014, 31(3): 16⁃17.
Bofill P, Zibulevsky M. Underdetermined blind source separation using sparse representations [J]. Signal Processing, 2001, 81: 2353⁃2362.
He Xuansen, Wang Fang, Cai Wenbiao, et al. Ant colony clustering algorithm for underdetermined BSS [J]. Chinese Journal of Electronics, 2013, 22(2): 319⁃324.
张伟灿, 何选森. 基于改进蜂群聚类的欠定盲源分离 [J]. 计算机工程与应用, 2018, 54(17): 243⁃248.
Zhang Weican, He Xuansen. Underdetermined blind source separation based on improved bee colony clustering [J]. Computer Engineering and Application, 2018, 54(17): 243⁃248.
苏彬, 苏皓然, 刘肖. 基于粒子群算法的欠定盲源分离方法改进 [J]. 科学技术与工程, 2018, 18(15): 123⁃128.
Su Bin, Su Haoran, Liu Xiao. The improved underdetermined blind source separation based on particle swarm optimization [J]. Science Technology and Engineering, 2018, 18(15): 123⁃128.
马欢, 江桦. 改进的粒子滤波单通道盲分离算法 [J]. 数据采集与处理, 2016, 31(5): 1051⁃1058.
Ma Huan, Jiang Hua. Improved single⁃channel blind separation algorithm based on particle filtering [J]. Journal of Data Acquisition and Processing, 2016, 31(5): 1051⁃1058.
赵知劲, 吴棫. 利用粒子流滤波的单通道BPSK信号盲分离算法 [J]. 数据采集与处理, 2018, 33(3): 409⁃415.
Zhao Zhijin, Wu Yu. Blind separation algorithm of single channel BPSK signal using particle flow filtering [J]. Journal of Data Acquisition and Processing, 2018, 33(3): 409⁃415.
Murata N, Koyama S, Takamune N, et al. Spares representation using multidimensional mixed⁃norm penalty with application to sound field decomposition [J]. IEEE Transactions on Signal Processing, 2018, 66(12): 3327⁃3338.
Feng Fangchen, Kowalski M. Underdetermined reverberant blind source separation: Sparse approaches for multiplicative and convolutive narrowband approximation[J]. IEEE Transactions on Audio, Speech, and Language Processing, 2019, 27(2): 442⁃456.
He Xuansen, He Fan, Cai Weihua. Underdetermined BSS based on K⁃means and AP clustering [J]. Circuits, Systems, and Signal Processing, 2016, 35(8): 2881⁃2913.
Chowdhury K, Chaudhuri D, Pal A K, et al. Seed selection algorithm through K⁃means on optimal number of clusters [J]. Multimedia Tools and Application, 2019: 10.1007/s11042⁃018⁃7100⁃4.
Vera E, Lucio D, Fernandes L A F, et al. Hough transform for real⁃time plane detection in depth images [J]. Pattern Recognition Letters, 2018, 103: 8⁃15.
付宁, 彭喜元. K⁃Hough欠定盲信道估计算法 [J]. 电子测量与仪器学报, 2008, 22(5): 63⁃67.
Fu Ning, Peng Xiyuan. K⁃Hough underdetermined blind mixing model recovery algorithm [J]. Journal of Electronic Measurement and Instrument, 2008, 22(5): 63⁃67.
Sun Jiedi, Li Yuxia, Wen Jiangtao, et al. Novel mixing matrix estimation approach in underdetermined blind source separation [J]. Neurocomputing, 2016, 173(3): 623⁃632.
Chen Yewang, Tang Shengyu, Bouguila N, et al. A fast clustering algorithm based on pruning unnecessary distance computation in DBSCAN for high⁃dimensional data [J]. Pattern Recognition, 2018, 83: 375⁃387.
Rodriguez A, Laio A. Clustering by fast search and find of density peaks [J]. Science, 2014, 344(6191): 1492⁃1496.
Kim S G, Yoo C D. Underdetermined blind source separation based on subspace representation [J]. IEEE Transactions on Signal Processing, 2009, 57(7): 2604⁃2614.
Neamatollahi P, Abrishami S, Naghibzadeh M, et al. Hierarchical clustering⁃task scheduling policy in cluster⁃based wireless sensor networks [J]. IEEE Transactions on Industrial Informatics, 2018, 14(5): 1876⁃1886.
He Xuansen, Zhu Tao. ICA of noisy music audio mixtures based on iterative shrinkage denoising and fast ICA using rational nonlinearities [J]. Circuits, Systems, and Signal Processing, 2014, 33(6): 1917⁃1956.
蔡伟华, 何选森. 基于UWT和独立分量分析的含噪盲源分离 [J]. 计算机工程与应用, 2016, 52(16): 180⁃185.
Cai Weihua, He Xuansen. Noisy blind source separation based on undecimated wavelet transform and independent component analysis [J]. Computer Engineering and Application, 2016, 52(16): 180⁃185.
陈梦, 何选森. 基于八阶收敛牛顿迭代的Fast⁃ICA改进算法 [J]. 计算机工程与应用, 2017, 53(11): 178⁃181.
Chen Meng, He Xuansen. Improved fast⁃ICA algorithm based on eighth⁃order convergence of Newton’s iterative method [J]. Computer Engineering and Application, 2017, 53(11): 178⁃181.