基于中藥專利數據集的關聯規則發現算法
2007-12-31 00:00:00錢增瑾辛燕鞠時光
計算機應用研究 2007年7期
摘要：指出關聯規則在中藥數據分析中的難點，據此提出了一種改進的Apriori算法——Apriori+算法；最后，以治療感冒的中藥專利數據集為測試數據，進一步驗證算法的有效性和實用性。結果表明，此算法能夠有效地從治療感冒的專利數據庫中發現布爾型與數值型關聯規則，為開發新的感冒中藥提供配伍依據。
關鍵詞：數據挖掘； 數據預處理； 關聯規則； 中藥配伍規則
中圖分類號：TP301．6文獻標志碼：A
文章編號：1001－3695(2007)07－0061－03
數據挖掘技術已成功地應用于西藥的研究[1]，而對中醫藥數據的分析尚處于起步階段。由于西藥是由有機化學藥品、無機化學藥品和生物制品組成，研究的是人工合成的物質，其組成有較高的確定性；而中藥是由我國傳統使用的植物、動物和礦物藥及其成藥組成，是天然藥物，加之中藥上千年的發展，在不同地方形成不同的中藥文化，中藥的組成較為復雜。用于分析西藥的技術并不能直接應用于中藥的研究。為此，根據中藥數據的特點，將關聯規則用于分析傳統的中藥專利數據庫，及時發現中醫藥數據庫中中藥方劑的配伍規律，從而打破中醫藥數據堆積而信息貧乏的局面，為中藥新藥的研制提供決策信息。
1基于方劑用量值的約束關聯規則挖掘算法
將關聯規則用于分析傳統的中藥專利數據庫，其主要目的是為了及時發現中醫藥數據庫中中藥方劑的配伍規律，如治療某種疾病時哪幾味中藥會同時出現，以及同時出現的幾味中藥中它們各自所對應的用量范圍，即需要從中醫藥專利數據庫中同時發現布爾型與數值型關聯規則。針對上述目標，結合經典的關聯規則挖掘算法——Apriori算法思想，本文提出Apriori+算法。
在Apriori+算法中，每一個項由項名與項值構成，在掃描所有事務時，不僅對每個項的出現次數計數，還對每個項名的出現次數計數。因此得到的關聯規則同時包括了數值型與布爾型兩種關聯規則。
1．1數據結構定義
為了方便算法的描述，并結合預處理之后方劑信息的存儲形式（圖1），定義如下數據結構來存放中藥事務數據庫中的每個中草藥對象，即事務數據庫中的某一項。
struct item
{string: name；
int: weight；}
1．2算法改進
利用Apriori+算法挖掘關聯規則時，主要在以下幾方面進行擴充和改進：
（1）支持度閾值的設定
由于Apriori+算法要同時獲取布爾型和數值型關聯規則，為產生這兩種不同的關聯規則分別設置了不同的支持度閾值min_supB、min_supQ，且min_supB≥min_supQ。這是因為，在中藥專利數據中，同一味中草藥可以以不同的藥劑量出現在不同的藥方中，在中藥專利數據庫中就表現為一個項名和不同的項值組合成不同的項，所以項名的出現頻率一定大于項的出現頻率。
（2）候選項集的產生
候選項集的產生同樣也包括關于項的候選項集和關于項名的候選項集的產生這兩個不同過程。關于項名的候選項集的產生與經典的Apriori算法過程一致；而關于項的候選項集的產生則通過下述連接過程實現：為找頻繁k－項集Lk，通過由L(k-1)與自身連接生成候選k－項集的集合Ck。在此規定L(k-1)的元素可以進行連接的條件。
①前（k-2）個項所描述的屬性和屬性的事實約束值均相同；
②第（k-1）個項所描述屬性是不同的。
1．3算法實現
Apriori+算法如下：
輸入：事務數據庫ZY；最小支持度閾值min_supB、min_supQ
輸出：ZY中的頻繁項集L、L′
方法：
C1= find_1_itemsetsQ(ZY);
C′1= find_1_itemsetsB(ZY);
for each transaction t in ZY {
for each candidate c in C1
if c in t then c.count++;
for each candidate c′ in C′1
if c′ in t.name then c′. count++;
}
L1={c in C1 | c.count>=(min_supQ*|ZY|)};
L′1={c′ in C′1 | c′. count>=(min_supB*|ZY|)};
ifL1≠Φ then { flagQ=1;
kQ=2;}
ifL′1≠Φ then {flagB=1;
kB=2;}
while (flagB=1 or flagQ=1) {
if flagQ=1 then CkQ=apriori_genQ(LkQ-1);
if flagB=1 then C′kB=apriori_genB(L′kB-1);
for each transaction t in ZY {
if flagQ=1 then {Ct=subset(CkQ，t);
for each candidate c in Ct
c.count++;
}
if flagB=1 then { C′t=subset(C′kB， t.name);
for each candidate c′ in C′t
c′.count++;
}
}
if flagQ=1 then{LkQ={c in CkQ|c.count>=(min_supQ*
|ZY|)};
kQ=kQ+1;}
if flagB=1 then {L′kB={c′ in C′kB | c′.count>=(min_supB*|ZY|)};
kB=kB+1;
}
if LkQ=Φ then flagQ=0;
if L′kB=Φ then flagB=0;
}
return L=∪LkQ， L′=∪L′kB;
函數find_1_itemsetsQ(ZY)產生關于項集合的候選C1；函數find_1_itemsetsB(ZY)產生關于項名集合的候選C′1。變量kB與kQ分別表示項集中包含的項數；變量flagQ與flagB分別表示是否產生了空的頻繁集。函數subset(x，y)找出集合y中集合x的所有子集。過程apriori_genB與apriori_genQ分別產生兩類候選。至此，從數據庫中找出了頻繁項集，參照文獻[2]所介紹的方法可直接產生強關聯規則。
下面給出了適合于發現數值型關聯規則的連接過程apriori_genQ。
輸入：頻繁(k－1)－項集L(k-1)、頻繁(k-1)－項集L(k-1)的元素個數recnum
輸出：候選k－項集的集合Ck
方法：
procedure apriori_genQ （ L(k-1)， recnum）
array: l[recnum][k-1]
for i= 1 to recnum-1
for j=2 to recnum
if ((l[i][1].name=l[j][1].name)∧(l[i][1].weight=l[j][1].weight)∧
(l[i][2].name=l[j][2].name)∧(l[i][2].weight=l[j][2].weight)∧…∧
(l[i][k-2].name)=l[j][k-2].name∧（l[i][k-2].weight=l[j][k-2].weight）∧
(l[i][k-1].name＜l[j][k-1].name))
//meet the two conditions of link
then begin
c=l[i]*l[j]; //link step:generate candidates
if has_infrequent_subset (c，L(k-1)) then
delete c; //prune step:remove unfruitful candidate
else add c to Ck;
end
return Ck;}{apriori_genQ}
1．4算法實例
按照上述算法流程，針對表1所示的中藥專利事務數據庫，通過以下示例來說明該算法的執行過程。
表1ZY事務數據
3結束語
針對Apriori算法的局限性，并結合實際的應用情況，本文提出了Apriori+算法。經典的Apriori算法主要用于發現事務數據庫中的布爾型關聯規則；而Apriori+算法不僅繼承了原Apriori算法的功能，而且還為發現數值型關聯規則找到了一條途徑。在Apriori+算法的執行過程中，分別統計項與項名的出現頻數，為發現數值型與布爾型關聯規則奠定了基礎。在(k-1)－項頻繁集L(k-1)連接生成k－項候選集Ck的過程中，Apriori+算法中給出了兩個連接條件。其中，條件②是為了避免同一個項名與不同的事實約束值構成不同的項同時出現在一個頻繁項集中。這是因為在任一藥方中，每一味中藥不會以不同的重量出現，表現在中藥事務數據庫中，就是一個項名在同一個事務中至多出現一次，因而增設了條件②。這樣，使得過程apriori_genQ既避免了多余的運算，又不會使生成的候選集漏掉頻繁子集。
本文首先從中藥數據的特點出發，提出了規范中藥處方的方法；其次，為規范后的中醫藥數據設計了一種發現方劑之間關聯規則的算法Apriori+；最后，通過一個實驗進一步證實了算法的可行性，并得到了一系列中藥配伍的規則，為中藥新藥開發提供了重要的決策數據。目前，該系統還處在理論探索和研究階段，Apriori+算法需要反復掃描數據庫，通過模式匹配檢查一個很大的候選集合，時間復雜度較大。因此，今后的工作將集中在算法的改進和完善方面，以期提高算法的效率，并期望此系統能更好地結合領域專家的知識，提高挖掘的效率。
參考文獻：
[1]LAVALLE S M， FINE P W， KAVRAKIL E， et al. A randomized kinematics－based approach to pharmacophore－constrained conformational search and database screening[J]. Journal of Computational Chemistry， 2001，21(9):731－747.
[2]HAN Jiawei， KAMBER M. Data mining: concepts and technique[M]. USA: Morgan Kaufmann Publishers， 2001.
[3]XIN Yan，JU Shiguang.Mining conditional hybrid－dimensional associa－tion rules on the basis of multi－dimension transaction database: proc.of the 2nd International Conference on Machine Learning and Cybernetics(ICMLC 2003)[C].[S.l.]:[s.n.]， 2003:216－221.
[4]CARLOS O， CESAR A， BRAAL S L. Discovery interesting association rules in medical data: proc.of ACM SIGMOD Workshop on Research Issuse on Data Mining and Knowledge Discovery(DMKD 2000)[C].[S.l.]:[s.n.]， 2000:78－85.
[5]CATLETT J. On changing continmous attributes into ordered discrete attributes: proc.of European Working Session on Learning， Lecture Notes in Artificial Intelligent[C].[S.l.]:[s.n.]， 1991:167－178.
[6]崔雷.數據挖掘及其在醫學研究中的應用[J].信息系統，2001，24(5):368－370.
[7]錢增瑾，辛燕.中醫藥數據預處理方法的設計與實現[J].計算機工程與設計， 2005，26(12):3199－3200，3218.
[8]閻星娥，鞠時光，蔡濤，等.OLAP中基于FP－增長的關聯規則挖掘[J].計算機科學，2004，31(4):113－116.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
