第一章 緒論

1.1 課題研究背景與意義

隨著信息化時代的發(fā)展，人類的社會生產(chǎn)活動產(chǎn)生了大量有用的數(shù)據(jù)，尤其是隨著數(shù)據(jù)庫的發(fā)展和互聯(lián)網(wǎng)時代的到來，導(dǎo)致了海量數(shù)據(jù)的產(chǎn)生。在這些海量數(shù)據(jù)里，隱含著有價值或有潛力的信息�？焖俚貜倪@些海量數(shù)據(jù)中提取有用的信息，以輔助上層決策，對國家和企業(yè)來說，都是很有意義的。有了這些信息，決策者們再也不用像以前那樣光靠經(jīng)驗來做決策，而是多了一個可靠的參考信息。所以，如何有效地充分利用這些數(shù)據(jù)，就成了國家和企業(yè)決策者們迫切關(guān)心的問題。在這樣的大背景下，數(shù)據(jù)挖掘（Data Mining，DM）技術(shù)孕育而生，，有時也稱之為知識發(fā)現(xiàn)（Knowledge Discovery in Database，KDD）技術(shù)。由于各個領(lǐng)域都急需利用數(shù)據(jù)挖掘技術(shù)來處理數(shù)據(jù)，以此獲取數(shù)據(jù)中蘊含的知識和信息，所以數(shù)據(jù)挖掘技術(shù)得到了學(xué)術(shù)界和工業(yè)界的高度重視，并展開了廣泛而深入的研究，涌現(xiàn)出了大量優(yōu)秀的算法。

...............

1.2 國內(nèi)外研究現(xiàn)狀為了從已有的海量數(shù)據(jù)中提取有用的信息，數(shù)據(jù)挖掘技術(shù)孕育而生。關(guān)聯(lián)規(guī)則分析是數(shù)據(jù)挖掘任務(wù)中的一個子任務(wù)，其目的是從大量的數(shù)據(jù)中發(fā)現(xiàn)項之間有趣的關(guān)聯(lián)和相關(guān)關(guān)系，而頻繁項集挖掘是關(guān)聯(lián)規(guī)則分析中最為關(guān)鍵和耗時的一步。隨著研究的不斷深入，關(guān)聯(lián)規(guī)則分析技術(shù)已經(jīng)發(fā)展得相當成熟。數(shù)據(jù)挖掘（Data Mining，DM）[21]有時候也稱之為知識發(fā)現(xiàn)（KnowledgeDiscovery in Database，KDD）技術(shù)，它的一個簡單定義是：從數(shù)據(jù)庫中提取或“挖掘”知識。它興起于上世紀的 80 年代末，并在 90 年代獲得了重大發(fā)展。1989年，在第 11 屆國際人工智能聯(lián)合會議 IJCAI 上，首次舉辦了以數(shù)據(jù)庫知識發(fā)現(xiàn)為專題的討論。1995 年，在加拿大的蒙特利爾召開了首屆知識發(fā)現(xiàn)與數(shù)據(jù)挖掘國際學(xué)術(shù)會議（The ACM SIGKDD International Conference on KnowledgeDiscovery and Data Mining，SIGKDD’95），正式提出了數(shù)據(jù)挖掘的概念。

...............

第二章 相關(guān)技術(shù)分析

2.1 Spark

