醫(yī)療診斷與預測中的增量式Apriori方法研究

鄭會 何靜 李鵬

摘 要： 醫(yī)療診斷與預測因數(shù)據(jù)量太大而需要流式存儲，使得頻繁項集挖掘出現(xiàn)耗時大，效率低下等問題。以解決這些問題為目的，研究了一種改進的基于大規(guī)模數(shù)據(jù)流的頻繁項集挖掘方法，即增量式頻繁項集挖掘方法。文章的重要結(jié)果是，該方法可結(jié)合歷史數(shù)據(jù)與當前數(shù)據(jù)簇，快速求出近似全局支持度，并找出全局頻繁項集集合。將該方法應(yīng)用于Apriori算法上，通過實驗得出了該增量式Apriori方法具有高效率的結(jié)論。

關(guān)鍵詞： 醫(yī)療診斷與預測; 關(guān)聯(lián)規(guī)則; 增量式算法; 數(shù)據(jù)流

中圖分類號：G642 ? ? ? ? ?文獻標識碼：A ? ? 文章編號：1006-8228（2021）08-53-04

Research on the incremental Apriori algorithm for medical diagnosis and prediction

Zheng Hui， He Jing， Li Peng

（School of Computer Science， Nanjing University of Posts and Telecommunications， Nanjing， Jiangsu 210023， China）

Abstract： Medical diagnosis and prediction need streaming storage because of the large amount of data， which makes frequent itemset mining time-consuming and inefficient. In order to solve these problems， an improved frequent itemset mining method for large-scale data stream is studied， i.e.， the incremental frequent itemset mining method. The important result of this paper is that this method can combine the historical data with the current data cluster to quickly find out the approximate global support， and find out the set of global frequent itemsets. Applying the method to Apriori algorithm， the conclusion is obtained through experiments that the incremental Apriori algorithm has a high efficiency.

Key words： medical diagnosis and prediction; association rule; incremental algorithm; data stream

0 引言

在疾病診斷與預測上，關(guān)聯(lián)規(guī)則算法有不可替代的優(yōu)勢，但在求解大數(shù)據(jù)問題時，該算法通常執(zhí)行效率低下，其根本原因在于頻繁項集挖掘過程耗時較長[1]。本文通過研究頻繁項集挖掘算法的現(xiàn)有問題，并為了避免重復掃描大規(guī)模數(shù)據(jù)，本文采取了增量式Apriori方法的構(gòu)建方案，該方法通過持續(xù)性因子篩選出需要保存的局部頻繁項集統(tǒng)計信息;提出了近似全局支持度值的計算過程，以保證增量式頻繁項集的準確率;同時提出了增量式頻繁挖掘算法的求解步驟。

1 現(xiàn)有問題

醫(yī)療數(shù)據(jù)具有如下特點：①數(shù)據(jù)來源廣泛，比如數(shù)據(jù)來源可能包括診斷數(shù)據(jù)、醫(yī)療數(shù)據(jù)與體檢數(shù)據(jù)等[2];②數(shù)據(jù)更新頻繁發(fā)生，每當個體進行新的診斷、治療或體檢時，都會產(chǎn)生新的數(shù)據(jù)并被存儲到相關(guān)疾病數(shù)據(jù)庫中。因此，醫(yī)學數(shù)據(jù)庫會持續(xù)地進行更新[3]。

隨著醫(yī)學數(shù)據(jù)庫的更新，訓練出的診斷/預測模型也應(yīng)隨之變化，這樣才能使診斷/預測模型的實時性得到保證[4]。對于如何保持該實時性，理想化的做法是每當有新的記錄，計算機就重新建模，基于新模型挖掘頻繁項集與關(guān)聯(lián)規(guī)則[5]，然后利用新的關(guān)聯(lián)規(guī)則對個體進行疾病診斷與預測[6]。但這個理想化做法容易出現(xiàn)以下幾個問題。

問題1：隨著醫(yī)學數(shù)據(jù)規(guī)模的不斷增加，醫(yī)學數(shù)據(jù)庫的量級也在持續(xù)增大，使得構(gòu)建模型所需時間不斷延長。

問題2：當醫(yī)學數(shù)據(jù)庫中數(shù)據(jù)達到某個量級時，模型會因為耗時太長而喪失時效性。

問題3：頻繁地建立疾病診斷/預測模型，會增加計算資源和人力等相關(guān)成本。

由此得出，根據(jù)數(shù)據(jù)更新來頻繁地更新并持續(xù)地建模并不現(xiàn)實。為此，如何構(gòu)建具有實時性、高效性的增量式模型[8]就是本文要解決的一個重要問題。

2 方法構(gòu)建方案

