北邮郭军web搜索chapter5

Web搜索

郭军

北京邮电大学

第5章信息过滤基本方法模型学习垃圾邮件及垃圾短信过滤话题检测与追踪系统引言信息过滤的本质是“流环境”下的二元分类流环境：过滤系统处于信息持续新生的环境之中，新的数据源源不断地流经过滤系统二元分类：一类是需要筛选出来的，一类是系统不关心的以模式分类为技术核心，高效高精度地处理数据流IR被检索的文档相对稳定用户查询需求不同IF信息资源动态变化用户需求相对固定IF的研究重点分类器的选择针对特定的应用环境选择分类器模型目前研究较多的是朴素Bayes模型、向量相似度(模板匹配)模型、SVM、k-NN等分类器的学习及优化生成式算法、区分式算法计算效率，类别模型的增量学习和自动演进，半监督学习、特征降维技术基本方法信息过滤系统中常用的分类器Bayes分类器向量距离分类器k近邻分类器SVM系统性能评价Bayes分类器Bayes分类器将分类问题看作统计决策问题，以最小错误率为目标进行分类前提：事先获得各个类别的似然函数，决策时利用Bayes公式计算给定样本特征值条件下各类别的后验概率设随机变量x∈Rd,各类别的似然函数为P(x|ci)，对于某确定样本t,根据Bayes公式：分类方法计算得到各个P(ci|t)后，将样本t分到类别ck中，其中举例：随机选取100封邮件，进行人工标注，其中有30封垃圾邮件和70封非垃圾邮件，对于词“培训”，垃圾邮件中有21封含有该词，非垃圾邮件中有28封含有该词，假定过滤系统只采用该词判别是否为垃圾邮件，问若一封新邮件含有该词，则过滤系统认为该邮件是否是垃圾邮件？对于多个词，如何判别？似然比Rl二元分类问题可以根据似然比Rl来决定t的归属对数似然比：假设x的各维数据之间相互独立；朴素Bayes分类器向量距离分类器向量距离分类器可以看作是Bayes分类器的简化，它用各类别数据的均值向量、方差向量、协方差矩阵等参数近似描述它们的分布特性，利用向量之间的各种距离进行分类，常用的距离尺度有:k近邻分类器也称k-NN分类器(k-NearestNeighbor)最大特点是不需要训练类别模型，而是按某种合理的比例从各类别中抽取样本，用所有抽出的样本构成分类器的总体特征样本对于一个给定的样本t，首先按照某种距离测度找出与其最接近的k个样本，然后根据这k个样本所属类别进行投票SVMSVM是一种以结构风险最小化为目标的二元分类器，在寻找最优分类超平面时不但要求将两类数据隔离，而且要求两类数据距超平面的平均距离最大设线性可分数据集为D维空间中线性判别函数的一般形式为分类超平面方程为系统性能评价评价指标主要包括分类器的精度和速度速度取决于分类器算法的复杂程度，在实际应用中与计算机的硬件性能关系很大精度通过与人工标注结果(groundtruth)进行比较来计算对于二元分类问题，常用的精度指标有准确率召回率F-measurebreak-even点精度指标标注为L类标注为非L类判别为L类ab判别为非L类cd分类与标注对应关系的频次i)准确率(Precision)表示所有被分类器分到类L的数据中正确的所占的比例ii)召回率(Recall)表示所有实际属于L的数据被分类器分到L中的比例iii)平衡点BEP(Break-evenPoint):P和R值是互相影响的:P会随着R的升高而降低，反之亦然。因此，为了更全面地反映分类器的性能，一种做法是选取P和R相等时的值来表征系统性能，这个值叫BEPiv)F值一种把准确率和召回率综合考虑的评价方法，定义如下：模型学习生成式学习典型应用：利用EM算法对GMM的参数进行估计共同特征：每个类模型只用本类的样本进行估计，估计的准则是使模型产生训练样本的可能性最大(最大似然)早期的模型学习主要采用生成式算法区分式学习典型应用:SVM的学习共同特征:由需要相互区分的各类样本共同构成一个模型，通过多类样本的“角力”形成不偏不依的分类面降维变换需要进行学习的降维变换是指变换核（基函数）随被处理数据集变化以获得最佳变换效果的变换(自适应变换)主成分分析PCA(PrincipalComponentAnalysis)独立成分分析ICA(IndependentComponentAnalysis)线性鉴别分析LDA(LinearDiscriminativeAnalysis)希尔伯特—黄变换Hilbert-Huang自适应变换也存在生成式和区分式之分PCA

