Apriori算法的改進(jìn)及其在睡眠輔助醫(yī)療中的應(yīng)用

石 升，董金琳，王 瑋，閆 悅，孫艷蕊

(東北大學(xué) 理學(xué)院，沈陽(yáng) 110819)

1 引 言

關(guān)聯(lián)規(guī)則挖掘是指從數(shù)據(jù)中挖掘出不同元素之間的感興趣的規(guī)則，這種規(guī)則一般具有利用價(jià)值.Apriori算法對(duì)關(guān)聯(lián)規(guī)則挖掘的進(jìn)一步研究提供了新的思路.如Savasere[1]等人設(shè)計(jì)了基于否定規(guī)則的算法，葉永偉[2]等提出了基于興趣度關(guān)聯(lián)規(guī)則的算法，程昌品[3]等提出了基于矩陣與項(xiàng)集索引表的頻繁項(xiàng)集挖掘算法，邢俊鳳[4]等采用優(yōu)化關(guān)聯(lián)規(guī)則Apriori算法等.

睡眠呼吸暫停低通氣綜合征是一種臨床常見(jiàn)的呼吸系統(tǒng)疾病[5]，智慧輔助醫(yī)療建模是一種對(duì)醫(yī)療數(shù)據(jù)進(jìn)行挖掘從而實(shí)現(xiàn)醫(yī)療輔助的模型[6].利用現(xiàn)代的數(shù)據(jù)分析技術(shù)對(duì)患者的基本信息、病史、身體狀況等重要文本潛在病因特征以及與PSG檢查結(jié)果的關(guān)系進(jìn)行分析，挖掘患者潛在的病因?qū)ψ枞运吆粑鼤和；颊叩陌l(fā)病、病情嚴(yán)重程度、病程進(jìn)展及預(yù)后、相互影響等的作用大小，從而實(shí)現(xiàn)自動(dòng)的醫(yī)療臨床輔助，成為目前病情診斷的理想方法.

目前睡眠呼吸暫停低氣綜合征(PSG)方面沒(méi)有一個(gè)成熟的模型.在醫(yī)療過(guò)程中，大多還是依靠傳統(tǒng)經(jīng)驗(yàn)而進(jìn)行診斷，這樣就難免產(chǎn)生誤診的情況.為解決這些的問(wèn)題，對(duì)現(xiàn)有的Apriori算法進(jìn)行了研究、建立了基于改進(jìn)Apriori算法的睡眠呼吸暫停低通氣綜合征醫(yī)療模型，利用沈陽(yáng)市某醫(yī)院提供的關(guān)于睡眠呼吸暫停低通氣綜合征的病例醫(yī)療記錄驗(yàn)證了模型的有效性.

本文將對(duì)Apriori算法的改進(jìn)以及改進(jìn)算法在睡眠呼吸暫停低通氣綜合征輔助醫(yī)療建模上的應(yīng)用進(jìn)行研究.第1節(jié)對(duì)Apriori算法的原理和步驟進(jìn)行了介紹；第2節(jié)具體描述了基于組合思想的改進(jìn)Apriori算法的改進(jìn)方法和具體步驟；第3節(jié)闡述了基于位運(yùn)算和預(yù)剪枝的改進(jìn)Apriori算法的改進(jìn)方法和具體步驟；第4節(jié)說(shuō)明了具體的實(shí)驗(yàn)過(guò)程，包括預(yù)處理、算法性能、準(zhǔn)確率的分析比較和實(shí)驗(yàn)處理等過(guò)程；第5節(jié)對(duì)算法性能和實(shí)驗(yàn)結(jié)果進(jìn)行了詳細(xì)的分析比較；第6節(jié)對(duì)本文所進(jìn)行的工作進(jìn)行總結(jié)并進(jìn)一步討論下一步要進(jìn)行的工作.

2 Apriori算法

Apriori算法使用逐層搜索的迭代方法對(duì)頻繁項(xiàng)集進(jìn)行挖掘并對(duì)支持度計(jì)數(shù)進(jìn)行統(tǒng)計(jì)再用于關(guān)聯(lián)規(guī)則的挖掘[7].

