基于加权改进模糊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 都有较大提高，对混合矩阵的估计是可行和有效的。在后续研究中，可以关注更多维数据的处理，进一步提升算法的实用性。