秦琦冰，譚 龍,2

(1.黑龍江大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，哈爾濱 150080； 2.黑龍江省數(shù)據(jù)庫(kù)與并行計(jì)算重點(diǎn)實(shí)驗(yàn)室(黑龍江大學(xué))，哈爾濱 150080)

(*通信作者電子郵箱tanlong@hlju.edu.cn)

基于中醫(yī)方劑數(shù)據(jù)庫(kù)的Top-Rank-k頻繁模式挖掘算法

秦琦冰1，譚 龍1,2*

(1.黑龍江大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，哈爾濱 150080； 2.黑龍江省數(shù)據(jù)庫(kù)與并行計(jì)算重點(diǎn)實(shí)驗(yàn)室(黑龍江大學(xué))，哈爾濱 150080)

(*通信作者電子郵箱tanlong@hlju.edu.cn)

為降低中醫(yī)(TCM)方劑頻繁模式挖掘過(guò)程中對(duì)經(jīng)驗(yàn)參數(shù)的依賴(lài)，提高挖掘結(jié)果的準(zhǔn)確性，針對(duì)中醫(yī)方劑的數(shù)據(jù)特點(diǎn)，提出一種基于帶權(quán)無(wú)向圖的Top-Rank-k頻繁模式挖掘算法。該算法可以直接挖掘出頻繁k-itemset(k≥3)而無(wú)需產(chǎn)生1-itemset和2-itemset，并隨之快速回溯到核心藥物組合的頻繁項(xiàng)集所對(duì)應(yīng)的方劑信息；此外，采用一種動(dòng)態(tài)位向量(DBV)的壓縮機(jī)制對(duì)無(wú)向圖中邊的權(quán)重進(jìn)行壓縮存儲(chǔ)，以有效地提高算法的空間存儲(chǔ)效率。分別對(duì)中醫(yī)方劑數(shù)據(jù)集、真實(shí)數(shù)據(jù)集(Chess、Pumsb和Retail)和合成數(shù)據(jù)集(T10I4D100K和Test2K50KD1)進(jìn)行測(cè)試和比較，結(jié)果表明該算法與iNTK和BTK相比具有更高的時(shí)間和空間效率，而且也可以應(yīng)用于其他類(lèi)型的數(shù)據(jù)集。

中醫(yī)方劑；Top-Rank-k；頻繁模式；帶權(quán)無(wú)向圖；動(dòng)態(tài)位向量

0 引言

數(shù)據(jù)挖掘指的是從大量的數(shù)據(jù)中通過(guò)相應(yīng)的算法發(fā)現(xiàn)隱藏于其中未知且可能有用的信息[1-2]。在數(shù)據(jù)挖掘領(lǐng)域，頻繁模式挖掘始終扮演著至關(guān)重要的作用[3]。在傳統(tǒng)的頻繁模式挖掘過(guò)程中，用戶需要輸入最小支持度閾值來(lái)生成滿足條件的頻繁模式集合，因此傳統(tǒng)的頻繁模式挖掘可能會(huì)產(chǎn)生以下兩個(gè)問(wèn)題[4]： 1)用戶很難準(zhǔn)確設(shè)置合適的最小支持度，如果閾值太小可能會(huì)產(chǎn)生大量的頻繁模式，閾值太大可能會(huì)把某些關(guān)鍵信息過(guò)濾掉；2)傳統(tǒng)的頻繁模式挖掘結(jié)果中往往包含大量用戶不感興趣的關(guān)聯(lián)規(guī)則。

基于上述問(wèn)題，Han等[5]提出了一種新的挖掘任務(wù)——Top-k的頻繁閉模式，其中k是被挖掘的頻繁閉模式的數(shù)量，并且模式的最小長(zhǎng)度為min_l。為了更好地解決上述問(wèn)題，Wang等[6]提出了一種有效的挖掘算法——TFP(Top-kFrequent Patterns)算法。然而，在Top-k的頻繁閉模式過(guò)程中，用戶同樣需要輸入?yún)?shù)min_l，這對(duì)于用戶同樣是很難精確把握的。在此基礎(chǔ)上，Deng等[7]提出了一種Top-Rank-k頻繁模式的挖掘任務(wù)，并且提出了解決該問(wèn)題的FAE(Filtering And Extending)算法。與Top-k的頻繁閉模式不同的是，在Top-Rank-k頻繁模式挖掘過(guò)程中，用戶不需要設(shè)置參數(shù)min_l；由于此挖掘過(guò)程中是按照Rank-k對(duì)于候選模式進(jìn)行篩選，因此能夠包含更多用戶感興趣的規(guī)則。

