近年來雲端運算技術的發展與電腦設備效能提升,使得以大量電腦主機以水
平擴充的方式組成叢集運算系統,成為一可行的選擇。Apache Hadoop 是Apache
基金會的一個開源軟體框架,它是由Google 公司的MapReduce 與Google 檔案
系統實作成的分布式系統,可以管理數千台以上的電腦群集。Hadoop 利用分散
式檔案系統HDFS 可以提供PB 級以上的資料存放空間,透過MapReduce 框架
可以將應用程式分割成小工作分散到叢集中的運算節點上執行。
此外,企業累積了巨量的資料,如何處理與分析這些結構化或者是非結構化
的資料成了現在熱門研究的議題。因此傳統的資料挖掘方式與演算法必須因應新
的雲端運算技術與分散式框架的概念,進行調整與改良,發展新的方法。
關聯規則是分析資料庫龐大的資料中,項目之間隱含的關聯,常見的應用為
購物籃分析。一般情形下會在特定的維度與特定的顆粒度範圍內挖掘關聯規則,
但這樣的方式無法找出更細微範圍下之規則,例如挖掘一個年度的交易資料無法
發現消費者在聖誕節為了慶祝而購買的商品項目間的規則,但若將時間限縮在
12 月份即可挖掘出這些規則。
Apriori 演算法是挖掘關聯規則的一個著名的演算法,透過產生候選項目集
合與使用自訂的最小支持度進行篩選,產生高頻項目集合,接著以最小信賴度篩
選獲得關聯規則的結果。若有k 種單一項目集合,則候選項目集合最多有2𝑘 − 1
個,計算高頻項目時則需反覆掃描整個資料庫,Apriori 這兩個主要步驟需要耗費
相當大量的運算能力。
因此本研究將資料庫分割成多個資料區塊挖掘關聯規則,再將結果逐步更新
的演算法,解決大範圍挖掘遺失關聯規則的問題,結合spark 分散式運算的架構
實作程式,在電腦群集上平行運算減少關聯規則的挖掘時間。 / Because of improving technique of cloud-computing and increasing capability of
computer equipment, it is feasible to use clusters of computers by horizon scalable a lot
of computers. Apache Hadoop is an open-source software of Apache. It allows the
management of cluster resource, a distributed storage system named Hadoop
Distributed File System (HDFS), and a parallel processing technique called
MapReduce.
Enterprises have accumulated a huge amount of data. It is a hot issue to process
and analyze these structured or unstructured data. Traditional methods and algorithms
of data mining must make adjustments and improvement to new cloud computing
technology and concept of decentralized framework.
Association rules is the relations of items from large database. In general, we find
association rules in fixed dimensions and granular database. However, it might loss
infrequent association rules.
Apriori algorithm is one famous algorithm of mining association rule. There are
two main steps in this algorithm spend a lot of computing resource. To generate
Candidate itemset has quantity 2𝑘 − 1, if there are k different item. Second step is to
find frequent, this step must compare all tractions in the database.
This approach divides database to segmentations and finds association rules of
these segmentations. Then, we combine rules of segmentations. It can solve the problem
of missing infrequent itemset. In addition, we implement this method in Spark and
reduce the time of computing.
Identifer | oai:union.ndltd.org:CHENGCHI/G0103356040 |
Creators | 林洸儂, Lin, Guang-Nung |
Publisher | 國立政治大學 |
Source Sets | National Chengchi University Libraries |
Language | 中文 |
Detected Language | English |
Type | text |
Rights | Copyright © nccu library on behalf of the copyright holders |
Page generated in 0.0013 seconds