將關聯規則挖掘算法應用于警校學員隊信息管理

●湯鈺涵

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

一、引言

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

二、關聯規則挖掘、基本思想

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

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

三、警校學員隊信息管理現狀

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

四、關聯規則的經典算法

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

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

2.使用第一步找到的頻集產生期望的規則。

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

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

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);//事務 T中包含的候選集

For All Candidates C∈CtDo

C.Count++;

End

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

End

End

Answer=∪Lk

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

APriori_Gen()函數的參數為 Lk-1,結果返回含有 K個項目的候選項目集 Ck,事實上它由兩步構成：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條件,那么將出現很多重復項。因為約定項目集中的項目是按照字母順序排列的,所以,通過使用 If條件,可以避免產生重復的項。另外 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算法首先掃描數據庫并計算其中的每一個項目 I的支持度,產生大 1項目集 L1,然后再掃描數據庫計算大 2-項目集 L2,…,直到有個 R值使得Lr為空,這時算法停止。在第 K次循環中,由兩步組成：

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

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

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

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

表1 交易數據庫

五、結束語

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

[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數據庫系統開發[M].北京：人民郵電大學出版社,2004：16-90.

[5]葉子青.ASP網絡待發入門與實踐[M].人民郵電出版社,2006：78-136.

[6]郭常圳,李云錦.ASP.NET網絡應用開發例學與實踐[M].北京：清華大學出版社,2006：3-99.

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