基于Apriori算法的關(guān)聯(lián)規(guī)則挖掘系統(tǒng)的設(shè)計與實(shí)現(xiàn)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上基于Apriori算法的關(guān)聯(lián)規(guī)則挖掘系統(tǒng)的設(shè)計與實(shí)現(xiàn)論文作者姓名：申請學(xué)位專業(yè)：計算機(jī)科學(xué)與技術(shù)申請學(xué)位類別：工學(xué)學(xué)士指導(dǎo)教師姓名（職稱）：論文提交日期：專心-專注-專業(yè)基于Apriori算法的關(guān)聯(lián)規(guī)則挖掘系統(tǒng)的設(shè)計與實(shí)現(xiàn)摘 要隨著信息時代的發(fā)展，信息量呈幾何級數(shù)增長，人們發(fā)現(xiàn)從這些海量信息中獲取有用的信息越來越困難，要找出信息背后隱藏的規(guī)律更是不可想象。數(shù)據(jù)挖掘就是從大量數(shù)據(jù)中獲取有用信息的一門新技術(shù)，關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘方法中的一種。本文詳細(xì)論述了基于Apriori算法的關(guān)聯(lián)規(guī)則挖掘系統(tǒng)的設(shè)計開發(fā)過程。系統(tǒng)基于經(jīng)典的Apriori算法，對事務(wù)數(shù)據(jù)庫進(jìn)行了位圖矩陣

2、轉(zhuǎn)換，大大提高了搜索效率，并能分別挖掘頻繁項集和關(guān)聯(lián)規(guī)則。論文組織如下：首先介紹了數(shù)據(jù)挖掘的產(chǎn)生、定義和應(yīng)用；接著闡述了關(guān)聯(lián)規(guī)則挖掘的基本概念；然后對系統(tǒng)的需求進(jìn)行了分析，并提出設(shè)計方案；緊接著是系統(tǒng)的具體實(shí)現(xiàn)；最后對系統(tǒng)進(jìn)行了測試，將系統(tǒng)用于挖掘中藥方劑庫中的藥對藥組，驗證了系統(tǒng)的正確性和實(shí)用性。關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；Apriori算法The Design and Implementation of Association Rules Mining System based on Apriori ArithmeticAbstractWith the development of the

3、 information era, the quantity of information increases in the way of geometric series, and people find that it is more and more difficult to obtain valuable informatin and it is incogitable to find out the rules hiding in the information. Data mining is a new technology to mine valuable informatin

4、from abundant data, and association rules mining is a method of data mining. This paper elaborates on the process of the design and development of association rules mining system based on Apriori . The system is based upon classical Apriori arithmetic, and converts chinese medicine prescriptions dat

5、abase to a bitmap matrix, which greatly enhances the efficiency of search, and can mine frequent items and association rules respectively. The paper is organized as following: Firstly, introduces the generation, definition and application of data mining; Secondly, sets forth the conception of associ

6、ation rules mining; Thirdly, analyzes the demand of the system, and propses the design project and implements the system; Finally, gives a test to mine chinese medicine groups from a chinese medicine prescriptions data, which proves the system valid and applicable. Key words: Data mining; Apriori; C

7、hinese traditional medicine目錄論文總頁數(shù)：27頁1引言隨著數(shù)據(jù)庫技術(shù)的迅速發(fā)展以及數(shù)據(jù)庫管理系統(tǒng)的廣泛應(yīng)用，人們積累的數(shù)據(jù)越來越多。激增的數(shù)據(jù)背后隱藏著許多重要的信息，人們希望能夠?qū)ζ溥M(jìn)行更高層次的分析，以便更好地利用這些數(shù)據(jù)。目前的數(shù)據(jù)庫系統(tǒng)可以高效地實(shí)現(xiàn)數(shù)據(jù)的錄入、查詢、統(tǒng)計等功能，但無法發(fā)現(xiàn)數(shù)據(jù)中存在的關(guān)系和規(guī)則，無法根據(jù)現(xiàn)有的數(shù)據(jù)預(yù)測未來的發(fā)展趨勢。缺乏找出數(shù)據(jù)背后隱藏的知識的手段，導(dǎo)致了“數(shù)據(jù)爆炸但知識貧乏”的現(xiàn)象。于是數(shù)據(jù)挖掘技術(shù)應(yīng)運(yùn)而生，并顯示出強(qiáng)大的生命力。數(shù)據(jù)挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含在其中的、人們事先不知

8、道的、但又是潛在有用的信息和知識的過程。它使人類分析問題和發(fā)現(xiàn)知識能力得到了延伸。2數(shù)據(jù)挖掘概述2.1數(shù)據(jù)挖掘的產(chǎn)生隨著信息時代的發(fā)展，信息量呈幾何級數(shù)增長，然而用于對這些數(shù)據(jù)進(jìn)行分析處理的工具卻很少，人們擁有了海量的數(shù)據(jù)的同時卻苦于信息的缺乏。而激增的數(shù)據(jù)背后隱藏著許多重要的信息，人們希望能夠?qū)ζ溥M(jìn)行更高層次的分析，以便更好地利用這些數(shù)據(jù)。目前的數(shù)據(jù)庫系統(tǒng)可以高效地實(shí)現(xiàn)數(shù)據(jù)的錄入、查詢、統(tǒng)計等功能，但無法發(fā)現(xiàn)數(shù)據(jù)中存在的關(guān)系和規(guī)則，無法根據(jù)現(xiàn)有的數(shù)據(jù)預(yù)測未來的發(fā)展趨勢。缺乏挖掘數(shù)據(jù)背后隱藏的知識的手段，導(dǎo)致了“數(shù)據(jù)爆炸但知識貧乏”的現(xiàn)象。信息爆炸是一把雙刃劍：巨量的信息既是最重要的財富，又是

