第1章　数据挖掘基础

1.1　数据挖掘概述

数据挖掘出现于20世纪80年代后期，是数据库研究中很有应用价值的新领域。数据挖掘是一门交叉性学科，融合了人工智能、数据库技术、模式识别、机器学习、统计学和数据可视化等多个领域的理论和技术。

数据挖掘（data mining），又称数据库中的知识发现（Knowledge Discovery in Database, KDD）。从技术角度看，就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐藏在其中的人们事先不知道的，但又是潜在有用的信息和知识的过程。数据挖掘把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。典型的数据挖掘系统结构如图1-1所示。

数据挖掘基于的数据库类型主要有关系型数据库、面向对象数据库、事务数据库、演绎数据库、时态数据库、多媒体数据库、主动数据库、空间数据库、文本型、Internet信息库及数据仓库等。数据挖掘后获得的知识包括关联规则、特征规则、区分规则、分类规则、总结规则、偏差规则、聚类规则、模式分析及趋势分析等。

数据挖掘与传统的数据分析（如查询、报表、联机应用分析）的本质区别是数据挖掘是在没有明确假设的前提下挖掘信息、发现知识。数据挖掘是要发现那些不能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信息越是出乎意料就越可能有价值。在投资领域，能够比市场提前知道这种信息，提前做出决策，就能够获得超额的利润。

1.1.1　数据挖掘的过程

数据挖掘的过程会随所应用的专业领域的不同而有所变化。每一种数据挖掘技术都有各自的特性以及使用步骤，因此针对不同需求所发展出的数据挖掘过程也就存在着差异。

一般而言，常见的数据挖掘过程可以分为三个主要阶段：数据准备、数据挖掘及结果表达和解释，如图1-2所示。

1．数据准备

（1）数据集成。将多文件或多数据库运行环境中的数据进行合并处理，主要解决语义模糊性，处理数据中的遗漏和清洗脏数据等。

（2）数据选择。从原始数据库中选取相关数据或样本。数据选择的目的是辨别出需要分析的数据集合，缩小处理范围，提高数据挖掘的质量。

（3）预处理。检查数据的完整性及一致性，消除噪声等。

2．数据挖掘

此阶段进行实际的挖掘操作，利用机器学习、统计分析等方法，从数据库中发现有用的模式或知识。数据挖掘阶段的主要步骤如下：

（1）确定挖掘目标。确定要发现的知识类型。

（2）选择算法。根据确定的目标，选择合适的数据挖掘算法。

（3）数据挖掘。应用所选算法，提取相关知识并以一定的方式进行表示。

3．结果评价

此阶段对挖掘结果进行表达与解释。根据最终用户的决策目的，对提取的信息进行分析，把最有价值的信息区分出来，并且通过决策支持工具提交给决策者。该步骤的主要任务有如下两项：

（1）模式评估。对在数据挖掘步骤中发现的模式或知识进行评估。

（2）知识表示。使用可视化和知识表示相关技术，呈现所挖掘的知识。

1.1.2　数据挖掘的任务

数据挖掘的主要任务有6项：关联分析、时序模式、聚类、分类、偏差检测和预测。

1．关联分析

关联分析是从数据中发现知识的一类重要方法。若两个或多个数据项的取值之间重复出现且概率很高时，就存在某种关联，可以建立起这些数据项的关联规则。关联分析的目的在于生成部分数据的概要，例如寻找数据子集间的关联关系或者一些数据与数据之间的派生关系。关联规则的计算依赖于识别在相关数据中频繁出现的数据集。

例如，买面包的顾客中90%的人还买牛奶，这是一条关联规则。若商店中将面包和牛奶放在一起销售，将会提高销量。在大型数据库中，这种关联规则很多，需要进行筛选，一般用“支持度”和“可信度”两个阈值淘汰那些无用的关联规则。支持度表示该规则所代表的事例占全部事例的百分比。如买面包又买牛奶的顾客占全部顾客的百分比。可信度表示该规则所代表事例占满足前提条件事例的百分比。如买面包又买牛奶的顾客占买面包顾客中的90%，即可信度为90%。

2．时序模式

通过时间序列搜索出重复发生概率较高的模式，这里强调时间序列的影响。例如，在所有购买了激光打印机的人中，80%的人半年后再购买新硒鼓，20%的人用旧硒鼓装碳粉；在所有购买了彩色电视机的人中，有60%的人会再购买VCD产品。

在时序模式中，需要找出在某个最小时间内出现比率一直高于某一最小百分比（阈值）的规则。这些规则会随着形式的变化做适当的调整。时序模式中，一个有重要影响的方法是“相似时序”。用相似时序方法，按时间顺序查看时间事件数据库，从中找出另一个或多个相似的时序事件。例如，在零售市场上找到另一个有相似销售的部门；在股市中找到有相似波动的股票。

3．聚类

