一种基于关联规则分类的改进方法

掣业业业业业簟簟业躲鬻・数据库与信息处理・弗

凑习降习降习ｌｓ习，ｓ习ｌ｝铆ｓ习ｓ习降赤

一种基于关联规则分类的改进方法

查金水宋良图刘现平

（中科院合肥智能机械研究所，合肥２３００３１）

Ｅ－ｍａｉｌ：ｃｈａｊｉｎｓｈｕｉ＠１２６．ｃｏｒｎ

要论文首先对一种基于关联规则分类的算法做出了分析。然后对算法中的类关联规则的提取方法进行了改进，得

摘

到了一种新的基于关联规则分类的算法。并结合棉花病虫害数据运行的结果对两种算法的运行效率和实用性进行了比较。关键词

关联规则

类关联规则ＦＰ－树分类

文献标识码Ａ

中图分类号ＴＰｌ８１

文章编号１００２—８３３１一（２００６）１０—０１５５—０３

ＡｎＩｍｐｒｏｖｅｄ

Ｍｅｔｈｏｄ

Ｂａｓｅｄ

ｏｎ

ＣｌａｓｓｉｆｉｃａｔｉｏｎｏｆＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓ

ＬｉｕＸｉａｎｐｉｎｇ

ＺｈａＪｉｎｓｈｕｉ

ＳｏｎｇＬｉａｎｇｔｕ

（ＩｎｓｔｉｔｕｔｅｏｆＩｎｔｅｌｌｉｇｅｎｔＭａｃｈｉｎｅｓ．ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ。Ｈｅｆｅｉ２３００３１）

Ａｂｓｔｒａｃｔ：Ｆｒｏｍｅｘｔｒａｃｔｉｏｎｉｎ

ｔｈｉｓ

ａ

ｃｏｎｃｒｅｔｅ

ａｎａｌｙｓｉｓ

ｏｆｔｈｅｃｌａｓｓｉｆｉｅｄ

ａ

ａｌｇｏｒｉｔｈｍ

ｂａｓｅｄ

ｏｎ

ａｓｓｏｃｉａｔｉｏｎｒｕｌｅ，ｗｅｃｌａｓｓｉｆｉｃａｔｉｏｎｂｅｔｗｅｅｎ

ｔｈｅ

ｍａｋｅ

ｆｏｒｉｍｐｒｏｖｅｍｅｎｔｏｆ

ｍｅｔｈｏｄｉｎ

ａ

ｃｌａｓｓａｓｓｏｃｉａｔｉｏｎｃｏｍｐａｒｉｓｏｎ

ｒｕｌｅｓａｎｄ

ｎｅｗａｌｇｏｒｉｔｈｍｂａｓｅｄｐｒａｃｔｉｃａｂｉｌｉｔｙ

ｉｓ

ｏｎ

ｏｆａｓｓｏｃｉａｔｉｏｎ

ｔｗｏ

ｒｕｌｅｓｉｓ

ａｃｑｕｉｒｅｄ

ｔｏ

ｐａｐｅｒ．Ｔｈｅｎ

ｏｆｅｆｆｉｃｉｅｎｃｙ

ａｎｄ

ｍａｄｅ

ａｌｇｏｒｉｔｈｍｓａｃｃｏｒｄｉｎｇ

ｔｈｅ

ｏｐｅｒａｔｉｏｎｒｅｓｕｌｔｏｆ

ｃｏｔｔｏｎｄｉｓｅａｓｅｄａｔａ．

Ｋｅｙｗｏｒｄｓ：ａｓｓｏｃｉａｔｉｏｎｒｕｌｅ，ｃｌａｓｓａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ，Ｆｒｅｑｕｅｎｔ－ｐａｔｔｅｒｎｔｒｅｅ，ｃｌａｓｓｉｆｉｃａｔｉｏｎ

１

引言

对于一些大的数据库来说，建立一个精确而又有效的分类

（２）产生所有的类关联规则。

（３）基于已经产生的类关联规则建立一个分类器。（４）利用分类器对未知类别数据进行分类。

如图１所示，我们首先假设数据集是一个正常的关系表。这个表中包含了带有￡个不同属性值的Ⅳ个案例，这，ｖ个案例已经被划分为ｑ个已知的类。属性值可以是离散的也可以是连续的。对于一个连续的属性值，我们首先将其值的区间离散化成许多小区间。然后再将这些小的区间映射到一系列连续的整型值。

器是数据挖掘和机器学习的一个重要任务——给定一个带有

类别标签的测试数据集，用它来建立一个分类器，然后预测那些未知类别的数据对象。现在的许多分类方法都是基于启发式的搜索技术，比如决策数算法［１】、Ｂａｙｅｓ网络和一些统计学的方法。还有一些在商业化的数据挖掘领域内很少用到的方法，诸如ｋ一最近邻分类、基于案例的推理、遗传算法等。

分类规则的挖掘和关联规则脚的挖掘是两种重要的数据挖掘技术。分类规则挖掘的目标就是找出数据库中的一些规则，组成一个精确的分类器。而关联规则的挖掘就是找出数据库中满足最小支持度与最小确信度约束的规则。对关联规则来说，它的目标是没有预先确定的。而对分类规则的挖掘来说，它有一个预先确定的唯一的目标，即类别标签。分类规则和关联规则的挖掘在实际中都是不可缺少的。因此，数据挖掘技术也已将关联规则挖掘用于分类问题［３１。将两种挖掘技术结合起来对使用者来说既节省时间又方便很多。这两种技术的结合可以产生一种新的分类方法：基于关联规则的分类。在关联规则分类中，规则的右侧固定为类别的属性。我们将这些规则称为类关

联规则（ｃｌａｓｓａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ，ＣＡＲｓ）［４１。

鲞墨鍪塑查，主磊丽网查登塑型苎塑竺差

离散化

产生类关联规则

选择

测试结果分析ｒ

分类

、输入测试数据

建立分类器

优化分类器

●ｒ

＿－－●

图ｌ基于关联规则分类的流程图

设Ｄ为事务集．，是Ｄ中所有项目的集合、ｌ，是类别标签的集合。如果Ｘ∈ｄ，我们称一个数据项ｄ∈Ｄ包含Ｘ∈，，，是数

据项Ｄ的子集。一个类关联规则（ＣＡＲ）就是下面的形式Ｘ—

ｙ，其中Ｘ∈，、Ｙ∈Ｙ。它的支持度与确信度的定义如下：规则Ｒ：

数据挖掘中类关联规则的挖掘主要包括下面几个步骤（如

图１所示）：

Ｘ—ｙ的支持度ｓｕｐ是指Ｄ中有ｓ％的案例包含有带有类别标

签ｙ的项目Ｘ。ｓｕｐ与Ｄ中的含有Ｘ的案例数之比称为确信度

‘

（１）如果是连续的属性值，需要将其离散化。

基金项目：国家８６３高技术研究发展计划资助项目（编号：２００３ＡＡｌ１８０７０）

作者简介：查金水（１９７８一），男，硕士研究生，主要研究方向：数据挖掘，复杂系统。宋良图（１９６３一），男，副研究员，主要研究方向：智能化农业信息系

统。刘现平（１９７９一），男，硕士研究生，主要研究方向：图像检索系统，图形与图像处理。

计算机工程与应用２００６．１０

１５５

万方数据　

ｃｏｎｆｏ我们的目标就是根据使用者给定的最小支持度ｍｉｎｓｕｐ和最小置信度ｍｉｎｃｏｎｆ阀值来产生所有的ＣＡＲｓ集，然后根据产生的ＣＡＲｓ建立一个分类器。

２

ＣＢＡ算法的描述

ＣＢＡ算法阁包含两个步骤：类关联规则的产生和分类器的

建立。２．１

基本概念

产生规则的首要条件就是要找出所有大于最低支持度阀

值的规则。一个规则项ｒｕｌｅｉｔｅｍ的形式如下：＜ｃｏｎｄｓｅｔ，ｙ＞。这里的ｃｏｎｄｓｅｔ是一项集．ＹＥＹ是一个类别标签。Ｃｏｎｄｓｅｔ的支持度（ｃｏｎｄｓｕｐＣｏｕｎｔ）是指Ｄ中包含ｃｏｎｄｓｅｔ的数。规则项ｒｕｌｅｉｔｅｍ的支持度（ｒｕｌｅｓｕｐＣｏｕｎｔ）是指Ｄ中类别标签是Ｙ的ｃｏｎｄｓｅｔ的数。每一个ｒｕｌｅｉｔｅｍ可以表示一条规则：ｃｏｎｄｓｅｔ－－－＊ｙ。它的支持度是（ｒｕｌｅｓｕｐＣｏｕｎｔ／ＩＤＩ）４１００％，这里ｌＤＩ是数据集的大小。它的确信度是（ｒｕｌｅｓｕｐＣｏｕｎｔ／ｃｏｎｄｓｕｐＣｏｕｎｔ）４１００％。

