基于改進Apriori算法的糖尿病預(yù)診系統(tǒng)①

張 沖,張云華

(浙江理工大學(xué) 信息學(xué)院,杭州 310018)

1 引言

糖尿病(diabetes mellitus,DM)已成為世界性疾病,據(jù)世界衛(wèi)生組織(WHO)報道,2025年全球DM患者將達到3億.而更嚴重的是,DM相關(guān)疾病死亡人數(shù)為每年320萬[1].隨著人們生活水平的提高和生活方式的改變,DM發(fā)病率呈現(xiàn)低齡化,我國的DM患病率急劇增加.有關(guān)調(diào)查顯示,在我國經(jīng)濟發(fā)達地區(qū)DM患病率已高達9%～10%[2].

一方面,由于各方面診斷差異,糖尿病常被漏診誤診,對患者和社會醫(yī)療造成巨大負擔.另一方面,互聯(lián)網(wǎng)發(fā)展迅猛,醫(yī)療領(lǐng)域產(chǎn)生了海量臨床數(shù)據(jù),人工處理和分析所耗費成本過大.因此,需要一套良好的系統(tǒng)來完成對大量已確診病例的挖掘分析.

使用關(guān)聯(lián)規(guī)則可以挖掘分析高危因素與糖尿病之間的關(guān)系,但是,經(jīng)典Apriori算法主要存在兩大缺陷[3]:① 重復(fù)掃描數(shù)據(jù)庫,導(dǎo)致大量時間耗費于I/O操作[4].② 頻繁項集自身連接時產(chǎn)生大量候選集,導(dǎo)致空間消耗以指數(shù)形式增長.針對以上缺陷,本研究使用矩陣壓縮[5]的方式對Apriori算法進行改進,并應(yīng)用于糖尿病高危因素分析.基于此,設(shè)計了一款糖尿病預(yù)診分析系統(tǒng),該系統(tǒng)能夠分析患病概率,輔助醫(yī)療診斷.

2 改進算法

2.1 經(jīng)典Apriori算法

關(guān)聯(lián)分析中的Apriori算法是一種最具影響力的挖掘關(guān)聯(lián)規(guī)則頻繁項集的算法,其核心是基于兩階段頻繁項集思想的遞推算法.即首先找出滿足最小支持度的所有頻繁項集,然后探索同時滿足最小支持度閾值和最小置信度閾值的強關(guān)聯(lián)規(guī)則,從中發(fā)現(xiàn)隱藏在數(shù)據(jù)間的相關(guān)性.將經(jīng)典Apriori算法用數(shù)學(xué)語言可描述如下:

記項集X與Y,關(guān)聯(lián)規(guī)則可表示為如下蘊涵式:

記式(1)中項集X出現(xiàn)的事務(wù)次數(shù)為 σ(X),事務(wù)數(shù)據(jù)庫為T,則支持度的定義可表示為式(2):

置信度的定義可表示為式(3),其中,支持度大于閾值的項集,稱作頻繁項集,記為F.

經(jīng)典Apriori算法使用逐層搜索的迭代方法,用k-項集探索(k+1)-項集.首先找到頻繁1-項集,再依據(jù)頻繁1-項集尋找頻繁2-項集,直到找出所有頻繁項集,并產(chǎn)生大于閾值的關(guān)聯(lián)規(guī)則,如式(4):

記k-項集為Ck,記頻繁k-項集為Fk,記事務(wù)長度為|Tk|,Apriori算法有如下三條性質(zhì):

性質(zhì)1.Fk出 現(xiàn)的事務(wù)次數(shù)不小于最小支持數(shù).

性質(zhì)2.長度小于k的事務(wù)不包含任何Fk[6].

性質(zhì)3.由Ck-1生 成Ck過程中,若Ck-1-2項不同的項做自身連接,將得到冗余項集或非頻繁項集[7].

2.2 改進Apriori算法

