基于數據挖掘的關聯規則挖掘并行算法

龔浩

摘要：數據挖掘是人工智能和數據庫領域研究的熱點問題。數據挖掘是指從數據庫中大量數據中隱藏出來的，揭示出之前未知價值的信息的非正常過程，數據挖掘是一種決策支持過程，主要以人工智能基礎、機械學習、模式、統計學、數據庫可視化、技術等為高度幫助自動化地挖掘出分析企業資料的歸納推理的潛在模式，減少決策者調整市場戰略、風險，是正確的決策。數據挖掘是通過各數據分析，從大量數據中找出其法則的技術，主要有數據準備、法則查找和法則標識三個步驟，數據挖掘將從相關數據源中提取需要的數據，并整合到數據挖掘所用的數據集。尋找法則通過某種方法找出數據集中包含的法則。法則標示是盡可能通過使用者可理解的方式（例如可視化）來找到的法則。數據挖掘的任務是相關分析、分類分析、理想分析、特別集團分析及變遷分析等。

關鍵詞：數據挖掘;關聯規則挖掘;并行算法;分析

1 關聯規則挖掘并行算法及問題說明

1.1簡介

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

關聯規則的挖掘一般分為兩步：一是從現有的數據庫中找到所有的頻繁項集，二是由頻繁項集產生強關聯規則。Apriori算法是常用的用于挖掘出數據關聯規則的算法，它用來找出數據值中頻繁出現的數據集合，找出這些集合的模式有助于我們做一些決策。比如在常見的超市購物數據集，或者電商的網購數據集中，如果我們找到了頻繁出現的數據集，那么對于超市，我們可以優化產品的位置擺放，對于電商，我們可以優化商品所在的倉庫位置，達到節約成本，增加經濟效益的目的。

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

1.2相關工作

并行計算經過多年的發展，其相關實際應用也已經在多個領域起到十分重要作用。傳統的串聯關聯規則算法面對日益指數增長的數據，其數據處理也變得十分困難。因為Apriori算法存在著大量的迭代，I/O負載很高，時間效率很低，因此在如今的大數據時代，利用并行化技術加以改進，是很多人研究的方向。

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

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

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

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

2總結

當數據集逐漸擴大，并行程序的運行時間增長速度明顯小于串行程序，并逐漸接近。

當數據集擴大到一定程度，并行程序的運行效果，會優于串行程序，這充分體現了并行程序的優越性。