在上述學(xué)者的研究基礎(chǔ)上，F(xiàn)ang等[8]在FAE算法的基礎(chǔ)上，采用一種數(shù)據(jù)垂直分布的形式，將頻繁模式的計(jì)數(shù)轉(zhuǎn)化為一種Tid-lists相交操作，有效地提高了挖掘效率。Deng[9]將事務(wù)數(shù)據(jù)庫(kù)采用PPC-tree進(jìn)行存儲(chǔ)，對(duì)所有的項(xiàng)集按照Node-list進(jìn)行編碼，將Top-Rank-k頻繁模式挖掘轉(zhuǎn)化為Node-list的操作，提出了NTK(Node-list Top-Rank-K)算法。Huynh-Thi-Le等[10]在NTK算法的基礎(chǔ)上，將Subsume的概念及其相關(guān)性質(zhì)應(yīng)用到Top-Rank-k頻繁模式中，提出了iNTK(improved Node-list Top-Rank-K)算法。由于PPC-tree在構(gòu)建采用“先建樹(shù)后編碼”的方式，所以該過(guò)程需要掃描兩次事務(wù)數(shù)據(jù)庫(kù)，隨著事務(wù)數(shù)據(jù)庫(kù)的增加，算法效率有待提高，因此Dam等[11]采用一種“邊建樹(shù)邊編碼”的方式，設(shè)計(jì)和實(shí)現(xiàn)了更加有效的數(shù)據(jù)結(jié)構(gòu)——TB-tree，并在此基礎(chǔ)上采用B-list的方式進(jìn)行編碼，提出了更加有效的BTK(B-list Top-Rank-K)算法。

本研究團(tuán)隊(duì)一直從事中醫(yī)方劑中治療消渴病[12]方劑的數(shù)據(jù)挖掘工作。消渴病是以多飲、多食、多尿、身體消瘦，或尿濁、尿中有甜味為主要表現(xiàn)的一種臨床常見(jiàn)病、多發(fā)病，嚴(yán)重危害著人類(lèi)的健康，中醫(yī)對(duì)于消渴病的預(yù)防和治療有著豐富而且獨(dú)特的經(jīng)驗(yàn)[13]，因此，對(duì)《中醫(yī)方劑大辭典》中收錄的治療消渴病腎陰虛型方劑的研究也尤為重要。在研究中發(fā)現(xiàn)，在實(shí)際中醫(yī)方劑數(shù)據(jù)挖掘中，用戶很難設(shè)置合理的最小支持度閾值，因此相比傳統(tǒng)的頻繁模式，Top-Rank-k頻繁模式挖掘更加具有實(shí)際應(yīng)用價(jià)值。此外，治療消渴病相關(guān)癥型的方劑中往往存在大量的頻繁k-itemset，而相比1-itemset、2-itemset而言，k-itemset(k≥3)對(duì)于治療消渴病腎陰虛型也更具有重要的臨床參考價(jià)值。同時(shí)，在對(duì)方劑數(shù)據(jù)庫(kù)的Top-Rank-k頻繁模式挖掘過(guò)程中，上述傳統(tǒng)的算法在找到頻繁項(xiàng)集結(jié)果后，卻不能有效發(fā)現(xiàn)該頻繁項(xiàng)集所對(duì)應(yīng)的方劑名稱(chēng)，而方劑名稱(chēng)和頻繁項(xiàng)集的對(duì)應(yīng)關(guān)系，對(duì)方劑規(guī)律分析具有重要意義。

因此，針對(duì)上述研究問(wèn)題，本文提出了一種基于帶權(quán)無(wú)向圖(Weighted Undirected Graph, WUG)的Top-Rank-k頻繁模式挖掘算法(Top-Rank-kfrequent patterns mining algorithm based on WUG, WUG_TK)。該算法在動(dòng)態(tài)位向量(Dynamic Bit Vector, DBV)[14]的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上引入相關(guān)的性質(zhì)對(duì)無(wú)向圖中的權(quán)重進(jìn)行壓縮存儲(chǔ)，可以有效地提高空間效率；同時(shí)通過(guò)搜索頻繁項(xiàng)集環(huán)，大幅減少對(duì)原始數(shù)據(jù)庫(kù)的掃描次數(shù)，避免產(chǎn)生大量的候選項(xiàng)集，能夠直接有效地挖掘出滿足條件的k-itemset(k≥3)，并且快速回溯到該頻繁項(xiàng)集所對(duì)應(yīng)的方劑名稱(chēng)，提高對(duì)于中醫(yī)方劑數(shù)據(jù)挖掘效率。

1 系統(tǒng)模型

1.1 基本概念

本文系統(tǒng)模型為，存在項(xiàng)集I={I1,I2,…,Im}，事務(wù)數(shù)據(jù)庫(kù)D={〈TID,T〉|T?I}，其中：TID為代表每一條事務(wù)的標(biāo)識(shí)符；T為項(xiàng)的集合稱(chēng)為模式或者項(xiàng)集；T的支持度用Sup(T)表示。本文中所涉及到的概念介紹如下：

定義1 模式的Rank。假設(shè)存在某模式A，以及事務(wù)數(shù)據(jù)庫(kù)D，A模式的Rank記為RA，則：

RA=|{Sup(X)}|X?I∧Sup(X)≥Sup(A)}|

其中|Y|表示集合Y里面的元素?cái)?shù)目。

