Lasso问题的最新算法研究-论文

Ｉ Ｓ Ｓ Ｎ　 １ ０ ０ ４ — ９ ０３ ７ ， ＣＯＤＥＮ　 Ｓ ＣＹＣＥ４ 　

Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｆ 　 Ｄａ ｔ ａ 　 Ａｃ ｑ ｕ ｉ ｓ ｉ ｔ ｉ ｏ ｎ 　 ａ ｎ ｄ 　 Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ 　 Ｖｏ １ ． ３ ０， Ｎｏ ．１ ， Ｊ ａ ｎ ． ２ ０ １ ５， Ｐ Ｐ ． ３ ５— ４ ６ 　 Ｄ ｏＩ ： １ ０ ． １ ６ ３ ３ ７ ／ ｊ ． １ ０ ０ ４ — ９ ０ ３ ７ ． ２ ０ １ ５ ． ０ １ ． ０ ０ ３ 　

ｈ ｔ ｔ ｐ ： ／ ／ ｓ ｊ ｃ ｊ ． ｎ ｕ ａ ａ ． ｅ ｄ ｕ ． ｃ ｎ 　 Ｅ — ｍａ ｉ ｌ ： ｓ ｊ ｃ ｊ ＠ｎ ｕ ａ ａ ． ｅ ｄ ｕ ． ｃ ａ 　 Ｔｅ ｌ ／ Ｆａ ｘ： ＋８ ６ － ０ ２ ５ — ８ ４ ８ ９ ２ ７ ４２ 　

◎ ２ ０ 　 １ 　 ５ 　 ｂ ｙ 　 Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｆ 　 Ｄ ａ ｔ ａ 　 Ａｃ ｑ ｕ ｉ ｓ ｉ ｔ ｉ ｏ ｎ 　 ａ ｎ ｄ 　 Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ 　

Ｌａ ｓ ｓ ｏ问题 的最 新 算 法研 究　
刘 　柳 　 陶大程 　
（ 悉 尼 科 技 大 学 工 程 与信 息 技 术 学 院量 子 计 算 与 智 能 系 统 研 究 中心 ， 悉尼 ， 澳 大利 亚 ， ２ ０ ０ ７ ） 　

摘　 要 ：随 着 大规 模 数 据 的增 加 ， 解决 Ｌ ａ ｓ ｓ ｏ问题 成 为 一 个新 的 热 点 ， 以往 的 方 法很 难 满 足 大 数 据 背 景　 下 的 时 间 和 效 率 问题 。为 了解 决 大规 模 数 据 及 高维 数 据 而 带 来 的 计 算 和 储 存 的 困难 ， 本 文 从 三 个 方 面　 分析 最 新 的 算 法 ， 即一阶方法 、 随 机 方 法及 并 行 和 分 布 计 算 。本 文 介 绍 和 分 析 了解 决 最 小收 缩 和 选 择 算　

子（ Ｌ ｅ ａ ｓ ｔ 　 ａ ｂ ｓ ｏ ｌ ｕ ｔ ｅ 　 ｓ ｈ ｒ ｉ ｎ ｋ ａ ｇ ｅ 　 ａ ｎ ｄ 　 ｓ ｅ ｌ ｅ ｃ ｔ ｉ ｏ ｎ 　 ｏ ｐ ｅ ｒ ａ ｔ ｏ ｒ ， Ｌ ａ ｓ ｓ ｏ ） 问题 的 最 新 算 法 ： 梯度下降方法 、 交 替 方 向 乘　
子 法（ Ａｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ 　 ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ 　 ｍｅ ｔ ｈ ｏ ｄ 　 ｏ ｆ 　 ｍｕ ｌ ｔ ｉ ｐ ｌ ｉ ｅ ｒ ｓ ，ＡＤ ＭＭ ） 和 坐标 下 降 方 法 。其 中梯 度 下 降 结合 一 阶 方　 法 和 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ的 加 速 和 光 滑技 术 ； 交替 方 向 乘 子 方 法 将 随 机 方 法 融 入 在 最 新 的 算 法 中； 坐 标 下 降 方 法　

利 用其 坐标 系的 特 点 结 合 一 阶 方 法 、 随机方法和并行和分布计算 ， 本 文 分 别 从 原 始 目标 函数 和 对 偶 目标　
函数 的 角度 对 算 法进 行 分 析 和研 究 。 　

关 键 词 ：Ｌ ａ ｓ ｓ ｏ问题 ； 一阶方 法； 随机 方 法 ； 交替 方 向 乘子 法 ； 坐标 下 降　
中 图分 类 号 ：ＴＰ１ ８ １ 　 文献 标 志 码 ： Ａ 　

Ｒｅ ｖ ｉ ｅ ｗ　 ｏ ｎ 　 Ｒｅ ｃ ｅ ｎ ｔ 　 Ｍｅ ｔ ｈ ｏ ｄ 　 ｏ ｆ 　 Ｓ ｏ ｌ ｖ ｉ ｎｇ 　 Ｌａ ｓ ｓ ｏ 　 Ｐｒ ｏ ｂ ｌ ｅ ｍ　
Ｌｉ ｕ 　 Ｌｉ ｕ，Ｄａ ｃ ｈ ｅ ｎ ｇ 　 Ｔａ ｏ 　
（ Ｑｕ ａ ｎｔ ｕｍ　 Ｃｏ ｍｐ ｕｔ ａ ｔ ｉ ｏ ｎ＆ Ｉ ｎ ｔ ｅ ｌ ｌ ｉ ｇ ｅ ｎｔ 　 Ｓｙ ｓ ｔ ｅ ｍｓ ，Ｆａ ｃ ｕ ｌ ｔ ｙ 　 ｏ ｆ 　 Ｅｎ ｇ ｉ ｎ ｅ ｅ ｒ ｉ ｎ ｇ 　 ａ ｎ ｄ 　 Ｉ ｎ ｆ ｏ ｒ ｍａ ｔ ｉ ｏ ｎ 　 Ｔｅ ｃ ｈ ｎ ｏ ｌ ｏ ｇ ｙ，Ｕｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ 　 ｏ ｆ 　 Ｔｅ ｃ ｈ ｎｏ ｌ ｏ ｇ ｙ。 　
Ｓ ｙ ｄ ｎ ｅ ｙ ，Ａｕｓ ｔ ｒ ａ ｌ ｉ ａ ，２ ０ ０ ７ ） 　

Ａｂ ｓ ｔ ｒ ａ ｃ ｔ ：Ｗ ｉ ｔ ｈ 　 ｔ ｈｅ 　 ｉ ｎｃ ｒ ｅ ａ ｓ ｅ 　 ｏ ｆ 　 ｂ ｉ ｇ 　 ｄ ａ ｔ ａ ，ｓ ｏ ｌ ｖ ｉ ｎ ｇ 　 Ｌａ ｓ ｓ ｏ 　 ｐ ｒ ｏ ｂ ｌ ｅ ｍ　 ｂ ｅ ｃ ｏ ｍｅ ｓ 　 ｔ ｏ ｐ 　 ｒ ｅ ｓ ｅ ａ ｒ ｃ ｈ 　 ｆ ｉ ｅ ｌ ｄ ．Ｐａ ｓ ｔ 　 ｍｅ ｔ ｈ ｏ ｄ ｓ 　 ｃ ｏ ｕ ｌ ｄ 　 ｎ ｏ ｔ 　 ｓ ａ ｔ ｉ ｓ ｆ ｙ 　 ｔ ｈ ｅ 　 ｔ ｉ ｍｅ 　 ａ ｎ ｄ 　 ｅ ｆ ｆ ｉ ｃ ｉ ｅ ｎ ｔ 　 ｐ ｒ ｏ ｂ ｌ ｅ ｍ　 ｕ ｎｄ ｅ ｒ 　 ｂ ｉ ｇ 　 ｄ ａ ｔ ａ 　 ｓ ｉ ｔ ｕ ａ ｔ ｉ ｏ ｎ ．Ｉ ｎ 　 ｏ ｒ ｄ ｅ ｒ 　 ｔ ｏ 　 ｄ ｅ ａ ｌ 　 ｗｉ ｔ ｈ 　 ｄ ｉ ｆ ｆ ｉ ｃ ｕ ｌ ｔ ｙ 　 ｏ ｆ 　 ｃ ｏ ｍｐ ｕ ｔ ａ ｔ ｉ ｏ ｎ 　 ａ ｎ ｄ 　 ｓ ｔ ｏ ｒ ａ ｇｅ 　 ｂ ｒ ｉ ｎ ｇ ｉ ｎ ｇ 　 ｆ ｒ ｏ ｍ　 ｈ ｕ ｇ ｅ — ｓ ｃ ａ ｌ ｅ 　 ａ ｎｄ 　 ｈ ｉ ｇ ｈ — ｄ ｉ ｍｅ ｎ ｓ ｉ ｏ ｎ 　 ｄ ａ ｔ ａ，ｔ ｈ ｉ ｓ 　 ｐ ａ ｐ ｅ ｒ 　 ａ ｎ ａ ｌ ｙ ｚ ｅ 　 ｔ ｈｅ 　 ｒ ｅ ｃ ｅ ｎ ｔ 　 Ｌａ ｓ ｓ ｏ 　 ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ　 ｆ ｒ ｏ ｍ　 ｔ ｈ ｒ ｅ ｅ 　 ａ ｓ ｐ ｅ ｃ ｔ ｓ：ｏ ｎ ｅ — ｏ ｒ ｄ ｅ ｒ 　 ｍｅ ｔ ｈ ｏ ｄ，ｒ ａ ｎ ｄ ｏ ｍ ，ａ ｎ ｄ 　 ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ 　 ａ ｎ ｄ 　 ｄ ｉ ｓ ｔ ｒ ｉ ｂ ｕ ｔ ｅ ｄ 　 ｃ ｏ ｍｐ ｕ ｔ ａ — 　 ｔ ｉ ｏ ｎ，ｗｈ ｉ ｃ ｈ 　 ｐ ｌ ａ ｙ 　 ａ ｎ 　 ｉ ｍｐ ｏ ｒ ｔ ａ ｎ ｔ 　 ｒ ｏ ｌ ｅ ｓ 　 ｉ ｎ 　 ｄ ｅ ａ ｌ ｉ ｎｇ 　 ｗｉ ｔ ｈ 　 ｈ ｕｇ ｅ — ｓ ｃ ａ ｌ ｅ 　 ｄ ａ ｔ ａ 　 ｐ ｒ ｏ ｂｌ ｅ ｍ ． Ｂａ ｓ ｅ ｄ 　 ｏ ｎ 　 ｔ ｈ ｏ ｓ ｅ 　 ｔ ｈ ｒ ｅ ｅ 　 ａ ｓ — 　 ｐ ｅ ｃ ｔ ｓ ，ｔ ｈ ｉ ｓ 　 ｐ ａ ｐｅ ｒ 　 ｉ ｎ ｔ ｒ ｏ ｄ ｕ ｃ ｅ ｓ 　 ａ ｎ ｄ 　 ａ ｎ ａ ｌ ｙ ｚ ｅ ｓ 　 ｔ ｈ ｅ 　 ｎ ｏ ｖ ｅ ｌ 　 ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍｓ ：ｇｒ ａ ｄ ｉ ｅ ｎ ｔ 　 ｄ ｅ ｓ ｃ ｅ ｎ ｔ 　 ｍｅ ｔ ｈ ｏ ｄ，Ａｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ 　 Ｄｉ — 　 ｒ ｅ ｃ ｔ ｉ ｏ ｎ 　 ｍｅ ｔ ｈ ｏ ｄ 　 ｏ ｆ 　 ｍｕ ｌ ｔ ｉ ｐ ｌ ｉ ｅ ｒ ｓ（ Ａ ＤＭ Ｍ ），ａ ｎ ｄ 　 ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ｄ ｅ ｓ ｃ ｅ ｎ ｔ 　 ｍｅ ｔ ｈ ｏ ｄ ． Ｇｒ ａ ｄ ｉ ｅ ｎ ｔ 　 ｄ ｅ ｓ ｃ ｅ ｎ ｔ 　 ｍｅ ｔ ｈ ｏ ｄ 　 ｃ ｏ ｍ— 　

ｂ ｉ ｎ ｅ 　 ｏ ｎ ｅ — ｏ ｒ ｄ ｅ ｒ 　 ｍｅ ｔ ｈ ｏ ｄ 　 ａ ｎｄ 　 Ｎｅ ｓ ｔ ｅ ｒ ｏｖ 　 Ｓ 　 ａ ｃ ｃ ｅ ｌ ｅ ｒ ａ ｔ ｅ 　 ａ ｎ ｄ 　 ｓ ｍｏ ｏ ｔ ｈ ｉ ｎｇ 　 ｍｅ ｔ ｈ ｏ ｄ； Ａ ＤＭ Ｍ 　 ｐ ｕ ｔ 　 ｔ ｈ ｅ 　 ｒ ａ ｎ ｄ ｏ ｍ　 ａ ｌ ｇ ｏ — 　 ｒ ｉ ｔ ｈｍ　 ｉ ｎ ｔ ｏ 　 ｔ ｈ ｅ 　 ｒ ｅ ｃ ｅ ｎｔ 　 ｒ ｅ ｓ ｅ ａ ｒ ｃ ｈ；Ｃｏ ｏ ｒ ｄ ｉ ｎａ ｔ ｅ 　 ｄ ｅ ｓ ｃ ｅ ｎ ｔ 　 ｍａ ｋ ｅ 　 ｕ ｓ ｅ 　 Ｏ ｆ 　 ｔ ｈｅ 　 ｃ ｈ ａ ｒ ａ ｃ ｔ ｅ ｒ 　 ｏ ｆ 　 ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ｓ ｙ ｓ ｔ ｅ ｍ　 ｉ ｎ ｃ ｏ ｒ — 　
ｐ ｏ ｒ ａ ｔ ｉ ｏ ｎ 　 ｏ ｎ ｅ — ｏｒ ｄ ｅ ｒ 　 ｍｅ ｔ ｈ ｏ ｄ， ｒ ａ ｎｄ ｏ ｍ ，ａ ｎ ｄ 　ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ 　 ａ ｎｄ 　 ｄ ｉ ｓ ｔ ｒ ｉ ｂ ｕ ｔ ｅ ｄ 　 ｃ ｏ ｍｐ ｕ ｔ ａ ｔ ｉ ｏ ｎ ． Ｍｏ ｒ ｅ ｏ ｖ ｅ ｒ ，ｔ ｈ ｉ ｓ 　 ｐ ａ ｐ ｅ ｒ 　

ｍａ ｋ ｅ ｓ 　 ａ 　 ｄ ｅ ｅ ｐ 　 ａ ｎ ａ ｌ ｙ ｓ ｉ ｓ 　 ａ ｎ ｄ 　 ｒ ｅ ｓ ｅ ａ ｒ ｃ ｈ 　 ｆ ｒ ｏ ｍ　 ｐ ｒ ｉ ｍａ ｌ 　 ａ ｎ ｄ 　 ｄ ｕ ａ ｌ 　 ｏ ｂ ｊ 　 ｅ ｃ ｔ ｉ ｖ ｅ 　 ｆ ｕ ｎ ｃ ｔ ｉ ｏ ｎ ． 　
Ｋｅ ｙ 　 ｗｏ ｒ ｄ ｓ ：Ｌａ ｓ ｓ ｏ 　 ｐ ｒ ｏ ｂ ｌ ｅ ｍ ；ｏ ｎ ｅ — ｏ ｒ ｄ ｅ ｒ 　 ｍｅ ｔ ｈ ｏ ｄ；ｒ ａ ｎｄ ｏ ｍ　 ｍｅ ｔ ｈ ｏ ｄ；ＡＤＭ Ｍ ；ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ｄ ｅ ｓ ｃ ｅ ｎｔ 　 ｍｅ ｔ ｈ ｏ ｄ 　

收稿 日期 ： ２ ０ １ ４ — １ ０ — １ ０ ； 修 订 日期 ： ２ ０ １ ４ — １ ２ － ３ ０ 　

３ ６ 　

数 据 采 集 与 处理 Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｆ 　 Ｉ Ｄ ａ ｔ ａ 　 Ａｃ ｑ ｕ ｉ ｓ ｉ ｔ ｉ ｏ ｎ 　 ａ ｎ ｄ 　 Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ 　 Ｖｏ １ ． ３ ０ ， Ｎｏ ． １ ，２ ０ １ ５ 　

引　

言　
随 着 科技 的进 步 ， 收 集 数 据 的技 术 也 有 了 很 大 的 发 展 。 因此 如 何 有 效 地 从 数 据 中挖 掘 出有 用 的 信　

息 也 越 来 越 受 到 人们 的关 注 。一 般 采 用 基 于 机 器学 习 和 统 计 的方 法 来 解 决 大 规 模 数 据 ， 这 种 趋 势 称 为　 “ 大数据” 。它在 很 多领 域 中起 着 非 常 重 要 的 作 用 ， 如人工智 能 、 网络 应 用 、 计算生 物 、 医学 、 金 融 和 市 场　

等 。虽 然 应 用在 不 同 的方 面 ， 但 是 大 数 据 问 题 却 又 几个 共 同 的特 点 ： （ １ ） 数据量非常大 ， 包 含 几 百 万 个 或　 上亿个训练样本 ； （ ２ ） 数 据 的维 度 很 高 ， 通 常 会详 细 记 录 每 一 个 样 本 的 的信 息 ； （ ３ ） 大 规模 的 数 据 通 常 以 　
分 布 式 的 方 式储 存 或 收集 。在 机 器 学 习 的算 法 中 ， 对 最 新 算 法 的要 求 既 能 够 解 决 数 据 的 复 杂 性 又 能 够　 采 用 平 行 或 分 布 式 的 方 法处 理 大数 据 。 　 Ｌ ａ ｓ ｓ ｏ问题 是 １ ９ ９ ６年 Ｔｉ ｂ ｓ ｈ ｉ ｒ ａ ｎ ｉ 　 使 用 ｕ 惩 罚 因 子解 决 含 有 独 立 高 斯 分 布 的 线 性 回归 问 题 ， Ｌ ａ ｓ ｓ ｏ 　 问题 包 含 平 方 误 差 的 求 和 以及 Ｌ１正 则 化 项 。虽 然 Ｌ ａ ｓ ｓ ｏ问题 出 现 的 比较 晚 ， 然而正则 化项 早在 １ ９ ４ ３ 　