对于有同样ｃｏｎｄｓｅｔ的项集来说。确信度最高的将被选为可能的规则ＰＲ（ｐｏｓｓｉｂｌｅｒｕｌｅｓ）来代表这个项集。如果有超过一个的项集具有相同的最高的确信度，我们将随机的选择一个项集。如果一条规则的确信度大于最低确信度阀值，我们说这条规则是精确的。而类关联规则集就是包含那些既频繁又精确的

所有的ＰＲ。

２．２产生类关联规则

ＣＢＡ产生类关联规则的算法ＣＢＡ—ＲＧ如下：

１ＦＩ＝｛ｌａｒｇｅ１－ｒｕｌｅｉｔｅｍｓ｝；２ＣＡＲｌ＝ｇｅｍＲｕｌｅｓ（‘）；

３ｐｒＣＡＲｌ＝ｐｒｕｎｅＲｕｌｅｓ（ＣＡＲｌ）；

４ｆｏｒ（ｋ＝２；Ｒ—ｌ≠∥；＾＋＋）ｄｏ５Ｇ＝ｃａｎｄｉｄａｔｅＧｅｎ（疋一１）；

６ｆｏｒｅａｃｈｄａｔａ

ｃａｓｅ

ｄ∈Ｄ

ｄｏ

７Ｑ＝ｒｕｌｅＳｕｂｓｅｔ（ｑ，ｄ）；

８ｆｏｒｅａｃｈｃａｎｄｉｄａｔｅ

ｃ∈ｑｄｏ

９ｃ．ｃｏｎｄｓｕｐＣｏｕｎｔ＋＋；

１０ｉｆｄ．ｃｌａｓｓ＝ｃ．ｃｌａｓｓｔｈｅｎｃ．ｒｕｌｅｓｕｐＣｏｕｎｔ＋＋１１ｅｎｄ

１２ｅｎｄ１３Ｅ＝（ｃ∈ＱＩｃ．ｒｕｌｅｓｕｐＣｏｕｎｔ≥ｍｉｎｓｕｐ）；

１４ＣＡＲ女＝ｇｅｎＲｕｌｅｓ（Ｅ）；１５

ｐｒＣＡＲ＾＝ｐｒｕｎｅＲｕｌｅｓ（ＣＡＲＩ）；１６ｅｎｄ１７

ＣＡＲｓ＝Ｌ）ｋＣＡＲ＾；

１８ｐｒＣＡＲｓ＝ＵＩｐｒＣＡＲＩ；

由上述的算法可以看出，在算法的每个循环中都要进行四个主要的操作。如在第ｋ循环中，首先通过第南一１循环中的频繁项集疋一。来产生频繁候选ｋ项集Ｃｋ，这一步主要是通过使用了ｃａｎｄｉｄａｔｅＧｅｎ函数来实现。接着扫描数据库来更新Ｃ。中各个候选集的支持度计数，然后这些新的频繁项组成新的Ｅ。算

法使用ｇｅｎＲｕｌｅｓ函数来产生规则ＣＡＲ。。最后使用对这些ＣＡＲ。

规则进行剪枝。

２．３建立分类器

为了在已经获得的规则上面建立一个最好的分类器，需要选择那些错误最少的规则。设Ｒ是所有已经产生的规则，Ｄ是

１５６

２００６．１０计算机工程与应用

万　

方数据训练数据。算法的基本目的就是从Ｒ中选择一些优先度比较高的规则来替代Ｄ。在这里优先度的定义为：给定两条规则，ｒ．和‘，■＞ｒＪ（即■的优先度比ｌ高）需满足下列条件：

（１）如果ｔ的确信度比一的高，或

（２）两者的确信度相同，但是一的支持度比‘的大，或（３）两者的确信度和支持度相同，但ｒ，产生的比ｒｉ早（也就是在规则的左手边ｒ．有更少的属性）；

我们建立的分类器的形式如下：

口１，１＂２，…，ｒ，ｄｅｆａｕｌｔ＿ｃｌａｓｓ＞，这里‘ｅＲ，如果ｂ＞ａ，则Ｌ＞ｒ６。ｄｅｆａｕｌｔ＿ｃｌａｓｓ是默认的类。在对一条未知类别的案例进行分类时，第一条满足这个案例的规则即可以分类这个案例。如果没有规则满足。则将这个案例归为默认的类。

分类器的建立有三个步骤：

（１）对所有Ｒ中的规则根据关系按降序排列。这确保我们的分类器可以选到优先度最高的规则。

（２）对于每条规则ｒ∈Ｒ，我们到Ｄ中去寻找可以被ｒ替代（即它们满足规则ｒ的左手边属性值）的案例，如果ｒ至少可以正确分类，即可以替代，一个案例，它将是我们分类器的一条潜在的规则。对于那些可以被分类的案例将其从Ｄ中移出来。对于Ｄ中那些不能被规则ｒ替代的案例．我们用ｄｅｆａｕｌｔ＿ｃｌａｓｓ来标识。然后来计算由分类器和默认的类别号分类的错误的案例数。这里的ｄｅｆａｕｌｔ＿ｃｌａｓｓ是指Ｄ中剩余案例中大部分案例所属

的那个类。

（３）将分类器中那些不能增加分类器准确率的规则抛弃，剩下的未被抛弃的规则和ｄｅｆａｕｌｔ＿ｃｌａｓｓ一起组成我们的分类器。具体的算法参见［５］。

３改进的基本措施

由上述对ＣＢＡ算法的描述我们可以看出．类关联规则的产生算法与Ａｐｒｉｏｆｉ算法类似。与Ａｐｒｉｏｒｉ不同的是在算法过程中要对两项进行支持度的计算，即ｃｏｎｄｓｅｔ和ｒｕｌｅｉｔｅｍ。这个主要是为了后面可以计算ｒｕｌｅｉｔｅｍ的确信度。以前针对ＣＢＡ算法的一些改进主要是集中在ＣＢＡ—ＲＧ阶段．为了使数据库可以一次性的载入到内存中，对数据库进行划分，每部分采用单独的支持度计数。它对于数据库的划分和规则的产生采用不同的算法，选择效率最高的一个［６１。

在类关联规则的挖掘过程中，由于采用了Ａｐｒｉｏｒｉ算法同，需要不断地产生候选集，虽然利用Ａｐｒｉｏｒｉ性质，可以对候选集进行缩减以达到提高挖掘效率的目的，仍然存在两个问题：（１）产生的候选集过多；（２）需要对数据库进行反复扫描，通过一定的模式匹配的方式对大量候选集进行检验。为了避免产生的候选集过多．以及提高挖掘的效率，我们提出了一个新的基于关

联规则分类的算法——ＮＣＢＡ。

为了发现分类规则，ＮＣＢＡ首先挖掘训练数据，通过支持度和置信度阀值来发现所有的频繁项集。这也是一个典型的频繁模式关联规则挖掘任务。为了使挖掘的效率更高，ＮＣＢＡ算法使用ＦＰ一树［８１算法。ＦＰ一树的频繁模式生成方法比Ａｐｒｉｏｒｉ类的方法更快，特别是对于大数据集、低的支持度阀值、长模式来说效率更高。通过使用ＦＰ一树挖掘类关联规则来改进ＣＢＡ算法的主要思想通过如下的例子来说明：

给定一个如表１所示的训练数据集ｒ。假定设最小支持度阀值是２，确信度阀值是５０％。我们首先对数据集ｒ进行扫描

一次，然后找出那些支持度大于２的那些项，项集肚ｋ，ｄ∥ｋ｝

称为频繁项集。其它的支持度小于最小支持度的项不能在关联规则中起到作用。所以将被剪枝。

表ｌ调练数据集

