《数据挖掘导论》第四章 续3

4.6 基于关联的分类方法

关联规则挖掘是当前数据挖掘中一个重要而又活跃的研究领域。本书的第五章将要详细介绍几种主要的关联规则挖掘算法。近年来，已开始将关联挖掘方法应用到分类方法中，以获得新的数据挖掘技术。本节将要介绍基于关联的分类方法。

图-4.12  网络规则抽取过程示意描述

一种基于关联的分类方法，称为关联分类（association classification）。它主要包括两大处理步骤：第一步利用标准关联规则挖掘算法（如：Apriori 修改版本）挖掘出有关的关联规则；第二步就是基于所挖掘出的关联规则构造一个分类器。

设 D 为训练数据集，Y 为 D 中所有的类别集合。算法将符号属性映射为连续正整数，同样连续属性被离散化并作类似映射。D 中的每个数据样本是用一组属性-值对（称为项）和一个类别 y 来表示的。设 I 为 D 中所有属性-值对（项） 集合。一个关联分类规则（简称 CAR ）具有“ condset ⇒ y ”形式；其中 condset 为一组项，即有 condset ⊆ I 和 y ∈Y ，因此这类规则可以通过“< condset，y >” 形式来加以描述（简称规则项集）。

一条 CAR 规则也具有信任度c ，它表示 D 中有 c% 的样本包含属于类别 y 的 condset 。一个 CAR 规则还具有支持度 s ，它表示 D 中有 s% 的样本包含 condset 且属于类别 y 。一个 condset 的支持度为 D 中包含 condset 的样本数（记为 condsupCount ）。一个规则的支持度为 D 中包含 condset 且属于类别 y 的样本数 （记为rulesupCount）。满足最小支持度的规则项集称为频繁规则项集。若一组规则项目集具有相同的condset，那么选择其中具有最大信任度的规则作为可能规则（possible rule， 简称PR）来表示这一组规则项集。满足最小信任度的规则称为准确的。

关联分类规则挖掘方法的第一步就是发现所有的频繁和准确的可能规则 （PR），它们是类别关联规则（简称CARs）。若一个规则项目集中的 condset 包含 k 个项目，就称这一规则项目集为 k-ruleitems 。算法利用与 Apriori 算法类似的循环过程，只是用规则项集替换了其中的项。算法扫描数据库，搜索 k-ruleitems ， 对于 k = 1,2,...。直到所有频繁 k-ruleitems 均被发现出来。对每一个 k值也需要进行一次数据库扫描，利用 k-ruleitems 产生（k+1）-ruleitems。在第一遍扫描数据库后，获得 1-ruleitems 的支持度；之后就是候选 2-ruleitems （C2）。有关频繁规则项集性质的知识可以用来帮助消减候选规则项目集（小于支持度），这一知识就是：所有频繁规则项目集的子集也应是频繁规则项目集。再次扫描数据库，以确定每个候选规则项目集是否为频繁  2-ruleitems （F2）。不断重复这一过程，即利用频繁项集 Fi来产生候选项集Ci+1，直到不再发现新的频繁项集为止。满足最小信任度的频繁规则项集就构成了类别关联规则集合（CARs）。

关联分类规则挖掘第二步就是对所获得的 CARs 进行处理以便构造一个分类器。由于为获得最准确的规则集而要对所有规则子集进行检查，这样所要处理的规则数目极为庞大。因此这里采用了一个启发知识。首先定义一个规则优先概 念，即规则 ri 比规则 rj 优先，记为：。条件是：（1） ri  的信任度大于 rj 的 信任度；或（2）两规则信任度相同，但  ri  的支持度更大；或（3）  ri  和 rj 的信任度和支持度都相同，但 ri  产生的比 rj 早。算法通常选择一组能覆盖 D 中样本且具有高优先值的规则（CARs）。算法需要扫描数据库一遍以上以便确定最后的分类器。分类器对所选的规则按优先值从高到低排列。当进行分类时，先使用优先值大且满足条件的规则进行分类。此外分类器还包含一个缺省规则（具有最低优先值），当其它规则都不满足时，利用这一缺省规则对数据对象进行分类。

通常，以上介绍关联分类方法对一些数据集的测试结果，要比 C4.5 算法更准确；且（算法）上述两个步骤都具有线性可扩展性。

基于聚类的关联规则挖掘也可应用到分类问题上。关联规则聚类（简称 ARCS ）可以挖掘具有“ Aquan1 ∧ Aquan2 ⇒ Acat ”的关联规则。其中 Aquan1 和 Aquan2 是对定量属性范围的测试（这里的范围是动态决定的）； Acat 根据训练样本将一个类别（值）赋给一个符号属性。

还可以将关联规则用一个二维方格表示出来。算法扫描整个方格集合，寻找长方形规则聚类。在一个规则聚类中的相邻范围的定量属性将被合并。由 ARCS 所获得的聚类关联规则也可应用于分类问题。ARCS 的预测准确率与所使用的离散化方法有关。在可扩展性方面，ARCS 需要一块确定大小的内存，但与数据库大小无关。与 ARCS 相比，C4.5 的运算时间呈指数增长，而需要的存储空间为 数据库大小的若干倍（且需要整个放入内存中）。因此关联规则挖掘是产生准确和具有可扩展性分类器的一个重要策略。

4.7 其他分类方法

