数据挖掘是从人工智能领域的一个分支——机器学习发展而来的，因此机器学习、模式识别、人工智能领域的常规技术，如聚类、决策树、统计等方法经过改进，大都可以应用于数据挖掘。

1）决策树

决策树广泛地使用了逻辑方法，相对较小的树更容易理解。图8-2是关于训练数据的决策二叉树。为了分类一个样本集，根节点被测试为真或假的决策点。根据对关联节点的测试结果，样本集被放到适当的分枝中进行考虑，并且这一过程将继续进行。当到达一个决策点时，它存贮的值就是答案。从根节点到叶子的一条路就是一条决策规则。决定节点的路是相互排斥的。

使用决策树，其任务是决定树中的节点和关联的非决定节点。实现这一任务的算法通常依赖于数据的划分，在更细的数据上通过选择单一最好特性来分开数据和重复过程。树归纳方法比较适合高维应用。这经常是最快的非线性预测方法，并常应用动态特性选择。

最早的决策树方法是1966年Hunt所提出的CLS算法，而最著名的决策树学习算法是Quinlan于1979年提出的ID3方法。

图8-2　决策树

（1）CLS算法。CLS算法的主要思想是从一个空的决策树出发，通过添加新的判定节点来改善原来的决策树，直至该决策树能够正确地将训练例分类为止。

①令决策树T的初始状态只含有一个树根（X，Q），其中X是全体训练实例的集合，Q是全体测试属性的集合。

②若T的所有节点（X′，Q′）都有如下状态：或者第一个分量X′中的训练实例都属于同一个类，或者第二个分量Q′为空，则停止学习算法，学习结果为T。

③否则，选取一个不具有步骤（2）所述状态的叶节点（X′，Q′）。

④对于Q′，按照一定规则选取测试属性b，设X′被b不同取值分为m个不相交的子集Xi′，1≤i≤m，从（X′，Q′）伸出m个分叉，每个分叉代表b的一个不同取值，从而形成m个新的叶结点（Xi′，Q′－｛b｝），1≤i≤m。

⑤转步骤②。

（2）ID3算法。ID3算法对检测属性的选择给出一种启发式规则，这个规则选择平均信息量（熵）最小的属性A，因此，又称为最小熵原理。

①选取整个训练实例集X的规模为W的随机子集X1（W称为窗口规模，子集称为窗口）。

②以信息熵最小为标准选取每次的测试属性，形成当前窗口的决策树。

③顺序扫描所有训练实例，找出当前的决策树的例外，如果没有例外则训练结束。

④组合当前窗口中的一些训练实例与某些在（3）中找到的例外形成新的窗口，转（2）。

2）关联规则方法

关联规则方法是数据挖掘的主要技术之一。关联规则方法就是从大量的数据中挖掘出关于数据项之间的相互联系的有关知识。

关联规则挖掘也称为“购物篮分析”，主要用于发现交易数据库中不同商品之间的关联关系。发现的这些规则可以反映顾客购物的行为模式，从而可以作为商业决策的依据。在商业领域得到了成功应用。Apriori算法是一种经典的生成布尔型关联规则的频繁项集挖掘算法。

如超市的后台数据库会存储大量的消费者每天的购物数据。表8-1中的每行对应一个事务，包含了唯一的标识ID和消费者购买的物品的集合。超市分析员通常会挖掘这些数据内在的联系，了解超市的消费者的购买行为。挖掘出的有价值的规律可以用来支持各种促销计划，库房的供销管理等。

表8-1　超市购物数据

这里采用关联分析（association analysis）的方法，用来发现隐藏在大量数据中的潜在的有用联系。所挖掘出来的关系可以用关联规则（association rule）和频繁项集的形式来进行表达。

｛尿布｝→｛啤酒｝，这条规则说明了尿布和啤酒之间的销售有着很强的联系，因为许多消费者购买尿布的同时也购买了啤酒，销售商可以利用这类规则，增加新的交叉销售的机会。

