网络信息体系结构总结

1、Web 图与 Crawling Web Graph的性质 大小，连接性，结构 Size = Sa/( nO/nb) 200 million nodes & 1.5 billion links Some parts un reachable, Others have long paths found Bow-tie Structure Power law network （scale-free network） 重尾分布（heavy tail，长尾）是：度大的节点（网页）概率小，但很多，并 不能忽略。 对数尺度下为一斜线 Small world network Diameter of graph

2、 is small （log N） as compared to overall size Empirical study of Web-graph reveals small-world property d = 0.35 + 2.06 log （n） 高性能搜集系统 DNS resolve bottleneck 搜索引擎中可以设计一个专用的DN模块，含有 1、用于地址解析的DNSslient （和本模块的DNSS存服务器打交道）: 专门对付多个请求的并发处理，容许一次发出多个解析请求，通 过polling来看请求的完成情况 协助在多个DNS server之间做负载分配（例如根据掌握的URL

3、S行适当调度） 2、缓存 server : 大缓存容量，跨DN系统的刷新保持内容 3、预取 client 用不着等待解析的完成 Fetch bottleneck 多个并发的抓取 1、用多线程 / 多进程 2、用异步 I/O: 带事件处理的非阻塞 sockets Politeness DoS、 robots.txt 在“利用访问的局部性 ”和 “对网站的礼貌性 ”之间求得平衡 Duplicate detection 对UR进行规格化 MD摘要检测重复的网页 信息检索 信息检索模型 信息检索研究和解决哪一类问题？ Representation Storage Organization Access

4、 of information items for people who are interesting in them 检索模型包括几个方面内容？ D: 文档集的机内表示 Q: 用户需求的机内表示 F: 文档表示、查询表示和它们之间的关系的模型框架 R(qi, dj): query qi和 document dj 间的 relevance 计算函数 三种经典检索模型看待检索问题的角度有何异同？ 1、布尔模型 每个索引词在一篇文档中只有两种状态：出现或不出现，对应权值为0 或1。 查询是由三种布尔逻辑运算符 and, or, not 连接索引词组成的布尔表达式 2、向量空间模型 文档表示D：文

5、档用词向量表示：词典 刀=k1,k2,kt构成一个线性空间， d=为此空间内的向量 wi称为权值，表示对应词项 ki对于表达文档d的重要程度 查询表示与D相似：q=，查询可以是一个文档 Idf=lg(N/ni) 3、经典概率模型 信息获取看成是一个过程：用户提交一个查询，系统提供给用户它所认为的 相关结果列表；用户考察这个集合后给出一些辅助信息，系统再进一步根 据这辅助信息 (加上以前的信息) 得到一个新的相关结果列表； 如此继续。 VSM 向量空间模型 概率模型 文档表示：同向量模型： 查询表示：同向量模型： R(q i ,d j )的计算：也用Sim(q i ,d j)表示，它的思想是用先

6、验值来计算后验值， 具体的解释如下： 进行独立性假设：词语在文档或查询中的出现是独立的。 对于q存在一个相关子集R(R是 D的子集) 随机从D中取出一个d,它属于R的概率是多少P( R|d)，它不属于R的概率是多 少P ( R的补集|d) Sim(qi ,dj )用 P ( R|d)/ P ( R 的补集 |d )来表示，Sim(q i ,d j)越大，则认 为d与q越相关。其中P ( R|d)/ P ( R的补集|d )的计算利用了先验值， 也即利用系统中已知的相关子集中字典中的词出现的概率。 逐步求精过程(leehoom) 第1 步：P(ki|R) = 0.5，P(ki,R 的补)=ni/

7、N 其中N = |D| ，ni表示D中含有ki的文档个数 第2步：根据lisy前面总结的公式计算出前r个文档，记为V,Vi为V中含有ki 的文档组成的 集合。P(ki|R) 约等于P(ki|V) 约等于|Vi|/|V|，P(ki|R的补)约等于 P(ki,D-V) f约 2PR 等于(ni - |Vi|)/(N - ljV|) R 第3步：重复迭代过程2 信息检索系统评估 检索系统性能如何评测？ 一般用什么样的评测指标？ 对某个测试参考集，信息查询实例为I，I对应的相关文档集合为 R。假设 用某个检索策略对I进行处理后，得到一个结果集合 A。令Ra表示R与 A的交 集。 查全率(Recall)

8、:检出的相关文档个数与相关文档集合总数的比值，即 R=|Ra| / |R| 查准率(Precision):检出的相关文档个数与检出文档总数的比值，即 P=|Ra| / |A| 测试集 文档集、信息查询的实例，实例对应的相关文档 评估指标P,R,F F指数=2PR/(P+R) 信息提取 信息提取处理的问题是？ 信息提取是通过分析非结构化文本，提取预先定义好的实体、关系或事件， 把非结构化的文本转化为结构化的信息库 Wrapper是？如何构造？为什么要做 Wrapper Induction ？ Lear ning wrappers is wrapper in duct ion Sometimes,

9、 the relati onsare structural. Webpages gen erated by a database. Tables, lists, etc. Cantcomputers automatically learn the patter ns a huma n wrapper-writer would use? Wrapper in ducti on is usually regular relati ons which can be expressed by the structure of the document: the item in bold in the

