賢南大学学报(自然科学版)JournalofJinanUniversity(NaturalScience)临床数据中挖掘关联规则算法的选用殷彬，方思行(音南大学计算机科学系，广东广州510632)【摘要］对典型的挖掘关联规则的Apriori算法和tP-growth算法进行比较分析•然后，结合临床数据的特点，建议在临床数据关联规则挖掘中采用FP-growth算法.［关键词］数据挖掘；关联规则；Apriori算法；FT-growth算法；支持度；稀疏数据集；稠密数据集［中图分类号］TP311［文献标识码］A［文章编号］1000・9965(2004)0—0026・04数据挖掘(血tamining)是指从大型数据库中提取潜在的、可理解的、有用的规律性知识或指导性规则的处理过程.关联规则(associationnile)是数据挖掘研究中一个巫要方面.挖掘关联规则的算法非常多，有R.Aprawal等人⑴提岀的Apriori算法、Park等人⑵提出的DHP算法、Brin等人⑶提出的DIC算法、Toivonen等人⑷的抽样算法J.Han等人廿⑹提出FP-growth算法和H-Mine算法.其中以Apriori算法和FP-growth算法最为著名.面对众多的算法，为了在临床数据中挖掘出关联规则，我们应该采取哪种算法才能比较高效地进行挖掘呢？本文将对典型的Apriori算法和FP-growth算法进行比较分析，然后根据临床数据本身的特点，决定采用何种算法.1基本概念设/二｛",「2,…，心｝是m个不同项的集合.给定一个事务数据库。，其中每一个事务T是/中某一组项的集合，即TQI.每一个事务都与一个唯一标识符TID相联.假设？!是一个项集，事务T包含4当且仅当ACT.关联规则是形如A斗B的蕴涵式，其中AU/,BU/,并且4D=0・如果事务数据库D中有s%的事务包含4和则称关联规则在D中具有支持度(support)s%・如果D中包含4的事务中有c%同时包含则称关联规则A=>B在D中具有置信度(confidence)c%・挖掘关联规则就是要挖掘出所有同时具有不小于用户指定的最小支持度(min.sup)和最小置信度(min.conf)的关联规则⑴.关联规则挖掘分为两个子问题：(1)寻找所有支持度不小于最小支持度的项集，即频繁项集.(2)利用频繁项集生成所需的关联规则，根据最小置信度选取关联规则.第1个子问题更重要，也更为烦琐.关联规则挖掘的主要工作都集中在发现频繁项集中.如果一个数据集是满足公式I/I二0(loglDII)的集合，则称为是稀疏数据集，反之则称［收稿日期】2003-05^21［基金项目］国家自然科学基金重点资助顶目(9020903)；广东省'自然科学基金资助项R(021149)［作者简介］殷彬(1978-)•男•族士研究生•研究方向：数撫挖掘与时公数据库.通讯联系人：方思行.第25卷第1期20M年2月度是10.1•如图1、图2、图3和图4所示.10'10q蚤劭，000图2稠密数据集T25I5D10K上空间占用一支持度曲线为稠密数据集，其中I/I是事务的平均长度，IDII是数据集中不同项的数目•例如，当数据集中有128个不同的项，而事务的平均长度小于7时，则该数据集是稀疏的.2算法比较分析Apriori算法使用的是一种逐层搜索的迭代方法-项集用于探索％+1)-项集.首先找出频繁1-项集的集合，记为J.然后在儿的基础上进行连接操作，产生候选2■项集的集合,再在候选2~项集的集合中进行剪枝操作•产生频繁2-项集的集合L2.类似地，在L2的基础上找出L3.如此下去，直到不能找到频繁k-项集为止.FP-growth算法采取分而治之的策略：在保持项集关联信息的情况下，把数据库压缩到一棵频繁模式树(FP-Tree),它比原始数据库小很多；然后，将压缩后的数据库按照频繁项投影,分成一些条件数据库，并分别挖掘每个数据库，这样就减少了后续的扫描数据库的时间.它又采取频繁模式增长的方式，不产生候选项集，这使得它在挖掘的过程中不会产生数据库中没有的新事务.而Apriori算法则可能产牛大量的候选项集，同时可能需耍巫复地扫描数据库.下面是用4个数据集进行实验的结果比较67】.其中,Gazelle数据集是…个稀疏数据集.它是从Gazelle.com获得的对该网站访问的数据集合(点击记录).它包含了59602个事务，在事务集中总共有1000个项，每个事务含的项不超过267项，平均事务长度为2.5.25I5D10K是一个用合成数据产生器产生的稠密数据集，包含了10000个事务，在事务集中总共有1000个项，每个事务含的项不超过25项，平均事务长度是15.BMS-POS数据集是一个稀疏数据...