基于云平臺的并行關聯規則挖掘算法分析

穆俊

摘 要： 自云計算技術出現之后，數據挖掘技術取得了突破性發展。數據挖掘系統不僅實現了低成本、高效率運行，并且系統儲存空間和系統可擴展性也在不斷擴大，大大提高了數據挖掘效率。這里簡要闡述了基于云平臺的并行關聯規則挖掘算法分析的研究意義，并對基于Hadoop的數據挖掘系統和數據算法設計進行了詳細介紹。

關鍵詞： 數據挖掘； 關聯規則； 云平臺； Hadoop

中圖分類號： TN702?34； TP391 文獻標識碼： A 文章編號： 1004?373X（2015）11?0123?03

Analysis of parallel association rule mining algorithm based on cloud platform

MU Jun

（Department of Information Science and Technology， Lincang Teachers College， Lincang 677000， China）

Abstract： A breakthrough development of data mining technologies was acquired after cloud computing technology appeared. The data mining system realizes the operation of low cost and high efficiency， and expands systems storage space and scalability gradually， so data mining efficiency is improved greatly. In this paper， research significance of parallel association rule mining algorithm based on cloud platform is expounded briefly， data mining system and data algorithm design based on Hadoop are introduced in detail.

Keywords： data mining； association rule； cloud platform； Hadoop

隨著計算機網絡技術、信息技術以及無線通信技術在各個領域和各個行業中的應用，數據庫也得到了廣泛應用，并且其所積累的數據量也越來越大，幾乎都達到了TB級，甚至，有一些數據量已經達到了PB級。由于這些數據都相對比較復雜，屬于異構結構，并且這些數據大多有噪聲，數據量巨大，所以很難被直接利用。因此，通過高效率、低成本的挖掘方式將有用的數據信息從這些數據中挖掘出來進行有效利用，成為當前數據挖掘技術領域最為重要的研究課題。一直以來，雖然相關研究人員都致力于對這些數據挖掘技術的研究，但是由于受到科學技術以及自身技術水平等方面因素的限制，一直沒有研究出有效的解決方案，而云計算的出現，則為數據挖掘技術的研究帶來了突破。本文對基于云平臺的并行關聯規則挖掘算法進行詳細分析，為進一步提升數據挖掘技術水平提供科學有效的參考依據。

1 數據挖掘

數據挖掘也被稱為是數據庫中的知識發現（Knowledge Discovery in Databases，KDD），主要指的是從大量的、有噪聲的、異構的和復雜的海量數據中挖掘出有利用價值的信息或者是知識，然后對這些信息或者是知識進行整理和分析的過程[1]。一直以來，在對數據信息和知識進行挖掘的過程中，所采用的都是依靠大規模計算機和數據挖掘設備對海量數據中的有效信息和知識進行挖掘和分析，這種數據挖掘方式，雖然也能夠對數據信息和知識進行有效挖掘和分析，但是這種數據挖掘方法比較繁瑣，過程比較復雜，并且成本也比較大，不利于普及應用。而基于云平臺的并行關聯規則挖掘技術，則為數據挖掘技術的提升帶來了新的解決方案，通過計算機網絡技術、信息技術以及無線網絡通信技術的結合，實現了數據挖掘和計算的虛擬化[2?3]。與傳統數據挖掘和計算技術相比，基于云平臺的云計算技術具有更加強大的計算能力和更加龐大的儲存空間，并且由于實現了數據挖掘和計算的虛擬化，其運行成本更低，靈活性更強。可以說，云計算的出現，實現了海量數據挖掘和計算的改革創新，使企業能夠利用更低的成本獲取更加有價值的數據信息，這對于提升企業決策的合理性和科學性，進一步提升企業的經濟效益，推動企業更好、更快發展具有極為重要的影響作用。

對于任何一個企業來說，如果能夠從海量數據中挖掘出有利用價值的信息，并能夠對這些信息進行有效分析和整理，就能夠為企業的決策帶來強有力的支持，使企業決策變得更加合理和科學，進而使企業在行業競爭中占據有利地位，為企業謀取更大的經濟效益，這對于推動企業的快速、持續發展具有極為重要的影響作用。基于以上特點，越來越多的企業開始對數據挖掘技術引起足夠重視，并不斷對數據挖掘技術進行研究和應用。

