计算机应用   2017, Vol. 37 Issue (4): 924-927,935  DOI: 10.11772/j.issn.1001-9081.2017.04.0924
0

引用本文 

王亚强, 汤铭, 曾沁, 唐聃, 舒红平. 级联式低消耗大规模网页分类在线获取方法[J]. 计算机应用, 2017, 37(4): 924-927,935.DOI: 10.11772/j.issn.1001-9081.2017.04.0924.
WANG Yaqiang, TANG Ming, ZENG Qin, TANG Dan, SHU Hongping. Cascaded and low-consuming online method for large-scale Web page category acquisition[J]. Journal of Computer Applications, 2017, 37(4): 924-927,935. DOI: 10.11772/j.issn.1001-9081.2017.04.0924.

基金项目

国家自然科学基金资助项目(61501063,61501064);四川省科技计划项目(2016JY0240);四川省教育厅科研基金资助项目(15ZB0177)

通讯作者

王亚强 (1984-), 男, 吉林龙井人, 讲师, 博士, CCF会员, 主要研究方向:大数据、云计算、自然语言处理、机器学习. E-mail: yaqwang@cuit.edu.cn

作者简介

曾沁 (1975-), 男, 广东梅州人, 高级工程师, 硕士, 主要研究方向:大数据、云计算、精细化预报、气象大数据分析;
唐聃 (1982-), 男, 四川成都人, 副教授, 博士, CCF会员, 主要研究方向:大数据、云计算、编码理论;
舒红平 (1974-), 男, 重庆人, 教授, 博士, 主要研究方向:大数据、云计算

文章历史

收稿日期:2016-10-08
修回日期:2016-11-27
级联式低消耗大规模网页分类在线获取方法
王亚强1, 汤铭1, 曾沁2, 唐聃1, 舒红平1    
1. 成都信息工程大学 软件工程学院, 成都 610225;
2. 广东省气象台, 广州 510080
摘要: 针对海量网页在线自动高效获取网页分类系统设计中如何更有效地平衡准确度与资源开销之间的矛盾问题,提出一种基于级联式分类器的网页分类方法。该方法利用级联策略,将在线与离线网页分类方法结合,各取所长。级联分类系统的一级分类采用在线分类方法,仅利用锚文本中网页标题包含的特征预测其分类,同时计算分类结果的置信度,分类结果的置信度由分类后验概率分布的信息熵度量。若置信度高于阈值(该阈值采用多目标粒子群优化算法预先计算取得),则触发二级分类器。二级分类器从下载的网页正文中提取特征,利用预先基于网页正文特征训练的分类器进行离线分类。结果表明,相对于单独的在线法和离线法,级联分类系统的F1值分别提升了10.85%和4.57%,并且级联分类系统的效率比在线法未降低很多(30%左右),而比离线法的效率提升了约70%。级联式分类系统不仅具有更高的分类能力,而且显著地减少了分类的计算开销与带宽消耗。
关键词: 大规模网页数据获取    网页分类    级联分类器    置信度函数    多目标粒子群优化    
Cascaded and low-consuming online method for large-scale Web page category acquisition
WANG Yaqiang1, TANG Ming1, ZENG Qin2, TANG Dan1, SHU Hongping1     
1. College of Software Engineering, Chengdu University of Information Technology, Chengdu Sichuan 610225, China;
2. Guangdong Meteorological Observatory, Guangzhou Guangdong 510080, China
Abstract: To balance the contradiction between accuracy and resource cost during constructing an automatic system for collecting massive well-classified Web pages, a cascaded and low-consuming online method for large-scale Web page category acquisition was proposed, which utilizes a cascaded strategy to integrate online and offline Web page classifiers so as to take full of use of their advantages. An online Web page classifier trained by features in the anchor text was used as the first-level classifier, and then the confidence of the classification results was computed by the information entropy of the posterior probability. The second-level classifier was triggered when the confidence is larger than the predefined threshold obtained by Multi-Objective Particle Swarm Optimization (MOPSO). The features were extracted from the downloaded Web pages by the secondary classifier, then they were classified by an offline classifier pre-trained by Web pages. In the comparison experiments with single online classification and single offline classification, the proposed method dramatically increased the F1 measure of classification by 10.85% and 4.57% respectively. Moreover, compared with the single online classification, the efficiency of the proposed method did not decrease a lot (less than 30%), while the efficiency was improved about 70% compared with single offline classification. The results demonstrate that the proposed method not only has a more powerful classification ability, but also significantly reduces the computing overhead and bandwidth consumption.
Key words: large scale Web page acquisition    Web page classification    cascaded classifier    confidence function    Multi-Objective Particle Swarm Optimization (MOPSO)    
0 引言

