一種改進(jìn)的關(guān)聯(lián)規(guī)則算法在就業(yè)管理信息系統(tǒng)中的應(yīng)用研究

周 賢

(湖南第一師范學(xué)院招生就業(yè)處，湖南長(zhǎng)沙410002)

一種改進(jìn)的關(guān)聯(lián)規(guī)則算法在就業(yè)管理信息系統(tǒng)中的應(yīng)用研究

周 賢

(湖南第一師范學(xué)院招生就業(yè)處，湖南長(zhǎng)沙410002)

隨著高校畢業(yè)生就業(yè)制度的改革和高等教育規(guī)模的迅速擴(kuò)大，高校畢業(yè)生的數(shù)量迅速增加，高等教育的決策者很想知道高等教育學(xué)科專業(yè)結(jié)構(gòu)、辦學(xué)基本條件與學(xué)生就業(yè)之間的關(guān)系，以判斷高等教育是否適應(yīng)社會(huì)需求。以高校畢業(yè)生就業(yè)信息數(shù)據(jù)為研究對(duì)象，將一種改進(jìn)的關(guān)聯(lián)規(guī)則算法應(yīng)用于就業(yè)信息數(shù)據(jù)分析，希望從大量積累的歷史就業(yè)信息數(shù)據(jù)中挖掘出有意義的規(guī)則，以便以就業(yè)為導(dǎo)向，提高高等教育質(zhì)量，提高學(xué)生就業(yè)率。

關(guān)聯(lián)規(guī)則;就業(yè)管理;信息系統(tǒng)

隨著計(jì)算機(jī)技術(shù)的發(fā)展，我國不少單位的管理工作都向信息化方向轉(zhuǎn)變。比如就業(yè)管理方面的信息系統(tǒng)已經(jīng)在不少高校投入運(yùn)行，而且經(jīng)過若干年的應(yīng)用，系統(tǒng)積累了非常重要的就業(yè)管理方面的數(shù)據(jù)。但就目前所使用的就業(yè)管理信息系統(tǒng)而言，一般只是提供一些簡(jiǎn)單的功能，比如:信息錄入、信息查詢以及信息的統(tǒng)計(jì)等。隨著就業(yè)信息量的增加，如何從其中挖掘出有效的規(guī)則，并進(jìn)一步指導(dǎo)高校教學(xué)以及就業(yè)管理就成為一個(gè)值得關(guān)注的問題。也就是說，通過數(shù)據(jù)挖掘技術(shù)，從就業(yè)管理信息系統(tǒng)的數(shù)據(jù)中挖掘出知識(shí)，從而預(yù)測(cè)未來［1］。

尤其是最近幾年，我國高校規(guī)模不斷增大，畢業(yè)生就業(yè)制度也有了一定的變化，每年畢業(yè)生數(shù)量呈大幅度增長(zhǎng)的趨勢(shì)，高校教育也由原來的精英化教育逐漸轉(zhuǎn)變成大眾化教育。這時(shí)，一個(gè)關(guān)鍵問題就顯現(xiàn)出來了。那就是這么多的大學(xué)生涌入社會(huì)，如何保證這些學(xué)生都能就業(yè)就成為亟待解決的問題。我國政府、高校以及企事業(yè)單位都在努力緩解就業(yè)壓力。高校領(lǐng)導(dǎo)層也認(rèn)識(shí)到了就業(yè)率與教學(xué)專業(yè)結(jié)構(gòu)、辦學(xué)基本條件等之間的關(guān)系，但只能借助于挖掘技術(shù)，才能實(shí)現(xiàn)以就業(yè)為導(dǎo)向，提取合理性的規(guī)則，從而提升高校教育水平，促進(jìn)學(xué)生就業(yè)率的提高。作者提出了一種改進(jìn)的關(guān)聯(lián)規(guī)則看法:希望從就業(yè)信息數(shù)據(jù)中挖掘出有意義的規(guī)則。

一 關(guān)聯(lián)規(guī)則Apriori算法的基本思想

