將關(guān)聯(lián)規(guī)則挖掘算法應(yīng)用于警校學(xué)員隊信息管理

●湯鈺涵

(公安海警高等專科學(xué)校,浙江寧波 315801)

一、引言

隨著 Internet的迅猛發(fā)展,當(dāng)今社會已進(jìn)入網(wǎng)絡(luò)時代,計算機信息技術(shù)廣泛深入到人類社會的各個領(lǐng)域并發(fā)揮著越來越重要的作用,各種信息管理系統(tǒng)應(yīng)運而生。在大背景的帶動下,現(xiàn)在部隊信息化建設(shè)也開展得如火如荼,辦公自動化、部隊信息化日趨完善。公安海警高等專科學(xué)校作為培養(yǎng)公安現(xiàn)役邊防學(xué)員的高等學(xué)府,更要與時俱進(jìn),加強信息化建設(shè)。為解決部隊院校學(xué)員隊隊務(wù)管理信息化建設(shè)問題,針對公安海警高等專科學(xué)校學(xué)員隊軍事化管理的特點,擬將關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘技術(shù)應(yīng)用于學(xué)員隊信息管理中,把管理人員從繁瑣的數(shù)據(jù)計算處理中解脫出來,對促進(jìn)學(xué)員隊管理工作的科學(xué)化、正規(guī)化具有十分重大的意義。

二、關(guān)聯(lián)規(guī)則挖掘、基本思想

數(shù)據(jù)庫中知識發(fā)現(xiàn)(KDD)是從目標(biāo)數(shù)據(jù)集合中提取出有效的、可信的、潛在有用的以及最終可理解的模式的非平凡過程。在此描述中：數(shù)據(jù)是一系列事實的集合(例如數(shù)據(jù)庫中的實例),模式是使用某種語言對數(shù)據(jù)集合一個子集的表述,過程是在 KDD的步驟(如數(shù)據(jù)的預(yù)處理、模式搜索、知識表示及知識評價等),非平凡是指它已經(jīng)超越了一般封閉形式的數(shù)量計算,而將包括對結(jié)構(gòu)、模式和參數(shù)的搜索。對于數(shù)據(jù)挖掘,比較公認(rèn)的數(shù)據(jù)挖掘定義是 W.J.Frawlev.Gpiatetsky-shapiro等人提出的：數(shù)據(jù)挖掘就是從大型數(shù)據(jù)庫的數(shù)據(jù)中提取出人們感興趣的知識。這些知識是隱含的、事先未知的潛在有用信息,提取的知識表示為概(Coneepts)、規(guī)則(Rules)、規(guī)律(Regularities)、模式(Patterns)等形式。而更廣義的說法是：數(shù)據(jù)挖掘意味著在一些事實或觀察數(shù)據(jù)的集合中尋找模式的決策支持過程。這樣,數(shù)據(jù)挖掘的對象不僅可以是數(shù)據(jù)庫,也可以是文件系統(tǒng),或其他任何組織在一起的數(shù)據(jù)集合,例如 WWW信息資源。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的一個重要研究方向,也是數(shù)據(jù)挖掘中最成熟、最活躍的研究領(lǐng)域。它表示的是數(shù)據(jù)庫中一組對象之間某種關(guān)聯(lián)關(guān)系的規(guī)則(例如“同時發(fā)生”或“從一個對象可以推出另一個”),形式如 AB?CD(95%),用例子表示就是“購買了項目 A和 B的顧客中有 95%的人又買了 C和D”。挖掘的一般對象是事務(wù)數(shù)據(jù)庫。這種數(shù)據(jù)庫的一個主要應(yīng)用是零售業(yè),條碼技術(shù)的發(fā)展使得數(shù)據(jù)的收集變得更容易、更完整,從而存儲了大量的交易資料。關(guān)聯(lián)規(guī)則就是辨別這些交易項目之間是否存在某種關(guān)聯(lián)關(guān)系。利用這些信息可以進(jìn)行商品銷售目錄設(shè)計、商場布置、生產(chǎn)安排、針對性的市場營銷等。

關(guān)聯(lián)規(guī)則的基本思想：一是找到所有支持度大于最小支持度的頻繁項集,即頻集。二是使用第一步找到的頻集產(chǎn)生期望的規(guī)則。其核心方法是基于頻集理論的遞推方法。

三、警校學(xué)員隊信息管理現(xiàn)狀

