数据挖掘技术概述

文章摘要:
数据挖掘(Data Mining)就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。数据挖掘研究现状，数据挖掘的挖掘任务和挖掘方法在本文中简略说明。
关键词　数据挖掘，数据库，抽取，分类发现，聚类，关联规则
数据挖掘技术概述
一. 数据挖掘技术概述
近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，千万万个数据库被用于商业管理、政府办公、科学研究和工程开发等等，并且这一势头仍将持续发展下去。于是，一个新的挑战被提了出来:在这被称之为信息爆炸的时代，信息过量几乎成为人人需要面对的问题。如何才能不被信息的汪洋大海所淹没，从中及时发现有用的知识，提高信息利用率呢?要想使数据真正成为一个公司的资源，只有充分利用它为公司自身的业务决策和战略发展服务才行，否则大量的数据可能成为包袱，甚至成为垃圾。因此，面对"人们被数据淹没，人们却饥饿于知?quot;的挑战，数据挖掘和知识发现(DMKD)技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。
数据挖掘(Data Mining)就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。还有很多和这一术语相近似的术语，如从数据库中发现知识(KDD)、数据分析、数据融合(Data Fusion)以及决策支持等。人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。原始数据可以是结构化的，如关系数据库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的;可以是演绎的，也可以是归纳的。发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门很广义的交叉学科，它汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并行计算等方面的学者和工程技术人员。
特别要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据库的简单检索查询调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、综合和推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已有的数据对未来的活动进行预测。例如加拿大BC省电话公司要求加拿大SimonFraser大学KDD研究组，根据其拥有十多年的客户数据，总结、分析并提出新的电话收费和管理办法，制定既有利于公司又有利于客户的优惠政策。这样一来，就把人们对数据的应用，从低层次的末端查询操作，提高到为各级经营决策者提供决策支持。这种需求驱动力，比数据库查询更为强大。同时需要指出的是，这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。所有发现的知识都是相对的，是有特定前提和约束条件、面向特定领域的，同时还要能够易于被用户理解，最好能用自然语言表达发现结果。因此DMKD的研究成果是很讲求实际的。
二、数据挖掘研究现状
KDD一词首次出现在1989年8月举行的第11届国际联合人工智能学术会议上。迄今为止，由美国人工智能协会主办的KDD国际研讨会已经召开了7次，规模由原来的专题讨论会发展到国际学术大会，人数由二三十人到七八百人，论文收录比例从2X1到6X1，研究重点也逐渐从发现方法转向系统应用，并且注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。其他内容的专题会议也把数据挖掘和知识发现列为议题之一，成为当前计算机科学界的一大热点。
此外，数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也纷纷开辟了KDD专题或专刊。IEEE的KnowledgeandDataEngineering会刊领先在1993年出版了KDD技术专刊，所发表的5篇论文代表了当时KDD研究的最新成果和动态，较全面地论述了KDD系统方法论、发现结果的评价、KDD系统设计的逻辑方法，集中讨论了鉴于数据库的动态性冗余、高噪声筒蝗范ㄐ浴⒖罩档任侍猓琄DD系统与其它传统的机器学习、专家系统、人工神经网络、数理统计分析系统的联系和区别，以及相应的基本对策。6篇论文摘要展示了KDD在从建立分子模型到设计制造业的具体应用。
不仅如此，在Internet上还有不少KDD电子出版物，其中以半月刊KnowledgeDiscoveryNuggets最为权威，如要免费订阅，只需向http://www.kdnuggets.com/subscribe.html发送一份电子邮件即可，还可以下载各种各样的数据挖掘工具软件和典型的样本数据仓库，供人们测试和评价。另一份在线周刊为DS*(DS代表决策支持)，1997年10月7日开始出版，可向dstrial@tgc.com提出免费订阅申请。在网上，还有一个自由论坛DMEmailClub，人们通过电子邮件相互讨论DMKD的热点问题。而领导整个潮流的DMKD开发和研究中心，当数设在美国EMDEN的IBM公司开发部。
随着DMKD研究逐步走向深入，人们越来越清楚地认识到，DMKD的研究主要有3个技术支柱，即数据库、人工智能和数理统计。
数据库技术在经过了80年代的辉煌之后，已经在各行各业成为一种数据库文化或时尚，数据库界目前除了关注万维网数据库、分布式数据库、面向对象数据库、多媒体数据库、查询优化和并行计算等技术外，已经在开始反思。数据库最实质的应用仅仅是查询吗?理论根基最深的关系数据库最本质的技术进步点，就是数据存放和数据使用之间的相互分离。查询是数据库的奴隶，发现才是数据库的主人;数据只为职员服务，不为老板服务!这是很多单位的领导在热心数据库建设后发出的感叹。
由于数据库文化的迅速普及，用数据库作为知识源具有坚实的基础;另一方面，对于一个感兴趣的特定领域--客观世界，先用数据库技术将其形式化并组织起来，就会大大提高知识获取起点，以后从中发掘或发现的所有知识都是针对该数据库而言的。因此，在需求的驱动下，很多数据库学者转向对数据仓库和数据挖掘的研究，从对演绎数据库的研究转向对归纳数据库的研究。
专家系统曾经是人工智能研究工作者的骄傲。专家系统实质上是一个问题求解系统，目前的主要理论工具是基于谓词演算的机器定理证明技术--二阶演绎系统。领域专家长期以来面向一个特定领域的经验世界，通过人脑的思维活动积累了大量有用信息。
在研制一个专家系统时，知识工程师首先要从领域专家那里获取知识，这一过程实质上是归纳过程，是非常复杂的个人到个人之间的交互过程，有很强的个性和随机性。因此，知识获取成为专家系统研究中公认的瓶颈问题。
其次，知识工程师在整理表达从领域专家那里获得的知识时，用if-then等类的规则表达，约束性太大，用常规数理逻辑来表达社会现象和人的思维活动局限性太大，也太困难，勉强抽象出来的规则有很强的工艺色彩，差异性极大，知识表示又成为一大难题。 此外，即使某个领域的知识通过一定手段获取并表达了，但这样做成的专家系统对常识和百科知识出奇地贫乏，而人类专家的知识是以拥有大量常识为基础的。人工智能学家Feigenbaum估计，一般人拥有的常识存入计算机大约有100万条事实和抽象经验法则，离开常识的专家系统有时会比傻子还傻。例如战场指挥员会根据"在某地发现一只刚死的波斯猫"的情报很快断定敌高级指挥所的位置，而再好的军事专家系统也难以顾全到如此的信息。
以上这3大难题大大限制了专家系统的应用，使得专家系统目前还停留在构造诸如发动机故障论断一类的水平上。人工智能学者开始着手基于案例的推理，尤其是从事机器学习的科学家们，不再满足自己构造的小样本学习模式的象牙塔，开始正视现实生活中大量的、不完全的、有噪声的、模糊的、随机的大数据样本，也走上了数据挖掘的道路。 数理统计是应用数学中最重要、最活跃的学科之一，它在计算机发明之前就诞生了，迄今已有几百年的发展历史。如今相当强大有效的数理统计方法和工具，已成为信息咨询业的基础。信息时代，咨询业更为发达。然而，数理统计和数据库技术结合得并不算快，数据库查询语言SQL中的聚合函数功能极其简单，就是一个证明。咨询业用数据库查询数据还远远不够。一旦人们有了从数据查询到知识发现、从数据演绎到数据归纳的要求，概率论和数理统计就获得了新的生命力，所以才会在DMKD这个结合点上，立即呈现出"忽如一夜春风来，千树万树梨花开"的繁荣景象。
三. 数据挖掘的挖掘任务和挖掘方法
数据挖掘所能发现的知识有如下几种:广义型知识，反映同类事物共同性质的知识;特征型知识，反映事物各方面的特征知识;差异型知识，反映不同事物之间属性差别的知识;关联型知识，反映事物之间依赖或关联的知识;预测型知识，根据历史的和当前的数据推测未来数据;偏离型知识，揭示事物偏离常规的异常现象。所有这些知识都可以在不同的概念层次上被发现，随着概念树的提升，从微观到中观再到宏观，以满足不同用户、不同层次决策的需要。例如，从一家超市的数据仓库中，可以发现的一条典型关联规则可能是"买面包和黄油的顾客十有八九也买牛奶"，也可能是"买食品的顾客几乎都用信用卡"，这种规则对于商家开发和实施客户化的销售计划和策略是非常有用的。至于发现工具和方法，常用的有分类、聚类、减维、模式识别、可视化、决策树、遗传算法、不确定性处理等。
数据挖掘涉及的学科领域和方法很多，有多种分类法。根据挖掘任务分，可分为分类或预测模型发现、数据总结、聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等等;根据挖掘对象分，有关系数据库、面向对象数据库、空间数据库、时态数据库、文本数据源、多媒体数据库、异质数据库、遗产数据库以及环球网Web;根据挖掘方法分，可粗分为:机器学习方法、统计方法、神经网络方法和数据库方法。机器学习中，可细分为:归纳学习方法(决策树、规则归纳等)、基于范例学习、遗传算法等。统计方法中，可细分为:回归分析(多元回归、自回归等)、判别分析(贝叶斯判别、费歇尔判别、非参数判别等)、聚类分析(系统聚类、动态聚类等)、探索性分析(主元分析法、相关分析法等)等。神经网络方法中，可细分为:前向神经网络(BP算法等)、自组织神经网络(自组织特征映射、竞争学习等)等。数据库方法主要是多维数据分析或OLAP方法，另外还有面向属性的归纳方法。
以下将主要从挖掘任务和挖掘方法的角度，着重讨论数据抽取、分类发现、聚类和关联规则发现四种非常重要的发现任务。
1、数据抽取
数据抽取目的是对数据进行浓缩，给出它的紧凑描述。传统的也是最简单的数据抽取方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值，或者用直方图、饼状图等图形方式表示。数据挖掘主要关心从数据泛化的角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从低层次抽象到高层次上的过程。由于数据库上的数据或对象所包含的信息总是最原始、基本的信息(这是为了不遗漏任何可能有用的数据信息)。人们有时希望能从较高层次的视图上处理或浏览数据，因此需要对数据进行不同层次上的泛化以适应各种查询要求。数据泛化目前主要有两种技术:多维数据分析方法和面向属性的归纳方法。
多维数据分析方法是一种数据仓库技术，也称作联机分析处理(OLAP)。数据仓库是面向决策支持的、集成的、稳定的、不同时间的历史数据集合。决策的前提是数据分析。在数据分析中经常要用到诸如求和、总计、平均、最大、最小等汇集操作，这类操作的计算量特别大。因此一种很自然的想法是，把汇集操作结果预先计算并存储起来，以便于决策支持系统使用。存储汇集操作结果的地方称作多维数据库。
采用多维数据分析方法进行数据抽取，它针对的是数据仓库，数据仓库存储的是脱机的历史数据。为了处理联机数据，研究人员提出了一种面向属性的归纳方法。它的思路是，直接对用户感兴趣的数据视图(用一般的SQL查询语言即可获得)进行泛化，而不是像多维数据分析方法那样预先就存储好了泛化数据。方法的提出者对这种数据泛化技术称之为面向属性的归纳方法。原始关系经过泛化操作后得到的是一个泛化关系，它从较高的层次上总结了在低层次上的原始关系。有了泛化关系后，就可以对它进行各种深入的操作而生成满足用户需要的知识，如在泛化关系基础上生成特性规则、判别规则、分类规则，以及关联规则等。
2、分类发现
分类在数据挖掘中是一项非常重要的任务，目前在商业上应用最多。分类的目的是学会一个分类函数或分类模型(也常常称作分类器)，该模型能把数据库中的数据项映射到给定类别中的某一个。分类和回归都可用于预测。预测的目的是从利用历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行预测。和回归方法不同的是，分类的输出是离散的类别值，而回归的输出则是连续数值。这里我们将不讨论回归方法。
要构造分类器，需要有一个训练样本数据集作为输入。训练集由一组数据库记录或元组构成，每个元组是一个由有关字段(又称属性或特征)值组成的特征向量，此外，训练样本还有一个类别标记。一个具体样本的形式可为:(v1，v2，...，vn;c);其中vi表示字段值，c表示类别。
分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。统计方法包括贝叶斯法和非参数法(近邻学习或基于事例的学习)，对应的知识表示则为判别函数和原型事例。机器学习方法包括决策树法和规则归纳法，前者对应的表示为决策树或判别树，后者则一般为产生式规则。神经网络方法主要是BP算法，它的模型表示是前向反馈神经网络模型(由代表神经元的节点和代表联接权值的边组成的一种体系结构)，BP算法本质上是一种非线性判别函数。另外，最近又兴起了一种新的方法:粗糙集(roughset)，其知识表示是产生式规则。
不同的分类器有不同的特点。有三种分类器评价或比较尺度:1预测准确度;2计算复杂度;3模型描述的简洁度。预测准确度是用得最多的一种比较尺度，特别是对于预测型分类任务，目前公认的方法是10番分层交叉验证法。计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是巨量的数据库，因此空间和时间的复杂度问题将是非常重要的一个环节。对于描述型的分类任务，模型描述越简洁越受欢迎;例如，采用规则表示的分类器构造法就更有用，而神经网络方法产生的结果就难以理解。
另外要注意的是，分类的效果一般和数据的特点有关，有的数据噪声大，有的有缺值，有的分布稀疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续值或混合式的。目前普遍认为不存在某种方法能适合于各种特点的数据。
3、聚类
聚类是把一组个体按照相似性归成若干类别，即"物以类聚"。它的目的是使得属于同一类别的个体之间的距离尽可能的小，而不同类别上的个体间的距离尽可能的大。聚类方法包括统计方法、机器学习方法、神经网络方法和面向数据库的方法。
在统计方法中，聚类称聚类分析，它是多元数据分析的三大方法之一(其它两种是回归分析和判别分析)。它主要研究基于几何距离的聚类，如欧式距离、明考斯基距离等。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。这种聚类方法是一种基于全局比较的聚类，它需要考察所有的个体才能决定类的划分;因此它要求所有的数据必须预先给定，而不能动态增加新的数据对象。聚类分析方法不具有线性的计算复杂度，难以适用于数据库非常大的情况。
在机器学习中聚类称作无监督或无教师归纳;因为和分类学习相比，分类学习的例子或数据对象有类别标记，而要聚类的例子则没有标记，需要由聚类学习算法来自动确定。很多人工智能文献中，聚类也称概念聚类;因为这里的距离不再是统计方法中的几何距离，而是根据概念的描述来确定的。当聚类对象可以动态增加时，概念聚类则称是概念形成。
在神经网络中，有一类无监督学习方法:自组织神经网络方法;如Kohonen自组织特征映射网络、竞争学习网络等等。在数据挖掘领域里，见报道的神经网络聚类方法主要是自组织特征映射方法，IBM在其发布的数据挖掘白皮书中就特别提到了使用此方法进行数据库聚类分割。
4、关联规则发现
关联规则是形式如下的一种规则，"在购买面包和黄油的顾客中，有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。
如果不考虑关联规则的支持度和可信度，那么在事务数据库中存在无穷多的关联规则。事实上，人们一般只对满足一定的支持度和可信度的关联规则感兴趣。在文献中，一般称满足一定要求的(如较大的支持度和可信度)的规则为强规则。因此，为了发现出有意义的关联规则，需要给定两个阈值:最小支持度和最小可信度。前者即用户规定的关联规则必须满足的最小支持度，它表示了一组物品集在统计意义上的需满足的最低程度;后者即用户规定的关联规则必须满足的最小可信度，它反应了关联规则的最低可靠度。
在实际情况下，一种更有用的关联规则是泛化关联规则。因为物品概念间存在一种层次关系，如夹克衫、滑雪衫属于外套类，外套、衬衣又属于衣服类。有了层次关系后，可以帮助发现一些更多的有意义的规则。例如?quot;买外套买鞋子"(此处，外套和鞋子是较高层次上的物品或概念，因而该规则是一种泛化的关联规则)。由于商店或超市中有成千上万种物品，平均来讲，每种物品(如滑雪衫)的支持度很低，因此有时难以发现有用规则;但如果考虑到较高层次的物品(如外套)，则其支持度就较高，从而可能发现有用的规则。
另外，关联规则发现的思路还可以用于序列模式发现。用户在购买物品时，除了具有上述关联规律，还有时间上或序列上的规律，因为，很多时候顾客会这次买这些东西，下次买同上次有关的一些东西，接着又买有关的某些东西。
四.数据挖掘工具的评价标准
如何选择满足自己需要的数据挖掘工具呢？评价一个数据挖掘工具，需要从以下几个方面来考虑：
1产生的模式种类的多少
2．解决复杂问题的能力
数据量的增大，对模式精细度、准确度要求的增高都会导致问题复杂性的增大。数据挖掘系统可以提供下列方法解决复杂问题：
多种模式多种类别模式的结合使用有助于发现有用的模式，降低问题复杂性。例如，首先用聚类的方法把数据分组，然后再在各个组上挖掘预测性的模式，将会比单纯在整个数据集上进行操作更有效、准确度更高。
多种算法很多模式，特别是与分类有关的模式，可以有不同的算法来实现，各有各的优缺点，适用于不同的需求和环境。数据挖掘系统提供多种途径产生同种模式，将更有能力解决复杂问题。 验证方法在评估模式时，有多种可能的验证方法。比较成熟的方法像N层交叉验证或Bootstrapping等可以控制，以达到最大的准确度。
数据选择和转换模式通常被大量的数据项隐藏。有些数据是冗余的，有些数据是完全无关的。而这些数据项的存在会影响到有价值的模式的发现。数据挖掘系统的一个很重要功能就是能够处理数据复杂性，提供工具，选择正确的数据项和转换数据值。
可视化可视化工具提供直观、简洁的机制表示大量的信息。这有助于定位重要的数据，评价模式的质量，从而减少建模的复杂性。 扩展性为了更有效地提高处理大量数据的效率，数据挖掘系统的扩展性十分重要。需要了解的是：数据挖掘系统能否充分利用硬件资源？是否支持并行计算？算法本身设计为并行的或利用了DBMS的并行性能？支持哪种并行计算机，SMP服务器还是MPP服务器？当处理器的数量增加时，计算规模是否相应增长？是否支持数据并行存储？
为单处理器的计算机编写的数据挖掘算法不会在并行计算机上自动以更快的速度运行。为充分发挥并行计算的优点，需要编写支持并行计算的算法。
3．易操作性
易操作性是一个重要的因素。有的工具有图形化界面，引导用户半自动化地执行任务，有的使用脚本语言。有些工具还提供数据挖掘的API，可以嵌入到像C、VisualBasic、PowerBuilder这样的编程语言中。
模式可以运用到已存在或新增加的数据上。有的工具有图形化的界面，有的允许通过使用C这样的程序语言或SQL中的规则集，把模式导出到程序或数据库中。
4．数据存取能力
好的数据挖掘工具可以使用SQL语句直接从DBMS中读取数据。这样可以简化数据准备工作，并且可以充分利用数据库的优点（比如平行读取）。没有一种工具可以支持大量的DBMS，但可以通过通用的接口连接大多数流行的DBMS。Microsoft的ODBC就是一个这样的接口。
5．与其他产品的接口
有很多别的工具可以帮助用户理解数据，理解结果。这些工具可以是传统的查询工具、可视化工具、OLAP工具。数据挖掘工具是否能提供与这些工具集成的简易途径？
因为数据挖掘工具需要考虑的因素很多，很难按照原则给工具排一个优劣次序。最重要的还是用户的需要，根据特定的需求加以选择。数据挖掘工具可以给很多产业带来收益。国外的许多行业如通信、信用卡公司、银行和股票交易所、保险公司、广告公司、商店等已经大量利用数据挖掘工具来协助其业务活动，国内在这方面的应用还处于起步阶段，对数据挖掘技术和工具的研究人员以及开发商来说，我国是一个有巨大潜力的市场。