關(guān)聯(lián)規(guī)則挖掘在數(shù)據(jù)挖掘中是一個(gè)重要的課題，最近幾年已被業(yè)界所廣泛研究。而Apriori算法則是關(guān)聯(lián)規(guī)則中的一個(gè)經(jīng)典算法。該算法能夠有效生成候選測(cè)試規(guī)則。其中，算法可以在K－項(xiàng)目集的基礎(chǔ)上生成(K+1)－項(xiàng)目集。首先，算法生成頻繁1－項(xiàng)目集所對(duì)應(yīng)的集合，可以記為L(zhǎng)1。在L1集合的基礎(chǔ)上再生成頻繁2－項(xiàng)目集的集合，可以記為L(zhǎng)2，并再次在L2的基礎(chǔ)上生成L3，不斷按照這樣的規(guī)則進(jìn)行循環(huán)處理，直到最終生成頻繁K－項(xiàng)目集。需要注意的是，生成一個(gè)Lk都必須經(jīng)過一次數(shù)據(jù)庫的掃描處理［2］。

Apriori算法屬于層次化算法的范疇，實(shí)現(xiàn)過程也比較簡(jiǎn)單。但存在的關(guān)鍵問題是:Apriori算法每次生成項(xiàng)目候選集的時(shí)候都需要對(duì)數(shù)據(jù)庫進(jìn)行一次掃描操作，當(dāng)數(shù)據(jù)庫比較大，也就是對(duì)應(yīng)的候選集比較大時(shí)，Apriori算法會(huì)花費(fèi)大量時(shí)間在數(shù)據(jù)庫的掃描操作上，從而直接導(dǎo)致Apriori算法在時(shí)間上的開銷過大。另外，由于數(shù)據(jù)庫中的數(shù)據(jù)并不是不變的，隨著應(yīng)用的深入，數(shù)據(jù)庫中的數(shù)據(jù)也在不斷增加中，而Apriori算法在運(yùn)行時(shí)會(huì)涉及到頻繁項(xiàng)目集以及關(guān)聯(lián)規(guī)則的生成。這里為了挖掘結(jié)果的有效性，必須對(duì)這些增加的數(shù)據(jù)再次進(jìn)行Apriori算法挖掘，這也表示之前挖掘出來的頻繁項(xiàng)目集以及關(guān)聯(lián)規(guī)則是無效的，這樣將明顯不利用于關(guān)聯(lián)規(guī)則的高效挖掘［3］。同時(shí)，如果數(shù)據(jù)庫的規(guī)模大于主存的時(shí)候，該Apriori算法的不足之處越明顯，效率也會(huì)受到更大的影響。

二 關(guān)聯(lián)規(guī)則Apriori算法的優(yōu)化

從Apriori算法分析中，不難發(fā)現(xiàn)，Apriori算法生成一次頻繁集，都會(huì)執(zhí)行數(shù)據(jù)庫掃描操作來判斷候選頻繁項(xiàng)目集是不是屬于頻繁項(xiàng)目集。在實(shí)際的執(zhí)行過程中，有些項(xiàng)明顯不屬于頻繁項(xiàng)目集的，但Apriori算法仍然要去掃描數(shù)據(jù)庫，這顯然是影響了Apriori算法的效率，為避免這些不必要的掃描操作還需要進(jìn)一步進(jìn)行研究。本文提出關(guān)聯(lián)規(guī)則挖掘的改進(jìn)模式，在Apriori改進(jìn)算法中涉及到的關(guān)鍵術(shù)語定義如下:

(一)信息系統(tǒng)的定義

信息系統(tǒng)可以用S={U，I，F(xiàn)}加以表示，所有對(duì)象的非空有限集合用U={X1，X2，…，Xp}加以表示，屬性的非空有限集合用I={I1，I2，…，Im}加以表示，我們也可以稱之為屬性集。

(二)分辨矩陣的定義

信息系統(tǒng)用S={U，I，F(xiàn)}加以表示，定義映射φi:Vi→{0，1}如下:

(三)分辨向量的定義

若Dj稱為項(xiàng) Ij的分辨向量［4］。

三 Apriori優(yōu)化算法的偽碼描述

基于分辨矩陣的關(guān)聯(lián)規(guī)則Apriori算法的優(yōu)化思想描述如:

Stepl:錄入信息系統(tǒng)，同時(shí)設(shè)置最小支持度。