例如在表1的事務(wù)數(shù)據(jù)庫(kù)中，I2分別出現(xiàn)在TID1、TID2、TID3、TID4、TID5模式中，Sup(I2)=5，通過(guò)計(jì)算其他模式的支持度可以發(fā)現(xiàn)Sup(I2)最大，因此{(lán)I2}的Rank為1，記為：RI2=1。

定義2Top-Rank-k頻繁模式。假設(shè)存在事務(wù)數(shù)據(jù)庫(kù)D和閾值k，?A?I，如果RA≤k，那么A為T(mén)op-Rank-k頻繁模式。

Top-Rank-k頻繁模式挖掘的目的是在給定的事務(wù)數(shù)據(jù)庫(kù)D和閾值k基礎(chǔ)上， 發(fā)現(xiàn)所有的模式Rank不超過(guò)k的模式集合，記為STop-Rank-k，則：

STop-Rank-k={X|X?I∧RX≤k}

例如在表1的事務(wù)數(shù)據(jù)庫(kù)中，假設(shè)k=3, 則滿足條件的Top-Rank-k頻繁模式如下所示：

STop-Rank-k={{I1},{I2},{I1I2},{I4},{I5},

{I1I4},{I1I5},{I2I4},{I2I5},{I1I2I4},{I1I2I5}}

文獻(xiàn)[7]中已經(jīng)證明Top-Rank-k頻繁模式挖掘過(guò)程滿足反單調(diào)性，即：?模式A?B，如果模式A不是Top-Rank-k頻繁模式，那么B也一定不是Top-Rank-k頻繁模式。

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

1.2 DBV數(shù)據(jù)結(jié)構(gòu)

Top-Rank-k頻繁模式挖掘過(guò)程中，如何對(duì)數(shù)據(jù)進(jìn)行高效存儲(chǔ)十分重要。Dong等[15]提出的BitTable-FI和Song等[16]提出的Index-BitTableFI都是根據(jù)事務(wù)的數(shù)量，采用一種基于數(shù)據(jù)垂直分布的定長(zhǎng)的方式進(jìn)行儲(chǔ)存。當(dāng)處理數(shù)據(jù)比較稀疏時(shí)，BitTable-FI和Index-BitTableFI會(huì)造成空間的浪費(fèi)，因此，本文采用一種更加高效的數(shù)據(jù)結(jié)構(gòu)——?jiǎng)討B(tài)位向量(DBV)[14]進(jìn)行存儲(chǔ)，并且在此基礎(chǔ)上引入了有關(guān)DBV的定義以及與本文算法有關(guān)的性質(zhì)和操作。

DBV數(shù)據(jù)結(jié)構(gòu)包含兩個(gè)域，用二元組的形式表示：〈Pos，BVecor〉，其中:Pos表示存儲(chǔ)的第一個(gè)非0位的位置；BVecor表示從Pos開(kāi)始到尾部最后一個(gè)非0位置的所有二進(jìn)制位(本文中采取十進(jìn)制的形式表示)。

例如，在表1中，n=5，在申請(qǐng)1個(gè)char類(lèi)型存儲(chǔ)空間(8位)的情況下，按照從低位到高位的按位存儲(chǔ)，項(xiàng)I1存在的TID為2，3，4，5，即：t(I1)=〈0,1,1,1,1,0,0,0〉，項(xiàng)I1二進(jìn)制位存儲(chǔ)方式如圖1所示。

圖1 項(xiàng)I1二進(jìn)制位存儲(chǔ)方式

Fig.1BinarybitstoragemodeofitemI1

由此可見(jiàn)，當(dāng)數(shù)據(jù)比較稀疏時(shí)，低位和高位存儲(chǔ)的0會(huì)造成空間浪費(fèi)，因此采用DBV數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)，如圖2所示。

圖2 項(xiàng)I1的DBV存儲(chǔ)方式

在t(I1)=〈0,1,1,1,1,0,0,0〉中，存儲(chǔ)的第一個(gè)非0位的位置是1，所以Pos=1，則項(xiàng)I1的DBV存儲(chǔ)方式為：

DBV(I1)=〈1,〈1,1,1,1〉〉=

〈1,〈21+22+23+24=30〉〉=〈1,30〉

下面介紹兩個(gè)DBV之間的相交操作。

定義3 對(duì)于任意兩個(gè)DBV，假設(shè)DBV1=〈Pos1,BVector1〉，DBV2=〈Pos2,BVector2〉，當(dāng)且僅當(dāng)DBV1∩DBV2=DBV1時(shí)，DBV1是DBV2的子集，即：DBV1?DBV2。

定義4 對(duì)于任意兩個(gè)DBV，假設(shè)DBV1=〈Pos1,BVector1〉,DBV2=〈Pos2,BVector2〉，當(dāng)且僅當(dāng)Pos1=Pos2,|BVector1|=|BVector2|,?i∈[0,|BVector1|-1]，BVector1[i]=BVector2[i]，則DBV1與DBV2相等，即：DBV1=DBV2

性質(zhì)1 對(duì)于任意兩個(gè)DBV，假設(shè)DBV1=〈Pos1,BVector1〉，DBV2=〈Pos2,BVector2〉，如果Pos1+|BVector1|

