序列模式挖掘算法在高血壓治療中的研究

張曉宇，謝紅薇，孟 亮

(太原理工大學 計算機科學與技術學院，山西 太原 030024)

0 引 言

逐步治療是針對患有慢性疾病(糖尿病、高血壓、哮喘等)的病人采用的一種治療方法。中國高血壓[1,2]基層防治指南中根據(jù)高血壓病病情的發(fā)展，對患者的治療方法提出：高血壓分為輕危高血壓、中危高血壓和高危高血壓。當初診為輕度高血壓時，采取生活方式干預和單種藥物(ACEI，CCB，低劑量的固定復方制劑等)治療的方法，當血壓不能得到有效控制時，采用多種藥物聯(lián)合治療的方法。

本文應用序列模式挖掘算法研究高血壓患者服用藥物的序列，能夠為醫(yī)生提供參考，縮短診療時間，降低醫(yī)療成本。

序列模式挖掘最早是由R.Algrawal等提出的，并提出了ApriorAll算法和多階段迭代算法GSP用于零售行業(yè)客戶購買行為的研究。SPADE算法是Zaki等提出的序列模式挖掘算法[3]。SPADE算法針對GSP算法需要多次掃描數(shù)據(jù)庫的不足，基于格理論和等價類的思想，采用垂直存儲結構，將掃描數(shù)據(jù)庫的次數(shù)減少到3次，使時間復雜度降低。

Jenna Reps等[4]指出SPADE適用于醫(yī)療數(shù)據(jù)庫，采用SPADE算法研究疾病復發(fā)的可能性以及影響疾病復發(fā)的一些因素。Aileen等[5]采用了SPADE算法挖掘2型糖尿病患者藥物治療的序列。

然而，SPADE算法存在支持度閾值難以設定的問題。因為頻繁序列挖掘的結果對支持度的依賴很大，當使用一個較小的支持度時，可能產生大量冗余的頻繁序列，而使用一個較大的支持度閾值，則可能產生較少的頻繁序列，可能會丟失一些重要的信息。針對這個問題Hu Y H等[6]提出了基于多支持度的模式挖掘算法、Amphawan K[7,8]提出了top-k頻繁模式挖掘、劉瑞陽等[9]將邏輯理論的引入模式挖掘算法優(yōu)化支持度閾值等。然而，上述方法在實際應用中是很難實現(xiàn)的。本文采用統(tǒng)計學的思想，利用支持度閾值和頻繁序列數(shù)之間的關系，并考慮電子病歷中醫(yī)療數(shù)據(jù)的特性[10]，和高血壓患者服藥數(shù)據(jù)的特點，提出了一種改進的SPADE算法，來解決支持度閾值難以設定的問題。

1 相關定義

定義1 項目集合I：I是m個不同的項目組成的集合，記為：I={i1,…,im}。

定義2 項集：項集是從I中選取l個項目的非空集合，記為：{i1,i2,…,il}， 其中項目按升序排列并且l>0。

定義3 序列：序列是項集的有序列表，序列α記為：α1→α2→…→αL，其中αi表示第i個項集(1≤i≤l)，αi也被稱為是序列α的一個元素。一個序列有L個項目，該序列被稱為L-序列。

定義4 序列數(shù)據(jù)庫：序列數(shù)據(jù)庫SDB(sequence database)，每個序列都有唯一的標示符(sid)，每一個序列的每一個項集都有暫時的項集標示符(eid)即時間戳，在一個序列中，eid是唯一的，并且如果一個序列中項集ei先于項集ej發(fā)生，那么ei的eid必須嚴格大于ej的eid。

定義5 子序列：存在兩個序列，一個序列是sa=α1→α2→…→αn， 另一個序列是sb=β1→β2→…→βm， 當且僅當存在1≤i1

定義6 支持度：請參見文獻[4]。記為：sup(α)。

定義7 頻繁序列：D是一個序列數(shù)據(jù)庫，在D中，如果一個序列模式p的支持度大于支持度閾值(min_sup),并且p的子序列也都是頻繁的，那么就稱p是頻繁的。

定義8 序列模式挖掘：請參見文獻[4]。

2 算法描述

2.1 SPADE算法思想

SPADE算法是使用“垂直”數(shù)據(jù)結構的序列數(shù)據(jù)庫，并采用了格理論的方法，將原來的搜索空間分解成小格，使得掃描數(shù)據(jù)庫的次數(shù)減少到3次。為庫中每個序列建立一個序號列表，列表中每個序列包含序列號和項目號兩個屬性，在計算序列支持度時，只需要計算序號列表中包含的不同的序列號的個數(shù)。并且將具有相同前綴的等長度序列歸并為一個等價類，新生成的序列只會在等價類內部產生。SPADE算法提高了支持度的計算效率，降低了I/O成本。

