数据挖掘技术

数据挖掘涉及的学科领域和方法很多,有多种分类法。根据挖掘任务分,可分为分类或预测模型发现、数据总结、聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等等;根据挖掘对象分,有关系数据库、面向对象数据库、空间数据库、时态数据库、文本数据源、多媒体数据库、异质数据库、遗产数据库以及环球网Web;根据挖掘方法分,可粗分为:机器学习方法、统计方法、神经网络方法和数据库方法。机器学习中,可细分为:归纳学习方法(决策树、规则归纳等)、基于范例学习、遗传算法等。统计方法中,可细分为:回归分析(多元回归、自回归等)、判别分析(贝叶斯判别、费歇尔判别、非参数判别等)、聚类分析(系统聚类、动态聚类等)、探索性分析(主元分析法、相关分析法等)等。神经网络方法中,可细分为:前向神经网络(BP算法等)、自组织神经网络(自组织特征映射、竞争学习等)等。数据库方法主要是多维数据分析或OLAP 方法,另外还有面向属性的归纳方法。
本文将主要从挖掘任务和挖掘方法的角度,着重讨论数据总结、分类发现、聚类和关联规则发现四种非常重要的发现任务。

一、数据总结

数据总结目的是对数据进行浓缩,给出它的紧凑描述。传统的也是最简单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值,或者用直方图、饼状图等图形方式表示。数据挖掘主要关心从数据泛化的角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从低层次抽象到高层次上的过程。由于数据库上的数据或对象所包含的信息总是最原始、基本的信息(这是为了不遗漏任何可能有用的数据信息 )。人们有时希望能从较高层次的视图上处理或浏览数据,因此需要对数据进行不同层次上的泛化以适应各种查询要求。数据泛化目前主要有两种技术:多维数据分析方法和面向属性的归纳方法。

多维数据分析方法是一种数据仓库技术,也称作联机分析处理(OLAP)。数据仓库是面向决策支持的、集成的、稳定的、不同时间的历史数据集合。决策的前提是数据分析。在数据分析中经常要用到诸如求和、总计、平均、最大、最小等汇集操作,这类操作的计算量特别大。因此一种很自然的想法是,把汇集操作结果预先计算并存储起来,以便于决策支持系统使用。存储汇集操作结果的地方称作多维数据库。多维数据分析技术已经在决策支持系统中获得了成功的应用,如著名的SAS数据分析软件包、Business Object公司的决策支持系统Business Object,以及IBM公司的决策分析工具都使用了多维数据分析技术。

采用多维数据分析方法进行数据总结,它针对的是数据仓库,数据仓库存储的是脱机的历史数据。为了处理联机数据,研究人员提出了一种面向属性的归纳方法。它的思路是 ,直接对用户感兴趣的数据视图(用一般的SQL查询语言即可获得)进行泛化,而不是像多维数据分析方法那样预先就存储好了泛化数据。方法的提出者对这种数据泛化技术称之为面向属性的归纳方法。原始关系经过泛化操作后得到的是一个泛化关系,它从较高的层次上总结了在低层次上的原始关系。有了泛化关系后,就可以对它进行各种深入的操作而生成满足用户需要的知识,如在泛化关系基础上生成特性规则、判别规则、分类规则,以及关联规则等。

二、分类发现

分类在数据挖掘中是一项非常重要的任务,目前在商业上应用最多。分类的目的是学会一个分类函数或分类模型(也常常称作分类器),该模型能把数据库中的数据项映射到给定类别中的某一个。分类和回归都可用于预测。预测的目的是从利用历史数据纪录中自动推导出对给定数据的推广描述,从而能对未来数据进行预测。和回归方法不同的是,分类的输出是离散的类别值,而回归的输出则是连续数值。这里我们将不讨论回归方法。

要构造分类器,需要有一个训练样本数据集作为输入。训练集由一组数据库记录或元组构成,每个元组是一个由有关字段(又称属性或特征)值组成的特征向量,此外,训练样本还有一个类别标记。一个具体样本的形式可为:( v1, v2, ..., vn; c );其中vi表示字段值,c表示类别。

分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。统计方法包括贝叶斯法和非参数法(近邻学习或基于事例的学习),对应的知识表示则为判别函数和原型事例。机器学习方法包括决策树法和规则归纳法,前者对应的表示为决策树或判别树,后者则一般为产生式规则。神经网络方法主要是BP算法,它的模型表示是前向反馈神经网络模型(由代表神经元的节点和代表联接权值的边组成的一种体系结构),BP算法本质上是一种非线性判别函数。另外,最近又兴起了一种新的方法:粗糙集(rough set),其知识表示是产生式规则。

