《模式识别原理与应用》课件第11章.ppt

1、第11章文本分类第第11章文章文 本本 分分 类类11.1文本分类技术文本分类技术11.2垃圾邮件识别技术垃圾邮件识别技术11.3网页分类技术网页分类技术习题习题第11章文本分类11.1文本分类技术文本分类技术11.1.1文本分类流程文本分类流程文本分类的流程图如图11-1所示,它包含中文分词、特征提取、向量表示、分类器等四大部分。首先,收集大量的包含各种信息的文本语料,形成训练数据集,并对其进行人工分类;其次,对训练数据进行中文分词(对英文文本不需要分词)、特征提取、向量表示,形成特征向量;再次,选择合适的分类器模型,对训练数据的特征向量进行训练,得到有效的分类器;最后,利用训练好的分类器对

2、待分类的文本进行分类。第11章文本分类图 11-1文本分类流程第11章文本分类11.1.2文本预处理文本预处理1.中文分词中文分词中文文本是由字连接在一起组成的。在文本处理中,中文文本需要先分割成一个个有意义的词,这就是中文分词。对于英文,就是识别出空格(多个空格可以看成是一个空格),并把它作为词的分隔符。现有的分词算法分为三大类:基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。第11章文本分类(1)基于字符串匹配的分词方法又叫做机械分词方法,它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配,若在词典中找到某个字符串,则匹配成功(识别出一个词)。常

3、用的几种机械分词方法有正向最大匹配、逆向最大匹配、最少切分(使每一句中切出的词数最小)等。第11章文本分类(2)基于理解的分词方法是利用汉语的语法知识和语义知识及心理学知识进行分词,需要建立分词数据库、知识库和推理机。由于此方法需要使用大量的语言知识和信息,目前这种系统还处在试验阶段。第11章文本分类(3)基于统计的分词方法是根据字与字相邻共现的频率能够较好地反映成词的可信度这一点,对语料中相邻共现的各个字的组合的频度进行统计,计算它们的互现信息。这种方法只需对语料中的字组频度进行统计,不需要切分词典,因而又叫做无词典分词法或统计取词方法。这种方法增加了空间复杂度。第11章文本分类衡量自动分词

4、技术的主要指标是切分精度和切分速度。针对信息检索与分类/聚类系统来说,分词技术的主要问题是确定词的颗粒度大小、对专用术语的识别、判别词与词之间的语义关联、对未登录词的处理等。可以先采用最大匹配、最短路径、概率统计等方法,得到一个词语粗分结果,然后再对粗分结果进行歧义词排除、未登录词识别等处理。第11章文本分类2.文本表示模型文本表示模型文本表示模型主要研究选择计算机能够识别的模型,用其来完整的表示文本内容。目前,具有代表性的文本表示模型有布尔模型(Boolean Model)、向量空间模型(Vector Space Model,VSM)、概率模型(Probabilistic Model)等。向

5、量空间模型目前已被成功地应用于著名的文本检索系统SMART中。一些研究表明向量空间模型在处理大规模文本方面有很强的优势,它逐渐成为最简便、最高效的文本表示模型之一。向量空间模型的基本概念如下:第11章文本分类(1)文本。本书泛指一般的文本或者文本中的段落、句群或者句子,通常指的是一篇文章。尽管文本可以是多媒体对象,但是在本书的讨论中,只认为是文本对象。(2)特征项。文本的内容由一些特征项来表达,一般由文本所含有的基本语言单位(字、词、词组或短语等)来表示,即文本可以表示为D(t1,t2,tn),其中,tk表示各个特征项,每个特征项表示文本的一个维度。第11章文本分类(3)特征项权重。在一个文本

6、中,每个特征项都被赋予一个权重wk,以表示这个特征项在该文本中的重要程度。这样文本就表示为 1122(,;,;,)nnDD t w t wtw(11-1)其中,特征项tk的权重为wk,1kn。第11章文本分类(4)向量空间模型。给定一个文本D=D(t1,w1;t2,w2;tn,wn),由于tk在文本中既可以重复出现又应该有先后次序的关系,分析起来有一定的难度,为了简化分析,可以暂不考虑tk在文本中的先后次序,但要求tk互异(即没有重复)。这时可以把t1,t2,tn 看成一个n维的坐标系,而w1,w2，,wn为相应的坐标值,因此,一个文本就表示为n维空间的一个向量,称D=D(w1,w2,wn)为