9、最危險的殺手。巨量信息也導(dǎo)致決策與理解危機(jī)。面對“人人被數(shù)據(jù)淹沒，人們卻饑餓于知識”的挑戰(zhàn)，數(shù)據(jù)挖掘和知識發(fā)現(xiàn)技術(shù)應(yīng)運(yùn)而生，并得以蓬勃發(fā)展，越來越顯示出其強(qiáng)大的生命力。數(shù)據(jù)挖掘是信息技術(shù)自然演化的結(jié)果。演化過程的見證是數(shù)據(jù)庫業(yè)界開發(fā)以下功能：數(shù)據(jù)收集和數(shù)據(jù)庫創(chuàng)建，數(shù)據(jù)管理（包括數(shù)據(jù)存儲和檢索，數(shù)據(jù)庫事務(wù)處理），以及數(shù)據(jù)分析與理解（涉及數(shù)據(jù)倉庫和數(shù)據(jù)挖掘）。例如，數(shù)據(jù)收集和數(shù)據(jù)庫創(chuàng)建機(jī)制的早期開發(fā)已成為稍后數(shù)據(jù)存儲和檢索、查詢和事務(wù)處理有效機(jī)制開發(fā)的必備基礎(chǔ)。隨著提供查詢和事務(wù)處理的大量數(shù)據(jù)庫系統(tǒng)廣泛付諸實(shí)踐，數(shù)據(jù)分析和理解自然成為下一個目標(biāo)。2.2數(shù)據(jù)挖掘的定義數(shù)據(jù)挖掘是從大量數(shù)據(jù)中提取或“挖

10、掘”知識。具體來說，數(shù)據(jù)挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。人們把原始數(shù)據(jù)看作是形成知識的源泉，就像從礦石中采礦一樣。原始數(shù)據(jù)有結(jié)構(gòu)化的，如關(guān)系數(shù)據(jù)庫中的數(shù)據(jù)，也有半結(jié)構(gòu)化的，如文本、圖形、圖像數(shù)據(jù)，甚至是分布在網(wǎng)絡(luò)上的異構(gòu)型數(shù)據(jù)。發(fā)現(xiàn)知識的方法可以是數(shù)學(xué)的，也可以是非數(shù)學(xué)的;可以是演繹的，也可以是歸納的。發(fā)現(xiàn)了的知識可以被用于信息管理、查詢優(yōu)化、決策支持、過程控制等，還可以用于數(shù)據(jù)自身的維護(hù)。因此，數(shù)據(jù)挖掘是一門很廣義的交叉學(xué)科，它匯聚了不同領(lǐng)域的研究者，尤其是數(shù)據(jù)庫、人工智能、數(shù)理統(tǒng)計、可視化、并

11、行計算等方面的學(xué)者和工程技術(shù)人員。數(shù)據(jù)挖掘使用復(fù)雜的統(tǒng)計分析和建模技術(shù)來揭示企業(yè)數(shù)據(jù)庫中隱藏的模式與關(guān)系而這些模式是有可能被普通的方法所忽略的。數(shù)據(jù)挖掘從數(shù)據(jù)的分析入手、幫助決策，能從數(shù)據(jù)中尋找有價值的規(guī)律的技術(shù)。同時它也代表一個分析過程，我們具體化為方法學(xué)。實(shí)際上，數(shù)據(jù)庫中的知識發(fā)現(xiàn)是一門交叉性學(xué)科，涉及到機(jī)器學(xué)習(xí)、模式識別、統(tǒng)計學(xué)、智能數(shù)據(jù)庫、知識獲取、數(shù)據(jù)可視化、高性能計算、專家系統(tǒng)等多個領(lǐng)域。從數(shù)據(jù)庫中發(fā)現(xiàn)出來的知識可以用在信息管理、過程控制、科學(xué)研究、決策支持等許多方面。特別要指出的是，數(shù)據(jù)挖掘技術(shù)從一開始就是面向應(yīng)用的。它不僅是面向特定數(shù)據(jù)庫的簡單檢索查詢調(diào)用，而且要對這些數(shù)據(jù)進(jìn)行

12、微觀、中觀乃至宏觀的統(tǒng)計、分析、綜合和推理，以指導(dǎo)實(shí)際問題的求解，企圖發(fā)現(xiàn)事件間的相互關(guān)聯(lián)，甚至利用已有的數(shù)據(jù)對未來的活動進(jìn)行預(yù)測。許多人把數(shù)據(jù)挖掘視為另一個常用的術(shù)語數(shù)據(jù)庫中的知識發(fā)現(xiàn)或KDD (knowledge discovery in databases)的同義詞。而另一些人只是把數(shù)據(jù)挖掘視為數(shù)據(jù)庫中知識發(fā)現(xiàn)過程的一個基本步驟。知識發(fā)現(xiàn)過程如圖1所示，由以下步驟組成：1) 數(shù)據(jù)清理（消除噪聲或不一致數(shù)據(jù)）2) 數(shù)據(jù)集成（多種數(shù)據(jù)源可以組合在一起）3) 數(shù)據(jù)選擇（從數(shù)據(jù)庫中檢索與分析任務(wù)相關(guān)的數(shù)據(jù)）4) 數(shù)據(jù)變換（數(shù)據(jù)變換或統(tǒng)一成適合挖掘的形式，如通過匯總或聚集操作）5) 數(shù)據(jù)挖掘（基本

13、步驟，使用智能方法提取數(shù)據(jù)模式）6) 模式評估（根據(jù)某種興趣度度量，識別出真正有趣的模式）7) 知識表示（使用可視化和知識表示技術(shù)，向用戶提供挖掘的知識）圖1 知識發(fā)現(xiàn)過程雖然數(shù)據(jù)挖掘是知識發(fā)現(xiàn)過程的一個步驟，然而，在產(chǎn)業(yè)界、媒體和數(shù)據(jù)庫研究界，“數(shù)據(jù)挖掘”比較長的術(shù)語“數(shù)據(jù)庫中知識發(fā)現(xiàn)”更流行。目前比較公認(rèn)的定義是Fayyad等給出的：KDD是從數(shù)據(jù)集中識別出有效的、新穎的、潛在有用的以及最終可理解模式的高級處理過程。這里的高級處理過程是指一個多步驟的處理過程，多步驟之間相互影響、反復(fù)調(diào)整，形成一種螺旋式的上升過程。而數(shù)據(jù)挖掘則指的是從存放在數(shù)據(jù)庫、數(shù)據(jù)倉庫或其他信息庫中的大量數(shù)據(jù)中挖掘有趣

