数据挖掘与知识发现(讲稿12---文本挖掘)

第1节  文本挖掘概述

1.1 文本挖掘的出现

在现实世界中，我们面对的数据大都是文本数据，这些数据是由各种数据源（如新闻文章、研究论文、书籍、数字图书馆、电子邮件和Web页面等）的大量文档组成。所以，随着文档信息量的飞速增长，文本数据的数据量也急剧地增长。

文本数据是所谓的半结构化数据（Semi-Structure Data），它既不是完全无结构的也不是完全结构化的。如，文档可能包含结构字段，比如：标题、作者、出版日期、长度、分类等，也可能包含大量的非结构化的文本，如摘要和内容。

文本挖掘（Text Mining），国外有人称之为文本数据挖掘（Text Data Mining）和文本分析（Text Analysis）。文本挖掘一词大约出现于1998年4月在欧洲举行的第十届机器学习会议上，组织者 Kodratoff明确地定义了文本挖掘的概念，并分清它与“信息检索”的不同点和共同点。Kodratoff认为，文本挖掘的目的是从文档集合中搜寻知识，并不试图改进自然语言理解，并不要求对自然语言的理解达到多高水平，而只是想利用该领域的成果，试图在一定的理解水平上尽可能多地提取知识。因此，文本挖掘需要数据挖掘、语言学、数据库以及文本标引和理解方面的专家参与。

我国于1998年在国家重点基础研究发展规划（“973计划”）首批实施项目中，包括了文本挖掘的内容。

1.2 文本挖掘的基本概念

   1、概念

    文本挖掘是一个从大量文本数据中提取以前未知的、可理解的、可操作的知识的过程。文本数据包括：技术报告、文档集、新闻、电子邮件、网页、用户手册等。

文本挖掘对单个文档或文档集（如，Web搜索中返回的结果集）进行分析，从中提取概念，并按照指定的方案组织、概括文档，发现文档集中重要的主题。它除了从文本中提取关键词外，还要提取事实、作者的意图、期望和主张等。这些知识对许多，如市场营销、趋势分析、需求处理等，都是很有用的。

   2、任务

主要任务有：

（1）文本标引和短语提取，即在读取大量的非结构化文本时，应用自然语言处理技术提取文本，集中所有相关的短语。提取时要处理同义词和词义模糊现象。可以形象地把文本挖掘看作是一支荧光笔，它通读文本时高亮度显示有关的短语，这些短语放在一起就可以得到对文本的一个较好的理解。

（2）概念提取（聚类），即对这些短语之间的关系，建立一个“词汇网”；将相关短语分组，并增强这些组中最重要的特征；最后得到的模式反映了该文本集中的主要概念。然后，通过提取出的概念集发现未知的知识。

（3）可视化显示和导航。对挖掘得来的信息（词频、相关概率、时事性话题、地域依赖信息、时间序列等），可以从多个视角出发进行分析。

   3、文本挖掘与数据挖掘

相似点在于：两者都处理大量的数据，都有归属到知识管理的知识发现领域中。

差别在于：许多经典的数据挖掘算法，如数值预测、决策树等都不太适用于文本挖掘，因为它们依赖于结构化的数据。而像概念关系分析等工作则是文本挖掘所独有的，如表所示。

文本挖掘与数据挖掘的区别

信息检索是文本挖掘相关的一个概念，但它与文本挖掘又是不同的两个概念。

信息检索是指从大量的文档集合C中，找到与给定的查询请求q相关的、恰当数目的文档子集S的过程。区别主要表现在如下几个方面：

（1）方不同

信息检索是目标驱动的，用户需要明确提出查询要求；而文本挖掘结果于用户的信息需求，是用户所无法预知的。

（2）着眼点不同

信息检索着重于文档中字与词和链接；而文本挖掘在于理解文本的内容和结构。

（3）目的不同

信息检索的目的在于帮助用户发现资源，即从大量的文本中找到满足其查询请求的文本子集；而文本挖掘是为了揭示文本中隐含的知识。

（4）评价方法不同

信息检索用查准率（Precision, 检索到的文档中的相关文档占全部检索到的文档的百分比）和查全率（Recall, 即被检索出的文档中的相关文档占全部相关文档的百分比）来评价其性能，要求尽可能多的检索出相关文档，同时不相关的文档尽可能少。而文本挖掘采用收益（Gain）、置信度（Certainty）、简洁性（Simplicity）等来衡量所发现知识的有效性、可用性和可理解性。

（5）使用场合不同

有时信息检索系统返回太多的结果以致用户无法一一浏览，有时用户没有明确的信息需求，有时用户希望发现文档集合中所具有的结构、趋势、含义，在这些场合下，就需要使用挖掘技术。

尽管文本挖掘是比信息检索层次更高的技术，但它并不是用来取代信息检索技术的，二者是相辅相成的。一方面，这两种技术各有所长，有各自适用的场合；另一方面，可以利用文本挖掘的研究成果来提高信息检索的精度和效率，改善检索结果的组织，使信息检索系统发展到一个新的水平。

第2节  文本特征表示与提取

2.1 文本特征的表示

