1、. 華 中 科 技 大 學(xué) 碩 士 學(xué) 位 論 文碩士學(xué)位論文一種基于生物數(shù)據(jù)的多層關(guān)聯(lián)規(guī)則挖掘算法.;A Thesis Submitted in fulfillment of the Requirements for the Degree of Master of EngineeringAn Algorithm for Mining Biological Data Multilevel Association RulesCandidate: Zhang PingMajor: Computer Software and TheorySupervisor: Prof. Lu YanshengHu

2、azhong University of Science & TechnologyWhuhan 430074, P.R.ChinaJune, 2007獨(dú)創(chuàng)性聲明本人聲明所呈交的學(xué)位論文是我個(gè)人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知，除文中已經(jīng)標(biāo)明引用的內(nèi)容外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫過的研究成果。對(duì)本文的研究做出貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本人完全意識(shí)到，本聲明的法律結(jié)果由本人承擔(dān)。 學(xué)位論文作者簽名： 日期：     年   月   日學(xué)位論文版

3、權(quán)使用授權(quán)書本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué)校有權(quán)保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)華中科技大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。本論文屬于 保 密 ，在_年解密后適用本授權(quán)書。不保密。（請(qǐng)?jiān)谝陨戏娇騼?nèi)打“”）學(xué)位論文作者簽名：                  

4、 指導(dǎo)教師簽名：日期：    年   月   日              日期：    年   月    日摘 要數(shù)據(jù)挖掘是從大量數(shù)據(jù)中發(fā)現(xiàn)潛在的、有趣的知識(shí)的過程，是解決“數(shù)據(jù)豐富，知識(shí)貧乏”狀況的有效方法。關(guān)聯(lián)規(guī)則挖掘用于從大量數(shù)據(jù)中揭示項(xiàng)集之間的有趣關(guān)聯(lián)或相關(guān)聯(lián)系，是數(shù)據(jù)挖掘的一項(xiàng)

5、重要研究?jī)?nèi)容，在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用。研究表明，關(guān)聯(lián)規(guī)則挖掘技術(shù)是尋找基因間關(guān)系的有效手段；但現(xiàn)有算法未針對(duì)高通量生物數(shù)據(jù)的特點(diǎn)進(jìn)行優(yōu)化，而存在著效率低下、規(guī)則缺乏生物學(xué)意義等缺點(diǎn)。與單層關(guān)聯(lián)規(guī)則挖掘相比，多層關(guān)聯(lián)規(guī)則能夠提供更加豐富、更具普遍意義的知識(shí)；選用合理的概念層次結(jié)構(gòu)與多層關(guān)聯(lián)規(guī)則挖掘算法，能夠更好的適應(yīng)生物數(shù)據(jù)挖掘的需要。已有的多層關(guān)聯(lián)規(guī)則挖掘算法如Cumulate 算法、ML_T2L1算法，都是通過對(duì)Apriori算法進(jìn)行擴(kuò)展得到的。這些算法仍采用候選生成并驗(yàn)證的方式得到頻繁模式，導(dǎo)致了巨大的計(jì)算和I/O 開銷，使得效率較低。選用Gene Ontology完善的概念層次結(jié)構(gòu)，

6、通過對(duì)FP_Growth算法進(jìn)行擴(kuò)展，獲得了一種優(yōu)化的生物數(shù)據(jù)多層關(guān)聯(lián)規(guī)則挖掘算法MAGO-FP。MAGO-FP算法采用的擴(kuò)展措施如下：(1)在掃描數(shù)據(jù)庫的過程中通過把每個(gè)項(xiàng)的全部祖先加入到事務(wù)中對(duì)每條事務(wù)進(jìn)行擴(kuò)充，該措施能夠確保得到多層關(guān)聯(lián)規(guī)則；(2)通過及時(shí)刪除概念層次樹中不是頻繁項(xiàng)的祖先項(xiàng)來壓縮搜索空間，提高挖掘效率；(3)避免產(chǎn)生冗余的頻繁模式。性能實(shí)驗(yàn)表明MAGO-FP算法是正確的，并繼承了FP_Growth算法運(yùn)行效率高的優(yōu)點(diǎn)。應(yīng)用MAGO-FP算法分析了一組由S.cerevisiae酵母菌cDNA微陣列芯片產(chǎn)生的實(shí)驗(yàn)數(shù)據(jù)，發(fā)現(xiàn)了一些候選關(guān)聯(lián)規(guī)則。并針對(duì)其中一些重要的關(guān)聯(lián)規(guī)則，通過

7、相關(guān)文獻(xiàn)證實(shí)了其真實(shí)性，表明該算法在基因表達(dá)分析、基因調(diào)控網(wǎng)絡(luò)等研究中具有一定的應(yīng)用價(jià)值。關(guān)鍵詞：數(shù)據(jù)挖掘，多層關(guān)聯(lián)規(guī)則，基因本體論，MAGO-FP算法AbstractData mining is a process to reveal latent and interesting knowledge from massive data, and an effective approach to solve the problem of "rich data and poor knowledge". Association rules mining can reveal i

8、nteresting correlations among item sets from massive data. It is an important subject of data mining and is widely used in real life.Recent studies have proved that association rules can reveal the interactions between genes, showing patterns that may not have been identified using traditional clust

9、ering methods; but existing algorithms still have some shortcomings. The proposed algorithms for mining multilevel association rules, such as Cumulate algorithm and ML_T2L1 algorithm, are based on Apriori algorithm. These algorithms still adopt "candidate generate and test" method to get f

10、requent patterns which cause large cost in computing and I/O; so they are inefficient.Improved from FP_Growth algorithm, MAGO-FP, an optimized data mining technique to discover the multilevel association rules from gene expression data and the concept hierarchy of Gene Ontology (GO) has been propose

11、d. The following measures are applied to expand FP-Growth algorithm: (1) Expanding every transaction by adding all ancestors of each item during the process of scanning the database. This measure ensures that we can get multilevel association rules; (2) Deleting the ancestors that are not frequent i

12、tems in time to compress search space and enhance the efficiency of mining; (3) Avoiding generating redundant frequent patterns. The multilevel association rules mining algorithm can figure out the relations between GO terms by summarizing the genes with the hierarchy of GO. An experiment showed tha

13、t MAGO-FP algorithm got the same result as Cumulate algorithm did and inherited the strongpoint of high efficiency of FP_Growth algorithm.A data set of 300 expression profiles for yeast has been analyzed; using the algorithm, we found numerous rules in the data. A cursory analysis of some of these r

14、ules reveals numerous associations between certain genes, many of which made sense biologically, others suggesting new hypotheses that may worth of being further investigated. The algorithm could be used to analyze gene expression profiles and uncover gene networks.Key words: Data Mining, Multilevel

15、 Association Rules, Gene Ontology, MAGO-FP Algorithm目 錄摘 要IABSTRACTII1 緒 論1.1 研究背景與意義(1)1.2 關(guān)聯(lián)規(guī)則挖掘研究進(jìn)展(2)1.3 生物數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘的基本步驟(11)1.4 論文組織結(jié)構(gòu)(14)2 關(guān)聯(lián)規(guī)則挖掘算法2.1 關(guān)聯(lián)規(guī)則的定義和相關(guān)概念(15)2.2 兩種經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法(17)2.3 多層關(guān)聯(lián)規(guī)則的定義和相關(guān)概念(25)2.4 兩種經(jīng)典的多層關(guān)聯(lián)規(guī)則挖掘算法(28)2.5 小結(jié)(31)3 GENE ONTOLOGY結(jié)構(gòu)下優(yōu)化的多層關(guān)聯(lián)規(guī)則挖掘算法3.1 基于 Apriori 算法的多層關(guān)