14、知識的過程。數(shù)據(jù)挖掘其實(shí)是知識發(fā)現(xiàn)的核心部分，而知識發(fā)現(xiàn)是在積累了大量數(shù)據(jù)后，從中識別出有效的、新穎的、潛在的、有用的及最終可以理解的知識，人們利用這些知識改進(jìn)工作，提高效率和效益。KDD是一門交叉學(xué)科，涉及到人工智能、機(jī)器學(xué)習(xí)、模式識別、統(tǒng)計學(xué)、智能數(shù)據(jù)庫、知識獲取、數(shù)據(jù)可視化、專家系統(tǒng)等多個領(lǐng)域。數(shù)據(jù)挖掘算法的好壞將直接影響到所發(fā)現(xiàn)知識的好壞。數(shù)據(jù)挖掘的任務(wù)是從數(shù)據(jù)中發(fā)現(xiàn)模式。雖然數(shù)據(jù)挖掘是知識發(fā)現(xiàn)過程的一個步驟，然而，在產(chǎn)業(yè)界、媒體和數(shù)據(jù)庫研究界，“數(shù)據(jù)挖掘”比較長的術(shù)語“數(shù)據(jù)庫中知識發(fā)現(xiàn)”更流行。目前比較公認(rèn)的定義是Fayyad等給出的：KDD是從數(shù)據(jù)集中識別出有效的、新穎的、潛在有用

15、的以及最終可理解模式的高級處理過程。這里的高級處理過程是指一個多步驟的處理過程，多步驟之間相互影響、反復(fù)調(diào)整，形成一種螺旋式的上升過程。而數(shù)據(jù)挖掘則指的是從存放在數(shù)據(jù)庫、數(shù)據(jù)倉庫或其他信息庫中的大量數(shù)據(jù)中挖掘有趣知識的過程。其實(shí)數(shù)據(jù)挖掘是知識發(fā)現(xiàn)的核心部分，而知識發(fā)現(xiàn)是在積累了大量數(shù)據(jù)后，從中識別出有效的、新穎的、潛在的、有用的及最終可以理解的知識，人們利用這些知識改進(jìn)工作，提高效率和效益。KDD是一門交叉學(xué)科，涉及到人工智能、機(jī)器學(xué)習(xí)、模式識別、統(tǒng)計學(xué)、智能數(shù)據(jù)庫、知識獲取、數(shù)據(jù)可視化、專家系統(tǒng)等多個領(lǐng)域。數(shù)據(jù)挖掘算法的好壞將直接影響到所發(fā)現(xiàn)知識的好壞。數(shù)據(jù)挖掘的任務(wù)是從數(shù)據(jù)中發(fā)現(xiàn)模式。2.

16、3 數(shù)據(jù)挖掘的應(yīng)用數(shù)據(jù)挖掘可以應(yīng)用在各個不同的領(lǐng)域。電訊公司和信用卡公司是用數(shù)據(jù)挖掘檢測欺詐行為的先行者。保險公司和證券公司也開始采用數(shù)據(jù)挖掘來減少欺詐。醫(yī)療應(yīng)用是另一個前景廣闊的產(chǎn)業(yè):數(shù)據(jù)挖掘可以用來預(yù)測外科手術(shù)、醫(yī)療試驗和藥物治療的效果。零銷商更多的使用數(shù)據(jù)挖掘來決定每種商品在不同地點(diǎn)的庫存，通過數(shù)據(jù)挖掘更靈活的使用促銷和優(yōu)惠券手段。制藥公司通過挖掘巨大的化學(xué)物質(zhì)和基因?qū)膊〉挠绊懙臄?shù)據(jù)庫來判斷哪些物質(zhì)可能對治療某種疾病產(chǎn)生效果。以下為數(shù)據(jù)挖掘的一些成功案例:(1)加拿大BC省電話公司要求加拿大Simon Fraser大學(xué)KDD研究組根據(jù)其擁有的十多年的客戶數(shù)據(jù)，總結(jié)、分析并提出新的電話收

17、費(fèi)和管理辦法，制定既有利于公司又有利于客戶的優(yōu)惠政策。(2)美國著名的國家籃球隊NBA的教練，利用IBM公司提供的數(shù)據(jù)挖掘工具臨場決定替換隊員。大約20個NBA球隊使用了IBM公司開發(fā)的數(shù)據(jù)挖掘應(yīng)用軟件Advanced Scout系統(tǒng)來優(yōu)化他們的戰(zhàn)術(shù)組合。例如Scout就因為研究了魔術(shù)隊隊員不同的布陣安排，在與邁阿密熱隊的比賽中找到了獲勝的機(jī)會。（3）國外使用數(shù)據(jù)挖掘技術(shù)，對西藥的新藥開發(fā)研究也早已利用數(shù)據(jù)挖掘技術(shù)。我國在中藥的數(shù)據(jù)挖掘技術(shù)上已步入起步階段。3關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系。隨著大量數(shù)據(jù)不停地收集和存儲，許多業(yè)界人士對于從他們的數(shù)據(jù)庫中挖掘關(guān)

18、聯(lián)規(guī)則越來越感興趣。從大量商務(wù)事務(wù)記錄中發(fā)現(xiàn)有趣的關(guān)聯(lián)關(guān)系，可以幫助許多商務(wù)決策的制定，如分類設(shè)計、交叉購物和促銷分析。關(guān)聯(lián)規(guī)則挖掘的一個典型例子是購物籃分析。該過程通過發(fā)現(xiàn)顧客放入其購物籃中不同商品之間的聯(lián)系，分析顧客的購買習(xí)慣。通過了解哪些商品頻繁地被顧客同時購買，這種關(guān)聯(lián)的發(fā)現(xiàn)可以幫助零售商制定營銷策略。例如，如果顧客購買牛奶的同時也購買面包（和什么類型的面包）的可能性有多大？通過幫助零售商有選擇地經(jīng)銷和安排貨架，這種信息可以引導(dǎo)銷售。例如，將牛奶和面包盡可能放近一些，可以進(jìn)一步刺激一次去商店同時購買這些商品。3.1基本概念設(shè)I=i1,i2,im是項的集合。設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)

