北邮郭军2016web搜索第二章

1、Web 搜索搜索郭军郭军北京邮电大学 第第2 2章章 文本检索文本检索nWeb信息采集信息采集n文本的保存与索引文本的保存与索引n检索模型检索模型n网页排序网页排序n查询重构查询重构n文本聚类文本聚类n文本分类文本分类n特征选择特征选择n特征变换特征变换引言引言n文本是最基本、同时也是最高级（抽象）的信息媒体n文本检索是Web搜索的起点也是重点n文本检索所涉及的问题uWeb信息的采集与组织u文本的表示u用户查询方法u相关文档排序u文本聚类u文本分类Web信息采集信息采集nCrawler/Spider:u利用hyperlink自动获取网页的URLu利用HTTP 进行网络编程自动下载网页nCraw

2、ler的基本原理u网页采集过程是一个从WWW的某网页出发不断向前漫游的过程u漫游的方向和路线是随机的u为了将随机漫游变成有序的向外扩展，必须对其进行有效地控制Crawler 的工作进程的工作进程Crawler的工作效率的工作效率n多线程Crawlern分布式Crawler: 通过分散在不同地点的服务器实现Crawler的难题的难题n前沿URL的选择u广度优先/深度优先?u优质网页优先？n无效URL问题n同一网页的多重访问问题n网页的再访问周期问题u流行度高的网页给予高频访问u基于链接分析判断网页的活跃度文本的预处理与保存文本的预处理与保存n预处理u网页去重: 基于消息摘要/链接结构u网页解析:

3、 HTML/XML文档的解析，取出其中的元数据、超链接、标题和文本内容n文本的保存u文本通常以压缩的形式保存u网页平均长度为10KB，压缩后为2-4KBu通用文件系统的存储块尺寸为4-8KBu网页存储通常采用专门开发的文件系统u大型商用搜索引擎需要在全球建立多个镜像的文件系统骨干服务器文本的索引文本的索引(1/2)n建立索引就是制作标记来指示内容的位置nWeb搜索通常情况下是全文搜索，即对网页中包含的所有词汇都建立索引n倒排文件(inverted file)u词汇表(vocabulary): 文本中所有不同词汇的集合u位置表(occurrences):词汇在文本中出现的地址列表(posting

4、 list)、字地址、词地址、文档地址uHeaps定律: vO(Na ) a 0.5 Gb级文本、Mb级词汇n查询步骤: 查询词汇表位置表文档或段落文本的索引文本的索引(2/2)n倒排索引的更新批量更新u主索引+新索引(stop-press index)u新索引(d,t,s)三元组倒排(t,d,s)n对一个用户的查询，主索引反馈文档集D0，新索引返回文档集D+和D-，返回给用户D0D+ D-n索引压缩u文档的标识符压缩: delta编码n索引词的选取u词标识、去停词(stopword)、词干化(stemming)检索模型检索模型n文本检索的本质问题: u用户需求文本集中最相关(最切题)的文档n

5、需解决的3个基本问题u用户如何提出需求t简单、便捷，关键词的方式u相关文档如何定义和计算t语法层相关/语义层相关u检索结果如何反馈tURL地址清单段落检索QABoolean模型模型n查询: 由关键词及逻辑关系符构成的Boolean表达式n文档: 索引词的集合n查询与文档相关的定义: 索引词的集合是否满足查询Boolean表达式n二元决策，无相关程度的度量n人们常常不容易用Boolean表达式描述查询n用户往往只是同时输入多个关键词，隐含地应用“与”逻辑VSMn用索引词出现的绝对或相对频度来表达文档和查询n所有m个不同的索引词构成m维的特征向量n文档dj的特征向量dj = w1j, w2j, ,

6、wmjn查询q的特征向量q = w1q, w2q, ,wmqn计算q和dj之间相关性或相似性有多种方法 相关性计算相关性计算12211( ,)mijiqimmijiqiiwwcoswwjq dn余弦相似度12211() ()( ,)()()mijjiqqimmijjiqqiiwwwwrwwwwjq dn相关系数索引词的权重索引词的权重nTF: ijijjfreqfMaxFreqnIDF: logiiNidfnnTF-IDF:() logijijjifreqNwMaxFreqnn查询词的权重:0.5(0.5) logiqiqqifreqNwMaxFreqn概率模型概率模型(1/2)n给定一个用户

