3.2 信息检索技术的延伸——数据挖掘

从技术上来说，搜索引擎和数据挖掘是互补且有一定的相同之处。但是，数据挖掘超越了搜索技术，并正在将搜索技术推向一个新层次。

搜索引擎和数据挖掘处理的都是字串和文本，从这一点上它们是相同的。但是，搜索引擎提供的功能是单一的，主要是查找定位符合用户查询需要的文献的位置，尤其是在网络上的位置，因此它需要用户提供由一个或若干关键字串组成的查询表达式。它开始于用户的查询表达式，结束于一个按照某种方式（大部分是相关程度）排序的信息以及信息位置的列表（List），基本是一个简单的顺序过程，支持这一过程的核心技术是数据库和索引，而代理技术则为它的智能化提供了有力的帮助。尽管数据挖掘的确也提供定位信息位置的功能，但这不是它的主要功能。好的数据挖掘能够自动地提取相关信息之间有价值的关系知识，并且将这些知识以可视的、动态改变的方式反馈给用户。可视方式给用户以直观的、易于快速理解的知识掌握途径，而动态改变特性提供用户以及时性。因此，数据挖掘开始于一些文本（最好是已经具有一定的物理相似性，如相同的文本格式等），结束于文本之间的潜在关系知识，而这个过程一般是一个需要不断反馈和调整的复杂过程。支持这一过程的核心技术是特征提取、分类、聚类和关联规则发现、知识评价等。

可以认为搜索引擎的结果往往可以作为数据挖掘的输入，也就是说，搜索引擎在一定程度上可以被认为是数据挖掘的前处理，后数据挖掘则可被理解为信息检索的延伸。

3.2.1 数据挖掘基本概况

1.数据挖掘概述

数据挖掘（Data Mining，DM）是从大量的、不完全的、有噪声的、模糊的、随机的数据集中识别有效的、新颖的、潜在有用的以及最终可理解模式的非平凡过程。数据挖掘也被称为“知识发现”。数据是形成知识的源泉，就好像从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数据库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至可以是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理、查询优化、决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘把人们对数据的应用从低层次的简单查询，提升到了从数据中挖掘知识，提供决策支持。

数据挖掘已在电讯、信用卡、医疗等方面得到应用。其实在日常生活中我们也可以看到许多数据挖掘的应用，例如，如果你在一家比较著名的电子商务网站购买了一张周星驰的经典搞笑片《大话西游》，该网站会提醒你：

【购买该商品的用户还买了这些商品】

《家有喜事》

《武状元苏乞儿》

《秀兰邓波儿》（12套装）

这些就是用数据挖掘技术从购买这部片子的人群中统计出来的。当然这只是一种比较简单的应用。但从这个例子，我们可以初步认识到：数据挖掘是一个利用各种分析工具在海量数据中发现模型和数据间关系的过程，这些模型和关系可以用来做出预测。

为此，我们可以进一步定义数据挖掘。

数据挖掘是伴随着数据仓库技术的发展而逐步完善起来的，主要是为了处理大量的模糊和随机数据，以进行统计、分析、综合和推理后，寻找其后隐含的规律及事物间的相互关联，并对未来的活动进行预测，同时将其模型化，来完成辅助决策的作用。

2.数据挖掘的基本原理

数据挖掘是从大量的、不完全的、有噪声的、随机的数据中，提取潜在有用的信息和知识的过程。数据挖掘源自人工智能的机器学习领域，是在一个已知状态的数据集上，通过设定一定的学习算法，从数据集中获取所需的知识。这些知识能够用于信息管理、智能查询、决策支持、过程控制以及其他方面。数据挖掘的最初对象是一些大型的商业数据库，它通过描述数据、计算统计变量（比如平均值、均方差等），并将这些变量用图表直观地表示出来，进而找出数据变量之间的相关性，简单的概括即发现知识，以提供解决问题的依据。随着数据挖掘技术在商业数据库中的成功应用，它又被迅速移植到电信、医疗保险等领域，而Internet的出现为它提供了一个更为广阔的空间。借用数据挖掘的原理来实现网络数据的深层挖掘，发现并组织网络知识，是将网络信息检索技术推向智能化高度的有效手段。

3.数据挖掘技术的实现流程（如图3-1所示）

（1）数据采样。从大量的数据中取出一个与挖掘目标相关的数据子集，通过数据样本的精选，不仅能减少数据的处理量，还能突出相关的规律性。数据采样的代表性和质量尤其重要。