Step2:對(duì)數(shù)據(jù)庫進(jìn)行掃描操作，并產(chǎn)生對(duì)應(yīng)的分辨矩陣D。

Step3:由分辨矩陣生成頻繁1－項(xiàng)目集，同時(shí)將K設(shè)置成2。

Step4:根據(jù)Lk－1中的頻繁k－1項(xiàng)目集產(chǎn)生頻繁K－項(xiàng)目集，并將頻繁K－項(xiàng)目集命名為集合R。

Step5:根據(jù)集合R，產(chǎn)生對(duì)應(yīng)的項(xiàng)集下標(biāo)集W。

Step6:對(duì)W中每一個(gè)下標(biāo)Wi，計(jì)算下標(biāo)集L'(Wi)，若存在Wi∈W，使得L'(Wi)≠Φ，則將Wi從W中刪去，并加入L'中。

Step7:對(duì)剪枝后的W中的每一個(gè)下標(biāo)Wi，生成對(duì)應(yīng)的分辨向量DWi，計(jì)算支持度計(jì)數(shù)，如下所示:

若 support－count(Rwi)＜ min－sup×|D|，則將Wi從W中刪去，并加入到L'中。

Step8:若W≠Φ，則根據(jù)下標(biāo)集W中的每一個(gè)下標(biāo)，生成集合R所相應(yīng)的項(xiàng)集，并生成K－項(xiàng)目集，用Lk加以表示，令K=K+1轉(zhuǎn)至Step4，否則Step9。

Step9:輸出分辨矩陣中符合最小支持度的頻繁目集，用L=∪KLK加以表示。

四 關(guān)聯(lián)規(guī)則改進(jìn)算法在就業(yè)管理信息系統(tǒng)中的應(yīng)用

Apriori優(yōu)化算法的思想就是利用Lk－1中的k－1項(xiàng)集連接生成K－項(xiàng)集的集合R，最終生成分辨矩陣D。那么針對(duì)就業(yè)信息，根據(jù)Apriori優(yōu)化算法的思想，首先應(yīng)找出學(xué)生就業(yè)信息系統(tǒng)的頻繁一維謂項(xiàng)集，然后在頻繁一維謂項(xiàng)集的基礎(chǔ)上，發(fā)現(xiàn)所有的頻繁k維謂項(xiàng)集，從而產(chǎn)生學(xué)生就業(yè)信息系統(tǒng)分辨矩陣所對(duì)應(yīng)的關(guān)聯(lián)規(guī)則。由此可見關(guān)于多維頻繁謂詞集的生成是核心內(nèi)容。因此，應(yīng)用流程的核心就是如何由頻繁K－謂項(xiàng)集求頻繁K+1謂項(xiàng)集，我們可以借助于函數(shù)的遞歸調(diào)用來實(shí)現(xiàn)，應(yīng)用的實(shí)現(xiàn)過程如下:

算法開始執(zhí)行后，第一步先找到頻繁1－項(xiàng)目集，也就是頻繁一維謂詞集;第二步在頻繁1－項(xiàng)目集的基礎(chǔ)上，生成頻繁二維謂詞集，由此循環(huán)，生成最終的頻繁k維謂詞集。比如:針對(duì)就業(yè)管理信息中的“專業(yè)英語”字段，算法將其定義了一維頻繁謂詞，則生成的二維頻繁謂詞就可以是“專業(yè) －英語”、“生源地 －長(zhǎng)沙”。當(dāng)該二維頻繁謂詞的相關(guān)計(jì)數(shù)值滿足一開始設(shè)定的最小支持度，則可以生成三維頻繁謂詞:“專業(yè) － 英語”、“生源地 － 長(zhǎng)沙”、“綜合測(cè)評(píng) －高”。

但是，如果該二維頻繁謂詞的相關(guān)計(jì)算值并不滿足一開始設(shè)定的最小支持度，則凡是包括“專業(yè)－英語”、“生源地－長(zhǎng)沙”的相關(guān)模式是不再被掃描的。關(guān)聯(lián)規(guī)則挖掘算法就是會(huì)其他的二維頻繁項(xiàng)集進(jìn)行計(jì)數(shù)，比如:“專業(yè) －英語”、“生源地 －湘潭”，然后重復(fù)上面的比較操作。根據(jù)上述的步驟進(jìn)行不斷的頻繁謂詞添加后綴并判斷，最終生成所有的頻繁k維謂項(xiàng)集。