年 Ｔ ｉ ｋ ｈ ｏ ｎ ｏ ｖ 就 提 出用 来 逼 近 不 可解 的 整数 等 式 问 题 。通 常 情 况 下 ， 在 参 数 中增 加 约 束 化 项 ， 用 来 求 解　
评 估 问题 ， 如 最 大 似 然 函 数 。正 则 化 项 用 来 减 小 变 量 从 而 避 免 过 拟 合 ， 得 到 的正则化 项 的解更 稳 定 ， 　 Ｂ ｉ ｃ ｋ ｅ ｌ ｌ ２ 　 给 出 了 正则 化 项 在 统 计 理 论 中详 细 的 分 析 。 　

Ｌ ａ ｓ ｓ ｏ问题 在 解 决 稀 疏 规 划 中起 着 非 常 重 要 的作 用 。它 可 以解 释 为 寻 找 最 小 二 乘 或 线 性 回归 问 题　 的稀 疏 问题 ， 即采 用 若 干 个 非零 的 变量 。Ｌ ａ ｓ ｓ ｏ问题 在 信 号 处 理 领 域 中 同 样 起 着 重 要 的作 用 ， 包 括 解 决　 稀疏 信 号修 复　 、 稀疏 回 归 　 ］ 、 稀 疏 图 回 归　 ］ ， 稀 疏 逆 协 方 差　 和 稀 疏 字 典 的 学 习口 ］ 。生 物 数 据 的 分　
析　］ ， 比如 选 取 大 数 据 中 的－ －４ ， 部 分 来 预 测 结 果 。Ｌ ａ ｓ ｓ ｏ问题 同 样 可 以应 用 在 视 频 中 ， Ｇｅ ｎ ｇ 　 采 用 并 行　 Ｌ ａ ｓ ｓ ｏ的 方 法 解决 大 规 模 视 频 概 念 检 测 ， Ｚ ｈ ｕ ｌ ５ 　 使 用 Ｇｒ ｏ ｕ ｐ 　 Ｌ ａ ｓ ｓ ｏ解 决 视 频 标 签 以及 Ｚ ｈ ｏ ｕ 　 用 稀疏 离 群　

值分 割移 动 目标 。在 图像 处 理 中 ， Ａ ｆ ｏ ｎ ｓ ｏ 　 使用 Ｌ ａ ｓ ｓ ｏ方法 解 决 图像 修 复 、 图像 去 噪　 和 去 模 糊　 ， 其　 中正 则 化项 是 图像 的梯 度 范 数 、 网页 图 像 排 序　 及 图像 质 量 评 估　 ， 利 用 稀 疏 编码 处 理 图像 标 签　 问 　
题 。在 遥感 领域 中 ， Ｌ ａ ｓ ｓ ｏ问题 用 来 解 决 稀 疏 解 混　 删 ， 从 而 可 以得 到 每 个 端 元 都 含 有 哪 些 物 质 ， 在 航　 天、 农业领域 ， 对 研 究 物 质 成 分 问题 起 着 非 常 重 要 的 作 用 。 　 解决 Ｉ 　 ａ ｓ ｓ ｏ问题 的方 法 有 很 多 ， 其中Ｅ ｆ ｒ ｏ ｎ ＿ １ 　２ ０ ０ ４年 提 出 最 小 角 回 归 ， 它 能 够 有 效 地 解 决 潜 在 的　

Ｌ ａ ｓ ｓ ｏ 优 化 问题 ， 同时 在 统 计 和 机 器 学 习 领域 ， 它 为加速 Ｌ ａ ｓ ｓ ｏ算 法 提 供 了一 个 重 要 的 工 具 。在 解 决 大　
规模数据问题 中， 梯 度下 降方 法 是 最 简 单 的方 法 。Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 　 提 出最 优 的 梯 度 下 降 方 法 和 光 滑 模 型 ， 　

在 Ｌ ａ ｓ ｓ ｏ问 题 中 被广 泛 的应 用 ， 如 快 速 的 交 替 方 向优 化 方 法　 ， 锥 模 型 优 化 方 法　 以 及 快 速 迭 代 收 缩　
阈值 方 法　 。随 着 数 据 量 的 增加 ， ＡＤＭＭ 能 够 解 决 大 数 据 问题 ， 并且 已经成 功地应 用在很 多领域 ， 包　

括解决 Ｌ ａ ｓ ｓ ｏ问 题 ， Ｂｅ ｃ ｋ ｌ ２ 　结 合 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ的加 速 方 法 ， 提 出了快速 的方法 ， 其中Ｔ ｏ ｍ［ ２ 　提 出 了 快 速 的　

Ａ Ｄ ＭＭ 方 法 。最 近 的研 究 者 Ｔ ａ ｉ ｊ ｉ ＿ ２ 　 驯 和 Ｈｕ ａ 　 。 　 结 合大数据 的特点 采用随机 的方法 ， 在 原 有 算 法 的 基　 础上 ， 提 高 了算 法 的收 敛 率 ， 　 在 大 数 据 背 景 下 随 机 坐 标 下 降 方法 成 为一 个 新 的热 点 ， 而 随 机 优 化 方 法 在 解 决 高 维 数 据 和 大 规 模　 样 本 有 至关 重 要 的作 用 。Ｎ ｅ ｓ ｔ ｅ ｒ ｏ ｖ ｌ ２ 　和 Ｊ ｉ ［ 。 　分 别 给 出 了随 机 坐标 下 降方 法 的理 论 分 析 和 证 明 。越 来 越　 多 的 基 于 随机 优 化 方 法 出 现 在 Ｌ ａ ｓ ｓ ｏ问 题 ， 包 括 原 始 随 机 坐 标 下 降 方 法　 法口 　 和 原 始 随 机 对偶 坐标 下 降方 法　 ， 对 偶 随 机 坐 标 下 降 方　 ， 而 且 基 本 的 随 机 下 降 坐 标 方 法 结 合 了 一 阶 最 优 方 法【 ３ 　、 随　

机 方 法 和并 行分 布 系统 ， 这 三 个 方 面 在 解 决 大 规模 数 据 中起 着 非 常 重 要 的作 用 ， 弥 补 了一 般 算 法 在 大 数　
据背景下的不足 ， 其 中 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ加 速 的一 阶 最 优 方 法 ， 只需要 一阶梯度 信息 ， 从 而运算 复杂度 小 、 速 度　

快； 随 机 的 方 法 主要 考 虑大 数 据 的本 质 ， 因为 最 终 决 定 最 优 解 的 信 息 并 不 需 要 全 部 的 数 据 ， 如 果 全 部 的　
数据都用 来 计 算 不 仅 需 要 更 多储 存 空 间， 而且会 消耗更多 的时间， 从 而 影 响 算 法 的 性 能 。 最 近　

Ａｖ ｒ ｏ ｎ 　训 介 绍 了在 随 机 梯 度 和 随 机 坐 标 下 降 方 法 下 的 多 核 运 算 ， 　 算 法 中提 出异 步 并 行计 算 提 高 收敛 率 。 　

在 Ｋａ ｃ ｚ ｍａ ｒ ｚ 算 法 和 坐 标 下 降　

刘柳 等 ： Ｌ ａ ｓ ｓ ｏ问题 的 最 新 算 法 研 究　

３ ７ 　

在解决 Ｌ ａ ｓ ｓ ｏ问 题 的过 程 中 ， 很 多 实 验 室 公 开 了软 件 包 和 代 码 ， 以供 大 家 学 习 和 研 究 ， 其 中包 含 凸　

优化模型框架 Ｃ Ｖ Ｘ 　 ， 它 可 以用 来 解 决所 有 的 凸优 化 问题 ； 压缩感知包 １ １ 一 ＭＡＧ Ｉ Ｃ 　 ， 它 将 问 题 转 化 为　
两阶凸规划 （ Ｓ ｅ ｃ ｏ ｎ ｄ － ｏ ｒ ｄ ｅ ｒ 　 ｃ ｏ ｎ ｅ 　 ｐ ｒ ｏ ｇ ｒ ａ ｍ ，Ｓ ＯＣ Ｐ ｓ ） ， 一 阶锥 模 型 （ Ｔｅ ｍｐ ｌ ａ ｔ ｅ ｓ 　 ｆ ｏ ｒ 　 ｆ ｉ ｒ ｓ ｔ — ｏ ｒ ｄ ｅ ｒ 　 ｃ ｏ ｎ ｉ ｃ 　 ｓ ｏ ｌ ｖ ｅ ｒ ｓ ， 　 ＴＦ ＯＣＳ ） 　 ， 它 主要 是 将 问题 转 化 为 标 准 的 锥模 型 ， 并利用一阶优化方法 ； 共 轭 梯 度 迭 代 方法 （ Ｃｏ ｎ ｊ ｕ ｇ ａ ｔ ｅ 　 ｇ ｒ ａ ｄ ｉ ｅ ｎ ｔ 　 ｉ ｔ ｅ ｒ ａ ｔ ｉ ｖ ｅ 　 ｓ ｈ ｒ ｉ ｎ ｋ ａ ｇ ｅ ／ ｔ ｈ ｒ ｅ ｓ ｈ ｏ ｌ ｄ ｉ ｎ ｇ ， Ｃ ＧＩ Ｓ Ｔ） 　 ， 它 主要 结 合 向 前 向后 分 裂方 法 和加 速 步 长 方 法 。 　

１ 　Ｌ ａ ｓ ｓ ｏ问题　
在 机 器 学 习 的优 化 算 法 中 ， 一 般 的 凸优 化 问题 可 以表 示 为　

ｍ 　 ｉ ｎ 　 Ｐ （ 　 ） 一 　
其 对 偶 函 数 为　

（ 　） ＋ 　（ 　 ） ） 　

（ １ ） 　

｛ 　： 砉 一 　一， 一 Ａ ｇ 　 （ ÷ 砉 　） ） 　
式中 ： ａ 　 ， …， ａ 　∈ Ｒ 　为 ； ７ １ ＂ 个数据样本向量； 　 ， …， 　 为损 失 函数 ； 　 … ． ， 　 为　 的 共 轭 函 数 ； ｇ 　 （?） 为 正 则 化 函数 ； ｇ 　（?） 为 ｇ的共 轭 函 数 ； 　为原始变量 ； Ｙ为 对 偶 变 量 ； 　≥０为 正 则 化 参 数 。 　

每一个样本数据 ｎ 　 对应着一个独立的变量 ｂ 　 ， 当 仍（ ａ Ｔ ｘ ） 一寺 （ ａ Ｔ ｘ —ｂ 　 ） 　 ， ｇ （ 　 ） ＝ｌ 　ｌ ＿ １ ｌ ， 即得到 　
ｚ 　约束 线 性 回归 的 特 殊 形 式 ， 称为 Ｌ ａ ｓ ｓ ｏ问 题 ＿ １ ］ ， 即　

ｍｉ ｎ÷ ｝ ｌ 　 Ａ ｘ—ｂ 　 ＋　 ｌ ｌ 　ｌ 　 　 Ｊ

（ ３ ） 　

式中 ： 变 量 ｘＥ 　 Ｒ 　 ； 矩 阵 Ａ∈Ｒ 　 ； ｂ Ｅ 　 Ｒ 　； 　＞ ０是 尺 度 约束 参 数 。Ｌａ ｓ ｓ ｏ问题 可 以解 释 为寻 找最 小 二　 乘 或线 性 回归 问 题 的 稀 疏 解 。 　

１ ． １ 　 一般 的 Ｌ ａ ｓ ｓ ｏ问题　

ｍｉ ｎ ÷ ｌ 　 ｌ Ａ ｘ—ｂ 　 ｌ ｌ ； ＋　 ｌ ｌ 　 ｌ 　 ｌ
其 中 Ｆ是 任 意 的线 性 变 换 ， 一 个 特 殊 的例 子是 当 Ｆ为 差 异 矩 阵 时 ， 有　
ｆ 　 １ 　 Ｆ 　一　一 １ 　 Ｊ— ｉ ＋１ 　 Ｊ— ｉ 　

（ ４ ） 　

（ ５ ） 　

【 ０ 　

其他　

这 个 问题 转 变 为 Ｔ Ｖ 降 噪 问题　 ， 在 信 号 处 理 中有 广 泛 的应 用 。当 Ａ—Ｉ ， Ｆ是 二 次 差 分 矩 阵 ， 问 题　
变 为 Ｌ１趋 势 滤 波　 ， 用 来 分 析 在 不 同学 科 中 的 时 间 序 列 数 据 。更 新　 的迭 代 过 程 中 ， 矩阵Ａ 　 Ａ＋ Ｆ 　 Ｆ　 是 五对 角矩 阵 ， 只需 运 行 ０（ 　） 的浮点运算 。 　 １ ． ２ 　 组 Ｌａ ｓ ｓ ｏ问题　

ｍ ｉ ｎ 　 １ 　 ｌ 　 Ｉ Ａ ｘ —ｂ 　＋ 　 ∑　
式 中　 一 （ 　

ｌ 　

一 ， 　 ） ， Ｘ 　 ∈Ｒ 　 ， 每一个正则化约束项都是分 开 的， 但并不 是完全 的分开 ， 这种 Ｌ １ 范　

数 约束 的 扩展 问题 称 之 为 组 Ｌ ａ ｓ ｓ ｏ问题　 “ 　， 或者叫做 Ｓ ｕ ｍ　 ｏ ｆ 　 ｎ ｏ ｒ ｍｓ 　 ｒ ｅ ｇ ｕ ｌ ａ ｒ ｉ ｚ ａ ｔ ｉ ｏ ｎ 　 ， 解 决组 Ｌ ａ ｓ ｓ ｏ问　 题 一 般 采 用 分 裂 的方 法 ， 并 对 每 一个 子 问 题 进 行 Ｌ ａ ｓ ｓ ｏ问题 的 处 理 。 　

随着 大规 模 数 据 的增 加 ， 以 往解 决 Ｌ ａ ｓ ｓ ｏ问 题 的 方 法 很 难 满 足 人 们 对 时 间 和 效 率 的 要 求 。 当 数 据　
的维 度 越 来 越 大 ， 函数 值 或 梯 度值 计 算 就 会 变 得 越 来 越 困难 ， 尤 其 是 当数 据 的 空 间维 度 大 于存 储 空 间　 时， 一 般 的梯 度 方 法将 不 再适 用 。如 果储 存 空 间 不 影 响 梯 度 的 运 算 ， 那 么 大 数 据 的 运 算 可 能会 消耗 更 多　

３ ８ 　

数 据 采 集 与 处理 Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｆ 　 Ｄａ ｔ ａ 　 Ａｃ ｑ ｕ ｉ ｓ ｉ ｔ ｉ ｏ ｎ 　 ａ ｎ ｄ 　 Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ 　 Ｖｏ １ ． ３ ０ ， Ｎｏ ． １ ，２ ０ １ ５ 　

的时间， 从 而 在 实 际应 用 中会 受 到影 响 ， 比如 图像 处 理 过 程 。 除 了 数 据 的 大 小 ， 并 不 是 所 有 的数 据 都 要　 用 来 描 述 机 器 学 习 的 相 关 问题 ， 其 中一部分数 据就 可以解决 优化 问题 ， 而 不 是 等 到 全 部 的 数 据 都 处 理　
完 。所 以解 决 这 些 问题 的方 法 不 仅 要 考 虑 算 法 的复 杂 度 ， 而 且 还 应从 实 际 问题 出发 ， 考 虑 如 何 能 够 更 快　 地 解 决 大 规 模 数 据 带 来 的 困难 。 　

２ 　Ｌ ａ ｓ ｓ ｏ问题 解 决 方 法　
大规 模 数 据 下 的 Ｌ ａ ｓ ｓ ｏ问题 主要 面临 着 计 算 复 杂 度 和 时 间 复 杂 度 问 题 ， 而 解 决 这 些 问 题 主 要 从 三　

个 方 面考 虑　 ： （ １ ） 一 阶方 法 。一 阶 方法 使 用 目标 函数 的梯 度 信 息 ， 虽 然 获 得 较 低 或 中等 精 确 的数 值 结　
果， 但 是相 比一 些 复 杂 的运 算 过 程 ， 一 阶 方法 消耗 更 短 的 时 间 。根 据 邻 近 映 射 原 则 ， 一 阶方 法 能 够 解 决　

非 光 滑 函 数 问题 ， 并 且 适 合 分 布 和 并 行 计算 。 （ ２ ） 随 机 性 。随 机 问 题 在 其 他 的 逼 近 问题 中 尤 为 突 出 ， 因　 为 它 能 够 控 制期 望值 ， 从 而 增 加 一 阶 方 法 的 可 扩展 性 。关 键 的 问题 是 随 机 更 新 部 分 变 量信 息 ， 而不 是 全　
部的变量 ， 进 而并 不 需 要 全 部 的 梯 度 信 息 ； 简单 的统计评估 就能 有很好 的计算 结果 ； （ ３ ） 并 行 和 梯 度 计　

算： 一 阶梯 度方 法 能 够 用 在 并 行 计 算 和 分 布 优 化 中 ， 同 时还 可 以从 集 中通 信 的并 行 计 算 扩 展 到分 散 通 信　
的异 步 算 法 。这 ３个 方 面 在 大 数 据 中 起 着 重 要 的作 用 ， 比如 随机 一 阶方 法 比确 定 策 略 的 方法 要 快 ， 它 能　 够 忽 略 一 小 部 分 信 息 而 获得 高 概 率 的最 优 目标 函 数 结 果　 。 　

２ ． １ 梯 度 下 降 方 法　
梯 度 下 降 的 方 法 是 基 于一 阶方 法 ， 利 用 局 部 梯 度 信 息 和 迭代 公 式　
Ｘ 　 一Ｘ 　 一ａ 　 ｆ（ ｘ 　 ） 　 （ ７ ） 　

当 目标 函数 为 光 滑 函 数 时 ， 可 以使 用 更 快 的加 速 方 法 ， 如牛顿方法 ， 但 是 它 需 要 目标 函数 更 多 的信　

息， 比如 二 阶求 导 信 息 ， 从 而 消耗 更 多 的 时 间 ， 而 这 些 信 息 并 不 容 易 在 约 束 函数 和 非 光 滑 函数 中得 到 。 　 梯 度 下 降 法 却 弥 补 了这 些 缺 点 。一 般 的梯 度 下 降 方 法 需 要 ０ （ Ｉ ／ ｅ ） 的迭代次数才 能达到 ￡ 的精确结果 。 　
Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 　 提 出 了一 个 改 进 ， 增 加 一 个 额 外 的 动量 步长 ． ８ 一是 ／ （ 走 ＋１ ）， 从 而 到 达 到 ０（ １ ／ ｅ 　 ） 的迭代次 数 ， 　 这种 方 法 称 为 最 优 一 阶 方 法 。表 １给 出 了加 速 方 法 在 凸 函 数 和 强 凸 函数 中 的算 法 复 杂 度 。为 了能 够 得　