7、文本D的向量表示或向量空间模型。第11章文本分类(5)相似度度量。两个文本D1和D2之间的相关程度常常用它们的相似度Sim(D1,D2)来度量。在向量空间模型下,可以借助向量之间的某种距离来表示文本间的相似度。常用的是采用向量之间的内积来计算相似度,定义式如下:12121(,)nkkkSim D Dw w(11-2)第11章文本分类或者采用夹角余弦计算,定义式如下:12112221211(,)cos()()nkkknnkkkkw wSim D Dww(11-3)夹角余弦公式忽略了各个向量的绝对长度,着重从形状考虑它们之间的关系,当两个向量方向相近时,夹角余弦值较大,反之则较小。本节所涉及的文本

8、之间的相似度均采用向量之间的夹角余弦来计算。向量空间模型如图11-2所示。第11章文本分类图 11-2向量空间模型第11章文本分类向量空间模型的最大优点在于把文本内容简化为特征与其权重的向量表示,把对文本内容的处理简化成向量空间的向量运算,使得问题的难度大大降低了。向量空间模型表达效果的优劣,直接依赖于特征项的选择和特征加权方式。选取特征项主要有以下两条原则:第11章文本分类(1)应当选择包含文本信息多的,对文本的表现能力较强的语言单位作为特征项。特征项可以是文本中基本的语言单位,例如单字、词、词组或者短语等多个层次,也可以是更高层次的单元,例如概念等。层次越高,包含的文本信息也越多,能更好地

9、描述文本内容,同时存在的问题就是它可能需要复杂的附加处理,比如,对汉语特征,如果选择词作为特征项,则首先需要先进行中文分词处理,而中文分词是一个比较复杂的处理过程。第11章文本分类(2)特征项的提取过程应当比较容易,时间和空间开销都不应当大。对特征项的选择问题,许多学者做了研究。在文本分类领域,通过对使用单词、词组、聚类单词和聚类词组作为特征项所做的实验比较分析,结果表明单词特征项作为文本特征项,不仅方法简单,而且具有较高的分类精确度。第11章文本分类如何用选择的特征项来更好地描述文本内容？向量空间模型中用特征的权重来表示一个文本的内涵,或者称为内容,即D=D(w1,w2,wn),w1,w2,

10、wn为相应特征t1,t2,tn在n维向量空间的坐标值。文本描述的权重计算的准则是要最大限度地区分不同的文档。目前大多数特征权重的计算方法是基于下面两个准则或者假设:第11章文本分类(1)一个特征在文本中出现的范围越广,说明该特征区分文本之间区别的能力越低。(2)一个特征在一个特定文本中出现的频率越高,说明该特征区分这个文本之间区别的能力越强。特征项权重的计算一般分为两种:一种是由专家或者用户根据自己的经验与所掌握的领域知识,人为地赋权值,这种办法随意性较大,很难适用于大规模真实文本的处理;另一种是运用统计的方法,也就是用文本的统计信息(如词频等)来计算项的权重。第11章文本分类运用统计的方法有

11、布尔频率法和TFIDF算法。布尔频率法的规则是:如果特征项tk在文本Di中出现,就记权值wik为1,否则,wik为0。这种方法无法体现特征在文本中的作用程度。TFIDF(Terms Frequency Inverse Document Frequency)算法利用词条在文档中出现的频率TF和每个特征项在整个数据集文档的反向文档频率IDF来计算权值。用tfik(Term Frequency)表示特征项tk在文本Di中的出现次数,idfk(Inverse Document Frequency)表示特征项tk的反向文档频数,TFIDF公式定义为 第11章文本分类ikikkwtfidf(11-4)式中

12、:tfik是一个局部统计量,它在不同文本中有不同的值;反向文档频率idfk是一个全局统计量,反映了一个给定的词条在整个文档集中的分布情况。IDF的原始定义为 logkkNidfn(11-5)第11章文本分类其中:N表示整个集合中包括的文档数;nk是集合中出现特征项tk的文档数。可以看出,包含给定词条的文档数越少,IDF的值就越大;如果文档集中的每篇文档都包含给定的词条,则idf的值等于0。在实际的应用中,为了避免0值的出现,将式(11-5)进行改进,即 logkkNidfcn(11-6)第11章文本分类其中,c(0,1)为常数,目前较为常用的公式为 log0.01kkNidfn(11-7)如果

13、考虑到文本长度对权值的影响,还应该对特征项权值公式做归一化处理,将各权值规范到区间0,1,即 21log0.01log0.01ikkiknikkkNtfnWNtfn(11-8)第11章文本分类TFIDF算法是一种经验公式,并没有坚实的理论基础。但是,多年的实践表明,式(11-8)是文本处理中的一个有效工具,在信息检索等诸多领域都得到了广泛应用。3.特征空间降维特征空间降维采用向量空间模型进行文本描述时,每一个不同的特征都作为特征空间中的一维,每一个文本都是空间中的一个向量,这种描述方法简单而且直接,但同时也使得特征空间变得高维,致使文本分类的性能急剧下降。为了解决这个问题，必须降维,目前采用的

