基于模拟退火的在线Web文档内容数据质量评估

摘要：针对基于训练模型或用户交互的Web数据质量评估方法不能在线响应，也不能获取内容事实内涵的问题，提出一种基于模拟退火（SA）的在线Web文档内容数据质量评估（QASA）方法。首先，通过在Web上搜集主题相关文档，构建目标文档的相关空间，进一步采用开放式信息抽取技术抽取文档内容的事实；然后，采用SA技术在线构建两个最重要的数据质量维度即准确性和完整性的参照；最后，通过比对目标文档和维度参照的事实来量化数据质量维度。实验结果表明，QASA方法可以及时返回近似最优解，并保持与离线算法等同或高于10%的精度。该方法不仅能满足实时响应的要求，而且具有高的评估精度，可应用于在线识别高质量的Web文档。

关键词：数据质量；Web文档；模拟退火；维度；事实

中图分类号： TP311.13； TP18

文献标志码：A

Abstract： Because the existing Web quality assessment approaches rely on trained models， and users interactions not only cannot meet the requirements of online response， but also can not capture the semantics of Web content， a data Quality Assessment based on Simulated Annealing （QASA） method was proposed. Firstly， the relevant space of the target article was constructed by collecting topicrelevant articles on the Web. Then， the scheme of open information extraction was employed to extract Web articles facts. Secondly， Simulated Annealing （SA） was employed to construct the dimension baselines of two most important quality dimensions， namely accuracy and completeness. Finally， the data quality dimensions were quantified by comparing the facts of target article with those of the dimension baselines. The experimental results show that QASA can find the nearoptimal solutions within the time window while achieving comparable or even 10 percent higher accuracy with regard to the related works. The QASA method can precisely grasp data quality in realtime， which caters for the online identification of highquality Web articles.

Key words： data quality； Web article； Simulated Annealing （SA）； dimension； fact

0引言

人们经常在线获取Web文档，其数据质量直接影响获取的数据的价值。数据质量公认为分解成若干数据质量维度来衡量，主要包括准确性、完整性、新鲜性、一致性等[1-3]。然而Web文档内容的数据质量评估极具挑战性，原因在于：1）相比结构化数据，Web文档是松散的自然语句序列，缺少模式约束来保证质量；2）Web上缺少有效的规范和审核机制，数据拷贝方便，低质网页容易泛滥。目前Web数据质量评估方面已经有许多工作[4-11]。但这些工作多采用离线训练模型或采用用户交互的方式来衡量数据质量，不适合在线处理的场合，也不能从事实内涵角度揭示Web文档内容是否和现实一致。

为了实现准实时的Web文档数据质量鉴别，提出基于模拟退火的数据质量在线评估（Quality Assessment based on Simulated Annealing， QASA）方法。QASA采用模拟退火（Simulated Annealing， SA）在线构建数据质量维度参照，通过比对目标文档和参照的事实来量化数据质量维度。该方法由以下两个连续步骤构成：1）相关文档识别和事实提取。根据目标文档内容，在Web上搜集主题相关文档，并抽取其中的事实，从而构建目标文档的主题相关空间。2）在线维度参照构建和维度量化。在相关空间中，采用模拟退火在线构建两个最重要的数据质量维度即准确性和完整性的参照，然后将目标文档事实和维度参照进行比较，量化数据质量维度。

该方法的创新之处在于：1）利用模拟退火在线构建维度参照，可在规定的时间内返回处理结果，满足在线处理要求；2）通过信息抽取，将文档转化为事实集合，从事实内涵角度量化Web文档内容是否和现实世界一致。在实际数据上的实验表明QASA是Web文档数据质量在线评估的有效方法。

1相关工作

1.1Web文档数据质量评估

