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

陳瀟瀟+++蔡迎歸

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

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

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

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

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

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

Apriori算法是最經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法，是由Agrawal首次提出的，是基于計(jì)算候選集的遞推方法，其思想是利用已知的高頻數(shù)據(jù)集推導(dǎo)其他高頻數(shù)據(jù)項(xiàng)集，是一種寬度優(yōu)先算法。該算法的主要工作在于尋找頻繁項(xiàng)集，它利用了頻繁項(xiàng)集的向下封閉性（即頻繁項(xiàng)集的子集必須是頻繁項(xiàng)集），k-項(xiàng)集用于探索（k+1）-項(xiàng)集。Apriori通過(guò)K次掃描數(shù)據(jù)庫(kù)來(lái)發(fā)掘頻繁K項(xiàng)集，大量的時(shí)間浪費(fèi)在IO上，并且以數(shù)據(jù)庫(kù)中各項(xiàng)目的重要程度相同以及各項(xiàng)目分布均勻?yàn)榍疤幔菀缀雎愿怕市〉匾愿叩捻?xiàng)目。

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

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

2.1 候選項(xiàng)目集的支持度計(jì)算過(guò)程

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果及分析

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

5 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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