在醫(yī)學領(lǐng)域上采用關(guān)聯(lián)規(guī)則算法具有明顯的優(yōu)勢，關(guān)聯(lián)規(guī)則算法可以挖掘出數(shù)據(jù)潛在關(guān)系與關(guān)聯(lián)[7]，從而可以在醫(yī)學領(lǐng)域上協(xié)助實現(xiàn)醫(yī)療診斷與預測[8]。但是，其在應(yīng)用中仍存在一些不足。

⑴ 沒有解決頻繁項集挖掘過程中效率低下的問題。

⑵ 并不適用于對大數(shù)據(jù)問題的處理，特別是在處理增量式醫(yī)療大數(shù)據(jù)時還未發(fā)揮應(yīng)有的作用。

針對頻繁項集挖掘在處理大數(shù)據(jù)時效率低下的問題，本文將闡述如何對算法進行改進，探討實現(xiàn)大數(shù)據(jù)增量式的頻繁項集挖掘方法，以此來提升關(guān)聯(lián)規(guī)則挖掘算法效率。

2.1 方法主要目的

本文通過研究增量式頻繁挖掘算法，以期達到如下兩個目標。

目標1：在每一批次數(shù)據(jù)簇中，都能直接保留全局頻繁項集到候選頻繁項集集合;

目標2：成功過濾掉其他所有非潛在的全局頻繁項集，從而實現(xiàn)對存儲空間的最大優(yōu)化。

2.2 研究內(nèi)容與創(chuàng)新性

本文采取近似的頻繁項集挖掘方法，該方法主要是通過對每個批次數(shù)據(jù)簇中的局部頻繁項集與潛在全局頻繁項集的存儲，在此基礎(chǔ)上獲得全局支持度計算所需的數(shù)據(jù)統(tǒng)計摘要信息，從而達到盡可能地保留全局頻繁項集的目的。為獲得這些全局支持度值的統(tǒng)計信息，需要做到以下幾點。

⑴ 對于某一批次中被認定為頻繁的項集，直接保存該局部頻繁項集及其支持度信息。

⑵ 對于當前批次數(shù)據(jù)簇中非頻繁而有潛力的項集，即潛在的全局頻繁的項集，同樣保存該潛在頻繁項集及其支持度信息。

⑶ 對于當前批次數(shù)據(jù)簇中非頻繁且無潛力的項集，直接忽略其支持度信息。

由此，本文研究的增量式頻繁項集挖掘（增量式Apriori）算法中，只需對每個批次數(shù)據(jù)簇分別進行局部頻繁項集挖掘，就能得到潛在的全局頻繁項集，根據(jù)全局候選頻繁項集的相關(guān)統(tǒng)計信息即可計算得出全局支持度值，從而確定全局頻繁項集。本文還分析近似算法的誤差估計，進一步限制近似算法的誤差。

3 方法的求解步驟

本文通過對增量式頻繁項集挖掘方法的構(gòu)建，來實現(xiàn)數(shù)據(jù)流數(shù)據(jù)頻繁項集挖掘方法，以下對該方法的具體步驟作詳細說明。

3.1 批次頻繁項集與持續(xù)性因子

持續(xù)性因子k表示，如果某項集在某一批次數(shù)據(jù)簇中是頻繁的，則該項集的信息將至少被統(tǒng)計k 次，具體如下。①如果一個項集在第i批次數(shù)據(jù)簇中是頻繁的，那么即使它在之后批次的數(shù)據(jù)簇中不是頻繁的，候選全局頻繁項集還是會對其相關(guān)信息進行保存與統(tǒng)計，直到第i+k批次數(shù)據(jù)簇。②如果該項集在后續(xù)的k個批次的數(shù)據(jù)簇中都不是頻繁的，則該項集在第i+k+1批次中將被視為普通項集。根據(jù)②，如果當前項集在第i+k+1個數(shù)據(jù)簇中是頻繁的，那么需將其支持度計算所需統(tǒng)計信息進行保存;但如果該項集在第i+k+1個數(shù)據(jù)簇中是不頻繁的，那么無須對其全局支持度計算相關(guān)信息進行保存。當然，在第i批次到第i+k+1批次個數(shù)據(jù)簇之間的每個數(shù)據(jù)簇中，若該項集出現(xiàn)局部頻繁，則需要將局部頻繁項集保存為候選頻繁項集，同時重新賦值當前持續(xù)性因子k ，并對接下來的k個數(shù)據(jù)簇項集相對應(yīng)的頻繁信息進行累計，并持續(xù)地繼續(xù)統(tǒng)計其信息。

持續(xù)性因子k可以擴展到根據(jù)數(shù)據(jù)簇批次不同而動態(tài)調(diào)整。一個簡單的辦法是根據(jù)不同批次數(shù)據(jù)簇進行數(shù)據(jù)歐式距離測算，當相鄰兩個數(shù)據(jù)簇歐式距離越大，則加大持續(xù)性因子;反之，則減少持續(xù)性因子。這里，根據(jù)數(shù)據(jù)分布來變化的持續(xù)性因子是本文提出的增量式算法的一個創(chuàng)新。

