《搜索引擎零距离》第1章网页数据挖掘

roki 2009-06-16

第1章网页数据挖掘
1.1 网页数据挖掘定义
数据挖掘(Data Mining，DM)，是从存放在数据库、数据仓库或其他信息库中的大量数据中提取或“挖掘”有趣知识的过程。随着网络的不断发展，因特网目前已成为一个巨大的、分布广泛的和全球性的信息服务中心。从海量的网络信息中寻找有用的知识，早已成为人们的迫切需求。各种类似Google、Baidu等的搜索引擎也层出不穷，Web数据挖掘的应用在现实中不断体现。
Web数据挖掘建立在对大量的网络数据进行分析的基础上，采用相应的数据挖掘算法，在具体的应用模型上进行数据的提取、数据筛选、数据转换、数据挖掘和模式分析，最后做出归纳性的推理、预测客户的个性化行为以及用户习惯，从而帮助决策和管理，减少决策的风险。
Web数据挖掘涉及多个领域，除数据挖掘外，还涉及计算机网络、数据库与数据仓储、人工智能、信息检索、可视化、自然语言理解等技术。
1.2 Web数据挖掘面临的问题
Web的巨大、分布广泛和内容多样使得目前的Web数据挖掘面临着众多问题和挑战。首先，对有效的数据仓库和数据挖掘来说，Web上的数据过于庞大。而且， Web上的数据具有极强的动态性，不仅数量增长快而且更新十分迅速。但是面对如此大量的Web信息，却有调查表明：99%的Web信息对于99%的用户是无用的。这样看来，面对网络上形形色色的用户群体，许多由Web搜索引擎所检索到的资料将会被淹没。
另外，由于Web页面缺乏统一的结构，其结构又比任何传统的文本文档都要复杂，所以要实现基于Web的数据挖掘和信息检索在目前来说是非常具有挑战性的。
Web数据挖掘是一项具有挑战性的课题。它实现对Web存取模式、Web结构和规则以及动态的Web内容的查找。
1.3 Web数据挖掘的分类
一般来说，Web数据挖掘可分为四类： Web内容挖掘、Web结构挖掘、Web使用记录挖掘和Web用户性质挖掘。其中，Web内容挖掘、Web结构挖掘和Web使用记录挖掘是Web 1.0时代就已经有了的，而Web用户性质挖掘则是伴随着Web 2.0的出现而出现的。
Web内容挖掘主要包括文本挖掘和多媒体挖掘两类，其对象包括文本、图像、音频、视频、多媒体和其他各种类型的数据。这些数据一般由非结构化的数据(如文本)、半结构化的数据(如HTML 文档)和结构化的数据(如表格)构成。对非结构化文本进行的Web数据挖掘，称为文本数据挖掘或文本挖掘，是Web数据挖掘中比较重要的技术领域。Web数据挖掘中另一个比较重要的技术领域是Web 多媒体数据挖掘。
目前，关于Web内容挖掘的研究大体以Web文本内容挖掘为主。Web内容挖掘一般从资源查找和数据库两个方面进行研究。
从资源查找的方面来看，Web内容挖掘的任务是从用户的角度出发，怎样提高信息质量和帮助用户过滤信息，主要是对非结构化文档和半结构化文档的挖掘。非结构化文档主要指Web上的自由文本，如小说、新闻等。Web上的半结构化文档挖掘是指在加入了HTML、超链接等附加结构的信息上进行挖掘，其应用包括超链接文本的分类、聚类、发现文档之间的关系、提出半结构化文档中的模式和规则等。
从数据库的方面来看，进行Web内容挖掘主要是试图建立Web站点的数据模型并加以集成，以支持复杂查询，而不只是简单的基于关键词的搜索。这要通过找到Web文档的模式、建立Web知识库来实现。
对文本数据进行挖掘的文档分类和模型质量评价方法与传统的数据挖掘方法类似，分类算法主要应用朴素贝叶斯(Naive Bayes Classifier)。对模型的质量评价主要有分类的正确率(Classification Accuracy)、准确率(Precision)和信息估值(Information Score)。
Web多媒体数据挖掘是指从多媒体数据库中提取隐藏的知识、多媒体数据关联或者是其他没有直接储存在多媒体数据库中的模式。Web多媒体数据挖掘包括对图像、视频和声音的挖掘。Web多媒体数据挖掘首先进行特征提取，然后再应用传统的数据挖掘方法进行进一步的信息挖掘。对网页中的多媒体数据进行特征的提取，应充分利用 HTML的标签信息。
Web数据挖掘是当今世界上的热门研究领域，其研究具有广阔的应用前景和巨大的现实意义。目前，国内的Web数据挖掘尚处于学习、跟踪和探索阶段。Web数据挖掘有许多问题有待于进一步的研究和深化。Web 2.0的出现给Web数据挖掘提出了新的要求。基于Web 2.0的数据挖掘目前还处于起步阶段，它必将成为Web数据挖掘中很重要的一个研究领域。

