一種基于帶權(quán)無向圖的中醫(yī)方劑頻繁項(xiàng)集挖掘算法

譚 龍 秦琦冰

(黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 黑龍江 哈爾濱 150080)

一種基于帶權(quán)無向圖的中醫(yī)方劑頻繁項(xiàng)集挖掘算法

譚 龍 秦琦冰

(黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 黑龍江 哈爾濱 150080)

根據(jù)中醫(yī)方劑數(shù)據(jù)的特點(diǎn)，將頻繁項(xiàng)集發(fā)現(xiàn)算法應(yīng)用到中醫(yī)方劑的研究中，挖掘治療消渴病胃火熾盛癥型的方劑中不同藥對之間的關(guān)聯(lián)規(guī)則以及核心藥物組合，提出一種基于帶權(quán)的無向頻繁項(xiàng)集圖的挖掘算法。該算法可以快速挖掘頻繁k-items(k≥3)，并隨之快速回溯頻繁項(xiàng)集所對應(yīng)的方劑，從而完成了中醫(yī)方劑數(shù)據(jù)特點(diǎn)的快速數(shù)據(jù)挖掘。通過實(shí)驗(yàn)表明，該算法避免產(chǎn)生大量候選項(xiàng)集，提高了中醫(yī)方劑數(shù)據(jù)挖掘效率，對完成中醫(yī)消渴病方劑信息的用藥規(guī)律分析具有重要意義。

消渴病 頻繁項(xiàng)集 無向圖 中醫(yī)方劑 數(shù)據(jù)挖掘

0 引 言

數(shù)據(jù)挖掘是數(shù)據(jù)庫知識發(fā)現(xiàn)領(lǐng)域內(nèi)非常熱點(diǎn)的研究方向，主要目的是從大量的數(shù)據(jù)庫中檢索出用戶感興趣的信息[1]。在數(shù)據(jù)挖掘中，關(guān)聯(lián)規(guī)則的挖掘是其核心任務(wù)之一，其根本意義在于從大量數(shù)據(jù)中挖掘出項(xiàng)集之間的相互關(guān)系。關(guān)聯(lián)規(guī)則分析方面代表性案例就是“購物籃分析”，該案例是通過挖掘顧客購買商品的交易數(shù)據(jù)，來發(fā)現(xiàn)不同商品在交易過程中隱藏的關(guān)系，從而獲得銷售的增益[2]。大量研究人員已經(jīng)在挖掘頻繁項(xiàng)集的算法中作了許多工作，Agrawal等人提出的Apriori的算法是一種最經(jīng)典的挖掘頻繁項(xiàng)集的算法，在此基礎(chǔ)上，也提出了許多基于Apriori的改進(jìn)算法，如HEA[3]、MTR-FMA[4]、Modified Apriori[5]以及Improved Aprori[6]等算法，Han等于2000年提出的FP-Growth算法也在頻繁項(xiàng)集挖掘中做出了突出貢獻(xiàn)。

同時，針對基于圖存儲的頻繁項(xiàng)集挖掘方法的研究也引起了很多學(xué)者的關(guān)注，Yen等人第一次提出了基于有向圖存儲的頻繁項(xiàng)集挖掘算法，文獻(xiàn)[7]又對上述算法進(jìn)行了改進(jìn)。在此基礎(chǔ)上，Kumar等提出了一種FIG(Frequent Item Graph)的算法[8]；Tiwari等在FP-Growth的基礎(chǔ)上進(jìn)行改進(jìn)，提出了FP-Growth-Graph來進(jìn)行頻繁項(xiàng)集挖掘[9]。

上述頻繁項(xiàng)集挖掘的算法中，大致可以分為兩個關(guān)鍵思路：(1) 產(chǎn)生候選頻繁項(xiàng)集以及進(jìn)行剪枝。(2) 不產(chǎn)生候選頻繁項(xiàng)集的方法[10]。在頻繁項(xiàng)集挖掘的過程中，方法(1)可能會產(chǎn)生大量的候選項(xiàng)集，增加算法的時間和空間復(fù)雜度，而方法(2)避免了候選項(xiàng)集的產(chǎn)生，但是往往需要大量的額外開銷，挖掘效率有待于進(jìn)一步提高。本文所提出的算法主要遵循方法(2)中思路進(jìn)行。