歷史數(shù)據(jù)簇頻繁項集集合重點對歷史全局候選頻繁項集集合進行描述，具體來說：①針對當前批次數(shù)據(jù)簇之前全部批次數(shù)據(jù)簇組成的數(shù)據(jù)集合，對這些數(shù)據(jù)集合的局部頻繁項集集合進行挖掘，并存儲其所有支持度相關(guān)信息，用以計算項集的全局近似支持度值;②在頻繁項集挖掘算法，如Apriori算法的基礎(chǔ)上，持續(xù)進行頻繁項集挖掘。

3.2 支持度計算與近似方法誤差估計

假設(shè)m_1個頻繁的數(shù)據(jù)簇中支持度值的總和為s_1，并對剩下的所有非頻繁數(shù)據(jù)簇中的統(tǒng)計信息進行統(tǒng)計，并在此基礎(chǔ)上設(shè)m_2個數(shù)據(jù)簇中的支持度值總和為s_2。而m_2作為所有項集中的非頻繁項集數(shù)據(jù)簇數(shù)，其值遠遠小于所有項集中頻繁項集數(shù)據(jù)簇數(shù)值，此時有：

m_2m_1

則該項集的全局支持度可近似地表示為：

ASupp= 1/m （s_1+（（m-m_1 ）×s_2）/m_2 ） ⑴

其中，ASupp表示的是近似支持度（approximate support）。

由于公式⑴是一個近似計算公式，因此必然會存在誤差，為證明該公式的準確性，本節(jié)重點對近似算法的誤差進行統(tǒng)計，從而對該算法進行更客觀的評估。本節(jié)通過支持度值的上界與下界進行分析，實驗對近似公式⑴的誤差進行估計。在本文中，Supp表示支持度（Support）的統(tǒng)計值。

假設(shè)支持度閥值（最小支持度值）為μ ，可得近似支持度的上界，有：

Supp ≤?Supp=（s_1+s_2+（m-m_1-m_2）×μ）/m ⑵

同時得其支持度的下界，有：

Supp≥▁Supp= （s_1+s_2）/m ⑶

于是，近似支持度值計算方法的誤差范圍有如下表示：

|ASupp-Supp|≤?Supp-▁Supp

=（m-m_1-m_2）×μ/m ⑷

基于對當前所有頻繁項集信息的整理，可得到一個關(guān)于頻繁項集的簡單估計即該項集的數(shù)據(jù)簇數(shù)量之和為m_1+m_2，且該值接近于數(shù)據(jù)簇總數(shù)m。因此，當m→∞時，誤差估計自然趨近于零;反之亦然，當m_2→∞時，則該項集的支持度近似值出現(xiàn)以下情況：①或許不能收斂;②或許能收斂但收斂于的數(shù)值低于閥值μ。如果非頻繁項集的近似支持度可以收斂，則其對應(yīng)為頻繁的m_1個數(shù)據(jù)簇的支持度值是收斂的，且收斂于數(shù)據(jù)簇總數(shù)量m。

增量式Apriori方法的具體步驟如圖1所示。

⑴ 根據(jù)模型參數(shù)選擇數(shù)據(jù)批次大小與持續(xù)性因子值;

⑵ 對于數(shù)據(jù)流批量數(shù)據(jù)中接收一批次的數(shù)據(jù)作為當前數(shù)據(jù)簇;

⑶ 計算當前批次數(shù)據(jù)簇與前一批次數(shù)據(jù)簇之間的歐式距離;當前批次數(shù)據(jù)為第一批次數(shù)據(jù)簇時，歐式距離默認賦值為最小值0;

⑷ 根據(jù)持續(xù)性因子抽取已處理過的數(shù)據(jù)摘要信息，包括歷史數(shù)據(jù)簇中支持度信息，從而獲得m_1，s_1，m_2，s_2的值;

⑸ 結(jié)合前面的數(shù)據(jù)摘要信息，對當前批次數(shù)據(jù)簇進行頻繁項集挖掘;

⑹ 輸出當前頻繁項集結(jié)果，如果有一下批次數(shù)據(jù)則重復上述步驟⑵-⑸。

3.3 方法實驗分析

本節(jié)主要進行方法實驗分析。實驗數(shù)據(jù)主要以數(shù)據(jù)生成器所生成的隨機數(shù)據(jù)集為基礎(chǔ)，將該數(shù)據(jù)集應(yīng)用到Apriori方法[9-10]中。在本節(jié)實驗中，僅展示出算法的固定持續(xù)性因子的情況。

實驗涉及的參數(shù)：持續(xù)性的因子k=3;最小支持度閥值μ=0.10。

