Web内容挖掘

Web Content Data Mining

Abstract:    With the significant growth of the Web, there is an ever-increasing scale of data and information published in numerous Web pages. The research in Web content mining aims to develop effective techniques to extract and mine useful data from these Web pages. This paper first introduces some approaches of extracting data from Web pages. Then, we describe the importance of Web page blocks. A Web page can be partitioned  into multiple segments or blocks，and these blocks have different functions. Page blocks is very important at the process of Web content mining, otherwise it will cause great damage to the Web data mining. At the last of this article, we describe two projects of searching for web services and schema matching about mining semantics on the Web. Both of them exploit a corpus of structures. They correspond to the two steps in searching and accessing the hidden web: (1) locating desirable data source; (2) reformulating a query onto the schema of the source. Both steps rely on mining semantics and a good understanding of the structure information.

Key words:    data mining; Web content; page blocks; semantic Web

摘  要:    随着Web规模的显著增长，众多网页背后滋生出前所未有的数据和信息量。Web内容挖掘旨在为Web应用开发出高效的Web数据挖掘技术。本文先介绍了一些从Web网页上提取数据的方法。然后，本文介绍了Web网页分块的重要性。一个Web网页可以划分为不同的块，这些块有不同的作用。在Web内容挖掘过程中，分块技术很重要，否则会为Web上的数据挖掘造成很大程度的伤害。最后，本文的Web语义挖掘部分介绍了Web服务搜索与模式匹配。这两个项目利用了语料库的结构。它们在搜索隐蔽网络内容时分为两个过程：（1）定位有价值的数据；（2）把对数据源模式的查询再用形式表示。这两个过程从语义程度上进行数据挖掘，需要对数据的结构信息有一定的了解。

关键词:    数据挖掘;Web内容;网页分块;Web语义

中图法分类号:    TP301　　　文献标识码: A

1  引言

Web是一个强大的环境，催生了大范围的应用与服务，提供了用户与企业、机构、非盈利组织或其他用户的交互。关键的Web事务度量需要数据的获取与处理。这样的数据保证了Web服务的高效运行。

Web挖掘技术旨在开发新的技术，从而能够高效地从Web页面中提取有用的信息。由于Web固有的、不断扩大的异质性，基于Web的应用需要整合从不同来源、不同渠道获得的多种类型数据。Web挖掘技术在Web数据提取、Web语义挖掘和Web网页块挖掘方面都有了令人惊叹的成果。

本文一开始在第2部分介绍了Web数据提取的一些方法。这是Web应用的数据来源。第3部分描述了Web网页分块的重要性。第4部分给出了Web语义挖掘的一些应用。

2  Web数据提取

人们可获取的Web数据分为两类，非结构化数据和结构化数据。非结构化的数据在HTML页面上以文本形式存在；而结构化数据存在于数据库和知识库中。Web服务和Web应用从本质上都是对Web数据的分析和操作，因此Web数据的提取对Web发展起到重大的影响。

2.1  非结构化数据提取

强大搜索引擎的出现提高了我们获得Web数据的能力，但是这仅仅局限于非结构化数据。Web上可获取很多文本形式的非结构化数据。基于自然语言处理技术（NLP），在内联网上的这些文本化数据经常被用于提取概念和它们之间的关系。P. Pantel的The Terascale Challenge[1] 和Large-Scale Extraction of Fine-Grained Semantic Relations between Verbs[2]给出了这方面的研究成果。Edoardo Airoldi给出了另外一种使用文本化数据的方法[3]。

现在的非结构化数据提取技术通常是以机器学习和自然语言加工的方式，从人为定下标签的样本上获得数据提取规则。现在一部分研究者通过Web上的常见语言模式以及信息冗余来发现概念、概念之间的关系以及已命名实体。这个语言模式的信息可自学习获得或者由人类用户提供。另外一个该领域的研究是Web问答。虽然问答技术最早应用于信息检索文献，但由于Web是最大的信息来源，加上很多Web搜索查询的目标是获取简单问题的答案，因此问答技术在Web上也显得非常重要。[4,5] 通过查询转换、查询扩展和选择扩展了Web问答技术。

2.2  结构化数据提取

结构化数据的挖掘应该是Web内容挖掘方面范围最广的研究主题了。结构化数据隐藏在Web查询接口（Web表单）、Web服务和寻常的数据库API中。接触这类数据通常需要提交完整的Web表单，或使用如SOAP这样的协议通过编写代码来访问Web服务。

