淺析改進的Apriori關(guān)聯(lián)挖掘算法的實踐

1、淺析改進的Apriori關(guān)聯(lián)挖掘算法的實踐         這篇淺析改進的Apriori關(guān)聯(lián)挖掘算法的實踐的關(guān)鍵詞是數(shù)據(jù)挖掘,Apriori算法,圖書館管理,讀者管理,                    摘要：本文介紹了數(shù)據(jù)挖掘技術(shù)在圖書館中的應(yīng)用，并運用改進的Apriori關(guān)聯(lián)挖掘算法對安徽省圖書館自動化系統(tǒng)中讀

2、者流通庫進行挖掘，并對挖掘出的結(jié)果及其意義進行評價，從而為圖書館讀者管理、圖書資源的采購提供決策支持。        關(guān)鍵詞：數(shù)據(jù)挖掘 Apriori算法 圖書館管理 讀者管理        數(shù)據(jù)挖掘技術(shù)在商業(yè)領(lǐng)域內(nèi)的應(yīng)用給圖書館帶來了很大的啟發(fā)。圖書館的數(shù)據(jù)庫可以運用數(shù)據(jù)挖掘技術(shù)中的關(guān)聯(lián)規(guī)則分析、聚類分析、決策樹、時間序列分析等數(shù)據(jù)挖掘方法，以找出數(shù)據(jù)庫中蘊藏的對于圖書館管理有用的潛在規(guī)則，并且通過描述和預(yù)測，為圖書館的圖書采購、讀者

3、服務(wù)、館藏目錄設(shè)置等管理工作提供決策支持。        關(guān)聯(lián)規(guī)則是與多數(shù)人想象的挖掘過程中最相近的一種數(shù)據(jù)挖掘形式，即尋找在同一事件中出現(xiàn)的不同項的相關(guān)性。關(guān)聯(lián)規(guī)則的研究有助于發(fā)現(xiàn)數(shù)據(jù)庫中不同商品間的聯(lián)系，找出顧客購買行為模式。在圖書館運用關(guān)聯(lián)規(guī)則分析可以細分出讀者群，根據(jù)其借閱情況提供不同的服務(wù)，為圖書館的管理決策提供參考。關(guān)聯(lián)規(guī)則的核心算法是Apriori算法。        關(guān)聯(lián)規(guī)則的基本概念及算法  

4、60;     挖掘流通借閱事務(wù)數(shù)據(jù)庫中所有的關(guān)聯(lián)規(guī)則的問題可以被劃分成如下兩個子問題：        找出所有具有最小支持度的項集(即頻繁項集)，可用Apriori算法來找出頻繁項集。由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則，對于每一個頻繁項集I，找出其中所有的非空子集，然后，對于每一個這樣的子集a，如果support(I)與support(a)的比值大于最小置信度，則存在規(guī)則a=>(I-a)。      

5、0; (一)關(guān)聯(lián)規(guī)則算法        關(guān)聯(lián)規(guī)則的挖掘主要是在數(shù)據(jù)庫中找出支持用戶指定的最小支持度S和最小置信度C的關(guān)聯(lián)規(guī)則，從而指導人們的一些管理決策。目前，關(guān)聯(lián)規(guī)則的挖掘方法主要是找出數(shù)據(jù)庫中的頻繁項集，然后由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則。        (二)Aprior算法        Apriori算法是一種挖掘布爾關(guān)聯(lián)規(guī)則的頻繁項集的算法，它

