關聯規則挖掘Apriori算法的一種改進

屈鑫乙　王迪　劉滏

[摘 要]Apriori算法是關聯規則挖掘中的經典算法，但在算法執行中，會多次掃描數據庫并產生大量的候選集，導致算法效率降低。在分析Apriori算法的基礎上，利用任何一個頻繁k+1項集一定可以表示成一個頻繁k項集與一個頻繁1項集的交集這一性質，產生頻繁項集，并減少掃描數據庫的次數，提高算法的效率，實驗結果也表明，改進算法比Apriori算法有更好的性能。

[關鍵詞]Apriori算法；關聯規則；數據挖掘

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

1 引 言

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

R.Agrawal于1994年首先提出了挖掘關聯規則的Apriori算法[3]，其基本思想是重復掃描數據庫，根據頻繁項集的超集才可能是頻繁項集這一原理，由長度為k的頻繁項集進行迭代計算產生長度為k+1的候選集，再對數據庫進行掃描判斷其是否為頻繁項集。

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

2 改進的Apriori算法

2.1 算法的相關概念

頻繁項集具有如下幾個性質：[8]

性質1 頻繁項集的所有非空子集都是頻繁項集，非頻繁項集的超集都是非頻繁項集。

性質2 如果頻繁k項集還能產生頻繁k+1項集，則頻繁k項集中的項數必須大于k。

2.2 算法思想

Apriori算法將關聯規則的發現過程分成了兩個步驟：

（1）找出所有支持度高于用戶設定的最小支持度的項集，即發現所有的頻繁項集。

（2）通過發現的頻繁項集構造出滿足用戶最小置信度的規則。[9]

但是在執行過程中Apriori算法需要頻繁地掃描數據庫，這一行為會造成過重的I/O負擔[10]，改進算法將通過減少數據庫掃描次數的方式來減輕I/O負擔。

2.3 實例分析

依據上述改進的算法，以一個實例對該算法進行分析。表1為事務數據庫，設最小支持度為20%，則最小支持度計數等于2。

2.4 算法實驗與分析

為了驗證本文改進算法的有效性，將其與Apriori經典算法進行實驗對比，測試的數據庫選用本校對高校教師的一次調查問卷，數據庫中共有1681條記錄，數據庫中部分記錄如表3所示。因為在本次調查中，教師只需要在24個選項中，選出最符合自己意愿的某幾個選項，因此數據的存儲采用簡單二維表進行記錄，用以節省存儲空間。

采用的實驗環境：CPU為Intel Core I7 2.60GHz，內存8GB，操作系統為WIN10 專業版，數據庫采用SQL2014，算法采用C#語言編寫并在VS2012環境下編譯，下圖是改進算法與Apriori經典算法在不同支持度下執行時間對比。

不同支持度下兩種算法的執行時間對比

改進算法在效率上優于Apriori算法，并且在最小支持度較小時，改進算法的執行時間相對于Apriori算法具有明顯優勢，但是隨著最小支持度的增加，兩種算法的執行時間均大幅減少，Apriori算法與改進算法的執行時間開銷非常接近，這是因為隨著最小支持度的增加，迭代次數減少，運算過程中產生的頻繁項集的數量均大幅度減少，使得算法的執行時間減少。

3 結論與思考

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

參考文獻：

[1]劉華婷，郭仁祥，姜浩.關聯規則挖掘Apriori算法的研究與改進[J].計算機應用與軟件，2009，26（1）：146-149.

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

[3]Pang-Ning Tan，Michael Steinbach，Vipin Kumar.數據挖掘導論[M].北京：人民郵電出版社，2006.

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

[5]焦學磊，王新莊.基于矩陣的頻繁項集發現算法[J].江漢大學學報：自然科學版，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]崔貫勛，李梁，王柯柯，等.關聯規則挖掘中Apriori算法的研究與改進[J].計算機應用.2010，30（11）：2952-2955.

[8]劉興濤，石冰，解英文.挖掘關聯規則中Apriori算法的一種改進[J].山東大學學報：理學版，2008，43（11）：67-71.

[9]熊平.數據挖掘算法與Clementine實踐[M].北京：清華大學出版社，2011.

[10]周超發，王志堅，葉楓，等.關聯規則挖掘算法Apriori的研究改進[J].計算機科學與探索，2015，9（9）：105-108.

3.1.2 人員操作過程不規范

變電工作人員是整個變電設備運行中的直接操作者，是整個變電運作的核心。他們的整體素質、安全防范意識、操作熟練度以及規范度都將直接關乎整個變電運行工作的安全性和穩定性。[5]一方面，因為變電站的需要操控的設備繁多，導致變電工作人員工作次數頻繁，但其勞動形式單一，卻容易導致變電工作人員喪失工作熱情、實際操作中注意力不集中，進而造成操作失誤。另一方面，由于一些操作人員缺乏對于變電工作的了解，加之安全意識薄弱、工作態度不嚴謹、對操作程序不嚴格執行等，都會大大增加安全事故發生的可能性。

3.1.3 安全管理工作不到位

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

3.2 變電設備安全防范措施

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

首先，從人員層面，我們要加強變電運行人員的安全思想教育，讓操作人員深刻意識到安全操作的重要性，同時加強員工素質，對變電運行操作人員進行崗前培訓，在熟悉設備性能和設備操作流程的基礎上，加強其操作的熟練度，培養操作規范性，并使其學會鑒別異?，F象和設備維護工作。

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

最后，從制度層面，我們要完善管理制度，加強監督機制，對參與變電運行的所有工作人員落實其崗位責任，實行定崗定員制度，同時加強交接班時的安全工作，做到準時交接，記錄詳細，在交接班時也要注意對口交接，并對現場做進一步的巡查。

4 結 論

輸電工程和變電工程是電力供應中的重要且復雜的環節，兩者的安全與穩定，是我國電力系統正常運行的關鍵保障，更是我國經濟發展的重要保障工作之一。因此，為了保障變電設備安全運行，這就需要我們各部門的共同合作，加強安全意識培訓，提高變電工作人員工作能力，增強其責任意識，嚴格按照相關規定操作電力設備，及時檢修和更換設備，做到防患于未然。在保障輸電設備安全運行的過程中，我們需要準確、全面、細致地識別其故障模式，對癥下藥，推動我國電力行業持續、健康發展。

參考文獻：

[1]李盛盛.輸電設備狀態監測主站系統的設計與開發[J].電力信息與通信技術，2010，8（11）：14-18.

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

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

[4]張兵.輸電線路運行中的安全隱患管控及預防對策探析[J].科技創業家，2012（21）.

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