Ａｐｒｉｏｒｉ改進算法及其在課程相關(guān)性分析中的應(yīng)用
2008-12-31 00:00:00董彩云劉培華
電腦知識與技術(shù) 2008年36期
摘要：該文分析與研究了Apriori算法，指出其在實用中存在的主要問題。鑒于此，該文提出了一種改進的關(guān)聯(lián)規(guī)則挖掘算法，使其可以有效地壓縮數(shù)據(jù)規(guī)模，并給出了改進后的關(guān)聯(lián)規(guī)則算法描述。最后將其應(yīng)用于課程相關(guān)性分析，得到了有益于課程設(shè)置挖掘結(jié)果。實驗結(jié)果表明了算法性能優(yōu)良，提高了數(shù)據(jù)挖掘執(zhí)行的效率。
關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；Apriori算法
中圖分類號：TP311文獻標識碼：A 文章編號：1009-3044(2008)36-2561-02
Apriori Improved Algorithm and its Application in Course Correlation
DONG Cai-yun1，LIU Pei-hua2
(1.Open college，Shan Dong Broadcast TV University， Jinan 250014，China;2.School of Information Science Engineering， Jinan University， Jinan 250022，China)
AbstraCt: By analyzing and studying Apriori algorithm， this paper finds problems. Thus， this paper presents a new method which can effeCtively reduce the number of data. This paper also offers a particular description of the new algorithm. At last the new algorithm is used to course correlation， by this we can get some useful result which is helpful to decision making of course setting .The results show the algorithm can improve the data mining performance and is excellent.
Key words: Datamining; Association rules; Apriori algorithm
1 Apriori算法及其存在的問題
1993年，Agrawal[1]等人提出關(guān)聯(lián)規(guī)則挖掘算法后，給出了經(jīng)典關(guān)聯(lián)規(guī)則挖掘算法Apriori，它是一種找頻繁項集的基本算法。利用該算法進行關(guān)聯(lián)規(guī)則的挖掘是一個兩步過程[2]：1) 找出所有頻繁項集：這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持計數(shù)一樣。2) 由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則：這些規(guī)則必須滿足最小支持度和最小置信度。挖掘關(guān)聯(lián)規(guī)則的總體性能由第一步?jīng)Q定，算法的核心也主要在尋找頻繁項目集上。主要是基于Apriori性質(zhì)：頻繁項集的所有非空子集都必須也是頻繁的。利用這個性質(zhì)可以有效地壓縮搜索空間。算法主要思路如下：為找Lk，通過Lk-1與自己連接產(chǎn)生候選k-項集的集合，該侯選項的集合記作CK，依次下去直到CK+1為空。在產(chǎn)生Ck，k=1，2，…，K時，利用剪枝策略壓縮Ck。利用任何非頻繁的(k-1) -項集都不可能是頻繁k-項集這一Apriori性質(zhì)，刪去那些(k-1)-子集不在Lk-1中的k-候選項目集。
使用Apriori算法進行關(guān)聯(lián)規(guī)則挖掘，可以比較有效地產(chǎn)生關(guān)聯(lián)規(guī)則，但在運行時卻由于運行效率問題難以推廣使用。主要原因是：
1) 數(shù)據(jù)庫掃描的次數(shù)太多；2) 另外，當模式太長時產(chǎn)生的候選項目集太多。導(dǎo)致數(shù)據(jù)庫或K太大時，算法的時耗太大或無法完成。本文主要討論的是算法的效率問題。特別是目前，隨著數(shù)據(jù)倉庫中數(shù)據(jù)的持續(xù)增加，在數(shù)據(jù)挖掘過程中，進行一次數(shù)據(jù)挖掘的時間越來越長。
2 改進算法
2.1 改進依據(jù)
針對于Apriori算法為了確定每個侯選項的計數(shù)，需要反復(fù)掃描事務(wù)數(shù)據(jù)庫的弊端，本文從減少掃描事務(wù)數(shù)的目的出發(fā)，提出了一個改進的算法來得到頻繁項集，該算法仍基于支持度和可信度。
算法依據(jù)：1) 所有侯選項集Ck是Ck-1項的超集；2) 如果某一事務(wù)中不包含侯選項集，則刪除該事務(wù)后不會影響頻項集的產(chǎn)生。
2.2 算法改進的思想
算法思想：給事務(wù)數(shù)據(jù)庫中的每一項增加一個標志位delete，初值為1。在每次計算侯選項集Ck出現(xiàn)次數(shù)的過程中，若不包含Ck中某一項的事務(wù)，則將該標志位的值置為true，若包含某一項，則將值置為1，并給該項的計數(shù)加１，且標記不再改變。若最終該項標記為true，即事務(wù)不包含選項的任一項，則將其從事務(wù)數(shù)據(jù)庫中刪除。這樣計算侯選項集支持度所涉及的記錄數(shù)目將小于事務(wù)數(shù)據(jù)庫中實際記錄數(shù)，并且隨k值的增大，這一差值也不斷增大，因而有效降低了侯選項集的計數(shù)速度，提高了整個算法的效率。
2.3 改進算法的實現(xiàn)
算法:改進后的Apriori.
輸入:事務(wù)數(shù)據(jù)庫D；最小支持度閾值min_sup
輸出:D中的頻繁項目集L。
Method:
(1) L1=find-frequent_l_itemsets(D);
(2) For(k=2;Lk-1≠Ф，k++){
(3)Ck=apriori_gen(Lk-1，min_sup); //掃描Ｄ，對侯選項計數(shù)
(4)for each transaCtion t∈D{//取得事務(wù)t的侯選項集合
(5) Ct=subset(Ck，t);//設(shè)置刪除標記
(6)Ift.delete=1 then {
(7)If ?埸Ctthen {
(8)t.delete=true;
(9) break;}
(10) elsec.count++;
}
(11)elseifc∈Ct then{
(12)c.count++;
(13)t.delete=1 }
}//若t中不包含任何侯選項，將其
//從Ｄ中刪除
(14)ift.delete=true then
(15)delete t from transaCtion
(16)Lk={c∈Ck|c.count≥min_sup}
}
(17)return L=∪kLk;
procedure apriori_gen(Lk_1:frequent(k-1)-itemsets;
min_sup:minimum support threshold)
(1)for each itemset l1∈Lk-1
(2)for each itemset l2∈Lk-1
(3) if(l1[1]=l2[1])∧ (l1[2]=l2[2])∧ l2[k-2]) …∧(l1[k-２]=l2[k-２]) ∧ (l1[k-1]=l2[k-1])then{
(4) c=l1 join l2; //join step;generate candidates
(5)if has_infrequent_subset(c，Lk-1) then
//prune step:remove unfruitful candidate
(6)delete c
(7)else add c to Ck;
}
(8)return Ck;
procedure has_infrequent_subset( c: candidate k-itemset; Lk-1:frequent(k-1)-itemset);
(1)for each (k-1)-subset s of c
(2)if s Lk-1 then
(3)return TRUE;
(4)return 1;
2.4 改進算法的驗證
采用了如表1的事務(wù)數(shù)據(jù)庫，對該算法進行了驗證。設(shè)置最小支持度數(shù)為2。
采用改進的Apriori算法進行找侯選項集，頻繁項集的過程如下所示：
L1C2
■
一次掃描修改后的事務(wù)數(shù)據(jù)庫Ｄ1 L2 C3
■
二次掃描修改后的事務(wù)數(shù)據(jù)庫Ｄ2L3
■
其中事務(wù)T5由于不包含中的C2中的任何項集，在第二遍掃描后可以刪除；同樣道理，事務(wù)T1在第三遍掃描后可以刪除，使得掃描數(shù)據(jù)庫的規(guī)模減小，提高了算法的效率。而得到的頻繁項集與經(jīng)典Apriori算法的相同。由此可見算法是可取的。（下轉(zhuǎn)第2565頁）
（上接第2562頁）
3改進算法在教學中的應(yīng)用
目前各高校都積累了大量的學員成績信息，管理人員很難從這些信息中找出有用的規(guī)律。因此將數(shù)據(jù)挖掘用于發(fā)現(xiàn)課程之間的關(guān)系對科學設(shè)置課程指導(dǎo)學員選課是有意義的。
筆者采用關(guān)聯(lián)規(guī)則算法對某學院的學員成績數(shù)據(jù)庫進行采掘，目的是得到課程的相關(guān)性信息，以期發(fā)現(xiàn)課程之間的關(guān)系，更合理的設(shè)置課程和指導(dǎo)學員選課。算法重點研究和設(shè)計了“學員”、“課程”為主題的數(shù)據(jù)集市，為數(shù)據(jù)挖掘提供集成的數(shù)據(jù)源。在預(yù)處理階段，為保證數(shù)據(jù)的準確與完整，對學員成績進行了以下處理：1)學員補考的問題。按照學校的有關(guān)規(guī)定，學員考試不及格必須補考，為了合格證挖掘結(jié)果的準確與合理，按他們的原始成績?yōu)闇省?）由于其它原因有科目未參加正常考試者，參考其補考成績及其其它科目的成績給予一個適當?shù)某煽儭?）對學員成績進行分檔處理。將成績分為A（85-100）、B（70-84）、C（60-69）、D（0-59）。
由于在數(shù)據(jù)挖掘階段，筆者采用改進的Apriori算法根據(jù)學員的考試成績進行分析，設(shè)置支持度為0.1，置信度為0.8，得到了有關(guān)課程的關(guān)聯(lián)規(guī)則。現(xiàn)將挖掘結(jié)果中的部分關(guān)聯(lián)規(guī)則在采用表格形式表示各項分別為（no，front ， rear，C），其含義分別是(產(chǎn)生關(guān)聯(lián)規(guī)則的序號，關(guān)聯(lián)規(guī)則前件，關(guān)聯(lián)規(guī)則后件，可信度)，其中關(guān)聯(lián)規(guī)則項需要通過查詢組合第二列和第三列得出來。部分結(jié)果如表2所示。
通過分析挖掘結(jié)果可以得出加強《高等數(shù)學》《數(shù)字電子技術(shù)》的學習有助于對《計算機組成原理》及《微機原理》課程的學習，其他規(guī)則同樣可按照這種方式分析。如果分析人員對結(jié)果不滿意，可以調(diào)整支持度，可信度及興趣度閾值，重新執(zhí)行挖掘過程，直到滿意為止。用戶根據(jù)挖掘結(jié)果做出決策，合理的設(shè)置課程，同時該也可以指導(dǎo)學員選課，有利于學員更好的學習各門課程。
4 結(jié)束語
本文給出的減小事務(wù)數(shù)據(jù)庫的規(guī)模求得頻繁項集的方法，能夠提高算法的效率，特別是隨著事務(wù)數(shù)據(jù)庫的增大，侯選項集的增大，此算法的效率更加明顯。但在挖掘的過程中也出現(xiàn)了一些問題，比如有些新開設(shè)的課程信息是用戶所關(guān)心的，但在挖掘過程中由于其出現(xiàn)頻率低，而不能得到其關(guān)聯(lián)信息，因此影響了挖掘的結(jié)果，下一步的工作是為各課程增設(shè)權(quán)值以期發(fā)現(xiàn)新增課程與原課程之間的聯(lián)系，得到更為合理的用戶更為感興趣的挖掘結(jié)果。
參考文獻：
[1] Agrawal R， Imielinski T， Swami A. Mining Association Rules between Sets of Items in Large Database[M]. In SIGMOD’ 93，Washington，DC， May 1993.207-216.
[2] 范明， 孟小峰，等譯. 數(shù)據(jù)挖掘概念與技術(shù)[M].北京: 機械工業(yè)出版社. 2003.3.150-221.
[3] 賈彩燕， 倪現(xiàn)君.關(guān)聯(lián)規(guī)則挖掘研究述評[J]. 計算機科學， 2003， 30(4):145-148.
[4] 朱明. 數(shù)據(jù)挖掘[M]. 北京: 中國科學大學出版社. 2002.5.129-140.
[5] 馬光志， 龍碩柱. 基于聚類和分類的自學習系統(tǒng)模型[J]. 計算機工程與應(yīng)用， 2003， 39(10):83-84.
[6] 高春玲.關(guān)聯(lián)規(guī)則挖掘的實現(xiàn)[D]. 鄭州大學 2001，13-15.
注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”