与数据库中的结构化数据相比，文档具有有限的结构，或者根本就没有结构。即使具有一些结构，也是着重于格式，而非文档内容。不同类型的文档结构也不一致。此外，文档的内容是人类所使用的自然语言，计算机很难处理其语义。文本信息源的这些特殊性使得现有的数据挖掘技术无法直接应用于其上。这就需要对文本进行预处理，抽取其特征的元数据。这些特征可以用结构化的形式保存，作为文档的中间表示形式。

文本的特征指的是关于文本的元数据，分为：

（1）描述性特征，如文本的名称、日期、大小、类型等；

（2）语义性特征，如文本的作者、机构、标题、内容等；

一般，描述性特征易于获得，而语义性特征则较难得到。W3C(中国万维网联盟)近年来制定的XML（Extensible Markup Language, 可扩展标记语言）、RDF（Resource Description Framework, 一种用于描述Web资源的标记语言）等规范提供了对文档资源进行描述的语言和框架。在此基础上，可以从半结构化的文档中抽取作者、机构等特征。对于内容这个难以表示的特征，首先要找到一种能够被计算机所处理的表示方法。

矢量空间模型（VSM）是近年来应用较多且效果较好的表示文本特征的方法。在该模型中，文档空间被看作是由一组正交词条矢量所张成的矢量空间，每个文档d表示为其中的一个范化特征矢量：

其中，为词条项，为在中的权值。可以是d中出现的所有单词，也可以是d中出现的所有短条，从而提高内容特征表示的准确性。一般被定义为在d中出现的频率的函数，即。常用的有：

    （1）布尔函数

    （2）平方根函数

（3）对数函数

（4）TFIDF函数

其中，为所有文档的数目，为含有词条的文档数目。

2.2 文本的特征提取

特征提取主要是识别文本中代表其特征的词项。提取过程是自动的，提取的特征大部分是文本集中表示的概念。

文本特征分为一般特征和数字特征，其中一般特征主要包括动词和名词短语，如人名、组织名等；数字特征主要包括日期、时间、货币以及单纯数字信息。这些特征包含重要的信息，因此特征提取是一种强有力的文本挖掘技术。通过文本的特征抽取，记录文本的特征，可以更好地组织文本，如文本的存储、检索、过滤、分类和摘要等。

中文姓名识别属于中文信息处理中未登录词处理的范畴，中文姓名在文章中的出现频率虽然不高，但绝非可以忽略，因为中文姓名本身包含着重要的信息，它可能是整个句子甚至整个段落的语义中心，如果不予处理，将影响文本挖掘的性能。数字特征反映一定的信息，但不能表达文本的中心思想，通常只作为文本挖掘中的参考信息。姓名特征提取算法所提取的姓名特征，作为文本内容的特征表示。

构成文本的词汇，通常数量很大，因此表示文本的向量空间的维数也相当大，可以达到几万维，需要压缩维数。

为了提高分类精度，对于每一类，应去除那些表现力不强的词汇，筛选出针对该类的特征项集合。目前，存在多种筛选特征项的算法，如根据词和类别的互信息量判断、根据词熵判断、根据KL距离判断等。

比如，根据词和类别的互信息量进行特征项抽取的判断标准，其算法过程如下：

（1）初始情况下，该特征项集合包含所有该类中出现的词；

（2）对于每个词，计算词和类别的互信息量

其中，；为在类中出现的比重；为该类的训练样本数；为词W在文本中的词频；为总词汇；为该类所有词的词频和；为词W在所有训练样本中的比重。

（3）对于该类中的所有词，依据上面计算的互信息量排序；

（4）抽取一定数量的词作为特征项，具体需要抽取多少维的特征项，目前无很好的解决方法。一般采用先定初始值，然后根据实验测试和统计结果确定最佳值，初始值一般定在几千左右；

（5）将每类中所有的训练样本，根据抽取的特征项，进行向量维数压缩，精简向量表示。

第3节  文本挖掘

3.1 文本分类

文档分类是一种重要的文本挖掘工作，由于现在存在大量的联机文档，自动对其分类组织以便对文档的检索和分析，是至关重要的。

如何进行文档的自动分类？一般做法如下：

首先，把一组预先分类过的文档作为训练集；然后对训练集进行分析以便得出分类模式。这种分类模式通常需要一定的测试过程，不断地细化。之后就用这些导出的分类模式对其他联机文档加以分类。

这一处理过程与关系数据的分类相似，但还是存在本质的区别。因为，关系数据是结构化的，而文档数据库则不是结构化的，它没有“属性，值”对的结构。因此，对关系数据的分类方法，如决策树分析，并不适用对文档数据库的分类。

对文档分类的有效方法是基于关联的分类，它基于一组关联的、经常出现的文本模式对文档加以分类。基于关联的分类方法处理过程如下：

（1）通过简单的信息检索技术和关联分析技术，提出关键词和词汇；

（2）使用已经有的词类，或基于专家知识，或使用某些关键字分类方法，生成关键字和词的概念层次，或类层次结构。

（3）词关联挖掘方法用于发现关联词，它可以最大化区分一类文档与另一类文档。这导致了对每一类文档，有一组关联规则。这些分类规则可以基于其出现频率加以排序，并用于对新的文档的分类。

基于关联的文档分类方法已经证明是有效的。

文本分类是一种典型的有教师的机器学习问题，一般分为训练和分类两个阶段。具体过程如下：