7、查询q和一个文档dj ，概率模型通过估计dj与q的相关的概率来判断二者的相关性n假设在所有文档中存在一个对应q的理想集合R，即R中的文档都是q的相关文档，R之外的文档都是q的不相关文档n概率模型计算几率比:uP(dj relevant to q)/P(dj non-relevant to q)n在概率模型中，索引词的权重变量都是二值的，即wij 0,1，wiq 0,1概率模型概率模型(2/2)n取对数后简化ndj与q的相似性sim(dj, q)被定义为(R | ,)(|R, )(R)(, )(R | ,)(|R, )(R)jPqPqPsim dqPqPqPjjjjdddd1(1|R, )(1(

8、1|R, )(, )log(1(1|R, ) (1|R, )mijijjijiqiijijp wqp wqsim d qw wp wq p wqn两个概率的初始化 (1| R, )0.5ijP wq(1|R, )iijnP wqNn返回文档集合V后的改进估计|(1|R, )|iijVP wqV|(1|R, )|iiijnVP wqNVBayesian推理网络模型推理网络模型n节点对应文档、检索词、概念、查询等各类实体n每个节点v都与一个随机Boolean变量相联系，给定父节点u1, uk, P(v|u1,uk) 通常采用“或”逻辑，即只要有一个父节点的置信逻辑为“真”，则本节点就为“真”r1d

9、1d2dn-1dnr2r3rm-1rmc1c2coq狗牛羊文档层表示层概念层查询猫宠物偶蹄动物网页排序网页排序n基于文档与查询的相关性的排序n基于网页质量的排序n通过超链接分析来改进排序结果是Web文本检索与数据库文本检索的一个十分重要的区别u指向一个网页的超链接的数量代表着网页的流行度和质量u两个网页包含较多的相同的链接或被相同的网页所指向常常意味着它们之间具有某种密切的关系PageRankn模拟用户在Web上可用Markov链建模的网页浏览行为n假设任意节点u对于节点v都有一条有向路径，用户以概率分布p0随机地从一个节点出发，pi为i时刻到达各节点的概率n令Web邻接矩阵(图)为E，如果节

10、点u和v之间存在超链接，则E(u,v) = 1，否则为0 (Nu是节点u的出度)( , )( , )/uu vu vNLE令1TiipL p则p将收敛于LT的主特征向量PageRank的完善的完善n假设用户在Web图的每个节点上将进行两种选择u以概率q随机浏览Web上的任意一个网页u以概率1-q在所有的出链接中以均匀概率选择一个，继续前进则11/1/(1)1/1/(1)/(1,.,1)TiiiTTiNNqqNNqq NpL ppL pPageRank的近似解的近似解n当N很大时，直接求解改进PageRank方程组是困难的n简单算法是先将p0的所有元素设为1/N，然后反复用因子(1-q)LT+q

11、/N 1N乘以pi，并将|pi|缩放至1。n但此方法不能保证收敛。HITSnHITS (Hypertext Induced Topic Search)n与PageRank不同，是与查询相关的网页质量评价算法n收到查询q后，系统返回一个网页的集合RnR中的任意节点(网页)指向的节点和指向R中任意节点的节点构成集合X，R与X共同构成一个基本集合Vn构造图G = (V , E)，E为节点间的有向链接n评价网页的两个测度: a(authority)和h(hub)( , )( )( )v ua uh vE( , )( )( )u vh ua vET= Eah= Ehan 赋初值a = h = 1 迭代，

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

13、部分析自动局部分析n对于一个给定的查询q，称检索出来的文档集合Dl为局部文档集合n自动局部分析从Dl中查找查询词的近邻词n近邻的测度u关联度u近邻度u间接相关度 或jluvujvjdDsff1( , )iuvuvdDiuvnr t t|uviuvuvssss|uviuvuvnnnn11|( , )iuvuvdDuviuvnDr t tuvuvuuvvuvsssss局部语境分析局部语境分析LCAn基于由名词词组所构成的“概念”进行查询扩展n概念的定义通常基于词典进行n步骤: u1) 将初始查询检索出的文档分割成固定长度的段落，然后按与查询的相关性对其排序，取出前n个u2) 计算各段落中每个概念c