16、聯(lián)規(guī)則挖掘算法的局限性(32)3.2 基因本體論（Gene Ontology）及其概念分層結(jié)構(gòu)(32)3.3 MAGO-FP算法(39)3.4 小結(jié)(44)4 MAGO-FP算法的實(shí)驗(yàn)分析4.1 實(shí)驗(yàn)平臺(tái)與過程(45)4.2 性能優(yōu)勢(shì)分析(45)4.3 實(shí)驗(yàn)結(jié)果與分析(46)4.4 小結(jié)(48)5 結(jié) 論(50)致 謝(51)參考文獻(xiàn)(52)附錄1（攻讀學(xué)位期間發(fā)表論文目錄）(60)611 緒 論1.1 研究背景與意義生命科學(xué)近年來獲得突破性進(jìn)展1，隨著生物學(xué)和醫(yī)學(xué)的迅速發(fā)展，生物數(shù)據(jù)呈指數(shù)級(jí)增長(zhǎng)，無論是在數(shù)量上還是在質(zhì)量上都極大的豐富了生命科學(xué)的數(shù)據(jù)資源，提供了揭開生命奧秘的數(shù)據(jù)基礎(chǔ)。然而生

17、物數(shù)據(jù)種類豐富，高通量，維數(shù)高，本質(zhì)上具有異質(zhì)性與網(wǎng)絡(luò)性，遠(yuǎn)遠(yuǎn)超出傳統(tǒng)的分析方法的能力和速度，其處理、挖掘、分析和理解日益迫切。如何分析這些具有豐富內(nèi)涵的數(shù)據(jù)并從中獲得關(guān)生物結(jié)構(gòu)和功能的信息，從中得到對(duì)人類有益的信息，是生物研究的瓶頸，是當(dāng)前研究所面臨的一個(gè)嚴(yán)峻挑戰(zhàn)。生物信息學(xué)是在此背景下發(fā)展起來的綜合運(yùn)用生物學(xué)、數(shù)學(xué)、信息學(xué)以及計(jì)算機(jī)科學(xué)等諸多學(xué)科理論方法的嶄新交叉學(xué)科，是在生命科學(xué)的研究中,以計(jì)算機(jī)科學(xué)知識(shí)為輔導(dǎo)工具對(duì)生物信息進(jìn)行儲(chǔ)存、檢索和分析的科學(xué)，是當(dāng)今生命科學(xué)和自然科學(xué)的重大前沿領(lǐng)域之一。它包含兩方面的內(nèi)容，一方面是對(duì)海量數(shù)據(jù)的搜索、管理、服務(wù)，即“管好數(shù)據(jù)”；另一方面從中發(fā)現(xiàn)規(guī)律

18、，即“讀懂”數(shù)據(jù)。隨著人類基因組計(jì)劃的完成，生物信息學(xué)的研究重點(diǎn)已經(jīng)從開始的序列分析、數(shù)據(jù)庫查詢逐漸向生物信息的挖掘、表達(dá)、數(shù)據(jù)多樣性分析的方向發(fā)展，高通量實(shí)驗(yàn)數(shù)據(jù)分析成為目前生物信息學(xué)研究的熱點(diǎn)和重點(diǎn)。這些數(shù)據(jù)是通過一些高通量實(shí)驗(yàn)測(cè)量技術(shù)得到的，往往包含著幾千個(gè)基因或基因片斷和幾十個(gè)屬性。高通量實(shí)驗(yàn)數(shù)據(jù)，無論是轉(zhuǎn)錄水平上還是蛋白質(zhì)水平上，其中都蘊(yùn)含著豐富的生物學(xué)知識(shí)，可以幫助我們理解基因、理解生物、理解細(xì)胞等等，例如某疾病是由什么基因引起的、細(xì)胞是處于正常還是惡化狀態(tài)、藥物對(duì)腫瘤細(xì)胞是否有效等。由于越來越多數(shù)據(jù)得以公開，人們迫切希望通過數(shù)據(jù)挖掘技術(shù)在這些具有豐富內(nèi)涵的海量數(shù)據(jù)中獲得有益的信息

19、。對(duì)高通量實(shí)驗(yàn)數(shù)據(jù)的分析可以獲取基因功能和基因表達(dá)調(diào)控信息，這是生物信息學(xué)的重大挑戰(zhàn)之一，也是基因組學(xué)、蛋白質(zhì)組學(xué)的相關(guān)實(shí)驗(yàn)技術(shù)能夠在生物醫(yī)學(xué)領(lǐng)域中廣泛應(yīng)用的關(guān)鍵原因之一，它們?cè)卺t(yī)學(xué)臨床診斷、藥物療效判斷、揭示疾病發(fā)生機(jī)制等方面有重要的應(yīng)用。數(shù)據(jù)挖掘2是新興的一種科學(xué)計(jì)算技術(shù)與數(shù)據(jù)分析方法，它能夠有效地從存有海量信息的數(shù)據(jù)庫中提取隱含的、事先未知的潛在的和有用的信息和知識(shí)，經(jīng)過多年的研究與發(fā)展，它已經(jīng)成為一項(xiàng)很重要的數(shù)據(jù)分析工具。作為一種以數(shù)據(jù)庫、統(tǒng)計(jì)學(xué)和人工智能學(xué)為基礎(chǔ)的新興技術(shù)，數(shù)據(jù)挖掘給基因組學(xué)家們提供了前所未有的數(shù)據(jù)分析工具，為基因和蛋白信息的分析和提取提供了強(qiáng)有力的手段。生物信息學(xué)、

20、數(shù)據(jù)挖掘兩者的結(jié)合，不論是現(xiàn)在還是將來，不論在理論上還是應(yīng)用上都具有十分重要的意義。因此生物數(shù)據(jù)挖掘日益重要，逐漸成為生物信息學(xué)研究領(lǐng)域的關(guān)鍵。數(shù)據(jù)挖掘的常用技術(shù)中，聚類和分類技術(shù)已經(jīng)成為基因鑒定、功能預(yù)測(cè)和基因表達(dá)分析等研究中最常用的手段。而關(guān)聯(lián)規(guī)則挖掘技術(shù)，作為分析海量數(shù)據(jù)庫中項(xiàng)目間相關(guān)聯(lián)系的重要技術(shù)，目前在生物學(xué)領(lǐng)域中并未得到廣泛應(yīng)用，相應(yīng)的算法也不夠成熟。與數(shù)據(jù)挖掘的其他技術(shù)相比，關(guān)聯(lián)規(guī)則更能挖掘出基因間的網(wǎng)絡(luò)結(jié)構(gòu)。因?yàn)榫垲惡头诸惣夹g(shù)只能顯示數(shù)據(jù)中基因群普遍的表現(xiàn)形式；而關(guān)聯(lián)規(guī)則的頻繁模式集不但可以顯示出表現(xiàn)形式，其所產(chǎn)生的推論規(guī)則更可以描述基因間的聯(lián)系；另外還有支持度和置信度參數(shù)可供

21、生物學(xué)家作評(píng)價(jià)標(biāo)準(zhǔn)。同時(shí)，關(guān)聯(lián)規(guī)則能有效的克服聚類等分析技術(shù)只能將基因分到某一群，往往忽略了基因可能同時(shí)參與幾個(gè)生化路徑的缺點(diǎn)。但是，目前的生物數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘算法仍然存在著挖掘結(jié)果缺乏很強(qiáng)的生物學(xué)意義，候選規(guī)則冗余度高和挖掘計(jì)算效率低等不足，迫切需要針對(duì)生物數(shù)據(jù)的特殊性建立適用的關(guān)聯(lián)規(guī)則挖掘算法。本研究擬選用Gene Ontology完善的概念層次結(jié)構(gòu)3，通過對(duì)FP_Growth算法4進(jìn)行擴(kuò)展，期望實(shí)現(xiàn)一種優(yōu)化的生物數(shù)據(jù)多層關(guān)聯(lián)規(guī)則挖掘算法：能有效地克服傳統(tǒng)的、基于Apriori5的多層關(guān)聯(lián)規(guī)則挖掘算法的缺點(diǎn)，大幅提高挖掘效率；并且保證挖掘結(jié)果具有良好的生物學(xué)意義。因此，擬提出的新算法預(yù)期在