随着网络的飞速发展和普及, 互联网已成为人类获取日常生活、工作和社会热点信息的重要信息来源。为满足不同人群对信息内容的差异性需求, 各类信息通过不同的网络途径进行着传播, 并且数据量已成规模。如何在互联网中根据网页主题内容的不同, 实现对大规模网页资源的自动整理和分类, 是大数据研究的重点内容之一, 对帮助人类高效地获取信息、提高工作效率和生活质量具有重要的意义。

目前, 实现大规模网页资源的自动分类的方法主要分为两种:离线法和在线法[1]。离线法是一种传统、朴素的网页资源分类方法, 该方法利用网络爬虫, 无约束地在互联网中抓取网页, 然后基于朴素贝叶斯 (Naïve Bayes, NB)[2-3]、支持向量机 (Support Vector Machine, SVM)[4-5]等分类方法, 离线完成对网页内容的分类。该类方法充分利用网页中包含的特征信息训练分类器, 可获得良好的网页分类性能。然而离线法的良好分类性能建立在大量网络资源被浪费的条件下, 文献[6]中报道的结果显示, 在给定资源条件下, 离线的网页正文提取速度是每一万篇网页平均消耗140 min, 远大于网页抓取速度, 这类资源消耗在大数据时代将是惊人的。

在线法是近年提出的一种较新颖的方法[7], 该类方法利用网络爬虫在爬取网页的过程中获取到的与网页内容相关的特征信息 (锚文本、网页URL及上下文信息) 训练分类器, 然后将该分类器集成到网络爬虫中, 实现网络爬虫在线对目标网页内容类别进行判定, 如果与目标类别相关, 才将该网页下载并存储管理。该类方法能有效地降低网络资源的消耗, 降低离线网页数据管理的复杂性, 而且在相同带宽的条件下, 具有更快的网页分类速度和更少的网络资源消耗[8]。然而, 由于分类器所利用特征信息有限, 网页分类性能在较严格的约束条件下相对较低。

针对两类方法在网页分类质量和资源收集效率方面的各自优势, 本文采用级联策略, 按分类器复杂度递增的顺序, 构建多级网页内容决策序列, 并通过在各级增加置信度阈值的方式, 协调系统整体的分类质量和效率开销;同时, 提出基于熵的多目标粒子群优化方法实现置信度阈值的自动选取。分类器级联思想在机器学习领域已有一定的理论研究[9-10], 本文将其引入高效的大规模网页分类资源获取应用中, 以实现低消耗、高质量的网页分类在线获取。

1 级联式网页分类系统

在线法具有低网络资源消耗的特点, 而离线法具有高准确度的优势, 为综合两种方法的各自优点, 级联式网页分类系统应兼顾彼此, 在尽量保证准确度的情况下, 实现网络资源的低消耗。

1.1 基本框架

目前, 网页分类常采用基于统计的分类模型, 如朴素贝叶斯[2-3]、支持向量机[4-5]。该类方法一般为待分类网页产生属于某类别的概率值, 然后将这个预测值与预先设定的分类阈值进行比较, 若大于该阈值, 则将其划分到该类别下。以该思想为基础, 在进行级联分类系统的设计时, 可通过预先设定较高的置信度阈值, 将在线法能够以较高置信度确认分类的网页直接丢弃或分类并下载保存, 而将判别结果模糊的网页交给分类准确度较高的离线法进一步分析确认, 以此实现两种方法的优势综合, 其基本框架如图 1所示。

图 1 级联式分类系统的基本框架 Figure 1 Basic architecture of cascaded classification system

