内容无关的信息检索模型.ppt

内容无关的信息检索模型,杜小勇 2008-03-13,基于文本内容的检索模型 布尔模型 向量空间模型 概率模型 统计语言模型 语义网络模型,与内容无关的其他检索模型 基于协同的模型 基于链接分析的模型 基于关联的模型 通常与基于内容的模型一起使用,Collaborative Recommendation,raj denotes the score of item j rated by an active user a. If user a had not rated item j, raj=0. m - total number of users, n - total number of items.,协同推荐模型,For a given user-a and document-j, Predicate paj =? is the number of users who are similar to user a and have rated item j. w(a,i): The weight of the similarity between user a and user i. k is a normalizing factor such that the absolute values of the weights sum to unity.,算法主要的问题,冷启动(cold star) 稀疏性(sparse) 高维性(high dimension),基于分类的协同过滤推荐,基本思想： （1）对矩阵进行划分 划分依据资源的语义分类 （2）根据划分后的子矩阵进行协同过滤 （3）生成预测结果,基于分类的协同过滤推荐,基本思想： （1）把每一项资源归到一个或几个类别中； （2）用户对资源评价矩阵进行分解，,（3）对 进行裁减，去掉对该类资源没有打分的用户,基于分类的协同过滤算法(续),（4）根据 计算用户在某一类别中的相似度，即得到一个用户的最邻近邻居们。 （5）计算用户对特定类别中的资源感兴趣度 （6）综合用户在多个类别中的感兴趣程度，得到最终推荐结果。,基于聚类的协同过滤算法,基本思想： （1）对矩阵进行划分 划分根据稀疏矩阵聚类、KMeans等聚类算法 （2）根据划分后的子矩阵进行协同过滤 （3）生成预测结果,基于矩阵聚类的协同过滤,基于矩阵聚类的协同过滤,基本思想： （1）把每一项资源归到一个或多个子矩阵中，每个用户被划分到一个或多个子矩阵中；,基于聚类的协同过滤算法(续),（2）根据 计算用户在某一类别中的相似度，即得到一个用户的最邻近邻居们。 （3）计算用户对特定类别中的资源感兴趣度 （4）综合用户在多个类别中的感兴趣程度，得到最终推荐结果。,与内容无关的其他检索模型 基于协同的模型 基于链接分析的模型 基于关联的模型 通常与基于内容的模型一起使用,链接分析模型,对于超文本（例如WWW上的网页 ），超链结构是个非常丰富和重要的资源，如果能够充分利用的话，可以极大地提高检索结果的质量。 Sergey Brin 和Larry Page 在1998 年提出了PageRank 算法 J.Kleinberg 于1998年提出了HITS 算法 其它一些学者也相继提出了另外的链接分析算法，如SALSA，PHITS，Bayesian等算法。,Page Ranking算法,Brin S, Page L The anatomy of a large-scale hypertextual web search engine. WWW98 基本思想：以下三条启发式规则： 如果一个页面被多次引用，那么这个页面很可能是重要的。 如果一个页面被重要的页面引用，那么这个页面很可能是重要的。 一个页面的重要性被均分并传递到它所引用的页面。,PageRanking,Citation graph (link graph) of the web A web pages “PageRank”: PR(A)=(1-d)+d(PR(T1)/C(T1)+PR(Tn)/C(Tn) Page A has pages T1,Tn which point to it (i.e. are citations) 0d1 is a damping factor (d=0.85) C(A) is the number of links going out of A,HITS算法,J. Kleinberg. Authoritative sources in a hyperlinked environment. In Proc. Ninth Ann. ACM-SIAM Symp. Discrete Algorithms, pages 668-677, ACM Press, New York, 1998 Hub页面：指向权威页面的页面，例如目录页面等。 Authority页面：被很多页面指向的页面,HITS算法,Step1: 构造子图S 查询结果页面R（前n个） R中每一个页面所指向的页面 指向R中页面的页面（可能要限制数量） Step2:迭代计算页面的h值和a值 每一个页面的 h(p)=1,a(p)=1 定义两个操作： I: a(p) = (q,p) E h(q) O: h(p) = (p,q) E a(q),HITS算法（续）,Step3：重复Step2 k次（可以证明上述迭代可以收敛到一个不动点，但是，如何确定一个k值是一个问题）输出top-m个hub页面和权威页面,与内容无关的其他检索模型 基于协同的模型 基于链接分析的模型 基于关联的模型 通常与基于内容的模型一起使用,SimRank算法,基本思想： 同一个类型下的两个对象,如果经常连接到相同的其他对象，那么这两个对象的相似性应该很高。,Simrank算法,Similarity btw. a & b denoted by: if a = b, s(a,b) = 1, s(a,a) = s(b,b) = 1 otherwise: C is called as “confidence level” or “decay factor”. a constant btw. 0 & 1 if |I(a)| or |I(b)| is 0, s(a,b) = 0 symmetric : s(a,b) = s(b,a) Similarity btw. a & b is the average similarity btw. in-neighbors of a and in-neighbors of b,Simrank算法-文本相似度计算,1.利用文章的相互之间的引用关系计算文本的相似度。 -两个文档的引文相同，那么这两个文档的相似性很高。 2.利用文章的内部信息和外部信息共同的计算文本的相似度。 -文档外部信息（作者，发表会议） -文档内部信息（摘要，关键字，内容） 思想：两个文档有共同的作者，共同的关键词，发表到共同的会议上，文章内容中包含共同的词那么这两个文档的相似度很高。,Simrank算法计算改进工作,Linkclus算法： 1）2/8原则： 图中两个点的相似性的计算只由图中的部分点来决定，并不是由图中的所有的点来决定。 由这个核心的想法，将SimRank的全局计算转化到一个局部的树形的计算中来，大大提高了效率。,参考文献,LinkMing: 1 Lise Getoor, Christopher P. Diehl, Link Mining: A Survey, SIGKDD, 2005 2 Ted E. Senator* Link Mining Applications: Progress and Challenges, SIGKDD, 2005 3 Lise Getoor, Link mining: a new data mining challenge , SIGKDD, 2003 Similarity Compute: 1 Glen Jeh, Jennifer Widom, SimRank: A Measure of Structural-Context Similarity, SIGKDD, 2002 2 Jimeng Sun, Huiming Qu, Deepayan Chakrabarti, Christos Faloutsos Relevance Search and Anomaly Detection in Bipartite Graphs, SIGKDD, 2005 3 Xiaoxin Yin, Jiawei Han, Philip S. Yu,LinkClus: Efficient Clustering via Heterogeneous Semantic Links, VLDB, 2006 4 Xiaoxin Yin, Jiawei Han Distinguishing Ob