Step1:與就業(yè)管理信息系統(tǒng)的數(shù)據(jù)進(jìn)行連接操作，查詢定位相關(guān)信息，涉及到關(guān)鍵表的一些屬性維以及記錄數(shù)等等信息。

Step2:K=m=n=1，求一維頻繁謂詞項(xiàng)集，N=總屬性維數(shù)。

Step3:針對(duì)于就業(yè)管理信息系統(tǒng)中的一維頻繁謂詞集，可以選擇其中的第m個(gè)屬性作為起始屬性，并根據(jù)該屬性的n個(gè)成員作為頻繁維謂詞集，如果k的取值是1，那么當(dāng)前的頻繁維謂詞集就是1維的。

Step4:將頻繁維謂詞項(xiàng)與數(shù)據(jù)庫表第i+1個(gè)屬性維中的第j個(gè)成員進(jìn)行連接操作，產(chǎn)生對(duì)應(yīng)的K+1謂詞項(xiàng)，同時(shí)對(duì)數(shù)據(jù)庫進(jìn)行掃描并生成該謂詞項(xiàng)的計(jì)數(shù)。

Step5:判斷計(jì)數(shù)與一開始設(shè)定的最小支持度之間的大小關(guān)系。如果大于，則將K+1謂詞項(xiàng)作為當(dāng)前頻繁維謂詞項(xiàng)，i及k進(jìn)行步長(zhǎng)為1的遞增;否則，計(jì)算j是否大于第i+1個(gè)屬性維中的成員總數(shù)，如果是，將i進(jìn)行步長(zhǎng)為1的遞增，j=1。

Step6:計(jì)算n是否大于第m個(gè)屬性維中的成員總數(shù)。如果是，則m++，n=1;反之，轉(zhuǎn)至Step3;

Step7:計(jì)算m是否大于N，如果是，則終止算法流程。反之，轉(zhuǎn)至Step3。

五 關(guān)聯(lián)規(guī)則改進(jìn)算法在就業(yè)管理信息系統(tǒng)中的應(yīng)用實(shí)例

某高校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)每學(xué)期都要統(tǒng)計(jì)學(xué)生的就業(yè)分配情況，現(xiàn)隨機(jī)抽取400名學(xué)生的畢業(yè)分配情況，將學(xué)號(hào)、數(shù)據(jù)結(jié)構(gòu)課程成績(jī)、大學(xué)英語成績(jī)、文化課測(cè)評(píng)成績(jī)、綜合測(cè)評(píng)成績(jī)、行業(yè)、收入等7項(xiàng)數(shù)據(jù)輸入數(shù)據(jù)庫(如表1所示)。我們將找出數(shù)據(jù)結(jié)構(gòu)課程成績(jī)和大學(xué)英語成績(jī)對(duì)就業(yè)行業(yè)的影響，文化測(cè)評(píng)成績(jī)和綜合測(cè)評(píng)成績(jī)哪個(gè)對(duì)收入的影響更大。

表1 就業(yè)評(píng)價(jià)信息表

在上表中，數(shù)據(jù)結(jié)構(gòu)成績(jī)、大學(xué)英語成績(jī)、文化課測(cè)評(píng)成績(jī)、綜合測(cè)評(píng)成績(jī)及收入都是樹立屬性(非離散屬性)，這里，我們將其離散化。首先，對(duì)數(shù)據(jù)結(jié)構(gòu)成績(jī)、大學(xué)英語成績(jī)、文化課測(cè)評(píng)成績(jī)、綜合測(cè)評(píng)成績(jī)采用統(tǒng)一的量化標(biāo)準(zhǔn)，分為兩個(gè)等級(jí)，成績(jī)高于85分的為良好，低于85分的為一般。將收入也量化為兩個(gè)值，高于1 500的為高收入，低于1 500的為低收入。

將表中的相關(guān)記錄進(jìn)行編碼，將就業(yè)評(píng)價(jià)信息表中的記錄以 i1，i2，…，i8進(jìn)行編碼。

