基于频繁模式增长算法的2型糖尿病患病风险预测的分析研究

韦 哲叶广健王能才



基于频繁模式增长算法的2型糖尿病患病风险预测的分析研究

韦 哲①②叶广健①②王能才①

［摘要］目的：分析基于频繁模式增长（FP-growth）算法的2型糖尿病患病风险预测，避免经典Apriori算法在2型糖尿病相关危险因素分析中执行效率低的缺陷。方法：选取兰州某医院医学信息科2009年1月至2014年3月的2型糖尿病患者的首次病程记录资料及其健康数据档案，根据2型糖尿病相关危险因素分析中的需要，引入更适用于2型糖尿病相关危险因素分析的FP-growth算法。采用C#语言对经典Apriori算法和FP-growth算法进行编程，对比分析两种算法的执行效率。结果：通过对比分析得到两种算法在运行时间与记录数据以及运行时间与支持度两个方面的对比值。结论：FP-growth算法在预测2型糖尿病相关风险因素的分析中执行效率更高，能够找到更多的糖尿病风险因素。

［关键词］数据挖掘；Apriori算法；关联规则；频繁模式增长算法；风险分析；糖尿病

韦哲，男，（1963- ），博士，高级工程师。兰州军区兰州总医院医学工程科、兰州理工大学电信学院，从事医学信息检测和处理方面的研究工作。

［First-author’s address］ 1.Lanzhou General Hospital， Lanzhou Military Area Command， Lanzhou， Gansu，730050， China. 2.School of Electrical Engineering and Information Engineering， Lanzhou University of Technology，Gansu， Lanzhou 730050，China.

糖尿病（diabetes mellitus，DM）是由胰岛素分泌缺陷和（或）胰岛素作用缺陷所引起的，并以慢性高血糖伴碳水化合物、脂肪和蛋白质的代谢障碍为特征的慢性疾病［1］。2型糖尿病（diabetes mellitus，type 2）又称为非胰岛素依赖型糖尿病［2］。非胰岛素依赖型糖尿病的发病机制主要是由于人体的胰岛素抵抗并胰岛素分泌不足所导致的，2型糖尿病患者自身的β细胞并无自身免疫性缺陷，其发病特点是成年发病，起病比较缓慢，病情也较轻，其比例也占全部糖尿患者的绝大多数［3-4］。据统计，1985年全球糖尿患者有3000万，到1995年这一数字增长到1.35亿，2000年达到1.71亿，预测到2025年将突破3亿。庞大的数字和越来越快的增长速度充分表明对2型糖尿病的研究具有重要的意义［5］。

在挖掘2型糖尿病相关危险因素之间关联规则时发现，由于Apriori算法自身的缺陷：①每生成1个频繁项集就则须扫描一次数据库［6］；②由（k-1）频繁项集生成k项候选项集时，会产生许多候选项集，而许多候选项集日后并无需应用，使得2型糖尿病相关危险因素的数据挖掘等待时间较长，执行效率较低。本研究针对2型糖尿病相关危险因素关联规则挖掘数据量大、变量属性众多等特点，引入一种适用于2型糖尿病相关危险因素关联分析的频繁模式增长（frequent pattern growth，FP-growth）算法［7］。

1 建立挖掘2型糖尿病相关危险因素数据规则

1.1 FP-growth算法

FP-growth算法是一种不产生候选挖掘频繁项集的，基于频繁树（FP-tree）的算法。FP-growth算法采用分治策略，先将提供原始事务数据库压缩到一棵频繁模式树（FP-tree）中，且保留项集关联信息，然后将新的数据库按条件划分，每个频繁项对应一个条件［8］。

FP-growth算法分为两个过程：①根据原始事务数据库构造树形；②在树中递归挖掘。

（1）FP-growth算法中第一步为经典Apriori算法中生成候选项集L1，其产生出基本树形结构（FP-gree），是FP-growth算法的核心步骤，且为本研究第一次扫描原始数据库→再一次扫描数据库，利用每个事务中的频繁项构选树形，找出节点，按L1规定的顺序加入树形中。

（2）通过递归搜索发现一些满足条件的短模式，并与后缀连接得到长模式［9］。在经典Apriori算法中，连接的定义是：为了找到频繁项集合Lk，需要连接Lk-1与自己产生连接候选项集k-项集的集合。该候选频繁项集合记作Ck。设l1和l2是Lk中的项集。记li［j］表示li的第j项。执行连接过程Lk-1∞Lk-1，其中要求Lk-1的元素l1和l2可以连接，如果：（l1［1］=l2［1］）^（l1［2］=l2［2］）^…^（l1［k-2］=l2［k-2］）^（l1［k-1］^l2［k-1］），连接l1和l2产生的结果项集是l1［1］，l1［2］……l1［k-1］，l1［k-1］。记号li［j］表示li的第j项。同理，在FP-growth算法中，连接是为了找到在某一特定条件下的频繁项集合。但基于第一步建立的FP-tree，已经不必每一次都扫描原始数据库，而是搜索条件频繁项集，条件频繁项集一般情况要比原始数据库小很多，这样就极大降低了搜索开销，提高了算法的效率［10］。

