人工智能-原理、算法和实践 第七章 数据挖掘

第七章数据挖掘一、数据挖掘的概述二、分类三、聚类四、关联规则1一、数据挖掘的概述数据挖掘概念与发展

随着科学技术的飞速发展，使得各个领域或组织机构积累了大量数据。如何从这些数据中提取有用的信息和知识以帮助做出明智决策成为巨大的挑战。计算机技术的迅速发展使得处理并分析这些数据成为可能，这种技术就是数据挖掘(DataMining，DM)，又称为数据库知识发现(KnowledgeDiscoveryinDatabase，KDD)。数据挖掘概念首次出现在1989年举行的第11届国际人工智能学术会议上，其思想主要来源于机器学习、模式识别、统计和数据库系统。目前对数据挖掘并没有统一的定义，大多采用的是韩家炜先生给出的定义：2数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们事先不知道的，但又是潜在有用的信息和知识的过程。上述定义的含义有以下几个方面：第一，数据源必须是大量的、真实的，真实的数据往往含有噪声或缺失。第二，发现的是用户感兴趣的知识。第三，发现的知识要可接受，可理解，可运用，能支持特定的问题发现，能够支持决策，可以为企业带来效益，或者为科学研究寻找突破口。3数据挖掘的任务

数据挖掘的任务可以分为预测型任务和描述型任务，预测型任务就是根据其他属性的值预测特定属性的值，如回归、分类、离群点检测等。描述型任务就是寻找、概括数据中潜在联系的模式，如聚类分析、关联分析、演化分析、序列模式挖掘。4数据挖掘的应用数据挖掘就是为大数据而生的，有大量数据的地方就有数据挖掘的用武之地。目前，应用较好的领域或行业有生物信息学、电信业、零售业以及保险、银行、证券等金融领域。

生物信息学是数据挖掘应用的新领域，是21世纪生物学的产物。零售业收集了关于销售、顾客购物史、消费等大量数据，是数据挖掘很好的应用领域之一。金融领域存有大量的客户信息记录、自身服务记录等，可用数据挖掘技术分析客户需求和兴趣，银行方面可以预测存、贷款趋势等，可以更好地服务客户。随着网络的发展，大量的文档数据涌现在网上，文本挖掘显得更加重要，这也是数据挖掘应用的一个重要子领域。5数据挖掘过程与方法数据挖掘只是数据挖掘过程的一部分，完整的挖掘过程还包括以下步骤：定义业务目标、甄别数据源、收集数据、选择数据、数据质量检查、数据转换和结果解释。

在数据挖掘阶段，概括而言，数据挖掘分析员可以使用的数据挖掘的方法主要有以下几个：预估模型。包括分类和预估两种类型。聚类技术连接技术时间序列技术在本章中将介绍几种具体的数据挖掘方法。6二、

分类

7

8基于规则的分类器基于规则的分类器是使用一组“if...then...”规则来对记录进行分类的技术。为了建立基于规则的分类器，需要提取一组规则来识别数据集的属性和类标号之间的关键联系。提取分类规则的方法有两大类：直接方法和间接方法。直接方法是直接从数据中提取分类规则，间接方法是从其他分类模型中提取分类规则。顺序覆盖算法经常被用来直接从数据中提取规则，规则对于某种评估度量以贪心的方式增长。该算法按照从包含多个类的数据集中一次提取一个类的规则，决定哪一个类的规则最先产生的标准取决于多种因素，如类的普遍性，或者给定类中误分类记录的代价。9

10朴素贝叶斯分类器

朴素贝叶斯分类方法是基于统计的学习方法，利用概率统计进行学习分类，如预测一个数据属于某个类别的概念。主要算法有朴素贝叶斯分类算法、贝叶斯信念网络分类算法等。贝叶斯分类方法的主要特点如下：

(1)利用先验知识显式计算假设概率。

(2)利用有向图表示，直观易于理解。

(3)能进行增量学习，方便处理不完整数据。贝叶斯定理是朴素贝叶斯分类算法和贝叶斯信念网络分类算法的基础，在6.8节讨论过，在此不再重复。本节介绍朴素贝叶斯分类算法。根据朴素贝叶斯分类原理，算法原理描述见课本第161页。11

1213三、

聚类1.概念聚类分析的核心是聚类，聚类是一种无监督学习，实现的是将整个数据集分成不同的“簇”，在相关的文献中，也将之称为“对象”或“数据点”。聚类要求簇与簇之间的区别尽可能大，而簇内数据的差异尽可能小。与分类不同，不需要先给出数据的类别属性。2.聚类分析的基本方法聚类分析的研究主要基于距离和基于相似度的方法。根据不同的数据类型和聚类的目的可以选择不同的聚类算法。主要的聚类算法可以划分为如下4类。14

划分聚类的方法给定一个数据集，将构建数据集的有限个划分，每个划分都是一个簇，且每一个划分应当满足如下两个条件：(1)每个划分中至少包含一个样本。(2)每个样本只能属于一个簇。k-Means和k-Medoids就是典型的划分聚类算法。k-Means算法是一种最常用的基于划分的聚类方法。其基本思想是：把数据集划分成k个簇，每个簇内部的样本非常相似，但不同簇之间样本则又差异很大。在给定初始k个簇之后，算法根据某个距离函数反复地把数据分入k个聚类中，直到满足终止条件为止。k-Means并不适合所有的数据类型。1516

1718AGNES是一种采用自底向上聚合策略的层次聚类方法基于密度的方法其主要思想是:只要“领域”中的密度超过了某个阈值，就继续增长给定的簇。这样的方法可以用来过滤噪声或离群点，发现任意形状的簇。基于密度的聚类代表算法有DBSCAN、OPTICS、DENCLUE算法等。DBSCAN是一个比较有代表性的基于密度的聚类方法。与层次聚类不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的空间数据库中发现任意形状的聚类。然而，当簇的密度变化太大时，密度定义更为困难。1920基于模型的聚类基于模型的聚类方法试图将给定数据与某个数学模型达成最佳拟合。此类方法经常假设数据是根据潜在的概率分布生成的。基于模型的聚类方法主要包括统计学方法、概念聚类方法和神经网络方法。AutoClass方法是一种基于贝叶斯理论的数据聚类算法，通过对数据进行处理，计算出每条数据属于每个类别的概率值，对数据进行聚类。COBWEB是一个常用且简单的增量式概念聚类方法。它的输入对象采用符号-值对(属性-值对)来描述。该方法采用分类树的形式创建一个层次聚类。2122SOM是神经网络方法的典型代表，SOM采用竞争学习算法，其聚类过程通过若干单元对当前单元的竞争来完成，与当前单元权值向量最接近的单元成为赢家或获胜单元，同时抑制距离较远的神经元。四、

关联规则

23

24

25

262728下面举例说明该算法的规则。现有一个事务数据库如表所示，找出其所有满足最小支持度计数的关联规则。表的每一行表示一条交易，共有9行，左边表示顾客ID，右边表示商品ID，为了方便计算，这里给出最小支持度计数为min_sup=2(等于最小支持度为22%)。29

303132

33由于规则由频繁项集产生，因此每个规则都自动满足最小支持度。频繁项集和它们的支持度可以预先放在散列表中，使得它们可以被快速访问。由前面的例子可以知道AllElectronics数据库包含频繁项集X={I1,I2,I5}，非空子集是{I1,I2}、{I1,I5}、{I5,I2}、{I1}、{I2}、{I5}。产生的关联规则如下：{I1,I2}⇒{I5}，confidence=2/4=50%{I1,I5}⇒{I2}，confidence=2/2=100%{I2,I5}⇒{I1}，c