本研究團(tuán)隊(duì)一直從事研究中醫(yī)方劑中治療消渴病方劑的數(shù)據(jù)挖掘工作。消渴病是以多飲、多食、多尿、身體消瘦，或尿濁、尿中有甜味為主要表現(xiàn)的一種臨床常見病、多發(fā)病，嚴(yán)重危害著人類的健康[11]，中醫(yī)對于消渴病的預(yù)防和治療有著豐富而且獨(dú)特的經(jīng)驗(yàn)[12]，因此，對《中醫(yī)方劑大辭典》中收錄的治療消渴病胃火熾盛癥型的方劑研究也尤為重要。在研究中發(fā)現(xiàn)，治療該癥型的方劑中往往存在大量的頻繁的k-items(k≥3)，而相比于頻繁1-items、頻繁2-items而言，頻繁k-items(k≥3)的產(chǎn)生對于治療消渴病胃火熾盛癥型也更具有重要的臨床參考價值。

同時，在對方劑數(shù)據(jù)庫的頻繁項(xiàng)集挖掘過程中，傳統(tǒng)算法在找到頻繁項(xiàng)集結(jié)果后，卻不能有效發(fā)現(xiàn)該頻繁項(xiàng)集所對應(yīng)的方劑名稱，而方劑名稱和頻繁項(xiàng)集的對應(yīng)關(guān)系，對方劑規(guī)律分析具有重要意義。因此，本文提出了一種基于帶權(quán)的無向頻繁項(xiàng)集圖WUFIG(WeightedUndirectedFrequentItemsGraph)挖掘算法來挖掘頻繁項(xiàng)集。該算法不僅可以解決上述問題，還大大減少了對原始數(shù)據(jù)庫的掃描次數(shù)，避免產(chǎn)生大量的候選項(xiàng)集，能夠有效的挖掘出頻繁k-items(k≥3)，提高了對于中醫(yī)方劑數(shù)據(jù)挖掘效率。

1 系統(tǒng)模型

本文系統(tǒng)模型為，存在項(xiàng)集I={I1,I2,…,Im}，事務(wù)數(shù)據(jù)庫D={〈TID,T〉|T?I}，TID為代表每一條事務(wù)的標(biāo)識符；T為項(xiàng)的集合。事務(wù)數(shù)據(jù)庫D，將進(jìn)一步產(chǎn)生帶權(quán)的無向頻繁項(xiàng)集圖(如圖1所示)，無向頻繁項(xiàng)集圖的節(jié)點(diǎn)為項(xiàng)集I中的項(xiàng)組成，節(jié)點(diǎn)項(xiàng)之間如果是頻繁項(xiàng)集，則有一條邊，邊的權(quán)值用邊的兩個節(jié)點(diǎn)項(xiàng)之間的權(quán)重表示。

圖1 帶權(quán)無向頻繁項(xiàng)集圖

定義1 對于項(xiàng)X，包含所有的X的TID的集合稱之為項(xiàng)X的事務(wù)集合，簡稱Tidset，用Tidset(X)表示。

假設(shè)TID的個數(shù)為n，則Tidset(X)為n位二進(jìn)制位組成的元組，該元組可存儲在整型Long數(shù)據(jù)類型(4個字節(jié))中。通常，《中醫(yī)方劑大辭典》中收錄的治療常見癥型的方劑約為300首左右，因此，最多需要申請10個Long類型空間存儲事務(wù)數(shù)據(jù)庫中的n位二進(jìn)制元組，滿足算法的存儲要求。例如，在表1中，n=9，需申請2個Long類型存儲空間(16位)，按照從低位到高位的按位存儲，項(xiàng)I1存在的TID為1，4，7，8，9，則：

Tidset(I1)=<(0,0,0,0,0,0,0,1),(1,1,0,0,1,0,0,1)>

為描述方便，針對表1所示，n=9情況，本文將Tidset(I1)表示為：

Tidset(I1) = <1,0,0,1,0,0,1,1,1>

表1 事務(wù)數(shù)據(jù)庫表

