北邮郭军web搜索第五章

Web搜索郭军北京邮电大学第5章信息过滤基本方法模型学习垃圾邮件及垃圾短信过滤话题检测与追踪系统引言信息过滤的本质是“流环境”下的二元分类流环境：过滤系统处于信息持续新生的环境之中，新的数据源源不断地流经过滤系统二元分类：一类是需要筛选出来的，一类是系统不关心的以模式分类为技术核心，高效高精度地处理数据流IR•被检索的文档相对稳定•用户查询需求不同IF•信息资源动态变化•用户需求相对固定IF的研究重点分类器的选择针对特定的应用环境选择分类器模型目前研究较多的是朴素Bayes模型、向量相似度(模板匹配)模型、SVM、k-NN等分类器的学习及优化生成式算法、区分式算法计算效率，类别模型的增量学习和自动演进，半监督学习、特征降维技术基本方法信息过滤系统中常用的分类器Bayes分类器向量距离分类器k近邻分类器SVM系统性能评价Bayes分类器Bayes分类器将分类问题看作统计决策问题，以最小错误率为目标进行分类前提：事先获得各个类别的概率分布，决策时利用Bayes公式计算给定样本特征值条件下各类别的后验概率设随机变量x∈Rd,各类别的概率分布为P(x|ci)，对于某确定样本t,根据Bayes公式：()()()()iiiPcPcPcPttt分类方法计算得到各个P(ci|t)后，将样本t分到类别ck中，其中1argmax()jjmkPct举例：随机选取100封邮件，进行人工标注，其中有30封垃圾邮件和70封非垃圾邮件，对于词“培训”，垃圾邮件中有21封含有该词，非垃圾邮件中有28封含有该词，假定过滤系统只采用该词判别是否为垃圾邮件，问若一封新邮件含有该词，则过滤系统认为该邮件是否是垃圾邮件？对于多个词，如何判别？似然比Rl二元分类问题可以根据似然比Rl来决定t的归属对数似然比：假设x的各维数据之间相互独立；朴素Bayes分类器111222(|)()(|)(|)()(|)lPcPcPcRPcPcPctttt111221()(|)()(|)djjldjjPcPtcRPcPtc121211lnln()ln()ln(|)ln(|)ddljjjjRPcPcPtcPtc向量距离分类器向量距离分类器可以看作是Bayes分类器的简化，它用各类别数据的均值向量、方差向量、协方差矩阵等参数近似描述它们的分布特性，利用向量之间的各种距离进行分类，常用的距离尺度有:21()dgjijjDt1||dcjijjDt1()()TmiiiDtt221()/dsjijijjDtk近邻分类器也称k-NN分类器(k-NearestNeighbor)最大特点是不需要训练类别模型，而是按某种合理的比例从各类别中抽取样本，用所有抽出的样本构成分类器的总体特征样本对于一个给定的样本t，首先按照某种距离测度找出与其最接近的k个样本，然后根据这k个样本所属类别进行投票SVMSVM是一种以结构风险最小化为目标的二元分类器，在寻找最优分类超平面时不但要求将两类数据隔离，而且要求两类数据距超平面的平均距离最大设线性可分数据集为D维空间中线性判别函数的一般形式为分类超平面方程为1{(,)}niiiyDxdRx1,1y()gbxwx0bwx系统性能评价评价指标主要包括分类器的精度和速度速度取决于分类器算法的复杂程度，在实际应用中与计算机的硬件性能关系很大精度通过与人工标注结果(groundtruth)进行比较来计算对于二元分类问题，常用的精度指标有准确率召回率F-measurebreak-even点精度指标标注为L类标注为非L类判别为L类ab判别为非L类cd分类与标注对应关系的频次aPabaRaci)准确率(Precision)表示所有被分类器分到类L的数据中正确的所占的比例ii)召回率(Recall)表示所有实际属于L的数据被分类器分到L中的比例iii)平衡点BEP(Break-evenPoint):P和R值是互相影响的:P会随着R的升高而降低，反之亦然。因此，为了更全面地反映分类器的性能，一种做法是选取P和R相等时的值来表征系统性能，这个值叫BEPiv)F值一种把准确率和召回率综合考虑的评价方法，定义如下：22(1)PRFPR12PRFPR模型学习生成式学习典型应用：利用EM算法对GMM的参数进行估计共同特征：每个类模型只用本类的样本进行估计，估计的准则是使模型产生训练样本的可能性最大(最大似然)早期的模型学习主要采用生成式算法区分式学习典型应用:SVM的学习共同特征:由需要相互区分的各类样本共同构成一个模型，通过多类样本的“角力”形成不偏不依的分类面降维变换需要进行学习的降维变换是指变换核（基函数）随被处理数据集变化以获得最佳变换效果的变换(自适应变换)主成分分析PCA(PrincipalComponentAnalysis)独立成分分析ICA(IndependentComponentAnalysis)线性鉴别分析LDA(LinearDiscriminativeAnalysis)希尔伯特—黄变换Hilbert-Huang自适应变换也存在生成式和区分式之分PCAdRxN1i}{ixX11NxiiNx11)NtxixixiN(x)(x设随机变量，存在一个样本集，则其均值可估计如下：协方差矩阵可估计如下：xiia1{,...,}dAaa()xtAyx求解按降序排列的d个特征值和对应的特征向量，并构成矩阵称为x的PCA变换(也称K-L变换)，则式PCA的性质yxtAAxyx1ydPCA变换后的变量y是零均值的随机变量，其协方差矩阵为：由于A是列为的特征向量的正交矩阵，所以是对角阵且对角线元素为的特征值，即：由于y的非对角元素都是零，所以随机变量y的各维之间是不相关的LDALDA的思想是找一个投影方向，使得投影后在低维空间里样本的类间散度较大，类内散度较小x1x2x’LDA的定义(1/3)1cwiiSS()()itiiCSixxmxmdRx1()()ctbiiiinSmmmmm设Ci为第i类样本的集合，共有c类样本，则样本类内散度矩阵定义为：其中，mi为第i类样本的均值，样本类间散度矩阵定义为：其中为样本集的总体均值向量LDA的定义(2/3)tWyx:将d维的随机变量x变换到c-1维11()()()()ySSiccttwiibiiiiCinymymmmmmSWSWSWSWttwwbbwSoptW定义在变换空间中样本的类内和类间散度矩阵：容易证明因此，如果是非奇异矩阵，最优的投影方向就是使得样本在变换空间的类间散度矩阵和样本类内散度矩阵的行列式比值最大的那些正交特征向量LDA的定义(3/3)定义如下的准则函数：()argmaxargmaxTbbTwwJoptWWSWS(1,2,)biiwiic1SwSw…，-1wbSS1SS121{,,,}cdiag容易证明，使J(.)最大化的变换矩阵W的列向量由下列等式中的最大特征值对应的特征向量组成：这是一个广义特征值问题，如果Sw是非奇异的，W的列向量就是由矩阵的特征向量组成其中LDA的奇异性LDA是信息过滤中数据降维的核心算法之一在应用中常遇到类内分散度矩阵Sw奇异的问题当数据维数很高时，能够获得的样本数常常相对不足，使得独立的训练样本数N小于数据维数d，而这将导致Sw为奇异矩阵信息过滤所处理的文本、图像、音频等一般都是在高维数据空间中表达的解决LDA奇异性问题时，常先用某种生成式算法对数据进行降维LDA奇异性的解决主要方法:正则化LDAPCA+LDAPCA+NULL空间LDA/QRLDA/GSVD正则化LDA（RLDA）一种简单的解决Sw矩阵奇异的方法是利用正则化思想在Sw上加一个扰动量，数学表达为其中0，I为一个单位矩阵这种方法的主要问题在于扰动量的选取有难度。如果扰动量太小可能不足以解决奇异问题，太大又会使Sw内包含的判决信息丢失wwSSIPCA+LDA首先用PCA对数据降维，使Sw成为非奇异矩阵，然后再进行LDA将生成式变换与区分式变换结合PCA变换使数据中的信息被“忠实地”保留，同时数据维数得到了压缩，以便消除使Sw奇异的条件难点：没有明确的理论指导PCA降维的维数选择如果PCA维数太低，会丢失过多的鉴别信息如果维数太高，相对来说训练样本会仍显不足，这样即使能解决Sw的奇异问题，也难免会出现过拟合的现象LDA/QR对Hb进行QR分解，得到一个正交矩阵Q和一个上三角矩阵R，然后在Q张成的低维子空间内进行鉴别分析算法分两步完成：bdrRQbrcRR,TTbbwwSQSQSQSQ,bwSS第一步，对Hb进行QR分解，Hb=QR的正交列张成了Hb的秩空间是上三角矩阵第二步，在上运用LDA然后定义:LDA/GSVD通过广义奇异值分解GSVD，用Hb和Hw代替Sb和Sw根据GSVD理论，正交矩阵Y∈Rc*c，Z∈Rn*n，以及非奇异矩阵X∈Rd*d满足如下关系：因此有[,][,]TTbbTTwwYHXΣ0ZHXΣ0IIDDOObwbwbwbw1(,,)twbbrrrdiagD1(,,)twbwrrrdiagD221iiTTbbwwIX的列向量就是矩阵对[Hb,Hw]对应的广义奇异向量，并将其作为基于GSVD的鉴别特征子空间RDMRDM的特点主要有两方面1）将LDA问题转化为同时对角化类内和类间散度矩阵问题2）通过能量适应准则来近似估计12,{,,,}TwndiagSΦΛΦΛΛΛI0对类内散度矩阵Sw进行对角化，得：在对角矩阵上加上一个小的扰动量进行正则化，即（）σ的选择11*,()min()miimnmiiJmmE其中RDM将Sw的能量谱用作选择σ的标准J(m)通过前m个特征值在总能量谱中所占的比例来确定m的值半监督学习问题：样本不足/标注样本不足找到有效的方法，使得只需手工标注少数数据，就能较准确地对全部数据进行自动标注三类算法在聚类过程中利用已标注的数据来引导聚类在对标注样本进行学习之后，首先处理那些有较高置信度的未标注样本，然后迭代地把这些估计加入到标注样本集中将数据看作图上的结点，将数据间的(已知的)相似性看作结点间的初始边长(权重)，应用图的理论对数据进行聚类半监督学习的形式定义1{,,}lxx1CiRy1{,,}lluxx标注样本集合L=标注样本的类别向量用yij=1andyiq=0(qj)表示xi点属于第j类，C为类别数用fi表示，fi是元素值为0或1的C维向量用Y表示已标注样本集的真实类别矩阵用F表示数据集的类别指示矩阵，其类别指示向量设未标注样本集合U=半监督学习:在已知数据集L、U和Y的情况下估计F基于图的算法在图中估计样本的类别函数f，使其满足两个条件：1)对于已标注样本，其真实类别和通过f得到的结果越接近越好2)对于整个样本集，f足够平滑这两个条件可以通过正则化方法得到满足，即在求解的过程中用先验知识对求解过程加以约束，从而获得有意义的解类别估计函数f一般由两项组成，一项是损失函数，用来评价条件1的满足度；另一项是正则化，保证条件2得到满足基于随机场的半监督学习首先在图上定义一个连续的随机场，然后根据能量函数最小化时调和函数的特性获得聚类结果2,1()[()()]2ijijEwijfff()1()EpeZffexp[()]llZEdffYf基于相似点应属于相同类别，得到二次能量函数：式中W={wij