1.2 数据挖掘方法

本研究在对2型糖尿病相关危险因素进行数据挖掘时，选取兰州某医院医学信息科提取了3万余份2型糖尿病患者的首次病程记录及健康数据档案［11］。选取的相关因素分别为：年龄、性别、收缩压、舒张压、血脂、遗传病史、饮食、腰臀比、吸烟情况、饮酒情况、运动情况、学历和工作性质［3，12-13］。在对这些原始数据进行数据预处理时，将选定的相关危险因素转化为34个属性值，如年龄在＞65岁、40～65岁、＜40岁、高收缩及高舒张压等。而如此庞大的数据量如果采用经典Apriori算法，其计算量是巨大的，会消耗很多电脑I/O开销，并且耗时巨大，因此本研究尝试引入FP-growth算法。

1.3 FP-growth算法描述

FP-growth算法首先根据原始数据库构造FP-tree，然后在FP-tree中挖掘频繁模式。FP-tree是一种压缩数据结构，由以下3部分构成。

（1）FP-tree包含1个根节点（null），1个项目前缀子树（item prefix subtree）集合作为根节点的孩子，1个频繁项头表（frequent item header table）。

（2）项前缀子树中的每个节点由项目名、计数和节点链3个域构成。分别表示节点代表的项的名称，本节点为止的路径的事务数，指向FP-tree中具有相同项目名的节点。

（3）频繁项头表中每个条目由项目名和节点链头2个域组成。节点链头指向所有具有相同项目名节点的第一个节点，其FP-growth算法流程如图1所示。

图1 FP-growth算法流程图

FP-growth算法的具体描述如下。

输入：事务数据库D，按实际要求设置最小支持度阈值min_sup

输出：FP-tree

（1）扫描事务数据库D一次，得到频繁项集和其每个频繁项的支持度，并对频繁项集合所有频繁项按其支持度降序排序，得到频繁项表L；

（2）创建根节点T，标记为（null）；

（3）For事务数据集D中每个事务Trans do

（4）对Trans中所有频繁项按L排序；

（5）对排序后的频繁项表以［p|P］表示，其中p是L第一个元素，而P是频繁项表中除去p后剩余元素组成的项表；

（6）调用insert_tree（［p|P］，T）；

（7）End for

输入：FP-tree，项集a（初值为空），最小支持度min_sup；

输出：事务数据集D的频繁项集L；

（1）L初值为空；if Tree只包含单个路径P then

（2）for 路径P中节点的每个组合（记为β） do

①产生项目集β⌒α，其支持度support等于b中节点的最小支持度数；

②Return L=L⌒支持度数大于min_sup的项目集β⌒α

（3）else//包含多个路径

①for Tree的头表中的每个频繁项αfdo

②产生一个项目集β=αf⌒α，其支持度等于αf的支持度；

③构造β的条件模式B，并根据其构造β的条件FP-treeβ；

④if Treeβ非空 then

⑤递归调用FP_growth（Treeβ，β）；

⑥end if

⑦end for

⑧end if

（4）产生一个模式β=αiα，其支持度support =αisupport；

（5）构造β的条件模式基，然后构造β的条件FP-treeβ；

（6）if Treeβ非空then

（7）调用FP_growth（Treeβ，β）

2 实验结果

（1）为了对比FP-growth算法和经典Apriori算法的性能和效率，用C#语言对这两种算法进行编程，并用这两种模型分别对数据平均长度为4，平均频繁项长度为2，10000条数据（T4I2D10000）的随机数据库进行分析，实验硬件条件为CPU为Intel i5处理器，内存为4 G，操作系统为WIN 8系统。得出经典Apriori算法和FP-growth算法搜索不同长度频繁项和不同支持度条件下的运行时间对比，如图2和图3所示。

图2 两种算法搜索频繁项时间关系柱状图

图3 两种算法不同支持度条件下运行时间关系曲线图

图2显示，当对频繁1项集进行搜索时，经典Apriori算法消耗的时间，要比FP-growth算法少很多，这是因为，后者在搜索频繁1项集时，要两次扫描数据库，但随着搜索频繁项目的长度增加，FP-growth算法的效率开始要明显优于经典Apriori算法，因为经典算法每次要生成大量无用候选项集，而FP-grow算法只是在FP-tree这个极小的数据库中进行递归计算。

图3表示的是两种算法在不同支持度阈值条件下，算法效率的对比。研究发现，当最小支持度要求在4%时，经典算法运行时间要比FP-growth算法高，而随着支持度减小，FP-growth算法的效率要明显优于经典算法。这是因为，支持度决定着一个数据库搜索出来的关联规则的复杂程度：支持度越小，关联规则越复杂。研究表明，FP-grow算法在数据维度大、数据结构复杂、数据量巨大的数据库的分析中，要比经典算法有优势。