目前Web文档内容质量评估主要采用基于模型或基于用户交互的方法。基于模型的方法提取内容中的特征，训练模型来进行质量评估：文献[4]综合文本、评论和网络三个方面特征，采用支持向量机模型对Web文档的数据质量进行评估；文献[5]根据文本长度，采用机器学习推断Wikipedia文档数据质量好坏；文献[6]利用文档长度、词性、Web特征和可读性等，用最大熵理论训练模型，评估Wikipedia文档质量。基于用户交互的方法根据用户和文档交互特征来评估数据质量：文献[7-9]根据文档的修改历史和作者信誉度来估计Web内容质量的好坏；文献[10]利用用户信誉度和文本内容的依赖关系来计算文档质量；文献[11]根据用户的交互模式来判定Wikipedia文档的数据质量好坏。但这些方法侧重于离线处理，同时也不能抓取文档的事实内涵。

1.2模拟退火技术

模拟退火（Simulated Annealing， SA）算法在1982年由Kirkpatrick等首次提出[12]。它依据固体物质退火过程与问题求解过程的相似性来设计搜索策略，是一种启发式随机搜索算法。模拟退火算法不只是接受最优解，也会以一定的概率接受近似最优解。目前模拟退火技术在组合优化[13]、实时处理[14]方面得到广泛应用。

1.3信息抽取技术

近年信息抽取技术获得长足进步[15-19]，这个领域专注于从文档中抽取实体或事实，主要分成基于模式的、基于规则的和基于统计学习的三类方法[15-17]。这些方法针对特定模式或需求进行信息抽取，要预先知道种子模式。近年，针对开放域的信息抽取技术收到广泛关注[18-19]，该类方法不依赖特定的特征，直接从文本中抽取事实，具有通用性。但针对Web文档内容抽取数据质量参照则鲜有工作。

2相关文档识别和事实抽取

目标文档的相关空间通过以下两个步骤识别。

1）搜集备选相关文档。根据目标文档题目和关键字在Web上搜索相关文档，选取PageRank值高于设定阈值的文档，以获得普遍认可的备选相关文档。

2）过滤不相关文档。目标文档的相关空间由所有和目标文档描述相同主题的文档构成。给定目标文档和备选相关文档，如果两篇文档描述相同的主题，其词法应具有较高的相似度。本文提出在ngram空间中[20]识别主题密切相关文档，如算法1所示。

可见，在FA质量类上，QASA在运行时间小于180ms的情况下，精度稍逊色于QASVM方法，但随着迭代时间增加，QASA方法的精度很快优于QASVM方法；在ST质量类上，QASA在运行时间小于200ms的情况下，精度稍逊色于QASVM方法，但此后，QASA方法的精度要高于QASVM方法。在其他质量类上表现出类似的趋势，篇幅有限，不再赘述。这是因为QASA方法以内容的事实为基础，采用退火算法以概率逼近最优解，当时间非常短时结果不够理想，但绝大部分情况会给出一个高精度的结果。由于QASA方法不需要离线训练模型，因此更适合在线处理场合。

5结语

为了实现Web文档及时、准确的信息获取，Web文档内容的数据质量在线评估是亟待解决的问题。本文提出在抽取文档事实的基础上，用模拟退火实现准实时的在线评估，保证在任何时候返回一个可接受的近似最优解。本文方法根据事实语义量化数据质量，不依赖任何特征，是一种通用的在线数据质量评估方法。实验表明QASA是实现Web文档数据质量在线评估的有效途径。

参考文献：

[1]AEBI D， PERROCHON L. Towards improving data quality [C]// Proceedings of the 1993 International Conference on Information Systems and Management of Data. Washington， DC： IEEE Computer Society， 1993： 273-281.

[2]BATINI C， CAPPIELLO C， FRANCALANCI C， et al. Methodologies for data quality assessment and improvement [J]. ACM Computing Surveys， 2009， 41（3）：8-75.

[3]BOUZEGHOUB M， PERALTA V. A framework for analysis of data freshness [C]// Proceedings of the 2004 International Information Quality Conference on Information System. Washington， DC： IEEE Computer Society， 2004： 59-67.

[4]DALIP D H， GONCALVES M A， CRISTO M， et al. Automatic assessment of document quality in Web collaborative digital libraries [J]. Journal of Data and Information Quality， 2011， 2（3）： article 14.

