山東科技大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院 李 瀟

基于數(shù)據(jù)挖掘Apriori算法實(shí)現(xiàn)與應(yīng)用

山東科技大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院 李 瀟

本文主要對(duì)數(shù)據(jù)挖掘的有關(guān)算法進(jìn)行學(xué)習(xí)與應(yīng)用。首先介紹了這些算法的基本思想和算法步驟，然后運(yùn)用這些算法進(jìn)行實(shí)際問(wèn)題的求解。本文著重介紹的是關(guān)聯(lián)規(guī)則的Apriori算法。對(duì)Apriori算法，用其對(duì)當(dāng)下高等學(xué)校排課的問(wèn)題進(jìn)行求解。

數(shù)據(jù)挖掘；Apriori算法

1.關(guān)聯(lián)規(guī)則

給定一個(gè)事物集D，挖掘關(guān)聯(lián)規(guī)則問(wèn)題就是尋找支持度和置信度分別大于用戶給定的最小閥值的關(guān)聯(lián)規(guī)則。

我們?cè)谟藐P(guān)聯(lián)規(guī)則解決某一問(wèn)題時(shí)一般遵循一下步驟：

（1）任務(wù)：描述變量之間的關(guān)聯(lián)關(guān)系；

（2）結(jié)構(gòu)：用概率表示的“關(guān)聯(lián)規(guī)則”；

（3）評(píng)分函數(shù)：支持度和置信度的閥值；

（4）搜索方法：系統(tǒng)搜素方法（通常使用的是帶有修剪的廣度優(yōu)先）；

（5）數(shù)據(jù)管理技術(shù)：多重線性掃描。

2.Apriori算法及改進(jìn)

Apriori算法是挖掘關(guān)聯(lián)規(guī)則的最典型算法，該算法將挖掘關(guān)聯(lián)規(guī)則的過(guò)程分為兩個(gè)步驟：第一步利用迭代，找出所有的頻繁項(xiàng)集；第二步利用頻繁項(xiàng)集構(gòu)造出強(qiáng)關(guān)聯(lián)規(guī)則。算法的核心是利用剪枝步和連接步找出所有的頻繁項(xiàng)集。

最后可能會(huì)產(chǎn)生大量的候選集和迭代過(guò)程中需要大量的掃描數(shù)據(jù)庫(kù)，是Apriori算法運(yùn)行效率不高的重要原因。為了提高算法的運(yùn)算效率，Mannila曾經(jīng)提出過(guò)一個(gè)Apriori算法的改進(jìn)，即修剪算法。因?yàn)橐粋€(gè)項(xiàng)集是頻繁項(xiàng)集當(dāng)且僅當(dāng)它的所有子集都是頻集。那么，如果Ck中某個(gè)候選項(xiàng)集中有一個(gè)（k-1）子集不是頻集，那么即可以通過(guò)修剪算法剪掉Ck。正因?yàn)橛辛诵藜羲惴梢燥@著降低計(jì)算所有的候選項(xiàng)集支持度。可以減少產(chǎn)生大量的候選項(xiàng)集。

另一種解決方法是，可以利用哈希表存儲(chǔ)數(shù)據(jù)信息，包含該記錄的編號(hào)和它的字段長(zhǎng)度。在每次的掃描時(shí)，只掃描表中存在的記錄，不需要每條記錄都掃描。通過(guò)輔助表F，減少數(shù)據(jù)庫(kù)的訪問(wèn)次數(shù)，提高運(yùn)算速度。

3.Apriori算法在學(xué)生成績(jī)中的應(yīng)用

3.1 問(wèn)題引入

成績(jī)是國(guó)內(nèi)各高校評(píng)價(jià)學(xué)生的重要指標(biāo)，合理開(kāi)發(fā)利用這些資源，利用數(shù)據(jù)挖掘分析這些學(xué)生成績(jī)，找到課程之間的相關(guān)關(guān)系，必將對(duì)課程的開(kāi)設(shè)安排具有重要的指導(dǎo)作用。

