基于扩展概念格的带约束关联分类规则挖掘方法

翟悦,李楠,于文武

(1.大连科技学院 数字技术学院，辽宁 大连116052；2.大连交通大学 软件学院，辽宁 大连 116028) *

近年来采用关联规则构造分类器的关联分类方法广泛应用于医疗、社会服务等领域，然而产生的关联分类规则CARs(Class Association Rules)往往会包含大量冗余规则，对此许多学者展开了带约束的关联分类算法研究，该类算法主要分为事前处理与事后处理两种策略，采用约束事前处理方法如： CBC[1]、FP-growth[2]，这类算法当用户关心的约束条件变化后，算法不得不重新扫描数据库，根据新约束集重新构建分类器，不具备重用性；采用约束事后处理方法如： CCAR[3]、MAC[4]等方法. 该类算法会产生大量候选CARs从而降低算法性能.

本文采用约束事后处理方法，为解决产生候选项目集过多导致效率低下等问题：本文利用扩展概念格结构存储频繁项目集FIs (Frequent Itemsets)，运用结点之间关系定理快速在概念格中搜索符合约束条件的CARs；格结点在信息不丢失的前提条件下大大减少形成分类规则的数量，差集(diffset)概念引入不仅降低格结点内存占用，还能加快对类属性支持度和置信度计算，使得改进后的挖掘算法在时间和空间上具备良好性能.当约束条件变化时无需重新建立概念格，仅需在格上重新搜索.

1 基本定义

1.1 关联分类规则相关概念

设数据库D=(AEC)，其中：一个项目集合由条件属性A={A1,A2,…,An}构成，每一个条件属性Ai可以取某一个特定的值，项目集X={(Ai1,ai1), (Ai2,ai2),…,(Ain,ain)}，类属性C={c1,c2,…,ck}.见表1.

表1 范例数据库D

定义1关联分类规则R形如蕴含式：X→Cj，其中Cj∈C,X为项目集[5]

例……