（2）数据分析。最终的目的是要从采样中分析出多个因素相互影响的关系。这些关系需要经过仔细分析、观察和反复试验，先分析众多因素之间的相关性，再按其相关的程度了解它们之间相互作用的情况，从而重视数据分析呈现出的新关系。由于数据分析是一个反复尝试的过程，因此通过可视化的操作能有效提高数据分析的效率。如果数据可行，直接进入数据模型的建立，反之则需要进行数据调整。

（3）数据调整。在数据采样和分析实施之后，会更加了解数据的状态和趋势，需要调整的内容有：① 需要重新对采样数据进行分析；② 需要对问题进一步细化，要求审视采样数据集，看它是否适应建立数据模型。也可能按照对整个数据挖掘过程的新认识，组合或者生成一些新的变量，体现对状态的有效描述。这样才能对下一步数据挖掘应采用的技术手段就更加明了。

（4）建立数据模型。这是数据挖掘工作的核心环节，需要采用数理统计方法、人工神经元网络和决策树等多种技术。最常用的主流技术手段是利用数理统计方法实现对各种不同类型模型、不同特点数据的回归分析，对多种试验设计模型的方差分析，以及处理一般线性模型和广义线性模型、多变量统计分析、聚类分析、时间序列分析等。数据挖掘实现流程如图3-1所示。

通过这些数理统计工具不仅能揭示已有数据间的新关系和隐藏着的规律性，而且能反过来预测其发展趋势或在一定条件下将会出现什么结果。数据挖掘中使用哪一种方法主要取决于数据集的特征和要实现的目标，一般要多试几种方法，从实践中选出最适合的。

3.2.2 数据挖掘常用的技术

1.分类-决策树

决策树（Decision Tree）学习是以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则的事例中推理出决策树表示形式的分类规则，采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较并根据不同的属性值判断从该节点向下的分支，并在决策树的叶节点得到结论。所以从根到叶节点的一条路径就对应着一条合取规则，整棵决策树就对应一组析取表达式规则。基于决策树的学习算法的一个最大优点就是它在学习过程中不需要使用者了解很多背景知识，只要训练例子能够用“属性-结论”式的方式表示出来，就能使用该算法来学习。

一棵决策树由三部分组成：节点、分支和叶子。将给定的训练集作为决策树的根节点，训练集中的记录具有标识类别的字段。用信息增益来寻找节点上具有最大信息量的字段，根据对该字段的不同取值建立该节点的若干分支，并为所有分支子集建立对应的节点。在每个分支子集中重复建立下层分支和节点，直到节点中所有记录的类别都相同为止。这样便生成一棵完整的决策树，然后把决策树的节点分裂过程转化为“如果……那么……”的规则，利用这些规则就可以对新数据进行分类。

2.聚类

所谓聚类（Clustering）就是按照事务的某些属性，把事务聚集成类，使类间的相似性尽量小，类内相似性尽量大。正所谓“物以类聚”。用户想知道他们的客户中是否存在相似性，并以此划分消费群体，从而根据不同类型的客户提供更好的服务，以便更好地销售产品和开拓市场。聚类技术试图找出数据集合中的共性和差异，并将具有共性的元组聚合在相应类中。聚类技术可根据数据之间的差异将它们分组。从分组的图表中可以获得数据集中关于数据分组情况的知识。一旦将类划分完毕，分析人员就可以着手了解这些类之间的共性和差异。

3.神经网络

神经网络（Neural Network）是一种很有效的预测模型技术。数据挖掘的重要问题之一是决策哪些属性是与要建立的模型最相关、最重要的属性，以便模型能尽量正确地进行预测。神经网络大致是根据人脑的组织和学习方式构成的。

神经网络中有两种重要的结构。

（1）节点：对应于人脑的神经元。

（2）连接：对应于人脑神经元之间的联系。

神经网络的工作原理是这样的：它从左边的节点获得预测的属性值，对这些值进行计算后，在最右边的节点产生新值，而最右边节点的值就表示神经网络模型做出的预测值。作为预测模型，神经网络在商业界得到了广泛的应用。

4.关联规则

关联规则挖掘大量数据项集之间的关联及相互联系，帮助制定商务决策。关联规则挖掘的一个典型应用是购物篮分析，通过分析顾客购物篮中的商品，从而分析顾客的购物习惯，并进一步分析哪些商品频繁地同时被顾客购买，帮助零售商指定营销策略。

