1 引言

非负矩阵分解(Non-negative Matrix Factorization,NMF)^[1]算法因其收敛速度快以及分解后的稀疏分量能够清晰直观地描述原始数据等特点, 在计算机视觉, 文本聚类, 模式识别等领域受到了广泛关注. NMF本质上是一种基于部分的矩阵分解方法, 能够以非负形式表示原始数据的局部特征.

NMF将原始非负矩阵 ${{X}}$ 分解为两个非负矩阵 ${{WH}}$ 的乘积. 分解后的矩阵仅包含非负元素, 并且基向量 ${{W}}$ 具有一定的数据局部表示能力, 这使得NMF在诸多领域得到广泛运用. 在文献[2]中, Park等通过人眼过滤和最小化基于NMF的重构图像错误率来进行人眼检测. 考虑到数据集合的内部几何结构, 文献[3]通过最近邻图来刻画数据集中相邻数据点的关系, 提出了图正则化非负矩阵分解. 为了充分利用判别信息, 同时考虑到数据中的几何结构, 文献[4]提出了K近邻非负矩阵分解(NMF-K-NN). 在此基础上, Jun Ye等使用模糊集来处理模式识别中的不确定因素, 提出了模糊K近邻非负矩阵分解(NMF-FK-NN)方法^[5]. Zhang等^[6]通过最小化约束梯度距离, 提出保持拓扑性非负矩阵分解(TPNMF), 该方法能够保持脸部空间的局部内在拓扑结构. 在研究聚类问题的过程中, Yang等指出^[7], 正交性的约束能在很大程度上优化聚类效果, 其本质是施加正交性约束后的NMF结果更加稀疏, 从而使原始数据的基之间区别性增强, 进而提升聚类效果. Li等^[8]提出基于正交子空间的非负矩阵分解(Non-negative Matrix Factorization on Orthogonal Subspace, NMFOS), 将对 ${\bf{W}}$ (或 ${\bf{H}}$ )的正交性约束作为NMF目标函数中的一部分直接进行优化, 减少因施加正交性约束而带来的巨大计算量, 同时还能在一定程度上提升基矩阵 ${\bf{W}}$ (系数矩阵 ${\bf{H}}$ )的稀疏性.

基于正交子空间的非负矩阵分解虽然能在一定程度上提升分解矩阵的稀疏性, 但是它导致的稀疏程度是难以控制的. 本文为了在分解过程中进一步提升分解矩阵的稀疏性, 在分解过程中引入了L1范数约束, 将L1范数约束转换成目标函数的正则部分进行求解, 提出了L1范数约束正交子空间非负矩阵分解(Non-negative Matrix Factorization on Orthogonal Subspace with L1 norm constrains, NMFOS-L1). 本文方法不仅能提升聚类效果, 同时还提升了分解结果的稀疏表达能力, 具有实用价值.

2 非负矩阵分解

给定非负矩阵 ${\bf{X}} = [{x_1},{x_2},\cdots,{x_n}] \in R_ + ^{m \times n}$ , NMF将原始矩阵分解为两个非负低秩矩阵 ${\bf{W}}$ 和 ${\bf{H}}$ , 即:

${\bf{X}} \approx {{\bf{W}}_{m \times r}}{{\bf{H}}_{r \times n}}$

(1)

其中, $r < < {\rm{min}}\{ m,n\} $ . NMF常采用欧氏距离衡量 ${\bf{WH}}$ 对 ${\bf{X}}$ 的逼近程度, 目标函数如下:

$\begin{array}{l}\min f({\bf{W}},{\bf{H}}) = \left\| {{\bf{X}} - {\bf{WH}}} \right\|_F^2{\kern 1pt} \;\\\;{\rm {s.t.}}\;\;{\bf{W}},{\bf{H}} \ge 0\end{array}$

(2)

