現在、世界中で注目を集めているビッグデータ分析基盤技術Apache Sparkの機能を紹介します。今回は、マーケティングなどでよく使われるデータマイニング手法のうち、最近Sparkで実装された頻出系列パターンマイニングアルゴリズムPrefixSpanを中心に解説します。
デキるマーケッターは知っている！頻出系列パターンマイニング
今やマーケティングにおいて欠かすことのできなくなったビッグデータ。そのビッグデータが語られる文脈で、データマイニングに関する手法も多く見られるようになってきました。
では、データマイニングとはどういったものなのでしょうか。
Wikipediaによりますと、データマイニングとは、
「データの巨大集合やデータベースから有用な情報を抽出する技術体系」
とあります。大量にある情報の中から有益な情報を見つけ出す―「掘り出す」ことがデータマイニングと言えます。
参考：Wikipedia
特に、
- POSデータなどの購買ログデータ
- Webページへのアクセスログデータ
などから、一定頻度以上で出現するパターンを抽出することが、マーケティングにおいても非常に有益となるため、注目を集めている技術です。
例えば、「ある商品Aと一緒によく買われる商品は何か？」という分析は、全購買履歴データから、商品Aと一緒に買われた商品の購買パターンの個数をカウントすることで求めることができます。
ここでは、データマイニングの有名な事例「おむつとビール※」を例に解説したいと思います。
※仕事の合間に!3分間データマイニング入門 第1回
上の例では、POSデータからビールとおむつを一緒に買う頻度を求めることで、ビールとおむつがいっしょに買われやすいといった分析ができます。
このように、データから、ある一定頻度以上出現するアイテムパターンを抽出することは、データマイニングの主な目的の1つで、頻出パターンマイニングと呼ばれています。
上記のバスケット分析では商品アイテムの購買パターンだけを考慮して、商品アイテムの順序は区別する必要がありませんでした。
しかし、時系列データのようにアイテムに順序があって、その順序関係を考慮した頻出パターンを抽出することも応用上重要となります。これは、頻出系列パターンマイニングと呼ばれています。
頻出系列パターンマイニングの適用例を1つ紹介しましょう。
下の文集合は、ウェブページから抽出した“嵐”を含む文の単語列の集合の一部ですが※、
※N-gram コーパス – 日本語ウェブコーパス 2010
これらの単語列には、“嵐”の後に“コンサート”という単語が6回出現していることがわかります。そこで、テキストデータから“嵐” – “コンサート”のようなある一定数以上出現する単語の系列パターンをすべて抽出することが、頻出系列パターンマイニングの適用例になります。
上の例からわかるように、頻出系列パターンマイニングによって抽出された単語系列パターンにより、単語の用法や、単語間の意味的つながりを分析できるようになります。
D2Cの広告事業への応用例では、例えば大量の検索クエリーログから、ある一定頻度以上出現するキーワードの系列パターンを抽出することで、フレーズ一致キーワードにも対応した広告用のキーワードの推定やパフォーマンス予測に応用するなどを考えています。
この頻出系列パターンマイニングアルゴリズムの1つが今回紹介するPrefixSpanです。
Spark MLlib PrefixSpanが実現するビッグデータの高速処理
PrefixSpanアルゴリズムは、深さ優先、再帰的に頻出系列パターンを抽出するのが特徴の手法で※、オープンソース実装もいくつか公開されています※※。
※J.Pei, J.Han, B.Mortazavi-Asl, H.Pinto, Q.Chen, U.Dayal, and M.-C. Hsu, “PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth”, Proc. of The 17th Int’l Conf. on Data Engineering, pp.215-224 (2001)
※※PrefixSpan
公開されているPrefixSpan実装はデータをオンメモリーで処理するため、ある程度以上の大規模データから頻出パターンを抽出させることが困難でした。
このPrefixSpanを分散処理で大規模データにも対応させようと実装されたのが、Spark MLlibのPrefixSpan実装です。Spark MLlib PrefixSpanは系列パターン抽出を複数のサーバー上で分散処理によって実行します。分散処理により数千万件以上の大規模データからでも頻出系列パターンを抽出できるように実装されているのが特長です。
今回は、このことを確認するために、ベンチマークとして1000万件の連続キーワードデータから頻出するキーワードパターンを抽出するタスクをこのSpark MLlib PrefixSpanに実行させました。
使ったデータは日本語Webページを対象にN-gram コーパスのデータ1000万件です。先ほど例として示した、“嵐” – “コンサート”の系列パターンを抽出した文集合はこのデータの一部になります。
ベンチマークの結果、master1台、worker7台、計8台のSparkサーバー上でPrefixSpanを実行させ、1000万件データから頻出パターンを即時に抽出できることを確認しました。
頻度1万件以上の系列パターン抽出は約4分で実行でき、頻度1000件以上のパターン抽出も30分程度で実行できました。詳細は「Spark mllibのPrefixSpan実装」を参照してください。
PrefixSpanのように深さ優先で再帰的に処理するアルゴリズムは分散処理させづらいと考えていました。しかし、Spark上で実装されたPrefixSpanは効率的に並列分散処理できるように実装されており、D2Cの大規模データに対しても応用できる見込みを得られました。今後は、D2CサービスのログにSpark MLlib PrefixSpanを適用して各種サービスに有益な情報を抽出する計画を検討中です。
Apache Sparkの広告ログデータ活用に向けて
今回はSparkのデータマイニングアルゴリズム実装の1つPrefixSpanの紹介をしました。このPrefixSpanが1000万件の大規模データから頻出単語パターン抽出を実時間でできることも紹介しました。
SparkにはPrefixSpan以外にも下記データマイニングアルゴリズム、
- FP-Growth
- Association Rules
を同梱していて、大規模データからデータマイニング、頻出パターンマイニングを実行できます。今回はPrefixSpanのみの紹介に留まりましたが、これらのアルゴリズムもD2Cの広告ログデータに活用していきたいと考えています。
現在、D2Cでは、このApache Sparkベースのテキストマイニング、データマイニング技術をサービスに適用し始めています。これらの成果につきましても今後、紹介できればと考えています。