目前,隨著學(xué)校的不斷建設(shè)和發(fā)展,越來越多的學(xué)員進(jìn)入學(xué)校學(xué)習(xí)和深造,學(xué)校編制不斷擴大,學(xué)員隊日常管理信息不斷積累。而學(xué)員隊各項信息記錄不夠詳細(xì)和具體,記錄格式不規(guī)范或過于簡單,而且紙質(zhì)資料容易損壞或丟失,查詢和上報信息時存在著諸多不便。因此,加強學(xué)員隊隊務(wù)信息管理,加速信息化進(jìn)程、提高學(xué)員隊隊務(wù)信息管理水平變得越來越重要。一般的信息管理系統(tǒng),其基本特征是“聯(lián)機事務(wù)處理”,一般著眼于后臺管理,缺少直接面對用戶的系統(tǒng)功能,并且不適用軍事院校這種比較特殊的單位。

四、關(guān)聯(lián)規(guī)則的經(jīng)典算法

Agrawal等在 1993年設(shè)計了一個基本算法——Apriori算法,關(guān)聯(lián)規(guī)則的一個重要方法,這是一個基于兩階段挖掘思想的方法,挖掘算法的設(shè)計分解為兩個子問題：

1.找到所有支持度大于等于最小支持度的項集(Itemset),這些項集稱為頻繁項目集 (FrequentItemset)。

2.使用第一步找到的頻集產(chǎn)生期望的規(guī)則。

在這里,第二步相對簡單一點。如給定了一個頻集 Y=I1,I2,…,Ik,(K≥2),Ij∈I產(chǎn)生只包含集合{I1,I2,…,Im}中的項的所有規(guī)則(最多 K條),其中每一條規(guī)則的右部只有一項,(即形如[Y-Ii]?Ii,?1≤i≤k),這里采用的是中規(guī)則的定義。一旦這些規(guī)則被生成,那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來。

為了生成所有頻集,使用了遞推的方法。其核心思想如下：

L1={Large l-Itemsets}：

For(K=2;Lk-1≠Φ;K++)Do

Begin

Ck=Apriori-Gen(Lk-1);//新的候選集

For All Transaetions T∈D Do

Begin

C1=Subset(Ck,T);//事務(wù) T中包含的候選集

For All Candidates C∈CtDo

C.Count++;

End

Lk={C∈ Ck(C.Count≥Minsup)}

End

End

Answer=∪Lk

首先產(chǎn)生頻繁 1-項集 L1,然后是頻繁 2-項集L2,直到有某個 R值使得 Lr為空,這時算法停止。這里在第 K次循環(huán)中,過程先產(chǎn)生候選 K-項集的集合 Ck,Ck中的每一個項集是對兩個只有一個項不同的屬于 Lk-1的頻集做一個(K-2)連接來產(chǎn)生的。Ck中的項集是用來產(chǎn)生頻集的候選集,最后的頻集Lk必須是 Ck的一個子集。Ck中的每個元素需在交易數(shù)據(jù)庫中進(jìn)行驗證來決定其是否加入 Lk,這里的驗證過程是算法性能的一個瓶頸。這個方法要求多次掃描很大的交易數(shù)據(jù)庫,即如果頻集最多包含 10個項,那么就需要掃描交易數(shù)據(jù)庫 10遍,這需要很大的 I/O負(fù)載。

APriori_Gen()函數(shù)的參數(shù)為 Lk-1,結(jié)果返回含有 K個項目的候選項目集 Ck,事實上它由兩步構(gòu)成：Join連接步和 Prune修剪步。Jnin步通過對 Lk-1自連接操作生成 Ck*,然后對任意的 C∈Ck

*,刪除Ck

*中所有那些(K-1)子集不在 Lk-1的項目集,得到候選集合 Ck。具體算法描述如下：

APriori_Gen的 Join算法步驟：

Ck=Φ

For All Itemsets X∈ Lk-1,And Y∈Lk-1Do

If X1=Y1∧ …∧ Xk-2=Yk-2∧ Xk-1＜Yk-1Then

Begin

C=X1X2…Xk-1Yk-1;

End;

Apriori_Gen的 prune算法步驟：For All Itemsets C∈Ck

For All(K-1)-Subsets SOf CDo

If(S?Lk-1)Then

Delete C From Ck;

End

End;

在 Join步中,將 Lk-1自連接生成 Ck*,若上面的算法描述中沒有 If條件,那么將出現(xiàn)很多重復(fù)項。因為約定項目集中的項目是按照字母順序排列的,所以,通過使用 If條件,可以避免產(chǎn)生重復(fù)的項。另外 Prune步驟是用來刪除 Ck中的非頻繁項目集的。