roki 2009-06-16

1.4 网页数据的结构与特点
1.4.1 HTML超文本标记语言
什么是HTML文件？HTML的英文全称是 Hyper Text Markup Language，中文叫做“超文本标记语言”。和一般文本不同的是，一个HTML文件不仅包含文本内容，还包含一些Tag，中文称“标记”。一个HTML文件的后缀名是.htm，或者是.html。用文本编辑器就可以编写HTML文件。
这就试写一个HTML文件吧！
打开你的Notepad，新建一个文件，然后输入代码到这个新文件，最后将这个文件保存为first.html，其中的代码如下：

<html>
<head>
<title>Title of page</title>
</head>
<body>
This is my first homepage. This text is bold
</body>
</html>

要浏览这个first.html文件，双击它，或者打开浏览器，在File菜单中选择Open命令，然后选择这个文件就行了。
1. 示例解释
这个文件的第一个Tag是<html>，这个Tag告诉浏览器这是HTML文件的头。文件的最后一个Tag是</html>，表示HTML文件到此结束。Tag通常是成对出现的，比如<body></body>，起始的叫做Opening Tag(起始标记)，结尾的就叫做Closing Tag(结尾标记)。在<head>和</head>之间的内容，是Head信息。Head信息是不显示出来的，在浏览器里看不到。但是这并不表示这些信息没有用处，比如，可以在Head信息里加上一些关键词，有助于搜索引擎搜索网页。在<title>和</title>之间的内容，是这个文件的标题。你可以在浏览器最顶端的标题栏看到这个标题。在<body>和</body>之间的信息，是正文。
HTML 文件看上去和一般文本类似，但是它比一般文本多了 Tag，比如<html>、等。在和之间的文字，用粗体表示。顾名思义，就是bold的意思。通过这些Tag，可以告诉浏览器如何显示这个文件。
HTML元素(HTML Element)用来标记文本，表示文本的内容。比如，body, p, title就是HTML元素。 HTML元素用Tag表示，Tag以<开始，以>结束。目前HTML的Tag不区分大小写，比如，<HTML>和<html>其实是相同的。
2. HTML元素(HTML Elements)的属性
HTML元素可以拥有属性，属性可以扩展HTML元素的能力。比如，你可以使用一个bgcolor属性，使页面的背景色变成红色，这时的标记形如<body bgcolor="red">。再比如，你可以使用border属性，将一个表格设置成一个无边框的表格，这时的标记形如<table border="0">。
属性通常由属性名和值成对出现，形如name="value"。上面例子中的bgcolor, border就是name，red和0就是value。属性值一般用双引号标记起来。属性通常是附加给HTML的Opening Tag，而不是Closing Tag。
1.4.2 WML 无线标记语言
WML(Wireless Markup Language，无线标记语言)。这种描述语言同我们常听说的HTML语言同出一家，都属于XML语言这一大家族。WML的语法跟XML一样，WML是XML的子集。HTML语言写出的文件，我们可以在PC机上用IE或是NetScape等浏览器进行阅读，而WML语言写出的文件则专门用来在手机等的一些无线终端显示屏上显示，供人们阅读，并且同样也可以向使用者提供人机交互界面，接受输入的查询等信息，然后向使用者返回他所想要获得的最终信息。
1．WML文件结构
WML由一组互相链接的卡片(CARD)组成。当移动电话访问一个WML页面的时候，页面的所有CARD都会从WAP服务器下载到设备里。CARD之间的切换由电话内置的处理器处理，不需要再到服务器上取信息。CARD可以包含文本、标记、链接、输入控制、任务(TASK)、图像等。CARD之间可以互相链接。
文档的实体包含在<wml>和</wml>标记之间，文档里每个CARD又包含在<card>和</card>标记之间，实际的文字段落则包含在和标记之间。
下面是一个简单的例子：

