胡綠慧，任玉蘭，何振林

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

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

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

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

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

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

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

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

1.2 Apriori算法描述

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

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

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

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

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

1.3 Apriori算法分析

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

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

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

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

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

2.2 算法描述

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

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

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

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

（4）分別對(duì)Di求頻繁項(xiàng)集，加到候選頻繁項(xiàng)集中；

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

算法偽代碼：

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

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

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

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

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

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

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

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

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

3 實(shí)例分析

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

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

收集到的原始病案數(shù)據(jù)存在有噪聲、有缺省、格式不一致等情況，甚至有些病案只有寥寥數(shù)語(yǔ)，這在一定程度上加大了數(shù)據(jù)挖掘的難度。數(shù)據(jù)挖掘中對(duì)數(shù)據(jù)的規(guī)范化、標(biāo)準(zhǔn)化、結(jié)構(gòu)化要求很高，數(shù)據(jù)的預(yù)處理將直接關(guān)系到挖掘的結(jié)果精確度［5］。數(shù)據(jù)經(jīng)過(guò)數(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ò)使用關(guān)聯(lián)規(guī)則挖掘結(jié)果并結(jié)合針灸專業(yè)知識(shí)進(jìn)行分析，發(fā)現(xiàn)針灸治療面癱地倉(cāng)、頰車兩穴使用頻次最高，療效最好。其他具體穴位使用頻次見(jiàn)表5。針灸治療面癱腧穴配伍規(guī)律中，頰車與地倉(cāng)兩穴配伍使用最多，它們的支持度和置信度都達(dá)到最高。具體配伍、置信度見(jiàn)表6。

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

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

表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ù)庫(kù)壓縮理論引入到經(jīng)典Apriori算法的改進(jìn)工作中，很好地解決了大規(guī)模數(shù)據(jù)在處理上的效率問(wèn)題，有效地解決了數(shù)據(jù)冗余。實(shí)驗(yàn)驗(yàn)證該方法在數(shù)據(jù)挖掘中有效提高了運(yùn)行時(shí)間復(fù)雜度、空間復(fù)雜度。在解決實(shí)際問(wèn)題中，取得了很好的效果。

［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］.計(jì)算機(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］.計(jì)算機(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］.計(jì)算機(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］.計(jì)算機(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）