（1）训练阶段

    ① 定义类别集合，这些类别可以是层次式的，也可以是并列式的；

    ② 给出训练文档集合，每个训练文档被标上所属的类别标识；

③ 统计S中所有文档的特征矢量，确定代表C中每个类别的特征矢量

（2）分类阶段

① 对于测试文档集合中的每个待分类文档，计算其特征矢量与每个之间的相似度；

② 选取相似度最大的一个类别作为的类别。

注：在计算时，有多种方法可供选择。最简单的方法是仅考虑两个特征矢量中所包含的词条的重叠程度，即：

其中，是和具有相同词条的数目；是和具有的所有词条数目。

     最常用的方法，是考虑两个特征矢量之间的夹角余弦。

3.2 关联分析

关联分析首先要对文本数据进行分析、词根处理、去除非用词等预处理，然后调用关联挖掘算法。

在文档数据库中，每一个文档被视为一个事务，文档中的关键字组可视为事务中的一组事务项。即数据库可表示为：

       {document_id, a_set_of_keywords}

于是，文档数据库中的关键字关联挖掘问题，就变成事务数据库中事务项的关联挖掘问题。

注意：一组经常连续出现或紧密相关的关键字可形成一个词或词组。关联挖掘有助于找出复合关联，即领域相关的词或词组。如，[科技大学，大学] 或 [总统， 布什]，或非复合词关联，如[美元，参股，交易，总额，佣金，赌注，证券]。基于这些关联的挖掘称为“词级关联挖掘”（相对应的是字级的挖掘）。

词的识别和词级关联在文本分析中有两个优点：

（1）词和词组被自动标记，无需人去标记文档；

（2）挖掘算法的执行时间和无意义的结果将极大减少。

利用这种词和词组的识别，词级挖掘可以用于找出词或关键字间的关联。一些用户可能喜欢从给定关键字或词组中找出关键字或词对之间的关联，而有些用户可能希望找出一起出现的最大词集。因此，根据用户挖掘的需要，可以使用关联挖掘或最大模式挖掘算法。

3.3 文档聚类

文本聚类是一种典型的无教师的机器学习问题。目前的文本聚类方法大致可分为：层次凝聚法和平面划分法两种类型。

1、层次凝聚法

对于给定的文档集合，层次凝聚法的具体过程如下：

（1）将D中的每个文档看作是一个具有单成员的簇，这些簇构成了D的一个聚类；

（2）计算C中每对簇（）之间的相似度；

（3）选取具有最大相似度的簇对，并将和合并为一个新的簇，从而构成了D的一个新的聚类；

（4）重复上述步骤，直至C中剩下一个簇为止。

该过程构造出一棵生成树，其中包含了簇的层次信息，以及所有簇内和簇间的相似度。层次聚类方法是最为常用的聚类方法，它能够生成层次化的嵌簇，且精确度较高。但是在每次合并时，需要全局地比较所有簇之间的相似度，并选择出最佳的两个簇，因此运行速度较慢，不适合于大量文档的集合。

2、平面划分法

平面划分法与层次凝聚法的区别在于，它将文档集合水平地分割为若干个簇，而不是生成层次化的嵌套簇。对于给定的文档集合，平面划分法的具体过程如下：

（1）确定要生成簇的数目；

（2）按照某种原则，生成个聚类中心作为聚类的种子；

（3）对D中每个文档，依次计算它与各个种子的相似度；

（4）选取具有最大相似度的种子，将归入以为聚类中心的簇，从而得到D的一个聚类；

（5）重复步骤（2）、（3）、（4）若干次，以得到较为稳定的聚类结果。该方法的运行速度较快，但是必须事先确定的取值，且种子选取的好坏对聚类结果有较大影响。

第4节  Web挖掘

万维网目前是一个巨大的、分布广泛和全球性的信息服务中心，它涉及新闻、广告、消费信息、金融管理、教育、、电子商务和许多其他信息服务。Web还包含了丰富和动态的超链接信息，以及Web页面的访问和使用信息，这为数据挖掘提供了丰富的资源。所以，随着Internet的飞速发展，网上的数据资源空前的丰富。但是数据资源中蕴涵的知识却至今未能得到充分的挖掘和利用，数据丰富但知识贫乏的问题非常严重。在日益激烈的电子商务买方市场竞争中，任何与消费者行为有关的信息对商家来说都非常重要。

目前，大多数的用户从Web上获取信息的途径主要是通过搜索引擎或者通过浏览Web页面，搜索引擎虽然部分的解决了资源发现的问题，但其精确度不高，不能为用户提供结构化的信息，也不能提供文档分类、过滤等功能；而浏览Web页面在用户需要查找、查全大量的资料时，基本不能提供资源发现的功能，显然，这两种信息检索手段都不能满足用户的基本要求。

数据库领域采用了数据挖掘技术，以从大量数据的集合中发现有用的信息，但数据挖掘绝大部分工作所涉及的是结构化数据库，很少有处理Web上的异质、非结构化信息的工作。因此怎样从Web上大量的信息中有效的、快速的找出用户感兴趣的信息就成为一项重要而迫切的课题，人们也迫切需要这样一种能快速、有效地发现资源和知识的工具。近年来兴起的数据挖掘（Data Mining）技术在Web上的应用即Web 数据挖掘技术为解决这个问题带来了一线曙光。

