数据挖掘� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �第七章�复杂数据的挖掘�
� ����
������������� ������
�����
�����
�����
�
前面所介绍的数据挖掘方法主要是对关系数据库、交易数据库和由结构化数
据转换与集成过来的数据仓库中的内容进行挖掘。随着数据收集工具,先进的数
据库系统技术,以及互联网技术的迅速发展,不断获得巨量各种复杂形式的数据,
其中包括:结构化形式、非结构化形式、半结构化形式和多媒体形式等。因此数
据挖掘的一个重要任务就是挖掘复杂类型的数据,包括:复杂对象、空间数据、
多媒体数据、时序数据、文本数据和互联网信息。�
本章将要讨论如何更进一步地研究发展基本的数据挖掘方法,如:定性归纳、
分类学习、关联挖掘和聚类分析等,以及如何设计出新的数据挖掘方法以处理复
杂类型的数据对象,以便从复杂信息海洋中挖掘出富有价值的知识来。第一节将
介绍多维分析与复杂对象描述性知识的挖掘;第二节介绍空间数据的挖掘;第三
节是关于多媒体数据挖掘;第四节是关于时序数据的挖掘;第五节则是关于文本
数据的挖掘;最后一节是关于互联网信息的挖掘。�
���� ���������
����������
����������
����������
���
许多商用数据仓库与多维数据库分析 ���� 工具的主要局限就是:它们对
维的描述与计算所涉及的数据类型均有限制。大多数数据立方(操作)的实现都
将维限制在非数值类型的数据描述;而计算方法也仅为简单的数值累计。为了将
数据挖掘引入包含复杂对象的多维数据分析,就需要了解对复杂结构对象是如何
进行泛化操作的,以及对象立方是如何构造的以便于 ����处理与对象数据库的
挖掘。�
本节将详细介绍复杂对象的泛化操作是如何进行的。�
存储与检索复杂结构数据的问题已在对象-系数据库和面向对象数据库系统
领域中进行了较长时间的研究。这些系统将一个大规模复杂数据对象按类(��� )
进行组织;并将这些类构造成类
子类层次结构。一个类中的对象描述包括:(�)
一个对象标记;(�)一组可能包含复杂数据结构,如集合-值、列表-值、类别组
成层次、多媒体数据等属性;(
)一组对相应(复杂结构)对象进行相关计算与
处理的方法。�
为了便于在这样(具有复杂结构)的数据库中进行泛化与归纳操作,就需要
对对象-关系数据库和面向对象数据库中的每类成分如何进行泛化,以及泛化后
的数据如何用于多维数据分析和数据挖掘的有关情况进行讨论。�
数据挖掘� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �第七章�复杂数据的挖掘�
����
������ ������������������������������
对象-关系数据库和面向对象数据库的一个重要特点就是:它们具有对复杂
结构数据(如集合-值、列表-值和嵌套结构数据)进行存储、检索和建模的功能。
可以通过好几种方法对这类数据进行泛化操作,以获得概要性的有意义的模式。� �
集合-值属性可以是同质或异质的类型。通常一个集合-值数据可以通过以下
方法进行泛化:(�)对一个集合中每个值都泛化到相应更高的层次上;(�)获得
一个集合带有普遍性的概述,如一个集合中的元素个数、集合中的取值范围等。
此外还可以通过应用不同的泛化操作来探索不同的泛化路径。而这种情况下,所
获得的泛化结果就是一个异质集合。�
如一个人的习惯(�����)就是一个集合-值属性。它包含一组值,诸如:�网
球、足球、下棋、钢琴�;该属性可以被泛化到更高的概念层次,如:�运动、音
乐�或 �(属性中的元素个数)等。此外也还可以附加一个属性 �����(它与泛化
后属性相关联,用以描述相应属性是由多少个(低层)元素泛化而来的。如:�运
动(
)、音乐(�)�,其中运动(
)表示有三种类型的运动。�
一个集合-值属性可以被泛化到一个集合-值属性或单值属性;反之一个单值
属性,在层次是网格结构或泛化有不同路径时,也可以被泛化为一个集合-值属
性。对这类泛化后所获得的集合-值属性,做进一步泛化时就需要遵守集合中每
个值相应的泛化路径。�
一个列表-值或一个序列-值属性的泛化方式与集合-值属性的泛化方式相
似;唯一不同的是一个序列中的元素顺序在泛化后应该仍然保留。列表中的每个
值可以泛化到相应的更高一层;当然也可以根据列表所表示出的概要特征对列表
进行泛化,如列表长度、列表元素类型、列表取值范围等;也可以丢掉列表中的
一些元素(进行泛化)。一个列表可以被泛化为一个列表、一个集合或一个数值。
例如:描述一个人教育
的一个序列列表为:“��学士,电气工程,北大,����,
� 月�,�硕士,计算机工程,清华,���
,� 月�,�博士,计算机科学,科大,
����,� 月��”;可以通过消除这一列表中一些不太重要的描述,如“�����,�
月�,��”,或者保留一些最重要的元组,如“�博士,计算机科学,科大,������
月�”。�
集合-值和列表-值属性,都是简单的结构-值属性。通常一个结构-值属性可
以包含集合、元组、列表、树、记录或它们的组合。此外一个结构也可以在任一
层次嵌套在另一个结构之中。结构-值属性一般可以采用以下几种方法进行泛化:
(�)泛化结构中的每个属性并保留结构整体形式;(�)拉平(����������)结构
并对拉平后的结构进行泛化;(
)通过高层次概念或累计来概述低层次的结构;
数据挖掘� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �第七章�复杂数据的挖掘�
� ����
(�)返回一个结构的综述或类型。�
������ ��
��
������
��
������
��
������
��
������
除了泛化概念替换和结构数据概述之外,累计和近似也可以认为是一种很重
要的泛化手段。它们可以对具有许多取值属性、复杂结构、空间与多媒体数据进
行泛化。�
以空间数据为例,将非常详细的地理(信息)点泛化为聚类(性)区域,如
根据土地使用情况,将其聚合为商业、居民、工业,或农业区域等。这种泛化需
要利用空间操作(如空间合并和空间聚类等)来归并一系列的地理区域。而累计
和近似也是这种泛化中的重要方法。在空间归并中,不仅需要(在同一类中)聚
合具有相似类型的区域;而且还要计算整个面积、平均密度,或其它累计函数
(值);忽略掉一些(对有关任务)不太重要并具有不同类型的分散区域,如:
不同的土地具有不同的农业用途。如种植蔬菜、稻谷、水果等。可以通过空间合
并将它们聚合起来以形成一大块农业用地(区域);然而这样一些农业用地可能
会包含高速公路、房屋、小商店等;如果相应土地的大部分是农业用地,那么就
可以忽略掉这些零散的其它用途的(区域)点,而整个区域也可以近似认为是农
业用地(区域)。�
空间操作,如空间联合、空间重叠、空间交叉等,都可用于将小的区域归并
为大的聚合(性)区域;这时也就可以用到空间累计和近似操作来帮助进行有关
的泛化工作。�
一个多媒体数据库可能包含复杂文本、图形、图像、视频(段)、地图、音
乐和其它形式的视频
音频信息。这样的多媒体信息通常都是按照可变长的字节
序列进行存放的。并在多维空间中对这些数据段进行连接和索引以方便检索与查
询。对多媒体数据进行泛化可以通过识别和抽取数据模式中的基本特征来完成。�
目前已有一些从多媒体数据中抽取基本特征或通用模式的方法。对一幅图像
(处理)来讲,可以利用累计和近似的操作从图像数据中抽取出大小、颜色、纹
理、定位,以及所包含对象或区域的相对位置和结构等信息;而对于一段音乐(处
理),它的旋律则可通过对数据段中不断重复的(近似)模式进行归结而获得。
而对于一篇文章来讲,它的摘要和内容目录、主题和(文本中频繁出现)关键词
等,均可以作为泛化结果。�
对多媒体数据和空间数据进行泛化以便抽取出(隐含在数据中)有意义的知
识,是一项富有挑战性的工作。在多媒体和空间数据库中所研发的技术,象图像
检索、多媒体索引、空间数据存取与分析技术等,可以与数据泛化和数据挖掘技
术相结合以便获得满意的结果。以下就将介绍对这类数据的挖掘技术。�
数据挖掘� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �第七章�复杂数据的挖掘�
����
������ �������������������������������������������
一个面向数据库的基本组件就是对象标记,它是用来唯一标记对象的。它在
对数据结构进行重组时保持不变。表面上看似乎不太可能对对象标记进行泛化。
但是由于对象数据库中的对象已被组织为类
子类层次结构。对一个对象的泛化
可以利用它的相关层次结构来完成。因此一个对象标记可以通过以下几种方式进
行泛化:首先对象标记泛化为(对象所属)最低层次的子类标记;然后这个子类
标记逐步(通过沿类
子类层次结构上升)泛化到一个更高层次类
子类标记。类
似的,通过沿相关类
子类层次结构上升,一个类
子类也可以泛化到相应的超类。�
������ ���
���������
���������
���������
��������
由于面向对象数据库组织成了一个类
子类层次,一个对象(类)某些属性
或方法并没有在类本身中明确定义,但是从更高层次类中继承而来。在类
子类
结构是按方格进行组织时,一些面向对象数据库可能容许对象从多于一个超类中
继承其性质(称为多重继承)。一个对象所继承的性质可以通过数据库中的查询
获得。从数据泛化的角度来看,区分同一个类中哪些数据是继承而来;哪些数据
所存放类本身是没有多大意义的。只要能够通过查询处理获得相关数据,数据挖
掘就可以将继承而来的数据当作存储在类本身数据,并进行相应的泛化操作。�
方法是面向数据库中的另一个重要组件。许多对象的数据行为可以通过利用
方法来获得。由于方法通常是通过采用计算过程
函数,或通过一组演绎
来
定义。虽不可能对方法本身进行泛化,但却对由方法应用所获数据进行泛化。也
就是,可以通过应用方法或通过数据检索,获得与任务相关的数据,然后将这些
产生的数据作为现有的数据来进行泛化。�
���� � ����������������������������������
一个对象属性可以由另一个对象组成或描述。而这些属性由有可能由其它对
象组成或描述,这就形成了一个类组成结构。对这种类组成结构进行泛化就可以
看成一组(可能是无限,若是递归嵌套的话)嵌套结构数据。�
原则上讲,对复杂对象的引用可能需要通过对类组成结构中的相关引用序列
来描述。然而在大多数情况下,所涉及的引用越长,与原对象的联系也就越弱。
例如:一个“学生”对象的“车主”属性,就引用了另一个对象“车”,这一“车”
对象可能包含属性“汽车销售商”,它又会引用包含“子女”属性的“经理”对
象。显然不太可能发现在学生和它汽车销售商经理子女之间存在有价值的联系规
律。因此对这一对象的泛化就只需对其本身属性值、方法,以及(通过类组织结
构上紧密相联的有关部件的)有限引用进行相应操作即可。�
数据挖掘� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �第七章�复杂数据的挖掘�
� ����
����
� ��������� !�������� !�������� !�������� !�
在一个对象数据库中,数据泛化与多维分析不是对单个对象而是对一组数据
类进行的。因此一个重要的问题就是如何基于类对大量对象进行泛化。�
由于一个类中的对象可以共享许多属性和方法;而对每个属性和方法的泛化
均涉及一系列泛化操作,那么主要的问题就变成如何协调(类中)不同属性和方
法的泛化过程以产生有意义的结果。�
利用基于类的泛化,(第三章介绍的)基于属性归纳方法,可以进行扩展以
挖掘对象数据库中的数据特征。�
一个基于泛化的数据挖掘过程可以看成对不同属性应用一系列基于类的泛
化操作,直到所获类中包含一小部分泛化对象,它们可以用利用更高层次项的简
洁泛化的规则来描述为止。为提高执行效率,复杂对象类的多维属性泛化可以通
过检查每个属性(维)、将它们泛化到简单的值,以及构造一个多维数据立方(称
为对象立方)来完成。在建立对象立方后,就可以对这样的对象立方进行(与关
系数据库数据立方类似的)多维分析与数据挖掘了。�
但从应用的角度来看,将一组数值泛化为单个数值并不一定是理想的。如:
对一本书,关键字属性可能会包含一组描述这本书内容的关键字。而将这组关键
字泛化到一个值就没有多大意义。在构造对象立方和基于对象数据挖掘中,如何
有效处理集合-值数据仍然是一个有待研究的问题。�
������ �"#��� !"#��� !"#��� !"#��� !�
本小节以一个具体挖掘示例来说明泛化操作在挖掘复杂数据库所起的作用。
这个挖掘任务就是:从一个
数据库利用分而治之策略,发现成功操作的重要
模式。�
一个计划包括一串长度可变的操作序列;而一个计划数据库(或简称计划库)
就是许多计划的集合。计划挖掘任务就是从计划库中发现重要的模式知识。计划
挖掘可以用于从飞行航班数据库中发现商业旅行的旅行模式,或从一系列汽车修
理活动中发现重要的模式。�
计划挖掘与序列模式挖掘不同,后者是在更详细的操作层次上,挖掘出大量
频繁发生的序列。计划挖掘就是要从计划库中抽取出重要的泛化后序列模式。�
下面就以航空旅行为例来说明计划挖掘过程。�
示例示例示例示例 ���:假设一个航空旅行计划库,如表-��� 所示,存有顾客飞行序列,
其中每个记录对应一个序列库中的一个操作;一系列带有相同计划号的记录就构
成了一系列动作的一个计划。属性“
��
��
”和属性“�
����”描述相应启停
数据挖掘� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �第七章�复杂数据的挖掘�
���
航空港的编号,如表-���所示,就是有关航空港的信息。�
������ �������� �!�"�#"�� �!�"�#"�$%�&�� �""�'��� �""�'��$%�&�� ��"����� ��
��
��
��
��
��
! �
��
��
�
��
��
! �
��(�
)*+�
�, �
��-�
.�/�
! �
�0���
�����
�
���
�����
�����
! �
)*+�
�, �
��-�
.�1�
�, �
! �
�����
��
��
�2���
�0���
�����
! �
%3��
4��
4��
���
���
! �
��
��
��
��
��
! �
表-���� 飞行计划库内容描述�
如表-���所示,从计划库中有许多可以挖掘的模式。如:可以发现美国亚特
兰大城市飞往中西部城市的航班会在 �, 停留,这主要是因为 �, 是主要航
班枢纽之一。注意有关航班枢纽的信息,象洛杉矶(��-)、芝加哥(�, )和
纽约()*+),可以根据机场大小很容易地从表-��� 中获得。然而一个航班数据
库有数百个枢纽,不加区分地挖掘这些“枢纽”信息将会导致获得非常多的分散
的(缺乏实质支持的)规则;并仍会漏掉有关的全局的一个清楚描述。�
��"!�"�$5�6�� 5��7� .����� ,������ ��"!�"�$.�8�� ��
�, �
.�/�
��-�
��(�
! �
59������
.!"�������6�
�� ������� �
��:��7�
! �
/������ �
/������ �
5�����"����
1�;�<�"=�
! �
>�6?3� ��
>�6?3� ��
��������
���������
! �
�������
������
0�����
������
! �
��
��
��
��
! �
表-���� 航空港信息库描述�
这里所希望发现的就是涵盖重要计划的一小部分普遍序列模式;可以根据这
样挖掘序列来进行指导搜索。要挖掘这样序列模式的关键就是将计划库中计划泛
化到足够高的层次。对于一个多维数据库,如表-���所示的航班计划库,就可以
用于帮助进行计划的泛化操作。由于低层次信息很少能够有共同点以便形成简洁
的计划,因此可以对计划库根据多维模型,如图-���所示,进行多方向的泛化,
直到泛化后计划具有共同的、有意义的、具有实质支持的序列模式;并产生高层
次简洁的规则。�
现在就对计划库进行检查,通过聚合具有相同计划编号,可以获得以下的计
数据挖掘� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �第七章�复杂数据的挖掘�
� ��
�
划序列动作:“���
��
������� ��������
�������������
�”;“��
��
������� �
�
�
�
����!��
!������"�
��”。�
��"!�"�$.�8�
��������
��������
��"����
�����������
��
����
����������
���� ����� ������
沿概念层次树
提升
�
图-���� 数据库的多维模型描述�
这些序列看起来是很不同的。但是它们可以进行多维泛化操作。在它们根据
机场大小(��"!�"�$.�8�)维进行泛化时,可以获得诸如“�������”(其中 � 代
表一个大机场(枢纽),. 则代表一个相对较小的地区机场)的有意义的序列模
式,如表-��
所示。�
������ ���?.�@� .�8�?.�@� .����?.�@� ,�����?.�@� ��
��
��
! �
��(?)*+?�, ?��-?.�1�
.�/?�, ?)*+?.<,�
! �
.?�?�?�?.�
.?�?�?.�
! �
1?1?/?5?5�
/?/?1?1�
! �
A?A?>?�?��
>?>?A?A�
! �
��
��
! �
表-��
� 航空港信息库描述�
对大量的飞行旅行计划进行泛化,特别是使用合并和选择操作来处理泛化后
的序列,就会得到相当通用且很有规律的模式,如表-���所示。其中合并操作就
是将连续相同的符号合并为一个并用“B”来表示一个具有相同类型的动作序列;
而选择操作则利用“CD”来表示方括号中的对象或动作是可选择的。�
通过合并相似的动作,就可以获得一个泛化序列模式,如:“C.D?��?C.D� � �
C�0��ED”;其中:��表示模式 �出现一次或多次;方括号表示其中的内容是可以
选择的。此外该模式的支持度为 �0��E,也就是说有 �0��E的旅行计划具有
“C.D?��?C.D”模式,即首先从一个小机场出发,中途在一到多个大机场逗留,最
后到达一个小机场。�
数据挖掘� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �第七章�复杂数据的挖掘�
����
在识别出重要的序列模式之后,就可以利用它们来划分计划库;然后挖掘每
个所划分的计划库以发现共同的特征。例如:从一个划分后的计划库中,可以发
现:�
�
��������
���������
��
��
��������
��
��������� =⇒F�GHF�GHF�G � C��ED�
上述规则表明:若从一个小机场 �直飞一个大机场 �,那么 �和 �有 ��E的
概率是在同一区域。� � � � � � � � � � � � � � ■�
������ ���?.�@� .�8�?.�@� .����?.�@� ��
��
��
! �
C.D?��?C.D�
C.D?��?C.D�
! �
1�?/?�5��
/�?1��
! �
A�?>?���
>�?A��
! �
��
��
! �
表-���� 合并计划中连续、相同的动作列表�
上述示例表明利用分而治之策略,首先通过对计划库进行多维泛化操作,来
发现一些有价值的、高层次的简洁计划序列;然后根据所挖掘出的模式划分计划
库以发现相应各子计划集的特征。这种挖掘方法可以用于许多应用,如:网站访
问模式挖掘,即通过研究网站的访问记录数据来识别受欢迎的网站入口和共同路
径;然后再对详细的子模式进行挖掘。�
计划挖掘技术在几个方面得到拓展。例如:可以利用(与关联规则挖掘类似
的)最小支持阈值来帮助确定泛化的层次以保证一个模式覆盖足够的示例数;也
可以探讨计划挖掘中的其它操作(如小于),以便从子序列中抽取出关联信息,
或挖掘出包含多维属性的序列模式。如:包含“��"!�"�$.�8�”和“,�����”的模
式。这样与维结合的挖掘也需要首先将每个维泛化到更高的层次;然后再检查结
合的序列模式。�
���� �
������
������
������
�������
空间数据库存放着大量与空间相关的数据,诸如地图、遥感数据或医疗图像
数据、大规模集成电路设计数据等。所谓空间数据挖掘就是指抽取空间关系知识,
或其它没有在空间数据库明确存放的有意义的模式。�
与关系数据库不同,空间数据描述涉及许多特征。它包含拓扑和(或)距离
信息;它们按照复杂多维空间索引结构进行组织;并通过空间数据存取方法进行
存取。它常常还需要进行空间推理、地理计算和知识表示技术。空间数据挖掘需
要将数据挖掘与空间数据库技术结合起来。空间数据挖掘的一项重要工作就是探
索有效空间数据挖掘技术,因为空间数据规模巨大,空间数据类型和存取方法也
数据挖掘� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �第七章�复杂数据的挖掘�
� ����
是非常之多。�
空间数据挖掘可以帮助理解空间数据、发现空间关系和空间与非空间数据间
关系、构造空间知识库、重组空间数据库,以及优化空间查询等。此外也可以广
泛应用于地理信息系统、地理市场、遥感、图像数据库探索、医疗成像、导航、
交通控制、环保和许多其它利用空间数据的领域。�
空间数据的统计分析也是一种常用的空间数据分析方法;并提出了许多帮助
进行这类分析的统计分析算法和各种优化技术。它可以较好地处理数值数据并提
出描述空间问题的实际模型。然而这种方法通常是基于空间分布数据相互独立假
设基础之上的,但是实际上空间数据经常相互关联。此外统计方法不能很好地处
理符号量、不完全或不确定数据;而且在大规模数据库中的处理代价也很大。空
间数据挖掘通过强调有效、可扩展、与数据库系统协作、更好的用户交互和发现
新知识,来帮助扩展传统空间数据分析方法。�
������ �� ������ ������ ������ ����� ��
��
与关系数据类似,可以将空间数据集成起来构造数据仓库以促进空间数据的
挖掘。空间数据仓库就是一个面向主题、集成化、与时间相关所确定的空间与非
空间数据集合,它支持空间数据挖掘和与空间数据相关的决策活动。�
示例示例示例示例 ��#:在 ("��� 9�5��#&:��(简称 (�5�)分布着三百个气象观测站。每个
气象站记录(特定小区域)每天温度和降雨情况,将有关记录发送给省级气象站。
要在一张地图上逐月、逐个地区或不同温度和降雨组合情况下,观察气象模式;
或者沿着任意维动态 6"���?6�;� 或 "���?#! 以探索所期望的模式,如:���� 年夏
季 *"� �"�I����7的湿热区域。� � � � � � � � � � � � ■�
为方便多维气象模式的分析,需要建立一个空间数据仓库并支持空间
����。但是在构造和利用空间数据仓库方面存在几个挑战。�
第一个挑战就是集成来自异质数据源和系统的空间数据。空间数据通常是保
存在不同企业和政府机构并采用不同的数据格式。数据格式不仅结构特别(使用
光栅与基于向量空间数据、面向对象与关系模型、不同空间存储索引结构等);
而且也是因厂商不同而不同。之前在集成与异质空间数据交换方面所做的大量工
作已为空间数据集成与空间数据仓库的构造奠定了基础。�
第二个挑战就是在一个空间数据仓库中实现快速灵活在线分析处理。星
雪
花模式仍是空间数据仓库建模的较好选择。原因是它提供了一个简洁有组织的数
据仓库结构并方便 ����操作。然而在一个空间数据仓库中,维与测量都可能包
含空间组件。�
空间数据立方包含三种类型的维:�
数据挖掘� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �第七章�复杂数据的挖掘�
����
(�) 非空间的维,它是仅包含非空间数据的维。例如:两个维,温度
(�
��
���
)和降雨(�
����������),可以用于构造示例 ��� 所示的数
据仓库;其中每个维均包含非空间数据,它们的泛化也是非空间的,如:
热(���)和湿(�
�)。�
(�) 空间到非空间维,它是一个维,其基本层次数据是空间数据;但泛化后,
从一定高层次开始,就变为非空间数据了。例如:在美国地图上的州(����
)
维就是空间数据;但每个州可以泛化到一个非空间值,如J西北太平洋,
或大的州等;并且做进一步泛化仍然是非空间的,因此这时它可以作为非
空间维进行处理了。�
(
) 空间到空间维,它是一个维,其基本层次和所有其它高层次的泛化数据均
为空间数据。例如:等温区域,就是一个空间数据;且它的所有泛化数据,
诸如:覆盖 �?�度的区域、�?��度区域等等均为空间数据。�
需要区分空间数据立方中的两种类型的量度:�
(�) 数值量度,它是一种仅包含数值数据的量度。例如:空间数据仓库中的一
个量度可以是一个区域的月收入;而利用 "���?#! 操作就可以获得每年、
每个国家的年收入。数值量度又可以进一步分为:分布类、代数类和整体
类等。�
(�) 空间量度,它是一种包含指向空间对象的指针集合。例如:在示例 ���所
涉及的数据立方泛化操作中,具有相同温度和降雨范围的区域可被聚合为
相同的单元而形成的量度;它是包含一组指向这些区域的指针集合。�
��������� �
��
�
��
��������
�������������
������� �
����
�����
���
�
�������
�� ������
��
�
�������
����������
�������������
��
�������
�� ������
��
�������
��
�������
��
����������
�� �
�� ������
�� �
���
����
������
��������� ��
� ������
�������
�����
��������
����
������
��������
$���气象气象气象气象
�
图-���� (�5�气象空间数据仓库星模型和 (�5�气象观测区域图�
一个非空间数据立方仅仅包含非空间的维和数值量度。若一个空间数据立方
数据挖掘� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �第七章�复杂数据的挖掘�
� ����
包含空间维但没有涉及空间量度,那么它的 ����操作,如:6"���?6�;�或 "���?#!
操作,就可以按照类似与非空间数据立方中的相应操作进行;但是将空间量度引
入空间数据立方后,就会在如何有效实现方面提出一些挑战性的问题。在以下的
示例中就会看到。�
示例示例示例示例 ��%:示例 ��� 所描述 (�5�气象的数据仓库星模型如图-��� 所示。它包
括四个维:温度(��&!�"��#"�)、降雨(!"���!�������)、时间(��&�)和区域名称
("�����$��&�);此外还有三个量度:"�����$&�!、�"���和 ��#��。每个维的概念
层次树可以由用户或专家创建,或根据数据聚类分析自动产生。如表-���所示,
就是 (�5�气象数据仓库中各维所对应的概念层次树。�
J$ ���
�
���� �
��������
�� �����
���
���
����
��������
⊂
⊂⊂⊂�
�
����� �
�
���������������
⊂⊂⊂ �
J
�
��
���
�
��
�K
��
�K�����K���
���K�����K�����K��
��K�����K�������
����
����
����
����
�
�������
��������������
⊂
⊂
−−−−⊂
⊂
�
J���
������� �
�����K��
���
K�������K����
����K�������K�������K����
����K���������K��
����
����
�
�
!��
�
�
�
�!��
�
����
⊂
⊂
⊂
⊂
�
表-���� (�5�气象仓库各维所对应的概念层次树�
�
图-��
� 不同 "���?#!操作产生的两个不同泛化区域�
在示例 ��
所涉及的三种量度中,� �"��和 ��#��是数值量度;它们可通过类
似与非空间数据立方的计算方式求得。而 "�����$&�! 则是一个空间量度。它代
表一组指向相应区域的指针集合。由于不同空间的 ���� 操作是在一个
"�����$&�!上进行,这样就会产生不同的空间对象集合。这也提出了一个新的课
题:如何动态灵活地计算归并所获得的大量区域。如在 (�5�气象图上进行两个不
数据挖掘� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �第七章�复杂数据的挖掘�
����
同的 "���?#! 操作可能产生两个不同的泛化区域图,如图-��
所示。图中的每一
个结果都是对如图-���(右边)所示区域的归并结果。�
与数值量度不同,后者所计算的每个累计值只需要几个字节(来存储);而
一个归并后的 (�5�区域图可能需要数兆的存储空间。因此无法预先计算所有可能
的空间归并(结果),并将它们存放到数据立方的相应立方单元中。只有在线计
算成本和存放计算归并所获结果所需要的存储空间之间取得平衡与折衷。�
在构造空间数据立方的空间量度计算方面,至少有三种选择:� �
(�) 收集存储相应空间对象指针集合;但不对空间数据立方中的数据量度进行
预先计算。这一做法可以通过在相应立方单元存放指向一组空间对象指针
的指针,并完成相应空间对象的空间归并操作来实现。必要时,可以边使
用边产生(����9����7);尤其在只需要空间显示(而无须完成实际归并时),
或当没有许多区域需要进行归并时,或在线空间归并计算足够快时,这种
做法都不失为一个好办法。由于 ����结果常用于在线空间分析和挖掘,
因此仍然需要在可能的情况下,预先计算好一些空间概念区域以提高进行
这类分析的工作速度。�
(�) 在一个空间数据立方中,预先计算(好)和存储空间量度一些大致近似
估计。当粗略估计结果不占用空间时,求得一个空间归并的大致粗略结果
是一个好的选择。如一个最小约束矩形(>(,),它由两个点来表示的。
它可作为一个归并区域的粗略估计。因此这样表示的预先计算(好)的结
果就比较小且可以很快提供给用户。若对特定单元需要更高精度,那就需
要读取预先计算好的结果(如果有的话),或当场计算。�
(
) 在空间数据立方中,预先计算好一些空间量度。这似乎是一个聪明的选择。
但问题是如何选择数据立方中的单元进行预先计算。选择可以在立方层次
上进行;也就是要么对立方中每个单元(构成的)可归并的空间区域进行
预先计算和存储;要么在没有选择立方情况下,什么也不计算。由于立方
中通常包含大量空间对象,这样做或许涉及预先计算和存储大量可归并的
空间对象;但其中有一些却很少用到。因此这里推荐在一个较细层次进行
选择方法。即检查一个立方中每组可归并空间对象以确定这种归并是否要
预先计算。需要根据使用率(存取频率或存取优先级)、所归并区域的可
共享性、平衡整体空间和在线计算开销进行(选择)决策。�
借助有效空间数据立方和空间 ����的实现,基于泛化描述的空间挖掘,诸
如:空间定性描述和差异描述,就可以有效进行了。�
������ �� $%&'� $%&'� $%&'� $%&'�
数据挖掘� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �第七章�复杂数据的挖掘�
� ����
与在事务数据库和关系数据库中挖掘关联规则类似,也可以从空间数据库中
挖掘空间关联规则。一个空间关联规则具有形式: �� → � EDE�C �� ,这里 " 和
#是空间和非空间谓词集合; �
为规则的支持度; �� 为规则的可信度。如以下
规则就是一个空间关联规则:�
F�G$F$�G$F�G$ ��
$�������
�
��
���
��������
���������� →∧ � ED0�E����C �
上述规则表示J0�E接近运动场的学校也接近公园;而数据库中有 ���E数据
是属于这种情况的。�
有许多类型的空间谓词可以用于构造空间关联规则;如表示拓扑关系的:相
交、重叠和不相交等;表示空间定位的:左边、西边等;以及表示距离的:接近、
远离等。�
由于空间关联挖掘需要对大量空间对象中的多种关系进行评估。这一过程可
能开销很大。这里可利用一个被称为主动提炼有价值的挖掘优化方法,来帮助进
行空间关联分析。该方法首先利用快速算法粗略挖掘大的数据集;然后利用更费
时的算法对粗略挖掘所获数据集进行更一步处理以改善其挖掘质量。�
为确保(后一阶段)利用高质量数据挖掘算法时,粗略挖掘得到的数据集能
够覆盖所有结果,就要求前一个阶段所应用的粗略挖掘算法应满足性质,即超集
覆盖性质“保留所有可能的结果”;换句话说,就是它应容许一个假的真结果,
即一个结果所包含数据集中的有一部分可能不属于
内容;但不容许出现假的
假结果,即将一些真的结果排除在外。�
为挖掘与空间谓词“��� �$��”相关的空间关联,需要首先收集满足最小支
持阈值的候选;具体做法就是:(�)应用一定的粗略空间评估算法,如利用最小
约束矩形(>(,)结构(只登记两点而不是一组复杂的多边形);(�)评估一
个宽松的空间谓词,如“�$��� �$��”,它是将“���� �$��”泛化后所得到的覆盖
了更多的内容,象“��� �$��”和“��#�9”等。若两个空间对象相距较近,围绕
它们所形成的两个最小约束矩形也相距较近,与“�$��� �$��”相匹配。但反过
来却不一定是这样了,若两个最小约束矩形相距较近,那么相应两个对象不一定
相距较近。所以最小约束矩形消除是一种检查“��� �$��”有效(假之真)测试
工具。只有通过粗略集测试,才能够利用更费时的空间计算算法来进行进一步检
查。通过这一预处理,只有在近似水平上频繁出现的模式,才应该作进一步仔细
同时又是费时的空间计算分析。� �
������ �� (�&'� (�&'� (�&'� (�&'�
在一个大规模多维数据集中,借助特定的距离计算方法,空间数据聚类分析
数据挖掘� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �第七章�复杂数据的挖掘�
����
就应该识别出聚类或密集区域。空间聚类在第六章已作了详细介绍,而聚类分析
通常也是将空间聚类作为示例和应用领域。�
������ �� &��)*&'� &��)*&'� &��)*&'� &��)*&'�
空间分类空间分类空间分类空间分类就是分析空间对象和推导出分类模式,如决策树,以及与一定空间
性质相关的,如高速公路、河流,或地区的邻居(情况)。�
假设要根据家庭平均收入,将一个省的区域划分为富或穷的部分,以帮助发
现决定一个区域是富还是穷的(与空间相关)重要因素。这就是一个空间分类问
题。鉴于空间对象涉及许多描述属性,诸如山区、大学园、省间高速路、靠近湖
或海。这些特征可以用来进行相关分析以发现有价值的分类模式。�
空间趋势分析是完成另一项任务。也就是:发现空间维上的变化和趋势。通
常趋势分析是检测时间(维)的变化,如时序数据中的时模式变化,空间趋势检
测则将时间换成了空间,即研究空间中非空间和空间数据变化的趋势。例如:在
从城市中心向外推移空间中的经济情势的变化趋势,或从海洋向内陆移动空间中
植物或气候的变化趋势等。这样的分析中,常常用到利用空间数据结构和存取方
法的回归和相关分析方法。�
也有许多涉及在时空中变化模式的应用。例如:高速路上或城市中的交通流
量分析,就(同时)涉及时间与空间。天气模式也与时间与空间(同时)密切相
关。要发现时空模式并进行有效预测,就需要研究并提出挖掘时空数据的有效方
法。�
目前虽然在空间分类和空间趋势分析方面有一些研究,但在时空数据挖掘方
面却少有人去研究。未来还需要在时空数据挖掘方法与应用做必要的研究。�
���� � �+,��- !+,��- !+,��- !+,��- !�
空间数据库系统通常处理的是向量数据,如:点、线、多边形(区域),或
它们的合成,如网络与划分等。典型的这类数据包括:地图、设计图、蛋白质分
子
- 表示图等。但是还有许多与空间有关的数据是采用光栅(图像)形式表
示的,如:卫星图像、遥感数据、-断层扫描图像等等。因此对光栅或图像数据
库进行挖掘也是很重要的。以下将在介绍多媒体数据挖掘中介绍有关图像的挖掘
方法。�
���� ����������������������������������
随着视频-音频设备、5 -,�> 和互联网应用的普及,许多数据库中存有
大量的多媒体对象,其中包括:视频数据、音频数据、图像数据、序列数据和超
数据挖掘� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �第七章�复杂数据的挖掘�
� ����
文本数据(其中包含文本、链接和标记)。存储和管理大量多媒体对象的数据库
系统就称为是多媒体数据库系统。典型的多媒体数据库就是美国航空航天局的
A�.(地球观测系统)多媒体数据库。还有其它图像数据库、视频
音频数据库、
人类基因数据库和互联网数据库,它们均是多媒体数据库。�
本节将介绍基本的多媒体挖掘方法,包括:基于内容的多媒体检索和相似性
搜索,多媒体数据泛化和多维分析,多媒体数据的分类与预测分析,以及多媒体
数据关联挖掘等方法。�
������ ���
���./01��
���./01��
���./01��
���./01�
多媒体索引和检索系统有两大类:(�)基于描述的检索系统,该系统根据多
媒体描述,如关键字、标题、大小、创建时间等来建立对象索引和进行相应的检
索操作;(�)基于内容的检索系统。该系统支持根据多媒体内容,如:颜色直方
图、纹理、形状、对象等,进行检索。前者需要进行涉及大量人力劳动的(写)
标题,或(由于多媒体内容描述关键字不准情况下)进行自动抽取所产生低质量
描述;而后者帮助利用可视特征进行多媒体索引,并根据特征相似性检索对象,
从而可以满足应用需求。�
在基于内容检索系统中,常常用到两类检索:基于图像采样的查询和基于图
像特征描述的查询。前者就是要发现所有与给定样本相似的图像。在数据库中搜
索相似图像工作是通过描述图像的特征向量比较来实现的。相关的特征已在数据
库中建立了索引且首先从样本图像抽取相应的特征。而后者则是通过图像的颜色
直方图、纹理、形状等特征,对数据库中图像所具有的相应特征进行比较来实现。
有些系统(L(/5,L#�"7�:7� /&����5������)则支持基于采样和基于特征两种检
索方式;也有系统支持基于内容和基于描述的查询。�
基于内容检索具有广泛的应用,其中包括:医疗诊断、天气预报、%I生产、
3�:图像搜索引擎和电子商务等。�
在图像数据库中已提出了一些基于相似性检索的方法,有关这些方法的情况
说明如下:�
(�) 基于颜色直方图的特征向量。这种方法中的一个图像的特征向量是由根据
图像的颜色构成所获得的颜色直方图组成,而与图像的大小和位置无关。
由于这种表示方法中没有包含有关形状、位置、纹理的任何信息,因此两
个具有相同颜色构成的图像或许具有非常不同的形状或纹理,甚至在含义
上毫不相关。�
(�) 多特征组成的特征向量。这种方法中的一个图像的特征向量包括多个图像
特征,诸如:颜色直方图、形状、位置和纹理。而且可以给不同特征定义
数据挖掘� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �第七章�复杂数据的挖掘�
���
不同的距离函数;然后将它们结合到一起形成整个的输出结果。基于内容
的多维搜索常常利用一到多个探索特征来搜索包含这样(类似)特征的图
像。也可以用于搜索类似图像。�
(
) 基于小波的特征向量。这种方法中利用一个图像的小波相关系数作为特征
向量。原因就是小波从一个整体角度表示了图像的形状、纹理和位置信息。
从而减少了(�)多维搜索所使用的基本特征并改善效率。但是由于它只
是利用一个特征向量来描述整个图像,因此在遇到包含类似对象但位置不
同或大小不同的图像将会失败。�
(�) 基于小波和基于区域细度的特征向量。这种方法中,对图像不同细度的特
征向量进行计算与比较而不是整个图像。因为相似图像包含相似区域但一
个图像区域需要进行缩放以使其与另一个图像的相应区域匹配。因此需要
定义查询图像%和目标图像�相似性计算方法;其中采用有两个匹配图像
%和�所覆盖图像的程度来描述其相似性。这种基于区域的相似搜索可以
发现包含类似对象的图像,但要对图像中相应区域进行转换。�
������ ���
��2&'��
��2&'��
��2&'��
��2&'�
为帮助对大型多媒体数据库进行多维分析,就需要设计并构造多媒体数据立
方。有关方法与从关系数据库中设计构造传统数据立方类似。但与从关系数据库
中的数据立方所不同的是,多媒体数据立方可能包含有关多媒体信息的附加维和
量度,如:颜色、纹理和形状等。�
这里介绍一个多媒体数据挖掘系统原型,称为 >#���>�6��>���"。在
>#���>�6��>���" 中进行测试的多媒体数据库构造做法如下:每个图像都包含两
个描述符:即特征描述符和外观描述符。初始的图像可能不能直接存储在数据库
中;只能存储它的特征描述符。描述性信息包括:图像文件名称、图像 4,�、
图像类型(���、M!��、:&!、&!��等)、一系列引用该图像的网页(父链接)、一
系列关键字、供用户浏览图像和视频时使用的小图。每个可视特性均采用一个向
量表示所形成特征向量集合就是整个图像的特征向量。主要的向量有:(�)颜色
向量,它包括颜色直方图,定量为 ���种颜色( ��� ×× 颜色分别为 ��� ×× );
(�)>*5(最大频率颜色)向量和>*�(最频繁方位)向量。>*5和>*�包
含 �个颜色和 �个方位边(代表 �个最常用的方位,各边分别代表 �� 、 ����� 、 ��� 、
���2� 和 ��� );(
)外观设计描述包括一个颜色外观向量和一个边外观向量。无
论它们原来大小如何,这些图像均划分为 ��× 网格。这 2�个网格中>*5存放在
颜