Spark 誕生于伯克利大學(xué)的 AMP 實驗室，它是當今大數(shù)據(jù)領(lǐng)域最為活躍、熱門和高效的大數(shù)據(jù)通用計算平臺，Apache Spark 官方對 Spark 的定義是：Spark是一個通用的大規(guī)模數(shù)據(jù)快速處理引擎[64]。因此，可以簡單地把 Spark 理解為是一個大數(shù)據(jù)分布式處理框架。Spark 是一個基于內(nèi)存計算的大規(guī)模數(shù)據(jù)快速處理引擎，因為它不具備管理計算任務(wù)的能力，所以 Spark 需要第三方資源管理平臺（如 YARN、Mesos）來調(diào)度和分配任務(wù)。從圖 2-1 可以看出，Spark 可與多種文件系統(tǒng)兼容，如 HDFS、Amazon S3 等。從某種意義上講，Spark 的出現(xiàn)并不是要消滅 Hadoop。相反，Spark充分利用了 HDFS 和 YARN，可以看作是為了彌補 Hadoop 的缺點而產(chǎn)生的。RDD（Resilient Distributed Datasets）是彈性分布式數(shù)據(jù)集的簡稱，它是分布式只讀且已分區(qū)的集合對象。這些對象是彈性的，即如果數(shù)據(jù)的某部分丟失，則還可以對它們進行重建，因此它具有自動容錯、位置感知調(diào)度和可伸縮性。圖 2-1 顯示的是 Spark 的體系結(jié)構(gòu)。

...............

2.2 頻繁項集挖掘算法

關(guān)聯(lián)規(guī)則挖掘的整個過程主要分兩步來完成：第一步是找出數(shù)據(jù)庫中所有滿足最小支持度閾值的頻繁項集；第二步是由頻繁項集產(chǎn)生所有滿足最小置信度閾值的關(guān)聯(lián)規(guī)則[1]。由于關(guān)聯(lián)規(guī)則挖掘的整體性能主要是由第一步的性能所決定，因此，關(guān)聯(lián)規(guī)則挖掘的關(guān)鍵和難點都集中在了頻繁項集的挖掘上。隨著關(guān)聯(lián)分析技術(shù)的不斷發(fā)展，眾多的研究學(xué)者提出了許多優(yōu)秀的頻繁項集挖掘算法，包括單機（single-machine）挖掘算法、基于 MPI（Message Passing Interface）的挖掘算法、基于 MapReduce 的挖掘算法和基于 Spark 的挖掘算法，接下來分別簡要介紹一些優(yōu)秀的頻繁項集挖掘算法。

...............

第三章 基于 Spark 的分布式頻繁項集挖掘算法...............19

3.1 FP-growth 算法 ................19

3.2 基于 Spark 的分布式頻繁項集挖掘算法設(shè)計................23

第四章 面向大規(guī)模 Spark 集群的 DFPS 優(yōu)化策略................31

4.1 面向大規(guī)模 Spark 集群的 DFPS 優(yōu)化策略概述................31

4.2 用戶自定義優(yōu)化策略..................32

第五章 實驗與分析.................39

5.1 實驗環(huán)境與數(shù)據(jù)集概述......................39

5.2 PFP 算法和 YAFIM 算法 ................40

第六章 DFPS 算法在項目中的應(yīng)用

6.1 項目概述

項目將主要基于 SAP 技術(shù)，搭建 SAP 技術(shù)大數(shù)據(jù)應(yīng)用平臺，做大數(shù)據(jù)技術(shù)的前瞻性研究和開發(fā)應(yīng)用。利用 SAP 技術(shù)，搭建從數(shù)據(jù)抽取、數(shù)據(jù)存儲到數(shù)據(jù)應(yīng)用的大數(shù)據(jù)技術(shù)平臺，對其中的技術(shù)點進行前瞻性研究，同時該技術(shù)平臺可以做為培訓(xùn)和學(xué)習(xí)的操作環(huán)境，具體包括：1）基于互聯(lián)網(wǎng)大數(shù)據(jù)的采集利用甲方現(xiàn)有產(chǎn)品萬網(wǎng)智能平臺，進行互聯(lián)網(wǎng)大數(shù)據(jù)的采集，對采集的數(shù)據(jù)進行處理和整合，做為后繼數(shù)據(jù)存儲和數(shù)據(jù)挖掘的數(shù)據(jù)集；2）HANA 和 Hadoop 的大數(shù)據(jù)多層存儲架構(gòu)搭建 HANA 和 Hadoop 的集成環(huán)境，實現(xiàn)大數(shù)據(jù)的分層存儲，滿足查詢性能和存儲空間的平衡需求；3）基于 SAP PA 的數(shù)據(jù)挖掘技術(shù)基于大數(shù)據(jù)的分層存儲，對加工好的數(shù)據(jù)進行數(shù)據(jù)挖掘技術(shù)的研究，包括預(yù)測、分類、社交網(wǎng)絡(luò)和推薦功能；4）基于 R 語言的數(shù)據(jù)挖掘技術(shù)集成 HANA 和 R 的環(huán)境，基于大數(shù)據(jù)以 R 語言進行數(shù)據(jù)挖掘的探究，實現(xiàn)SAP PA 同樣的功能，并對數(shù)據(jù)挖掘結(jié)果進行比對分析。