22、基因表達(dá)分析、基因調(diào)控網(wǎng)絡(luò)等研究中具有廣泛的應(yīng)用價(jià)值。1.2 關(guān)聯(lián)規(guī)則挖掘研究進(jìn)展關(guān)聯(lián)規(guī)則挖掘是發(fā)現(xiàn)大量數(shù)據(jù)中項(xiàng)集之間有趣的關(guān)聯(lián)或相關(guān)關(guān)系。它是數(shù)據(jù)挖掘中的一個(gè)重要問題，其研究目標(biāo)是找出滿足最小支持度和最小可信度要求的關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則是形如AB的蘊(yùn)涵式，其中A、B都是項(xiàng)集。一般地,關(guān)聯(lián)規(guī)則發(fā)現(xiàn)分為找出所有的頻繁項(xiàng)集和由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則兩個(gè)步驟，其中找出所有的頻繁項(xiàng)集是關(guān)聯(lián)規(guī)則算法的性能瓶頸。因此絕大部分對(duì)關(guān)聯(lián)規(guī)則算法的研究都集中在第一步，即如何在保證精度的基礎(chǔ)上提高算法的運(yùn)行效率，其中精度是指所找出的頻繁項(xiàng)集的滿足要求的程度。1993年，Agrawal等提出了關(guān)聯(lián)規(guī)則發(fā)現(xiàn)問題6，同時(shí)提

23、出了第一個(gè)頻繁項(xiàng)集發(fā)現(xiàn)算法。此后，在各種問題背景下，圍繞著提高算法效率和結(jié)果的有用性（即用戶對(duì)其感興趣程度），研究者們提出了各種頻繁項(xiàng)集發(fā)現(xiàn)算法7,8。根據(jù)這些算法的研究重點(diǎn)不同，可將其分為基本頻繁項(xiàng)集發(fā)現(xiàn)算法和增強(qiáng)頻繁項(xiàng)集發(fā)現(xiàn)算法。基本頻繁項(xiàng)集發(fā)現(xiàn)算法致力于設(shè)計(jì)各種算法框架，高效地發(fā)現(xiàn)所有支持度大于某個(gè)不變的最小支持度的頻繁項(xiàng)集。但是它存在一些缺陷，比如所發(fā)現(xiàn)的頻繁項(xiàng)集的有用性不高、發(fā)現(xiàn)的頻繁項(xiàng)集數(shù)量過多、遺漏用戶感興趣的頻繁項(xiàng)集等等。增強(qiáng)頻繁項(xiàng)集發(fā)現(xiàn)算法致力于提高發(fā)現(xiàn)結(jié)果的有用性，它通過引入概念層次結(jié)構(gòu)、約束條件、可變支持度等方式來克服基本頻繁項(xiàng)集算法的缺陷。基本頻繁項(xiàng)集發(fā)現(xiàn)算法是在單數(shù)據(jù)

24、庫、單概念層次和最基本要求（即使用相同的最小支持度發(fā)現(xiàn)所有頻繁項(xiàng)集）的條件下發(fā)現(xiàn)頻繁項(xiàng)集，它是其它更“高級(jí)”頻繁項(xiàng)集發(fā)現(xiàn)算法的基礎(chǔ)。根據(jù)算法提出的時(shí)間和算法原理的不同，可將它們細(xì)分為Apriori算法出現(xiàn)之前的算法、Apriori類算法、基于分塊的算法、基于采樣的算法、新出現(xiàn)的高性能算法、基于最大頻繁項(xiàng)集的算法和頻繁封閉項(xiàng)集發(fā)現(xiàn)算法等。其中后三類算法在分析強(qiáng)相關(guān)性數(shù)據(jù)時(shí)有明顯的性能優(yōu)勢(shì)。1993年，Agrawal等提出面向單個(gè)事務(wù)的頻繁項(xiàng)集發(fā)現(xiàn)算法AIS8。1995年，Houtsma等提出面向集合的頻繁項(xiàng)集發(fā)現(xiàn)算法SETM9。這是兩種在Apriori算法出現(xiàn)之前的算法，它們根據(jù)每個(gè)事務(wù)中的已發(fā)

25、現(xiàn)頻繁項(xiàng)集和此事務(wù)中的其它項(xiàng)生成候選頻繁項(xiàng)集，因此生成的非候選頻繁項(xiàng)集數(shù)量很多，導(dǎo)致性能在各種情況下都不如Apriori算法，因此沒有得到實(shí)際應(yīng)用。1994年，Agrawal等提出簡(jiǎn)單高效的頻繁項(xiàng)集發(fā)現(xiàn)算法Apriori5。該算法是基于廣度優(yōu)先搜索策略的，它利用了頻繁項(xiàng)集的反單調(diào)性頻繁項(xiàng)集的子集必定是頻繁的，通過在第(k-1)次掃描數(shù)據(jù)庫后所得到的長(zhǎng)度為(k-1)的頻繁項(xiàng)集（簡(jiǎn)記為(k-1)-頻繁項(xiàng)集，下同）生成k-候選頻繁項(xiàng)集，然后在第k次掃描數(shù)據(jù)庫時(shí)統(tǒng)計(jì)k-候選頻繁項(xiàng)集的頻繁度。Apriori算法在巨型數(shù)據(jù)庫上有良好性能。但是，由于Apriori算法使用生成-檢驗(yàn)循環(huán)的方式發(fā)現(xiàn)頻繁項(xiàng)集，因

26、此當(dāng)數(shù)據(jù)庫中頻繁項(xiàng)集的密度比較大或最長(zhǎng)頻繁項(xiàng)集比較長(zhǎng)時(shí)，Apriori算法不能避免所生成的候選頻繁項(xiàng)集數(shù)量的指數(shù)爆炸，導(dǎo)致性能急劇下降；而且Apriori算法需要多次掃描數(shù)據(jù)庫，造成沉重的I/O負(fù)擔(dān)。Agrawal等還發(fā)現(xiàn)，Apriori算法的最大運(yùn)行時(shí)間開銷階段是剛開始的幾次生成-檢驗(yàn)循環(huán)，特別是發(fā)現(xiàn)2-頻繁項(xiàng)集的循環(huán)，在此階段生成了大量無效的候選頻繁項(xiàng)集，限制了算法的效率。大部分改進(jìn)的算法把注意力集中在生成大項(xiàng)目集的優(yōu)化上，主要有四種優(yōu)化方法:基于劃分的方法，基于hash表的方法，減少對(duì)交易數(shù)據(jù)庫的遍歷次數(shù)，基于隨機(jī)采樣技術(shù)的方法。1995年Savasere等設(shè)計(jì)了一個(gè)基于劃分原理的Par

27、tition算法10。Partition算法將原數(shù)據(jù)庫邏輯地分成若干個(gè)互不相交的子數(shù)據(jù)庫，其中每個(gè)子數(shù)據(jù)庫都充分小，足以放入內(nèi)存。由于任何頻繁項(xiàng)集至少在其中一個(gè)子數(shù)據(jù)庫中是頻繁的，所以可先分別發(fā)現(xiàn)每個(gè)子數(shù)據(jù)庫中的頻繁項(xiàng)集，然后將這些頻繁項(xiàng)集匯總作為總候選頻繁項(xiàng)集，再掃描一遍原數(shù)據(jù)庫發(fā)現(xiàn)其中滿足全局支持度條件的頻繁項(xiàng)集。由于每個(gè)子數(shù)據(jù)庫可放入內(nèi)存，所以發(fā)現(xiàn)其中的頻繁項(xiàng)集不需要使用非常耗時(shí)的I/O操作，算法總體執(zhí)行速度比較快。另外，Partition算法還是一種本質(zhì)并行算法。不過，當(dāng)子數(shù)據(jù)庫數(shù)目增大時(shí)，Partition算法生成的無效總候選頻繁項(xiàng)集數(shù)目快速增長(zhǎng)，導(dǎo)致效率降低，因此Partition