然后对Ｆ中的项，按照支持度计数的降序排列，排列的结果是Ｆ—ｌｉｓｔ＝ａ—ｄ一户ｋ。然后再扫描一次训练数据集来构建一棵ＦＰ一树（如图２所示）。先创建树的根结点，用Ｎｕｌｌ表示。接着我们按照Ｆ—ｌｉｓｔ中出现的项和项的顺序对训练数据集中的每个元组进行选取。例如：在第一个元组中，只有（ａ，，）出现在Ｆ—ｌｉｓｔ中．将其选取出来，作为最左边的一个分枝插入到树中。类别标签放在路径的最后一个节点上。

在训练集中的元组将会在树中分享一个共同的前缀。例如，第二个元组的属性值（ｎ，ｄ；，）。这样在Ｆ—ｌｉｓｔ中将会和第一个元组分享同一个前缀ａ。因此在ＦＰ一树中也同时分享最左边分枝的ａ的子路。所有相同属性值的节点作为一个队列从头节点开始连起来。

根据Ｆ—ｌｉｓｔ．我们可以将类关联规则集划分为无重复的四个子集：（１）含有ｋ的集；（２）含有厂但是不含有ｋ的集；（３）含有ｄ但不含有ｋ和厂的集；（４）只含有ａ的集。

图２ＦＰ一树

图３合并节点ｋ之后的ＦＰ－树

为了找到含有ｋ的子集的规则，我们观察ＦＰ一树，遍历含有ｋ指针的节点组成一个后一ｄｂ数据库．我们可以发现危一ｄｂ含有三个元组：（ａ，ｄ，厂，ｋ）：Ｃ，（ａ，ｄ，ｋ）：Ｃ，ｋ：Ａ，这就是所有含有ｋ的元组。在训练集中找出所有含有的频繁模式的问题就简化为在詹一ｄｂ数据库中挖掘频繁模式。

由上述可知．在｜｜｝一ｄｂ中，ａ和ｄ都是频繁的属性值，因为它们都大于或等于支持度的门槛值。又因为在｜ｊ｝一ｄｂ中，ｋ在每一个元组中都出现，因此必定是频繁的。所以我们也不需要计算ｋ的支持度。我们可以通过循环的构造ＦＰ一树和ｄｂ数据库来挖掘ｄｂ数据库中的类关联规则。

在七一ｄｂ数据库中，ａ和ｄ正好都是同时出现，因此ｎｄ是一个频繁模式。ａ和ｄ是以的两个子集，与甜有相同的支持

度。基于类别标签的信息，我们可以产生三条规则：ⅡＪ｝一Ｃ，幽一

Ｃ，觎一Ｃ。它们三个的支持度皆为２、确信度皆为１００％。

在搜寻到所有的含有ｋ的规则之后．所有的ｋ的节点都分

万　

方数据别和它们各自的父节点合并。也就是说在ｋ结点中的类别标签将在其父节点的标注。缩减之后的树如图３所示。余下的规则的提取同上述的类似。

由此我们可以看出，在对树的挖掘过程中．将原有的发现较长频繁模式的问题转化为反复寻找较短的模式而后再连接其前缀的过程。因此和ＣＢＡ中采用的Ａｐｒｉｏｆｉ算法相比，不必重复扫描数据库。可以降低搜索成本，极大的提高效率。

由于ＦＰ一树在扫描数据库的过程中，需要将数据库一次性装入内存中来构建树。因此对机器的内存有一定的要求，如果数据库比较大的话，我们可以首先对数据库进行分割，然后再对每一个分割后的数据库用ＦＰ一树算法提取类关联规则。

４实验结果及分析

我们采用了某一地区的棉花病虫害数据为例测试算法的效果。本实验以Ｄｅｌｐｈｉ６，０为开发环境，数据存储在ａｃｃｅｓｓ数据库中，即为分类的样本空间。部分数据如图４所示。

图４棉花病虫害数据

由图４可以看出，我们将前面四个属性：病斑颜色、病害部位、病害形状、病害特征作为ｃｏｎｄｓｅｔ集，最后的一个属性：病的种类作为类别标签ｙ。然后我们对数据进行转化，将这些文本数据转化为布尔型数据，以方便规则的挖掘。接着选定ｍｉｎ—得到的类关联规则建立分类器。我们使用样本中的９０％的数据为训练数据。其余的为测试数据。图５即为得到的分类器中的类关联规则。

图５

训练样本为９０％时得到的分类器中的类关联规则

我们分别使用了三组数据进行了测试，样本数分别为４０、

０００个。两种算法测试比较的结果如表２所示。

表２两种算法运行时间比较ｓ

由实验结果可以看出，随着样本数目的增加，ＮＣＢＡ算法（下转２０３页）

计算机工程与应用２００６．１０

１５７

ｓｕｐ＝１５％，ｍｉｎｃｏｎｆ＝８０％来进行类关联规则的挖掘，然后对挖掘的运行时间明显比ＣＢＡ算法少，效率增加。随着数据库的不断增大，ＣＢＡ算法运行效率低的瓶颈就暴露出来了。因此改进后

２００和１

表ｌ几种方法的检测结果比较

图像序号实有目标数目ＣＡ—ＣＦＡＲ结果Ｇ０一ＣＦＡＲ结果本文方法结果

１１７１７１５１７

２１４１３１４１４

３２３２１２０２３

（ａ）原始图象

（ｂ）ＣＡ—ＣＦＡＲ检测结果

６结论

本文提出了一种在ＳＡＲ图像中检测目标的方法。该方法采用基于ｗｅｉｂｕｌｌ分布模型的ＣＦＡＲ检测技术，对背景区域分块，根据每个子块的统计参数和空间分布，确定子块类型，根据各子块类型不同，选择不同的参考单元确定阈值。同时根据目标灰度、方差特征剔除明显不可能为目标的像素，利用多数滤

（ｅ）本文ＣＦＡＲ方法检测结果

（ｄ）本文方法最终结果

波器和目标形状特征，进一步排除虚警。相比于ＣＡ—ＣＦＡＲ方法．本文方法保留了算法简单、同质区检测性能好的优点，同时．对存在杂波边缘或多目标干扰的情况，也能有很好的检测效果。实验证明本文方法检测性能好，自适应性强，适应于大多数ＳＡＲ图像的目标检测。（收稿日期：２００５年９月）

图５实验结果图像

检测结果中，ＣＡ—ＣＦＡＲ方法有２个虚警、２个漏警，本文方法有１个虚警，无漏警，且轮廓的完整性保持更好。可以看出，本文方法相比ＣＡ—ＣＦＡＲ方法，具有更好的检测效果，说明该方法是有效的。对检测结果进一步判别。虚警目标被滤除，得

到目标的ＲＯＩ。

参考文献

１．Ｑｕｏｏ

Ｈ

Ｐｈａｍ，ＴｉｍｏｔｈｙＭＢｍｓｎａｎ，Ｍａｒｋ

Ｔａｒｇｅｔｓｉｎ

ＳＡＲ

ＪＴＳｍｉｔｈ．ＭｕｌｔｉｓｔａｇｅＡｌｇｏ－

表ｌ给出了三种方法在其他几幅图像的检测结果，比较得出：ＣＡ—ＣＦＡＲ和ＧＯ—ＣＦＡＲ分别只对部分图像有较好的检测效果，本文方法对所有图像都有较好检测效果。在背景平稳区域，本文方法性能接近ＣＡ—ＣＦＡＲ；在杂波边缘，ＣＡ—ＣＦＡＲ虚警增多，而本文方法较好地抑制了虚警，检测性能接近Ｇ０一ＣＦＡＲ；在多目标区域，ＣＡ—ＣＦＡＲ由于目标间的相互干扰，检测出目标轮廓不完整甚至漏警，本文方法由于自动排除了干扰目标影响，比ＣＡ—ＣＦＡＲ和ＧＯ—ＣＦＡＲ具有更好的检测效果。在一幅图像中．杂波边缘和多目标情况经常可能同时存在，ＣＳＳ０一ＣＦＡＲ或ＣＳＧＯ—ＣＦＡＲ方法只是单纯地选大或者选小，不能对图象灰度分布变化自适应，当图像复杂时难以有好的效果。本方法的最大优势在于结合了各种方法的优点，智能判定区域类型。在各种复杂环境下都具有较好的检测性能。

（上接１５７页）

ｒｉｔｈｍｆｏｒＤｅｔｅｃｔｉｏｎｏｆ

Ｉｍａｇｅ

