一种中文网页分类算法

一种中文网页分类算法

随着网络向世界的普及和互联网发展，网络已成为网络中最重要的信息资源。WWW网页采用超文本描述语言(HTML)格式,每一个网页可以被引用为链接,也可以指向任何其它网页。为了网页信息的有效组织和检索,人们开发了网络信息搜索器。网络信息搜索器以给定的超链接(URL)为入口,按照HTTP协议,依次与WWW服务器建立连接,获取网页(如图1所示)。为了帮助因特网用户查询感兴趣的信息,国内外研究开发了一些网络搜索引擎,如国外的AltaVista,Infoseek,Lycos等,国内的网络指南针、网易、天网等。但是,目前中文搜索引擎存在以下问题:1)中文检索采用基于字或词的方法,由于中文切词有时存在不确定因素,导致中文的查全率和查准率不高;2)搜索引擎的分类信息资源主要依靠人工维护,不便信息更新。因此,研究中文网页的自动分类,一方面,可以将网页按类分别建立相应的数据库,对分类数据库进行查询,提高中文查全率和查准率;另一方面,可以建立自动的分类信息资源,为用户提供分类信息目录在英文文本自动分类算法[2～5]的基础上,结合中文网页的特点,采用非参数在线训练方法,提出了一种新的中文网页分类算法。实验证明,这种算法对中文网页的自动分类具有较好的效果。1文本分类方法文本自动分类就是用大量的带有类标识的文本,对分类准则或模型参数进行训练;然后,用训练得到的结果对未知类别的文本进行识别。目前,英文的文本自动分类方法有两大类:一类是参数方法,另一类是非参数方法[2～5,8,9]。参数方法是假定文本的概率分布模型,通过训练,得到具体参数的估计值。非参数方法是不假定任何概率分布形式,通过准则函数直接训练,得到各类的权重向量,然后对待识别样本进行判别。由于分类文本的概率分布模型很难准确地定义,非参数的分类方法应用较广。2中文网页分类中文分类与英文不同。英文分类算法大多以单词为关键词,利用空格等作为分隔符,提取文章特征;但中文一般是一串无分隔符的字串,词之间没有明显的分隔标志,而且切词比较难,不能直接采用英文分类方法。另外,与一般的纯文本文件不同,网页是HTML格式的超文本,页面中有〈title〉、〈meta〉等标记,以及描述此页面的标题(title)、页面描述(description)、关键词(keywords)、超链接(URL)等。这些包含重要的分类信息。提出的中文网页分类算法是一种非参数在线训练算法。其基本思想是根据中文字间的相关性等信息提取中文网页的关键词,每个关键词对文章分类的作用包括正权重和负权重。通过训练,计算每个关键词的正、负权重,形成本类的专家库。识别时,首先提取文章中的关键词,然后从专家库读取相应的正、负权重,利用判别准则,进行判别。2.1中国汉字时期分类模型对于中文而言,中文字间的相关性包含重要的分类信息。如果以单字作为关键词,不考虑字间的相关性,就会丢失文章的某些有用信息,影响分类结果。但是,如果考虑所有的前后字间的相关性,简单将前后相连的字定义为关键词,训练量非常大。因此,训练时采用中文词典,对文章进行切词,将词典中出现的词作为关键词。这样,既保留了必要的字间相关信息,同时也减少了训练量。设带有类标识的训练样本库T,T={tl,l=1,2,…L}。训练样本库T共有N类样本。设训练样本tl的类标识为cl,cl∈{0,1},其中,cl=1,表示该样本属于第n类,cl=0,表示该样本不属于第n类。下面对第n类进行训练。设第n类的专家库为Pooln,训练初始时,Pooln=h。对每个训练样本tl∈T,l=1,2,…L做以下处理:设词典为Dict,对训练样本tl进行切词,提取词典Dict中出现的中文词,构成关键词集合关键词w对判断tl是否属于第n类有两种贡献:属于第n类和不属于第n类,定义前者为,后者为。因此,构成关键词训练集合设w1的权重为正权重的权重为负权重,对关键词训练集合中的关键词权重进行初始化归一化关键词的权重,设的归一化值,则当不考虑词频信息时,判别准则为选取参数θc∈(0,1),计算式(5):如果yl>θc,判为n类,否则,判为非n类。由于文章中关键词出现的频率也在一定程度上反映了文章的主题,在对中文切词过程中,可以统计每个关键词出现的次数。设训练样本tl的关键词的词频。这里为中文网页的文本部分的词频。考虑网页的特点,它与普通的中文文本不同之处在于WWW网页除纯文本信息以外,还有其他描述信息,如标题、页面描述、关键词和超链接等。这些描述信息中出现的关键词包含网页的重要信息,对分类有较大的作用。因此,从网页中提取这些信息,引入加权的词频参数,对自动分类比较重要。设训练样本tl的关键词在标题、页面描述、关键词、超链接中的词频分别为总词频为其中:a,b,c,d是大于零的可调参数。考虑关键词词频和网页的页面标记,见式(6),准则式(5)可写为当时,式(7)与式(5)相同;当a=b=c=d=0时,,此时,忽略网页的标记信息,只考虑网页的文本部分的词频。根据式(7),更新关键词权重。设参数U∈(0,1)为衰减系数,进行本类样本训练(cl=1)时,非本类样本训练(cl=0)时,归一化关键词权重,使得更新前后权重之和不变。设S0,S1分别为更新权重前、后的关键词正、负权重之和,即则,归一化的权重为用本次训练的结果更新专家库,即2.2待识别样本集的识别设有N类专家库P={Pooln,n=1,…,N},其中,Pooln是按上述的训练算法得到的第n类的专家库,待识别样本集R={rm,m=1,…,M}。识别步骤与训练基本相同,只是不做(8)式以后的各步。对每个待识别样本rm,根据(7)式,计算rm对第n类的值ynm,得到集合Ym={ynm,n=1,…,N}。如果yjm=maxYm则将rm判为第j类。3实验数据的收集定义分类识别率:有N类待识别样本,根据2.2的算法进行分类。对某一类的样本,识别率为从网络搜索器收集的大量中文网页中,选用了包括足球类、计算机类、医学类、杂志类的样本共16200篇。实验过程中,可调参数:U=0.5,θc=0.5,a=1,b=1,c=1,d=1。词典:二字词32826个,三字词7195个,四字词16699个,五字词以上2469个。3.1白砂糖网页的识别结果采用无词频参数(即式(6)中,),并且只用足球类样本对足球类进行训练,即训练时省略式(9)。识别结果如表1所示。从表1可以看出,对中文网页,忽略字间的相关信息,用单字作关键词,识别率较低。考虑两个字的相关性,识别率比单字有较大提高。如果保留二字词和三字词或用词典中所有的词作关键词,识别率更高。因此,在训练时,保留必要的字间相关信息对网页的分类非常重要。3.2其他非本类训练用足球类和医学类样本分别对各自的本类进行训练;然后,用其他类样本分别对足球和医学类进行非本类训练。忽略关键词的词频参数(即式(6)中,)。识别结果如表2所示。由表2可以看出,通过加入非本类样本训练,可以较大程度地提高识别正确率。3.3识别结果采用词典提取关键词,用医学类样本对医学类进行训练,并且不采用非本类训练,即省略式(9)。比较加入词频参数,以及网页的标题等信息的识别结果,如表3所示。由表3可以看出,通过词频和页面描述信息进行加权调整,在训练和识别时,加大那些在网页文本部分出现频率高的词以及标题、描