从广义上讲，Web信息也是一类特别的文本信息，因此文本挖掘的各种技术也适合于Web挖掘，但是由于Web信息自身的特点，文本挖掘和Web挖掘应该区别对待。

4.1 什么是Web数据挖掘

Web数据挖掘是从大量的Web文件的集合中发现有用的信息和模式。Web数据挖掘是一门综合技术，涉及领域非常广泛，如：数据挖掘、信息学、计算机语言学、人工智能等领域。

Web挖掘从数据挖掘而来，但由于Web上的信息的特点使得它又不同于传统的数据挖掘，它所面临的挑战更大。此外，Web挖掘技术也不同于信息检索（IR）。

Web数据挖掘具有以下特点：

   1、Web 信息特别庞大 

Web的数据量目前以几百G字节计算，而且仍在迅速地增长。许多机构和社团都在把各自大量的可访问信息置于网上。怎样对这些数据进行复杂的应用是数据挖掘技术的研究热点。

2、Web信息非常复杂

Web文件是半结构化或无结构的。每一站点的数据都各自设计，并且数据本身具有自述性和动态可变性，没有特定的模型描述。需要研究统一的语义模型，并解决半结构化或无结构数据的抽取技术。所以，Web页面缺乏统一的结构，它包含了远比任何一组书籍或其他文本文档多得多的风格和内容。Web可以看作是一个巨大的数字图书馆；然而，这一图书馆中的大量文档并不根据任何有关排列次序加以组织。它没有分类索引，更没有按标题、作者、封面页、目录等的索引。对在这样一个图书馆中搜索希望得到的信息是极具挑战性的。

3、Web信息是动态的

Web是一个动态性极强的信息源。Web不仅以极快的速度增长，而且其信息还在不断地发生着更新。新闻、股票、股票市场、公司广告和Web服务中心都在不断地更新着各自的页面。链接信息和访问记录也在频繁地更新之中。

4、Web信息使用者复杂

相对于一般的数据库应用系统，Web面对的是一个广泛的、形形色色的用户群体。目前的Internet上连接有约五千多万台工作站，其用户群仍在不断扩展中。各个用户可以有不同的背景、兴趣和使用目的。大部分用户并不了解信息网络结构，不清楚搜索的高昂代价，极容易在“黑暗”的网络中迷失方向，也极容易在“跳跃式”访问中烦乱不已和在等待一段信息中失去耐心。

5、Web信息中“垃圾”非常多

Web信息只有很小的一部分是相关的或有用的。据说99%的Web信息对于99%的用户是无用的。虽然这看起来不是很明显，但一个人只是关心Web上很小很小一部分信息确是事实，Web所包含的其余信息对用户来说是不感兴趣的，而且会淹没所希望得到的搜索结果。

6、异构的数据环境

Web页面的复杂性远比任何传统的文本文档复杂得多。Web上的每一个站点就是一个数据源，每个数据源都是异构的，各自的信息和组织不一样，构成了一个巨大的异构数据环境。如果想要利用这些数据进行数据挖掘，必须要解决站点之间异构数据的集成问题。

4.2自适应网站技术

为了更好地满足人性化访问地要求，必须做进一步基于网站自身的挖掘。因而提出了基于Web日志的数据挖掘的自适应网站技术。

所谓自适应网站是指：对于特定的网站和特定的用户，通过学习访问者或用户的访问模式自动改善其组织和信息描述方式的网站。

由于挖掘是基于用户的浏览行为而不是用户输入的数据，从而消除了描述的差异，适用于个性化服务。其优点是适用范围广，不需要用户参与，不涉及隐私，数据真实。其缺点是数据的杂质特性，在区分使用者、会话、识别会话的终结点方面存在着许多困难。

自适应网站建立的主要目的是消除网站设计者假设的用户兴趣和网站使用者兴趣的差别。网站设计者在设计时总是基于某些用户为什么及怎样访问网站的假设，并据此规划网站，然而使用者的需要往往与设计者假设的用户需要并不相同。此时设计者与使用者之间就存在着一条“兴趣沟”，而自适应Web数据挖掘可以很好的消除这条“沟”。自适应的周期要经历4个阶段，数据准备、数据挖掘、数据分析、网站改进。整个过程是不断循环不断完善的。

在以上的自适应Web数据挖掘中有一个重要的基础就是数据的准确性；必须有准确的数据才能每次都正确地反映使用者的意图，从而可以使分析沿着正确的方向进行。由于日志记录和HTTP协议的自身原因，日志数据是杂乱的，还原的信息可能包含错误信息，因此对日志信息进行准确的预处理是非常关键的。

4.3 Web数据挖掘的研究热点

当前,数据挖掘研究正方兴未艾,尤其是对基于Web的数据挖掘的研究,研究热点可能会集中到以下几个方面:

(1)研究专门的数据挖掘语言,使其像SQL语言一样走向形式化和标准化。

(2)寻求数据挖掘过程中的可视化方法,使知识发现的过程能够被用户理解 ,也便于在知识发现过程中能够方便地进行人－机交互。

(3)研究在网络环境下的数据挖掘技术,特别是在Internet上与数据库服务器配合,实现数据挖掘。

(4)加强对各种非结构化数据的挖掘,如文本数据、图形图像数据、多媒体数据。