定義2 兩個項(xiàng)X和Y之間的Tidset可以進(jìn)行按位與(&)操作，記為Tidset(X)&Tidset(Y)，其結(jié)果與元組一一對應(yīng)，我們稱該元組為項(xiàng)X與項(xiàng)Y之間的權(quán)重，用weight(X,Y)表示。

例如，由定義1可知表1中：

Tidset(I1) = <1,0,0,1,0,0,1,1,1>

Tidset(I2) = <1,1,1,1,0,1,0,1,1>

則：

Tidset(I1)&Tidset(I2)) = <1,0,0,1,0,0,0,1,1>

在帶權(quán)的無向頻繁項(xiàng)集圖中，設(shè)頻繁1-items為點(diǎn)集V，E為邊集，E(Vx,Vy)表示為點(diǎn)Vx和Vy的邊，minsup為最小支持度閾值，count(Tidset(Vx)&Tidset(Vy))表示Vx和Vy同時出現(xiàn)的次數(shù)。由上述定義1和定義2，可得邊權(quán)重weight(Vj,Vk)的計(jì)算方法為：

?Vi∈L1(1≤i≤m)

?count(Tidset(Vj)&Tidset(Vk))≥minsup則：

E=E∪E(Vj,Vk)

weight(Vj,Vk)=Tidset(Vj)&Tidset(Vk)

在基于帶權(quán)的無向頻繁項(xiàng)集圖(WUFIG)中，對于任意兩個頻繁1-items， 如果count(Tidset(X)&Tidset(Y))不小于最小支持閾值，那么X與Y之間存在邊E(X,Y)，該邊加入到E中，同時weight(E(X,Y))為Tidset(X)&Tidset(Y)的結(jié)果。

在基于帶權(quán)的無向頻繁項(xiàng)集圖(WUFIG)中，對于某個點(diǎn)集合V′中任意兩點(diǎn)Vi和Vk，如果都存在一條邊E(Vi,Vk)E，則V′中所有的點(diǎn)構(gòu)成一條頻繁項(xiàng)集環(huán)，即為頻繁項(xiàng)集。因此，?Vi∈L1(1≤i≤m)，?V′=,如果對于?Vi∈V′，?Vj∈V′，使得E(Vi,Vj)∈E成立，則存在一條頻繁k-items環(huán)，該環(huán)路經(jīng)過的頂點(diǎn)即為頻繁k-items。

2 基于帶權(quán)的無向頻繁項(xiàng)集圖挖掘算法

本文中提出的算法是基于帶權(quán)的無向頻繁項(xiàng)集圖基礎(chǔ)上搜索頻繁k-items環(huán)，算法命名為WUFIG(WeightedUndirectedFrequentItemsGraph)。

圖4中，V1、V3、V5分別表示閥1、3、5收到脈沖觸發(fā)信號，發(fā)生不對稱故障后，由于a相幅值降低，ab換相線電壓過零點(diǎn)超前于對稱故障時的過零點(diǎn)，此時導(dǎo)致實(shí)際的觸發(fā)角增大，在換相線電壓變?yōu)檎驎r換相結(jié)束，因此導(dǎo)致?lián)Q相失敗。

2.1 算法原理

本算法使用帶權(quán)無向圖的方式進(jìn)行存儲，圖中頂點(diǎn)集合即為頻繁1-items，頂點(diǎn)之間邊的權(quán)值即為Tidset(Vi) &Tidset(Vj)，在基于帶權(quán)的無向頻繁項(xiàng)集圖(WUFIG)中，如果存在頻繁k-items環(huán)，則環(huán)上面的頂點(diǎn)即為頻繁k-items。頻繁k-items環(huán)路的每條邊的權(quán)值，進(jìn)行與(&)操作，其結(jié)果即為頻繁k-items所在的TID。該TID在具體中醫(yī)方劑數(shù)據(jù)處理中，即為頻繁藥物組合所對應(yīng)的方劑名稱。

無向頻繁項(xiàng)集圖的生成算法見WUFIG_GEN算法，在此無向頻繁項(xiàng)集圖基礎(chǔ)上，搜索頻繁k-items環(huán)的操作見Mining_Frequent_K_Items算法，該算法調(diào)用Searchfrequentk-itmesloop來完成對頻繁k-items環(huán)的搜索。

