lecture18-lsi 信息检索导论 王斌 PPT 公开课一等奖省优质课大赛获奖课件

第18讲隐性语义索引LatentSemanticIndexing1/11/27提要2上一讲回顾隐性语义索引

空间降维处理LSI在IR中应用提要3上一讲回顾隐性语义索引

空间降维处理LSI在IR中应用4层次聚类层次聚类目标是生成类似于前面提到Reuters目录一个层次结构：这个层次结构是自动创建，能够经过自顶向下或自底向上方法来实现。最著名自底向上方法是层次凝聚式聚类(hierarchicalagglomerativeclustering，HAC)。45

单连接:最大相同度(最短距离)

56

全连接:最小相同度67质心法78组平均89四种HAC算法比较9方法 结合相同度时间复杂度是否最优?注释单连接簇间文档最大相同度Ɵ(N2)yes链化效应全连接簇间文档最小相同度Ɵ(N2logN)no对离群点敏感组平均全部文档相同度平均值Ɵ(N2logN)no大部分应用中最正确选择质心法全部簇间相同度平均值Ɵ(N2logN)no相同度颠倒10

簇标签生成例子10文档数目

簇标签生成方法质心互信息标题4622oilplantmexicoproductioncrudepower000refinerygasbpdplantoilproductionbarrelscrudebpdmexicodollycapacitypetroleumMEXICO:HurricaneDollyheadsforMexicocoast91017policesecurityrussianpeoplemilitarypeacekilledtoldgroznycourtpolicekilledmilitarysecuritypeacetoldtroopsforcesrebelspeopleRUSSIA:Russia’sLebedmeetsrebelchiefinChechnya10125900000tonnestradersfutureswheatpricescentsseptembertonnedeliverytradersfuturestonnetonnesdeskwheatprices00000USA:ExportBusiness-Grain/oilseedscomplex三种方法：选择质心向量中突出词项，使用MI差异式标签，使用离质心最近文档标题三种方法结果都不错11本讲内容矩阵SVD分解隐性语义索引LSI(LatentSemanticIndexing)LSI在IR中应用11提要12上一讲回顾隐性语义索引

空间降维处理LSI在IR中应用13回顾一下词项-文档矩阵该矩阵是计算文档和查询相同度基础，接下来我们要介绍，能否经过对该矩阵进行转换来取得文档和查询之间一个更加好相同度计算方法？13AnthonyandCleopatraJuliusCaesarTheTempestHamletOthelloMacbethanthony5.253.180.00.00.00.35brutus1.216.100.01.00.00.0caesar8.592.540.01.510.250.0calpurnia0.01.540.00.00.00.0cleopatra2.850.00.00.00.00.0mercy1.510.01.900.125.250.88worser1.370.00.114.150.251.95...14隐性语义索引LSI介绍我们将词项-文档矩阵转换成多个矩阵乘积这里我们使用是一个特定分解方法：奇异值分解(singularvaluedecomposition

，简称SVD)SVD:C=UΣV

T(其中

C=词项-文档矩阵)利用SVD分解结果我们来结构一个新、改进词项-文档矩阵

C′经过C′我们能够得到一个更加好相同度计算方法(相对于

C而言)为了这种目标使用SVD被称为隐性语义索引(latentsemanticindexing)或者简称

LSI。1415例子C=UΣVT:矩阵C

上面给出了一个标准词项-文档矩阵，为简单起见，这里使用了布尔矩阵。1516例子C=UΣVT:矩阵U

每个词项对应一行，每个min(M,N)对应一列，其中M为词项数目，N是文档数目。

这是个正交矩阵：列向量都是单位向量；

任意两个列向量之间都是相互正交。能够想象这些列向量分别代表不一样“语义”维度，比如政治、体育、经济等主题。矩阵元素

uij

给出是词项i和第j个“语义”维度之间关系强弱程度。1617例子C=UΣVT:矩阵