但是,无论怎样,需求牵引和市场驱动是永恒的,数据挖掘技术(尤其是基于Web的数据挖掘技术)将首先满足信息时代用户的急需,大量基于数据挖掘的决策支持软件工具产品不久将会问世。

4.4 Web挖掘分类

一般将Web挖掘定义为：从WWW的资源和行为中抽取感兴趣的、有用的模式和隐含的信息。

一般地，Web挖掘可分为3类：Web内容挖掘（Web Content Mining）、Web结构挖掘（Web Structure Mining）和Web使用记录挖掘（Web Usage Mining）。

下图是Web挖掘的分类图：

1、Web内容挖掘

Web内容挖掘是从文档内容或文档描述中抽取知识的过程。Web文档内容的挖掘，基于概念索引的资源发现，以及基于代理的技术都属于这一类。

    Web内容挖掘有两种策略：

（1）直接挖掘文档的内容；

（2）在工具搜索的基础上进行改进。

    采用第1种策略的有：针对Web的查询语言Weblog、WebOQL等，利用启发式规则来寻找个人主页信息的Ahoy等等。

采用第2种策略的方法，主要是对搜索引擎的查询结果进行进一步的处理，得到更为精确和有用的信息。属于该类的有WebSQL，及对搜索引擎的返回结果进行聚类的技术等。

2、Web结构挖掘

  Web结构挖掘是从WWW的组织结构和链接关系中挖掘知识。由于文档之间的互连，WWW能够提供除文档内容之外的有用信息。利用这些信息，可以对页面进行排序，发现重要的页面。这方面工作的代表有PageRank和CLEVER。此外，在多层次Web数据仓库中，也利用了页面的链接结构。

3、Web使用记录挖掘

  Web使用记录挖掘的主要目标则是从Web的访问记录中抽取感兴趣的模式。WWW中的每个服务器都保留了访问日志（Web access log），记录了关于用户访问和交互的信息。分析这些数据可以帮助理解用户的行为，从而改进站点的结构，或为用户提供个性化的服务。

这方面的研究主要有两个方向：一般访问模式的追踪和个性化使用记录的追踪。

一般访问模式的追踪通过分析使用记录来了解用户的访问模式和倾向，以改进站点的组织结构；而个性化使用记录的追踪则倾向于分析单个用户的偏好，其目的是根据不同用户的访问模式，为每个用户提供定制的站点。

4.6 Web数据挖掘的用途

到一个站点的所有访问者都会留下浏览的踪迹，这些信息自动存储在Web服务器的日志文件中。Web分析工具通过分析和处理Web服务器的日志文件来生成有意义的信息。例如有多少人访问了该页面，他们从哪来，哪些页面最受欢迎等。当前经济模式的变化，从传统实体的商店到Internet上的电子交易，同时也改变了销售商和顾客的关系。现在网上顾客的流动性很大，他们关注的主要因素是商品的价值，而不像以前注意品牌和地理因素。因此，电子销售商一个主要挑战是，如何确定顾客的爱好、兴趣和价值取向，以保证在电子时代的竞争力。数据挖掘是用来发现不明显的、有潜在价值的数据。Web上数据挖掘的潜力在于应用存在的和最新的数据挖掘算法，分析Internet服务器上的日志以及顾客、销售和产品的外部数据。

就电子商务而言，Web数据挖掘有以下三个方面的益处：

（1）理解顾客行为：

1通过理解访问者的动态行为来优化电子商务网站的经营模式；

2电子销售商可以获知访问者的个人爱好；

3决定网站上由访问者到购买者的转化率；

4决定顾客的回头率（顾客第二次购买同一品牌的概率）；

5发现顾客的购买模式和访问者的浏览模式；

6发现什么样的顾客群在网站上购买什么商品；

7发现电子商务网站上顾客之间的联系。

（2）判断Web站点的效率：

1发现站点上的高购买率部分和低购买率部分；

2Web设计者不再依靠专家的定性指导来设计网站，而是根据访问者的信息来修改和设计网站的结构和外观；

3电子销售商可以根据不同的客户提供个性化服务。

（3）评估电子商务模式的成功与否：

1容易将用户按模式分类；

2容易评测广告的投资回报率；

3容易得到可靠的市场回馈信息。

4.7 XML与Web数据挖掘技术

以XML为基础的新一代WWW环境是直接面对Web数据的，不仅可以很好地兼容原有的Web应用，而且可以更好地实现Web中的信息共享与交换。XML可看作一种半结构化的数据模型，可以很容易地将XML的文档描述与关系数据库中的属性一一对应起来，实施精确地查询与模型抽取。

1. XML的产生与发展  

XML(eXtensible Markup Language)是由万维网协会(W3C)设计，特别为Web应用服务的SGML（Standard General Markup Language）的一个重要分支。总的来说，XML是一种中间标记语言（Meta-markup Language），可提供描述结构化资料的格式，是一种类似于HTML，被设计用来描述数据的语言。XML提供了一种的运行程序的方法来共享数据，它是用来自动描述信息的一种新的标准语言。