28、算法在較大數(shù)據(jù)庫上的性能不如Apriori算法。Brin等提出DIC（動(dòng)態(tài)項(xiàng)集計(jì)數(shù)）算法，可視為一種串行化的Partition算法11。采用哈希修剪技術(shù)在快速發(fā)現(xiàn)2-項(xiàng)集的過程中十分有效，Park等在這個(gè)方法的基礎(chǔ)上引入哈希技術(shù)來改進(jìn)產(chǎn)生2-項(xiàng)集的方法，提出Apriori算法的一種改進(jìn)DHP（直接亂散與刪剪）算法12。通過使用哈希技術(shù)，DHP比Apriori算法少生成一個(gè)數(shù)量級(jí)的2-候選頻繁項(xiàng)集，從而提高了算法性能。另外，由于所生成的2-候選頻繁項(xiàng)集數(shù)量大大減小，所以DHP算法可在發(fā)現(xiàn)2-頻繁項(xiàng)集之后就從數(shù)據(jù)庫中刪掉無需再考慮的事務(wù)和項(xiàng)。AprioriTID算法13與Apriori算法的思路基

29、本一致，不同在于：前者在經(jīng)過一次掃描數(shù)據(jù)庫后，不再利用數(shù)據(jù)庫來計(jì)算項(xiàng)目集的支持度，而利用候選項(xiàng)集來計(jì)算，因而減少了對(duì)交易數(shù)據(jù)庫的遍歷次數(shù)，提高了效率。基于采樣的技術(shù)，是先利用從數(shù)據(jù)庫中抽取出來的采樣，生成一些可能的規(guī)則，然后再針對(duì)數(shù)據(jù)庫中剩余的部分驗(yàn)證這些規(guī)則。Toivenen提出的隨機(jī)抽樣技術(shù)14可以節(jié)約相當(dāng)可觀的I/O代價(jià)，但是一個(gè)很大的缺點(diǎn)就是產(chǎn)生的結(jié)果不精確，即存在所謂的數(shù)據(jù)扭曲(data skew)。分布在同一頁面上的數(shù)據(jù)時(shí)常是高度相關(guān)的，可能不能表示整個(gè)數(shù)據(jù)庫中模式的分布，由此而導(dǎo)致的是采樣5%的交易數(shù)據(jù)所花費(fèi)的代價(jià)可能同掃描一遍數(shù)據(jù)庫相近。Lin和Dunham討論了反扭曲(Ant

30、i-skew)算法來挖掘關(guān)聯(lián)規(guī)則15，他們引入的技術(shù)使得掃描數(shù)據(jù)庫的次數(shù)少于2次。Brin等16提出的算法使用比傳統(tǒng)算法少的掃描遍數(shù)來發(fā)現(xiàn)頻繁項(xiàng)集，同時(shí)比基于采樣的方法使用更少的候選集，這些改進(jìn)了算法在低層的效率。具體的考慮是：在計(jì)算k-項(xiàng)集時(shí)，一旦認(rèn)為某個(gè)(k+1)-項(xiàng)集可能是頻繁項(xiàng)集時(shí)，就并行地計(jì)算這個(gè)(k+1)-項(xiàng)集的支持度。該算法需要的總的掃描次數(shù)通常少于最大的頻繁項(xiàng)集的項(xiàng)數(shù)。這里他們也使用了雜湊技術(shù)，并提出產(chǎn)生“相關(guān)規(guī)則”（Correlation Rules）的一個(gè)新方法。Zaki等認(rèn)為，在頻繁項(xiàng)集發(fā)現(xiàn)過程中使用采樣技術(shù)至少可提高一個(gè)數(shù)量級(jí)的速度，而且精度損失不多17。1996年，T

31、oivonen提出一種基于采樣的頻繁項(xiàng)集發(fā)現(xiàn)算法18，其基本思想是對(duì)數(shù)據(jù)庫進(jìn)行采樣，形成采樣數(shù)據(jù)庫；然后用較小的最小支持度發(fā)現(xiàn)采樣數(shù)據(jù)庫中的頻繁項(xiàng)集S；再將S和它的負(fù)邊界Bd(S)合并，構(gòu)成候選頻繁項(xiàng)集SBd(S)；接著掃描一遍原數(shù)據(jù)庫從SBd(S)中發(fā)現(xiàn)所有頻繁項(xiàng)集S/：如果其中Bd(S)包含頻繁項(xiàng)集，那么說明原數(shù)據(jù)庫中可能存在還未被發(fā)現(xiàn)的頻繁項(xiàng)集，這時(shí)需要用公式S/=S/Bd(S/)疊代計(jì)算直到S/不再增大，然后將S/作為候選集再掃描一遍原數(shù)據(jù)庫，發(fā)現(xiàn)所有被遺漏的頻繁項(xiàng)集。此算法在一般情況下只需掃描數(shù)據(jù)庫一次，在最差情況下需要掃描兩次。1997年，Park等提出兩個(gè)可調(diào)節(jié)精度的算法DS和S

32、H19。其中DS算法可視為DHP算法加入采樣技術(shù)之后的推廣。DS和SH算法可用于為了提高效率而允許損失一些精度的場(chǎng)合。Apriori類算法在數(shù)據(jù)庫為高密度、長(zhǎng)模式或低支持度等情況下性能急劇下降，針對(duì)這個(gè)問題，一些新的高性能頻繁項(xiàng)集發(fā)現(xiàn)算法被提出來。2000年，Agarwal等提出一種全新的高效算法TreeProjection20,21。此算法構(gòu)造一個(gè)詞典樹，并根據(jù)已發(fā)現(xiàn)的頻繁項(xiàng)集，將數(shù)據(jù)庫投影到一組精簡(jiǎn)的子數(shù)據(jù)庫上。由于詞典樹提升了檢驗(yàn)候選頻繁項(xiàng)集的效率，并且此算法還使用其它各種提高效率的技術(shù)，所以TreeProjection算法比Apriori算法的性能高一個(gè)數(shù)量級(jí)。2000年，Han等提出

33、一種不需要生成候選頻繁項(xiàng)集的算法FP_Growth4。此算法是基于深度優(yōu)先搜索策略的：首先掃描兩遍數(shù)據(jù)庫，生成信息高度壓縮的高頻模式樹，該樹中仍保留了項(xiàng)集的關(guān)聯(lián)信息；然后在其上遞歸生成條件高頻模式樹，同時(shí)找出所有頻繁項(xiàng)集。由于此算法不需要生成候選頻繁項(xiàng)集，避免了Apriori類算法本質(zhì)具有的候選頻繁項(xiàng)集數(shù)量指數(shù)爆炸情況，對(duì)于挖掘長(zhǎng)的和短的頻繁模式，它是有效和可伸縮的，并且大約比Apriori算法快一個(gè)數(shù)量級(jí)。但Apriori算法對(duì)空間的需求比較低，對(duì)數(shù)據(jù)庫規(guī)模的伸縮性要好于FP_Growth算法。兩者各有所長(zhǎng)。如果一個(gè)頻繁項(xiàng)集不是其它頻繁項(xiàng)集的真子集，那么稱此頻繁項(xiàng)集為最大頻繁項(xiàng)集。最大頻繁項(xiàng)