2.1 符號(hào)與基本概念

符號(hào)說(shuō)明：I={i1，i2，…，im}是全體數(shù)據(jù)項(xiàng)集；D是全體事務(wù)集，|D|表示總事務(wù)數(shù)，每個(gè)事務(wù)有唯一的標(biāo)識(shí).

定義1.數(shù)據(jù)集X在D中的支持?jǐn)?shù)是D中包含D的事務(wù)數(shù).X在D中的支持度就是X在D中的支持?jǐn)?shù)與D的總事務(wù)數(shù)之比.

定義2.支持度閾值S是X滿足最低顯著性需求的支持度，支持?jǐn)?shù)閾值是達(dá)到S所需的支持?jǐn)?shù)，滿足如下關(guān)系.

min-support(X)=S×|D|

(1)

如果X的支持度達(dá)到S，則稱X為頻繁項(xiàng)集.

定義3.含有事務(wù)數(shù)最多的頻繁項(xiàng)集稱為最大頻繁項(xiàng)集.

2.2 算法步驟

Apriori算法作為一種寬度優(yōu)先的算法產(chǎn)生的頻繁項(xiàng)集的子集都是頻繁的且不頻繁項(xiàng)集的超集都是不頻繁的[8].

產(chǎn)生頻繁項(xiàng)集具體步驟如下：

步驟1.通過(guò)遍歷一次數(shù)據(jù)庫(kù)統(tǒng)計(jì)一切單個(gè)事務(wù)的支持度并將達(dá)到閾值的事務(wù)組成1維頻繁項(xiàng)集L1；

步驟2.從最大頻繁項(xiàng)集集合Lk中生成長(zhǎng)度為k+1的候選集Ck+1，通過(guò)遍歷數(shù)據(jù)庫(kù)統(tǒng)計(jì)所有候選項(xiàng)目的支持度并將達(dá)到閾值的項(xiàng)目組成k+1維頻繁項(xiàng)集Lk+1；

步驟3.轉(zhuǎn)至步驟2，直至新生成的頻繁項(xiàng)目集Lk+1為空集，最后得到頻繁項(xiàng)目集集合為.

(2)

2.3 算法缺點(diǎn)

Apriori算法具有遍歷數(shù)據(jù)庫(kù)次數(shù)多、內(nèi)存消耗大、運(yùn)行時(shí)間長(zhǎng)的缺點(diǎn)[9]，本文基于這些缺點(diǎn)對(duì)算法進(jìn)行目標(biāo)為減少單次遍歷的時(shí)間以及減少遍歷次數(shù)的改進(jìn).

3 基于組合思想的改進(jìn)Apriori算法

針對(duì)Apriori算法遍歷數(shù)據(jù)庫(kù)次數(shù)多的缺點(diǎn)利用組合思想在第2次掃描到該數(shù)據(jù)集時(shí)將其所有可能的子集找出并生成子集庫(kù).結(jié)合相關(guān)性質(zhì)找出所有的頻繁項(xiàng)集將遍歷次數(shù)減少到3次.

3.1 組合思想

組合是指通過(guò)每次從原集合中選出不同的項(xiàng)的方法生成原集合的所有子集.在尋找頻繁項(xiàng)集時(shí)，每一個(gè)事務(wù)集包含的頻繁項(xiàng)集只能是該事務(wù)集的子集.原算法需要不斷的通過(guò)k-1項(xiàng)頻繁項(xiàng)集生成k項(xiàng)候選集，并掃描原數(shù)據(jù)庫(kù)計(jì)算k項(xiàng)集的支持度計(jì)數(shù)來(lái)判斷k項(xiàng)候選集是否是頻繁項(xiàng)集.

通過(guò)組合的方式在第1次遍歷數(shù)據(jù)庫(kù)時(shí)將每一事務(wù)集的所有子集找出，最后子集在所有事務(wù)集生成的全部子集中出現(xiàn)的次數(shù)即為其支持度計(jì)數(shù)，其長(zhǎng)度即為項(xiàng)集的長(zhǎng)度，不需要重新生成更高項(xiàng)集以及計(jì)算支持度計(jì)數(shù).

