临床数据中挖掘关联规则算法的选用

《临床数据中挖掘关联规则算法的选用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第25卷第1期20M年2月賢南大学学报(自然科学版)JournalofJinanUniversity(NaturalScience)临床数据中挖掘关联规则算法的选用殷彬，方思行(音南大学计算机科学系，广东广州510632)【摘要］对典型的挖掘关联规则的Apriori算法和tP-growth算法进行比较分析•然后，结合临床数据的特点，建议在临床数据关联规则挖掘中采用FP-growth算法.［关键词］数据挖掘；关联规则；Apriori算法；FT-growth算法；支持度；稀疏数据集；稠密数据集［中图分类号］TP311［文献标识码］A［文章编号］1000・9965(2004)0—0026

2、・04数据挖掘(血tamining)是指从大型数据库中提取潜在的、可理解的、有用的规律性知识或指导性规则的处理过程.关联规则(associationnile)是数据挖掘研究中一个巫要方面.挖掘关联规则的算法非常多，有R.Aprawal等人⑴提岀的Apriori算法、Park等人⑵提出的DHP算法、Brin等人⑶提出的DIC算法、Toivonen等人⑷的抽样算法J.Han等人廿⑹提出FP-growth算法和H-Mine算法.其中以Apriori算法和FP-growth算法最为著名.面对众多的算法，为了在临床数据中挖掘出关联规则，我们应该采取哪种算法才能比较高效地进行挖掘呢？本文将对典

3、型的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%・挖掘关联规则

4、就是要挖掘出所有同时具有不小于用户指定的最小支持度(min.sup)和最小置信度(min.conf)的关联规则⑴.关联规则挖掘分为两个子问题：(1)寻找所有支持度不小于最小支持度的项集，即频繁项集.(2)利用频繁项集生成所需的关联规则，根据最小置信度选取关联规则.第1个子问题更重要，也更为烦琐.关联规则挖掘的主要工作都集中在发现频繁项集中.如果一个数据集是满足公式I/I二0(loglDII)的集合，则称为是稀疏数据集，反之则称［收稿日期】2003-05^21［基金项目］国家自然科学基金重点资助顶目(9020903)；广东省'自然科学基金资助项R(021149)［作者简介］殷彬(19

5、78-)•男•族士研究生•研究方向：数撫挖掘与时公数据库.通讯联系人：方思行.为稠密数据集，其中I/I是事务的平均长度，IDII是数据集中不同项的数目•例如，当数据集中有128个不同的项，而事务的平均长度小于7时，则该数据集是稀疏的.2算法比较分析Apriori算法使用的是一种逐层搜索的迭代方法-项集用于探索％+1)-项集.首先找出频繁1-项集的集合，记为J.然后在儿的基础上进行连接操作，产生候选2■项集的集合,再在候选2~项集的集合中进行剪枝操作•产生频繁2-项集的集合L2.类似地，在L2的基础上找出L3.如此下去，直到不能找到频繁k-项集为止.FP-growth算法采取分而治之

6、的策略：在保持项集关联信息的情况下，把数据库压缩到一棵频繁模式树(FP-Tree),它比原始数据库小很多；然后，将压缩后的数据库按照频繁项投影,分成一些条件数据库，并分别挖掘每个数据库，这样就减少了后续的扫描数据库的时间.它又采取频繁模式增长的方式，不产生候选项集，这使得它在挖掘的过程中不会产生数据库中没有的新事务.而Apriori算法则可能产牛大量的候选项集，同时可能需耍巫复地扫描数据库.下面是用4个数据集进行实验的结果比较67】.其中,Gazelle数据集是…个稀疏数据集.它是从Gazelle.com获得的对该网站访问的数据集合(点击记录).它包含了59602个事务，在事务集中

7、总共有1000个项，每个事务含的项不超过267项，平均事务长度为2.5.25I5D10K是一个用合成数据产生器产生的稠密数据集，包含了10000个事务，在事务集中总共有1000个项，每个事务含的项不超过25项，平均事务长度是15.BMS-POS数据集是一个稀疏数据集,它是从一个规模很大的零售商那里获得的包含儿年的零售数据.在这个数据集中，一个消费者的购买事务就是消费者一次购买的商品目录.它包含515597个事务，在事务集中总共有1657个项，最长的事务的长度为164,