19、的集合，其中每個事務(wù)T是項的集合，使得TÍI。每個事務(wù)有一個標(biāo)示符，稱作TID。設(shè)A是一個項集，事務(wù)T包含A當(dāng)且僅當(dāng) AÍT。關(guān)聯(lián)規(guī)則是形如AÞB的蘊(yùn)涵式，其中AI，BI，并且AB=Æ。如果D中有s%的事務(wù)包含AB，則稱關(guān)聯(lián)規(guī)則AÞB在事務(wù)數(shù)據(jù)庫D中具有大小為s%的支持度，它是概率P(AB)。如果D中包含項目集A的事務(wù)中有c%的事務(wù)同時也包含項目集B，則稱規(guī)則AÞB在事務(wù)數(shù)據(jù)庫D中具有大小為c%的置信度，它是條件概率P(B|A)。即： support(AÞB)= P(AB) confidence(AÞB)=P(B|

20、A) 如果不考慮關(guān)聯(lián)規(guī)則的支持度和置信度，在事務(wù)數(shù)據(jù)庫中可以發(fā)現(xiàn)無窮多的規(guī)則。事實(shí)上，滿足一定的支持度和置信度的關(guān)聯(lián)規(guī)則才是有意義的。因此，需要給定兩個閾值：最小支持度（min_sup）和最小置信度（min_conf）。同時滿足最小支持度閾值和最小置信度閾值的規(guī)則稱作強(qiáng)規(guī)則。為方便計，我們用0%和100%之間的值而不是用0到1之間的值表示支持度和置信度。項的集合稱為項集(itemset)。包含k個項的項集稱為k-項集。項集的出現(xiàn)頻率是包含項集的事務(wù)數(shù)，簡稱為項集的支持計數(shù)。如果項集滿足最小支持度，則稱它為頻繁項集(frequent itemset)。頻繁k-項集的集合通常記作Lk。3.2購物籃

21、分析先看看購物籃分析，這是一個引發(fā)關(guān)聯(lián)規(guī)則挖掘的典型例子。例1 超市的經(jīng)理想了解顧客的購物習(xí)慣。例如，想知道“哪些商品組合常常被顧客同時購買？”為回答這一問題，可以在超市的事務(wù)數(shù)據(jù)庫上運(yùn)行購物籃分析。分析結(jié)果可以幫助超市經(jīng)理設(shè)計不同的商品布局。一種策略是：將經(jīng)常一塊購買的商品放近一些，以便進(jìn)一步刺激這些商品一起銷售。例如，如果顧客購買牛奶也傾向于同時購買面包，那么將牛奶和面包擺放得近一點(diǎn)，可能有助于增加二者的銷售。另一種策略是：將牛奶和面包分別放在超市的進(jìn)、出口，可能誘發(fā)買這些商品的顧客一路挑選其他商品。例如，顧客在買了牛奶之后，去找面包，路上看到水果，可能會決定也買一些水果。購物籃分析也可以

22、幫助超市規(guī)劃什么商品降價出售。如果顧客趨向于同時購買數(shù)字彩電和DVD機(jī)，數(shù)字彩電降價出售可能既促使購買數(shù)字彩電，又促使購買DVD機(jī)。想象全域是超市中可利用的商品的集合，則每種商品有一個布爾變量，表示該商品的有無。每個籃子則可用一個布爾向量表示?？梢苑治霾紶栂蛄浚玫椒从成唐奉l繁關(guān)聯(lián)或同時購買的購買模式。這些模式可以用關(guān)聯(lián)規(guī)則的形式表示。例如，購買牛奶也趨向于同時購買面包可以用以下關(guān)聯(lián)規(guī)則表示：牛奶Þ面包 support= 2% ,confidence= 60% 規(guī)則的支持度和置信度是兩個規(guī)則興趣度度量，它們分別反映發(fā)現(xiàn)規(guī)則的有用性和確定性。上一條關(guān)聯(lián)規(guī)則的支持度2%意味分析中的全部事

23、務(wù)的 2%同時購買牛奶和面包。置信度60%意味購買牛奶的顧客60%也購買面包。如果關(guān)聯(lián)規(guī)則滿足最小支持度閾值和最小置信度閾值，則被認(rèn)為是有趣的。這些閾值可以由用戶或領(lǐng)域?qū)＜以O(shè)定。3.3Apriori經(jīng)典算法下面介紹形式最簡單的關(guān)聯(lián)規(guī)則挖掘方法。這種關(guān)聯(lián)規(guī)則是單維、單層、布爾關(guān)聯(lián)規(guī)則，如前面討論的購物籃分析。關(guān)聯(lián)規(guī)則的挖掘分兩步：1) 找出所有頻繁項集：根據(jù)定義，這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持計數(shù)一樣。2) 由頻繁項集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則：根據(jù)定義，這些規(guī)則必須滿足最小支持度和最小置信度。也可以使用附加的興趣度度量。這兩步中，第二步最容易。挖掘關(guān)聯(lián)規(guī)則的總體性能由第一步?jīng)Q定。Apriori

24、算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法。算法的名字基于頻繁項集性質(zhì)的先驗知識，正如我們將看到的。Apriori使用逐層搜索的迭代方法，k-項集用于探索(k+1)-項集。首先，找出頻繁1-項集的集合。該集合記作L1。L1用于找頻繁2-項集的集合L2，而L2用于找L3，如此下去，直到不能找到頻繁 k-項集。找每個Lk需要一次數(shù)據(jù)庫掃描。為提高頻繁項集逐層產(chǎn)生的效率，一種稱作Apriori性質(zhì)的重要性質(zhì)用于壓縮搜索空間。我們先介紹該性質(zhì)，然后用一個例子解釋它的使用。Apriori性質(zhì)：頻繁項集的所有非空子集都必須也是頻繁的。Apriori性質(zhì)基于如下觀察：根據(jù)定義，如果項集I不滿足最小支