14、技术主要有特征选择和特征提取。第11章文本分类特征提取方法主要是采用代数的方法进行特征空间降维,主要方法有主成分分析(Principal Component Analysis)、奇异值分解(Singular Value Decomposition)等。特征选择是构造一个特征评估函数,根据特征评估函数对各个特征进行独立的评估,然后按照评估值的大小排序,最后选择评估值大于某个设定阈值的特征作为最优特征。第11章文本分类文本分类中,通常使用的特征评估函数有信息增益(Information Gain)、期望交叉熵(Expected Cross Entropy)、文档频率(Document Freque

15、ncy)、文本证据权(the Weight of Evidence for Text)、开方拟合检验(2statistic)、优势率(Odd Ratio)、互信息(Mutual Information)等。每一种特征选择方法对应一种特征评估函数。第11章文本分类用c1,c2,ck表示文本的k个类;t表示某个特征;P(t)表示特征t出现的概率;表示特征t不出现的概率;P(cj)表示第j类的出现概率;P(cj,t)表示特征t与类别cj共同出现的联合概率;表示特征t不与类别cj共同出现的联合概率。一般采用两种概率估算方式,分别是布尔概率估算方式和词频概率估算方式。()P t(,)jP ct第11章文

16、本分类采用布尔概率估算方式,可得:(1)P(t)是训练文本集合中出现特征t的文本个数与总的文本个数的比值;(2)是训练文本集合中不出现特征t的文本个数与总的文本个数的比值;(3)P(cj)是第cj类的文本总数与训练文本总数的比值;(4)P(cj,t)是属于cj类且含有特征t的文本总数与训练文本总数的比值;(5)是属于cj类且不含特征t的文本个数与训练文本总数的比值。()P t(,)jP ct第11章文本分类采用词频概率估算方式,可得:(1)P(t)是训练文本集合中出现特征t的个数与总的特征个数的比值;(2)是训练文本集合出现的不包含特征t的个数与总的特征个数的比值;(3)P(cj)是第cj类文

17、本的特征总数与所有特征总数的比值;(4)P(cj,t)是在cj类文本中出现特征t的个数与总的特征个数的比值;(5)是在cj类文本出现的不包含特征t的特征个数与总的特征个数的比值。()P t(,)jP ct第11章文本分类下面定义各种特征评估函数。1)文档频率阈值法文档频率阈值法是利用特征的文档频率进行特征选择。特征t的文档频率是指包含这个特征的训练文本的总数,定义式如下:1()()kjjt cDF t(11-9)其中,t(cj)为cj类中包含特征t的训练文本的个数。第11章文本分类运用文档频率阈值法进行特征选择时,首先计算各个特征的文档频率,然后将文档频率大于某个设定阈值的特征选为最优特征。文

18、档频率阈值法基于这样一种假设:对于一个类而言,出现频率小的特征是没有任何意义的,删除它们对分类结果不会造成不利的影响。这种假设显然有其局限性,在一些信息检索的研究中,频率小的词可能具有很大的类别区分度。文档频率阈值法是最简单的一种文本特征选择方法,它的最大优势就是速度快,时间复杂度和文本数目成线性关系,所以非常适合应用到大规模文本特征集合的特征选择,同时它也是最有效的文本特征选择方法之一。第11章文本分类2)期望交叉熵法期望交叉熵法是利用期望交叉熵进行特征选择。期望交叉熵考虑了特征t出现的概率,同时也考虑了特征t与类别之间的关系,定义式如下:1()(,)(,)log()()kjjjjECE t

19、P c tP c tP c P t(11-10)第11章文本分类3)信息增益法信息增益法是利用信息增益进行特征选择。信息增益法经常被应用于机器学习领域。信息增益法是通过一个特征t是否出现在文本中来推算该特征对整个分类所提供的信息量,定义为特征t在文本出现前后的信息熵之差,定义式如下:11(,)(,)(,)log(,)log()()()()()kkjjjjjjjjP c tP c tP c tP c tP cP cP tIG tP t(11-11)第11章文本分类它与期望交叉熵的区别是考虑了特征不出现在同一类别文本中对类别的影响,因为有时特征不出现也可能对判断文本类别有贡献。4)文本证据权法文本

20、证据权法是利用文本证据权进行特征选择。文本证据权比较了类cj出现的概率与在给定特征t下类cj出现的条件概率之间的差别,定义式如下:第11章文本分类1()log(,)(1()()()(,)()()kjjjjjjP cP c tP cP cP tP c tWE tP t(11-12)如果特征和类别之间为强相关(P(cj|t)值大),且类别出现的概率小,则说明此特征类别区分度大,计算出来的文本证据权值大,可选择该特征作为最优特征。如果特征和类别之间为弱相关(P(cj|t)值小),且类别出现的概率大,则说明此特征类别区分度小,计算出来的文本证据权值小,不会被选为最优特征。第11章文本分类5)开方拟合检