[5]BLUMENSTOCK J E. Size matters： word count as a measure of quality on Wikipedia [C]// Proceedings of the 17th International Conference on World Wide Web. New York： ACM Press， 2008： 1095-1096.

[6]RASSBACH L， PINCOCK T， MINGUS B. Exploring the feasibility of automatically rating online article quality [EB/OL]. [20130810]. http：///wikipedia/wikimania2007/d/d3/RassbachPincockMingus07.pdf.

[7]ZENG H， ALHOSSAINI M A， DING L. Computing trust from revision history [C]// PST06： Proceedings of the 2006 International Conference on Privacy， Security and Trust： Bridge the Gap Between PST Technologies and Business Services. New York： ACM Press， 2006： 33-40.

[8]ZENG H， ALHOSSAINI M A， FIKES R， et al. Mining revision history to assess trustworthiness of article fragments [C]// Proceedings of the 2006 International Conference on Collaborative Computing： Networking， Applications and Worksharing. New York： ACM Press， 2006： 1-10.

[9]HU M， LIM E P， SUN A. Measuring article quality in Wikipedia： models and evaluation [C]// Proceedings of the 16th ACM International Conference on Information and Knowledge Management. New York： ACM Press， 2007： 243-252.

[10]YU S， MASATOSHI Y. Assessing quality scores of Wikipedia article using mutual evaluation of editors and texts [C]// Proceedings of the 22nd ACM Conference on Information and Knowledge Management. New York： ACM Press， 2013： 1727-1732.

[11]LIU J， RAM S. Who does what： collaboration patterns in the Wikipedia and their impact on article quality [J]. ACM Transactions on Management Information Systems， 2011， 2（2）：1-23.

[12]JOHNSON D S， ARAGON C R， McGEOCH L A， et al. Optimization by simulated annealing： an experimental evaluation [J]. Operations Research， 1991， 39（3）： 78-406.

[13]WANG X， XU X， WANG Z. A profit optimization oriented service selection method for dynamic service composition [J]. Chinese Journal of Computers， 2010， 33（11）： 2104-2115.（王显志，徐晓飞，王忠杰.面向组合服务收益优化的动态服务选择方法[J].计算机学报，2010，33（11）：2104-2115.）

[14]TAN C M. Simulated annealing [M]. Vienna： InTech Publisher， 2008： 77-88.

[15]DALVI N， KUMAR R， SOLIMAN M. Automatic wrappers for large scale Web extraction [C]// Proceedings of the 37th International Conference on Very Large Databases. New York： VLDB Endowment， 2011： 219-230.

[16]XIAO S， HE Y. Approach of Chinese event IE based on verb argument structure [J]. Computer Science， 2012， 39（5）： 161-164.（肖升，何炎祥.基于动词论元结构的中文事件抽取方法[J].计算机科学，2012，39（5）：161-164.）

[17]YANG S， LIN H， HAN Y. Automatic data extraction from templategeneration Web pages [J]. Journal of Software， 2008， 19（2）： 209-223.（杨少华，林海略，韩燕波.针对模板生成网页的一种数据自动抽取方法[J].软件学报，2008，19（2）：209-223.）

[18]ETZIONI O， FADER A， CHRISTENSEN J， et al. Open information extraction： the second generation [C]// Proceedings of the 22nd International Joint Conference on Artificial Intelligence. Menlo Park： AAAI Press， 2011： 3-10.

[19]SIMES G， GALHARDAS H， GRAVANO L. When speed has a price： fast information extraction using approximate algorithms [C]// Proceedings of the 39th International Conference on Very Large Databases. New York： VLDB Endowment， 2013： 1462-1473.

[20]MAYS E， DAMERAU F J， MERCER R L. Context based spelling correction [J]. Information Processing and Management， 1991， 27（5）： 517-522.

[21]Princeton University. WordNet： a lexical database for English [EB/OL]. [20130910]. http：//wordnet.princeton.edu/.