基于云平臺(tái)的并行關(guān)聯(lián)規(guī)則挖掘算法分析

穆俊

摘 要： 自云計(jì)算技術(shù)出現(xiàn)之后，數(shù)據(jù)挖掘技術(shù)取得了突破性發(fā)展。數(shù)據(jù)挖掘系統(tǒng)不僅實(shí)現(xiàn)了低成本、高效率運(yùn)行，并且系統(tǒng)儲(chǔ)存空間和系統(tǒng)可擴(kuò)展性也在不斷擴(kuò)大，大大提高了數(shù)據(jù)挖掘效率。這里簡(jiǎn)要闡述了基于云平臺(tái)的并行關(guān)聯(lián)規(guī)則挖掘算法分析的研究意義，并對(duì)基于Hadoop的數(shù)據(jù)挖掘系統(tǒng)和數(shù)據(jù)算法設(shè)計(jì)進(jìn)行了詳細(xì)介紹。

關(guān)鍵詞： 數(shù)據(jù)挖掘； 關(guān)聯(lián)規(guī)則； 云平臺(tái)； Hadoop

中圖分類號(hào)： TN702?34； TP391 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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

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

1 數(shù)據(jù)挖掘

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

對(duì)于任何一個(gè)企業(yè)來說，如果能夠從海量數(shù)據(jù)中挖掘出有利用價(jià)值的信息，并能夠?qū)@些信息進(jìn)行有效分析和整理，就能夠?yàn)槠髽I(yè)的決策帶來強(qiáng)有力的支持，使企業(yè)決策變得更加合理和科學(xué)，進(jìn)而使企業(yè)在行業(yè)競(jìng)爭(zhēng)中占據(jù)有利地位，為企業(yè)謀取更大的經(jīng)濟(jì)效益，這對(duì)于推動(dòng)企業(yè)的快速、持續(xù)發(fā)展具有極為重要的影響作用。基于以上特點(diǎn)，越來越多的企業(yè)開始對(duì)數(shù)據(jù)挖掘技術(shù)引起足夠重視，并不斷對(duì)數(shù)據(jù)挖掘技術(shù)進(jìn)行研究和應(yīng)用。

數(shù)據(jù)挖掘包含的技術(shù)十分繁雜，其中，聚類分析技術(shù)、預(yù)測(cè)技術(shù)、數(shù)據(jù)計(jì)算技術(shù)、關(guān)聯(lián)規(guī)則技術(shù)、模糊邏輯技術(shù)、可視化技術(shù)、自動(dòng)化和智能化技術(shù)以及數(shù)據(jù)統(tǒng)計(jì)分析技術(shù)是最為重要的幾種技術(shù)，對(duì)整個(gè)數(shù)據(jù)挖掘技術(shù)具有比較重要的影響[4]。應(yīng)用數(shù)據(jù)挖掘系統(tǒng)對(duì)數(shù)據(jù)進(jìn)行挖掘的過程中，主要分為目標(biāo)業(yè)務(wù)確定、數(shù)據(jù)源選擇、收集數(shù)據(jù)、選擇數(shù)據(jù)、對(duì)數(shù)據(jù)質(zhì)量進(jìn)行檢查、對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)換以及對(duì)數(shù)據(jù)挖掘結(jié)果進(jìn)行分析等幾個(gè)流程，其中任何一個(gè)環(huán)節(jié)出現(xiàn)問題都會(huì)對(duì)整個(gè)數(shù)據(jù)挖掘的最終結(jié)果造成影響[5]。

2 基于Hadoop的數(shù)據(jù)挖掘系統(tǒng)

自20世紀(jì)80年代第一代數(shù)據(jù)挖掘系統(tǒng)誕生以來，數(shù)據(jù)挖掘系統(tǒng)歷經(jīng)五代發(fā)展，專家、學(xué)者一直在對(duì)數(shù)據(jù)挖掘系統(tǒng)進(jìn)行改進(jìn)和完善。

第一代數(shù)據(jù)挖掘系統(tǒng)是最為簡(jiǎn)單的一代系統(tǒng)，系統(tǒng)中僅包含了幾個(gè)數(shù)據(jù)挖掘算法，其不論是數(shù)據(jù)挖掘能力還是計(jì)算能力都比較有限。 第一代系統(tǒng)在對(duì)數(shù)據(jù)進(jìn)行挖掘的過程中，需要將數(shù)據(jù)輸入到系統(tǒng)中之后才能夠?qū)?shù)據(jù)進(jìn)行挖掘和計(jì)算，所以，系統(tǒng)中幾種算法也只適合應(yīng)用于向量數(shù)據(jù)的挖掘[6]。

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

第三代數(shù)據(jù)挖掘系統(tǒng)是在第二代數(shù)據(jù)挖掘系統(tǒng)之上進(jìn)行了進(jìn)一步升級(jí)和擴(kuò)展，并實(shí)現(xiàn)了數(shù)據(jù)挖掘的集成化和網(wǎng)絡(luò)化，進(jìn)一步提升了數(shù)據(jù)挖掘效率。與第二代數(shù)據(jù)挖掘系統(tǒng)相比，第三代數(shù)據(jù)挖掘系統(tǒng)已經(jīng)初步實(shí)現(xiàn)了數(shù)據(jù)挖掘的網(wǎng)絡(luò)化。