證明 當(dāng)Pos1+|BVector1|

當(dāng)Pos2+|BVector2|

對(duì)于兩個(gè)DBV之間的相交操作之前，首先要對(duì)于DBV1和DBV2進(jìn)行相交操作，以判斷是否存在子集、相等、空集，如果存在，則由上述定義3、定義4和性質(zhì)1直接進(jìn)行計(jì)算。否則，從Posmax的位置對(duì)BVector進(jìn)行&操作，如果&操作結(jié)果為0，則Posmax+1，直到&操作結(jié)果為1，則Posmax記錄下該位置；從該位置開(kāi)始進(jìn)行&操作，一直到剩余位都是0。具體算法DBV_Intersection如下所示：

Input:DBV1=〈Pos1,BVector1〉,DBV2=〈Pos2,BVector2〉 Output:DBV_finalProcedure DBV_Intersection(DBV1,DBV2)

1)

Pos=max(Pos1,Pos2)

2)

i=Pos1

3)

j=Pos1

4)

count=|BVector1|-i<|BVector2|-j?|BVector1|-i:|BVector2|-j

//intersection操作中的位數(shù)

5)

whilecount>0 andBVector1[i] &BVector2[j]=0

//找到第一個(gè)非零位

6)

i=i+1;j=j+1;

7)

Pos=Pos+1;count=count-1;

8)

i1=i+count-1;j1=j+count-1;

9)

whilecount>0 andBVector1[i1] &BVector2[j1]=0

//找到最后一個(gè)非零位

10)

i1=i1-1;j1=j1-1;

11)

count=count-1;

12)

Fork=0 tocount-1

//找到進(jìn)行intersection操作的位置

13)

BVector[k]=BVector1[i] &BVector2[j]

14)

i=i+1;j=j+1; End procedure

如圖3中所示，DBV(I3)=〈0,〈1,1〉〉，DBV(I1)=〈1, 〈1,1,1,1〉〉，則從Pos_I1開(kāi)始對(duì)DBV數(shù)據(jù)結(jié)構(gòu)中的BVector進(jìn)行&操作，則DBV(I1I3)=〈1,1〉=〈1,2〉。

圖3 I1和I3的DBV_Intersection

1.3 帶權(quán)無(wú)向圖

針對(duì)中醫(yī)方劑Top-Rank-k頻繁模式挖掘，本文采用一種帶權(quán)無(wú)向圖對(duì)于Top-Rank-k頻繁模式進(jìn)行存儲(chǔ)，該算法可以直接產(chǎn)生更加符合中醫(yī)數(shù)據(jù)特點(diǎn)的頻繁模式(k-itemset,k≥3)，而且可以有效地回溯到該頻繁模式所對(duì)應(yīng)的方劑名，這對(duì)于中醫(yī)方劑數(shù)據(jù)挖掘有著重要意義。另外，該算法還可以避免產(chǎn)生大量的候選項(xiàng)集，提高算法效率。

本文中帶權(quán)無(wú)向圖中的節(jié)點(diǎn)由項(xiàng)集I中的項(xiàng)組成；節(jié)點(diǎn)項(xiàng)之間如果是Top-Rank-k頻繁模式，則有邊；1-itemset為點(diǎn)集V；E為邊集；E(Vx,Vy)表示點(diǎn)Vx和Vy的邊；Top-Rank-k頻繁模式閾值為k。則有以下定義：

定義5 權(quán)重。假設(shè)存在項(xiàng)集X、Y，以及DBV(X)和DBV(Y)，如果DBV(XY)=DBV(X)∩DBV(Y)，則稱(chēng)該DBV(XY)為X與Y之間的權(quán)重。

例如DBV(I3)={0,{1,1}}，DBV(I1)=〈1,〈1,1,1,1〉〉，則DBV(I1I3)=〈1,1〉=〈1,2〉,則DBV(I1I3)則為I1與I3之間的權(quán)重，Sup(I1I3)=|DBV(I1I3)|=1。

對(duì)于任意兩個(gè)項(xiàng)集X和Y，如果XY模式Rank不大于k，即：RXY≤k，則X與Y之間存在邊E(X,Y)，該邊加入到E中，同時(shí)weight(X,Y)=DBV(XY)。重復(fù)此過(guò)程生成可存儲(chǔ)Top-Rank-k頻繁模式的帶權(quán)無(wú)向圖，具體的生成算法Procedure WUG_GEN如下所示：

Input： Transactional DatabaseD,kOutput: WUG Procedure WUG_GEN(D,k)

1)

For eachVj∈L1

2)

For eachVi∈L1(i≠j)

3)

CountSup(VjVi) and sort in descending order bySup(VjVi)

4)

IfR(VjVi)≤k

5)

AddE(Vi,Vi) to Edge setE;

//增加邊E(Vi,Vi)到邊集E中

6)

weight(Vi,Vj)=DBV_Intersection

7)

End if;

8)

End for;

9)

End for;

End procedure