关联规则的挖掘基于多维数据集。维度是多维数据集的重要属性，多维数据集的维度属性有多种类型：分类属性具有有限个不同值，值之间无序，如职业、颜色等维度是多维数据集的分类属性；量化属性是数值型，且值之间有某种隐含的序，如年龄、价格维度是多维数据集的量化属性。

关联规则的数据挖掘技术根据对量化属性的处理分为3种基本方法。

（1）使用预定义的概念分层对量化属性离散化，如把收入划分为若干区间：0～2万，2万～3万，3万～4万等，用这些区间替代收入属性的值。这种离散化是静态的、预定义的，离散化后的属性具有区间值，可以进行分类处理。

（2）根据数据的分布，将量化属性离散化到“箱”。此策略将数值属性的值处理成量，以满足某种挖掘标准的、动态的方式进行离散化。

（3）根据数据点之间的距离将其离散化。

3.2.3 信息检索和数据挖掘的技术关联分析

在信息量极大丰富的网络资源中，蕴涵着大量潜在的有价值的知识。与此同时，人们却面临着“信息爆炸而知识匮乏”的问题。目前的数据库系统和搜索引擎也可以高效地实现数据的统计和信息查询，但由于各类搜索引擎均存在查准率、查全率不高的现象，无法发现信息中存在的关系和规则，从而无法满足人们希望能够从网络中快速、有效地发现有用的知识，来分析当前的态势和预测未来的发展趋势的要求。同时电子商务以及各种网络信息服务迅速兴起，原有的网络信息处理与组织技术无法赶上这样的发展趋势。人们需要有新的技术，数据挖掘正是在这样的应用需求环境下产生并迅速发展起来的，它的出现为自动和智能地把海量的数据转化为知识、有用的信息、新闻、或新闻线索提供了手段。

传统的数据库中的知识发现（KDD）虽然能从数据库中发现潜在的、有意义的、未知的关系，模式和趋势，并以易被理解的方式表示出来。但其所运用的技术所涉及的主要是结构化的数据库，而网上数据资源往往是经常变动和不规则的。因此，人们需要比信息检索层次更高的、能包含网络数据库在内的新的数据挖掘技术，从而以更有效的手段对各种大量数据进行挖掘以发挥其潜能。

网络信息资源上的数据挖掘和网络信息检索是两种不同的技术，它们的方法不同、着眼点不同、目的也不同。信息检索是要帮助用户从大量的文档中找到满足需要的资源。而网络数据挖掘是为了揭示数据中隐含的知识，它是比信息检索层次更高的一种技术。

1.信息检索和数据挖掘的比较分析

（1）信息检索和数据挖掘的原理比较

信息检索就是用户的信息需求与存储在数据库中的信息进行比较和选择，即匹配（match）的过程。也就是对某一数据库采用一定的技术手段检索出相关的信息。

数据挖掘就是从大量不完全的、有噪声的、模糊的或者随机的数据中提取人们事先不知道的但又是有用的信息和知识。网络数据挖掘是数据挖掘技术在网络信息处理中的应用，是从Web网站的数据中发掘关系和规则。Web上的每一个站点就是一个数据源，每一站点之间的信息和组织都不一样，这就构成了一个巨大的异构数据库环境。

（2）信息检索和数据挖掘的过程比较

信息检索：① 信息进行采集、标引、存储、处理，形成数据库；② 提供能表达用户信息需求的检索模型机制，如提供布尔逻辑算符、截词符、权值等；③ 以优良的匹配选择算法完成信息集合与需求集合的一致性比较；用户对初步检索结果进行相关性判断，调整或修改检索策略；④ 根据用户返回反馈信息，重新检索，直到检出满意的结果为止。

数据挖掘：① 资源发现，即检索所需的信息资源；② 信息选择和预处理，即从检索到的网络资源中自动挑选和预先处理得到专门的信息；③ 概括化，即从单个的Web站点以及多个站点之间发现普遍的模式；④ 分析，对挖掘出的模式进行确认或者解释。将挖掘来的信息与挖掘目标的特征进行匹配。

（3）信息检索和数据挖掘的类型比较

信息检索：① 数据检索：以查找某一数据为目的，利用各类检索系统查出包含在信息中的某一数据、参数、公式、图表或化学分子式等的检索；② 事实检索：是以事实为检索对象，是从存储事实信息系统中查找出指定的事实的行为；③ 文献检索：能够满足用户需求的文献线索或文献全文。