（2）将FP-growth算法在通用数据挖掘工具SPSS Clementine 12.0进行建模，并对预处理后的2型糖尿病病历数据进行分析，最小置信度设为40%，前项支持度阈值设为10%，前项数设为3，得到输出的部分结果如图4所示。

图4 部分关联规则挖掘结果示图

在图4中以第一行为例，表示同时具有＞65岁、WHR高和经常醉酒三个因素的情况下，出现2型糖尿病的概率是67.667%，因此可以得出6个最高治病性的因素：即年龄＞65岁、高收缩压、无运动、经常醉酒、WHR过高和经常高热饮食。

3 结论

仿真结果表明，经典Apriori算法［14］在搜索所有满足条件的频繁项集时，生成大量的无用候选项集，极大的降低了算法的效率，而FP-grow算法能够有效减少频繁项的生成数目，提高算法效率；同时，在不同支持度条件下，两种算法的效率也不同：经典算法更适用于支持度大，结构较简单的数据，而FP-growth算法更适用于支持度较低，结构更复杂的数据。

对糖尿病电子病历数据FP-growth算法的建模，找出了年龄＞65岁、高收缩压、无运动、经常醉酒、WHR过高和经常高热饮食这6种致病程度最高的风险因素，对辅助预防2型糖尿病有一定的指导意义。

参考文献

［1］Cho YS，Chen CH，Hu C.Meta-analysis of genome-wide association studies identifies eight new loci for type 2 diabetes in east Asians［J］. Nat Genet，2011，44（1）：67-72.

［2］吕琴.血清尿酸与2型糖尿及糖尿病肾病的关系研究［D］.武汉：华中科技大学，2013.

［3］Chen G，McAlister FA，Walker RL，et al. Cardiovascular outcomes in framingham participants with diabetes：the importance of blood pressure［J］.Hypertension，2011，57（5）：891-897.

［4］Patil BM，Joshi RC，Toshniwal D.Association rule for classification of Type-2 diabetic patients［C］.2010 Second International Conference on Machine Learning and Computing，2010：34-38.

［5］王海鹏.我国诊断糖尿病疾病经济负担趋势预测研究［D］.济南：山东大学，2013.

［6］Agrawal R.Database Mining：A performance perspective［J］.IEEE Transactions on Knowledge and Data Engineering，1993，5（6）：914-925.

［7］白晶.Apriori算法及其在智能小区用电分析中的应用研究［D］.北京：华北电力大学，2014.

［8］Totad SG，Geeta RG.Batch incremental processing for FP-tree construction using FP-growth algorithm［J］.Knowledge and Information Systems，2012，33（2）：475-490.

［9］Gruca.Improvement of FP-growth algorithm for mining description-oriented rules［C］.3rd International Conference on Man-Machine Inter actions（ICMMI），2014，242：183-192.

［10］H Genther，M Glesner.Automatic generation of a fuzzy classification system using fuzzy clustering methods［C］.Proceedings of the 1994 ACM Symposium on Applied Computing，1994：180-183.

［11］贾伟平.中国人2型糖尿病遗传机制与个体化医疗［J］.医学信息，2014，9，13（9）：726-724.

［12］董会敏，高秋菊，闫玉英.体重指数、腰围预测成人高血压和（或）糖尿病的危险程度及交互作用分析［J］.郑州大学学报（医学版），2013，32（6）：678-680.

［13］王超.中国成人超重和肥胖及主要危险因素对糖尿病发病的影响［D］.北京：北京协和医学院中国医学科学院，2014.

［14］韦哲，于启炟，辛迈，等.基于Apriori算法的高危人群2型糖尿病预测研究［J］.中国医学装备，2015，12（1）：45-47.

①兰州军区兰州总医院医学工程科 甘肃 兰州 730050

②兰州理工大学电信学院 甘肃 兰州 730050

［文章编号］1672-8270（2016）05-0045-04 ［中图分类号］ R197.324

［文献标识码］A

DOI:10.3969/J.ISSN.1672-8270.2016.05.015

作者简介

收稿日期：2016-01-17

Analysis for risk factors of type 2 diabetes mellitus based on FP-growth algorithm

WEI Zhe， YE Guang-jian， WANG Neng-cai

China Medical Equipment，2016，13（5）:45-48.

［Abstract］ Objective: We do it to solve the problem of low efficiency in analyzing risk factors of type 2 diabetes mellitus by Apriori Algorithm. Methods: We used the patients’ data from the information department of one tertiary referral hospital in Lanzhou which include course note of disease and their health record form January 2009 to March 2014.We found out that the FP-growth algorithm analyzes risk factors of type 2 diabetes better. And we analyzed the efficiency by programming FP-growth and Apriori algorithm with C#. Results: We can analyze the run time and recorded data， time and support degree. Conclusion: The FP-growth algorithm has a higher efficiency in analyzing risk factors of type 2 diabetes mellitus.

［Key words］Data mining； Apriori algorithm； Association rules； FP-growth algorithm； Risk analysis； Diabetes mellitus