Ｄａｔａ［ｊ］．ＳＰＩＥ，１９９７；３０７０

２．王世锦，孟健青．单元筛选后作最小选择的ＣＦＡＲ自适应检测器【Ｊ】．雷达与对抗．２００４；（４）

３．贾承丽．计科峰，匡纲要等．利用ＧａｍｍａＣＦＡＲ进行ＳＡＲ图像目标检测［Ｊ】．系统工程与电子技术，２００５；（１）

４．何友，关键，孟祥伟．雷达自动检测和ＣＦＡＲ处理方法综述忉．系统工程与电子技术，２００１；２３（１）

５．ＭｉｃｈａｅｌＢａｓｅｄ

Ｅｌｅｃｔ

ｏｎ

ＥＳｍｉｔｈ．Ｐｒａｍｏｄ

Ｄａｔａ

Ｋ

Ｖａｒｓｈｎｅｙ．Ｉｎｔｅｌｌｉｇｅｎｔ

Ｔｒａｎｓａｃｔｉｏｎｓ

ｏｎ

ＣＦＡＲＰｒｏｃｅｓｓｏｒ

ａｎｄ

Ｖａｒｉａｂｉｌｉｔｙ［Ｊ】．ＩＥＥＥ

Ａｅｒｏｓｐａｃｅ

ｔｏｎｉｃＭｉｎｇ

Ｓｙｓｔｅｍｓ，２０００Ｗｏｎｇ，Ｃｈｅｅ

Ｈａｎｇ

Ｃｈａｎｇ，Ｗｅｉｘｉａｎ

Ｉｎｔｅｒｎａｔｉｏｎａｌ

Ｌｉｕ

ｅｔ

６．Ｃｈａｒ

ｉｎ

ａ１．ＣＡ—ＣＦＡＲ

ｏｎ

ｗｅｉｂｕｌｌ

Ｂａｃｋｇｒｏｕｎｄ［Ｃ］．Ｉｎ：２ｎｄ

ＣｏｎｆｅｒｅｎｃｅＭｉ—

ｃｒｏｗａｖｅ７．Ｍ

ａｎｄＭｉｌｌｉｍｅｔｅｒＷａｖｅ

ＴｅｃｈｎｏｌｏｇｙＰｒｏｃｅｅｄｉｎｇｓ，２０００

Ｓｋｏｌｎｉｋ．Ｒａｄａｒ

Ｈａｎｄｂｏｏｋ［Ｍ］．２ｎｄｅｄｎ．，ＭｃＧｒａｗＨｉｌｌ，ｌ９９０

Ｄａｔａｂａｓｅｓ［Ｃ］．Ｉｎ：ＰｒｏｃｏｆｔｈｅＡＣＭＳＩＧＭＯＤ

ｏｎ

ＳｅｔｓｏｆＩｔｅｍｓ

ｉｎ

Ｌａｒｇｅ

的ＮＣＢＡ算法的实际应用性也较ＣＢＡ有了很大的提高。

Ｉｎｔｅｒｎａｔｉｏｎａｌｃｏｎｆｅｒｅｎｃｅ

Ｍａｎａｇｅｍｅｎｔ

ｏｆ

Ｄａｔａ，Ｗａｓｈｉｎｇｔｏｎ

Ｄ

Ｃ，

１９９３：２０７～２１６

５

结论

本文通过对基于关联规则的分类方法ＣＢＡ的分析，指出

３．ＨａｎＪＷ，ＫａｍｂｅｒＭ．数据挖掘：概念与技术【Ｍ］．北京：机械工业出版

社．２００ｌ

４．ＬｅｎｔＢ，ＳｗａｍｉＡ，ＷｉｄｏｍＪ．Ｃｌｕｓｔｅｒｉｎｇ

ｔｈｅ

１３“Ｉｎｔｅｒｎａｔｉｏｎａｌ

Ｃｏｎｆｅｒｅｎｃｅ

ｏｎ

ａｓｓｏｃｉａｔｉｏｎ

ｒｕｌｅｓ［Ｃ］．Ｉｎ：Ｐｒｏｃｏｆ

它的效率不足之处：它需要反复扫描数据库，而且会产生大量的候选集，通过一定的模式匹配方法对大量候选集进行检验。我们新的ＮＣＢＡ算法通过使用ＦＰ一树来提取类关联规则，由于ＦＰ一树算法比较简单．只需扫描一遍数据库，可以将较长的频繁模式转化为先寻找较短的模式而后再连接其前缀的过程。有效的降低了搜索成本。通过对算法的改进使运行效率有了很大的提高，并举例说明了获取类关联规则的具体过程。最后通过一个实际的例子说明两种算法的效果，证明了改进后算法的实用性和效率都有了很大的提高。（收稿日期：２００５年１１月）

Ｄａｔａ

Ｅｎｇｉｎｅｅｒｉｎｇ，Ｂｉｒｍｉｎｇｈａｍ，

１９９７：２２０～２３１５．Ｌｉｕ

Ｂ，Ｈｓｕ

Ｗ，ＭａＹ．ＩｎｔｅｇｒａｔｉｎｇＣｌａｓｓｉｆｉｃａｔｉｏｎａｎｄ

ＡｓｓｏｃｉａｔｉｏｎＲｕｌｅ

ｏｎ

Ｍｉｎｉｎｇ［Ｃ］．Ｉｎ：Ｐｒｏｃｏｆｔｈｅ４ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ

Ｄｉｓｃｏｖｅｒｙ

Ｋｎｏｗｌｅｄｇｅ

ａｎｄＤａｔａ

Ｍｉｎｉｎｇ，ＮｅｗＹｏｒｋ，１９９８

Ｋ．Ｉｍｐｒｏｖｉｎｇ

ａｎ

６．ＬｉｕＢ．Ｍａ

Ｙ，Ｗｏｎｇ

ＡｓｓｏｃｉａｔｉｏｎＲｕｌｅ

ｏｎ

ＢａｓｅｄＣｌａｓｓｉ—Ｐｒｉｎｃｉｐｌｅｓ

ｔｉｅｒ［Ｃ］．Ｉｎ：Ｐｒｏｃｏｆｔｈｅ４ｔｈＥｕｒｏｐｅａｎＣｏｎｆｅｒｅｎｃｅ

Ｐｒａｃｔｉｃｅ

ｏｆＲ

ａｎｄ

ＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙ

ｉｎ

Ｄａｔａｂａｓｅｓ，Ｌｙｏｎ，２０００

Ｍｉｎｉｎｇ

ｏｎ

７．Ａｇｒａｗａｌ

２ＳｒｉｋａｎｔＲ．ＦａｓｔＡｌｇｏｒｉｔｈｍｓｆｏｒ

Ａｓｓｏｃｉａｔｉｏｎ

Ｒｕｌｅｓ［Ｃ】．

Ｉｎ：Ｐｒｏｃｏｆｔｈｅ２０ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ

ＶｅｒｙＬａｒｇｅＤａｔａｂａｓｅｓ．

参考文献

１．ＱｕｉｎｌａｎＪ—Ｒ．Ｃ４．５：Ｐｒｏｇｒａｍｓ

ｆｏｒ

Ｓａｎｔｉａｇｏ，Ｃｈｉｌｅ，１９９４；９：４８７～４９９

８．Ｈａｎ

ＭａｃｈｉｎｅＬｅａｒｎｉｎｇ．Ｃａｌｉｆｏｒｎｉａ：Ｍｏｒｇａｎ

Ｊ

Ｗ．ＰｅｉＪ，ＹｉｎＹ．ＭｉｎｉｎｇＦｒｅｑｕｅｎｔＰａｔｔｅｒｎｓｗｉｔｈｏｕｔＣａｎｄｉｄａｔｅ

Ｋａｕｆｍａｎｎ，１９９３

２．Ａｇｒａｗａｌ

Ｒ，ＩｍｉｅｌｉｎｓｋｉＴ，Ｓｗａｍｉ

Ａ．ＭｉｎｉｎｇＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓｂｅｔｗｅｅｎ

Ｇｅｎｅｒａｔｉｏｎ［Ｃ］．Ｉｎ：Ｐｒｏｃｏｆ１９“ＡＣＭＳＩＧＭＯＤＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ

ｏｎ

ＭａｎａｇｅｍｅｎｔｏｆＤａｔａ，Ｄａｌｌａｓ，２０００：２０７－２１６

计算机工程与应用２００６．１０