数据挖掘：① 内容挖掘：即从网络的内容/数据/文档中发现有用信息的过程；② 结构挖掘，即挖掘Web潜在的链接结构模式，它有助于用户找到相关主题的权威站点，并且可以概观指向众多权威站点的相关主题的站点；③ 用法挖掘：可以了解用户的网络行为数据所具有的意义。

（4）数据挖掘与搜索引擎的数据处理比较

搜索引擎：它由Robot、索引数据库和查询引擎组成。搜索软件Robot对整个网络进行逐一搜索，尽可能多地发现新的信息。全文检索技术对搜集到的信息建立索引并存入索引数据库中，查询引擎接收并分析用户的查询，根据较为简单的匹配策略搜索索引数据库，最后将结果地址集提交给用户。搜索引擎只能处理以关键词形式表示的简单目标，无法处理用户给出的样本形式的复杂模糊目标。

数据挖掘：它沿用了Robot，全文检索等搜索引擎的优秀成果，同时综合运用归纳学习、机器学习、统计分析等方法和人工智能、模式识别、神经网络领域的各种技术。数据挖掘系统与搜索引擎的最大不同在于它能够根据用户定义的要求，根据目标特征信息在网络上或者数据库中进行有目的的信息检索。

2.网络数据挖掘的技术难点和XML语言的拓展运用

（1）网络数据挖掘的技术难点

网络上有海量的数据信息，利用现有的检索技术并不能满足人们的应用需求。相对于网络上的数据而言，传统的数据库中的数据为完全结构化的数据，而网络上数据的特点是数据没有严格的结构模式、含有不同格式的数据（文本、声音、图像等）、面向显示的HTML文本无法区分数据类型等。显然，面向网络数据挖掘比面向单个数据仓库的数据挖掘要复杂得多。

首先，网络数据挖掘面对的是一个大而复杂的异构数据环境，若将网络上每一站点视为数据源，那么每个数据源都是异构的，各站点间的信息和组织都不一样，如果想利用这些数据进行数据挖掘，那么必须研究站点之间异构数据的集成问题，这是对数据进行分析、处理的基础。

其次，网络上的数据与传统的数据库中的数据不同，多为半结构化或非结构化数据，没有特定的模型描述。因此，传统数据挖掘的方法在此并不完全适用。寻找一个半结构化的数据模型是解决问题的关键。除了要定义一个半结构化数据模型外，还需要一种半结构化模型抽取技术，即自动地从现有数据中抽取半结构化模型的技术。面向网络数据挖掘必须以半结构化模型和半结构化数据模型抽取技术为前提。近来兴起的XML数据就是一种自描述的半结构化数据，它是面向数据的，支持用户自定义文档标记，用有序的、嵌套的元素来组织有一定结构的数据。它的出现推动了WWW在电子商务、电子数据交换和电子图书馆等多方面的应用。

（2）XML语言在信息检索和数据挖掘上的运用

HTML是目前因特网上广泛应用的标记语言，其优点是：非常简单、固定的样式、链接标准且简易；支持表格、编程简单。但是也存在难以扩展、交互性差、语义性差、超链接为单向、链路丢失后不能自动纠正、动态内容需要下载的部件太多致使搜索引擎返回的结果过多、缺乏对双字节或多国文字的支持等不足。尤其是目前基于HTML的搜索引擎存在着返回结果太多，检索精度差的弊端，而XML可以却有效地克服这些不足。

XML（eXtensible Markup Language，可扩展标记语言）是一种能更好地描述结构化数据的语言，作为通用标记语言（Standard Generalized Markup Language，SGML）的一个子集，1998年成为W3C（World Wide Web Consortium）认可的一个标准。作为HTML语言的一种补充，XML由于具有一系列特性，如可扩展性、简单性、开放性、互操作性、支持多国语言等，从而能够较好地解决HTML语言的一些缺陷，已在Web页面上得到了广泛应用。现在主要的浏览器厂家都在各自的浏览器中不同程度地支持XML。IBM、Oracle等数据库厂商都在各自的数据库产品中加入了处理XML数据的功能。

XML句法可标注出文档的结构和目的，这样就可缩小检索范围，提高提高检索精度。例如，用户想购买二手车，就可将查询限制为用于描述“汽车销售”的标识中。

