基于改進(jìn)Apriori算法的水政數(shù)據(jù)關(guān)聯(lián)規(guī)則分析研究

陳瀟瀟+++蔡迎歸

摘 要：數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則挖掘能夠發(fā)現(xiàn)大量數(shù)據(jù)中項集之間潛在的關(guān)聯(lián)，運用關(guān)聯(lián)分析方法對水事違法案件數(shù)據(jù)進(jìn)行挖掘分析，從而總結(jié)出水政執(zhí)法隊伍在監(jiān)察過程中存在的問題，以期提高水政執(zhí)法能力和水平，有效地預(yù)防、遏制涉水違法現(xiàn)象。

關(guān)鍵詞：改進(jìn)Apriori算法 水政 關(guān)聯(lián)規(guī)則

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2017）09（c）-0202-02

隨著互聯(lián)網(wǎng)以及計算機相關(guān)技術(shù)的飛速發(fā)展，政務(wù)信息化的不斷推進(jìn)，水政執(zhí)法部門積累了海量的水事違法案件數(shù)據(jù)，而目前對于這些數(shù)據(jù)的使用多限于統(tǒng)計、查詢等傳統(tǒng)方式，其潛在的使用價值還遠(yuǎn)沒能得到充分的挖掘和實用，對于隱藏在這些數(shù)據(jù)后的規(guī)律、產(chǎn)生的原因往往無法得知，從而不能有針對性地對水政監(jiān)察管理中已存在的問題進(jìn)行相應(yīng)的變革。傳統(tǒng)的處理數(shù)據(jù)方式，已經(jīng)難以適應(yīng)于日益增長的數(shù)據(jù)規(guī)模，“信息爆炸”但“知識貧乏”，已成為一個現(xiàn)實問題。

由此，應(yīng)用數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則對水政數(shù)據(jù)進(jìn)行分析，通過對所采集到的水事違法案件數(shù)據(jù)進(jìn)行預(yù)處理、數(shù)據(jù)挖掘等步驟，從中總結(jié)出水政執(zhí)法隊伍在監(jiān)察過程中存在的問題，以期提高水政執(zhí)法能力和水平，有效地預(yù)防、遏制涉水違法現(xiàn)象。

1 關(guān)聯(lián)規(guī)則Apriori算法

Apriori算法是最經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法，是由Agrawal首次提出的，是基于計算候選集的遞推方法，其思想是利用已知的高頻數(shù)據(jù)集推導(dǎo)其他高頻數(shù)據(jù)項集，是一種寬度優(yōu)先算法。該算法的主要工作在于尋找頻繁項集，它利用了頻繁項集的向下封閉性（即頻繁項集的子集必須是頻繁項集），k-項集用于探索（k+1）-項集。Apriori通過K次掃描數(shù)據(jù)庫來發(fā)掘頻繁K項集，大量的時間浪費在IO上，并且以數(shù)據(jù)庫中各項目的重要程度相同以及各項目分布均勻為前提，容易忽略概率小但重要性高的項目。

2 Apriori算法的改進(jìn)

本文從候選項目集的支持度計算過程和小候選項目集的規(guī)模兩個方面對原Apriori算法進(jìn)行優(yōu)化。

2.1 候選項目集的支持度計算過程

在整個事務(wù)數(shù)據(jù)庫中，如果想要求得一條事務(wù)項的集合，可以將該事務(wù)項分解為單一的元素項，對單一元素項的集合在取交集的結(jié)果即是。根據(jù)這一定理，對Ck的計數(shù)工作，不需要再去頻繁的掃描數(shù)據(jù)庫，而是根據(jù)候選項集的集合可以分解為其項集元素在數(shù)據(jù)庫中的集合的交集這一規(guī)則，利用已經(jīng)生成的候選項集C1來推導(dǎo)得到。這樣，在計算支持度的計數(shù)的過程中，只掃描一遍數(shù)據(jù)庫，時間開銷會低于原算法。

2.2 縮小候選項目集的規(guī)模

在生成頻繁k-1項集后，對整個候選集進(jìn)行檢查裁剪，判斷LK-1包含的項集數(shù)是否小于其項集的維度。若小于，則不能生成k項候選集的，算法即可終止。在候選集LK-1中的項集Ii和Ij連接生成X時，對于X的每一個項集元素同樣進(jìn)行檢查，若項集元素個數(shù)小于候選集的維度，則該項集元素不會出現(xiàn)在生成k維的候選項目集中，可以刪除掉以減小候選集的規(guī)模。

通過上述兩個方面的優(yōu)化，可以生成一個完整的基于支持度計數(shù)工作和候選項目集規(guī)則優(yōu)化的改進(jìn)方案， 從而使算法效率有較大的提高。

3 Apriori算法在水政數(shù)據(jù)分析中的應(yīng)用

3.1 水事違法案件信息的預(yù)處理