数据库中的数据可以划分为一系列有意义的子集，即类。在同一类别中，个体之间的距离较小，而不同类别上的个体之间的距离较大。聚类用于从数据集中找出相似的数据，并组成不同的组。聚类增强了人们对客观现实的认识，即通过聚类建立宏观概念，例如鸡、鸭、鹅等都属于家禽。与预测模型不同，聚类中没有明显的目标变量作为数据的属性存在。

聚类方法包括统计分析方法、机器学习方法、神经网络方法等。

在统计分析方法中，聚类分析是基于距离的聚类，如欧几里得距离、海明距离等。这种聚类分析方法是一种基于全局比较的聚类，它需要考察所有的个体才能决定类的划分。常用的统计分析聚类算法很多，包括K-Means算法、分层凝聚法、期望极大值法等。

在机器学习方法中，聚类是无导师的学习。在这里距离是根据概念的描述确定的，故聚类也称为概念聚类。当聚类对象动态增加时，概念聚类则称为概念形成。

在神经网络中，自组织神经网络方法用于聚类，如ART模型、Kohonen模型等，这是一种无监督学习方法。当给定距离阈值后，各样本按阈值进行聚类。

4．分类

分类是数据挖掘中应用最多的任务。分类是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类的内涵描述，一般用规则或决策树模式表示。该模式能把数据库中的元组影射到给定类别中的某一个。

一个类的内涵描述分为特征描述和辨别性描述。特征描述是对类中对象的共同特征的描述。辨别性描述是对两个或多个类之间的区别描述。特征描述允许在不同类中具有共同特征；而辨别性描述对不同的类不能有相同特征。辨别性描述用得更多。

分类是利用训练样本集通过有关算法求得的。分类一直为人们所关注，广泛使用的方法有决策树、朴素贝叶斯、逻辑回归、神经网络等。

目前，分类方法的研究成果较多，判别方法的好坏可以从三个方面进行：①预测准确度（对非样本数据的判别准确度）；②计算复杂度（方法实现对时间和空间的复杂度）；③模式的简洁度（如在同样效果情况下，希望决策树小或者规则少）。

5．偏差检测

数据库中的数据存在很多异常情况，从数据分析中发现这些异常情况也是很重要的，以引起人们对它更多的注意。

偏差包括很多有用的知识，如分类中的反常实例、模式的例外、观察结果对模型预测的偏差量值等。偏差检测的基本方法是寻找观察结果与参照之间的差别。观察常常是某一个域的值或多个域值的汇总。参照是给定模型的预测、外界提供的标准或另一个观察。

6．预测

预测是利用历史数据找出变化规律、建立模型，并用此模型预测未来数据的种类、特征等。典型的方法是回归分析，即利用大量的历史数据，以时间为变量建立线性或非线性回归方程。预测时，只要输入任意的时间值，通过回归方程就可求出该时间的状态。

近年来发展起来的神经网络方法，如BP模型，实现了非线性样本的学习，能进行非线性函数的判别。分类也能进行预测，但分类一般用于离散数值。回归预测用于连续数值。神经网络预测方法既可用于连续数值，也可以用于离散数值。

1.1.3　数据挖掘的应用

数据挖掘是从海量数据中提取知识的信息技术。数据挖掘使数据处理技术进入了一个更高级的阶段，不仅能对过去的数据进行查询和遍历，还能够找出以往数据间潜在的联系，促进信息的传播。目前，数据挖掘在国内外都受到了前所未有的重视，并广泛应用于各个领域，如银行、电信、保险、交通、零售等商业领域。数据挖掘所能解决的典型商业问题包括数据库营销（database marketing）、客户群体划分（customer segmentation & classification）、背景分析（profile analysis）、交叉销售（cross selling）等市场分析行为，以及客户流失性分析（churn analysis）、客户信用记分（credit scoring）、欺诈发现（fraud detection）等。

近年来，计算技术和存储技术的飞速发展为数据挖掘技术的日臻完善提供了条件。数据挖掘技术在商业领域的应用已经比比皆是，例如：

• 互联网巨头谷歌和百度等公司通过复杂的挖掘算法，评估网页对用户搜索关键词的相关度，对广告单击率进行预测等；
• 电子商务巨头亚马逊和eBay等公司，通过数据挖掘预测用户购买某一商品的可能性，以及推荐相关商品和个性化商品等；
• 零售巨头沃尔玛公司，很早就通过分析顾客购买记录寻找不同商品之间的关联性，从而做到更合理上架不同品类商品；
• 商业银行通过分析历史存贷款及还款记录预测客户的贷款风险；
• 对冲基金依赖于数据挖掘技术预测证券的价格走势和寻找投资机会；
• 证券交易监管部门通过分析证券交易数据发现内线交易。

1.1.4　数据挖掘的存在问题、未来发展和挑战

数据挖掘的存在问题、未来发展和挑战主要体现在以下三个方面。

1．数据挖掘技术和用户交互的问题

