Ε 1 Ε 1 Ε 2008 年 10 月 第 10 期 October 2008 No. 10 F 范数及矩阵分解实例研究 李华云 (盐城工学院图书馆 , 江苏 盐城 224003) 〔摘 　要〕 　本文分别介绍了两种矩阵分解的方法 ———QR 分解和 SVD 分解。并引入罗贝尼乌斯 (Frobenius) 范数 对以上两种矩阵分解方法分别进行降秩度量。最后用实例模拟了 SVD 分解和 F 范数评估 , 得出一些有益的结论。 〔关键词〕 　矩阵分解 ; SVD ; QR ; F 范数 〔中图分类号〕G354 　〔文献标识码〕C 　〔文章编号〕1008 - 0821 (2008) 10 - 0223 - 03 Frobenius Norm and Matrix Decomposition (Library , Yancheng Institute of Technology , Yancheng 224003 , China) Li Huayun 〔Abstract〕 　This article introduced two methods for matrix decomposition. They are QR decomposition and SVD decomposition. Frobenius norm was used to do downward rank measurement for these two methods. Finally , a docu ment was set as an example to do SVD decomposition and F - norm evaluation. 〔Key words〕 　matrix decomposition ; SVD ; QR ; F - norm 　　研究发现 , 文本库中往往存在隐含的关于词使用的语 义结构 , 这种结构由于部分地被文本中词的语义和形式上 的多样性所掩盖而不明显 。潜在语义分析 (Latent semantic analysis) 作为一种新型的信息处理方法 , 通过利用统计计 算导出文本中隐含的语义 , 可以有效地提高信息利用的准 确性 。其中奇异值分解 ( Singular value decomposition) 方法 是 LSI 的关键计算步骤 。目前 , 矩阵分解方式主要有 QR 分 解和 SVD 分解两种 。本文将通过这两种方法的比较和 F 范 数的评估来分析 SVD 方法的有效性 。 1 　QR 分解 早先信息检索利用正交分解方法 ———QR 分解 , 虽然 这种方法已经被 SVD 取代 , 但是可以用来说明降秩的意 义 ; 矩阵 A 的 QR 分解可以表示为 : A = QR (1 - 1) 可以证明 , 任何矩阵的 QR 分解都是存在的 。其中 A 是 t ×d 的词汇 - 文本矩阵 , Q 是 t ×t 正交矩阵 , R 是 t × d 上三角矩阵 。 假设矩阵 A 的秩为 rA , 则 A 的 d 个列向量都可以用列 空间的 rA 个基向量来表示 , 从而可由 Q 的 rA 个列向量表 示 , 即 Q 的这 rA 个列向量作为 A 的一个基 。 A = QR = QA , QA ⊥ RA 0 = QARA (1 - 2) 其中 RA 是 R 的非零行 , QA ⊥对 A 不起作用 , QA 构成 了 A 的一个基 。如果 R 中零不出现在其底部 , 需要先对 A 作列置换 , 再 QR 分解 , 即 A P = QR , 其中 P 是一个置换 矩阵 , 交换 A 的列并没有改变数据库 , 只是对文档向量进 收稿日期 : 2008 - 04 - 14 作者简介 : 李华云 (1969 - ) , 男 , 馆员 , 研究方向 : 图书情报 , 发表论文 10 余篇。 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 行重新排序 。为简单起见 , 仍然用 A 代替 A P。建设 RA 的 第 j 列为 Rj , 则 A 的第 j 列 aj = QArj , 于是得到提问式与文 档之间的余弦夹角公式为 : cosθj = ( QArj) Tq ‖QArj ‖2 ‖q ‖2 = rT j ( QT Aq) ‖rj ‖2 ‖q ‖2 (1 - 3) 若要得到 A 的 k 秩近似 Ak , 则让 R 的除了前 k 行以外 的其它元素都置为零 。 2 　SVD ( Singular Value Decomposition) 奇异值分解 在论述矩阵的奇异值与奇异值分解之前 , 先看下面的 结论和定理 : (1) 设 A ∈Cm ×n 其特征值均是非负数 ; r ( r > 0) , 则 AHA 是 Hermite 矩阵 , 且 rank ( AHA) = rank ( A) ; (2) (3) 设 A ∈Cm ×n r ( r > 0) , 则 A = 0 的充要条件是 AHA = 0。 ( r > 0) , 则 AHA 的特征值为 r …λr 1 　设 A ∈Cm ×n 定义 3 λ1 λ2 则称σi = λi ( i = 1 ,2 , …, n) 为 A 的奇异值 。 定理 3 λr + 1 = …=λn = 0 1 　设 A ∈Cm ×n r ( r > 0) , 则存在 m 阶酋矩阵 U 和 n 阶酋矩阵 V , 使得 UTAV = ∑ 0 其中 ∑ = diag (σ1 ,σ2 , …,σr) 0 0 矩阵 A 的全部非零奇异值 。 公式 2 - 1 可变换为 : (2 - 1) , 而σi ( i = 1 ,2 , …, r) 为 —322— ■ 情 报 纵 横 

