北邮郭军2016web搜索第二章

Web搜索

郭军

北京邮电大学

第2章文本检索Web信息采集文本的保存与索引检索模型网页排序查询重构文本聚类文本分类特征选择特征变换引言文本是最基本、同时也是最高级（抽象）的信息媒体文本检索是Web搜索的起点也是重点文本检索所涉及的问题Web信息的采集与组织文本的表示用户查询方法相关文档排序文本聚类文本分类Web信息采集Crawler/Spider:利用hyperlink自动获取网页的URL利用HTTP进行网络编程自动下载网页Crawler的基本原理网页采集过程是一个从WWW的某网页出发不断向前漫游的过程漫游的方向和路线是随机的为了将随机漫游变成有序的向外扩展，必须对其进行有效地控制Crawler的工作进程Crawler的工作效率多线程Crawler分布式Crawler:通过分散在不同地点的服务器实现Crawler的难题前沿URL的选择广度优先/深度优先?优质网页优先？无效URL问题同一网页的多重访问问题网页的再访问周期问题流行度高的网页给予高频访问基于链接分析判断网页的活跃度文本的预处理与保存预处理网页去重:基于消息摘要/链接结构网页解析:HTML/XML文档的解析，取出其中的元数据、超链接、标题和文本内容文本的保存文本通常以压缩的形式保存网页平均长度为10KB，压缩后为2-4KB通用文件系统的存储块尺寸为4-8KB网页存储通常采用专门开发的文件系统大型商用搜索引擎需要在全球建立多个镜像的文件系统骨干服务器文本的索引(1/2)建立索引就是制作标记来指示内容的位置Web搜索通常情况下是全文搜索，即对网页中包含的所有词汇都建立索引倒排文件(invertedfile)词汇表(vocabulary):文本中所有不同词汇的集合位置表(occurrences):词汇在文本中出现的地址列表(postinglist)、字地址、词地址、文档地址Heaps定律:v~O(Na

)a≈0.5Gb级文本、Mb级词汇查询步骤:查询词汇表位置表文档或段落文本的索引(2/2)倒排索引的更新—批量更新主索引+新索引(stop-pressindex)新索引(d,t,s)三元组倒排(t,d,s)对一个用户的查询，主索引反馈文档集D0，新索引返回文档集D+和D-，返回给用户D0∪D+\D-索引压缩文档的标识符压缩:delta编码索引词的选取词标识、去停词(stopword)、词干化(stemming)检索模型文本检索的本质问题:用户需求文本集中最相关(最切题)的文档需解决的3个基本问题用户如何提出需求简单、便捷，关键词的方式相关文档如何定义和计算语法层相关/语义层相关检索结果如何反馈URL地址清单段落检索QABoolean模型查询:由关键词及逻辑关系符构成的Boolean表达式文档:索引词的集合查询与文档相关的定义:索引词的集合是否满足查询Boolean表达式二元决策，无相关程度的度量人们常常不容易用Boolean表达式描述查询用户往往只是同时输入多个关键词，隐含地应用“与”逻辑VSM用索引词出现的绝对或相对频度来表达文档和查询所有m个不同的索引词构成m维的特征向量文档dj的特征向量dj=[w1j,w2j,…,wmj]查询q的特征向量q=[w1q,w2q,…,wmq]计算q和dj之间相关性或相似性有多种方法

相关性计算余弦相似度相关系数索引词的权重TF:IDF:TF-IDF:查询词的权重:概率模型(1/2)给定一个用户查询q和一个文档dj

，概率模型通过估计dj与q的相关的概率来判断二者的相关性假设在所有文档中存在一个对应q的理想集合R，即R中的文档都是q的相关文档，R之外的文档都是q的不相关文档概率模型计算几率比:P(djrelevanttoq)/P(djnon-relevanttoq)在概率模型中，索引词的权重变量都是二值的，即wij

∈{0,1}，wiq

∈{0,1}概率模型(2/2)取对数后简化dj与q的相似性sim(dj,q)被定义为两个概率的初始化