21、验法开方拟合检验法是利用开方拟合检验进行特征选择。开方拟合检验是衡量类cj和特征t之间的独立性的缺乏程度,或者称为统计相关性。开方拟合检验值越大,说明类cj和特征t之间的独立性越小,相关性越大,特征t携带的类cj的信息也就越多。特殊的情况,当特征t与类cj之间独立时,开方拟合检验值为0,此时特征t不包含任何与类别cj有关的信息,定义式如下:第11章文本分类22()(,)()()()()jNADCBc tACBDABCD(11-13)其中,A、B、C、D表示文本的个数,如表11-1所示。式(11-13)计算的是类cj和特征t的开方拟合检验值,特征t对于整个训练文本的开方拟合检验值是其相对于所有类

22、的开方拟合检验值的综合,定义式如下:221()()(,)kjjjtP cc t(11-14)第11章文本分类表表11-1开方拟合检验法中开方拟合检验法中A、B、C、D的含义的含义 类cj的文本个数非cj的文本个数特征t出现 A B特征t不出现 C D第11章文本分类6)互信息法互信息法是利用互信息进行特征选择。特征t对类别cj的互信息为二者的互信息量,定义式如下:(,)(,)log()()jjjP c tMI c tP t P c(11-15)互信息衡量特征t和类cj之间独立的统计关系,MI的值越大,说明特征t和类cj共同出现的程度越大。第11章文本分类1(,)()()log()()kjjjj

23、P c tMI tP cP t P c(11-16)7)优势率法 优势率法是利用优势率进行特征选择,它只能用于二分类问题,定义式如下:100110(,)()(,)()log()(,)(,)P c t P cP c tOR tP cP c t P c t(11-17)第11章文本分类11.1.3分类器分类器文本分类器的任务是在给定的分类体系前提下,根据文本的内容自动确定文本关联的类别。文本分类是一个映射的过程,它将未标明类别的文本映射到已有的类别中。该映射可以是一对一映射,也可以是一对多的映射。文本分类的映射规则是系统根据已经掌握的若干分类技术,总结出分类的规律性而建立的类别公式和判别规则。这样

24、,用户不但能够方便地浏览文档,而且可以通过限制搜索范围来使文档的查找更为容易。利用文本分类技术可以对大量文档进行快速、有效的自动分类。第11章文本分类1.K-近邻分类器近邻分类器KNN算法的思想很简单:给定一篇待分类的文档,系统在训练集中找到与之距离最近的文档,这K个文档中的大多数文档所在的类别就是待分类文档的类别。假设有一个任意的输入文档,系统在训练文档中对它最近邻居排序,并采用排列在最前面的K个文档来预测输入文档的类。邻居文档与待分类的新文档间的相似值被当作类的权重,K个最近邻居的类权重之和被用于类的排序。第11章文本分类2.SVM分类器分类器文本学习以文档或文本字段为学习对象,通过大量文

25、档集的训练,系统掌握文档的类别特征,获得识别新文档的规则和模型,从而为分类器提供分类的知识。文本学习是学习分类器内含的一种机制。分类器被输入一组文档,学习机制根据文档信息内容来进行监督,学习形成的分类器就可用于识别新文档。最典型的方法就是SVM分类器。第11章文本分类3.贝叶斯分类器贝叶斯分类器超文本的结构是半自动化的,且多数页面文本内容短小,如果用平常的文本分类器去分类,则效果明显不好。目前对超文本的分类,主要涉及页面的纯文本分类、超文本结构信息分类和协调分类等。纯文本分类方法没有用超文本页面中的任何结构信息,只是将此页面当作一个普通文本看待,用一般的文本分类方法进行分类。超文本页面中含有大

26、量有用的结构信息,这些信息可能包括该页面标题、重要的子标题等重要内容。如果将这些结构信息用于分类,一方面可以提高分类精度,另一方面可以减少计算量。最典型的综合协调法就是朴素贝叶斯分类器法。第11章文本分类贝叶斯分类器的原理是计算文本d属于某个类别cj的条件概率P(cj|d),进而将文本d分到概率最大的类别中去。计算P(cj|d)时,利用贝叶斯公式:(|)()(|)()jjjP d c P cP cdP d(11-18)其中:P(cj)是类的先验概率;P(d|cj)是类的条件概率。第11章文本分类对同一篇文本,P(d)是一定的,在分类的过程中可以忽略。如果设文本d可以表示为特征集合(t1,t2,

27、tn),n为特征个数,贝叶斯分类器中假定各特征项之间是相互独立,则有 121(|)(,|)(|)njnjijiP d cP t ttcP tc(11-19)式中,P(cj)和P(ti|cj)都利用训练集加以估计。假定Nj表示训练样本集中属于第cj类的文本总数,N表示训练样本集的文本总数,则先验概率P(cj)为 第11章文本分类()jjP cNN(j=1,2,k)(11-20)()jiijjctP t cc类的所有文本中特征词 的出现次数类的所有文本中出现的特征词总数(i=1,2,n;j=1,2,k)(11-21)最大后验概率准则如下:如果1(|)max(|)jii kP cdP cd 则d属于

