Apriori优化算法在临床数据挖掘中的应用分析

2013-08-08陈安娜

长春师范大学学报 2013年4期

陈安娜

（漳州卫生职业学院信息技术部，福建漳州 363000）

以电子病历、医学影像、病理参数、化验结果等临床数据为基础建立的医学数据库是一个复杂类型数据库系统，这些临床信息具有隐私性、多样性、不完整性、冗余性、异质性和缺乏数学性质的自身特殊性和复杂性，使得临床数据挖掘与常规的数据挖掘之间存在着较大的差异。关联规则挖掘是从大量数据中发现项集之间有趣的关联或相关联系，在临床中常用于疾病相关因素分析、疾病预测等。如何发现频繁项集是关联规则挖掘的核心问题，本文提出Apriori改进算法，通过提高发现频繁项集的效率，促进疾病的诊断与治疗。

1 关联规则的基本概念

关联规则挖掘[1]是指从一个大型事务数据库中发现项集之间所隐藏的有趣的相关联系，即从数据集中识别出频繁项集，然后利用这些频繁项集创建描述关联关系规则的过程，产生强关联规则。

一个事务数据库（事务集）的关联规则挖掘描述如下：设项集I={i1,i2,…,in}，事务集D={t1,t2,…,tm}，每个事务ti（i=1,2,…,m）都是I上的一个非空子集，每一个事务都与一个唯一的标识符TID(Transaction ID)对应。

关联规则是一个项集I的子集组成的蕴涵式，即形如A圯B的蕴涵式，其中A奂I，B奂I，且A∩B=覫。

支持度s：指A和B这两个项集在事务集D中同时出现的概率，support(A圯B)=P(A∪B)=|A∪B|/|D|。置信度c：指出现项集A的事务集D中，项集B也同时出现的概率，conficence(A圯B)=P(A|B)=P(A∪B)/P(A)。为了发现有意义的规则，需要预先设定两个阈值，即最小支持度（min_sup）和最小置信度（min_conf）。同时满足最小支持度和最小置信度的规则，称为强关联规则（强规则）。

2 Apriori算法优化

在关联规则挖掘的整个过程中，频繁项集的产生是核心问题。在众多频繁项集挖掘算法中，Apriori算法[2]是一种典型的挖掘布尔关联规则频繁项集的基本算法。它是利用层次顺序搜索的循环方法来完成频繁项集的挖掘工作，首先找出频繁1-项集L1；然后利用L1来挖掘频繁2-项集L2；不断如此循环，直到无法找到更多的频繁k-项集的集合Lk为止。此算法利用了两个基本性质：(1)一个频繁项集的所有非子集必定也是频繁的；(2)一个非频繁项集的任一超集必定也是非频繁的。

Apriori算法结构简单，易于理解，但由于数据库的规模一般都很大，在每进行一次迭代的时候要扫描一次数据库，多次扫描数据库导致开销非常大；同时，在迭代过程中要在内存中产生处理和保存候选频繁项集，可能产生大量候选项，统计支持度非常耗时，从而影响频繁项集的挖掘效率。现在基于文献[5]所给的病人就诊数据进行算法优化分析，产生频繁项集。

2.1 事务集的布尔矩阵表示

对于任一给定的事务集D，令

f：D→R，其中：R=f(D)=(rij)n×m.

这里

于是，事务集D经过一次扫描后，在f的作用下映射成布尔矩阵R。对于文献[5]所给的病人就诊数据库，如表1所示，可映射成图1所示的布尔矩阵R。

表1 病人就诊数据表

图1 布尔矩阵表示就诊数据库

2.2 无向项集图的定义与构建

2.2.1 无向项集图(Undirected itemsets graph，UDISG)

(1)UDISG(V，E)中，V表示结点集，是数据库中症状和疾病的集合{v1,v2,…vn}，每个结点包含结点名称、结点出现次数和指向关联结点的指针三个属性。(2)UDISG（V，E）中，E表示边集，是边的集合，包含边的名称和边出现次数两个属性。

2.2.2 构建UDISG

设最小支持度为20%，即每个频繁项集至少有2个以上的支持。(1)扫描矩阵R，R中的每个项集作为一个结点，各项集的支持度计数为矩阵行向量之和。构成无向项集图的结点必须满足最小支持度的要求。(2)两结点（病状或疾病）之间的边可以通过矩阵R中对应行向量的运算来确定。当结点A、B对应的行向量按位不为空，且与运算所得的行向量之和不小于最小支持度时，则结点A、B之间有一条边存在，A、B对应的矩阵行向量与运算后，各位之和就是边出现的次数。图2给出了图1所示的布尔矩阵而生成的无向项集图。边出现的次数不小于2，则结点A与结点B之间存在一条边。

图2 矩阵R生成的UDISG

算法1 构建UDISG

输入：事务集D，最小支持度min_sup

输出：UDISG

2.3 基于深度优先的无向项集图频繁项集挖掘算法

本算法遍历无向项集图是采用深度优先（DFS）[3]搜索策略。过程描述如下：(1)从图中的任意一个结点vi出发，搜索UDISG；(2)结点{vi}组成了满足最小支持度min_sup的频繁1-项集L1；(3)任意一对相邻结点{vi，vj}组成了满足最小支持度min_sup的频繁2-项集L2；(4)图中存在n(n≥3)个结点的环，并且这n个结点的所有子集都是频繁的，则这n个结点{vi，vj,…,vn}组成了满足最小支持度min_sup的频繁n-项集Ln。

算法2 UDISG频繁项集发现算法

输入：UDISG

输出：频繁项集L

根据算法2，可推出图2中包含的频繁1-项集L1={S1，S2，A1，A2}；频繁2-项集L2={{S1，S2}，{S1，A1}，{S1，A2}，{S2，A1}，{S2，A2}}；频繁3-项集L3={{S1，S2，A1}，{S1，S2，A2}}。

2.4 结果分析

以上将优化的Apriori算法应用在文献[5]给出的病人就诊数据挖掘的实例中，产生的频繁项集与文献[5]利用基本的Apriori算法产生的频繁项集结果一致。与基本的Apriori算法相比，优化的Apriori算法有以下优点：(1)使用优化的Apriori算法只需扫描一次病人就诊数据库，而基本的Apriori算法需要反复扫描数据库，在文献[5]中使用基本的Apriori算法需要对病人就诊数据库进行3次扫描；(2)优化的Apriori算法遍历一次无向项集图即可得到新的频繁项集，因此当事务集和最小支持度发生变化时，可以动态生成频繁项集，而基本的Apriori算法会产生大量的候选项集。在遍历图时，DFS的时间复杂度是由结点的个数、频繁项集的长度和邻接表的长度决定，因此执行时间要远远小于基本的Apriori算法。