3.2 算法步驟

改進(jìn)后的Apriori算法可通過(guò)將事務(wù)組合后對(duì)子集進(jìn)行挖掘的方法大幅度減少遍歷原數(shù)據(jù)庫(kù)的次數(shù).其產(chǎn)生頻繁項(xiàng)集及其支持度的具體步驟如下：

步驟1.通過(guò)遍歷一次數(shù)據(jù)庫(kù)統(tǒng)計(jì)一切單個(gè)事務(wù)的支持度并將達(dá)到閾值的事務(wù)組成1維頻繁項(xiàng)集L1；

步驟2.通過(guò)遍歷一次數(shù)據(jù)庫(kù)將每一個(gè)事務(wù)集中不屬于L1中的項(xiàng)目刪除以更新數(shù)據(jù)庫(kù)；

步驟3.將第1個(gè)事務(wù)集D1的所有子集找出放入候選集C中并將計(jì)數(shù)初始化為1；

步驟4.通過(guò)遍歷一次數(shù)據(jù)庫(kù)，在遍歷到第i個(gè)事務(wù)集D1時(shí)，通過(guò)組合思想將事務(wù)集D1的所有子集找出來(lái)，將一切子集對(duì)比加入到候選集C中，若子集屬于C將其支持度計(jì)數(shù)加1；若子集不屬于C加入該子集更新候選集C并將其支持度計(jì)數(shù)設(shè)為1；

步驟5.將候選集C中一切事務(wù)集的支持度計(jì)數(shù)與支持度計(jì)數(shù)閾值進(jìn)行比較，若不小于閾值則為頻繁項(xiàng)集將事務(wù)集和其支持度計(jì)數(shù)保存在集合L中，最終生成頻繁項(xiàng)集集合L.

4 基于且位運(yùn)算和預(yù)剪枝的改進(jìn)Apriori算法

針對(duì)Apriori算法內(nèi)存消耗大和運(yùn)行時(shí)間長(zhǎng)的缺點(diǎn)利用矩陣存儲(chǔ)數(shù)據(jù)并利用且位運(yùn)算進(jìn)行項(xiàng)集運(yùn)算簡(jiǎn)化計(jì)算過(guò)程.利用預(yù)剪枝加強(qiáng)剪枝條件使得每一次由低項(xiàng)集生成高項(xiàng)集時(shí)減少候選集的生成并提高運(yùn)行效率.

4.1 且位運(yùn)算與預(yù)剪枝

位運(yùn)算是指將整數(shù)對(duì)應(yīng)的二進(jìn)制數(shù)直接進(jìn)行處理[10].本文利用且位運(yùn)算(&)對(duì)數(shù)據(jù)集進(jìn)行計(jì)算.

預(yù)剪枝是指在每一次由低項(xiàng)頻繁項(xiàng)集生成高項(xiàng)候選項(xiàng)集時(shí)利用頻繁項(xiàng)集的所有子集都是頻繁的等性質(zhì)對(duì)候選項(xiàng)集進(jìn)行篩選并刪除不符合要求的項(xiàng)集，以此達(dá)到減少計(jì)算量的目的.

4.2 改進(jìn)方法

4.2.1 符號(hào)說(shuō)明

數(shù)據(jù)集Ac×m=(a1，a2，…，ac)T，共有c條數(shù)據(jù)，m個(gè)特征，ai={ai1，ai2，…，aim}(1≤i≤c)表示A的第i行，其中aij(1≤j≤m)的可能取值為0或1，其中1代表第i條數(shù)據(jù)含有第j個(gè)特征，0代表無(wú).

頻繁k項(xiàng)集的集合為Yk={y1，y2，…，ylk}，Yk中元素個(gè)數(shù)為lk，也即頻繁k項(xiàng)集的個(gè)數(shù)為lk，對(duì)第i個(gè)頻繁k項(xiàng)集yi={yi1，yi2，…，yim}，其中yij=0或1(1≤j≤m)，且滿足.