定理1 在給定的帶權(quán)無(wú)向圖中，對(duì)于某個(gè)點(diǎn)集合V′中任意兩點(diǎn)Vi和Vk，如果都存在一條邊E(Vi,Vk)∈E，則V′中所有的點(diǎn)構(gòu)成一條Top-Rank-k頻繁項(xiàng)集環(huán)，即為T(mén)op-Rank-k頻繁項(xiàng)集。

證明 假設(shè)?Vi∈V(1≤i≤m),?V′=〈V1,V2,…,Vi, …,Vj, …,Vk〉,如果對(duì)于?Vi∈V′, ?Vj∈V′，使得E(Vi,Vj)∈E成立，由ProcedureWUG_GEN和Top-Rank-k頻繁模式挖掘過(guò)程中的反單調(diào)性[7]可知，{V1，V2，Vi,…,Vj, …，Vk}為T(mén)op-Rank-k頻繁項(xiàng)集，即存在一條Top-Rank-k頻繁項(xiàng)集環(huán)，該環(huán)路經(jīng)過(guò)的頂點(diǎn)〈V1,V2,…,Vk〉即為滿足Rank條件的頻繁項(xiàng)集。

2 WUG_TK

本文在帶權(quán)無(wú)向項(xiàng)圖的基礎(chǔ)上，提出了一種Top-Rank-k頻繁模式挖掘算法(WUG_TK)。算法中使用帶權(quán)無(wú)向圖存儲(chǔ)Top-Rank-k頻繁模式，圖中頂點(diǎn)集合即為1-itemset，頂點(diǎn)之間邊的權(quán)值即為DBV(ViVj)，如果存在Top-Rank-k頻繁項(xiàng)集環(huán)，則環(huán)上面的頂點(diǎn)即為滿足Rank條件的頻繁項(xiàng)集。環(huán)路的每條邊的權(quán)值，進(jìn)行與(&)操作，其結(jié)果即為頻繁項(xiàng)集所在的TID。該TID在具體中醫(yī)方劑數(shù)據(jù)處理中，即為頻繁藥物組合所對(duì)應(yīng)的方劑名稱(chēng)。

在上述生成的帶權(quán)無(wú)向圖(WUG)的基礎(chǔ)上，搜索Top-Rank-k頻繁項(xiàng)集環(huán)的操作見(jiàn)Procedure Mining_Top-Rank-k_Frequent Patterns算法，該算法調(diào)用Procedure Top-Rank-k_Frequent Patterns loop來(lái)完成對(duì)Top-Rank-k頻繁項(xiàng)集環(huán)的搜索。

Mining_Top-Rank-k_Frequent Patterns算法描述如下：

Input： WUG Output: Top-Rank-k_Frequent Patterns,TIDProcedureMining_Top-Rank-k_Frequent Patterns(WUG)

1)

WhileV≠?do

2)

ForeachVi,Vj(i≠j)ofV

3)

IfE(Vi,Vj)∈Ethen

//Vi,Vj之間有邊相連

4)

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

//L為其中任意兩點(diǎn)都有邊相連的點(diǎn)集合；

//V′為含有未搜索到的點(diǎn)的集合

5)

Search Top-Rank-k_Frequent Patterns loop(L,V′);

//調(diào)用Procedure Top-Rank-k_Frequent Patterns loop

//來(lái)搜索Top-Rank-k頻繁項(xiàng)集環(huán)

6)

End If;

7)

End For;

8)

End While;

End procedure;

Procedure Top-Rank-k_Frequent Patterns loop(L,V′)

1)

WhileV′≠nulldo

2)

ForunvisitedVkofV′

3)

IfE(Vk,?Vj∈V′)∈Ethen;

4)

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

5)

OutputLandweight_&;

//輸出Top-Rank-k_Frequent Patterns和對(duì)應(yīng)的TID

6)

Endif;

7)

Endfor;

8)

Endwhile;

Endprocedure

例如在表1事務(wù)數(shù)據(jù)庫(kù)中，設(shè)k=3，根據(jù)WUG_GEN算法：I1出現(xiàn)TID分別為2、3、4、5，則DBV(I1)=〈1,〈1,1,1,1〉〉=〈1,30〉，I2出現(xiàn)TID分別為1、2、3、4、5，則DBV(I2)=〈0,〈1,1,1,1,1〉〉=〈0,31〉，因?yàn)镈BV(I1)是DBV(I2)的子集，則DBV(I1)∩DBV(I2)=DBV(I1)=〈1,〈1,1,1,1〉〉，則Sup(I1I2)=4，此時(shí)R(I1 I2)=1，則頂點(diǎn)I1頂點(diǎn)I2之間存在一條邊E(I1,I2)，weight(I1,I2)=〈1,〈1,1,1,1〉〉=〈1,30〉，以此類(lèi)推可以生成如圖4所示的Top-Rank-3的頻繁模式圖。

圖4 Top-Rank-3的頻繁模式圖