结构化数据的提取方法有几种。第一种方法是针对各个Web网站，根据观察到的数据格式模式，手动地编写数据提取程序。这个方法需要众多的劳动力和时间的消耗，所以并不适宜大量的Web网站数据提取。第二种方法是包装归纳或包装学习，是如今的主流技术。包装学习是这样工作的：用户先手动地为页面集合增加标签，学习系统在这些页面上开始产生规则，最终的规则可用于从Web页面中提取目标项目。包装归纳系统包括 WIEN [6], Stalker [7], BWI [8], WL2[9]等。第三种是自动化的方法。Web上的结构化数据对象通常是来自底层数据库的数据库记录，然后在Web页面上以固定的模版呈现出来的。自动化方法旨在Web页面上发现模式或语法，然后用于提取数据。自动化方法包括IEPAD [10], MDR [11], RoadRunner [12], EXALG [13], [14], [15], [16]等。

2.3  从大型特定区域网站提取信息

鉴于Web网站的规模和多样性，发展成熟的Web语义嵌入技术还很困难。但是，凭借现在的技术可以设计一个以任务为导向的数据提取基本体。

文献[17]展示了新的数据提取任务，能够处理更多特定领区域内异质的Web数据源。同一区域的Web网站之间大多彼此相似。作者的目标是在特定网站区域下，通过观察用户点击样本网站的路径，用学习模型在通过尽可能少的页面的前提下到达用户目标页面。例如，从大学主页上提取计算机科学系的演讲通知；从电子商店中找到一个目录层下特定商品的价格；从企业列表中寻找特定企业的联系地址等。

信息提取任务分为两个阶段：训练阶段和寻找阶段。训练阶段时，CRF（Conditional Random Field）学习用户点击到达目标页面的路径，并标记这些过程页面。为CRF状态的路径编码的方式有很多，这取决于用户监督的层次。用户只需要给出提示是否已经到达目标页面。训练阶段通过上阶段的信息重叠，加强模型的学习程度，确定到达目标页面的页面顺序。这需要为路径学习和页面寻找建立一个健全、统一的机制。

这些模型需要我们获得很多特征变量，包括从超链接和HTML页面中提取出的关键词和模式、邻近页面的从属关系、统一框架中已命名实体存在的数据库等。有了这些数据挖掘的支持，作者给出的模型在实验中能够达到90%的准确率。

2.4  从HTML存储库提取数据

HTML文件上有大量有价值的数据，这些数据很大范围得覆盖在互联网和企业内联网中。但是，HTML文件主要是基于描述的，很难对其进行查询。[18]开发了一个从上千个HTML文件中提取有价值数据的系统。结果中的冗余数据系统会自动消除。作者提出了基于不同捕获概率的捕获-再捕获模型，用来评价该系统结果的覆盖情况。同时，作者还提出评价提取信息错误率的技术和提高信息质量的交互技术。

具体说来，作者建立的系统分为两个阶段。第一阶段提取HTML数据并把它们转化为结构化形式。多余的信息会自动消除。此外，系统评测了HTML数据集来源对应的结果集的覆盖范围。第二阶段对提取的数据的质量进行评价与提高。这个阶段中，系统向用户展示随机样本，让用户选择出他认为错误的信息，这样系统获得了用户的反馈意见。基于该反馈意见，系统自动消除之前提取到的错误信息。虽然不是强制用户交互，系统为用户交互提供的增值服务还是提升了提取的信息质量。

3  Web网页块

一个典型的网页包含很多块或区域，例如主要内容区、导航区、广告区等等。有时候为一些实用的Web应用划分区域是很重要的。比如在Web数据挖掘中，页面分类、聚类、识别主要内容区或者移除噪声块（noisy blocks，如广告等）都需要Web网页分块技术。[19,20]表明，噪声块包含的信息会对数据挖掘起到很严重的影响。

文献[21]为Web页面的各个块自动计算重要值，以判断页面块的重要程度。作者首先基于视觉的页面分割技术把一个Web页面分为分层结构的语义块，然后提取出空间特性和内容特性，为每个块提供一个特征向量。最后，学习算法建立一个模型为Web页面的每个块分配重要值。在实验中，最好的模型表现是Micro-F1  80.2%和Micro-Accuracy 86.8%。量化Web页面块的重要程度能帮助我们移除噪声块，从而提高数据挖掘的质量。

4  Web语义挖掘

