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

鄭會 何靜 李鵬

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

關鍵詞： 醫療診斷與預測; 關聯規則; 增量式算法; 數據流

中圖分類號：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 引言

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

1 現有問題

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

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

問題1：隨著醫學數據規模的不斷增加，醫學數據庫的量級也在持續增大，使得構建模型所需時間不斷延長。

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

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

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

2 方法構建方案

在醫學領域上采用關聯規則算法具有明顯的優勢，關聯規則算法可以挖掘出數據潛在關系與關聯[7]，從而可以在醫學領域上協助實現醫療診斷與預測[8]。但是，其在應用中仍存在一些不足。

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

⑵ 并不適用于對大數據問題的處理，特別是在處理增量式醫療大數據時還未發揮應有的作用。

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

2.1 方法主要目的

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

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

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

2.2 研究內容與創新性

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

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

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

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

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

3 方法的求解步驟

本文通過對增量式頻繁項集挖掘方法的構建，來實現數據流數據頻繁項集挖掘方法，以下對該方法的具體步驟作詳細說明。

3.1 批次頻繁項集與持續性因子

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

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

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

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

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

m_2m_1

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

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

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

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

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

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 ⑷

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

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

⑴ 根據模型參數選擇數據批次大小與持續性因子值;

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

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

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

⑸ 結合前面的數據摘要信息，對當前批次數據簇進行頻繁項集挖掘;

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

3.3 方法實驗分析

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

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

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

4 結束語

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

參考文獻（References）：

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

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

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

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

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

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

[7] 王青松，姜富山，李菲.大數據環境下基于關聯規則的多標簽學習算法[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）; 江蘇省高校研究生科研創新計劃項目（SJKY19_0761，SJKY19_0759，KYCX20_0759）

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

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