WUFIG_GEN算法描述如下：

Input：Transactional Database D, minsup

Output: WUFIG

procedure WUFIG_GEN (D, minsup)

1) For each Vj∈L1

2) For each Vi∈L1(i≠j)

3) If (vj∩vi)≠? and count(Tidset(Vj)&Tidset(Vi)) ≥minsup;

4) Add E(Vi,Vi)to Edge set E;

5) Weight(Vi, Vj) = Tidset(Vi)& Tidset(Vj);

6) End if;

7) End for;

8) End for;

End procedure;

Mining_Frequent_K_Items算法描述如下：

Input：WUFIG

Output: frequent k-items,TID

//(k≥3)

Procedure Mining_Frequent_K_Items

//(k≥3)

1) While V≠? do

2) For each Vi, Vj(i≠j) of V

3) If E(Vi, Vj)∈E then

//Vi, Vj之間有邊相連

4) L = Vi∪Vj,V′ = V-{ Vi, Vj}

5) Search frequent k-itmes loop(L,V′);

6) End if;

7) End for;

8) End while;

End procedure;

procedure Search frequent k-itmes loop(L,V′)

1) While V′≠? do

2) For unvisited Vkof V′

3) If E(Vk, ?Vj∈V′)∈E then;

4) L=L∪Vk, V′ = V′-{ Vk};

5) Output L and weight_&;

//輸出頻繁k-items和對應(yīng)的TID

6) End if;

7) End for;

8) End while;

End procedure;

根據(jù)WUFIG_GEN算法，在最小支持度minsup為2的基礎(chǔ)上，首先對事務(wù)數(shù)據(jù)庫D中頻繁1-items的計(jì)算Tidset，同時計(jì)算任意兩個頻繁1-items的Tidset的交集。

例如，從表1得到：

Tidset(I1) = <1,0,0,1,1,0,1,1,1>

Tidset(I2) = <1,1,1,1,0,1,0,1,1 >

count(Tidset(I1)&Tidset(I2))=count(<1,0,0,1,0,0,0,1,1>)由于count(Tidset(I1)&Tidset(I2))=4>minsup，則I1，I2之間存在一條邊E(V1,V2)。 因此weight(I1,I2) = <1,0,0,1,0,0,0,1,1>，Tidset(I4) = <0,1,0,1,0,0,0,0,0>，count(Tidset(I1)&Tidset(I4) ) =count(<0,1,0,0,0,0,0,0,0>)。由于count(<0,1,0,0,0,0,0,0,0>)=1

根據(jù)Mining_Frequent_K_Items算法：對于WUFIG(V,E,W)中?E(Vi,Vj)∈E，例如：圖1中點(diǎn)I1和點(diǎn)I2，從V′=V-{I1,I2}={I3,I4,I5}中選取點(diǎn)I3，則E(I3,I1)∈E，E(I2,I1)∈E，則點(diǎn)I1、點(diǎn)I2和點(diǎn)I3之間存在一條頻繁3-items環(huán)，則I1I2I3為頻繁3-items，weight(I1,I2)&weight(I1,I3)&weight(I2,I3) = <0,0,0,0,0,0,0,1,1>，即I1I2I3出現(xiàn)的TID為8，9，同理可以由圖1可以生成頻繁3-itemsI1I2I5，I1I2I5出現(xiàn)的TID為1，8。

2.2 算法復(fù)雜性分析

本文提出的基于帶權(quán)的無向頻繁項(xiàng)集圖(WUFIG)的頻繁項(xiàng)集挖掘算法，在空間上的耗費(fèi)主要在于存儲WUFIG中的N個頂點(diǎn)、K條邊以及邊的權(quán)重，而存儲WUFIG的復(fù)雜度主要取決于事務(wù)數(shù)據(jù)庫的長度。隨著中醫(yī)方劑數(shù)據(jù)庫長度的增大，WUFIG的空間復(fù)雜度也會相應(yīng)的增加，因此，通常的方法是在原始中醫(yī)方劑數(shù)據(jù)的基礎(chǔ)上采用聚類方法，將治療同一癥型的方劑分簇，然后在同一簇內(nèi)采用該算法進(jìn)行頻繁項(xiàng)集的挖掘，這樣就可以有效地降低其空間復(fù)雜度。

