数据挖掘中的半结构化数据
发布时间：2015-07-13 09:46
摘 要 半结构化数据是网络中一种重要的数据形式，也是进行数据挖掘的重要基础。因此要对Internet上巨量的数据进行数据挖掘，半结构化数据及模型是前提。本文介绍了半结构化数据的相关概念及其数据模型。
关键词 半结构化数据、数据挖掘、数据模型
1 数据挖掘与半结构化数据模型
1.1 数据挖掘与异构数据库
数据挖掘(DM)是从在大型数据库或数据仓库中发现并提取隐藏在其中的信息或者知识的过程。其目的是帮助分析人员寻找数据之间的关联，发现被忽略的要素，而这些信息对于预测趋势和决策行为是十分有用的。
数据挖掘源于人工智能的机器学习领域，其实质的内涵是在一个已知状态的数据集(DataSet)上，通过设定一定的学习算法，从数据集中获取所谓的知识。知识发现技术的相关研究为数据挖掘技术提供了坚实的理论基础，数据挖掘技术实际上是人工智能领域中的知识发现技术和数据库技术共同发展的结果。
传统意义的数据库、数据仓库和上面我们提到的Internet中的数据是我们所拥有的数据资源，也是进行数据挖掘的基础。传统数据库中的数据结构性很强，其中的数据为完全结构化的数据；数据仓库是由数据库导出的用于分析型的数据环境；我们可把Web网站上的信息看作一个数据库，一个更大、更复杂的数据库，Web上的每一个站点就是一个数据源，每个数据源都是异构的，因而每一站点之间的信息和组织都不一样，这就构成了一个巨大的异构数据库环境。
1.2 半结构化数据模型与数据挖掘
Internet上的数据与传统的数据库中的数据不同，传统的数据库都有一定的数据模型，可以根据模型来具体描述特定的数据，同时可以很好地定义和解释相关的查询语言。而Internet上的数据非常复杂，没有特定的模型描述，每一站点的数据都各自独立设计，并且数据本身具有自述性和动态可变性，其结构也不可琢磨，是一种我们称之为半结构化数据。所谓半结构化是相对于结构化(传统数据库)和非结构化(如一本书、一张图片等)而言的。但是Internet上存在的数据既不是完全结构化的也不是完全非结构化的，因为它的页面也具有一定的描述层次的，存在一定的结构，所以我们将它称为半结构化的数据。如果想要利用Internet上的数据进行数据挖掘，必须先要研究站点之间异构数据的集成问题，只有将这些站点的数据都集成起来，提供给用户一个统一的视图，才有可能从巨大的数据资源中获取所需的东西。其次，还要解决Web上的数据查询问题，因为如果所需的数据不能很有效地得到，对这些数据进行分析、集成、处理就无从谈起。针对Internet上的数据半结构化的特点，寻找一个半结构化的数据模型则成为了解决上述问题的关键所在。此外，除了要定义这样一个半结构化数据模型外，还需要一项技术能够自动地从现有数据中将这个模型抽取出来，这就是所谓的模型抽取技术。因此半结构化数据模型及其抽取技术是面向Internet的数据挖掘技术实施的前提。
2 半结构化数据的定义
半结构化数据有两层含义，一种是指在物理层上缺少结构的数据，另一种是指在逻辑层上缺少结构的数据。有一些结构化数据，为用于web页面的显示而与html语言的标记符号嵌在一起，构成了物理上的半结构化数据。Internet中有大量丰富的数据，这些数据多存在于html文件中，没有严格的结构及类型定义，这些都是逻辑层半结构化的数据。Internet上的数据与传统数据库中的数据不同，传统的数据库都有一定的数据模型，可以根据模型来具体描述特定的数据.而上的数据非常复杂，没有特定的模型描述，每一站点的数据都各自独立设计，并且数据本身具有自述性和动态可变性.因而，Internet上的数据具有一定的结构性，但因自述层次的存在，是一种非完全结构化的数据，这也被称为半结构化数据。半结构化是上数据的最大特点。
半结构化数据主要来源有3方面:
1）在WWW等对存储数据无严格模式限制的情形下，常见的有HTML、XML和SGML文件；
2）在电子邮件、电子商务、文献检索和病历处理中，存在着大量结构和内容均不固定的数据；
3）异构信息源集成情形下，由于信息源上的互操作要存取的信息源范围很广，包括各类数据库、知识库、电子图书馆和文件系统等。
3 半结构化数据具有如下特点:
◆ 隐含的模式信息
虽然具有一定的结构，但结构和数据混合在一起，没有显式的模式定义(HMTL文件是一个典型)。
◆ 不规则的结构
一个数据集合可能由异构的元素组成，或用不同类型的数据表示相同的信息。
◆ 没有严格的类型约束
由于没有一个预先定义的模式，以及数据在结构上的不规则性，导致缺乏对数据的严格约束。
4 半结构化数据的数据模型
半结构化数据是缺乏严格、完整结构的数据。这类数据并非毫无结构，但它们的结构可能是隐含的、不完整的，甚至可能是需要不断修改的。要对这样的数据进行查询等处理，首要问题就是对半结构化的数据进行描述。由于没有强制性模式限制，使半结构化数据具有很大灵活性，能够满足网络这种复杂分布式环境需要，但同时也给数据描述和处理带来了很大困难。
4.1 半结构化数据的表示
具体地，象WWW这种数据模型可表示成3种关系：
{Obj(oid)，Ref(source，label，destination)，Val(oid，value)}
其中Obj表示一个无限的对象集合，例如WWW上的网页，网页中的内容都可看成是对象。Ref(o1，label，o2)表示从源对象o1到目标对象o2间存在一种联系，这种联系的语义信息用标记label表示。在我们的实现中，这种联系不仅包括了网页间存在的链接，而且当某个网页Pageobj包含多个具有相同意义的
对象o1，o2，…，on时，可以引入一个虚拟对象Vobj，这样，网页代表的对象Pageobj作为源对象，虚拟对象Vobj作为其目标对象，而o1，o2，…，on又作为Vobj的目标对象，并且Vobj与o1，o2，…，on的联系都有相同的标记。如，在我校图书馆的电子资源的网页中，包含对象中国期刊网，而其具体的论文的题目等内容在另一个页面，这样对象中国期刊网与链接所指页面就是源与目标对象的关系。关系Val（oid，value）提供了原子对象的取值信息，例如可以将每一篇论文作为一个对象，它的值为论文的题目。
4.2 半结构化数据的数据模型
目前，对半结构化数据及其模式主要有五种描述方法:基于图的描述形式、基于树的描述形式、基于逻辑的描述形式、基于关系的描述形式以及基于对象的描述形式。基于图的描述形式一般对半结构化数据采用标记有向图(labeled directed graph)来表示，其中最有代表性的是OEM(Object Exchange Model)模型。这种描述形式的一个显着优点是模式和数据采用同一种数据模型(图模型)，非常便于处理。模式数据图通常是一个有根且带边标记的有向图，模式图的边标记可以与数据图相同，也可以加以扩充，如允许正规式形式，或采用特定形式规则，等等。对于模式图中的节点，可以加一定注释，表明其代表语义或其它特定含义。
一般地，一个OEM对象表示为：
OID:
Label
Type
value
即OEM对象由4部分组成：对象的标识OID，标记，类型，值。其中OID唯一标识了一个OEM对象，既可以是一个无符号整数，也可以是某个用于描述该对象出自何处的表达式；标记表达一种语义信息，即对象表示的是什么；对象值的类型可取集合类型或原子类型；对象的值可以是原子值或是对象集合。OEM是一种基于图的数据模型，对象对应节点，对象与对象的关系以带标记的边表示。如下图所示：
图中，顶层结点为根对象，其标记为Music，它的值为一对象集合，因此其类型为set型。在构成Music值的对象集合中，MTV是其中的一个成员。当然，可能还有其它的标记为song的对象出现在该集合中。对象MTV的取值类型也是set型，然而与MTV不同的是，此处的集合类似一种记录结构，即对象MTV的值是具有不同标记的子对象集合，每个标记相当于结构的域。
5 半结构化数据的模式与以往关系数据模式的区别
半结构化数据的模式与传统的关系数据模式或面向对象数据模式的区别在于:先有数据，后有模式；不对数据结构进行强制约束，只描述数据的结构信息；它是只描述数据部分结构的非精确模式；随着被描述对象数据的不断更新而动态变化，分析半结构化数据的特点及产生原因，半结构化数据查询应该能够处理:
(1)单值和集合值属性兼容。即同一查询对应不同的半结构化数据，结果可能是单值，也可能是集合值。
(2)不同的查询对象数据类型。如HMTL文件中同一项目可以是描述信息，也可以是一个链接(网址)。
(3)未知结构的查询对象。有时查询对象往往是部分结构已知，需要通过一些机制了解数据源中的对象结构及关联的内容。
6 结语
随着Internet的日益普及，半结构化数据源也将会越来越丰富，因而如何有效地利用这些丰富的信息资源也逐渐受到人们的重视。半结构化数据是网络数据的一种重要形式，是一种特殊的数据资源，在半结构化数据上进行数据组织、管理和分析的技术有不同于结构化数据的特点，并对相关算法的并行性、效率、动态性都提出了新的要求。进一步的工作包括模式提取、查询表达及优化、DBMS集成服务、将聚类方法应用于半结构化数据，以及为半结构化数据提供适当的查询模式。
参考文献
[1]:FotoAfrati，e Notes in Computer Science 1186，Database Theory-ICDT’ York， Springer-Verlag， 1997，1-18.
seTechniquesfortheWorld-WideWeb:MODRecord.1998，27(3):59~74
InmonWH.数据仓库[M].王志海等译1北京:机械工业出版社，2000.
许学标，顾宁，施伯乐.半结构化数据模型及查询语言[J].计算机研究与发展，1998，35(10).
PapakonstantinouY，Garcia-MolinaH，ExchangeAcrossHeterogeneousInformation Sources. Proc. ofICDE. Taipei， 1995，251-260.