Frequency Pattern Mining
- 1. Frequency Pattern Mining Karubi Namuru Nov. 14, 2010
- 2. 自己紹介 ● Karubi Namuru, Ph.D. ● Kauli 株式会社 ● Twitter: @karubi ● Facebook: http://facebook.com/karubi ● 出身：広島 , 居住：東京 , Seongnam
- 4. 代表的な頻出パターンマイニング ● 相関ルール抽出 ● たとえば，データベースに蓄積した大量のデータか ら，頻繁に，かつ，同時に，発生する事象を見つけ ること． ● 同時に発生する事象を，相関の強い関係としてルー トとして抽出 ● バスケット分析 – POS データや EC などで取得できるトランザクションか ら購買履歴を分析
- 5. バスケット分析 ● 購買履歴から「一緒に買われる商品」という特徴的な パターンを発見する ● 併売商品の発見 – デジタルカメラと液晶を保護するためのシート を購入する顧客は，メモリカードも一緒に買う ● 商品陳列レイアウト – おむつを買う顧客は同時にビールも買うなら両 方の商材を近くに陳列しておく
- 6. どのように分析しているのか デジタルカメラと液晶を保護するためのシートを購入する顧 客は，メモリカードも一緒に買う傾向がある ｛デジタルカメラ，液晶保護シート｝?｛メモリカード｝ ｛ X ｝?｛ Y ｝
- 7. 基本の手順 ● 全アイテムから全てのルールを洗い出す ● 全アイテムからｋ個を選ぶ ● この全通りについて，意味のあるルールを見つける ● このアイテムの各々が前提にくるか，結論にくるか で分け方が変わる ● 全アイテムが前提に集まる場合と，全アイテムが結 論に集まる場合はルールにならないので排除する
- 8. 実際の計算方法 ● m 種類のアイテムにおいて存在するルールの数 ● たとえば 10 種類の場合，ルールの総数： 57000 弱 ● 価値のあるルールの数：わずかな数 ∑ k=2 m a b2 m ?2
- 9. アプリオリアルゴリズム ● 確信度，サポートという 2 つの指標を導入する ● それぞれ，最小確信度と，最小サポートのふたつを与える ● 確信度，サポートとも最小より大きいルールを発見する方法
- 10. FPGrowth アルゴリズム ● アプリオリアルゴリズムの効率を改善するアルゴリズム ● アプリオリアルゴリズムは頻出アイテムセットを抽出する必要 があったが， FPGrowth は FP-Tree という木構造にトランザ クションを圧縮して， FP-Tree から頻出アイテムセットを抽出 する． ● FP-Growth は候補パターンを生成しないため，データセット のスキャン回数を抑えることができる．つまり，アプリオリよ り高速に頻出アイテムセットを抽出することができる．
- 12. FPGrowth アルゴリズム ● Conditional Pattern Base に分割 ● 3 を含む集合 ● 1 を含んで３を含まない集合 ● ４を含んで，１と３を含まない集合 4 2 1 3 5 6 root 4 1 3 2 5 6
- 14. FPGrowth を動かす ● Mahout を動く環境をつくる ● Linux の場合 – Virtual Macine をつくる，たとえば CentOS – Java のインストール，たとえば OpenJDK – 環境変数を設定 – Mahout をダウンロードして，適当なディレクトリに置 く – 環境変数を設定
- 15. データセット ● ネット上の無料の資源を利用する ● 学術で使うもの – だいたいデータの中身がよくわからない – どういう事象を記録したかのみ説明 – 個々の値については，抽象化されてわからない．．． ● 見てわかりやすいデータ – MovieLens
- 16. ネット上の情報源 ● 公開されている明示的な情報源（一部） ● The Netflix prize datasets – Netflix ：アメリカのオンライン DVD レンタルサービス – 1 億レコード以上 – 480,189 人が 17,770 タイトルについて評価 ● Grouplens Research – ミネソタ大の研究チーム， MovieLens プロジェクト – 10 万， 100 万， 1000 万レコードの 3 つのデータ – 71,567 人が 10,681 タイトルについて評価（ 1000 万）
- 18. ●
- 19. 処理済みデータの内容 ● データ形式 ● １行目 ● 122,185,231,292,316,329,355,356,362,364,370,377 ,420,466,480,520,539,586,588,589,594,616 ● → 1 行目のユーザ：ユニーク ID 「１」番の人 ● → 122,185,231,.... ：高い評価を与えた映画
- 20. 例のユーザ ● 122: Boomerang (1992), Comedy|Romance ● 185: Net, The (1995), Action|Crime|Thriller ● 231: Dumb & Dumber (1994), Comedy ● 292: Outbreak (1995), Action|Drama|Sci-Fi| Thriller ● 316: Stargate (1994), Action|Adventure|Sci-Fi ● 329: Star Trek: Generations (1994), Action| Adventure|Drama|Sci-Fi
- 21. Mahout FPGrowth ● コマンドラインで動かせる 1.Mahout をダウンロードしたディレクトリに移動 2.Bin ディレクトリの中に mahout バイナリがある 3.コマンドを打つ – ./mahout fpg -i /home/you/dir/data.dat -o patterns -k 50 -method mapreduce ↓ だいたいの意味 ./mahout (FPGrowth を動かす ) -i ( 解析対象ファイルの 場所 ) -o ( 出力を記録する場所） -k （ TopK ） -method （ Hadoop MapReduce で動かす）
- 22. 計算中の画面 ●
- 24. 処理速度 ● Junjie Hou, Chunping Li, "A Pattern Growth Method Based on Memory Indexing for Frequent Patterns Mining," cimca, vol. 1, pp.663-668, International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce Vol-1 (CIMCA-IAWTIC'05), 2005 0 10 20 30 40 50 60 70 80 90 100 0 0.5 1 1.5 2 2.5 3 Support threshold(%) Run time(sec.) D1 FP-grow th runtime D1 Apriori runtime sec
- 26. ● Thank you