该框架的设计目标是满足大规模网页资源的收集和分类的实时系统, 其输入是从网页中获取的锚文本及URL, 输出是对该网页分类的结果。其运行过程如下:

步骤1  网络爬虫解析网页并获取其中包含的锚文本资源信息。

步骤2  将锚文本进行分词 (本文的分词均采用开源的NLPIR工具完成, http://ictclas.nlpir.org/), 并将其作为分类特征输入一级分类器。

步骤3  根据一级分类器输出的网页分类的后验概率预测值, 使用置信度函数 (判别器) 量化该判别结果的置信度。

步骤4  若预测值高于预先给定的置信度阈值, 那么认为本次判断置信度足够高, 并将判断结果作为该网页的最终分类结果, 保存至分类网页资源库; 若预测值低于预先给定的置信度阈值, 那么拒绝一级分类器的判别结果, 此时, 网络爬虫将下载该锚文本的URL所对应的网页, 抽取网页正文并分词提取特征, 将网页正文特征交由二级分类器进行处理。

步骤5  根据网页正文包含的丰富的分类特征信息, 二级分类器进行更准确的网页分类, 并将该分类结果作为该网页最终的分类结果保存至分类网页资源库。

1.2 置信度函数的确定方法

在1.1节所述的框架中, 其核心在于如何有效地确定其中包含的置信度阈值, 该阈值由置信度函数衡量, 合理的定义置信度函数将直接影响系统整体的性能。

本文的置信度函数,用于确定在给定锚文本特征x的条件下,网页被判定为类别cj的后验概率P(cj|x),是否具有较高的置信度将该网页划分至类别cj。条件概率分布P(cj|x) 的确定与不确定性判断结果如图 2所示。从图 2可看出:在P(cj|x) 分布较均匀的情况下, 分类结果的可判别性较低;而分布越不均匀, 则其分类结果的可判别性较高。根据此特性, 在本文提出的框架中, 一级分类器输出结果是否会交由二级分类器进行进一步的判别, 可由该特性对应的判别函数进行度量。

图 2 条件概率分布的确定与不确定判断结果情况 Figure 2 Certain and uncertain discrimination conditions of the conditional probability distributions

信息熵是用于度量变量不确定性的重要函数。熵值越大, 则说明变量的不确定性越大; 熵值越小, 则变量的不确定性越小。根据这一思路, 本文采用网页分类条件概率分布P(cj|x) 的信息熵作为置信度度量函数, 其度量方法如式 (1) 所示:

$H(C) = \sum\limits_{j = 1}^m {P({c_j}|x){\rm{lb}}P({c_j}|x)} $ (1)

其中:C为预先确定的网页类别划分的集合; m为集合C的大小。H(C) 值越大, 网页分类条件概率分布越均匀, 则网页类别划分越不确定; 置信度度量函数结果值越小, 说明网页分类条件概率分布越不均匀, 决策结果的置信度越高, 越容易根据分类器得到的网页分类概率分布确定当前网页类别的具体划分。如图 2(a), 该网页分类条件概率分布的信息熵值约为0.600 3, 当前待分类网页属于各类别的概率相当, 类别划分的不确定性较高; 而图 2(b)中的网页分类条件概率分布的信息熵值约为0.290 6, 且更容易判别当前待分类网页的所属类别划分。

1.3 置信度阈值的选取方法

置信度阈值选取的本质是参数优化问题, 首先需要确定优化的目标。网页分类属于文本分类任务, 其优化目标一般包括准确度、宏F1值和时间开销。本文将置信度阈值的选取定为多目标优化问题[11]:在给定准确度、宏F1值和时间开销的条件下, 寻找能够获得最优分类结果的阈值。

为选取优化置信度阈值, 本文采用多目标粒子群优化 (Multi-Objective Particle Swarm Optimization, MOPSO) 算法寻找最优阈值, 优化的目标为分类的准确度、宏F1值和被一级分类器拒绝的样本数量。其中, “被一级分类器拒绝的样本数量”是对级联分类器的“时间开销”的近似估计, 而“被一级分类器拒绝的样本”是指那些无法被一级分类器以较高的置信度 (详见1.2节) 来判断分类的网页。

为确保解的多样性和非支配解分布的均匀性, 本文采用文献[12]提出的最大拥挤距离的粒子更新策略:当所有粒子都能找到第一前沿时, 迭代结束。由于分类准确度和时间开销之间存在矛盾, 同时找到两者的最优值是不可能的, 只能通过MOPSO找出多个非支配解, 这些解一并构成Pareto前沿[13], 再根据实际需求 (即系统的实现需求是更重视高准确度, 还是更重视降低资源开销, 又或者要求两者均衡), 动态地选择最佳阈值。

1.4 级联分类系统的时间开销估算

系统的真实总体时间开销难以直接求得, 考察级联分类系统框架发现, 系统的分类时间其实与一级分类器拒绝的样本数有关, 即一级分类器拒绝的样本数越多, 那么二级分类器需要进行判别的样本就越多, 时间开销就越大。

表 1为一级分类器的分类情况。

表 1 一级分类器的分类情况 Table 1 Classification results of the first-level classifier

表 1中:CP为该分类器正确分类且被保留未传递给二级分类器的网页总数; CN为该分类器正确判别, 但由于其分类结果的条件概率分布的熵值高于预先设定的阈值, 因此被误传递给二级分类器进行进一步判别的网页总数; EP为该分类器判断错误但因该判别得到的条件概率分布的熵值高于预先设定的阈值而被误保留的网页总数; EN为一级分类器无法准确判断且通过置信度正确被过滤传递给二级分类器进行进一步判别的网页总数。

级联分类系统的理论开销时间Tc可通过式 (2) 得出。

$ {T_{\rm{c}}} = {T_1} + {T_2} = N \cdot {v_1} + (CN + EN) \cdot {v_2} $ (2)

其中:T1T2分别是一级分类器和二级分类器的时间开销;v1v2分别表示一级分类器和二级分类器处理网页相关特征的平均速度;N为分类网页样本总量。由此分析可知, 级联分类系统的分类时间与拒绝样本总数 (CN+EN) 正相关, 而与预先设定的置信度阈值负相关。因此, 本文使用一级分类器的拒绝样本数衡量系统的时间开销。

2 实验结果及分析 2.1 分类器参数的设定

本文使用的实验数据来源于新浪、网易和凤凰网上六类栏目的新闻网页, 分别是娱乐、财经、游戏、军事、体育、科技, 网页总数为90 206。文献[7]验证了朴素贝叶斯 (NB) 分类器用于在线分类具有良好的性能, 文献[5, 14-15]证明了SVM一般是最优的网页离线分类器, 因此, 本文以NB作为在线一级分类器, SVM作为离线二级分类器 (用“NB+SVM”表示)。验证本文提出的级联式网页分类获取策略的有效性, 采用10折交叉验证方法, 以各分类器在每个类别下的F1值作为分类性能的整体评价结果。

在本文实验中, 使用径向基函数作为SVM的核函数, 其包含的参数cγ分别定为851和1.5, 为SVM在本文数据集上取得最优分类结果时的参数, 限于篇幅未在本文赘述SVM的参数调优结果。

2.2 NB与SVM的性能分析

在线法的分类 (即利用NB进行网页分类) 依据是锚文本特征, 而离线分类则利用的是目标网页中包含的正文内容, 后者需要从包含大量噪声的网页中选取特征, 本文主要研究级联分类策略, 因此, 网页正文的抽取采用基于规则的方法完成。图 3给出了在线法和离线法在六个类别下的F1值分类结果, 该结果与2.1节描述的前人的研究结果保持一致。

图 3 在线与离线方法在预定类别下的F1值 Figure 3 F1 scores of different predefined classes achieved by online and offline classifiers
2.3 置信度阈值与样本数的相关性分析

为了分析置信度阈值与拒绝样本数的关系, 首先在熵值的值域内等间距取格点, 在NB+SVM级联分类系统上进行分类实验, 得到如图 4所示结果。从图 4可看出, 样本总数 (即一级分类器要作判别的网页总数) 始终保持不变, 即所有网页均要经过一级分类器进行判别, 这与事实相符。而拒绝样本总数 (即利用置信度阈值过滤的无法判别网页样本总数) 随阈值的增大而减少, 验证了1.4节提出的利用拒绝样本数衡量系统时间开销的合理性。

图 4 置信度阈值与样本数的相关性 Figure 4 Correlation between confidence threshold and number of instances
2.4 置信度阈值的选取

置信度阈值的大小同时影响级联分类系统的优化目标、分类准确度和分类时间, 使用信息熵作为置信度函数时, 熵值取得越小, 对置信度的要求就越高, 拒绝样本数就越多, 分类时间越长。相比拒绝样本数, 分类系统的准确度和熵值之间并没有明确关系, 因此本文通过MOPSO寻找一组阈值的最优解集。图 5给出了该系统在“拒绝样本比例”和“宏F1值”下32个粒子迭代60次的Pareto曲线。从图 5中看出, 两个优化目标之间存在明显的制约关系, 对于其中一个目标的优化必须以牺牲另一个目标的性能作为代价。由于Pareto曲线上的点均为模型的可行解, 因此认为最优阈值应根据实际工程需求, 在Pareto曲线上动态地选取 (正如1.3节所述)。此外曲线在“拒绝样本比例”上分布更广, 说明阈值对整个系统的时间性能影响较大, 本文以给定宏F1值为0.956 7时最小化时间开销为后续级联分类系统的测试方案, 即从曲线的左侧取值, 将0.273 9作为该系统的置信度阈值以分析系统的分类能力。

图 5 NB+SVM级联分类系统的置信度阈值Pareto曲线 Figure 5 Pareto curve of confidence threshold by using NB+SVM cascaded classification system
2.5 级联分类系统的分类能力分析

图 6对比了NB+SVM级联分类系统与单独使用NB作在线分类和单独使用SVM作离线分类在各类别下的F1值结果。从图 6中可以看到, 级联分类系统具有更准确和更稳定的分类性能, 在各类别上的分类性能均有提升。特别是对科技类网页的识别, 性能提升明显, 其平均F1值达到0.959 6。并且, 相对于单独使用NB作在线分类和单独使用SVM作离线分类, 其F1值分别提升了10.85%和4.57%。

图 6 在线、离线和级联分类系统在预定类别下的F1值 Figure 6 F1 scores of different predefined classes achieved by online, offline, and cascaded classification system

此外, 从图 6可以看到, 级联分类系统 (NB+SVM) 的分类性能更加稳定, 在各类别下的分类水平比单独的离线法 (SVM) 和在线法 (NB) 均得到改善, 且类别之间的分类性能差异得到改善, 实现了各类别的分类性能的兼顾, 达到了级联分类系统“优势能力互补”的目标。

为进一步验证级联分类系统的分类性能, 本文还实现了使用NB做在线分类、K近邻 (K-Nearnest Neighbors, KNN) 作离线分类的对比实验, 图 7给出了该组实验结果。从图 7中可以明显看到, 级联分类系统的性能始终优于单独采用在线法和离线法, 并且同样实现了各类别分类性能的兼顾, 达到了级联分类系统“能力互补”的目标。

图 7 在线、离线、级联分类系统在预定类别下的F1值 Figure 7 F1 scores of different predefined classes achieved by online, offline and cascaded classification system

此外, 从时间开销成本上看, 级联分类系统在一级分类阶段平均约有31.38%(NB+SVM约有30.14%, NB+KNN约有32.61%) 的实例交由二级分类器进行处理。这意味着级联分类系统不仅可有效地提升了网页分类的总体能力,同时, 取得该明显的分类能力提升, 只需要消耗比在线法多出30%左右的时间消耗。而对比于离线法, 级联分类系统可以大大降低其时间消耗 (约70%)。

3 结语

本文对在线和离线网页分类的级联方法进行了研究, 提出了采用级联策略实现在线法和离线法的优势能力互补, 基于多目标粒子群优化算法实现参数的调优。本文通过实验结果表明了该方法的可行性, 相对于单独的在线法和离线法, 级联分类系统的总体分类性能分别提升了10.85%和4.57%;并且级联分类系统的效率比在线法未降低很多 (30%左右), 但比离线法的效率提升了70%左右。结果表明, 本文提出的级联分类系统在分类能力和时间、带宽等资源开销上均有较大优势, 能够在保证效率的条件下, 有效地提升分类总体的性能。在当前大数据环境下, 该方法是一种有效的低消耗大规模网页分类资源的获取方法。

参考文献
[1] PANT G, SRINIVASAN P. Link contexts in classifier-guided topical crawlers[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18 (1) : 107-122. doi: 10.1109/TKDE.2006.12
[2] FENG G, GUO J, JING B-Y, et al. Feature subset selection using Naïve Bayes for text classification[J]. Pattern Recognition Letters, 2015, 65 : 109-115. doi: 10.1016/j.patrec.2015.07.028
[3] LIU B, BLASCH E, CHEN Y, et al. Scalable sentiment classification for big data analysis using Naïve Bayes classifier[C]//Proceedings of 2013 IEEE International Conference on Big Data. Piscataway, NJ: IEEE, 2013:99-104.
[4] CHANG C C, LIN C J. LIBSVM: a library for support vector machines[J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2 (3) : Article No. 27.
[5] HWANG Y S, KWON J B, MOON J C, et al. Classifying malicious Web pages by using an adaptive support vector machine[J]. Journal of Information Processing Systems, 2013, 9 (3) : 395-404. doi: 10.3745/JIPS.2013.9.3.395
[6] WU G, LI L, HU X, et al. Web news extraction via path ratios[C]//CIKM 2013: Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. New York: ACM, 2013:2059-2068.
[7] 韩国辉, 陈黎, 梁时木, 等. Naïve Bayes分类器制导的专业网页爬取算法[J]. 中文信息学报, 2010, 24 (4) : 32-38. ( HAN G H, CHEN L, LIANG S M, et al. Naïve Bayesian classifier guided domain specific webpage crawling algorithm[J]. Journal of Chinese Information Processing, 2010, 24 (4) : 32-38. )
[8] RAJALAKSHMI R, ARAVINDAN C. Web page classification using n-gram based URL features[C]//Proceedings of the 2013 Fifth International Conference on Advanced Computing. Piscataway, NJ: IEEE, 2013:15-21. http://www.academia.edu/12270221/Journal_of_Computer_Science_January_2014
[9] TRAPEZNIKOV K, SALIGRAMA V, CASTANON D. Multi-stage classifier design[J]. Machine Learning, 2013, 92 (2) : 479-502.
[10] KAYNAK C, ALPAYDIN E. Multistage cascading of multiple classifiers: one man's noise is another man's data[C]//ICML 2000: Proceedings of the Seventeenth International Conference on Machine Learning. San Francisco: Morgan Kaufmann Publishers, 2000: 455-462.
[11] FUMERA G, ROLI F, GIACINTO G. Reject option with multiple thresholds[J]. Pattern Recognition, 2000, 33 (12) : 2099-2101. doi: 10.1016/S0031-3203(00)00059-5
[12] 裴胜玉, 周永权. 基于Pareto最优解集的多目标粒子群优化算法[J]. 计算机工程与科学, 2010, 32 (11) : 85-88. ( PEI S Y, ZHOU Y Q. A multi-objective particle swarm algorithm based on the Pareto optimization solution set[J]. Computer Engineering and Science, 2010, 32 (11) : 85-88. )
[13] TEA T, BOGDAN F. Visualization of Pareto front approximations in evolutionary multiobjective optimization: a critical review and the prosection method[J]. IEEE Transactions on Evolutionary Computation, 2015, 19 (2) : 225-245. doi: 10.1109/TEVC.2014.2313407
[14] CHEN R-C, HSIEH C-H. Web page classification based on a support vector machine using a weighted vote schema[J]. Expert Systems with Applications, 2006, 31 (2) : 427-435. doi: 10.1016/j.eswa.2005.09.079
[15] SEBASTIANI F. Machine learning in automated text categorization[J]. ACM Computing Surveys, 2002, 34 (1) : 1-47. doi: 10.1145/505282.505283