<?xml version="1.0"?>
<!DOCTYPE wml PUBLIC "-//WAPFORUM//DTD WML 1.1//EN"
　 "http://www.wapforum.org/DTD/wml_1.1.xml">

<wml>
<card id="HELLO" title="HELLO">
　
　Hello world!
　
</card>
</wml>

显示结果如下：

------ HELLO ------
Hello World!
2．WML字符集
WML是XML的子集，继承了XML的字符集设置。WML文档默认的字符集是UTF-8。要显示中文，有两种办法。最简单的办法就是在文档头使用encoding，即把第一行改为：

<?xml version="1.0" encoding="gb2312"?>

然而令人失望的是，有些手机和模拟器并不支持这种方法(将来会的)。所以目前第二种方法更普遍：不改变字符集设置，但是在写中文的时候用UNICODE代表中文字符，如：

 通讯录

代表：

通讯录
3．WML元素：标记(Tag)和属性
WML的主要内容是文本，由于标记会降低与手持设备的通讯速度，所以WML标准里仅仅使用了很少一部分标记。用于表格和图像的标记几乎都被排除了。
与XML一样，在WML语言中，所有元素都放在符号<和>中，并且包含一个开始标记、一个结束标记和一个内容标记，或者使用自身结束的控制标记。就像这样：
<tag>内容</tag> 例如：Hello World!
或<tag/> 例如： 和 <go href="#done"/>
WML同样支持在标记中标出属性。属性是标记的附加信息，与元素的内容不一样，它并不在屏幕上显示出来。属性通常在元素的开始标记后指定。如上面最后一个例子。
由于WML是XML的一种应用，因此所有的WML标记和属性都是区分大小写的(<wml>跟<WML>完全不同)，而且所有的标记都必须正确地结束。WML要求属性的值必须放在双引号或单引号内，单引号可放在属性标记内或双引号内，字符亦可作为属性的值。
4. WML注释
XML支持这样的注释格式：
这些注释在浏览器中并不显示出来。WML不支持嵌套元素注释。WML外部引用方式跟HTML相同，都用<href a="address.html">desc</a>这种形式书写。
WML是一种比较严格的语言，字符使用必须遵守相应的规则，这些基本规则主要包括以下几个方面：
(1) 大小写敏感。在WML中，无论是标签元素还是属性内容都是大小写敏感的，这一点继承了XML的严格特性，任何大小写错误都可能导致访问错误。
一般来说，WML的所有标记、属性、规定和枚举及它们的可接收值必须小写，Card的名字和变量可大写或小写，但它是区分大小写的。包括参数的名字和参数的数值都是大小写敏感的，例如variable1、Variable1和 vaRiable1是不同的参数。
(2) 空格。对于连续的空字符，程序运行时只显示一个空格。属性名、等号(＝)和值之间不能有空格。
(3) 标记。标记内属性的值必须使用双引号(")或单引号(')括起来。对于不成对出现的标记，必须在大于号(>)前加上右斜杠(/)，比如换行标记 必须写成 才正确。
(4) 不显示的内容。在WML中，不显示的字符主要包括换行符、回车符、空格和水平制表符，它们的8位十六进制内码分别是10、13、32及9。
程序执行时，WML将忽略所有多于一个以上的不显示字符，即WML会把一个或多个连续的换行、回车、水平制表符及空格转换成一个空格。
(5) 保留字符。这是WML的一些特殊字符，如小于号(<)、大于号(>)、单引号(')、双引号(")、和号(&)。如果需要在文本中显示这些字符，则在程序中必须转义。这种指定方式在WML中称为字符的实体(Entity)，比如&就是&amp的实体，&lt就是小于号(<)的实体。

roki 2009-06-16

1.5 网页数据挖掘的基本方法
网页数据挖掘的关键部分是信息提取，本节将主要介绍如何通过编写特定格式的表达式来表述网页信息提取的各种需求。
名词定义：
信息提取表达式(Information Extracting Expression，IEE)：用于定义如何提取页面中的信息的表达式。
表述格式：
在两行横线之间的内容是IEE的实际内容，比如：

---------------------------
匹配:	 <title>[$filmTitle]</title>
------------------------

上述IEE表达式的实际内容就是：

匹配： <title>[$filmTitle]</title>

上下的两行横线起到分隔符的作用。
1.5.1 预备知识
1．正则表达式
什么是正则表达式？
“正则表达式”是一个描述一组字符串的模板。正则表达式是使用多种操作符来组合更小的表达式构建类似算术表达式。建立块的基本原则是正则表达式匹配一个单字符。多数字符，包括所有的字幕和数字，都是匹配它们自己的正则表达式。任何带有特殊含义的字符可以以反斜杠开头来进行引用。
2．正则表达式特殊字符
正则表达式可以跟随几个重复操作符(通配符)，正则表达式操作符如表1.1所示。
表1.1 正则表达式操作符
操作符效果
. 匹配任何单个字符
? 之前的项目是可选的，匹配最多一次
* 匹配出现零次或者多次的先前项目
+ 匹配一次或者多次先前项目
{N} 精确匹配N次先前的项目
{N,} 先前的项目匹配N或者更多次
{N,M} 先前的项目匹配至少N次，但是不多于M次
- 表示范围如果不是列表中最先或者最后或者一个范围的结束点
^ 匹配行开始的空字符串；也表示不在列表范围内的字符
$ 匹配行末的空字符串
\d 匹配数字
\s 匹配空格

两个正则表达式可以用中缀操作符“|”连接起来；作为结果的正则表达式匹配任何匹配字表达式的字符串。

1.5.2 变量模板匹配方法
假设我们要采集 http://www.mtime.com/movie/10057 这个页面上的信息。
1．简单模式
先从最简单的做起，从页面中取出页面标题。在这个实际的页面中，标题是这样一段内容：

<title>
阿金 The Stunt Woman(1996) - Mtime时光网
</title>

我们可以这样表达出信息提取的需求：

-----------------------------------------------
	匹配： <title>[$filmtitle]</title>
-----------------------------------------------

上面这句话表达出了这样一个意思：我要找这个页面的标题，而标题的内容是<title>和</title>之间的内容，取到标题内容后，存进名为 $filmtitle的变量。
2．正则限制条件模式
假设某页面上有如下内容:

图片总共的页数：共10页。

如果我们想取出数字10，可以这样表达：

-----------------------------------------------
匹配： 共[$pagenum(\d*?)]页
-----------------------------------------------

这样的话，就能把数字10取出来，并存放入变量 $pagenum。为什么要加上 (\d*?)呢？加上这个表达式就是说，限制需要提取的文本必须是数字。如果没有这个限制的话，就会匹配到“图片总共的页数”这句话中的“的”字，于是 $pagenum就变成“的”了，这是错的。
3．正则模板模式
假设某页面上有如下内容：

1：<a href="xxx.com/song.mp3">菊花台</a>
2：<a href="xxx.com/song2.mp3">发如雪</a>
…………………………………………………
<a href="xxx.com/zhoujielun.jsp">周杰伦</a>

我们试图用以下表达式：

-----------------------------------------------
	匹配： <a href="[$url]">[$songname]</a>
-----------------------------------------------

提取出页面中的歌名和下载地址，但是上述表达式同样能匹配到
<a href=“xxx.com/zhoujielun.jsp”>周杰伦</a>
这一行，这并不是我们所希望的，观察页面后发现，歌名之前是有数字序号的，而歌手之前没有，于是，可以把IEE表达成：

-----------------------------------------------
	匹配:  \d+： <a href="[$url]">[$songname]</a>
	修饰符： 正则模板模式
-----------------------------------------------

上述的\d+表明，我们需要匹配的模板的开始位置必须是一个或多个数字，上述的“修饰符：正则模板模式”表明这是一个用“正则模板模式”处理的IEE。上述IEE可以从页面中提取出如表1.2所示的信息。这正是我们需要的结构化信息。
表1.2 从页面中提取出的信息
url songname
xxx.com/song.mp3 菊花台
xxx.com/song2.mp3 发如雪

补充说明：“正则限制条件模式”与“正则模板模式”可以混合使用。
4．组匹配模式
考虑如下例子。
页面内容：

电影名：黄金甲
主演: <a href="zhoujielun.htm">周杰伦</a><a href="zhourunfa.htm">周润发</a><a href="gongli.htm">巩俐</a>...更多

电影名：色戒
主演: <a href="zhoujielun.htm">梁朝伟</a><a href="zhoujielun.htm">汤唯</a>...更多

我们希望把每个主演以及对应的链接提取出来，为了实现这个需求，IEE表达式如下：

------------------------------------------------
匹配:	'电影名：[$fileName]主演:[%actorInfo=<a href="[$url]>[$actor]</a>%]...更多'
修饰符：'#组模式{& \s};'
---------------------------------------------------

上述IEE表达式中，[%和%]符号之间的式子是组匹配模式的描述文本，而“actorInfo=”这段表明这组信息将被存入名为actorInfo变量中去，而[$url]和[$actor]标识了这个组模式中的两个子变量的名字以及位置，修饰符中的&和\s是组模式的信息提取的结果字符串的分隔符(\s代表空格)。最终这个IEE表达式可以从页面中提取出这样的信息，如表1.3所示。
表1.3 从页面中提取出的信息
fileName actorInfo

roki 2009-06-16

表1.3 从页面中提取出的信息
fileName actorInfo
黄金甲 zhoujielun.htm&周杰伦 zhourunfa.htm&周润发 gongli.htm&巩俐
色戒 Liangchaowei.htm&梁朝伟 tangwei.htm&汤唯

可以根据需要而改变分隔符，如果分隔符这样描述的话:{= & \n}，那么，actorInfo字段的值会变成：

-------------------------------------------------
url=zhoujielun.htm&actor=周杰伦
url=zhourunfa.htm&actor周润发
url=gongli.htm&actor=巩俐
----------------------------------------------------

上述的字符串也是便于处理的。

roki 2009-06-16

1.5.3 树节点直接标识方法
1．单节点模式
1) DOM
通过JavaScript，可以重构整个HTML文档，也可以添加、移除、改变或重排页面上的项目。要改变页面的某个东西，JavaScript就需要有对HTML文档中所有元素进行访问的入口。这个入口，连同对HTML元素进行添加、移动、改变或移除的方法和属性，都是通过文档对象模型来获得的(DOM)。
在1998年，W3C发布了第一级的DOM规范。这个规范允许访问和操作HTML页面中的每一个单独的元素。所有的浏览器都执行了这个标准，因此，DOM的兼容性问题也几乎难觅踪影了。
DOM可被JavaScript用来读取和改变HTML、XHTML以及XML文档。DOM被分为不同的部分(核心、XML及HTML)和级别(DOM Level 1/2/3)。
2) Core DOM
定义了一套标准的针对任何结构化文档的对象。

