Apriori算法在畢業(yè)生信息應(yīng)用中的改進(jìn)分析

摘要:通過學(xué)習(xí)和研究關(guān)聯(lián)規(guī)則在商場(chǎng)購(gòu)物問題上的應(yīng)用，分析學(xué)校畢業(yè)生信息特點(diǎn)，相對(duì)商場(chǎng)購(gòu)物信息，畢業(yè)生信息性質(zhì)單一。根據(jù)其特點(diǎn)進(jìn)行量化得出大量重復(fù)數(shù)據(jù)，結(jié)合算法對(duì)量化后的數(shù)據(jù)采用關(guān)聯(lián)規(guī)則分析數(shù)據(jù)。Apriori算法會(huì)對(duì)重復(fù)數(shù)據(jù)多次重復(fù)掃描，因此將Apriori算法應(yīng)用于學(xué)生就業(yè)問題時(shí)要對(duì)其進(jìn)行改進(jìn)，以利于決策者的分析與應(yīng)用，試圖增加一個(gè)屬性列count來記錄相同數(shù)據(jù)數(shù)目，以改進(jìn)Apriori在畢業(yè)生信息分析中的適用性。

關(guān)鍵詞:關(guān)聯(lián)規(guī)則;Apriori算法;畢業(yè)生信息

中圖分類號(hào):TP311 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1009-3044(2009)36-10513-02

Apriori Algorithm in Graduate Information Applications of the Improved Analysis

LI Li-xian

(Information Science and Technology Institute of Jiujiang University， Jiujiang 332005， China)

Abstract: Through study and research association rules in the shopping mall on the issue of application， Analysis of information characteristics of school leavers， Comparative shopping information， Graduates of a single nature of the information. Quantified according to their characteristics come to a large number of duplicate data， combined with algorithms to quantify the data after the analysis of data using association rules. Apriori algorithm is repeated duplication of data would be scanned and will therefore Apriori algorithm is applied to the employment problem of the students you want to make improvements in order to facilitate the analysis and application of decision-makers， Attempt to increase an attribute to record the same data column count the number of graduates in order to improve Apriori in the applicability of information analysis.

Key words: association rules; apriori arithmetic; graduate information

Agrawal等在1993年設(shè)計(jì)了一個(gè)基本算法，提出了挖掘關(guān)聯(lián)規(guī)則的一個(gè)重要方法，這是一個(gè)基于兩階段頻集思想的方法，關(guān)聯(lián)規(guī)則挖掘算法可以分解為兩個(gè)子問題，第一步是尋找頻集，第二步是由頻集產(chǎn)生規(guī)則[3-4]。

Apriori算法如下:

輸入:事務(wù)數(shù)據(jù)庫D，最小支持度閾值min_sup。

輸出:D中的頻繁項(xiàng)集E。

方法:

1)E1=find_frequent_1-itemsets(D):

2)for(i=2;Ei-1≠?準(zhǔn);i++){

3)Ci=Apriori_gneL(Ei-1，min_sup); //新的候選項(xiàng)集

4)for each transaction t∈D{

5)Ct=subset(Ci，t); //變量t中所包含的候選集

6)foreachcandidates C∈Ct

7)C.count=C.count+1;

8)}

9)Ei ={C∈Ci|C.count=min_sup}

10) }

11) return E=∪iEi;

procedure apriori_gen(Ei-1;frequent(i-1)-itemsets;min_sup:min support threshold)

1)for each itemset E1∈Ei-1

2)for each itemsetE2∈Ei-1

3)if(E1[1]=E2[1] ∧E1[2]=E2[2] ∧…∧E1[i-2]=E2[i-2] ∧E1[i-1]

4)C=E1?茌E2//join step;generate candidates

5)if has_infrequent_subset(C，Ei-1) then

6)delete C; //prune step:remove unfruitful candidate

7)else add C to Ci;

8)}

9)return Ci;

Procedure has_infrequent_subset(C:candidatek-itemset;Ei-1:frequent(i-1)-itemset)

1)for each (i-1)-subset S of C

2)if S?埸Ei-1 then

3)return true;

4)return 1;

1 畢業(yè)生信息特點(diǎn)

