非负矩阵分解：数学的奇妙力量.pdf

非负矩阵分解 数学的奇妙力量 东南大学汪鹏 文 计算机是人类解决难题 探索未知以及提供娱乐的绝佳工具 在高效运行着的各种计算机应用背后 融汇 了人类在物理 电子和数学等多门学科的高超智慧 严密的数学使得计算机能高效执行人类指令 控制内部各 种数据流的走向 因此在现代计算机科学研究中 数学的基础地位和重要作用无可替代 它使我们最大程度利 用有限的 硬件 软件资源 它使我们能够在 浩瀚的数据海洋中 快速查 到所关心的信息 数学与计算机科学一 起演绎了 许多精彩的故事 N M F 的发展及原理 著名的科学杂志 Na t u r e 于1 9 9 9 年刊登了两位科学家D D L e e和H S S e u n g对数学中非负矩阵研究的突出成 果 该文提出了一种新的矩阵分解思想 非负矩阵分解 N o n n e g a t i v e Ma t r i x F a c t o r i z a t i o n N MF 算法 即N MF 是在矩阵中所有元素均为非负数约束条件 之下的矩阵分解方法 该论文的发表迅速 引起了各个领域中的科学研究人员的重 视 一方面 科学研究中的很多大规模数 据的分析方法需要通过矩阵形式进行有效 处理 而N MF思想则为人类处理大规模 数据提供了一种新的途径 另一方面 N MF分解算法相较于传统的一些算法而 言 具有实现上的简便性 分解形式和分 解结果上的可解释性 以及占用存储空间 少等诸多优点 信息时代使得人类面临分析或处理 各种大规模数据信息的要求 如卫星传回 的大量图像 机器人接受到的实时视频 流 数据库中的大规模文本 we b 上的海 量信息等 处理这类信息时 矩阵是人们 最常用的数学表达方式 比如一幅图像就 恰好与一个矩阵对应 矩阵中的每个位置 3 8计算机教育 2 0 0 4 1 0 存放着图像中一个像素的空 白 位置和色彩 信息 由于实际问题中这样的矩阵很庞 大 其中存放的信息分布往往不均匀 因 此直接处理这样的矩阵效率低下 这对很 多实际问题而言就失去了实用意义 为高 效处理这些通过矩阵存放的数据 一个关 键的必要步骤便是对矩阵进行分解操作 通过矩阵分解 一方面将描述问题的矩阵 的维数进行削减 另一方面也可以对大量 的数据进行压缩和概括 在科学文献中 讨论利用矩阵分解 来解决实际问题的分析方法很多 如 P C A 主成分分析 I C A 独立成分分 析 S VD 奇异值分解 V Q 矢量量 化 等 在所有这些方法中 原始的大矩 阵V被近似分解为低秩的V WH形式 这 些方法的共同特点是 因子W 和 H中的 元素可为正或负 即使输入的初始矩阵元 素是全正的 传统的秩削减算法也不能保 证原始数据的非负性 在数学上 从计算 的观点看 分解结果中存在负值是正确 的 但负值元素在实际问题中往往是没有 意义的 例如图像数据中不可能有负值的 像素点 在文档统计中 负值也是无法解 释的 因此 探索矩阵的非负分解方法一 直是很有意义的研究问题 正是如此 L e e 和S e u n g两位科学家的N MF方法才得到 人们的如此关注 NMF 是一种新的矩阵分解算法 它 克服了传统矩阵分解的很多问题 通过寻 找上下文有意义的解决方法 提供解释数 据的更滦看法 NMF通过寻找低秩 非 负分解那些都为非负值的矩阵 这在现实 的应用中有很多例子 如数字图像中的像 素一般为非负数 文本分析中的单词统计 也总是非负数 股票价格也总是正数等 等 N MF 的基本思想可以简单描述为 对 于任意给定的一个非负矩阵A N MF算 法能够寻找到 一 个非负矩阵 U和一个非 负矩阵V 使得满足 从而将一个非负的 矩阵分解为左右两个非负矩阵的乘积 由 于分解前后的矩阵中仅包含非负的元素 因此 原矩阵A中的一列向量可以解释为 对左矩阵 U中所有列向量 称为基向量 的加权和 而权重系数为右矩阵V中对应 列向量中的元素 这种基于基向量组合的 表示形式具有很直观的语义解释 它反映 了人类思维中 局部构成整体 的概念 研究指出 非负矩阵分解是个N P 问题 可 以划为优化问题用迭代方法交替求解 U 和V NMF算法提供了基于简单迭代的 求解 u V的方法 求解方法具有收敛速 维普资讯 度快 左右非负矩阵存储空间小的特点 它能将高维的数据矩阵降维处理 适合处 理大规模数据 利用NMF 进行文本 图 像大规模数据的分析方法 较传统的处理 算法速度更快 更便捷 NMF思想的提 出迅速得到了很多人的重视 并有很多将 这种思想应用到实际中成功解决具体实际 问题的例子 通过图1中的面部特征提取例子可 领略N MF处理数据的方式 最左边的大 矩阵由一系列的小图组成 这些小图是分 析数据库中包含的2 4 2 9个脸部图像的结 果 每幅图像由1 9 1 9 个像素组成 传 统方法中这样的小图是一幅完整的人睑图 像 但是在NMF方法中 每个小图是通 过一组基图像乘以一个权重矩阵而产生的 面部特征图 经过这样处理的每幅小图像 恰好表示了诸如 鼻子 嘴巴 眼睛 等人睑局部概念特征 这便大大压缩了存 放的图像数据量 左边的大矩阵由每幅小 图像的1 9 列一起组成矩阵的一列 那样它 就是 1 9 1 9 3 6 1 行 2 4 2 9 列 由于N MF 不允许基图像或中间的权重矩阵中出现负 值 因此只有相加组合得到的正确基图像 才允许 最后通过处理后的重构图像效果 是比较满意的 这个例子中 NMF方法 用基图像来代表眼 眉毛 鼻子 嘴 耳 朵 胡子等 它们一起组成了数据库中的 脸 这样给人最先的直觉就是它很好地压 缩了数据 事实上L e e 和S e u n g在他们的 论文中更深入地指出 与人类识别事物的 过程相似 N MF 也是一种优化的机制 近 似于我们的脑分析和存储人脸数据的过 程 这个例子中 原图像表示这些局部特 征的加权组合 这与人类思维中 局部构 成整体 的概念是相吻合的 因此 N MF 算法似乎体现了一种智能行为 事实上 在L ee和S e u n g 发表他们的 研究成果之前 针对非负矩阵的研究早在 2 0世纪 7 0年代已 经有数学家做了一 些相关的工作 但 是没有引起过多的 关注 2 0 世纪9 0 年 代早期 科学家开 始将数学上非负矩 阵的研究成果用于 环境处理和卫星遥 原始图像 重构图像 因 冒 图 1 N MF 提取面部特征的实例 控的应用 但是对于非负矩阵的应用意义 和价值的理解仍只局限于少数科学家中 人们还没有广泛重视这种方法 直到1 9 9 9 年L ee和S e u n g的非负矩阵研究成果发表 在 N a t u r e 杂志之后 达一切 得以改 变 尽管同年有另曲位科学家也发表 r 与 L ee 和 S e u n g相近的研究结果 但由十论 文刊登在并非如 Na t u r e 那样具有极高 声誉的学术杂志上 因此其工作并没有得 到如L ee和S e u n g 同样的关注 这也从一 个侧面折射了高水平学术杂志对研究工作 的推动作用 应用领域 NMF是一个很有效的算法 它力 图在大规模的矩阵数据中发现具有解释 功能的关系 相比当前文献中公布的其 他方法来说 使用NMF的算法也是非 常精确和快速的 NMF算法思想能为 世界上权威的学术刊物所接受并非偶 然 因为该理论本身蕴涵了巨大的潜 能 这种潜在的力量将通过各种具体的 应用来得以体现 计算机能通过 NM F 算法更快更好地处理哪些实际问题呢 在众多应用中 NMF能被用于发现数 据库中的图像特征 便于快速自动识别 应用 能够发现文档的语义相关度 用 于信息自动索引和提取 能够在 DNA 阵列分析中识别基因等等 我们将对此 作一些大致的描述 1 图像分析 NMF最成功的 类应用是在图像的 分析和处理领域 图像本身包含大量的数 据 计算机一般将图像的信息按照矩阵的 形式进行存放 针对图像的识别 分析和 处理也是在矩阵的基础上进行的 这些特 点使得 N MF方法能很好地与图像分析处 理相结合 人们已经利用N MF算法 对 卫星发回的图像进行处理 以自动辨别太 空中的垃圾碎片 使用NMF算法对天文 望远镜拍摄到的图像进行分析 有助于天 文学家识别星体 美国还尝试在机场安装 由N MF算法驱动的识别系统 根据事先 输入计算机的恐l布 分子的特征图像库来自 动识别进出机场的可疑恐怖分子 2 文本聚类 数据挖掘 文本在人类日常接触的信息中占有 很大分量 为 r 更快更精确地从大量的文 本数据中取得所需要的信息 针对文本信 息处理的研究一直没有停止过 文本数据 不光信息量大 而且一般是无结构的 此 外 典型的文本数据通常以矩阵的形式被 计算机处理 此时的数据矩阵具有高维稀 疏的特征 因此 对大规模文本信息进行 处理分析的另一个障碍便是如何削减原始 数据的维数 NMF算法正是解决这方面 难题的一种新手段 NMF在挖掘用户所 需数据和进行文本聚类研究中都有着成功 的应用例子 由于 N MF算法在处理文本 数据方面的高效性 著名的商业数据库软 计算机教育 2 0 0 4 1 0 39 维普资讯 件O r a c l e 在其第 l O 版中专门利用N MF算 法来进行文本特征的提取和分类 为什么 NMF 对十文本信息提取得很好呢 原因在 于智能文本处理的核心问题是以一种能捕 获语义或相关信息 的方式来表示文本 但 是传统的常用分析方法仅仅是对词进行统 计 而不考虑其他的信息 而N MF不同 它往往能达到表示信息的局部之间相关关 系的效果 从而获得更好的处理结果 3 语音处理 语音的 自动识别一直是计算机科学 家努力的方向 也是未来智能应用实现的 基础技术 语音同样包含大量的数据信 启 识别语音的过程也是对这些信息处理 的过程 NMl 算法 这方面也为我们提 供了一种新方法 住已有的应用中 N MF 算法成功实现 r 有效的语音特征提取 并 且由于NMF算法的快速性 对实现机器 的实时语音识别有着促进意义 也有使用 NMF方法进行音乐分析的应用 复调音 乐的识别是个很困难的问题 三菱研究所 和MI T 麻省理 I 学院 的科学家合作 利用NMF从演奏中的复凋音乐中识别出 各个调子 并将它们分别记录 卜 来 实验 结果表明 这种采用N MF算法的方法 光简单 而且无须基十知识库 4 机器人控制 如何快速准确地让机器人识圳周嗣 的物体对于机器人研究具有重要的意义 因为这是机器人能迅速作出相 反应和动 作的基础 机器人通过传感器获得周围环 境的图像信息 这些图像信息也是以矩阵 的形式存储的 已经有研究人员采用 NMF算法实现了机器人对周同对象的快 速识别 根据现有的研究资料 示 识别 的准确率达到 了8 0 以上 5 生物医学工程和化学工程 生物医学和化学研究中 也常常需 要借助计算帆来分析处理试验的数据 往 往一蝗烦杂的数据会耗费研究人员的过多 精力 NMF算法也为这些数据的处理提 供了一种新的高效快速的途径 科学家将 NMF方法用于处理核医学中的电 发射 过程的动态连续图像 有效地从这些动态 图像中提取所需要的特征 NMF还町以 应用列遗传学和药物发现中 因为N MF 的分解不出现债值 因此采用N MF分析 基因D N A的分子序列口 丁 使分析结果更加可 靠 同样 用N MF 来选择药物成分还可以 获得最有效的且负作用最小的新药物 此外 NMF算法在环境数据处理 信号分析与复杂对象的识别方面都有着很 好的应用 近年来采用NMF思想的应用 才刚展开 相信以后会有更多的成功应 用 这些 成功 的 应用反过 来也 将 促进 NMF的进 步研究 结束语 数学如同计算机的灵魂 N MF通过 计算机与备个领域结合后的应用取得了令 人叹服的成效 NMF的故事还在继续 NMF的应用领域还有侍进 一 步的发掘 针对 NM F的进一 步研究也没有停止过 其中诸如分解的存在性 惟一性和收敛性 以及收敛的速度等问题的深入探讨必将使 该 思 想 能更 好 地服 务 于人 类 互 第二届中国软件质量 测试与产业发展战略国际研讨会 软件工程国际合作研i t 2 0 0 4 年1 0 月2 3 2 4日于北京召开 2 0 0 4 年1 0 月1 4 1 5日于上海举行 为贯彻科学技术部 信息产业部等国家五部委关于 软件 在国务院和外交部的大力支持下 第2 8 届国际软件工程 企业要努力提高自身的标准化水平 积极开展质量保证体系评 大会 I C S E 2 0 0 6 将于2 0 0 6 年 5 月2 0日 2 8日 在上海国际 估工作和软件测试工作 规范软件产品的开发和生产过程 保 会议中心举办 届时将有全世界 1 0 0 0多名软件行业专家与学 证国产软件质量 的精神 中国软件行业协会与国家科技部火 者参加会议 这也将是中国软件界最有影响的重大事件之一 炬高技术产业开发中心将于2 0 0 4 年1 0 月2 3 2 4日在北京召开 国际软件工程大会主要由美国计算机协会 AC M 和美国电 第二届中国软件质量 测试与产业发展战略国际研讨会 气与电子工程师协会一计算机协会 I E E E C S 主办 大会 会议将邀请信息产业部 科学技术部等政府部门领导做 以交流软件前沿技术和传播先进理念为宗旨 其发布的软件 指导性讲话 由国际国内软件质量与测试专家进行演讲 国际 工程最新研究成果在学术界享有盛誉 国内大型软件企业介绍先进的软件测试与质量管理经验 银 于2 0 0 4 年 1 0 月 1 4 1 5日在上海召开的软件工程国际合 行 电信 安全等不同领域的软件