Φ 其中 X′为 X 的转置矩阵 , Trace ( X′X) 等于 X′X 的对角 元素之和 , 对于一个 m ×m 正交矩阵 Y , 有 : ‖YX ‖F = Trace ( X′X) = ‖X ‖F Trace ( ( YX)′( YX) ) = Trace ( X′Y′YX) = (3 - 2) 类似的 , 对于 n ×n 正交矩阵 Z , 有 ‖XZ ‖F = ‖X ‖F 3 1 　F 范数对 QR 分解降秩的度量 原矩阵 A 在 QR 分解降秩后 , 即 R11 0 A = QR = Q R12 R22 R11 0 ≈ Q R12 0 = QARA 降秩前后 , 矩阵改变为 QR - QARA = Q = Q R11 0 0 0 R12 R22 0 R22 , 故 ‖QR - QARA ‖F = Q - Q R11 0 R12 0 0 0 0 R22 F = ‖R22 ‖F , 同 时 ‖A ‖F = ‖R ‖F , 计算原矩阵降秩后相比原矩阵的的改 变量公式为 : ‖QR - QARA ‖F ‖A ‖F = ‖R22 ‖F ‖R ‖F (3 - 3) 3 2 　F 范数对 SVD 分解降秩的度量 在 SVD 分解中 , A = U ∑V T ≈ Uk ∑kV T k = Ak , 改变 量可以通过以下公式计算 : 　 ‖A - Ak ‖F ‖A ‖F = = ‖A - X ‖F min rank ( X) ‖U ∑V T ‖F k r A ∑ λ2 j j = k+1 r A ∑ λ2 j j =1 = ‖∑- ∑k ‖∑‖F ‖F (3 - 4) 由此可以看出 , 在 SVD 奇异值分解后 , Ak 为 A 的惟一 一个秩为 k 的最小二乘意义上的近似矩阵 。由于将高维的 标引词 - 文本矩阵降维到 k , 远远小于系统所用的标引词 , 就可以忽视次要的词之间的区别 , 从而可以削弱多义词对 检索的影响 。下面 , 我们用实例来讨论 SVD 方法对于矩阵 降维的效果 。 4 　实例分析 我们选取超星电子图书馆中的《论文全文库》作为文 本数据来源 , 在该数据库中选出 9 篇具有代表性的文章 , 以此编制关键词表 (见表 1) , 模拟潜在语义分析 。 4 1 　原始数据及索引词抽取 2008 年 10 月 第 10 期 October 2008 No. 10 0 0 V T (2 - 2) A = U ∑ 0 称公式 2 - 2 为矩阵的奇异值分解 。 对词汇 ———文本矩阵 A 的 SVD 分解可以用以下公式表示 : A = U ∑AT (2 - 3) 其中 U 是 t ×t 的正交矩阵 , 它的每一列是 A 的左奇 异向量 , V 是 d ×d 正交矩阵 , 它的每一列是 A 的右奇异 向量 , ∑是 t ×d 对角矩阵 , 对角线元素是 A 的奇异值 , 按大小顺序排列 , 即λ1 λmin ( t , d) 。可以证明对任 … 意矩阵 , 这种分解都是存在的 。 λ2 对词 汇 ———文 本 矩 阵 A 进 行 奇 异 值 分 解 后 , 得 U 、 ∑、V T3 个矩阵 , ∑为对角矩阵 , 对角线元素为奇异值 。 每一词汇 、每篇文本都能根据分解结果 , 在一个几何空间 内 , 找到其相应的固定点 , 然后 , 可以依据其相互间距离之 远近来判断其相关程度之高低 , 词汇的空间位置由 U 而定 , 文本则由 V 而定 , 该空间就被称为 r 维潜在语义空间。 ■ 由于词汇和文本通常数量很多 , 不可避免得造成 “词 汇 ———文本”矩阵也十分庞大 , 因此在实际计算时 , 需要 在分解结果中作进一步简化 。取正整数 k , 0 < k < r , 在 ∑中 , 仅考虑其中值最大的 k 个元素 (即词汇文本相关 关系中最主要的部分) , 让 A 的除了前 k 个最大奇异值以外 的奇异值都置为零 。取 ∑中相应的 k 阶对角矩阵 、U 中 相应的 K 列 、V T 中相应的 k 行 , 最终得到新的 k 秩近似 Ak , 其中 Uk 是 U 的前 k 列形成的 t ×k 矩阵 , Vk 是 V 的前 k 列形成的 d ×k 矩阵 , ∑k 是 A 的 k 个最大奇异值形成的 k ×k 对角矩阵 , 得 A = U ∑V T ≈ Uk ∑kV T (2 - 4) Ak 即为经过优化降维后的语义结构 , Uk 为词汇矩阵 , k = Ak 情 报 纵 横 k 为文本矩阵 。 V T 文本 词 汇 A^ = U 　 ∑ k ×k 　 V T k k ×d t ×d t ×k 图 1 　词汇 ———文本矩阵的奇异值分解图示 　 3 　降秩估计的度量 ———罗贝尼乌斯( Frobenius)范数 罗贝尼乌斯 ( Frobenius) 范数 , 简称 F 范数 , 可作为 判定矩阵大小的依据 。对于 m ×n 矩阵 X , 其 F 范数为 : ‖X ‖F = Trace ( X′X) = Trace ( XX′) (3 - 1) 表 1 　中文样本的原始数据 文本标题 阿奇霉素粉针剂治疗呼吸道感染的临床疗效 安瑞克治疗小儿发烧的疗效观察 “肺炎”2 例 “求其属”浅议 加味止嗽散治疗喉源性咳嗽 120 例 中药外敷治疗颈椎病 当归补血汤加味治疗泌尿系统疾病临床研究 索引词 呼吸道感染、发热、高烧 感冒、发烧、感染 SARS、流感、感染 中药、咳嗽、气管 落枕、颈椎 当归、活血、造血 序号 d1 d2 d3 d4 d5 d6 —422— © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 

