摘 要 稀疏表示分类方法 在人脸识别方面取得了当前最好的分类结果 针 对 存 在 的 问 题 提出稀疏近邻表示 方 法 在局部线性嵌入方法前提假设成立的条件下 通过稀疏近邻表示实现目标分类 在几个不同数据集上的实验结果显示 适用于呈非线性分布的数据集 并取得了较好的效果 进一步的分析表明 能 够 较 好的适用于那些通过降维方法得到的低维数据的分类问题 尤其适用于基于近邻保持的一类降维方法得到的低维数据 并 且具有较低的时间复杂度
关 键 词 稀 疏 表 示 局 部 线 性 嵌 入 稀 疏 近 邻 表 示 近 邻 分 类 降 维
　　引 言
　　传统的信号表示理论大多是基于非冗余的正交基函数的 变 换 如 傅 立 叶 变 换 变 换 小 波 变 换 等年 等 人 首先提出基于过完备的 词 典 的 信号稀 疏 表 示 方 法 开创了信号稀疏分解的新方向 近 年 来该领 域 的 研 究 主 要 集 中 在 设计一组针对具体对象的过完备 字 典 有效的求解稀疏编码的算法 以 及 在 信 号和图像处理还有模式识别领域的应用 在模式识别这个研 究 方 向 有利于解决分类问题的一类稀疏表示方法得到显 著 的 关 注 文 献 介绍了一种学习多个字典的方法其中每个字典在具有重构性的同时 还 具 有 判 别 性 该 方法 通 过 学 习 得 到 的 字 典 对 每 个 图 像 块进 行 稀 疏 表 示 最后用重构误差实现对像素的分类 与 文献 相 比 等 人 则提出一种同时具有重构性和判别性的稀疏图像分类方法 该方法在具有稀疏性的同时还具有鲁棒性很强的重构性 进而有效的实现了对有损 信 号 的 分 类 与 文 献 预 先 指 定 字 典 相 似 在 文 献中 作者提出一种基于图像的通用目标识别方法 基于稀疏表示的分类方法该方法把模式识别问题看作一个针对多个线性重构模型的分类问题 同 时 文 献 还 强 调 信 号稀疏表示理论为该方法解决模式识别问题提供了强有力的依据 虽 然 算法的主要目的是强调其判别性 但 是 算计算机工程与设计 年法整个过程并没有体现出明显的判别性 针 对 上 述 问 题本文提出改进的稀疏表示分类方法 判别性是本文提出方法强调的一个重要方面
　　基于稀疏表示的分类方法
　　算 法 的 主 要 思 想 是 对于一个测试样本 从 一个过完备的字典中 包 含 整 个 训 练 集 寻找能够稀疏表示的 一 组 基 元 素 全部基元素称作基 具 体 而 言 如 果 训练集中包含的样本数量足够多 那 么 对 于 测 试 样 本 来 说其将可以由与其属于同一类别的部分训练样本线性重构同 时 其线性重构权值向量满足一定的稀疏性 即 重 构权值向量中只有少数几个分量是非零的文献 总 结 了 算法在解决计算机视觉问题方面 的 两 个 贡 献 一 方 面 针对高维可视化的数据 采 用 稀疏表示尤其重要 另 一 方 面 提 供 了 一 个 求 解 范 数 最 小化 问 题 的 方 法 对其它的优化方法也具有较好的借鉴意义从 文 献 的 几 个 示 例 中 可 以 发 现 如果恰当的应用算 法 其可以达到目前最好的分类性能 算 法 的具体步骤如下所示单 位 化 训 练 集 中 的 每 个 样 本其 中求 解 范数最小化问题满 足 或 者 求 解对于任意的一个测试样本 计算每一类的残差式 中 一 个 维 向 量 并 且 若 属 于 第 类 那 么否 则虽 然 算 法 有 很 多 令 人 满 意 的 优 点 其 同 时 也 存 在一 些 缺 陷 首 先 该算法缺乏明显的判别性 算 法 根据基元素所属的类别对测试样本 进 行 分 类 若 基 元 素 属于第类 那 么 也 属 于 第 类 其 中 基 元 素 为 那 些 可 以最好的稀疏表示 的一类训练样本 事 实 上 由 确 定 的这组基元素中很可能包括距离 比 较 远 的 样 本 即 这 组基元素并不一定是 的 局 部 近 邻 在 此 情 况 下 根 据算 法 将被分到某一类中 其中该类基元素所张成的子空间 距 离 最 近 即使该类样本距离 比 较 远 然 而 如 果上述结论成立的话 算法需要一个前提假设 即 使 每类的基元素相互之间距离比较远 由各类基元素张成的子空间仍然是线性的 也 就 是 说 算法成立的一个前提是 每类训练样本所张成的子空间是线性的 其 次 即 使每类训练样本分布在一个线性子空间里 仍 可 能 出 现一 种 情 形 测 试 样 本 可以由来自多个不同类别的基元素稀 疏 表 示 其 原 因 在 于 分别由各个类别训练样本所张成的子 空 间 之 间 可 能 存 在 交 集 从而那些距离交集比较近的测试样本则可以由来自不同类别的基元素稀疏表示 而 这可能导致在求得的基元素中 没有或者包含很少的与 属于同一类别的训练样本 因 此 除了需要满足每类训练样本位于同一个线性子空间的假设 还需要另外一个前提 条 件 各个类别训练样本张成的子空间之间不能有交集或 者 距 离 太 近 由 上 述 分 析 可 知 算法无法有效处理非线性分布的数据分类问题基于稀疏近邻表示的分类方法本文提出一种新的分类方法 基于稀疏近邻表示的分类 方 法该方法可以有效的解决上述 算 法 遇 到 的 问题 即 数据集是非线性分布的 不 满 足 算 法 的 前提 假 设算 法 介 绍对于任意的一个测试样本 与 算 法 不 同 的 是算 法 首 先 计 算 在每个类别中的 近 邻 其 次 每 类的 近邻被当作一个局部基 然 后 这 些 基 被 用 来 线 性 表示 最 后 被分到某个类别中 满足其在该类别的基能够 最 好 的 线 性 重 构 简 而 言 之 算法求解如下优化 问 题式 中 在 第 个 类 中 的 近 邻 且 或者 求 解 以 下 问 题其 中为 了 方 便 起 见 等同于求解如下优化问题其 中 且 需 要 注 意 的 是 由 于因 此与 在整个训练集中寻找一个全局基不同的是则从每个类别中寻找 的 近邻作为其在该类别的局部 基 这 么 做 的 好 处 在 于 可以有效的避免 遇到 的 问 题 即 根 据 算法得到的基可能包含来自各个类 别 的 样 本 更 差 的 情 况 是 该基中仅仅只有很少的甚至没 有 与 属于同一类别的样本 在 此 情 形 下 很 容 易 被 分错 类 别 然 而 算法则不会发生上述情形 其 原 因在 于 在每一类中都寻找了 近邻作为一个局部基即对每一类分别计算 此 外 再 加 上 另 外 两个 约 束 项 算 法 还第 卷 第 期 王琦 惠康华 基于稀疏近邻表示的分类方法可以用于线性分布的数据分类问题 进 一 步 地 与 相比 求解每个局部基稀疏表示系数的时间复杂度要更 低 算法的整个识别过程如下所示单 位 化 每 个 训 练 样 本 其 中在 训 练 集 的 每 一 个 类 别 中 分别计算测试样本 的近 邻 其 中 是 在 第类 中 的 第 个 近 邻 且求解最小化问题计算局部稀疏表示残差算 法 论 证对于非线性分布的一类数据集 算 法 如 何 保 证仅根 据 其 在 每 类 中 的 近 邻 就可以对测试样本进行正确的 分 类？在 讨 论 开 始 之 前 先考虑一个问题 如 果 一 个 样本 属 于 第 类 那么其近邻将属于哪个类别？根 据分类方法的分类原则可知 的大部分近邻将和 属 于 同 一类 别 如果上述分析成立的话 如 何 使 得 被 正 确 分 类 呢？这里首先介绍一个非线性降维方法 局 部 线 性 嵌 入 方法 方 法 有 一 个 前提 假 设 即使高维样本数据分布在一个非线性的流形上该流形的局部区域仍然满足线性关系 也 就 是 说 每 个 样本及其局部近邻位于一个 近 似 的 局 部 线 性 块 上 用 这些局部线性块来近似的描述流形结构的重要意义在于 其近似的表示不会引起太大的误差 其 原 因 在 于 当 对 流 形进行局部分析时 其局部区域并不会包括太多的曲形结构从而用线性超平面来近似表示是可行的 此 外 在 过 去 的几 年 内 相关作者提出许多基于 的 一 类 算 法算 法 以及正交近邻保持映射所有这些方法的成功应用证明了 的 前 提 假设 即非线性流形的局部块满足线性关系是可信的现在 回到上面的问题 对 于 一 个 测 试 样 本算法如何进行正确分类 根 据 算 法 可 知 在 样 本 集 的数据 量 比 较 充 足 的 情 况 下 样本集中的每个样本及其局部近 邻 将 位 于 一 个 近 似 的 局 部 线 性 块 上 也 就 是 说 如果 测 试 样 本 距 离 其 在 第 类 的 近 邻 比 较 近 的 话 那 么式 中的线性重构残差 将 会 非 常 的 小与此 同 时 根 据 的 分 类 原 则 可 知 与其局部近邻属于 同 一 个 类 别 但 是 对 于 那 些 距 离 比 较 远 的 样 本的分类原则将不再适用 针 对 算 法 判 别 性 的 分析 如 下 若 测 试 样 本 属 于 第 类 那 么 根 据 分 类 准则 与 其 在 第 类 的 近 邻 之 间 的 距 离 比 之 与 其 它类 别 中 的 近邻之间的距离 将 会 明 显 的 小 即 第 类 近 邻对 的线性重构残差 将明显小于其它类别近 邻 对 的线性重构残差 其 中且具 体 而 言 根 据 分类方法的分类准则 样 本 在第类 的 近邻中的大部分样本将属于 在整个训练集上的近 邻 即 第 类 的 近 邻 是 的 真 实 近 邻 然 而 样 本 在其 它 类 别 的 近邻中的大部分样本将不属于 在 整 个 训 练集 上 的 近 邻 即这些类别中的 近 邻 距 离 比 较 远 于 此同 时 根 据 的 假 设 的这些真实近邻由于距离 比较 近 满 足 局 部 性 因而可以较好的 近 似 线 性 表 示与 之 相 对 地 由于其它类别的 近 邻 距 离 比 较 远 不满 足 局 部 性 因此这些近邻将无法保证可以近似的线性表 示诚 然 与 算法采用稀疏近邻表示方法线性重构相 比 算法通过在整个训练集上优化求得的基可以更好的线性重构测试样本 但 是 这在分类问题中 作用并不是特别明显 相 比 算 法 算 法 在 采 用 稀疏近邻表示方法实现次优的稀疏表示的同时 增 加 了 判 别性 从 某 种 意 义 上 来 说 算法可以被看作是稀疏表示和判别性的一种折衷图 算 法表 示 测 试 样 本 为 在 第 类 的 近邻 为 在 第 类 的 近 邻 对 应 的 实 线 长度 分 别 代 表 第 类重构权值向量 的 两 个 分 量 值 以 及 第类重构权值向量 的 两 个 分 量 值需 要 注 意 的 是 如果通过求解如下的重构误差优化 问 题代 替 式 其将只适用于那些满足局部线性并且全局 非 线 性 的 数 据 集 原 因 在 于 如果数据集满足全局线性关 系 那么对于属于第 类 的 测 试 样 本 来 说 由 于 数 据 集是 局 部 线 性 的 所 以 第 类 的 近 邻 对 的 线 性 重 构 误 差将 会 较 小 但 是 同 时 其它类的近邻对 的线 性 重 构 误 差 也 可 能 比 较 小 因 为 数 据 集是全 局 线 性 的 也 就 是 说 当数据集满足全局线性关系时计算机工程与设计 年可能比较接近甚至大于进 而 测 试 样 本 容 易 被 错 分 然 而 算 法 将 不 会 发生 上 述 情 形 如 图 所 示 虽 然 在 第 类 的 近 邻和 第 类 的 近 邻 都 可 以 很好 的 线 性 重 构 但是第类近邻的线性重构权值向量 和第 类近邻的重 构 权 值 向 量 却 截 然 不 同 详 细 地 相 比而言 距离测试样本 更近 并且 此外 为了使得 和 之间的差异变大被 加 到 式 上 即 式 或 者 式令 的原因在于 距离测 试 样 本 比较远的那些样本在重 构 的 过 程 中 容易产生负的重构权值 即比 较 容 易 大 于 从 而 当时 即使数据集是 全 局 线 性 的 式 中 的 值 仍将远小于 根据上述分析 式 使 得 算 法 不 仅可以处理非线性数据的分类问题 对线性数据同样适用至 此 为 何 算法能够通过稀疏近邻表示方法同时适合处理非线性和线性数据的这个问题已经分析清楚对 于 的 特 点 总 结 如 下 首 先 满 足 局 部 性 对 任意 一 个 测 试 样 本 在每类中计算其 近 邻 其 次 是 线性 重 构 的 及 其 近邻位于一个近似的局部线性块上 从而 可很好的由其近邻来线性表示 再 次 具 有 稀 疏 性只 在 近邻中挑选部分样本来线性重构 最 后 具 有 判别 性 因 为 及 其 近 邻 是 局 部 的 分 类 准 则 指 出与 其 近 邻 属 于 同 一 类 别 因 此 算法可以被看作是吸 收 了 算 法 和 分 类 器 的 优 点 同 时 弥 补 了算 法 的 缺 陷实验验证本文采用 和 两 个 数 据 集 来评估 算法的性能 数据集中的 个训练样本 作 为 训 练 集 个测试样本作为测试集数据集包含 个人以 种 姿 态 以 及 在 种 光 照 条 件下 采集得到的 幅人脸图像 为了和 算法 进 行 比较 本文实验也选用 个人共 计 幅正面人脸图像作为数据集 此外 这 幅图像被随机的分成两个子集 训练集和测试集 其中每个子集都为 幅图像可 分 性 分 析为了 更 好 的 观 察 的 分 类 性 能 本部分实验将同时 列 出 和 的 分 类 结 果 此 外 上 述 三 种 分 类 方法 针 对 降 维 后 的 数 据 分 别 由 以 及降 维 的分类效果也进行了比较 经 验 性 地 手 写体 数 字 分 别 降 到 以 及 维 子 空 间 中 依 次 对 应为 保 留 以 及 的 主 成 分 同 样 地正面人脸图像则分别降到 以 及 维与其它两种方法不同的是 降维方法确定的最大维数比样本类别数少 因 此 确 定 的 手 写 体 数字 图 像 的 低 维 空 间 是 一 个 维 的 子 空 间 对 于正面人脸图像则是 维 的 子 空 间 这里人脸图像降到 维 而 不 是 维 的原因是为了和 两 种降维方法在相同的低维空间进行对比 图 和 图 分 别 列出了 和 三种识别方法在 和上的分类性能对比结果 以及包括上述两个数 据 集 分 别 被 和 降到不同低维子空间后的 分 类 效 果 此 外 上述三种分类方法针对由 降 到维 的 数 据 集 的 分 类 结 果 的 比 较 在 表 中 单 独 列出 其中加下划线的表示更好的结果 从上述数据可以发现 对不同类型数据的可分性均要好于另外两种 方 法表 三 种 方 法 在 上 的 识 别 率表 中 样 本 维 数 已 由 降 到 维 表 示和 的 近 邻 参 数 或 的 稀 疏 度此 外 从 表 图 及 图 中 还 可 以 看 出 实 验 结 果显示了三个重要的现象 首 先 在 正 面 人脸 数 据 集 上 当数据维数分别为 和由 降 维 时 方法的分类结果毫无疑问的均要好于 和 其中 如 图 所 示 当 稀 疏 度时 方法甚至达到了 的 正 确 识 别 率 其 原 因如下 由 于 人脸图像在采集过程中 每 个人在一种特定姿势的情况下 拍 摄 的 幅基于不同光照环境的图像的这个环节是在两秒左右的时间内完成的 幅秒 因 此 该 幅 图 像 中 人脸位置的变化以及面部表情的变化都非常小 也 就 是 说 该 幅图像近似的只受光 照 变 化 的 影 响 文 献 指 出 若 人 脸 或 者 其 它 任意对 象 的 象素图像只受光照变化的影响 那 么 任 意 的这 些 图 像 都 将 位 于 图像空间的一个凸锥里 文 献指 出 上述凸锥可以近似的由一个低维线性子空间表示 从 而 可 知 上 面 提 及 的 数 据 集 中 每 个人 的 正 面 幅人脸图像由于近似的只受光照的影响 因此 每个类别的图像近似的位于一个线性子空间中 即满 足 算法成立的第一个前提条件 与 此 同 时 不 同 人第 卷 第 期 王琦 惠康华 基于稀疏近邻表示的分类方法之间 的 人 脸 差 异 很 大 这使得各类样本所张成得子空间之间 的 距 离 比 较 远 即 满 足 算法的第二个前提假设当上述两个条件都成立时 算法取得非常好的分类效果也就理所当然了 此 外 当 人 脸 图 像 被 降 到 维时 由 于 是 线 性 降 维 方 法 同 时 维 子 空 间 保 留了 原 始 人 脸 图 像 的 主 成 分 也 就 是 说 维 的 子 空间近似的保持了原始高维空间的线性结构 从 而维的子空间可以近似的被看作是一个线性子空间图 手写体数字识别结果图 中 原 始 样 本 分 别 由 和 降 到和 维 子 空 间 中 每 个 子 图 的 坐 标 均 表 示 和两种算法选择的不同的近邻参数 或 者 表 示 算法 的 稀 疏 度图 正面人脸图像识别率计算机工程与设计 年图 中 原始样本分别由 以 及 降 到和 维 子 空 间 中 每个子图的横坐标均表示和 两种方法选择的不同的近邻参数 或 者 表 示方 法 的 稀 疏 度然 而 在大多数情形下 上述情况发生了很大的变化比 如 在 数 据 集 上 由于其每类样本所张成的空间不满足 线 性 关 系 从 而 不 满 足 方法的第一个前提假设从图 中 可 以 看 出 在 某 些 情 形 下 的分类性能甚至不 如 分 类 器 但 是 方 法 却 仍 然 有 效 得 到 了的 最 高 识 别 率 进一步地观察可以发现 近 邻 参 数的变 化 对 分类性能影响不大 如 图 以 及 图所 示 在 数 据 集 上 当 在 区 间 里 变化 以 及 在 数 据 集 上 在 区 间 里变 化 对 方法效果的影响都很小最 后 从上述所示的实验结果可以观察到 针 对 由 不同降维方法得到的低维数据 与 相 比 取 得 了更好的分类效果 特 别 地 组合的分类性能总是 好 于 组 合 即 使 是 在 数 据 集上 其 原 因 是 由 和 两种方法的特性决定的 具体而 言 对 于 高 维 数 据 的目标是得到其低维的近邻保 持 的 映 射 虽 然 方法本身是线性降维方法 但 是 在降 维 过 程 中 并不保持原始高维空间的线性结构 而 是 寻找高维数据局部近邻之间的关系 并把这种关系保留在低维嵌 入 空 间 换 句 话 说 即使原始高维空间满足线性关系当该高维数据由 方 法 降 维 后 对应的低维空间将不再满 足 线 性 关 系 但是高维数据的局部近邻关系被保留下来了 进 而 在 理 想 的 情 况 下 原始高维数据中任意一个样本 的 局 部 近 邻 在对应的低维嵌入空间将仍然是该样本的局 部 近 邻 由 此 可 知 降 维 方 法 不 适 合 与 方 法 组合 但 是 非 常 适 合 与 方 法 组 合 即 方 法 需 要线性空间的保证 而 方法需要局部近邻的保持时间复杂度分析假 设 训 练 集 包 含 的 样 本 个 数 为 样 本 类 别 数 为每 个 样 本 的 维 数 为 近 邻 参 数 为 算 法 的 时 间复杂度如下所示单位化所有样本计 算 近 邻求解最小化的优化问题计算局部稀疏表示残差由 于 方法没有详细的讨论式 中 的 参 数 如 何选 择 因 此 在 本 文 算 法 实 验 中 用 范 数 取 代范 数 范数的优化问题是个 问 题 其 时 间 复 杂度 为 ！！ ！ 因 此 实 验 中 采 用 算 法求 范数的近似最优解 从 实 验 来 看 范 数 求 得 的 虽 然是 近 似 解 但 是 与 范数求得的最优解相比 分 类 正 确 率相差 很 小 方 法 需 要 运 行 次才能得到稀疏度为的 稀 疏 表 示 其时间复杂度如下所示单位化所有样本求 解 范数最小化问题计算稀疏表示残差从上述两种方法的时间复杂度对比来看 和两种方法的时间复杂度依赖于近邻参数 样 本 维数以及样本个数 当 时 方法的时间复杂度将 主 要 由 其 步 骤 决 定 也 由 其 步 骤 决 定此 时 由 于 在每个类别中均要寻找 近 邻 其 时 间 复杂 度 将 是 的倍 但 是 要 远 低 于 方 法 当 值 逐渐 变 大 时 的 时 间 复 杂 度 将 主 要 由 步 骤 和决 定 对 应 地 时间复杂度则仍然由步骤 决 定此 时 的时间复杂度依然远低于 尤 其 是 值增 加 且 值 很 大 时 的字典将非常庞大 其 优 化 过 程很 费 时 图 显示了上述三种分类方法在 和数据集上的时间花费 从 图 可 以 发 现 当值 很 小 时 算法的时间花费与 相 比 相 差 不大 但 是 当 值 增 加 时 两者区别则明显变大 然 而 在各 种 情 形 下 的时间花费都要低于 其 主 要 原因 是 需要在整个训练集上求解线性重构的权值向量而 只需要在局部近邻上求解 通 常 这 也 支 持了本文开头的讨论图 及 在两个数据集上的时间花费
　　结束语
　　理论分析和实验结果指出 方法高的分类性能需要满足两个前提假设 每类的训练样本分布在一个线性子 空 间 里 不同类别样本张成的子空间之间不能相交或第 卷 第 期 王琦 惠康华 基于稀疏近邻表示的分类方法者距 离 比 较 近 然 而 对于现实生活中的真实数据集来说上述两个假设是很难同时满足的 针 对 上 述 问 题 本 文 提出基于稀疏近邻表示的分类方法 其可被看作兼顾了和 两 个 分 类 方 法 的 特 性 与 方法假设过于牵强不 同 方 法 假 设 即使整个数据集是非线性的 每个样本及其局部近邻仍然位于一个 近 似 的 局 部 线 性 块上 这 也 是 算 法 的 前 提 假 设 而 且 通过本文实验也证 明 这 个 假 设 是 可 行 的 此 外 针对由不同降维方法进行降维后的数据集分类问题 在大多数情形下 方 法的识别结果要好于 方 法 尤其当降维方法是通过保持高维数据的局部近邻关系得到低维样本的 进 一 步 地方法的时间复杂度要远低于 总 而 言 之方 法 可 以 被 看 作 是 针对非线性数据集的一种重要 补 充