到强 凸 函数 ， 可 以在 目标 函数 中 增加 约 束 化 项 。 因为 如 果 函数 ｆ （ ｘ ） 一／ ￣ ／ ２ ｘ ； 是 凸 函数 的 ， 那 么 是 厂（ 　 ） 　
强 凸 函数 ， 所 以非 光 滑 函数 也 可 以有强 凸 函数 的性 质 ， 在 Ｌ ａ ｓ ｓ ｏ函数 中增 加 一 个 约 束 项 ， 即 ｇ（ 　） ＝Ｘ 　 ＋　 ／ ￣ ／ ２ ｘ ； 。 　
表 １ 梯 度 下 降 方 法 的 算 法 复 杂 度 比较　
Ｔａ ｂｌ ｅ 　 ｌ 　 Ｃｏ ｍｐ ｌ ｅ ｘｉ ｔ ｙ 　 ｏ ｆ 　 ｔ ｈｅ 　 ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈｍ　 ｃ ｏ ｍ ｐａ ｒ ｉ ｓ ｏ ｎ 　 ｏ ｆ 　 ｇ ｒ ａ ｄｉ ｅ ｎｔ 　 ａ ｓ ｃ ｅ ｎｔ 　 ｍｅ ｔ ｈｏ ｄ 　

２ ． １ ． １ 　 邻 近 梯 度 方 法　

邻 近 算 法　 可 以 看 成是 解 决 非 光 滑 、 约束 、 大 规 模 和 分 布 式 问 题 的 工 具 。邻 近 算 法 可 以 看 成 是 求　
解一部分凸优化问题 ， 从 邻 近运 算 定 义 可 以看 出　
， 　 １ 　 、 　

ｐ ｒ ｏ ｘ 　 （ ． ） ， ） 一ａ ｒ ｇ ｍ ｉ ｎ ｛ ｇ （ 　 ） ＋寺 ｌ 　 —Ｙ 　 Ｉ Ｉ ； ｝ 　
、 　

（ ８ ） 　

函数 的邻 近 运 算 等 价 于 求 解 函数 的梯 度 步长 ｐ ｒ ｏ ｘ 　 （ ｙ ） 一Ｙ — 　 ｇ （ 　 ）。 　 Ｌ ａ ｓ ｓ ｏ函 数是 一 般 混 合 目标 函数 的 一 种 特殊 形式 ， 邻 近 梯 度 方 法 可 以 利 用 混 合 函数 的性 质 ， 获 得 在　 光滑 梯 度 方 法 下 的相 同的 收 敛速 度 （ 如表 １ ） ， 邻 近梯 度 方 法 可 以看 成 是 最 优 梯 度 方 法 的 扩 展 ， 于 是 原 始　 的Ｌ ａ ｓ ｓ ｏ问题 结 合 最 优 梯 度方 法 和邻 近梯 度 方 法 ， 得到基于 Ｘ 　 展 开 的 目标 函数　

刘柳 等 ： Ｌａ ｓ ｓ ｏ问题 的 最 新 算 法研 究　

３ ９ 　

一 ａ ｒ ｇ 　 ｉ “ ｛ ＿ 厂 （ 　 ） ＋ Ｖ ｆ （ ｘ 　 ） 　 （ 　 一 　） ＋ 壶ｌ 　 ｌ ｙ 一 　ｌ ｌ ； ＋ ｇ （ ｙ ） ｊ 　
应 用 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ的加 速 方 法 ， 得 到加 速 的邻 近梯 度 方 法　
Ｘ ｋ ＋ 　一 ｐ ｒ ｏ ｘ 　（ ｖ 　 一ａ ＾ 　 ｆ（ ｖ 　 ）） 　
… 一Ｘ 　 ＋　 （ 　 ） 　

（ ９ ） 　
（ １ ０ ） 　

在 Ｌ ａ ｓ ｓ ｏ问题 中 ｇ（ ｚ ） 为 Ｌ１范 数 ， 邻 近 运 算 可 以通 过 软 阈值 的方 法 求 解 ， 这 种 加 速 的 方 法 称 为 快 速　 收 缩 阈值 算 法 （ Ｆ ａ ｓ ｔ 　 ｉ ｔ ｅ ｒ ａ ｔ ｉ ｖ ｅ 　 ｓ ｈ ｒ ｉ ｎ ｋ ａ ｇ ｅ ／ ｔ ｈ ｒ ｅ ｓ ｈ ｏ ｌ ｄ ｉ ｎ ｇ 　 ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ， Ｆ Ｉ Ｓ ＴＡ） 　 。除 了 在 迭 代 步 骤 能 够 减 少　

迭代次数 、 增 加 收敛 率 ， Ｂ ｌ ａ ｃ ｋ ｆ ｏ ｒ ｄ 　
２ ． １ ． ２ 对 偶 锥 方 法　

采 用 了并 行 矩 阵 一 向量 相 乘 的方 法 来 加 速 运算 。 　

对 偶 锥　 方 法 结 合 对 偶 、 光 滑和一阶优 化方法 ， 用 来 解 决 一 般 的 凸 锥 优 化 问题 。该 方 法 的 优 点 是　 能够得到稳定 、 有 效 的迭 代 方 法 。不 用 于邻 近梯 度 方 法 ， 对 偶 锥 方 法 在 对 偶 函数 中加 入 一 阶 优 化 方 法 。 　

在 原 始 函数 中 ， 这 两 种 方 法 都 增 加 了 一个 约 束项 ， 使 得 目标 函 数 为 强 凸 函数 ， 从 而 达 到表 １中 的收 敛 速　 度 。对 偶 锥 方 法 可 以看 成 是 不 断 的缩 减原 始 和对 偶 函数 差 值 ， 当 原 始 函 数值 和 目标 函数 值 相 同 时 ， 即 达　
到 最 优 解 。对 偶 锥 方 法 包 含 ４个 步 骤 。 　 （ １ ） 确 定 等 价 的锥 形 式　
Ｌａ ｓ ｓ ｏ问题 的 锥 形 式 可 以表 示 为　

ｍｉ ｎ 　 ｌ 　 ｌ ｌ 　 ｌ １ 　 Ｓ ． ｔ ．１ 　 ｌ （ ２ ） 确 定 对 偶 形 式　 原 始 函数 不 采 用 一 阶优 化 方 法 有 几 种 可 能 ： （ １ ） 原函数非光 滑 ； （ ２ ） 投影在 ｌ ｌ 　 Ａ 　 ｂ 　 Ｉ Ｉ ≤￡ 需 要 消 耗　 大量 的时间 ， 所 以将 问题 转 化 为 对偶 问 题 用 于 减 少 运 算 时 间 ， 对 偶 问 题 表 示 为　 ｍａ ｘ 　 ｉ ｎ ｆ ｛１ 　
（ ３ ） 应 用 光 滑技 术　

一ｂ 　 ｌ ｌ≤ ｅ 　

（ １ １ ） 　

１ 一＜ ｚ ， Ａ ｘ一 ６ ） ｝ 　

（ １ ２ ） 　

Ｌａ ｓ ｓ ｏ问 题 中 含 有 Ｌ１范 数 ， 从 而 应 用 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ的光 滑 技 术 ， 在 原 目标 函数 中增 加 约束 项 ， 得 到 光 滑　
的对 偶 问题　

Ｄ 　 （ 　 ） 一ｍ ａ ｘ 　 ｉ ｎ ｆ ｛ ｌ 　Ｉ 　＋÷ 　ｌ 　— ｌ 　 。 ｌ ； 　＜ ｚ ， Ａ ｘ 一６ ＞ ｝ 　
（ ４ ） 使 用 一 阶优 化 方法　

（ １ ３ ） 　

在 对 偶 函数 中使 用 一 阶优 化 方 法 ， 类似于邻近梯度方法 ， 同样 采 用 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ的 加 速 方 法 ， 只 不 过 变　

量 增 加 了对 偶 变 量 。对 偶 锥 方 法 可 以 看 成 是 鞍 点 方 法 ， 通过交替迭代优化原始函数和对偶函数 ， 达 到 共　 同 的最 优 解 。具 体 的算 法 过程 如 下　
一

（ １ 一 Ｏ ｋ ） 　 ＋　 ｚ 　 ～ 　 Ａ 　Ｙ 　 ， 　 ） 　

一

Ｓ ｏ ｆ ｔ Ｔｈ ｒ ｅ ｓ ｈ ｏ ｌ ｄ （ ｚ ０ 　

ｚ … 一 Ｓｈ ｒ ｉ ｎｋ（ ｚ 　一　 ｔ 　（ ． ） ， 一 Ａｓ ｃ 　）， 　 ￡ 女 ￡） 　

ｖ … 一（ １一　 ） Ｖ 　＋　 ｚ ¨ １ 　

（ １ ４ ） 　

式中： Ｓ ｈ ｒ ｉ ｎ ｋ （?） 是１ 。收 缩 运 算 ， Ｓ ｏ ｆ ｔ Ｔｈ ｒ ｅ ｓ ｈ ｏ ｌ ｄ （?） 是 软 阈 值 运 算 。 图 ｌ表 示 的 是 模 拟 数 据 下 ， 基　

于对 偶 锥 方法 和 加 速对 偶 锥 方 法 的 迭 代 结 果 ， 其 中横 坐 标 是 外 部 迭 代 次 数 ， 纵 坐 标 表示 迭代 点 与 最 优 点　 的 迭代 误 差 ｌ 　 一Ｘ ｌ 　ｌ ｌ 　／ｌ 　 ｌ Ｘ 　ｌ 　， ｌ 从 图 １中可 以 看 出 ， 基 于 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 加速的方法收敛更快 。 　 ２ ． ２ 交 替 方 向 乘 子 方 法　 交 替 方 向乘 子 （ Ａｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ 　 ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ 　 ｍｅ ｔ ｈ ｏ ｄ 　 ｏ ｆ 　 ｍｕ ｌ ｔ ｉ ｐ ｌ ｉ ｅ ｒ ｓ ， Ａ Ｄ Ｍ Ｍ） 方 法　 结 合 分 布 式 凸 优 化 问 　
题， 适 合 解 决 大 规模 数 据 的 问 题 。ＡＤＭＭ 可 以看 成 是 融 合 对 偶 分 解 和 增 广 Ｌ ａ ｇ ｒ ａ ｎ ｇ ｉ ａ ｎ的 优 点 ， 它 跟 很　

４ ０ 　

数据采集与处理 Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｙ 　 Ｄａ ｔ ａ 　 Ａｃ ｑ ｕ ｉ ｓ ｉ ｔ ｉ ｏ ｎ 　 ａ ｎ ｄ 　 Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ 　 Ｖｏ １ ． ３ ０ ， Ｎｏ ． １ ，２ ０ １ ５ 　

外部迭代 次数　

图 Ｉ 对 偶锥 方 法 和加 速 的对 偶 锥方 法　
Ｆｉ ｇ ．１ 　 Ｄｕａ ｌ 　 ｃ ｏｎ ｉ ｃ 　 ａ ｎｄ 　 ａ ｃ ｃ ｅ ｌ ｅ ｒ ａｔ ｅ ｄ 　 ｄｕ ａ ｌ 　 ｃ ｏｎ ｉ ｃ 　 ｍｅ ｔ ｈ ｏｄ 　

多算 法 有 相 互 联 系 ， 如 Ｂ ｒ ｅ ｇ ｍａ ｎ迭 代 方 法 ， Ｄ ｏ ｕ ｇ ｌ ａ ｓ 　 Ｒａ ｃ ｈ ｆ ｏ ｒ ｄ分 裂 方 法 及 Ｄｙ ｋ ｓ ｔ ｒ ａ交 替 投 影 方 法 等 。 　 ＡＤＭＭ 方 法 可 以追 溯 到 １ ９ ７ ０年 ， 它 在解 决 大规 模 分 布 计 算 系统 和 大 量 的 优 化 问题 中 起 着 非 常 重 要 的　
作用 。 　 在 ＡＤＭＭ 形 式 中 ， Ｉ 　 ａ ｓ ｓ ｏ问题 可 以看 成　
ｍｉ ｎ ｆ（ ｘ ） ＋ ｇ（ ｚ ） 　 Ｓ ． ｔ ． 　
１ 　

— ｚ一 ０ 　

（ １ ５ ） 　

Ｎ　

式中＿ ／ 、 （ 　 ） 一 专【 【 Ａ ｘ — ｂ 　， ｇ （ 　 ） 一 　 ∑　 得 到 基 于Ａ Ｄ Ｍ Ｍ的 算法 　
１ 　

”一（ Ａ 　 Ａ＋ ｐ Ｊ ） 　 （ Ａ 　 ｂ＋ ｐ （ ｚ 　一 “ 　 ）） 　
ｚ 　 一Ｓ 　（ 　 “－ ＋ － 　 ） 　
ｌ ｆ 　 一Ｈ 　＋　 … 一 ｚ 　

（ １ ６ ） 　

式 中　 的更 新 是岭 回归 过程 ， 解决 Ｌ ａ ｓ ｓ ｏ问题 的 ＡＤＭＭ 方 法 可 以解 释 为 交 替 实 施 岭 回归 过 程 。 图 ２ 　

表示 的是模 拟 数 据 下 ， ＡＤＭＭ 与 梯度 迭 代 方法 的 比较 。其 中红 色 曲线 表 示加 速 的 ＡＤＭＭ（ Ｆ ａ ｓ ｔ － ＡＤ ＭＭ） ， 　

趔　

鞴　
圆　

峰　
Ｉ １ Ｉ Ｉ 　

图 ２ 　 ＡＤＭＭ 方 法 和 梯 度 方 法　
Ｆｉ ｇ ．２ 　 Ａ ＤＭ Ｍ 　 ａ ｎｄ 　 ｇｒ ａ ｄｉ ｅ ｎｔ 　 ｍｅ ｔ ｈｏ ｄ 　

刘柳 等 ： Ｌ ａ ｓ ｓ ｏ问题 的 最 新 算 法研 究　

４ ｌ 　

黑 色 曲线 表示 ＡＤＭＭ ， 绿 色表 示 加 速 的 邻 近 梯 度 放 方 法 ， 蓝色表 示邻 近梯度 方法 ， 虚 线 表 示 真 实 值 曲　 线 。加 速 的 ＡＤＭＭ 比没 有 加 速 的 ＡＤＭＭ 方 法 能 够 更 快 的接 近 最 优 的 目标 函数 值 ， 加 速 的邻 近 梯 度 方　 法 相 对 于邻 近梯 度 方法 能 够更 快 的 达 到 最 优 的 函数 值 ， 但是从 整体来 说 ， ＡＤＭＭ 方 法 能 更 快 地 收 敛 最　 优 目标 函 数 值 。 　
一

般 的 ＡＤＭＭ 算 法 的收 敛 速 度 为 ０（ １ ／ ｋ ） ， Ｇｏ ｌ ｄ ｓ ｔ ｅ ｉ ｎ ［ ２ 　结 合 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 　 的 一 阶 最 小 方 法 能 达 到 ０　

（ １ ／ ｋ 　 ） 的全 局 收敛 速 度 。然 而 随着 数 据 的 快 速 增 加 ， 如 自然 语 言 处 理 、 图像 识 别 和 生 物 信 息 等 ， 随 机 优　 化 算 法 已 成 为 在 机 器 学 习 中重 要 的 方 法 。Ｓ ｕ ｚ ｕ ｋ ｉ ＿ ２ 　 提 出 了 基 于 随 机 优 化 算 法 的 ＡＤＭＭ 方 法 ， 同样 结　

合 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 一阶优化方法 ， 应用在一般 的凸函数 ， 其收敛速 度为 ０（ １ ／ √ 忌 ） ， 而对于强 凸函数能够 达到 ０ 　
（ １ ｏ ｇ （ 忌 ） ／ 忌 ） 的 收敛 速 度 ， Ｓ ｕ ｚ ｕ ｌ ｉ 　 结合随机对偶 坐标下降方 法（ Ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ 　 ｄ ｕ ａ ｌ 　 ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ａ ｓ ｃ ｅ ｎ ｔ ， Ｓ ＤＣＡ） 　 和 ＡＤＭＭ ， 由 于在 每次 迭代 中 需 要 一 个 或 多 个 样 本 ， 所以 Ｓ ＤＣ Ａ— ＡＤＭＭ 并 不 需 要 非 常 大 的储 存 空 间 ， 　 这 种 特 点 尤其 是 在 面 对 大 数 据 量 时 ， 能 够 更 好 地 体 现 出算 法 的优 越 性 。 　 ２ ． ３ 坐 标 下 降 方 法　

在 机 器学 习 中 ， 坐 标 下 降 方 法　 在 解 决 大 规 模 优 化 问 题 中 起 着 重 要 的作 用 ， 尤 其 是 当 样 本 数 ｍ 非　
常大 时 ， 求 全 梯 度 或 次 梯 度需 要 消 耗 大 量 的 时 间 和 储 存 空 间 ， 这 样 求 解 目标 函 数 的 子 函 数 问题 就 成 为 研　 究 大规 模 问题 的 热 点 。 子 函 数 问 题 可 以看 成 选 取 坐 标 系 中 的 某 一 个 坐 标 或 某 一 组 坐 标 ， 保 持 其 他 的 坐　 标 系 的变 量 不 变 ， 在每一次迭代过程 ， 只 优 化 在 选 取 坐 标 系 下 的 目标 函 数 。 　 有 效 的坐 标 下 降方 法取 决 于 每 一 次 迭 代 过 程 消 耗 的 时 间 和 目标 函 数 的 下 降 量 。一 个极 端 的 方 法 是　

贪婪方法 ， 即选 取 最 大 的 下 降 方 向 。但 是 贪 婪 方 法 面 临 的 问题 ： （ １ ） 要求 所有 的数据可行 ； （ ２ ） 可 能 会 超　
出计 算 机 的计 算 能 力 ， 比如需 要计 算 全 梯 度 的 迭 代 步 长 ， 而 不 是 某 个 坐标 系 下 的 迭 代 步 长 。另 外 两 个 选　 择 坐标 系 的方 法 是 周期 和 随 机 ， 一般的选择坐标方法是基于周期循环 ， 循 环 坐 标 下 降 方 法 的全 局 和 局 部　 收敛 性 质 在 文献 ［ － ５ ７ ￣ 中给出了详细的分析 ， 它 主 要 分 析 了在 等 渗 性 假 设 下 的 光 滑 凸 函 数 。虽 然 周 期 循　