25、持度閾值min_sup，則I不是頻繁的，即P(I)<min_sup。如果項A添加到I，則結(jié)果項集（即IA）不可能比I更頻繁出現(xiàn)。因此，IA也不是頻繁的，即P(IA)<min_sup。該性質(zhì)屬于一種特殊的分類，稱作反單調(diào)(anti-monotone)，意指如果一個集合不能通過測試，則它的所有超集也都不能通過相同的測試。稱它為反單調(diào)，是因為在通不過測試的意義下，該性質(zhì)是單調(diào)的?！叭绾螌priori性質(zhì)用于算法？”為理解這一點(diǎn)，我們必須看看如何用Lk找Lk-1。下面的兩步過程由連接和剪枝組成。(1) 連接步：為找Lk ，通過Lk-1 與自己連接產(chǎn)生候選k-項集的集合。該候選項集的集合記

26、作Ck。設(shè)l1和l2是Lk-1中的項集。記號lij表示li的第j項（例如，l1k- 2 表示l1的倒數(shù)第3項）。為方便計，假定事務(wù)或項集中的項按字典次序排序。執(zhí)行連接Lk1Lk1 ，其中Lk1的元素是可連接的，如果它們前(k- 2 )個項相同。即是，L k1的元素l1和l2是可連接的，如果(l11 = l21)(l12 =l2 2) . . . (l1k-2= l2k-2)(l1k-1< l2k-1 )。條件(l1k-1< l2k-1 )是簡單地保證不產(chǎn)生重復(fù)。連接l1和l2產(chǎn)生的結(jié)果項集是l11 l22. l1k- 1 l2k- 1 。(2) 剪枝步：Ck是Lk的超集；即是，它的

27、成員可以是也可以不是頻繁的，但所有的頻繁k-項集都包含在Ck中。掃描數(shù)據(jù)庫，確定Ck中每個候選的計數(shù)，從而確定Lk（即根據(jù)定義，計數(shù)值不小于最小支持度計數(shù)的所有候選是頻繁的，從而屬于Lk）。然而，Ck可能很大，這樣所涉及的計算量就很大。為壓縮Ck，可以用以下辦法使用 Apriori性質(zhì)：任何非頻繁的 (k-1)-項集都不可能是頻繁的，從而可以由Ck中刪除。這種子集測試可以使用所有頻繁項集的散列樹快速完成。下面的Apriori算法是Agrawal R提出來的：算法1：Apriori使用根據(jù)候選生成的逐層迭代找出頻繁項集。輸入：事務(wù)數(shù)據(jù)庫D；最小支持度閾值min_sup。輸出：D中的頻繁項集L。方

28、法：1) L1= find_frequent_1-itemsets(D) ;2) for (k = 2; Lk-1 ; k+) 3) Ck= aproiri_gen(Lk-1 ,min_sup) ;4) for each transaction tD /scan D for counts5) Ct = subset(Ck , t); /get the subsets of t 6) for each candidate cCt7) c.count+;8) 9) Lk= cC | c.count min_sup10) 11) return L = kLk;procedure apriori_ge

29、n(Lk-1:frequent(k-1)-itemsets; min_sup:minimum support threshold)1) for each itemset l1Lk-12) for each itemset l2 Lk-13) if (l11=l21)(l12=l22). . .(l1k-2 =l2k-2)(l1 k-1<l2k-1) then 4) c = l1l2 ; /join step: generate candidates5) if has_infrequent_subset(c,Lk-1 ) then6) delete c; / prune step: rem

30、ove unfruitful cadidate7) else add c to Ck ;8) 9) return Ck ;procedure has_infrequent_subset(c:candidate k-itemset; L :frequent (k- 1 )- itemset )/ use prior knowledge1) for each (k-1)-subset s of c2) if sLk-1then3) return TRUE ;4) return FALSE;如上所述，Apriori_gen做兩個動作：連接和剪枝。在連接部分，Lk與Lk-1連接產(chǎn)生可能的候選（第1-4

31、步）。剪枝部分（第5-7步）使用Apriori性質(zhì)刪除具有非頻繁子集的候選。非頻繁子集的測試在過程has_infrequent_subset中。一旦由數(shù)據(jù)庫D中的事務(wù)找出頻繁項集，由它們產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則是直接了當(dāng)?shù)模◤?qiáng)關(guān)聯(lián)規(guī)則滿最小支持度和最小置信度）。對于置信度，可以用下式，其中條件概率用項集支持度計數(shù)表示。其中，support_count(AB)是包含項集AB的事務(wù)數(shù)，support_count(A)是包含項集A的事務(wù)數(shù)。4需求分析和設(shè)計方案4.1需求分析由于事務(wù)數(shù)據(jù)庫一般只具有對大量數(shù)據(jù)的存取、檢索功能，對于用戶的一般性的使用可以滿足，然而，正是由于數(shù)據(jù)庫中存放了大量的數(shù)據(jù)，不同的數(shù)據(jù)項，

32、以及多個數(shù)據(jù)項之間還存在有大量的隱含的、未知的、有意義的數(shù)據(jù)關(guān)系，這些關(guān)系對于用戶有著及其重要的作用，所以數(shù)據(jù)挖掘便在此情況下產(chǎn)生了。而關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中一個重要規(guī)則，Apriori算法又是關(guān)聯(lián)挖掘的一個經(jīng)典算法，它能發(fā)現(xiàn)大量數(shù)據(jù)中項集之間有趣的關(guān)聯(lián)和相關(guān)聯(lián)系。隨著大量數(shù)據(jù)不停地收集和存儲，許多業(yè)界人士對于從他們的數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則越來越感興趣。從大量商務(wù)事務(wù)記錄中發(fā)現(xiàn)有趣的關(guān)聯(lián)關(guān)系，可以幫助許多商務(wù)決策的制定，如分類設(shè)計、交叉購物和促銷分析。4.2設(shè)計方案數(shù)據(jù)庫建立位圖矩陣參數(shù)設(shè)置數(shù)據(jù)挖掘功能Apriori關(guān)聯(lián)算法關(guān)聯(lián)規(guī)則圖2 系統(tǒng)結(jié)構(gòu)圖通常在尋找頻繁項集時要反復(fù)掃描整個事務(wù)數(shù)據(jù)庫，