28、cj类。第11章文本分类11.2垃圾邮件识别技术垃圾邮件识别技术电子邮件由于其快捷、方便、高效的特点,已经成为现代通信方式的重要组成部分。然而随着人们日益广泛地使用电子邮件,令人厌烦的不请自来的垃圾邮件日益泛滥。2006年1月，CCNNIC(中国互联网络信息中心)发布的第十六次中国互联网发展状况统计报告显示,中国网民平均每周收到邮件16.8封,其中六成以上是垃圾邮件。第11章文本分类什么是垃圾邮件？至今没有一个统一定义,中国互联网协会定义的垃圾邮件是指包括下述属性的电子邮件:(1)收件人事先没有提出要求或者不同意接收的广告、电子刊物以及各种形式的宣传邮件;(2)收件人无法拒收的电子邮件;(3)

29、隐藏发件人身份、地址、标题等信息的电子邮件;(4)含有虚假的信息源、发件人、路由等信息的电子邮件。第11章文本分类垃圾邮件的存在干扰了人们正常的生活,浪费了用户的时间和金钱。通常人们判断一封垃圾邮件所需要时间大约为10 s,用户每天都需要花费一段时间来处理垃圾邮件,对于全球用户来讲被浪费的时间是不可估计的,同时有调查表明下载垃圾邮件所需要的上网费和电话费,每年大约被浪费掉100亿美元以上。第11章文本分类垃圾邮件占用了大量传输、存储和运算资源,影响了网络的正常运行,给相关企业带来了巨大的经济损失。业内人事分析:一旦垃圾邮件占到了网络总数据流量的1/3以上,将会造成巨大的存储需求,甚至对信息安全

30、系统的有效性造成威胁。AOL、雅虎、Hotmail等Internet服务提供商(ISP)所处理的邮件,垃圾邮件已超过50%,仅仅考虑和处理这些垃圾邮件就会花费大量的人力物力。据估计,全世界企业大约用80到100亿美元来处理垃圾邮件。第11章文本分类此外,垃圾邮件的存在给社会带来了不稳定因素。有些人利用电子邮件方便快捷、价格低廉以及开放无国界性的特点传播反动、黄色、病毒等不良信息,给网络安全以及社会的发展和稳定带来很大的危害。第11章文本分类要解决垃圾邮件泛滥问题必须综合法律、技术等多种手段。许多国家和地区都制定了反垃圾邮件的法律和法规,例如我国制定的网络安全法、电子商务法等法律,这些法律法规都

31、对减少垃圾邮件的数量起到了一定的作用。但是Internet是一个开放的全球范围的网络,法律法规的作用受到诸多不确定因素的影响，因此,目前大多采用技术手段来防治垃圾邮件,统称为反垃圾邮件技术。垃圾邮件过滤技术是其主流技术,下面将详细介绍该技术的相关内容。第11章文本分类11.2.1服务器与客户端过滤服务器与客户端过滤电子邮件的协议和内容格式由RFC(Request for Comments)的几个文档规定。RFC 821规定了SMTP(简单传输协议),定义了发送邮件协议。RFC 822规定了邮件文本从主机传送到主机的格式化定义。RFC 1725规定了POP3(邮局协议版本3),定义了从POP3服

32、务器收取邮件的机制。MIME(多用途互联网邮件扩展协议)是RFC 822的扩展,支持多种非文本文件的传送,目前几乎所有的电子邮件系统都支持此标准。Internet电子邮件系统概念模型如图11-3所示。第11章文本分类图 11-3Internet电子邮件系统概念模型第11章文本分类下面解释图11-3中的几个概念。MUA(Mail User Agent):邮件用户代理,为客户端程序。MUA是用户用来发送和接收电子邮件的客户端程序,负责为用户提供处理电子邮件的界面,例如Outlook。MUA将邮件系统的复杂性与用户隔离开。第11章文本分类MTA(Mail Transfer Agent):邮件传输代理