14、与查询q之间的相似度sim(c, q)u3) 将相似度最大的前m个概念加到初始查询之中n关键是第二步，选择一种合适的计算概念c和查询q中包含的词之间的相似度测度基于概念空间的全局分析基于概念空间的全局分析n寻找整个查询的近邻词n用文本集的所有N个文档构成一个概念空间，每个文档是空间中的一个维度n无论是检索词还是查询，都被看作概念空间中的数据点，即概念，对于检索词ti(i = 1,m)，ti=(wi1,wiN)，其中21(0.50.5)log(/)max ()(0.50.5)log(/)max ()ijjjijijNillllilfm mfwfm mfn 而查询 n 通过计算q与各检索词的相关性

15、进行查询扩展iiqtqwiqt基于同义词辞典的全局分析基于同义词辞典的全局分析n辞典包含若干同义词类n每个类由通过文档聚类算法获得的若干检索词构成u采用全链接(complete link)的聚类算法，即类对之间的相似度被定义为所有文档对的相似度的最小值uBottom-up的层次聚类u通过设置以下参数进行同义词类选择tTsim:最小类内相似度阈值tTnod:类内最大文档数阈值tTidf:倒文档频度阈值文本聚类文本聚类n在文本检索中的作用非常广泛和重要n聚类一直是模式识别、机器学习、数据挖掘等领域中的一个重点课题n无监督学习(Unsupervised learning)n目的是找到数据集合中潜在(

16、latent)的聚合结构n两大类聚类算法u区分法(discriminative method)u生成法(generative method)区分式聚类的基本思想区分式聚类的基本思想n给定一个(文档)集合D = di|i=1,Nu其中di = (di1,diM)为元素di的VSMn定义sim(di, dj)为di和dj之间的相似度n聚类问题可以定义为:u将集合D划分为k个子集D1,Dk，使类内的相似度总和S达到最大1sim(,)ikiDS uvuvd ,ddd区分式聚类的方式区分式聚类的方式n区分性聚类也称为分割聚类，核心操作是将集合中的元素排他式地划归到某个类中nbottom-up方式u初始将

17、每个文档作为一类，然后对最相似的类进行合并，直至类别数目或类内相似度达到设定值ntop-down方式u先将所有文档放在一类，然后以增大类内相似度为目标，对类进行分裂操作，直至类别数目或类内相似度达到设定的阈值Bottom-up方式例方式例Top-down方式例方式例层次汇合聚类层次汇合聚类HAC算法算法n1) 令每个文档d在一个单独的组中，形成N个组dn2) 令 G 为这N个组的集合n3) while |G| 1 don4)选择 u, vG，标准为合并它们将带来最大的利益测度n5)将 u 和 v 从 G 中移除n6)令 w = uvn7)将 w 插入 Gn8) end while随着合并次数的

18、增加，被合并类之间的相似度sim(u,v)会越来越低第4步的常用测度，S(w)的类内相似度，w = uv2,| |1( )sim(,)ijd dwwS wCijd dk-means聚类聚类n给定数据集合x1, xN, 每个数据是一个d维向量n目标是把这个数据集合划分为K个类(cluster)n预设K个类的质心k (k = 1, K)n通过使下式最小化，迭代新质心k和类别归属rnkk-means聚类算法聚类算法n1)初始化k个组的质心向量n2) while 还可以继续改进 don3) for 每个元素(文档) d don4)找出质心向量与d最相似的组cn5)将d调整到组c之中n6) end fo

19、rn7) for 每个组 c don8) 重新计算质心向量n9) end forn10) end while要点:u预先确定类别数为ku质心与元素都用向量表示k-means聚类示意聚类示意k-means聚类应用聚类应用软软k-means聚类聚类n硬k均值聚类: 元素d要么属于组c，要么不属于组c，在计算质心时，组内所有元素都具有相同的权重n软k均值聚类:允许一个元素部分地分别属于不同的组，但在计算组的质心时各个元素的贡献不同u计算质心的公式2211/ |()1/ |Niccicijcjddd基于亲和性消息的聚类基于亲和性消息的聚类n在k均值聚类中，如果选用样本数据为类中心，则称为k中心法，称被

20、选为中心的数据为范例(exemplar)，但初始范例选取困难n基于消息传播的聚类方法Frey 07将所有样本看作潜在范例，数据点通过已知的相似度被连成网络，相邻节点通过反复地传递和修改两个消息responsibility和availability使范例涌现出来n迭代更新a(i,k)和r(i, k)算法基于亲和性消息的聚类算法基于亲和性消息的聚类算法n1) 输入数据点间的相似度s(i,k)，表示k作为i的范例的适当度n2) 为每个数据点输入偏爱度s(k,k)，该值越大k越可能为范例n3) 将所有可用性消息a(i,k)置为0， a(i,k)是由k发给i的一个累积的“证据”， 来证明k适合于作为i的