Σ这是个min(M,N)×min(M,N)对角方阵。对角线上是矩阵C奇异值。奇异值大小度量是对应“语义”维度主要性。我们能够经过忽略较小值来忽略对应“语义”维度1718例子C=UΣVT:矩阵VT每篇文档对应一列，每min(M,N)对应一行。一样，这也是一个正交矩阵：(i)每个行向量都是单位向量；(ii)任意两个行向量之间都是正交；一样每个行向量代表是一个语义维度，矩阵元素vij

代表是文档

i

和语义维度j关系强弱程度1819例子C=UΣVT:全部四个矩阵1920LSI:小结词项-文档矩阵能够分解成3个矩阵乘积词项矩阵U–每个词项对应其中一个行向量文档矩阵

VT–每篇文档对应其中一个列向量奇异值矩阵

Σ–对角方阵，对角线上奇异值代表是每个“语义”维度主要性接下来我们要介绍这么做原因。20提要21上一讲回顾隐性语义索引

空间降维处理LSI在IR中应用22为何在LSI中使用SVD分解最关键性质：每个奇异值对应是每个“语义”维度权重将不太主要权重置为0，能够保留主要信息，去掉一些信息“枝节”这些“枝节”可能是：噪音–这种情况下，简化LSI噪音更少，是一个更加好表示方法枝节信息可能会使原来应该相同对象不相同，一样简化LSI因为其能更加好地表示相同度，因而是一个更优表示方式“细节越少越好”一个类比鲜红色花朵图像红黑花朵图像假如忽略颜色，将更轻易看到二者相同性2223将空间维度降为2实际上，我们只需将矩阵Σ中对应维度置为0即可。此时，相当于矩阵U和VT

对应维度被忽略，然后计算C2=UΣ2VT.2324维度降为22425回顾原始未分解矩阵

C=UΣVT2526原始矩阵

Cvs.简化矩阵

C2=UΣ2VTC2

能够看成矩阵C一个二维表示。我们将表示维度缩减至2维。2627为何新低维空间更加好？27在原始空间中，d2和d3相同度为0；不过在新空间下，

d2和d3相同度为：0.52*0.28+0.36*0.16+0.72*0.36+0.12*0.20+-0.39*-0.08≈0.5228为何新低维空间更加好？28“boat”和“ship”语义上相同。低维空间能够反应出这一点。SVD什么性质会造成相同度计算有所提升？提要29上一讲回顾隐性语义索引

空间降维处理LSI在IR中应用30LSI在IR中使用原因LSI能够发觉文档语义上关联......不过在原始向量空间中这些文档相同度不大(因为它们使用不一样词语)......于是经过LSI能够将它们映射到新低维向量空间中......在新空间下，二者相同度较高所以，LSI能够处理一义多词(synonymy)和语义关联问题在标准向量空间下，同义词对文档相同度计算没有任何贡献LSI所期望效果：同义词对文档相同度贡献很大3031LSI是怎样处理一义多词和语义关联问题降维迫使我们忽略大量“细节”我们将原始空间下不一样词映射到低维空间同一维中将同义词映射到同一维“开销”远小于无关词聚集SVD选择开销最小映射方法所以，SVD会将同义词映射到同一维不过，它同时能防止将无关词映射到同一维3132LSI与其它方法比较假如查询和文档没有公共词项时，前面我们介绍相关反馈和查询扩展能够用于提升IR召回率LSI会提升召回率不过损害正确率所以，它和相关反馈查询扩展处理是同一问题......一样它们缺点也一致3233

LSI实现对词项-文档矩阵进行SVD分解计算在新低维空间下文档表示将查询映射到低维空间中上述公式来自：计算

q2

和V2中全部文档表示相同度像以往一样按摄影同度高低输出文档结果课堂练习：上述做法最基本问题是什么？3334

最优性SVD在下面意义上说是最优：保留

k

个最大奇异值并将其它奇异值置为0，这种做法得到是原始矩阵C最正确迫近(参考Eckart-Young定理