返回文档集合V后的改进估计Bayesian推理网络模型节点对应文档、检索词、概念、查询等各类实体每个节点v都与一个随机Boolean变量相联系，给定父节点u1,…uk,P(v|u1,…uk)通常采用“或”逻辑，即只要有一个父节点的置信逻辑为“真”，则本节点就为“真”网页排序基于文档与查询的相关性的排序基于网页质量的排序通过超链接分析来改进排序结果是Web文本检索与数据库文本检索的一个十分重要的区别指向一个网页的超链接的数量代表着网页的流行度和质量两个网页包含较多的相同的链接或被相同的网页所指向常常意味着它们之间具有某种密切的关系PageRank模拟用户在Web上可用Markov链建模的网页浏览行为假设任意节点u对于节点v都有一条有向路径，用户以概率分布p0随机地从一个节点出发，pi为i时刻到达各节点的概率令Web邻接矩阵(图)为E，如果节点u和v之间存在超链接，则E(u,v)=1，否则为0(Nu是节点u的出度)令则p将收敛于LT的主特征向量PageRank的完善假设用户在Web图的每个节点上将进行两种选择以概率q随机浏览Web上的任意一个网页以概率1-q在所有的出链接中以均匀概率选择一个，继续前进则PageRank的近似解当N很大时，直接求解改进PageRank方程组是困难的简单算法是先将p0的所有元素设为1/N，然后反复用因子(1-q)LT+q/N1N乘以pi，并将|pi|缩放至1。但此方法不能保证收敛。HITSHITS(HypertextInducedTopicSearch)与PageRank不同，是与查询相关的网页质量评价算法收到查询q后，系统返回一个网页的集合RR中的任意节点(网页)指向的节点和指向R中任意节点的节点构成集合X，R与X共同构成一个基本集合V构造图G

=(V,E)，E为节点间的有向链接评价网页的两个测度:a(authority)和h(hub)赋初值a=h=1

迭代，

收敛后，a等于ETE的主特征向量

h等于EET的主特征向量查询重构用户提出一个适当的查询请求往往是不容易的可将用户的第一个查询看作是初始的尝试，通过对获得的文档的相关分析，对初始查询进行重构查询重构的三类方法基于用户反馈信息的的方法基于对初始反馈文档的局部分析的方法基于对全部文档集合的全局分析的方法用户相关反馈先将检索出的文档清单提交给用户，用户查阅后，对相关的文档进行标记设D+为用户标记的相关文档的集合，D-为反馈文档中非相关文档的集合Rocchio公式α，β和γ都是可调参数，简单的设置是令它们都为1

在D-不好确定时，常令γ为0自动局部分析对于一个给定的查询q，称检索出来的文档集合Dl为局部文档集合自动局部分析从Dl中查找查询词的近邻词近邻的测度关联度近邻度间接相关度

或局部语境分析LCA基于由名词词组所构成的“概念”进行查询扩展概念的定义通常基于词典进行步骤:1)将初始查询检索出的文档分割成固定长度的段落，然后按与查询的相关性对其排序，取出前n个2)计算各段落中每个概念c与查询q之间的相似度sim(c,q)3)将相似度最大的前m个概念加到初始查询之中关键是第二步，选择一种合适的计算概念c和查询q中包含的词之间的相似度测度基于概念空间的全局分析寻找整个查询的近邻词用文本集的所有N个文档构成一个概念空间，每个文档是空间中的一个维度无论是检索词还是查询，都被看作概念空间中的数据点，即概念，对于检索词ti(i=1,…,m)，ti=(wi1,…,wiN)，其中而查询