环 是 求 解 连续 坐 标 系 的 迭 代 过 程 ， 但 是 并 不 是 在 所 有 坐 标 系 下 的求 解 对 目标 函数 都 产 生 影 响 。 随 机 选　
取 坐标 或 坐标 块 的 方 法 已经 成 为 在 大 规 模 数 据 分 析 中的 研 究 热 点 。随 机 选 择 坐 标 系 的 方 法 更适 合 大 规　 模数据 ， 最 近 的 研究 表 明 随 机 方 法 确 实 能 够 增 加 收 敛 率　 。 　 。在 均 匀 概 率 下 ， 随 机 选 择 坐 标 系 看 似 等　
效 于周 期 循 环 ， 但 是 随 机 坐标 系 的选 择 能 够 避 免 周 期 循 环 下 最 糟 糕 的 情 况 ， 比如 某 些 坐 标 系下 的 数 据 对　

目标 函数 并 没 有 作 用 。 除 了均 匀 概率 ， 不 同 的 概率 密 度 函 数 同样 可 以 增 加 收敛 速 度 。 同 时 ， 并 行 分 布 式　 运 算 也 可 以用 在 坐标 下 降 方 法 中 ， 从 而达到更好的运算效率 。 　
Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ加 速 方 法 已经 成 功 地 应 用 在 全 梯 度 下 降 方 法 ， 将 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ的 加 速 方 法 应 用 在 随 机 坐 标 下　
降 方 法 中 已经 在 文 献 ［ ２ １ ， ３ ４ ］ 中进 行 了 分 析 。Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 口 　提 出 了 一 种 加 速 的 随机 坐 标 梯 度 方 法 用 于 解　 决 最 小 化 无 约束 的光 滑 函 数 ， Ｌ ｕ和 Ｘｉ ａ ｏ ｌ ３ 　给 出 了基 于 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ方 法 的 证 明分 析 。 　
２ ． ３ ． １ 　 随 机 坐 标 下 降 方 法　

随机 坐 标 下 降方 法　 是 在某 个 概 率 分 布 下 选 择 坐 标 系 进 行 迭 代 的 过 程 ， 首先将 Ｎ 维空间分成 ７ ＂ ／ 个　

子空 间， ｕ 　∈ Ｒ 　 为矩阵的列置换 ， 任何一个 Ｎ 维空间 的 向量　 可 以唯一 的表示 为　 一 ＞ 　 Ｕ 　
ｚ“ ’ 一ｕ 　 、 Ｘ∈Ｒ 　， 当 Ｎ　 一１时 ， 即为 单 位 ｅ向量 。Ｌａ ｓ ｓ ｏ问 题 可 以 简 单 的 表示 为　
１ Ｔ Ｉ ｉ ｎ ｛ Ｐ（ 　）一 厂（ 　） ＋Ａ ｇ（ 　）｝ 　
∈　

， 　

（ １ ７ ） 　

每 一 次 迭 代 过 程 只需 要 在 随机 选择 的 坐 标 系 下 进行 ， 即　
Ｐ（ 　＋ Ｕ 　 ｔ ）一 ＿ 厂 （ Ｘ４ － Ｕ　 ｔ ） ＋２ ｇ（ 　＋ Ｕ 　 ｔ ） 　 （ １ ８ ） 　
ｒ 　

其 中 ｆ（ ｘ＋ Ｕ 　 ｔ ）的 上 界 可 以通 过 ／ （ 　） 函数 的光 滑 性 表 示 ：ｆ （ ｘ ＋Ｕ　 ｔ ） ≤ 厂（ 　） ＋（ 　 厂（ 　） ， ｆ ） ＋　 Ｊ ｆ 　 ｔ 　

４ ２ 　

数 据 采 集 与 处理 Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｆ 　 Ｄａ ｔ ａ 　 Ａｃ ｑ ｕ ｉ ｓ ｉ ｔ ｉ ｏ ｎ 　 ａ ｎ ｄ 　 Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ 　 Ｖｏ １ ． ３ ０， Ｎｏ ． １ ，２ ０ １ ５ 　

１ ； 　Ｌ 　 为 每个 坐 标 系 下 的 Ｌ ｉ ｐ ｓ ｃ ｈ ｉ ｔ ｚ 常 数 。每 一 次 的 迭 代 过 程 需 要 上 一 次 的 迭 代 结 果 ， 得 到 基 本 的 随　 机 坐 标算 法　

ｊ 　 Ｔ “ 　 （ ｘ ｋ ） 一 ａ ｒ ｇ ｍ ｉ “ ｉ （ 　＿ 厂 （ Ｘ ｋ ） ， 　 ） ＋ 等ｌ 　 ｌ ｝ Ｉ 　 ２ 　 ＋ ｇ 　 （ 　 ＋ 　 ） ， 　 ∈ Ｒ 　 ｝ 　
【 Ｘ … 一　 ＋ Ｕ 　 Ｔ“ 　 （ 　） 　

（ １ ９ ） 　

在Ｌ ａ ｓ ｓ ｏ问题 的 目标 函 数 上增 加 正则 化 项 Ｉ Ｉ 　 —Ｘ 。 　

， 使 得 目标 函数 变 为 严 格 凸 函数 ， 这 种 方 法　

应 用 在 基 于 光 滑 函 数 的 坐标 下 降方 法 中得 到 更 好 的 迭 代 结 果 。表 ２ 对 比 了不 同算 法 的 复 杂 度 的结 果 。 　
表 ２ 不同算法的复杂度比较（ １ ） 　
Ｔ ａ ｂ ｌ ｅ 　 ２ 　 Ｃｏ ｍｐ ｌ ｅ ｘ ｉ ｔ ｙ 　 ｃ ｏ ｍｐ ａ ｒ ｉ ｓ ｏ ｎ 　 ｏ ｆ 　 ｔ ｈ ｅ 　 ｄ ｉ ｆ ｆ ｅ ｒ ｅ ｎ ｔ 　 ａ ｉ ｇ ｒ ｉ ｔ ｈ ｍ （ Ｉ ） 　

算 法　 Ｙｕ ｎ 　 ａ ｎ ｄ 　 Ｔｓ ｅ ｎ ｇ 　 Ｓ ｈ ａ ｌ ｅ ｖ — Ｓ ｈ ｗａ ｒ ｔ ｚ 　 。 　 Ｐ ｅ ｔ ｅ ｒ 　 Ｒ ｉ ｃ ｈ ｔ ａ ｒ ｉ ｋ 　

复 杂 度　 Ｏ（ ｎ Ｌ（ 　＿ 厂 ）ｌ 　 Ｘ 　一 　０ 　 ／ ￡ ） 　 Ｘ ｏ 　 ／ ｅ ） 　 ｏ 　ｌ ； ／ ｅ ） 　 Ｏ（ ｎ ｐ 　 Ｉ 　 Ｉ Ｘ 　一 　。Ｉ Ｉ ； ／ ｅ ） 　 Ｏ （ ｎ 　 　 ｌ Ｘ 　

Ｓ ａ ｈ ａ ｒ ａ 　 ａ ｎ ｄ 　 Ｔｅ ｗａ ｒ ｉ 　 ” 　Ｏ（ ｎ Ｌ（ 　厂 ）ｌ 　

２ ． ３ ． ２ 邻 近 随机 对 偶 坐标 下 降　

邻 近 的 随机 对 偶 坐 标 下 降 方 法 （ Ｐ ｒ ｏ ｘ ｉ ｍａ ｌ 　 ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ 　 ｄ ｕ ａ ｌ 　 ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ａ ｓ ｃ ｅ ｎ ｔ ， Ｐ ｒ ｏ ｘ － Ｓ Ｄ Ｃ Ａ） 　 是 Ｓ ｈ ａ — 　
ｌ ｅ ｖ和 Ｚ ｈ ａ ｎ ｇ 　 对 随 机对 偶 问题 的扩 展 ， 允 许 正 则 化 函数 ｇ为 一 般 的 强 凸 函 数 ， 这 样 可 以 用 来 解 决 非 凸　 的 Ｌ１正 则 化 函数 。 在 目标 函 数 中增 加 正则 化 项 Ｐ（ 　）＋　／ ２ 　 ｌ 　 ｌ Ｘ— ｚ 　 ， 其 中 ｚ是 上 一 步 的 迭 代 结 果 ， 　
：

Ｏ（ １ ／ ￣ ｎ ）， 当时 １ ／ （ 　） 》 ｎ， 强 正则 化 项 能 够 使 得 邻 近 随 机 对 偶 坐 标 下 降 的 运算 时 间达 到 Ｏ（ ｄ ｎ ） 。在　

每次迭代过程中 ， 选择合适 的　 能够达到 ｄ 　 一 　

的运算 时间。表 ３ 是不同算 法的运算 时间对 比表 。 　

表 ３ 不 同 算 法 的 运 算 时 间 比 较　
Ｔａ ｂｌ ｅ 　 ３ 　 Ｃｏ ｍ ｐｕ ｔ ｉ ｎｇ 　 ｔ ｉ ｍｅ 　 ｃ ｏ ｍ ｐａ ｒ ｉ ｓ ｏ ｎ 　 ｏ ｆ 　 ｔ ｈｅ 　 ｄｉ ｆ ｆ ｅ ｒ ｅ ｎｔ 　 ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈｍ　

对偶 坐标 下 降 方 法 的 目标 是 增 加 对 偶 目标 函 数 值 ， 随 机 选 取 对 偶 变 量 的 Ｙ的 一 个 坐 标 系 ｅ 　 ， 即Ｙ 　

对 应 着 原 始 问题 的第 ｉ 个 样 本 。最 大 化 对偶 函数 ， 得 到对 偶 变 量 的迭 代 步 长　

Ａ ｙ 　 ＝ ａ ｒ ｇ 　 ｉ ｎ ｛ 一 　（ 一（ 　＋Ａ ｙ 　 ） ） 　Ａ ｇ 　 （ 　∑＆ 　＋ ｉ ｔ 　 １ ｎ 　 Ａ ｙ 　 ） ） 　
的下 界 问 题　

（ ２ ０ ） 　

为 了简 化 优化 问题 ， 对 共 轭 函数 ｇ做 光滑 处 理 ， 即一阶泰勒展开 ， 从 而 问 题 转 化 为 最 大 化 对 偶 函 数　

Ａ ｙ 　 — — ａ ｒ ｇ 　 ｉ ｎ ｛ 一 　（ 一（ 　＋Ａ ｙ 　 ） ） 一 　ｇ 　 （ ∑＆ 　） 一（ ２ ｔ ｉ ）＆ 　 Ａ ｙ 　 ） 　
正则 化 项 ｇ （ 　） 一 　Ｉ 　 ｌ １ ． ＋ 　ｌ 　 ｌ Ｘ 　 １ Ｉ 。 ≈　 ｌ 　 ｌ Ｘ 　 ｌ 　（ ｌ 　足 够 小 ） 。则 ｇ （ 　 ） 的共 轭 函数梯 度 为　

（ ２ １ ） 　

在 Ｌ ａ ｓ ｓ ｏ问 题 的 正则 化项 中 ， Ｌ１正 则 化 项 不 是 强 凸正 则 化 项 ， 增加 Ｌ ２正 则 化 项 ， 从而定 义 Ｌ ｌ — Ｉ 　 ２ 　

ｇ 　（ 　） 一ｓ ｉ ｇ ｎ （ ｙ 　 ） ［ 　１ １ 一ｉ ｔ ／ ￣ ３ ＋ 　
Ｐｒ ｏ ｘ — Ｓ ＤＣ Ａ 加 速 方 法 采 用 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 　 Ｓ评 估 序 列 技 术　

（ ２ ２ ） 　

用 于 逼 近 随 机 的 邻 近 映 射 。在 每 一 次　

Ｐ ｒ ｏ ｘ － Ｓ Ｄ Ｃ Ａ的迭代过程中 ， 改 进 目标 函数 Ｐ（ 　） ＋ 　／ ２ 　 　 ｆ Ｘ 　 ｚ 　” 　

， 其 中 正 则 化 项 围 绕 着 向量 ｚ 　 ”＝ 　

刘柳 等 ： Ｌ ａ ｓ ｓ ｏ问题 的 最新 算 法研 究　

４ ３ 　

Ｘ 　 ”４ － 口 （ 　 ”一 　
方法 。 　

）， 从 而 得 到更 快 的收 敛 速 度 。对 于 选 取 坐 标 系 ， 一 般 在 均 匀 分 布 的概 率 下 选 取 ， 　

Ｚ ｈ ａ ｎ ｇ 　 阳 提 出 了在 对 偶 坐 标 系 下 根 据 任 意 的 分 布 选 取 对 偶 变 量 ， 并 获 得 了有 效 的 并 行 和 分 布 式 变 量　
２ ． ３ ． ３ 　 随 机 原 始 对 偶 坐 标 下 降 方 法　

随 机 原 始 对 偶 坐 标 下 降方 法 （ Ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ 　 ｐ ｒ ｉ ｍａ ｌ — ｄ ｕ ａ ｌ 　 ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ ， Ｓ Ｐ ＤＣ） 　 是 通 过交 替 优 化 对 偶 函 数　

和 原 始 函数 ， 其 中 随机 选 择 对 偶 变量 中 的 一 维 空 间 ， 由 于对 偶 变 量 对 应 着 原 始 目标 函数 中 的样 本 数 。在　
给 出随 机 原 始 对 偶 问题 的算 法 前 ， 先 定 义原 始 问题 的 凸一 凹 鞍 点 问 题　

ｍｉ ｎ 　 ｍａ ｘ ｛ ｆ （ ｘ ， Ｊ ， ） 一２ 　（ 　（ ｎ 　 ， 　 ） 一　 （ 　） ） ＋Ａ ｇ（ 　 ）｝ 　
ｚ∈ 　 ｙ ＥＲ 　 、 　

关 于 变 量 Ｙ通 过 最 大 化 目标 函数 ｆ（ ｘ， 　） 得到 ， 需 要 消 耗 ０（ ｎ ｄ ） 的计 算 量 ， 如 果　 很 大 ， 需 要 消 耗 更　 多 的时间， 所 以通 过 随机 选 取 对 偶 变量 ｙ的坐 标 来 减 少 计 算 量 。这 样 在 选 取 的 坐 标 系 下 最 大 化 目标 函　

数， 然 后 交 替 优 化 原 始 目标 函数 。不 同 于一 般 的原 始 对 偶 问题 ， 根 据 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 　 Ｓ 的加速技 巧 ， 在 原 始 和　 对 偶 函数 中增 加 了两 个 正则 化 项 ， 从 而 得 到更 快 的 收 敛 速度 ， Ｃ ｈ ｅ ｎ 　 介 绍 了随 机 原 始 对 偶 方 法 ， 在 原 始　 和 对 偶 目标 函数 中增 加 一 阶变 量 并 且 融人 多 阶段 的 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 的加速方 法 ， 同时 不 需 要 采 用 光 滑 技 术 也　 能 达 到 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 光 滑 后 的 收敛 速 度 。同 时 ， Ｚ ｈ ａ ｎ ｇ 　 提 出 Ｍｉ ｎ ｉ — ｂ ａ ｔ ｃ ｈ的方 法 ， 自动 选 取 多 个 对 偶 坐标 变　
量， 在 并 行 运 算 中更 新　“ ¨　， 仅需 ｏ（ 　） 的迭 代 时 间 ， 当然处理多个 对偶坐标 ， 它 的 收 敛 率 比一 般 的 Ｓ Ｐ — 　 ＤＣ方 法 要 快 很 多 ， 表 ４给 出 了 不 同算 法 的时 间 复 杂 度 。 　
表 ４ 不 同算 法 的 复 杂 度 比 较 （ ２ ） 　
Ｔａ ｂ ｌ ｅ 　 ４ 　 Ｃｏ ｍｐ ｌ ｅ ｘ ｉ ｔ ｙ 　 ｃ ｏ ｍｐ ａ ｒ ｉ ｓ ｏ ｎ 　 ｏ ｆ 　 ｔ ｈ ｅ 　 ｄ ｉ ｆ ｆ ｅ ｒ ｅ ｎ ｔ 　 ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ （ Ⅱ ） 　

算 法　
Ｎｅ ｓ ｔ ｅ ｒ ｏｖ ［ 　］ 　 Ｔｓ ｅ ｎ ｇ［ 　］ 　

复 杂 度　
Ｏ（（ １＋　）ｌ ｏ ｇ（ １ ／ ｅ ）） 　

０（ （ 　＋　 ）ｌ ｏ ｇ （ １ ／ ｅ ）） 　
Ｏ（ （ 　＋Ⅳ）ｌ ｏ ｇ（ １ ／ ｅ ）） 　

Ｓｈａ ｌ ｅ ｖ － Ｓｈｗａ ｒ ｔ ｚ ［ ３ ２ ］ 　 Ｚｈ ａ ｎｇ 　 ａ ｎ ｄ 　 Ｌｉ ｎｃ 。 　 ］ 　

Ｏ（ （ １ ＋ 　

）ｌ ｏ ｇ （ １ ／ Ｅ ）） 　

３ 　 结 束 语　
近年来 ， 随 着 数 据 量 的增 加 ， 对解决 Ｌ ａ ｓ ｓ ｏ问 题 提 出 了更 大 的挑 战 。在 解 决 大 规 模 数 据 中 ， 必 须 要　 考虑计算时间和储存能力 ， 当硬 件 条 件 还 不 能 完 全 满 足 大 数 据 背 景 下 带 来 的需 求 ， 尤 其 是 面 对 高 维 数　
据， 以往 的 方 法 很 难 再 满 足 人 们 对 数 据 的分 析 ， 研 究 最 新 的算 法 就 成 为 最 新 的 热 点 。一 阶 方 法 、 随机 方　