數據挖掘包含的技術十分繁雜，其中，聚類分析技術、預測技術、數據計算技術、關聯規則技術、模糊邏輯技術、可視化技術、自動化和智能化技術以及數據統計分析技術是最為重要的幾種技術，對整個數據挖掘技術具有比較重要的影響[4]。應用數據挖掘系統對數據進行挖掘的過程中，主要分為目標業務確定、數據源選擇、收集數據、選擇數據、對數據質量進行檢查、對數據進行轉換以及對數據挖掘結果進行分析等幾個流程，其中任何一個環節出現問題都會對整個數據挖掘的最終結果造成影響[5]。

2 基于Hadoop的數據挖掘系統

自20世紀80年代第一代數據挖掘系統誕生以來，數據挖掘系統歷經五代發展，專家、學者一直在對數據挖掘系統進行改進和完善。

第一代數據挖掘系統是最為簡單的一代系統，系統中僅包含了幾個數據挖掘算法，其不論是數據挖掘能力還是計算能力都比較有限。 第一代系統在對數據進行挖掘的過程中，需要將數據輸入到系統中之后才能夠對數據進行挖掘和計算，所以，系統中幾種算法也只適合應用于向量數據的挖掘[6]。

第二代數據挖掘系統相對于第一代數據挖掘系統已經有了突破性進展，其不僅支持數據庫，還能與DBMS進行集成， 具有比較良好的擴展性。除此之外，在第二代系統中還對數據算法進行了完善，不再局限于對向量數據進行挖掘，對于一些大型數據集和復雜數據集也能夠進行數據挖掘，并且具有比較良好的挖掘效果。同時，在第二代系統中，還支持數據挖掘查詢語言和數據挖掘模式，能夠在一定程度上提升系統的實用性和應用效率。

第三代數據挖掘系統是在第二代數據挖掘系統之上進行了進一步升級和擴展，并實現了數據挖掘的集成化和網絡化，進一步提升了數據挖掘效率。與第二代數據挖掘系統相比，第三代數據挖掘系統已經初步實現了數據挖掘的網絡化。

第四代數據挖掘系統在基于第三代系統網絡化的基礎上實現了一定移動計算。在第四代數據挖掘系統中，可以對嵌入式系統、移動系統以及一些分布式系統中的數據進行挖掘和計算，實現了數據挖掘系統的移動化和分布化。

第五代數據挖掘系統也就是基于云平臺的數據挖掘系統，系統中的算法為并行關聯規則挖掘算法，是當前應用最為廣泛，也是數據挖掘主要發展方向的數據挖掘系統[7]。該系統與前幾代數據挖掘系統相比，不僅更加方便、快捷、高效，并且具有成本低、儲存空間大以及擴展性強等特點。

3 基于Hadoop的數據算法設計

3.1 數據流程

基于云平臺的并行關聯規則挖掘算法設計主要是在AprioriPMR算法的基礎上，通過使用兩次MapReduce job查找，將頻繁項目集的集合[L]找出。在對算法進行設計的過程中，為了確保算法設計的順利進行，在第一次執行MapReduce job的過程中，應該先利用空格將Map任務階段的每一條交易記錄都分離出來，并對交易中的每個項目都進行賦值， 賦值為1，使其形成<‘項目，1>鍵值對。在執行Reduce任務時，對‘項目key值相同的鍵值對進行歸約處理， 并對其value值進行累加計算，形成與鍵值對相對應的‘支持頻度。如果在系統運行的過程中，用戶給定的支持頻度小于‘支持頻度，則系統就會輸出<‘項目（value），‘項目（key）>，當系統中所有的<‘支持頻度（value），‘項目（key）>都被輸出之后，就會形成1?項目的頻繁集合[L1。]在第二次執行MapReduce job的過程中，在Map任務階段，應該對所有項目進行篩選，只留下[L1]集合中的項目，并將其相對應的交易記錄信息保留在項目中，形成另一個項目集S和非空冪集P（S），并依照第一步中的處理方式對集中項目進行賦值，形成<‘冪集元素，1>鍵值對[8]。然后，在執行Reduce任務時，對‘冪集元素key值相同的鍵值對進行歸約處理， 并對其value值進行累加計算，形成與鍵值對相對應的‘支持頻度。如果在系統運行的過程中，用戶給定的支持頻度小于‘支持頻度，則系統就會輸出<‘項目（value），‘冪集元素（key）>，當系統中所有的<‘支持頻度（value），‘冪集元素（key）>都被輸出之后，就會形成1?項目的頻繁集合L。當L集合生成之后，就能夠生成并行關聯規則，用來支持數據挖掘系統的正常運行[9]。以上算法流程如圖1所示。

