基于數(shù)據(jù)挖掘的關(guān)聯(lián)規(guī)則挖掘并行算法

龔浩

摘要：數(shù)據(jù)挖掘是人工智能和數(shù)據(jù)庫領(lǐng)域研究的熱點(diǎn)問題。數(shù)據(jù)挖掘是指從數(shù)據(jù)庫中大量數(shù)據(jù)中隱藏出來的，揭示出之前未知價值的信息的非正常過程，數(shù)據(jù)挖掘是一種決策支持過程，主要以人工智能基礎(chǔ)、機(jī)械學(xué)習(xí)、模式、統(tǒng)計學(xué)、數(shù)據(jù)庫可視化、技術(shù)等為高度幫助自動化地挖掘出分析企業(yè)資料的歸納推理的潛在模式，減少決策者調(diào)整市場戰(zhàn)略、風(fēng)險，是正確的決策。數(shù)據(jù)挖掘是通過各數(shù)據(jù)分析，從大量數(shù)據(jù)中找出其法則的技術(shù)，主要有數(shù)據(jù)準(zhǔn)備、法則查找和法則標(biāo)識三個步驟，數(shù)據(jù)挖掘?qū)南嚓P(guān)數(shù)據(jù)源中提取需要的數(shù)據(jù)，并整合到數(shù)據(jù)挖掘所用的數(shù)據(jù)集。尋找法則通過某種方法找出數(shù)據(jù)集中包含的法則。法則標(biāo)示是盡可能通過使用者可理解的方式（例如可視化）來找到的法則。數(shù)據(jù)挖掘的任務(wù)是相關(guān)分析、分類分析、理想分析、特別集團(tuán)分析及變遷分析等。

關(guān)鍵詞：數(shù)據(jù)挖掘;關(guān)聯(lián)規(guī)則挖掘;并行算法;分析

1 關(guān)聯(lián)規(guī)則挖掘并行算法及問題說明

1.1簡介

Apriori算法是常用的用于挖掘出數(shù)據(jù)關(guān)聯(lián)規(guī)則的算法，它用來找出數(shù)據(jù)值中頻繁出現(xiàn)的數(shù)據(jù)集合，找出這些集合的模式有助于我們做一些決策。比如在常關(guān)聯(lián)規(guī)則挖掘的目的是找出事物之間的隱藏的關(guān)系，比如經(jīng)典的案例啤酒和尿布的的故事，通過對購物數(shù)據(jù)進(jìn)行數(shù)據(jù)分析和挖掘，得到這樣一個結(jié)論，男性在買尿布的時候會買幾瓶啤酒。這二者并沒有什么因果關(guān)系，然而通過對海量數(shù)據(jù)進(jìn)行關(guān)聯(lián)分析，卻能夠發(fā)現(xiàn)這個有趣且有價值的關(guān)聯(lián)現(xiàn)象，通過對貨物的調(diào)整，就可以明顯的提升了超市啤酒和尿布的銷量。

關(guān)聯(lián)規(guī)則的挖掘一般分為兩步：一是從現(xiàn)有的數(shù)據(jù)庫中找到所有的頻繁項集，二是由頻繁項集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。Apriori算法是常用的用于挖掘出數(shù)據(jù)關(guān)聯(lián)規(guī)則的算法，它用來找出數(shù)據(jù)值中頻繁出現(xiàn)的數(shù)據(jù)集合，找出這些集合的模式有助于我們做一些決策。比如在常見的超市購物數(shù)據(jù)集，或者電商的網(wǎng)購數(shù)據(jù)集中，如果我們找到了頻繁出現(xiàn)的數(shù)據(jù)集，那么對于超市，我們可以優(yōu)化產(chǎn)品的位置擺放，對于電商，我們可以優(yōu)化商品所在的倉庫位置，達(dá)到節(jié)約成本，增加經(jīng)濟(jì)效益的目的。

隨著互聯(lián)網(wǎng)時代的深入發(fā)展，物聯(lián)網(wǎng)時代的來臨，生活中的數(shù)據(jù)以指數(shù)級增長，當(dāng)我們對這些數(shù)據(jù)進(jìn)行分析時，常用的串行算法無疑會消耗大量的時間，而且很可能得不到較好的結(jié)果。因此，并行計算概念的提出讓海量數(shù)據(jù)的處理成為了可能。如何對原有的傳統(tǒng)的串行關(guān)聯(lián)規(guī)則算法進(jìn)行并行化，成了我們需要解決的一個重要問題。

1.2相關(guān)工作

并行計算經(jīng)過多年的發(fā)展，其相關(guān)實(shí)際應(yīng)用也已經(jīng)在多個領(lǐng)域起到十分重要作用。傳統(tǒng)的串聯(lián)關(guān)聯(lián)規(guī)則算法面對日益指數(shù)增長的數(shù)據(jù)，其數(shù)據(jù)處理也變得十分困難。因?yàn)锳priori算法存在著大量的迭代，I/O負(fù)載很高，時間效率很低，因此在如今的大數(shù)據(jù)時代，利用并行化技術(shù)加以改進(jìn)，是很多人研究的方向。