10、3rd column of the table is the price Wrapper in ducti on tech niq ues can also lear n: If there is a page about a research project X and there is a link n ear the word people to a page that is about a person Y then Y is a member of the project X. HMM是？怎样在实际问题中应用？(理解) 文本分类 什么是分类问题？：形式化定义 Given:A desc

11、riptionof an instanee,xX, where X is the instanee Ianguage or instanee space . A fixed set of categories: C = c1, c2,cn Determine:The category of x: c(x)三C, where c(x) is a categorization function whose doma in is Xand whose range is C 不同文本表示视角下的分类方法：向量空间和概率表示 KNN算法 To classify docume ntd into class

12、 c Define k-n eighborhood N as k n earest n eighbors of d Count nu mber of docume nts i in N that bel ong to c Estimate P(c| d) as i/k Choose as class argmaxc P(c|d) 分类面、线性可分性(了解) 有限规模数据集上分类评测的方法 语料库 分类结果评估主要指标 准确率 P 召回率 R F测度值F 宏平均 Macro- 微平均 Micro- Macroaveraged precisi on: (10/20 + 90/100)/2 = 0.

13、7 Microaveraged precisi on: 100/120 = .83 ATC Evaluation Training set/Test set Confusion-matrix Recall: cii/ 第i 列和 Perception: cii/ 第 i行禾口 N-fold Cross-validation 分成N份，N-1份做训练集，1份做测试集，则轮换可有 N份相互独立的测试集，最 后求平均 文本聚类 什么是聚类问题？ 聚类是对数据对象进行划分的一种过程，与分类不同的是，它所划分的类是 未知的，故此，这是一个无指导的学习(un supervised learni ng )过

14、 程，即聚类算法不需要教师的指导，不需要提供训练数据，它倾向于 数据的自然划分。 问题背景(motivations) Whole corpus an alysis/navigatio nBetter user in terface For improvi ng recall in search applicati ons Better search results For better n avigati on of search results Effective “ user recall” will be higher For speedi ng up vector space retr

15、ieval Faster search 导航、结果集、结果导航、根据预先的聚类返回结果而不需计算向量相似度 问题描述(problem statement) PrtiHonal dustring. Given： a cfD di| n $imjlarihr measure (or distance metrk) a 卩arli honing criterion a desired number of cluslers K Cocnpule； An assignment function * : D 一 1K such that sa th ties the pirlitiaiAing crite

16、rion wilh respect to the similarity measure, 文档集、相似度度量、划分标准、聚类个数K 聚类评测(evaluation) 选择人工已经分好类或者做好标记的文档集合作为测试集合，聚类结束后， 将聚类结果与已有的人工分类结果进行比较。 聚类错误率CE=(错误关联+遗漏关联)/文档集合中所有可能的文档对的数量 聚类全面率CR=正确关联数/人工分类中文档对的数量 聚类准确率CP=正确关联数/聚类结果中文档对的数量 聚类方法 戈U分方法(partitional clustering) K-means 算法 Given： X: a sei of A veclor

17、s d: distance metric A: desired number of clusteis Select K random seeds丙.：恳用 fiom X Let 讥:=励，1 k p = c*E Tp Power Iterati on: 初始化向量pO,使得|p0|=1 对于k = 1,2, 执行如下步骤 x = ETpk-1 ,基本迭代 pk = x/|x|,规格化步骤 PageRank 算法 浏览者每次以一定的概率(1- B )沿着超链走，以概率(3 )重新随机选择一个 新的起始节点 Lu,v=Eu,v/d u prB、 Pi十=(1 P)LTpi + 二(1n b = (

18、1 0)LT + 石(1n) |Pi NNJ HITS算法(了解) HITS针对具体查询、应用在查询时间，而PageRa nk是独立于查询的 Root set, R(q):和查询q相关的网页集合 Base set, V(q):除了 R(q)夕卜，还包括指向R(q)元素和被R(q)元素指向的网页 Expa nded set = V - R 两个概念(直觉上有意义) 1、AUTHORITY(权威型网页)：内容权威，质量高的网页 2、 HUB(目录型网页)：指向许多authority 网页的网页 交叉定义 一个网页u的a值依赖于指向它的网页 v的h值 一个网页u的h值依赖于它所指的网页 v的a值 a

19、 = ET h 信息推荐 h = E a 二 E ET h 推荐系统(Recommendation System) What they are? Given a set of users and items Recomme nd items to a user based on 1、Past behavior of this and other users Who has viewed/bought/liked what? 2、Additional information on users and items Both users and items can have known attrib

20、utes age, genre, price, 相关算法 Classical Collaborative Filtering (CF)- memory-based algorithm n Pa J =+ 托刀- Vi) paq =Va 7 a.Paq n p aq =Z waiZiq i =1 Wai =E Zak zik k Ziq 二 v iq vi Combine collaborative and content filtering Model-based algorithm 系统评估 MAE存在的冋题是？ 文本索引 Text Parsing Tokenize, normalize, lemmatization, stem Inverted Inde