在对购物篮事务使用关联分析技术时，需要处理两个关键的问题：第一，在大型关系数据库中使用关联分析的计算成本非常高，容易导致维灾难；第二，挖掘出来的关联规则的可信程度如何？是必然的内在联系还是偶尔出现的小概率事件呢？

定义：令I=｛i1，i2，…，in｝是购物篮数据集中所有项的集合，T=｛t1，t2，…，tm｝是所有事务的集合。每个事务ti所包含的项集ii都是集合I的子集。像这样包含了0个或者n个项的集合就被称为项集。项集包含了多少个项，就称为·项集。如包含了m项，称为m 项集。如表中的事务ID为1的项集｛面包，牛奶｝，是一个2-项集。

关联分析挖掘出来的关联规则的一般为具有“X→Y”形式的蕴涵表达式，其中X⊂I，Y⊂I并且X∩Y≠∅。关联规则的强弱程度一般使用支持度（support）和置信度（confidence）来度量。支持度使得规则度量了给定数据集的频繁程度，表示了一种期望和规则的有用性，如果支持度较高说明规则是经常出现的，较低的支持度说明规则偶然性高，使用价值不大。置信度确定了Y在包含了X的事务中出现的频繁程度，描述的是关联规则的确定性，置信度越高，相应的Y在包含X的事务中出现的概率也就越高。关于支持度s和置信度c的数学定义如下：

其中σ（·）称为支持度计数，计算方式为：

对关联分析进行关联规则的挖掘算法通常分解为两个步骤：

第一步：发现项集频度满足预先定义的阈值最小支持度（minimum support count）的所有项集，这些项集称为频繁项集（frequent itemset）。

第二步：从第一步获取的所有频繁项集当中提取高置信度的规则，这些规则称为强规则（strong rule）。所谓的高置信度也是预先定义的一个阈值，强规则满足定义好的最小置信度。

例：一个体育用品商店的简单购物数据说明关联分析的过程（见表8-2）。

表8-2　体育用品超市商店的购物记录

从数据表中可以看出，事务计数=6，项集I=｛网球拍，网球，运动鞋，羽毛球｝。对网球拍和网球进行关联规则挖掘：事务1，2，3，4，6包含网球拍，事务1，2，6同时包含网球拍和网球，可以计算出支持度s=0.5，置信度c=0.6，如果事先给定的支持度s的阈值为0.5，置信度c的阈值为0.6，那么我们就可以认为网球拍和网球之间存在强关联规则，解释说法就是购买网球拍的顾客通常也会同时购买网球。

关联分析在实际应用中产生的频繁项集数目会非常大，需要探索的项集空间一般都达到了指数级，所以需要有相应的高效算法来降低算法的时间复杂度，详细算法描述流程及实现将在第4章介绍。实际应用当中还有更多比超市购买更复杂的问题，学者们也做了许多研究从各个方向对关联规则进行拓展，将更多的技术混合到关联规则挖掘技术之中，使得关联规则的覆盖面进一步扩大。如考虑数据集记录属性之间的类别层次关系，时态关系，多表挖掘等。近年来关于关联规则的研究主要集中于两个方向，即如何扩大经典关联分析算法解决问题的范畴，提高经典关联分析挖掘算法的效率和规则实用性。

3）聚类

20世纪80年代，Everitt关于聚类给出了以下定义：在同一个类簇中的数据样本是相似的，而在不同的类簇中的样本是不同的，而且分别处于两个类中的数据间的距离要大于一个类中的两数据之间的距离。计算相异和相似度的方法是基于对象的属性值，常运用距离作为度量方式。

数据挖掘中，聚类与分类既有联系又有区别，被称为无监督分类，而分类分析是有监督分类。

高效的聚类算法需要满足两个条件：①簇类的样本相似度高；②簇间的相似度低。一个聚类算法采用的相似度度量方法以及如何实现很大程度上影响着聚类质量的好坏，且与该算法是否能发现潜在的模式也有一定的关系。

（1）聚类的一般过程。(www.daowen.com)

①数据的准备：这一阶段是将数据的特征进行标准化处理和降低数据的维数；