２０３

万方数据　

掣业业业业业簟簟业躲鬻・数据库与信息处理・弗

凑习降习降习ｌｓ习，ｓ习ｌ｝铆ｓ习ｓ习降赤

一种基于关联规则分类的改进方法

查金水宋良图刘现平

（中科院合肥智能机械研究所，合肥２３００３１）

Ｅ－ｍａｉｌ：ｃｈａｊｉｎｓｈｕｉ＠１２６．ｃｏｒｎ

要论文首先对一种基于关联规则分类的算法做出了分析。然后对算法中的类关联规则的提取方法进行了改进，得

摘

到了一种新的基于关联规则分类的算法。并结合棉花病虫害数据运行的结果对两种算法的运行效率和实用性进行了比较。关键词

关联规则

类关联规则ＦＰ－树分类

文献标识码Ａ

中图分类号ＴＰｌ８１

文章编号１００２—８３３１一（２００６）１０—０１５５—０３

ＡｎＩｍｐｒｏｖｅｄ

Ｍｅｔｈｏｄ

Ｂａｓｅｄ

ｏｎ

ＣｌａｓｓｉｆｉｃａｔｉｏｎｏｆＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓ

ＬｉｕＸｉａｎｐｉｎｇ

ＺｈａＪｉｎｓｈｕｉ

ＳｏｎｇＬｉａｎｇｔｕ

（ＩｎｓｔｉｔｕｔｅｏｆＩｎｔｅｌｌｉｇｅｎｔＭａｃｈｉｎｅｓ．ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ。Ｈｅｆｅｉ２３００３１）

Ａｂｓｔｒａｃｔ：Ｆｒｏｍｅｘｔｒａｃｔｉｏｎｉｎ

ｔｈｉｓ

ａ

ｃｏｎｃｒｅｔｅ

ａｎａｌｙｓｉｓ

ｏｆｔｈｅｃｌａｓｓｉｆｉｅｄ

ａ

ａｌｇｏｒｉｔｈｍ

ｂａｓｅｄ

ｏｎ

ａｓｓｏｃｉａｔｉｏｎｒｕｌｅ，ｗｅｃｌａｓｓｉｆｉｃａｔｉｏｎｂｅｔｗｅｅｎ

ｔｈｅ

ｍａｋｅ

ｆｏｒｉｍｐｒｏｖｅｍｅｎｔｏｆ

ｍｅｔｈｏｄｉｎ

ａ

ｃｌａｓｓａｓｓｏｃｉａｔｉｏｎｃｏｍｐａｒｉｓｏｎ

ｒｕｌｅｓａｎｄ

ｎｅｗａｌｇｏｒｉｔｈｍｂａｓｅｄｐｒａｃｔｉｃａｂｉｌｉｔｙ

ｉｓ

ｏｎ

ｏｆａｓｓｏｃｉａｔｉｏｎ

ｔｗｏ

ｒｕｌｅｓｉｓ

ａｃｑｕｉｒｅｄ

ｔｏ

ｐａｐｅｒ．Ｔｈｅｎ

ｏｆｅｆｆｉｃｉｅｎｃｙ

ａｎｄ

ｍａｄｅ

ａｌｇｏｒｉｔｈｍｓａｃｃｏｒｄｉｎｇ

ｔｈｅ

ｏｐｅｒａｔｉｏｎｒｅｓｕｌｔｏｆ

ｃｏｔｔｏｎｄｉｓｅａｓｅｄａｔａ．

Ｋｅｙｗｏｒｄｓ：ａｓｓｏｃｉａｔｉｏｎｒｕｌｅ，ｃｌａｓｓａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ，Ｆｒｅｑｕｅｎｔ－ｐａｔｔｅｒｎｔｒｅｅ，ｃｌａｓｓｉｆｉｃａｔｉｏｎ

１

引言

对于一些大的数据库来说，建立一个精确而又有效的分类

（２）产生所有的类关联规则。

（３）基于已经产生的类关联规则建立一个分类器。（４）利用分类器对未知类别数据进行分类。

如图１所示，我们首先假设数据集是一个正常的关系表。这个表中包含了带有￡个不同属性值的Ⅳ个案例，这，ｖ个案例已经被划分为ｑ个已知的类。属性值可以是离散的也可以是连续的。对于一个连续的属性值，我们首先将其值的区间离散化成许多小区间。然后再将这些小的区间映射到一系列连续的整型值。

器是数据挖掘和机器学习的一个重要任务——给定一个带有

类别标签的测试数据集，用它来建立一个分类器，然后预测那些未知类别的数据对象。现在的许多分类方法都是基于启发式的搜索技术，比如决策数算法［１】、Ｂａｙｅｓ网络和一些统计学的方法。还有一些在商业化的数据挖掘领域内很少用到的方法，诸如ｋ一最近邻分类、基于案例的推理、遗传算法等。

分类规则的挖掘和关联规则脚的挖掘是两种重要的数据挖掘技术。分类规则挖掘的目标就是找出数据库中的一些规则，组成一个精确的分类器。而关联规则的挖掘就是找出数据库中满足最小支持度与最小确信度约束的规则。对关联规则来说，它的目标是没有预先确定的。而对分类规则的挖掘来说，它有一个预先确定的唯一的目标，即类别标签。分类规则和关联规则的挖掘在实际中都是不可缺少的。因此，数据挖掘技术也已将关联规则挖掘用于分类问题［３１。将两种挖掘技术结合起来对使用者来说既节省时间又方便很多。这两种技术的结合可以产生一种新的分类方法：基于关联规则的分类。在关联规则分类中，规则的右侧固定为类别的属性。我们将这些规则称为类关

联规则（ｃｌａｓｓａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ，ＣＡＲｓ）［４１。

鲞墨鍪塑查，主磊丽网查登塑型苎塑竺差

离散化

产生类关联规则

选择

测试结果分析ｒ

分类

、输入测试数据

建立分类器

优化分类器

●ｒ

＿－－●

图ｌ基于关联规则分类的流程图

设Ｄ为事务集．，是Ｄ中所有项目的集合、ｌ，是类别标签的集合。如果Ｘ∈ｄ，我们称一个数据项ｄ∈Ｄ包含Ｘ∈，，，是数

据项Ｄ的子集。一个类关联规则（ＣＡＲ）就是下面的形式Ｘ—

ｙ，其中Ｘ∈，、Ｙ∈Ｙ。它的支持度与确信度的定义如下：规则Ｒ：

数据挖掘中类关联规则的挖掘主要包括下面几个步骤（如

图１所示）：

Ｘ—ｙ的支持度ｓｕｐ是指Ｄ中有ｓ％的案例包含有带有类别标

签ｙ的项目Ｘ。ｓｕｐ与Ｄ中的含有Ｘ的案例数之比称为确信度

‘

（１）如果是连续的属性值，需要将其离散化。

基金项目：国家８６３高技术研究发展计划资助项目（编号：２００３ＡＡｌ１８０７０）

作者简介：查金水（１９７８一），男，硕士研究生，主要研究方向：数据挖掘，复杂系统。宋良图（１９６３一），男，副研究员，主要研究方向：智能化农业信息系

统。刘现平（１９７９一），男，硕士研究生，主要研究方向：图像检索系统，图形与图像处理。

计算机工程与应用２００６．１０

１５５

万方数据　

ｃｏｎｆｏ我们的目标就是根据使用者给定的最小支持度ｍｉｎｓｕｐ和最小置信度ｍｉｎｃｏｎｆ阀值来产生所有的ＣＡＲｓ集，然后根据产生的ＣＡＲｓ建立一个分类器。

２

ＣＢＡ算法的描述

ＣＢＡ算法阁包含两个步骤：类关联规则的产生和分类器的

建立。２．１

基本概念

产生规则的首要条件就是要找出所有大于最低支持度阀

值的规则。一个规则项ｒｕｌｅｉｔｅｍ的形式如下：＜ｃｏｎｄｓｅｔ，ｙ＞。这里的ｃｏｎｄｓｅｔ是一项集．ＹＥＹ是一个类别标签。Ｃｏｎｄｓｅｔ的支持度（ｃｏｎｄｓｕｐＣｏｕｎｔ）是指Ｄ中包含ｃｏｎｄｓｅｔ的数。规则项ｒｕｌｅｉｔｅｍ的支持度（ｒｕｌｅｓｕｐＣｏｕｎｔ）是指Ｄ中类别标签是Ｙ的ｃｏｎｄｓｅｔ的数。每一个ｒｕｌｅｉｔｅｍ可以表示一条规则：ｃｏｎｄｓｅｔ－－－＊ｙ。它的支持度是（ｒｕｌｅｓｕｐＣｏｕｎｔ／ＩＤＩ）４１００％，这里ｌＤＩ是数据集的大小。它的确信度是（ｒｕｌｅｓｕｐＣｏｕｎｔ／ｃｏｎｄｓｕｐＣｏｕｎｔ）４１００％。