通过计算q与各检索词的相关性进行查询扩展基于同义词辞典的全局分析辞典包含若干同义词类每个类由通过文档聚类算法获得的若干检索词构成采用全链接(completelink)的聚类算法，即类对之间的相似度被定义为所有文档对的相似度的最小值Bottom-up的层次聚类通过设置以下参数进行同义词类选择Tsim:最小类内相似度阈值Tnod:类内最大文档数阈值Tidf:倒文档频度阈值文本聚类在文本检索中的作用非常广泛和重要聚类一直是模式识别、机器学习、数据挖掘等领域中的一个重点课题无监督学习(Unsupervisedlearning)目的是找到数据集合中潜在(latent)的聚合结构两大类聚类算法区分法(discriminativemethod)生成法(generativemethod)区分式聚类的基本思想给定一个(文档)集合D={di|i=1,…,N}其中di=(di1,…,diM)为元素di的VSM定义sim(di,dj)为di和dj之间的相似度聚类问题可以定义为:将集合D划分为k个子集D1,…Dk，使类内的相似度总和S达到最大区分式聚类的方式区分性聚类也称为分割聚类，核心操作是将集合中的元素排他式地划归到某个类中bottom-up方式初始将每个文档作为一类，然后对最相似的类进行合并，直至类别数目或类内相似度达到设定值top-down方式先将所有文档放在一类，然后以增大类内相似度为目标，对类进行分裂操作，直至类别数目或类内相似度达到设定的阈值Bottom-up方式例Top-down方式例层次汇合聚类HAC算法1)令每个文档d在一个单独的组中，形成N个组{d}2)令G为这N个组的集合3)while|G|>1do4)选择u,v∈G，标准为合并它们将带来最大的利益测度5)将u和v从G中移除6)令w=u∪v7)将w插入G8)endwhile随着合并次数的增加，被合并类之间的相似度sim(u,v)会越来越低第4步的常用测度，S(w)的类内相似度，w=u∪vk-means聚类给定数据集合{x1,…xN},每个数据是一个d维向量目标是把这个数据集合划分为K个类(cluster)预设K个类的质心μk(k=1,…,K)通过使下式最小化，迭代新质心μk和类别归属rnkk-means聚类算法1)初始化k个组的质心向量2)while

还可以继续改进do3)

for

每个元素(文档)d

do4)找出质心向量与d最相似的组c5)将d调整到组c之中6)

endfor7)

for

每个组c

do8)重新计算质心向量9)

endfor10)endwhile要点:预先确定类别数为k质心与元素都用向量表示k-means聚类示意k-means聚类应用软k-means聚类硬k均值聚类:元素d要么属于组c，要么不属于组c，在计算质心时，组内所有元素都具有相同的权重软k均值聚类:允许一个元素部分地分别属于不同的组，但在计算组的质心时各个元素的贡献不同计算质心的公式基于亲和性消息的聚类在k均值聚类中，如果选用样本数据为类中心，则称为k中心法，称被选为中心的数据为范例(exemplar)，但初始范例选取困难基于消息传播的聚类方法[Frey07]将所有样本看作潜在范例，数据点通过已知的相似度被连成网络，相邻节点通过反复地传递和修改两个消息—responsibility和availability使范例涌现出来迭代更新a(i,k)和r(i,k)算法基于亲和性消息的聚类算法1)输入数据点间的相似度s(i,k)，表示k作为i的范例的适当度2)为每个数据点输入偏爱度s(k,k)，该值越大k越可能为范例3)将所有可用性消息a(i,k)置为0，

a(i,k)是由k发给i的一个累积的“证据”，来证明k适合于作为i的范例4)更新依靠性消息r(i,k)，这是由i发给候选范例k的(通过与其他候选范例比较的)一个累积的“证据”，证明k适于作为i的范例5)按如下规则分别更新可用性消息a(i,k)和a(k,k)6)对每个元素i计算

，如不满足终止条件，转4)继续迭代生成式聚类每个文档类别被看作对应一个主题的文档集合将文档的产生看作随机过程，每个主题类别有一个关于文档的概率分布模型一个文档应该归属哪个类，决定于哪个类别的模型产生该文档的概率最大关键是各个类别概率模型的估计二值概率模型文档是二值元素的向量，每个元素对应词表W中的一个词t假设词的出现是相互独立的事件，且只考虑词是否出现而不管出现的次数，则可得在概率参数集合Φ条件下文档d生成的二值概率模型由于词表中的词数远远多于文档中的词数，且的平均值低于0.5，使得该模型有利于短文本的生成，同时降低了实际出现可能性大的文档的产生概率多值概率模型考虑词在文档中的出现次数假设文档的总长度L符合一个概率分布P(l)文档的产生过程是一个掷|W|个面的骰子的过程，每个面对应词表中的一个词产生长度为ld的文档的过程就等于投掷骰子ld次假设第t面出现了n(d,t)次，则文档的生成概率概率模型的参数估计假设要处理的文档集合共对应m个话题，产生第i类话题的概率为αi，第i类话题中词t的产生概率为θi,t将m类话题文档的所有参数表示为:获得多类模型的关键步骤是通过训练数据将模型中的参数估计出来，著名的EM算法可用来完成这个参数估计基于MLE准则的参数估计为了简化描述，假设每个类别只有一个参数μi，即用x表示文档，则其生成概率设有n个iid样本构成训练集合X={x1,…,xn}，则可根据MLE准则通过对以下函数最大化来估计参数ΘEM算法(E步)EM算法的思想：初始值E步/M步迭代寻优算法在不知各个样本的类别Y={y1,…,yn}的情况下求解先对Θ给出初始“猜想”值Θ'，令全数据似然度Q为X、Y和Θ'条件下logL的期望值