根據(jù)Mining_Top-Rank-k_Frequent Patterns算法：對(duì)于WUG(V,E,W)中?E(Vi,Vj)∈E，例如圖1中的點(diǎn)I1和點(diǎn)I2，從V′=V-{I1,I2}={I4,I5}中選取點(diǎn)I4，則E(I4,I1)∈E，E(I4,I2)∈E，則點(diǎn)I1、點(diǎn)I2和點(diǎn)I4之間存在一條Top-Rank-3頻繁項(xiàng)集環(huán)，則I1I2I4為滿足Rank小于等于3的頻繁3-itemset，weight(I1,I2) &weight(I1,I4) &weight(I2,I4)=〈1,〈1,1,0,1〉〉，即I1I2I4出現(xiàn)的TID為2、3、5。同理可以由圖4可以生成Rank小于等于2的頻繁3-itemsetI1I2I5，I1I2I5出現(xiàn)的TID為3、4、5。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)置與結(jié)果

實(shí)驗(yàn)環(huán)境為IntelCorei3-3110M2.4GHzCPU,4GBRAM，操作系統(tǒng)為Windows7。算法在VisualStudio2012，.NetFrameworkVersion4.5.50709的環(huán)境下實(shí)現(xiàn)。

中醫(yī)方劑實(shí)驗(yàn)數(shù)據(jù)是從《中醫(yī)方劑大辭典》中收錄的治療消渴病腎陰虛型方劑中篩選出來(lái)的346首方劑，包含163味中藥藥材。針對(duì)數(shù)據(jù)的前期準(zhǔn)備處理主要是針對(duì)藥物組成的規(guī)范，該規(guī)范包括：藥材的重名和異名處理、同名異方的處理、藥材計(jì)量單位的統(tǒng)一。在此規(guī)范數(shù)據(jù)基礎(chǔ)上，構(gòu)建方劑數(shù)據(jù)庫(kù)。

通過(guò)對(duì)《中醫(yī)方劑大辭典》中收錄的方劑進(jìn)行分析，初步按照編號(hào)、方劑名、組成、別名、性、味、歸經(jīng)、功效等8個(gè)屬性進(jìn)行描述，完成對(duì)原始數(shù)據(jù)庫(kù)的構(gòu)建；然后利用基于帶權(quán)無(wú)向圖的Top-Rank-k頻繁模式挖掘算法對(duì)數(shù)據(jù)源存儲(chǔ)的方劑進(jìn)行分析研究。

根據(jù)本次治療腎陰虛型方劑數(shù)量和用到的中藥個(gè)數(shù)，結(jié)合經(jīng)驗(yàn)判斷以及不同參數(shù)提取數(shù)據(jù)的預(yù)讀，篩選出部分有價(jià)值的Top-Rank-16的k-itemset(k≥3)及所對(duì)應(yīng)的方劑名見(jiàn)表2。

表2 治療腎陰虛型組方中Top-Rank-16藥物核心組合

3.2 算法性能對(duì)比及分析

本文提出的WUG_TK算法主要與Huynh-Thi-Le等[10]的iNTK算法和Dam等[11]的BTK算法分別從運(yùn)行時(shí)間、消耗空間作了對(duì)比實(shí)驗(yàn)。對(duì)比實(shí)驗(yàn)數(shù)據(jù)集分別采用中醫(yī)方劑數(shù)據(jù)集和公開(kāi)測(cè)試數(shù)據(jù)集。中醫(yī)方劑數(shù)據(jù)集實(shí)驗(yàn)數(shù)據(jù)采用《中醫(yī)方劑大辭典》中收錄的治療消渴病腎陰虛型和胃火熾盛型兩種癥型方劑。其中，治療腎陰虛型方劑共346首，包含163味中藥藥材；治療消渴病胃火熾盛方劑共382首，包含218味中藥藥材。公開(kāi)測(cè)試數(shù)據(jù)集如表3所示，主要包括Chess、Pumsb和Retail三個(gè)真實(shí)數(shù)據(jù)集(http://fimi.ua.ac.be/data/)，以及T10I4D100K和Test2K50KD1人工合成數(shù)據(jù)集。其中人工合成數(shù)據(jù)集主要是由LUCS-KDD數(shù)據(jù)生成器合成的。算法運(yùn)行時(shí)間的對(duì)比實(shí)驗(yàn)在真實(shí)數(shù)據(jù)集上進(jìn)行，結(jié)果如圖5所示；而算法消耗空間的對(duì)比實(shí)驗(yàn)在人工模擬數(shù)據(jù)集上進(jìn)行，結(jié)果如圖6所示。

表3 對(duì)比實(shí)驗(yàn)數(shù)據(jù)集

圖5 算法運(yùn)行時(shí)間對(duì)比

圖6 算法空間消耗對(duì)比

實(shí)驗(yàn)中，三種算法通過(guò)設(shè)置不同的k值進(jìn)行實(shí)驗(yàn)比較。當(dāng)平均項(xiàng)數(shù)目較小時(shí)，生成有效項(xiàng)集的概率就會(huì)降低，符合條件的Top-Rank-k的頻繁模式就會(huì)增多，挖掘代價(jià)也會(huì)相應(yīng)增加。因此，實(shí)驗(yàn)中對(duì)不同的實(shí)驗(yàn)數(shù)據(jù)集選擇不同的閾值，從而保證實(shí)驗(yàn)結(jié)果的有效性。

由于WUG_TK算法通過(guò)帶權(quán)無(wú)向圖直接產(chǎn)生k-itemset(k≥3)，避免了候選項(xiàng)集的產(chǎn)生，而iNTK和BTK都采取了“建樹(shù)-編碼”的過(guò)程，與之相比，WUG_TK算法不需要對(duì)數(shù)據(jù)集中的項(xiàng)集進(jìn)行編碼，而是在構(gòu)造完成的帶權(quán)無(wú)向圖上直接搜索符合Rank條件的頻繁模式環(huán)，從而大幅提高了算法的運(yùn)行效率，因此WUG_TK算法性能明顯優(yōu)于iNTK和BTK算法。

由于WUG_TK算法中對(duì)于權(quán)重采用DBV的壓縮數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)，可以有效地提高空間利用率，而iNTK算法和BTK算法在運(yùn)行過(guò)程中都需要采用臨時(shí)表對(duì)中間結(jié)果集進(jìn)行存儲(chǔ)，從而也造成了過(guò)大開(kāi)銷(xiāo)。因此本文提出的WUG_TK算法在空間效率上也優(yōu)于iNTK算法和BTK算法。