在水政監(jiān)察管理系統(tǒng)的案件信息中，去除重復(fù)數(shù)據(jù)，挑選出科學(xué)的、安全、適用于數(shù)據(jù)挖掘應(yīng)用的屬性數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗。對于原始數(shù)據(jù)中某些屬性為空缺值的記錄，盡量補充缺失屬性。如用身份證件號碼填補年齡、籍貫的空缺、案件類型的空缺可以通過分析其他屬性獲得。數(shù)據(jù)清洗后，對某些原來沒有的屬性按需要進(jìn)行生成，通過泛化、屬性離散化處理將數(shù)據(jù)轉(zhuǎn)換以構(gòu)成一個適合數(shù)據(jù)挖掘的描述形式。如將案件類型泛化處理，取河道案、水工程案、水資源案、水土保持案和其他類案件五大類；年齡由出生日期轉(zhuǎn)化生成，并概化為少年（17歲以下）、青年（18～40歲）、中年（41～65歲）、老年（66歲以上）四個年齡段；將發(fā)案時間離散化處理為上午、下午、夜間、深夜；發(fā)案季節(jié)由發(fā)案時間轉(zhuǎn)化，離散化處理為春（3～5月）、夏（6～8月）、秋（9～11月）、冬（12～2月）；發(fā)案地點劃分成對應(yīng)水政監(jiān)察總隊所管轄的幾個地區(qū)；經(jīng)濟損失泛化劃分為一般、較大、嚴(yán)重、重大；職業(yè)泛化為無業(yè)、事業(yè)、企業(yè)、個體四大類；文化程度泛化為小學(xué)及以下、初中、高職中專、專（本）科、碩士及以上五類；戶籍略去縣市、街道等細(xì)節(jié)信息，簡化為各個省份名稱。

3.2 改進(jìn)Apriori算法對水事違法案件信息進(jìn)行關(guān)聯(lián)規(guī)則挖掘

數(shù)據(jù)做好預(yù)處理工作之后，根據(jù)造成經(jīng)濟損失的不同程度，進(jìn)行項目屬性權(quán)值的設(shè)置，如水事違法案件中造成重大經(jīng)濟損失的案件，其重要和危害程度明顯要高于其他案件，但它的發(fā)生概率通常較小而容易被忽略，需要增大其屬性權(quán)值。然后通過已經(jīng)由程序?qū)崿F(xiàn)的優(yōu)化算法，找出相關(guān)屬性之間的強關(guān)聯(lián)規(guī)則，如案件類型、發(fā)案地點、發(fā)案時間段、發(fā)案季節(jié)、經(jīng)濟損失、違法人員年齡段、職業(yè)、文化程度以及戶籍等屬性之間的強關(guān)聯(lián)規(guī)則，并對結(jié)果進(jìn)行解釋評估，為水政執(zhí)法部門制定重要決策，合理部署水政執(zhí)法工作提供宏觀決策依據(jù)。

4 實驗結(jié)果及分析

以經(jīng)過預(yù)處理后的水事違法案件信息作為數(shù)據(jù)源進(jìn)行仿真實驗，案件信息記錄5400條，運用經(jīng)典關(guān)聯(lián)規(guī)則Apriori算法和改進(jìn)后的Apriori算法，通過設(shè)置不同的事務(wù)數(shù)量、不同的支持度、不同的項目個數(shù)，統(tǒng)計兩種算法的運行時間和生成強關(guān)聯(lián)規(guī)則數(shù)量，對比分析算法的性能和效率。實驗測試采用Matlab語言編寫程序，在Matlab平臺下進(jìn)行調(diào)試，CPU采用的Intel（R）i3-3217U，內(nèi)存4G，操作系統(tǒng)為64位Windows7。挖掘結(jié)果得出了采用同樣最小支持度對于不同事務(wù)記錄條數(shù)進(jìn)行比較時，兩種算法在執(zhí)行時間的區(qū)別。從實驗結(jié)果來看，改進(jìn)的Apriori算法實現(xiàn)了預(yù)期的目標(biāo)，與同類算法相比，改算法具有挖掘結(jié)果準(zhǔn)確、速度快、運算量小、時間短、空間利用率高等特點。同時，也反映了這兩種算法的最小支持度與時間的關(guān)系：最小支持度最高，所需要的時間越多；對于不同的最小支持度，改進(jìn)的Apriori算法所需時間比經(jīng)典Apriori算法所需要的時間短。通過以上分析，綜合關(guān)聯(lián)規(guī)則挖掘結(jié)果，得到如下結(jié)論，水事違法案件雖然類型多情況復(fù)雜，但是違法人員結(jié)構(gòu)極其類似，年齡趨于兩極化，青少年和老年居多，而且文化素質(zhì)低，特別是無業(yè)人員在違法人員中所占比重較大。水土保持案和水資源案較多的在A1地區(qū)，在A2地區(qū)夜間多發(fā)盜竊設(shè)備的水工程案

5 結(jié)語

本文詳細(xì)說明了關(guān)聯(lián)規(guī)則算法Apriori在水事違法案件信息挖掘中的應(yīng)用過程：首先簡述了關(guān)聯(lián)規(guī)則基本概念和Apriori算法原理；其次提出了一個完整的基于支持度計數(shù)工作和候選項目集規(guī)則優(yōu)化的改進(jìn)方案，從而使算法效率有較大的提高；最后以經(jīng)過預(yù)處理后的水事違法案件信息作為數(shù)據(jù)源進(jìn)行仿真實驗，對關(guān)聯(lián)規(guī)則挖掘結(jié)果進(jìn)行分析，從而提高水政執(zhí)法能力和水平，有效地預(yù)防、遏制涉水違法現(xiàn)象。

參考文獻(xiàn)

[1] 苗苗苗，王玉英.基于矩陣壓縮的Apriori算法改進(jìn)的研究[J].計算機工程與應(yīng)用，2013，49（1）：159-162.

[2] 付沙，周航軍.關(guān)聯(lián)規(guī)則挖掘Apriori算法的研究與改進(jìn)[J].微電子學(xué)與計算機，2013，30（9）：110-114.endprint