如今，语义网的挖掘是Web研究领域的热门目标。但是，随着可获取的语义网数据逐渐增长，这些数据的挖掘工作将对语义网的研究起到更加重要的作用。T.Berners-Lee提出，语义网是当今网络的扩展形式。语义网给出了信息的明确定义，让人与电脑更好的合作共处。

文献[22]证明了大型语料库结构有助于解决桥接异构性语义的基本困难。利用大型语料库结构（例如WSDL文件）的统计分析，作者详细描述了Web服务搜索和模式匹配。Web服务搜索部分描述了一个智能的Web服务搜索引擎，这个引擎可以精确地寻找到符合用户需求的Web服务操作。模式匹配部分描述了基于语料库的模式匹配框架，利用已知的模式库来匹配未知模式。这两个工程应用了Web语义的挖掘，提供了Web数据的搜索和匹配功能。

4.1  Web服务搜索

Web服务是松散耦合的软件组件。一个Web服务通常由参数的操作组成。每个这样的操作先携带一个内含输入参数列表的SOAP协议包，完成特定任务之后，在一个SOAP协议输出包中返回操作的结果。

图1  Web服务例子。每个服务包含带有输入输出参数的操作

搜索结构化数据需要理解底层数据源的语义。这个结构的大部分(但不是全部)有其指定的模式。然而，无论是Web服务的文本描述和操作还是输入输出参数的名字，都没有完全覆盖底层语义的操作。这提高了Web服务相似性搜索的难度。这足以说明，语义的知识对于确定操作相似性起到很关键的作用。大致来说，作者提出的Web服务搜索算法整合了多个决定Web服务相似程度的参考量，尤其是操作和整个服务的文本化描述的相似性，以及操作参数名字的相似性。

该算法分为两个部分，第一部分把参数聚类成概念，第二部分计算操作的相似性。

（1）参数聚类成概念。由于Web服务的输入输出通常携带很少的参数，加上输入输出参数命名规则的不确定性，人们很难获得输入和输出参数的底层语义。因此，作者采用了Web服务输入输出的术语同现方法，把术语聚类成有意义的概念。这些有意义的概念有助于识别输入输出的相似性，进而有助于识别Web服务操作的相似性。作者采用的聚类算法是agglomerative聚类算法[23]的提炼。

（2）计算操作相似性。直觉上来说，两个操作的相似性与它们的描述、输入输出参数、主机Web服务等的相似性有关。算法在计算Web服务相似性时考虑了参数名字的相似性、输入/输出概念的相似性、输入/输出的相似性、Web服务操作的相似性等。综合上述相似性的计算，算法最终获得Web服务的相似程度。根据Web服务的相似程度，搜索引擎可以提供与用户搜索服务相近的Web服务列表。

4.2  模式匹配

    模式匹配是识别不同模式下的相似元素的一致性问题。模式匹配很难实现自动化，因为数据的准确语义只有其设计者才能完全清楚，模式本身并不了解。所以语义匹配过程需要人的参与。

    之前的方法只考虑在两个匹配模式中当前的信息。这样的模式通常缺少能够发现匹配的有效证据。比如考虑图2中T1和T2表定义的结构。虽然两个表都描述了项目的可用性，但是如果单独考虑一张表将无法得到匹配。

图2 T3、T4模式的知识能够有助于匹配T1和T2

    作者描述的模式匹配算法采用了基于语料库的匹配。在特定区域内与语料库中的模式进行匹配提高了模式匹配算法的健壮性。语料库保存了区域内可供选择的概念描述。

    假设模式S中有一个元素e（表或属性名），在语料库中与e相似的元素集合为Ce。在上面的例子中，T1.BookAvailability和语料库中的T3.BookStore相似（它们的列彼此相似）。同样，T2.Stock与 T4.ProductAvailability相似。把T1、T3联系起来，再把T2和T4联系起来，显然可以更好的匹配T1和T2。根据这个直觉知识，作者提出了Augment算法。

    另外一个利用语料库的模式匹配算法对模式及其元素进行统计评估。比如，给定一个语料库的库存模式，ProductAvailability表一直拥有与productID相似的列，并且有一个关于warehouseID属性的外键。这些统计信息可以创建模式的区域约束（比如如果一个表没有能够匹配productID的列，那它不太可能匹配ProductAvailability表）。这些约束有助于提高模式匹配的质量。

5  结束语