法 和 并 行 和 分 布 计 算 在 解 决 大 规 模 数 据 中起 中重 要 的 作 用 ， 首先 一 阶方法计算起 来简单 ， 消耗时 间短 ， 　 符合人们对时间效率的要求 ； 再次 ， 随 机 方 法 主要 从 数 据 的 特 点 来 考 虑 ， 大 规 模 数 据 并 不 代 表 所 有 的 数　 据都会对算法产生影响 ， 如 果 对 所 有 的数 据 进 行 处 理 ， 那 么 必 将 消 耗 更 多 的 时 间 和储 存 空 间 ， 随 机 算 法　 正 好 弥 补 了这 些 缺 点 ； 并 行 和 分 布 计 算 同样 是 为 了减 少 时 间 消耗 ， 加 速运 算 ， 增加效率 。 　 本文从 ３ 个典型的算法分析 了 Ｌ ａ ｓ ｓ ｏ 问 题 的最 新 算 法 ： 梯度下降方法 、 交 替 方 向乘 子 法 和 坐 标 下 降　 方 法 。解 决 大 规 模 数 据 往 往 采 用 简 单 的方 法 更 能 提 高 效 率 。梯 度 下 降 是 做 简 单 的 方 法 ， 它 结 合 一 阶 方　 法和 Ｎ ｅ ｓ ｔ ｅ ｒ ｏ ｖ的加 速 和光 滑技 术 ， 使 最 终 的 收敛 速度 达 到 ０ （ １ ／ ｋ 　 ） 。ＡＤ ＭＭ 和 坐 标 下 降 方 法 也 是 在 梯　 度下降方法的基础上进行改进 ， 使 得 它 们 能 够 更 适 合 大 规 模 的 数 据 。同 时 Ａ Ｄ ＭＭ 和 坐 标 下 降 方 法 采　 用随机方法进行迭代 ， 因为 在 大 规 模 数 据 中能 够 减 少 时 间 消 耗 ， 实验结果 也证实 了在大规模 数据 中， 基　 于 随 机 算 法 能 够 得 到 更 好 的结 果 。坐 标 下 降 方 法 利 用 其 坐 标 系 的 特 点 结 合 一 阶方 法 、 随 机 方 法 和 并 行　 和 分 布计 算 。坐 标 下 降 方 法 之 所 以是 最 近 研 究 的热 点 ， 主 要 是 利 用 了其 坐 标 系 的特 点 ， 另 一 个 原 因是 数　 据 样 本 的增 加 和 数 据 维 度 越 来 越 高 ， 为 了提 高 效 率 ， 坐标 下 降 方 法 是 可 行 的 方 法 ， 在 原 始 目标 函 数 中采　

４ ４ 　

数 据 采 集 与 处理 Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｆ 　 Ｄａ ｔ ａ 　 Ａｃ ｑ ｕ ｉ ｓ ｉ ｔ ｉ ｏ ｎ 　 ａ ｎ ｄ 　 Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ 　 Ｖｏ １ ． ３ ０， Ｎｏ ． １ ，２ ０ １ ５ 　

用 坐 标 下 降 方 法 是 为 了 避 免 高维 度 ， 而 在 对 偶 函数 下 的 坐标 下 降 为 了 解 决 大 数 据 样 本 问题 。 基 于 随 机　 的坐 标 下 降 方 法 在 未 来 的研 究 中仍 然 起 着 非 常 重 要 的 作 用 ， 同 时 在 某 些 概 率分 布下 ， 对 坐 标 系 的 随机 选　
择 将 会 是 下 一 个 阶 段研 究 的热 点 问题 。 　 参考文献 ： 　
［ １ ］ 　 Ｔｉ ｂ ｓ ｈ ｉ ｒ ａ ｎ ｉ 　 Ｒ．Ｒｅ ｇ ｒ ｅ ｓ ｓ ｉ ｏ ｎ 　 ｓ ｈ ｒ ｉ ｎ ｋ ａ ｇ ｅ 　 ａ ｎ ｄ 　 ｓ ｅ ｌ ｅ ｃ ｔ ｉ ｏ ｎ 　 ｖ ｉ ａ 　 ｔ ｈ ｅ 　 ｌ ａ ｓ ｓ ｏ ［ Ｊ ］ ．Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｆ 　 ｔ ｈ ｅ 　 Ｒ ｏ ｙ ａ ｌ 　 Ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ａ ｌ 　 Ｓ ｏ ｃ ｉ ｅ ｔ ｙ ．Ｓ ｅ ｒ ｉ ｅ ｓ 　 Ｂ（ Ｍｅ ｔ ｈ ｏ ｄ — 　
ｏ ｌ ｏ ｇ ｉ ｃ ａ １ ）， １ ９ ９ ６， １ ５ （ １ ） ： ２ ６ ７ — ２ ８ ８ ． 　

Ｅ ２ ］ 　Ｂ ｉ ｃ ｋ ｅ ｌ 　 Ｐ 　 Ｊ ，Ｌ ｉ 　 Ｂ ，Ｔｓ ｙ ｂ ａ ｋ ｏ ｖ 　 Ａ 　 Ｂ，ｅ ｔ 　 ａ １ ．Ｒｅ ｇ ｕ ｌ ａ ｒ ｉ ｚ ａ ｔ ｉ ｏ ｎ 　 ｉ ｎ 　 ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ｓ ［ Ｊ ］ ．Ｓ ｏ ｃ ｉ ｅ ｄ ａ ｄ 　 ｄ ｅ 　 Ｅ ｓ ｔ ａ ｄ ｉ ｓ ｔ ｉ ｃ ａ 　 ｅ 　 Ｉ ｎ ｖ ｅ ｓ ｔ ｉ ｇ ａ ｃ ｉ ｏ ｎ 　 Ｏｐ ｅ ｒ ａ ｔ ｉ ｖ ａ ， 　
２ ０ ０６ ，１ ５ （ ２ ）： ２ ７ １ － ３ ４ ４ ． 　

［ ３ ］ 　 Ｆ ａ ｄ ｉ ｌ ｉ 　 Ｍ　 Ｊ ， Ｓ ｔ ａ ｒ ｃ ｋ 　 Ｊ 　 Ｉ 　 Ｍｏ ｎ ｏ ｔ ｏ ｎ ｅ 　 ｏ ｐ ｅ ｒ ａ ｔ ｏ ｒ 　 ｓ ｐ ｌ ｉ ｔ ｔ ｉ ｎ ｇ 　 ｆ ｏ ｒ 　 ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ 　 ｐ ｒ ｏ ｂ ｌ ｅ ｍｓ 　 ｉ ｎ 　 ｓ ｐ ａ ｒ ｓ ｅ 　 ｒ ｅ ｃ ｏ ｖ ｅ ｒ ｙ ［ Ｃ］ 　 Ｉ ｍａ ｇ ｅ 　 Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ 　 （ Ｉ ＣＩ Ｐ ） ，２ ０ ０ ９ 　 １ ６ ｔ ｈ 　 Ｉ Ｅ ＥＥ 　 Ｉ ｎ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｏ ｎ ａ ｌ 　 Ｃ ｏ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ 　 ｏ ｎ ．Ｃａ ｉ ｒ ｏ ，Ｅ ｇ ｙ ｐ ｔ ；ｓ ． ｎ ． ］ ，２ ０ ０ ９ ：１ ４ ６ １ － １ ４ ６ ４ ． 　 ［ ４ ］ 　 Ｉ 　 ｉ ｕ 　 Ｊ ， Ｙｕ ａ ｎ 　 Ｉ 　 ，Ｙｅ 　 Ｊ ．Ｄ ｉ ｃ ｔ ｉ ｏ ｎ ａ ｒ ｙ 　 Ｌ ａ ｓ ｓ ｏ ：Ｇ ｕ ａ ｒ ａ ｎ ｔ ｅ ｅ ｄ 　 ｓ ｐ ａ ｒ ｓ ｅ 　 ｒ ｅ ｃ ｏ ｖ ｅ ｒ ｙ 　 ｕ ｎ ｄ ｅ ｒ 　 ｌ ｉ ｎ ｅ ａ ｒ 　 ｔ ｒ ａ ｎ ｓ ｆ ｏ ｒ ｍａ ｔ ｉ ｏ ｎ ［ Ｃ ］ ∥ Ｐ ｒ ｏ ｃ ｅ ｅ ｄ ｉ ｎ ｇ ｓ 　 ｏ ｆ 　 Ｍａ — 　

ｃ ｈ ｉ ｎ ｅ 　 Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ ，２ ０ １ ２ 　 ３ ０ ｔ ｈ 　 Ｉ Ｅ Ｅ Ｅ 　 ｉ ｎ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｏ ｎ ａ １ 　 Ｃ ｏ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ ．Ａｔ ｌ ａ ｎ ｔ ａ ，ＵＳ Ａ： Ｅ ｓ ． ｎ ． ］ ， ２ ０ １ ２ ：１ － ２ ８ ． 　
Ｅ ｓ ３ 　Ｚ ｈ ｏ ｕ 　 Ｔ，Ｔ ａ ｏ 　 Ｄ．Ｍｕ ｌ ｔ ｉ — ｔ ａ ｓ ｋ 　 ｃ ｏ ｐ ｕ ｌ ａ 　 ｂ ｙ 　 ｓ ｐ ａ ｒ ｓ ｅ 　 ｇ ｒ ａ ｐ ｈ 　 ｒ ｅ ｇ ｒ ｅ ｓ ｓ ｉ ｏ ｎ ［ Ｃ ］ 　 Ｐ ｒ ｏ ｃ ｅ ｅ ｄ ｉ ｎ ｇ ｓ 　 ｏ ｆ 　 ｔ ｈ ｅ 　 ２ ０ ｔ ｈ 　 ＡＣ Ｍ　 Ｓ Ｉ ＧＫＤ Ｄ 　 Ｉ ｎ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｏ ｎ ａ ｌ 　 Ｃ ｏ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ 　 ｏ ｎ 　 Ｋｎ ｏ ｗｌ ｅ ｄ ｇ ｅ 　 Ｄ ｉ ｓ ｃ ｏ ｖ ｅ ｒ ｙ 　 ａ ｎ ｄ 　 Ｄ ａ ｔ ａ 　 Ｍｉ ｎ ｉ ｎ ｇ ．Ｎｅ ｗ　 Ｙｏ ｒ ｋ，ＵＳ Ａ： Ｅ ｓ ． ｎ ． ］ ，２ ０ １ ４ ： ７ ７ １ － ７ ８ ０ ． 　 ［ ６ ３ 　 Ｙｕ ａ ｎ 　 ｘ ．Ａｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ 　 ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ 　 ｍｅ ｔ ｈ ｏ ｄ ｓ 　 ｆ ｏ ｒ 　 ｓ ｐ ａ ｒ ｓ ｅ 　 ｃ ｏ ｖ ａ ｒ ｉ ａ ｎ ｅ ｅ 　 ｓ ｅ ｌ ｅ ｃ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｆ 　 Ｓ ｃ ｉ ｅ ｎ ｔ ｉ ｆ ｉ ｃ 　 Ｃ ｏ ｍｐ ｕ ｔ ｉ ｎ ｇ ， ２ ０ １ ２ ，５ １ （ ２ ） ： 　
２６１ — ２７３ 　

［ ７ ］ Ｓ ｕ ｎ 　 Ｙ， Ｌ ｉ ｕ 　 Ｑ，Ｔ ａ ｎ ｇ 　 Ｊ ，ｅ ｔ 　 ａ １ ．Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ 　 ｄ ｉ ｓ ｃ ｒ ｉ ｍｉ ｎ ａ ｔ ｉ ｖ ｅ 　 ｄ ｉ ｃ ｔ ｉ ｏ ｎ ａ ｒ ｙ 　 ｆ ｏ ｒ 　 ｇ ｒ ｏ ｕ ｐ 　 ｓ ｐ ａ ｒ ｓ ｅ 　 ｒ ｅ ｐ ｒ ｅ ｓ ｅ ｎ ｔ ａ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．Ｉ Ｅ ＥＥ 　 Ｔ ｒ ａ ｎ ｓ ａ ｃ ｔ ｉ ｏ ｎ 　 ｏ ｎ 　
Ｉ ｍａ ｇｅ 　 Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ，２ ０ １ ４，２ ３ （ ９ ）： ３ ８１ ６ － ３ ８ ２ ６ 　

［ ８ ］ 　 Ｈａ ｓ ｔ ｉ ｅ 　 Ｔ， Ｔｉ ｂ ｓ ｈ ｉ ｒ ａ ｎ ｉ 　 Ｒ， Ｆ ｒ ｉ ｅ ｄ ｍａ ｎ 　 Ｊ ， ｅ ｔ 　 ａ １ ．Ｔｈ ｅ 　 ｅ ｌ ｅ ｍｅ ｎ ｔ ｓ 　 ｏ ｆ 　 ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ａ ｌ 　 ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ： Ｄａ ｔ ａ 　 ｍｉ ｎ ｉ ｎ ｇ ，ｉ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ 　 ａ ｎ ｄ 　 ｐ ｒ ｅ ｄ ｉ ｃ ｔ ｉ ｏ ｎ ［ Ｊ ］ ． 　
Ｔｈ ｅ 　 Ｍａ ｔ ｈ ｅ ｍａ ｔ ｉ ｃ ａ ｌ 　 Ｉ ｎ ｔ ｅ ｌ ｌ ｉ ｇ ｅ ｎｃ ｅ ｒ ，２ ０ ０ ５，２ ７（ ２） ： ８ ３ — ８ ５ ． 　

［ ９ ］ 　 Ｇｅ ｎ ｇ 　 Ｂ ，Ｌ ｉ 　 Ｙ，Ｔａ ｏ 　 Ｄ，ｅ ｔ 　 ａ １ ．Ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ 　 ｌ ａ ｓ ｓ ｏ 　 ｆ ｏ ｒ 　 ｌ ａ ｒ ｇ ｅ — ｓ ｃ ａ ｌ ｅ 　 ｖ ｉ ｄ ｅ ｏ 　 ｃ ｏ ｎ ｃ ｅ ｐ ｔ 　 ｄ ｅ ｔ ｅ ｃ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．Ｍｕ ｌ ｔ ｉ ｍｅ ｄ ｉ ａ ， Ｉ Ｅ Ｅ Ｅ 　 Ｔｒ ａ ｎ ｓ ａ ｃ ｔ ｉ ｏ ｎ ｓ 　 ｏ ｎ ， 　
２ Ｏ １ ２， １ ４ （ １ ）： ５ ５ － ６ ５ ． 　

［ １ Ｏ ］ 　Ｚ ｈ ｏ ｕ 　 Ｔ， Ｔａ ｏ 　 Ｄ．Ｓ ｈ ｉ ｆ ｔ ｅ ｄ 　 ｓ ｕ ｂ ｓ ｐ ａ ｅ ｅ ｓ 　 ｔ ｒ ａ ｃ ｋ ｉ ｎ ｇ 　 ｏ ｎ 　 ｓ ｐ ａ ｒ ｓ ｅ 　 ｏ ｕ ｔ ｌ ｉ ｅ ｒ 　 ｆ ｏ ｒ 　 ｍｏ ｔ ｉ ｏ ｎ 　 ｓ ｅ ｇ ｍｅ ｎ ｔ ａ ｔ ｉ ｏ ｎ ［ Ｃ ］ 　Ｐ ｒ ｏ ｃ ｅ ｅ ｄ ｉ ｎ ｇ ｓ 　 ｏ ｆ 　 ｔ ｈ ｅ 　 Ｔ ｗｅ ｎ ｔ ｙ — Ｔｈ ｉ ｒ ｄ 　

Ｉ ｎ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｏ ｎ ａ ｌ 　 Ｊ ｏ ｉ ｎ ｔ 　 Ｃ ｏ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ 　 ｏ ｎ 　 Ａｒ ｔ ｉ ｆ ｉ ｃ ｉ ａ ｌ 　 Ｉ ｎ ｔ ｅ ｌ ｌ ｉ ｇ ｅ ｎ ｃ ｅ ．Ｂ ｅ ｉ ｊ ｉ ｎ ｇ ，Ｃ ｈ ｉ ｎ ａ ： ［ ｓ ． ｎ ． ］ ，２ ０ １ ３ ：１ ９ ４ ６ — １ ９ ５ ２ ． 　 ｏ ｎ ｓ ｏ 　 Ｍ　 Ｖ ，Ｂｉ ｏ ｕ ｃ ａ ｓ － Ｄｉ ａ ｓ 　 Ｊ 　 Ｍ ，Ｆｉ ｇ ｕ ｅ ｉ ｒ ｅ ｄ ｏ 　 Ｍ　 Ａ． Ｆａ ｓ ｔ 　 ｉ ｍａ ｇｅ 　 ｒ ｅ ｃ ｏ ｖ ｅ ｒ ｙ 　 ｕ ｓ ｉ ｎ ｇ 　 ｖ ａ ｒ ｉ ａ ｂ ｌ ｅ 　 ｓ ｐ ｌ ｉ ｔ ｔ ｉ ｎ ｇ 　 ａ ｎ ｄ 　 ｃ ｏ ｎ ｓ ｔ ｒ ａ ｉ ｎ ｅ ｄ 　 ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ 　 ［ １ ｉ ３ 　Ａｆ
Ｅ Ｊ ］ ．Ｉ ｍａ ｇ ｅ 　 Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ ，Ｉ Ｅ Ｅ Ｅ 　 Ｔｒ ａ ｎ ｓ ａ ｃ ｔ ｉ ｏ ｎ ｓ 　 ｏ ｎ ， ２ ０ １ ０ ，１ ９ （ ９ ） ： ２ ３ ４ ５ — ２ ３ ５ ６ ． 　 ［ １ ２ ］ 　Ｅ ｌ ａ ｄ 　 Ｍ ，Ｍａ ｔ ａ ｌ ｏ ｎ 　 Ｂ ，Ｚ ｉ ｂ ｕ ｌ ｅ ｖ ｓ ｋ ｙ 　 Ｍ．Ｉ ｍａ ｇ ｅ 　 ｄ ｅ ｎ ｏ ｉ ｓ ｉ ｎ ｇ 　 ｗｉ ｔ ｈ 　 ｓ ｈ ｒ ｉ ｎ ｋ ａ ｇ ｅ 　 ａ ｎ ｄ 　 ｒ ｅ ｄ ｕ ｎ ｄ ａ ｎ ｔ 　 ｒ ｅ ｐ ｒ ｅ ｓ ｅ ｎ ｔ ａ ｔ ｉ ０ ｎ ｓ ［ ｃ ］ ∥ Ｃ ｏ ｍｐ ｕ ｔ ｅ ｒ 　 Ｖ ｉ ｓ ｉ ｏ ｎ 　 ａ ｎ ｄ 　 Ｐ ａ ｔ ｔ ｅ ｒ ｎ 　 Ｒｅ ｃ ｏ ｇ ｎ ｉ ｔ ｉ ｏ ｎ ，２ ０ ０ ６ 　 Ｉ Ｅ Ｅ Ｅ 　 Ｃ ｏ ｍｐ ｕ ｔ ｅ ｒ 　 Ｓ ｏ ｃ ｉ ｅ ｔ ｙ 　 Ｃ ｏ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ ，Ｎｅ ｗ 　 Ｙｏ ｒ ｋ ，ＵＳ Ａ：ｓ ． ｎ ． ］ ，２ ０ ０ ６ ， ２ ：１ ９ ２ ４ — １ ９ ３ １ ． 　 ［ １ ３ ］ 　Ｆ ｉ ｇ ｕ ｅ ｉ ｒ ｅ ｄ ｏ 　 Ｍ　 Ａ，Ｎ ｏ ｗａ ｋ 　 Ｒ 　 Ｄ ．Ａ ｎ 　 ｅ ｍ 　 ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ 　 ｆ ｏ ｒ 　 ｗａ ｖ ｅ ｌ ｅ ｔ — ｂ ａ ｓ ｅ ｄ 　 ｉ ｍａ ｇ ｅ 　 ｒ ｅ ｓ ｔ ｏ ｒ ａ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．Ｉ ｍａ ｇ ｅ 　 Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ ， Ｉ Ｅ Ｅ Ｅ 　 Ｔｒ ａ ｎ ｓ ａ ｃ — 　
ｔ ｉ ｏ ｎ ｓ 　 ｏｎ．２ ０ ０ ３，】 ２ （ ８） ． ９ ０ ６ － ９ １ ６ ． 　