对于有同样ｃｏｎｄｓｅｔ的项集来说。确信度最高的将被选为可能的规则ＰＲ（ｐｏｓｓｉｂｌｅｒｕｌｅｓ）来代表这个项集。如果有超过一个的项集具有相同的最高的确信度，我们将随机的选择一个项集。如果一条规则的确信度大于最低确信度阀值，我们说这条规则是精确的。而类关联规则集就是包含那些既频繁又精确的

所有的ＰＲ。

２．２产生类关联规则

ＣＢＡ产生类关联规则的算法ＣＢＡ—ＲＧ如下：

１ＦＩ＝｛ｌａｒｇｅ１－ｒｕｌｅｉｔｅｍｓ｝；２ＣＡＲｌ＝ｇｅｍＲｕｌｅｓ（‘）；

３ｐｒＣＡＲｌ＝ｐｒｕｎｅＲｕｌｅｓ（ＣＡＲｌ）；

４ｆｏｒ（ｋ＝２；Ｒ—ｌ≠∥；＾＋＋）ｄｏ５Ｇ＝ｃａｎｄｉｄａｔｅＧｅｎ（疋一１）；

６ｆｏｒｅａｃｈｄａｔａ

ｃａｓｅ

ｄ∈Ｄ

ｄｏ

７Ｑ＝ｒｕｌｅＳｕｂｓｅｔ（ｑ，ｄ）；

８ｆｏｒｅａｃｈｃａｎｄｉｄａｔｅ

ｃ∈ｑｄｏ

９ｃ．ｃｏｎｄｓｕｐＣｏｕｎｔ＋＋；

１０ｉｆｄ．ｃｌａｓｓ＝ｃ．ｃｌａｓｓｔｈｅｎｃ．ｒｕｌｅｓｕｐＣｏｕｎｔ＋＋１１ｅｎｄ

１２ｅｎｄ１３Ｅ＝（ｃ∈ＱＩｃ．ｒｕｌｅｓｕｐＣｏｕｎｔ≥ｍｉｎｓｕｐ）；

１４ＣＡＲ女＝ｇｅｎＲｕｌｅｓ（Ｅ）；１５

ｐｒＣＡＲ＾＝ｐｒｕｎｅＲｕｌｅｓ（ＣＡＲＩ）；１６ｅｎｄ１７

ＣＡＲｓ＝Ｌ）ｋＣＡＲ＾；

１８ｐｒＣＡＲｓ＝ＵＩｐｒＣＡＲＩ；

由上述的算法可以看出，在算法的每个循环中都要进行四个主要的操作。如在第ｋ循环中，首先通过第南一１循环中的频繁项集疋一。来产生频繁候选ｋ项集Ｃｋ，这一步主要是通过使用了ｃａｎｄｉｄａｔｅＧｅｎ函数来实现。接着扫描数据库来更新Ｃ。中各个候选集的支持度计数，然后这些新的频繁项组成新的Ｅ。算

法使用ｇｅｎＲｕｌｅｓ函数来产生规则ＣＡＲ。。最后使用对这些ＣＡＲ。

规则进行剪枝。

２．３建立分类器

为了在已经获得的规则上面建立一个最好的分类器，需要选择那些错误最少的规则。设Ｒ是所有已经产生的规则，Ｄ是

１５６

２００６．１０计算机工程与应用

万　

方数据训练数据。算法的基本目的就是从Ｒ中选择一些优先度比较高的规则来替代Ｄ。在这里优先度的定义为：给定两条规则，ｒ．和‘，■＞ｒＪ（即■的优先度比ｌ高）需满足下列条件：

（１）如果ｔ的确信度比一的高，或

（２）两者的确信度相同，但是一的支持度比‘的大，或（３）两者的确信度和支持度相同，但ｒ，产生的比ｒｉ早（也就是在规则的左手边ｒ．有更少的属性）；

我们建立的分类器的形式如下：

口１，１＂２，…，ｒ，ｄｅｆａｕｌｔ＿ｃｌａｓｓ＞，这里‘ｅＲ，如果ｂ＞ａ，则Ｌ＞ｒ６。ｄｅｆａｕｌｔ＿ｃｌａｓｓ是默认的类。在对一条未知类别的案例进行分类时，第一条满足这个案例的规则即可以分类这个案例。如果没有规则满足。则将这个案例归为默认的类。

分类器的建立有三个步骤：

（１）对所有Ｒ中的规则根据关系按降序排列。这确保我们的分类器可以选到优先度最高的规则。

（２）对于每条规则ｒ∈Ｒ，我们到Ｄ中去寻找可以被ｒ替代（即它们满足规则ｒ的左手边属性值）的案例，如果ｒ至少可以正确分类，即可以替代，一个案例，它将是我们分类器的一条潜在的规则。对于那些可以被分类的案例将其从Ｄ中移出来。对于Ｄ中那些不能被规则ｒ替代的案例．我们用ｄｅｆａｕｌｔ＿ｃｌａｓｓ来标识。然后来计算由分类器和默认的类别号分类的错误的案例数。这里的ｄｅｆａｕｌｔ＿ｃｌａｓｓ是指Ｄ中剩余案例中大部分案例所属

的那个类。

（３）将分类器中那些不能增加分类器准确率的规则抛弃，剩下的未被抛弃的规则和ｄｅｆａｕｌｔ＿ｃｌａｓｓ一起组成我们的分类器。具体的算法参见［５］。

３改进的基本措施

由上述对ＣＢＡ算法的描述我们可以看出．类关联规则的产生算法与Ａｐｒｉｏｆｉ算法类似。与Ａｐｒｉｏｒｉ不同的是在算法过程中要对两项进行支持度的计算，即ｃｏｎｄｓｅｔ和ｒｕｌｅｉｔｅｍ。这个主要是为了后面可以计算ｒｕｌｅｉｔｅｍ的确信度。以前针对ＣＢＡ算法的一些改进主要是集中在ＣＢＡ—ＲＧ阶段．为了使数据库可以一次性的载入到内存中，对数据库进行划分，每部分采用单独的支持度计数。它对于数据库的划分和规则的产生采用不同的算法，选择效率最高的一个［６１。

在类关联规则的挖掘过程中，由于采用了Ａｐｒｉｏｒｉ算法同，需要不断地产生候选集，虽然利用Ａｐｒｉｏｒｉ性质，可以对候选集进行缩减以达到提高挖掘效率的目的，仍然存在两个问题：（１）产生的候选集过多；（２）需要对数据库进行反复扫描，通过一定的模式匹配的方式对大量候选集进行检验。为了避免产生的候选集过多．以及提高挖掘的效率，我们提出了一个新的基于关

联规则分类的算法——ＮＣＢＡ。

为了发现分类规则，ＮＣＢＡ首先挖掘训练数据，通过支持度和置信度阀值来发现所有的频繁项集。这也是一个典型的频繁模式关联规则挖掘任务。为了使挖掘的效率更高，ＮＣＢＡ算法使用ＦＰ一树［８１算法。ＦＰ一树的频繁模式生成方法比Ａｐｒｉｏｒｉ类的方法更快，特别是对于大数据集、低的支持度阀值、长模式来说效率更高。通过使用ＦＰ一树挖掘类关联规则来改进ＣＢＡ算法的主要思想通过如下的例子来说明：

给定一个如表１所示的训练数据集ｒ。假定设最小支持度阀值是２，确信度阀值是５０％。我们首先对数据集ｒ进行扫描

一次，然后找出那些支持度大于２的那些项，项集肚ｋ，ｄ∥ｋ｝

称为频繁项集。其它的支持度小于最小支持度的项不能在关联规则中起到作用。所以将被剪枝。

表ｌ调练数据集