33、,为服务器端程序。MTA负责从客户端或者另一个MTA接收电子邮件,并判断电子邮件的目的地是本地地址还是非本地地址。如果为本地地址,则将电子邮件交给本地MDA,由本地MDA负责将电子邮件传递到邮箱。如果为非本地地址,则将电子邮件传给远程的MDA,由远程MDA将邮件传给下一个MTA。MDA(Mail Delivery Agent):邮件投递代理。MDA是MTA的附带服务器程序,用于将电子邮件投递到目的邮箱或者投递给远程MTA。第11章文本分类MRA(Mail Retrieval Agent):邮件获取代理,为服务器端程序,用于MUA从邮件服务器上获取电子邮件。根据图11-3,给出电子邮件的传递过程

34、如下:(1)电子邮件发送方利用MUA编辑电子邮件。(2)通过与MTA进行SMTP会话,将电子邮件交给MTA。(3)MTA根据电子邮件地址判断电子邮件的目的地是否为本地。如果目的地是本地邮箱,则调用本地MDA,将电子邮件发送到本地邮箱;如果不是本地邮箱,则调用远程MDA，通过SMTP会话,将电子邮件传递给下一个MTA。第11章文本分类(4)接收到新电子邮件的MTA重复(3),直至电子邮件投递到目的邮箱中。(5)邮箱用户可以通过驻留在服务器上的MUA查看邮箱接收的电子邮件,也可以使用远程计算机上的MUA通过POP协议或者IMAP协议获取查看电子邮件。根据上述电子邮件传递过程,垃圾邮件过滤可以在三个

35、不同位置进行:(1)用户端过滤MUA过滤,在客户端过滤。(2)邮件上传阶段过滤MTA过滤,即在MUA与MTA 会话过程中对邮件进行检测,判断是否为垃圾邮件，并进行过滤。第11章文本分类(3)邮件递送阶段过滤MDA从MTA中接收邮件,在本地或者远程投递时进行检查,判断是否为垃圾邮件，并进行过滤。垃圾邮件过滤技术一般都同时适用于客户端和服务器端的垃圾邮件过滤,技术的应用研究在推进和发展阶段主要集中于三个方面:(1)利用IP或域名的“黑白名单”进行的邮件限制或过滤,例如利用黑名单过滤、用户自定义邮件白通道等。第11章文本分类(2)基于垃圾邮件的特征分析、规则提取的规则匹配过滤方法,例如关键词过滤技术

36、、信头分析、群发过滤等。(3)利用文本分类和统计算法进行垃圾邮件的检测。比较有代表的是贝叶斯过滤器,它是贝叶斯文本分类方法应用于垃圾邮件过滤中的结果,过滤器通过对邮件文本内容的学习来实现垃圾邮件的自动过滤。第11章文本分类11.2.2黑白名单过滤技术黑白名单过滤技术利用“黑白名单”过滤技术进行邮件限制或过滤,是一种最传统的方式。通过黑名单技术对垃圾邮件进行屏蔽,通过白名单技术对允许的邮件进行放行。黑白名单内容可以是电子邮件地址、IP地址或域名等。网站、运营商、企业和个人都可以参与制定和维护名单,拦截已知垃圾邮件发送者的所有邮件。黑名单一般由比较权威的组织所提供,例如中国反垃圾邮件网站(http

37、:/)建立了自己的黑名单,为大众提供服务。第11章文本分类黑白名单技术的优点是过滤简单、速度快。该技术的缺点首先是无法区分垃圾邮件和合法邮件,只是机械地进行过滤,过滤效果差。例如,如果垃圾邮件发送者改变了地址,黑名单又没有跟上,就可能使垃圾邮件“漏网”;如果自己的朋友改变了邮箱地址,而自己没有将其加入白名单中,那就可能收不到他的信,阻止掉了合法邮件是用户不能忍受的。其次,Internet是一个跨国家、无边界的网络,对于黑名单技术而言要想起到好的效果,需要各个国家之间的合作,才能确保垃圾邮件制造者无处隐匿。第11章文本分类11.2.3规则匹配过滤技术规则匹配过滤技术规则匹配过滤技术是根据垃圾邮件

38、的某些特征,首先人工设定一些规则,通过这些规则来描述垃圾邮件,当邮件符合这些规则中的一条或几条时,则判定其为垃圾邮件。下面主要介绍规则匹配过滤技术中的群发过滤和关键词过滤。第11章文本分类1.群发过滤群发过滤垃圾邮件发送者为了降低发送垃圾邮件的成本,大多使用群发功能,使得邮件服务器在一段较短时间内收到来自同一个地址的大量邮件,或者在一段较短时间内收到不同地址发送过来的大量内容相同的邮件,这些邮件都被认为是垃圾邮件而进行过滤。缺点是当一个用户大批量发送正常邮件时,正常邮件很可能被误判为垃圾邮件。第11章文本分类2.关键词过滤关键词过滤通常的做法是创建一些简单或复杂的,能够反映垃圾邮件特征的单词表