XML由若干规则组成，这些规则可用于创建标记语言，并能用一种被称为分析程序的简明程序处理所有新创建的标记语言，正如HTML为第一个计算机用户阅读Internet文档提供一种显示方式一样，XML也创建了一种任何人都能读出和写入的世界语。XML解决了HTML不能解决的两个Web问题，即Internet发展速度快而接入速度慢的问题，以及可利用的信息多，但难以找到自己需要的那部分信息的问题。XML能增加结构和语义信息，可使计算机和服务器即时处理多种形式的信息。因此，运用XML的扩展功能不仅能从Web服务器下载大量的信息，还能大大减少网络业务量。

XML中的标志(TAG)是没有预先定义的，使用者必须要自定义需要的标志，XML是能够进行自解释(Self Describing)的语言。XML使用DTD(Document Type Definition文档类型定义)来显示这些数据，XSL(eXtensible Style Sheet Language)是一种来描述这些文档如何显示的机制，它是XML的样式表描述语言。XSL的历史比HTML用的CSS(层叠式样式表Cascading Style Sheets)还要悠久，XSL包括两部分：一个用来转换XML文档的方法；一个用来格式化XML文档的方法。XLL（eXtensible Link Language）是XML连接语言，它提供XML中的连接，与HTML中的类似，但功能更强大。使用XLL，可以多方向连接，且连接可以存在于对象层级，而不仅仅是页面层级。由于XML能够标记更多的信息，所以它就能使用户很轻松地找到他们需要的信息。利用XML，Web设计人员不仅能创建文字和图形，而且还能构建文档类型定义的多层次、相互依存的系统、数据树、元数据、超链接结构和样式表。

2. XML的特点    

正是XML的特点决定了其卓越的性能表现。XML作为一种标记语言，有许多特点：    

（1）简单。XML经过精心设计，整个规范简单明了，它由若干规则组成，这些规则可用于创建标记语言，并能用一种常常称为分析程序的简明程序处理所有新创建的标记语言。XML能创建一种任何人都能读出和写入的世界语，这种创建世界语的功能叫做统一性功能。如XML创建的标记总是成对出现，以及依靠称为统一代码的新的编码标准。

（2）开放。XML是SGML在市场上有许多成熟的软件可用来帮助编写、管理等,开放式标准XML的基础是经过验证的标准技术，并针对网络做最佳化。众多业界顶尖公司，与W3C的工作群组并肩合作，协助确保交互作业性，支持各式系统和浏览器上的开发人员、作者和使用者，以及改进XML标准。XML解释器可以使用编程的方法来载入一个XML的文档，当这个文档被载入以后,用户就可以通过XML文件对象模型来获取和操纵整个文档的信息，加快了网络运行速度。

（3）高效且可扩充。支持复用文档片断，使用者可以发明和使用自己的标签，也可与他人共享，可延伸性大，在XML中，可以定义无限量的一组标注。XML提供了一个标示结构化资料的架构。一个XML组件可以宣告与其相关的资料为零售价、营业税、书名、数量或其它任何数据元素。随着世界范围内的许多机构逐渐采用XML标准，将会有更多的相关功能出现：一旦锁定资料，便可以使用任何方式透过电缆线传递，并在浏览器中呈现，或者转交到其他应用程序做进一步的处理。XML提供了一个的运用程序的方法来共享数据，使用DTD，不同的组中的人就能够使用共同的DTD来交换数据。你的应用程序可以使用这个标准的DTD来验证你接受到的数据是否有效，你也可以使用一个DTD来验证你自己的数据。

（4）国际化。标准国际化，且支持世界上大多数文字。这源于依靠它的统一代码的新的编码标准，这种编码标准支持世界上所有以主要语言编写的混合文本。在HTML中，就大多数字处理而言，一个文档一般是用一种特殊语言写成的，不管是英语，还是日语或阿拉伯语，如果用户的软件不能阅读特殊语言的字符，那么他就不能使用该文档。但是能阅读XML语言的软件就能顺利处理这些不同语言字符的任意组合。因此，XML不仅能在不同的计算机系统之间交换信息，而且能界和超越不同文化疆界交换信息。

3. XML在Web数据挖掘中的应用    

XML已经成为正式的规范，开发人员能够用XML的格式标记和交换数据。XML在三层架构上为数据处理提供了很好的方法。

XML应用于以下四个方面：

1需要Web客户端在两个或更多异质数据库之间进行通信的应用；

2试图将大部分处理负载从Web服务器转到Web客户端的应用；

3需要Web客户端将同样的数据以不同的浏览形式提供给不同的用户的应用；

4需要智能Web代理根据个人用户的需要裁减信息内容的应用。

显然，这些应用和Web的数据挖掘技术有着重要的联系，基于Web的数据挖掘必须依靠它们来实现。

XML给基于Web的应用软件赋予了强大的功能和灵活性，因此它给开发者和用户带来了许多好处。比如：

（1）进行更有意义的搜索，并且Web数据可被XML唯一地标识。没有XML，搜索软件必须了解每个数据库是如何构建的，但这实际上是不可能的，因为每个数据库描述数据的格式几乎都是不同的。由于不同来源数据的集成问题的存在，现在搜索多样的不兼容的数据库实际上是不可能的。XML能够使不同来源的结构化的数据很容易地结合在一起。软件代理商可以在中间层的服务器上对从后端数据库和其它应用处来的数据进行集成。然后，数据就能被发送到客户或其他服务器做进一步的集成、处理和分发。

