基于劃分和壓縮數(shù)據(jù)庫的改進(jìn)Apriori算法

胡綠慧，任玉蘭，何振林

（成都中醫(yī)藥大學(xué) 醫(yī)學(xué)信息工程學(xué)院，成都610075）

隨著信息技術(shù)的發(fā)展，醫(yī)學(xué)信息的迅猛增加，而人腦的儲存和處理信息的能力又有一定的局限性，因此會對臨床問題的思考、信息的判斷、尋找解決問題的辦法和制定臨床治療方案決策造成困擾。面對跨越千年的文獻(xiàn)資料，如何快速、有效地挖掘有價值的信息，獲取最佳證據(jù)以供臨床治療方案決策所用是目前面臨的最大困難和亟待解決的問題。傳統(tǒng)的文獻(xiàn)研究方法或數(shù)理統(tǒng)計方法均無法解決古今針灸文獻(xiàn)相關(guān)性和規(guī)律性問題，而計算機領(lǐng)域發(fā)展起來的數(shù)據(jù)挖掘可以解決這個難題。

數(shù)據(jù)挖掘是通過發(fā)現(xiàn)蘊藏在海量數(shù)據(jù)中的潛在知識而提高數(shù)據(jù)價值的技術(shù)。關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘中的一個主要分支，它主要是通過分析大量數(shù)據(jù)以挖掘數(shù)據(jù)之間的依賴關(guān)系［1］。其中Apriori算法是關(guān)聯(lián)規(guī)則挖掘應(yīng)用中最常使用的一個算法，但是Apriori算法也存在一些不足，特別是面對大規(guī)模數(shù)據(jù)時，其效率較低。本文針對Apriori算法的不足，提出了一種基于劃分和壓縮數(shù)據(jù)庫方法的改進(jìn)方法，通過改進(jìn)可以將大規(guī)模數(shù)據(jù)集進(jìn)行有效的劃分和壓縮，對子數(shù)據(jù)庫進(jìn)行關(guān)聯(lián)規(guī)則挖掘，然后將結(jié)果合并。這種方法有效地改變了Apriori算法在面對大規(guī)模數(shù)據(jù)時效率較低的不足。

1 關(guān)聯(lián)規(guī)則

1.1 關(guān)聯(lián)規(guī)則描述

關(guān)聯(lián)規(guī)則（Association Rule）是指從大量數(shù)據(jù)中發(fā)現(xiàn)項集之間有價值的聯(lián)系，相關(guān)關(guān)系或因果結(jié)構(gòu)，以及項集的頻繁模式。關(guān)聯(lián)規(guī)則的目地是找出大量數(shù)據(jù)中隱藏的關(guān)聯(lián)網(wǎng)，展示屬性值頻繁地在給定數(shù)據(jù)集中一起出現(xiàn)的模式［1－3］。

關(guān)聯(lián)規(guī)則挖掘有兩個步驟：

（1）找出所有頻繁項集。根據(jù)最小支持度找出數(shù)據(jù)集D中所有不同長度的、滿足用戶給定最小支持度的頻繁項集。

（2）由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則，產(chǎn)生的規(guī)則必須滿足最小支持度和最小置信度。

通過關(guān)聯(lián)規(guī)則算法挖掘出屬性值的結(jié)合模式，結(jié)合相關(guān)的專業(yè)領(lǐng)域知識，可以更有效地挖掘出數(shù)據(jù)集中隱藏的可利用價值。常用的關(guān)聯(lián)規(guī)則挖掘算法主要有 Apriori算法，F(xiàn)-P算法［3］以及Eclat算法。

1.2 Apriori算法描述

Apriori算法是一種使用頻繁集的先驗知識從而生成關(guān)聯(lián)規(guī)則的一種算法，是最有影響的關(guān)聯(lián)規(guī)則挖掘算法，采用了逐層搜索的迭代方法尋找頻繁項集［2］。即掃描一次事務(wù)數(shù)據(jù)庫，找出頻繁1－項集的集合L1，基于L1來尋找所有可能的候選2－項集的集合L2，類似上一步，L2用于尋找L3，如此循環(huán)，直到不能找到頻繁項集。Apriori算法，在尋找頻繁項集時是由連接和裁剪這兩個步驟構(gòu)成的。Apriori算法的主要解決步驟如下：

（1）掃描事務(wù)數(shù)據(jù)庫。掃描事務(wù)數(shù)據(jù)庫D產(chǎn)生頻繁一項集L1。