以國(guó)內(nèi)某大學(xué)01屆計(jì)算機(jī)專業(yè)學(xué)生在校四年的學(xué)習(xí)成績(jī)?yōu)閿?shù)據(jù)源，選取成績(jī)數(shù)據(jù)庫(kù)中計(jì)算機(jī)網(wǎng)絡(luò)，C語(yǔ)言，計(jì)算機(jī)基礎(chǔ)，外語(yǔ)，高等數(shù)學(xué)，數(shù)據(jù)庫(kù)原理等8門課程作為研究對(duì)象，找出某門課程對(duì)其他課程的開(kāi)設(shè)是否有影響，為學(xué)校教科老師以后排課提供參考，為以后學(xué)生選課提供依據(jù)。

3.2 建模過(guò)程

（1）數(shù)據(jù)清洗：原始數(shù)據(jù)庫(kù)中包含全校各個(gè)專業(yè)、各個(gè)年級(jí)、各個(gè)學(xué)科的所有成績(jī)，某些記錄難免會(huì)有一些差錯(cuò)或者從經(jīng)驗(yàn)上看沒(méi)有關(guān)聯(lián)的數(shù)據(jù)，為了便于進(jìn)行數(shù)據(jù)挖掘，只選擇某班部分學(xué)生的8門課程成績(jī)作為挖掘?qū)ο?，去掉其他所有不需要的字段，刪除完全空白記錄，如果某條記錄中的某一兩門課程成績(jī)?nèi)鄙伲瑒t該條記錄缺少的成績(jī)補(bǔ)為該科成績(jī)的平均分，對(duì)于某條記錄中的某門課程成績(jī)有多于一個(gè)成績(jī)的情況，則該門成績(jī)按第一次成績(jī)計(jì)算。則清洗后的數(shù)據(jù)表部分?jǐn)?shù)據(jù)如表2.1所示。

表2.1

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

（3）數(shù)據(jù)挖掘：數(shù)據(jù)挖掘過(guò)程主要是利用Apriori算法，采用廣度優(yōu)先的迭代搜素，設(shè)最小支持度為30%，產(chǎn)生頻繁子集50個(gè)，從產(chǎn)生的頻繁項(xiàng)目集中產(chǎn)生子集，根據(jù)關(guān)聯(lián)規(guī)則挖掘算法原理，設(shè)置最小置信度60%，得到的關(guān)聯(lián)規(guī)則15個(gè)，部分規(guī)則如表2-2所示。

表2.2

3.3 結(jié)果分析

第五條規(guī)則說(shuō)明數(shù)據(jù)庫(kù)原理成績(jī)?cè)?0-90，計(jì)算機(jī)網(wǎng)絡(luò)也在80-90的支持度為58.4%，置信度為76.5%，第六條規(guī)則說(shuō)明C++程序設(shè)計(jì)在80-90分，計(jì)算機(jī)網(wǎng)絡(luò)也在80-90的支持度為56.9%，置信度為83.4%這兩個(gè)規(guī)則可信度和置信度都較高，但實(shí)際有沒(méi)有關(guān)聯(lián)還需要做深入的討論。

上面第二條規(guī)則說(shuō)明《計(jì)算機(jī)基礎(chǔ)》成績(jī)?cè)?0-80分之間，《高等數(shù)學(xué)》在80-90分之間的支持度為55.8%，置信度為87.2，雖然支持度和置信度都達(dá)到了要求，但是根據(jù)老師多年的教學(xué)經(jīng)驗(yàn)，這兩者之間并沒(méi)有很強(qiáng)的關(guān)系，因此在實(shí)際排課中我們要實(shí)際經(jīng)驗(yàn)聯(lián)系數(shù)據(jù)做出安排。

3.4 模型改進(jìn)

