基于Apriori算法的关联规则分析

王晓丽 奚克敏 刘占波

摘  要： 用糖尿病患者患病记录作为实例详细阐述了基于Apriori算法的关联规则问题。探讨了Apriori算法在关联规则中求解频繁项集的基本思想，并用实例描述了算法的执行过程。

关键词： Apriori;关联分析;数据挖掘;医学信息学

中图分类号： TP393.4    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2019.02.005

【Abstract】： This paper elaborates the association rule based on Apriori algorithm taking the diabetic patient's disease record as a case. The core idea of association rule based on Apriori algorithm for mining large itemsets is discusses， furthemore the example show the execution process of the algorithm.

【Key words】： Apriori; Association analysis; Data mining; Medical informatics

0  引言

1993年，Agrawal等人借鉴了Petr Hjek[1]的逻辑推理思想，提出了关联规则的概念[2]。Agrawal举出了一个最典型的使用案例，超市购物篮的购物分析（basket analysis）。在顾客的大量购物中超市发现了一个有趣的现象，40%左右的年轻男士购买完尿布也会购买啤酒。于是超市将尿布和啤酒放在一起进行促销，使得尿布和啤酒的销量大增。利用类似的关联发现超市可以获得各种关于顾客的相似商品购买习惯，这样能够帮助其开发更好的营销策略从而利于商品销售[3]。关联规则的实际应用远不仅如此，在金融分析、工程建筑、铁路航空、大数据、网络安全、医疗卫生、生物医药等各个领域都与关联分析紧密相关。目前关联规则已成为数据挖掘的一个重要研究方向， 大量的科研人员改进相关算法并将其应用于具体案例中。在关联规则各种算法中，Agrawal等人在1994年发表的Apriori算法是目前影响最为深远的算法之一[4]，本文基于Apriori算法对经典的关联规则进行分析并对其执行过程进行探讨。

1  关联规则及其抽象描述

在实际中患者往往会同时患有多种疾病，很多疾病都是由并发症所引起，比如糖尿病往往会同时与高血压、高血脂、冠心病、胰腺炎、肥胖症、痛风、酒精性肝炎、周围神经炎等相互关联，还会引起视网膜病变，肾脏及神经性病变等并发症[5]。医疗从业人员往往会在这些大量的患者电子病例数据库中寻找这些疾病的相互关联性，疾病的种类可能是成千上万，电子病例数据库中的病例数量可以达到几十万条以上[6]。

为了描述方便，将几万种疾病种类简化为5种：糖尿病，高血压，脂肪肝，白内障，肾病。即假设患者病例中只患这5种或5类疾病，并假设这5种疾病在病例数据库中按照字典序号排列，既糖尿病排在高血压的前面。将病例数据库中的几十万条病例简化为10条并去除杂项。具体描述如图1所示。

2  关联规则暴力算法

根据关联规则的基本定义可以得到最基本的求解关联规则简单的暴力算法：对于m个项组成的集合，首先用穷举法生成所有的关联规则，然后对每一个关联规则扫描数据库计算出支持度和置信度，和规定的阈值进行比较来生成强关联规则。根据排列组合可以知道利用窮举方式生成的所有关联规则数量为：，并且每一个关联规则计算支持度和置信度都需要扫描事务数据库一次，扫描事物数据库的时间复杂度将达到指数级。

利用暴力算法亦可先穷举出所有的频繁项集，共有个，然后用频繁项集再生成强关联规则。可以看出这2种方法的时间复杂度都是指数级。

如果设定的最小支持度和最小置信度很小接近于零，那么暴力算法穷举出的所有关联规则都是强关联规则，任何改进算法同暴力算法一样都需要生成所有的关联规则。在实际应用中给定的阈值不是很低时，求得的强关联规则往往没有那么多，尤其是频繁项集数可能很少。对于一个几十万条记录，成千上万种图书的图书管理系统寻找关联规则，利用时间复杂度是指数级的暴力算法显然不是很好的选择。这就需要我们另外寻找更为高效的算法应用于关联分析。

3  Apriori算法

3.1  算法基本思想

强关联规则的生成需要满足2点：最小支持度，最小置信度。于是可以通过某种方法先生成满足最小支持度的项集，即频繁项集，不频繁项集及所对应的关联规则可以迅速排除。然后通过频繁项集来得到强关联规则，生成方法可以简单对每个频繁项集用暴力法生成其每个非空子集，然后用该集合作为关联规则的前项，用频繁项集和子集的差集作为关联规则后项，如果其置信度大于最小置信度则生成强关联规则。Apriori算法是快速生成频繁项集的一种算法。

Apriori算法首先将项集I中的每一项生成1-项集（生成的项集可能是频繁项集，也可能不是频繁项集，称之为候选项集），然后扫描数据库D，将所有1-项集和最小支持度进行比较生成频繁1-项集。将频繁1-项集中的项两两拼接生成候选2-项集，再次扫描数据库D，将所有由频繁1-项集产生的候选2-项集和最小支持度进行比较生成频繁2-项集。通过频繁2-项集生成候选3-项集，然后生成频繁3-项集…直到没有新的频繁项集产生为止。在频繁（k-1）- 项集拼接成候选k-项集的过程中，需要找出前k-2项相同，最后一项不同的项集进行依次两两拼接，由于项集中的项已经按照字典序号排列，因此生成的项集不会产生重复项。