(3)

若yij=1表示第i個(gè)頻繁k項(xiàng)集包含第j個(gè)特征，若為0，則無(wú).支持度閾值為sup，候選頻繁k項(xiàng)集的集合為Ck.

4.2.2 預(yù)剪枝條件

加強(qiáng)預(yù)剪枝條件，在原有剪枝條件的基礎(chǔ)上，從篩選候選1項(xiàng)集開(kāi)始，對(duì)預(yù)剪枝判斷失敗或支持度計(jì)數(shù)未達(dá)標(biāo)準(zhǔn)的項(xiàng)集進(jìn)行記錄于矩陣B.在產(chǎn)生k選項(xiàng)集的預(yù)剪枝判斷過(guò)程中，對(duì)產(chǎn)生的項(xiàng)集與當(dāng)前已有的矩陣B進(jìn)行匹配，若B中存在某行向量與該項(xiàng)集匹配成功，則該項(xiàng)集預(yù)剪枝判斷不通過(guò).

4.2.3 且位運(yùn)算和矩陣存儲(chǔ)

利用計(jì)算機(jī)位運(yùn)算中的且位運(yùn)算進(jìn)行處理，利用特殊矩陣存儲(chǔ)數(shù)據(jù)庫(kù)，簡(jiǎn)化支持度計(jì)數(shù)的計(jì)算過(guò)程.

1)候選1項(xiàng)集的支持度計(jì)數(shù)

對(duì)給定的某個(gè)下標(biāo)k特征，直接對(duì)指定列經(jīng)累加可得其1項(xiàng)集的支持度為:

(4)

可以減少一次遍歷.

2)候選k項(xiàng)集的支持度計(jì)數(shù)

Apriori算法在計(jì)算候選k項(xiàng)集支持度計(jì)數(shù)時(shí)對(duì)候選項(xiàng)集中每個(gè)項(xiàng)至少進(jìn)行n×(k-1)次判斷.本文利用計(jì)算機(jī)自有的且位運(yùn)算對(duì)候選項(xiàng)集的支持度進(jìn)行統(tǒng)計(jì).

當(dāng)xi&xj=xj時(shí)，有xi?xj，也即xj中的項(xiàng)在xi中均有出現(xiàn).由此得到.

定理1.對(duì)給定的某個(gè)候選項(xiàng)集yj，該候選項(xiàng)集的支持度計(jì)數(shù)為:

(5)

其中ai為矩陣A的第i行.

3)預(yù)剪枝的匹配計(jì)數(shù)

根據(jù)且位運(yùn)算的相關(guān)性質(zhì)，可以得到.

定理2.對(duì)項(xiàng)集y，若存在某行Bi，使得Bi&y==Bi的值為1(真)，則y是非頻繁項(xiàng)集.

4.3 算法步驟

基于且位運(yùn)算和預(yù)剪枝的改進(jìn)Apriori算法可一定程度提高運(yùn)行效率.其具體步驟如下.

步驟1.通過(guò)遍歷一次數(shù)據(jù)庫(kù)利用位運(yùn)算統(tǒng)計(jì)數(shù)據(jù)庫(kù)中所有單個(gè)項(xiàng)目的支持度并將達(dá)到閾值的項(xiàng)目組成1維頻繁項(xiàng)目集L1；

步驟2.從最大頻繁項(xiàng)集集合Lk中生成長(zhǎng)度為k+1的候選集Ck+1，將候選集Ck+1與記錄矩陣Bk進(jìn)行比較，刪除非頻繁項(xiàng)集，通過(guò)遍歷數(shù)據(jù)庫(kù)統(tǒng)計(jì)所有候選項(xiàng)目的支持度并將達(dá)到閾值的項(xiàng)目組成k+1維頻繁項(xiàng)目集Lk+1同時(shí)使用沒(méi)有達(dá)到閾值的項(xiàng)目更新非頻繁項(xiàng)集記錄矩陣Bk生成Bk+1；