經(jīng)典算法每找一個頻繁項集Fk都需要掃庫一次,導(dǎo)致大量時間耗費于I/O操作;其次,經(jīng)典算法探索下一個頻繁項集過程中做自身連接來產(chǎn)生候選項集時,存在大量冗余.

現(xiàn)有較多Apriori算法的優(yōu)化或改進方案,文獻[8]將算法剪枝與矩陣相聯(lián)系來減少掃庫次數(shù),提高了算法效率,但未處理自連接產(chǎn)生的冗余.文獻[9]采用事務(wù)矩陣相乘的方法得到頻繁項集,一定程度上減少I/O操作,但在事務(wù)數(shù)據(jù)庫體量偏大時,矩陣相乘將會占用較多CPU計算時間.

盡管Apriori算法已存在諸多改進方案,但從空間占用率上講,較少有改進方案處理自連接的冗余,從時間效率上講,也尚有進一步優(yōu)化和改進的余地.本文改進算法在自連接過程中去除項集冗余,縮減空間占用率,以避免無效計算.并用事務(wù)布爾矩陣壓縮的方式對計算方式進行改進,進一步提高算法時間性能.

記項I的向量為,如式(5).其中m為事務(wù)總數(shù),Ti為第i個事務(wù).

根據(jù)式(5)建立形如式(6)的事務(wù)布爾矩陣B.其中m為事務(wù)總數(shù),n為項總數(shù).

結(jié)合以上定義與Apriori算法的三大性質(zhì),可推導(dǎo)得到如下三條對布爾矩陣進行壓縮的規(guī)則:

規(guī)則2.布爾矩陣里,長度小于k的事務(wù)可以在挖掘Fk過程中刪除.即行應(yīng)滿足式(9):

規(guī)則3.布爾矩陣里,滿足前k-2項相同的項才有必要在挖掘Fk過程中進行自身連接.

下面分析一個建立事務(wù)布爾矩陣,在經(jīng)典算法的基礎(chǔ)上對掃庫和自連接步驟進行改進,即根據(jù)壓縮矩陣獲取頻繁項集和探索關(guān)聯(lián)規(guī)則的實例:

① 輸入事務(wù)數(shù)據(jù)庫T,如表1.輸入最小支持度min_sup=0.5,最小置信度min_conf=0.7.

表1 事務(wù)數(shù)據(jù)庫

② 掃描事務(wù)數(shù)據(jù)庫,建立候選布爾矩陣B′1,并于首行 首列和末行末列各類輔助值,如表2所示.

表2 候選布爾矩陣B'1

③ 根據(jù)規(guī)則1壓縮矩陣B'1,即保留A、B、C、D列,得到矩陣B1如表3.分析B1得頻繁1-項集如下:

表3 頻繁布爾矩陣B1

④ 根據(jù)規(guī)則2壓縮矩陣B1,即保留所有行;再根據(jù)規(guī)則3對矩陣 B1進行自身連接,即連接AB、AC、A D、BC、BD、CD列;最后得到矩陣B′2如表4.

表4 候選布爾矩陣B'2

⑤ 重復(fù)③: 根據(jù)規(guī)則1壓縮矩陣 B′2,即保留AB、AC、BC、CD列,得到矩陣 B2如表5.分析B2可得頻繁2-項集和關(guān)聯(lián)規(guī)則如下:

表5 頻繁布爾矩陣B2

⑥ 以此類推,根據(jù)規(guī)則1和規(guī)則2不斷壓縮矩陣,直到B′i≠?,算法結(jié)束.

結(jié)合上述分析,改進Apriori算法偽代碼如下:

2.3 算法分析與對比

為驗證性能是否得到提升,對兩個算法進行實驗對比.實驗環(huán)境為: Intel Core i5 CPU 3.20 GHz,4 GB內(nèi)存,512 GB硬盤,Windows 10 操作系統(tǒng),在Matlab R2017b中得到以下關(guān)于兩個算法的性能對比圖.

圖1 最小支持度與運行時間

從圖1可以看出,在相同的最小支持度下,改進Apriori算法在運行速度上得到了明顯性能提升.

