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

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

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

中圖分類號:TP311 文獻標(biāo)識碼:A 文章編號: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è)計了一個基本算法，提出了挖掘關(guān)聯(lián)規(guī)則的一個重要方法，這是一個基于兩階段頻集思想的方法，關(guān)聯(lián)規(guī)則挖掘算法可以分解為兩個子問題，第一步是尋找頻集，第二步是由頻集產(chǎn)生規(guī)則[3-4]。

Apriori算法如下:

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

輸出:D中的頻繁項集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); //新的候選項集

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è)生信息特點

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

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

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

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

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

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

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

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

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

3.2 用Apriori算法

但相對經(jīng)典的Apriori算法有一點改變。在支持度計數(shù)時，不再是一條對應(yīng)記錄加1，而是加上對應(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)中心對于結(jié)果一目了然，而且更便于對結(jié)果信息的理解。通過算法的改進，不僅增強了可讀性，而且更加提高了程序執(zhí)行的效率。

4 改進后算法效果

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

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

表4 驗證表

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

5 小結(jié)

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

參考文獻:

[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ù)測中的應(yīng)用[J]. 廣西工學(xué)院學(xué)報，2005，16(4):82-84.

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

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

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

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