6、主要是利用逐層搜索的迭代方法來尋找數(shù)據(jù)庫中頻繁出現(xiàn)的項集。主要步驟是：第一步，產(chǎn)生頻繁1-項集L1，掃描數(shù)據(jù)庫D，出現(xiàn)在D中各個數(shù)據(jù)項的集合就是頻繁1-項候選項集C1，并統(tǒng)計出每個數(shù)據(jù)項出現(xiàn)的次數(shù)，次數(shù)大于最小支持計數(shù)(預(yù)先)定義的項的集合就是頻繁1-項集L1;第K步，產(chǎn)生頻繁K-項集Lk，利用上一步產(chǎn)生的頻繁(K-1)-項集Lk-1，與自己連接產(chǎn)生K-項集候選集Ck，掃描數(shù)據(jù)庫事務(wù)庫，計算Ck中每個成員出現(xiàn)的次數(shù)，將小于最小支持度的候選項刪除，最后產(chǎn)生頻繁K-項集。        算法：Apriori使用根據(jù)候選

7、生成的逐層迭代找出頻繁項集        輸入：流通借閱數(shù)據(jù)庫D;最要支持度閾值minsup        輸出：D中的頻繁項集L        算法代碼：        1)L1一所有頻繁項集1-項目集;      &

8、#160; 2)for(k=2;Lk，k+)        3)Ck=apriori_gen(Lk-1，minsupport)        4)for all CCt do        5)Ct=Subset(Ck，T)        6)For all cCt d

9、o        7)c.count+;        8)        9)Lk=cCk|support(c)>=minsup        10)        11)return L=所

10、有的Lk        Apriori算法的第1步找出頻繁1-項集的集合L1。在第210步中，Lk-1用于產(chǎn)生候選Ck，以找出Lk。Apriori過程產(chǎn)生候選，第3步使用Apriori性質(zhì)刪除那些具有非頻繁子集的候選，第4步掃描數(shù)據(jù)庫，第5步使用subset函數(shù)找出事務(wù)中的候選的所有子集，第6步和第7步對每個這樣的候選累加計數(shù)。最后，所有滿足最小支持度的候選會形成頻繁項集L。        Apriori-gen過程 

11、0;      Apriori-gen過程由Lk-1產(chǎn)生第K次迭代時的候選項集Ck，該過程描述如下：        For each itemset I1Lk-1        For each itemset I2Lk-1        If (I11=I21)(I12=I22(I1K-2=I2K

12、-2)(I1K-1 =I2 K-2)(I1K-I=I2K-1)        Then c=I1，I12，I1K-I，I2K-1);        Ck=Ck U c;        For(c的每個包含k-1個項目的子集s)        If(s不屬于Fk-1) &

13、#160;      從Ck中刪除C;                Return(Ck);        改進的Apriori算法在圖書館的具體實現(xiàn)        以安徽省圖書館某年度讀者借閱事務(wù)庫為例，可從圖書館借閱

14、記錄中挖掘出形如“讀者-圖書”強關(guān)聯(lián)規(guī)則。首先要進行數(shù)據(jù)清洗，只保留屬性概念中分層最低層的屬性項，將同一個讀者的所有借閱記錄合并為一條記錄。        (一)算法思想        在讀者借閱記錄關(guān)聯(lián)規(guī)則挖掘過程中有一些特殊的性質(zhì)，因為每一個讀者借閱記錄的長度是固定的，即含有五個單項，前四個是屬性值，最后一個是圖書分類號，并且要挖掘的規(guī)則最后一項必須是圖書分類號，且不能出現(xiàn)沖突的屬性值或圖書分類號。基于這些特殊性質(zhì)，在數(shù)據(jù)挖掘中對A

15、priori改進算法如下：        1)把壓縮過的事務(wù)集讀入內(nèi)存;        2)掃描事務(wù)集，找到每一類頻繁單項：即頻繁的年齡段、頻繁的學歷、頻繁的職稱、頻繁的職業(yè)、頻繁的圖書分類。        3) 把各類頻繁的屬性單項和頻繁的圖書分類單項連接成 2 - 候選頻繁項集， k = 2。即生成年齡-圖書類，學歷-圖書類，職業(yè)-圖書類，職稱-圖書類，

