信息检索与数据挖掘 2019年4月9日 信息检索与数据挖掘 矩阵分解在信息检索中的应用
信息检索与数据挖掘 2019年4月9日 1 信息检索与数据挖掘 矩阵分解在信息检索中的应用
信息检索与数据挖掘 2019年4月9日 3 矩阵分解在信息检索中的应用 •矩阵分解及隐性语义索引 ·关于词项-文档矩阵 ·线性代数基础 ·矩阵分解与低秩逼近 ·R中的隐性语义索引 ·矩阵分解的计算机实现 •推荐系统 ·推荐系统的兴起 ·推荐系统的基本方法 。示例：UV分解用于音乐推荐
信息检索与数据挖掘 2019年4月9日 3 矩阵分解在信息检索中的应用 • 矩阵分解及隐性语义索引 • 关于词项-文档矩阵 • 线性代数基础 • 矩阵分解与低秩逼近 • IR中的隐性语义索引 • 矩阵分解的计算机实现 • 推荐系统 • 推荐系统的兴起 • 推荐系统的基本方法 • 示例：UV分解用于音乐推荐
信息检索与数据挖掘 2019年4月9日 4 词项-文档矩阵C→CCT C:MXW的词项-文档矩阵 CCT的物理意义？ 习题18-4合 6*5 C=01 (18-12) 10 为某个文档集上的词项-文档出现矩阵，计算词项的共现矩阵CC。当C是一个词项-文档出现 掌 屋 喜 矩阵时，CC对角线上的元素是什么？ OC6SI AOAg&G CCT方阵，其每行和每列都对应M个词项中的一个。CCT 的第i行、第列的元素是词项i和词项共现的文档数目。 只 C5*6 6 o d d2 d3 da ds de 品 o o O ship 1 0 1 0 0 0 boat 0 1 0 0 0 0 匠 ocean 1 1 0 0 0 0 品 o voyage 1 0 0 1 1 0 trip 0 0 0 1 0 1 哈
信息检索与数据挖掘 2019年4月9日 4 词项-文档矩阵C→CCT • C ：M×N 的词项-文档矩阵 • CCT 的物理意义？ CCT 方阵，其每行和每列都对应M个词项中的一个。CCT 的第i 行、第j 列的元素是词项i 和词项j 共现的文档数目。 C5*6 CT 6*5
信息检索与数据挖掘 2019年4月9日 5 词项-文档矩阵C→CC 习题18-6 假定C是词项-文档出现矩阵，那么CC的元素的含义是什么？ C:MXN的词项-文档矩阵 CTC的物理意义？ CT *5 CC是方阵，其每行和每列都对应N个文档中的一 掌 OC69I AOAg&G 个。CCT的矩阵中的第i行、第j列的元素实际上 是第i个文档与第j个文档含有相同词项的数目。 只 民 C5*6 品 d d2 d3 da ds d6 ship 1 0 1 0 0 0 经 boat 0 1 0 0 0 0 吊 ocean 1 1 0 0 0 0 voyage 1 0 0 1 1 0 trip 0 0 0 1 0
信息检索与数据挖掘 2019年4月9日 5 词项-文档矩阵C→CTC • C ：M×N 的词项-文档矩阵 • CTC的物理意义？ CTC是方阵，其每行和每列都对应N个文档中的一 个。 CCT 的矩阵中的第i 行、第j 列的元素实际上 是第i 个文档与第j 个文档含有相同词项的数目。 C5*6 CT 6*5
信息检索与数据挖掘 2019年4月9日 6 词项-文档计数(f矩阵C→CCT、CTC 词项-文档权重(fidD矩阵C→CCT、CTC 。物理意义？ ·A:是词项在不同文档中出现次数的平方和 ·A是词项和词项j共现时f*tf的累计 习题18-7合 021 C= 0 3 (18-14) 上式为一个词项-文档矩阵，其中每个元素都是词项频率，因此词项1在文档2中出现2次，而 在文档3中出现1次。计算Cc,并找出两个词项的最高词频都出现在同一文档时所对应的元素。 CCT各元素体现了词项和词项之间的关联程度 CTC各元素体现了文档和文档之间的关联程度
信息检索与数据挖掘 2019年4月9日 6 词项-文档计数(tf)矩阵C→CCT 、CTC 词项-文档权重(tf-idf)矩阵C→ CCT 、 CTC • 物理意义？ • Aii是词项i在不同文档中出现次数的平方和 • Aij是词项i和词项j共现时tfi*tfj的累计 CCT各元素体现了词项和词项之间的关联程度 CTC各元素体现了文档和文档之间的关联程度
信息检索与数据挖掘 2019年4月9日 7 小结：词项-文档矩阵 ·C:MXN的词项-文档矩阵 。C的每一列即为向量空间模型中的一个向量 。文档和查询均表示为向量，相关度为向量的“距离” ·A=CTC ·A是词项i和词项i共现的文档数目 ·A=CCT ·A,是第i个文档与第个文档含有相同词项的数目 ·词项-文档计数(f矩阵C→CCT、CTC ·词项-文档权重(fidf矩阵C→CCT、CTC
信息检索与数据挖掘 2019年4月9日 7 小结：词项-文档矩阵 • C ：M×N 的词项-文档矩阵 • C的每一列即为向量空间模型中的一个向量 • 文档和查询均表示为向量，相关度为向量的“距离” • A=CTC • Aij是词项i 和词项j 共现的文档数目 • A=CCT • Aij是第i 个文档与第j 个文档含有相同词项的数目 • 词项-文档计数(tf)矩阵C→CCT 、CTC • 词项-文档权重(tf-idf)矩阵C→ CCT 、 CTC
信息检索与数据挖掘 2019年4月9日 9 矩阵分解在信息检索中的应用 •矩阵分解及隐性语义索引 。关于词项-文档矩阵 ·线性代数基础 ·矩阵分解与低秩逼近 ·R中的隐性语义索引 ·矩阵分解的计算机实现 •推荐系统 ·推荐系统的兴起 ·推荐系统的基本方法 。示例：UV分解用于音乐推荐
信息检索与数据挖掘 2019年4月9日 9 矩阵分解在信息检索中的应用 • 矩阵分解及隐性语义索引 • 关于词项-文档矩阵 • 线性代数基础 • 矩阵分解与低秩逼近 • IR中的隐性语义索引 • 矩阵分解的计算机实现 • 推荐系统 • 推荐系统的兴起 • 推荐系统的基本方法 • 示例：UV分解用于音乐推荐
信息检索与数据挖掘 2019年4月9日 10 线性代数基础 特征值与特征向量 令C为一个M×N的矩阵，其中的每个元素都是非负实数。矩阵 的秩(rank)是线性无关的行（或列）的数目，因此有rank(C)s min{M,N。一个非对角线上元素均为零的r×r方阵被称为对角 阵(diagonal matriⅸ)，它的秩等于其对角线上非零元素的个数 。如果上述对角阵上的r个元素都是1，则称之为r维单位矩阵( identity matrix),记为o 对于MXM的方阵C及非零向量元，满足Cx=λ龙的)被称为矩 阵C的特征值(eigenvalues)。C的非零特征值的个数最多是 rank(C)。对于特征值)，满足C元=入的M维非零向量元称为其右 特征向量(right eigenvector)。对应最大特征值的特征向量被称 为主特征向量(principal eigenvector)。同样，矩阵C的左特征 向量(left eigenvectors)是满足rC=r式的M维向量)
信息检索与数据挖掘 2019年4月9日 10 线性代数基础 特征值与特征向量 令C 为一个M×N 的矩阵，其中的每个元素都是非负实数。矩阵 的秩（rank）是线性无关的行（或列）的数目，因此有rank(C)≤ min{M,N}。一个非对角线上元素均为零的r×r 方阵被称为对角 阵（diagonal matrix），它的秩等于其对角线上非零元素的个数 。如果上述对角阵上的r 个元素都是1，则称之为r 维单位矩阵（ identity matrix），记为Ir。 对于M×M的方阵C 及非零向量𝑥റ ，满足C𝑥റ = λ𝑥റ 的λ 被称为矩 阵C 的特征值（eigenvalues）。C 的非零特征值的个数最多是 rank(C)。对于特征值λ，满足C𝑥റ = λ𝑥റ的M维非零向量𝑥റ 称为其右 特征向量（right eigenvector）。对应最大特征值的特征向量被称 为主特征向量（principal eigenvector）。同样，矩阵C 的左特征 向量（left eigenvectors）是满足𝑦റ 𝑇C = λ𝑦റ 𝑇 式的M维向量𝑦റ
信息检索与数据挖掘 2019年4月9日 11 线性代数基础 求解特征值 等式C元=λx可以改写成(C-λM)元=0，这个等式称为特征方 程(characteristic equation),可以通过求解这个方程来得到矩 阵的特征值。因此，C的特征值也就是方程I(C-IM)川=0的 解，其中S表示的是方阵S的行列式(determinant) 。 I(C-λIM)川=0是一个以为变量的M阶多项式方程，因此它 最多有M个根，这些根也就是矩阵C的特征值。即使C中所有 元素都是实数，那么这些特征值通常也有可能是复数。 对于对称(symmetric)矩阵S,不同特征值所对应的特征向量 之间是正交的(orthogonal)。另外，如果S是实对称矩阵，那 么所有特征值也都是实数
信息检索与数据挖掘 2019年4月9日 11 线性代数基础 求解特征值 等式C𝑥റ = λ𝑥റ可以改写成 C − 𝜆𝐼𝑀 𝑥റ = 0，这个等式称为特征方 程（characteristic equation），可以通过求解这个方程来得到矩 阵的特征值。因此，C的特征值也就是方程 (C − 𝜆𝐼𝑀) = 0 的 解，其中|S|表示的是方阵S 的行列式（determinant）。 (C − 𝜆𝐼𝑀) = 0 是一个以λ为变量的M阶多项式方程，因此它 最多有M个根，这些根也就是矩阵C 的特征值。即使C 中所有 元素都是实数，那么这些特征值通常也有可能是复数。 对于对称（symmetric）矩阵S，不同特征值所对应的特征向量 之间是正交的（orthogonal）。另外，如果S 是实对称矩阵，那 么所有特征值也都是实数
信息检索与数据挖掘 2019年4月9日 12 线性代数基础 向量可表征为特征向量的线性组合 30 考虑矩阵S= 0 20 0, 很明显，矩阵的秩是3，并且具 1 有3个非零特征值入=30、)2=20及入3=1，它们对应的特征向量 分别是：x= -0s-9 现考虑任意一个向量，如)= 总是可以将表示成$的三 6 个特征向量的线性组合，如本例：方= 4 =2x1+4x2+6x3 6
信息检索与数据挖掘 2019年4月9日 12 线性代数基础 向量可表征为特征向量的线性组合 考虑矩阵S = 30 0 0 0 20 0 0 0 1 ，很明显，矩阵的秩是3，并且具 有3 个非零特征值 λ1=30、λ2=20 及λ3=1，它们对应的特征向量 分别是：𝑥1 = 1 0 0 , 𝑥2 = 0 1 0 , 𝑥3 = 0 0 1 。 现考虑任意一个向量，如𝑣റ = 2 4 6 ，总是可以将𝑣റ表示成S 的三 个特征向量的线性组合，如本例：𝑣റ = 2 4 6 = 2𝑥1+4𝑥2 + 6𝑥3