在上面建模過(guò)程中，在數(shù)據(jù)轉(zhuǎn)換時(shí)，將成績(jī)離散化為1-5的值，這樣每一門課都會(huì)有5個(gè)不同的表示，例如A1、A2、A3、A4、A5，10門課就會(huì)有50個(gè)不同的符號(hào)來(lái)表示每一個(gè)項(xiàng)目。雖然之中劃分對(duì)于分析沒(méi)門課程之間的聯(lián)系會(huì)給出更加有利和詳細(xì)的證據(jù)。實(shí)際情況中，每一個(gè)專業(yè)大學(xué)四年所學(xué)課程通常都是在三四十門以上。如果仍談按照以上的方式進(jìn)行數(shù)據(jù)處理,掃描數(shù)據(jù)庫(kù)中上百條記錄，程序的運(yùn)行效率會(huì)很低。

綜上所述，為了兼顧程序的運(yùn)行效率和得到確實(shí)可信的結(jié)果，當(dāng)需要掃描大數(shù)據(jù)的數(shù)據(jù)庫(kù)時(shí)，在數(shù)據(jù)轉(zhuǎn)換時(shí)，不再將成績(jī)劃分成五個(gè)等級(jí)，而是將成績(jī)劃分為2個(gè)等級(jí)，如果成績(jī)大于該科的平均分，則該成績(jī)記為1，否則記為0

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

這樣就將excel中的數(shù)據(jù)讀入data中。

將數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)內(nèi)存中，當(dāng)運(yùn)行Apriori算法程序時(shí)，不需要每次都掃描數(shù)據(jù)庫(kù)，只需掃描一次數(shù)據(jù)庫(kù)文件，以后每次迭代中都只是掃描存儲(chǔ)到計(jì)算機(jī)內(nèi)存中的矩陣。加快了數(shù)據(jù)訪問(wèn)速度。模型改進(jìn)之后，需要訪問(wèn)的數(shù)據(jù)量減少了一半以上，數(shù)據(jù)的訪問(wèn)次數(shù)也減少了很多，因此程序的運(yùn)行效率會(huì)有顯著的提高。這是今后在做大數(shù)據(jù)挖掘時(shí)，加快程序運(yùn)行速度的一個(gè)解決辦法。

4.結(jié)語(yǔ)

對(duì)于某些事情，憑借經(jīng)驗(yàn)完全可以做出決策，如學(xué)校課程的安排，但是這些決策沒(méi)有堅(jiān)強(qiáng)的理論基礎(chǔ)做支撐，有時(shí)候是很難站住腳的。但是如果我們能運(yùn)用數(shù)據(jù)挖掘的有關(guān)知識(shí)，為這些經(jīng)驗(yàn)提供理論科學(xué)依據(jù)，就會(huì)讓這些經(jīng)驗(yàn)顯得更加可信。需要我們運(yùn)用正確的方法，分析數(shù)據(jù)，做出決策，而數(shù)據(jù)挖掘技術(shù)就是最正確的方法。

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

[2]史忠植.知識(shí)發(fā)現(xiàn)[M].北京:清華大學(xué)出版社,2002.

[3]張志霞,許童羽等.高等學(xué)校成績(jī)分析方法的研究[J].沈陽(yáng)農(nóng)業(yè)大學(xué)學(xué)報(bào),2008-06,10(3):322-324.

[4]楊洪偉,許童羽.Apriori算法在學(xué)生成績(jī)分析中的應(yīng)用研究[J].現(xiàn)代計(jì)算機(jī)(專業(yè)版),2010.

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

[6]常朝德,代永衛(wèi)等.關(guān)聯(lián)規(guī)則在公安情報(bào)信息系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(5):75-78.

[7]趙輝.數(shù)據(jù)挖掘技術(shù)在學(xué)生成績(jī)分析中的研究及應(yīng)用[D].大連:大連海事大學(xué),2007.

[8]陸楠.關(guān)聯(lián)規(guī)則的挖掘及其算法的研究[D].長(zhǎng)春:吉林大學(xué),2007.

[9]周根貴.數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘[M].浙江:浙江大學(xué)出版社,2004.