21、范例n4)更新依靠性消息r(i,k)，这是由i发给候选范例k的(通过与其他候选范例比较的)一个累积的“证据”，证明k适于作为i的范例( , )( , )max ( ,)( ,)kkr i ks i ka i ks i kn5) 按如下规则分别更新可用性消息a(i,k)和a(k,k) , ( , )min0, ( , )max0, ( , )ii ka i kr k kr i k( , )max0, ( , )ika k kr i kn6) 对每个元素i计算 ，如不满足终止条件，转4)继续迭代argmax ( ,)( ,)kkr i ka i k生成式聚类生成式聚类n每个文档类别被看作对应一个主

22、题的文档集合n将文档的产生看作随机过程，每个主题类别有一个关于文档的概率分布模型n一个文档应该归属哪个类，决定于哪个类别的模型产生该文档的概率最大n关键是各个类别概率模型的估计二值概率模型二值概率模型n文档是二值元素的向量，每个元素对应词表W中的一个词tn假设词的出现是相互独立的事件，且只考虑词是否出现而不管出现的次数，则可得在概率参数集合条件下文档d生成的二值概率模型,P( |)(1)ttt dt W t dd n由于词表中的词数远远多于文档中的词数，且 的平均值低于0.5，使得该模型有利于短文本的生成，同时降低了实际出现可能性大的文档的产生概率t多值概率模型多值概率模型n考虑词在文档中的出

23、现次数n假设文档的总长度L符合一个概率分布P(l)n文档的产生过程是一个掷|W|个面的骰子的过程，每个面对应词表中的一个词n产生长度为ld的文档的过程就等于投掷骰子ld次n假设第t面出现了n(d,t)次，则文档的生成概率( , )P( , ( , )|)P(|)P( ( , )|,)P(|) ( , )ddddn d tdtt dln d tLln d tllLln d t 12! ( , )( , )! ( , )!.ddlln d tn d tn d t概率模型的参数估计概率模型的参数估计n假设要处理的文档集合共对应m个话题，产生第i类话题的概率为i ，第i类话题中词t的产生概率为i,tn