4 結(jié)語(yǔ)

本文根據(jù)中醫(yī)方劑的數(shù)據(jù)特點(diǎn)，提出了一種基于帶權(quán)無(wú)向圖的Top-Rank-k頻繁模式挖掘算法WUG_TK。該算法在不產(chǎn)生1-itemset和2-itemset的前提下，可以直接產(chǎn)生k-itemset(k≥3)，更加符合中醫(yī)方劑挖掘的需求；同時(shí)WUG_TK可以回溯到頻繁項(xiàng)集所在的方劑名，這對(duì)方劑規(guī)律分析具有重要意義；此外，WUG_TK算法中采用DBV數(shù)據(jù)結(jié)構(gòu)對(duì)于無(wú)向圖中的權(quán)重進(jìn)行壓縮存儲(chǔ)，可以有效地降低空間復(fù)雜度。實(shí)驗(yàn)結(jié)果表明，WUG_TK算法與iNTK和BTK算法相比具有更高的時(shí)間和空間效率。

由于本文中DBV數(shù)據(jù)結(jié)構(gòu)采取了一種位向量的方式進(jìn)行動(dòng)態(tài)壓縮存儲(chǔ)，當(dāng)處理的數(shù)據(jù)過(guò)于稠密時(shí)，數(shù)據(jù)中往往存在大量的非0位，此時(shí)DBV的壓縮效果還有待提高。另外，由于中醫(yī)方劑Top-Rank-k頻繁模式挖掘中往往存在冗余，這就會(huì)造成挖掘效率的降低，下一步將針對(duì)如何在挖掘過(guò)程中減少信息冗余進(jìn)行研究。

References)

[1] SOLANKI S K, PATEL J T.A survey on association rule mining [C]// ACCT 2015： Proceedings of the 2015 5th International Conference on Advanced Computing & Communication Technologies.Washington, DC: IEEE Computer Society, 2015: 212-216.

[2] CHEN H, LI T, LUO C, et al.A decision-theoretic rough set approach for dynamic data mining [J].IEEE Transactions on Fuzzy Systems, 2015, 23(6): 1958-1970.

[3] KARTHIKEYAN T, RAVIKUMAR N.A survey on association rule mining [J].International Journal of Advanced Research in Computer and Communication Engineering, 2014, 3(1): 5223-5227.

[4] LE B, VO B, HUYNH-THI-LE Q, et al.Enhancing the mining top-rank-kfrequent patterns [C]// SMC 2014: Proceedings of the 2014 IEEE International Conference on Systems, Man and Cybernetics.Piscataway, NJ: IEEE, 2014: 2008-2012.

[5] HAN J, WANG J, LU Y, et al.Mining top-k frequent closed patterns without minimum support [C]// ICDM ’02: Proceedings of the 2002 IEEE International Conference on Data Mining.Washington, DC: IEEE Computer Society, 2002: 211-218.

[6] WANG J, HAN J, LU Y, et al.TFP: an efficient algorithm for mining top-kfrequent closed itemsets [J].IEEE Transactions on Knowledge and Data Engineering, 2005, 17(5): 652-664.

[7] DENG Z-H, FANG G-D.Mining top-rank-kfrequent patterns [C]// Proceedings of the 2007 International Conference on Machine Learning and Cybernetics.Piscataway, NJ: IEEE, 2007: 851-856.

[8] FANG G-D, DENG Z-H.VTK: vertical mining of top-rank-kfrequent patterns [C]// FSKD’08: Proceedings of the 2008 5th International Conference on Fuzzy Systems and Knowledge Discovery.Washington, DC: IEEE Computer Society, 2008, 2: 620-624.

