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

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

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

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

4、60;     挖掘流通借閱事務(wù)數(shù)據(jù)庫中所有的關(guān)聯(lián)規(guī)則的問題可以被劃分成如下兩個(gè)子問題：        找出所有具有最小支持度的項(xiàng)集(即頻繁項(xiàng)集)，可用Apriori算法來找出頻繁項(xiàng)集。由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，對(duì)于每一個(gè)頻繁項(xiàng)集I，找出其中所有的非空子集，然后，對(duì)于每一個(gè)這樣的子集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ī)則，從而指導(dǎo)人們的一些管理決策。目前，關(guān)聯(lián)規(guī)則的挖掘方法主要是找出數(shù)據(jù)庫中的頻繁項(xiàng)集，然后由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則。        (二)Aprior算法        Apriori算法是一種挖掘布爾關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集的算法，它

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

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

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

11、0;      Apriori-gen過程由Lk-1產(chǎn)生第K次迭代時(shí)的候選項(xiàng)集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的每個(gè)包含k-1個(gè)項(xiàng)目的子集s)        If(s不屬于Fk-1) &

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

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

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

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

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

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

19、。其他的連接過程可以參閱Apriori的連接。本文通過設(shè)置最小置信度閾值以找出強(qiáng)關(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項(xiàng)集        while(!candidates.empty

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

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

23、#160;      vector&candidates)                for(int i = 0; i < patterns.size(); +i)/ 遍歷過濾后的候選k-1項(xiàng)集， 兩兩連接        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項(xiàng)集， 保存到輸出列表        candidates.push_back(ItemsCounter(items，0，0);                 

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