本节将要简要介绍一下其它的分类方法。这其中包括：k −最近邻分类、基于示例推理、遗传算法、粗糙集和模糊集合方法。一般而言，这些方法在商用数据挖掘系统中采用的频率要比前面所介绍的方法小许多。例如k −最近邻分类方法，需要存储所有的训练样本，这在处理大规模数据集时就会出现较大问题。而其它象基于示例推理、遗传算法和粗糙集等用于分类的方法，尚在原型研究阶段。 但这些方法正在受到越来越多的重视。

4.7.1 k-最近邻方法

k−最近邻分类器是基于类比学习的分类方法。训练样本是由 n 个数值属性所描述。每个样本代表 n 维空间中的一个点，这样所有的样本就被存放在 n 维空间中。当给定一个未知（类别）数据对象，一个 k- 最近邻分类器就搜索 n 维空间， 并从中找出 k 个与未知数据对象最为接近的训练样本，这 k 个训练样本就是未知数据对象的“k个最近邻”。所谓最近就是指 n 维空间中两点之间的欧氏距离， 而 n 维空间中两点X={x₁,x₂,...,x_n}和Y={y₁,y₂,...,y_n}之间的欧氏距离就是：

这样未知类别的数据对象就被归属于这“k个最近邻”中出现次数最多的类别。而当 k=1 时，未知类别的数据对象就被归属于最接近它的一个训练样本所具有的类别。

最近邻分类器是基于实例学习或懒惰学习（lazy learning）方法，因为它实际并没有（根据所给训练样本）构造一个分类器，而是将所有训练样本首先存储起来，当要进行分类时，就临时进行计算处理。与积极学习方法，如决策树归纳方法和神经网络方法相比，后者在进行分类前就已构造好一个分类模型；但前者， 懒惰学习方法，在当训练样本数目迅速增加时，就会导致最近邻的计算量迅速增加。因此懒惰学习方法需要有效的索引方法支持。就学习而言，懒惰学习方法比积极学习方法要快，但懒惰学习方法在进行分类时，需要进行大量的计算，因此这时它要比积极学习方法慢许多。此外与决策树归纳方法和神经网络方法不同的是，最近邻分类器认为每个属性的作用都是相同的（赋予相同权值），这样在属性集包含有许多不相关属性时，就会误导分类学习过程。

最近邻分类器也可以用于预测，也就是可以返回一个实数值作为一个未知数据对象的预测值。这时就可以取这“k个最近邻”的输出实数值（作为类别值） 的均值作为结果输出。

4.7.2 基于示例推理

基于示例推理（case_ based resoning， 简称CBR）分类器，不同于最近邻分类器，后者将训练样本存为欧氏空间中的点；而 CBR 所存储的示例常常涉及复杂的符号描述。CBR 在商业上有许多应用，如：客户服务中的问题求解，或与产品有关的故障诊断问题等。此外 CBR 还可应用于工程、法律等领域，在这些领域中示例通常都是技术设计方案或法律案件等。

当给定一个未知示例需要分类时，一个基于示例的推理器将首先检查是否有一个相同训练样本存在，若找到，则返回训练样本中所包含的解决方法；若没有相同训练样本存在，就寻找与新示例的组成有相似之处的训练样本，从某种意义上讲，这些训练样本也是（新示例的）最近邻。如果示例可以用图来表示的话， 那么这就涉及到相似子图的搜索。基于示例的推理器将试图对最近邻的若干解决方法进行合并以给出一个（针对新示例）解决方法。若各示例返回方法不兼容， 必要时还必须回溯搜索其它的解决方法。基于示例的推理器可以利用背景知识和问题求解策略来帮助获得一个可行的解决方法。

基于示例推理分类方法中所存在的问题包括：寻找相似度量方法（如子图匹 配）、开发快速索引技术和求解方法的合并等。

4.7.3 遗传运算

遗传算法借鉴了自然进化的基本思想。遗传算法学习过程说明如下：

（1）创建一个初始生物群，其中包含随机产生的规则集。每条规则可以用位串码（bits）来表示。给一个简单例子，一个给定训练样本可以用两个布尔属性 A₁ 和 A₂ ，以及两个类别 C₁ 和 C₂ 来描述。那么规则“IF A₁ and not  A₂ THEN C₂”可以表示为“100”位串；其中左边两位分别表示属性 A₁ 和 A₂ ，最右边一 位表示类别。类似地，规则“IF not A₁ and not A₂，THEN C₁”，就可表示为“001”。 若一个属性具有 k 个不同取值（k > 2 ），那么就可以使用 k 位来表示（编码）相应属性的值，同样也可以类似地进行编码。 

（2）基于适者生存的原则，根据当前生物群产生新的生物群，其中包含了更合适的规则集；这些规则一部分来自原来的规则，另一部分则是新产生的规则 （又称规则的后代）。规则的合适度（fitness）是通过对一组训练样本的分类准确率来确定的。

（3）生物群的后代则是通过利用遗传操作，如：交叉（crossover）、变异 （mutation）。在交叉操作中，来自一对规则的位串编码进行交换以形成新的一对规则。而在变异操作中，随机选择一个规则的位串编码进行求反，从而得到一个新规则。

（4）基于先前生物群（规则集）来不断产生新生物（新规则），直到生物群 P“进化”到某个阶段，即 P 中的每个规则均满足预先设置的一个阈值。

遗传算法很容易实现并行运算，也可以用于分类等优化问题的求解。在数据挖掘中，它也可用于对其它算法的适应度进行评估。