推导可得由于Q是Θ的对数似然度在Y的分布上获得的期望，因此这一步被称为E步EM算法(M步)怎样才能在Θ'的基础上获得一个更好的Θ值呢，一种合理的方法是通过最大化Q来实现，这一步被称为M步Θ中包含α和μ两类参数，先以α为例介绍M步的更新算法因为有约束条件通过标准的Lagrange优化，可得方程组

求解可得EM算法(M步)假设各类别的概率分布服从均值为μk的Poisson分布

Pr(x|μ)=e-μμx/x!求解可得文本分类分类是最基本最重要的智能活动之一模式识别系统的主要任务就是构造性能优良的分类器分类是靠有监督的学习实现的，即通过有类别标注的样本对分类器进行训练在Web搜索中的应用网页及文档分类Spam检测情感分类在线广告

k-NN分类器利用k个与未知样本最接近的已知样本的类别来投票决定未知样本的类别两个步骤:寻找未知样本的k个最近邻(测度问题)利用k近邻的类别对未知样本的类别进行投票预测只需对训练样本进行标注，不需要进行其他训练参数k的选择是最大问题计算和存储开销通常很大Bayes分类器基于Bayes规则的分类器，理论与应用均非常重要假设每个文档只属于一个类别，并按如下条件建模每个类c都有一个先验概率P(c)对于每个类c，存在似然度函数P(d|c)则，生成类c中的文档d的概率等于P(d|c)P(c)，而给定文档d,类c的(后验)概率朴素Bayes模型假设样本的各维特征之间是相互独立的应用在文本分类中，假设词汇之间相互独立以二值文档概率模型为例为简化计算，将上式改写为上式的第二个乘积与d无关可以预先计算利用朴素Bayes模型需进行参数平滑，以防零概率事件Bayes网络P(d|c)不再是所有词的概率乘积，而成为条件概率的乘积X表示节点，x表示其取值最大熵原理最大熵原理：当需要对事物进行预测时，所做的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设(以保证概率分布的信息熵最大)假设有训练数据{(di,ci),i=1,…,n}P(c|d)的最大熵模型通过一些反映已知条件的特征函数来建立。作为最基本的特征函数，每个特征fj的期望为假设训练数据无重复文档且每个文档只有一个标签，可获得如下约束：最大熵分类器在满足已知约束条件下利用最大熵原理求解P(c|d)利用Lagrange乘子法，为对应每个特征的约束设一个Lagrange乘子λi，所有乘子构成集合Λ，构造函数通过最大化G，可获得：区分式分类器区分式分类器不去探究概率分布P(c|d)，而是直接将文档特征向量映射为类别标签例如，一种构造区分式二元分类器的方法是：在特征空间中找到一个向量α，使得文档d的类别标签等于sgn(α·di+b)线性最小二乘回归是获得上述分类器参数α和b的有效方法它利用训练数据{(di,ci),i=1,…,n}，通过最小化类标签预测的均方误差求解参数，即最小化误差SVM基本思想是最大化分类面两侧的样本距超平面的最小距离建立在统计学习的结构风险最小化原则基础上文档向量空间中线性判别函数的一般形式为g(d)=α·d+b分类面方程为α·d+b=0将判别函数归一化，即使离分类面最近的样本的|g(d)|=1，则分类间隔等于2/‖α‖SVM的优化目标使间隔最大等价于使‖α‖最小而要求H对所有样本正确分类，应使引入正的松弛因子ξi允许错分样本的存在，则从而，寻找最优分类面问题可表示为如下二次优化问题SVM的求解利用Lagrange优化方法，可将上式的优化问题转化为如下对偶问题上式的解中，只有少数λi不为零，它们所对应的样本就是支持向量，分类阈值b*可利用最优分类面方程通过两类中任意一对支持向量求得最终，文档d的最优分类函数为非线性SVM对于非线性可分的情况，可以用一个非线性映射Φ将样本映射到高维特征空间中，使之在高维空间中线性可分文本在高维空间的内积为Φ(di)·Φ(dj)问题是能否找到函数K，使得K(di,dj)=Φ(di)·Φ(dj)，K被称为核函数有了核函数，非线性SVM的求解就变成最优分类函数变为常用核函数多项式核函数径向基函数Sigmoid函数特征选择文本聚类和文本分类都以词作为基本特征来描述文档高维文档特征不仅带来高额的运算开销，而且会产生由训练样本不足所导致的模型不可靠或失效的问题特征降维非常重要，特征选择是方法之一两类特征选择算法包含算法:从空集开始选择越来越多好的特征，直到适当为止排除算法:从初始特征集开始逐步排除差的特征，直到适当为止包含算法算法1)对每个词，计算其类区分性测度2)按区分性测度对词进行降序排序3)保留最好的n个词作为特征用于表达文档各个词的类区分性一般是独立计算的，因此这类算法具有贪心(greedy)的特点区分性测度是关键常用测度包括χ2、互信息、Fisher鉴别指数等χ2测度以二类问题为例，设k00,k01分别为不包含/包含词t的类0中文档数k10