39、来识别和处理垃圾邮件。比如某些关键词大量出现在垃圾邮件中,如一些病毒的邮件标题(如test)、一些商业广告的标题(如“free”、“赠送”、“免费”等)。它的基础是必须创建一个庞大的过滤关键词列表。这种技术缺陷很明显,过滤的能力同关键词有明显联系。当然,系统采用这种技术来处理邮件时消耗的系统资源会比较多,并且,一般躲避关键词的技术(如拆词、组词)就很容易绕过过滤,例如,我们知道带有标题“Free”的信件是垃圾邮件,但是这种技术可能会因为字母之间有空格而放过它,所以误判率较高。第11章文本分类11.2.4垃圾邮件内容过滤技术垃圾邮件内容过滤技术由于邮件中很大一部分信息集中于邮件的文本中,因此可以

40、通过对文本的分析来识别邮件是否为垃圾邮件,目前采用的识别技术主要是将文本分类技术引入到垃圾邮件过滤中,将邮件自动分类为垃圾邮件和合法邮件。垃圾邮件内容过滤的实质是二分类问题,主要包括训练过程和过滤过程,其基本框图如图11-4所示。第11章文本分类图 11-4垃圾邮件内容过滤的基本框图第11章文本分类(1)输入/输出。训练过程输入为由专家分好类别的垃圾邮件训练语料库,输出为构造的垃圾邮件过滤器。过滤过程输入为待过滤的垃圾邮件,输出为待过滤邮件的类别(合法邮件类或垃圾邮件类)。(2)预处理。预处理主要通过对垃圾邮件训练语料库文本进行扫描,从而采集到邮件原始特征集合,为邮件文本表示做好准备,使邮件文

41、本信息能够表示成计算机可以处理的结构化模型。第11章文本分类(3)特征提取。特征提取主要是采用特征空间降维技术来选取最优特征集合(即能够尽量完整描述文本信息的尽可能少的特征集合),然后对最优特征集合中的每个特征进行适当的加权,利用处理好的最优特征将邮件文本表示成计算机可以处理的结构化模型,特征提取是垃圾邮件过滤中重要的一步,是正确过滤的基础。第11章文本分类(4)训练与过滤。训练主要是各种垃圾邮件过滤方法的实现。过滤主要是利用加权后的最优特征形成待过滤邮件文本向量,然后应用训练结果和相应的过滤方法,对待过滤邮件进行过滤。此外,构建实际垃圾邮件过滤系统时还应包括反馈学习过程。因为垃圾邮件的内容、

42、形式以及用户需求在不断变化。垃圾邮件过滤系统需要通过反馈学习来自动更新垃圾邮件过滤器。第11章文本分类在垃圾邮件过滤领域中,有人研究了英文邮件文本特征项的选择,对单词、词组等特征进行测试,结果显示使用单词和词组作为特征项下的垃圾邮件过滤效果相差不大。由于单词特征项的提取只需要根据英文单词之间的空格或符号进行,比词组的提取更容易,一般直接采用单词作为邮件文本的特征项。在垃圾邮件过滤中,特征选择大都采用信息增益法。第11章文本分类垃圾邮件内容过滤技术不像规则匹配技术,不需要预先设定规则,不需要分析邮件句法或内容的含义,而是采用某种文本分类算法对已知的垃圾邮件样本进行学习,提取垃圾邮件的特征,构造过

43、滤器,然后运用此过滤器,对待过滤的新的邮件,机器自动判断过滤垃圾邮件。目前,垃圾邮件内容过滤技术的研究主要集中在将已有的文本分类方法应用于垃圾邮件过滤中。应用于垃圾邮件过滤中的文本分类方法(又称垃圾邮件过滤方法)主要有判别分析中的K近邻判别法(KNN方法)、贝叶斯判别法、支持向量机分类法等。第11章文本分类从实际应用来看,基于贝叶斯分类方法的垃圾邮件过滤技术已被263、Yahoo等多家邮件服务商采用。此外,市场上还出现了一些邮件客户端工具,帮助用户定义和训练个性化的垃圾邮件过滤器,例如,国内最著名的 Internet 电子邮件客户端软件Foxmail 5.0,其反垃圾邮件功能中就采用了该技术。

44、第11章文本分类11.3网页分类技术网页分类技术11.3.1网页分类流程网页分类流程网页分类是先将网页转化为文档形式,去除网页中的相关噪声,提取其中的纯文本信息;再利用文本分类技术对纯文本信息进行分类,从而实现网页的分类。网页分类的流程框图如图11-5所示,其中,在文本分类流程框图(图11-1)中添加了“网页文本内容提取”。第11章文本分类图 11-5网页分类流程第11章文本分类在浏览Internet的网页时,会发现它们通常包含两部分内容:一部分内容体现的是网页的主题信息,比如一张新闻网页中的新闻部分,将这部分内容称为“主题”内容;另一部分则是与主题内容无关的导航条、广告信息、版权信息以及调查