步驟3.轉(zhuǎn)至步驟2，直至新生成的頻繁項(xiàng)目集Lk+1為空集，最后由公式(1)得到頻繁項(xiàng)目集集合為L(zhǎng).

4.4 算法準(zhǔn)確性分析

當(dāng)n=1時(shí)，對(duì)于任意的頻繁1項(xiàng)集yi={yi1，yi2，…，yim}(1≤i≤ln)，存在唯一的p(0≤p≤m)，有yip=1且yij=0對(duì)于任意的j≠p都成立，又由于yi是頻繁的，必有:

(6)

所以yi可被正確選擇進(jìn)入頻繁項(xiàng)集集合.

假設(shè)n≤k-1，k≥2時(shí)，頻繁項(xiàng)集集合都準(zhǔn)確.則當(dāng)n=k時(shí)，對(duì)于任意的頻繁k項(xiàng)集yi={yi1，yi2，…，yim}(1≤i≤ln)，其前k-1項(xiàng)也是頻繁的，所以yi∈Cn，又頻繁項(xiàng)集的子集均是頻繁的，所以yi中不存在不頻繁的子集，即yi可通過(guò)預(yù)剪枝，由其頻繁可得:

(7)

如果(ai&yi)==yi為真，那么(ai&yi)==yi的值為1，否則值為0，也即yi可被正確選擇進(jìn)入頻繁n項(xiàng)集集合.

5 實(shí)驗(yàn)過(guò)程

5.1 數(shù)據(jù)樣本介紹

為研究病癥與臨床表現(xiàn)、生活習(xí)慣等的關(guān)系，本文使用來(lái)自沈陽(yáng)市某醫(yī)院的數(shù)千條醫(yī)療記錄作為數(shù)據(jù)源，信息包括年齡、性別、一些行為表現(xiàn)如晨起口干，夜間憋尿等，還包括患者血壓記錄、其他疾病記錄史等.

5.2 數(shù)據(jù)預(yù)處理

5.2.1 建立病人系統(tǒng)數(shù)據(jù)庫(kù)

利用Excel對(duì)數(shù)據(jù)進(jìn)行預(yù)處理并將文本形式醫(yī)療記錄信息轉(zhuǎn)化為數(shù)據(jù)庫(kù)表格.每一行代表一位病人的信息，每一列代表所有病人的某個(gè)具體特征信息.

5.2.2 數(shù)據(jù)清洗和離散化

數(shù)據(jù)清理主要將數(shù)據(jù)中的缺失值和異常數(shù)據(jù)進(jìn)行識(shí)別和刪除處理.在缺失值的識(shí)別及刪除處理方面，由于部分項(xiàng)目如就診日期、病人姓名等對(duì)本文的研究無(wú)較大意義，本文對(duì)這些事務(wù)進(jìn)行了刪除處理，而對(duì)于在部分?jǐn)?shù)據(jù)中出現(xiàn)某項(xiàng)缺失值的整行數(shù)據(jù)進(jìn)行了刪除處理.數(shù)據(jù)離散方面，本文通過(guò)查找相關(guān)醫(yī)學(xué)文獻(xiàn)，依據(jù)每個(gè)字段的標(biāo)準(zhǔn)值，將連續(xù)數(shù)據(jù)離散化.進(jìn)一步進(jìn)行數(shù)據(jù)歸約，并對(duì)離散后的數(shù)據(jù)進(jìn)行了相關(guān)字符編碼.

5.3 實(shí)驗(yàn)步驟

本文首先隨機(jī)生成數(shù)據(jù)規(guī)模為500×26、1000×26、1500×26、2000×26、5000×5、5000×10、5000×15和5000×20的8個(gè)數(shù)據(jù)集，分別使用Apriori算法、基于組合思想的改進(jìn)Apriori算法和基于且位運(yùn)算和預(yù)剪枝的改進(jìn)Apriori算法對(duì)隨機(jī)數(shù)據(jù)集進(jìn)行處理，比較分析3個(gè)算法的性能和準(zhǔn)確率并利用基于位運(yùn)算和預(yù)剪枝的改進(jìn)Apriori算法對(duì)醫(yī)療病例數(shù)據(jù)進(jìn)行實(shí)驗(yàn)分析.