輸入:就業(yè)評(píng)價(jià)信息表;輸出:分辨矩陣表。

(1)挖掘頻繁1－項(xiàng)集L1

輸入:分辨矩陣表和最小支持度min－sup=0．25

輸出:L1={i1，i2，…，i8}

(2)挖掘頻繁項(xiàng)集L

輸入:L14L

輸出:L=k∪=1k，其中 L1同上

L2={i14，i16，i17，i34，i45，i46，i47，i48，i56，i67}，

L3={i146，i147，i167，i456，i467}，

［1］閆 禹．?dāng)?shù)據(jù)挖掘技術(shù)在高校學(xué)生就業(yè)指導(dǎo)決策中的運(yùn)用［J］．沈陽工業(yè)大學(xué)學(xué)報(bào)，2007，29(3):344－346．

［2］宋 波，李妙妍，趙 晶．利用泛型DAO模式改進(jìn)輕量級(jí)J2EE架構(gòu)［J］．計(jì)算機(jī)工程與設(shè)計(jì)，2009，30(24):5663－5666．

［3］劉美玲，李 熹，李永勝．?dāng)?shù)據(jù)挖掘技術(shù)在高校教學(xué)與管理中的應(yīng)用［J］．計(jì)算機(jī)工程與設(shè)計(jì)，2010，31(5):1130－1133．

［4］李燚琳，張 璞．?dāng)?shù)據(jù)挖掘技術(shù)在教務(wù)信息挖掘系統(tǒng)中的應(yīng)用［J］．制造業(yè)自動(dòng)化，2010，32(4):200－203．

L4={i1467}。

(3)挖掘關(guān)聯(lián)規(guī)則集R

輸入:L，最小置信度min－conf=0．75

輸出:R1:i1i46(sup=0．3061，conf=0．789 5)

R1:i1i46(sup=0．2959，conf=0．878 8)

R2:i7i14(sup=0．2959，conf=0．763 2)

R3:i1i47(sup=0．2653，conf=0．787 9)

R4:i7i16(sup=0．2959，conf=0．878 8)

R5:i7i46(sup=0．2653，conf=0．896 6)

R6:i67i14(sup=0．2653，conf=0．812 5)

R7:i47i16(sup=0．2653，conf=0．896 6)

R8:i17i46(sup=0．2653，conf=0．812 5)

搜索原始數(shù)據(jù)庫，得到滿足最小支持度和最小置信度的關(guān)聯(lián)規(guī)則:

(1)數(shù)據(jù)結(jié)構(gòu)(良好)。行業(yè)(IT):數(shù)據(jù)結(jié)構(gòu)成績(jī)良好的學(xué)生從事IT行業(yè)。該規(guī)則的支持度為28%，置信度為72%。

(2)綜合測(cè)評(píng)(良好)。收入(高收入):綜合測(cè)評(píng)成績(jī)良好的學(xué)生的工資收入比較高。該規(guī)則的支持度為24%，置信度為81%。

(3)文化課測(cè)評(píng)(良好)。收入(高收入):文化課測(cè)評(píng)成績(jī)良好的學(xué)生的工資收入比較高。該規(guī)則的支持度為25%，置信度為74%。

規(guī)則(l)說明數(shù)據(jù)結(jié)構(gòu)成績(jī)好的學(xué)生的實(shí)際編程能力很強(qiáng)，很適合從事IT行業(yè)，大部分學(xué)生的就業(yè)行業(yè)都是IT業(yè)。規(guī)則(2)和規(guī)則(3)說明測(cè)評(píng)成績(jī)高的學(xué)生的工資收入比較高。規(guī)則(2)的置信度高于規(guī)則(3)，且規(guī)則(3)的支持度高于規(guī)則(2)的支持度，這說明綜合測(cè)評(píng)高的學(xué)生獲得高工資的可能性更大，也就是在找工作的過程中，用人單位更注重綜合能力。因此，在培養(yǎng)學(xué)生的過程中，多注重綜合能力的培養(yǎng)。

G421

A

1674－5884(2011)10－0032－03

2011－07－18

周 賢(1981－)，男，湖南湘潭人，碩士生，政工師，主要從事高教管理研究。

(責(zé)任編校 楊鳳娥)