设随机变量，存在一个样本集，则其均值可估计如下：协方差矩阵可估计如下：求解按降序排列的d个特征值和对应的特征向量，并构成矩阵称为x的PCA变换(也称K-L变换)，则式PCA的性质PCA变换后的变量y是零均值的随机变量，其协方差矩阵为：由于A是列为的特征向量的正交矩阵，所以是对角阵且对角线元素为的特征值，即：由于的非对角元素都是零，所以随机变量y的各维之间是不相关的LDA

LDA的思想是找一个投影方向，使得投影后在低维空间里样本的类间散度较大，类内散度较小x1x2x’LDA的定义(1/3)设Ci为第i类样本的集合，共有c类样本，则样本类内散度矩阵定义为：其中，mi为第i类样本的均值，样本类间散度矩阵定义为：其中为样本集的总体均值向量LDA的定义(2/3):将d维的随机变量x变换到c-1维定义在变换空间中样本的类内和类间散度矩阵：容易证明LDA的定义(3/3)定义如下的准则函数：容易证明，使J(.)最大化的变换矩阵W的列向量由下列等式中的最大特征值对应的特征向量组成：这是一个广义特征值问题，如果Sw是非奇异的，W的列向量就是由矩阵的特征向量组成其中LDA的奇异性LDA是信息过滤中数据降维的核心算法之一在应用中常遇到类内分散度矩阵Sw奇异的问题当数据维数很高时，能够获得的样本数常常相对不足，使得独立的训练样本数N小于数据维数d，而这将导致Sw为奇异矩阵信息过滤所处理的文本、图像、音频等一般都是在高维数据空间中表达的解决LDA奇异性问题时，常先用某种生成式算法对数据进行降维LDA奇异性的解决

主要方法:正则化LDAPCA+LDAPCA+NULL空间LDA/QRLDA/GSVD

正则化LDA（RLDA）一种简单的解决Sw矩阵奇异的方法是利用正则化思想在Sw上加一个扰动量，数学表达为 其中

0，I为一个单位矩阵这种方法的主要问题在于扰动量的选取有难度。如果扰动量太小可能不足以解决奇异问题，太大又会使Sw内包含的判决信息丢失PCA+LDA首先用PCA对数据降维，使Sw成为非奇异矩阵，然后再进行LDA将生成式变换与区分式变换结合PCA变换使数据中的信息被“忠实地”保留，同时数据维数得到了压缩，以便消除使Sw奇异的条件难点：没有明确的理论指导PCA降维的维数选择如果PCA维数太低，会丢失过多的鉴别信息如果维数太高，相对来说训练样本会仍显不足，这样即使能解决Sw的奇异问题，也难免会出现过拟合的现象LDA/QR对Hb进行QR分解，得到一个正交矩阵Q和一个上三角矩阵R，然后在Q张成的低维子空间内进行鉴别分析算法分两步完成：第一步，对Hb进行QR分解，Hb=QR的正交列张成了Hb的秩空间是上三角矩阵第二步，在上运用LDA然后定义:LDA/GSVD

通过广义奇异值分解GSVD，用Hb和Hw代替Sb和Sw根据GSVD理论，正交矩阵Y∈Rc*c，Z∈Rn*n，以及非奇异矩阵X∈Rd*d满足如下关系：因此有X的列向量就是矩阵对[Hb,Hw]对应的广义奇异向量，并将其作为基于GSVD的鉴别特征子空间RDMRDM的特点主要有两方面1）将LDA问题转化为同时对角化类内和类间散度矩阵问题2）通过能量适应准则来近似估计对类内散度矩阵Sw进行对角化，得：在对角矩阵上加上一个小的扰动量进行正则化，即（）σ的选择RDM将Sw的能量谱用作选择σ的标准J(m)通过前m个特征值在总能量谱中所占的比例来确定m的值半监督学习问题：样本不足/标注样本不足找到有效的方法，使得只需手工标注少数数据，就能较准确地对全部数据进行自动标注三类算法在聚类过程中利用已标注的数据来引导聚类在对标注样本进行学习之后，首先处理那些有较高置信度的未标注样本，然后迭代地把这些估计加入到标注样本集中将数据看作图上的结点，将数据间的(已知的)相似性看作结点间的初始边长(权重)，应用图的理论对数据进行聚类半监督学习的形式定义标注样本集合L=标注样本的类别向量用yij=1andyiq=0(qj)表示xi点属于第j类，C为类别数用fi表示，fi是元素值为0或1的C维向量用Y表示已标注样本集的真实类别矩阵用F表示数据集的类别指示矩阵，其类别指示向量设未标注样本集合U=半监督学习:在已知数据集L、U和Y的情况下估计F基于图的算法在图中估计样本的类别函数f，使其满足两个条件：1)对于已标注样本，其真实类别和通过f得到的结果越接近越好2)对于整个样本集，f足够平滑这两个条件可以通过正则化方法得到满足，即在求解的过程中用先验知识对求解过程加以约束，从而获得有意义的解类别估计函数f一般由两项组成，一项是损失函数，用来评价条件1的满足度；另一项是正则化，保证条件2得到满足基于随机场的半监督学习首先在图上定义一个连续的随机场，然后根据能量函数最小化时调和函数的特性获得聚类结果基于相似点应属于相同类别，得到二次能量函数：式中W={wij}是图的权值矩阵，代表结点间的相似性通过已标注数据，可以获得部分f(i)的取值即，如果xi∈L

