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

張 沖,張?jiān)迫A

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

1 引言

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

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

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

2 改進(jìn)算法

2.1 經(jīng)典Apriori算法

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

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

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

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

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

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

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

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

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

2.2 改進(jìn)Apriori算法

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

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

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

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

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

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

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

規(guī)則3.布爾矩陣?yán)?滿足前k-2項(xiàng)相同的項(xiàng)才有必要在挖掘Fk過(guò)程中進(jìn)行自身連接.

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

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

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

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

表2 候選布爾矩陣B'1

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

表3 頻繁布爾矩陣B1

④ 根據(jù)規(guī)則2壓縮矩陣B1,即保留所有行;再根據(jù)規(guī)則3對(duì)矩陣 B1進(jìn)行自身連接,即連接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-項(xiàng)集和關(guān)聯(lián)規(guī)則如下:

表5 頻繁布爾矩陣B2

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

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

2.3 算法分析與對(duì)比

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

圖1 最小支持度與運(yùn)行時(shí)間

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

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

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

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

3.1 糖尿病高危因素分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖6 電子病歷部分?jǐn)?shù)據(jù)

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

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

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