式中, ${\left\| \cdot \right\|_F}$ 为Frobenius范数, 矩阵 ${\bf{W}}$ 的每一列称作基向量, 矩阵 ${\bf{H}}$ 每一列为系数向量, 将基向量进行线性组合来表示原始数据矩阵. Lee和Seung^[9]给出如下乘性迭代规则:

${\bf{H}} \leftarrow {\bf{H}} \otimes \frac{{({{\bf{W}}^{\rm T}}{\bf{X}})}}{{({{\bf{W}}^{\rm T}}{\bf{WH}})}}$

(3)

${\bf{W}} \leftarrow {\bf{W}} \otimes \frac{{({\bf{X}}{{\bf{H}}^{\rm T}})}}{{({\bf{WH}}{{\bf{H}}^{\rm T}})}}$

(4)

式中, $ \otimes $ 为矩阵元素的乘积运算符号, 交替进行式(3)和式(4), 可以求得式(2)的系数矩阵和基矩阵.

3 基于正交子空间的非负矩阵分解

NMFOS将分解所得矩阵的正交性约束通过拉格朗日乘子引入到矩阵分解的目标函数中进行优化, 从而使分解结果的正交性不必通过正交性约束完成, 减少计算量. NMFOS的目标函数如下: 对矩阵 ${\bf{W}}$ 加入正交性约束, 目标函数为:

$\begin{array}{l}\mathop {{\rm{min}}}\limits_{{\bf{W}},{\bf{H}}} \;{J_{\rm {NMFOS}}} = \left\| {{\bf{X}} - {\bf{W}}{{\bf{H}}^{\rm T}}} \right\|_F^2 + \lambda \left\| {{{\bf{W}}^{\rm T}}{\bf{W}} - {\bf{I}}} \right\|_F^2\;\;\\{\rm {s.t.}}\;\;{\bf{W}},{\bf{H}} \ge 0\end{array}$

(5)

对矩阵 ${\bf{H}}$ 加入正交性约束, 目标函数为:

$\begin{array}{l}\mathop {{\rm{min}}}\limits_{{\bf{W}},{\bf{H}}} \;{J_{\rm {NMFOS}}} = \left\| {{\bf{X}} - {\bf{W}}{{\bf{H}}^{\rm T}}} \right\|_F^2 + \lambda \left\| {{\bf{H}}{{\bf{H}}^{\rm T}} - {\bf{I}}} \right\|_F^2\;\\\;{\rm {s.t.}}\;\;{\bf{W}},{\bf{H}} \ge 0\end{array}$

(6)

其中, $\lambda \geqslant 0$ 为正则参数, ${\bf{I}}$ 是全1矩阵. 对于式(5)和式(6), Li等^[8]给出了如下的乘性迭代规则:

${\bf{W}} \leftarrow {\bf{W}} \otimes \frac{{{\bf{XH}} + 2\lambda {\bf{W}}}}{{{\bf{W}}{{\bf{H}}^{\rm T}}{\bf{H}} + 2\lambda {\bf{W}}{{\bf{W}}^{\rm T}}{\bf{W}}}}$

(7)

${\bf{H}} \leftarrow {\bf{H}} \otimes \frac{{{{\bf{W}}^{\rm T}}{\bf{X}}}}{{{{\bf{W}}^{\rm T}}{\bf{W}}{{\bf{H}}^{\rm T}}}}$

(8)

${\bf{W}} \leftarrow {\bf{W}} \otimes \frac{{{\bf{XH}}}}{{{\bf{W}}{{\bf{H}}^{\rm T}}{\bf{H}}}}$

(9)

${\bf{H}} \leftarrow {\bf{H}} \otimes \frac{{{{\bf{W}}^{\rm T}}{\bf{X}} + 2\lambda {{\bf{H}}^{\rm T}}}}{{{{\bf{W}}^{\rm T}}{\bf{W}}{{\bf{H}}^{\rm T}} + 2\lambda {{\bf{H}}^{\rm T}}{\bf{H}}{{\bf{H}}^{\rm T}}}}$