該算法的時間代價主要在于掃描事務(wù)數(shù)據(jù)庫以及搜索頻繁k-items環(huán)的過程。掃描事務(wù)數(shù)據(jù)庫所需要的時間取決于事務(wù)數(shù)據(jù)庫的長度，因此這一過程的平均時間復(fù)雜度為O(n)；搜索頻繁項(xiàng)集環(huán)所需的時間取決于WUFIG中點(diǎn)的個數(shù)，V′中點(diǎn)的個數(shù)以及頻繁項(xiàng)集的長度，因此這一過程的平均時間復(fù)雜度為O(N×K×L)，其中N為V中點(diǎn)的個數(shù)，K為V′中點(diǎn)的個數(shù)，L為所求頻繁項(xiàng)集的長度。因此總的時間復(fù)雜度為O(n)+O(N×K×L)。

3 實(shí) 驗(yàn)

本文的實(shí)驗(yàn)算法使用VC++6.0環(huán)境來實(shí)現(xiàn)。實(shí)驗(yàn)數(shù)據(jù)是從《中醫(yī)方劑大辭典》中收錄的治療消渴病胃火熾盛方劑中篩選出來的382首方劑，包含218味中藥藥材。

本文中針對于數(shù)據(jù)的前期準(zhǔn)備處理主要是針對藥物組成的規(guī)范，該規(guī)范包括：藥材的重名和異名處理；同名異方的處理；藥材的計(jì)量單位的統(tǒng)一標(biāo)準(zhǔn)。在此規(guī)范數(shù)據(jù)基礎(chǔ)上，構(gòu)建方劑數(shù)據(jù)庫。通過對《中醫(yī)方劑大辭典》中收錄的方劑進(jìn)行分析，初步按照編號、方劑名、組成、別名、性、味、歸經(jīng)、功效等8個屬性進(jìn)行描述，完成對原始數(shù)據(jù)庫的構(gòu)建。從而，利用基于帶權(quán)的無向頻繁項(xiàng)集圖(WUFIG)的頻繁項(xiàng)集挖掘算法對數(shù)據(jù)源存儲的方劑進(jìn)行分析研究。

3.1 實(shí)驗(yàn)結(jié)果

根據(jù)本次治療胃火熾盛方劑數(shù)量和用到的中藥個數(shù)，結(jié)合經(jīng)驗(yàn)判斷以及不同參數(shù)提取數(shù)據(jù)的預(yù)讀，選擇組方中3味藥物核心組合支持度≥20，提取出96個組合，根據(jù)提出結(jié)果結(jié)合經(jīng)驗(yàn)判斷，篩選出部分有價值的頻繁3-items以及所對應(yīng)的方劑名見表2所示。由實(shí)驗(yàn)結(jié)果中選擇4味藥物核心組合支持度≥15，提取出67個組合，根據(jù)提出結(jié)果結(jié)合經(jīng)驗(yàn)判斷，篩選出部分有價值的頻繁4-items以及對應(yīng)的方劑名見表3所示。

表2 治療胃火熾盛組方中3個藥物核心組合

表3 治療胃火熾盛組方中4個藥物核心組合

根據(jù)對于消渴病胃火熾盛癥型的經(jīng)驗(yàn)，藥物關(guān)聯(lián)規(guī)則結(jié)果中選擇支持度≥15，置信度≥0.6，去掉相互包含的規(guī)則后，同時針對胃火熾盛方劑對得到的結(jié)果進(jìn)行關(guān)聯(lián)規(guī)則分析后得到20條有價值的規(guī)則，見表4所示。

表4 胃火熾盛方劑中部分藥物關(guān)聯(lián)規(guī)則

《中醫(yī)方劑大辭典》中收載的治療胃火熾盛型消渴病的方劑，分析得到治療胃火熾盛型消渴病的方劑中藥物的使用頻次，選取適合的支持度，提取出治療胃火熾盛型消渴病3 味藥物的核心組合96組、4 味藥物的核心組合67 組，并且進(jìn)一步揭示了胃火熾盛型消渴病組方中藥物的關(guān)聯(lián)規(guī)則，可以得出以下結(jié)論：