33、讀出每一條記錄，判斷記錄是否包含候選項集，這樣對于較大型的事務(wù)數(shù)據(jù)庫，花在掃描數(shù)據(jù)庫、讀記錄上的開銷很大。同時，本文提出的關(guān)聯(lián)規(guī)則是建立在置信度上的挖掘技術(shù)，與頻繁項集無關(guān)，更是需要反復(fù)掃描事物數(shù)據(jù)庫。于是本文引入了位圖矩陣。先給方劑庫建立一個位圖矩陣，然后只在位圖矩陣上進(jìn)行挖掘操作。使用位圖矩陣有如下好處：（1）對位圖進(jìn)行操作，簡單快速。（2）只需要在建立位圖矩陣時對整個方劑庫掃描一次。（3）在做實(shí)驗時需要反復(fù)調(diào)整支持度閾值和置信度閾值，以得到多組實(shí)驗數(shù)據(jù)，但位圖矩陣只在做第一組實(shí)驗時建立一次，調(diào)整支持度閾值和置信度閾值再做實(shí)驗時，不用再建。用Ik(k為自然數(shù))表示事務(wù)數(shù)據(jù)庫中的一項，I1、

34、I2、Ik、In表示事務(wù)數(shù)據(jù)庫中的所有項。用Tj(i1,i2,ik,in)表示事務(wù)數(shù)據(jù)庫中的一個事務(wù)，ik對應(yīng)Ik，占用1位(bit),當(dāng)事務(wù)Tj含有Ik這項時，Tj的ik位為1,否則為0，所以事務(wù)Tj可以用位圖i1i2ikin來表示。T1、T2、Tj、Tm表示事務(wù)數(shù)據(jù)庫中所有的事務(wù)，T1、T2、Tj、Tm都可以用位圖i1i2ikin來表示，這樣所有這些位圖就構(gòu)成了事務(wù)數(shù)據(jù)庫的位圖矩陣。圖2就是一個位圖矩陣。該位圖矩陣對應(yīng)的事務(wù)數(shù)據(jù)庫含I1、I2、I3、I4、I5共5個項，含T1、T2、T3、T4、T5、T6、T7共7個事務(wù)。事務(wù)T1的位圖為11010，所以含I1、I2、I4三個項；事務(wù)T2的

35、位圖為01001，所以含I2、I5兩個項；事務(wù)T3的位圖為10110，所以含I1、I3、I4三個項；事務(wù)T4的位圖為11101，所以含I1、I2、I3、I5四個項；事務(wù)T5的位圖為10100，所以含I1、I3兩個項；事務(wù)T6的位圖為11001，所以含I1、I2、I5三個項；事務(wù)T7的位圖為01010，所以含I2、I4兩個項。I1I2I3I4I5IT111010T201001T310110T411101T510100T611001T701010圖3一個位圖矩陣的例子5基于Apriori算法的關(guān)聯(lián)規(guī)則挖掘系統(tǒng)基于上述技術(shù)，作者開發(fā)了Apriori算法的關(guān)聯(lián)規(guī)則挖掘系統(tǒng)，整個系統(tǒng)在NetBeans下

36、開發(fā)，下面依次介紹實(shí)現(xiàn)關(guān)聯(lián)規(guī)則挖掘的步驟。在這之前，我們首先要介紹一下數(shù)據(jù)挖掘在中藥方劑研究中的應(yīng)用，因為本文所涉及的挖掘是關(guān)于中藥方劑配伍進(jìn)行的發(fā)掘。5.1數(shù)據(jù)挖掘在中藥方劑研究中的應(yīng)用數(shù)千年來，我國中藥豐富的經(jīng)驗、浩瀚的文獻(xiàn)，是世界上任何國家無可比擬的。而當(dāng)今人類社會正大規(guī)模、高速度進(jìn)入信息時代，信息已經(jīng)成為社會發(fā)展、進(jìn)步和人類賴以生存的重要資源和基本需求。在這樣的歷史環(huán)境下，中藥現(xiàn)代化的發(fā)展在很大程度上取決于中醫(yī)藥信息利用、轉(zhuǎn)化和傳播的能力及速度。實(shí)現(xiàn)中藥現(xiàn)代化，就要將我國豐富的中藥信息資源和現(xiàn)代最新信息技術(shù)相結(jié)合，整理浩如煙海的中藥文獻(xiàn)資料，實(shí)現(xiàn)中藥信息資源處理、轉(zhuǎn)化及傳播現(xiàn)代化。而中

37、藥復(fù)方數(shù)據(jù)挖掘研究是將我國豐富的中藥信息資源和現(xiàn)代最新信息技術(shù)相結(jié)合的重要內(nèi)容。它是指在中醫(yī)理論指導(dǎo)下，用知識發(fā)現(xiàn)技術(shù)對傳統(tǒng)中藥新藥、中醫(yī)組方理論及規(guī)律、中藥作用機(jī)制、有效成分構(gòu)效關(guān)系等多個方面進(jìn)行全面、系統(tǒng)的研究。中藥數(shù)據(jù)挖掘的研究與建立是一個多學(xué)科協(xié)作工程。它要求在中醫(yī)理論指導(dǎo)下，完成由事實(shí)型數(shù)據(jù)庫向智能型數(shù)據(jù)庫的轉(zhuǎn)變。中藥數(shù)據(jù)挖掘系統(tǒng)包括單味中藥數(shù)據(jù)庫、復(fù)方中藥數(shù)據(jù)庫、中醫(yī)專家知識庫等數(shù)據(jù)庫，以及預(yù)處理、數(shù)據(jù)聚焦、模式提取、工具箱、模式評價、知識編輯等模塊，該系統(tǒng)具有一般事實(shí)型及文獻(xiàn)型數(shù)據(jù)庫的功能，并具有利用上述數(shù)據(jù)庫進(jìn)行人工智能信息處理、獲取新知識的功能。目前我國尚未建立中藥數(shù)據(jù)挖掘系