舉例說明如下：L3={(A,B,C),(A,B,D),(A,C,D),(A,C,E),(B,C,D)},通過 Join操作后得到：C4={(A,B,C,D),(A,C,D,E)},修剪后得到C4=(A,B,C,D),因為{C,D,E}? L3.

APriori算法首先掃描數(shù)據(jù)庫并計算其中的每一個項目 I的支持度,產(chǎn)生大 1項目集 L1,然后再掃描數(shù)據(jù)庫計算大 2-項目集 L2,…,直到有個 R值使得Lr為空,這時算法停止。在第 K次循環(huán)中,由兩步組成：

(1)從大(K-1)項目集 Lk-1中產(chǎn)生出候選集合Ck;

(2)掃描數(shù)據(jù)庫計算 Ck中每一個候選集的支持度;

候選集的產(chǎn)生過程是從大(K-1)項目集中計算出潛在的大 K-項目集,一個新的 K候選集由兩個大 K-1項目集構(gòu)成,這兩個大項集的前(K-2)個項目是相同的(假設(shè)項目都是按照字典序排列的)。產(chǎn)生候選集 Ck后,要返回去檢查它的(K-1)子集是否頻繁,子集不頻繁的候選集就被修剪掉。此步之后,就需要對他們計數(shù)來確定它們是否頻繁,這一步很關(guān)鍵,它影響著算法的效率,由于候選集合可能會很大,APriori采用 Hash-Tree來存儲這些候選集。Apriori算法中 Subset函數(shù)就是用 Hash-Table結(jié)構(gòu)來發(fā)現(xiàn)交易中包含的候選項目集的,對于每一項交易,若候選項目集在其中出現(xiàn)了,就相應(yīng)的給此項集的 Counts加 1。檢查完數(shù)據(jù)庫后,濾掉那些小的候選集,把剩下大的加入到 Lk中。

舉個例子,考慮表 1中的交易數(shù)據(jù)庫,假設(shè)支持度為 40%,也就是說一個項目集至少由兩個交易支持它,第一遍掃描之后,L1=(A,B,C,D),APriori Gen函數(shù)計算出 C2={AB,AC,AD,BC,BD,CD},掃描數(shù)據(jù)庫計算支持度后,得出 L2=(AB,AC,AD,BD)。用 L2產(chǎn)生 C3=(ABC,ABD,ACD),但 ABC的子集 BC不在 L2中,所以修剪掉它,同樣也可以修剪掉 ACD。掃描數(shù)據(jù)庫產(chǎn)生 L3{ABC}。C4為空,算法停止。

表1 交易數(shù)據(jù)庫

五、結(jié)束語

將關(guān)聯(lián)規(guī)則應(yīng)用于警校學(xué)員隊信息管理是筆者的一個設(shè)想,目的就是提高學(xué)員隊日常管理工作的效率,節(jié)省更多的時間和人力,一個實用的管理系統(tǒng)將為決策提供支持,使數(shù)據(jù)獲取過程變得更加方便,更有根據(jù),數(shù)據(jù)分析更加全面,但是數(shù)據(jù)挖掘只是一個強大的工具,永遠(yuǎn)不能替代有經(jīng)驗的管理人員所起的作用,警校如果想在以后的學(xué)員隊管理過程中走向科學(xué),需要數(shù)據(jù)挖掘工作者與管理者的配合。

[1]R AGRAWAL,T IMIELINSKI,A SWAMI[C].Mining Association Rulesetween Sets of Items in Large Databases.Proceedings of the ACM SIGMOD Conference on Management of Data,1993.

[2]A SAVASERE,E OMIECINSK I,S NNAVATHE[C].An efficient Algorithm for Mining Association Rules in Large Databases.Proceedings of the 21st International Conference on Very large Database,1995.

[3]JSPARK,M SCHEN,PS YU[C].An Effective Hash-based Algorithm for Mining Association Rules.Proceedings of ACM SIGMOD International Conference on Management of Data,1995,(5)：175-186.

[4]劉韜,樓興華.SQL Server 2000數(shù)據(jù)庫系統(tǒng)開發(fā)[M].北京：人民郵電大學(xué)出版社,2004：16-90.

[5]葉子青.ASP網(wǎng)絡(luò)待發(fā)入門與實踐[M].人民郵電出版社,2006：78-136.

[6]郭常圳,李云錦.ASP.NET網(wǎng)絡(luò)應(yīng)用開發(fā)例學(xué)與實踐[M].北京：清華大學(xué)出版社,2006：3-99.

[7]蔡偉杰,楊曉輝,等.關(guān)聯(lián)規(guī)則綜述[J].計算機工程,2001,27(5)：31-33,49.