（2）XML的扩展性和灵活性允许它描述不同种类应用软件中的数据，从描述搜集的Web页到数据记录，从而通过多种应用得到数据。

（3）由于基于XML的数据是自我描述的，数据不需要有内部描述就能被交换和处理。

（4）利用XML，用户可以方便地进行本地计算和处理，XML格式的数据发送给客户后，客户可以用应用软件解析数据并对数据进行编辑和处理。使用者可以用不同的方法处理数据，而不仅仅是显示它。

（5）XML文档对象模式(DOM)允许用脚本或其他编程语言处理数据，数据计算不需要回到服务器就能进行。

（6）XML可以被利用来分离使用者观看数据的界面，使用简单灵活开放的格式，可以给Web创建功能强大的应用软件，而原来这些软件只能建立在高端数据库上。另外，数据发到桌面后，能够用多种方式显示。

（7）XML还可以通过以简单开放扩展的方式描述结构化的数据，XML补充了HTML，被广泛地用来描述使用者界面。HTML描述数据的外观，而XML描述数据本身。由于数据显示与内容分开，XML定义的数据允许指定不同的显示方式，使数据更合理地表现出来。本地的数据能够以客户配置、使用者选择或其他标准决定的方式动态地表现出来。CSS和XSL为数据的显示提供了公布的机制。

（8）通过XML，数据可以粒状地更新。每当一部分数据变化后，不需要重发整个结构化的数据。变化的元素必须从服务器发送给客户，变化的数据不需要刷新整个使用者的界面就能够显示出来。但在目前，只要一条数据变化了，整一页都必须重建。这严重了服务器的升级性能。XML也允许加进其他数据，比如预测的温度。加入的信息能够进入存在的页面，不需要浏览器重新发一个新的页面。

（9）XML应用于客户需要与不同的数据源进行交互时，数据可能来自不同的数据库，它们都有各自不同的复杂格式。但客户与这些数据库间只通过XML一种标准语言进行交互。由于XML的自定义性及可扩展性，它足以表达各种类型的数据。客户收到数据后可以进行处理，也可以在不同数据库间进行传递。在这类应用中，XML解决了数据的统一接口问题。但是，与其他的数据传递标准不同的是，XML并没有定义数据文件中数据出现的具体规范，而是在数据中附加TAG来表达数据的逻辑结构和含义。这使XML成为一种程序能自动理解的规范。

（10）XML应用于将大量运算负荷分布在客户端，即客户可根据自己的需求选择和制作不同的应用程序以处理数据，而服务器只须发出同一个XML文件。如按传统的“Client/Server”工作方式，客户向服务器发出不同的请求，服务器分别予以响应，这不仅加重服务器本身的负荷，而且网络管理者还须事先调查各种不同的用户需求以做出相应不同的程序，但假如用户的需求繁杂而多变，则仍然将所有业务逻辑集中在服务器端是不合适的，因为服务器端的编程人员可能来不及满足众多的应用需求，也来不及跟上需求的变化，双方都很被动。应用XML则将处理数据的主动权交给了客户，服务器所作的只是尽可能完善、准确地将数据封装进XML文件中，正是各取所需、各司其职。XML的自解释性使客户端在收到数据的同时也理解数据的逻辑结构与含义，从而使广泛、通用的分布式计算成为可能。

（11）XML还被应用于网络代理，以便对所取得的信息进行编辑、增减以适应个人用户的需要。有些客户取得数据并不是为了直接使用而是为了根据需要组织自己的数据库。比方说，教育部门要建立一个庞大的题库，考试时将题库中的题目取出若干组成试卷，再将试卷封装进XML文件，接下来在各个学校让其通过一个过滤器，滤掉所有的答案，再发送到各个考生面前，未经过滤的内容则可直接送到老师手中，当然考试过后还可以再传送一份答案汇编。此外，XML文件中还可以包含进诸如难度系数、往年错误率等其他相关信息，这样只需几个小程序，同一个XML文件便可变成多个文件传送到不同的用户手中。

第5节 时序数据和序列数据的挖掘概述

5.1 时序数据库与序列数据库

●    时序（time-series）数据库：由随时间变化的序列值或事件组成的数据库。序列值通常是在等时间间隔测得的数据（如股票的每日收盘价等）。

●    序列数据库：由有序事件的序列组成的数据库。它可以有时间标    记，也可以没有时间标记（如Web页面访问序列）。

●    两者关系：时序数据一定是序列数据；序列数据不一定是时序数据。

5.2 时序数据与序列数据挖掘的类型

(1)时序数据的趋势分析：分析时序数据随数据变化的趋势。

(2)时序分析中的相似搜索：查询与给定查询序列最接近的数据序列。

(3)时序数据的周期分析：对周期模式的挖掘（即在时序数据库中找出重复出现的模式）。

(4)序列模式挖掘：挖掘相对时间或其他模式出现频率高分模式。

5.3 时序数据的趋势分析

1. 时序数据的变化类型

(1)长期趋势变化(Long-term or trend movement)：反映时序数据在较长时间间隔的变化趋势。典型方法是加权移动平均法和最小二乘法。

(2)循环变化(Cyclic movement)：趋势线呈现摆动迹象，它可以是周期性的也可以不是周期性的，即在等时间间隔之间循环不一定按照相同的模式演进。

