關(guān)聯(lián)規(guī)則挖掘Apriori算法的一種改進(jìn)

屈鑫乙　王迪　劉滏

[摘 要]Apriori算法是關(guān)聯(lián)規(guī)則挖掘中的經(jīng)典算法，但在算法執(zhí)行中，會(huì)多次掃描數(shù)據(jù)庫并產(chǎn)生大量的候選集，導(dǎo)致算法效率降低。在分析Apriori算法的基礎(chǔ)上，利用任何一個(gè)頻繁k+1項(xiàng)集一定可以表示成一個(gè)頻繁k項(xiàng)集與一個(gè)頻繁1項(xiàng)集的交集這一性質(zhì)，產(chǎn)生頻繁項(xiàng)集，并減少掃描數(shù)據(jù)庫的次數(shù)，提高算法的效率，實(shí)驗(yàn)結(jié)果也表明，改進(jìn)算法比Apriori算法有更好的性能。

[關(guān)鍵詞]Apriori算法；關(guān)聯(lián)規(guī)則；數(shù)據(jù)挖掘

[DOI]10.13939/j.cnki.zgsc.2016.36.086

1 引 言

隨著計(jì)算機(jī)技術(shù)與數(shù)據(jù)庫技術(shù)的迅猛發(fā)展，如何從海量的數(shù)據(jù)中尋找出有效的信息成為了數(shù)據(jù)挖掘問題中的一項(xiàng)重要研究內(nèi)容。數(shù)據(jù)挖掘是從大量的數(shù)據(jù)中挖掘出隱含的、未知的、用戶可能感興趣的和對(duì)決策有潛在價(jià)值的知識(shí)和規(guī)則。[1]挖掘關(guān)聯(lián)規(guī)則問題可以分解為以下兩個(gè)子問題：[2]①找出所有頻繁項(xiàng)集。這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持計(jì)數(shù)一樣。②根據(jù)定義，由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則必須滿足最小支持度和最小置信度。

R.Agrawal于1994年首先提出了挖掘關(guān)聯(lián)規(guī)則的Apriori算法[3]，其基本思想是重復(fù)掃描數(shù)據(jù)庫，根據(jù)頻繁項(xiàng)集的超集才可能是頻繁項(xiàng)集這一原理，由長度為k的頻繁項(xiàng)集進(jìn)行迭代計(jì)算產(chǎn)生長度為k+1的候選集，再對(duì)數(shù)據(jù)庫進(jìn)行掃描判斷其是否為頻繁項(xiàng)集。

很多文獻(xiàn)基于Apriori算法提出改進(jìn)算法，楊志剛[4]等人提出了基于壓縮事務(wù)矩陣相乘的改進(jìn)算法，焦學(xué)磊[5]等人提出了基于矩陣的頻繁項(xiàng)集發(fā)現(xiàn)算法，將數(shù)據(jù)庫信息全部以矩陣表示，該方法僅需要對(duì)數(shù)據(jù)庫進(jìn)行一次掃描，有效地減少了算法執(zhí)行的時(shí)間，Najadat[6]等人對(duì)Apriori算法的不足之處進(jìn)行了討論，并優(yōu)化了Apriori算法在剪枝過程中計(jì)算量大的問題，崔貫勛[7]等人提出對(duì)數(shù)據(jù)庫進(jìn)行一定的處理，使其成為水平結(jié)構(gòu)再進(jìn)行計(jì)算，但該方法需要占用大量的空間，也使得該方法的提高程度受到了限制。

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

2.1 算法的相關(guān)概念

頻繁項(xiàng)集具有如下幾個(gè)性質(zhì)：[8]

性質(zhì)1 頻繁項(xiàng)集的所有非空子集都是頻繁項(xiàng)集，非頻繁項(xiàng)集的超集都是非頻繁項(xiàng)集。

性質(zhì)2 如果頻繁k項(xiàng)集還能產(chǎn)生頻繁k+1項(xiàng)集，則頻繁k項(xiàng)集中的項(xiàng)數(shù)必須大于k。

2.2 算法思想

Apriori算法將關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)過程分成了兩個(gè)步驟：

（1）找出所有支持度高于用戶設(shè)定的最小支持度的項(xiàng)集，即發(fā)現(xiàn)所有的頻繁項(xiàng)集。