②特征选择：这一阶段是剔除多余的信息，减少信息量的过程，尽量的选择出所有有用的特征；

③特征提取：这一阶段是把上一步的特征进行转换，使之能够成为进行下一步聚类所用的特征；

④聚类：这一阶段需要选取某种适当的相似性度量（一般采用欧几里得距离），然后选择合适的算法进行聚类的划分；

⑤效果评估：这一阶段主要是指对上一阶段得到的聚类结果进行评估，评估主要有外部有效性、内部有效性和相关性测试评估三种方式。

（2）相似性度量。

聚类分析是依据对象两两之间的相似（或差异）程度来划分类的，而这相似程度通常是用距离来衡量的。运用最广泛的距离计算公式是欧几里得距离（Euclidean distance），公式如下：

其中，i=（xi1，xi2，…，xip），j=（xj1，xj2，…，xjp）。曼哈顿（Manhattan）距离是另一个常见的距离公式，公式如下：

欧几里得距离和曼哈顿（Manhattan）距离是闵可夫斯基（Minkowski）距离的两个特例。闵可夫斯基距离的公式如下：

由此可知，若r=1，则它就是曼哈顿距离公式；若r=2，则它就是欧几里得距离公式。

（3）准则函数。

聚类的目的是使类内的相似性高，而类间的相似性低。聚类结果的质量可以由聚类准则函数来判断，若准则函数选的好，质量就会高，反之，质量达不到要求时，则须反复运行聚类过程。一般的聚类准则函数有以下三种：

①误差平方和准则：

当各种样本较密集，且数量相差不大时，误差平方和准则可以获得良好的聚类结果。函数定义如下：

式中，mj是类型wj中样本的平均值，其计算方法如下：

式中，mj是c个集合的中心，可以代表c个类型。Jc表示最终的误差平方和。若Jc的值小，则表示聚类结果好，也就是误差小。

②加权平均平方距离和准则：

式中的的公式如下：

式中，xj中的样本数量为nj，xj中的样本互相组合共有种。是所有样本间的距离之和。

③类间距离和准则：

加权类间距离和准则：

式中，，Pj是类型wj的先验知识概率。

上述公式表示不同类间的分离程度，因此，Jb的值越小，说明类间的差别程度越小，聚类效果越差。

（4）数据挖掘中的聚类分析方法。

①基于划分的方法。

假设一个数据集总共有n个对象，要生成k个类，且k≤n。起初划分k个类，接着根据相应的规则，使得对象在各个类之间不断的移动，并且反复运算聚类中心，直到最终获得满足条件的k个划分。k个划分中的每个划分都必须满足以下两个条件：一是每个类必须都是非空的；二是对每个对象而言，它只可能在某一个类，而不可能同时出现在两个类中。划分的准则是：相同类中的对象间的相似性尽量高，而不同的类的对象之间的相似性尽量低。基于划分的聚类算法快速、简单且有效，但也有某些不足之处；例如：容易陷入局部最优和对初始值敏感等。最常用的基于划分的算法有：K-means算法和K-中心值算法等。

②基于层次的方法。

基于层次的方法是将数据对象一层一层地进行分解，通常通过树状图来显示。层次的聚类方法包含两种，分别是分裂的方法，还有凝聚的方法。

③基于网格的方法。

该方法将数据空间创建成类似方块的网格结构且包含的网格数量一定，接着在这些网格上进行操作。该方法执行迅速，能够有效地处理大数据集，处理时间仅与划分的单元数量有关，与数据对象的数目不相关，并且输入数据的先后次序对聚类结果没有影响。

④基于密度的方法。

大多数划分方法的聚类是依据对象之间的距离，如此仅能处理球状簇，很难处理其他形状的簇。而基于密度的方法是依据对象的密度，解决了这一难题，其思想是：当某一区域的对象的密度高于设定的阈值，则将该区域内的对象合并到相近的聚类中。

习题

（1）什么是知识发现？什么是数据挖掘？它们有何关系？

（2）简述数据挖掘的基本过程。

（3）数据挖掘有哪些常用的方法和技术？