第三节 数据挖掘

一 知识发现的定义

随着计算机软件、硬件技术及网络的快速发展，数据收集变得方便且容易，海量数据存放在大型、大量、异构的数据库中，数据库中的知识发现技术（Knowledge Discovery in Databaes, KDD）可以在海量数据中分析出有价值的知识，解决了数据丰富但信息贫乏的问题。KDD的复杂性决定了它是一门交叉学科，涉及统计学、机器学习、人工智能、数据库技术、知识库技术、神经网络、模式识别、高性能计算、专家系统并行计算、数据可视化等多个领域。

1989年Fayyad给出的KDD定义是目前公认度最高的，“从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程”。其中“数据集”是一系列事实的集合F; “有效”表示可信度高；“新颖”表示发现的模式是以前未发现的；“潜在有用”表示发现的模式是用户需要的知识；“模式”是用语言L表示的一个表达式E, E用于描述数据集的特性（注意：E所描述的数据集是集合F的一个子集FE）;“过程”是KDD中包含的一个步骤，如数据清理、数据集成、模式搜索、知识表示、知识评价等；“非平凡”表示它已经超越了一般封闭形式的数量计算，还包括对结构、模式和参数的搜索。

二 知识发现的实现过程

基于知识发现的定义可知知识发现是一个综合的、复杂的、迭代的过程，包含以下五个步骤[1,6,26]：

（一）数据清理和集成。消除噪声后将多种数据源组合在一起；

（二）数据选择。从数据库中提取与分析任务相关的数据集；

（三）数据变换。通过汇总、合并、聚集等操作将数据转换为适合数据挖掘的形式；

（四）数据挖掘。核心步骤，选择合适的工具、操作提取数据模式；

（五）知识表示。根据用户的决策目的对挖掘出的信息进行分析，把最有价值的信息提取出来，并且通过可视化技术和知识表示技术等提交给决策者。

基于知识发现的五个步骤可以看出，数据挖掘（Data Mining）是知识发现的核心步骤，它发现用来评估的隐藏的模式。数据挖掘是利用特定的算法，在一定运算效率的限制下，从海量数据集中提取出有价值的知识的过程。

典型的数据挖掘系统包含数据库或数据仓库、引擎、模式评估和用户界面、知识库五个部分。

数据挖掘技术是面向应用的，它是对数据库中的数据进行微观的、中观的乃至宏观的统计、分析、综合和推理，是用来指导、发现现实问题的解决方案，试图找到多个事件之间的某种或多种相互联系，甚至使用现有的数据集对未来即将发生的某种事件进行定性、定量的预测。而且数据挖掘发现的任何知识都是相对的，是在某种特定的前提和约束条件下，面向某种特定领域的，易于被用户理解的发现结果。虽然数据挖掘过程是数据库中的知识发现的一个步骤，但人们往往不严格区分数据挖掘和数据库中的知识发现，将二者混淆使用。

数据挖掘的对象。原则上可以针对任何种类的数据进行数据挖掘，如关系数据库、事务数据库、数据仓库、高级数据库等。随着数据库技术的飞快发展，基于高级数据库的数据挖掘变得尤为重要，高级数据库主要包括：

（一）对象关系数据库

对象关系数据库是基于对象关系数据模型的，它使用了面向对象数据库的基本概念，是关系数据库系统与面向对象数据库模型的结合。它支持复杂数据的存储和处理，实现了对象属性和方法的封装。面向对象关系数据库的数据挖掘，重点解决处理复杂对象结构、复杂数据类型、类和子类的关系、类的属性和方法等。

（二）时间数据库、序列数据库、时间序列数据库

时间数据库包含时间属性。序列数据库包含有序事件的序列。时间序列数据库包含时间属性及重复的有序事件的序列。面向这三类数据库的数据挖掘，可以发现对象的演变特征或预测对象的变换趋势。

（三）空间数据库和时间空间数据库

空间数据库包含空间属性。时间空间数据库包含时间和空间属性。面向这两类数据库的数据挖掘，可以发现地理数据库、超大规模集成电路、卫星图像数据库中对象的分类、聚类特征或预测对象的变换趋势。

（四）文本数据库和多媒体数据库

文本数据库包含对象的语句描述，面向文本数据库的数据挖掘意在发现文本对象的关联规则、聚类行为等。多媒体数据库包含声音、图像、视频等多种媒体，面向多媒体数据库的数据挖掘意在提取多种媒体间的特征或模式匹配。

（五）异构数据库和遗产数据库

