鄭會(huì) 何靜 李鵬

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

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

中圖分類號(hào)：G642 ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A ? ? 文章編號(hào)：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 引言

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

1 現(xiàn)有問(wèn)題

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

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

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

問(wèn)題2：當(dāng)醫(yī)學(xué)數(shù)據(jù)庫(kù)中數(shù)據(jù)達(dá)到某個(gè)量級(jí)時(shí)，模型會(huì)因?yàn)楹臅r(shí)太長(zhǎng)而喪失時(shí)效性。

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

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

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

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

⑴ 沒(méi)有解決頻繁項(xiàng)集挖掘過(guò)程中效率低下的問(wèn)題。

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

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

2.1 方法主要目的

本文通過(guò)研究增量式頻繁挖掘算法，以期達(dá)到如下兩個(gè)目標(biāo)。

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

目標(biāo)2：成功過(guò)濾掉其他所有非潛在的全局頻繁項(xiàng)集，從而實(shí)現(xiàn)對(duì)存儲(chǔ)空間的最大優(yōu)化。

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

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

⑴ 對(duì)于某一批次中被認(rèn)定為頻繁的項(xiàng)集，直接保存該局部頻繁項(xiàng)集及其支持度信息。

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

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

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

3 方法的求解步驟

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

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

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

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

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

3.2 支持度計(jì)算與近似方法誤差估計(jì)

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

m_2m_1

則該項(xiàng)集的全局支持度可近似地表示為：

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

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

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

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

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

同時(shí)得其支持度的下界，有：

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

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

|ASupp-Supp|≤?Supp-▁Supp

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

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

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

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

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

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

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

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

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

3.3 方法實(shí)驗(yàn)分析

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)（References）：

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

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

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

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

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

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

[7] 王青松，姜富山，李菲.大數(shù)據(jù)環(huán)境下基于關(guān)聯(lián)規(guī)則的多標(biāo)簽學(xué)習(xí)算法[J].計(jì)算機(jī)科學(xué)，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

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

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

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