高等學(xué)校中的畢業(yè)生信息數(shù)據(jù)和商場(chǎng)購(gòu)物籃問題數(shù)據(jù)有很大的不同。商場(chǎng)購(gòu)物籃問題數(shù)據(jù)存放在事務(wù)數(shù)據(jù)庫中，每一購(gòu)買行為在事務(wù)數(shù)據(jù)庫中對(duì)應(yīng)一項(xiàng)事務(wù)，不同事務(wù)之間它們的項(xiàng)完全相同的可能性很小，這種事務(wù)數(shù)據(jù)庫中的數(shù)據(jù)挖掘只能逐個(gè)記錄地掃描數(shù)據(jù)庫。畢業(yè)生信息一般以關(guān)系數(shù)據(jù)庫的形式存在，對(duì)反映畢業(yè)生生情況、畢業(yè)生就業(yè)的數(shù)據(jù)庫，每個(gè)學(xué)生一條記錄。就我們所使用的畢業(yè)生據(jù)庫中的畢業(yè)登記表來說，記錄有相同的屬性，而對(duì)其字段進(jìn)行了量化和類聚處理。具體內(nèi)容說明如下:綜合測(cè)評(píng)E1是不分專業(yè)，只按畢業(yè)時(shí)間，利用均值來進(jìn)行量化，在平均之上(含平均值)的取為1，在平均值之下的取為0;專業(yè)E2是根據(jù)屬于的熱門專業(yè)的取為1，屬于非熱門專業(yè)的取為0;是否就業(yè)E3是根據(jù)畢業(yè)生是否有就業(yè)單位，有就業(yè)單位取值為1，沒有就業(yè)單位取值為0;外語等級(jí)E4是指英語是否過了國(guó)家英語四級(jí)，過了四級(jí)取值為1，沒有過四級(jí)取值為0;戶口所在E5是指學(xué)生戶籍是城市的取值為1，戶籍是農(nóng)村取值為0。如兩個(gè)數(shù)據(jù)庫記錄如表1。對(duì)此數(shù)據(jù)進(jìn)行量化后，兩個(gè)畢業(yè)生信息記錄可表示如表2。即經(jīng)量化處理后，兩個(gè)畢業(yè)生會(huì)有相同的記錄產(chǎn)生。

表1 畢業(yè)生信息實(shí)例表表2 畢業(yè)生信息實(shí)例量化表

2 Apriori算法在畢業(yè)生信息中的應(yīng)用

Apriori算法使用一種稱作逐層搜索的迭代方法，并使用了“頻繁項(xiàng)集的所有非空子集必須也是頻繁”的論斷來提高逐層搜索的性質(zhì)。通過前面的試驗(yàn)我們比較清楚的分析出，由于畢業(yè)生信息與商場(chǎng)的購(gòu)物籃問題的信息存在著極大的不同性，因此當(dāng)Apriori算法應(yīng)用于畢業(yè)生信息中時(shí)就存在著一定的問題。因?yàn)槠湫畔⑴c商場(chǎng)的購(gòu)物籃問題的信息相比，性質(zhì)比較單一，因?yàn)楫厴I(yè)生信息具有很多相同的共性，尤其是當(dāng)多個(gè)字段量化后，相同量化后學(xué)生信息數(shù)據(jù)更為增多，這樣就使得經(jīng)過Apriori算法進(jìn)行挖掘分析的學(xué)生數(shù)據(jù)不利于決策者進(jìn)行觀察，而且由于畢業(yè)生信息的重復(fù)數(shù)據(jù)使得Apriori算法也仍然要對(duì)重復(fù)數(shù)據(jù)進(jìn)行多次重復(fù)的掃描。這樣的雙重問題使得在將Apriori算法應(yīng)用于畢業(yè)生就業(yè)問題時(shí)，要對(duì)其進(jìn)行改進(jìn)，以利于決策者的分析與應(yīng)用。

3 應(yīng)用于畢業(yè)生信息的Apriori算法的改進(jìn)

算法的改進(jìn)主要是由于畢業(yè)生信息中的相關(guān)記錄中存在相關(guān)記錄多，量化后會(huì)有很多重復(fù)記錄的特點(diǎn)，同時(shí)采用劃分的聚類方法，來將它作為本文Apriori算法應(yīng)用中的畢業(yè)生信息預(yù)處理步驟。具體的可以對(duì)挖掘算法分兩個(gè)步驟執(zhí)行[5]。

3.1 對(duì)量化后的畢業(yè)生信息進(jìn)行聚類操作

在重復(fù)的記錄中保留第一條記錄，刪除其它相同記錄，(即利用聚類的方法)大大壓縮被挖掘數(shù)據(jù)庫的信息量。在本次改進(jìn)算法中，聚類分析作為Apriori算法的一個(gè)預(yù)處理步驟而出現(xiàn)。也就是在原有Apriori算法中加一屬性count來記錄相同記錄的數(shù)量，如上例兩名畢業(yè)生信息的兩條記錄，聚類后可表示如表3。

表3 畢業(yè)生信息聚類表

3.2 用Apriori算法

但相對(duì)經(jīng)典的Apriori算法有一點(diǎn)改變。在支持度計(jì)數(shù)時(shí)，不再是一條對(duì)應(yīng)記錄加1，而是加上對(duì)應(yīng)記錄的count值，在Apriori算法上的c.count=c.count+1修改為c.count=c.count+count，這樣就使得最終挖掘結(jié)果分析的畢業(yè)生信息數(shù)據(jù)沒有重復(fù)的記錄，而且其支持度與置信度就可以表現(xiàn)出來。重復(fù)數(shù)據(jù)的消除在最終提供給就業(yè)指導(dǎo)中心的表單中也不存在著相同信息，使得就業(yè)指導(dǎo)中心對(duì)于結(jié)果一目了然，而且更便于對(duì)結(jié)果信息的理解。通過算法的改進(jìn)，不僅增強(qiáng)了可讀性，而且更加提高了程序執(zhí)行的效率。

