Degeneration Characters of Heterogeneous-interdependent Network and Key Node Identification
-
摘要: 针对传统复杂网络理论通常以同质单层网络作为研究对象，忽视现有工业复杂网络具有多异质节点与多层网络互耦合性的问题，提出异质依存网络（Heterogeneous-interdependent network，HI net）理论及其关键节点辨识方法.以含多类型节点的异质依存网络作为研究对象，分析异质节点依存关系以及网络衰退机理.构建分块结构下异质节点依存矩阵，将多层异质依存网络归并于单层网络.提出节点效用耦合系数，描述不同故障类型下邻居节点效用耦合性.建立节点邻域效用耦合系数计算方法及其影响力传播方法，识别节点对网络状态的影响，实现关键节点识别.通过对典型的含多电源电网系统与电力信息物理异质依存网络进行仿真实验，分别验证了所提方法对不同故障类型下关键节点识别的有效性.Abstract: In order to solve the problem that traditional complex network theory usually takes homogeneous single-layer network as research object, and neglects mutual coupling relations among heterogeneous nodes or multi-layer networks in industrial complex networks, the heterogeneous-interdependent network (HI net) theory with key node identification method is proposed. Taking the HI net with multi types of nodes as the object, we study the dependency relations of nodes and the mechanism of network degeneration. Then, the dependency matrix of heterogeneous nodes is established to combine the multi-layer HI networks into one layer. To describe the effectiveness coupling for neighboring node under different fault mode, the effectiveness coupling coefficient is designed. Finally, the effectiveness coupling coefficient of neighborhood nodes and its propagation method are given to calculate the influence from node to networks to identify the key nodes in HI net. The effectiveness of the key nodes identification method is verified by the simulations of two typical HI nets, including the power system with multi generations and power-information HI net.
-
观测空间中的数据达到上千维甚至上万维时,巨大的数据计算量对计算系统来说是一个挑战.对图像、音频、视频和网络搜索来说,通过降低数据维度来提高处理速度显得尤为重要.
为解决"维数灾难"问题,许多文献假设数据具有低维的固有属性(例如:低秩、稀疏性、低维流形),然后根据这些假设建立各种不同的模型.一个简单有效的假设是:观测数据落在一个低维流形子空间中.基于这样的假设,利用PCA (Principle component analysis)、LDA (Linear discriminant analysis)、ICA (Independent component analysis)、 LPP (Locality preserving projection)等不同的线性降维算法,对高维空间做线性投影处理,以得到数据所在的子空间[1].另一方面,非线性降维算法(例如ISOMAP (Isometric mapping)、 LLE (Locally linear embedding))在降维处理中,可保留数据的非线性几何结构[1].
上述两类算法侧重于挖掘和发现原始数据在低维空间中的内在属性,而对数据的恢复能力仍有待改进.压缩感知 (Compressed sensing,CS)算法的出现,使得我们能从更低的采样信号中(低于奈奎斯特采样率)较好地恢复原始信号[2].
CS在减少观测次数来表示一个有限维向量 $x \in {\bf R}^m$ 的同时,更加注重于原始信号 $x$ 的稀疏性.假设 $y = \Phi x$ ,其中 $\Phi \in {\bf R}^{d \times m},d \ll m$ 是观测到的信号,由于观测矩阵 $\Phi$ 的行数小于列数,通过观测信号 $y$ 来获取原始信号 $x$ 是不适定的反问题.但是如果信号 $x$ 在给定的字典 $D$ 下足够稀疏,那么在一定的条件下,只要维数 $d$ 不低于某个限定值,观测信号 $y$ 可以唯一重构 $x$ [3-4].求解原始信号 $x$ 在字典 $D$ 下的稀疏表示 $\alpha$ 的过程可表述为
$ \alpha^* = \arg\min \limits_{\alpha} \{ ||y-\Phi D \alpha||^2_F + \lambda ||\alpha||_1 \} $
(1) 我们认为 $x=D\alpha + \varepsilon$ ,其中 $\varepsilon$ 是高斯白噪声, $\alpha$ 是 $x$ 在 $D$ 下的稀疏表示.大多数图像、语音等自然信号,在某些字典下都有很好的稀疏性.
式(1)所表达的稀疏编码框架具有很强的鲁棒重建能力,并且在数据压缩、超分辨率重建、去噪、分类等领域成功应用.一方面,任务驱动的数据降维方法认为特定的任务(如图像识别、数据可视化等)需要特定的降维方法将数据从高维降至低维,因此提取的特征也不一样.文献[5-7]认为在稀疏域中,信号的几何关系是一种有效的结构信息.文献[5]通过字典学习,得到原始信号的稀疏表示系数 $\alpha$ ,利用 $\alpha$ 的几何结构信息,建立一个通用有效的框架来解决不同任务的字典学习问题.类似地,文献[6]依据 $\alpha$ 的几何结构信息,直接利用PCA作用于稀疏系数 $\alpha$ 上,实现数据降维.文献[7]有针对性地保留稀疏域中信号间的内积关系,通过学习得到原始信号到降维信号的线性投影来完成数据降维.另一方面,数据驱动的数据降维方法采用将CS框架与高斯随机投影结合的框架.文献[8]利用高斯随机矩阵将原始特征映射到观测空间,证明在低维空间中并没有发生重大的信息丢失,并给出结论:低维空间的特征保留了原始信号的主要信息.类似地,文献[9-12]假设信号是在一个嵌入高维空间的低维流形中,因此在降维的过程中,一些重要的几何信息(例如:角度、距离)得以保留.文献[13]认为通过学习得到的观测矩阵比随机投影更加有效.上述基于CS框架的方法都必须服从RIP (Restricted isometry property)条件,这对于数据降维中的可视化(2D或者3D)来说是不适合的.而且,虽然文献[9-12, 14]给出了将CS框架搭建在流形上的理论分析,但是实际可行的算法很少.
上述工作都是基于一个先验给定的字典 $D$ ,不需要学习字典.更进一步的研究认为:在采样和重建的过程中不需要知道字典 $D$ 的先验知识,而是从训练样本中学习字典(本文称为"在数据降维中的字典学习方法").盲压缩感知是这个框架下一个典型的例子,在严格的条件下,字典 $D$ 可以通过低维的观测值训练学习而来[15-16].文献[17-20]认为高维信号 $X$ 与低维信号 $Y$ 之间,在字典 $D_x$ 和 $D_y$ 下共同享有稀疏表示系数.字典对 $D_x$ 和 $D_y$ 是分别对应高维数据 $x$ 和降维数据 $y$ 的高维字典和低维字典,是从数据降维过程中学习而来的.
本文结合降维算法中保留数据结构特征和CS算法中数据恢复能力的优点,提出聚能量字典学习(Concentrated dictionary learning,CDL)算法. CDL算法既能够在CS中RIP下界的维数限制之外具有一定的信号重建能力,又结合了流形的特点,在降维后的空间中保留原始信号中的特征(例如:内积、距离、夹角)[21].并且,利用训练得到的字典,仿照 CS算法设计算法框架.为验证算法的有效性,将CDL与CS+K-SVD (K-means-singular value decomposition)[22-23]等算法进行数据恢复对比实验,结果表明本文算法相比传统算法有明显的提升.同时,进行了图像数据的3维观测性实验,本文算法表现良好.在噪声污染严重的图像压缩实验中,本文算法相对于 JPEG2000,也具有一定程度的优势.
其余章节安排如下:第1节回顾CS算法及K-SVD字典训练算法.第2节阐述本文字典学习算法推导及思路,对于内积、距离、夹角特征推导出字典对 $D$ 和 $P$ 的具体形式.第3节进行图像重构、3D可视化和图像压缩的对比实验.最后,总结全文,讨论本文算法的应用拓展性.
1. CS及字典学习回顾
本文算法基于CS算法框架,下面对CS算法框架进行简要的回顾. CS算法框架如图 1所示, $X$ 为原始信号, $Y$ 是观测值, $\Phi$ 是观测矩阵, $\alpha$ 是稀疏表示系数, $D$ 是字典.典型的CS算法选取 $\Phi$ 为高斯随机矩阵, $\Phi : {\bf R}^m\rightarrow {\bf R}^d,d \ll m,y=\Phi x$ ;字典 $D$ 由标准正交基组成,如小波基、离散余弦变换(Discrete cosine transform,DCT)字典).
CS通过正交匹配追踪算法(Orthogonal matching pursuit,OMP)[4, 24-25]解决如式(2)的最优化问题得到稀疏系数 $\alpha$ ,最后由字典 $D$ 恢复原始信号 $x$ : $x=D\alpha$ .
$ \nonumber \min ||\alpha_0||_0 \\ {\rm s. t.}\quad ||y-\Phi D \alpha||<\varepsilon $
(2) 其中, $\varepsilon \in {\bf R}^+$ .在此过程中,低维观测值 $y \in {\bf R}^d$ 的维数 $d$ 受到一定条件的限制: $d>{\rm O}(Cs{\rm log}({k}/{s}))$ ,其中, $C$ 为常数, $C\in(0,1)$ , $s$ 是稀疏系数的稀疏性, $k$ 是字典的原子的个数,这种限制被称为RIP条件[3-4].一旦采样信号 $y$ 的维数低于 $d$ ,那么就无法从 $y$ 中恢复原始信号 $x$ ,或者恢复的效果很差.例如,如果需要同时将数据可视化(二维或三维)和信号恢复作为目标,那么传统的CS算法远远满足不了实际需求.
在CS算法框架中所用到的字典往往是给定的正交基字典.不同于给定字典的思路,K-SVD算法提供了很好的字典学习方法[22-23].从训练集中训练学习得到的字典比给定的正交基字典表现更加出色,通过字典 $D$ 能够得到最佳的稀疏系数.它的优势主要表现在:
1) 灵活性:能够与任何的匹配追踪算法相结合,确保所选的匹配追踪算法能够适合于所要求的时间限制;
2) 有效性: K-SVD算法复杂度低,具有高效性和快速收敛性,更新字典原子和稀疏表示系数是同时进行的.
2. CDL算法
以CS框架为基础,利用K-SVD字典算法的优点,本文提出基于字典学习的信号降维和重建算法.该算法可在RIP条件的限制之外具有一定的信号重建能力,即能够从较低维的观测值中恢复出原始信号.
$ X \rightleftharpoons{D}{} \alpha \rightleftharpoons{P(\alpha,y)}{Y} $
(3) 原始信号 $x$ 可看作是高维稀疏系数 $\alpha$ 通过字典 $D$ ,在低维子空间中的一种表现形式.不同于观测矩阵 $\Phi$ 的做法,本文直接将稀疏系数 $\alpha$ 通过映射函数 $P(\alpha,y)$ 投影到另一低维子空间 $y$ 中,如式(3)所示.那么信号 $x$ 与 $y$ 之间的映射关系 $F(x,y)$ 就可以通过稀疏系数 $\alpha$ 搭建桥梁,建立模型.理论证明该做法具有保留几何结构特性的作用[21].
为了得到映射函数 $P(\alpha,y)$ ,可简单地认为 $\alpha$ 到 $y$ 的投影是通过一个矩阵 $P$ 来实现的.而矩阵 $P$ 是通过字典 $D$ 获取的.那么式(3)可以转为如下表达形式:
$ X \rightleftharpoons{D}{} \alpha \rightleftharpoons{P=g(D)}{Y} $
(4) 假设已知 $P$ 与 $D$ 的关系,那么 $x$ 到 $y$ 的映射函数 $F(x,y)$ 也就确定下来.在本文中,仅考虑 $x$ 和 $y$ 之间的关系有:内积、距离、夹角.那么 $x$ 到 $y$ 的降维算法就转换为字典 $D$ 到 $P$ 的函数关系,如式(5)所示.
$ F(x,y):D \xrightarrow{g(D,P)} P $
(5) 设 $X=[x_1,x_2,\cdots,x_n]\in {\bf R}^{m\times n}$ 表示高维空间中 ${\bf R}^m$ 的 $n$ 个输入信号.给定字典 $D$ , $\alpha=[\alpha _1,\alpha _2,\cdots ,\alpha _n]\in {\bf R}^{k \times n}$ 是 $X$ 在字典 $D$ 下的 $n$ 个稀疏表示系数.给定映射函数 $F(x,y)$ , $Y=[y_1,y_2,\cdots,y_n]\in {\bf R}^d$ 是低维空间中的特征.那么通过稀疏系数 $\alpha$ 搭建的桥梁,( $X,Y$ )可以表示为如下形式:
$ \left\{ \begin{array}{ll} x=D\alpha + \varepsilon _1\\ y=P\alpha + \varepsilon _2\\ \end{array} \right. $
(6) 其中,噪声 $\varepsilon _1 \in {\bf R}^m,\varepsilon _2 \in {\bf R}^d$ .
2.1 内积关系
当期望 $X$ 内部 $x_i$ 与 $x_j$ 之间的内积关系能在 $Y$ 中保留下来时,定义 $f(x_i,x_j;y_i,y_j)=y_i^{\rm T} y_j - x_i^{\rm T} x_j$ .将式(6)带入其中,得到关于 $P$ 的最优化问题:
$ P := \min \frac{1}{n^2} \sum\nolimits_{i,j}^n f^2(x_i,x_j;y_i,y_j) $
(7) 为了解决上述最优化问题,定义核函数:
$ K_x(i,j) = x_i^{\rm T} x_j=(D\alpha_i +\varepsilon_{1,i})^{\rm T} (D\alpha _j + \varepsilon _{1,j}) $
(8) $ K_y(i,j) = x_i^{\rm T} x_j = (P\alpha_i +\varepsilon_{2,i})^{\rm T} (P\alpha _j + \varepsilon _{2,j}) $
(9) 那么 $f^2(x_i,x_j;y_i,y_j)$ 的表示如下:
$ f^2(x_i,x_j;y_i,y_j) = (y_i^{\rm T} y_j - x_i^{\rm T} x_j)^2 =\notag\\ \qquad (K_y(i,j) - K_x(i,j))^2 =\notag \qquad ((\alpha_i^{\rm T} (D^{\rm T} D - P^{\rm T} P) \alpha_j) +\notag\\ \qquad (\alpha_i^{\rm T} (D^{\rm T} \varepsilon _{1,j} - P^{\rm T} \varepsilon _{2,j}) +\notag\\ \qquad(D^{\rm T} \varepsilon _{1,i} - P^{\rm T} \varepsilon _{2,i})^{\rm T} + (\varepsilon _{1,i} \varepsilon _{1,j} - \varepsilon _{2,i} \varepsilon _{2,j}))^2 $
(10) 假设 $(x_i,x_j)$ 和 $(y_i,y_j)$ 内部相互独立,那么:
$ f^2(x_i,x_j;y_i,y_j) = (y_i^{\rm T} y_j - x_i^{\rm T} x_j)^2\approx \notag\\ \qquad((\alpha_i^{\rm T} (D^{\rm T} D - P^{\rm T} P) \alpha_j)+\notag\\ \qquad 2 \alpha_i^{\rm T} (\sigma_1 D^{\rm T} D - \sigma_2 P^{\rm T} P) \alpha_j +\notag\\ \qquad(\alpha_i^{\rm T} (\sigma_1^2 D^{\rm T} D - \sigma_2^2P^{\rm T} P) \alpha_j)^2 \approx\notag\\ \qquad(\alpha_i^{\rm T} ((1+\sigma_1^{\rm T}) D^{\rm T} D - (1+\sigma_2^2) P^{\rm T} P) \alpha_j))^2 $
(11) 其中, $\sigma_1,\sigma_2$ 为 $\varepsilon_1,\varepsilon_2$ 的方差,由式(11),式(7)最终转化为求解下式:
$ \min \limits_{P}||(1+\sigma_1^2) D^{\rm T} D - (1+\sigma_1^2) P^{\rm T} P||_F^2 $
(12) 2.2 距离关系
同样地,若期望在 $Y$ 中保留 $X$ 内部 $x_i$ 与 $x_j$ 之间的距离关系,定义 $d_x(i,j)=||x_i-x_j||_F^2$ , $d_y(i,j)=||y_i-y_j||_F^2$ ,将 $f(x_i,x_j;y_i,y_j)$ 写成如下形式:
$ f(x_i,x_j;y_i,y_j) = d_x(i,j) - d_y(i,j) $
(13) 同样地,将式(6)带入式(13)得到一个关于 $P$ 的最优化问题:
$ \begin{split} P := \min \frac{1}{n^2} \sum\limits_{i,j}^n (d_x(i,j)-d_y(i,j))^2 =\\ \quad \min \frac{1}{n^2} \sum\limits_{i,j}^n f^2(x_i,x_j;y_i,y_j) +\\ \quad \frac{1}{n} \sum\limits_{i}^n h^2(x_i;y_i) \end{split} $
(14) 上式中第二部分 $h^2(x_i;y_i)$ 推导如下:
$ \begin{split} h^2(x_i;y_i)= \\ \quad(x_i^{\rm T} x_i - y_i^{\rm T} y_i)^2 \approx\\ \quad ((\alpha_i^{\rm T}(D^{\rm T} D - P^{\rm T} P) \alpha _i) + 2\alpha_i^{\rm T}(\sigma_1 D^{\rm T} D -\\ \quad\sigma_2 P^{\rm T} P)\alpha_i + \alpha_i^{\rm T}(\sigma_1 D^{\rm T} D - \sigma_2 P^{\rm T} P)\alpha_i)^2 \approx\\ \quad ((\alpha_i^{\rm T} (1 + \sigma_1^2)D^{\rm T} D - (1 + \sigma_2^2 P^{\rm T} P) \alpha _i)^2 \end{split} $
(15) 可以看出,得到的结果与内积关系式(12)相同.
2.3 夹角关系
定义 $X$ 和 $Y$ 内部的夹角关系为
$ \begin{split} \theta_{x_i,x_j} = \cos^{-1}\left( \frac{\langle x_i,x_j\rangle}{||x_i||_2 \cdot ||x_j||_2}\right) \approx\\ \quad {\rm cos}^{-1} ((x_i + \varepsilon_{1,i})^{\rm T} + x_j + \varepsilon_{1,j})) \end{split} $
(16) 事实上,在处理数据集时,常常将数据集归一化,即: $||x_i||_2=1$ .可以看出夹角关系与内积关系是相似的.
2.4 理论推导
从内积、距离、夹角关系中可看出,需要解决如下问题:
$ \min \limits_{P} ||(1+\sigma_1^2)D^{\rm T} D - (1 + \sigma_2^2)P^{\rm T} P||_F^2 $
(17) 将上式重写为
$ \min \limits_{P} \sum_{1\leq i,j \leq k,i\neq j} \left(d_i^{\rm T} d_j - \sqrt{\frac{1+\sigma_1^2}{1+\sigma_2^2}} p_i^{\rm T} p_j\right)^2 $
(18) 通过求解式(17)得到的特征 $Y$ 的维数可以比CS算法更低,因此该算法框架可在CS算法的RIP限制之外具有恢复信号的能力[25].
由式(18),可认为字典 $P$ 是字典 $D$ 的PCA降维,不妨假设:
$ P=A^{\rm T} D $
(19) 当字典维数较低时,DCT及K-SVD字典在降维后,无法保留较多的主成分.因此,本文通过训练字典,使得能量聚集于较低的维度内(见图 4),保留较多的主成分,以满足式(19)的需求.
图 4 不同字典奇异值的分布 (当选取90%主成分 $(t_d=0.9)$ 时, 图中的点代表所需的字典维数. DCT字典: 207, K-SVD字典: 148, CDL字典: 16Fig. 4 Distribution of singular values from different dictionaries (When selecting 90% component of dictionaries $(t_d=0.9)$ , the dots represent the required dimensions for different dictionaries. DCT: 207, K-SVD: 148, CDL: 16)文献[25]中提到 $D$ 与 $P$ 是具有如下条件的矩阵:
$ \sum {\rm diag}\{D^{\rm T} D\} = \sum {\rm diag}\{P^{\rm T} P\} = k $
(20) 且
$ \sum_i \sigma_i^2 = k $
(21) 式(21)说明,奇异值分解中的 $\Theta$ 总能量是保持不变的,如果 $\Theta$ 中靠后的( $m-d$ )个奇异值越小,那么前 $d$ 个奇异值越大.因此,为了使字典 $D$ 前 $d$ 维聚集更多的能量,应满足下述条件:
1) 原始信号 $X$ 在字典 $D$ 下表示系数足够稀疏;
2) 给定正整数 $q$ ,当 $d<q$ 时, $D$ 的奇异值分解: $D=U\Theta V^{\rm T}$ 中,关于奇异值 $\Theta $ 有:
$ \frac{\sum\nolimits _i (\Theta _d)}{\sum\nolimits _i (\Theta )} \geq t_d $
(22) 其中, $\Theta _d$ 是奇异值 $\Theta $ 取前 $d$ 行 $d$ 列, $t_d$ 是设定的主成分阈值.
3) 为了保证 $D$ 的满秩性,要求奇异值 $\Theta$ 后 $m-d$ 个奇异值很小却非零.
当 $D$ 满足上述条件时,字典 $P$ 可以保留字典 $D$ 中较多的主成分.设 $D$ 的奇异值分解为
$ D=U\Theta V^{\rm T} = \begin{bmatrix} U_d U_r \end{bmatrix} \begin{bmatrix} \Theta _d 0 \\ 0 \Theta _r \end{bmatrix} \begin{bmatrix} V_d V_r \end{bmatrix}^{\rm T} \\ D^{\rm T} D = V\Theta ^{\rm T} \Theta V^{\rm T} $
(24) 式(19)中,取 $A = U_d$ ,则有:
$ \hat{P} = U_d^{\rm T} U \Theta V^{\rm T} = \Theta_d V_d^{\rm T} $
(25) 式(25)中,如果能够保证 $\Theta_d$ 足够大,即:
$ \sum {\rm diag}\{\hat{P}^{\rm T} \hat{P}\} \approx k $
(26) 那么式(18)的最优解就是 $\hat{P}$ .
2.5 字典训练
通过上述分析,明确训练字典 $D$ 的两个目标:
1) 字典 $D$ 要使得测试图像在该字典下的表示系数足够稀疏.
2) 对字典 $D$ 作奇异值分解: $D=U\Theta V^{\rm T}$ .将分为两部分,并且 $\Theta_d$ 足够大, 而 $\Theta_r$ 足够小,但是又不为0 (保证 $D$ 的满秩性).
为了达到上述目标,利用式(25)的性质,令:
$ D^{\rm T} D = u \Lambda v^{\rm T} $
(27) 其中
$ \Lambda = \begin{pmatrix} \Lambda_d&0 \\ 0&\Lambda_r \end{pmatrix} $
(28) 令
$ \hat{\Lambda}_d = \frac{\Lambda_d}{||\Lambda_d||} \cdot k \cdot t_d,\hat{\Lambda}_r = \frac{\Lambda_r}{||\Lambda_r||} \cdot k \cdot (1-t_d) $
(29) 更新奇异值分解: $D=U\Theta V^{\rm T}$ 中 $\Theta $ :
$ \hat{\Theta } = \begin{pmatrix} \sqrt{\hat{\Lambda}_d}&0 \\ 0 & \sqrt{\hat{\Lambda}_r} \end{pmatrix} $
(30) 令
$ \hat{D} = U\hat{\Theta }V^{\rm T} $
(31) $ \hat{D} = \Gamma(D) $
(32) 将上述更新过程写作:
最后将更新后的字典 $\hat{D}$ 代入K-SVD字典学习算法框架中迭代更新,直到满足限制条件为止,由于 $D$ 中能量集中于较低的维度内,因此本文将该算法称为CDL算法. CDL算法的实现步骤如下:
输入.训练图集 $X$ ,迭代次数 $T$ .
输出.训练好的字典 $D$ 、 $P$ .
初始化.从训练图集中随机选取 $16\times16$ 的图像块,并将每个小块排列成列向量形式 $x_i(256\times1)$ ,令 $X=[x_1,x_2,\cdots,x_n]$ .初始化DCT字典 $D$ .
第一阶段. 稀疏编码
1) 稀疏编码
对每一个 $x_i$ ,利用匹配追踪算法得到稀疏表示系数 $\alpha_i$ [24-25]:
$ \alpha \leftarrow \min \limits{\alpha} \frac{1}{2} ||X - D \alpha||_2^2 + \lambda||\alpha||_1 $
其中, $\alpha=[\alpha_1,\alpha_2,\cdots,\alpha_n] \in {\bf R}^{k\times n}$ .
第二阶段. 字典D更新
2) 对 $D^{\rm T} D$ 作奇异值分解: $D^{\rm T} D = u\Lambda v^{\rm T}$ ;
3) 更新字典 $\hat{D} = \Gamma(D)$ ;
4) 对 $\hat{D}$ 中的每一列 $(k=1,2,\cdots,K)$ ,定义只用到了 $d_k$ 的稀疏系数集 $w_k=(i|1\leq i \leq N,\alpha_i(k) \neq 0)$ ,计算 $E_k= Y - \sum_{j\neq k}d_j\alpha^j$ ;
5) 仿照K-SVD字典学习算法[22-23],将 $E_k$ 限定在 $w_k$ 集合中,得到 $E_k^R$ ;
6) 对 $E_k^R$ 做奇异值分解: $E_k^R=M\Delta N^{\rm T}$ .做如下更新: $d_k = m_1,\alpha_k^R = \Delta(1,1)n_1$ ;
7) 重复步骤1) $ \sim $ 6)直到 $\frac{\sum\nolimits_i (\Theta_d)}{\sum\nolimits_i(\Theta )} \geq t_d$ ,或者达到最大迭代步数 $T$ .
第三阶段. 字典P计算
8) 根据式(23)字典 $D$ 的奇异值分解得到 $U_d$ ,则字典 $P=U_d^{\rm T}D$ .
2.6 训练结果
图 3所示的CDL字典是利用自然图像(如图 2所示)训练得到的,见第3.1节描述.根据式(23)字典 $D$ 的奇异值分解得到 $U_d$ ( $d=16$ ),令 $P=U_d^{\rm T} D$ ,即可得到对应的低维字典.字典 $P$ 如图 3 (b)所示.
CDL字典能够将主成分集中于较低的维数中,具有能量聚集的作用,如图 4所示.当选取90%主成分 $(t_d = 0.9)$ 时,CDL字典的能量集中于前16维,而K-SVD字典则需要148维,DCT字典需要207维.当字典的维数降得较低时,DCT,K-SVD字典在降维后,无法保留较多的主成分.
3. 实验结果分析
为了验证本文算法的有效性,分别从图像重构与数据可视化、RIP条件验证和图像压缩三个方面进行实验和分析.实验中的图像包括:自然图像、USPS手写数字和PIE人脸图像.
3.1 图像重构和3D可视化
本文的对比算法有: CS+K-SVD、PCA、LPP[1].低维空间的维数分别为: $d=8$ ,16,32,64. CS+K-SVD算法中,降维采样矩阵分别用高斯随机阵(GAU)和主成分分析(PCA).重构图像的质量评价用峰值信噪比(Peak signal to noise ratio,PNSR)表示.
1) 自然图像重构
自然图像集包括13张图片[19],尺寸为 $256\times256$ 或者 $512\times512$ ,如图 2所示.训练时,随机选取图集中的图像块13 000个 $(16\times 16)$ .分别用K-SVD算法和本文CDL算法训练字典.测试用的图像分别为: Lena $(512\times512)$ 、Boat $(512\times512)$ ,测试结果如图 5、图 6所示.由表 1和表 2可看出,CDL重构效果明显优于其他算法,比CS+K-SVD (GAU)高出3 dB以上.
图 5 Lena图像重构对比(原始图像、CS+K-SVD (GAU)、CS+K-SVD (PCA)、PCA、LPP、CDL, $d=16$ )Fig. 5 Reconstructed images of Lena (Original image, CS+K-SVD (GAU), CS+K-SVD(PCA), PCA, LPP, CDL, $d=16$ )
图 6 Boat图像重构对比(原始图像、CS+K-SVD (GAU)、CS+K-SVD (PCA)、PCA、LPP、CDL, $d=32$ )Fig. 6 Reconstructed images of Boat (Original image, CS+K-SVD (GAU), CS+K-SVD (PCA), PCA, LPP, CDL, $d=32$ )表 1 Lena图像重构对比Table 1 Comparison of reconstructed Lena images维数 8 16 32 64 PSNR (dB) CS+K-SVD (GAU) 25.38 27.62 29.35 34.16 CS+K-SVD (PCA) 24.25 25.97 28.73 33.55 PCA 23.28 26.11 27.66 32.67 LPP 23.06 24.56 27.89 33.21 CDL 29.14 31.13 33.86 37.25 表 2 Boat图像重构对比Table 2 Comparison of reconstructed Boat images维数 8 16 32 64 PSNR (dB) CS+K-SVD (GAU) 22.16 23.35 26.25 30.01 CS+K-SVD (PCA) 24.25 25.97 28.73 31.73 PCA 23.74 26.51 28.22 31.52 LPP 24.28 25.35 27.89 30.69 CDL 25.08 26.98 29.52 32.59 2) 手写数字重构和3D可视化
手写数字图片来自USPS库 $^1$ ,包含9 298个图片 $(16\times16)$ .选取其中每类数字的一半做训练,分别降至8,16,32和64维,利用训练得到的CDL字典对剩余的一半数字做重构测试.如图 7及表 3所示,给出 $d=16$ 时各种方法的重构结果,并统计出不同方法恢复结果的平均PSNR值. 表 4统计不同维数下各方法重构的PSNR平均值,可看出CDL的重构效果优于其他算法.
图 7 USPS手写数字重构对比(从上到下: 原始图像、CS+K-SVD (GAU)、CS+K-SVD (PCA)、PCA、CDL， $d=16$ )Fig. 7 Reconstructed images of USPS (From top to bottom:original image, CS+K-SVD (GAU), CS+K-SVD (PCA), PCA, CDL, $d=16$ )表 3 USPS手写数字重构对比（d=16)Table 3 Comparison of reconstructed USPS (d = 16)数字 PSNR (dB) CS+K-SVD (GAU) CS+K-SVD (PCA) PCA CDL 0 12.53 14.87 13.34 15.51 1 15.07 13.77 15.02 18.09 2 9.54 9.28 9.73 12.23 3 10.54 14.39 14.43 17.43 4 8.93 15.3 14.13 15.63 5 12.61 13.08 13.19 18.3 6 11.06 9.89 18.4 21.59 7 11.39 15.53 19.64 22.49 8 22.23 25.22 21.65 28.11 9 11.42 20.76 18.63 21.7 表 4 USPS手写数字重构对比（d = 8、16、32、64)Table 4 Comparison of reconstructed USPS (d = 8, 16, 32, 64)维数 8 16 32 64 PSNR (dB) CS+K-SVD (GAU) 13.53 15.87 19.65 21.43 CS+K-SVD (PCA) 15.21 18.71 22.81 25.97 PCA 15.82 19.23 23.18 26.38 CDL 19.11 22.75 25.57 27.25 同时,在USPS中取3类数据(数字0、3、4),共3 229个.利用CDL、CS+PCA[6]和PCA算法降至3维后,给出3维平面上的数据分布,如图 8所示. 图 8给出的3D可视化结果表明,通过CDL降维后的数据可分性很强,而CS+PCA由于受到RIP条件的限制,导致算法失效,具体分析见第3.2节.在图像重构方面,CDL仍然能够将降至3维后的数据恢复,如图 9所示.
图 8 USPS手写数字三类样本(0、3、4)可视化结果( $d=3$ )Fig. 8 The visualization results of USPS (0, 3, 4) ( $d=3$ )
图 9 USPS手写数字三类样本(0、3、4)图像重构对比(从上到下:原始图像、CDL、CS+K-SVD (GAU))Fig. 9 Reconstructed images of USPS (0, 3, 4) (From top to bottom: original image, CDL, CS+K-SVD (GAU))3) 人脸重构
人脸图像来自PIE库 $^{1}$ $(16\times16)$ .选取其中的10类样本1 700个图片,一半用于训练字典,另一半用于测试,分别计算将数据降至8、16、32和64维时的PSNR值,并统计不同方法的PSNR平均值(如图 10和表 5所示).从表 5可看出在PIE上CDL也优于其他算法.
图 10 PIE人脸图像重构对比(从上到下: 原始图像、CS+K-SVD (GAU)、CS+K-SVD (PCA)、PCA、CDL, $d=16$ )Fig. 10 Reconstructed images of PIE (From top to bottom:original image, CS+K-SVD (GAU), CS+K-SVD (PCA), PCA, CDL, $d=16$ )表 5 PIE人脸图像重构对比(d = 8、16、32、64)Table 5 Comparison of reconstructed PIE(d = 8, 16, 32, 64)维数 8 16 32 64 PSNR (dB) CS+K-SVD (GAU) 21.29 25.87 27.65 32.43 CS+K-SVD (PCA) 25.35 28.71 32.81 37.97 PCA 20.27 22.1 25.18 28.38 CDL 27.14 30.75 36.57 40.25 另外,文献[6]中提到: CS+PCA在满足RIP条件的情况下可以得到很好的降维效果,可以用于数据可视化和数据分类.针对上述PIE库,用本文中的字典 $P$ 和直接对 $\alpha$ 做PCA降维的方法得到降维数据( $d=64$ ),本文算法可以有效恢复图像;而文献[6]采用CS+PCA方法,则无法恢复出原始数据(如图 11所示).
图 11 PIE人脸图像重构对比(从上到下: 原始图像、CS+PCA、CDL) ( $d=64$ )Fig. 11 Reconstructed images of PIE (From top to bottom:original image, CS+PCA, CDL) ( $d=64$ ))从上述实验可以看出,本文CDL算法的图像重构效果明显优于其他算法.
3.2 RIP条件验证
本文假设CS算法利用文献[6]中的OMP算法求解式(1),低维观测值 $y\in {\bf R}^d$ 的维数 $d$ 的RIP条件: $d>{\rm O}(Cs\log(\frac{k}{s})$ (见第2节).为验证CDL算法确实能够在RIP条件限制之外的恢复能力,设计实验如下:设定参数 $C=1$ , $k=784$ , $s=4$ ,则可计算出临界值 $d>9.16$ .将测试图像Lena和Barbara划分为 $16\times16$ 的图像块,降至4维后恢复,结果如图 12所示.可看出,当 $d=4<9.16$ 时,CS+K-SVD (GAU)失效(见图 12的第2、5幅图像,PSNR均低于5 dB),而CDL的恢复结果虽然不是特别清晰,但在Lena和Barbara图像恢复中PSNR均大于20 dB,这说明CDL算法可在CS的RIP条件限制之外取得较好的重构效果.
图 12 Lena图像和Barara图像重构对比( $d=4$ )Fig. 12 Reconstructed images of Lena and Barara ( $d=4$ )另外,回顾第3.1节中CS+PCA[6]在USPS数据集上3D可视化的结果(如图 8所示),在实验中, $k=784$ , $s=10$ ,RIP条件为: $d>18.94$ .当维数降至3维时不满足RIP条件限制,其低维(3D)嵌入也丧失了原始数据的可分性结构. CS算法只有在严格的条件限制下具有一定的信息保持能力,详见文献[9].
利用USPS数字0、3、4做图像重构实验时,针对RIP条件,对比CDL和CS+K-SVD的性能.首先,分别用CDL和K-SVD训练字典,字典规格均为 $256\times784$ ,即 $k=784$ .实验中稀疏系数的稀疏性 $s=6$ ,则RIP条件: $d>12.7$ . CDL算法中利用字典 $P$ 降维; CS算法中,降采样矩阵为高斯随机阵.实验中两种算法同时对数据降至12维和3维,实验结果如图 9和表 6所示.可以发现,当 $d=12$ 时,在RIP条件临界值附近,CS+K-SVD算法依然有效,但是当维数更低时 $(d=3\ll 12)$ ,CS+K-SVD算法无法完成图像重构;而CDL在 $d=3$ 仍然能够恢复数据.因此,CDL能够在RIP条件限制之外仍具有较好的图像重构能力.
表 6 USPS手写数字三类样本（0、3、4)图像重构对比Table 6 Comparison of reconstructed USPS (0, 3, 4)维数数字 d = 3 d =12 0 3 4 0 3 4 PSNR (dB) CS+K-SVD (GAU) 3.40 2.31 3.10 12.66 10.38 10.56 CDL 12.43 10.22 11.10 18.05 19.49 18.69 3.3 图像压缩
从压缩的角度出发,为了最大限度地减少数据量,在本文算法的基础上,不重叠的取出测试图像块.实验中,仍然取图像块大小为 $16\times16$ ,并分别降维至64、32、16、8,即分别对应压缩比CR为4、8、16和32.测试图像为Lena $(512\times512)$ ,分别在无噪声,添加方差为10、20、40的噪声情况下(如图 13~图 16所示),进行压缩重建. CDL与JPEG2000进行对比,用PSNR来评判解压图像质量的优劣,如表 7~表 10所示.
图 13 Lena图像压缩重建(从左到右: 原始图像、JPEG2000 (38.45 dB)、CDL (30.56 dB)) (无噪声, CR = 16)Fig. 13 Reconstructed images of Lena (From left to right:original image, JPEG2000 (38.45 dB), CDL (30.56 dB)) (No noise, CR= 16)
图 14 Lena图像压缩重建(从左到右: 原始图像、加噪图像(28.15 dB)、JPEG2000 (32.04 dB)、CDL (30.24 dB) ( $\sigma = 10$ , CR = 16))Fig. 14 Reconstructed images of Lena (From left to right: original image, noisy image (28.15 dB), JPEG2000 (32.04 dB), CDL(30.24 dB) ( $\sigma = 10$ , CR = 16))
图 15 Lena图像压缩重建(从左到右: 原始图像、加噪图像(22.09 dB)、JPEG2000 (25.93 dB)、CDL (29.34 dB) ( $\sigma = 20$ , CR = 16)Fig. 15 Reconstructed images of Lena (From left to right:original image, noisy image (22.09 dB), JPEG2000 (25.93 dB), CDL (29.34 dB) ( $\sigma = 20$ , CR = 16))
图 16 Lena图像压缩重建(从左到右: 原始图像、加噪图像(16.09 dB)、JPEG2000 (19.76 dB)、CDL (26.96 dB) ( $\sigma =40$ , CR = 16))Fig. 16 Reconstructed images of Lena (From left to right:original image, noisy image (16.09 dB), JPEG2000 (19.76 dB),CDL (26.96 dB) ( $\sigma =40$ , CR = 16))表 7 Lena图像压缩重建（无噪声）Table 7 Comparison of reconstructed Lena (No noise)CR 4 16 32 64 PSNR(dB) JPEG2000 46.32 41.82 38.45 35.19 CDL 35.22 32.46 30.56 28.23 表 8 Lena图像压缩重建（σ = 10)Table 8 Comparison of reconstructed Lena (σ=10)CR 4 16 32 64 PSNR(dB) JPEG2000 27.95 29.04 32.04 32.8 CDL 32.37 31.53 30.24 28.14 表 9 Lena图像压缩重建(σ = 20)Table 9 Comparison of reconstructed Lena (σ = 20)CR 4 16 32 64 PSNR(dB) JPEG2000 22.07 23.18 25.93 28.8 CDL 28.36 29.52 29.34 27.85 表 10 Lena图像压缩重建( $\sigma =40$ )Table 10 Comparison of reconstructed Lena ( $\sigma =40$ )CR 4 16 32 64 PSNR(dB) JPEG2000 28.36 29.52 26.96 27.85 CDL 16.38 17.5 19.76 22.86 实验表明: 1)无噪声时,JPEG2000解压效果优于CDL. 2)但在噪声环境下,CR较低时,CDL优于JPEG2000;随着噪声的增加,CDL相比JPEG2000的优势越明显.由于在重构的过程中,当原始信号 $X$ 通过字典 $D$ 转化为稀疏系数 $\alpha$ 表示时,此过程中存在一定去噪的功能,而 $Y$ 在字典 $P$ 转化为 $\alpha$ 表示时,恢复过程同样有一定的去噪功能.因此,本文CDL算法对噪声具有很好的鲁棒性.
4. 结束语
本文提出一种聚能量字典学习算法,应用于图像降维与恢复.基于字典学习的理论,本文算法通过字典对(高维字典 $D$ 和低维字典 $P$ ),能够在原始信号 $X$ 到特征 $Y$ 的降维过程中保留高维信号的本质特征,并且能够在RIP条件限制之外仍具有较好的信号重构能力.在自然图像、人脸图像、手写数字上的实验验证了本文算法的优越性.
从 $X$ 到 $Y$ 降维的同时,因为 $Y$ 中保留了 $X$ 的几何结构特征,因此可以从 $Y$ 中恢复出原始信号 $X$ .算法本身并不局限于内积、距离、夹角等特征,只要能找到合适映射关系,可推导出不同的模型,以实现不同任务需求:如目标识别、目标跟踪、视频分析等.
-
图 9 IEEE 39节点系统不同节点三相接地时系统暂态状态
Fig. 9 Transient state of IEEE 39-node system when three-phase ground fault occurs to different node
图 10 IEEE 39节点系统节点重要度与状态衰退时节点电压振荡
Fig. 10 Node importance and the voltage oscillation caused by state degeneration in IEEE 39-node system
-
[1] 阮逸润, 老松杨, 王竣德, 白亮, 陈立栋.基于领域相似度的复杂网络节点重要度评估算法.物理学报, 2017, 66(3):Article No.038902 http://mall.cnki.net/magazine/Article/JSJC201210023.htmRuan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Chen Li-Dong. Node importance measurement based on neighborhood similarity in complex network. Acta Physica Sinica, 2017, 66(3):Article No.038902 http://mall.cnki.net/magazine/Article/JSJC201210023.htm [2] 韦相, 赵军产, 胡春华.两个异构复杂网络的广义同步与参数识别.自动化学报, 2017, 43(4):595-603 http://www.cqvip.com/QK/90250X/201704/671875705.htmlWei Xiang, Zhao Jun-Chan, Hu Chun-Hua. Generalized synchronization and system parameters identification between two different complex networks. Acta Automatica Sinica, 2017, 43(4):595-603 http://www.cqvip.com/QK/90250X/201704/671875705.html [3] 谢琼瑶, 邓长虹, 赵红生, 翁毅选.基于有权网络模型的电力网节点重要度评估.电力系统自动化, 2009, 33(4):21-24 doi: 10.7500/AEPS200805140Xie Qiong-Yao, Deng Chang-Hong, Zhao Hong-Sheng, Weng Yi-Xuan. Evaluation method for node importance of power grid based on the weighted network model. Automation of Electric Power Systems, 2009, 33(4):21-24 doi: 10.7500/AEPS200805140 [4] 余新, 李艳和, 郑小平, 张汉一, 郭奕理.基于网络性能变化梯度的通信网络节点重要程度评价方法.清华大学学报(自然科学版), 2008, 48(4):541-544 http://www.cnki.com.cn/Article/CJFDTOTAL-GGYT201115037.htmYu Xin, Li Yan-He, Zheng Xiao-Ping, Zhang Han-Yi, Guo Yi-Li. Node importance evaluation based on communication network performance grads. Journal of Tsinghua University (Science & Technology), 2008, 48(4):541-544 http://www.cnki.com.cn/Article/CJFDTOTAL-GGYT201115037.htm [5] 符修文, 李文锋, 段莹.分簇无线传感器网络级联失效抗毁性研究.计算机研究与发展, 2016, 53(12):2882-2892 doi: 10.7544/issn1000-1239.2016.20150455Fu Xiu-Wen, Li Wen-Feng, Duan Ying. Invulnerability of clustering wireless sensor network towards cascading failures. Journal of Computer Research and Development, 2016, 53(12):2882-2892 doi: 10.7544/issn1000-1239.2016.20150455 [6] 吴润泽, 张保健, 唐良瑞.双网耦合模型中基于级联失效的节点重要度评估.电网技术, 2015, 39(4):1053-1058 http://www.oalib.com/paper/4639654Wu Run-Ze, Zhang Bao-Jian, Tang Liang-Rui. A cascading failure based nodal importance evaluation method applied in dual network coupling model. Power System Technology, 2015, 39(4):1053-1058 http://www.oalib.com/paper/4639654 [7] Zhao L, Park K, Lai Y C. Attack vulnerability of scale-free networks due to cascading breakdown. Physical Review E, 2004, 70(2):Article No.035101 http://www.ncbi.nlm.nih.gov/pubmed/15524565 [8] Tang L, Jing K, He J, Stanley H E. Complex interdependent supply chain networks:cascading failure and robustness. Physica A:Statistical Mechanics and Its Applications, 2016, 443:58-69 doi: 10.1016/j.physa.2015.09.082 [9] 谢丰, 程苏琦, 陈冬青, 张国强.基于级联失效的复杂网络抗毁性.清华大学学报(自然科学版), 2011, 51(10):1252-1257 http://www.cqvip.com/QK/93884X/201110/39550908.htmlXie Feng, Cheng Su-Qi, Chen Dong-Qing, Zhang Guo-Qiang. Cascade-based attack vulnerability in complex networks. Journal of Tsinghua University (Science & Technology), 2011, 51(10):1252-1257 http://www.cqvip.com/QK/93884X/201110/39550908.html [10] Buldyrev S V, Parshani R, Paul G, Stanley H E, Havlin S. Catastrophic cascade of failures in interdependent networks. Nature, 2010, 464(7291):1025-1028 doi: 10.1038/nature08932 [11] Gao J X, Buldyrev S V, Stanley H E, Havlin S. Networks formed from interdependent networks. Nature Physics, 2012, 8(1):40-48 doi: 10.1038/nphys2180 [12] Sun Y Z, Han J W, Yan X F, Yu P S, Wu T Y. PathSim:meta path-based top-k similarity search in heterogeneous information networks. Proceedings of the VLDB Endowment, 2011, 4(11):992-1003 https://www.researchgate.net/publication/220538331_PathSim_Meta_Path-Based [13] Boldi P, Santini M, Vigna S. PageRank:functional dependencies. ACM Transactions on Information Systems, 2009, 27(4):Article No.19 http://vigna.di.unimi.it/ftp/papers/PageRankFunctional.pdf [14] Eom Y H, Shepelyansky D L. Opinion formation driven by PageRank node influence on directed networks. Physica A:Statistical Mechanics and Its Applications, 2015, 436:707-715 doi: 10.1016/j.physa.2015.05.095 [15] Wu X D, Kumar V, Quinlan J R, Ghosh J, Yang Q, et al. Top 10 algorithms in data mining. Knowledge and Information Systems, 2008, 14(1):1-37 http://dl.acm.org/citation.cfm?id=1327436 [16] Pai M A. Energy Function Analysis for Power System Stability. London:Kluwer Academic Publishers, 1989. [17] Wang K, Zhang B H, Zhang Z, Yin X G, Wang B. An electrical betweenness approach for vulnerability assessment of power grids considering the capacity of generators and load. Physica A:Statistical Mechanics and Its Applications, 2011, 390(23-24):4692-4701 doi: 10.1016/j.physa.2011.07.031 [18] Arianos S, Bompard E, Carbone A, Xue F. Power grid vulnerability:a complex network approach. Chaos, 2009, 19(1):Article No.013119 http://www.ncbi.nlm.nih.gov/pubmed/19334983 期刊类型引用(9)
1. 何晓军，刘璇，魏宪. 融合字典学习与视觉转换器的高分遥感影像场景分类方法. 激光与光电子学进展. 2023(14): 189-198 . 
百度学术2. 王莲子，李钟晓，陈倩倩，庄晓东. 基于信号子空间低维表征的快速字典学习算法. 传感器与微系统. 2022(08): 144-147+152 . 百度学术3. 贾澎涛，雷文华，张婧. 基于最优奇异值占比的融合特征人脸检测. 西安科技大学学报. 2022(06): 1198-1204 . 百度学术4. 代少飞，刘文波，王郑毅，李开宇. 基于双迭代聚能量字典学习的数据压缩算法. 数据采集与处理. 2021(06): 1147-1156 . 百度学术5. 王莲子，李钟晓，陈倩倩，庄晓东. 基于K-SVD算法和组合字典的语音信号清浊音判决研究. 青岛大学学报(工程技术版). 2020(02): 17-23 . 百度学术6. 王莲子，庄晓东，李钟晓，陈倩倩. 基于PCA的快速字典学习算法研究. 青岛大学学报(工程技术版). 2020(04): 11-16 . 百度学术7. 姚涛，孔祥维，付海燕，TIAN Qi. 基于映射字典学习的跨模态哈希检索. 自动化学报. 2018(08): 1475-1485 . 本站查看8. 徐俊，李元祥，Wei Xian，骆建华. 基于核字典学习的图像分类. 计算机应用研究. 2017(12): 3820-3824 . 百度学术9. 李向丽，曹晓锋，邱保志. 基于矩阵模型的高维聚类边界模式发现. 自动化学报. 2017(11): 1962-1972 . 本站查看其他类型引用(17)
-
下载:
下载:
计量
- 文章访问数: 2221
- HTML全文浏览量: 316
- PDF下载量: 575
- 被引次数: 26