（2）連接。在k（k＞1）次掃描事務(wù)數(shù)據(jù)庫時，采用遞推的連接方法求Lk，通過Lk－1與自己連接產(chǎn)生候選k項集的集合Ck。

（3）裁剪。設(shè)Ck∈Lk，即Ck是的超集。根據(jù)Apriori任何非頻繁的（k－1）項集都不可能是頻繁k項集的子集這一性質(zhì)，如果滿足Ck－1?Lk－1，則該候選項集也不是頻繁的，即Ck?Lk，從而候選k項集Ck可以從候選k項集的Ck中刪除。

（4）產(chǎn)生強關(guān)聯(lián)規(guī)則。根據(jù)所設(shè)定的最小置信度min-con遍歷整個頻繁項集，得出強關(guān)聯(lián)規(guī)則，算法結(jié)束。

1.3 Apriori算法分析

Apriori算法雖然可以實現(xiàn)在海量數(shù)據(jù)中挖掘其關(guān)聯(lián)規(guī)則，但算法在執(zhí)行速度和效率上具有一定的局限性，主要表現(xiàn)在：在生成頻繁k-項集的過程中，需對事務(wù)數(shù)據(jù)庫進(jìn)行多次掃描。候選集的大小決定了掃描事務(wù)數(shù)據(jù)庫的次數(shù)，假如候選k-項集Ck的大小為｜Ck｜，則需要掃描｜Ck｜次數(shù)據(jù)庫，這就大大增加了I/O負(fù)載，也大大降低了Apriori算法的執(zhí)行效率。

目前，很多文獻(xiàn)提出了對Apriori算法的改進(jìn)［4－8］，如基于把 Apriori算法與FP-Tree的結(jié)構(gòu)結(jié)合，提出的增量式Apriori算法。

2 改進(jìn)的Apriori算法

2.1 算法改進(jìn)的思想

基于Apriori算法在處理大數(shù)據(jù)集時的不足，結(jié)合針灸數(shù)據(jù)處理特定需求，設(shè)計了一個基于劃分?jǐn)?shù)據(jù)庫技術(shù)的改進(jìn)算法。該算法的基本思想：針灸數(shù)據(jù)表是由（0，1）表示某穴位是否出現(xiàn)在某個案例治療方案中，所以存在很大一部分治療案例方案不包含某些穴位，由此引起的數(shù)據(jù)冗余影響了數(shù)據(jù)處理的效率。首先依據(jù)穴位出現(xiàn)的頻率將穴位按照升序存儲在臨時數(shù)組A［N］中；然后按照穴位出現(xiàn)的頻率將原始事務(wù)數(shù)據(jù)庫D分為幾個互不相交的事務(wù)數(shù)據(jù)庫，使得子數(shù)據(jù)庫能夠容納在內(nèi)存中；最后根據(jù)每個子數(shù)據(jù)庫計算出的頻繁項集計算整個數(shù)據(jù)庫的頻繁項集。

2.2 算法描述

數(shù)據(jù)庫劃分是指依據(jù)各個列屬性值把事務(wù)數(shù)據(jù)庫中的所有項分成若干份，然后對每個單獨的部分生成頻繁項集。從數(shù)據(jù)庫中計算出候選頻繁項的實際支持度，確定最后的頻繁項集。算法的主要依據(jù)是把數(shù)據(jù)庫分為若干份，整個數(shù)據(jù)庫上的頻繁項集至少在數(shù)據(jù)庫的一個分段上是頻繁的；其次，每個分段上的頻繁項集的并集就是整個數(shù)據(jù)庫上潛在的頻繁項集的集合。因此，基于數(shù)據(jù)庫的劃分對Apriori算法的改進(jìn)可以描述為：

（1）計算每個穴位屬性中為1的項的個數(shù)，按升序排序于數(shù)組A［N］中（i＝0）；

（2）根據(jù)數(shù)據(jù)庫中A［i］是否為1，將數(shù)據(jù)庫D分為兩個部分Di，D；

（3）新的數(shù)據(jù)庫D中，A［i］列的屬性值都為0，刪除該列，i＋＋，返回到步驟（2）；

（4）分別對Di求頻繁項集，加到候選頻繁項集中；

（5）在原始數(shù)據(jù)庫中，計算每個候選頻繁項集的支持度，判斷是否滿足最小閾值，確定最后的頻繁項集。