ｇ １ ４ ３ 　Ｙｕ 　 Ｊ ，Ｒｕ ｉ 　 Ｙ，Ｔ ａ ｏ 　 Ｄ　 Ｃｌ ｉ ｃ ｋ 　 ｐ ｒ ｅ ｄ ｉ ｃ ｔ ｉ ｏ ｎ 　 ｆ ｏ ｒ 　 ｗ ｅ ｂ 　 ｉ ｍａ ｇ ｅ 　 ｒ ｅ ｒ ａ ｎ ｋ ｉ ｎ ｇ 　 ｕ ｓ ｉ ｎ ｇ 　 ｍｕ ｌ ｔ ｉ ｍｏ ｄ ａ ｌ 　 ｓ ｐ ａ ｒ ｓ ｅ 　 ｃ ｏ ｄ ｉ ｎ ｇ ［ Ｊ ３ ．Ｉ Ｅ Ｅ Ｅ 　 Ｔｒ ａ ｎ ｓ ａ ｅ ｔ ｉ ｏ ｎ ｓ 　 ０ ｎ 　
Ｉ ｍａ ｇ ｅ 　 Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎｇ，２ ０ １ ４，２ ３（ ５ ）：２ ０ １ ９ － ２ ０ ３ ２． 　

［ １ 　 ５ ］ 　Ｈｅ 　 Ｉ 　 ，Ｔａ ｏ 　 Ｄ， Ｉ Ａ 　 ｘ，ｅ ｔ 　 ａ １ ．Ｓ ｐ ａ ｒ ｓ ｅ 　 ｒ ｅ ｐ ｒ ｅ ｓ ｅ ｎ ｔ ａ ｔ ｉ ｏ ｎ 　 ｆ ｏ ｒ 　 ｂ ｌ ｉ ｎ ｄ 　 ｉ ｍａ ｇ ｅ 　 ｑ ｕ ａ ｌ ｉ ｔ ｙ 　 ａ ｓ ｓ ｅ ｓ ｓ ｍｅ ｎ ｔ ［ Ｃ ］ ∥Ｃ ｏ ｍｐ ｕ ｔ ｅ ｒ 　 Ｖｉ ｓ ｉ ｏ ｎ 　 ａ ｎ ｄ 　 Ｐ ａ ｔ ｔ ｅ ｒ ｎ 　 Ｒｅ ｃ — 　
ｏ ｇ ｎ ｉ ｔ ｉ ｏ ｎ（ Ｃ ＶＰ Ｒ ） ，２ ０ １ ２ 　 Ｉ Ｅ Ｅ Ｅ 　 Ｃ ｏ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ ．Ｒｈ ｏ ｄ ｅ ，Ｉ ｓ ｌ ａ ｎ ｄ ：ｓ ． ｎ ． ］ ，２ ０ １ ２ ，１ １ ４ ６ — １ １ ５ ３ ． 　
ｏｕ ｃ ａ ｓ — Ｄｉ ａ ｓ 　 Ｊ 　 Ｍ ，Ｆｉ ｇ ｕ ｅ ｉ ｒ ｅ ｄ ｏ 　 Ｍ　 Ａ．Ａｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ 　 ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ 　 ａ ｌ ｇｏ ｒ ｉ ｔ ｈ ｍｓ 　 ｆ ｏ ｒ 　 ｃ ｏ ｎ ｓ ｔ ｒ ａ ｉ ｎ ｅ ｄ 　 ｓ ｐ ａ ｒ ｓ ｅ 　 ｒ ｅ ｇ ｒ ｅ ｓ ｓ ｉ ｏ ｎ：Ａｐ ｐ ｌ ｉ ｃ ａ ｔ ｉ ｏ ｎ 　 ｔ ｏ 　 ｈ ｙ ｐ ｅ ｒ — 　 ［ １ ６ ］ 　Ｂｉ

ｓ ｐ ｅ ｃ ｔ ｒ ａ ｌ 　 ｕ ｎ ｍｉ ｘ ｉ ｎ ｇ ［ Ｃ ］ ∥ Ｈｙ ｐ ｅ ｒ ｓ ｐ ｅ ｃ ｔ ｒ ａ ｌ 　 Ｉ ｍａ ｇ ｅ 　 ａ ｎ ｄ 　 Ｓ ｉ ｇ ｎ ａ ｌ 　 Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ ：Ｅ ｖ ｏ ｌ ｕ ｔ ｉ ｏ ｎ 　 ｉ ｎ 　 Ｒ ｅ ｍｏ ｔ ｅ 　 Ｓ ｅ ｎ ｓ ｉ ｎ ｇ（ Ｗ ＨＩ Ｓ Ｐ ＥＲ Ｓ ） ，２ ０ １ ０ 　 ２ ｎ ｄ 　
Ｗｏ ｒ ｋ ｓ ｈ ｏ ｐ ．Ｒｅ ｙ ｋ ｊ ａ ｖ ｉ ｋ ，Ｉ ｃ ｅ ｌ ａ ｎ ｄ ： ［ ｓ ． ｎ ． ］ ，２ ０ ｉ ０ ：ｌ 一 ４ ． 　 ［ １ ７ ］ 　Ｌ ｉ ｎ ｅ ａ ｒ 　 Ａ．Ｆ ｏ ｒ ｅ ｗｏ ｒ ｄ 　 ｔ ｏ 　 ｔ ｈ ｅ 　 ｓ ｐ ｅ ｃ ｉ ａ ｌ 　 ｉ ｓ ｓ ｕ ｅ 　 ｏ ｎ 　 ｓ ｐ ｅ ｃ ｔ ｒ ａ ｌ 　 ｕ ｎ ｍｉ ｘ ｉ ｎ ｇ 　 ｏ ｆ 　 ｒ ｅ ｍｏ ｔ ｅ ｌ ｙ 　 ｓ ｅ ｎ ｓ ｅ ｄ 　 ｄ ａ ｔ ａ ［ Ｊ ］ ．Ｉ Ｅ Ｅ Ｅ 　 Ｔｒ ａ ｎ ｓ ａ ｃ ｔ ｉ ｏ ｎ ｓ 　 ｏ ｎ 　 Ｇ ｅ ｏ ｓ ｃ ｉ ｅ ｎ ｃ ｅ 　
ａ ｎ ｄ 　 Ｒｅ ｍｏ ｔ ｅ 　 Ｓ ｅ ｎ ｓ ｉ ｎ ｇ， ２ ０ １ １，４ ９（ １ １ ）： ４ １ ０ ３ ． 　

［ １ ８ ］ 　Ｒ ｉ ｃ ｈ ａ ｒ ｄ ｓ 　 Ｊ 　 Ａ．Ｒｅ ｍｏ ｔ ｅ 　 ｓ ｅ ｎ ｓ ｉ ｎ ｇ 　 ｄ ｉ ｇ ｉ ｔ ａ ｌ 　 ｉ ｍａ ｇ ｅ 　 ａ ｎ ａ ｌ ｙ ｓ ｉ ｓ ［ Ｍ］ ．Ｎｅ ｗ 　 Ｙ ｏ ｒ ｋ： Ｓ ｐ ｒ ｉ ｎ ｇ ｅ ｒ ，１ ９ ９ ９ ． 　 ［ １ ９ ］ 　Ｅ ｆ ｒ ｏ ｎ 　 Ｂ，Ｈａ ｓ ｔ ｉ ｅ 　 Ｔ，Ｊ ｏ ｈ ｎ ｓ ｔ ｏ ｎ ｅ 　 Ｉ 。ｅ ｔ 　 ａ １ ．Ｌ ｅ ａ ｓ ｔ 　 ａ ｎ ｇ ｌ ｅ 　 ｒ ｅ ｇ ｒ ｅ ｓ ｓ ｉ ｏ ｎ ［ Ｊ ］ ．Ｔ ｈ ｅ 　 Ａｎ ｎ ａ ｌ ｓ 　 ｏ ｆ 　 Ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ｓ ， ２ ０ ０ ４ ，３ ２ （ ２ ） ： ４ ０ ７ — ４ ９ ９ ． 　

［ ２ ０ ］ 　Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 　 Ｙ，Ｎ ｅ ｓ ｔ ｅ ｒ ｏ ｖ 　 Ｉ 　 Ｅ ．Ｉ ｎ ｔ ｒ ｏ ｄ ｕ ｃ ｔ ｏ ｒ ｙ 　 ｌ ｅ ｃ ｔ ｕ ｒ ｅ ｓ 　 ｏ ｎ 　 ｃ ｏ ｎ ｖ ｅ ｘ 　 ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ： Ａ　 ｂ ａ ｓ ｉ ｃ 　 ｃ ｏ ｕ ｒ ｓ ｅ ￣ Ｍ］ ．ＵＳ Ａ： Ｓ ｐ ｒ ｉ ｎ ｇ ｅ ｒ ，２ ０ ０ ４ ． 　
［ ２ １ ］ 　Ｎ ｅ ｓ ｔ ｅ ｒ ｏ ｖ 　 Ｙ．Ｓ ｍｏ ｏ ｔ ｈ 　 ｍｉ ｎ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ 　 ｏ ｆ 　 ｎ ｏ ｎ — ｓ ｍｏ ｏ ｔ ｈ 　 ｆ ｕ ｎ ｃ ｔ ｉ ｏ ｎ ｓ ［ Ｊ ￣ ．Ｍａ ｔ ｈ ｅ ｍａ ｔ ｉ ｃ ａ ｌ 　 Ｐ ｒ ｏ ｇ ｒ ａ ｍｍｉ ｎ ｇ ，２ ０ ０ ５ ，１ ０ ３ （ １ ） ： １ ２ ７ — １ ５ ２ ． 　
ｏ ｙ ｄ 　 Ｓ，Ｐ ａ ｒ ｉ ｋｈ 　 Ｎ ，Ｃｈ ｕ 　 Ｅ，ｅ ｔ 　 ａ １ ．Ｄｉ ｓ ｔ ｒ ｉ ｂ ｕ ｔ ｅ ｄ 　 ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ 　 ａ ｎｄ 　 ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ａ ¨ｅ ａ ｒ ｎ ｉ ｎ ｇ 　 ｖ ｉ ａ 　 ｔ ｈ ｅ 　 ａ ｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ 　 ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ 　 ｍｅ ｔ ｈ ｏ ｄ 　 ｏ ｆ 　 ｍｕｌ — 　 ［ ２ ２ ］ 　Ｂ

ｔ ｉ ｐ ｌ ｉ ｅ ｒ ｓ ［ Ｊ ］ ．Ｆ ｏ ｕ ｎ ｄ ａ ｔ ｉ ｏ ｎ ｓ 　 ａ ｎ ｄ 　 Ｔｒ ｅ ｎ ｄ ｓ 　 Ｒ 　 ｉ ｎ 　 Ｍａ ｃ ｈ ｉ ｎ ｅ 　 Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ ，２ ０ １ １ ，３ （ １ ） ： １ － １ ２ ２ ． 　 Ｅ ２ ３ ］ 　Ｂ ｅ ｃ ｋ ｅ ｒ 　 Ｓ ．Ｒ， Ｃ ａ ｎ ｄ ６ ｓ 　 Ｅ 　 Ｊ ，Ｇｒ ａ ｎ ｔ 　 Ｍ　 Ｃ．Ｔｅ ｍｐ ｌ ａ ｔ ｅ ｓ 　 ｆ ｏ ｒ 　 ｃ ｏ ｎ ｖ ｅ ｘ 　 ｃ ｏ ｎ ｅ 　 ｐ ｒ ｏ ｂ ｌ ｅ ｍｓ 　 ｗｉ ｔ ｈ 　 ａ ｐ ｐ ｌ ｉ ｃ ａ ｔ ｉ ｏ ｎ ｓ 　 ｔ ｏ 　 ｓ ｐ ａ ｒ ｓ ｅ 　 ｓ ｉ ｇ ｎ ａ ｌ 　 ｒ ｅ ｃ ｏ ｖ ｅ ｒ ｙ ［ Ｊ ］ ． 　
Ｍａ ｔ ｈ ｅ ｍａ ｔ ｉ ｃ ａ ｌ 　 Ｐｒ ｏ ｇ ｒ ａ ｍｍ ｉ ｎｇ 　 Ｃｏ ｍｐ ｕ ｔ ａ ｔ ｉ ｏ ｎ，２ ０ １ １，３ （ ３ ）： １ ６ ５ — ２１ ８ ． 　

［ ２ ４ ］ 　Ｂ ｅ ｃ ｋ 　 Ａ，Ｔ ｅ ｂ ｏ ｕ ｌ ｌ ｅ 　 Ｍ．Ａ 　 ｆ ａ ｓ ｔ 　 ｉ ｔ ｅ ｒ ａ ｔ ｉ ｖ ｅ 　 ｓ ｈ ｒ ｉ ｎ ｋ ａ ｇ ｅ — ｔ ｈ ｒ ｅ ｓ ｈ ｏ ｌ ｄ ｉ ｎ ｇ 　 ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ 　 ｆ ｏ ｒ 　 ｌ ｉ ｎ ｅ ａ ｒ 　 ｉ ｎ ｖ ｅ ｒ ｓ ｅ 　 ｐ ｒ ｏ ｂ ｌ ｅ ｍｓ ［ Ｊ ］ ．Ｓ Ｉ ＡＭ　 Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｎ 　 Ｉ ｍ— 　
ａ ｇ ｉ ｎ ｇ 　 Ｓ ｃ ｉ ｅ ｎ ｃ ｅ ｓ ，２ ０ ０ ９，２ （ １ ）： １ ８ ３ — ２ ０ ２ ． 　

［ ２ ５ ］ 　Ｇ ｏ ｌ ｄ ｓ ｔ ｅ ｉ ｎ 　 Ｔ，ＯＤ ｏ ｎ ｏ ｇ ｈ ｕ ｅ 　 Ｂ ，Ｓ ｅ ｔ ｚ ｅ ｒ 　 Ｓ ．Ｆ ａ ｓ ｔ 　 ａ ｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ 　 ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ 　 ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ 　 ｍｅ ｔ ｈ ｏ ｄ ｓ ［ Ｊ ］ ．Ｓ Ｉ ＡＭ　 Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 Ｉ ｍａ ｇ ｉ ｎ ｇ 　 Ｓ ｃ ｉ ｅ ｎ ｃ ｅ ｓ ， 　

刘柳 等 ： Ｌａ ｓ ｓ ｏ问题 的 最 新 算 法研 究　
Ｚ Ｏｌ ４，７（ ３） ： ｌ ５ ８ ８ 一 ｌ ６ Ｚ ３ ． 　

４ ５ 　

［ ２ ６ ］ 　Ｓ ｕ ｚ ｕ ｋ ｉ 　 Ｔ．Ｄ ｕ ａ ｌ 　 ａ ｖ ｅ ｒ ａ ｇ ｉ ｎ ｇ 　 ａ ｎ ｄ 　 ｐ ｒ ｏ ｘ ｉ ｍａ ｌ 　 ｇ ｒ ａ ｄ ｉ ｅ ｎ ｔ 　 ｄ ｅ ｓ ｃ ｅ ｎ ｔ 　 ｆ ｏ ｒ 　 ｏ ｎ ｌ ｉ ｎ ｅ 　 ａ ｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ 　 ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ 　 ｍｕ ｌ ｔ ｉ ｐ ｌ ｉ ｅ ｒ 　 ｍｅ ｔ ｈ ｏ ｄ ｉ Ｃ ］ｆ ，Ｐ ｒ ｏ ｃ ｅ ｅ ｄ ｉ ｎ ｇ ｓ 　
ｏ ｆ 　 ｔ ｈ ｅ 　 ３ ｏ ｔ ｈ 　 Ｉ ｎ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｏ ｎ ａ ｌ 　 Ｃ ｏ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ 　 ｏ ｎ 　 Ｍａ ｃ ｈ ｉ ｎ ｅ 　 Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ（ Ｉ ＣＭＬ － １ ３ ） ．Ａｔ ｌ ａ ｎ ｔ ａ ，ＵＳ Ａ： ［ ｓ ． ｎ ． ］ ， ２ ０ １ ３ ：３ ９ ２ — ４ ０ ０ ． 　 ［ ２ ７ ］ 　Ｓ ｕ ｚ ｕ ｋ ｉ 　 Ｔ ．Ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ 　 ｄ ｕ ａ ｌ 　 ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ａ ｓ ｃ ｅ ｎ ｔ 　 ｗ ｉ ｔ ｈ 　 ａ ｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ 　 ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ 　 ｍｕ ｌ ｔ ｉ ｐ ｌ ｉ ｅ ｒ 　 ｍｅ ｔ ｈ ０ ｄ ［ Ｅ Ｂ ／ ０Ｌ ］ ．ｈ ｔ ｔ ｐ ： ∥ａ ｒ ｘ ｉ ｖ ． ｏ ｒ ｇ ／ ， ２ ０ １ ４ ． 　

［ ２ ８ ３ 　Ｏｕ ｙ ａ ｎ ｇ 　 Ｈ ，Ｈｅ 　 Ｎ， Ｔｒ ａ ｎ 　 Ｌ， ｅ ｔ 　 ａ １ ．Ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ 　 ａ ｌ ｔ ｅ ｒ ｎ ａ ｔ ｉ ｎ ｇ 　 ｄ ｉ ｒ ｅ ｃ ｔ ｉ ｏ ｎ 　 ｍｅ ｔ ｈ ｏ ｄ 　 ｏ ｆ 　 ｍｕ ｌ ｔ ｉ ｐ ｌ ｉ ｅ ｒ ｓ ［ Ｃ ￣ ∥Ｐ ｒ ｏ ｃ ｅ ｅ ｄ ｉ ｎ ｇ ｓ 　 ｏ ｆ 　 ｔ ｈ ｅ 　 ３ ０ ｔ ｈ 　 Ｉ ｎ ｔ ｅ ｒ — 　
ｎ ａ ｔ ｉ ｏ ｎ ａ ｌ 　 Ｃｏ ｎ ｆ ｅ ｒ ｅ ｎ ｃ ｅ 　 ｏ ｎ 　 Ｍａ ｃ ｈｉ ｎｅ 　 Ｌｅ ａ ｒ ｎ ｉ ｎ ｇ，Ａｔ ｌ ａ ｎ ｔ ａ ，ＵＳＡ ： ｓ ． ｎ ． 　 ２ Ｏ１ ３：８ Ｏ 一 ８ ８ ． 　