34、集集合的每一個(gè)元素的所有子集的集合的并集就是完整的頻繁項(xiàng)目集集合，但每一個(gè)頻繁項(xiàng)目集的支持度不能由最大頻繁項(xiàng)集推導(dǎo)出來，因此還需要對(duì)數(shù)據(jù)庫掃描一次并進(jìn)行計(jì)數(shù)，這一趟掃描的時(shí)間花銷通常很大。典型的基于最大頻繁項(xiàng)目集的算法是Zaki等在1997年提出的算法ClusterApr22。該算法首先使用聚類技術(shù)將相關(guān)的項(xiàng)集分組，以此得到最大頻繁項(xiàng)集集合的超集，然后生成此超集的所有子集，將這些子集作為候選頻繁項(xiàng)集，最后掃描一遍數(shù)據(jù)庫驗(yàn)證此候選頻繁項(xiàng)集。ClusterApr算法的性能優(yōu)于Apriori算法，遜于Partition算法。而后，Shen等提出與Zaki算法類似的基于最大頻繁項(xiàng)集的頻繁項(xiàng)集發(fā)現(xiàn)算法2

35、3，并且此算法具有本質(zhì)并行性。封閉項(xiàng)集是一組事務(wù)都包含的項(xiàng)的最大項(xiàng)集。一個(gè)數(shù)據(jù)庫的頻繁封閉項(xiàng)集集合與其頻繁項(xiàng)集集合的信息量相等，但是前者比后者小得多，因此發(fā)現(xiàn)頻繁封閉項(xiàng)集能夠減少數(shù)據(jù)庫的掃描遍數(shù)和CPU開銷，從而提升頻繁項(xiàng)集發(fā)現(xiàn)的效率，并大幅減少輸出冗余信息。1999年，Pasquier等提出基于Apriori算法框架的頻繁封閉項(xiàng)集發(fā)現(xiàn)算法Close24。相對(duì)于Apriori算法，Close算法在分析強(qiáng)相關(guān)數(shù)據(jù)時(shí)具有明顯的性能優(yōu)勢(shì)，可將數(shù)據(jù)庫掃描遍數(shù)減少到原來遍數(shù)的1/4到1/2。1999年，Zaki等提出使用垂直數(shù)據(jù)庫結(jié)構(gòu)的頻繁封閉項(xiàng)集發(fā)現(xiàn)算法CHARM25。Close算法和CHARM算法在

36、發(fā)現(xiàn)長(zhǎng)模式或低支持度閾值時(shí)效率不高。2000年，Pei等提出基于FP_Growth算法框架的頻繁封閉項(xiàng)集發(fā)現(xiàn)算法CLOSET26。項(xiàng)一般具有概念層次關(guān)系。當(dāng)存在概念層次關(guān)系時(shí)，用戶通常對(duì)包含不同概念層次的項(xiàng)的規(guī)則感興趣，并稱這種規(guī)則為廣義關(guān)聯(lián)規(guī)則或多層關(guān)聯(lián)規(guī)則發(fā)現(xiàn)。廣義關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法提高性能的關(guān)鍵也在于廣義頻繁項(xiàng)集發(fā)現(xiàn)的效率。1995年，Srikant等提出直接推廣Apriori算法的廣義頻繁項(xiàng)集發(fā)現(xiàn)算法Cumulate算法27。此算法將數(shù)據(jù)庫中所有事務(wù)的每個(gè)項(xiàng)的所有高層次概念項(xiàng)都加入到此事務(wù)中，形成擴(kuò)展事務(wù)，然后再套用Apriori算法。由于和高層次概念有關(guān)的項(xiàng)集一般有較大的支持度，和低層

37、次概念有關(guān)的項(xiàng)集一般有較小的支持度，而Cumulate算法對(duì)不同類型項(xiàng)集只能使用相同的最小支持度，導(dǎo)致其發(fā)現(xiàn)結(jié)果不太有用。1995年，Han等在Aprior算法基礎(chǔ)上提出多層頻繁項(xiàng)集發(fā)現(xiàn)算法ML_T2L128。該算法首先將所有項(xiàng)替換為最高層次上的項(xiàng)，同時(shí)設(shè)置較高的最小支持度，然后找出滿足支持度要求的第一層次頻繁項(xiàng)集L1。在L1基礎(chǔ)上，將所有項(xiàng)替換為第二層次上的項(xiàng)，降低最小支持度，找出第二層次頻繁項(xiàng)集L2。反復(fù)進(jìn)行，直到Lk為空。在傳統(tǒng)的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)中，用戶僅僅設(shè)置了初始閾值（包括支持度，置信度），然后就是等待系統(tǒng)交付最終的結(jié)果。系統(tǒng)往往需要經(jīng)過幾個(gè)小時(shí)或者更長(zhǎng)多時(shí)間來產(chǎn)生大量的關(guān)聯(lián)規(guī)則，而在這

38、些關(guān)聯(lián)規(guī)則中，往往只有小部分是用戶關(guān)心的。顯然，如果用戶能對(duì)關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)過程進(jìn)行指導(dǎo)，使得產(chǎn)生的關(guān)聯(lián)規(guī)則就是用戶需要的，這樣不僅規(guī)則的數(shù)目大大減少了，而且挖掘的效率更高29。1994年，Klemettinen等提出在關(guān)聯(lián)規(guī)則中應(yīng)用模板以發(fā)現(xiàn)用戶感興趣的關(guān)聯(lián)規(guī)則30。模板是用戶自定義詞匯表示的規(guī)則，其中詞匯使用項(xiàng)集進(jìn)行定義。如果一條規(guī)則滿足模板，那么這條規(guī)則就是用戶感興趣的。但是由于用戶自定義模板的復(fù)雜性，頻繁項(xiàng)集發(fā)現(xiàn)算法難以高效地檢驗(yàn)一個(gè)頻繁項(xiàng)集是否滿足模板。1995年，F(xiàn)u提出元規(guī)則指導(dǎo)的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)31。元規(guī)則可視為Klemettinen等提出的模板概念的一種簡(jiǎn)單推廣。這種類型的發(fā)現(xiàn)算法

39、首先由用戶給定要發(fā)現(xiàn)的關(guān)聯(lián)規(guī)則的元模式或模板，然后根據(jù)這些模板在數(shù)據(jù)庫中發(fā)現(xiàn)與模板相適應(yīng)的實(shí)際存在的關(guān)聯(lián)規(guī)則。Fu提出了兩個(gè)相應(yīng)的算法：大謂詞增長(zhǎng)算法和直接p謂詞剝?cè)囁惴ārikant等研究了在提供布爾表達(dá)式約束情況下的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)問題32。這種布爾表達(dá)式約束允許用戶指定他所感興趣的關(guān)聯(lián)規(guī)則的集合，這種約束不僅可以用來對(duì)事務(wù)數(shù)據(jù)庫進(jìn)行預(yù)加工，而且可以把它集成在挖掘算法內(nèi)部，從而提高算法的執(zhí)行效率，文中根據(jù)這種集成方式的不同給出了三種實(shí)現(xiàn)項(xiàng)約束的算法：Multiple_Joins、Recorder、Direct。其中項(xiàng)約束就是要求所發(fā)現(xiàn)的頻繁項(xiàng)集必須包含或不包含用戶所指定的若干項(xiàng)。這三種算法推

