一种通用论坛信息提取方法
2018-07-27谭文韬付园斌
刘 锐,谭文韬,付园斌,王 红,3
1(山东师范大学 信息科学与工程学院,济南 250014)2(山东省分布式计算机软件新技术重点实验室,济南 250014)3(山东师范大学 生命科学研究院,济南 250014)
1 引 言
随着互联网的不断发展,人们在互联网中进行交流的方式也在不断增多,互联网论坛从网络开始推广普及之时起便已成为人们在网络中交流和分享经验的主要平台.据文献[1]的中国互联网络信息中心发布的第38次《中国互联网络发展状况统计报告》显示,截至2016年6月,中国互联网论坛和BBS用户达1.08亿人,占网民总量的15.2%.然而在当下的网络论坛中,以广告为主的各类无关信息充斥在论坛中,这些网页噪声对信息检索和用户体验都会带来极大的不便.因此,如何有效消除网页噪声,提取出论坛主题帖正文内容,依然是当下研究的重要课题之一.传统的基于文本密度的正文提取方法[2-4]没有充分考虑到网页中噪声的影响,将网页源码中文本的长度作为判别正文的依据,使得其算法难以被有效应用到正文内容长度跨度大,网页噪声与网页正文混杂交错的网络论坛中.
为了系统地解决网络论坛主题帖正文提取的问题,本文从主题帖页面识别和主题帖正文提取两个方面入手,分别进行解决.两种方法均是对数据集中的样本数据进行处理,利用解析所得的规则完成后续分类和提取步骤,保障准确度和执行效率.实验表明:本文定义的网址相异度函数适合描述网址间的差异程度;USC方法与KSF方法均具有极强的通用性,适合大规模提取;两种方法在准确度上均明显优于传统方法,且易于扩展和自定义.
本文其余章节安排如下:第二节介绍信息提取领域的相关工作进展,第三节对两种方法进行理论介绍和阐释,第四节验证实验的结果和分析,第五节是本文的总结和对未来研究方向的展望.
2 相关工作
在学术领域,对网页进行分类已经有诸多方法.文献[5]根据语义结构对XML网址进行分类,在实验中可以达到较高的准确率;文献[6]使用遗传算法,以网页标签和属性为分类特征,对网页进行分类;文献[7]基于网址结构对网页进行分类,为本文USC方法的提出提供了灵感.文献[8]利用上下文特征,使用支持向量机对网页进行分类,是一种经典的网页分类方法.文献[9]使用蚁群算法优选网页特征,并用朴素贝叶斯、KNN等算法根据优选的特征进行分类,以提高分类的准确度和执行速度.文献[10]将向量机和无监督聚类优势互补,旨在解决向量机效率低和无监督聚类准确度低的问题.
在正文提取方面,前人也已有诸多突出的成果:文献[11]提出一种针对微博的正文提取方法,并以推特为例进行了实验.文献[3]使用DOM节点的文本密度为标准进行正文提取,该方法便捷且高效.文献[2]则在此基础上,提出针对短正文网页的正文提取方法,其提取正文的方法仍然为文本密度.除了文本密度方法外,文献[12]提出根据网页结构和文本特征进行正文提取的方法,文献[13]则使用布局相似性作为依据进行提取,然而这些方法在处理短正文时也存在一定缺陷.
总体而言,传统的网页分类更多倾向于内容特征方法,而正文提取则以文本密度为基本思想.内容特征的优点是易于分离出不同网页的个性与共性,为分类提供依据,且这些特征不易受主观因素影响,而缺点是内容特征自身的选择易受主观影响,且分类结果易受选择的结果影响,缺乏通用性和指导依据.而文本密度方法优点是简单高效,具有一定通用性,但缺点是完全忽略了网页中正文的语义因素,容易受到长度较高的噪声影响,且难以应用到正文较短,结构复杂的论坛之中.
3 通用论坛正文提取
3.1 网页结构化聚类方法
在主题帖页面识别部分,本文提出了一种基于网址结构的聚类方法USC.在该方法中,首先根据分隔符将网址划分为若干部分,随后使用聚类算法将网址划分到不同簇中,筛选出主题帖所在的簇,以此提取出所有主题帖页面的网址.USC方法使用基于网址结构运作,而不对网页内容直接进行处理,相比传统方法更具有针对性,且在性能上也略胜一筹.
3.1.1 网址结构特征
统一资源定位符(Universal Resource Locator,URL),俗称网址,是用于唯一定位互联网上网络资源的一种表示方法,其主要由传输协议、服务器、端口号、路径、查询、片段六部分组成.隶属于同一论坛的网页,除了协议、服务器名和端口号完全相同外,在路径和查询部分也有一定的相似之处,如共用的文件夹,共用的附加参数等等.USC从网址中提取若干结构特征和内容特征,以描述该网址,进而反映出网址指向的网页所属的类别.
论坛中的各类网页根据其生成方式的差异可以被划分为动态网页,静态网页,伪静态网页三种类别.三类网页在网址结构上有着各自的特征:
动态网页:动态网页的网址中会包含“?”,其后的内容为向服务器提交的参数列表,该部分由若干以“&”符号连接的键值对组成.
静态网页:静态网页不需要查询部分.但为便于分类和查找,网页文件往往会被放置在特定的文件夹中,故网址中会包含较长的路径部分.
伪静态网页:伪静态网页的网址结构既不含查询部分,且路径部分也相对较短,但由于实质是将动态网页的网址进行重写,所以路径部分往往会包含各种分隔符号.
由上面的说明可以得出,同一论坛下的各类网页,在网址结构上也会有诸多相似.为此本文引入网址的结构向量,该向量对网址进行定量表示,对网址中不同位置的结构块按其内容类别(文本或数字)和内容进行编码.
定义1.网址的结构向量.一个结构向量由若干结构块编号元组组成,二者的定义分别为:
p(u,i)=(t(u,i),v(u,i))
(1)
S(u)={p(u,i)|i=1,2,…,N}
(2)
其中u为网址,i指网址中第i个结构块,t(u,i)为类别编号,v(u,i)为值编号,p(u,i)为结构块编号元组;N为总结构块数,S为结构向量.
一个结构块即为被分隔符号包围的一段字符串,在为网址u的第i个结构块进行编号时,首先为其类别进行编号,当该结构块的类型(包括空值)为首次出现时,为其赋予新的编号,否则沿用已经为该类型分配的编号;对值分配编号时类似,若该结构块的值(包括空值)为首次出现时,赋予新的编号,否则沿用既有编号.N的值取数据集中拥有最多结构块的网址u的结构块数.若某网址的结构块数不足N,则不足的部分以空值的编号补齐.此外,当对同一论坛提取的网页构造结构向量时,可以忽略其传输协议和域名部分.
在上述定义下,若有如下5条 网址在数据集中:
1.http://example.com/query.php?id=001&grade=100
2.http://example.com/query.php?id=001&grade=99
3.http://example.com/query.php?id=002&grade=100
4.http://example.com/query.php?id=002&grade=99
5.http://example.com/query.php?id=003
分别简记为u1到u5,类型编号如表1所示.
表1 类型编号
Table 1 Type numbers
编号类型0(空值)1纯字母2纯数字
对值编号如表2所示.
表2 值编号
Table 2 Value numbers
编号值编号值编号值0(空值)400180021Query5grade90032php61003id799
则对上述网址分别构造结构向量为:
S(u1)=[(1,1),(1,2),(1,3),(2,4),(1,5),(2,6)]
S(u2)=[(1,1),(1,2),(1,3),(2,4),(1,5),(2,7)]
S(u3)=[(1,1),(1,2),(1,3),(2,8),(1,5),(2,6)]
S(u4)=[(1,1),(1,2),(1,3),(2,8),(1,5),(2,7)]
S(u5)=[(1,1),(1,2),(1,3),(2,9),(0,0),(0,0)]
在对上述网址构造结构向量时,由于其均隶属于同一域名,故统一忽略域名部分,从路径部分开始构造.每次读取一条网址,分别查找对应的结构块的类型和值的编号,若找到则采用现有编号,否则在编号表中添加新的编号.
定义2.网址之间的相异度.如下所示:
Ns(um,un)=min{i|p(um,i)≠p(un,i)}
(3)
(4)
其中um,un代表不同的网址,p(u,i)与N的定义为定义1中的定义,D(um,un)为网址um和un的相异度.
Ns(um,un)是要找到最小的i,使得两个网址在位置i的结构块不同.如此定义可防止当两个网址完全不同和仅第一个结构块相同时相异度相等的情况.
目录结构是典型的树形结构,上级目录的差异会在后续层级中不断被扩大,因而对高层目录级赋予较高权值,他们体现为阶乘中较大的乘数.当其产生差异时,后续子目录会进一步扩大这种差异,故采用乘法连接不同层级.
在上述定义下,若有如下三个结构向量:
S(u1)=[(1,1),(1,2),(1,3),(1,4),(1,5)]
S(u2)=[(1,1),(1,2),(1,3),(1,1),(1,2)]
S(u3)=[(1,1),(2,2),(1,3),(1,4),(1,5)]
则对于u1和u2,其从第4个结构块开始不同,故Ns(u1,u2)=4,D(u1,u2)=5!/4!=5;而对于u1和u3,虽然仅有第2维不同,但由于其为第一组不同的,所以Ns(u1,u3)=2,D(u1,u3)=5!/2!=60.
3.1.2 KNN-PDC聚类
本文以KNN-PDC聚类[14]为例,介绍聚类算法在USC方法中的应用.KNN-PDC聚类是PDC聚类[15]的一种改进.PDC聚类利用簇中心局部密度较高和不同簇中心距离较远两条假设,分别求取每个点的局部密度和到另一个密度更高的点的距离,以此确定簇中心.KNN-PDC聚类在此基础上利用样本点的K近邻信息,统一了DPC聚类的局部密度定义,摆脱了DPC算法受截断距离影响较大的缺点[14].
在KNN-PDC聚类中,簇中心的确定依赖于样本i局部密度ρi和局部密度大于i且离i最近的样本点距离δi,下面,我们给出二者的定义.
定义3.局部密度ρi和局部密度大于i且离i最近的样本点距离δi.公式如下所示:
(5)
(6)
其中,KNN(i)代表点i的K近邻集合,dij为点i与点j之间的距离.K近邻集合中的点到i的距离越近,则ρi值越高,局部密度越大.δi则当比i局部密度大的最近的点离i较远时δi较大.
如下是KNN-PDC聚类的主要流程.
Algorithm1KNN-PDCClusteringInputpoints：distancefunctionisavailableInputK：numberofneighborsOutputclusters：resultclusters1：procedureClustering(points，K)2： foralliinpointsdo3： //KNN(i)指点i的K近邻点集4： ρi←sumofdistancetopointsinKNN(i)5： δi←mindistancetopointjwhereρj>ρi6： endfor7： DecisionGraph←scatterplotofeachδiandρi8： //更高的ρi和δi意味着更可能是族中心9： centers←pointsinDecisionGraphw/highρiandδi10： clusters←BFS(points，centers，K)11： returnclusters12：endprocedure
在上述流程中,用到了寻找各簇中心的K近邻点的函数BFS,该函数的流程如算法2所示.
Algorithm2BreadthFirstSearchInputpoints：distancefunctionisavailableInputcenters：centerswithhighρiandδiInputK：numberofneighborsOutputclusters：resultclusters1：procedureBFS(points，centers，K)2： clusters←Array
通过如上算法,可以将输入的所有网页划分为若干簇,以便进行后续处理.此外,由于主题帖网址大多具有极高的结构相似性,因而本文中没有考虑对离群点的处理,如有相关需求,可进一步参考文献[14].
3.1.3 网址解析模块
为了能够快速对大量的网址进行类别筛选,同时为了适应分布式计算的要求,我们需要将分类后的结果进行解析.本文给出了较为通用的解析器定义,通过对给定网页各结构块的排列方式,内容加以限定,进而得到网址的解析器.下面,我们将给出其公式定义.
定义4.解析其模块r(i)和解析器R.其公式如下:
r(i)=(t(i),v(i))
(7)
R={r(i)|i=1,2,…,N}
(8)
其中t为类别集合,描述所有待解析网址定位置的结构块类型,v为与t中元素对应的值集合,描述所有待解析网址子特定位置的结构块值,r为对应于特定位置的结构块的规则元组,R为对所有网址的解析器.
在使用时,解析器和网址结构向量类似,不同处在于解析器中每个位置可能存放多个编号值,使用时采用令网址相异度最小的组合方式,与普通网址计算相异度.
3.1.4 结构化聚类流程
上文中分别介绍了结构向量,网址相异度,KNN-DPC聚类和解析器的有关内容,该小节将结合前述内容,介绍USC方法的完整流程.在网页类型识别的过程中,往往需要对从同一论坛获取的大量网页同时进行处理,这并不要求对所有网页都进行聚类等操作,而是先对少量网页进行解析,将解析所得规则应用于其他页面,以此快速完成对所有页面的分类,也便于利用集群进行分布式处理.上述方法的伪代码表示如算法3所示.
Algorithm3URLs′StructureClusteringInputurls：urlsfromsingleforumInputK：numberofneighborsOutputtopics：urlsoftopicpages1：procedureUSC(urls，K)2： samples←randomurlsinurls3： a←specifiedtopicpageurlinsamples4： //类别有如动态网页、伪静态网页等5： samples←sampleswithsametypeofa6： vectors←structurevectorsofallurls7： clusters←Clustering(vectors，K)8： topics←clustertowhichabelongs9： //根据主题帖网址构造解析器10： Rule←resolverulefromtopics11： topics←topicurlsidentifiedbyRule12： returntopics13：endprocedure
3.2 关键字打分筛选方法
在主题帖正文提取部分,本文提出关键词打分筛选方法(Keyword Scoring Filter,KSF).在该方法中,需要使用特定方法确定词条关键程度,我们以词频-逆向文件频率(TF-IDF)方法为例,来介绍KSF方法的主要思想和算法流程.
首先,根据停用词库排除无关文本,其后根据TF-IDF值找出文本关键词,接着对关键词出现的区域进行打分,解析得到得分最高的区域,对其他网页采用解析得到的规则直接进行正文提取.采用这种方法,不仅提升了主题帖正文提取的准确率和运行效率,同时可以获得适用于其他页面的通用解析规则,以简化后续的对于同一论坛的提取工作.
3.2.1 TF-IDF统计方法
TF-IDF统计方法是一种用于信息检索和文本加权的技术,常用于评估某一词条在一个语料库中的一份文件中的重要程度.词条的重要性随着其在文件中出现的次数上升而上升,随着其在语料库中出现的次数上升而下降.
词频(Term Frequency,TF)的计算是该方法的第一个步骤,表示一词条在当前文件中出现的频率,其计算公式如下:
(9)
其中,F为语料库中所有文件的集合,f∈F为文件,w为词条,N(f,w)为词条w在文件f中出现的次数.
当一个词条在文件中多次出现,如在计算机类文章中频繁出现“分布式”,则我们有理由认为该词条在该文章中重要性较高.体现到TF值中,则会被赋予较高的值.
逆向文件频率(Inverse Document Frequency,IDF)是该方法的第二步,该指标体现一个词条在所有文件中出现的普遍程度,其公式如下:
(10)
其中,P(f,w)为词条出现函数,当词条w出现在文件f中时,值为1,否则为0,分母部分+1是为了防止词条w在语料库中没有出现过,导致分母为0的情况发生.
当一个词条在多个文件中频繁出现,如在各类文件中都大量出现的“的”字,则我们有理由认为该词条在整个语料库中重要性较低.体现到IDF值中,也就会导致分母值上升,使得IDF值下降.
结合上述二者,最终可以根据以下公式得到词条w在文件f中相对于整个语料库F的重要度.
W(f,w)=TF(f,w)×IDF(f,w)
(11)
其中W为词条w的重要度,该重要度体现了词条在文章中的突出程度和语料库中普遍程度二者的调和,倾向于选择在文件中真正突出的词条,而排除掉因行文需要而大量出现的常用字词.
3.2.2 打分评价方法
在利用上文中的TF-IDF方法对文本重要度进行加权的过程中,难免会遇到异常页面,如无人回复的冷门帖,含有大量图片而缺乏文字的图片帖等等,这些噪声的存在可能会对主题帖关键词提取造成误导,使得无法得到正确的提取规则,进而使得对所有页面的正文提取全部出错.为预防这类问题,本文基于正文出现频率大于噪声出现频率的假设,采用打分评价方法对每个网页反馈的结果进行评估,依照得分高低决定采用哪一个结果作为最终的输出.其伪代码流程如算法4所示.
除了可以将算法4应用到对每个网页返回结果的评估中外,还可以将其应用到对单一网页内正文位置的判别中,其基本流程与上述流程类似,故不再赘述.
Algorithm4ScoringInputobjs：candidatesgroupOutputresult：resultsgroup1：procedureScoring(objs)2： scorcs←Map
3.2.3 关键字打分筛选流程
上文中分别介绍了TF-IDF统计方法和打分评价方法,下面将两种算法结合,加以部分优化步骤,构成从主题帖页面中提取出主题帖正文的完整算法.
首先,从所有网页中抽取部分网页作为样本;然后,初步清理样本网页中的噪声并剔除重复样本;接着,对样本网页中的文本进行分词并计算权重;再后,对词条隶属网页元素打分;最后,借助打分结果构造解析规则,利用打分结果对其他网页提取正文.其伪代码流程描述如算法5所示.
Algorithm5KeywordScoringFilterInputhtmls：sourcecodeofwebpagesOutputcontent：contentextractedfromwebpages1：procedureKSF(htmls)2： samples←randomwebpagesinhtmls3： results←Array
在算法5中,涉及到了停用规则,内容相似规则,提取规则三种规则,这三类规则的具体实现可以根据用户自身需求自行定义.停用规则是当单一行内的文本满足特定条件时,该行文本会被视噪声而被去除,常用的停用规则有根据停用词库匹配,设定文本长度阈值,是否存在特定文本结构等.内容相似规则用于判断两部分内容是否由网页模板生成,而非用户所写,若时是则将其去除,常见的生成内容如回帖发表日期,用户个人信息栏,“只看楼主”等论坛操作按钮,等等,为了辨别这些内容,可以选择每行文本的开头数个字符作为键,若键相同则视为模板生成.提取规则用于精确表示需要进行提取的位置,选用的方法必须能够恰好涵盖所有正确的位置,通常选用代码中标签的class属性值.
4 实验与分析
4.1 结构化聚类
相比传统分类方法,USC并不直接对所有网页进行分类,而是从所有网页中抽取部分样本作为训练数据,根据分类结果构造解析器,再利用解析器对剩余网页进行解析,因而最终的分类结果在很大程度上取决于解析器,构造解析器的规则中,除直接使用结构向量外,也可使用正则表达式以提升程序的通用性.本文实验中为便于描述,解析器将仍然使用结构向量.
4.1.1 实验数据
我们利用网络爬虫在互联网上随机爬取了若干网页,经过人工去除非论坛网页、广告页等无关网页,剩余有效网页数13346,其中主题帖网页数5888,在所有有效网页中,Discuz!论坛页面11822,独立论坛页面数1524.这些页面来自不同领域不同话题的论坛,具有一定的代表性.
4.1.2 评价指标
在信息提取领域,通用的评价指标是召回率R,准确率P和F值.三者的计算公式分为:
(12)
(13)
(14)
其中,Net为提取主题帖数,Nt为主题帖网址数,Ne为提取数.一般而言,提取结果的优劣由F值进行评估,其值越高,效果越好.
4.1.3 结果分析
本部分实验主要是与文献[16]所采用的基于DOM树的网页聚类算法相比较,在同样的数据集下,二者的运行结果分别如表3和表4所示.
在此次实验中,我们根据预实验的结果对K值进行了微调,以维持较高的准确率,尽管可能会有部分坛的由于网址结构过于单一而导致本应同类别的网址被划分到不同类别中,使得召回率降低,但对于一般的网站,基本可以维持较高的召回率,同时也使得准确率得到保证,确保构造的解析器中不会将噪声网址包含在内.
将表3和表4中的数据绘制为折线图,其结果如图1,图2,图3所示.
综合实验结果,可以看出USC方法中的聚类部分具有如下优点:
1.准确度高,构造解析器的簇中不含任何噪声,确保使用解析器进行大规模提取时的正确性.
2.适应性强,对各类论坛均有较高的召回率,确保拥有足够的样本数据构造解析器并使得解析器可以提取到更多符合要求的网页网址.
表3 USC聚类结果
Table 3 Result of clustering in USC
序号网址数主题帖网址数提取数提取主题帖数召回率/%准确率/%F值/%1522287287287100．00100．00100．00276221421121198．60100．0099．293481202202202100．00100．00100．00436813112812897．71100．0098．8451102671671671100．00100．00100．00662729128228296．91100．0098．43763320119819898．51100．0099．25883145544944998．68100．0099．34948721019019090．48100．0095．0010859282282282100．00100．00100．00
表4 文献[16]的聚类结果
Table 4 Result of clustering in reference [16]
序号网址数主题帖网址数提取数提取主题帖数召回率/%准确率/%F值/%152228723023082．58100．0090．462762214808038．19100．0055．273481202909048．67100．0065．474368131505043．09100．0060．225110267153053079．93100．0088．85662729121021075．52100．0086．05763320113013064．86100．0078．69883145539039087．04100．0093．079487210210210100．00100．00100．001085928219019069．73100．0082．17
4.2 关键字打分
KSF方法采用语义分割和TF-IDF加权方法提取出网页文本部分的关键词,对关键词所在位置进行打分,构造出解析规则,故能否从网页中正确提取到主题帖的正文信息取决于解析规则的构造情况.本实验中需要的对文本进行进行分词,为简化实验流程,实验中的分词程序将使用开源的分词程序包jieba.下面,本实验将对使用KSF方法构造解析规则的过程进行评估.
图1 召回率Fig.1 Recall value
4.2.1 实验数据
我们利用网络爬虫,在每个网络论坛中爬取若干论坛页面,去除非主题帖页面后,所有论坛剩余主题帖页面数总计为3417,每次从同一论坛的页面中随机抽取5个页面进行训练,根据解析所得规则判断是否正确分离出所需内容,每个论坛将重复进行10次实验.
图2 准确率Fig.2 Precision value
图3 F值Fig.3 F value
4.2.2 评价指标
本实验重在检验解析规则的正确性,为简化处理,以标签class属性值作为解析规则,故评价指标为解析所得class属性值恰为论坛正文区标签class属性值的比例和程序用时.
4.2.3 结果分析
这一部分实验我们使用文献[2]中的SCEED算法作为对照实验,实验的结果如表5和表6所示.
表5 正文提取算法综合对比
Table 5 Brief comparison between KSF and SCEED
算法名称准确率/%平均用时/sKSF90．7728．24SCEED72．3127．43
在用时方面,KSF算法相比SCEED算法要慢,进行中文分词需要读取中文数据库,并对字符串序列进行划分和匹配.SCEED方法没有这些步骤,因而速度相对较快,但准确率较差.
综合实验数据,KSF方法具有以下特点:
1.鲁棒性较强,在有较多噪声的主题帖页面中仍可正常进行解析工作.
2.通用性强,解析出的规则可以应用于同论坛内的所有主题帖页面.
3.效率高,对一般论坛中单一网页的解析速度视内容量从2秒到9秒不等.
表6 正文提取算法效果对比
Table 6 Detailed comparison between KSF and SCEED
序号正确数/个平均用时/sKSFSCEEDKSFSCEED1101028．6139．33210844．0233．4737038．8034．6749109．627．4758537．3134．41691025．5222．547101021．5322．418101012．1411．8699318．2916．05108611．9817．101110104．613．351210618．2519．48138696．4694．41
5 总结与展望
本文首先提出了网址的结构向量表示法,使得对网址的处理可以采用类似向量的的方法进行,此外还给出网址相异度函数的定义,这是一种结合目录结构特性的相异度计算方法,可以将其推广应用到更多目录结构的表示中.此外,本文第二节提出的基于网址结构的聚类方法USC是对传统论坛网页分类方法的改进,该方法充分利用网络论坛在网址结构上的相似性和结构化特性,无需读取网页内容,即可对同论坛下的网页直接进行分类,同时兼顾性能与质量.最后,本文结合语义分词技术,TF-IDF加权统计方法,打分评估方法提出的关键词打分筛选方法,可以快速对论坛中的网页解析出通用的提取规则,应用于后期大规模正文提取中,以满足持久化信息提取的需求.
本文在使用KNN-DPC进行聚类时,虽然可以通过决策图直观地选出簇中心,然而仍然缺乏一种适合于所有情况的自动化簇中心选择方法,在接下来的工作中将通过曲线分析寻找自动确定簇数的方法.此外,本文中为便于描述而采用较为简单的解析规则,在实际应用过程中,除可替换为正则表达式,还可根据需求完全自定义解析规则的行驶,如何合理构造具有较强鲁棒性的解析规则,仍是一个亟待研究的问题.