（2）通過發(fā)現(xiàn)的頻繁項(xiàng)集構(gòu)造出滿足用戶最小置信度的規(guī)則。[9]

但是在執(zhí)行過程中Apriori算法需要頻繁地掃描數(shù)據(jù)庫，這一行為會(huì)造成過重的I/O負(fù)擔(dān)[10]，改進(jìn)算法將通過減少數(shù)據(jù)庫掃描次數(shù)的方式來減輕I/O負(fù)擔(dān)。

2.3 實(shí)例分析

依據(jù)上述改進(jìn)的算法，以一個(gè)實(shí)例對(duì)該算法進(jìn)行分析。表1為事務(wù)數(shù)據(jù)庫，設(shè)最小支持度為20%，則最小支持度計(jì)數(shù)等于2。

2.4 算法實(shí)驗(yàn)與分析

為了驗(yàn)證本文改進(jìn)算法的有效性，將其與Apriori經(jīng)典算法進(jìn)行實(shí)驗(yàn)對(duì)比，測試的數(shù)據(jù)庫選用本校對(duì)高校教師的一次調(diào)查問卷，數(shù)據(jù)庫中共有1681條記錄，數(shù)據(jù)庫中部分記錄如表3所示。因?yàn)樵诒敬握{(diào)查中，教師只需要在24個(gè)選項(xiàng)中，選出最符合自己意愿的某幾個(gè)選項(xiàng)，因此數(shù)據(jù)的存儲(chǔ)采用簡單二維表進(jìn)行記錄，用以節(jié)省存儲(chǔ)空間。

采用的實(shí)驗(yàn)環(huán)境：CPU為Intel Core I7 2.60GHz，內(nèi)存8GB，操作系統(tǒng)為WIN10 專業(yè)版，數(shù)據(jù)庫采用SQL2014，算法采用C#語言編寫并在VS2012環(huán)境下編譯，下圖是改進(jìn)算法與Apriori經(jīng)典算法在不同支持度下執(zhí)行時(shí)間對(duì)比。

不同支持度下兩種算法的執(zhí)行時(shí)間對(duì)比

改進(jìn)算法在效率上優(yōu)于Apriori算法，并且在最小支持度較小時(shí)，改進(jìn)算法的執(zhí)行時(shí)間相對(duì)于Apriori算法具有明顯優(yōu)勢，但是隨著最小支持度的增加，兩種算法的執(zhí)行時(shí)間均大幅減少，Apriori算法與改進(jìn)算法的執(zhí)行時(shí)間開銷非常接近，這是因?yàn)殡S著最小支持度的增加，迭代次數(shù)減少，運(yùn)算過程中產(chǎn)生的頻繁項(xiàng)集的數(shù)量均大幅度減少，使得算法的執(zhí)行時(shí)間減少。

3 結(jié)論與思考

本文提出的算法與Apriori算法相比減少了I/O次數(shù)，在改進(jìn)算法中，是以項(xiàng)集中包含元素的數(shù)量與最小支持度計(jì)數(shù)對(duì)比判斷其是否為頻繁項(xiàng)集，不需要對(duì)數(shù)據(jù)庫進(jìn)行多次掃描，而Apriori算法在每次進(jìn)行剪枝時(shí)，需要對(duì)數(shù)據(jù)庫進(jìn)行掃描才能判斷生成的項(xiàng)集是否為頻繁項(xiàng)集，改進(jìn)算法是從這一點(diǎn)出發(fā)，進(jìn)行改進(jìn)從而提高算法的執(zhí)行效率，減少算法的執(zhí)行時(shí)間。雖然改進(jìn)算法雖然減少了I/O次數(shù)，提高了算法的執(zhí)行效率，但是算法在執(zhí)行過程中，需要保存大量的數(shù)據(jù)，因而需要占用較多的內(nèi)存空間，因此如何對(duì)數(shù)據(jù)量較大的數(shù)據(jù)庫執(zhí)行本算法，還有待進(jìn)一步的研究與改進(jìn)。

參考文獻(xiàn)：

[1]劉華婷，郭仁祥，姜浩.關(guān)聯(lián)規(guī)則挖掘Apriori算法的研究與改進(jìn)[J].計(jì)算機(jī)應(yīng)用與軟件，2009，26（1）：146-149.