2.2 改進的SPADE算法思想

2.2.1 算法思想

首先定義一個映射關系f，頻繁序列的數(shù)目m與支持度閾值min_sup構成的映射關系為：m=f(min_sup)。 先選取一個較小的支持度閾值作為初始值，然后支持度閾值線性遞增，分別計算不同min_sup下的m值，當m第一次遇到極值點時，對應的 min_sup為最佳的支持度閾值。將得到的min_sup值作為SPADE算法的支持度閾值，執(zhí)行SPADE算法。

2.2.2 算法流程圖

改進的SPADE算法流程如圖1所示。

圖1 改進的SPADE算法流程

3 實驗處理及結果分析

3.1 數(shù)據(jù)預處理

本文采用的是一家醫(yī)療中心的電子病歷數(shù)據(jù)，從2006年到2009年總計79 746條記錄，由于其包含所有患者的記錄。數(shù)據(jù)預處理模型如圖2所示。

圖2 數(shù)據(jù)預處理模型

在病歷數(shù)據(jù)庫中選取528名高血壓患者服用藥物的數(shù)據(jù)，共913條記錄，每條記錄有4個屬性，分別是病歷號、就診時間、藥品個數(shù)和處方藥。數(shù)據(jù)詳細說明見表1。

表1 數(shù)據(jù)集說明

通過實驗得出，由于治療高血壓藥品種類豐富而且繁雜，使得序列數(shù)據(jù)比較稀疏，稀疏的數(shù)據(jù)導致了得到的挖掘結果不理想，所以本文根據(jù)高血壓防治指南將高血壓藥品歸類為14個藥品類。

藥品和藥品類別歸來說明見表2。

表2 高血壓藥品和藥品類別歸類說明

注：其中二氫吡啶類CCB是指二氫吡啶類鈣拮抗劑；ACEI是指血管緊張素轉換酶抑制劑；ARB是指血管緊張素受體拮抗劑

經過分類匯總后實驗數(shù)據(jù)集(MD)一共有4個屬性值，分別是患者的序列號，就診時間，醫(yī)生所開處方藥的個數(shù)，以及藥品所屬類別。將數(shù)據(jù)集輸入序列數(shù)據(jù)庫中，數(shù)據(jù)格式見表3。

表3 輸入數(shù)據(jù)格式說明

3.2 支持度閾值的判斷及結果

將MD作為判定支持度閾值的特定數(shù)據(jù)集，應用GSP算法，然后得到支持度閾值的判定結果，結果見表4。

表4 支持度閾值判斷結果

由表4可以看出，將min_sup=0.001作為初始值，第一次出現(xiàn)的極值點在min_sup=0.007時，min_sup=0.007時也m=37，與min_sup=0.008時m的值相等，所以最終得到最佳支持度閾值min_sup=0.007。從圖3中也可直觀的反應出min_sup=0.007時是針對這一數(shù)據(jù)集的最佳支持度閾值。

圖3 數(shù)據(jù)集MD的 min_sup與m關系

將MD隨機平均分為兩個數(shù)據(jù)集MD1，MD2；分別應用GSP算法，得到如圖4的結果，當MD數(shù)據(jù)集減小為原來的一半時，MD1表現(xiàn)為m值在min_sup=0.006時出現(xiàn)第一次極值點，而MD2表現(xiàn)為m在min_sup=0.007時出現(xiàn)第一次極值點；再將MD隨機平均分為4個數(shù)據(jù)集MD3，MD4，MD5，MD6，分別應用GSP算法，發(fā)現(xiàn)這4個數(shù)據(jù)集的m值都在min_sup=0.07時出現(xiàn)第一次極值點，如圖5所示。由此可以得出對于特定數(shù)據(jù)集MD，如果只改變數(shù)據(jù)集的大小，頻繁序列數(shù)m都表現(xiàn)在支持度閾值min_sup=0.007時出現(xiàn)第一次極值點，所以再次驗證數(shù)據(jù)集MD的最佳支持度閾值為0.007。

圖4 數(shù)據(jù)集MD1和MD2的min_sup與m關系

圖5 數(shù)據(jù)集MD3、MD4、MD5和MD6的min_sup與m關系

從圖6中可以看出平均支持度在0.007時第一次到達極值點，min_sup=0.007時，平均支持度=0.018，min_sup=0.008時，平均支持度=0.018，所以在驗證了選取min_sup=0.007是合適的。同時，平均置信度也在0.007時到達第一次極值點，min_sup=0.07時，average confidence=0.1712，min_sup=0.08時，average confidence=0.1712，再次驗證了min_sup=0.007是最佳的。

圖6 最佳支持度閾值驗證

3.3 挖掘頻繁序列