如圖2所示，隨著數(shù)據(jù)簇批次的增多，總體數(shù)據(jù)量會相應(yīng)增加，傳統(tǒng)的Apriori算法需要在每次對數(shù)據(jù)簇批次重復掃描的基礎(chǔ)上實現(xiàn)對全局頻繁項集的挖掘，而利用增量式Apriori方法卻只需一次掃描數(shù)據(jù)，因此可節(jié)省大量時間，提高算法效率。本節(jié)實驗設(shè)定數(shù)據(jù)簇總批次為30。實驗過程中，不但對每一批次算法消耗時間進行了對比，同時也對比了全部批次算法消耗時間的平均值，并將其作為算法對比度量之一。在圖2中，當數(shù)據(jù)批次數(shù)大于15時，增量式Apriori方法耗費時間明顯低于其他對比方法。這說明數(shù)據(jù)量越大，增量式的方法的優(yōu)勢越明顯。

4 結(jié)束語

為了解決關(guān)聯(lián)規(guī)則與頻繁項集挖掘求解大規(guī)模數(shù)據(jù)耗時較長的問題，本文展示了一種增量式頻繁項集挖掘方法并將其作用于Apriori，即增量式Apriori。通過對持續(xù)性頻繁項集挖掘算法與近似的計算全局支持度算法的整合，來計算近似全局支持度值，從而找出全局頻繁項集。通常來說，數(shù)據(jù)量級越高，增量式頻繁項集挖掘方法找出的頻繁項集集合，與真實頻繁項集集合的結(jié)果越趨于一致。通過數(shù)據(jù)生成器模擬疾病相關(guān)數(shù)據(jù)，基于這些數(shù)據(jù)進行實驗對比分析，結(jié)果表明，相比標準Apriori算法，增量式Apriori方法具有效率高及性能穩(wěn)定等優(yōu)點。

參考文獻（References）：

[1] 古良云.頻繁模式挖掘方法的研究[D].江南大學碩士學位論文，2020.

[2] 李力恒，王曉磊.智能可穿戴式醫(yī)療設(shè)備在醫(yī)療數(shù)據(jù)信息安全中的應(yīng)用[J].自動化與儀器儀表，2020.3.

[3] 張玥，倪珺珉，王堅，宋小康，趙宇翔.基于關(guān)聯(lián)規(guī)則挖掘的健康信息學主題分析——以dHealth會議為例[J].信息資源管理學報，2020.10（6）：90-100

[4] 陳晨，王妮，黃艷群，周陽，李盛俊，陳卉.基于居民健康大數(shù)據(jù)的肥胖與常見慢病關(guān)聯(lián)規(guī)則分析[J].北京生物醫(yī)學工程，2020.39（4）：406-411

[5] 柯文俊，高金華，沈華偉，劉悅，程學旗.基于改進Apriori算法的問題模板無監(jiān)督抽取方法[J].中文信息學報，2020.34（10）：76-84

[6] 張千，方麗華，王慶瑋，孫曉，梁鴻，張萬義.基于機器學習的疾病診斷模型研究[J].計算機與數(shù)字工程，2020.48（7）：1705-1709

[7] 王青松，姜富山，李菲.大數(shù)據(jù)環(huán)境下基于關(guān)聯(lián)規(guī)則的多標簽學習算法[J].計算機科學，202047（5）：90-95

[8] Mohapatra Ankita， Sangita Khare， and Deepa Gupta.

Analysis of Tuberculosis Disease Using Association Rule Mining.In Advances in Artificial Intelligence and Data Engineering[J]. Springer， Singapore，2021：995-1008

[9] Wang Xiaoli， KuiSu， and Zhanbo Liu. Analysis of Diabetic

Association Rules Based on Apriori Algorithms.In Data Processing Techniques and Applications for Cyber-Physical Systems （DPTA 2019）[J].Springer，Singapore，2020：555-563

[10] Wang Chunxia， and Xiaoyue Zheng. Application of

improved time series Apriori algorithm by frequent itemsets in association rule data mining based on temporal constraint[J].Evolutionary Intelligence），2020.12（1）：39-49

收稿日期：2021-03-24

基金項目：本課題得到江蘇省科技支撐計劃項目（BE2019740）; 江蘇省高等學校自然科學研究項目（18KJA520008，20KJB520001）; 江蘇省高校研究生科研創(chuàng)新計劃項目（SJKY19_0761，SJKY19_0759，KYCX20_0759）

作者簡介：鄭會（1985-），女，河北廊坊人，博士，博士后，主要研究方向：數(shù)據(jù)挖掘，電子健康。

通訊作者：李鵬（1979-），男，福建長汀人，博士，教授，主要研究方向：高等教育研究、信息網(wǎng)絡(luò)。