范文一：2 聚类、分类、关联规则
聚类分析的含义
z聚类(Clustering )用于发现在数据库中 未知的对象类
z聚类方法对象类划分的依据是 “ 物以类 聚 ” ,即考察个体或数据对象间的相似性 z在聚类之前,对象类划分的数量与类型 均是未知的
分割聚类方法概述
z分割聚类方法是一种基于原型(Prototype ) 的聚类方法。
z其本质是首先从数据集中随机地选择几个对 象作为聚类的原型,然后将其它对象分别分 配到由原型所代表的最相似、也就是距离最 近的类中。
z分割聚类方法通过 迭代控制策略 对原型不断 地进行调整,从而使得整个聚类得到优化。
k -means 算法的思路 1. 首先 随机地选择 k 个对象 代表 k 个类, 每一个对象作为一个类的原型,根据 距 离原型最近 的原则将其它对象分配到各 个类中。
k -means 算法的思路 2. 以每一个类所有对象的 平均值(mean ) 作为该类新的原型, 迭代 进行对象的再分 配,直到没有变化为止,从而得到最终的 个类。
k -means 算法步骤 1. 首先随机地选择 k 个对象,每一个对象作 为一个类的 “ 中心 ” ,分别代表将分成的 k 个 类。
2. 根据距离 “ 中心 ” 最近的原则,寻找与各 对象最为相似的类,将其它对象分配到各 个相应的类中。
k -means 算法步骤 3. 在完成对象的分配之后,针对每一个 类,计算其所有对象的平均值,作为该 类的新的 “ 中心 ” 。
4. 根据距离 “ 中心 ” 最近的原则,重新进行 所有对象到各个相应类的分配。
5. 返回步骤(3),直到没有变化为止。
层次聚类方法概述 z层次聚类方法(Hierarchical Clustering Method )是采用 “ 自顶向下 (Top-Down ) ” 或 “ 自底向上 (Bottom-Up ) ” 的 方法 在不同的层次上 对对象进行分组, 形成一种树形的聚类结构。
z其包括分解型层次聚类法(自顶向下) 和聚结型层次聚类法(自底向上)。
层次聚类方法思想 z层次聚类方法按照 一定的相似性判断标准 ,合 并最相似的部分,或者分割最不相似的两个部 分。
z如果合并最相似的部分,从每一个对象作为一 个类开始, 逐层向上聚结 ,直到形成唯一的一 个类 。
z如果分割最不相似的两个部分,从所有的对象 归属在唯一的一个类中开始, 逐层向下分解 , 直到每一个对象形成一个类。
分类的目标
z 分类的目标是通过分析训练集中的数 据,对类进行准确的描述或者建立模 型,然后用它对数据库中的其它数据分 类或者上升为分类规则。
分类发现的处理过程 1. 分类模型的建立
监督学习 (Supervised Learning) z分类模型的建立是通过分析训练样本数 据总结出一般性的分类规则,建立分类 模型。
z分类模型以分类规则、决策树或数学公 式的形式给出。
分类发现的处理过程
2. 分类模型的应用
z在对建立的分类模型进行应用前,需要 对建立的分类模型进行评估,在确保分 类模型的准确性及精确度的情况下,才 能运用该分类模型对未知其类别的数据 样本进行分类处理。
分类发现的主要方法 1. 基于决策树模型的数据分类 —— ID3算法
2. 基于统计模型的数据分类 —— 贝叶斯分类
3. 基于神经网络的数据分类
决策树生成过程 1. 用户根据实际需求以及所处理数据的 特性,选择 类别标识属性 和决策树的 决 策属性集 。
决策树生成过程
4. 针对上一步中得到的每一个子集,重 复进行上述的 2、 3两个步骤,直到最后 的子集符合结束的 三个条件之一 。
三个条件
1. 子集中的所有元组都属于同一类;
2. 该子集是遍历了所有决策属性得到的;
3. 子集中的所有剩余决策属性取值完全相 同,已不能根据这些决策属性进一步进行 子集划分。
决策树生成过程 5. 根据符合条件的不同,生成叶子节 点。
z对满足 “ 条件一 ” 所产生的叶子节点,直 接根据该子集的元组所属类别进行类别 标识。
z满足步骤 “ 条件二 ” 或 “ 条件三 ” 所产生的 叶子节点,选取子集所含元组的代表性 类别特征进行类别标识。
决策树剪枝
z 有决策树得到的初步规则中,有一些预 测规则准确性较低,因此需要对上述得 到的决策树进一步处理,这个进一步处 理的过程由 “ 剪枝 ” 过程完成。
决策树剪枝
z 主要是采用新的样本数据集(称为 测试 数据集 )中的数据检验决策树生成过程 中产生的初步规则,将那些影响预测准 确性的分枝剪除。
贝叶斯原理
zX 为未知其类标识的训练样本数据; zH 表示作出的一些假设 (例如,假设训练 样本数据 X 属于某一特定类 C) ;
z我们想得到 P(H|X),即该假设成立的可 能性。
zP(H|X)被称为假设 H 在训练样本数据 X 的 基础上的后验概率。
简单贝叶斯分类例 由此可得:
P(X|c 1 )= P (部门 = '系统部 ' | c 1 ) ×P (职位 = '高级 ' | c 1
) ×
P (年龄 = '21…30' | c 1 ) =0
P(X|c 1 )P(c 1 )=0
简单贝叶斯分类例 同理可得:
P(X|c 2 )= P (部门 = '系统部 ' | c 2 ) ×P (职位 = '高级 ' | c 2
) ×
P (年龄 = '21…30' | c 2 ) =0.4 ×0.4 ×0.4
=0.064
P(X|c 2 )P(c
2
)=0.064 ×0.4545=0.029
简单贝叶斯分类例 同理可得:
P(X|c 3 )= P (部门 = '系统部 ' | c 3 ) ×P (职位 = '高级 ' | c 3
) ×
P (年龄 = '21…30' | c 3 ) =0 ×0.5 ×0.4
=0
P(X|c 3 )P(c 3 )=0
简单贝叶斯分类例 zP(X|c2)P(c2) > P(X|c3)P(c3) = P(X|c1)P(c1) z因此,未知训练样本数据最有可能属于 C
2
类,该结果表示对于年龄在 21~30岁之 间、所属部门是 “ 系统部 ” 同时其地位属 于 “ 高级 ” 的员工的工资水平最有可能在 41K~55K之间。
神经网络
z神经网络由一组相关的输入及输出单元 组成,对于每一个关联都有一个权重与 之相对应。
z在网络构建阶段,神经网络通过调整权 重以达到能正确预测输入的训练样本数 据的类别归属,由于神经网络学习是一 种在各个单元之间的关联,因而又称之 为关联学习。
关联规则
z关联规则是指大量数据中项集之间有趣 的关联或相关联系。
z关联规则发现最初的形式是零售商的货 篮分析。
范文二：基于关联规则的分类方法初探
ISSN 1009-3044
Computer Knowledge and Technology 电脑知识与技术
Vol.5,No.3,January 2009, pp.535-536E-mail:jslt@cccc.net.cnhttp://www.dnzs.net.cnTel:+86-551-56909635690964基于关联规则的分类方法初探
刘红梅
（长江大学计算机学院软件系，湖北武汉434103）
摘要：分析、比较了当前具有代表性的分类关联算法，总结了关联规则分类存在的问题，便于使用者根据需要选择合适的算法，也便于研究者对算法进行研究改进，提出性能更好的分类算法。
关键词：数据挖掘；分类规则；关联规则
中图分类号：TP274文献标识码：A 文章编号：1009-3044(2009)03-0535-02
Research of Association Rule Classification
LIU Hong-mei
(Schoolof Computer Science, Yangtze River University, Wuhan 434103, China)
Abstract:Analyzing and comparing a variety of typical classified algorithms.Summarizing the weak point of Association Rule Classification, It ’s convenient for user to select an appropriate algorithm for the application. It ’s also convenient for researcher to improve old algorithms and develop a new effective one.
Key words:Data Mining; classification rule; association rule
1引言
自1993年Agrawal 提出数据库中的关联规则挖掘后，关联规则挖掘算法及应用得到迅速发展。关联规则的功能不再局限于概念描述。1997年，Ali 等人提出了使用分类关联规则进行部分分类的思想，但他们当时认为关联规则在分类预测问题上很难取得重大的进展。在1998年纽约举行的数据库知识发现国际会议上，新加坡国立大学的Liu 等人提出了基于分类关联规则的关联分类算法CBA ，从此揭开了关联分类的序幕。
与传统的决策树算法比较，关联分类具有分类预测准确度高的特点，因此关联分类在数据挖掘领域内引起广泛关注。目前，中国、美国和加拿大等国家都设立了国家自然科学基金进行这方面的研究。许多学者目前正在进行这方面的工作，且在分类算法上先后相继取得了一批研究成果，如CBA 、CAEP 、ADT 、CMAR 、CPAR 和CAAR 等。
2常用的关联规则分类方法
2.1基于关联规则的分类算法CBA
Liu 于1998年提出。该算法使用类Apriori 算法产生分类关联规则，使用的支持度阈值为1%，置信度阈值为50%，实验结果给出了分类误差值，并与决策树算法C4.5进行了比较。该研究存在的主要问题是采用类Apriori 算法产生大量分类关联规则，消耗的系统资源多。为了防止过度使用系统资源，算法规定挖掘的规则数量不能超过80000个，当遇到高维数据库时，挖掘的频繁项集长度迅速地减少，但分类模型的准确度显著地下降。
2.2显露模式分类法CAEP
显露模式分类法CAEP 由Dong 等人创立。显露模式是指从一个数据子集转变到另一个数据子集时，支持度发生显著变化的项集。最初的显露模式用于分析不同类型数据之间多个属性的对比或随时间改变的不同趋势之间多个属性的对比。显露模式分类利用支持度差异进行分类，没有充分的理论依据来确保分类准确度。他们将新算法与C4.5和CBA 等算法进行了对比。给出了在15个数据上不完整的分类结果，未给出算法的平均分类准确度，实验结果也未能充分说明CAEP 算法有何突出的优点，只能说明提供了一种新的关联分类方法。
2.3关联决策树ADT
2000年，Wang 等人结合关联规则分类和决策树分类各自的长处，提出了关联决策树方法。ADT 方法完全放弃支持度阈值，仅依据置信度阈值从分类关联规则中选择分类规则，以此构建准确度驱动的决策树，采用自低向上的闭包运算生成可信的关联规则。该方法的缺点是对噪声特别敏感，在实际应用中，由于存在噪声，难以达到试验取得的准确度。同年，Li 等人提出利用跳跃的显露模式用于分类，对显露模式分类提出了改进。
2.4基于多个分类关联规则的分类算法CMAR
2001年，J ．Li 等人给出了挖掘最小的分类关联规则集用于预测的形式化描述。他们提出在不损失预测能力的前提下挖掘最小的分类关联规则集。然而，他们并没有给出实验数据比较最小规则集与完全分类关联规则集的预测能力。而且，他们未能与其它典型的关联分类算法进行对比，在这种情况下提出算法在不损失准确度的前提下产生最小分类关联规则集的论点缺乏足够的证据。W.Li 等人提出了基于多个分类关联规则的分类算法CMAR ，该算法使用改进的频繁模式增长法FP-growth 来挖掘关联规则，使用基于权重的多个强关联规则来确定新实例的类标签，实验结果表明分类准确度优于CBA 算法。然而，该算法存在两个问题：第一，基于FP-growth 的关联规则挖掘尽管比Apriori 快，但FP-growth 不适合高维、大型的数据库。而且该算法的内存消耗过大，在大规模数据收稿日期：2009-12-08
作者简介：刘红梅（1973-），女，讲师，硕士，现主要从事算法与数据结构方面的教学与研究工作。
本栏目责任编辑：闻翔军数据库与信息管理535
Computer Knowledge and Technology 电脑知识与技术第5卷第3期(2009年1月) 库上不易实现。第二，强关联规则在分类预测中的权重选择标准很难确定。
2.5预测型关联规则的分类算法CPAR
Yin 避开了使用资源消耗过大的关联规则算法，采用贪婪算法直接从训练数据集中挖掘关联规则，于2003年提出了一个称为预测型关联规则的分类算法CPAR 规则的支持度阈值设置为5%。CPAR 算法继承了一阶归纳学习算法FOIL 的思想，采用基于信息熵的方法选择最优的5个规则用来分类一个实例。在预测时使用5个规则测试新实例的类标签，因此CPAR 分类器的规则数很大。CPAR 方法产生的规则数小于CMAR 算法，在分类准确度上与CMAR 算法相当。
Liu 等人针对数据有噪声和类分布高度不均匀的情况提出了利用完全分类关联规则集给未知实例评分的方法来提高分类准确度。在他们的方法中，因其首先挖掘所有分类关联规则，所以能给出所讨论问题的完整视图，利用完整的规则集能精确地估计新实例的类标签。然而，这种方法的实用性差，其缺点主要表现在两个方面：第一，分类过程需要利用所有分类关联规则，分类器的体积非常庞大；第二，这种方法只适合小规模数据挖掘，在大规模数据集上，利用低支持度阈值挖掘所有分类关联规则的计算开销大得惊人，特别是当数据集的属性个数多、属性值域规模较大时，需要对数据集进行许多次扫描。实际上，当数据集属性个数较大时，挖掘完全的分类关联规则集属于NP-难解问题。
2.6其他关联规则分类算法
2002年，Baralis [4]等人提出了一个懒的（Lazy ）分类关联规则剪枝方法，该方法迭代地去除产生错误分类的所有规则，分类经过两遍进行，并在26个UCI 数据集上进行了实验，结果表明该方法提高了分类精度。然而，该方法应用于大规模数据集时会面临执行性能问题，因为在大规模数据集上挖掘全部分类关联规则实际上是行不通的。
Li 等人对关联分类的鲁棒性进行了研究，提出使用k 个最优的规则集增强分类预测的可靠性，当测试数据遗失某个属性值时，其它k-1个规则能担任分类的任务。这个特性是关联分类相对于决策树而言具有的显著优点之一。但该算法的缺点是分类规则集庞大、模型的可理解性差。Li 等人提出了挖掘最优的分类关联规则。最优的分类关联规则是指具有与完全分类关联规则集同样预测能力的最小规则集。通过使用最小规则集，而不是完全规则集可以减少挖掘分类关联规则的时间。他们使用了自底向上的闭包特性，对弱规则剪枝，避免挖掘弱规则。实验结果表明该算法挖掘的规则数是完全分类关联规则个数的1/17。实质上，与CBA 相比，上述算法没有显示出多少优越性，原因是挖掘完全分类关联规则的算法在实际应用中几乎是行不通的，因为实际数据挖掘应用中的数据集很大，所以与挖掘完全的分类关联规则比较未能充分显示算法的优越性。
Davy 等人在2003-2004年期间，研究了如何对CBA 算法的改进，提出一个新的分类关联规则后件选择框架，并提出一个称为暗示强度的指标来评价分类关联规则质量，以提高分类预测准确度。然而，他们在比较该方法与CBA 算法时，只在16个UCI 数据集上进行了测试，而CBA 算法发布时使用了26个标准数据集。
2004年，出现了基于正、负关联规则的关联分类。
可见，自1998年至今，关联分类的研究及应用从未间断。
3关联规则分类存在的问题
目前，一般关联分类算法存在以下问题：
1）资源消耗大
基于关联规则的分类方法是一种使用一组关联规则来分类事务的技术。关联规则挖掘属于求解集合子集问题，是典型的NP 难问题。当数据集中实例个数较多时，项集之间的组合产生大量候选频繁项集，在数据集上测试候选频繁项集消耗大量系统资源。在挖掘大规模数据集时，CPU 时间和内存消耗问题更加突出。
2）规则剪枝难
分类关联规则与其他一般关联规则挖掘算法一样，追求规则的有趣性、完整性和可理解性。为了防止遗漏潜在的、有价值的知识，常常在低支持度下挖掘规则，从而产生大量冗余规则。导致难以评价分类规则的质量，难以从大量关联规则中提取有效的分类规则。因此，有效的剪枝技术和约束条件成为分类关联规则研究的重点。
3）分类模型较复杂
一般关联分类算法产生庞大的分类器，不利于分类知识的理解，降低了数据挖掘的功能。如何减少分类规则的数目，提高单个规则的推广能力，增强规则的预测功能和可理解性，还有待解决。
4结语
与传统的分类方法比较，基于关联规则的分类技术在总体上具有分类准确度高，鲁棒性好的优点。作为一种新的分类方法，关联分类技术的研究朝着追求高的分类准确度、有效的剪枝、减少冗余规则、提高计算性能的方向发展，还存在许多需要改进的地方，需要我们坚持不懈地努力探索研究。
参考文献：
[1]
[2]
[3]
[4]
[5]邹晓峰, 陆建江, 宋自林, 等. 基于模糊分类关联规则的分类系统[J].计算机研究与发展,2003,40(5):651-655.Dunham M H.Data Mining Introductory and Advanced Topics[M].郭崇慧, 译. 北京:清华大学出版社,2005. 张丽娟, 李舟军. 分类方法的新发展：研究综述[J].计算机科学.2006. 许孝元. 分类关联规则归纳算法及应用研究[D].华南理工大学博士学位论文,2005. Baralis E,Garza P.A lazy approach to pruning classification rules [C].Proceedingsof the IEEE 2002International Conference on Data
Mining, Maebashi City,Japan,2002:35-42.536数据库与信息管理本栏目责任编辑：闻翔军
范文三：关联规则挖掘与分类规则挖掘的比较研究
2006年第7期
文章编号:100622475(2006) 07256203
计算机与现代化
J IS UAN J I Y U XI ANDAIH UA
总第131期
关联规则挖掘与分类规则挖掘的比较研究
彭慧伶, 刘发升
(江西理工大学信息学院, 江西赣州 341000)
摘要:
。则挖掘的基本知识, 主要从挖掘目的、发现规则算法的方法、, 它们之间的联系。
关键词:数据挖掘; 关联规则; R on Association Rules Mining and Classification Rules Mining
PE NG Hui 2ling ,LI U Fa 2sheng
(Faculty of In formation Engineering , Jiangxi University of Science and T echnology , G anzhou 341000, China )
Abstract :Discovering ass ociation rules and classification rules are very important techniques of data mining. This paper first introduces the basis knowledge of discovering ass ociation rules and classification rules , then compares them mainly from the g oal of mining , the method of discovering rules alg orithm , the designing idea and s o on , finally introduces the relation of them. K ey w ords :data mining ;ass ociation rules ;classification rules
0 引 言
随着科学技术的飞速发展, 数据资源日益庞大,
人们迫切需要从中发现有用的信息或知识。针对这一需求, 出现了“数据挖掘”这门新兴学科。数据挖掘(Data Mining ) , 又称数据库中的知识发现(K DD :K nowledge Discovering in Database ) , 是指从大型数据库或数据仓库中提取人们感兴趣的知识, 这些知识是隐含的, 事先未知的潜在有用信息, 提取的知识一般可表示为概念(C oncepts ) 、规则(Rules ) 、规律(Regulari 2ties ) 、模式(Patterns
) 等形式[1]。也可以说, 数据挖掘是一类深层次的数据分析。它包括关联分析、时序模式、聚类、分类、偏差检测以及预测。关联规则挖掘和分类规则挖掘都是数据挖掘非常重要的内容, 对关联规则挖掘与分类规则挖掘的比较研究是很必要的。
1 关联规则挖掘的基本知识
关联规则的概念由Agrawal 等人1993年提出, 关
联规则的挖掘是数据挖掘领域中一个非常重要的研
究课题。它是发现大量数据库中项集之间的关联关系。关联规则是发现交易数据库中不同商品(项) 之间的联系, 通过这些规则找出顾客购买行为模式, 如购买了面包对购买牛奶的影响, 这种规则可以应用于超市商品货架设计、货物摆放以及根据购买模式对用户进行分类等。从而引伸至找出一个变量间不同选择之间的关系, 或找出不同变量间的关系。
设I ={i1,i 2,. . ,i m }是项集, 其中i k (k =1,2,. . . , m ) 可以是购物篮中的物品, 也可以是保险公司的顾客。设任务相关的数据D 是事务集, 其中每个事务T 是项集, 使得T ΑI 。对每一个事务有惟一的标识, 如事务号, 记作TI D 。设A 是一个项集, 且A ΑT 。关联规则是如下形式的逻辑蕴涵:A]B , 其中A
(1) 支持度:P (A ∪B ) , 即A 和B 这两个项集在事务集D 中同时出现的概率。例如有50%的人既买
收稿日期:2005208229
基金项目:江西省自然科学基金资助项目(0411046) ; 江西省教育厅2003年科技攻关计划资助项目。
作者简介:彭慧伶(19802) , 女, 河南西华人, 江西理工大学信息学院硕士研究生, 研究方向:数据挖掘与数据库; 刘发升(19632) , 男, 江西大余人, 副教授, 硕士生导师, 博士, 研究方向:数据挖掘与数据库, 模式识别与人工智能。
2006年第7期彭慧伶等:关联规则挖掘与分类规则挖掘的比较研究
57
了面包又买了牛奶, 那么支持度为50%。
(2) 置信度:P (B|A ) , 即在出现项集A 的事务集D 中, 项集B 也同时出现的概率。例如买面包的人中有60%的人买了牛奶, 那么可信度为60%。
同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。给定一个事务集D , 挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则, 也就是产生强规则的问题。
2 分类规则挖掘的基本知识
一, 标准或什么规则进行分类。分类主要是通过分析训练数据样本, 产生关于类别的精确描述, 它代表了这类数据的整体信息。这种类别通常由分类规则组成, 可以用来对未来的数据进行分类预测。由于分类技术解决问题的关键是构造分类器, 要构造分类器, 需要有一个训练样本数据集作为输入。训练集由一组数据库记录或元组构成, 每个元组是一个由特征(又称属性) 值组成的特征向量, 此外, 训练样本还有一个类别标记。一个具体样本的形式可为:(v1, v2, ... , vn ; c ) ; 其中v i 表示字段值,c 表示类别。
对于分类规则的挖掘通常有以下几种方法:决策树方法、贝叶斯方法、人工神经网络方法、粗集方法和遗传算法。不同的算法适用于不同特点的数据。
分类器的构造方法不同分类规则的描述形式也不同。分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。统计方法包括贝叶斯法和非参数法(近邻学习或基于范例的学习) , 对应的知识表示为判别函数和原型事例。机器学习方法包括决策树和规则归纳法, 前者对应的表示为决策树或判别树, 后者为一般的产生式规则。神经网络方法主要是BP 算法, 它的模型表示是前向反馈神经网络模型(由代表神经元的节点和代表联接权值的边组成的一种体系结构) ,BP 算法本质上是一种非线性判别函数[2]。
3 关联规则挖掘与分类规则挖掘的比较
1. 从挖掘的目的来看, 关联规则挖掘主要是发现大
量数据库中项集之间的关联关系, 而分类规则挖掘则是提出一个分类函数或分类模型(也常称作分类器) , 把数据库中的数据项映射到给定类别中的某一个。
2. 从发现规则算法的方法看, 发现关联规则的算法是无指导的学习方法, 也就是没有给定的类别作参考, 发现分类规则的算法是有指导的学习方法。在
分类规则挖掘的过程中要有训练集和测试集, 其中训练集中的数据将被用于建立分类器或模型, 训练集中数据的类别都是预先确定的。
3. 从算法的设计思想看, 尽管关联规则挖掘与分类规则挖掘都是分两个步骤来完成的, 但是它们具体的实现过程完全不同。关联规则挖掘:首先, 找出所有事务数据库中的频繁项集。找到所有支持度大(Itemset ) , 集() , 。对, 对于A , 若满足support -count (A ) /support -count (B ) ≥min -con f , 其中B 为A 的一个非空子集, 则输出规则B ]A 2B 。分类规则挖掘:首先, 建立一个模型, 描述给定的数据类集或概念集(简称训练集) , 然后使用模型对测试集中的数据进行分类。
4. 从关键技术看, 关联规则挖掘最基本的算法就是著名的Agrawal 的Apriori 算法, 是目前最有影响力的算法, 它的基本思想是使用逐层搜索技术来探测Apriori 的性质(
频繁项集的所有非空子集都是频繁的) , 来找出所有的频繁项集。随后的关联规则发现算法大多数建立在Apriori 算法基础上, 或进行改造, 或衍生变种。比如AprioriT id 和AprioriHybrid 算法。分类规则挖掘的关键就是构造分类器, 它有多种构造方法, 例如贝叶斯分类方法是一种具有最小错误率的概率分类方法, 可以用数学公式的精确方法表示出来, 并且可以用多种概率理论来解决。决策树(Deci 2sion Tree ) 又称为判定树, 是运用于分类的一种树结构。其中的每个内部结点(internal node ) 代表对某个属性的一次测试, 每条边代表一个测试结果, 叶结点(leaf ) 代表某个类(class ) 或者类的分布(class distribu 2tion ) , 最上面的结点是根结点。常用算法有I D3,C4. 5,C ART ,CH AI D 等。感知器分类是通过训练模式的迭代和学习算法, 产生线性或非线性可分的模式判别函数。它不需要对各类训练模式样本的统计性质作任何假设, 所以是一种确定性的方法。比如固定增量逐次调整算法、最小平方误差算法。
5. 从规则的判断标准看, 由于发现规则的过程不同, 那么判断规则的标准也显然不同。
对关联规则的主要判断标准是:
支持度:在关联规则X ]Y 中, 支持度表示X 和Y 在记录中同时出现的概率。
可信度:在关联规则X ]Y 中, 可信度表示X 在记录中出现的前提下,Y 出现的概率。
有时挖掘出来的规则虽然满足最小支持度和最小可信度, 但是规则在现实中是没有意义的, 虚假的或用户不感兴趣的。如表1所示, 设有3个项目数据
58
计 算 机 与 现 代 化2006年第7期
集X 、Y 和Z , 则可以发现关联规则X ]Y 和X ]Z , 其
支持度和可信度见表1。
表1 X 、Y 、Z 数据集及其相应的支持度、可信度
数据集
规则
X 11110000
Y 110000Z 0111111
X 5
75
X ]Y
25
50
支持度
(%) 可信度(%)
则挖掘的技术来解决分类规则挖掘方法无法处理的问题。例如, 对于分类规则来说, 有时数据库中的数据不是很精确, 数据集不能划分为正例和反例。那么就不能用示例学习的方法发现分类规则。但是结合关联规则挖掘的技术就可以实现分类规则的发现。利用关联规则技术把原始数据集转换成决策表, 使决策表具有无噪声和代表性高的特点通过决策表进行[5]]。
希望的研究领域, 在商业利益的强大驱动下, 将会不停地促进它们的发展。每年都有许多关联规则挖掘和分类规则挖掘的新方法和模型问世, 人们对它们的研究日益广泛和深入。尽管如此, 关联规则挖掘和分类规则挖掘技术仍面临着问题和挑战。例如, 在关联规则挖掘的过程中, 提供一种与分类规则挖掘技术相结合的方法, 把分类规则挖掘技术融入其中; 在处理大量数据时, 如何提高关联规则挖掘算法的效率; 生成结果的可视化等等, 还有待我们去研究。
参考文献:
[1] Fayyad U M , Piatecsky 2Shapiro G, Smyth P. Advances in
K nowledge Discovery and Data Mining[M].California ,AAAI/MIT Press , 1996. [2] 史忠植. 知识发现[M].北京:清华大学出版社,2002. [3] 王艳. 数据挖掘中关联规则的探讨[J].成都信息学院学
报,2004,19(2) :174.[4] 戴稳胜, 等. 数据挖掘中的关联规则[J].统计研究,2002
(8) :41.[5] 程岩, 等. 一种结合关联规则技术在数据库中挖掘分类
规则的方法[J].计算机应用研究,1999(12) :64～67. [6] 李顺安. 基于关联的自适应分类规则挖掘方法[J].西安
联合大学学报,2003,7(2) :73～76.
从表1可以看出Z 与X 并不相关, 即X ]Z 是一条虚假规则。但是可以看出虚假规则X ]Z 的支持度和可信度却分别超过了规则X ]Y 的支持度和可信度, 然而还不可能找到合适的最小支持度和最小可信度, 使得仅生成规则X ]Y 而不生成虚假规则X ]Z 。为了解决这种问题, 不少学者提出在生成关联规则时, 要加限制条件, 例如, 把兴趣度[3]或者增益[4]加入判断标准中。
对分类规则的判断标准是:
准确率:模型正确预测新数据类标号的能力。速度:产生和使用模型花费的时间。
健壮性:有噪声数据或空缺值数据时模型正确分类或预测的能力。
伸缩性:对于给定的大量数据, 有效地构造模型的能力。
可解释性:学习模型提供的理解和观察的层次。
4 关联规则挖掘与分类规则挖掘的联系
关联规则挖掘与分类规则挖掘之间既有区别又有联系。在发现分类规则的过程中可以采用关联规(上接第55页) 大框架下, 通过引入新概念, 得到一种关联规则挖掘的改进算法Im prove 算法。在对算法进行实验, 并得出Im prove 算法确实能够降低挖掘时间的结论后, 又分析了该算法的其它特点。综上所述, 本文提出的Im prove 算法是一种颇具发展潜力和实用
价值的关联规则挖掘算法。
参考文献:
[1] R Agrawal , T Imielinski , A S wami. Mining ass ociation rules
between sets of items in large database[A].Proceedings of the AC M SIG M OD C on ference on Management of Data[C].1993. 2072216.
[2] Agrawal R , Srikan R. Fast alg orithms for mining ass ociation
rules in large database [A ].Proceedings of 20th International C on ference on Very Large Data Bases[C].1994.
4872499. [3] Han J , Fu Y. Mining multiple 2level ass ociation rules in large
databases [J].IEEE T rans. K nowl. Data Eng. 1999,11(5) :128.
[4] Han Jiawei , Micheline K amber. Data Mining C oncepts and
T echniques[M].北京:机械工业出版社,2001. 158～161. [5] 杜威, 邹先霞. 基于PC 2树的关联规则挖掘方法[J].计
算机工程与设计,2005,l26(2) :445～447. [6] 王创新. 关联规则提取中对Apriori 算法的一种改进[J].
计算机工程与应用, 2004,40(34) :183～185. [7] 任小龙, 吴耿锋, 赵朔. 基于子规则的关联规则生成算
法[J].计算机工程,2004,l30(1) :77～79.
范文四：一种基于关联规则分类的改进方法
掣业业业业业簟簟业躲鬻?数据库与信息处理?弗
凑习降习降习ｌｓ习，ｓ习ｌ｝铆ｓ习ｓ习降赤
一种基于关联规则分类的改进方法
查金水宋良图刘现平
（中科院合肥智能机械研究所，合肥２３００３１）
Ｅ－ｍａｉｌ：ｃｈａｊｉｎｓｈｕｉ＠１２６．ｃｏｒｎ
要论文首先对一种基于关联规则分类的算法做出了分析。然后对算法中的类关联规则的提取方法进行了改进，得
摘
到了一种新的基于关联规则分类的算法。并结合棉花病虫害数据运行的结果对两种算法的运行效率和实用性进行了比较。关键词
关联规则
类关联规则ＦＰ－树分类
文献标识码Ａ
中图分类号ＴＰｌ８１
文章编号１００２—８３３１一（２００６）１０—０１５５—０３
ＡｎＩｍｐｒｏｖｅｄ
Ｍｅｔｈｏｄ
Ｂａｓｅｄ
ｏｎ
ＣｌａｓｓｉｆｉｃａｔｉｏｎｏｆＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓ
ＬｉｕＸｉａｎｐｉｎｇ
ＺｈａＪｉｎｓｈｕｉ
ＳｏｎｇＬｉａｎｇｔｕ
（ＩｎｓｔｉｔｕｔｅｏｆＩｎｔｅｌｌｉｇｅｎｔＭａｃｈｉｎｅｓ．ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ。Ｈｅｆｅｉ２３００３１）
Ａｂｓｔｒａｃｔ：Ｆｒｏｍｅｘｔｒａｃｔｉｏｎｉｎ
ｔｈｉｓ
ａ
ｃｏｎｃｒｅｔｅ
ａｎａｌｙｓｉｓ
ｏｆｔｈｅｃｌａｓｓｉｆｉｅｄ
ａ
ａｌｇｏｒｉｔｈｍ
ｂａｓｅｄ
ｏｎ
ａｓｓｏｃｉａｔｉｏｎｒｕｌｅ，ｗｅｃｌａｓｓｉｆｉｃａｔｉｏｎｂｅｔｗｅｅｎ
ｔｈｅ
ｍａｋｅ
ｆｏｒｉｍｐｒｏｖｅｍｅｎｔｏｆ
ｍｅｔｈｏｄｉｎ
ａ
ｃｌａｓｓａｓｓｏｃｉａｔｉｏｎｐａｒｉｓｏｎ
ｒｕｌｅｓａｎｄ
ｎｅｗａｌｇｏｒｉｔｈｍｂａｓｅｄｐｒａｃｔｉｃａｂｉｌｉｔｙ
ｉｓ
ｏｎ
ｏｆａｓｓｏｃｉａｔｉｏｎ
ｔｗｏ
ｒｕｌｅｓｉｓ
ａｃｑｕｉｒｅｄ
ｔｏ
ｐａｐｅｒ．Ｔｈｅｎ
ｏｆｅｆｆｉｃｉｅｎｃｙ
ａｎｄ
ｍａｄｅ
ａｌｇｏｒｉｔｈｍｓａｃｃｏｒｄｉｎｇ
ｔｈｅ
ｏｐｅｒａｔｉｏｎｒｅｓｕｌｔｏｆ
ｃｏｔｔｏｎｄｉｓｅａｓｅｄａｔａ．
Ｋｅｙｗｏｒｄｓ：ａｓｓｏｃｉａｔｉｏｎｒｕｌｅ，ｃｌａｓｓａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ，Ｆｒｅｑｕｅｎｔ－ｐａｔｔｅｒｎｔｒｅｅ，ｃｌａｓｓｉｆｉｃａｔｉｏｎ
１
引言
对于一些大的数据库来说，建立一个精确而又有效的分类
（２）产生所有的类关联规则。
（３）基于已经产生的类关联规则建立一个分类器。（４）利用分类器对未知类别数据进行分类。
如图１所示，我们首先假设数据集是一个正常的关系表。这个表中包含了带有￡个不同属性值的Ⅳ个案例，这，ｖ个案例已经被划分为ｑ个已知的类。属性值可以是离散的也可以是连续的。对于一个连续的属性值，我们首先将其值的区间离散化成许多小区间。然后再将这些小的区间映射到一系列连续的整型值。
器是数据挖掘和机器学习的一个重要任务——给定一个带有
类别标签的测试数据集，用它来建立一个分类器，然后预测那些未知类别的数据对象。现在的许多分类方法都是基于启发式的搜索技术，比如决策数算法［１】、Ｂａｙｅｓ网络和一些统计学的方法。还有一些在商业化的数据挖掘领域内很少用到的方法，诸如ｋ一最近邻分类、基于案例的推理、遗传算法等。
分类规则的挖掘和关联规则脚的挖掘是两种重要的数据挖掘技术。分类规则挖掘的目标就是找出数据库中的一些规则，组成一个精确的分类器。而关联规则的挖掘就是找出数据库中满足最小支持度与最小确信度约束的规则。对关联规则来说，它的目标是没有预先确定的。而对分类规则的挖掘来说，它有一个预先确定的唯一的目标，即类别标签。分类规则和关联规则的挖掘在实际中都是不可缺少的。因此，数据挖掘技术也已将关联规则挖掘用于分类问题［３１。将两种挖掘技术结合起来对使用者来说既节省时间又方便很多。这两种技术的结合可以产生一种新的分类方法：基于关联规则的分类。在关联规则分类中，规则的右侧固定为类别的属性。我们将这些规则称为类关
联规则（ｃｌａｓｓａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ，ＣＡＲｓ）［４１。
鲞墨鍪塑查，主磊丽网查登塑型苎塑竺差
离散化
产生类关联规则
选择
测试结果分析ｒ
分类
、输入测试数据
建立分类器
优化分类器
●ｒ
＿－－●
图ｌ基于关联规则分类的流程图
设Ｄ为事务集．，是Ｄ中所有项目的集合、ｌ，是类别标签的集合。如果Ｘ∈ｄ，我们称一个数据项ｄ∈Ｄ包含Ｘ∈，，，是数
据项Ｄ的子集。一个类关联规则（ＣＡＲ）就是下面的形式Ｘ—
ｙ，其中Ｘ∈，、Ｙ∈Ｙ。它的支持度与确信度的定义如下：规则Ｒ：
数据挖掘中类关联规则的挖掘主要包括下面几个步骤（如
图１所示）：
Ｘ—ｙ的支持度ｓｕｐ是指Ｄ中有ｓ％的案例包含有带有类别标
签ｙ的项目Ｘ。ｓｕｐ与Ｄ中的含有Ｘ的案例数之比称为确信度
‘
（１）如果是连续的属性值，需要将其离散化。
基金项目：国家８６３高技术研究发展计划资助项目（编号：２００３ＡＡｌ１８０７０）
作者简介：查金水（１９７８一），男，硕士研究生，主要研究方向：数据挖掘，复杂系统。宋良图（１９６３一），男，副研究员，主要研究方向：智能化农业信息系
统。刘现平（１９７９一），男，硕士研究生，主要研究方向：图像检索系统，图形与图像处理。
计算机工程与应用２００６．１０
１５５
万方数据
ｃｏｎｆｏ我们的目标就是根据使用者给定的最小支持度ｍｉｎｓｕｐ和最小置信度ｍｉｎｃｏｎｆ阀值来产生所有的ＣＡＲｓ集，然后根据产生的ＣＡＲｓ建立一个分类器。
２
ＣＢＡ算法的描述
ＣＢＡ算法阁包含两个步骤：类关联规则的产生和分类器的
建立。２．１
基本概念
产生规则的首要条件就是要找出所有大于最低支持度阀
值的规则。一个规则项ｒｕｌｅｉｔｅｍ的形式如下：。这里的ｃｏｎｄｓｅｔ是一项集．ＹＥＹ是一个类别标签。Ｃｏｎｄｓｅｔ的支持度（ｃｏｎｄｓｕｐＣｏｕｎｔ）是指Ｄ中包含ｃｏｎｄｓｅｔ的数。规则项ｒｕｌｅｉｔｅｍ的支持度（ｒｕｌｅｓｕｐＣｏｕｎｔ）是指Ｄ中类别标签是Ｙ的ｃｏｎｄｓｅｔ的数。每一个ｒｕｌｅｉｔｅｍ可以表示一条规则：ｃｏｎｄｓｅｔ－－－＊ｙ。它的支持度是（ｒｕｌｅｓｕｐＣｏｕｎｔ／ＩＤＩ）４１００％，这里ｌＤＩ是数据集的大小。它的确信度是（ｒｕｌｅｓｕｐＣｏｕｎｔ／ｃｏｎｄｓｕｐＣｏｕｎｔ）４１００％。
对于有同样ｃｏｎｄｓｅｔ的项集来说。确信度最高的将被选为可能的规则ＰＲ（ｐｏｓｓｉｂｌｅｒｕｌｅｓ）来代表这个项集。如果有超过一个的项集具有相同的最高的确信度，我们将随机的选择一个项集。如果一条规则的确信度大于最低确信度阀值，我们说这条规则是精确的。而类关联规则集就是包含那些既频繁又精确的
所有的ＰＲ。
２．２产生类关联规则
ＣＢＡ产生类关联规则的算法ＣＢＡ—ＲＧ如下：
１ＦＩ＝｛ｌａｒｇｅ１－ｒｕｌｅｉｔｅｍｓ｝；２ＣＡＲｌ＝ｇｅｍＲｕｌｅｓ（‘）；
３ｐｒＣＡＲｌ＝ｐｒｕｎｅＲｕｌｅｓ（ＣＡＲｌ）；
４ｆｏｒ（ｋ＝２；Ｒ—ｌ≠∥；＾＋＋）ｄｏ５Ｇ＝ｃａｎｄｉｄａｔｅＧｅｎ（疋一１）；
６ｆｏｒｅａｃｈｄａｔａ
ｃａｓｅ
ｄ∈Ｄ
ｄｏ
７Ｑ＝ｒｕｌｅＳｕｂｓｅｔ（ｑ，ｄ）；
８ｆｏｒｅａｃｈｃａｎｄｉｄａｔｅ
ｃ∈ｑｄｏ
９ｃ．ｃｏｎｄｓｕｐＣｏｕｎｔ＋＋；
１０ｉｆｄ．ｃｌａｓｓ＝ｃ．ｃｌａｓｓｔｈｅｎｃ．ｒｕｌｅｓｕｐＣｏｕｎｔ＋＋１１ｅｎｄ
１２ｅｎｄ１３Ｅ＝（ｃ∈ＱＩｃ．ｒｕｌｅｓｕｐＣｏｕｎｔ≥ｍｉｎｓｕｐ）；
１４ＣＡＲ女＝ｇｅｎＲｕｌｅｓ（Ｅ）；１５
ｐｒＣＡＲ＾＝ｐｒｕｎｅＲｕｌｅｓ（ＣＡＲＩ）；１６ｅｎｄ１７
ＣＡＲｓ＝Ｌ）ｋＣＡＲ＾；
１８ｐｒＣＡＲｓ＝ＵＩｐｒＣＡＲＩ；
由上述的算法可以看出，在算法的每个循环中都要进行四个主要的操作。如在第ｋ循环中，首先通过第南一１循环中的频繁项集疋一。来产生频繁候选ｋ项集Ｃｋ，这一步主要是通过使用了ｃａｎｄｉｄａｔｅＧｅｎ函数来实现。接着扫描数据库来更新Ｃ。中各个候选集的支持度计数，然后这些新的频繁项组成新的Ｅ。算
法使用ｇｅｎＲｕｌｅｓ函数来产生规则ＣＡＲ。。最后使用对这些ＣＡＲ。
规则进行剪枝。
２．３建立分类器
为了在已经获得的规则上面建立一个最好的分类器，需要选择那些错误最少的规则。设Ｒ是所有已经产生的规则，Ｄ是
１５６
２００６．１０计算机工程与应用
万
方数据训练数据。算法的基本目的就是从Ｒ中选择一些优先度比较高的规则来替代Ｄ。在这里优先度的定义为：给定两条规则，ｒ．和‘，■＞ｒＪ（即■的优先度比ｌ高）需满足下列条件：
（１）如果ｔ的确信度比一的高，或
（２）两者的确信度相同，但是一的支持度比‘的大，或（３）两者的确信度和支持度相同，但ｒ，产生的比ｒｉ早（也就是在规则的左手边ｒ．有更少的属性）；
我们建立的分类器的形式如下：
口１，１＂２，…，ｒ，ｄｅｆａｕｌｔ＿ｃｌａｓｓ＞，这里‘ｅＲ，如果ｂ＞ａ，则Ｌ＞ｒ６。ｄｅｆａｕｌｔ＿ｃｌａｓｓ是默认的类。在对一条未知类别的案例进行分类时，第一条满足这个案例的规则即可以分类这个案例。如果没有规则满足。则将这个案例归为默认的类。
分类器的建立有三个步骤：
（１）对所有Ｒ中的规则根据关系按降序排列。这确保我们的分类器可以选到优先度最高的规则。
（２）对于每条规则ｒ∈Ｒ，我们到Ｄ中去寻找可以被ｒ替代（即它们满足规则ｒ的左手边属性值）的案例，如果ｒ至少可以正确分类，即可以替代，一个案例，它将是我们分类器的一条潜在的规则。对于那些可以被分类的案例将其从Ｄ中移出来。对于Ｄ中那些不能被规则ｒ替代的案例．我们用ｄｅｆａｕｌｔ＿ｃｌａｓｓ来标识。然后来计算由分类器和默认的类别号分类的错误的案例数。这里的ｄｅｆａｕｌｔ＿ｃｌａｓｓ是指Ｄ中剩余案例中大部分案例所属
的那个类。
（３）将分类器中那些不能增加分类器准确率的规则抛弃，剩下的未被抛弃的规则和ｄｅｆａｕｌｔ＿ｃｌａｓｓ一起组成我们的分类器。具体的算法参见［５］。
３改进的基本措施
由上述对ＣＢＡ算法的描述我们可以看出．类关联规则的产生算法与Ａｐｒｉｏｆｉ算法类似。与Ａｐｒｉｏｒｉ不同的是在算法过程中要对两项进行支持度的计算，即ｃｏｎｄｓｅｔ和ｒｕｌｅｉｔｅｍ。这个主要是为了后面可以计算ｒｕｌｅｉｔｅｍ的确信度。以前针对ＣＢＡ算法的一些改进主要是集中在ＣＢＡ—ＲＧ阶段．为了使数据库可以一次性的载入到内存中，对数据库进行划分，每部分采用单独的支持度计数。它对于数据库的划分和规则的产生采用不同的算法，选择效率最高的一个［６１。
在类关联规则的挖掘过程中，由于采用了Ａｐｒｉｏｒｉ算法同，需要不断地产生候选集，虽然利用Ａｐｒｉｏｒｉ性质，可以对候选集进行缩减以达到提高挖掘效率的目的，仍然存在两个问题：（１）产生的候选集过多；（２）需要对数据库进行反复扫描，通过一定的模式匹配的方式对大量候选集进行检验。为了避免产生的候选集过多．以及提高挖掘的效率，我们提出了一个新的基于关
联规则分类的算法——ＮＣＢＡ。
为了发现分类规则，ＮＣＢＡ首先挖掘训练数据，通过支持度和置信度阀值来发现所有的频繁项集。这也是一个典型的频繁模式关联规则挖掘任务。为了使挖掘的效率更高，ＮＣＢＡ算法使用ＦＰ一树［８１算法。ＦＰ一树的频繁模式生成方法比Ａｐｒｉｏｒｉ类的方法更快，特别是对于大数据集、低的支持度阀值、长模式来说效率更高。通过使用ＦＰ一树挖掘类关联规则来改进ＣＢＡ算法的主要思想通过如下的例子来说明：
给定一个如表１所示的训练数据集ｒ。假定设最小支持度阀值是２，确信度阀值是５０％。我们首先对数据集ｒ进行扫描
一次，然后找出那些支持度大于２的那些项，项集肚ｋ，ｄ∥ｋ｝
称为频繁项集。其它的支持度小于最小支持度的项不能在关联规则中起到作用。所以将被剪枝。
表ｌ调练数据集
然后对Ｆ中的项，按照支持度计数的降序排列，排列的结果是Ｆ—ｌｉｓｔ＝ａ—ｄ一户ｋ。然后再扫描一次训练数据集来构建一棵ＦＰ一树（如图２所示）。先创建树的根结点，用Ｎｕｌｌ表示。接着我们按照Ｆ—ｌｉｓｔ中出现的项和项的顺序对训练数据集中的每个元组进行选取。例如：在第一个元组中，只有（ａ，，）出现在Ｆ—ｌｉｓｔ中．将其选取出来，作为最左边的一个分枝插入到树中。类别标签放在路径的最后一个节点上。
在训练集中的元组将会在树中分享一个共同的前缀。例如，第二个元组的属性值（ｎ，ｄ；，）。这样在Ｆ—ｌｉｓｔ中将会和第一个元组分享同一个前缀ａ。因此在ＦＰ一树中也同时分享最左边分枝的ａ的子路。所有相同属性值的节点作为一个队列从头节点开始连起来。
根据Ｆ—ｌｉｓｔ．我们可以将类关联规则集划分为无重复的四个子集：（１）含有ｋ的集；（２）含有厂但是不含有ｋ的集；（３）含有ｄ但不含有ｋ和厂的集；（４）只含有ａ的集。
图２ＦＰ一树
图３合并节点ｋ之后的ＦＰ－树
为了找到含有ｋ的子集的规则，我们观察ＦＰ一树，遍历含有ｋ指针的节点组成一个后一ｄｂ数据库．我们可以发现危一ｄｂ含有三个元组：（ａ，ｄ，厂，ｋ）：Ｃ，（ａ，ｄ，ｋ）：Ｃ，ｋ：Ａ，这就是所有含有ｋ的元组。在训练集中找出所有含有的频繁模式的问题就简化为在詹一ｄｂ数据库中挖掘频繁模式。
由上述可知．在｜｜｝一ｄｂ中，ａ和ｄ都是频繁的属性值，因为它们都大于或等于支持度的门槛值。又因为在｜ｊ｝一ｄｂ中，ｋ在每一个元组中都出现，因此必定是频繁的。所以我们也不需要计算ｋ的支持度。我们可以通过循环的构造ＦＰ一树和ｄｂ数据库来挖掘ｄｂ数据库中的类关联规则。
在七一ｄｂ数据库中，ａ和ｄ正好都是同时出现，因此ｎｄ是一个频繁模式。ａ和ｄ是以的两个子集，与甜有相同的支持
度。基于类别标签的信息，我们可以产生三条规则：ⅡＪ｝一Ｃ，幽一
Ｃ，觎一Ｃ。它们三个的支持度皆为２、确信度皆为１００％。
在搜寻到所有的含有ｋ的规则之后．所有的ｋ的节点都分
万
方数据别和它们各自的父节点合并。也就是说在ｋ结点中的类别标签将在其父节点的标注。缩减之后的树如图３所示。余下的规则的提取同上述的类似。
由此我们可以看出，在对树的挖掘过程中．将原有的发现较长频繁模式的问题转化为反复寻找较短的模式而后再连接其前缀的过程。因此和ＣＢＡ中采用的Ａｐｒｉｏｆｉ算法相比，不必重复扫描数据库。可以降低搜索成本，极大的提高效率。
由于ＦＰ一树在扫描数据库的过程中，需要将数据库一次性装入内存中来构建树。因此对机器的内存有一定的要求，如果数据库比较大的话，我们可以首先对数据库进行分割，然后再对每一个分割后的数据库用ＦＰ一树算法提取类关联规则。
４实验结果及分析
我们采用了某一地区的棉花病虫害数据为例测试算法的效果。本实验以Ｄｅｌｐｈｉ６，０为开发环境，数据存储在ａｃｃｅｓｓ数据库中，即为分类的样本空间。部分数据如图４所示。
图４棉花病虫害数据
由图４可以看出，我们将前面四个属性：病斑颜色、病害部位、病害形状、病害特征作为ｃｏｎｄｓｅｔ集，最后的一个属性：病的种类作为类别标签ｙ。然后我们对数据进行转化，将这些文本数据转化为布尔型数据，以方便规则的挖掘。接着选定ｍｉｎ—得到的类关联规则建立分类器。我们使用样本中的９０％的数据为训练数据。其余的为测试数据。图５即为得到的分类器中的类关联规则。
图５
训练样本为９０％时得到的分类器中的类关联规则
我们分别使用了三组数据进行了测试，样本数分别为４０、
０００个。两种算法测试比较的结果如表２所示。
表２两种算法运行时间比较ｓ
由实验结果可以看出，随着样本数目的增加，ＮＣＢＡ算法（下转２０３页）
计算机工程与应用２００６．１０
１５７
ｓｕｐ＝１５％，ｍｉｎｃｏｎｆ＝８０％来进行类关联规则的挖掘，然后对挖掘的运行时间明显比ＣＢＡ算法少，效率增加。随着数据库的不断增大，ＣＢＡ算法运行效率低的瓶颈就暴露出来了。因此改进后
２００和１
表ｌ几种方法的检测结果比较
图像序号实有目标数目ＣＡ—ＣＦＡＲ结果Ｇ０一ＣＦＡＲ结果本文方法结果
１１７１７１５１７
２１４１３１４１４
３２３２１２０２３
（ａ）原始图象
（ｂ）ＣＡ—ＣＦＡＲ检测结果
６结论
本文提出了一种在ＳＡＲ图像中检测目标的方法。该方法采用基于ｗｅｉｂｕｌｌ分布模型的ＣＦＡＲ检测技术，对背景区域分块，根据每个子块的统计参数和空间分布，确定子块类型，根据各子块类型不同，选择不同的参考单元确定阈值。同时根据目标灰度、方差特征剔除明显不可能为目标的像素，利用多数滤
（ｅ）本文ＣＦＡＲ方法检测结果
（ｄ）本文方法最终结果
波器和目标形状特征，进一步排除虚警。相比于ＣＡ—ＣＦＡＲ方法．本文方法保留了算法简单、同质区检测性能好的优点，同时．对存在杂波边缘或多目标干扰的情况，也能有很好的检测效果。实验证明本文方法检测性能好，自适应性强，适应于大多数ＳＡＲ图像的目标检测。（收稿日期：２００５年９月）
图５实验结果图像
检测结果中，ＣＡ—ＣＦＡＲ方法有２个虚警、２个漏警，本文方法有１个虚警，无漏警，且轮廓的完整性保持更好。可以看出，本文方法相比ＣＡ—ＣＦＡＲ方法，具有更好的检测效果，说明该方法是有效的。对检测结果进一步判别。虚警目标被滤除，得
到目标的ＲＯＩ。
参考文献
１．Ｑｕｏｏ
Ｈ
Ｐｈａｍ，ＴｉｍｏｔｈｙＭＢｍｓｎａｎ，Ｍａｒｋ
Ｔａｒｇｅｔｓｉｎ
ＳＡＲ
ＪＴＳｍｉｔｈ．ＭｕｌｔｉｓｔａｇｅＡｌｇｏ－
表ｌ给出了三种方法在其他几幅图像的检测结果，比较得出：ＣＡ—ＣＦＡＲ和ＧＯ—ＣＦＡＲ分别只对部分图像有较好的检测效果，本文方法对所有图像都有较好检测效果。在背景平稳区域，本文方法性能接近ＣＡ—ＣＦＡＲ；在杂波边缘，ＣＡ—ＣＦＡＲ虚警增多，而本文方法较好地抑制了虚警，检测性能接近Ｇ０一ＣＦＡＲ；在多目标区域，ＣＡ—ＣＦＡＲ由于目标间的相互干扰，检测出目标轮廓不完整甚至漏警，本文方法由于自动排除了干扰目标影响，比ＣＡ—ＣＦＡＲ和ＧＯ—ＣＦＡＲ具有更好的检测效果。在一幅图像中．杂波边缘和多目标情况经常可能同时存在，ＣＳＳ０一ＣＦＡＲ或ＣＳＧＯ—ＣＦＡＲ方法只是单纯地选大或者选小，不能对图象灰度分布变化自适应，当图像复杂时难以有好的效果。本方法的最大优势在于结合了各种方法的优点，智能判定区域类型。在各种复杂环境下都具有较好的检测性能。
（上接１５７页）
ｒｉｔｈｍｆｏｒＤｅｔｅｃｔｉｏｎｏｆ
Ｉｍａｇｅ
Ｄａｔａ［ｊ］．ＳＰＩＥ，１９９７；３０７０
２．王世锦，孟健青．单元筛选后作最小选择的ＣＦＡＲ自适应检测器【Ｊ】．雷达与对抗．２００４；（４）
３．贾承丽．计科峰，匡纲要等．利用ＧａｍｍａＣＦＡＲ进行ＳＡＲ图像目标检测［Ｊ】．系统工程与电子技术，２００５；（１）
４．何友，关键，孟祥伟．雷达自动检测和ＣＦＡＲ处理方法综述忉．系统工程与电子技术，２００１；２３（１）
５．ＭｉｃｈａｅｌＢａｓｅｄ
Ｅｌｅｃｔ
ｏｎ
ＥＳｍｉｔｈ．Ｐｒａｍｏｄ
Ｄａｔａ
Ｋ
Ｖａｒｓｈｎｅｙ．Ｉｎｔｅｌｌｉｇｅｎｔ
Ｔｒａｎｓａｃｔｉｏｎｓ
ｏｎ
ＣＦＡＲＰｒｏｃｅｓｓｏｒ
ａｎｄ
Ｖａｒｉａｂｉｌｉｔｙ［Ｊ】．ＩＥＥＥ
Ａｅｒｏｓｐａｃｅ
ｔｏｎｉｃＭｉｎｇ
Ｓｙｓｔｅｍｓ，２０００Ｗｏｎｇ，Ｃｈｅｅ
Ｈａｎｇ
Ｃｈａｎｇ，Ｗｅｉｘｉａｎ
Ｉｎｔｅｒｎａｔｉｏｎａｌ
Ｌｉｕ
ｅｔ
６．Ｃｈａｒ
ｉｎ
ａ１．ＣＡ—ＣＦＡＲ
ｏｎ
ｗｅｉｂｕｌｌ
Ｂａｃｋｇｒｏｕｎｄ［Ｃ］．Ｉｎ：２ｎｄ
ＣｏｎｆｅｒｅｎｃｅＭｉ—
ｃｒｏｗａｖｅ７．Ｍ
ａｎｄＭｉｌｌｉｍｅｔｅｒＷａｖｅ
ＴｅｃｈｎｏｌｏｇｙＰｒｏｃｅｅｄｉｎｇｓ，２０００
Ｓｋｏｌｎｉｋ．Ｒａｄａｒ
Ｈａｎｄｂｏｏｋ［Ｍ］．２ｎｄｅｄｎ．，ＭｃＧｒａｗＨｉｌｌ，ｌ９９０
Ｄａｔａｂａｓｅｓ［Ｃ］．Ｉｎ：ＰｒｏｃｏｆｔｈｅＡＣＭＳＩＧＭＯＤ
ｏｎ
ＳｅｔｓｏｆＩｔｅｍｓ
ｉｎ
Ｌａｒｇｅ
的ＮＣＢＡ算法的实际应用性也较ＣＢＡ有了很大的提高。
Ｉｎｔｅｒｎａｔｉｏｎａｌｃｏｎｆｅｒｅｎｃｅ
Ｍａｎａｇｅｍｅｎｔ
ｏｆ
Ｄａｔａ，Ｗａｓｈｉｎｇｔｏｎ
Ｄ
Ｃ，
１９９３：２０７～２１６
５
结论
本文通过对基于关联规则的分类方法ＣＢＡ的分析，指出
３．ＨａｎＪＷ，ＫａｍｂｅｒＭ．数据挖掘：概念与技术【Ｍ］．北京：机械工业出版
社．２００ｌ
４．ＬｅｎｔＢ，ＳｗａｍｉＡ，ＷｉｄｏｍＪ．Ｃｌｕｓｔｅｒｉｎｇ
ｔｈｅ
１３“Ｉｎｔｅｒｎａｔｉｏｎａｌ
Ｃｏｎｆｅｒｅｎｃｅ
ｏｎ
ａｓｓｏｃｉａｔｉｏｎ
ｒｕｌｅｓ［Ｃ］．Ｉｎ：Ｐｒｏｃｏｆ
它的效率不足之处：它需要反复扫描数据库，而且会产生大量的候选集，通过一定的模式匹配方法对大量候选集进行检验。我们新的ＮＣＢＡ算法通过使用ＦＰ一树来提取类关联规则，由于ＦＰ一树算法比较简单．只需扫描一遍数据库，可以将较长的频繁模式转化为先寻找较短的模式而后再连接其前缀的过程。有效的降低了搜索成本。通过对算法的改进使运行效率有了很大的提高，并举例说明了获取类关联规则的具体过程。最后通过一个实际的例子说明两种算法的效果，证明了改进后算法的实用性和效率都有了很大的提高。（收稿日期：２００５年１１月）
Ｄａｔａ
Ｅｎｇｉｎｅｅｒｉｎｇ，Ｂｉｒｍｉｎｇｈａｍ，
１９９７：２２０～２３１５．Ｌｉｕ
Ｂ，Ｈｓｕ
Ｗ，ＭａＹ．ＩｎｔｅｇｒａｔｉｎｇＣｌａｓｓｉｆｉｃａｔｉｏｎａｎｄ
ＡｓｓｏｃｉａｔｉｏｎＲｕｌｅ
ｏｎ
Ｍｉｎｉｎｇ［Ｃ］．Ｉｎ：Ｐｒｏｃｏｆｔｈｅ４ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ
Ｄｉｓｃｏｖｅｒｙ
Ｋｎｏｗｌｅｄｇｅ
ａｎｄＤａｔａ
Ｍｉｎｉｎｇ，ＮｅｗＹｏｒｋ，１９９８
Ｋ．Ｉｍｐｒｏｖｉｎｇ
ａｎ
６．ＬｉｕＢ．Ｍａ
Ｙ，Ｗｏｎｇ
ＡｓｓｏｃｉａｔｉｏｎＲｕｌｅ
ｏｎ
ＢａｓｅｄＣｌａｓｓｉ—Ｐｒｉｎｃｉｐｌｅｓ
ｔｉｅｒ［Ｃ］．Ｉｎ：Ｐｒｏｃｏｆｔｈｅ４ｔｈＥｕｒｏｐｅａｎＣｏｎｆｅｒｅｎｃｅ
Ｐｒａｃｔｉｃｅ
ｏｆＲ
ａｎｄ
ＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙ
ｉｎ
Ｄａｔａｂａｓｅｓ，Ｌｙｏｎ，２０００
Ｍｉｎｉｎｇ
ｏｎ
７．Ａｇｒａｗａｌ
２ＳｒｉｋａｎｔＲ．ＦａｓｔＡｌｇｏｒｉｔｈｍｓｆｏｒ
Ａｓｓｏｃｉａｔｉｏｎ
Ｒｕｌｅｓ［Ｃ】．
Ｉｎ：Ｐｒｏｃｏｆｔｈｅ２０ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ
ＶｅｒｙＬａｒｇｅＤａｔａｂａｓｅｓ．
参考文献
１．ＱｕｉｎｌａｎＪ—Ｒ．Ｃ４．５：Ｐｒｏｇｒａｍｓ
ｆｏｒ
Ｓａｎｔｉａｇｏ，Ｃｈｉｌｅ，１９９４；９：４８７～４９９
８．Ｈａｎ
ＭａｃｈｉｎｅＬｅａｒｎｉｎｇ．Ｃａｌｉｆｏｒｎｉａ：Ｍｏｒｇａｎ
Ｊ
Ｗ．ＰｅｉＪ，ＹｉｎＹ．ＭｉｎｉｎｇＦｒｅｑｕｅｎｔＰａｔｔｅｒｎｓｗｉｔｈｏｕｔＣａｎｄｉｄａｔｅ
Ｋａｕｆｍａｎｎ，１９９３
２．Ａｇｒａｗａｌ
Ｒ，ＩｍｉｅｌｉｎｓｋｉＴ，Ｓｗａｍｉ
Ａ．ＭｉｎｉｎｇＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓｂｅｔｗｅｅｎ
Ｇｅｎｅｒａｔｉｏｎ［Ｃ］．Ｉｎ：Ｐｒｏｃｏｆ１９“ＡＣＭＳＩＧＭＯＤＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ
ｏｎ
ＭａｎａｇｅｍｅｎｔｏｆＤａｔａ，Ｄａｌｌａｓ，２０００：２０７－２１６
计算机工程与应用２００６．１０
２０３
万方数据
范文五：基于关联规则的武器装备体系能力分类
２０１０．０３＾工自动化
ＯｒｄｎａｎｃｅＩｎｄｕｓｔｒｙＡｕｔｏｍａｔｉｏｎ
’１’
２９（３）
ｄｏｉ：１０．３９６９０．ｉｓｓｎ．１００６—１５７６．２０１０．０３．００１
基于关联规则的武器装备体系能力分类
黄魏，田亮。杨克巍，高兵
（国防科学技术大学信息系统与管理学院，湖南长沙４１００７３）
摘要：针对武器装备体系能力分类涉及利益相关者众多的特点，提出基于关联规则的武器装备体系能力分类方法．介绍关联规则的基本概念，对武器装备体系能力进行预处理后，采用ＦＰｇｒｏｗｔｈ算法挖掘能力间的关联规则，然后对产生的关联规则剪技，根据关联规则完成能力的分类，通过编程对基于规则的武器装备体系能力分类进行测试．分类实验表明，该方法可以完成能力的自动分类，并具有较好的准确率和召回率．
关键词：关联规则；ＦＰ树；能力；分类中图分类号：Ｃ９３４
文献标识码：Ａ
ＣａｐａｂｉｌｉｔｙＣａｔｅｇｏｒｉｚａｔｉｏｎｏｆＷｅａｐｏｎｓＥｑｕｉｐｍｅｎｔＳｙｓｔｅｍ
Ｗｅｉ，ＴＩＡＮＬｉａｎｇ，ＹＡＮＧ
Ｂａｓｅｄ
ｏｎ
ＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓ
ＨＵＡＮＧ
Ｋｅ．ｗｅｉ，ＧＡＯＢｉｎｇ
（Ｓｃｈｏｏｌ
ｏｆ
ＩｎｆｏｒｍａｔｉｏｎＳｙｓｔｅｍ＆Ｍａｎａｇｅｍｅｎｔ，ＮａｔｉｏｎａｌＵｎｉｖｅｒｓｉｔｙｏｆＤｅｆｅｎｓｅＴｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ４１００７３，Ｃｈｉｎａ）
ｃａｐａｂｉｌｉｔｙｃａｔｅｇｏｒｉｚａｔｉｏｎｓｙｓｔｅｍｆｏｒｔｈｅｓｔａｋｅｈｏｌｄｅｒｓｉｎｖｏｌｖｅｄｉｎ
ｏｎ
ａ
Ａｂｓｔｒａｃｔ：Ｗｅａｐｏｎｓ
ｆｏｒｗａｒｄ
ａ
ｌａｒｇｅｎｕｍｂｅｒｏｆｆｅａｔｕｒｅｓ，ｐｕｔａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ．Ｉｎｔｒｏｄｕｃｅｔｈｅ
ｎｅｗｍｅｔｈｏｄｏｆｃａｐａｂｉｌｉｔｙｃａｔｅｇｏｒｉｚａｔｉｏｎｏｆｗｅａｐｏｎｓｅｑｕｉｐｍｅｎｔｓｙｓｔｅｍｂａｓｅｄ
ｏｆａｓｓｏｃｉａｔｉｏｎ
ｂａｓｉｃｃｏｎｃｅｐｔｓａｌｇｏｒｉｔｈｍ
ｔｅｓｔ
ｔｏ
ｒｕｌｅｓ，ａｆｔｅｒ
ｐｒｅｐｒｏｃｅｓｓｉｎｇｔｈｅｗｅａｐｏｎｓｅｑｕｉｐｍｅｎｔｆｉｌｔｒａｔｅｄｔｈｅａｓｓｏｃｉａｔｉｏｎ
ｓｙｓｔｅｍｃａｐａｂｉｌｉｔｙ，ｕｓｅｔｈｅＦＰ－Ｇｒｏｗｔｈ
ｏｎ
ｐｌｅｔｅａｂｉｌｉｔｙｃａｔｅｇｏｒｉｚａｔｉｏｎ，
ｔｈｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄｂｙｐｒｏｇｒａｍｍｉｎｇ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｍｅｔｈｏｄｃａｎａｃｈｉｅｖｅｔｈｅａｕｔｏｍａｔｉｃ
ｒａｔｅ．
ｍｉｎｅｔｈｅａｓｓｏｃｉａｔｉｏｎ
ｒｕｌｅｓ，ａｎｄｒｕｌｅｓ．Ｔｈｅｎ，ｂａｓｅｄ
ｃａｔｅｇｏｒｉｚａｔｉｏｎｏｆｃａｐａｂｉｌｉｔｉｅｓａｎｄｈａｓｂｅｔｔｅｒａｃｃｕｒａｃｙａｎｄｒｅｃａｌｌｉｎｇ
Ｋｅｙｗｏｒｄｓ：Ａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ；ＦＰ?ｔｒｅｅ；Ｃａｐａｂｉｌｉｔｙ；Ｃａｔｅｇｏｒｉｚａｔｉｏｎ
Ｏ
引言
武器装备体系能力是武器装备体系需求开发
联或相关联系Ｈ１。
有ｍ个不同项的集合，＝｛‘，如，…，‘），其中的元
的核心要素【ｌ。２】，面向需求的能力是利益相关者对于武器装备体系完成特定战略规划的期望与约束，表现为武器装备体系执行或完成特定使命任务所具备的“本领”或具有的“潜力”【３】。传统的能力分类多是人工完成，而武器装备体系分类结果存在不确定的问题，不利于武器装备体系层面能力分类的达成共识，而且人工分类也会耗费大量人力、物力和时间。故提出基于关联规则实现武器装备体系能力的自动分类，以规范武器装备体系能力分类的过程。
１
１．１
素称为项，记Ｄ为事务丁的集合，即Ｄ＝环互，一Ｚ），
事务ｒ是项的集合，并且ｒ￡，。设Ａ、且是一个，中项的集合，如果Ａ∈丁，Ｂ∈丁，那么称事务ｒ包含Ａ、曰。一个关联规则是形如Ａ一÷召的表达式，其中Ａ∈，，Ｂｃ，且ＡｎＢ＝ａ，称Ａ为规则的前项集（前件），Ｂ为规则的后项集（后件）。
１．２
ＦＰ
ｇｒｏｗｔｈ算法ｌ，６１
现有的关联规则挖掘算法多是以Ａｐｒｉｏｒｉ算法为基础的，产生关联规则时需要生成大量的候选项目集。为了避免生成候选项目集，Ｈａｒｔ等提出了基于ＦＰ树生成频繁项目集的ＦＰｇｒｏｗｔｈ算法，该算法首先把频繁项目的挖掘问题转换成挖掘ＦＰ树问题，然后使用ＦＰ树项目集增大挖掘频繁项目集。
ＦＰ树挖掘过程可描述为：由长度为１的频繁项目开始，构造其条件项目基和条件ＦＰ树，并递归地在该树上进行挖掘，项目增长通过后缀项目与条件ＦＰ树产生的频繁项目连接实现。其中，ＦＰ树
关联规则
基本概念
关联是指两个或多个变量的取值或者活动之
间存在某种规律性，这种相互关联的规律可以理解为关联规则。关联规则用来描述在一个事务中交易之间同时出现的规律的知识模式，这些规则展示属
性一值频繁地在给定对象集中一起出现的条件，关
联规则挖掘可以发现大量数据中项集之间有趣的关
收稿日期；２００９－１０—１５；修同日期：２００９—１２—０４
基金项目：“十一五”武器装备预先研究项目（５１３３００１０２）．国家自然科学基金（７０９０１０７４）
作者简介：黄魏（１９８２一），男，湖南人，国防科技大学在读博士研究生，从事复杂系统、体系需求建模技术、文本挖掘研究。
万方数据
?２?
兵工自动化
第２９卷
的构造过程可描述为：首先创建树的根结点，用“ｎｕｌｌ”标记；扫描交易数据集ＤＢ，每个事务中的项目按照支持度递减排序，并对每个事务创建一个分枝，通常当为一个事务考虑增加分枝时，沿共同前缀上的每个结点的计数值增加１，为跟随在前缀之后的项目创建结点并链接：为方便遍历树，创建一个频繁项目列表，使得每个项目通过一个结点头指针指向它在树中的位置。
ＦＰ－ｇｒｏｗｔｈ算法将发现大频繁项目集的问题转换成递归地发现一些小频繁项目，然后连接后缀。它使用最不频繁的项目后缀，提供了好的选择性，大大降低了搜索开销。
挖掘武器装备体系能力关联规则，可发现能力之间的关联关系，根据这种关联关系可判断多个能力之间存在一定的相似性，是能力分类的重要依据。
２武器装备体系能力分类
在武器装备体系能力分析阶段，武器装备体系能力的外在表现形式是文本，文本内容即为利益相关者对武器装备体系能力的具体描述，包括其名称、承担的具体任务及其完成任务的手段方法等。因此，可以基于文本内容挖掘武器装备体系能力的关联规
则，并以此为依据对武器装备体系能力进行分类。
基于关联规则的武器装备体系能力分类首先提取待测试武器装备体系能力文本的特征，而后根据用户指定的最小支持度发现频繁项集，根据最小置信度对产生关联规则并进行规则剪枝，最后根据修剪后的关联规则将测试能力分组到相应的类别中。
２．１
武器装备体系能力的预处理
武器装备体系能力预处理是指对从能力文本
中抽取出的元数据即特征进行量化，以结构化形式描述文本信息，即将能力文本转化为特征词的集合。能力文本的特征词作为武器装备体系能力的中间表示形式，在分类时用以评价能力之间或能力与能力类之间的关联程度。
武器装备体系能力有类标签Ｃ，其特征集为Ｔ＝｛‘，ｔ２，…，ｋｌｏ用Ｄ＝｛Ｃ，ｔｌ，ｆ２，…，ｔ。ｌ表示该武器装备体系能力模型，则武器装备体系能力集可以表示成事务集，其项集由武器装备体系能力特征属性集（即词条）和武器装备体系能力所属类别组成，所有的关联规则都从事务集中产生。２．２基于ＦＰ树的关联规则挖掘
武器装备体系能力分类中感兴趣的关联规则
万
方数据形如：丁＿Ｃ（其中ｒ表示能力特征集，Ｃ表示武
器装备体系能力类标签）的事务。因此，首先要找到规则前件ｒ中的频繁项集，即能力特征词，然后将频繁项集中的能力特征词与其类标签Ｃ（规则后件）约束合并转为规则，最后计算规则集中每条规则的置信度，作为最后的结果保存。
基于ＦＰ树的武器装备体系能力关联规则挖掘算法实现的核心代码如下，其中的一些函数是系统自定义的。
ｔｈｉｓ．Ｍｉｎ—Ｓｕｐ＝ｍ—ｓ＊Ｔ＿ｎｕｍｂｅｒＯ；／／计算最小支持数
ＴｒａｎｓａｃｔｉｏｎｎｅｗＣａｐａｂｉｌｉｔｙＴ＝ｎｅｗ
Ｔｒａｎｓａｃｔｉｏｎ（）；
，，生成新能力事务
ｔｈｉｓ．Ｔ—Ｂｕｉｌｄ（一ｌｉｓｔＴｒａＬｉｓｔ，一ｌｉｓｔＳｔｒＬｉｓｔｌ）；
Ｉ／构建训练文本事务库，生成１．项频繁集
ｔｈｉｓ．Ｔｉｄｙ（——ｌｉｓｔＳｔｒＬｉｓｔｌ，．—ｌｉｓｔＴｒａＬｉｓｔ，．—ｌｉｓｔＴｒａＬｉｓｔｌ）；／／整理频集和事务库，生成频繁事务库
Ｌｉｓｔ一ｌｉｓｔ—ＴｒｅｅＮｏｄｅ＝ｎｅｗＬｉｓｔ０；
一ｌｉｓｔ＿ＴｒｅｅＮｏｄｅ＝ｔｈｉｓ．ＣｒｅａｔＦＰ＿Ｔｒｅｅ（＿ｌｉｓｔＳｔｒＬｉｓｔｌ，．．１ｉｓｔＴｒａＬｉｓｔ）；｜｜莹斌ＦＰ．Ｔｒｅｅ
Ｌｉｓｔ＞＞一ｌｉｓｔ＿ｌｉｓｔ—ｌｉｓｔ＿Ｎｏｄｅ＝ｎｅｗ
Ｌｉｓｔ＞＞Ｏ；
，，生成各节点到根节点的路径ｆｏｒｅａｃｈ（ＩｔｅｍＴａｂｌｅｉｔ
ｉｎ—ｌｉｓｔ—ＴｒｅｅＮｏｄｅ）
Ｉ
Ｌｉｓｔ＞一ｌｉｓｔ—ｌｉｓｔ－，ｒｒｅｅＰａｔｈ＝ｎｅｗ
Ｌｉｓｔ＞（）；
ｆｏｒｅａｃｈ（ＦＰ——ＴｒｅｅＮｏｄｅｆｐｉｎｉｔ．—．Ｌｉｓｔ——ＦＰ＿ＴｒｅｅＮｏｄｅ）
一ｌｉｓｔ＿ｌｉｓＬＴｒｅｅＰａｔｈ．Ａｄｄ（ｆｐ．ＣｏｎｖｅｒＴｏＰａｔｈ（ｆｐ））；ｉｆ（＿ｌｉｓｔ—ｌｉｓｔ＿ＴｒｅｅＰａｔｈ．Ｃｏｕｎｔ！＝Ｏ）
．．１ｉｓｔ＿ｌｉｓｔ
ｌｉｓｔ＿Ｎｏｄｅ．Ａｄｄ（一ｌｉｓｔ
ｌｉｓｔ
ＴｒｅｅＰａｔｈ）；
ｌ
ｆｏｒｅａｃｈ（Ｌｉｓｔ＞一ｌｉｓＬｌｉｓ￡＿乃ｅｅＰａｔｈｌｉｎ
．．１ｉｓｔ＿ｌｉｓｔｌｉｓｔ．．Ｎｏｄｅ）
ｔｈｉｓ．Ｉｎｔｅｒｓｅｃｔｉｏｎ（一ｌｉｓｔ—ｌｉｓｔ—ＴｒｅｅＰａｔｈ１，（ｄｏｕｂｌｅ）
ｔｈｉｓ．Ｍｉｎ—Ｓｕｐ）；／／生成同名节点的公共路径。
ｔｈｉｓ．ｃｒｅａｔＲｕｌｅｓ（ｄｏｕｂｌｅｍｉｎ＿ｃｏｎｆ）；／／生成关联规则
２．３关联规则剪技
关联规则丁—Ｃ的作用度（１ｉｆｔ）表示为
ｆ＿只ＣＩ乃／只ｏ［７１：
１）如果Ｉ（Ｔ—ｃ）的值大于ｌ，称丁和ｃ正相关，
表明每一个的出现都蕴含另一个的出现；
２）如果Ｚ仃＿ｃ）的值等于１，则丁和Ｃ相互独
立：
３）如果Ｚ（丁＿ｏ的值小于１，说明它们负相关。
因此，要保存的关联规则就是那些作用度大于ｌ的关联规则。
对于通过作用度筛选后的规则，按照置信度、支持度优先级递减的方式从大到小排列，如果２个
第３期
黄巍，等：基于关联规则的武器装备体墨堕力分＿耋
?３‘
规则的前件相同，则保留置信度大的规则，如果置
信度相同，则保留支持度大的规则‘８１。
２．４能力分类
获得关联规则后，就可以对体系能力进行分类。在提取待分类体系能力的特征集ｒ后，将生成的关
联规则与ｒ进行匹配，此时会有匹配成功与失败２种情况。当匹配成功时分类完成，当匹配失败时，可以采用以下策略：
１）抛弃关联规则，按照最优匹配原则，将待分
配，获得分类；
２）以某步长为标准，减小最小支持度（或置信３）将待分类的体系能力添加到训练能力文本中，对新训练能力文本进行聚类分析，获得待分类
的体系能力的类别。
基于关联规则的武器装备体系能力分类受训因素的影响，它是一种相对分类，而非绝对的。
实验结果
用美国海军能力领域中的能力文本的译本构
图１
武器装备体系能力分类程厚界面
输入水上作战及其特征属性后执行分类程序采用所开发的程序对武器装备体系能力分类进
万
方数据图２能力分类结果
基于关联规则的分类是一种经验分类，对于军事领域有一定的风险性：对于特殊问题，需要发挥相关人员的主观能动性。该方法的主要作用在于形
成武器装备体系能力分类的规范以获得利益相关者
的广泛认可，辅助决策。实验结果表明，该方法基
本满足能力分类的需要，能发挥辅助决策作用。在下一步的研究中，将研究能力与能力类之间的关联
度，进一步提高武器装备体系能力分类的准确率。
参考文献：
【ｌ】Ｊｏｉｎｔ
Ｃｈｉｅｆｏｆｓｔａｆｆ．ＣＪＣＳｌ３１７０．０１７Ｄ
ｊｏｉｎｔｃａｐａｂｉｌｉｔｉｅｓ
ｉｎｔｅｇｒａｔｉｏｎａｎｄ
ｄｅｖｅｌｏｐｍｅｎｔｓｙｓｔｅｍ［Ｓ／ＯＬ］．２００５－０８—１６．
：Ｈ．ｄｔｉｃ．ｍｉｌ／ｃｊｃｓ—ｄｉｒｅｃｔｉｖｅｓ，ｉｎｄｅｘ．ｈｔｍ
【２】ＭＯＤＡＦ
ＰｒｏＪｅｃｔＲｅｖｉｅｗＢｏａｒｄ．ＭＯＤＡｒｃｈｉｔｅｃｔｕｒａｌ
Ｆｒａｍｅｗｏｒｋ
Ｏｖｅｒｖｉｅｗ
１．０
【ＯＢ／ＯＬ］．
２００５—８—３１．
：／／．ｍｏｄａｌ．ｃｏｒｎ．
【３】赵青松．黄魏。鲁延京。等．基于概念格的体系使命任
务与能力关系分析【Ｊ】．系统仿真学报，２００９，１２（１２）：
３７８２－３７８４．
［４】Ｒ．Ａｇｒａｗａｌ．Ｔ．Ｉｍｉｅｌｉｎｓｋｉ，ａｎｄ
Ａ．Ｓｗａｍｉ．Ｍｉｎｉｎｇ
ａｓｓｏｃｉａｔｉｏｎ
ｒｕｌｅｓ
ｂｅｔｗｅｅｎ
ｓｅｔｓ
ｏｆ
ｉｔｅｍｓｉｎ
ｌａｒｇｅ
ｄａｔａｂａｓｅｓ［Ｒ］．Ｐｒｏｃｅｅｄｉｎｇｓ
ｏｆｔｈｅＡＣＭ
ＳｌＧＭＯＤ
Ｃｏｎｆｅｒｅｎｃｅ
ｏｎ
Ｍａｎａｇｅｍｅｎｔｏｆｄａｔａ．１９９３：２０７—２１６．
【５】易彤，徐宝文，吴方君．一种基于ＦＰ树的挖掘关联规
则的增量更新算法【Ｊ】．计算机学报，２００４，２７（５）：
７０３—７１０．
【６１ＨａｎＪ．ｃｔａ１．Ｍｉｎｉｎｇｆｆｅｑｕｅｎｔｐａｔｔｅｒｎｓｗｉｔｈｏｕｔｃａｎｄｉｄａｔｅ
ｇｅｎｅｒａｔｉｏｎ［Ｊ】．Ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２０００ＡＣＭＳＩＧＭ
ＯＤＣｏｎｆｅｒｅｎｃｅｏｎ
ＭａｎａｇｅｍｅｎｔｏｆＤａｔａ．Ｄａｌｌａｓ．ＴＸ．２０００：
１～１２．
【７】马光志，张生庭．基于关联规则的Ｗｅｂ文档分类［Ｊ】．
计算机工程与设计，２００５，２６（９）：２５１５－２５１８．
【８】张帆，严聪，郛建亮．改进灰色关联分析在导弹对抗预
警雷达效能评估中的应用【Ｊ】．四川兵工学报，２００９（９）：
１０７—１１１．
类体系能力与训练能力文本中的体系能力进行匹
度）的预定值，再次进行分类；
练文本、用于特征选择的统计量、规则选择原则等
３
建了分类的训练文本和测试文本，通过编程对基于关于规则的武器装备体系能力分类方法进行了测试。分类程序界面如图１。
即可将其分组至海上防护能力类，如图２，这个结果与美国海军能力领域中的分类是一致的。
行测试，准确率为８６．７％，召回率为８１．２５％。
４结束语
基于关联规则的武器装备体系能力分类
作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：
黄魏， 田亮， 杨克巍， 高兵
国防科学技术大学,信息系统与管理学院,湖南,长沙,410073兵工自动化
ORDNANCE INDUSTRY AUTOMATION2010,29(3)1次
参考文献(8条)
1. MODAF Project Review Board MOD Architectural Framework Overview 1.0 2005
2. Joint Chief of staff CJCSI3170.017D joint capabilities integration and development system 20053. 张帆;严聪;郭建亮 改进灰色关联分析在导弹对抗预警雷达效能评估中的应用[期刊论文]-四川兵工学报2009(09)
4. 马光志;张生庭 基于关联规则的Web 文档分类[期刊论文]-计算机工程与设计 2005(09)5. Han J Mining frequent patterns without candidate generation 2000
6. 易彤;徐宝文;吴方君 一种基于FP树的挖掘关联规则的增量更新算法[期刊论文]-计算机学报 2004(05)7. R.Agrawal;T.Imielinski;A.Swami Mining association rules between sets of items in large databases1993
8. 赵青松;黄魏;鲁延京 基于概念格的体系使命任务与能力关系分析[期刊论文]-系统仿真学报 2009(12)
本文读者也读过(10条)
1. 葛冰峰. 陈英武. 廖良才. 舒宇 基于多视图的武器装备体系结构描述方法研究[会议论文]-2008
2. 熊健. 杨克巍. 李孟军. XIONG Jian. YANG Ke-wei. LI Meng-jun 武器装备体系需求变更活动研究[期刊论文]-兵工自动化2007,26(9)
3. 许秉军. 李孟军. 李兴兵. 杨克巍 装甲装备体系对抗仿真评估系统研究[会议论文]-2007
4. 岑凯辉. 谭跃进. 李孟军. CEN Kai-hui. TAN Yue-jin. LI Meng-jun 一种轻量级的装备需求开发过程改进方法[期刊论文]-系统工程与电子技术2007,29(4)
5. 李善飞. 鲁延京. 杨克巍. 谭跃进. LI Shan-fei. LU Yan-jing. YANG Ke-wei. TAN Yue-jin 武器装备体系能力形式化描述研究[期刊论文]-兵工自动化2010,29(2)
6. 舒宇. 谭跃进. 廖良才. SHU Yu. TAN Yue-jin. LIAO Liang-cai 基于能力需求的武器装备体系作战能力评价[期刊论文]-兵工自动化2009,28(11)
7. 陈英武. 姜江 关于体系及体系工程[会议论文]-2008
8. 梁晓庆. 黄魏. 杨克巍. LIANG Xiao-qing. HUANG Wei. YANG Ke-wei 武器装备体系能力生成过程[期刊论文]-兵工自动化2010,29(1)
9. 陈英武. 姜江 关于体系及体系工程[期刊论文]-国防科技2008,29(5)
10. 葛冰峰. 陈英武. 舒宇. GE Bing-feng. CHEN Ying-wu. SHU Yu 基于多视图的武器装备体系结构描述方法[期刊论文]-火力与指挥控制2010,35(4)
引证文献(1条)
1. 顾小林. 张大为. 张可. 浦徐进. 曹文彬 基于关联规则挖掘的食品安全信息预警模型[期刊论文]-软科学 2011(11)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_bgzdh201003001.aspx
转载请注明出处范文大全网 » 2聚类、分类、关联规则