40、廣了Apriori算法的候選頻繁項(xiàng)集生成過程，在生成候選頻繁項(xiàng)集時(shí)檢驗(yàn)其滿足項(xiàng)約束的情況。崔立新提出Direct算法的改進(jìn)算法Separate33。用戶往往只對(duì)滿足一定約束條件的頻繁項(xiàng)集感興趣，因此如果頻繁項(xiàng)集發(fā)現(xiàn)算法只發(fā)現(xiàn)滿足用戶指定約束條件的頻繁項(xiàng)集，那么將大量節(jié)省用戶處理不感興趣的頻繁項(xiàng)集的時(shí)間，同時(shí)也可提高算法執(zhí)行速度。1998年，Ng等在分析一般挖掘過程缺乏用戶反饋與指導(dǎo)的弊端的基礎(chǔ)上，提出兩階段的關(guān)聯(lián)規(guī)則挖掘系統(tǒng)結(jié)構(gòu)，提出并分析了反單調(diào)性、簡(jiǎn)潔性這兩種性質(zhì)的約束。這里，約束形式可以是項(xiàng)的合取和否定，以及求均值等集合操作29。按照約束的性質(zhì)將約束分為反單調(diào)、簡(jiǎn)潔、頑固的三大類，同時(shí)將

41、反單調(diào)、簡(jiǎn)潔性的約束進(jìn)行組合，將其運(yùn)用到頻繁項(xiàng)集的剪枝過程中，提出了可使用單維變量約束的CAP算法。該算法是基于Apriori算法的，通過使用約束對(duì)中間頻繁項(xiàng)集進(jìn)行剪枝，使得頻繁項(xiàng)集的發(fā)現(xiàn)效率提高了一個(gè)數(shù)量級(jí)。隨后Lakshmanan等提出可使用二維變量約束的頻繁項(xiàng)集發(fā)現(xiàn)算法34。由于二維變量約束大部分不滿足反單調(diào)性、或者簡(jiǎn)潔性，因此提出一個(gè)“類簡(jiǎn)潔性”約束，先將二維的約束轉(zhuǎn)換或弱化成兩個(gè)一維的簡(jiǎn)潔性約束，然后再運(yùn)用CAP算法。簡(jiǎn)單的說，就是把多維約束轉(zhuǎn)換成一維約束，這里提出了一個(gè)轉(zhuǎn)換的基本思路。在對(duì)約束的性質(zhì)討論上，前后共提出五類性質(zhì)的約束，分別是反單調(diào)的、單調(diào)的、簡(jiǎn)潔的、可轉(zhuǎn)變的、不可轉(zhuǎn)變

42、的，針對(duì)這些性質(zhì)，關(guān)聯(lián)規(guī)則挖掘算法又有了很大發(fā)展35,36,37。Jean-Francois等人提出一個(gè)“負(fù)邊界”的思想38,39,40,41,42，將單調(diào)約束與反單調(diào)約束結(jié)合起來，提出了一個(gè)在Apriori基礎(chǔ)上的實(shí)現(xiàn)框架，同時(shí)論證了將反單調(diào)約束推進(jìn)到Apriori算法中是有利的，論證了free集是一種反單調(diào)的約束。Leung等43提出了一個(gè)利用FP樹實(shí)現(xiàn)簡(jiǎn)潔約束的算法FPS，而且能實(shí)現(xiàn)復(fù)雜的簡(jiǎn)潔約束，有很高的性能。Pei等提出可使用可轉(zhuǎn)變約束的頻繁項(xiàng)集發(fā)現(xiàn)算法（算法FICM、FICA）44。其基本思想是對(duì)項(xiàng)集進(jìn)行某種次序的排序，使得約束滿足反單調(diào)性或單調(diào)性。可轉(zhuǎn)變的約束可以在FP_Grow

43、th算法框架中實(shí)現(xiàn)，不能在Apriori算法框架中實(shí)現(xiàn)。該算法提出一種前綴增長(zhǎng)函數(shù)（Prefix Increasing Function），利用該函數(shù)，可以比較容易的判斷一些形式復(fù)雜的約束函數(shù)是否是可轉(zhuǎn)變的，是哪種可轉(zhuǎn)變的。這里，將可轉(zhuǎn)變的約束細(xì)分為單調(diào)可轉(zhuǎn)變的、反單調(diào)可轉(zhuǎn)變的、強(qiáng)可轉(zhuǎn)變的三類。該算法不能解決多個(gè)需要不同方式排序的可轉(zhuǎn)變約束。支持度約束也是一種反單調(diào)的約束。Apriori算法適用的前提之一是對(duì)于所有頻繁項(xiàng)集使用相同的最小支持度。如果在數(shù)據(jù)庫中存在出現(xiàn)頻率較低的項(xiàng)（稱為稀疏項(xiàng)），同時(shí)用戶對(duì)這些稀疏項(xiàng)又比較感興趣，那么需要使用可變的最小支持度以發(fā)現(xiàn)包含稀疏項(xiàng)的頻繁項(xiàng)集，同時(shí)不發(fā)現(xiàn)太

44、多的用戶不感興趣的頻繁項(xiàng)集。Lee將數(shù)據(jù)庫根據(jù)項(xiàng)出現(xiàn)頻率分為幾部分，然后對(duì)每部分應(yīng)用不同的最小支持度進(jìn)行頻繁項(xiàng)集發(fā)現(xiàn)。此方法難以發(fā)現(xiàn)跨越不同部分的頻繁項(xiàng)集。而Han等將若干相關(guān)的稀疏項(xiàng)合并為高層次概念的項(xiàng)，以增加稀疏項(xiàng)的支持度，但這種方法無法發(fā)現(xiàn)包含單個(gè)稀疏項(xiàng)的頻繁項(xiàng)集。1999年，Liu等提出的MSApriori算法是Apriori算法的一種推廣45。此算法賦予每個(gè)項(xiàng)一個(gè)最小項(xiàng)支持度（MIS），并以頻繁項(xiàng)集所包含的項(xiàng)的最小項(xiàng)支持度作為頻繁項(xiàng)集支持度的推廣定義。通過將項(xiàng)根據(jù)其MIS值從小到大排序，就可滿足推廣的頻繁項(xiàng)集的逆單調(diào)性。2000年，Wang等提出實(shí)現(xiàn)非統(tǒng)一的支持度（support）約

45、束的算法Adaptive Apriori46，將Apriori算法推廣到使用可變的最小支持度的情況，這樣可以避免很多“無意義”的中間頻繁項(xiàng)集的生成，使得結(jié)果對(duì)于用戶更有意義。Apriori算法首先解決的是布爾關(guān)聯(lián)規(guī)則(Boolean Associatin Rules)的挖掘問題，其后又?jǐn)U展到對(duì)數(shù)值型關(guān)聯(lián)規(guī)則(Quantitative Association Rules)及分類關(guān)聯(lián)規(guī)則(Categorical Association Rules)的挖掘，與布爾關(guān)聯(lián)挖掘不同的是在挖掘前需要對(duì)數(shù)值及分類屬性進(jìn)行必要的預(yù)處理。長(zhǎng)模式頻繁集的發(fā)現(xiàn)，也有很多的進(jìn)展。1997年，Gunopulos等提出一種

46、可用于長(zhǎng)模式發(fā)現(xiàn)的隨機(jī)頻繁項(xiàng)集發(fā)現(xiàn)算法47。算法循環(huán)地試圖隨機(jī)擴(kuò)展一個(gè)工作項(xiàng)集，直到失敗。由于是隨機(jī)算法，所以此算法不能保證發(fā)現(xiàn)所有的長(zhǎng)模式，但能夠有效地發(fā)現(xiàn)其中的一部分，不過它不能處理內(nèi)存放不下的數(shù)據(jù)庫。Zaki等提出的MaxEclat和MaxClique算法使用Apriori算法框架，試圖在其生成-檢驗(yàn)循環(huán)開始前識(shí)別長(zhǎng)模式，以減少候選頻繁項(xiàng)集的生成數(shù)目。Lin等提出Pincer-Search算法48，此算法同樣使用Apriori算法框架，并在其生成-檢驗(yàn)循環(huán)中識(shí)別長(zhǎng)模式。1998年，Bayardo等提出專門的長(zhǎng)模式發(fā)現(xiàn)算法Max-Miner算法49，此算法按照啟發(fā)式知識(shí)對(duì)項(xiàng)進(jìn)行排序，以提高