(10)

4 L1范数约束正交子空间非负矩阵分解

NMF算法的分解结果在一定程度上呈现稀疏性, 但是稀疏程度难以控制. Hoyer于2004年提出稀疏性非负矩阵分解^[10], 在目标函数上添加L1正则化的稀疏约束. 如果对NMFOS加上正则化的稀疏约束, 那么就可以得到更加稀疏的分解矩阵, 从而提高分解质量.

通过引入稀疏约束条件到NMFOS的目标函数, 将稀疏约束正交子空间非负矩阵分解归结为下列优化问题: 对矩阵 ${\bf{W}}$ 而言, 目标函数为:

$\begin{array}{l}{J_{\rm {NMFOS\;SC}}} = \left\| {{\bf{X}} - {\bf{WH}}} \right\|_F^2 + \lambda \left\| {{{\bf{W}}^{\rm T}}{\bf{W}} - {\bf{I}}} \right\|_F^2 + \alpha {\left\| {\bf{W}} \right\|_1}\;\;\\{\rm {s.t.}}\;\;{\bf{W}} \ge 0,{\bf{H}} \ge 0\end{array}$

(11)

对矩阵 ${\bf{H}}$ 而言, 目标函数为:

$\begin{array}{l}{J_{\rm {NMFOS\;SC}}} = \left\| {{\bf{X}} - {\bf{WH}}} \right\|_F^2 + \lambda \left\| {{\bf{H}}{{\bf{H}}^{\rm T}} - {\bf{I}}} \right\|_F^2 + \beta {\left\| {\bf{H}} \right\|_1}\;\;\\{\rm {s.t.}}\;\;{\bf{W}} \ge 0,{\bf{H}} \ge 0\end{array}$

(12)

式中, $\lambda ,\alpha ,\beta $ 均为大于0的常数. 利用最速下降法和乘子迭代法, 推导出上式的乘性迭代规则; 首先新的目标函数可表示为:

$\begin{array}{l}{J_{\rm {NMFOS\;SC}}} = Tr\left( {({\bf{X}} - {\bf{W}}{{\bf{H}}^{\rm T}}){{({\bf{X}} - {\bf{W}}{{\bf{H}}^{\rm T}})}^{\rm T}}} \right) \\\;\;\;\;\;\;\;\;\;\;\;+\lambda Tr\left( {({{\bf{W}}^{\rm T}}{\bf{W}} - {\bf{I}}){{({{\bf{W}}^{\rm T}}{\bf{W}} - {\bf{I}})}^{\rm T}}} \right) + \alpha {\left\| {\bf{W}} \right\|_1}\end{array}$

(13)

由Lagrange定理:

$\begin{array}{l}{J_{\rm {NMFOS\;SC}}} = Tr\left( {({\bf{X}} - {\bf{W}}{{\bf{H}}^{\rm T}}){{({\bf{X}} - {\bf{W}}{{\bf{H}}^{\rm T}})}^{\rm T}}} \right) \\\;\;\;\;\;\;\;\;\;\;+\lambda Tr\left( {({{\bf{W}}^{\rm T}}{\bf{W}} - {\bf{I}}){{({{\bf{W}}^{\rm T}}{\bf{W}} - {\bf{I}})}^{\rm T}}} \right)\; + \alpha {\left\| {\bf{W}} \right\|_1}\\\;\;\;\;\;\;\;\;\;\; + Tr\left( {\Psi {{\bf{W}}^{\rm T}}} \right) + Tr\left( {\Phi {{\bf{H}}^{\rm T}}} \right)\end{array}$

(14)

式中, $\Psi = [{\psi _{ik}}]$ 和 $\Phi = [{\varphi _{jk}}]$ 分别为约束 ${\bf{W}} \geqslant 0$ 和 ${\bf{H}} \geqslant 0$ 的拉格朗日乘子. 对式(13)分别关于 ${\bf{W}}$ 和 ${\bf{H}}$ 进行偏微分, 结果为:

$\begin{array}{l}\displaystyle\frac{{\partial J}}{{\partial {\bf{W}}}} = {\bf{X}}{{\bf{H}}^{\rm T}} + {\bf{WH}}{{\bf{H}}^{\rm T}} - 2\lambda {\bf{W}}\;\\\;\;\;\;\;\;\;\;\;\;\;\; + 2\lambda {\bf{W}}{{\bf{W}}^{\rm T}}{\bf{W}} + \alpha {\bf{I}}\end{array}$

(15)

$\frac{{\partial J}}{{\partial {\bf{H}}}} = \Delta {{\bf{W}}^{\rm T}}{\bf{X}} + {{\bf{W}}^{\rm T}}{\bf{WH}}$

(16)

式中, ${\bf{I}}$ 是全1矩阵. 由KKT最优条件 ${\varphi _{ik}}{{\bf{W}}_{ik}} = 0$ 和 ${\psi _{jk}}{{\bf{H}}_{jk}} = 0$ , 得 ${\bf{W}}$ 和 ${\bf{H}}$ 的乘性迭代规则为:

${\bf{W}} \leftarrow {\bf{W}} \otimes \frac{{{\bf{X}}{{\bf{H}}^{\rm T}} + 2\lambda {\bf{W}}}}{{{\bf{W}}{{\bf{H}}^{\rm T}}{\bf{H}} + 2\lambda {\bf{W}}{{\bf{W}}^{\rm T}}{\bf{W}} + \alpha {\bf{I}}}}$

(17)

${\bf{H}} \leftarrow {\bf{H}} \otimes \frac{{{{\bf{W}}^{\rm T}}{\bf{X}}}}{{{{\bf{W}}^{\rm T}}{\bf{WH}}}}$

(18)

同理可得式(12)的矩阵更新规则为:

${\bf{W}} \leftarrow {\bf{W}} \otimes \frac{{{\bf{X}}{{\bf{H}}^{\rm T}}}}{{{\bf{WH}}{{\bf{H}}^{\rm T}}}}$

(19)

${\bf{H}} \leftarrow {\bf{H}} \otimes \frac{{{{\bf{W}}^{\rm T}}{\bf{X}} + 2\lambda {\bf{H}}}}{{{{\bf{W}}^{\rm T}}{\bf{WH}} + 2\lambda {\bf{H}}{{\bf{H}}^{\rm T}}{\bf{H}} + \beta {\bf{I}}}}$

(20)

基于上述的乘性迭代规则, 可将NMFOS-L1算法归结为:

步骤1. 初始化: 输入矩阵 ${\bf{X}}$ , 初始化矩阵 ${\bf{W}}$ 和 ${\bf{H}}$ 为非负矩阵;

步骤2. 迭代更新: 将矩阵 ${\bf{W}}$ 和 ${\bf{H}}$ 带入式(17)~式(20), 解得 ${\bf{W}}$ 和 ${\bf{H}}$ ;

步骤3. 终止条件: 若 $\left\| {{\bf{X}} - {\bf{WH}}} \right\|_F^2$ 小于阈值或超出预定的迭代次数, 则算法终止; 否则返回步骤3.

5 实验与结果分析

为了验证NMFOS-L1算法有效性, 本文在手写体数字光学识别数据集(Optical Recognition of Handwriting Digits)^[11]、ORL 人脸数据库^[12]和Yale人脸数据库^[13]进行了聚类的对比实验. 同时, 为了验证本文算法所得到的基矩阵的稀疏性, 在ORL和Yale人脸数据库进行实验, 比较了几种不同算法的稀疏表达能力.