6 實(shí)驗(yàn)結(jié)果與分析

6.1 算法比較分析

使用隨機(jī)數(shù)據(jù)集對(duì)3種算法進(jìn)行實(shí)驗(yàn)并對(duì)所需時(shí)間進(jìn)行比較，結(jié)果如圖1和圖2所示.

圖1 算法運(yùn)行時(shí)間隨數(shù)據(jù)長(zhǎng)度變化曲線Fig.1 Curve of the running time of the algorithm varies with the length of the data

圖2 算法運(yùn)行時(shí)間隨數(shù)據(jù)寬度變化曲線Fig.2 Curve of the running time of the algorithm varies with the width of the data

從圖1和圖2中可以看出，當(dāng)單個(gè)數(shù)據(jù)集的寬度較小時(shí)基于組合思想的改進(jìn)Apriori算法性能最優(yōu)；當(dāng)單個(gè)數(shù)據(jù)的寬度較大時(shí)基于位運(yùn)算和預(yù)剪枝的改進(jìn)Apriori算法性能最優(yōu)且隨著寬度的增加優(yōu)勢(shì)越來(lái)越明顯.對(duì)輸出結(jié)果進(jìn)行對(duì)比，3種算法準(zhǔn)確率都為100%.

6.2 挖掘結(jié)果

由于醫(yī)療數(shù)據(jù)的單個(gè)數(shù)據(jù)寬度為39，本文決定使用基于位運(yùn)算和預(yù)剪枝的改進(jìn)Apriori算法對(duì)醫(yī)療病例數(shù)據(jù)進(jìn)行實(shí)驗(yàn)并對(duì)結(jié)果進(jìn)行分析.表1所列結(jié)果為部分導(dǎo)致患睡眠呼吸暫停低通氣綜合征的事務(wù)集及其支持度.

表1 部分挖掘結(jié)果Table 1 Partial mining results

6.3 挖掘結(jié)果的分析

從結(jié)果可看出睡眠呼吸暫停低通氣綜合征的患病原因及易患人群主要為：

1)患者多為男性，基本都具有夜晚睡覺(jué)打鼾癥狀，多數(shù)出現(xiàn)了晨起口干、白天嗜睡等癥狀，多數(shù)存在生活作息不規(guī)律現(xiàn)象，部分有家族病史；

2)具有睡覺(jué)打鼾、白天嗜睡、影響到工作、總體呈現(xiàn)輕微過(guò)度嗜睡情況的男性青年為易患人群；

3)具有夜晚易憋醒、白天嗜睡、晨起口干、睡覺(jué)打鼾情況的男性為易患人群；

上述結(jié)果與臨床表現(xiàn)一致，說(shuō)明所給出的模型是有效的，可以為實(shí)現(xiàn)快速實(shí)時(shí)在線診斷提供相關(guān)數(shù)據(jù).

7 結(jié) 語(yǔ)

本文基于Apriori算法提出了兩種改進(jìn)算法分別針對(duì)單個(gè)數(shù)據(jù)寬度較窄和較寬的情況，在保證準(zhǔn)確率的前提下盡可能提高了算法的挖掘效率.睡眠呼吸暫停低通氣綜合征病情診斷主要依靠醫(yī)生的臨床經(jīng)驗(yàn)，現(xiàn)在我們可以提供科學(xué)的理論依據(jù).本研發(fā)現(xiàn)的睡眠呼吸暫停低通氣綜合征的患病原因及易患人群對(duì)于提高患者對(duì)該疾病的預(yù)防效率以及醫(yī)生進(jìn)行疾病診斷具有較高的實(shí)用價(jià)值并且本研究為今后其他疾病的相關(guān)研究提供了新的思路方法.接下來(lái)的工作是對(duì)改進(jìn)后算法所適用的數(shù)據(jù)庫(kù)大小及稠密程度，進(jìn)行更精確的實(shí)驗(yàn).