38、統(tǒng)，現(xiàn)有數(shù)據(jù)庫只能提供檢索。統(tǒng)計等一般性服務(wù)，其包涵的大量隱含知識并未得到充分的挖掘和利用。建立中藥數(shù)據(jù)挖掘系統(tǒng)可以充分利用現(xiàn)有中藥數(shù)據(jù)庫中的大量數(shù)據(jù)，通過計算機(jī)智能信息處理，形成新的知識，為我國中藥新藥開發(fā)提供新的思路。由于國外使用數(shù)據(jù)挖掘技術(shù)較早，西藥的新藥開發(fā)研究也早已利用數(shù)據(jù)挖掘技術(shù)。隨著世界性回歸自然潮流的發(fā)展，天然藥物的開發(fā)越來越受到人們的重視，因此，如果我們自己不能利用數(shù)據(jù)挖掘技術(shù)充分挖掘我國現(xiàn)有中藥數(shù)據(jù)庫的潛能，就有可能被發(fā)達(dá)國家用較低的價格購買我們的數(shù)據(jù)庫，加上他們的數(shù)據(jù)挖掘技術(shù)進(jìn)行研制，然后高價返銷國內(nèi)，或利用這種具有數(shù)據(jù)挖掘系統(tǒng)的中藥數(shù)據(jù)庫進(jìn)行新藥開發(fā)，研制出我們尚未研制

39、出的中藥新藥，從而造成我國中藥信息資源廉價外流的局面。因此，中藥復(fù)方數(shù)據(jù)挖掘研究不僅可以提高我國現(xiàn)有中藥數(shù)據(jù)庫的利用價值，縮短我國中藥新藥開發(fā)的周期，而且也可以避免中藥信息資源的廉價流失。然而經(jīng)過多年的努力，信息處理技術(shù)用于中醫(yī)藥研究領(lǐng)域，我國雖起步較晚，但發(fā)展十分迅速。數(shù)據(jù)挖掘技術(shù)已開始應(yīng)用于中藥研究，但當(dāng)前我國中藥復(fù)方數(shù)據(jù)挖掘研究還存在一些問題：比如，由于對中藥復(fù)方數(shù)據(jù)(傳統(tǒng)方藥數(shù)據(jù)和現(xiàn)代研究數(shù)據(jù))沒有進(jìn)行科學(xué)管理，更缺乏系統(tǒng)分析的技術(shù)與方法，故信息利用的有效性和合理性較差。中藥復(fù)方的基本數(shù)據(jù)(方名、藥名、劑量、功用描述、主治癥名，等)不規(guī)范、不標(biāo)準(zhǔn)，這對方藥數(shù)據(jù)庫結(jié)構(gòu)和通用性產(chǎn)生了致命影

