基于支持度和置信度智能优化的关联分类算法

基于支持度和置信度智能优化的关联分类算法

王秀枝 安建成

【摘 要】摘 要 针对传统关联分类算法中支持度和置信度阈值无法根据问题规模准确设定，导致分类器的分类效果受人为因素影响的缺陷，提出一种基于智能优化思想的关联分类算法。该算法对CBA关联分类算法进行改进，利用模拟退火技术良好的全局搜索能力在解空间内对支持度和置信度阈值进行优化，从而使分类准确率达到全局最优。实验表明，与传统的关联分类算法相比，该方法可以有效地避免阈值设置不合理而影响分类效果的弊端，使分类结果更加精准。

【期刊名称】计算机应用与软件 【年(卷),期】2013(000)011 【总页数】4

【关键词】关键词 支持度 置信度 智能优化 CBA 模拟退火

0 引 言

关联分类[1]是分类规则挖掘和关联规则挖掘两大技术的结合，是数据挖掘领域及机器学习领域的重要技术之一。其基本思想是利用关联规则挖掘算法，从训练样本集中产生一组频繁规则和精确规则，然后利用这些规则构成分类器对测试样本分类。许多实验表明，与其他分类算法相比，关联分类算法具有分类准确率高、分类规则易于理解和可重用性好的优势。然而，现有的关联分类算法对决定分类关联规则产生的支持度阈值和置信度阈值的设定都是依赖于统一的经验值，难以保证分类器达到更好的分类效果。

为了克服基于关联规则的分类算法对支持度和置信度阈值设置的敏感性，文献

[2]提出了将优化求解策略引入到关联分类过程中。该文献利用爬山搜索技术来获得使分类准确率较高的支持度和置信度阈值，在一定程度上解决了阈值设置不合理而影响分类效果的问题。

然而爬山搜索技术是一种典型的贪心算法，利用该算法优化支持度和置信度阈值，容易使分类准确率陷入局部最优[3]，不能保证分类器达到最好的分类效果。本文针对该问题，对CBA关联分类算法进行改进，利用模拟退火良好的全局搜索能力优化支持度和置信度阈值，使分类效果更加精准。

1 基于关联规则的分类算法——CBA算法

1.1 关联分类算法相关定义[2]

定义1 规则项(ruleitem)：表示为〈condest,y〉,每个规则项表示一个规则condest-〉y,其中条件集condest是一个项集，y是一个类标签。

定义2 条件集支持度(condsupcount)：指数据库中包含condest的事例(case)数。

定义3 规则支持度(rulesupcount)：指数据库中包含condest及标注类别y的事例数。

定义4 支持度(support)：指数据库中包含condest及标注类别y的事例数与数据库中总的事例数的比值，表示为： (|D|表示数据库中的事例总数)

定义5 置信度(confidence)：指数据库中包含condest及标注类别y的事例数与包含condest事例数的比值，表示为：

定义6 频繁规则：一个规则，当其支持度不小于最小支持度或支持度阈值，则该规则是频繁的。

定义7 精确规则：一个规则，当其置信度不小于最小置信度或置信度阈值，则该规则是精确的。

1.2 CBA分类算法基本思想

1998年，Liu Bing等人首次将分类挖掘和关联挖掘整合，提出了基于关联规则的分类算法[4-8]CBA。该算法分以下两步完成：

(1) 规则生成(CBA-RG)：根据由经验设定的支持度和置信度阈值发现规则右部(y)为类标签的分类关联规则CARS(class association rules)： (a) 支持度阈值决定对频繁大项集的挖掘； (b) 置信度阈值决定最终产生的分类规则。

(2) 分类器构建(CBA-CB)：对产生的分类规则进行剪枝操作，即从发现的CARS中选择优先级高的规则来覆盖训练集，生成分类器。 1.3 CBA分类算法存在的问题

从上述算法基本思想可以分析得到支持度和置信度阈值在一定程度上会影响该算法的分类效果：

(1) 如果minsup和minconf设置过低，则导致在生成频繁规则项集过程中出现组合爆炸，使其呈指数级增长，算法无法进行；

(2) 如果minsup和minconf设置过高，则难以发现足够的分类规则，导致对分类样本的覆盖率较低。

而原始CBA算法支持度和置信度阈值无法根据问题规模准确设定，而是依赖于经验值，导致分类准确率受人为因素影响。所以将智能优化技术引入该算法非常必要。模拟退火SA(Simulated Annealing)是一种通用的智能优化算法，该算法依照Metropolis准则将搜索空间扩展到整个解空间，具有良好的全局优