著者

岩橋 永悟

出版者

Waseda University

巻号頁・発行日

2005-02-02

---

データマイニング分野における頻出パターン抽出問題では,大規模なデータに対して処理を行うため,メモリ容量不足やディスクアクセス増加といった問題に直面する.このようなリソース面の制約を緩め,現実時間で頻出パターンを抽出するために,様々な並列化手法が提案されている.しかし,従来の並列化手法の多くは全ての頻出パターンを抽出するため,結果として莫大な数のパターンが抽出されてしまう.大規模なデータに対しても,ユーザにとって解析する負担が少ない,冗長性を軽減したパターンを高速に提示する並列化手法が必要である.そこで,本稿では,FPcloseに基づき頻出飽和パターンを並列抽出する手法を提案する.さらに,並列化において問題となる,タスク負荷の偏りを平坦化する手法を提案する.提案した手法をPCクラスタ上で実装し,評価を行った結果,最小サポートを2%と設定した場合,32PU投入時に30.9倍の速度向上を得た.

著者

岩橋 永悟 山名 早人

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告データベースシステム(DBS) (ISSN:09196072)

巻号頁・発行日

vol.2003, no.71, pp.327-334, 2003-07-16

---

データマイニング分野で重要な問題の一つに頻出パターン抽出問題がある。頻出パターン抽出手法では、多くの拡張手法を生んだAprioriが有名である。2000年になるとAprioriよりも高速な手法として、FP-growthが提案されたが、従来の並列化手法の多くは、依然としてAprioriに基づいている。本稿では、並列にディスクアクセスを行い、FP-treeをローカルに構築することによって、FP-growthを並列化する。本手法を32ノードクラスタ上で実験した結果、最小サポートを0.25%とした場合に約2倍の速度向上を得ることができた。また、最小サポートを2%とした場合、約130倍の速度向上を得ることができた。Frequent patterns mining is one of the important problem in data mining research. The Apriori is a prominent algorithm followed by many variants. In 2000, the FP-growth, which is reported to be faster than the Apriori, was proposed. However, many parallel algorithms of frequent pattern mining are still based on the Apriori. In this paper, we propose a parallelized version of the FP-growth, which accesses disks in parallel and constructs local FP-trees on each local memory. As a result of the evaluation using 32 node PC cluster, our method is approximately 2 and 130 times faster than sequential FP-growth, when minimum support is 0.25% and 2%, respectively.