許德心的研究方向，是Apriori算法的改進(jìn)及其在Spark平臺上的并行化方案，并且將并行化的Apriori算法應(yīng)用于醫(yī)療診斷場景中。他首先分析了大數(shù)據(jù)的相關(guān)技術(shù)、關(guān)聯(lián)規(guī)則算法、Hadoop計算框架、Spark計算框架。然后選擇被廣泛使用的Apriori算法加以改進(jìn)，他創(chuàng)新性的引入了興趣度，排除無價值的強(qiáng)關(guān)聯(lián)規(guī)則，提高了準(zhǔn)確性，其改進(jìn)算法在基于Spark平臺的分布式并行方案來提高效率。再搭建Spark平臺群環(huán)境，測試了Apriori算法和他改進(jìn)的算法在單機(jī)環(huán)境與集群環(huán)境下的實(shí)驗(yàn)，比較出了兩種算法的差異性，以及改進(jìn)算法在不同數(shù)據(jù)量下的處理速度和準(zhǔn)確性。最后，將算法應(yīng)用到醫(yī)療輔助場景中。

程陽的研究方向是，基于Hadoop大數(shù)據(jù)平臺對傳統(tǒng)的關(guān)聯(lián)規(guī)則算法進(jìn)行并行化。其主要工作是利用Hadoop生態(tài)系統(tǒng)對Apriori算法和Fp-Growth算法進(jìn)行改進(jìn)，最后實(shí)現(xiàn)并行化目標(biāo)，有效的解決了傳統(tǒng)算法中存在的缺陷，提高運(yùn)行的效率。他先對Hadoop生態(tài)進(jìn)行深入的研究和分析，然后分析了傳統(tǒng)算法存在的問題，針對這些問題，在基于Hadoop的生態(tài)環(huán)境下提出新的改進(jìn)算法。并對FP-Growth算法提出了兩種改進(jìn)策略——合并剪枝和動態(tài)分組策略，設(shè)計并實(shí)現(xiàn)了算法的并行化。最后在搭建的Hadoop集群環(huán)境中進(jìn)行試驗(yàn)對比，通過實(shí)驗(yàn)驗(yàn)證了改進(jìn)的Apriori算法在處理數(shù)據(jù)時的高效性，驗(yàn)證了改進(jìn)的FP-Growth算法在處理海量數(shù)據(jù)時的獨(dú)特優(yōu)勢。

王永貴，謝楠，曲海誠三人的研究方向是，針對現(xiàn)有算法存儲結(jié)構(gòu)簡單，生成大量冗余的候選集，時間和空間復(fù)雜度高，挖掘效率不理想的情況，為了進(jìn)一步提高關(guān)聯(lián)規(guī)則算法挖掘頻繁集的速度，優(yōu)化算法的執(zhí)行性能，提出基于內(nèi)存結(jié)構(gòu)改進(jìn)的關(guān)聯(lián)規(guī)則挖掘算法。其算法是基于Spark分布式框架，分區(qū)并行挖掘出頻繁集，提出在挖掘過程中利用布隆過濾器進(jìn)行項目存儲，并對事務(wù)集和候選集進(jìn)行精簡化操作，進(jìn)而達(dá)到加快挖掘頻繁集的速度，節(jié)省計算資源的目的。算法在占用較少內(nèi)存的條件下，相比于YAFIM和MR-Apriori算法，在挖掘頻繁集效率上有明顯的提升，不但能較好地提升挖掘速度，降低內(nèi)存的壓力，而且具有很好的可擴(kuò)展性，使得算法可以應(yīng)用到更大規(guī)模的數(shù)據(jù)集和集群，從而達(dá)到優(yōu)化算法性能的目的。

王誠，趙申屹的研究方向是，針對傳統(tǒng)的基于頻繁模式增長的并行關(guān)聯(lián)規(guī)則算法，消耗了大量時間和存儲空間，且沒有充分考慮頭表分組過程中組間負(fù)載量不同的問題。為了解決在關(guān)聯(lián)規(guī)則的實(shí)際挖掘過程中，數(shù)據(jù)集快速增長所造成的增量更新問題，基于并行頻繁模式增長PFP-tree算法，基于Spark分布式并行處理框架，提出一種改進(jìn)的并行關(guān)聯(lián)規(guī)則增量更新算法。在增量更新過程中，為了減少挖掘時間和存儲空間，利用已有挖掘結(jié)果對新增數(shù)據(jù)集構(gòu)建頻繁模式樹。通過改進(jìn)頭表分組策略，實(shí)現(xiàn)了并行挖掘節(jié)點(diǎn)之間的負(fù)載均衡。最后的實(shí)驗(yàn)分析表明，相較于傳統(tǒng)的關(guān)聯(lián)增量更新算法，該算法是可行的且具備較高的挖掘效率和可擴(kuò)展性，適用于動態(tài)增長的大數(shù)據(jù)環(huán)境。

2總結(jié)

當(dāng)數(shù)據(jù)集逐漸擴(kuò)大，并行程序的運(yùn)行時間增長速度明顯小于串行程序，并逐漸接近。

當(dāng)數(shù)據(jù)集擴(kuò)大到一定程度，并行程序的運(yùn)行效果，會優(yōu)于串行程序，這充分體現(xiàn)了并行程序的優(yōu)越性。