將min_sup設置為0.007作為參數(shù)，繼續(xù)執(zhí)行序列模式挖掘算法，得到頻繁序列集F，F(xiàn)集中有37條頻繁序列，在表5中列舉了一些頻繁序列及序列的支持度。

3.4 序列規(guī)則的生成

將頻繁序列生成序列規(guī)則這里采用Zhang X Y等[11]提出的將序列的最后一項作為規(guī)則的結論，序列中除最后一項的所有項作為規(guī)則的條件生成序列規(guī)則的方法。這里針對特殊的1-頻繁序列，將空集作為條件，將1-頻繁序列作為結論來生成規(guī)則。例如1-頻繁序列(<{噻嗪類利尿劑}>)，它生成的規(guī)則為(<{}>-> <{噻嗪類利尿劑}>)表示初次診斷為高血壓的患者，醫(yī)生根據(jù)其各項指標給患者的處方可能是噻嗪類利尿劑類的藥物。

表5 頻繁序列

本文在生成序列規(guī)則時選取最小置信度為0.01，將頻繁序列生成序列規(guī)則共37個，表6中列舉了部分序列規(guī)則。其中<{β受體阻滯劑}>=><{ACEI，噻嗪類利尿劑，β受體阻滯劑}>，表示患者之前用藥是β受體阻滯劑類，由于病情惡化，之前的藥物不足以控制血壓時，醫(yī)生可能開出的處方藥是ACEI類，噻嗪類利尿劑類和β受體阻滯劑類，3種藥物聯(lián)合治療。

表6 部分序列規(guī)則說明

3.5 規(guī)則可視化

下面將挖掘得到的規(guī)則實現(xiàn)可視化處理，如圖7為序列規(guī)則圖。

圖7 序列規(guī)則

4 結束語

本文提出了一種改進的SPADE算法，解決了SPADE算法支持度閾值難以設定的問題。根據(jù)支持度閾值和頻繁序列數(shù)目的關系，選擇變化曲線上第一個極值點對應的支持度閾值為最佳支持度閾值。

將改進的SPADE算法應用于研究高血壓患者服藥歷史的序列數(shù)據(jù)，挖掘頻繁序列模式，然后將頻繁序列模式轉換為序列規(guī)則可以為患者逐步藥物治療提供指導。

將得到的高血壓患者服藥的序列規(guī)則結合患者的各項身體指標用于推薦，是下一步工作重點。

[1]World Health Organization.A global brief on hypertension[M].Geneva.WHO,2013:7-15.

[2]HUANG Fei,XIE Hongwei,HAO Xiaoyan.An intelligent classification system used for identifying cardiovascular risk level of hypertensive[J].Science Technology and Engineering,2014,14(7):204-211(in Chinese).[黃飛,謝紅薇,郝曉燕.高血壓患者心血管風險水平智能分層系統(tǒng)[J].科學技術與工程,2014,14(7):204-211.]

[3]Kumar K M V M,Srinivas P V S,Rao C R.Sequential pattern mining with multiple minimum supports by MS-SPADE[J].International Journal of Database Management Systems,2012,9(5):285-292.

[4]Reps J,Garibaldi J M,Aickelin U,et al.Discovering sequential patterns in a UK general practice database[C]//Procee-dings of IEEE-EMBS International Conference on Biomedical and Health Informatics.Piscataway:IEEE,2012:960-963.

[5]Wright A P,Wright A T,Mccoy A B.The use of sequential pattern mining to predict next prescribed medications[J].

Journal of Biomedical Informatics,2015,53(C):73-80.

[6]Hu Y H,Wu F,Liao Y J.An efficient tree-based algorithm for mining sequential patterns with multiple minimum supports[J].Journal of Systems & Software,2013,86(5):1224-1238.

[7]Amphawan K,Lenca P,Surarerks A.Mining top-k,regular-frequent itemsets using database partitioning and support estimation[J].Expert Systems with Applications,2012,39(2):1924-1936.

[8]Amphawan K,Lenca P.Mining top-k frequent-regular closed patterns[J].Expert Systems with Applications,2015,42(21):7882-7894.

[9]LIU Duanyang,FENG Jian,LI Xiaofen.Logic-based frequent sequential pattern mining algorithm[J].Computer Science,2015,42(5):260-264(in Chinese).[劉端陽,馮建,李曉粉.一種基于邏輯的頻繁序列模式挖掘算法[J].計算機科學,2015,42(5):260-264.]

[10]Huang Z,Dong W,Bath P.On mining latent treatment patterns from electronic medical records[J].Data Mining and Knowledge Discovery,2015,29(4):914-949.

[11]Zhang X Y.Research on sequential pattern mining algorithm in recommendation of hypertensive drugs[D].Taiyuan:Taiyuan University of Technology,2017.