(1) 從表2、表3可知，治療胃火熾盛型消渴病方劑中藥物頻次最高的四味藥為黃連、麥冬、天花粉、知母，為醫(yī)家基本用藥組合，可作為臨床組方用藥時的重要參考與借鑒。

(2) 通過核心藥對所在的方劑名，可以得到治療胃火熾盛型消渴病的方劑治療時以清胃火為主，同時兼補(bǔ)心、肺、胃、腎等相關(guān)臟腑之陰。

(3) 通過以上數(shù)據(jù)中的用藥頻次與藥物關(guān)聯(lián)規(guī)則可以看出，黃連、麥冬、天花粉、知母四味藥物與石膏、黃芩、黃柏、大黃等藥物的配伍運(yùn)用亦為治療胃火熾盛型消渴病的常見藥物組合。

3.2 實(shí)驗(yàn)對比分析

本文主要針對FP-Growth、FIG、FP-Graph算法，選擇了minsupthreshold為0.3%、0.25%、0.2%、0.15%、0.1%進(jìn)行對比實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)通過采用《中醫(yī)方劑大辭典》中收錄的治療消渴病胃火熾盛方劑作為基礎(chǔ)數(shù)據(jù)，采用常用藥材隨機(jī)分布的方式，構(gòu)建了10 000條實(shí)驗(yàn)數(shù)據(jù)，進(jìn)行算法性能對比分析。實(shí)驗(yàn)結(jié)果如圖2所示。從圖中可以看出，隨著最小支持度閾值的降低，運(yùn)行時間都在增加，但是基于帶權(quán)的無向頻繁項(xiàng)集圖(WUFIG)的頻繁項(xiàng)集挖掘算法的時間增加率要遠(yuǎn)低于其他算法。從實(shí)驗(yàn)結(jié)果可以得知：基于帶權(quán)的無向頻繁項(xiàng)集圖(WUFIG)的頻繁項(xiàng)集挖掘算法的復(fù)雜度要優(yōu)于其他算法。

圖2 基于不同支持度算法對比分析圖

假設(shè)minsupthreshold為0.25%，實(shí)驗(yàn)方劑數(shù)據(jù)量從2 000增加到10 000，進(jìn)行算法性能的對比實(shí)驗(yàn)。隨著實(shí)驗(yàn)方劑數(shù)據(jù)量的增加，算法產(chǎn)生的中間候選項(xiàng)集會不斷增大，時間代價也會越來越大。由圖3可知，基于帶權(quán)的無向頻繁項(xiàng)集圖(WUFIG)的頻繁項(xiàng)集挖掘算法性能方面優(yōu)于其他算法。

圖3 基于不同事務(wù)數(shù)量算法對比分析圖

4 結(jié) 語

在對《中醫(yī)方劑大辭典》中收載的治療胃火熾盛型消渴病方劑進(jìn)行研究分析時，針對研究分析數(shù)據(jù)的特點(diǎn)，提出了一種基于帶權(quán)的無向頻繁項(xiàng)集圖(WUFIG)的頻繁項(xiàng)集挖掘算法。該算法能夠有效快速地產(chǎn)生頻繁k-items(k≥3)，并隨之快速回溯頻繁項(xiàng)集所對應(yīng)的方劑，對于分析該癥型中醫(yī)用藥規(guī)律的研究有著重要意義。由于該算法只需掃描一次原始數(shù)據(jù)庫，而且在頻繁項(xiàng)集挖掘過程中，避免產(chǎn)生大量候選項(xiàng)集，降低了時間復(fù)雜度，大大提高了算法的效率。同時，隨著事務(wù)數(shù)據(jù)庫的增大，帶權(quán)的無向頻繁項(xiàng)集圖邊的權(quán)重元組的存儲空間會增加，接下來，我們將針對如何有效地壓縮其存儲空間作進(jìn)一步研究。

