内容无关的信息检索模型

内容无关的信息检索模型杜小勇2008-03-13•基于文本内容的检索模型–布尔模型–向量空间模型–概率模型–统计语言模型–语义网络模型•与内容无关的其他检索模型–基于协同的模型–基于链接分析的模型–基于关联的模型•通常与基于内容的模型一起使用CollaborativeRecommendation•rajdenotesthescoreofitemjratedbyanactiveusera.Ifuserahadnotrateditemj,raj=0.•m-totalnumberofusers,n-totalnumberofitems.nmmnmjmanajanjnmrrrrrrrrrR111111协同推荐模型•Foragivenuser-aanddocument-j,Predicatepaj=?•isthenumberofuserswhoaresimilartouseraandhaverateditemj.•w(a,i):Theweightofthesimilaritybetweenuseraanduseri.•kisanormalizingfactorsuchthattheabsolutevaluesoftheweightssumtounity.amiiijaajrriawkrp1))(,(am算法主要的问题•冷启动(coldstar)•稀疏性(sparse)•高维性(highdimension)基于分类的协同过滤推荐基本思想：（1）对矩阵进行划分划分依据资源的语义分类（2）根据划分后的子矩阵进行协同过滤（3）生成预测结果基于分类的协同过滤推荐基本思想：（1）把每一项资源归到一个或几个类别中；（2）用户对资源评价矩阵进行分解，iiiniiininmmvmvvvinmmnmnddddDddddD11211111iiniivvviGenre,,,][21（3）对进行裁减，去掉对该类资源没有打分的用户iD基于分类的协同过滤算法(续)（4）根据计算用户在某一类别中的相似度，即得到一个用户的最邻近邻居们。（5）计算用户对特定类别中的资源感兴趣度（6）综合用户在多个类别中的感兴趣程度，得到最终推荐结果。iiiiniimiiimiiniiinmvuvuvuvuiiddddDD1111''iD基于聚类的协同过滤算法基本思想：（1）对矩阵进行划分划分根据稀疏矩阵聚类、KMeans等聚类算法（2）根据划分后的子矩阵进行协同过滤（3）生成预测结果基于矩阵聚类的协同过滤资源用户12345678111100000211010000301110000410110000500000111600000110700110011800111111900101000经过(1,0)转换后的评分矩阵（划分前）资源用户123411110211013011141011资源用户6785111611070118111资源用户345711081119101划分后的矩阵基于矩阵聚类的协同过滤基本思想：（1）把每一项资源归到一个或多个子矩阵中，每个用户被划分到一个或多个子矩阵中；iiiiniimiiimiiniiinmvuvuvuvuiiddddDD1111'基于聚类的协同过滤算法(续)（2）根据计算用户在某一类别中的相似度，即得到一个用户的最邻近邻居们。（3）计算用户对特定类别中的资源感兴趣度（4）综合用户在多个类别中的感兴趣程度，得到最终推荐结果。'iD•与内容无关的其他检索模型–基于协同的模型–基于链接分析的模型–基于关联的模型•通常与基于内容的模型一起使用链接分析模型•对于超文本（例如上的网页），超链结构是个非常丰富和重要的资源，如果能够充分利用的话，可以极大地提高检索结果的质量。•SergeyBrin和LarryPage在1998年提出了PageRank算法•J.Kleinberg于1998年提出了HITS算法•其它一些学者也相继提出了另外的链接分析算法，如SALSA，PHITS，Bayesian等算法。PageRanking算法•BrinS,PageLTheanatomyofalarge-scalehypertextualwebsearchengine.’98•基本思想：以下三条启发式规则：–如果一个页面被多次引用，那么这个页面很可能是重要的。–如果一个页面被重要的页面引用，那么这个页面很可能是重要的。–一个页面的重要性被均分并传递到它所引用的页面。PageRanking•Citationgraph(linkgraph)oftheweb•Awebpage’s“PageRank”:PR(A)=(1-d)+d(PR(T1)/C(T1)+…+PR(Tn)/C(Tn))•PageAhaspagesT1,…,Tnwhichpointtoit(i.e.arecitations)•0d1isadampingfactor(d=0.85)•C(A)isthenumberoflinksgoingoutofAHITS算法•J.Kleinberg.Authoritativesourcesinahyperlinkedenvironment.InProc.NinthAnn.ACM-SIAMSymp.DiscreteAlgorithms,pages668-677,ACMPress,NewYork,1998•Hub页面：指向权威页面的页面，例如目录页面等。•Authority页面：被很多页面指向的页面HITS算法•Step1:构造子图S–查询结果页面R（前n个）–R中每一个页面所指向的页面–指向R中页面的页面（可能要限制数量）•Step2:迭代计算页面的h值和a值–每一个页面的h(p)=1,a(p)=1–定义两个操作：I:a(p)=∑(q,p)∈Eh(q)O:h(p)=∑(p,q)∈Ea(q)HITS算法（续）•Step3：重复Step2k次（可以证明上述迭代可以收敛到一个不动点，但是，如何确定一个k值是一个问题）输出top-m个hub页面和权威页面•与内容无关的其他检索模型–基于协同的模型–基于链接分析的模型–基于关联的模型•通常与基于内容的模型一起使用SimRank算法•基本思想：同一个类型下的两个对象,如果经常连接到相同的其他对象，那么这两个对象的相似性应该很高。Simrank算法•Similaritybtw.a&bdenotedby:–ifa=b,s(a,b)=1,s(a,a)=s(b,b)=1–otherwise:•Ciscalledas“confidencelevel”or“decayfactor”.aconstantbtw.0&1•if|I(a)|or|I(b)|is0,s(a,b)=0•symmetric:s(a,b)=s(b,a)–Similaritybtw.a&bistheaveragesimilaritybtw.in-neighborsofaandin-neighborsofb)(1)(1))(),(()()(),(bIjjiaIibIaIsbIaICbasSimrank算法----文本相似度计算•1.利用文章的相互之间的引用关系计算文本的相似度。----两个文档的引文相同，那么这两个文档的相似性很高。•2.利用文章的内部信息和外部信息共同的计算文本的相似度。---文档外部信息（作者，发表会议）---文档内部信息（摘要，关键字，内容）思想：两个文档有共同的作者，共同的关键词，发表到共同的会议上，文章内容中包含共同的词那么这两个文档的相似度很高。Simrank算法计算改进工作Linkclus算法：1）2/8原则：图中两个点的相似性的计算只由图中的部分点来决定，并不是由图中的所有的点来决定。由这个核心的想法，将SimRank的全局计算转化到一个局部的树形的计算中来，大大提高了效率。参考文献LinkMing:[1]LiseGetoor,ChristopherP.Diehl,LinkMining:ASurvey,SIGKDD,2005[2]TedE.Senator*LinkMiningApplications:ProgressandChallenges,SIGKDD,2005[3]LiseGetoor,Linkmining:anewdataminingchallenge,SIGKDD,2003SimilarityCompute:[1]GlenJeh,JenniferWidom,SimRank:AMeasureofStructural-ContextSimilarity,SIGKDD,2002[2]JimengSun,HuimingQu,DeepayanChakrabarti,ChristosFaloutsosRelevanceSearchandAnomalyDetectioninBipartiteGraphs,SIGKDD,2005[3]XiaoxinYin,JiaweiHan,PhilipS.Yu,LinkClus:EfficientClusteringviaHeterogeneousSemanticLinks,VLDB,2006[4]XiaoxinYin,JiaweiHanDistinguishingObjectswithIdenticalNamesinRelationalDatabases,ICDE,2007[5]ZhenjiangLin,IrwinKing,andMichaelR.Lyu,PageSim:ANovelLink-basedSimilarityMeasurefortheWorldWideWeb,