XML能帮助人们辨别模糊词义。自然语言中的词经常多义、多指，使得网络信息检索系统不能分辨哪一种意思是查询中的，哪一种是文档中的。XML有助于解决词义模糊问题，提高检索的准确性。例如，用户使用“brown”作为检索词，他有可能想查找由DonaldBrown所写的论文，也可能是查找由Brown University出版的论文，或有关brown bear的论文。如果用户明确想查询的目标，可以分别输入“〈author〉Brown〈/author〉”，“〈university〉Brown〈/university〉”，或是“〈subject〉brown〈/subject〉”，这样就会提高检索准确性。

XML使得能用结构相邻关系来替代物理相邻关系进行检索结果相关性排序，而且可允许利用非文本数据，如数值数据、地理位置、温度值等进行检索。

以XML为基础的新一代WWW环境是直接面对Web数据的，不仅可以很好地兼容原有的Web应用，而且能更好地实现Web中的信息共享与交换。XML可视为一种半结构化的数据模型，可以很容易地将XML的文档描述与关系数据库中的属性对应起来，实施精确的查询与模型抽取。XML可以更详细地定义某个数据对象的数据结构，例如，描述产品或者详细定义该产品的生产厂、产品名、产品号、产地等信息。这种定义不仅为标记该产品提供方便，而且这种XML数据很容易按生产厂、产品名等排序，使用户的查询变得更加方便。XML有利于数据交换和传递的特性，进一步推动了电子商务、电了数据交换等的发展。

因此，我们要利用数据挖掘的思想和方法进行Web信息挖掘。这样一来，数据挖掘的对象将不仅仅是传统的关系数据库，还包括WWW上的各种有用信息。目前从Web上抽取信息的方法有：传统的从WWW上提取信息的搜索引擎；基于智能代理的搜索工具；把半结构化的Web信息重构的更结构化，然后使用标准的数据库查询机制和数据挖掘方法进行分析；对Web页面内容及结构进行信息挖掘等。

3.信息检索向信息挖掘的过渡和应用发展

狭义上讲，网络信息检索就是网络信息（内容）挖掘的一种。最初，信息检索的目标是信息标引，并从集合中找出有用的文档。而发展到今天，信息检索的研究已涉及建立模型、信息分类与归类、用户交互、数据可视化、数据过滤等。从这个角度看，网络信息挖掘只能作为信息检索过程的一部分，最明显的一个例子就是Web文档的分类与归类。

以搜索引擎Google为例，我们可以剖析网络信息挖掘技术在网络信息检索中的应用。

Google的搜索机制如图3-2所示，几个分布的自动搜索软件根据服务器提供的URL列表在网络上搜索，并将搜索到的网页送到存储服务器（Store Server）中。存储服务器于是就把这些网页压缩后存入一个知识库（repository）中。每个网页都有一个关联ID——docID，当一个新的URL从一个网页中解析出来时，就被分配一个docID。索引库（Indexer）和排序器（Sorter）负责建立索引，并由索引库从知识库中读取记录，将文档解压并进行解析，每个文档就转换成一组词的出现状况（word occurrences），称为hits。hits记录了词以及词在文档中的位置、字体大小和大小写等。索引库把这些hit又分成一组“barrels”，产生经过部分排序后的索引。索引库同时分析网页中所有的链接并将重要信息存在Anchors文档中。这个文档包含了足够信息，可以用来判断一个链接被链入或链出的节点信息。

URL分解器（URL Resolver）阅读Anchors文档，并把相对的URL转换成绝对的URLs，并生成doc ID，它进一步为Anchor文本编制索引，并与Anchor所指向的doc ID建立关联。同时，它还产生由doc ID对（pairs of doc ID）所形成的数据库。这个链接数据库（Links）用于计算所有文档的页面等级（Pagerank）。

排序器会读取barrels，并根据词的ID号（wordID）列表来生成倒排挡。一个名为DumpLexicon的程序会把上面的列表和由索引库产生的一个新的词表结合起来，并产生另一个新的词表供搜索器（Searcher）使用。这个搜索器就是利用Web服务器与由DumpLexicon所生成的词表，以及上述倒排挡和页面等级来回答用户的提问。

从Google的体系结构以及搜索原理中可以看到，其关键而具有特色的一步是：利用URL分解器获得Links信息，并且运用一定的算法得出了页面等级的信息，而这个技术正是网络结构挖掘技术。作为一个新兴的搜索引擎，Google正是利用这种对WWW的连接进行分析和大规模的数据挖掘的技术，使其搜索技术远胜一筹。