45、问卷等内容,称之为“噪声”内容。第11章文本分类根据噪声数据的粒度,一般将其分为两大类:(1)全局噪声(Global Noise):这种噪声具有极大的粒度,通常不小于一个网页,一般包括数据镜像站点、合法/不合法的冗余网页等。(2)局部噪声(Local Noise):指网页内的噪声,这些数据通常伴随着网页的主要内容,例如广告、导航信息等。第11章文本分类在网页分类中,一般所获得的网页要首先经过全局噪声的去除,也就是对网页数据进行去空和去重处理;然后再进行局部噪声的去除。而通常网页文本内容提取所关心的是局部噪声的有效去除和文本内容的提取,因此下面主要分析局部噪声的去除。第11章文本分类噪声内容通常

46、分布在主题内容周围,有时也夹杂在主题内容中间,但它们并无内容相关性。从图11-6可以看出一个新闻网页一般由下面几个部分组成:最上方的导航链接,例如“首页”、“娱乐”;“无处不在”的广告链接;检索界面;版权信息;页面主题区。第11章文本分类图 11-6页面的信息示意图第11章文本分类需要特别注意的一个现象是:现在许多站点的收入都来自于广告,而且随着因特网的普及,这个现象会越来越明显。设计者在设计广告时考虑的首要问题是如何吸引用户的“眼球”。因为图像相比文字具有更强的表现力,所以通常网页中的广告都是以图像的形式嵌入到网页中。如果用户对广告感兴趣,则点击图片就可以进入广告站点。实际上,人们对广告信息

47、不感兴趣,而且图像占据了网页下载的大多数时间。第11章文本分类网页文本内容提取,也就是对网页中的文本内容进行提取,主要的面向对象是新闻性质的网页。这部分工作主要包括对网页的书写和构造方式进行分析,研究网页标记语言的写法、网页的组织结构及特点,去除网页中含有的大量噪声,如广告、版权、导航链接等相关内容,将网页中的新闻主题和内容以txt的格式进行存储。第11章文本分类在这部分的处理过程中,由于当前网页构造语言的多样性,如XML、HTML、VRML以及WML等多种语言书写的网页,其风格各不相同;另外,还有很多个人风格的网页书写,其风格可谓各式各样,这些多风格的网页书写格式对网页内容的提取造成了一定的

48、困难。这里介绍一种基于向量空间模型的网页噪声净化方法。第11章文本分类11.3.2基于向量空间模型的网页噪声净化基于向量空间模型的网页噪声净化在视觉上,一张网页的页面可以划分为若干个区域,一个区域称为一个内容块。这些内容块中,有的包含主题内容,而有的则包含噪声内容。通常,一个内容块中的内容是紧密相关的,这就意味着我们可以以内容块为单位对网页中的内容进行取舍。基于这样的分析,网页噪声净化过程就是保留网页中包含主题内容的内容块而去掉包含噪声内容的内容块。因此,网页净化的过程可以分为两个步骤:网页内容结构的表示和网页内容块的取舍。第11章文本分类基于向量空间模型的网页噪声净化的基本思想如下:(1)将

49、一篇HTML网页解析为文档树(Document Object Model,DOM)结构,并根据table与/table标签为最小单位将网页内容划分为不同的内容块。(2)根据规则挑选出网页的主题内容块并利用向量空间模型来表示。(3)根据内容相似性比较技术，判断其余内容块是否为噪声内容块。第11章文本分类1.文档树文档树根据网页的结构分析可以看出,网页是用标识语言来书写的,其中定义了一套标签来刻画网页显示时的界面。因此,对于HTML网页最常用的结构表示方法就是构造网页相对应的标签树。现有标签树的构造方法有很多,文档树就是一个常用标签树构造工具,它可以将网页中的标签按照嵌套关系整理成一棵树状结构。针

50、对网页净化的特殊需求,我们首先对HTML规范中的标签按照功能进行分类,进而提出更加适合网页净化的标签树的构造方法。第11章文本分类依据标签的作用可以将HTML的标签分为两类:规划网页布局的标签和描述显示特点的标签。规划网页布局的标签:如上所述,在视觉上,网页是由若干内容块组成的,而内容块是由特定的标签规划出的(称之为容器标签),常用的容器标签有table、tr、td、p、div等。描述显示特点的标签:除了描述布局结构的标签外,HTML标准中还定义了一套标签来描述其包含的内容本身。比如，b标签说明它所包含的内容要用粗体显示,img标签说明它包含的是一个图片,等等。第11章文本分类由于网页净化是以