臺灣博碩士論文加值系統

關聯式資料探勘讓人們從不起眼的數據獲得有用的資訊。然而，現今數據的產量急速增加，對於探勘的演算法也需要有更好的資料處理能力。本論文針對PIETM (Principle of Inclusion-Exclusion and Transaction Mapping)關聯式資料探勘演算法提出完全平行化的方法來提升演算法運算能力，並且基於Hadoop MapReduce框架完成實作。PIETM演算法結合了Apriori與FP-growth兩演算法的優點，像是由下而上(Bottom-Up)的簡單搜尋方式以及整體探勘過程只需掃描兩次資料庫等優點。過去，有學者基於Hadoop MapReduce框架將PIETM平行化(簡稱BMR-PIETM)，不過仍有部分處理程序需要改進，例如：產生二階候選項目集、建立交易樹、降低交易區間表占用記憶體的空間。本研究以MapReduce框架及資料本身的結構特性提出了解決上述之問題的方法，特別是透過「間隔標籤(ITag)」將建立交易樹的過程平行化。另外也透過「間隔標籤(ITag)」將交易區間表的大小縮小。由於本研究完全的使用MapReduce框架將PIETM完全平行化，所以將此平行化之PIETM稱為Parallel-PIETM(簡稱P-PIETM)。本研究之解決方法，除了適用在Apriori演算法也適用在FP-growth演算法外，實驗結果顯示，P-PIETM演算法的效能可以比BMR-PIETM演算法以及Apriori演算法更好，效能提升最高可達66.17%。

We can get useful and valuable information from insignificant data through data mining and gain huge benefit from professional analysis. However, it is important to improve the performance of data mining for Big Data processing. The purpose of this study is to improve the performance of parallel association-rule mining algorithm of PIETM (Principle of Inclusion- Exclusion and Transaction Mapping) under the MapReduce framework. PIETM is arranging transaction data in database into a tree structure which is called Transaction tree (T-tree), and then transform T-tree into Transaction Interval tree (TI-tree). And use principle of Inclusion- Exclusion according to TI-tree to calculate all frequent itemsets. PIETM combines the benefits of Apriori and FP-growth algorithms and only needs to scan the database twice in data mining. However, we still need to improve some procedures, for example, construct a transaction tree and generate candidate k-item sets. For the two problems described above, we provide a solution respectively. These two solutions adopted the FP-growth and Apriori algorithms respectively.

【目次】

摘要 i
ABSTRACT ii
目次 iv
表目錄 vi
圖目錄 vii
第一章　緒論 1
第一節 研究背景 1
第二節 研究目的 2
第二章　相關研究 4
第一節 Hadoop 4
第二節 關聯規則 6
2-2-1 Apriori演算法 7
2-2-2 Frequent pattern growth演算法 9
2-2-3 PIETM演算法 14
2-2-4 BMR-PIETM演算法 18
第三章　研究方法 26
第一節 設計構想 26
第二節 平行化產生二階候選項目集 27
3-2-1 問題說明 27
3-2-2 方法描述 27
3-2-3 處理流程與程式設計說明 28
第三節 平行化建立交易樹及交易區間表 34
3-3-1 問題說明 34
3-3-2 方法描述 34
3-3-3 處理流程與機制設計 38
第四節 降低交易區間表在記憶體的佔用量 43
3-4-1 問題說明 43
3-4-2 方法描述 43
3-4-3 處理流程與機制設計 44
第四章　實驗結果 55
第一節 實驗環境 55
第二節 產生二階候選項目集之效能測試 55
第三節 建立交易區間表之效能測試 57
第四節 P-PIETM演算法與Apriori演算法之效能測試 61
4-4-1 在不同最小支持度下之效能測試 62
4-4-2 在不同資料長度下之效能測試 63
4-4-3 在不同交易項目量下之效能測試 64
4-4-4 在不同交易資料量下之效能測試 65
第五章　結論及未來工作方向 66
參考文獻 67
　
　
【表目錄】