（1）挖掘数据库中不同类型的知识。由于不同的用户可能对不同类型的知识感兴趣，数据挖掘应当能涵盖范围很广的数据分析和知识发现任务，包括数据特征化、区分、关联与相关分析、分类、预测、聚类、离群点分析和演变分析等。这些任务可能以不同的方式使用相同的数据库，并需要开发大量的数据挖掘技术。

（2）多个抽象层的交互知识挖掘。由于很难准确地知道能够在数据库中发现什么，数据挖掘过程应当是交互的。对于包含海量数据的数据库，首先应当使用适当的抽样技术，进行交互式数据探查。交互式挖掘允许用户聚焦搜索模式，根据返回的结果提取和精练数据挖掘请求。类似于联机分析处理对数据立方体所做的那样，应当能通过交互地在数据空间和知识空间下钻、上卷和旋转挖掘知识。用这种方法用户可以与数据挖掘系统交互，以不同的粒度从不同的角度观察数据和发现模式。

（3）结合背景知识。可以使用背景知识或关于所研究领域的信息指导发现过程，并使得发现的模式以简洁的形式在不同的抽象层表示。关于数据库的领域知识，如完整性约束和演绎规则，可以帮助聚焦和加快数据挖掘过程，或评估发现模式的兴趣度。

（4）数据挖掘查询语言和特定的数据挖掘。关系查询语言（如SQL）允许用户提出特定的数据检索查询。类似地，需要开发高级数据挖掘查询语言，使得用户可以通过说明分析任务的相关数据集、领域知识、所挖掘的知识类型、被发现的模式必须满足的条件和约束，描述特定的数据挖掘任务。这种语言应当与数据库或数据仓库查询语言集成，并且对于有效的、灵活的数据挖掘是优化的。

（5）数据挖掘结果的表示和可视化。发现的知识应当用高级语言、可视化表示或其他形式进行表示，使得知识易于理解，能够直接被人们使用。如果数据挖掘系统是交互的，这一点尤其重要。这要求系统采用有表达能力的知识表示技术，如树、表、规则、图、图表、交叉表、矩阵或曲线等。

（6）处理噪声和不完全数据。存放在数据库中的数据可能反映噪声、异常情况或不完全的数据对象。在挖掘数据规律时，这些对象可能扰乱分析过程，导致所构造的知识模型过分拟合数据。其结果是所发现的模式的准确性可能很差。需要处理数据噪声的数据清理方法和数据分析方法，以及发现和分析异常情况的离群点挖掘方法。

（7）模式评估即兴趣度问题。数据挖掘系统可能发现数以千计的模式。对于给定的用户，所发现的许多模式都不是有趣的，因为它们表示的是一些常识或缺乏新颖性的东西。关于开发模式兴趣度的评估技术，特别是关于给定用户类，基于用户的信念或期望，评估模式价值的主观度量仍然存在挑战。使用兴趣度度量或用户指定的约束指导发现过程和压缩搜索空间是又一个活跃的研究领域。

2．数据挖掘算法的性能问题

（1）数据挖掘算法的有效性和可伸缩性。为了有效地从数据库的海量数据中提取信息，数据挖掘算法必须是有效的和可伸缩的。也就是说，数据挖掘算法在大型数据库中的运行时间必须是可预计的和可接受的。从数据库的知识发现角度，有效性和可伸缩性是数据挖掘系统实现的关键问题。

（2）并行、分布和增量挖掘的算法。许多数据库的巨大规模、数据的广泛分布和一些数据挖掘算法的计算复杂性是促使开发并行和分布式数据挖掘算法的因素。这种算法将数据划分成若干部分，并行处理，最后合并每个部分的结果。此外，有些数据挖掘过程的高开销导致了对增量数据挖掘算法的需要。增量算法与数据库更新结合在一起，而不必“从头开始”挖掘全部数据，这种算法增量地进行知识修改、修正和加强业已发现的知识。

3．数据库类型的多样性问题

（1）复杂数据类型的处理。由于关系数据库和数据仓库已经广泛使用，为这样的数据开发有效的数据挖掘系统是重要的。然而其他数据库可能包含复杂的数据对象、超文本和多媒体数据、空间数据、时间数据或事务数据等。由于数据类型的多样性和数据挖掘目标不同，指望一个系统挖掘所有类型的数据是不现实的。因此，为挖掘特定类型的数据应当构造特定的数据挖掘系统。

（2）从异构数据库和全球信息系统挖掘信息。局域网和广域网连接了许多数据源，形成了庞大的分布和异构数据库。从具有不同数据语义的结构化、半结构化和非结构化的不同数据源发现知识，对数据挖掘提出了巨大挑战。数据挖掘可以帮助发现多个异构数据库中的高层数据规律，这些规律多半难以被简单的查询系统发现，并可以改进异构数据库信息交换和互操作性能。

以上问题是数据挖掘技术未来发展的主要需求和挑战。在近年来的数据挖掘研究和开发中，一些挑战已经在一定程度上受到关注，并且现在认为是必需的，而另一些仍处于研究阶段。