，则f(i)由yi确定另，利用Gauss随机场赋予f一个概率分布其中β为常数，Z为配分函数令D为一个对角矩阵,，表示点i的度,则定义由此，能量函数可以改写为：Gauss随机场可以改写为：的定义:组合Laplace矩阵基于Gauss随机场的学习(1/2)

上式中的含义与图中的平滑概念是一致的(f(i)取周围点的均值)将权重矩阵W写成分4块的分块矩阵调和函数的解是在满足fl=yl的条件下使Δf

=0其中P为图的转移概率矩阵，P=D-1W在能量函数达到最小的条件下，未标注样本点满足基于Gauss随机场的学习(2/2)

基于局部一致和全局平滑的学习用一个加权图来描述数据集，在满足与标注信息一致的条件下使样本集的类别平滑变化定义图G={V,W}，wij的计算方法如下根据相似度越大类别越可能一致的原则，定义目标函数η是数据集中每个点与其近邻点间的差异度，越小越好优化目标函数聚类结果必须满足已标注的真实类别信息将这些信息表示为等式：A为C×n的系数矩阵，yi为已标注样本i的真实类别向量(行向量)F为n×C的类别指示矩阵b是C×C的对角矩阵，bjj等于标注样本中属于第j类的样本个数最优的类别估计结果就是当xi∈L时，fi=yi因此，半监督学习问题就转化为了如下的最优化问题优化问题的求解令矩阵，上述优化问题可转化为将F取0/1值的条件进行松弛，使其取实数值将优化问题变为标准的二次规划问题，定义Lagrange函数令可求得类别指示向量F的最优实数解为其中演进式学习演进式学习—分类模型随着信息环境的变化而自动演进随机过程(而不是随机变量)动态描述数据分布，使分类模型随着分布的变化而自动演进分类模型永远是动态的，系统通过应用环境中的样本对模型不断进行修正不再试图估计静态的“总体分布”，而只考虑当前时刻随机变量的分布如何从上一时刻的分布演进出来演进学习通过小样本完成，因而可以提高学习效率演进式学习的流程不断地从应用环境中获取新样本进行模型的演进增加自动采集新样本、接收识别(分类)模块的样本反馈、以及演进式模型学习和更新分类模型等过程类别标注样本库中存放从应用环境中自动采集的数据样本和分类器识别后反馈的样本，作为模型演进的数据源模型的演进方法假设S(ti)是随机过程{X(t)}在ti时刻的一个学习样本集相邻时刻学习样本集的关系是:S(ti)=S(ti-1)\E(ti)∪A(ti)

即，S(ti)可以通过从S(ti-1)

中剔除样本集E(ti)后添加样本集A(ti)的方法获得模型演进的关键问题：获得A(ti)和E(ti)的方法利用A(ti)和E(ti)对ti-1时刻的模型进行演进，获得ti时刻的模型|A(ti)|和|E(ti)|的变化规律在t0时刻用N0个样本初始化，演进初期|A(ti)|>>|E(ti)|随着系统的成熟，|A(ti)|和|E(t)|逐步接近tc是系统性能达到设计要求进入常态的时刻，交换的训练样本数为dd的大小与演进周期(ti-ti-1)成正比在演进周期(ti-ti-1)比较短的情况下，|A(ti)|和|E(ti)|都远小于|S(ti-1)|。性能指标影响因素：系统进入常态的时刻dA(ti)和E(ti)的获得ti时刻以随机的方式从采集的样本和反馈的识别样本中选出一个集合N(ti)，从中选出|A(ti)|个识别得分最低的样本组成A(ti)，在S(ti-1)中选出|E(ti)|个识别得分最低的样本组成E(ti)|S(ti)|=|S(ti-1)|+|A(ti)|-|E(ti)|物理意义是通过更换边缘样本来移动学习样本集的类中心。模型演进对于生成式模型，采用ML准则下的增量式EM算法对于区分式模型；可采用基于自适应特征分布变化的adaboost算法需要注意的是，由于自动采集和识别反馈的样本的类别标注是有错误率的，因此在没有人工校对的情况下S(ti)是含噪的垃圾邮件及垃圾短信过滤