[2]Han J. W.，Kamber M.Data Mining：Concepts and Techniques，數(shù)據(jù)挖掘：概念與技術(shù)[M].范明，孟小峰，等，譯.北京：機(jī)械工業(yè)出版社，2001.

[3]Pang-Ning Tan，Michael Steinbach，Vipin Kumar.數(shù)據(jù)挖掘?qū)д揫M].北京：人民郵電出版社，2006.

[4]楊志剛，何順月.基于壓縮事務(wù)矩陣相乘的Apriori改進(jìn)算法[J].中國新技術(shù)新產(chǎn)品，2010，30（6）：57-58.

[5]焦學(xué)磊，王新莊.基于矩陣的頻繁項(xiàng)集發(fā)現(xiàn)算法[J].江漢大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，35（1）：43-46.

[6]Najadat H.M.，Al-Maolegi M.，Arkok B..An Improved Apriori Algorithm for Association Rules[J].International Research Journal of Computer Science and Application，2013，（1）：1-8.

[7]崔貫勛，李梁，王柯柯，等.關(guān)聯(lián)規(guī)則挖掘中Apriori算法的研究與改進(jìn)[J].計(jì)算機(jī)應(yīng)用.2010，30（11）：2952-2955.

[8]劉興濤，石冰，解英文.挖掘關(guān)聯(lián)規(guī)則中Apriori算法的一種改進(jìn)[J].山東大學(xué)學(xué)報(bào)：理學(xué)版，2008，43（11）：67-71.

[9]熊平.數(shù)據(jù)挖掘算法與Clementine實(shí)踐[M].北京：清華大學(xué)出版社，2011.

[10]周超發(fā)，王志堅(jiān)，葉楓，等.關(guān)聯(lián)規(guī)則挖掘算法Apriori的研究改進(jìn)[J].計(jì)算機(jī)科學(xué)與探索，2015，9（9）：105-108.

3.1.2 人員操作過程不規(guī)范

變電工作人員是整個(gè)變電設(shè)備運(yùn)行中的直接操作者，是整個(gè)變電運(yùn)作的核心。他們的整體素質(zhì)、安全防范意識(shí)、操作熟練度以及規(guī)范度都將直接關(guān)乎整個(gè)變電運(yùn)行工作的安全性和穩(wěn)定性。[5]一方面，因?yàn)樽冸娬镜男枰倏氐脑O(shè)備繁多，導(dǎo)致變電工作人員工作次數(shù)頻繁，但其勞動(dòng)形式單一，卻容易導(dǎo)致變電工作人員喪失工作熱情、實(shí)際操作中注意力不集中，進(jìn)而造成操作失誤。另一方面，由于一些操作人員缺乏對(duì)于變電工作的了解，加之安全意識(shí)薄弱、工作態(tài)度不嚴(yán)謹(jǐn)、對(duì)操作程序不嚴(yán)格執(zhí)行等，都會(huì)大大增加安全事故發(fā)生的可能性。

3.1.3 安全管理工作不到位

安全管理工作不到位是造成變電設(shè)備工作安全問題的重要原因，主要表現(xiàn)在安全管理工作不科學(xué)、不規(guī)范。由于缺乏科學(xué)的設(shè)計(jì)，管理制度上存在著安全漏洞，例如安全事故責(zé)任劃分不清，領(lǐng)導(dǎo)混亂；領(lǐng)導(dǎo)層對(duì)員工的安全教育培訓(xùn)不重視，往往以走過場的形式組織安全教育，員工在安全意識(shí)、安全技能方面都十分匱乏。一線操作人員是保障變電設(shè)備安全運(yùn)行的關(guān)鍵，但是心無大局，對(duì)于安全意識(shí)以及安全問題造成的后果沒有明確的意識(shí)，對(duì)于安全工作往往是應(yīng)付了事；監(jiān)督人員沒有按照規(guī)定行使好監(jiān)督責(zé)任，沒有及時(shí)地做好每日的安全監(jiān)督記錄工作，存在著監(jiān)督無用的錯(cuò)誤想法。這些現(xiàn)象都表明了安全工作只停留在制度層面，而安全管理工作疏忽大意，體現(xiàn)了管理者管理能力、水平仍有待提高。在這種管理狀態(tài)下，很可能導(dǎo)致安全事故的進(jìn)一步惡化。