［ ２ ９ ］ 　 Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 　 Ｙ．Ｅ ｆ ｆ ｉ ｃ ｉ ｅ ｎ ｃ ｙ 　 ｏ ｆ 　 ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ｄ ｅ ｓ ｃ ｅ ｎ ｔ 　 ｍｅ ｔ ｈ ｏ ｄ ｓ 　 ｏ ｎ 　 ｈ ｕ ｇ ｅ — ｓ ｃ ａ ｌ ｅ 　 ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ 　 ｐ ｒ ｏ ｂ ｌ ｅ ｍｓ ［ Ｊ ］ ．Ｓ Ｉ ＡＭ　 Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｎ 　 Ｏｐ ｔ ｉ ｍｉ ｚ ａ — 　
ｔ ｉ ｏ ｎ，２ ０ １ ２，２ ２ （ ２ ）： ３ ４１ － ３ ６ ２ ． 　

［ ３ ０ ］ 　 １ 　 ｉ ｕ 　 Ｊ ， Ｗｒ ｉ ｇ ｈ ｔ 　 Ｓ 　 Ｊ ．Ａｓ ｙ ｎ ｃ ｈ ｒ ｏ ｎ ｏ ｕ ｓ 　 ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ 　 ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ｄ ｅ ｓ ｃ ｅ ｎ ｔ ： Ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ｉ ｓ ｍ　 ａ ｎ ｄ 　 ｃ ｏ ｎ ｖ ｅ ｒ ｇ ｅ ｎ ｃ ｅ 　 ｐ ｒ ｏ ｐ ｅ ｒ ｔ ｉ ｅ ｓ［ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ ： ∥ 　
ａ ｒ ｘ ｉ ｖ ． ｏ ｒ ｇ ／ ，２ ０ １ ４ ． 　
Ｒｉ ｃ ｈ ｔ ｄ ｒ ｉ ｋ 　 Ｐ，Ｔａ ｋ ｄ 　ｃ 　 Ｍ．Ｉ ｔ ｅ ｒ ａ ｔ ｉ ｏ ｎ 　 ｃ ｏ ｍｐ ｌ ｅ ｘ ｉ ｔ ｙ 　 ｏ ｆ 　 ｒ ａ ｎ ｄ ｏ ｍｉ ｚ ｅ ｄ 　 ｂ ｌ ｏ ｃ ｋ — ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ｄ ｅ ｓ ｃ ｅ ｎ ｔ 　 ｍｅ ｔ ｈｏ ｄ ｓ 　 ｆ ｏ ｒ 　 ｍｉ ｎ ｉ ｍｉ ｚ ｉ ｎ ｇ 　 ａ 　 ｃ ｏ ｍｐ ｏ ｓ ｉ ｔ ｅ 　 ［ ３ １ ］ 　

ｆ ｕ ｎ ｃ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．Ｍａ ｔ ｈ ｅ ｍａ ｔ ｉ ｃ ａ ｌ 　 Ｐ ｒ ｏ ｇ ｒ ａ ｍｍｉ ｎ ｇ ， ２ ０ １ ４ 。１ ４ ４ （ １ － ２ ） ： １ － ３ ８ ． 　 ［ ３ ２ ］ 　Ｓ ｈ ａ Ｉ ｅ ｖ 　 Ｓ ｈ ｗａ ｒ ｔ ｚ 　 Ｓ ，Ｚ ｈ ａ ｎ ｇ 　 Ｔ．Ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ 　 ｄ ｕ ａ ｌ 　 ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ａ ｓ ｃ ｅ ｎ ｔ 　 ｍｅ ｔ ｈ ｏ ｄ ｓ 　 ｆ ｏ ｒ 　 ｒ ｅ ｇ ｕ ｌ ａ ｒ ｉ ｚ ｅ ｄ 　 ｌ ｏ ｓ ｓ ［ Ｊ ］ ．Ｔｈ ｅ 　 Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｆ 　 Ｍａ ｃ ｈ ｉ ｎ ｅ 　
Ｌｅ ａ ｒ ｎ ｉ ｎ ｇ 　 Ｒｅ ｓ ｅ ａ ｒ ｃ ｈ，２ ０１ ３ ，１ ４ （ １ ）： ５ ６ ７ — ５ ９ ９ ． 　

［ ３ ３ ］ 　 Ｓ ｈ ａ ｌ ｅ ｖ — Ｓ ｈ ｗ ａ ｒ ｔ ｚ 　 Ｓ， Ｚ ｈ ａ ｎ ｇ 　 Ｔ ．Ａｃ ｃ ｅ ｌ ｅ ｒ ａ ｔ ｅ ｄ 　 ｐ ｒ ｏ ｘ ｉ ｍａ ｌ 　 ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ 　 ｄ ｕ ａ ｌ 　 ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ａ ｓ ｃ ｅ ｎ ｔ 　 ｆ ｏ ｒ 　 ｒ ｅ ｇ ｕ ｌ ａ ｒ ｉ ｚ ｅ ｄ 　 ｌ ｏ ｓ ｓ 　 ｍｉ ｎ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ［ Ｅ Ｂ ／ 　

ＯＬ ］ ．ｈ ｔ ｔ ｐ ｔ ？ ？ ｌ ｉ ｎ ｋ ． ｓ ｐ ｒ ｉ ｎ ｇ ｅ ｒ ． ｃ ｏ ｍ／ ｊ ｏ ｕ ｒ ｎ ａ ｌ ／ １ ０ １ ０ ７ ，２ ０ １ ５ ． 　
［ ３ ４ ］ 　 Ｚ ｈ ａ ｎ ｇ 　 Ｙ，Ｘｉ ａ ｏ 　 Ｌ ．Ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ 　 ｐ ｒ ｉ ｍａ ｌ — ｄ ｕ ａ ｌ 　 ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ｍｅ ｔ ｈ ｏ ｄ 　 ｆ ｏ ｒ 　 ｒ ｅ ｇ ｕ ｌ ａ ｒ ｉ ｚ ｅ ｄ 　 ｅ ｍｐ ｉ ｒ ｉ ｃ ａ ｌ 　 ｒ ｉ ｓ ｋ 　 ｍｉ ｎ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ［ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ ： ∥　
ａ ｒ ｘ ｉ ｖ ． ｏ ｒ ｇ ／，２ ０ １ ４ ． 　

［ ３ ５ ］ 　 Ｃｈ ｅ ｎ 　 Ｙ，Ｌ ａ ｎ 　 Ｇ，Ｏｕ ｙ ａ ｎ ｇ 　 Ｙ．Ｏｐ ｔ ｉ ｍａ ｌ 　 ｐ ｒ ｉ ｍａ ｌ 　 ｄ ｕ ａ ｌ 　 ｍｅ ｔ ｈ ｏ ｄ ｓ 　 ｆ ｏ ｒ 　 ａ 　 ｃ ｌ ａ ｓ ｓ 　 ｏ ｆ 　 ｓ ａ ｄ ｄ ｌ ｅ 　 ｐ ｏ ｉ ｎ ｔ 　 ｐ ｒ ｏ ｂ ｌ ｅ ｍｓ ［ Ｊ ］ ．Ｓ Ｉ ＡＭ　 Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｎ 　 Ｏｐ ｔ ｉ ｍｉ — 　
ｚ ａ ｔ ｉ ｏ ｎ，２ ０ １ ４，２ ４（ ４ ）： １ 　 ７ ７ ９ － １ ８ １ ４ ． 　

［ ３ ６ ３ 　 Ｄｅ ｖ ｏ ｌ ｄ ｅ ｒ 　 Ｏ， Ｇｌ ｉ ｎ ｅ ｕ ｒ 　 Ｆ， Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 　 Ｙ ．Ｆ ｉ ｒ ｓ ｔ — ｏ ｒ ｄ ｅ ｒ 　 ｍｅ ｔ ｈ ｏ ｄ ｓ 　 ｏ ｆ 　 ｓ ｍｏ ｏ ｔ ｈ 　 ｃ ｏ ｎ ｖ ｅ ｘ 　 ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ 　 ｗｉ ｔ ｈ 　 ｉ ｎ ｅ ｘ ａ ｃ ｔ 　 ｏ ｒ ａ ｃ ｌ ｅ ［ Ｊ ］ ．Ｍａ ｔ ｈ ｅ ｍａ ｔ ｉ — 　
ｃ ａ ｌ 　 Ｐｒ ｏ ｇ ｒ ａ ｍｍ ｉ ｎ ｇ，２ ０１ ４，１ ４ ６（ １ — ２ ）： ３ ７ — ７ ５ ． 　
Ａｖ ｒ ｏ ｎ 　 Ｈ ［ ３ ７ ］ 　 ，Ｄｒ ｕ ｉ ｎ ｓ ｋ ｙ 　 Ａ ，Ｇｕ ｐ ｔ ａ 　 Ａ． Ｒｅ ｖ ｉ ｓ ｉ ｔ ｉ ｎ ｇ 　 ａ ｓ ｙ ｎ ｃ ｈｒ ｏ ｎｏ ｕ ｓ 　 ｌ ｉ ｎ ｅ ａ ｒ 　 ｓ ｏ ｌ ｖ ｅ ｒ ｓ ：Ｐｒ ｏ ｖ ａ ｂｌ ｅ 　 ｃ ｏ ｎｖ ｅ ｒ ｇ ｅ ｎｃ ｅ 　 ｒ ａ ｔ ｅ 　 ｔ ｈ ｒ ｏ ｕ ｇ ｈ 　 ｒ ａ ｎ ｄ ｏ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ 　

［ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ 　？ ｝ ａ ｒ ｘ ｉ ｖ ． ｏ ｒ ｇ ／ 　２ ０ １ ４ ． 　 Ｅ ３ ８ ］ 　 Ｒｅ ｅ ｈ ｔ 　 Ｂ， Ｒｅ 　 Ｃ， Ｗｒ ｉ ｇ ｈ ｔ 　 Ｓ， ｅ ｔ 　 ａ １ ．Ｈｏ ｇ ｗｉ ｌ ｄ ： Ａ 　 ｌ ｏ ｃ ｋ — ｆ ｒ ｅ ｅ 　 ａ ｐ ｐ ｒ ｏ ａ ｃ ｈ 　 ｔ ｏ 　 ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ ｉ ｚ ｉ ｎ ｇ 　 ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ 　 ｇ ｒ ａ ｄ ｉ ｅ ｎ ｔ 　 ｄ ｅ ｓ ｃ ｅ ｎ ｔ ［ Ｃ ］ ∥ Ａｄ ｖ ａ ｎ ｃ ｅ ｓ 　 ｉ ｎ 　 Ｎｅ ｕ ｒ ａ ｌ 　 Ｉ ｎ ｆ ｏ ｒ ｍａ ｔ ｉ ｏ ｎ 　 Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ 　 Ｓ ｙ ｓ ｔ ｅ ｍｓ ．Ｇｒ ａ ｎ ａ ｄ ａ ，Ｓ ｐ ａ ｉ ｎ ： Ｉ ｓ ． １ ３ ＿ ． ］ ，２ ０ １ １ ：６ ９ ３ — ７ ０ １ ． 　
［ ３ ９ ］ 　 Ｒｉ ｃ ｈ ｔ ｄ ｒ ｉ ｋ 　 Ｐ， Ｔａ ｋ ｄ 　ｃ 　 Ｍ ．Ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ 　 ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ｄ ｅ ｓ ｃ ｅ ｎ ｔ 　 ｍｅ ｔ ｈ ｏ ｄ ｓ 　 ｆ ｏ ｒ 　 ｂ ｉ ｇ 　 ｄ ａ ｔ ａ 　 ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ［ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ ： ∥ａ ｒ ｘ ｉ ｖ ． ｏ ｒ ｇ ／ ，２ ０ １ ４ ． 　

［ ４ ｏ ］ 　 Ｌ ｉ ｕ 　 Ｊ ，Ｗｒ ｉ ｇ ｈ ｔ 　 Ｓ 　 Ｊ ， Ｒ６ 　 Ｃ， ｅ ｔ 　 ａ １ ．Ａｎ 　 ａ ｓ ｙ ｎ ｃ ｈ ｒ ｏ ｎ ｏ ｕ ｓ 　 ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ 　 ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ 　 ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ｄ ｅ ｓ ｃ ｅ ｎ ｔ 　 ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ［ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ ： ∥ａ ｒ ｘ ｉ ｖ ． 　
ｏ ｒ ｇ ／ ，２ ０ １ ４ ． 　

［ ４ １ ３ 　 Ｌ ｉ ｕ 　 Ｊ ，Ｗ ｒ ｉ ｇ ｈ ｔ 　 Ｓ 　 Ｊ ，Ｓ ｒ ｉ ｄ ｈ ａ ｒ 　 Ｓ ．Ａ ｎ 　 ａ ｓ ｙ ｎ ｃ ｈ ｒ ｏ ｎ ｏ ｕ ｓ 　 ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ 　 ｒ ａ ｎ ｄ ｏ ｍｉ ｚ ｅ ｄ 　 ｋ ａ ｅ ｚ ｍａ ｒ ｚ 　 ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ ［ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ ： ∥ａ ｒ ｘ ｉ ｖ ． ｏ ｒ ｇ ／ ， 　
２ Ｏ １ ４ ． 　

［ ４ ２ ３ 　 Ｓ ｔ ｒ ｏ ｈ ｍｅ ｒ 　 Ｔ， Ｖｅ ｒ ｓ ｈ ｙ ｎ ｉ ｎ 　 Ｒ．Ａ 　 ｒ ａ ｎ ｄ ｏ ｍｉ ｚ ｅ ｄ 　 ｋ ａ ｃ ｚ ｍａ ｒ ｚ 　 ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ 　 ｗ ｉ ｔ ｈ 　 ｅ ｘ ｐ ｏ ｎ ｅ ｎ ｔ ｉ ａ ｌ 　 ｃ ｏ ｎ ｖ ｅ ｒ ｇ ｅ ｎ ｃ ｅ ［ Ｊ ］ ．Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｆ 　 Ｆ ｏ ｕ ｒ ｉ ｅ ｒ 　 Ａｎ ａ ｌ ｙ ｓ ｉ ｓ 　
ａ ｎ ｄ 　 Ａｐ ｐ ｌ ｉ ｃ ａ ｔ ｉ ｏ ｎ ｓ ，２ ０ ０ ９，１ ５（ ２ ）： ２ ６ ２ — ２ ７ ８ ． 　

［ ４ ３］ Ｇｒ ａ ｎ 　 Ｍ ，Ｂ ｏ ｙ ｄ 　 Ｓ ，Ｙｅ 　 Ｙ．Ｃ ｖ ｘ ：Ｍａ ｔ ｌ ａ ｂ 　 ｓ ｏ ｆ ｔ ｗ ａ ｒ ｅ 　 ｆ ｏ ｒ 　 ｄ ｉ ｓ ｃ ｉ ｐ ｌ ｉ ｎ ｅ ｄ 　 ｃ ｏ ｎ ｖ ｅ ｘ 　 ｐ ｒ ｏ ｇ ｒ ａ ｍｍｉ ｎ ｇ ［ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ ： ∥ｃ ｖ ｘ ｒ ． ｃ ｏ ｍ／ ｃ ｖ ｘ ／ ， 　
２ ０ ０ ８ ． 　

［ ４ ４ ］Ｃ ａ ｎ ｄ ｅ ｓ 　 Ｅ， Ｒｏ ｍｂ ｅ ｒ ｇ 　 Ｊ ．１ １ 一 ｍａ ｇ ｉ ｃ ：Ｒｅ ｃ ｏ ｖ ｅ ｒ ｙ 　 ｏ ｆ 　 ｓ ｐ ａ ｒ ｓ ｅ 　 ｓ ｉ ｇ ｎ ａ ｌ ｓ 　 ｖ ｉ ａ 　 ｃ ｏ ｎ ｖ ｅ ｘ 　 ｐ ｒ ｏ ｇ ｒ ａ ｍｍｉ ｎ ｇ ．［ Ｅ Ｂ ／ Ｏ Ｌ］ ．ｈ ｔ ｔ ｐ ： ∥ ｅ —ｄ ｕ ／ ｌ ｌ ｍａ ｇ ｉ ｃ ／ 　
ｄ ｏ ｗｎ ｌ ｏ ａ ｄ ｓ ／ ｌ ｌ ｍａ ｇ ｉ ｃ ， ２ ０ ０ ５ ． 　

［ ４ ５ ３ 　 Ｇｏ ｌ ｄ ｓ ｔ ｅ ｉ ｎ 　 Ｔ，Ｏｓ ｈ ｅ ｒ 　 Ｓ ．Ｔｈ ｅ 　 ｓ ｐ ｌ ｉ ｔ 　 ｂ ｒ ｅ ｇ ｍａ ｎ 　 ｍｅ ｔ ｈ ｏ ｄ 　 ｆ ｏ ｒ 　 １ １ 一 ｒ ｅ ｇ ｕ ｌ ａ ｒ ｉ ｚ ｅ ｄ 　 ｐ ｒ ｏ ｂ ｌ ｅ ｍｓ ［ Ｊ ］ ．Ｓ Ｉ ＡＭ　 Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｏ 　 Ｉ ｍａ ｇ ｉ ｎ ｇ 　 Ｓ ｃ ｉ ｅ ｎ ｃ ｅ ｓ ，２ ０ ０ ９ ， 　
２ （ ２ ）： ３ ２ ３ － ３ ４ ３ ． 　

［ ４ ６ ］ Ｒｕ ｄ ｉ ｎ 　 Ｉ 　 Ｉ 　 Ｏｓ ｈ ｅ ｒ 　 Ｓ， Ｆ ａ ｔ ｅ ｍｉ 　 Ｅ ．Ｎｏ ｎ ｌ ｉ ｎ ｅ ａ ｒ 　 ｔ ｏ ｔ ａ ｌ 　 ｖ ａ ｒ ｉ ａ ｔ ｉ ｏ ｎ 　 ｂ ａ ｓ ｅ ｄ 　 ｎ ｏ ｉ ｓ ｅ 　 ｒ ｅ ｍｏ ｖ ａ ｌ 　 ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍｓ ［ Ｊ ］ ．Ｐ ｈ ｙ ｓ ｉ ｃ ａ 　 Ｄ： Ｎｏ ｎ ｌ ｉ ｎ ｅ ａ ｒ 　 Ｐ ｈ ｅ ｎ ｏ ｍｅ — 　
ｎ ａ，１ ９ ９ ２，６ Ｏ（ １ ）： ２ ５ ９ － ２ ６ ８． 　