垃圾邮件(spam)过滤系统TRECSpam评测的技术是基于内容识别的，这不同于目前在市场上普遍应用的技术，如黑白名单过滤、基于地址分析及跟踪的启发式过滤等文本分类器是TRECSpam技术的核心，统计学习算法是研究的重点过滤器的性能两个指标：Ham错分百分比hm%：被错分到Spam目录中的ham占ham总数的百分比Spam错分百分比sm%：被错分到Ham目录中的spam占spam总数的百分比系统根据邮件为spam的可能性进行过滤若可能性大于阈值t，则将其投入spam目录，否则投入ham目录提高t有利于降低hm%，但会升高sm%；反之，降低t有利于降低sm%，但会升高hm%给出每封邮件的score，可以通过改变t值获得sm%相对hm%的函数关系，这种函数关系的图形表示就是著名的ROC(ReceiverOperatingCharacteristic)曲线Spam过滤器最常见的是SVM和朴素Bayes[Brat05]创新性地将动态数据压缩中的局部匹配预测PPM(PredictionbyPartialMatching)用于Spam过滤PPM是一种自适应概率编码压缩技术每处理被压缩数据的一个符号，PPM的概率模型—P(x|context)都会随之更新每处理完一个符号，都会得到一个新的P(x|context)系统根据P(x|context)获得一个熵编码方案编码方案随着context的演变而自适应调整PPM通过训练数据获得PPM的两个概率模型P(x|context-spam)和P(x|context-ham)与常见的方法的差别：PPM假设信源产生符号的过程符合k阶Markov过程PPM模型会随着处理的进行而自动演进，这恰好应对了Spam特征的演进性在PPM中，通常约定用-1阶模式指出系统的字符集A，并且假定所有字符以相同的概率1/|A|出现未出现过的转移模式用Esc表示例:“abracadabra”的2阶PPM模型垃圾短信的过滤短信的基本特点：长度短，最长不能超过140个ASCII字符或70个汉字不完整(省略、指代、简化等)、不规范(用词另类、语法随意等)短信分类不统一运营商：订阅（由SP提供的）/手写（由手机用户手工输入的）用户：私人/广告安全部门：合法/非法发送形式：SPMU/UU/UMU发送内容：普通短信/垃圾短信/异常短信细分类：聊天短信、问候短信、祝福短信、娱乐短信、新闻短信、理财短信基于正则表达式的分类正则表达式(RegularExpression)由数学家StephenKleene于1956年提出在许多脚本语言中得到支持，如Perl、PHP、JavaScript，已经被国际组织ISO和OpenGroup标准化正则表达式由模式修正符、元字符、子模式、量词和断言等元素组成，通过一系列模式对字符串进行匹配快速地分析大量的文本以找到特定的字符模式，提取、编辑、替换或删除字符串基于统计的分类特征抽取——主要采用VSM和n-gram模型构造一个词的集合来很好覆盖短信中出现的词汇分词词集合的选择是短信特征抽取的关键简便的方法是以字为单位进行处理基于单字特征的Bayes分类器TDT系统Topic:特指在特定时间特定地点发生的事件，而非一般意义的事件类例：“汶川地震”VS“地震”一个话题或事件，会有多个相关的报道(story)TDT的任务报道分割将一个连续的文本流划分为一个个报道事件检测回顾式检测/在线式检测事件跟踪将新产生的报道与系统已知的事件联系起来给定目标事件的条件下判断每个后续报道是否在讨论这个目标事件报道分割算法的评价一方面是直接评价其对报道边界定位的准确性另一方面是间接评价其对事件追踪的支持能力基于HMM进行报道分割基于话题转换的概率进行分割基于局部语境分析LCA进行报道分割将句子转换为LCA词，对其索引后判断报道边界将视频分割应用于报道分割基于LCA方法的关键要素基于内容的特征:一对语言模型，用于帮助判断话题是否大幅改变在线自适应语言模型VS离线静态语言模型表示局部语境的语言学和结构特征的词汇特征使用各个词的位置偏移量对词的特征进行编码以更精细的粒度对与分割边界相关的词进行判断增量式地选择最佳的词汇特征的学习算法，并将词汇特征与语言模型相结合形成统一的统计模型增量式地构建一个越来越详细的模型，对分割边界设置的正确性进行概率估计事件检测在新闻流中标识出新的或是以前没有标识的事件本质：无监督的学习任务模式：回顾式/在线式回顾式的输入是整个文本集，输出是对文本集一簇簇的划分在线式的输入是按时间顺序的实时报道流，系