基于數據挖掘Apriori算法實現與應用

山東科技大學數學與系統科學學院 李 瀟

基于數據挖掘Apriori算法實現與應用

山東科技大學數學與系統科學學院 李 瀟

本文主要對數據挖掘的有關算法進行學習與應用。首先介紹了這些算法的基本思想和算法步驟，然后運用這些算法進行實際問題的求解。本文著重介紹的是關聯規則的Apriori算法。對Apriori算法，用其對當下高等學校排課的問題進行求解。

數據挖掘；Apriori算法

1.關聯規則

給定一個事物集D，挖掘關聯規則問題就是尋找支持度和置信度分別大于用戶給定的最小閥值的關聯規則。

我們在用關聯規則解決某一問題時一般遵循一下步驟：

（1）任務：描述變量之間的關聯關系；

（2）結構：用概率表示的“關聯規則”；

（3）評分函數：支持度和置信度的閥值；

（4）搜索方法：系統搜素方法（通常使用的是帶有修剪的廣度優先）；

（5）數據管理技術：多重線性掃描。

2.Apriori算法及改進

Apriori算法是挖掘關聯規則的最典型算法，該算法將挖掘關聯規則的過程分為兩個步驟：第一步利用迭代，找出所有的頻繁項集；第二步利用頻繁項集構造出強關聯規則。算法的核心是利用剪枝步和連接步找出所有的頻繁項集。

最后可能會產生大量的候選集和迭代過程中需要大量的掃描數據庫，是Apriori算法運行效率不高的重要原因。為了提高算法的運算效率，Mannila曾經提出過一個Apriori算法的改進，即修剪算法。因為一個項集是頻繁項集當且僅當它的所有子集都是頻集。那么，如果Ck中某個候選項集中有一個（k-1）子集不是頻集，那么即可以通過修剪算法剪掉Ck。正因為有了修剪算法可以顯著降低計算所有的候選項集支持度。可以減少產生大量的候選項集。

另一種解決方法是，可以利用哈希表存儲數據信息，包含該記錄的編號和它的字段長度。在每次的掃描時，只掃描表中存在的記錄，不需要每條記錄都掃描。通過輔助表F，減少數據庫的訪問次數，提高運算速度。

3.Apriori算法在學生成績中的應用

3.1 問題引入

成績是國內各高校評價學生的重要指標，合理開發利用這些資源，利用數據挖掘分析這些學生成績，找到課程之間的相關關系，必將對課程的開設安排具有重要的指導作用。

以國內某大學01屆計算機專業學生在校四年的學習成績為數據源，選取成績數據庫中計算機網絡，C語言，計算機基礎，外語，高等數學，數據庫原理等8門課程作為研究對象，找出某門課程對其他課程的開設是否有影響，為學校教科老師以后排課提供參考，為以后學生選課提供依據。

3.2 建模過程

（1）數據清洗：原始數據庫中包含全校各個專業、各個年級、各個學科的所有成績，某些記錄難免會有一些差錯或者從經驗上看沒有關聯的數據，為了便于進行數據挖掘，只選擇某班部分學生的8門課程成績作為挖掘對象，去掉其他所有不需要的字段，刪除完全空白記錄，如果某條記錄中的某一兩門課程成績缺少，則該條記錄缺少的成績補為該科成績的平均分，對于某條記錄中的某門課程成績有多于一個成績的情況，則該門成績按第一次成績計算。則清洗后的數據表部分數據如表2.1所示。

表2.1

（2）數據轉換：由于編寫的Aprior算法程序是是處理離散數值的，因此，需要將數據進行轉化，將大于等于90分，大于等于80且小于90，大于等于70且小于80，大于等于60且小于70，小于60的成績分別用12345表示。將8門課程依次用ABCDEFGH表示。

（3）數據挖掘：數據挖掘過程主要是利用Apriori算法，采用廣度優先的迭代搜素，設最小支持度為30%，產生頻繁子集50個，從產生的頻繁項目集中產生子集，根據關聯規則挖掘算法原理，設置最小置信度60%，得到的關聯規則15個，部分規則如表2-2所示。

表2.2

3.3 結果分析

第五條規則說明數據庫原理成績在80-90，計算機網絡也在80-90的支持度為58.4%，置信度為76.5%，第六條規則說明C++程序設計在80-90分，計算機網絡也在80-90的支持度為56.9%，置信度為83.4%這兩個規則可信度和置信度都較高，但實際有沒有關聯還需要做深入的討論。

上面第二條規則說明《計算機基礎》成績在70-80分之間，《高等數學》在80-90分之間的支持度為55.8%，置信度為87.2，雖然支持度和置信度都達到了要求，但是根據老師多年的教學經驗，這兩者之間并沒有很強的關系，因此在實際排課中我們要實際經驗聯系數據做出安排。

3.4 模型改進

在上面建模過程中，在數據轉換時，將成績離散化為1-5的值，這樣每一門課都會有5個不同的表示，例如A1、A2、A3、A4、A5，10門課就會有50個不同的符號來表示每一個項目。雖然之中劃分對于分析沒門課程之間的聯系會給出更加有利和詳細的證據。實際情況中，每一個專業大學四年所學課程通常都是在三四十門以上。如果仍談按照以上的方式進行數據處理,掃描數據庫中上百條記錄，程序的運行效率會很低。

綜上所述，為了兼顧程序的運行效率和得到確實可信的結果，當需要掃描大數據的數據庫時，在數據轉換時，不再將成績劃分成五個等級，而是將成績劃分為2個等級，如果成績大于該科的平均分，則該成績記為1，否則記為0

然后再利用matlab程序，導入內存中：Data=xlsread(‘E:ookl’)；

這樣就將excel中的數據讀入data中。

將數據存儲到計算機內存中，當運行Apriori算法程序時，不需要每次都掃描數據庫，只需掃描一次數據庫文件，以后每次迭代中都只是掃描存儲到計算機內存中的矩陣。加快了數據訪問速度。模型改進之后，需要訪問的數據量減少了一半以上，數據的訪問次數也減少了很多，因此程序的運行效率會有顯著的提高。這是今后在做大數據挖掘時，加快程序運行速度的一個解決辦法。

4.結語

對于某些事情，憑借經驗完全可以做出決策，如學校課程的安排，但是這些決策沒有堅強的理論基礎做支撐，有時候是很難站住腳的。但是如果我們能運用數據挖掘的有關知識，為這些經驗提供理論科學依據，就會讓這些經驗顯得更加可信。需要我們運用正確的方法，分析數據，做出決策，而數據挖掘技術就是最正確的方法。

[1]Xian jun Ni.Research of Data Mining Based on Neural Networks.北京:水利水電出版社,2003.

[2]史忠植.知識發現[M].北京:清華大學出版社,2002.

[3]張志霞,許童羽等.高等學校成績分析方法的研究[J].沈陽農業大學學報,2008-06,10(3):322-324.

[4]楊洪偉,許童羽.Apriori算法在學生成績分析中的應用研究[J].現代計算機(專業版),2010.

[5]李金忠.關聯規則Apriori算法[J].電腦編程技巧與維護,2008(6):35-37.

[6]常朝德,代永衛等.關聯規則在公安情報信息系統中的應用[J].計算機工程與應用,2008,44(5):75-78.

[7]趙輝.數據挖掘技術在學生成績分析中的研究及應用[D].大連:大連海事大學,2007.

[8]陸楠.關聯規則的挖掘及其算法的研究[D].長春:吉林大學,2007.

[9]周根貴.數據倉庫與數據挖掘[M].浙江:浙江大學出版社,2004.