(3)季节性变化(Seasonal movement)：反映每年都重复出现的事件，即同一或近似同一的模式在连续几年所有关期间重复出现（如情人节前巧克力和鲜花销量大增等）。

(4)非规则或随机变化(Irregular or random movement)由于随机或偶然事件（人自然灾害、恐怖袭击、劳工纠纷、企业高层人事变动等）引起的时序数据变化。

时序分析即将时序数据分解为以上趋势的、周期的、季节性的和非规则的四种基本变化（分别使用变量T、C、S、I表示）的分析。

2．加权移动平均方法

对给定的一组值（y1,y2,…,yn,…），计算n阶移动平均值序列：

        （y1＋y2,＋…＋yn） / n

        （y2＋y3,＋…＋yn+1） / n

        （y3＋y4,＋…＋yn+2） / n

            ……

使用移动平均值序列代替时序序列可减少不希望出现的波动，故又称为时序数据的平滑。如果在计算n阶移动平均值序列中使用加权算术平均，则称为n阶加权移动平均。

〖例〗对给定9个值的序列，计算其3阶移动平均以及权重为（1，4，1）的加权移动平均。

初始数据：            3   7   2   0   4   5   9   7   2

3阶移动平均：            4   3   2   3   6   7   6

加权移动平均：           5.5  2.5  1  3.5  5.5  8  6.5

其中，第1个加权移动平均值计算为（其余类同）：

（1×3＋4×7＋1×2）/ （1＋4＋1）＝33/6＝5.5

移动平均会丢失序列数据中的头尾数据，因而可能产生原始数据中不会产生的变化趋势。使用加权移动平均时给中间的数据赋予较大的权重，从而可降低其负面影响。

3．其他趋势分析方法

(1)最小二乘法：以最好的拟合曲线C＝f（x）作为最小二曲线，即使得Σ（yi－f(xi)）2最小。

(2)季节波动调整：引入“季节指数”的概念，即用一组数据表示一年中某些月份某变量的相关值，如：10月、11月、12月的销售量分别是全年平均月销售量的70％、110％、130％，则70、110、130为本年度的季节指数。将原始数据每个月的销售量用季节指数除，其结果称为“反季节的”或“对季节变量调整”。由于平滑季节性波动。

(3)时序图：有助于估算长期趋势、循环变化、季节变化和非规则变化的规律，从而进行长期或短期的预测（即预报时序）。

5.4 相似搜索  

1. 什么是相似搜索

与精确查询不同，相似搜索是找出与给定查询序列最接近的数据序列。

子序列匹配是找出与给定序列相似的所有数据序列。整体序列匹配是找出彼此间相似的序列。

相似搜索可应用于金融市场分析（如股票数据分析）、医疗诊断分析（如心电图分析）、工程数据分析（如能耗分析）等。

2. 数据变换

对时序数据进行相似搜索通常使用欧几里德距离作为相似计算的依据。

数据变换是将数据从时域变换为频域，其目的是提高搜索的效率。由于正交变换可保持距离不变，故离散付里叶变换（DFT）和离散小波变换（DWT）可应用于相似搜索的数据变换。

数据经过变换（如DFT）后，可用前几个付里叶系数建立一个索引。当用户向系统提交了一个相似搜索请求后，可以利用索引检索出与查询序列保持给定最小距离的序列。子序列的匹配通过将序列分割为窗口片段及映射为特征空间中的一个线索来实现。

3. 增强相似搜索方法

增强相似搜索方法用于处理偏移和振幅中的间隙和差异，而具有偏移和振幅中的间隙和差异的子序列也可以认为是匹配的。

增强相似搜索方法的步骤为：

●原子匹配

●窗口结合

●子序列排序

5.5周期分析

1. 什么是周期分析

周期分析是指对周期模式的挖掘，即在时序数据库中找出重复出现的模式。以发现诸如季节、潮汐、行星轨道、每日能源消耗、每日交通流量等的周期性规律。

2. 周期模式挖掘的类型

●挖掘全周期模式：每一时间点对时序数据的周期有影响（精确或近似）。

●挖掘部分周期模式：描述部分时间点的时序周期。

●挖掘循环或周期的关联规则：挖掘周期性出现的事件的关联规则。

3. 周期模式挖掘的方法

●全周期分析：FFT

●部分周期分析和周期关联规则挖掘：

    改进的Apriori算法（约束挖掘）＝Apriori算法＋约束

5.6 序列模式挖掘

1. 什么是序列模式挖掘

挖掘相对时间或其他模式出现频率高的模式。如：“9个月前购买奔腾PC的顾客很可能在一个月内定购新的CPU芯片”。

应用于商业交易、气象预报、生产过程控制等领域。

2. 序列模式挖掘的参数

(1)时间序列的持续时间：整个序列或某年、某月、每周等子序列。

(2)事件重叠窗口：在指定时间周期内出现的事件（如：“2003年购买PC机的顾客也购买数字相机”；“购买了PC机的顾客，可能接着购买内存芯片，再购买CD－ROM”等）。

(3)时间间隔（int）：

⏹    int＝0

⏹    min_interval ≦ int ≦max_interval

⏹    int＝C≠O

3. 序列模式挖掘的方法

(1)关联规则挖掘算法：Apriori算法的变形

(2)基于数据库投影的序列模式生长技术