...............

6.2 項目實施

在項目的實施階段，首先，根據(jù)項目的具體要求，設(shè)計出一個大數(shù)據(jù)研發(fā)平臺，實現(xiàn) HANA 和 Hadoop 的集成；然后，根據(jù)設(shè)計要求，搭建大數(shù)據(jù)平臺并集成 HANA/Hadoop 和 R 的環(huán)境；最后，基于 SAP PA 技術(shù)、R 語言和本文的研究算法——DFPS 算法，對淘寶的交易數(shù)據(jù)進行頻繁項集挖掘，得到頻繁地被客戶一起購買的商品組合。根據(jù)要求，我們需要設(shè)計一個 HANA 和 Hadoop 集成的方案，實現(xiàn)大數(shù)據(jù)的分層存儲，滿足查詢性能和存儲空間的平衡需求。最終，我們設(shè)計的方案是：結(jié)構(gòu)化數(shù)據(jù)存儲在 Hive 上，而非結(jié)構(gòu)化數(shù)據(jù)存儲在 HDFS 上，利用 Map Reduce計算框架，可以實現(xiàn)海量數(shù)據(jù)簡單的自定義分析邏輯；由于 Hadoop 所擅長的是批處理，對于迭代計算的問題則顯得力不從心，所以我們利用 Apache Spark 來彌補 Hadoop 的不足，實現(xiàn)非實時作業(yè)的分布式迭代計算；對于實時性要求較高的作業(yè)，則將這些作業(yè)移動到 HANA 中完成。通過 SAP HANA 和 Hadoop 的連接器，將 Hadoop 上的數(shù)據(jù)抽取到 HANA 中，并保存在原始表里，通過計算層得到的結(jié)果則存儲在結(jié)果表或分析視圖中。

...............

總結(jié)

隨著信息化時代的發(fā)展，人類逐步進入了大數(shù)據(jù)時代，在這些海量數(shù)據(jù)里，隱含著有價值或有潛力的信息�？焖俚貜倪@些海量數(shù)據(jù)中提取有用的信息，以輔助上層決策，對國家和企業(yè)來說，都是很有意義的。頻繁項集挖掘是數(shù)據(jù)挖掘研究領(lǐng)域中的一個重要課題，它是關(guān)聯(lián)規(guī)則、因果關(guān)系、相關(guān)性分析、情節(jié)片段、序列項集、局部周期性等許多數(shù)據(jù)挖掘任務(wù)的基礎(chǔ)。而目前已有的基于多處理器系統(tǒng)的并行頻繁項集挖掘算法，以及基于 Hadoop 等分布式集群的分布式頻繁項集挖掘算法，在面對海量數(shù)據(jù)的時候，表現(xiàn)得并不是很理想。因此，本文基于Apache Spark 計算引擎，設(shè)計了一個高效且具有良好可伸縮性的分布式頻繁項集挖掘算法——DFPS 算法，并針對它在面向大規(guī)模 Spark 集群的時候可能出現(xiàn)的并行度不高、沒有充分利用集群的計算能力，以及面對海量數(shù)據(jù)可能會出現(xiàn)棧溢出的問題，提出了兩種優(yōu)化 DFPS 算法的策略——用戶自定義優(yōu)化策略和集群自適應(yīng)優(yōu)化策略。

參考文獻（略）