异构数据库是相关的多个数据库的集合，其各个组成部分具有自身的自治性。遗产数据库包含一组异构数据库，比单一的异构数据库更复杂。面向异构数据库和遗产数据库的数据挖掘涉及异构数据库的数据交换问题，数据转换规则的制定决定挖掘的质量。

（六）数据流

数据流是只能以特定的顺序被读取一次的数据序列。因为数据流并未存储于数据库中，且数据流是对海量数据的快速扫描，因此面向数据流的数据挖掘要求响应迅速，主要用于一般模式和动态变化的有效性发现。

（七）万维网

万维网包含许多相互链接的超文本信息，面向万维网的数据挖掘是从超链接、网页内容和使用日志中探寻出有用的信息。

三 数据挖掘技术与方法

数据挖掘分为预测型和描述型两类。预测型数据挖掘包括分类、回归、时间序列分析等，描述型数据挖掘包括聚类、汇总、关联规则、序列发现等。根据数据挖掘过程中发现知识的具体形式，将数据挖掘技术分为关联规则、分类、聚类、序列模式等。

（一）关联规则

关联规则（correlation rules）是形如X→Y形式的规则，其中X是关联规则的先导，Y是关联规则的后继，X和Y均是数据集中的属性。关联规则用于揭示数据之间的相互关系，[27]例如经典的应用——计算超市购物中被共同购买的商品：啤酒加尿布。关联规则中两个重要的指标是：

1．支持度

支持度是指规则中所出现模式的频率，如果数据库D有s%的事务包含XY，则称关联规则XY在D中的支持度为s%，即：

support（XY）=P（XY）

2．信任度

信任度是指蕴含的强度，即数据库D中c%的包含X的交易同时包含XY。若X的支持度是support（x），规则的信任度为support（XY）/sup-port（X），即：

confidence（XY）=P（Y|X）

关联规则的发现过程包含发现大项目集、产生关联规则（基于大项目集）两个步骤，其中如何高效确定所有的大项目集是解决关联规则问题的重点和难点，如Apriori算法、抽样算法、FP-树频繁集算法等。关联规则广泛使用于商业、银行业、零售业、保险业、电信业等。

（二）分类

分类（classification analysis）是将数据映射到预先定义好的群组或类的过程。例如：地铁模式识别恐怖分子。分类的发现过程包含学习和分类两个步骤，学习步骤使用分类算法分析训练样本，分类步骤用来检验数据用于评估分类规则的准确率。分类方法主要包括：

1．线性回归

2．基于距离的算法（K-最近邻算法）[28-31]

3．贝叶斯分类[32-34]

4．决策树归纳算法（ID3、C4.5、C5.0、CART算法）[35]

5．基于神经网络的算法[28]

6．基于规则的算法[36-49]

分类方法的优劣主要通过准确率、效率、鲁棒性、伸缩性和解释性五个指标评估。

分类主要应用于医疗诊断、图像与模式识别、故障检测、金融市场走势分析、贷款审批等。

（三）聚类

聚类分析（cluster analysis）是将数据集划分或分割成相交或不相交的群组或类的过程，目的是使得同一个群组或类中的个体之间的距离尽可能的短，不同群组或类中的个体之间的距离尽可能地长。[50-51]聚类研究的主要内容是基于几何距离的聚类，如欧式距离、明考斯基距离等。例如：根据客人收入等物理特征归类客户。聚类与分类的相同之处是二者都是将数据进行分组，分类中的群组或类是预先定义的，聚类中的群组或类不是预先定义的，而是根据具体的数据特征按照数据间的相似性定义群组或类。聚类中的群组或类也称为簇，聚类方法主要包括：

1．层次方法

层次聚类算法是产生嵌套的簇集，根据分解的形式，分成凝聚或分裂两种，如BIRCH算法、ROCK算法等。

2．划分方法

给定数据集N，包含n个对象，划分方式是将数据集N中的n个对象划分为k个簇（k≤n）。如最小生成树算法、平方误差聚类算法、k-均值聚类[52-54]算法、最近邻算法、EM算法、PAM（k - 中心）算法、CLARANS算法等。

3．密度方法

密度方法将簇（群组或类）认为是数据空间中被噪声（低密度区域）分隔开的高密度对象区域。如DBSCAN算法[55-56]、OPTICS算法、DEN-CLUE算法等。

4．网格方法

网格方法将对象空间量化成为有限数量的单元，形成网格结构后进行数据挖掘。如STRING算法、WaveCluster算法、CLIQUE算法等。

聚类应用广泛，主要用于客户分割、模式识别、生物学研究等。

（四）序列模式