［ ４ ７ ］ Ｋｉ ｍ　 Ｓ 　 Ｊ ，Ｋｏ ｈ 　 Ｋ， Ｂ ｏ ｙ ｄ 　 Ｓ ．Ｓ ｋ ｙ ｓ ｔ ｒ ｅ ｎ ｄ 　 ｆ ｉ ｌ ｔ ｅ ｒ ｉ ｎ ｇ ［ Ｊ ］ ．Ｓ ｉ ａ ｍ 　 Ｒｅ ｖ ｉ ｅ ｗ， ２ ０ ０ ９ ，５ １ （ ２ ） ： ３ ３ ９ — ３ ６ ０ ． 　

［ ４ ８ ３ 　 Ｚ ｈ ｕ 　 ｘ，Ｈｕ ａ ｎ ｇ 　 Ｚ ，Ｃ ｕ ｉ 　 Ｊ ，ｅ ｔ 　 ａ １ ．Ｖｉ ｄ ｅ ｏ — ｔ ｏ — ｓ ｈ ｏ ｔ 　 ｔ ａ ｇ 　 ｐ ｒ ｏ ｐ ａ ｇ ａ ｔ ｉ ｏ ｎ 　 ｂ ｙ 　 ｇ ｒ ａ ｐ ｈ 　 ｓ ｐ ａ ｒ ｓ ｅ 　 ｇ ｒ ｏ ｕ ｐ 　 ｌ ａ ｓ ｓ ｏ ［ Ｊ ￣ ．Ｍｕ ｌ ｔ ｉ ｍｅ ｄ ｉ ａ ，Ｉ Ｅ Ｅ Ｅ 　 Ｔ ｒ ａ ｎ ｓ ａ ｃ — 　
ｔ ｉ ｏ ｎ ｓ 　 ｏ ｎ，２ Ｏ １ ３，１ ５（ ３ ）： ６ ３ ３ － ６ ４ ６ ． 　

［ ４ ９ ］ Ｙｕ ａ ｎ 　 Ｍ， Ｌｉ ｎ 　 Ｙ．Ｍｏ ｄ ｅ ｌ 　 ｓ ｅ ｌ ｅ ｃ ｔ ｉ ｏ ｎ 　 ａ ｎ ｄ 　 ｅ ｓ ｔ ｉ ｍａ ｔ ｉ ｏ ｎ 　 ｉ ｎ 　 ｒ ｅ ｇ ｒ ｅ ｓ ｓ ｉ ｏ ｎ 　 ｗｉ ｔ ｈ 　 ｇ ｒ ｏ ｕ ｐ ｅ ｄ 　 ｖ ａ ｒ ｉ ａ ｂ ｌ ｅ ｓ ［ Ｊ ］ ．Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｆ 　 ｔ ｈ ｅ 　 Ｒ ｏ ｙ ａ ｌ 　 Ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ａ ｌ 　 Ｓ ｏ — 　
ｃ ｉ ｅ ｔ ｙ：Ｓｅ ｒ ｉ ｅ ｓ 　 Ｂ（ Ｓｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ａ ｌ 　 Ｍｅ ｔ ｈ ｏ ｄ ｏ ｌ ｏ ｇ ｙ） ，２ ０ ０ ６，６ ８（ １ ）： ４ ９ — ６ ７ ． 　

［ ５ Ｏ ］Ｏｈ ｌ ｓ ｓ ｏ ｎ 　 Ｈ， Ｉ ￣ ｕ ｎ ｇ ，Ｌ ，Ｂ ｏ ｙ ｄ 　 Ｓ ．Ｓ ｅ ｇ ｍｅ ｎ ｔ ａ ｔ ｉ ｏ ｎ 　 ｏ ｆ 　 ａ ｒ ｘ － ｍｏ ｄ ｅ ｌ ｓ 　 ｕ ｓ ｉ ｎ ｇ 　 ｓ ｕ ｍ— ｏ ｆ — ｎ ｏ ｒ ｍｓ 　 ｒ ｅ ｇ ｕ １ ａ ｒ ｉ ｚ ａ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．Ａｕ ｔ ｏ ｍａ ｔ ｉ ｃ ａ ，２ ０ １ ０ ，４ ６ 　
（ ６ ）： １ １ ０ ７ — １ １ １ １ ． 　

［ ５ １ ］Ｃ ｅ ｖ ｈ ｅ ｒ 　 Ｖ， Ｂ ｅ ｃ ｋ ｅ ｒ 　 Ｓ ， Ｓ ｃ ｈ ｍｉ ｄ ｔ 　 Ｍ．Ｃ ｏ ｎ ｖ ｅ ｘ 　 ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ 　 ｆ ｏ ｒ 　 ｂ ｉ ｇ 　 ｄ ａ ｔ ａ ： Ｓ ｃ ａ ｌ ａ ｂ ｌ ｅ ，ｒ ａ ｎ ｄ ｏ ｍｉ ｚ ｅ ｄ ， ａ ｎ ｄ 　 ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ 　 ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍｓ 　 ｆ ｏ ｒ 　 ｂ ｉ ｇ 　 ｄ ａ — 　 ｔ ａ 　 ａ ｎ ａ ｌ ｙ ｔ ｉ ｃ ｓ ［ Ｊ ］ ．Ｓ ｉ ｇ ｎ ａ ｌ 　 Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ 　 Ｍａ ｇ ａ ｚ ｉ ｎ ｅ ，Ｉ Ｅ Ｅ Ｅ，２ ０ １ ４ ， ３ １ （ ５ ） ： ３ ２ — ４ ３ ． 　 Ｅ ５ ２ ］Ｐ ａ ｒ ｉ ｋ ｈ 　 Ｎ， Ｂ ｏ ｙ ｄ 　 Ｓ ．Ｐ ｒ ｏ ｘ ｉ ｍａ ｌ 　 ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍｓ ［ Ｊ ］ ．Ｆ ｏ ｕ ｎ ｄ ａ ｔ ｉ ｏ ｎ ｓ 　 ａ ｎ ｄ 　 Ｔｒ ｅ ｎ ｄ ｓ 　 ｉ ｎ 　 Ｏｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ，２ ０ １ ３ ，１ （ ３ ） ： １ ２ ３ — ２ ３ １ ． 　

４ ６ 　

数 据 采 集 与 处理 Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｆ 　 Ｄａ ｔ ａ 　 Ａｃ ｑ ｕ ｉ ｓ ｉ ｔ ｉ ｏ ｎ 　 ａ ｎ ｄ 　 Ｐｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ 　 Ｖｏ １ ． ３ ０ ， Ｎｏ ． １ ，２ ０ １ ５ 　

Ｅ ６ ３ ３ 　 Ｂ ｌ ａ ｃ ｋ ｆ ｏ ｒ ｄ 　 Ｌ 　 Ｓ ， Ｃｈ ｏ ｉ 　 Ｊ ， Ｃ ｌ ｅ ａ ｒ ｙ 　 Ａ，ｅ ｔ 　 ａ １ ．Ｓ ｃ ａ Ｌ ＡＰ ＡＣ Ｋ 　 ｕ ｓ ｅ ｒ ｓ 　ｇ ｕ ｉ ｄ ｅ ［ Ｅ Ｂ ／ ｏＬ ］ ．ｈ ｔ ｔ ｐ ： ∥ ＷＷＷ ． ｎ ｅ ｔ ｌ ｉ ｂ ． ０ ｒ ｇ ／ ｓ ｃ ａ ｌ ａ ｐ ａ ｃ ｋ ／ ｓ ｃ ａ ｌ ａ ｐ ａ ｃ ｋ 　
ｕ ｇ ． ｐ ｓ ．２ ０ ０ ６ ． 　

Ｅ ５ ４ ３ 　 Ｄ ｅ ｍｍｅ ｌ Ｍ　 Ｊ 　 Ｗ ，Ｈｅ ａ ｔ ｈ 　 Ｍ　 Ｔ， Ｖａ ｎ 　 Ｄｅ ｒ 　 Ｖｏ ｒ ｓ ｔ 　 Ｈ 　 Ａ．Ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ 　 ｎ ｕ ｍｅ ｒ ｉ ｃ ａ ｌ 　 ｌ ｉ ｎ ｅ ａ ｒ 　 ａ ｌ ｇ ｅ ｂ ｒ ａ ［ Ｊ ］ ．Ａｃ ｔ ａ 　 Ｎｕ ｍｅ ｒ ｉ ｃ ａ ，１ ９ ９ ３ ，２ ： １ １ １ — １ ９ ７ ． 　

［ ５ ５ ３ 　 Ｇａ ｌ ｌ ｉ ｖ ａ ｎ 　 Ｋ　 Ａ， Ｐ ｌ ｅ ｍｍｏ ｎ ｓ 　 Ｒ 　 Ｊ ， Ｓ ａ ｍｅ ｈ 　 Ａ．Ｐ ａ ｒ ａ ｌ ｌ ｅ ｌ 　 ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍｓ 　 ｆ ｏ ｒ 　 ｄ ｅ ｎ ｓ ｅ 　 ｌ ｉ ｎ ｅ ａ ｒ 　 ａ ｌ ｇ ｅ ｂ ｒ ａ 　 ｃ ｏ ｍｐ ｕ ｔ ａ ｔ ｉ ｏ ｎ ｓ ［ Ｊ ］ ．Ｓ Ｉ ＡＭ　 ｒ ｅ ｖ ｉ ｅ ｗ，１ ９ ９ ０ ， 　
３ ２ （ １ ）： ５ ４ － １ ３ ５ ． 　

Ｅ ５ ７ ］Ｓ ａ ｈ ａ 　 Ａ ，Ｔ ｅ ｗ ａ ｒ ｉ 　 Ａ．Ｏｎ 　 ｔ ｈ ｅ 　 ｆ ｉ ｎ ｉ ｔ ｅ 　 ｔ ｉ ｍｅ 　 ｃ ｏ ｎ ｖ ｅ ｒ ｇ ｅ ｎ ｃ ｅ 　 ｏ ｆ 　 ｃ ｙ ｃ ｌ ｉ ｃ 　 ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ｄ ｅ ｓ ｃ ｅ ｎ ｔ 　 ｍｅ ｔ ｈ ｏ ｄ ｓ ［ Ｊ ］ ．Ｓ ｉ ａ ｍ 　 Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｆ 　 Ｏｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ， 　
２ ０ ｌ ３，２ ３（ １） ： ５ ７ ６ — ６ ０１ ． 　

［ ５ ６ ］ 　 Ｆ ｒ ｉ ｅ ｄ ｍａ ｎ 　 Ｊ ，Ｈａ ｓ ｔ ｉ ｅ 　 Ｔ，Ｈｏ ｆ ｌ ｉ ｎ ｇ 　 Ｈ， ｅ ｔ 　 ａ １ ．Ｐ ａ ｔ ｈ ｗｉ ｓ ｅ 　 ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．Ｔｈ ｅ 　 Ａ ｎ ｎ ａ ｌ ｓ 　 ｏ ｆ 　 Ａ ｐ ｐ ｌ ｉ ｅ ｄ 　 Ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ｓ ，２ ０ ０ ７ ，１ 　
（ ２ ）： ３ ０ ２ － ３ ３ ２ ． 　

［ ５ ８ ３ 　 Ｌ ｅ ｖ ｅ ｎ ｔ ｈ ａ ｌ 　 Ｄ，Ｌ ｅ ｗｉ ｓ 　 Ａ 　 Ｓ ．Ｒ ａ ｎ ｄ ｏ ｍｉ ｚ ｅ ｄ 　 ｍｅ ｔ ｈ ｏ ｄ ｓ 　 ｆ ｏ ｒ 　 ｌ ｉ ｎ ｅ ａ ｒ 　 ｃ ｏ ｎ ｓ ｔ ｒ ａ ｉ ｎ ｔ ｓ ：Ｃ ｏ ｎ ｖ ｅ ｒ ｇ ｅ ｎ ｃ ｅ 　 ｒ ａ ｔ ｅ ｓ 　 ａ ｎ ｄ 　 ｃ ０ ｎ ｄ ｉ ｔ ｉ ｏ ｎ ｉ ｎ ｇ ［ Ｊ ］ ．Ｍａ ｔ ｈ ｅ ｍａ ｔ ｉ ｃ ｓ 　
ｏ ｆ 　 Ｏｐ ｅ ｒ ａ ｔ ｉ ｏ ｎ ｓ 　 Ｒｅ ｓ ｅ ａ ｒ ｃ ｈ，２ ０１ ０，３ ５ （ ３ ）： ６ ４ １ — ６ ５ ４ ． 　

［ ５ ９ ］Ｓ ｈ ａ ｌ ｅ ｖ ～ Ｓ ｈ ｗａ ｒ ｔ ｚ 　 Ｓ ，Ｔ ｅ ｗａ ｒ ｉ 　 Ａ．Ｓ ｔ ｏ ｃ ｈ ａ ｓ ｔ ｉ ｃ 　 ｍｅ ｔ ｈ ｏ ｄ ｓ 　 ｆ ｏ ｒ 　 １ 卜ｒ ｅ ｇ ｕ ｌ ａ ｒ ｉ ｚ ｅ ｄ 　 ｌ ｏ ｓ ｓ 　 ｍｉ ｎ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ［ Ｊ ］ ．Ｔｈ ｅ 　 Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｆ 　 Ｍａ ｃ ｈ ｉ ｎ ｅ 　 Ｌ ｅ ａ ｒ ｎ ｉ ｎ ｇ 　
Ｒｅ ｓ ｅ ａ ｒ ｃ ｈ，２ ０ １ ｌ，１ ２： １ ８ ６ ５ — １ ８ ９ ２ ． 　

［ ６ ０ ］ Ｑｕ 　 Ｚ， Ｒｉ ｃ ｈ ｔ ｄ ｒ ｉ ｋ 　 Ｐ， Ｚ ｈ ａ ｎ ｇ 　 Ｔ．Ｒ ａ ｎ ｄ ｏ ｍｉ ｚ ｅ ｄ 　 ｄ ｕ ａ ｌ 　 ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ａ ｓ ｃ ｅ ｎ ｔ 　 ｗｉ ｔ ｈ 　 ａ ｒ ｂ ｉ ｔ ｒ ａ ｒ ｙ 　 ｓ ａ ｍｐ ｌ ｉ ｎ ｇ［ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ ： ∥ａ ｒ ｘ ｉ ｖ ． ｏ ｒ ｇ ／ ， 　
２ Ｏ１ ４ ． 　

Ｅ ６ １ ］ Ｎｅ ｓ ｔ ｅ ｒ ｏ ｖ 　 Ｙ．Ｇ ｒ ａ ｄ ｉ ｅ ｎ ｔ 　 ｍｅ ｔ ｈ ｏ ｄ ｓ 　 ｆ ｏ ｒ 　 ｍｉ ｎ ｉ ｍｉ ｚ ｉ ｎ ｇ 　 ｃ ｏ ｍｐ ｏ ｓ ｉ ｔ ｅ 　 ｆ ｕ ｎ ｃ ｔ ｉ ｏ ｎ ｓ ［ Ｊ ］ ．Ｍａ ｔ ｈ ｅ ｍａ ｔ ｉ ｃ ａ ｌ 　 Ｐ ｒ ｏ ｇ ｒ ａ ｍｍｉ ｎ ｇ ， ２ ０ １ ３ ，１ ４ ０ （ １ ） ： １ ２ ５ — １ ６ １ ． 　 Ｅ ６ ２ ］ Ｔｓ ｅ ｎ ｇ 　 Ｐ．Ｏｎ 　 ａ ｃ ｃ ｅ ｌ ｅ ｒ ａ ｔ ｅ ｄ 　 ｐ ｒ ｏ ｘ ｉ ｍａ ｌ 　 ｇ ｒ ａ ｄ ｉ ｅ ｎ ｔ 　 ｍｅ ｔ ｈ ｏ ｄ ｓ 　 ｆ ｏ ｒ 　 ｃ ｏ ｎ ｖ ｅ ｘ － ｃ ｏ ｎ ｃ ａ ｖ ｅ 　 ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ 　 Ｅ Ｅ Ｂ ／ ＯＬ ］ ．ｈ ｔ ｔ ｐ 　 ｔ｝ ｝ ＷＷＷ． ｍｉ ｔ ． ｅ ｄ ｕ ／～　
ｄ ｉ ｍｉ ｔ ｒ ｉ ｂ ／ Ｐ Ｔ ｓ ｅ ｎ ｇ ／ ｐ ａ ｐ ｅ ｒ ｓ ． ｂ ｔ ｍｌ ，２ ０ ０ ８ ． 　

［ ６ ３ ］ Ｔｓ ｅ ｎ ｇ 　 Ｐ，Ｙｕ ｎ 　 Ｓ ．Ｂ ｌ ｏ ｃ ｋ — ｃ ｏ ｏ ｒ ｄ ｉ ｎ ａ ｔ ｅ 　 ｇ ｒ ａ ｄ ｉ ｅ ｎ ｔ 　 ｄ ｅ ｓ ｃ ｅ ｎ ｔ 　 ｍｅ ｔ ｈ ｏ ｄ 　 ｆ ｏ ｒ 　 ｌ ｉ ｎ ｅ ａ ｒ ｌ ｙ 　 ｃ ｏ ｎ ｓ ｔ ｒ ａ ｉ ｎ ｅ ｄ 　 ｎ ｏ ｎ ｓ ｍｏ ｏ ｔ ｈ 　 ｓ ｅ ｐ ａ ｒ ａ ｂ ｌ ｅ 　 ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ［ Ｊ ］ ． 　
Ｊ ｏ ｕ ｒ ｎ ａ ｌ 　 ｏ ｆ 　 Ｏｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ 　 Ｔｈ ｅ ｏ ｒ ｙ 　 ａ ｎｄ 　 Ａｐ ｐ ｌ ｉ ｃ ａ ｔ ｉ ｏ ｎ ｓ，２ ０ ０ ９，１ ４ ０（ ３） ： ５１ ３ — ５ ３ ５ ． 　

作 者 简介 ； 刘柳 （ １ ９ ８ ７ 一 ） ， 女， 博士研究生 ， 研究方向 ： 机 器 学 习 ，Ｅ — ｍａ ｉ ｌ ： Ｌ ｉ ｕ ． Ｌ ｉ ｕ 一 ２ ＠ｓ ｔ ｕ ｄ ｅ ｎ ｔ ． ｕ ｔ ｓ ． ｅ ｄ ｕ ． ａ ｕ ； 陶大程（ １ ９ ７ ８ 一 ） ， 男， 教 授　 研究方 向： 模式识别， 机器 学 习 ， 计算机视觉 ， Ｅ — ｍａ ｉ ｌ ： ｄ ａ ｃ ｈ ｅ ｎ ｇ ． ｔ ａ ｏ ＠ｇ ｍａ ｉ ｌ ． ｃ ｏ ｎ。 ｒ