不同的分类器有不同的特点。有三种分类器评价或比较尺度:1 预测准确度;2 计算复杂度;3 模型描述的简洁度。预测准确度是用得最多的一种比较尺度,特别是对于预测型分类任务,目前公认的方法是10番分层交叉验证法。计算复杂度依赖于具体的实现细节和硬件环境,在数据挖掘中,由于操作对象是巨量的数据库,因此空间和时间的复杂度问题将是非常重要的一个环节。对于描述型的分类任务,模型描述越简洁越受欢迎;例如,采用规则表示的分类器构造法就更有用,而神经网络方法产生的结果就难以理解。

另外要注意的是,分类的效果一般和数据的特点有关,有的数据噪声大,有的有缺值, 有的分布稀疏,有的字段或属性间相关性强,有的属性是离散的而有的是连续值或混合式的。目前普遍认为不存在某种方法能适合于各种特点的数据。

三、聚类

聚类是把一组个体按照相似性归成若干类别,即"物以类聚"。它的目的是使得属于同一类别的个体之间的距离尽可能的小,而不同类别上的个体间的距离尽可能的大。聚类方法包括统计方法、机器学习方法、神经网络方法和面向数据库的方法。


在统计方法中,聚类称聚类分析,它是多元数据分析的三大方法之一(其它两种是回归分析和判别分析)。它主要研究基于几何距离的聚类,如欧式距离、明考斯基距离等。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。这种聚类方法是一种基于全局比较的聚类,它需要考察所有的个体才能决定类的划分;因此它要求所有的数据必须预先给定,而不能动态增加新的数据对象。聚类分析方法不具有线性的计算复杂度,难以适用于数据库非常大的情况。


在机器学习中聚类称作无监督或无教师归纳;因为和分类学习相比,分类学习的例子或数据对象有类别标记,而要聚类的例子则没有标记,需要由聚类学习算法来自动确定。很多人工智能文献中,聚类也称概念聚类;因为这里的距离不再是统计方法中的几何距离 ,而是根据概念的描述来确定的。当聚类对象可以动态增加时,概念聚类则称是概念形成。

在神经网络中,有一类无监督学习方法:自组织神经网络方法;如Kohonen自组织特征映射网络、竞争学习网络等等。在数据挖掘领域里,见报道的神经网络聚类方法主要是自组织特征映射方法,IBM在其发布的数据挖掘白皮书中就特别提到了使用此方法进行数据库聚类分割。

  四、关联规则发现