然后对Ｆ中的项，按照支持度计数的降序排列，排列的结果是Ｆ—ｌｉｓｔ＝ａ—ｄ一户ｋ。然后再扫描一次训练数据集来构建一棵ＦＰ一树（如图２所示）。先创建树的根结点，用Ｎｕｌｌ表示。接着我们按照Ｆ—ｌｉｓｔ中出现的项和项的顺序对训练数据集中的每个元组进行选取。例如：在第一个元组中，只有（ａ，，）出现在Ｆ—ｌｉｓｔ中．将其选取出来，作为最左边的一个分枝插入到树中。类别标签放在路径的最后一个节点上。

在训练集中的元组将会在树中分享一个共同的前缀。例如，第二个元组的属性值（ｎ，ｄ；，）。这样在Ｆ—ｌｉｓｔ中将会和第一个元组分享同一个前缀ａ。因此在ＦＰ一树中也同时分享最左边分枝的ａ的子路。所有相同属性值的节点作为一个队列从头节点开始连起来。

根据Ｆ—ｌｉｓｔ．我们可以将类关联规则集划分为无重复的四个子集：（１）含有ｋ的集；（２）含有厂但是不含有ｋ的集；（３）含有ｄ但不含有ｋ和厂的集；（４）只含有ａ的集。

图２ＦＰ一树

图３合并节点ｋ之后的ＦＰ－树

为了找到含有ｋ的子集的规则，我们观察ＦＰ一树，遍历含有ｋ指针的节点组成一个后一ｄｂ数据库．我们可以发现危一ｄｂ含有三个元组：（ａ，ｄ，厂，ｋ）：Ｃ，（ａ，ｄ，ｋ）：Ｃ，ｋ：Ａ，这就是所有含有ｋ的元组。在训练集中找出所有含有的频繁模式的问题就简化为在詹一ｄｂ数据库中挖掘频繁模式。

由上述可知．在｜｜｝一ｄｂ中，ａ和ｄ都是频繁的属性值，因为它们都大于或等于支持度的门槛值。又因为在｜ｊ｝一ｄｂ中，ｋ在每一个元组中都出现，因此必定是频繁的。所以我们也不需要计算ｋ的支持度。我们可以通过循环的构造ＦＰ一树和ｄｂ数据库来挖掘ｄｂ数据库中的类关联规则。

在七一ｄｂ数据库中，ａ和ｄ正好都是同时出现，因此ｎｄ是一个频繁模式。ａ和ｄ是以的两个子集，与甜有相同的支持

度。基于类别标签的信息，我们可以产生三条规则：ⅡＪ｝一Ｃ，幽一

Ｃ，觎一Ｃ。它们三个的支持度皆为２、确信度皆为１００％。

在搜寻到所有的含有ｋ的规则之后．所有的ｋ的节点都分

万　

方数据别和它们各自的父节点合并。也就是说在ｋ结点中的类别标签将在其父节点的标注。缩减之后的树如图３所示。余下的规则的提取同上述的类似。

由此我们可以看出，在对树的挖掘过程中．将原有的发现较长频繁模式的问题转化为反复寻找较短的模式而后再连接其前缀的过程。因此和ＣＢＡ中采用的Ａｐｒｉｏｆｉ算法相比，不必重复扫描数据库。可以降低搜索成本，极大的提高效率。

由于ＦＰ一树在扫描数据库的过程中，需要将数据库一次性装入内存中来构建树。因此对机器的内存有一定的要求，如果数据库比较大的话，我们可以首先对数据库进行分割，然后再对每一个分割后的数据库用ＦＰ一树算法提取类关联规则。

４实验结果及分析

我们采用了某一地区的棉花病虫害数据为例测试算法的效果。本实验以Ｄｅｌｐｈｉ６，０为开发环境，数据存储在ａｃｃｅｓｓ数据库中，即为分类的样本空间。部分数据如图４所示。

图４棉花病虫害数据

由图４可以看出，我们将前面四个属性：病斑颜色、病害部位、病害形状、病害特征作为ｃｏｎｄｓｅｔ集，最后的一个属性：病的种类作为类别标签ｙ。然后我们对数据进行转化，将这些文本数据转化为布尔型数据，以方便规则的挖掘。接着选定ｍｉｎ—得到的类关联规则建立分类器。我们使用样本中的９０％的数据为训练数据。其余的为测试数据。图５即为得到的分类器中的类关联规则。

图５

训练样本为９０％时得到的分类器中的类关联规则

我们分别使用了三组数据进行了测试，样本数分别为４０、

０００个。两种算法测试比较的结果如表２所示。

表２两种算法运行时间比较ｓ

由实验结果可以看出，随着样本数目的增加，ＮＣＢＡ算法（下转２０３页）

计算机工程与应用２００６．１０

１５７

ｓｕｐ＝１５％，ｍｉｎｃｏｎｆ＝８０％来进行类关联规则的挖掘，然后对挖掘的运行时间明显比ＣＢＡ算法少，效率增加。随着数据库的不断增大，ＣＢＡ算法运行效率低的瓶颈就暴露出来了。因此改进后

２００和１

表ｌ几种方法的检测结果比较

图像序号实有目标数目ＣＡ—ＣＦＡＲ结果Ｇ０一ＣＦＡＲ结果本文方法结果

１１７１７１５１７

２１４１３１４１４

３２３２１２０２３

（ａ）原始图象

（ｂ）ＣＡ—ＣＦＡＲ检测结果

６结论

本文提出了一种在ＳＡＲ图像中检测目标的方法。该方法采用基于ｗｅｉｂｕｌｌ分布模型的ＣＦＡＲ检测技术，对背景区域分块，根据每个子块的统计参数和空间分布，确定子块类型，根据各子块类型不同，选择不同的参考单元确定阈值。同时根据目标灰度、方差特征剔除明显不可能为目标的像素，利用多数滤

（ｅ）本文ＣＦＡＲ方法检测结果

（ｄ）本文方法最终结果

波器和目标形状特征，进一步排除虚警。相比于ＣＡ—ＣＦＡＲ方法．本文方法保留了算法简单、同质区检测性能好的优点，同时．对存在杂波边缘或多目标干扰的情况，也能有很好的检测效果。实验证明本文方法检测性能好，自适应性强，适应于大多数ＳＡＲ图像的目标检测。（收稿日期：２００５年９月）

图５实验结果图像

检测结果中，ＣＡ—ＣＦＡＲ方法有２个虚警、２个漏警，本文方法有１个虚警，无漏警，且轮廓的完整性保持更好。可以看出，本文方法相比ＣＡ—ＣＦＡＲ方法，具有更好的检测效果，说明该方法是有效的。对检测结果进一步判别。虚警目标被滤除，得

到目标的ＲＯＩ。

参考文献

１．Ｑｕｏｏ

Ｈ

Ｐｈａｍ，ＴｉｍｏｔｈｙＭＢｍｓｎａｎ，Ｍａｒｋ

Ｔａｒｇｅｔｓｉｎ

ＳＡＲ

ＪＴＳｍｉｔｈ．ＭｕｌｔｉｓｔａｇｅＡｌｇｏ－

表ｌ给出了三种方法在其他几幅图像的检测结果，比较得出：ＣＡ—ＣＦＡＲ和ＧＯ—ＣＦＡＲ分别只对部分图像有较好的检测效果，本文方法对所有图像都有较好检测效果。在背景平稳区域，本文方法性能接近ＣＡ—ＣＦＡＲ；在杂波边缘，ＣＡ—ＣＦＡＲ虚警增多，而本文方法较好地抑制了虚警，检测性能接近Ｇ０一ＣＦＡＲ；在多目标区域，ＣＡ—ＣＦＡＲ由于目标间的相互干扰，检测出目标轮廓不完整甚至漏警，本文方法由于自动排除了干扰目标影响，比ＣＡ—ＣＦＡＲ和ＧＯ—ＣＦＡＲ具有更好的检测效果。在一幅图像中．杂波边缘和多目标情况经常可能同时存在，ＣＳＳ０一ＣＦＡＲ或ＣＳＧＯ—ＣＦＡＲ方法只是单纯地选大或者选小，不能对图象灰度分布变化自适应，当图像复杂时难以有好的效果。本方法的最大优势在于结合了各种方法的优点，智能判定区域类型。在各种复杂环境下都具有较好的检测性能。

（上接１５７页）

ｒｉｔｈｍｆｏｒＤｅｔｅｃｔｉｏｎｏｆ

Ｉｍａｇｅ

