基于改進Apriori算法的水政數據關聯規則分析研究

陳瀟瀟+++蔡迎歸

摘 要：數據挖掘中的關聯規則挖掘能夠發現大量數據中項集之間潛在的關聯，運用關聯分析方法對水事違法案件數據進行挖掘分析，從而總結出水政執法隊伍在監察過程中存在的問題，以期提高水政執法能力和水平，有效地預防、遏制涉水違法現象。

關鍵詞：改進Apriori算法 水政 關聯規則

中圖分類號：TP311 文獻標識碼：A 文章編號：1672-3791（2017）09（c）-0202-02

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

由此，應用數據挖掘中的關聯規則對水政數據進行分析，通過對所采集到的水事違法案件數據進行預處理、數據挖掘等步驟，從中總結出水政執法隊伍在監察過程中存在的問題，以期提高水政執法能力和水平，有效地預防、遏制涉水違法現象。

1 關聯規則Apriori算法

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

2 Apriori算法的改進

本文從候選項目集的支持度計算過程和小候選項目集的規模兩個方面對原Apriori算法進行優化。

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

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

2.2 縮小候選項目集的規模

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

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

3 Apriori算法在水政數據分析中的應用

3.1 水事違法案件信息的預處理

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

3.2 改進Apriori算法對水事違法案件信息進行關聯規則挖掘

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

4 實驗結果及分析

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

5 結語

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

參考文獻

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

[2] 付沙，周航軍.關聯規則挖掘Apriori算法的研究與改進[J].微電子學與計算機，2013，30（9）：110-114.endprint