圖2 最小支持度與頻繁項集數(shù)

從圖2可以看出,在相同的最小支持度下,改進Apriori算法在探索頻繁項集的過程中比經(jīng)典Apriori算法冗余更少,相應(yīng)所占用空間也更小.

3 糖尿病預(yù)診系統(tǒng)設(shè)計

3.1 糖尿病高危因素分析

本研究從UCL糖尿病數(shù)據(jù)集選取其中8個相關(guān)危險因素[10]進行分析,分別是: 年齡,有無高血壓或高血脂病史,身體質(zhì)量指數(shù)(BMI),腰臀比(WHR),是否吸煙,是否飲酒,是否過度飲食和運動量是否達標.將以上因素分別記為項A到項H,針對其中若干非布爾類型的數(shù)據(jù)預(yù)處理[11],年齡大于45記為1,BMI大于28記為1,男性WHR大于0.85、女性WHR大于0.8記為1.最后再加入預(yù)診結(jié)果項I,將所有數(shù)據(jù)整理為事務(wù)數(shù)據(jù)庫,便于后續(xù)工作進行挖掘和分析.

3.2 系統(tǒng)架構(gòu)設(shè)計

系統(tǒng)選用時下熱門技術(shù)棧: RPC框架Dubbo,微服務(wù)框架Spring Boot,消息中間件RabbitMQ,關(guān)系型數(shù)據(jù)庫MySQL,以及作為緩存的Redis.

Dubbo是一款開源RPC框架,它提供了三大核心能力: 面向接口的遠程方法調(diào)用,智能容錯和負載均衡,以及服務(wù)自動注冊和發(fā)現(xiàn).該框架不僅實現(xiàn)了高性能、高可用性,而且使用方便,擴展性極佳[12].

Spring Boot是Java領(lǐng)域知名的微服務(wù)框架,微服務(wù)的目的在于化解整體架構(gòu)服務(wù)的復(fù)雜性,以簡單快速的方式實現(xiàn)各個服務(wù)的部署和變更.而Spring Boot提供了形式多樣的庫,支持JPA、RESTFul、Docker等技術(shù),能夠讓配置、部署和監(jiān)控變得簡單方便[13].

RabbitMQ基于Erlang語言編寫,用于在分布式系統(tǒng)中存儲轉(zhuǎn)發(fā)異步消息,將彼此獨立的計算機連接起來組成松耦合的系統(tǒng),RabbitMQ在易用性擴展性、高可用性等方面表現(xiàn)不俗[14].

MySQL是一款由瑞典的公司開發(fā)并且廣泛應(yīng)用于中小型企業(yè)或組織的免費數(shù)據(jù)庫,基于Linux 操作系統(tǒng)開發(fā),MySQL體積小、速度快、總體擁有成本低.

Redis是一款基于內(nèi)存的、可持久化的非關(guān)系型Key-Value存儲系統(tǒng),它支持多種數(shù)據(jù)類型,并支持原子性操作[15].Redis與其他Cache相比,擁有更多的數(shù)據(jù)結(jié)構(gòu)并支持更豐富的數(shù)據(jù)操作.

基于上述所選技術(shù)棧進行系統(tǒng)架構(gòu)設(shè)計,將系統(tǒng)劃分為如圖3所示的若干層面.

圖3 糖尿病預(yù)診系統(tǒng)架構(gòu)圖

網(wǎng)關(guān)層: 作為統(tǒng)一請求入口,處理權(quán)限認證及負載均衡等,向外提供RESTFul API,并采用令牌桶算法實現(xiàn)API的動態(tài)限流.

服務(wù)代理層: 為提高系統(tǒng)擴展性和可復(fù)用性,抽取公用服務(wù)接口,由代理將請求路由至具體服務(wù).

具體服務(wù)層: 具體實現(xiàn)三大核心功能,包括關(guān)聯(lián)規(guī)則挖掘、糖尿病預(yù)診分析、電子病歷處理.

