Apriori算法的改進及其在睡眠輔助醫療中的應用

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

(東北大學 理學院，沈陽 110819)

1 引 言

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

睡眠呼吸暫停低通氣綜合征是一種臨床常見的呼吸系統疾病[5]，智慧輔助醫療建模是一種對醫療數據進行挖掘從而實現醫療輔助的模型[6].利用現代的數據分析技術對患者的基本信息、病史、身體狀況等重要文本潛在病因特征以及與PSG檢查結果的關系進行分析，挖掘患者潛在的病因對阻塞性睡眠呼吸暫停患者的發病、病情嚴重程度、病程進展及預后、相互影響等的作用大小，從而實現自動的醫療臨床輔助，成為目前病情診斷的理想方法.

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

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

2 Apriori算法

Apriori算法使用逐層搜索的迭代方法對頻繁項集進行挖掘并對支持度計數進行統計再用于關聯規則的挖掘[7].

2.1 符號與基本概念

符號說明：I={i1，i2，…，im}是全體數據項集；D是全體事務集，|D|表示總事務數，每個事務有唯一的標識.

定義1.數據集X在D中的支持數是D中包含D的事務數.X在D中的支持度就是X在D中的支持數與D的總事務數之比.

定義2.支持度閾值S是X滿足最低顯著性需求的支持度，支持數閾值是達到S所需的支持數，滿足如下關系.

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

(1)

如果X的支持度達到S，則稱X為頻繁項集.

定義3.含有事務數最多的頻繁項集稱為最大頻繁項集.

2.2 算法步驟

Apriori算法作為一種寬度優先的算法產生的頻繁項集的子集都是頻繁的且不頻繁項集的超集都是不頻繁的[8].

產生頻繁項集具體步驟如下：

步驟1.通過遍歷一次數據庫統計一切單個事務的支持度并將達到閾值的事務組成1維頻繁項集L1；

步驟2.從最大頻繁項集集合Lk中生成長度為k+1的候選集Ck+1，通過遍歷數據庫統計所有候選項目的支持度并將達到閾值的項目組成k+1維頻繁項集Lk+1；

步驟3.轉至步驟2，直至新生成的頻繁項目集Lk+1為空集，最后得到頻繁項目集集合為.

(2)

2.3 算法缺點

Apriori算法具有遍歷數據庫次數多、內存消耗大、運行時間長的缺點[9]，本文基于這些缺點對算法進行目標為減少單次遍歷的時間以及減少遍歷次數的改進.

3 基于組合思想的改進Apriori算法

針對Apriori算法遍歷數據庫次數多的缺點利用組合思想在第2次掃描到該數據集時將其所有可能的子集找出并生成子集庫.結合相關性質找出所有的頻繁項集將遍歷次數減少到3次.

3.1 組合思想

組合是指通過每次從原集合中選出不同的項的方法生成原集合的所有子集.在尋找頻繁項集時，每一個事務集包含的頻繁項集只能是該事務集的子集.原算法需要不斷的通過k-1項頻繁項集生成k項候選集，并掃描原數據庫計算k項集的支持度計數來判斷k項候選集是否是頻繁項集.

通過組合的方式在第1次遍歷數據庫時將每一事務集的所有子集找出，最后子集在所有事務集生成的全部子集中出現的次數即為其支持度計數，其長度即為項集的長度，不需要重新生成更高項集以及計算支持度計數.

3.2 算法步驟

改進后的Apriori算法可通過將事務組合后對子集進行挖掘的方法大幅度減少遍歷原數據庫的次數.其產生頻繁項集及其支持度的具體步驟如下：

步驟1.通過遍歷一次數據庫統計一切單個事務的支持度并將達到閾值的事務組成1維頻繁項集L1；

步驟2.通過遍歷一次數據庫將每一個事務集中不屬于L1中的項目刪除以更新數據庫；

步驟3.將第1個事務集D1的所有子集找出放入候選集C中并將計數初始化為1；

步驟4.通過遍歷一次數據庫，在遍歷到第i個事務集D1時，通過組合思想將事務集D1的所有子集找出來，將一切子集對比加入到候選集C中，若子集屬于C將其支持度計數加1；若子集不屬于C加入該子集更新候選集C并將其支持度計數設為1；

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

4 基于且位運算和預剪枝的改進Apriori算法

針對Apriori算法內存消耗大和運行時間長的缺點利用矩陣存儲數據并利用且位運算進行項集運算簡化計算過程.利用預剪枝加強剪枝條件使得每一次由低項集生成高項集時減少候選集的生成并提高運行效率.

4.1 且位運算與預剪枝

位運算是指將整數對應的二進制數直接進行處理[10].本文利用且位運算(&)對數據集進行計算.