序列模式（sequential patterns）用于确定数据之间与事件相关的序列，可以挖掘出多次（频繁的）出现的有顺序的事件。[57-59]例如“购买lenovo品牌笔记本的客户很可能在两个月内购买lenovo品牌打印机”。Agrawal和Srikant在1995年给出的定义是“给定一个序列集合，其中每一个的序列均由不同的元素（或事件）按顺序有序排列，每个元素（或事件）由不同项集组成，用户给出一个min sup阈值（即最小的支持度阈值），序列模式挖掘就是分析、挖掘出所有的频繁序列（包括其子序列），即找出的子序列在序列集中的出现频率不小于min sup”。序列模式挖掘都直接或间接地使用了Apriori算法或其变种算法。

序列模式和关联规则的共同点都是找到数据之间的关联性，但是二者是不同的。关联规则查找的是一次事务中数据的关联性，而序列模式查找的是多个事务中数据的关联性。如关联规则的经典应用是计算超市购物中被共同购买的商品——啤酒加尿布，它把每位顾客的一次交易视作一个事务，计算在不同事务中不同元素的组合规律。序列模式则考虑一位顾客在超市多次购物的情形，不同时间的交易记录就构成了一个购买序列，n个用户的购买序列就形成了一个规模为n的序列数据集。在关联规则基础上综合时间因素之后，我们可以得到比关联规则更有价值的规律，如关联挖掘能挖掘出如啤酒和尿布的关联规律，序列模式挖掘则能挖掘出有一定因果性质的规律——《育儿宝典》→婴儿车。影响序列模式挖掘的主要参数：时间序列的持续时间（duration）、事件的重叠窗口（event folding window）、被发现的模式中时间之间的间隔（interval）。

序列模式主要的应用领域是客户购买行为模式预测、Web访问模式预测、疾病诊断、自然灾害预测、天气预测、DNA序列分析等。

四 数据挖掘研究热点和难点

2002年麻省理工学院的《科技评论》杂志提出未来五年对人类产生重大影响的十大新兴技术，“数据挖掘”位居第三。最近的Gartner报告中列举了在今后3—5年内对工业将产生重要影响的五项关键技术，KDD和人工智能排名第一。数据挖掘的研究热点和难点如下：

（一）复杂结构数据挖掘

复杂结构数据挖掘即挖掘的对象是复杂结构数据，复杂结构数据在学术界并没有一个公认的定义，目前通常的描述是“不能使用属性值语言描述的数据即为复杂结构数据”，如复杂结构中数据的数据对象、类层次结构、类的组合与继承等，由于复杂结构数据体现了丰富的语义，用传统的数据挖掘技术难以处理。复杂结构数据挖掘中的难点是复杂结构数据的表示机制及针对复杂结构的挖掘技术。复杂结构数据挖掘在生物学、医学、反恐、语义Web、普适计算等领域都有涉及。

（二）图挖掘和社会网络分析

图是针对事物之间的联系而进行建模的普遍数据结构，图挖掘可以捕捉化合物网络、隐匿罪犯分析、社区网络分析（社区发现、图分割、连通子图发现等）、图分类、图聚类、频繁子图模式发现等。图挖掘是从频繁模式挖掘扩展而来，即从图中挖掘出频繁子图。但是图挖掘相比频繁模式挖掘要困难得多，如图节点标签是否允许重复，如何表示有约束的节点、如何解决图同构问题，因此开发有效的图是数据挖掘一个巨大的挑战。目前图挖掘和社会网络分析主要采用Apriori算法及其变种。

（三）高维（大数据）数据挖掘

高维数据挖掘是基于高维度的数据挖掘。随着计算机软件、硬件技术及互联网技术的快速发展，使得数据的收集越来越容易，因此数据库的规模越来越大，维度（属性）越来越多，维度值数以千计，因此称为高维度数据。基于高维度数据（也称大数据）的数据挖掘变得异常困难，导致“维灾”问题的出现。传统的数据挖掘技术是基于低维数据的，直接用于高维数据挖掘会导致挖掘性能骤然下降，目前主要的解决方法是将数据从高维降到低维、哈希索引、增量算法或并行算法来提高算法性能、重新设计欧式距离等，但高维数据挖掘的效率一直是个较难解决的问题。

（四）数据挖掘中的隐私保护

随着挖掘工具能力的逐步提高，随着互联网技术的发展，数据的获取越来越容易，通过数据挖掘很容易将分布于网络上的点滴收集整理后挖掘出个人隐私或共同隐私。隐私保护数据挖掘就是在保证数据挖掘的同时尽可能地保护敏感数据，在不精确访问原始数据的条件下，得到准确或基本准确的模型和分析结果。[24]但随着互联网技术和挖掘技术的发展，数据挖掘中的隐私保护遇到了前所未有的困难。