3) XML DOM
定义了一套标准的针对XML文档的对象。
4) HTML DOM
定义一套标准的针对HTML 文档的对象。以一个页面的数据提取为例子：URL：http://www.baidu.com/search/image_star.html，如图1.1所示，在IE中打开这个页面，并使用IEDevBar展开DOM树。

图1.1 在IE中打开页面
从这张图上，我们可以看到，整个页面被解析成了一棵完整的DOM树，页面中所有的内容都是DOM树上的一个节点。如图1.2所示是在一个信息采集系统的辅助开发工具中打开这个页面的情形。可以看到，我们所要提取的“港台女明星”的信息，在DOM树上0.3.16.1.1.1.5的位置。这个页面是明星的分类和姓名，分为港台女明星、大陆女明星、日韩女明星、欧美女明星几个大类。为了把明星的姓名和所在的分类这组信息正确的提取出来，我们需要编写如下IEE表达式：

-------------------------------------------------------------------
节点:'gt' 0.3.16.1.1.1.5 'target="_blank">[$name]</a>'
节点:'dl' 0.3.16.1.1.1.12 'target="_blank">[$name]</a>'
节点:'rh' 0.3.16.1.1.1.19 'target="_blank">[$name]</a>'
节点:'om' 0.3.16.1.1.1.26 'target="_blank">[$name]</a>'
-------------------------------------------------------------------