47、發(fā)現(xiàn)長(zhǎng)模式的效率。在某些數(shù)據(jù)集上Max-Miner算法比Apriori算法快1到2個(gè)數(shù)量級(jí)，而且其運(yùn)行時(shí)間與最大頻繁項(xiàng)集數(shù)目和數(shù)據(jù)庫大小成線性關(guān)系，與最長(zhǎng)頻繁項(xiàng)集的長(zhǎng)度無關(guān)。由于關(guān)聯(lián)規(guī)則挖掘是一項(xiàng)非常耗時(shí)的工作，從而導(dǎo)致了很多并行算法的相關(guān)研究，這些并行算法的主要特征是充分利用并行系統(tǒng)的強(qiáng)大運(yùn)算能力，通過對(duì)發(fā)現(xiàn)頻繁集這個(gè)任務(wù)的有效分割提高算法的效率。頻繁項(xiàng)集發(fā)現(xiàn)算法發(fā)展到目前為止，已經(jīng)獲得了長(zhǎng)足的進(jìn)步。作為許多面向應(yīng)用的數(shù)據(jù)挖掘技術(shù)的基礎(chǔ)，提高頻繁項(xiàng)集發(fā)現(xiàn)算法的性能、滿足不同應(yīng)用背景下的不同要求，依然是一項(xiàng)值得研究的課題。另外，還有很多其他的關(guān)聯(lián)規(guī)則的研究。Liu等人提出利用X2檢驗(yàn)縮小規(guī)則數(shù)

48、量的方法50，Padmanabhan等人提出置信驅(qū)動(dòng)的關(guān)聯(lián)規(guī)則挖掘算法(Belief-Driven Method for Discovering Unexpected Pattern)51，同時(shí)提出了兩個(gè)算法EstMerge和Cumulate，解決泛化(generalized)關(guān)聯(lián)規(guī)則的問題。Savasere等52研究了挖掘否定關(guān)聯(lián)規(guī)則的問題，他們的方法是使用分組信息如項(xiàng)之間的層次關(guān)系，以及現(xiàn)有數(shù)據(jù)中的正關(guān)聯(lián)性來導(dǎo)出與正關(guān)聯(lián)中的項(xiàng)“相近”的項(xiàng)之間的否定規(guī)則。在使用關(guān)聯(lián)規(guī)則挖掘生物數(shù)據(jù)的研究方面，Creighton等53詳細(xì)闡述了將關(guān)聯(lián)規(guī)則挖掘技術(shù)應(yīng)用于生物學(xué)數(shù)據(jù)的方法，并指出了其在尋找基因間的

49、聯(lián)系、構(gòu)造基因調(diào)控網(wǎng)絡(luò)中的應(yīng)用前景；但并未涉及具體的算法討論。Kotala等54提出了使用優(yōu)化的數(shù)據(jù)結(jié)構(gòu)Peano-count Trees來挖掘微陣列芯片數(shù)據(jù)的關(guān)聯(lián)規(guī)則。Chen等55提到使用Apriori算法挖掘微陣列芯片數(shù)據(jù)，以進(jìn)行轉(zhuǎn)錄因子的預(yù)測(cè)；但由于關(guān)聯(lián)規(guī)則挖掘的過程中產(chǎn)生了大量的冗余規(guī)則，影響到了后續(xù)的分析應(yīng)用。Tuzhilin等56提到如何處理從微陣列芯片中挖掘出的大量關(guān)聯(lián)規(guī)則，并首次提出以概念分層來后續(xù)分類規(guī)則的想法。繼而，Tseng等57實(shí)現(xiàn)了使用概念分層的方法來歸納大量且復(fù)雜的規(guī)則，繼而引入多層關(guān)聯(lián)規(guī)則挖掘算法ML_T2L128來尋找基因間的隱含關(guān)系。候選項(xiàng)生成并驗(yàn)證的方式成

50、為該算法的性能瓶頸，使得它們的效率較低。而高通量生物實(shí)驗(yàn)中需一次性處理的候選模式往往長(zhǎng)度很大，支持度有時(shí)也較低，因此該算法用來處理生物數(shù)據(jù)效率并不理想。1.3 生物數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘的基本步驟一次高通量實(shí)驗(yàn)?zāi)塬@得細(xì)胞在某一條件下的全基因組表達(dá)數(shù)據(jù)，包含成千上萬個(gè)基因在細(xì)胞中的相對(duì)或絕對(duì)豐度，不同條件（細(xì)胞周期的不同階段、藥物作用時(shí)間、腫瘤類型、不同病人等）下的全基因組表達(dá)數(shù)據(jù)就構(gòu)成了一個(gè)G×N的數(shù)據(jù)矩陣M，通常情況下G>>N，其中元素xij表示第i個(gè)基因在第 j 個(gè)條件下的表達(dá)水平值，行向量 xi=(xi1,xi2,xiN)代表基因i在不同條件下的表達(dá)水平，列向量xj=(x

51、1j,x2j,xGj)代表某一條件下的各基因的表達(dá)水平。本文其它關(guān)于高通量生物數(shù)據(jù)的描述都以矩陣M為例（如圖1.1所示）。圖1.1 高通量生物數(shù)據(jù)矩陣按行來分析，關(guān)系可以表示為R(Gid, xi1,xi2,xiN)，其中，Gid表示的是標(biāo)識(shí)不同基因的基因名，xi1,xi2,xiN則表示不同基因在不同實(shí)驗(yàn)環(huán)境中的值。比較矩陣行的相似性或差別，如果發(fā)現(xiàn)兩個(gè)行相似，可以推測(cè)它們對(duì)應(yīng)的基因具有協(xié)同調(diào)節(jié)和功能相關(guān)性。聚類和分類分析正是基于行進(jìn)行分析。按列分析，關(guān)系可以表示為R(Tid, x1j,x2j,xGj)，其中，Tid表示不同的環(huán)境的標(biāo)識(shí)，而x1j,x2j,xGj則表示在環(huán)境Tid下各個(gè)基因的表達(dá)

52、水平。通過分析在同一環(huán)境下各個(gè)基因的關(guān)聯(lián)度，發(fā)現(xiàn)基因之間的關(guān)聯(lián)水平。對(duì)高通量生物數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘多是基于列進(jìn)行分析。從數(shù)據(jù)分析可知，高通量生物學(xué)實(shí)驗(yàn)數(shù)據(jù)反映的是基因在細(xì)胞中的相對(duì)或絕對(duì)豐度，是數(shù)值型數(shù)據(jù)，而傳統(tǒng)的購物籃交易數(shù)據(jù)可看作是布爾型數(shù)據(jù)，因而對(duì)于生物數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘與對(duì)交易數(shù)據(jù)進(jìn)行挖掘并不完全相同。對(duì)于數(shù)值型數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘最常用的是將其轉(zhuǎn)換為布爾關(guān)聯(lián)規(guī)則挖掘，目前對(duì)高通量生物數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘正是采用這類方法。生物數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘的基本步驟如下：一、數(shù)據(jù)預(yù)處理對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行關(guān)聯(lián)、聚類等分析之前，需要進(jìn)行預(yù)處理，包括對(duì)丟失數(shù)據(jù)進(jìn)行填補(bǔ)、清除不完整的數(shù)據(jù)或合并重復(fù)數(shù)據(jù)等數(shù)據(jù)清洗，