預(yù)診分析模塊: 基于用戶電子病歷中的數(shù)據(jù),計算各項高危因素的指標,并匹配滿足置信度的關(guān)聯(lián)規(guī)則,分析糖尿病的患病概率.

電子病歷模塊: 為用戶建立電子病歷,涵蓋用戶各項相關(guān)高危因素信息,并針對特定項進行量化入庫.

規(guī)則挖掘模塊: 對于管理員設(shè)定的支持度和置信度,基于所建事務(wù)數(shù)據(jù)庫,在后臺挖掘滿足支持度和置信度閾值的關(guān)聯(lián)規(guī)則,并將關(guān)聯(lián)規(guī)則落庫.

3.3 系統(tǒng)流程設(shè)計

系統(tǒng)具體使用流程如圖4所示,主要包括三大核心功能的使用流程: 糖尿病自查流程、電子病歷錄入流程和關(guān)聯(lián)規(guī)則挖掘流程.

圖4 糖尿病預(yù)診系統(tǒng)流程圖

① 當用戶提交自查請求,網(wǎng)關(guān)層會對請求做權(quán)限認證、接口限流令牌校驗、安全處理等.隨后會生產(chǎn)一條異步消息推送至RabbitMQ,由代理層消費消息并路由至具體服務(wù),實現(xiàn)規(guī)則匹配和異步結(jié)果返回.

② 當用戶電子病歷記錄為空時,醫(yī)護人員錄入用戶各項相關(guān)數(shù)據(jù).數(shù)據(jù)提交后,代理層調(diào)用具體服務(wù)處理數(shù)據(jù),生成電子病歷并存儲入庫.

③ 當管理員提交關(guān)聯(lián)規(guī)則挖掘請求時,網(wǎng)關(guān)層對權(quán)限進行校驗,隨后代理層路由至具體服務(wù),使用改進Apriori算法在后臺對數(shù)據(jù)集進行篩選和挖掘.在關(guān)聯(lián)規(guī)則落庫后,以站內(nèi)信和其他特定方式通知管理員關(guān)聯(lián)規(guī)則的挖掘結(jié)果.

3.4 系統(tǒng)核心配置和UI設(shè)計

HIS子系統(tǒng)服務(wù)提供者配置文件provide.xml核心內(nèi)容如下,其中包括暴露的服務(wù)接口及注冊地址:

服務(wù)消費者配置文件consumer.xml核心內(nèi)容如下,同樣包含其注冊地址等信息:

接口HisRemoteService定義如下,其中包含根據(jù)病歷號或姓名性別查找患者、根據(jù)患者查找電子病歷和診斷結(jié)果等方法:

系統(tǒng)用雷達圖展示各指標危險臨界點與自身指標情況;用餅圖展示糖尿病患者某指標異常的比例;最后輔以診斷分析和醫(yī)囑建議等文字,效果如圖5所示.

3.5 預(yù)診結(jié)果分析

截取部分電子病歷的核心數(shù)據(jù),如圖6所示,其中年齡、病史、BMI、WHR、吸煙、飲酒、過度飲食、運動量達標為八項相關(guān)因素.

將八項高危因素按照3.1節(jié)規(guī)則量化,得到如圖7所示的項A到項H.運算得出結(jié)果即項I,可以發(fā)現(xiàn)與真實診斷結(jié)果無異.

圖5 糖尿病預(yù)診分析界面

圖6 電子病歷部分數(shù)據(jù)

圖7 量化后的數(shù)據(jù)

4 結(jié)束語

針對Apriori經(jīng)典算法存在的缺陷,本研究進行了改進,并應(yīng)用于糖尿病與其高危因素間的關(guān)聯(lián)規(guī)則挖掘.通過實驗對算法進行對比,結(jié)果表明改進Apriori算法性能得到了大幅度提高.基于以上工作,本研究設(shè)計了一款糖尿病預(yù)診分析系統(tǒng),隨著挖掘樣本數(shù)量的逐步增加其準確率也逐步提升.此系統(tǒng)為用戶自診和醫(yī)護人員輔助診斷提供了更加便捷的方式.