小型微型计算机系统Journal of Chine Computer Systems 2020年12月第12期 Vol.41 N o. 12 2020
Apriori算法的改进及其在睡眠辅助医疗中的应用
石升，董金琳，王玮，闰悦，孙艳蕊
(东北大学理学院，沈阳110819)
E-mail：20171225@ stu. neu. edu. cn
摘要：针对睡眠呼吸暂停低通气综合征结合沈阳市某医院的数据对睡眠呼吸暂停低通气综合征的相关诊断指标及潜在病因 进行频繁项集的挖掘.常用的Apriori算法实用性较强但效率不高且有局限性.本文针对Apriori算法的缺陷结合已有的优化算 法提出了一个新的优化算法，并在此基础上建立了睡眠呼吸暂停低通气综合征辅助医疗的模型.该算法效率更高、速度更快、适 用性更广，并且将结果与医学临床表现进行对比，符合临床表现，可信度较高.
关键词：睡眠呼吸暂停低通气综合征;Apriori算法的优化；频繁项集；预剪枝；辅助医疗模型
中图分类号：TP393 文献标识码：A文章编号：1000-1220(2020) 12-2668^04
Improvement of Apriori Algorithm and Its Application in Sleep Auxiliary Medicine
SHI She ng.D ON G J i n-l in.WANG W e i.Y A N Y u e.S U N Yan-rui
英语口语训练
(College of Science,Northeastern University,Shenyang 110819,China)sounds什么意思
A b stra c t ：According t o t h e d a t a of s l e e p apnea-hypopnea syndrome combined with t h e d a t a of a h o s p i t a l i n Shenyang,t h e r e l a t e d di agn o s t i c indexes and p o t e n t i a l e t i o l o g y of s l e e p apnea-hypopnea syndrome were mined f r e q u e n t l y.The commonly ud A p r i o r i a l g o r i t h m i s p r a c t i c a l bu t i n e f f i c i e n t and has l i m i t a t i o n s.I n t h i s paper.aiming a t t h e shortcomings of A p r i o r i algorithm^new o p t i m i z a t i o n al gorithm i s propod combined with t h e e x i s t i n g o p t i m i z a t i o n algorithm,and on t h i s basis,an a u x i l i a r y medical model of s l e e p apnea-hypopnea syndrome i s e s t a b l i s h e d.The al go ri th m i s more e f f i c i e n t,f a s t e r and more appl ic ab le,and t h e r e s u l t s a r e compared w i th t h e med-i c a l c l i n i c a l mani fe st at io ns,which i s c o n s i s t e n t with t h e c l i n i c a l m a n i f e s t a t i o n s and has high c r e d i b i l i t y.
K ey w ords ：s l e e p apnea-hy p>opnea syndrome; o p t i m i z a t i o n of A p r i o r i al g o r i t h m；f r e q u e n t itemts; pre-pruning; a u x i l i a r y medical model
i引言
关联规则挖掘是指从数据中挖掘出不同元素之间的感兴 趣的规则，这种规则一般具有利用价值.Apriori算法对关联规 则挖掘的进一步研究提供了新的思路.如Savare^等人设计 了基于否定规则的算法，叶永伟[2]等提出了基于兴趣度关联规 则的算法，程昌品[31等提出了基于矩阵与项集索引表的频繁项 集挖掘算法，邢俊凤;4]等采用优化关联规则Apriori算法等.
睡眠呼吸暂停低通气综合征是一种临床常见的呼吸系统 疾病[5]，智慧辅助医疗建模是一种对医疗数据进行挖掘从而 实现医疗辅助的模型[6].利用现代的数据分析技术对患者的 基本信息、病史、身体状况等重要文本潜在病因特征以及与 P S G检査结果的关系进行分析，挖掘患者潜在的病因对阻塞 性睡眠呼吸暂停患者的发病、病情严重程度、病程进展及预 后、相互影响等的作用大小，从而实现自动的医疗临床辅助，成为目前病情诊断的理想方法.
目前睡眠呼吸暂停低气综合征（P S G)方面没有一个成熟 的模型.在医疗过程中，大多还是依靠传统经验而进行诊断，这样就难免产生误诊的情况.为解决这些的问题，对现有的 Apriori算法进行了研究、建立了基于改进Apriori算法的睡眠 呼吸暂停低通气综合征医疗模型，利用沈阳市某医院提供的关于睡眠呼吸暂停低通气综合征的病例医疗记录验证了模型 的有效性.
本文将对A p rio ri算法的改进以及改进算法在睡眠呼吸暂 停低通气综合征辅助医疗建模上的应用进行研究.第1节对 A p rio ri算法的原理和步骤进行了介绍；第2节具体描述了基于 组合思想的改进A p rio ri
算法的改进方法和具体步骤；第3节 阐述了基于位运算和预剪枝的改进A p rio ri算法的改进方法和 具体步骤；第4节说明了具体的实验过程，包括预处理、算法性 能、准确率的分析比较和实验处理等过程；第5节对算法性能 和实验结果进行了详细的分析比较；第6节对本文所进行的工 作进行总结并进一步讨论下一步要进行的工作.
2 Apriori 算法
A p rio ri算法使用逐层搜索的迭代方法对频繁项集进行 挖掘并对支持度计数进行统计再用于关联规则的挖掘[71.
2.1符号与基本概念
符号说明:/= |/,,/2，…，/…|是全体数据项集；是全体事务集，IDI表示总事务数，每个事务有唯一的标识.
定义1.数据集X在D中的支持数是£>中包含D的事务 数.X在D中的支持度就是X在£)中的支持数与Z)的总事务 数之比.
收稿日期:2019-12-24收修改稿日期J02(M)1-15基金项目：国家级大学生创新创业项目（2〇A l01450014)资助.作者简介：石升，男，1999年生，研究方向为应用统计学；董金琳，女，1999年生，
研究方向为应用统计学；王玮，男，1999年生，研究方向为信息与计算科学；闫悦, 女，1998年生，研究方向为应用统计学；孙艳蕊（通讯作者），女，1965年生，博士，教授，研究方向为图论算法、数据数据科学.
石升等:Apriori算法的改进及其在睡眠辅助医疗中的应用2669 12期
客服专员英文
定义2.支持度阈值S是X满足最低显著性需求的支持 度，支持数阈值是达到^所需的支持数，满足如下关系.
min-s u pp or t(X) =5x IDI(1)如果x的支持度达到y则称x为频繁项集.
定义3.含有事务数最多的频繁项集称为最大频繁项集.
2.2算法步骤
Apriori算法作为一种宽度优先的算法产生的频繁项集 的子集都是频繁的且不频繁项集的超集都是不频繁的[81.
产生频繁项集具体步骤如下：在线成人网
步骤1.通过遍历一次数据库统计一切单个事务的支持 度并将达到阈值的事务组成1维频繁项集;
步骤2.从最大频繁项集集合L t中生成长度为i t+ 1的候 选集C t+I，通过遍历数据库统计所有候选项目的支持度并将 达到阈值的项目组成f c+ 1维频繁项集
步骤3.转至步骤2，直至新生成的频繁项目集为空集，最后得到频繁项目集集合为.
k
L=(2) 2.3算法缺点
Apriori算法具有遍历数据库次数多、内存消耗大、运行 时间长的缺点[9]，本文基于这些缺点对算法进行目标为减少 单次遍历的时间以及减少遍历次数的改进.
3基于组合思想的改进Apriori算法
针对Apriori算法遍历数据库次数多的缺点利用组合思 想在第2次扫描到该数据集时将其所有可能的子集找出并生 成子集库.结合相关性质找出所有的频繁项集将遍历次数减 少到3次.
3.1组合思想
组合是指通过每次从原集合中选出不同的项的方法生成 原集合的所有子集.在寻找频繁项集时，每一个事务集包含的 频繁项集只能是该事务集的子集.原算法需要不断的通过M
项频繁项集生成A：项候选集，并扫描原数据库计算（项集的 支持度计数来判断i t项候选集是否是频繁项集.
通过组合的方式在第1次遍历数据库时将每一事务集的 所有子集找出，最后子集在所有事务集生成的全部子集中出 现的次数即为其支持度计数，其长度即为项集的长度，不需要 重新生成更高项集以及计算支持度计数.
3.2算法步骤
改进后的Apriori算法可通过将事务组合后对子集进行 挖掘的方法大幅度减少遍历原数据库的次数.其产生频繁项 集及其支持度的具体步骤如下：
步骤1.通过遍历一次数据库统计一切单个事务的支持 度并将达到阈值的事务组成1维频繁项集;
步骤2.通过遍历一次数据库将每一个事务集中不属于 中的项目删除以更新数据库；
步骤3.将第1个事务集D，的所有子集找出放人候选集
C中并将计数初始化为1;
怪奇物语百度云步骤4.通过遍历一次数据库，在遍历到第；个事务集D，时，通过组合思想将事务集£>，的所有子集找出来，将一切子 集对比加人到候选集C中，若子集属于C将其支持度计数加1；若子集不属于C加人该子集更新候选集C并将其支持度 计数设为1;
步骤5.将候选集C中一切事务集的支持度计数与支持 度计数阈值进行比较，若不小于阈值则为频繁项集将事务集 和其支持度计数保存在集合i中，最终生成频繁项集集合i. 4基于且位运算和预剪枝的改进Apriori算法针对Apriori算法内存消耗大和运行时间长的缺点利用 矩阵存储数据并利用且位运算进行项集运算简化计算过程. 利用预剪枝加强剪枝条件使得每一次由低项集生成高项集时 减少候选集的生成并提高运行效率.
4.1且位运算与预剪枝
位运算是指将整数对应的二进制数直接进行处理[1°].本 文利用且位运算（&)对数据集进行计算.
预剪枝是指在每一次由低项频繁项集生成高项候选项集 时利用频繁项集的所有子集都是频繁的等性质对候选项集进 行筛选并删除不符合要求的项集，以此达到减少计算量的目 的.
4.2改进方法
4.2.1符号说明
数据集^^丨^^…^广共有^条数据^个特征,a,+= |a…,aa，…，(1«丨矣c)表示A的第f行，其中 (1^/矣m)的可能取值为0或1，其中丨代表第i'条数据含有 第）个特征,〇代表无
频繁*项集的集合为h丨，h中元素个数为/4，也即频繁A项集的个数为，对第个频繁A项集
=bf i J a，…,：
ViJ ，其中:y,;=〇或1(1句名爪），且满足.
X'. = * (3)若\= 1表示第/个-繁项集包含第y个特征，若为0, 则无.支持度阈值为，候选频繁/t项集的集合为
4.2.2预剪枝条件
加强预剪枝条件，在原有剪枝条件的基础上，从筛选候选 1项集开始，对预剪枝判断失败或支持度计数未达标准的项 集进行记录于矩阵B.在产生々选项集的预剪枝判断过程中，对产生的项集与当前已有的矩阵B进行匹配，若B中存在某 行向量与该项集匹配成功，则该项集预剪枝判断不通过.
4.2.3 且位运算和矩阵存储
利用计算机位运算中的且位运算进行处理，利用特殊矩 阵存储数据库，简化支持度计数的计算过程.
1) 候选1项集的支持度计数
考研现场确认需要带什么对给定的某个下标/t特征，直接对指定列经累加可得其 1项集的支持度为：
Z=尸t(4)
1=1
可以减少一次遍历.
2) 候选A项集的支持度计数
Apriori算法在计算候选&项集支持度计数时对候选项集中每个项至少进行n x (丨-丨）次判断.本文利用计算机自 有的且位运算对候选项集的支持度进行统计.
当=6时，有；也即七中的项在;C，中均有出
2670小型微型计算机系统2020 年
现.由此得到.
定理1.对给定的某个候选项集&，该候选项集的支持度 计数为：
= = yj](5)
i = l
其中a，为矩阵A的第i行.
3)预剪枝的匹配计数
根据且位运算的相关性质，可以得到.
定理2.对项集y，若存在某行S,，使得f i.c S y==S，的值为 1(真），则>"是非频繁项集.
4.3算法步骤
基于且位运算和预剪枝的改进Apriori算法可一定程度 提高运行效率.其具体步骤如下.
步骤1.通过遍历一次数据库利用位运算统计数据库中 所有单个项目的支持度并将达到阈值的项目组成1维频繁项 目集
步骤2.从最大频繁项集集合A中生成长度为+ 1的候 选集C t+1，将候选集(：4+1与记录矩阵足进行比较，删除非频 繁项集，通过遍历数据库统计所有候选项目的支持度并将达 到阈值的项目组成f t+ 1维
频繁项目集同时使用没有达到阈值的项目更新非频繁项集记录矩阵見生成;
步骤3.转至步骤2，直至新生成的频繁项目集为空集，最后由公式（1)得到频繁项目集集合为
4.4算法准确性分析
当”=1时，对于任意的频繁1项集y,= lyn，知，…，心1 (1矣!•《/…)，存在唯一的p(0矣/^m)，有\= 1且;=0对于 任意的7'都成立，又由于 是频繁的，必有：
C
a ip> su p(6)
i = i
所以 >>，可被正确选择进人频繁项集集合.
假设n U- 1,G2时，频繁项集集合都准确.则当《= * 时，对于任意的频繁*项集y,= Iyn,ya I (1=£;=£/…)，其前11项也是频繁的，所以兄e C…，又频繁项集的子集均是 频繁的，所以;V，中不存在不频繁的子集，即;V，可通过预剪枝，由其频繁可得：
C
X((ai&y i)=^sup(7)
i=\
如果(〇,&乂）=兄.为真，那么(a,+<6y,) ==y,.的值为1，否 则值为〇，也即；y,•可被正确选择进人频繁〃项集集合.
5实验过程
5.1数据样本介绍
为研究病症与临床表现、生活习惯等的关系，本文使用来 自沈阳市某医院的数千条医疗记录作为数据源，信息包括年 龄、性别、一些行为表现如晨起口干，夜间憋尿等，还包括患者 血压记录、其他疾病记录史等.
5.2数据预处理
英语六级查分5.2.1 建立病人系统数据库
利用Excel对数据进行预处理并将文本形式医疗记录信 息转化为数据库表格.每一行代表一位病人的信息，每一列代 表所有病人的某个具体特征信息.5.2.2数据清洗和离散化
数据清理主要将数据中的缺失值和异常数据进行识别和 删除处理.在缺失值的识别及删除处理方面，由于部分项目如 就诊日期、病人姓名等对本文的研究无较大意义，本文对这些 事务进行了删除处理，而对于在部分数据中出现某项缺失值 的整行数据进行了删除处理.数据离散方面，本文通过査找相 关医学文献，依据每个字段的标准值，将连续数据离散化.进 一步进行数据归约，并对离散后的数据进行了相关字符编码.
5.3实验步骤
本文首先随机生成数据规模为500 x26、1000 x26、1500 x26、2000 x26、5000 x5、5000 x10、5000 x15 和 5000 x20 的8个数据集，分别使用Apriori算法、基于组合思想的改进Apriori算法和基于且位运算和预剪枝的改进Apriori算法对 随机数据集进行处理，比较分析3个算法的性能和准确率并 利用基于位运算和预剪枝的改进Apriori算法对医疗病例数 据进行实验分析.
6实验结果与分析
6.1算法比较分析
使用随机数据集对3种算法进行实验并对所需时间进行 比较，结果如图1和图2所示.
500X26 1000X26 1500X26 2000X26
数据集大小
图1算法运行时间随数据长度变化曲线
Fig. 1Curve of the running time of the algorithm
varies with the length of the data
° 5000X10 5000X15 5000X20 5000X25
数据集大小
图2算法运行时间随数据宽度变化曲线
Fig.2 Curve of the running time of the algorithm
varies with the width of the data
从图1和图2中可以看出，当单个数据集的宽度较小时 基于组合思想的改进Apriori算法性能最优；当单个数据的宽 度较大时基于位运算和预剪枝的改进Apriori算法性能最优 且随着宽度的增加优势越来越明显.对输出结果进行对比，3
种算法准确率都为100%.
石升等:Apriori算法的改进及其在睡眠辅助医疗中的应用2671 12期
6.2挖掘结果
由于医疗数据的单个数据宽度为39，本文决定使用基于
位运算和预剪枝的改进Apriori算法对医疗病例数据进行实
验并对结果进行分析.表1所列结果为部分导致患睡眠呼吸
暂停低通气综合征的事务集及其支持度.
表1部分挖掘结果
Table 1P a r t i a l mining r e s u l t s
项数项集支持度
5男打鼾夜间憋醒白天嗜睡晨起口干22.459
5男主诉打鼾白天嗜睡晨起口干22.836
5男主诉打鼾夜间憋醒晨起口干22.961
5男青年影响工作白天嗜睡Epworth325.345
5男主诉晨起口干父母有打鼾史20.075
4打鼾夜间憋醒晨起口干有饮酒史20.201
金融时报中文版
4男白天嗜睡晨起口干有饮酒史20.326
4男晨起口干晨起舒张压Epworth220.452
4主诉打鼾夜间憋醒白天嗜睡20.577
4男白天嗜睡青年白天嗜睡20.577
4打鼾白天嗜睡晨起口干有饮酒史20.703
4男主诉打鼾晨起口干34.253
6.3挖掘结果的分析
从结果可看出睡眠呼吸暂停低通气综合征的患病原因及
易患人群主要为：
1) 患者多为男性，基本都具有夜晚睡觉打鼾症状，多数 出现了晨起口干、白天嗜睡等症状，多数存在生活作息不规律
现象，部分有家族病史；
2) 具有睡觉打鼾、白天嗜睡、影响到工作、总体呈现轻微 过度嗜睡情况的男性青年为易患人群；
3) 具有夜晚易憋醒、白天嗜睡、晨起口干、睡觉打鼾情况 的男性为易患人群；
上述结果与临床表现一致，说明所给出的模型是有效的，
可以为实现快速实时在线诊断提供相关数据.
7结语
本文基于A p rio ri算法提出了两种改进算法分别针对单
个数据宽度较窄和较宽的情况，在保证准确率的前提下尽可
能提高了算法的挖掘效率.睡眠呼吸暂停低通气综合征病情
诊断主要依靠医生的临床经验，现在我们可以提供科学的理
论依据•本研发现的睡眠呼吸暂停低通气综合征的患病原因
及易患人群对于提高患者对该疾病的预防效率以及医生进行
疾病诊断具有较高的实用价值并且本研究为今后其他疾病的
相关研究提供了新的思路方法.接下来的工作是对改进后算
法所适用的数据库大小及稠密程度，进行更精确的实验. References ：
地址英文缩写[1] Savare A,Omiecinski E,Navathe S. Mining for strong negative
associations in a large databa of customer transactions [ P ]. 14th International Conference on Data Engineering Proceedings, 1998.
[2 ] Ye Yong-wei, Cheng Yi-fei,Lai Jian-ren, et al. Fault prediction
mcxlel of ship unloader bad on improved association rules [ J ].
China Mechanical Engineering,2019,30(20) ：2463-2472.
[3] Cheng Chang-pin,Wu Yi-lin, Jiang Yong-sheng. Association rules
mining bad on improved apriori algorithm of matrix [ J ]. Journal of Guangdong Second Normal University ,2019,39(5) ：89-97.
[4]Xing Jun-feng,Hao Xiu-xia, Ma Ning. Diabetes prescription rule
bad on optimized association rule algorithm[ J]. Electronic Tech
nology and Software Engineering,2019,25(19) ：137-138.
[5] Cai Ying-ru, Lai Tian-wen, Li Wen. Progress in the treatment of
chronic obstructive pulmonary dia complicated with sleep ap- neahypopnea syndrome [ J ]. International Respiratory Journal, 2019,39(7) ：542-546.
[6 ] He Hai-yan,Liu Wei, Wang Yun-xia,et al. Application and devel
opment trend of big data analysis in intelligent medical assistant di- agnosis[J]. International Journal
of Laboratory Medicine,2019,40
(13)： 1537-1540.
[7] Hu Ji-ming, Xian Xue-feng. Rearch and improvement of Apriori
algorithm in mining association rules [ J ]. Computer Technology and Development,2006,16(4) ：99-101.
[8] Zhu Ming. Data mining [ M ]. Hefei ：University of Science and
Technology of China Press,2002 ： 100-110.
[9] Cai Wei-jie,Zhang Xiao-hui,Zhu Jian-qiu. Summary of association
rule mining [J]. Computer Engineering ,2001，27(5) :31-33.
[10] Hou Han-ming. Talking about the application of bit operation in
arch algorithm[ J]. China New Communications,2019,21 (1)：212-213.
附中文参考文献：
[2 ]叶永伟，程毅飞，赖剑人，等.基于改进关联规则的卸船机故障预
测模型[J].中国机械工程，2019,30(20) :2463-2472.
[3 ]程昌品，邬依林，姜永生.基于矩阵的Apriori改进算法的关联规
则挖掘[J].广东第二师范学院学报，2019,39(5) :89-97.
[4]邢俊凤，郝秀霞，马宁.基于优化关联规则算法的糖尿病处方
规律[J].电子技术与软件工程，2019,25(19) :137-138.
[5]蔡颖如，赖天文，李文.慢性阻塞性肺疾病合并睡眠呼吸暂停
低通气综合征的治疗进展[J].国际呼吸杂志，2019,39(7) :542- 546.
[6]和海妍，刘伟，王云霞，等.大数据分析在智慧医疗辅助诊断中
的应用与发展趋势[J].国际检验医学杂志，2019,40(13) :1537- 1540.
[7]胡吉明，鲜学丰.挖掘关联规则中Apriori算法的研究与改进
[J].计算机技术与发展,2006,16(4) :99-101.
[8]朱明.数据挖掘[M].合肥：中国科学技术大学出版社，2002:
100-110.
国庆假期几天
[9 ]蔡伟杰，张晓辉，朱建秋.关联规则挖掘综述[J].计算机工程，
2001,27(5) ：31-33.
[10]侯瀚茗.浅谈在搜索算法中位运算的应用[J].中国新通信，
2019,21( 1)：212-213.