53、根據(jù)分析的目的進(jìn)行數(shù)據(jù)過濾，以及針對(duì)分析方法選擇合適的數(shù)據(jù)轉(zhuǎn)換方法等。1. 數(shù)據(jù)清洗：數(shù)據(jù)分析前必須進(jìn)行的一項(xiàng)工作，對(duì)于生物實(shí)驗(yàn)數(shù)據(jù)，目的是去除表達(dá)水平是負(fù)值或很小的數(shù)據(jù)、或者明顯的噪聲數(shù)據(jù)(單個(gè)異常大或小的峰谷信號(hào))，同時(shí)處理缺失數(shù)據(jù)。2. 數(shù)據(jù)轉(zhuǎn)換：許多高通量實(shí)驗(yàn)的結(jié)果是測(cè)量樣本與對(duì)照樣本間信號(hào)強(qiáng)度的Ratio值。對(duì)于 Ratio 值，在大多數(shù)情況下是轉(zhuǎn)換到對(duì)數(shù)(log)空間中進(jìn)行處理，常用的對(duì)數(shù)底為 2，e，10。3. 數(shù)據(jù)的標(biāo)準(zhǔn)化：是將所有的數(shù)據(jù)轉(zhuǎn)換到同一個(gè)范圍內(nèi)，這樣做的好處是方便比較和計(jì)算相關(guān)系數(shù)。數(shù)據(jù)標(biāo)準(zhǔn)化按如下公式進(jìn)行:標(biāo)準(zhǔn)化變量公式：(1.1)其中(1.2)將所有的數(shù)據(jù) x

54、分布在a,b之間，還需要進(jìn)行如下轉(zhuǎn)換：(1.3)其中 xm in =min x1 , x 2, ,x N, x max =max x1 , x2 , , xN 。二、布爾矩陣的生成與購物籃交易數(shù)據(jù)相比，高通量實(shí)驗(yàn)數(shù)據(jù)的不同條件相當(dāng)于不同的交易，而每個(gè)基因則可看作是不同的商品。進(jìn)行關(guān)聯(lián)規(guī)則挖掘是為了找出各種項(xiàng)，即各個(gè)基因之間的相關(guān)聯(lián)系。然而還有一個(gè)關(guān)鍵問題需要解決，對(duì)于交易數(shù)據(jù)，交易中的每一項(xiàng)是以布爾值的形式出現(xiàn)的，它只能是兩種狀態(tài)之一：存在和不存在。而生物學(xué)實(shí)驗(yàn)數(shù)據(jù)中的項(xiàng)則表現(xiàn)為一定量的數(shù)值。在進(jìn)行關(guān)聯(lián)分析之前，必須對(duì)基因表達(dá)數(shù)據(jù)做離散化處理，使得各種條件下基因的表現(xiàn)形式為布爾值，也就是 Tr

55、ue(1)，F(xiàn)alse(0)。根據(jù)生物數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘的不同要求，對(duì)其進(jìn)行轉(zhuǎn)換的方法也有差別，目前常采用的布爾矩陣轉(zhuǎn)換方法有以下兩種：1. 根據(jù)實(shí)驗(yàn)數(shù)據(jù)的數(shù)值的大小，將其表達(dá)方式分為三種：偏高（up）、偏低（down）以及正常（neither up nor down）。給出一個(gè)區(qū)間a，b，對(duì)與xij ，xij a，b，則將它視為正常表達(dá)；xij <a，視它為偏低；xij >b，視它為偏高。因?yàn)閷?duì)高通量實(shí)驗(yàn)數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘的興趣在表達(dá)不正常的基因上，故將每個(gè)基因分割為兩個(gè)狀態(tài)，一是偏高，一是偏低。這樣，每個(gè)交易的項(xiàng)分為兩個(gè)項(xiàng)。如圖1.2所示，以-0.2，0.2為例對(duì)以下基因表達(dá)數(shù)據(jù)進(jìn)

56、行轉(zhuǎn)換。依據(jù)這種轉(zhuǎn)化方法即可得到形如Cancer geneA，geneB，geneC的關(guān)聯(lián)規(guī)則，揭露疾病與基因之間的關(guān)系。其中a，b的確定則根據(jù)不同的離散化方法得到。圖 1.2 布爾矩陣的生成2. 根據(jù)實(shí)驗(yàn)數(shù)據(jù)的數(shù)值的大小，將其表達(dá)方式分為兩種：超高（overexpressed）與正常(not overexpressed)。當(dāng)其值超高的時(shí)候，將其賦值為 1，否則賦值為 0。其閥值（cutoff）可根據(jù)個(gè)人經(jīng)驗(yàn)或目的自由根據(jù)不同的離散化方法確定。經(jīng)過這種轉(zhuǎn)換，可以得出形如geneAgeneB的關(guān)聯(lián)規(guī)則，揭露基因之間的相關(guān)聯(lián)系。三、使用挖掘算法對(duì)其進(jìn)行挖掘這一步是核心步驟。將高通量生物學(xué)實(shí)驗(yàn)數(shù)據(jù)轉(zhuǎn)

57、化后，可以采用與挖掘交易數(shù)據(jù)庫的算法對(duì)其進(jìn)行關(guān)聯(lián)規(guī)則挖掘。四、結(jié)果表現(xiàn)形式根據(jù)不同的挖掘目的，基因表達(dá)數(shù)據(jù)的關(guān)聯(lián)規(guī)則按其表示形式可以分為兩類：1. 基因之間的關(guān)聯(lián)，形如geneA geneB的關(guān)聯(lián)規(guī)則，揭露基因之間的相關(guān)聯(lián)系。為單維的關(guān)聯(lián)規(guī)則。2. 基因與疾病之間的關(guān)聯(lián)，形如Cancer geneA，geneB，genC的關(guān)聯(lián)規(guī)則，揭露疾病與基因之間的關(guān)系。因?yàn)槠湟幚淼臄?shù)據(jù)涉及到疾病以及基因兩個(gè)屬性，屬于多維的關(guān)聯(lián)規(guī)則。也有在2的基礎(chǔ)上再考慮另一些因素的，例如，根據(jù)表達(dá)值的大小將基因劃分為三個(gè)區(qū)間，得出形如CancergeneA，geneB，genC。對(duì)于多維關(guān)聯(lián)規(guī)則的處理方法就是將不同的維

58、當(dāng)作不同的屬性，根據(jù)不同的維的性質(zhì)指定它在關(guān)聯(lián)規(guī)則中的位置，例要求在規(guī)則的右邊必須是疾病這一屬性的某一個(gè)值，如Cancer。1.4 論文組織結(jié)構(gòu)本文內(nèi)容包含以下幾個(gè)部分：第一章：介紹生物數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘的研究背景、研究現(xiàn)狀和基本步驟等。第二章：介紹兩種經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法和兩種經(jīng)典的多層關(guān)聯(lián)規(guī)則挖掘算法的原理及實(shí)現(xiàn)過程，并作出了分析與比較。第三章：選用Gene Ontology完善的概念層次結(jié)構(gòu)，通過對(duì)FP_Growth算法進(jìn)行擴(kuò)展，提出一種優(yōu)化的生物數(shù)據(jù)多層關(guān)聯(lián)規(guī)則挖掘算法MAGO-FP，并分析其時(shí)間復(fù)雜度。第四章：應(yīng)用MAGO-FP算法分析實(shí)際的生物數(shù)據(jù)，發(fā)現(xiàn)一些候選關(guān)聯(lián)規(guī)則。進(jìn)行實(shí)驗(yàn)結(jié)果分析，并與傳統(tǒng)的多層關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行性能比較。第五章：對(duì)全文進(jìn)行總結(jié)，并提出進(jìn)一步的研究方向。2 關(guān)聯(lián)規(guī)則挖掘算法2.1 關(guān)聯(lián)規(guī)則的定義和相關(guān)概念關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘技術(shù)所能發(fā)現(xiàn)的非常重要的一類規(guī)則，它首先由 Agrawal等人6于 1993 年提出，能夠揭示項(xiàng)集之間的有趣聯(lián)系。關(guān)聯(lián)規(guī)則挖掘能夠從大量數(shù)據(jù)中發(fā)現(xiàn)關(guān)聯(lián)規(guī)則，例如，