40、響，高質(zhì)量的數(shù)據(jù)處理不可能實(shí)現(xiàn)?，F(xiàn)有中藥復(fù)方的相關(guān)數(shù)據(jù)庫幾乎都是信息查詢類型的，尚沒有以中藥復(fù)方為對象，數(shù)據(jù)規(guī)范、標(biāo)準(zhǔn)、結(jié)構(gòu)合理、系統(tǒng)化程度較高的分析型中藥復(fù)方數(shù)據(jù)庫。中藥復(fù)方數(shù)據(jù)的分析處理中傳統(tǒng)數(shù)理統(tǒng)計方法仍占優(yōu)勢，人們開始討論新技術(shù)方法的運(yùn)用，但這又涉及到這些方法與中藥復(fù)方數(shù)據(jù)特點(diǎn)及中醫(yī)用藥思路的匹配問題。5.2基于Apriori算法的關(guān)聯(lián)規(guī)則挖掘系統(tǒng)的實(shí)現(xiàn)5.2.1連接數(shù)據(jù)庫本設(shè)計使用的后臺數(shù)據(jù)庫為SQL2000，用到的數(shù)據(jù)表為藥物表和方劑表。連接數(shù)據(jù)庫的代碼如下：Class.forName("com.microsoft.jdbc.sqlserver.SQLServerDriv

41、er");/建立JDBC-ODBC橋接器ConnectiondbConn=DriverManager.getConnection(dbURL,userName, userPwd); /連接到數(shù)據(jù)庫，提供相應(yīng)的用戶名、密碼Statement stmt= dbConn.createStatement(ResultSet.TYPE_SCROLL_SENSITIVE, ResultSet.CONCUR_UPDATABLE); /用dbConn連接創(chuàng)建SQL語句對象5.2.2位圖矩陣的建立位圖矩陣的建立是在查詢數(shù)據(jù)庫中數(shù)據(jù)的基礎(chǔ)上產(chǎn)生的。在查詢數(shù)據(jù)庫得到的位圖矩陣中，行表示方劑，列表示此數(shù)據(jù)庫

42、中的藥物，矩陣中的數(shù)據(jù)項由1和0表示，假如Ri，j = 1（R表示位圖矩陣，i表示橫坐標(biāo)，j表示縱坐標(biāo)）,表示第i個方劑中含有第j位對應(yīng)的藥物。ResultSet rsName = stmt.executeQuery(queryName);i=0;while(rsName.next() if(i<405) drugNamei = rsName.getString("藥名"); i+;ResultSet rsId = stmt.executeQuery(queryId);i=0;while(rsId.next() fangjiIdi+ = rsId.getString(

43、"方編號");/把方編號存入數(shù)組 for(int i = 0; i<1060;i+) for(int j = 0 ;j<405;j+) matrixij = '0' for(int i=0;i<1060;i+) String queryName1 = "select 藥名 from 藥物表 where 方編號="+fangjiIdi+" group by 藥名 order by 藥名" /找出一種方劑的藥物ResultSet rsName1 = stmt.executeQuery(queryName1

44、);l=0;while(rsName1.next() /把每次查找出的一種方劑的一種藥名存放在臨時數(shù)組'temp'中. templ = rsName1.getString("藥名");l+; for( int k=0;k<l;k+) for( int j=0;j<405;j+) if(tempk.equals(drugNamej) matrixij = '1' tempk=""rsName1.close();通過以上語句，能得到一個位圖矩陣，每一行代表一種方劑，每一列代表一種藥，一共有1060行，405列。當(dāng)一

45、種方劑中含有這種藥物時，那么在這個位圖矩陣的這位為1，否則為0。這樣，就能建立起一個關(guān)于藥物，方劑的位圖矩陣。位圖矩陣的構(gòu)造完成，為以后的運(yùn)算帶來了不用反復(fù)查詢事務(wù)數(shù)據(jù)庫的繁瑣，提高了算法的效率，增加了運(yùn)算的速度。5.2.3頻繁項集在尋找頻繁項集時，根據(jù)Apriori算法的要求，需要依次找出頻繁項集。在找頻繁1項集時，我們只需要從每列從上往下相加來求的這種藥物的支持度記數(shù)。所以它的方法與找頻繁2，3項集有所不同。rivate NumberCount GetItem() /找出所有的一項集 NumberCount ItemNumerCount=new NumberCount405; for( i

46、nt i=0;i<405;i+)int count=0; for(int j=0;j<1060;j+) if(matrixji='1') count+; /支持度記數(shù) int CountArray = i; /將藥物編號轉(zhuǎn)為數(shù)組 ItemNumerCounti = new NumberCount(CountArray,count); /將藥物編號和支持度記數(shù)存入ItemNumerCounti return ItemNumerCount; private NumberCount GetOneItem_t(float ComparePercent) /把滿足支持度的一項

47、集選出 int t = 0; NumberCount Item = GetItem();/調(diào)用 GetItem()，將返回值存入Item for(int i = 0 ;i<Item.length&&Itemi!=null;i+) if(Itemi.GetIsTerm(1060,ComparePercent) t+; NumberCount OneItem =new NumberCountt; /把Item中符合條件的存入OneItemtxint tx=0; for(int i = 0 ;i<Item.length&&Itemi!=null;i+) i

48、f(Itemi.GetIsTerm(1060,ComparePercent)&&tx<t) OneItemtx=Itemi;tx+; OneNumberCount = OneItem; /存入到OneNumberCount 數(shù)組里，為了以后找關(guān)聯(lián)規(guī)則 return OneItem;因為找2，3項集，它所使用的方法一樣，所以這里只介紹找2項集的具體方法。我們在找2項集時，由于Apriori算法的要求，必須先找到頻繁1項集頻繁2項集中的項必須是有頻繁1項集產(chǎn)生。在找到頻繁1項集后，我們將得到的項兩兩任意組合，算出它們的支持度，看支持度是否大于我們預(yù)先設(shè)定的大小，如果大于預(yù)先設(shè)

49、定的支持度，說明它們是頻繁2項集。private NumberCount GetTwoItems_t(float ComparePercent) NumberCount OneItem = GetOneItem_t(ComparePercent); /先找到1項集 int NumberTermLength = OneItem.length; int ArrayLength=NumberTermLength*1; int TermsArray = new intArrayLength; /定義一個與1項集長度相等的整型數(shù)組 int ArrayNumber=0; for(int i= 0 ;i&l

50、t;NumberTermLength;i+ )int tarray = OneItemi.GetNumberArray();/得到1項集編號的數(shù)組 for(intj=0;j<tarray.length&&ArrayNumber<ArrayLength;j+) TermsArrayArrayNumber=tarrayj; ArrayNumber+; Terms TowTerms = new Terms(TermsArray,2); int TermsTowArray =TowTerms.GetTerms();/得到兩兩組合的2維數(shù)組 int TowLenth = Te

51、rmsTowArray.length; NumberCount TwoItems = new NumberCountTowLenth;int t=0; for(int i = 0 ;i<TowLenth;i+) int towCount = Andmatrix(TermsTowArrayi);NumberCounttNumberCount=newNumberCount(TermsTowArrayi,towCount);if(tNumberCount.GetIsTerm(1060,ComparePercent) TwoItemst = tNumberCount;t+; TwoNumberC

52、ount =TwoItems; return TwoItems;5.2.4關(guān)聯(lián)規(guī)則當(dāng)我們找到頻繁項集時，我們需要一些有意義的數(shù)據(jù)，所以要求設(shè)定一個置信度，它的值越大，表明關(guān)聯(lián)程度越高。所以我們通過在系統(tǒng)中的“關(guān)聯(lián)規(guī)則”按扭去找頻繁項集中有意義的數(shù)據(jù)，去驗正它們的關(guān)聯(lián)程度。rivate String GetTwoItem(float ComparePercent,float Percent_G)String Two_G=""GetTwoItems_t(ComparePercent); for(int i=0 ;i<TwoNumberCount.length&&a

53、mp;TwoNumberCounti!=null;i+) int TowItem = TwoNumberCounti.GetNumberArray(); for(inj=0;j<OneNumberCount.length&&OneNumberCountj!=null;j+) int OneItem =OneNumberCountj.GetNumberArray(); if(TowItem0=OneItem0|TowItem1=OneItem0) floatPer_t= TwoNumberCounti.GetCount()/(Float.valueOf(OneNumberCountj.GetCount(); if(Per_t>=Percent_G) Per_t = Per_t*100; String Per_s = String.valueOf(Per_t); Per_s = Per_s.substring(0,Per_s.indexOf("."); if(TowItem0=OneItem0) Two_G+= drugNameTowItem1+"=>"+drugNameTowItem0+"="+Per_