3.2 設計實現

（1） MapReduce job第一階段

該階段主要任務是通過執行計算獲得1?項目頻繁集合[L1，]該階段為AprioriPMR算法的第一步。在該階段，系統中的分布式文件系統HDFS會在執行Reduce任務的過程中，水平將D化為若干個數據塊，每一個數據塊的大小[10]皆為64M。在該階段，RecordReader接口主要依靠InputFormat實現，并且將所有數據塊進行歸約，格式化成<‘支持頻度（value），‘項目（key）>鍵值對[11]。在生產鍵值對之后，緊接著就會通過Map和Readuce操作來生產集合[L1。]

（2） MapReduce job第二階段

該階段主要任務是通過執行計算獲得1?項目頻繁集合L，該階段為AprioriPMR算法的主要階段，對形成并行關聯規則具有極為重要的影響作用[12]。該階段主要包括了AprioriPMR算法的第2步和第4步，其具體操作如圖2，圖3所示。

（3） 生成關聯規則階段

相對于前兩個階段而言，該階段比較簡單，主要針對[L]集合中的每一個元素，相對應地找出所有的非空真子集[s。]在找出每個非空真子集[s]之后，對其置信度進行詳細計算，以不小于置信度閾值為標準，生成關聯規則，并將其應用于數據挖掘系統中[13]。

4 結 語

隨著網絡全球化以及計算機網絡技術的深入普及，所生成的數據量越來越大，對于數據挖掘和挖掘算法的要求也越來越高。為了能夠有效解決該問題，提高對海量數據的挖掘效率，獲取更多具有利用價值的信息和知識，成為當前數據挖掘技術領域所面臨的主要問題。相關研究人員應該不斷加強對數據挖掘技術的研究和應用，并在基于云平臺的基礎上實現數據挖掘的云計算，進一步提升數據挖掘效率，為企業決策提供科學有效的參考依據，進一步提高企業的經濟效益。

參考文獻

[1] JIN R， YANG G， AGRAWAL G. Shared memory parallelization of data mining algorithms： techniques， programming interface， and performance [J]. IEEE Transactions on Knowledge and Data Engineering， 2004， 16（10）： 1?19.

[2] 陳沒，王慶波，何樂，等.云計算技術與實踐[M].北京：電子工業出版社，2011.

[3] 于楚禮.基于Hadoop的并行關聯規則算法研究[D].天津：天津理工大學，2011.

[4] YANG Xin?yue， LIU Zhen， FU Yan. MapReduce as a programming model for association rules algorithm on Hadoop [C]// 2010 3rd International Conference on Information Sciences and Interaction Sciences （ICIS）. Chengdu： IEEE， 2010： 99?102.

[5] 陳燕.數據挖掘技術與應用[M].北京：清華大學出版社，2011.

[6] 王智鋼，王池社，馬青霞.分布式并行關聯規則挖掘算法研究[J].計算機應用與軟件，2013（10）：113?115.

[7] 楊宸鑄.基于Hadoop的數據挖掘研究[D].重慶：重慶大學，2010.

[8] 侯建，帥仁俊，侯文.基于云計算的關聯規則挖掘算法[J].化工自動化及儀表，2011（5）：579?581.

[9] 郝延靜.云存儲系統日志關聯規則挖掘研究[D].西安：西安電子科技大學，2014.

[10] 劉世平.數據挖掘技術及應用[M].北京：高等教育出版社，2010.

[11] 韓秋明，李微，李華鋒，等.數據挖掘技術與應用實例[M].北京：機械工業出版社，2009.

[12] SHVACHKO K， KUANG H， RADIA S， et al. The Hadoop distributed file system [C]// 2010 IEEE/NASA Conference on Mass Storage Systems and Technologies. Incline Village： IEEE， 2010： 1?10.

[13] 車斌.基于Hadoop海量數據處理關鍵技術研究[D].成都：電子科技大學，2013.