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

●湯鈺涵

(公安海警高等?？茖W(xué)校,浙江寧波 315801)

一、引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

*,刪除Ck

*中所有那些(K-1)子集不在 Lk-1的項(xiàng)目集,得到候選集合 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*,若上面的算法描述中沒(méi)有 If條件,那么將出現(xiàn)很多重復(fù)項(xiàng)。因?yàn)榧s定項(xiàng)目集中的項(xiàng)目是按照字母順序排列的,所以,通過(guò)使用 If條件,可以避免產(chǎn)生重復(fù)的項(xiàng)。另外 Prune步驟是用來(lái)刪除 Ck中的非頻繁項(xiàng)目集的。

舉例說(shuō)明如下：L3={(A,B,C),(A,B,D),(A,C,D),(A,C,E),(B,C,D)},通過(guò) Join操作后得到：C4={(A,B,C,D),(A,C,D,E)},修剪后得到C4=(A,B,C,D),因?yàn)閧C,D,E}? L3.

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

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

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

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

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

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

五、結(jié)束語(yǔ)

將關(guān)聯(lián)規(guī)則應(yīng)用于警校學(xué)員隊(duì)信息管理是筆者的一個(gè)設(shè)想,目的就是提高學(xué)員隊(duì)日常管理工作的效率,節(jié)省更多的時(shí)間和人力,一個(gè)實(shí)用的管理系統(tǒng)將為決策提供支持,使數(shù)據(jù)獲取過(guò)程變得更加方便,更有根據(jù),數(shù)據(jù)分析更加全面,但是數(shù)據(jù)挖掘只是一個(gè)強(qiáng)大的工具,永遠(yuǎn)不能替代有經(jīng)驗(yàn)的管理人員所起的作用,警校如果想在以后的學(xué)員隊(duì)管理過(guò)程中走向科學(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ù)庫(kù)系統(tǒng)開(kāi)發(fā)[M].北京：人民郵電大學(xué)出版社,2004：16-90.

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

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

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