1 1 1 1 1 1 1 　续表 1 序号 d7 d8 d9 文本标题 论中医学人体之气的实质是新陈代谢 儿科复发呼吸道感染的免疫治疗 枕颌牵引针刺治疗颈椎病 40 例临床疗效观察 1 1 1 2008 年 10 月 第 10 期 October 2008 No. 10 索引词 代谢、解渴、感冒 咳嗽、呼吸道感染 颈椎、神经中枢 1 π 1 2 4 2 　词汇 ———文本矩阵的构建 文本数共为 9 , 索引词数共为 18。以词汇 ti 在文本 di 的摘要中出现频次数作为矩阵 X 元素 xij 的值得到矩阵 (见 表 2) 。 序号 索引词 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 t15 t16 t17 t18 呼吸道感染 发 　　热 高 　　烧 感 　　冒 感 　　染 SARS 流 　　感 中 　　药 咳 　　嗽 气 　　管 落 　　枕 颈 　　椎 当 　　归 活 　　血 造 　　血 代 　　谢 解 　　渴 神经中枢 表 2 　中文样本的“词汇 ———文本”矩阵 文 　　　　　本 d1 3 2 2 1 2 0 1 0 1 0 0 0 0 0 0 0 0 0 d2 0 2 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 d3 0 2 2 1 2 3 1 0 1 0 0 0 0 0 0 0 0 0 d4 2 0 1 0 0 0 1 3 3 2 0 0 0 0 0 0 0 0 d5 0 0 0 0 0 0 0 0 0 0 3 4 0 0 0 0 0 0 d6 0 0 0 0 0 0 0 0 0 0 0 0 4 3 2 0 0 0 ■ d7 1 0 0 2 0 0 0 0 0 0 0 0 0 0 0 2 2 0 d8 2 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 d9 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 4 3 　奇异值分解及降维效果分析 4 4 　结 　论 运用科学计算软件 MATLAB 中函数 svd 的运算 , 得分 2 节中公式 (3 - 4) 计算 F 解后的矩阵 : U , ∑, V 。根据 3 范数度量 SVD 降维的改变量得到如下结果 (见表 3) 。 表 3 　矩阵降维改变量 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7 k = 8 0 67466 0 65682 0 47012 0 35697 0 3228 0 15642 0 14916 利用 EXCEL 绘制成如下图 : 情 报 纵 横 从实验结果可以看出 , 随着 k 值增大 , 原始文本 ——— 词汇矩阵的改变量虽然减小 , 但是检出文本的范围被大大 缩小 , 并 且 其 相 似 度 系 数 的 数 值 也 有 变 动 。在 Michael Berry 等的《线性代数方法在信息智能检索中的运用》 W (Using Linear Algebra for Intelligent Information Retrieval) 一文 中 , 对西文样本的分析也表明了这一特性 。 但是 , 选择合适的 k 值是一个折中性的问题 。K 值取 小 , 则能忽略不重要的信息 , 但过小 , 即对原矩阵改变量 过大 , 则分辨能力反而不足 ; k 值取大 , 则能容纳所有现 实的结构信息 , 但过大 , 则消减了降维意义 , 即失去它确 定词间语义相关的能力 。 参 考 文 献 [1 ] Michael W Berry , Susan T Dumais , and Gavin W O Brien. Using Linear Algebra for Intelligent Information Retrieval [J ]. (37) : Society for Industrial and Applied Mathematics , 1995 , 573 - 595. [2 ] Michael W Berry , Zlatko Drmaˇc , Elizabeth R Jessup , Ma trices , Vector Spaces , and Information Retrieval [ C]. SIAM REVIEW 1999 Society for Industrial and Applied Mathematics Vol. 41 , No. 2 , pp. 335 - 362. 图 2 　词汇 ———文本矩阵降维维数和矩阵改变量图 　 [3 ] 何伟. LSI 潜在语义信息检索模型 [J ]. 数学的世间与 认识 , 2003 , 33 (9) : 1 - 10. © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net —522—