預剪枝是指在每一次由低項頻繁項集生成高項候選項集時利用頻繁項集的所有子集都是頻繁的等性質對候選項集進行篩選并刪除不符合要求的項集，以此達到減少計算量的目的.

4.2 改進方法

4.2.1 符號說明

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

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

(3)

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

4.2.2 預剪枝條件

加強預剪枝條件，在原有剪枝條件的基礎上，從篩選候選1項集開始，對預剪枝判斷失敗或支持度計數未達標準的項集進行記錄于矩陣B.在產生k選項集的預剪枝判斷過程中，對產生的項集與當前已有的矩陣B進行匹配，若B中存在某行向量與該項集匹配成功，則該項集預剪枝判斷不通過.

4.2.3 且位運算和矩陣存儲

利用計算機位運算中的且位運算進行處理，利用特殊矩陣存儲數據庫，簡化支持度計數的計算過程.

1)候選1項集的支持度計數

對給定的某個下標k特征，直接對指定列經累加可得其1項集的支持度為:

(4)

可以減少一次遍歷.

2)候選k項集的支持度計數

Apriori算法在計算候選k項集支持度計數時對候選項集中每個項至少進行n×(k-1)次判斷.本文利用計算機自有的且位運算對候選項集的支持度進行統計.

當xi&xj=xj時，有xi?xj，也即xj中的項在xi中均有出現.由此得到.

定理1.對給定的某個候選項集yj，該候選項集的支持度計數為:

(5)

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

3)預剪枝的匹配計數

根據且位運算的相關性質，可以得到.

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

4.3 算法步驟

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

步驟1.通過遍歷一次數據庫利用位運算統計數據庫中所有單個項目的支持度并將達到閾值的項目組成1維頻繁項目集L1；

步驟2.從最大頻繁項集集合Lk中生成長度為k+1的候選集Ck+1，將候選集Ck+1與記錄矩陣Bk進行比較，刪除非頻繁項集，通過遍歷數據庫統計所有候選項目的支持度并將達到閾值的項目組成k+1維頻繁項目集Lk+1同時使用沒有達到閾值的項目更新非頻繁項集記錄矩陣Bk生成Bk+1；

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

4.4 算法準確性分析

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

(6)

所以yi可被正確選擇進入頻繁項集集合.

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

(7)

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

5 實驗過程

5.1 數據樣本介紹

為研究病癥與臨床表現、生活習慣等的關系，本文使用來自沈陽市某醫院的數千條醫療記錄作為數據源，信息包括年齡、性別、一些行為表現如晨起口干，夜間憋尿等，還包括患者血壓記錄、其他疾病記錄史等.

5.2 數據預處理

5.2.1 建立病人系統數據庫

利用Excel對數據進行預處理并將文本形式醫療記錄信息轉化為數據庫表格.每一行代表一位病人的信息，每一列代表所有病人的某個具體特征信息.

5.2.2 數據清洗和離散化

數據清理主要將數據中的缺失值和異常數據進行識別和刪除處理.在缺失值的識別及刪除處理方面，由于部分項目如就診日期、病人姓名等對本文的研究無較大意義，本文對這些事務進行了刪除處理，而對于在部分數據中出現某項缺失值的整行數據進行了刪除處理.數據離散方面，本文通過查找相關醫學文獻，依據每個字段的標準值，將連續數據離散化.進一步進行數據歸約，并對離散后的數據進行了相關字符編碼.

5.3 實驗步驟

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

6 實驗結果與分析

6.1 算法比較分析

使用隨機數據集對3種算法進行實驗并對所需時間進行比較，結果如圖1和圖2所示.

圖1 算法運行時間隨數據長度變化曲線Fig.1 Curve of the running time of the algorithm varies with the length of the data

圖2 算法運行時間隨數據寬度變化曲線Fig.2 Curve of the running time of the algorithm varies with the width of the data

從圖1和圖2中可以看出，當單個數據集的寬度較小時基于組合思想的改進Apriori算法性能最優；當單個數據的寬度較大時基于位運算和預剪枝的改進Apriori算法性能最優且隨著寬度的增加優勢越來越明顯.對輸出結果進行對比，3種算法準確率都為100%.

6.2 挖掘結果

由于醫療數據的單個數據寬度為39，本文決定使用基于位運算和預剪枝的改進Apriori算法對醫療病例數據進行實驗并對結果進行分析.表1所列結果為部分導致患睡眠呼吸暫停低通氣綜合征的事務集及其支持度.

表1 部分挖掘結果Table 1 Partial mining results

6.3 挖掘結果的分析

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

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

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

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

上述結果與臨床表現一致，說明所給出的模型是有效的，可以為實現快速實時在線診斷提供相關數據.

7 結 語

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