图1.2 使用信息采集系统的辅助开发工具打开页面
表达式 0.3.16.1.1.1.5的意思是，DOM树的根节点的第0个子节点的第3个子节点的第16个子节点……依此类推。
以上IEE表达式具有如下功能：
把DOM树上 0.3.16.1.1.1.5位置的内容中符合 'target="_blank">[$name]</a>'模式的内容提取出来，并把[$name]位置的信息放入变量$name中。于是，命名为gt的节点匹配表达式就能够从目标节点中的内容提取出明星名字数组。
2．节点组模式
上一节中，提到了一种节点路径表达式，比如0.3.16.1.1.1.5，但是存在这样一种需求，需要把 0.3.16.1.1.1节点下的所有子节点都进行某种处理，这时候可以用通配符来表示：0.3.16.1.1.1.*，这样就能对DOM树上 0.3.16.1.1.1 路径下所有存在的节点进行处理了。
上节例子的IEE表达式可以写成:

-------------------------------------------------------------------
节点:'star' 0.3.16.1.1.1.* 'target="_blank">[$name]</a>'
-------------------------------------------------------------------

因此系统能自动寻找符合节点组表达式的目标节点上的内容。这样处理，起到的效果和指定节点的绝对路径相似。

roki 2009-06-16

1.5.4 语义规则识别方法
本章前几节描述的都是在目标文本格式比较有规律的情况下，能够用一定的模式去把目标信息匹配出来，存入不同的变量数组中去，但如果目标文本是无格式规律的文本，则用之前的方法就无法处理了，比如以下文本：“周杰伦-菊花台长度4分12秒，大小2M，类型MP3 <a href=http://download.com/juhuatai.mp3>下载</a>”。
为了对上述的文本进行语义分析，我们需要把句子中的词素(词语的基本单位)提取出来。

描述格式：词素 -> 词素类型

比如：

周杰伦 –> NAME
长度 –> LENGTH
大小 –> SIZE
4 -> NUM
<a href=http://download.com/juhuatai.mp3>下载</a> -> HREF

完成上述分析过程之后，目标文本中的基本语义就大致被分析出来了，考虑下面最简单的情形。
我们要把目标文本中的NAME语素存进$songer变量, 把LENGTH语素存进 $songTime变量，把HREF语素存进 $downloadAddress变量。为了表述上述需求，可以编写如下IEE表达式：

-------------------------------------------------------------------
自动识别:
LENGTH->$length
NAME->$singer
NUM->$fileSize
HREF->$downloadAddress
-------------------------------------------------------------------

以上IEE表达式表述了如何把自然语义分析之后提取出来的语素存进对应的变量中去。