数据挖掘是Web内容挖掘的基础。Web上隐藏了大量的有价值信息。Web内容的数据挖掘包括结构化的数据挖掘和非结构化的数据挖掘。分析这些数据有助于Web提供更好的服务。

大部分Web应用都需要提取Web数据，并在此基础上进行分类、聚类等。Web网页可以根据隐藏的数据分成若干个块。识别每个块的功能可以提高Web页面分析质量。除此之外，Web底层语义展示了Web服务的操作与性质，分析底层结构化数据的语义可以匹配出符合用户需求的Web服务。

数据挖掘将继续对Web内容挖掘产生巨大的影响。我们可以确信，如何提高Web数据挖掘的质量与效率方面的研究还会继续深入下去。

致谢  在此,我们向对本文的工作给予支持和建议的老师和同学。

References:

[1]  Ravichandran D., P. Pantel and E. Hovy (2004) .The Terascale Challenge. Proceeding of KDD Workshop on Mining for and from the Semantic Web (MSW’04), Seattle, USA,2004.

[2]  T. Chklovski and P. Pantel. Large-Scale Extraction of Fine-Grained Semantic Relations Between Verbs, 2004.

[3]  Bai, X., Padman, R., & Airoldi, E. (2004). Sentiment extraction from unstructured text using tabu search-enhanced Markov blanket. In Proceedings of the international workshop on mining for and from the semantic web.24~35.

[4]  Kwok, C., Etzioni, O., Weld, D. Scaling Question Answering to the Web. WWW-00, 2000.  

[5]  Radev, D., Fan, W., Qi, H., Wu, H., Grewal, A. Probabilistic Question Answering on the Web. WWW-02, 2002.  

[6]  Kushmerick, N. Wrapper Induction: Efficiency and Expressiveness. Artificial Intelligence, 118:15-68, 2000.  

[7]  Muslea, I., Minton, S. and Knoblock, C. A Hierarchical Approach to Wrapper Induction. Agents-99, 1999. 

[8]  Freitag, D and McCallum, A.  Information Extraction with HMM Structures Learned by Stochastic Optimization. AAAI-00, 2000. 

[9]  Cohen, W., Hurst, M., and Jensen, L. A Flexible Learning System for Wrapping Tables and Lists in HTML Documents. WWW-02, 2002.

[10]  Chang, C-H., Lui, S-L. IEPAD: Information Extraction Based on Pattern Discovery. WWW-10, 2001.

[11]  Liu, B., Grossman, R. and Zhai, Y. Mining Data Records in Web Pages. KDD-03, 2003.  

[12]  Crescenzi, V., Mecca, G. and Merialdo, P. ROADRUNNER: Towards Automatic Data Extraction from Large Web Sites. VLDB-01, 2001.

[13]  Arasu, A. and Garcia-Molina, H. Extracting Structured Data from Web Pages. SIGMOD-03, 2003.

[14]  Embley, D., Jiang, Y and Ng, Y. Record-boundary discovery in Web documents. SIGMOD-99, 1999.  

[15]  Lerman, K., Getoor L., Minton, S. and Knoblock, C. Using the Structure of Web Sites for Automatic Segmentation of Tables. SIGMOD-04, 2004.

[16]  Pinto, D., McCallum, A., Wei, X. and Bruce, W. Table Extraction Using Conditional Random Fields. SIGIR-03.

[17]  Sunita Sarawagi, V. G. Vinod Vydiswaran. Learning to extract information from large domain-specific websites using sequential models. Sigkdd Explorations, 6(2): 61-66, 2004.

[18]  Ruth Yuee Zhang, Laks V. S. Lakshmanan, Ruben H. Zamar. Extracting Relational Data from HTML Repositories. Sigkdd Explorations , 6(2): 5-13, 2004.

[19]  Yi, L., and Liu, B. Web Page Cleaning for Web Mining through Feature Weighting IJCAI-03, 2003.  

[20]  Yin, X. and Lee, W. S. Using Link Analysis to Improve Layout on Mobile Devices. WWW-04, 2004.  

[21]  Ruihua Song, Haifeng Liu, Ji-Rong Wen, Wei-Ying Ma. Learning important models for web page blocks based on layout and content analysis. Sigkdd Explorations ,6(2):14-23, 2004.   

[22]  Xin Dong, Jayant Madhavan, Alon Y. Halevy. Mining Structures for Semantics. Sigkdd Explorations, 6(2):53-60 , 2004.

[23]  L. Kaufman and P. J. Rousseeuw. Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley& Sons, New York, 1990.