本文算法通過對消渴病方劑數(shù)據(jù)分析所得到的核心藥物組合以及方劑名稱，在一定程度上反映消渴病胃火熾盛型的用藥規(guī)律，可作為在臨床針對消渴病胃火熾盛型的組方用藥時的重要參考與借鑒。在診療疾病的過程中對于臨床醫(yī)生的判讀與分析，提供了有效的保證，具有重要的臨床應(yīng)用價值。

[1] Solanki S K,Patel J T.A survey on association rule mining[C]//Advanced Computing & Communication Technologies (ACCT),2015 Fifth International Conference on.IEEE,2015:212-216.

[2] Girotra M,Nagpal K,Minocha S,et al.Comparative survey on association rule mining algorithms[J].International Journal of Computer Applications,2013,84(10):18-22.

[3] Li Z C,He P L,Lei M.A high efficient AprioriTid algorithm for mining association rule[C]//Machine Learning and Cybernetics,2005 International Conference on.IEEE,2005:1812-1815.

[4] Thevar R E,Krishnamoorthy R.A new approach of modified transaction reduction algorithm for mining frequent itemset[C]//Computer and Information Technology,2008 11th International Conference on.IEEE,2008:1-6.

[5] Abaya S A.Association rule mining based on Apriori algorithm in minimizing candidate generation[J].International Journal of Scientific & Engineering Research,2012,3(7):1-4.

[6] Sunil K S,Shyam K S,Akshay K C,et al.Improved Aprori algorithm based on bottom up approach using probability and matrix[J].International Journal of Computer Science Issues,2012,9(2):242-246.

[7] Yen S J,Chen A L P.A graph-based approach for discovering various types of association rules[J].IEEE Transactions on Knowledge and Data Engineering,2001,13(5):839-845.

[8] Kumar A V S,Wahidabanu R S D.A frequent item graph approach for discovering frequent itemsets[C]//Advanced Computer Theory and Engineering,2008 International Conference on.IEEE,2008:952-956.

[9] Tiwari V,Tiwari V,Gupta S,et al.Association rule mining:a graph based approach for mining frequent itemsets[C]//Networking and Information Technology (ICNIT),2010 International Conference on.IEEE,2010:309-313.

[10] Mohamed M H,Darwieesh M M.Efficient mining frequent itemsets algorithms[J].International Journal of Machine Learning and Cybernetics,2014,5(6):823-833.

[11] 王芳芳.消渴病古代文獻(xiàn)研究及近30年用柴胡類方治療資料的分析[D].廣州:廣州中醫(yī)藥大學(xué),2011.

[12] 榮開明.復(fù)興中醫(yī)藥學(xué)的幾點(diǎn)思考[J].湖北中醫(yī)藥大學(xué)學(xué)報,2015,17(2):59-62.

A TRADITIONAL CHINESE MEDICINE PRESCRIPTION FREQUENT ITEM SETS MINING ALGORITHM BASED ON WEIGHTED UNDIRECTED GRAPH

Tan Long Qin Qibing

(CollegeofComputerScienceandTechnology,HeilongjiangUniversity,Harbin150080,Heilongjiang,China)

According to the characteristics of traditional Chinese medicine prescription data, the frequent item sets discovery algorithm is used to the study of TCM prescriptions, and mine the association rule and core drug combination of the different drugs in the prescriptions for the treatment of Emaciation-Thirst disease with stomach fire flaming. In this paper, frequent item sets mining algorithm based on weighted undirected graph is proposed. The proposed algorithm can rapidly mine frequent k-items, and quickly backtrack to the prescription corresponding to frequent item sets, thus accomplishing the rapid data mining of TCM prescription data. Experiments show that this algorithm avoids generating a large number of candidate items and improves the data mining efficiency of TCM prescription, which is of great significance to analyze the law of drug use in the prescriptions of Emaciation-Thirst disease.

Emaciation-Thirst disease Frequent item sets Undirected graph Chinese medicine prescription Data mining

2016-04-05。國家自然科學(xué)基金面上項(xiàng)目(81273649)；黑龍江省自然科學(xué)基金面上項(xiàng)目(F201434)。譚龍，副教授，主研領(lǐng)域：傳感器網(wǎng)絡(luò)，數(shù)據(jù)挖掘。秦琦冰，碩士生。

TP

ADOI:10.3969/j.issn.1000-386x.2017.05.007