算法偽代碼：

為了說明和驗證算法的正確性，表1為從原始數(shù)據(jù)庫中提取的部分?jǐn)?shù)據(jù)進(jìn)行劃分和壓縮之后形成的一個數(shù)據(jù)庫模型，通過計算配伍規(guī)律的支持度和置信度來驗證這種改進(jìn)方法的有效性。

表1 數(shù)據(jù)庫劃分模型Table 1 The database partition model

由表1可知，原始數(shù)據(jù)庫依據(jù)列屬性值劃分形成若干子數(shù)據(jù)庫，子數(shù)據(jù)庫的最后一列都為1，通過直接刪除數(shù)據(jù)冗余部分，實現(xiàn)了對子數(shù)據(jù)庫的進(jìn)一步壓縮，使得最后形成若干大小合適、數(shù)據(jù)冗余度低的子數(shù)據(jù)庫。

例如在表1中，所有與太陽穴正相關(guān)的穴位是通過前2條案例數(shù)據(jù)由關(guān)聯(lián)規(guī)則挖掘出來，而與下關(guān)穴正相關(guān)的穴位是通過前2條數(shù)據(jù)中挖掘出的配伍規(guī)律與之后的3條案例數(shù)據(jù)挖掘出來的配伍規(guī)律加權(quán)得到；配伍規(guī)律之間的加權(quán)值由案例條數(shù)所占的比例得到。

例：表1中的13條案例數(shù)據(jù)中的用穴頻率見表2，在計算頻繁2－項集時，只需要統(tǒng)計子數(shù)據(jù)庫中A與B同時出現(xiàn)的次數(shù)。

表2 劃分模型中的用穴頻次Table 2 Acupoint frequency in the database partition model

通過表1中的數(shù)據(jù)可知，案例總數(shù)D為13，地倉與太陽穴一起出現(xiàn)的頻次是2，地倉與下關(guān)一起出現(xiàn)的頻次是0，地倉與合谷一起出現(xiàn)的頻次是2，根據(jù)以下公式即可得到表3的結(jié)果。

表3 頻繁2-項集計算結(jié)果Table 3 Results of 2sets of frequent

通過劃分?jǐn)?shù)據(jù)庫計算出的結(jié)果與原始的計算方法結(jié)果相同，算法改進(jìn)后，將大數(shù)據(jù)集劃分和壓縮為若干個小的子數(shù)據(jù)庫，一方面刪除了很多冗余的數(shù)據(jù)，減少了計算開銷；另一方面，可以將數(shù)據(jù)并發(fā)處理。

3 實例分析

將以上算法應(yīng)用在臨床針灸治療貝爾面癱用穴規(guī)律［9］研究中，數(shù)據(jù)以針灸療法治療貝爾面癱1 400條醫(yī)案為例進(jìn)行數(shù)據(jù)挖掘。

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

收集到的原始病案數(shù)據(jù)存在有噪聲、有缺省、格式不一致等情況，甚至有些病案只有寥寥數(shù)語，這在一定程度上加大了數(shù)據(jù)挖掘的難度。數(shù)據(jù)挖掘中對數(shù)據(jù)的規(guī)范化、標(biāo)準(zhǔn)化、結(jié)構(gòu)化要求很高，數(shù)據(jù)的預(yù)處理將直接關(guān)系到挖掘的結(jié)果精確度［5］。數(shù)據(jù)經(jīng)過數(shù)據(jù)集成、數(shù)據(jù)規(guī)約、數(shù)據(jù)清理、數(shù)據(jù)變換等預(yù)處理之后得到表4所列的格式的數(shù)據(jù)。

表4 數(shù)據(jù)格式表Table 4 Data format chart

3.2 結(jié)果分析

通過使用關(guān)聯(lián)規(guī)則挖掘結(jié)果并結(jié)合針灸專業(yè)知識進(jìn)行分析，發(fā)現(xiàn)針灸治療面癱地倉、頰車兩穴使用頻次最高，療效最好。其他具體穴位使用頻次見表5。針灸治療面癱腧穴配伍規(guī)律中，頰車與地倉兩穴配伍使用最多，它們的支持度和置信度都達(dá)到最高。具體配伍、置信度見表6。

表5 針灸治療貝爾面癱腧穴規(guī)律分析表Table 5 Analysis of the acupuncture points regularity for curing Baer facial paralysis