24、将m类话题文档的所有参数表示为:1,( ;,;, )mi tmi t n获得多类模型的关键步骤是通过训练数据将模型中的参数估计出来，著名的EM算法可用来完成这个参数估计基于基于MLE准则的参数估计准则的参数估计n为了简化描述，假设每个类别只有一个参数i，即11( ;,;,)mmm n用x表示文档，则其生成概率1P( |)P( |)mjjjxx n设有n个iid样本构成训练集合X = x1,xn，则可根据MLE准则通过对以下函数最大化来估计参数1P(|)P(|)(|)niiXxLX 11log (|)log(P(|)nmjijijLXxEM算法算法(E步步)nEM算法的思想：初始值E步/M步迭代

25、寻优n算法在不知各个样本的类别Y = y1,yn的情况下求解n先对给出初始“猜想”值 ，令全数据似然度Q为X、Y和条件下logL的期望值( ,)(log (|, )|,)P(|,)logP(,|)YYQELX YXY XX Y 11( ,)P( |,)log(P(|)mnililliQl xx n 推导可得n 由于Q是的对数似然度在Y的分布上获得的期望，因此这一步被称为E步EM算法算法(M步步)n怎样才能在的基础上获得一个更好的值呢，一种合理的方法是通过最大化Q来实现，这一步被称为M步n中包含和两类参数，先以为例介绍M步的更新算法n因为有约束条件1ii11log.P( |,)0mnlillil

26、kl x n 通过标准的Lagrange优化，可得方程组 n 求解可得11P( |,)nkiik xnEM算法算法(M步步)n 假设各类别的概率分布服从均值为k的Poisson分布 Pr( x | ) = e- x / x!11Pr( |,)(log)0mnilillikl xx n 求解可得11Pr( |,)Pr( |,)niiikniixk xk x文本分类文本分类n分类是最基本最重要的智能活动之一n模式识别系统的主要任务就是构造性能优良的分类器n分类是靠有监督的学习实现的，即通过有类别标注的样本对分类器进行训练n在Web搜索中的应用u网页及文档分类uSpam检测u情感分类u在线广告 k-

27、NN分类器分类器n利用k个与未知样本最接近的已知样本的类别来投票决定未知样本的类别n两个步骤:u寻找未知样本的k个最近邻(测度问题)u利用k近邻的类别对未知样本的类别进行投票预测n只需对训练样本进行标注，不需要进行其他训练n参数k的选择是最大问题n计算和存储开销通常很大Bayes分类器分类器n基于Bayes规则的分类器，理论与应用均非常重要n假设每个文档只属于一个类别，并按如下条件建模u每个类c都有一个先验概率P(c)u对于每个类c，存在似然度函数P(d|c)n则，生成类c中的文档d的概率等于P(d|c) P(c)，而给定文档d, 类c的(后验)概率P( | )P( )P( |)P( | )P

28、( )rd ccc dd rr朴素朴素Bayes模型模型n假设样本的各维特征之间是相互独立的n应用在文本分类中，假设词汇之间相互独立n以二值文档概率模型为例,P(|)(1)c tc ttdt W tddcn为简化计算，将上式改写为,P( | )(1)1c tc tt dt Wc td cn上式的第二个乘积与d无关可以预先计算n利用朴素Bayes模型需进行参数平滑，以防零概率事件Bayes网络网络thechtmlxmlPr(c = mp3) = .Pr(c = sports) = .thechtmlxml.Pr(xml = 1 | c = mp3) = .Pr(xml = 1 | c = spo

29、rts) = .Pr(xml = 1 | html = 1, c = mp3) = .Pr(xml = 1 | html = 1, c = sports) = .Pr(xml = 1 | html = 0, c = mp3) = .Pr(xml = 1 | html = 0, c = sports) = .(a)(b)xXx)(|Pr()Pr(paxP(d|c)不再是所有词的概率乘积，而成为条件概率的乘积X表示节点，x表示其取值最大熵原理最大熵原理n最大熵原理：当需要对事物进行预测时，所做的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设(以保证概率分布的信息熵最大)n假设有训练数

30、据(di, ci), i = 1, nnP(c|d)的最大熵模型通过一些反映已知条件的特征函数来建立。作为最基本的特征函数，每个特征fj的期望为,()P( , )( , )P( )P( |)( , )jjjd cdcE fd c fd cdc d fd cn假设训练数据无重复文档且每个文档只有一个标签，可获得如下约束：( ,)P( |)( , )jiiijiiicf d cc d f d c最大熵分类器最大熵分类器n在满足已知约束条件下利用最大熵原理求解P(c|d)n利用Lagrange乘子法，为对应每个特征的约束设一个Lagrange乘子i，所有乘子构成集合，构造函数,(P(|),)P()

31、P(|) log P(|)(,)P(|)(, )d cjjiiijijii cGcddcdcdfdccdfdc n通过最大化G，可获得：1P( |)exp( , )( )jjjc dfd cZ d区分式分类器区分式分类器n区分式分类器不去探究概率分布P(c|d) ，而是直接将文档特征向量映射为类别标签n例如，一种构造区分式二元分类器的方法是：在特征空间中找到一个向量，使得文档d的类别标签等于sgn (di + b)n线性最小二乘回归是获得上述分类器参数和b的有效方法n它利用训练数据(di, ci), i = 1, n，通过最小化类标签预测的均方误差求解参数，即最小化误差2() diiibcSV

32、Mn基本思想是最大化分类面两侧的样本距超平面的最小距离n建立在统计学习的结构风险最小化原则基础上n文档向量空间中线性判别函数的一般形式为g(d) = d + bn分类面方程为d + b = 0n将判别函数归一化，即使离分类面最近的样本的|g(d)|=1 ，则分类间隔等于2/SVM的优化目标的优化目标n使间隔最大等价于使最小n而要求H对所有样本正确分类，应使()11,., d iicbin n引入正的松弛因子i允许错分样本的存在，则()11,., d iiicb -in n从而，寻找最优分类面问题可表示为如下二次优化问题12()11,., d iiiiiMinimizeCsubject tocb

33、 -in SVM的求解的求解n利用Lagrange优化方法，可将上式的优化问题转化为如下对偶问题niandctosubjectccMinimizeiiiijijijijiii,.,1 C0 0 )(21 ,ddn上式的解中，只有少数i不为零，它们所对应的样本就是支持向量，分类阈值b*可利用最优分类面方程通过两类中任意一对支持向量求得n最终，文档d的最优分类函数为*( )sgn()d diiiSVf dcb非线性非线性SVMn对于非线性可分的情况，可以用一个非线性映射将样本映射到高维特征空间中，使之在高维空间中线性可分n文本在高维空间的内积为(di) (dj)n问题是能否找到函数K，使得K(di

34、 ,dj) =(di) (dj)，K被称为核函数n有了核函数，非线性SVM的求解就变成,1 (,)2 0 0C 1,.,iijijijii jiiiiMinimizecc Ksubject tocandin d dn最优分类函数变为*( )sgn()iiSVfc Kbidd ,d常用核函数常用核函数n多项式核函数n径向基函数nSigmoid函数( ,)(1)qjjKd dd d22()( ,)expjjKddd d( ,)tanh( ()jjKvcd dd d特征选择特征选择n文本聚类和文本分类都以词作为基本特征来描述文档n高维文档特征不仅带来高额的运算开销，而且会产生由训练样本不足所导致的模

35、型不可靠或失效的问题n特征降维非常重要，特征选择是方法之一n两类特征选择算法u包含算法: 从空集开始选择越来越多好的特征，直到适当为止u排除算法: 从初始特征集开始逐步排除差的特征，直到适当为止包含算法包含算法n算法u1) 对每个词，计算其类区分性测度u2) 按区分性测度对词进行降序排序u3) 保留最好的n个词作为特征用于表达文档n各个词的类区分性一般是独立计算的，因此这类算法具有贪心(greedy)的特点n区分性测度是关键n常用测度包括2、互信息、Fisher鉴别指数等2 测度测度n以二类问题为例，设uk00, k01分别为不包含/包含词t的类0中文档数uk10 , k11分别为不包含/包含

36、词t的类1中文档数un = k00 + k01+ k10+ k11uP(C=0) = (k00+k01) / n n定义n2越大，类与词之间的相关性也越大)()()()(00100111000110112011000112kkkkkkkkkkkkn22,()()()()pqtp qtknP Cp P OqnP Cp P Oq互信息互信息n通过互信息计算文档类与词之间的相关性n互信息通过P(x,y)对P(x)P(y)的偏离程度对随机变量之间的依赖程度进行测量n如果随机变量X和Y相互独立，则对于所有的取值x和y P(x,y)/P(x)P(y)=1n因此，定义互信息为P( , )( , )P( ,

37、)logP( )P( )MIxyx yX Yx yxyFisher鉴别鉴别n以二类学习问题为例，令X和Y分别表示一类向量的集合。向量的元素可以是令向量长度归一的实数nFisher鉴别在寻找一种映射*，它使得X和Y两个数据集被映射到二者质心间的距离相对集合内数据的展开幅度达到最大的方向上，即)()(maxarg)(maxarg2*YXTYXTSSJn令S = (SX+SY)/2，当S-1存在时， = S-1 (X-Y) 是一个解 Fisher鉴别指数鉴别指数nFisher鉴别是一种变换，具有破坏特征稀疏性的特点n将每个词t都看作为一个候选的方向，即令t = (0,1,0)T，即1只在词t的位置出

38、现，定义t的Fisher鉴别指数为tTtYXTttSJt2)()()(FIn由于t的特殊形式，上式可简化为XYtYttXttYtXyYxXt2,2,2,)(|)| /1 ()(|)| /1 ()()(FIn对于多类问题cDdtctdcccctctcxDt2,2, 12,2, 1)(|)| /1 ()()(FI排除算法排除算法n排除算法从全部词特征集T开始逐步对“无用”特征进行排除，直至获得一个满意的特征子集Fn排除算法的核心思想是尽量保持P(C |T)与P(C|F)的相似性，因为分类与聚类可以基于类(C)的后验概率分布来设计算法nP(C |T)与P(C|F)的相似性可用KL距离来度量cTcFcFcTCFCKL)|Pr()|Pr(log)|Pr()|Pr(|)|(Pr(排除算法排除算法n如果P(P=p|Q=q，R=r) = P(P=p|R=r)，则称P在R条件下独立于Qn排除算法的核心是寻找类与特征之间的条件独立关系n排除算法复杂度高，优点是考虑了特征之间的相关性特征维数确认特征维数确认nValidation: 取多少维特征最佳n普通确认u训练数据被分为两部分，分别用于特征排序和测试n交叉确认: 留一法(Le