第一章 緒論

1.1 課題研究背景與意義

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

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

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

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

第二章 相關技術分析

2.1 Spark

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

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

2.2 頻繁項集挖掘算法

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

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

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

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

3.2 基于 Spark 的分布式頻繁項集挖掘算法設計................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 算法在項目中的應用

6.1 項目概述

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

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

6.2 項目實施

在項目的實施階段，首先，根據(jù)項目的具體要求，設計出一個大數(shù)據(jù)研發(fā)平臺，實現(xiàn) HANA 和 Hadoop 的集成；然后，根據(jù)設計要求，搭建大數(shù)據(jù)平臺并集成 HANA/Hadoop 和 R 的環(huán)境；最后，基于 SAP PA 技術、R 語言和本文的研究算法——DFPS 算法，對淘寶的交易數(shù)據(jù)進行頻繁項集挖掘，得到頻繁地被客戶一起購買的商品組合。根據(jù)要求，我們需要設計一個 HANA 和 Hadoop 集成的方案，實現(xiàn)大數(shù)據(jù)的分層存儲，滿足查詢性能和存儲空間的平衡需求。最終，我們設計的方案是：結構化數(shù)據(jù)存儲在 Hive 上，而非結構化數(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 中，并保存在原始表里，通過計算層得到的結果則存儲在結果表或分析視圖中。

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

總結

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

參考文獻（略）