3.2 變電設(shè)備安全防范措施

針對(duì)變電設(shè)備運(yùn)行中存在的這些主要安全問題，我們需要采取合理的安全防范措施，才能減少甚至根除種種安全隱患。

首先，從人員層面，我們要加強(qiáng)變電運(yùn)行人員的安全思想教育，讓操作人員深刻意識(shí)到安全操作的重要性，同時(shí)加強(qiáng)員工素質(zhì)，對(duì)變電運(yùn)行操作人員進(jìn)行崗前培訓(xùn)，在熟悉設(shè)備性能和設(shè)備操作流程的基礎(chǔ)上，加強(qiáng)其操作的熟練度，培養(yǎng)操作規(guī)范性，并使其學(xué)會(huì)鑒別異?，F(xiàn)象和設(shè)備維護(hù)工作。

其次，從設(shè)備層面，我們要增強(qiáng)設(shè)備管理，除了每天的例巡檢查外，還需要對(duì)設(shè)備進(jìn)行不同的等級(jí)檢查，以便掌握設(shè)備的真實(shí)運(yùn)行狀況，根據(jù)檢查結(jié)果和實(shí)際情況做出快速、有效的綜合判斷，并及時(shí)維修或更換故障設(shè)備。在引進(jìn)新設(shè)備時(shí)，要從各個(gè)階段對(duì)設(shè)備質(zhì)量、運(yùn)行安全嚴(yán)格把關(guān)，依靠在線診斷系統(tǒng)等技術(shù)對(duì)設(shè)備進(jìn)行實(shí)時(shí)的檢測和評(píng)價(jià)。

最后，從制度層面，我們要完善管理制度，加強(qiáng)監(jiān)督機(jī)制，對(duì)參與變電運(yùn)行的所有工作人員落實(shí)其崗位責(zé)任，實(shí)行定崗定員制度，同時(shí)加強(qiáng)交接班時(shí)的安全工作，做到準(zhǔn)時(shí)交接，記錄詳細(xì)，在交接班時(shí)也要注意對(duì)口交接，并對(duì)現(xiàn)場做進(jìn)一步的巡查。

4 結(jié) 論

輸電工程和變電工程是電力供應(yīng)中的重要且復(fù)雜的環(huán)節(jié)，兩者的安全與穩(wěn)定，是我國電力系統(tǒng)正常運(yùn)行的關(guān)鍵保障，更是我國經(jīng)濟(jì)發(fā)展的重要保障工作之一。因此，為了保障變電設(shè)備安全運(yùn)行，這就需要我們各部門的共同合作，加強(qiáng)安全意識(shí)培訓(xùn)，提高變電工作人員工作能力，增強(qiáng)其責(zé)任意識(shí)，嚴(yán)格按照相關(guān)規(guī)定操作電力設(shè)備，及時(shí)檢修和更換設(shè)備，做到防患于未然。在保障輸電設(shè)備安全運(yùn)行的過程中，我們需要準(zhǔn)確、全面、細(xì)致地識(shí)別其故障模式，對(duì)癥下藥，推動(dòng)我國電力行業(yè)持續(xù)、健康發(fā)展。

參考文獻(xiàn)：

[1]李盛盛.輸電設(shè)備狀態(tài)監(jiān)測主站系統(tǒng)的設(shè)計(jì)與開發(fā)[J].電力信息與通信技術(shù)，2010，8（11）：14-18.

[2]李濤，馬薇，黃曉蓓.基于全壽命周期成本理論的變電設(shè)備管理[J].電網(wǎng)技術(shù)，2008，32（11）：50-53.

[3]徐興德.輸電線路運(yùn)行中存在的主要問題與維護(hù)管理措施[J].科技與創(chuàng)新，2014（17）：36-37.

[4]張兵.輸電線路運(yùn)行中的安全隱患管控及預(yù)防對(duì)策探析[J].科技創(chuàng)業(yè)家，2012（21）.

[5]余令勇，汪紅利.試論變電運(yùn)行安全管理與事故的防范[J].廣東科技，2012，21（24）：80-81.