关联规则是形式如下的一种规则,"在购买面包和黄油的顾客中,有90%的人同时也买了牛奶"(面包+黄油 ( 牛奶 )。用于关联规则发现的主要对象是事务型数据库,其中针对的应用则是售货数据,也称货篮数据。一个事务一般由如下几个部分组成:事务处理时间 ,一组顾客购买的物品,有时也有顾客标识号(如信用卡号)。

由于条形码技术的发展,零售部门可以利用前端收款机收集存储大量的售货数据。因此,如果对这些历史事务数据进行分析,则可对顾客的购买行为提供极有价值的信息。例如,可以帮助如何摆放货架上的商品(如把顾客经常同时买的商品放在一起),帮助如何规划市场(怎样相互搭配进货)。由此可见,从事务数据中发现关联规则,对于改进零售业等商业活动的决策非常重要。

设I={i1,i2,...,im}是一组物品集(一个商场的物品可能有上万种),D是一组事务集 (称之为事务数据库)。D中的每个事务T是一组物品,显然满足TI。称事务T支持物品集 X,如果XT。关联规则是如下形式的一种蕴含:XY,其中XI,YI,且X∩Y=I。

(1) 称物品集X具有大小为s的支持度,如果D中有s%的事务支持物品集X;

(2) 称关联规则XY在事务数据库D中具有大小为s的支持度,如果物品集X∪Y的支持度为s;

(3) 称规则XY在事务数据库D中具有大小为c的可信度,如果D中支持物品集X的事务中有c%的事务同时也支持物品集Y。

如果不考虑关联规则的支持度和可信度,那么在事务数据库中存在无穷多的关联规则。事实上,人们一般只对满足一定的支持度和可信度的关联规则感兴趣。在文献中,一般称满足一定要求的(如较大的支持度和可信度)的规则为强规则。因此,为了发现出有意义的关联规则,需要给定两个阈值:最小支持度和最小可信度。前者即用户规定的关联规则必须满足的最小支持度,它表示了一组物品集在统计意义上的需满足的最低程度;后者即用户规定的关联规则必须满足的最小可信度,它反应了关联规则的最低可靠度。

在实际情况下,一种更有用的关联规则是泛化关联规则。因为物品概念间存在一种层次关系,如夹克衫、滑雪衫属于外套类,外套、衬衣又属于衣服类。有了层次关系后,可以帮助发现一些更多的有意义的规则。例如,"买外套买鞋子"(此处,外套和鞋子是较高层次上的物品或概念,因而该规则是一种泛化的关联规则)。由于商店或超市中有成千上万种物品,平均来讲,每种物品(如滑雪衫)的支持度很低,因此有时难以发现有用规则;但如果考虑到较高层次的物品(如外套),则其支持度就较高,从而可能发现有用的规则。

另外,关联规则发现的思路还可以用于序列模式发现。用户在购买物品时,除了具有上述关联规律,还有时间上或序列上的规律,因为,很多时候顾客会这次买这些东西,下次买同上次有关的一些东西,接着又买有关的某些东西。



  2.多层次数据汇总归纳

数据库中的数据和对象经常包含原始概念层上的详细信息,将一个数据集合归纳成高概念层次信息的数据挖掘技术被称为数据汇总(Data Generalization) 。概念汇总将数据库中的相关数据由低概念层抽象到高概念层,主要有数据立方体和面向属性两种方法。

数据立方体(多维数据库)方法的主要思想是将那些经常查询、代价高昂的运算,如C ount、Sum、Average、Max、Min等汇总函数具体化,并存储在一个多维数据库中,为决策支持、知识发现及其它应用服务。

面向属性的抽取方法用一种类SQL数据采掘查询语言表达查询要求,收集相关数据,并利用属性删除、概念层次树、门槛控制、数量传播及集合函数等技术进行数据汇总。汇总数据用汇总关系表示,可以将数据转化为不同类型的知识,或将其映射成不同的表,并从中抽取特征、判别式、分类等相关规则。

面向属性抽取的概念层次树是指某属性所具有的从具体概念值到某概念类的层次关系树。概念层次可由相关领域专家根据属性的领域知识提供,按特定属性的概念层次从一般到具体排序。树的根结点是用ANY表示最一般的概念,叶结点是最具体的概念即属性的具体值,例如属性City的概念层次树如图4所示。概念层次为归纳分析提供有用信息,将概念组织为不同层次,从而在高概念层次上用简单、确切的公式表示规则。 

图4 属性City的概念层次树 

Cai Cencone利用属性值的概念层次关系,提出了面向属性的树提升算法,并得到一阶谓词逻辑表示的规则。面向属性的树提升方法主要是对目标类所有元组的属性值由低到高提升,使原来若干属性值不同的元组成为相同元组,进行合并,直到全部元组不超过最大规则数,再将其转化为一阶谓词逻辑表示的规则。


与面向元组的归纳方法相比,面向属性的归纳方法搜索空间减少,运行效率显著提高 ;对冗余元组的测试在概括属性的所有值后进行,提高了测试效率;最坏时间复杂性为O(N logP),N为元组个数,P为最终概括关系表中的元组个数。处理过程可利用关系数据库的传统操作。此方法已在数据挖掘系统DBMINE中采用,除关系数据库外,也可扩展到面向对象数据库。


3.决策树方法

利用信息论中的互信息(信息增益)寻找数据库中具有最大信息量的字段,建立决策树的一个结点,再根据字段的不同取值建立树的分支;在每个分支子集中,重复建立树的下层结点和分支的过程,即可建立决策树。国际上最有影响和最早的决策树方法是由Quiulan 研制的ID3方法,后人又发展了各种决策树方法,如IBLE方法使识别率提高了10%。


4.神经网络方法 

模拟人脑神经元方法,以MP模型和HEBB学习规则为基础,建立了三大类多种神经网络模型:前馈式网络、反馈式网络、自组织网络。


5. 覆盖正例排斥反例方法

利用覆盖所有正例排斥所有反例的思想来寻找规则,比较典型的有MICHALSKI的AQ11 方法、洪家荣改进的AQ15方法和AE5方法。


6. 粗集(Rough Set)方法 

在数据库中将行元素看成对象,将列元素看成属性(分为条件属性和决策属性)。等价关系R定义为不同对象在某个或几个属性上取值相同,满足等价关系的对象组成的集合被称为等价关系R的等价类。条件属性上的等价类E与决策属性上的等价类Y之间的关系分三种情况:


(1)下近似:Y包含E。对下近似建立确定性规则。 

(2)上近似:Y和E的交非空。对上近似建立不确定性规则(含可信度)。


(3)无关:Y和E的交为空。无关情况不存在规则。 

7. 遗传算法


模拟生物进化过程的算法,由繁殖(选择)、交叉(重组)、 变异(突变)三个基本算子组成。遗传算法已在优化计算、分类、机器学习等方面发挥了显著作用。 

8. 公式发现

在工程和科学数据库中,对若干数据项进行一定的数学运算,求得相应的数学公式。 BACON发现系统完成了对物理学的大量定律的重新发现。 

9. 统计分析方法


在数据库字段项之间存在两种关系:函数关系(能用函数公式表示的确定性关系)和相关关系(不能用函数公式表示,但仍是相关确定性关系),对它们的分析可采用回归分析、相关分析、主成分分析等方法。 

10. 模糊论方法


利用模糊集合理论,对实际问题进行模糊判断、模糊决策、模糊模式识别、模糊簇聚分析。系统的复杂性越高,精确能力就越低,模糊性就越强。这是Zadeh总结出的互克性原理。 

11. 可视化技术


拓宽了传统的图表功能,使用户对数据的剖析更清楚。 

另外还有归纳逻辑程序(Inductive Logic Programming)、Bayesian网络等方法。


四、空间数据库的数据采掘 

近年来,数据采掘研究多针对于关系数据库,但是空间数据库系统的发展为我们提供了丰富的空间数据,为数据分析和知识发现展示了广阔的前景。空间数据挖掘技术帮助人们从庞大的空间数据中抽取有用信息。由于空间数据的数量庞大及空间问题的特殊性,因此发现隐含在空间数据中的特征和模式,已成为空间数据库的一个重要问题。现已在GIS 系统、图像数据库等领域得到了广泛应用。


空间数据采掘的方法包括: 

1.归纳方法


基于归纳方法的空间数据采掘算法必须由用户预先给定或系统自动生成概念层次树 ,发现的知识依赖于层次树结构,计算复杂性为O(logN),N为空间数据个数。 

2.聚集方法


基于聚集方法的空间数据挖掘算法包括CLARANS、BIRCH、DBSCAN等算法。 

3.统计信息网格算法(STING)


该方法是一个查询无关算法,每个节点存储数据的统计信息,可处理大量的查询。算法采用增量修改,避免数据更新造成的所有单元重新计算,而且易于并行化。 

4. 空间聚集和特征邻近关系采掘


(1)发现集合邻近关系:给定一个点的聚集,找到聚集的K个最邻近特征。CRH算法寻找集合邻近关系,它是Circle、Isothetic Rectangle和Convex Hull的首字母缩写形式。C RH用筛选器逐步减少特征个数,直至找到K个最接近特征。在SPARC-10工作站上的实验结果表明,CRH作为一种近似算法,得出的结果相当精确,它能在约1秒CPU时间内从5000个特征中找到最近的25个。 

(2)发现集合邻近的共性:给定N个聚集,找到与全部或大多数聚集最接近的公共特征类,即出现在同一分类中的相似特征,例如发现所有居民区都与中学相近,而不一定是同一所中学。Gencom 算法从N个聚集的N个最近K个特征的集合中抽取集合邻近公共特征。


五、数据采掘的工具 

目前,国外有许多研究机构、公司和学术组织从事数据采掘工具的研制和开发。这些工具主要采用基于人工智能的技术,包括决策树、规则归纳、神经元网络、可视化、模糊建模、簇聚等,另外也采用了传统的统计方法。这些数据采掘工具差别很大,不仅体现在关键技术上,还体现在运行平台、数据存取、价格等方面。


数据采掘工具可根据应用领域分为三类:

  (1)通用单任务类:仅支持KDD的数据采掘步骤,并且需要大量的预处理和善后处理工作。主要采用决策树、神经网络、基于例子和规则的方法,发现任务大多属于分类范畴。


(2)通用多任务类:可执行多个领域的知识发现任务,集成了分类、可视化、聚集、概括等多种策略,如Clementine、IBM Intelligent Miner、SGI Mineset。 

(3)专用领域类:现有的许多数据采掘系统是专为特定目的开发的,用于专用领域的知识发现,对采掘的数据库有语义要求,发现的知识也较单一。如Explora用于超市销售分析 ,仅能处理特定形式的数据,知识发现也以关联规则和趋势分析为主。另外发现方法单一 ,有些系统虽然能发现多种形式的知识,但基本上以机器学习、统计分析为主,计算量大。


根据所采用的技术,采掘工具大致分为六类: 

(1)基于规则和决策树的工具:大部分数据采掘工具采用规则发现和决策树分类技术来发现数据模式和规则,其核心是某种归纳算法,如ID3和C4.5。它通常先对数据库中的数据进行采掘,生成规则和决策树,然后对新数据进行分析和预测,典型产品有Angoss Sof tware开发的Knowlege Seeker和ATTAR Software开发的XpertRule Profiler。

(2)基于神经元网络的工具:基于神经元网络的工具由于具有对非线性数据的快速建模能力,因此越来越流行。挖掘过程基本上是将数据簇聚,然后分类计算权值。它在市场数据库的分析和建模方面应用广泛,典型产品有Advanced Software 开发的PBProfile。

  (3)数据可视化方法:这类工具大大扩展了传统商业图形的能力,支持多维数据的可视化,同时提供了多方向同时进行数据分析的图形方法。

(4)模糊发现方法:应用模糊逻辑进行数据查询排序。

  (5)统计方法:这些工具没有使用人工智能技术,因此更适于分析现有信息,而不是从原始数据中发现数据模式和规则。

  (6)综合多方法:许多工具采用了多种挖掘方法,一般规模较大。

  工具系统的总体发展趋势是,使数据采掘技术进一步为用户所接受和使用,另一方面也可以理解成以使用者的语言表达知识概念。

  六、应用

  数据采掘系统已成功地用于VLDB的知识挖掘。

  QUEST 是Agrawal 为IBM开发的数据挖掘系统,用于发现VLDB中的关联规则、序列模式、分类规则、模式匹配分析等;DBMINE是Han et al.开发的关系数据挖掘系统,它能用于多抽象层的多类规则挖掘,包括特征规则、关联规则、分类规则等。南京大学开发的K night系统是一个通用的数据挖掘系统,对涉及的数据无既定的领域要求,可以用来处理不同领域的采掘任务。另外,Knight系统在数据采掘算法中引入遗传算法和信息论思想,提高了知识发现的效率和质量。

  在市场金融方面,Integral Solution为BBC开发的采用神经网络和归纳规则方法预测收视率的发现系统;零售业数据采掘主要应用于销售预测、库存需求、零售点选择和价格分析,例如用自然语言和商用图表分析超市销售数据的Spotlight系统,及扩展到其它市场领域的Opportunity Explorer系统;在医疗保健方面,由GTE开发的KEFIR数据采掘系统用于分析健康数据,确定偏差,并通过Web浏览器以超文本形式输出结果;在科学研究方面,S KICAT系统能对宇宙图像数据进行分类,Quakfinder利用卫星采集的数据监测地壳活动,H MMs和SAM用于发现和构造生物模型;在司法方面,可用数据采掘技术进行案件调查、zhapian监测、洗钱认证、犯罪组织分析,如美国财政部开发的FAIS系统;在制造业上,可利用数据采掘技术进行零部件的故障诊断、资源优化、生产过程分析等。

  在统计和机器学习领域中还有许多数据采掘系统。另外将数据仓库、OLTP、OLAP和数据采掘技术结合是近期数据库发展的一个趋势。数据仓库和数据采掘都可以完成对决策技术的支持,相互间有一定的内在联系,两者集成,可以有效地提高系统的决策支持能力。例如瑞典保险系统由OLTP系统、数据仓库、数据挖掘环境三部分构成。它建立在Orac le数据库基础上的MASY数据仓库从多个OLTP信息源收集相关数据。由多种数据挖掘工具 (Expla、RDT、C45等)构成的数据挖掘环境提供动态数据分析,使用户尽可能不依赖数据采掘专家执行多种类型的数据采掘任务。

  数据采掘在数据库之外的其它领域也有丰硕的成果,例如统计学中已发展了许多用于数据采掘的技术,演绎逻辑编程作为逻辑编程的一个迅速发展的分支,与数据采掘有密切联系。