数据挖掘概念综述

数据挖掘又称从数据库中发现知识（KDD）、数据分析、数据融合（Data Fusion）以及决策支持。KDD一词首次出现在1989年8月举行的第11届国际联合人工智能学术会议上。随后在1991年、1993年和1994年都举行KDD 专题讨论会，汇集来自各个领域的研究人员和应用开发者，集中讨论数据统计、海量数据分析算 法、知识表示、知识运用等问题。随着参与人员的不断增多，KDD国际会议发展成为年会。1998 年在美国纽约举行的第四届知识发现与数据 挖掘国际学术会议不仅进行了学术讨论，并且有30多家软件公司展示了他们的数据挖掘软件产品，不少软件已在北美、欧洲等国得到应用。

   一、什么是数据挖掘
   1.1、数据挖掘的历史
    近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，千万万个数据库被用于商业管理、政府办公、科学研究和工程开发等等，这一势头仍将持续发展下去。于是，一个新的挑战被提了出来：在这被称之为信息爆炸的时代，信息过量几乎成为人人需要面对的问题。如何才能不被信息的汪洋大海所淹没，从中及时发现有用的知识，提高信息利用率呢？要想使数据真正成为一个公司的资源，只有充分利用它为公司自身的业务决策和战略发展服务才行，否则大量的数据可能成为包袱，甚至成为垃圾。因此，面对”人们被数据淹没，人们却饥饿于知识”的挑战。另一方面计算机技术的另一领域——人工智能自1956年诞生之后取得了重大进展。经历了博弈时期、自然语言理解、知识工程等阶段，目前的研究 热点是机器学习。机器学习是用计算机模拟人类学习的一门科学，比较成熟的算法有神经网络、遗传算法等。用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后的知识，这两者的结合促成了数据库中的知识发现（KDD：Knowledge Discovery in Databases）的产生，因此，数据挖掘和知识发现（DMKD）技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。
   数据挖掘又称从数据库中发现知识（KDD）、数据分析、数据融合（Data Fusion）以及决策支持。KDD一词首次出现在1989年8月举行的第11届国际联合人工智能学术会议上。随后在1991年、1993年和1994年都举行KDD 专题讨论会，汇集来自各个领域的研究人员和应用开发者，集中讨论数据统计、海量数据分析算 法、知识表示、知识运用等问题。随着参与人员的不断增多，KDD国际会议发展成为年会。1998 年在美国纽约举行的第四届知识发现与数据 挖掘国际学术会议不仅进行了学术讨论，并且有30多家软件公司展示了他们的数据挖掘软件产品，不少软件已在北美、欧洲等国得到应用。
   2.2数据挖掘的概念
    从1989年到现在，KDD的定义随着人们研究的不断深入也在不断完善，目前比较公认的定义是Fayyad 等给出的：KDD是从数据集中识别出有效的、新颖的、潜在有用的以及最终可理解模式的高级处理过程。从定义可以看出，数据挖掘（Data Mining）就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。原始数据可以是结构化的，如关系数据库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门很广义的交叉学科，它汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并行计算等方面的学者和工程技术人员。
    特别要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据库的简单检索查询调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、综合和推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已有的数据对未来的活动进行预测。
    一般来说在科研领域中称为KDD，而在工程领域则称为数据挖掘。
    二、数据挖掘的步骤
    KDD包括以下步骤：
   1、数据准备
    KDD的处理对象是大量的数据，这些数据一般存储在数据库系统中，是长期积累的结果。但往往不适合直接在这些数据上面进行知识挖 掘，需要做数据准备工作，一般包括数据的选择（选择相关的数据）、净化（消除噪音、冗余数据）、推测（推算缺失数据）、转换（离散值 数据与连续值数据之间的相互转换，数据值的分组分类，数据项之间的计算组合等）、数据缩减（减少数据量）。如果KDD的对象是数据仓 库，那么这些工作往往在生成数据仓库时已经准备妥当。数据准备是KDD 的第一个步骤，也是比较重要的一个步骤。数据准备是否做好将影 响到数据挖掘的效率和准确度以及最终模式的有效性。
   2、数据挖掘
   数据挖掘是KDD最关键的步骤，也是技术难点所在。研究KDD的人员中大部分都在研究数据挖掘技术，采用较多的技术有决策树、分类、 聚类、粗糙集、关联规则、神经网络、遗传算法等。数据挖掘根据KDD的目标，选取相应算法的参数，分析数据，得到可能形成知识的模式 模型。
    3、评估、解释模式模型
    上面得到的模式模型，有可能是没有实际意义或没有实用价值的，也有可能是其不能准确反映数据的真实意义，甚至在某些情况下是与事 实相反的，因此需要评估，确定哪些是有效的、有用的模式。评估可以根据用户多年的经验，有些模式也可以直接用数据来检验其准确性。 这个步骤还包括把模式以易于理解的方式呈现给用户。
   4、巩固知识
    用户理解的、并被认为是符合实际和有价值的模式模型形成了知识。同时还要注意对知识做一
    致性检查，解决与以前得到的知识互相冲 突、矛盾的地方，使知识得到巩固。
   5、运用知识
    发现知识是为了运用，如何使知识能被运用也是KDD的步骤之一。运用知识有两种方法：一种是只需看知识本身所描述的关系或结果，就 可以对决策提供支持；另一种是要求对新的数据运用知识，由此可能产生新的问题，而需要对知识做进一步的优化
   三、数据挖掘的特点及功能
   3.1、数据挖掘的特点
   数据挖掘具有如下几个特点，当然，这些特点与数据挖掘要处理的数据和目的是密切相关的。
    1、处理的数据规模十分巨大。
    2、查询一般是决策制定者（用户）提出的即时随机查询，往往不能形成精确的查询要求。
    3、由于数据变化迅速并可能很快过时，因此需要对动态数据作出快速反应，以提供决策支持。
    4、主要基于大样本的统计规律，其发现的规则不一定适用于所有数据
    3.2、数据挖掘的功能
   数据挖掘所能发现的知识有如下几种：
    广义型知识，反映同类事物共同性质的知识；
    特征型知识，反映事物各方面的特征知识；
    差异型知识，反映不同事物之间属性差别的知识 ;关联型知识，反映事物之间依赖或关联的知识；
    预测型知识，根据历史的和当前的数据推测未来数据；偏离型知识，揭示事物偏离常规的异常现象。
    所有这些知识都可以在不同的概念层次上被发现，随着概念树的提升，从微观到中观再到宏观，以满足不同用户、不同层次决策的需要。例如，从一家超市的数据仓库中，可以发现的一条典型关联规则可能是”买面包和黄油的顾客十有八九也买牛奶”，也可能是”买食品的顾客几乎都用信用卡”，这种规则对于商家开发和实施客户化的销售计划和策略是非常有用的。至于发现工具和方法，常用的有分类、聚类、减维、模式识别、可视化、决策树、遗传算法、不确定性处理等。归纳起来，数据挖掘有如下几个功能：
    预测/验证功能：预测/验证功能指用数据库的若干已知字段预测或验证其他未知字段值。预测方法有统计分析方法、关联规则和决策树预测方法、回归树预测方法等。
    描述功能：描述功能指找到描述数据的可理解模式。描述方法包括以下几种：数据分类、回归分析、簇聚、概括、构造依赖模式、变化和偏差分析、模式发现、路径发现等。
   四、数据挖掘的模式
   数据挖掘的任务是从数据中发现模式。模式是一个用语言L来表示的一个表达式E，它可用来描述数据集F中数据的特性，E 所描述的数据是集 合F的一个子集FE。E作为一个模式要求它比列举数据子集FE中所有元素的描述方法简单。例如，“如果成绩在81 ～90之间，则成绩优良”可称 为一个模式，而“如果成绩为81、82、83、84、85、86、87、88、89 或90，则成绩优良”就不能称之为一个模式。
    模式有很多种，按功能可分有两大类：预测型（Predictive）模式和描述型（Descriptive）模式。
    预测型模式是可以根据数据项的值精确确定某种结果的模式。挖掘预测型模式所使用的数据也都是可以明确知道结果的。例如，根据各种 动物的资料，可以建立这样的模式：凡是胎生的动物都是哺乳类动物。当有新的动物资料时，就可以根据这个模式判别此动物是否是哺乳动物。
    描述型模式是对数据中存在的规则做一种描述，或者根据数据的相似性把数据分组。描述型模式不能直接用于预测。例如，在地球上，70 ％的表面被水覆盖，30 ％是土地。
    在实际应用中，往往根据模式的实际作用细分为以下6 种：
   1、分类模式
    分类模式是一个分类函数（ 分 类 器），能够把数据集中的数据项映射到某个给定的类上。分类模式往往表现为一棵分类树，根据数据的 值从树根开始搜索，沿着数据满足的分支往上走，走到树叶就能确定类别。
   2、回归模式
    回归模式的函数定义与分类模式相似，它们的差别在于分类模式的预测值是离散的，回归模式的预测值是连续的。如给出某种动物的特征，可以用分类模式判定这种动物是哺乳动物还是鸟类；给出某个人的教育情况、工作经验，可以用回归模式判定这个人的年工资在哪个范围内，是在6000元以下，还是在6000元到1万元之间，还是在1万元以上。
   3、时间序列模式
    时间序列模式根据数据随时间变化的趋势预测将来的值。这里要考虑到时间的特殊性质，像一些周期性的时间定义如星期、月、季节、年 等，不同的日子如节假日可能造成的影响，日期本身的计算方法，还有一些需要特殊考虑的地方如时间前后的相关性（过去的事情对将来有 多大的影响力）等。只有充分考虑时间因素，利用现有数据随时间变化的一系列的值，才能更好地预测将来的值。
   4、聚类模式
    聚类模式把数据划分到不同的组中，组之间的差别尽可能大，组内的差别尽可能小。与分类模式不同，进行聚类前并不知道将要划分成几 个组和什么样的组，也不知道根据哪一（几）个数据项来定义组。一般来说，业务知识丰富的人应该可以理解这些组的含义，如果产生的模式无法理解或不可用，则该模式可能是无意义的，需要回到上阶段重新组织数据。
   5、关联模式
    关联模式是数据项之间的关联规则。关联规则是如下形式的一种规则：“在无力偿还贷款的人当中，60％的人的月收入在3000元以下。”
   6、序列模式
    序列模式与关联模式相仿，而把数据之间的关联性与时间联系起来。为了发现序列模式，不仅需要知道事件是否发生，而且需要确定事件 发生的时间。例如，在购买彩电的人们当中，60％的人会在3个月内购买影碟机
   五、数据挖掘的发现任务
   数据挖掘涉及的学科领域和方法很多，有多种分类法。根据挖掘任务分，可分为分类或预测模型发现、数据总结、聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等等；根据挖掘对象分，有关系数据库、面向对象数据库、空间数据库、时态数据库、文本数据源、多媒体数据库、异质数据库、遗产数据库以及环球网Web;根据挖掘方法分，可粗分为：机器学习方法、统计方法、神经网络方法和数据库方法。机器学习中，可细分为：归纳学习方法（决策树、规则归纳等）、基于范例学习、遗传算法等。统计方法中，可细分为：回归分析（多元回归、自回归等）、判别分析（贝叶斯判别、费歇尔判别、非参数判别等）、聚类分析（系统聚类、动态聚类等）、探索性分析（主元分析法、相关分析法等）等。神经网络方法中，可细分为：前向神经网络（BP算法等）、自组织神经网络（自组织特征映射、竞争学习等）等。数据库方法主要是多维数据分析或OLAP 方法，另外还有面向属性的归纳方法。
    从挖掘任务和挖掘方法的角度而言有数据总结、分类发现、聚类和关联规则发现四种非常重要的发现任务。
   5.1、数据总结
    数据总结目的是对数据进行浓缩，给出它的紧凑描述。传统的也是最简单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值，或者用直方图、饼状图等图形方式表示。数据挖掘主要关心从数据泛化的角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从低层次抽象到高层次上的过程。由于数据库上的数据或对象所包含的信息总是最原始、基本的信息（这是为了不遗漏任何可能有用的数据信息）。人们有时希望能从较高层次的视图上处理或浏览数据，因此需要对数据进行不同层次上的泛化以适应各种查询要求。数据泛化目前主要有两种技术：多维数据分析方法和面向属性的归纳方法。
    1、多维数据分析方法是一种数据仓库技术，也称作联机分析处理（OLAP）。数据仓库是面向决策支持的、集成的、稳定的、不同时间的历史数据集合。决策的前提是数据分析。在数据分析中经常要用到诸如求和、总计、平均、最大、最小等汇集操作，这类操作的计算量特别大。因此一种很自然的想法是，把汇集操作结果预先计算并存储起来，以便于决策支持系统使用。存储汇集操作结果的地方称作多维数据库。多维数据分析技术已经在决策支持系统中获得了成功的应用，如着名的SAS数据分析软件包、Business Object公司的决策支持系统Business Object,以及IBM公司的决策分析工具都使用了多维数据分析技术。
    采用多维数据分析方法进行数据总结，它针对的是数据仓库，数据仓库存储的是脱机的历史数据。
    2、为了处理联机数据，研究人员提出了一种面向属性的归纳方法。它的思路是直接对用户感兴趣的数据视图（用一般的SQL查询语言即可获得）进行泛化，而不是像多维数据分析方法那样预先就存储好了泛化数据。方法的提出者对这种数据泛化技术称之为面向属性的归纳方法。原始关系经过泛化操作后得到的是一个泛化关系，它从较高的层次上总结了在低层次上的原始关系。有了泛化关系后，就可以对它进行各种深入的操作而生成满足用户需要的知识，如在泛化关系基础上生成特性规则、判别规则、分类规则，以及关联规则等。
   5.2、分类发现
    分类在数据挖掘中是一项非常重要的任务，目前在商业上应用最多。分类的目的是学会一个分类函数或分类模型（也常常称作分类器），该模型能把数据库中的数据项映射到给定类别中的某一个。分类和回归都可用于预测。预测的目的是从利用历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行预测。和回归方法不同的是，分类的输出是离散的类别值，而回归的输出则是连续数值。
    要构造分类器，需要有一个训练样本数据集作为输入。训练集由一组数据库记录或元组构成，每个元组是一个由有关字段（又称属性或特征）值组成的特征向量，此外，训练样本还有一个类别标记。一个具体样本的形式可为：（ v1, v2, …， vn; c ）；其中vi表示字段值，c表示类别。
    分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。统计方法包括贝叶斯法和非参数法（近邻学习或基于事例的学习），对应的知识表示则为判别函数和原型事例。机器学习方法包括决策树法和规则归纳法，前者对应的表示为决策树或判别树，后者则一般为产生式规则。神经网络方法主要是BP算法，它的模型表示是前向反馈神经网络模型（由代表神经元的节点和代表联接权值的边组成的一种体系结构），BP算法本质上是一种非线性判别函数。另外，最近又兴起了一种新的方法：粗糙集（rough set），其知识表示是产生式规则。
    不同的分类器有不同的特点。有三种分类器评价或比较尺度：1 预测准确度；2 计算复杂度；3 模型描述的简洁度。预测准确度是用得最多的一种比较尺度，特别是对于预测型分类任务，目前公认的方法是10番分层交叉验证法。计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是巨量的数据库，因此空间和时间的复杂度问题将是非常重要的一个环节。对于描述型的分类任务，模型描述越简洁越受欢迎；例如，采用规则表示的分类器构造法就更有用，而神经网络方法产生的结果就难以理解。
    另外要注意的是，分类的效果一般和数据的特点有关，有的数据噪声大，有的有缺值， 有的分布稀疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续值或混合式的。目前普遍认为不存在某种方法能适合于各种特点的数据。
   5.3、聚类
    聚类是把一组个体按照相似性归成若干类别，即”物以类聚”。它的目的是使得属于同一类别的个体之间的距离尽可能的小，而不同类别上的个体间的距离尽可能的大。聚类方法包括统计方法、机器学习方法、神经网络方法和面向数据库的方法。
    在统计方法中，聚类称聚类分析，它是多元数据分析的三大方法之一（其它两种是回归分析和判别分析）。它主要研究基于几何距离的聚类，如欧式距离、明考斯基距离等。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。这种聚类方法是一种基于全局比较的聚类，它需要考察所有的个体才能决定类的划分；因此它要求所有的数据必须预先给定，而不能动态增加新的数据对象。聚类分析方法不具有线性的计算复杂度，难以适用于数据库非常大的情况。
    在机器学习中聚类称作无监督或无教师归纳；因为和分类学习相比，分类学习的例子或数据对象有类别标记，而要聚类的例子则没有标记，需要由聚类学习算法来自动确定。很多人工智能文献中，聚类也称概念聚类；因为这里的距离不再是统计方法中的几何距离 ,而是根据概念的描述来确定的。当聚类对象可以动态增加时，概念聚类则称是概念形成。
    在神经网络中，有一类无监督学习方法：自组织神经网络方法；如Kohonen自组织特征映射网络、竞争学习网络等等。在数据挖掘领域里，见报道的神经网络聚类方法主要是自组织特征映射方法，IBM在其发布的数据挖掘白皮书中就特别提到了使用此方法进行数据库聚类分割。
   5.4、关联规则发现
    关联规则是形式如下的一种规则，”在购买面包和黄油的顾客中，有90%的人同时也买了牛奶”（面包+黄油 （ 牛奶 ）。用于关联规则发现的主要对象是事务型数据库，其中针对的应用则是售货数据，也称货篮数据。一个事务一般由如下几个部分组成：事务处理时间 ,一组顾客购买的物品，有时也有顾客标识号（如信用卡号）。
    由于条形码技术的发展，零售部门可以利用前端收款机收集存储大量的售货数据。因此，如果对这些历史事务数据进行分析，则可对顾客的购买行为提供极有价值的信息。例如，可以帮助如何摆放货架上的商品（如把顾客经常同时买的商品放在一起），帮助如何规划市场（怎样相互搭配进货）。由此可见，从事务数据中发现关联规则，对于改进零售业等商业活动的决策非常重要。
    如果不考虑关联规则的支持度和可信度，那么在事务数据库中存在无穷多的关联规则。事实上，人们一般只对满足一定的支持度和可信度的关联规则感兴趣。在文献中，一般称满足一定要求的（如较大的支持度和可信度）的规则为强规则。因此，为了发现出有意义的关联规则，需要给定两个阈值：最小支持度和最小可信度。前者即用户规定的关联规则必须满足的最小支持度，它表示了一组物品集在统计意义上的需满足的最低程度；后者即用户规定的关联规则必须满足的最小可信度，它反应了关联规则的最低可靠度。
    在实际情况下，一种更有用的关联规则是泛化关联规则。因为物品概念间存在一种层次关系，如夹克衫、滑雪衫属于外套类，外套、衬衣又属于衣服类。有了层次关系后，可以帮助发现一些更多的有意义的规则。例如，”买外套，买鞋子”（此处，外套和鞋子是较高层次上的物品或概念，因而该规则是一种泛化的关联规则）。由于商店或超市中有成千上万种物品，平均来讲，每种物品（如滑雪衫）的支持度很低，因此有时难以发现有用规则；但如果考虑到较高层次的物品（如外套），则其支持度就较高，从而可能发现有用的规则。另外，关联规则发现的思路还可以用于序列模式发现。用户在购买物品时，除了具有上述关联规律，还有时间上或序列上的规律，因为，很多时候顾客会这次买这些东西，下次买同上次有关的一些东西，接着又买有关的某些东西。