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

張 沖,張云華

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

1 引言

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

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

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

2 改進算法

2.1 經典Apriori算法

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

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

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

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

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

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

性質1.Fk出 現的事務次數不小于最小支持數.

性質2.長度小于k的事務不包含任何Fk[6].

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

2.2 改進Apriori算法

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

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

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

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

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

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

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

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

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

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

表1 事務數據庫

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

表2 候選布爾矩陣B'1

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

表3 頻繁布爾矩陣B1

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

表4 候選布爾矩陣B'2

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

表5 頻繁布爾矩陣B2

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

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

2.3 算法分析與對比

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

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

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

圖2 最小支持度與頻繁項集數

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

3 糖尿病預診系統(tǒng)設計

3.1 糖尿病高危因素分析

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

3.2 系統(tǒng)架構設計

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

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

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

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

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

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

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

圖3 糖尿病預診系統(tǒng)架構圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.5 預診結果分析

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

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

圖5 糖尿病預診分析界面

圖6 電子病歷部分數據

圖7 量化后的數據

4 結束語

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