對幾條關(guān)聯(lián)規(guī)則從針灸學(xué)角度來解釋：針灸治療貝爾面癱中經(jīng)絡(luò)腧穴的應(yīng)用具有明顯的規(guī)律特征，表現(xiàn)為：（1）從腧穴使用頻次分析來看，重視局部取穴，地倉、頰車、陽白、合谷、翳風(fēng)等面部穴位的應(yīng)用，體現(xiàn)了“腧穴所在，主治所在”的治療規(guī)律；（2）對經(jīng)脈的選擇中，體現(xiàn)了對病因辨證治療的原則，特別重視翳風(fēng)、合谷、風(fēng)池等穴位的應(yīng)用。通過對所挖掘出的關(guān)聯(lián)規(guī)則的分析結(jié)果，可以得出循經(jīng)取穴是針灸治療的重要原則，特定穴的運用是針灸處方的主要部分，符合針灸理論與臨床實踐，該方法有助于針灸臨床決策。

表6 針灸治療貝爾面癱腧穴配伍規(guī)律分析表Table 6 Analysis of the acupuncture acupoints compatibility regularity for curing Baer facial paralysis

4 結(jié)論

本文分析了關(guān)聯(lián)規(guī)則挖掘算法，將屬性劃分和數(shù)據(jù)庫壓縮理論引入到經(jīng)典Apriori算法的改進(jìn)工作中，很好地解決了大規(guī)模數(shù)據(jù)在處理上的效率問題，有效地解決了數(shù)據(jù)冗余。實驗驗證該方法在數(shù)據(jù)挖掘中有效提高了運行時間復(fù)雜度、空間復(fù)雜度。在解決實際問題中，取得了很好的效果。

［1］Agrawal R，Mannila H，Srikant R，etal.Fast discovery of association rules［C］//Advances in Knowledge Discovery and Data Mining.Menlo Park：AAAI/MIT Press，1996：307－328.

［2］Han J W，Pei J，Yin Y.Mining frequent patterns，without candidate generation［J］.Data Mining and Knowledge Discovery，2004（8）：53－87.

［3］Zhang P，Tong Y H，Tang S W，etal.An effective method for frivacy preserving association rule mining［J］.Journal of Software，2006，17（8）：1764－1774.

［4］Savasere A，Omiecinski E，Navathe S.An efficient algorithm for mining association rules in large databases［C］//Proceedings of the 21st VLDB Conference.Burlington： Morgan Kaufmann Publishers，1995：432－443.

［5］關(guān)心，李廣原.一種多約束關(guān)聯(lián)挖掘算法［J］.計算機應(yīng)用研究，2012，29（4）：1294－1296.Guan X，Li G Y.Efficent algorithm for mining association rules with multiple constraints［J］.Application Research of Computers，2012，29（4）：1294－1296.（In Chinese）

［6］苗苗苗，王玉英.基于矩陣壓縮的Apriori算法改進(jìn)的研究［J］.計算機工程與應(yīng)用，2013，49（1）：159－162.Miao M M，Wang Y Y.Research on improvement of Apriori algorithm based on matrix compression［J］.Computer Engineering and Applications，2014，49（1）：159－162.（In Chinese）

［7］崔旭，劉小麗.基于粗糙集的改進(jìn)Apriori算法研究［J］.計算機仿真，2013，30（1）：329－332.Cui X，Liu X L.Improved Apriori algorithm based on rough set［J］.Computer Simulation，2013，30（1）：329－332.（In Chinese）

［8］肖光磊，陸建峰，李文林，等.正相關(guān)關(guān)聯(lián)規(guī)則及其在中醫(yī)藥中的應(yīng)用［J］.計算機工程與應(yīng)用，2010，46（6）：227－230.Xiao G L，Lu J F，Li W L，etal.Positively correlated association rules and its application in traditional Chinese medicine［J］.Computer Engineering and Applications，2010，46（6）：227－230.（In Chinese）

［9］楊潔，任玉蘭，吳曦，等.基于數(shù)據(jù)挖掘技術(shù)的針灸治療貝爾面癱RCT文獻(xiàn)的用穴規(guī)律分析［J］.中華中醫(yī)藥雜志，2010，25（3）：348－351.Yang J，Ren Y L，Wu X，etal.Data mining-based analysis on rules of acupoints selection in RCT literature of acupuncture treatment of Bell palsy［J］.CJTCMP，2010，25（3）：348－351.（In Chinese）