Ｄａｔａ［ｊ］．ＳＰＩＥ，１９９７；３０７０

２．王世锦，孟健青．单元筛选后作最小选择的ＣＦＡＲ自适应检测器【Ｊ】．雷达与对抗．２００４；（４）

３．贾承丽．计科峰，匡纲要等．利用ＧａｍｍａＣＦＡＲ进行ＳＡＲ图像目标检测［Ｊ】．系统工程与电子技术，２００５；（１）

４．何友，关键，孟祥伟．雷达自动检测和ＣＦＡＲ处理方法综述忉．系统工程与电子技术，２００１；２３（１）

５．ＭｉｃｈａｅｌＢａｓｅｄ

Ｅｌｅｃｔ

ｏｎ

ＥＳｍｉｔｈ．Ｐｒａｍｏｄ

Ｄａｔａ

Ｋ

Ｖａｒｓｈｎｅｙ．Ｉｎｔｅｌｌｉｇｅｎｔ

Ｔｒａｎｓａｃｔｉｏｎｓ

ｏｎ

ＣＦＡＲＰｒｏｃｅｓｓｏｒ

ａｎｄ

Ｖａｒｉａｂｉｌｉｔｙ［Ｊ】．ＩＥＥＥ

Ａｅｒｏｓｐａｃｅ

ｔｏｎｉｃＭｉｎｇ

Ｓｙｓｔｅｍｓ，２０００Ｗｏｎｇ，Ｃｈｅｅ

Ｈａｎｇ

Ｃｈａｎｇ，Ｗｅｉｘｉａｎ

Ｉｎｔｅｒｎａｔｉｏｎａｌ

Ｌｉｕ

ｅｔ

６．Ｃｈａｒ

ｉｎ

ａ１．ＣＡ—ＣＦＡＲ

ｏｎ

ｗｅｉｂｕｌｌ

Ｂａｃｋｇｒｏｕｎｄ［Ｃ］．Ｉｎ：２ｎｄ

ＣｏｎｆｅｒｅｎｃｅＭｉ—

ｃｒｏｗａｖｅ７．Ｍ

ａｎｄＭｉｌｌｉｍｅｔｅｒＷａｖｅ

ＴｅｃｈｎｏｌｏｇｙＰｒｏｃｅｅｄｉｎｇｓ，２０００

Ｓｋｏｌｎｉｋ．Ｒａｄａｒ

Ｈａｎｄｂｏｏｋ［Ｍ］．２ｎｄｅｄｎ．，ＭｃＧｒａｗＨｉｌｌ，ｌ９９０

Ｄａｔａｂａｓｅｓ［Ｃ］．Ｉｎ：ＰｒｏｃｏｆｔｈｅＡＣＭＳＩＧＭＯＤ

ｏｎ

ＳｅｔｓｏｆＩｔｅｍｓ

ｉｎ

Ｌａｒｇｅ

的ＮＣＢＡ算法的实际应用性也较ＣＢＡ有了很大的提高。

Ｉｎｔｅｒｎａｔｉｏｎａｌｃｏｎｆｅｒｅｎｃｅ

Ｍａｎａｇｅｍｅｎｔ

ｏｆ

Ｄａｔａ，Ｗａｓｈｉｎｇｔｏｎ

Ｄ

Ｃ，

１９９３：２０７～２１６

５

结论

本文通过对基于关联规则的分类方法ＣＢＡ的分析，指出

３．ＨａｎＪＷ，ＫａｍｂｅｒＭ．数据挖掘：概念与技术【Ｍ］．北京：机械工业出版

社．２００ｌ

４．ＬｅｎｔＢ，ＳｗａｍｉＡ，ＷｉｄｏｍＪ．Ｃｌｕｓｔｅｒｉｎｇ

ｔｈｅ

１３“Ｉｎｔｅｒｎａｔｉｏｎａｌ

Ｃｏｎｆｅｒｅｎｃｅ

ｏｎ

ａｓｓｏｃｉａｔｉｏｎ

ｒｕｌｅｓ［Ｃ］．Ｉｎ：Ｐｒｏｃｏｆ

它的效率不足之处：它需要反复扫描数据库，而且会产生大量的候选集，通过一定的模式匹配方法对大量候选集进行检验。我们新的ＮＣＢＡ算法通过使用ＦＰ一树来提取类关联规则，由于ＦＰ一树算法比较简单．只需扫描一遍数据库，可以将较长的频繁模式转化为先寻找较短的模式而后再连接其前缀的过程。有效的降低了搜索成本。通过对算法的改进使运行效率有了很大的提高，并举例说明了获取类关联规则的具体过程。最后通过一个实际的例子说明两种算法的效果，证明了改进后算法的实用性和效率都有了很大的提高。（收稿日期：２００５年１１月）

Ｄａｔａ

Ｅｎｇｉｎｅｅｒｉｎｇ，Ｂｉｒｍｉｎｇｈａｍ，

１９９７：２２０～２３１５．Ｌｉｕ

Ｂ，Ｈｓｕ

Ｗ，ＭａＹ．ＩｎｔｅｇｒａｔｉｎｇＣｌａｓｓｉｆｉｃａｔｉｏｎａｎｄ

ＡｓｓｏｃｉａｔｉｏｎＲｕｌｅ

ｏｎ

Ｍｉｎｉｎｇ［Ｃ］．Ｉｎ：Ｐｒｏｃｏｆｔｈｅ４ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ

Ｄｉｓｃｏｖｅｒｙ

Ｋｎｏｗｌｅｄｇｅ

ａｎｄＤａｔａ

Ｍｉｎｉｎｇ，ＮｅｗＹｏｒｋ，１９９８

Ｋ．Ｉｍｐｒｏｖｉｎｇ

ａｎ

６．ＬｉｕＢ．Ｍａ

Ｙ，Ｗｏｎｇ

ＡｓｓｏｃｉａｔｉｏｎＲｕｌｅ

ｏｎ

ＢａｓｅｄＣｌａｓｓｉ—Ｐｒｉｎｃｉｐｌｅｓ

ｔｉｅｒ［Ｃ］．Ｉｎ：Ｐｒｏｃｏｆｔｈｅ４ｔｈＥｕｒｏｐｅａｎＣｏｎｆｅｒｅｎｃｅ

Ｐｒａｃｔｉｃｅ

ｏｆＲ

ａｎｄ

ＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙ

ｉｎ

Ｄａｔａｂａｓｅｓ，Ｌｙｏｎ，２０００

Ｍｉｎｉｎｇ

ｏｎ

７．Ａｇｒａｗａｌ

２ＳｒｉｋａｎｔＲ．ＦａｓｔＡｌｇｏｒｉｔｈｍｓｆｏｒ

Ａｓｓｏｃｉａｔｉｏｎ

Ｒｕｌｅｓ［Ｃ】．

Ｉｎ：Ｐｒｏｃｏｆｔｈｅ２０ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ

ＶｅｒｙＬａｒｇｅＤａｔａｂａｓｅｓ．

参考文献

１．ＱｕｉｎｌａｎＪ—Ｒ．Ｃ４．５：Ｐｒｏｇｒａｍｓ

ｆｏｒ

Ｓａｎｔｉａｇｏ，Ｃｈｉｌｅ，１９９４；９：４８７～４９９

８．Ｈａｎ

ＭａｃｈｉｎｅＬｅａｒｎｉｎｇ．Ｃａｌｉｆｏｒｎｉａ：Ｍｏｒｇａｎ

Ｊ

Ｗ．ＰｅｉＪ，ＹｉｎＹ．ＭｉｎｉｎｇＦｒｅｑｕｅｎｔＰａｔｔｅｒｎｓｗｉｔｈｏｕｔＣａｎｄｉｄａｔｅ

Ｋａｕｆｍａｎｎ，１９９３

２．Ａｇｒａｗａｌ

Ｒ，ＩｍｉｅｌｉｎｓｋｉＴ，Ｓｗａｍｉ

Ａ．ＭｉｎｉｎｇＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓｂｅｔｗｅｅｎ

Ｇｅｎｅｒａｔｉｏｎ［Ｃ］．Ｉｎ：Ｐｒｏｃｏｆ１９“ＡＣＭＳＩＧＭＯＤＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ

ｏｎ

ＭａｎａｇｅｍｅｎｔｏｆＤａｔａ，Ｄａｌｌａｓ，２０００：２０７－２１６

计算机工程与应用２００６．１０

２０３

万方数据