第四代數(shù)據(jù)挖掘系統(tǒng)在基于第三代系統(tǒng)網(wǎng)絡(luò)化的基礎(chǔ)上實(shí)現(xiàn)了一定移動(dòng)計(jì)算。在第四代數(shù)據(jù)挖掘系統(tǒng)中，可以對(duì)嵌入式系統(tǒng)、移動(dòng)系統(tǒng)以及一些分布式系統(tǒng)中的數(shù)據(jù)進(jìn)行挖掘和計(jì)算，實(shí)現(xiàn)了數(shù)據(jù)挖掘系統(tǒng)的移動(dòng)化和分布化。

第五代數(shù)據(jù)挖掘系統(tǒng)也就是基于云平臺(tái)的數(shù)據(jù)挖掘系統(tǒng)，系統(tǒng)中的算法為并行關(guān)聯(lián)規(guī)則挖掘算法，是當(dāng)前應(yīng)用最為廣泛，也是數(shù)據(jù)挖掘主要發(fā)展方向的數(shù)據(jù)挖掘系統(tǒng)[7]。該系統(tǒng)與前幾代數(shù)據(jù)挖掘系統(tǒng)相比，不僅更加方便、快捷、高效，并且具有成本低、儲(chǔ)存空間大以及擴(kuò)展性強(qiáng)等特點(diǎn)。

3 基于Hadoop的數(shù)據(jù)算法設(shè)計(jì)

3.1 數(shù)據(jù)流程

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

3.2 設(shè)計(jì)實(shí)現(xiàn)

（1） MapReduce job第一階段

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

（2） MapReduce job第二階段

該階段主要任務(wù)是通過執(zhí)行計(jì)算獲得1?項(xiàng)目頻繁集合L，該階段為AprioriPMR算法的主要階段，對(duì)形成并行關(guān)聯(lián)規(guī)則具有極為重要的影響作用[12]。該階段主要包括了AprioriPMR算法的第2步和第4步，其具體操作如圖2，圖3所示。

（3） 生成關(guān)聯(lián)規(guī)則階段

相對(duì)于前兩個(gè)階段而言，該階段比較簡(jiǎn)單，主要針對(duì)[L]集合中的每一個(gè)元素，相對(duì)應(yīng)地找出所有的非空真子集[s。]在找出每個(gè)非空真子集[s]之后，對(duì)其置信度進(jìn)行詳細(xì)計(jì)算，以不小于置信度閾值為標(biāo)準(zhǔn)，生成關(guān)聯(lián)規(guī)則，并將其應(yīng)用于數(shù)據(jù)挖掘系統(tǒng)中[13]。

4 結(jié) 語

隨著網(wǎng)絡(luò)全球化以及計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的深入普及，所生成的數(shù)據(jù)量越來越大，對(duì)于數(shù)據(jù)挖掘和挖掘算法的要求也越來越高。為了能夠有效解決該問題，提高對(duì)海量數(shù)據(jù)的挖掘效率，獲取更多具有利用價(jià)值的信息和知識(shí)，成為當(dāng)前數(shù)據(jù)挖掘技術(shù)領(lǐng)域所面臨的主要問題。相關(guān)研究人員應(yīng)該不斷加強(qiáng)對(duì)數(shù)據(jù)挖掘技術(shù)的研究和應(yīng)用，并在基于云平臺(tái)的基礎(chǔ)上實(shí)現(xiàn)數(shù)據(jù)挖掘的云計(jì)算，進(jìn)一步提升數(shù)據(jù)挖掘效率，為企業(yè)決策提供科學(xué)有效的參考依據(jù)，進(jìn)一步提高企業(yè)的經(jīng)濟(jì)效益。

參考文獻(xiàn)

[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] 陳沒，王慶波，何樂，等.云計(jì)算技術(shù)與實(shí)踐[M].北京：電子工業(yè)出版社，2011.

[3] 于楚禮.基于Hadoop的并行關(guān)聯(lián)規(guī)則算法研究[D].天津：天津理工大學(xué)，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] 陳燕.數(shù)據(jù)挖掘技術(shù)與應(yīng)用[M].北京：清華大學(xué)出版社，2011.

[6] 王智鋼，王池社，馬青霞.分布式并行關(guān)聯(lián)規(guī)則挖掘算法研究[J].計(jì)算機(jī)應(yīng)用與軟件，2013（10）：113?115.

[7] 楊宸鑄.基于Hadoop的數(shù)據(jù)挖掘研究[D].重慶：重慶大學(xué)，2010.

[8] 侯建，帥仁俊，侯文.基于云計(jì)算的關(guān)聯(lián)規(guī)則挖掘算法[J].化工自動(dòng)化及儀表，2011（5）：579?581.

[9] 郝延靜.云存儲(chǔ)系統(tǒng)日志關(guān)聯(lián)規(guī)則挖掘研究[D].西安：西安電子科技大學(xué)，2014.

[10] 劉世平.數(shù)據(jù)挖掘技術(shù)及應(yīng)用[M].北京：高等教育出版社，2010.

[11] 韓秋明，李微，李華鋒，等.數(shù)據(jù)挖掘技術(shù)與應(yīng)用實(shí)例[M].北京：機(jī)械工業(yè)出版社，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海量數(shù)據(jù)處理關(guān)鍵技術(shù)研究[D].成都：電子科技大學(xué)，2013.