,k11分别为不包含/包含词t的类1中文档数n=k00+k01+k10+k11P(C=0)=(k00+k01)/n…定义χ2越大，类与词之间的相关性也越大互信息通过互信息计算文档类与词之间的相关性互信息通过P(x,y)对P(x)P(y)的偏离程度对随机变量之间的依赖程度进行测量如果随机变量X和Y相互独立，则对于所有的取值x和yP(x,y)/P(x)P(y)=1因此，定义互信息为Fisher鉴别以二类学习问题为例，令X和Y分别表示一类向量的集合。向量的元素可以是令向量长度归一的实数Fisher鉴别在寻找一种映射α*，它使得X和Y两个数据集被映射到二者质心间的距离相对集合内数据的展开幅度达到最大的方向上，即令S=(SX+SY)/2，当S-1存在时，α=S-1(μX-μY)是一个解

Fisher鉴别指数Fisher鉴别是一种变换，具有破坏特征稀疏性的特点将每个词t都看作为一个候选的方向，即令

αt=(0,…,1,…,0)T，即1只在词t的位置出现，定义t的Fisher鉴别指数为由于αt的特殊形式，上式可简化为

对于多类问题

排除算法排除算法从全部词特征集T开始逐步对“无用”特征进行排除，直至获得一个满意的特征子集F排除算法的核心思想是尽量保持P(C

|T)与P(C|F)的相似性，因为分类与聚类可以基于类(C)的后验概率分布来设计算法P(C

|T)与P(C|F)的相似性可用KL距离来度量排除算法如果P(P=p|Q=q，R=r)=P(P=p|R=r)，则称P在R条件下独立于Q排除算法的核心是寻找类与特征之间的条件独立关系排除算法复杂度高，优点是考虑了特征之间的相关性特征维数确认Validation:取多少维特征最佳普通确认训练数据被分为两部分，分别用于特征排序和测试交叉确认:留一法(Leave-One-Out)训练数据较少时使用每次留出一个样本用于测试特征变换通过数学变换对原始特征进行不同的线性或非线性组合，从新产生的组合中挑选好特征本质是不同域或空间之间的映射目的是找到能用更低维度“紧凑”地表达文档数据的空间，同时，在新空间中，文档之间仍然保持在原空间的亲疏关系只要能起到特征降维和保持文档之间原有距离的效果的各种数学变换都可应用于文档特征变换Fourier、Wavelet、PCA、LDA、流形分析在文本聚类和分类中，SOM和LSI具有典型意义SOM(Self-OrganizingMap)输入数据并联地馈入到一维或二维排列的神经元阵列，将多维连续数据空间映射到一维或二维离散数据空间神经元间的拓扑距离代表使其兴奋