Frequency Pattern Mining

Frequency Pattern Mining
Karubi Namuru
Nov. 14, 2010

自己紹介
● Karubi Namuru, Ph.D.
●
Kauli 株式会社
● Twitter: @karubi
● Facebook: http://facebook.com/karubi
●
出身：広島 , 居住：東京 , Seongnam

Frequency Pattern Mining
●
頻出パターンマイニング
●
データの集合から，出現頻度の高い特徴的なパ
ターンを発見する
●
→ 頻出パターンの抽出

代表的な頻出パターンマイニング
●
相関ルール抽出
●
たとえば，データベースに蓄積した大量のデータか
ら，頻繁に，かつ，同時に，発生する事象を見つけ
ること．
●
同時に発生する事象を，相関の強い関係としてルー
トとして抽出
●
バスケット分析
– POS データや EC などで取得できるトランザクションか
ら購買履歴を分析

バスケット分析
● 購買履歴から「一緒に買われる商品」という特徴的な
パターンを発見する
● 併売商品の発見
– デジタルカメラと液晶を保護するためのシート
を購入する顧客は，メモリカードも一緒に買う
● 商品陳列レイアウト
– おむつを買う顧客は同時にビールも買うなら両
方の商材を近くに陳列しておく

どのように分析しているのか
デジタルカメラと液晶を保護するためのシートを購入する顧
客は，メモリカードも一緒に買う傾向がある
｛デジタルカメラ，液晶保護シート｝⇒｛メモリカード｝
｛ X ｝⇒｛ Y ｝

基本の手順
● 全アイテムから全てのルールを洗い出す
● 全アイテムからｋ個を選ぶ
● この全通りについて，意味のあるルールを見つける
● このアイテムの各々が前提にくるか，結論にくるか
で分け方が変わる
● 全アイテムが前提に集まる場合と，全アイテムが結
論に集まる場合はルールにならないので排除する

実際の計算方法
● m 種類のアイテムにおいて存在するルールの数
● たとえば 10 種類の場合，ルールの総数： 57000 弱
● 価値のあるルールの数：わずかな数
∑
k=2
m
a
b2
m
−2

アプリオリアルゴリズム
● 確信度，サポートという 2 つの指標を導入する
● それぞれ，最小確信度と，最小サポートのふたつを与える
● 確信度，サポートとも最小より大きいルールを発見する方法

FPGrowth アルゴリズム
● アプリオリアルゴリズムの効率を改善するアルゴリズム
● アプリオリアルゴリズムは頻出アイテムセットを抽出する必要
があったが， FPGrowth は FP-Tree という木構造にトランザ
クションを圧縮して， FP-Tree から頻出アイテムセットを抽出
する．
● FP-Growth は候補パターンを生成しないため，データセット
のスキャン回数を抑えることができる．つまり，アプリオリよ
り高速に頻出アイテムセットを抽出することができる．

サポート降順に　 {4,2,1,3,5,6}
{1,3,4}
{2,4,5}
{2,4,6}
4
2
1
3
5
6
root
4
1
3
2
5 6

● Conditional Pattern Base に分割
● 3 を含む集合
● 1 を含んで３を含まない集合
● ４を含んで，１と３を含まない集合
4
2
1
3
5
6
root
4
1
3
2
5 6

Mahout 0.4
●
FPGrowth に関しては，ほぼ変更なし
●
ソースは綺麗になってた

FPGrowth を動かす
●
Mahout を動く環境をつくる
●
Linux の場合
– Virtual Macine をつくる，たとえば CentOS
– Java のインストール，たとえば OpenJDK
– 環境変数を設定
– Mahout をダウンロードして，適当なディレクトリに置
く
– 環境変数を設定

データセット
●
ネット上の無料の資源を利用する
●
学術で使うもの
– だいたいデータの中身がよくわからない
– どういう事象を記録したかのみ説明
– 個々の値については，抽象化されてわからない．．．
●
見てわかりやすいデータ
– MovieLens

ネット上の情報源
●
公開されている明示的な情報源（一部）
●
The Netflix prize datasets
– Netflix ：アメリカのオンライン DVD レンタルサービス
– 1 億レコード以上
– 480,189 人が 17,770 タイトルについて評価
●
Grouplens Research
– ミネソタ大の研究チーム， MovieLens プロジェクト
– 10 万， 100 万， 1000 万レコードの 3 つのデータ
– 71,567 人が 10,681 タイトルについて評価（ 1000 万）

大まかな流れ
●
Ratings.dat から，各ユーザが高い評価を与えて
いるデータのみを抜き出す
●
各ユーザの高い評価を与えた組み合わせから，
頻出するパターンを抽出する

処理済みデータの内容
●
データ形式
●
１行目
●
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,.... ：高い評価を与えた映画

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 で動かす）

結果を見る方法
●
ダンパーを利用する
./mahout seqdumper –seqFile
patterns/fpgrowth/part-r-00000

処理速度
●
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

FPGrowth の応用分野
●
チェスの，勝つゲームもしくは負けるゲームに
おいて頻出する打ち方の分析
●
ウェブページの閲覧内容の分析
●
よくクリックされるニュースの分析
●
ポータルサイトで併用されているコンテンツ
●
クリックされたオンライン広告の分析
●
コンテンツ属性とオーディエンス属性
●
交通事故の発生する状況の分析

Frequency Pattern Mining

Recommended

Recommended

More Related Content

Viewers also liked

Viewers also liked (20)

Frequency Pattern Mining