手写体数字光学识别数据集: 该数据集从UCI数据库中选取0, 2, 4, 6几个数字, 构成2237个样本, 每个样本有62特征, 分为4个类. ORL人脸数据库^[12]是由40个人, 每人10幅图像构成. 每幅图像为256个灰度级, 分辨率为 $112 \times 92$ . 该库的人脸图像表情变化, 面部细节, 以及拍摄角度变化较大. 图1为ORL人脸库同一个人的10张图像.

Yale人脸库^[13]包含15个人每人11幅共165幅人脸图像, 这些照片在不同的光照条件和角度下拍摄, 人脸表情也有较大变化. 每幅图像均为 $100 \times 100$ 像素. 图2为Yale同一个人的10张图像.

5.1 聚类实验

在聚类问题中, 常见的评测指标是纯度和F值. 本文在已知类标签情况下, 将不同算法的聚类结果进行对比, 利用纯度来评价不同算法产生的分类效果. 纯度: 所有簇的纯净度的均值. 范围为[0, 1], 数值越大, 纯净度越高, 效果越好. 定义式为:

$Purity = \frac{1}{n}\sum\limits_{k = 1}^P {\mathop {\max }\limits_{1 \leqslant l \leqslant q} \;n_k^l} $

(21)

式中, $q$ 为总的类数, $n_k^l$ 是簇 $k$ 中标记为类 $l$ 的个数. 聚类熵: 度量各簇中所有类的分布情况. 取值范围为[0, 1], 取值越小, 聚类效果越好. 定义如下:

$Entropy = \Delta \frac{1}{{n{{\log }_2}q}}\sum\limits_{k = 1}^P {\sum\limits_{l = 1}^q {n_k^l{{\log }_2}\frac{{n_k^l}}{{{n_k}}}} } $

(22)

式中, ${n_k} = \displaystyle\sum\limits_l {n_k^l} $ , $q$ 为总得类数.

在本节实验中设定 $P = q$ , 在每个数据库独立地重复实验200次, 并设定迭代次数的最大值为2000. 在实验时, 选取参数 $\lambda = 5$ , $\beta = 1$ . 实验结果如表1所示.

5.2 稀疏性对比实验

本节我们在ORL和Yale人脸数据库上进行人脸特征提取, 对比了NMF、ONMF、NMFOS、和本文NMFOS-L1几种算法的局部表达能力. 图3给出了秩为25时, 不同算法得到的基矩阵图像.

由图3可以看出, 在这两个数据库上对比这4种算法的基图像稀疏度, NMF稀疏度最低, NMFOS-L1的基图像最为稀疏, 换言之, 该算法具有最优的局部表达能力.

Hoyer在文献[9]中给出了度量向量稀疏度的函数:

${\rm{sparse}}(x) = \frac{{\sqrt n - {{(\sum {{{\left| x \right|}_i}} )} / {\sqrt {\sum {x_i^2} } }}}}{{\sqrt n - 1}}$

(23)

其中, $n$ 表示 $x$ 的维数. 这个函数的值域为[0, 1], 取值越小, 向量 $x$ 越稠密, 反之越稀疏, 当该函数取值为1时, 表明非负向量 $x$ 只包含一个非零元素.

实验最后, 我们对矩阵分解结果的稀疏性进行对比. 从表3和表4中我们可以看到, 本文算法所得的基矩阵和稀疏矩阵更加稀疏, 本文算法的稀疏表达能力优于对比的几种算法.

6 结束语

针对正交子空间非负矩阵分解相对稀疏或局部化描述原数据时导致的稀疏能力和程度比较弱的问题, 本文将稀疏约束引入正交子空间非负矩阵分解的目标函数中, 提出稀疏约束正交子空间非负矩阵分解. 同时给出了迭代公式. 实验证明该算法具有更好的聚类效果以及稀疏表达能力, 在人脸特征提取领域具有应用潜力. 进一步提升正交子空间非负矩阵分解算法效率, 以及将本文方法推广应用到计算机视觉中都是我们进一步要研究的内容.