16、分別生成頻繁2項集。        4) 檢查k-候選頻繁項集，記錄其支持度和前件的支持度。頻繁項集的連接條件是前n項是為讀者屬性項，且讀者的屬性項內(nèi)容各不相同，最后一項為相同的圖書分類項。        5) 輸出置信度和支持度達到要求的頻繁 k - 頻繁項集。置信度為支持度除以前件的支持度。        6) 用得到k - 頻繁項集互相連接得到k+1

17、- 候選頻繁項集。通過剪枝，可減少連接的頻繁項集的個數(shù)，提高程序運行的效率。下面的是剪枝連接的規(guī)則：        a) 如果頻繁項集A 和 B 最后一項不同的時候不能連接。        b) 含有屬于同一屬性類別的不同單項，則不能連接。        c) 頻繁項集也不能和自身連接。      

18、  d) 如果用conf代表前件支持度，那么當min ( A.conf， B.conf)/最小支持度<最小置信度時，不能連接 A，B。        e) 其它情況可以連接。        7) k +， 如果生成的候選頻繁項集數(shù)目不為0，轉(zhuǎn)4)，否則結(jié)束。        本算法主要改進是步驟6， 這是經(jīng)典的Apriori算法沒有的

19、。其他的連接過程可以參閱Apriori的連接。本文通過設(shè)置最小置信度閾值以找出強關(guān)聯(lián)規(guī)則，令圖書類型為每條規(guī)則后件，讀者屬性為每條規(guī)則前件，最后得到關(guān)聯(lián)規(guī)則。        (二)程序?qū)崿F(xiàn)        / apriori算法的程序        void Apriori:Do()      

20、60;         vector candidates;        vector patterns;        generate2candidates(candidates); / 生成候選2項集        while(!candidates.empty

21、() / 當候選項集為空時中止         verify_candidate(candidates， patterns);/ 過濾候選k-1項集， 返回用于連接生成候選k項集的列表，同時輸出滿足所有條件的規(guī)則        generate_k_candidates(patterns，candidates); / 連接生成候選k項集， 準備下一次循環(huán)       

22、 patterns.clear();                        生成K項候選頻繁集：        inline void Apriori：generate_k_candidates(const vector&patterns， &

23、#160;      vector&candidates)                for(int i = 0; i < patterns.size(); +i)/ 遍歷過濾后的候選k-1項集， 兩兩連接        for(int j = i+1; j < patter

24、ns.size(); +j)        if(Items_method：Is_compatible_Items(patternsi.items_，patternsj.items_)/ 首先判斷能否連接        if(double)min(patternsi.freq_，patternsj.freq_) / minSupport_ >= minConf_)     

25、0;  Items items = Items_method：join_Items(patternsi.items_，patternsj.items_);/ 連接得到k項集， 保存到輸出列表        candidates.push_back(ItemsCounter(items，0，0);                 

26、       (三)算法評價        通過上述的介紹，可以看到本算法的思路基本上與Apriori算法保持一致，即它們的共同之處是通過掃描數(shù)據(jù)得到那些支持度不小于用戶給定的最小支持度的頻繁項集，但是又有不同之處就是在掃描數(shù)據(jù)庫之前就進行了剪枝，在剪枝后再重新連接掃描數(shù)據(jù)庫，減少了掃描的次數(shù)。        在算法效率上，通過數(shù)據(jù)壓縮可將挖掘的數(shù)據(jù)一次性掃描進入內(nèi)存中，避免了重復(fù)磁盤I/O操作，沒有壓縮的數(shù)據(jù)不可能一次性讀入內(nèi)存，從而提高了計算效率;另通過數(shù)據(jù)壓縮減少了每一項字符長度，特別是在比較兩項是否相同的時候，需比較的字符數(shù)就少了很多，可以提高運算速度。通過使用數(shù)據(jù)壓縮的方式，節(jié)省了內(nèi)存，減少了候選集比較的時間，從而生成頻繁項集速度將更快，同時加入了同屬性列只能出現(xiàn)一次和后件必須相同的約束，使得連接次數(shù)大大減少，計算復(fù)雜度也降低了。在對圖書館這樣的大型數(shù)