4 改進(jìn)后算法效果

在產(chǎn)生候選頻繁項(xiàng)集及頻繁項(xiàng)集時(shí)，通過檢測(cè)n項(xiàng)集的n-1項(xiàng)集是否為頻繁項(xiàng)集的方法來過濾非頻繁項(xiàng)集，但是由于畢業(yè)生信息的特點(diǎn)，如果按照正常的方法來進(jìn)行，花銷在候選頻繁項(xiàng)集上的時(shí)間相對(duì)較大。而且所獲得的重復(fù)的頻繁項(xiàng)集又很多，不利于對(duì)畢業(yè)生信息進(jìn)行挖掘性分析。因此，算法在畢業(yè)生信息方面利用聚集的方法在生成候選頻繁項(xiàng)集時(shí)首先進(jìn)行了數(shù)據(jù)預(yù)處理，將量化后的相同記錄進(jìn)行了計(jì)數(shù)上的改進(jìn)和處理，使得算法在數(shù)據(jù)的可讀性上有所提高，同時(shí)更能夠提高算法的時(shí)間效率。

算法運(yùn)行在CPU為 Pentium Dual Core 2.5GHz的PC計(jì)算機(jī)上，在數(shù)據(jù)庫中隨機(jī)提取的1000條畢業(yè)生信息記錄(事務(wù))，每條記錄由7個(gè)屬性(維)的項(xiàng)集構(gòu)成，新舊算法在產(chǎn)生頻繁項(xiàng)集的過程中所遇到的各項(xiàng)參數(shù)如表4所示。

表4 驗(yàn)證表

從運(yùn)行的結(jié)果可以看出改進(jìn)后的算法得出的關(guān)聯(lián)規(guī)則數(shù)目比改進(jìn)前的算法明顯減少，而實(shí)際改進(jìn)前算法所多出的關(guān)聯(lián)規(guī)則恰好也是重復(fù)顯示的關(guān)聯(lián)規(guī)則。這樣算法改進(jìn)后，去除了重復(fù)的關(guān)聯(lián)規(guī)則，使得所得數(shù)據(jù)結(jié)果的可讀性增強(qiáng)。同時(shí)可以看出由于相同記錄的去除，使得改進(jìn)后的算法在運(yùn)行時(shí)間效率上有了更加明顯的提高。程序運(yùn)行的時(shí)間對(duì)于算法改進(jìn)前后有了更加明顯的變化。

5 小結(jié)

分析了Apriori算法，并結(jié)合了畢業(yè)生信息進(jìn)行數(shù)據(jù)量化分析，根據(jù)畢業(yè)生信息特點(diǎn)對(duì)Apriori算法在畢業(yè)生信息和就業(yè)信息數(shù)據(jù)挖掘提出改進(jìn)方案，經(jīng)過數(shù)據(jù)檢驗(yàn)更適用于畢業(yè)生信息。改進(jìn)Apriori算法更有效的揭示畢業(yè)生信息屬性和就業(yè)行為之間數(shù)據(jù)的關(guān)聯(lián)規(guī)則。

參考文獻(xiàn):

[1] C.C.Aggarwal，and P.S.Yu.mining large itemsets for association rules.Bulletion of IEEE computer Society technical Committee on Data Engineering，1998.23-31.

[2] 楊霞玲，聶永紅. 聚類分析在畢業(yè)生就業(yè)預(yù)測(cè)中的應(yīng)用[J]. 廣西工學(xué)院學(xué)報(bào)，2005，16(4):82-84.

[3] 馮潔，陶宏才. 基于關(guān)聯(lián)規(guī)則挖掘領(lǐng)域的Apriori算法的優(yōu)化研究[J]. 微計(jì)算機(jī)信息， 2007，23(6-3):164-166.

[4] 李琦.在線挖掘關(guān)聯(lián)規(guī)則算法的改進(jìn)[J]. 華東理工大學(xué)學(xué)報(bào)，2000，5:67-71.

[5] 毛國(guó)君，劉椿年.基于項(xiàng)目序列集操作的關(guān)聯(lián)規(guī)則挖掘算法[J].計(jì)算機(jī)學(xué)報(bào)，2000，4:417~422.

[6] 吳斌，肖剛，陸佳煒. 基于關(guān)聯(lián)規(guī)則挖掘領(lǐng)域的Apriori算法的優(yōu)化研究[J].計(jì)算機(jī)工程與科學(xué)，2009，6(31):116-118.