[9] DENG Z-H.Fast mining top-rank-kfrequent patterns by using node-lists [J].Expert Systems with Applications, 2014, 41(4): 1763-1768.

[10] HUYNH-THI-LE Q, LE T, VO B, et al.An efficient and effective algorithm for mining top-rank-kfrequent patterns [J].Expert Systems with Applications, 2015, 42(1): 156-164.

[11] DAM T-L, LI K, FOURNIER-VIGER P, et al.An efficient algorithm for mining top-rank-kfrequent patterns [J].Applied Intelligence, 2016, 45(1): 96-111.

[12] 吳長(zhǎng)汶,張轉(zhuǎn)喜,吳水生,等.從五味太過(guò)探討“甘邪”與消渴病因的關(guān)系[J].中華中醫(yī)藥雜志,2015(3):670-672.(WU C W, ZHANG Z X, WU S S, et al.Exploration on the relationship between the sweet-evil and consumptive thirst pathogenesis based on theory of excess of five kinds of taste [J].China Journal of Traditional Chinese Medicine and Pharmacy, 2015(3): 670-672.)

[13] 榮開(kāi)明.復(fù)興中醫(yī)藥學(xué)的幾點(diǎn)思考[J].湖北中醫(yī)藥大學(xué)學(xué)報(bào),2015,17(2):59-62.(RONG K M.Considerations on revival of TCM [J].Journal of Hubei University of Chinese Medicine, 2015,17(2):59-62.)

[14] VO B, HONG T-P, LE B.DBV-Miner: a dynamic bit-vector approach for fast mining frequent closed itemsets [J].Expert Systems with Applications, 2012, 39(8): 7196-7206.

[15] DONG J, HAN M.BitTableFI: an efficient mining frequent itemsets algorithm [J].Knowledge-Based Systems, 2007, 20(4): 329-335.

[16] SONG W, YANG B, XU Z.Index-BitTableFI: an improved algorithm for mining frequent itemsets [J].Knowledge-Based Systems, 2008, 21(6): 507-513.

This work is partially supported by the National Natural Science Foundation of China (81273649), Natural Science Foundation of Heilongjiang Province (F201434), Graduate Student Innovation and Research Item of Heilongjiang University (YJSCX2016- 018HLJU).

QIN Qibing, born in 1990, M.S.candidate.His research interests include machine learning, data warehouse, data mining.

TAN Long, born in 1971, M.S., associate professor.His research interests include machine learning, sensor network, data mining.

Top-Rank-kfrequent patterns mining algorithm based on TCM prescription database

QIN Qibing1, TAN Long1,2*

(1.CollegeofComputerScienceandTechnology,HeilongjiangUniversity,HarbinHeilongjiang150080,China;2.KeyLaboratoryofDatabaseandParallelComputingofHeilongjiangProvince(HeilongjiangUniversity),HarbinHeilongjiang150080,China)

The dependency of the empirical parameters in frequent patterns mining of Traditional Chinese Medicine (TCM) prescriptions should be reduced to improve the accuracy of mining results.Aiming at the characteristics of TCM prescription data, an efficient Top-Rank-kfrequent patterns mining algorithm based on Weighted Undirected Graph (WUG) was proposed.The new algorithm can directly mining frequentk-itemset (k≥3) without mining 1-times and 2-times, and then quikly backtrack to the corresponding prescription of the frequent itemsets of core drugs combination.Besides, the compression mechanism of Dynamic Bit Vector (DBV) was used to store the edge weights in undirected graph to improve the spatial storage efficiency of the algorithm.Experiments were conducted on TCM prescription datasets, real datasets (Chess, Pumsb and Retail) and synthetic datasets (T10I4D100K and Test2K50KD1).The experimental results show that compared with iNTK (improved Node-list Top-Rank-K) and BTK (B-list Top-Rank-K), the proposed algorithm has better performance in terms of time and space, and it can be applied to other types of data sets.

Traditional Chinese Medicine (TCM) prescription; Top-Rank-k; frequent pattern; Weighted Undirected Graph (WUG); Dynamic Bit Vector (DBV)

2016- 08- 12;

2016- 09- 08。 基金項(xiàng)目:國(guó)家自然科學(xué)基金面上項(xiàng)目(81273649);黑龍江省自然科學(xué)基金面上項(xiàng)目(F201434);黑龍江大學(xué)研究生創(chuàng)新科研項(xiàng)目重點(diǎn)項(xiàng)目(YJSCX2016-018HLJU)。

秦琦冰(1990—),男,山東濰坊人,碩士研究生,主要研究方向:機(jī)器學(xué)習(xí)、數(shù)據(jù)倉(cāng)庫(kù)、數(shù)據(jù)挖掘; 譚龍(1971—),男,黑龍江哈爾濱人,副教授,碩士,CCF會(huì)員,主要研究方向:機(jī)器學(xué)習(xí)、傳感器網(wǎng)絡(luò)、數(shù)據(jù)挖掘。

1001- 9081(2017)02- 0329- 06

10.11772/j.issn.1001- 9081.2017.02.0329

TP311.13

A