表1　交易區間表示例 18
表2　原始交易資料庫資料內容 28
表3　平行化建立交易樹概念之交易資料內容 34
表4　剪枝作業後之交易資料內容 35
表5　交易樹樣式變化之交易區間比較表 36
表6　交易樹樣式變化之交易區間合併比較表 37
表7　交易樹平行化概念說明之交易區間表 38
表8　實驗環境詳細規格 55
表9　一階頻繁項目集之項目數量與資料量大小對照表 56
　
　
【圖目錄】
圖1　 hadoop架構 4
圖2 　MapReduce的執行流程 5
圖3 　MapReduce執行word count的過程 6
圖4　 Apriori演算法之虛擬碼 8
圖5　 Apriori演算法之範例介紹 8
圖6 　FP-growth演算法建構FP-tree之虛擬碼 10
圖7　 FP-growth演算法建構FP-tree之範例介紹 11
圖8 　FP-growth演算法探勘FP-tree之虛擬碼 12
圖9 　FP-growth演算法探勘FP-tree之範例介紹 13
圖10　PIETM演算法完整流程虛擬碼 14
圖11　PIETM演算法建構T-tree之虛擬碼 16
圖12　PIETM演算法建構T-tree之範例介紹 16
圖13　PIETM演算法建立交易區間之範例介紹 18
圖14　BMR-PIETM第一階段之Map class虛擬碼 19
圖15　BMR-PIETM第一階段之Reduce class虛擬碼 20
圖16　BMR-PIETM第一階段之流程圖 20
圖17　BMR-PIETM第二階段之Map class虛擬碼 22
圖18　BMR-PIETM第二階段之Reduce class虛擬碼 23
圖19　BMR-PIETM第二階段之流程圖 23
圖20　BMR-PIETM第三階段之Map class虛擬碼 24
圖21　BMR-PIETM第三階段之Reduce class虛擬碼 25
圖22　P-PIETM優化BMR-PIETM以實現PIETM平行化之示意圖 27
圖23　P-PIETM探勘一階頻繁項目集之流程圖 29
圖24　P-PIETM探勘一階頻繁項目集之Map class虛擬碼 29
圖25　P-PIETM探勘一階頻繁項目集之Reduce class虛擬碼 30
圖26　平行化產生二階候選項目集之流程圖 31
圖27　平行化產生二階候選項目之合併概念 31
圖28　平行化產生二階候選項目集的Map class虛擬碼 32
圖29　平行化產生二階候選項目集的Reduce class虛擬碼 33
圖30　平行化建立交易樹之概念說明圖之一 35
圖31　平行化建立交易樹之概念說明圖之二 36
圖32　平行化建立交易樹之概念說明圖之三 37
圖33　平行化建立交易樹之概念說明圖之四 38
圖34　平行化產生間隔標籤(ITag)之流程圖 39
圖35　平行化產生間隔標籤之Map class虛擬碼 40
圖36　平行化產生間隔標籤之Reduce class虛擬碼 41
圖37　平行化建立交易區間表之流程圖 41
圖38　平行化建立交易區間表之Map class虛擬碼 42
圖39　平行化建立交易區間表之Reduce class虛擬碼 42
圖40　尋找交易記錄中最頻繁項目及剪枝之流程圖 44
圖41　尋找交易記錄中最頻繁項目及剪枝之Map class虛擬碼45
圖42　統計各最頻繁項目出現次數之流程圖 46
圖43　統計各最頻繁項目出現次數之Map class虛擬碼 47
圖44　統計各最頻繁項目出現次數之Reduce class虛擬碼 48
圖45　最頻繁項目的排序及資料壓縮(一)之流程圖 49
圖46　最頻繁項目的排序及資料壓縮(一)之Map class虛擬碼50
圖47　最頻繁項目的排序及資料壓縮(一)之Reduce class虛擬碼50
圖48　最頻繁項目的排序及資料壓縮(二)之流程圖 51
圖49　最頻繁項目的排序及資料壓縮(二)之Map class虛擬碼52
圖50　最頻繁項目的排序及資料壓縮(二)之Reduce class虛擬碼53
圖51　交易區間表壓縮前後之結果概念圖 54
圖52　產生二階候選項目集之效能測試 56
圖53　建立交易區間表之執行時間比較圖 57
圖54　交易區間表壓縮前後之資料大小比較圖 58
圖55　BMR-PIETM與P-PIETM演算法的總執行時間比較圖 59
圖56　建立交易區間表的花費時間與second階段的時間反饋 60
圖57　建立交易區間表的花費時間與其他階段的時間反饋 61
圖58　不同最小支持度之執行時間比較圖 62
圖59　不同資料平均長度之執行時間比較圖 63
圖60　不同交易項目數量之執行時間比較圖 64
圖61　不同交易資料量之執行時間比較圖 65

[1]R. Agrawal and R. Srikant, &;quot;Fast Algorithm for Mining Association Rules in Large Database,&;quot; In Proceeding of the 20th International Conference on VLDB, Pages 487-499, 1994.
[2]S. Y. Chen, J. H. Li, K. C. Lin, H. M. Chen and T. S. Chen, &;quot;Using MapReduce Framework for Mining Association Rules&;quot;.
[3]J. Dean and S. Ghemawat, &;quot;MapReduce: Simplified Data Processing on Large Clusters,&;quot; in Communications of the ACM, Volume 51, Issue 1,Pages 107-113, 2008.
[4]S. Ghemawat, H. Gobioff. and S. T. Leung, “The Google File System,” in Proceedings of the nineteenth ACM symposium on Operating systems principles, Pages 29-43, 2003.
[5]J. Han, J. Pei and Y. Yin, &;quot;Mining Frequent Patterns without Candidate Generation,&;quot; Proceedings of the 2000 ACM SIGMOD international conference on Management of data, Pages 1-12, 2000.
[6]J. Han, J. Pei, Y. Yin, and R. Mao, &;quot;Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach,&;quot; in Data Mining Knowledge Discovery, Volume 8, Issue 1,Pages 53-83, 2004.
[7]K. F. Jea, M. Y. Chang, and K. C. Lin, &;quot; An Efficient and Flexible Algorithm for Online Mining of Large Itemset,&;quot; in Information Processing Letters, Volume 92, Issue 6, Pages 311-316, 2004.
[8]K. C. Lin, I. E. Liao, S. F. Lin, and T. P. Chang, &;quot;A Frequent Itemset Mining Algorithm based on the Principle of Inclusion-Exclusion and Transaction Mapping,&;quot; in Information Sciences, revised.
[9]C. L. Liu, Introduction to Combinatorial Mathematics,McGraw-Hill, New York, 1968.
[10]D. Zinn, S. Bowers, S. Köhler, and B. Ludäscher, &;quot;Parallelizing XML data-streaming workflows via MapReduce,&;quot; in Journal of Computer and System Sciences, Volume76, Pages 447-463, 2010.
[11]Han, Data Mining Concepts &; Techniques, 2007.
[12]T. White, &;quot;Hadoop: The Definitive Guide,&;quot; O&;apos;&;apos;Reilly Media, 2010.
[13]Apache hadoop. http://hadoop.apache.org
[14]Sorting_algorithm. https://en.wikipedia.org/wiki/Sorting_algorithm
[15]IBM Synthetic Data Generator, http://www.cs.nmsu.edu/~cgiannel/assoc_gen.html