こんにちは。永野と申します。スパイシーソフトでは2年弱のあいだ、CGMの事業部でアプリ★ゲットおよびマンガ★ゲットのリニューアルと保守を担当していました。現在は弊社が次に出すソーシャルゲームのログ分析の開発を担当しております。最近はまっているソーシャルゲームはモバゲーの神撃のバハムートとGREEのドラゴンコレクション、聖戦ケルベロスです。(TVCMでおなじみEXILEのカードを無課金でコンプしました。)
前述の通り現在私はログ分析を担当しています。現段階ではまずKPI算出や、離脱ページ特定、プレイヤーさんの行動および状態(ステータスやゲーム内リソース)の追跡など、基本的かつ効果が高い部分に注力して実装しているのですが、その先の一手のためにデータマイニングの再勉強をしています。今回はその中から決定木の紹介をいたします。
決定木とは分類器の一種で、データの集合から法則(変数)を発見するために使用することができます。Wikipediaのゴルフ場の例が分かりやすいので、参照して下さい。
この例ではゴルフ場の天・気温・湿度・風のうち現在ゴルフをするかしないかを決める法則はまず天気がくもりの場合であること、続いて晴れなら湿度が低いこと・雨なら風が弱いことが条件だということが、イラストの木構造を見ると分かります。この木構造を機械学習で自動的に作成するのが決定木学習です。
このように、決定木には、機械学習で作成できる他のモデル(ニューラルネットワーク、サポートベクタマシンなど)と比較して以下の特徴があります。
・学習結果が人間にとって非常に分かりやすい木構造で出力されるため、直観的解釈がやりやすい。
ログ分析とはPDCAサイクルのCの部分ですから、Aにつながりやすい出力を出せる決定木が有効であると私は考えます。前掲Wikipediaのゴルフの例にもある通り、問題個所が分かるのでそのポイントの改善施策を打つことで(例えば不人気な天気の時には値引きをするなど) 売り上げをはじめとするKPIの改善につなげることができます。
実際にプログラムを示していきます。今回はプレイヤーさんの時間帯別プレイ履歴のうち、1日継続率(今日アクセスしたプレイヤーさんが翌日も遊んでくださるかどうか)に寄与する条件を発見する、というのを例にとります。(これはあくまで例で、極度に単純化していますし、以下で示すサンプルデータもすべて架空のものです。) 実装はPHPのCLIとします。(実際には統計解析にPHPは向きません。参考文献には以下のコードのもととなったPython版プログラムが掲載されています。)
まず学習もとのログデータは以下の形式で表現することとします。6時間ごとに割った時間帯別のプレイ履歴有無(1が有)と、翌日継続有無(1が継続)を1行で表現しています。
$my_data = array(
//1行が1プレイヤーの1日+翌日の行動に相当する
//それぞれ「03-09時の間に1度でもプレイしたか」「09-15時」「15-21時」「21-03時」「翌日継続したか」
array(1,0,0,0,1),
array(0,1,0,0,1),
array(1,0,0,0,0),
array(0,0,0,1,0),
array(0,1,0,1,1),
array(1,0,1,1,0),
array(0,0,0,1,0),
array(1,1,1,1,1),
array(0,1,0,0,1),
);次に、データの集合を指定番目のカラムの値に基づき2つに分割するための関数を定義します。この関数がくりかえし適用されることで、前述の$my_dataが木構造に分解されていきます。その際使用されたカラムと値が、それぞれ、Wikipediaの図でいう「天気?」-「晴れ」に相当します。
function divideset($rows, $column, $value) {
list($left, $right) = array(array(), array());
foreach ($rows as $row) {
if ($row[$column] === $value) {
array_push($left, $row);
} else {
array_push($right, $row);
}
}
return array($left, $right);
}続いて、データの特徴をよく表現するような「良い分割」を判定するための関数を作成します。「良い分割」とは、1回の分割でよりきれいに割れるということ、我々の例で具体的に言うと翌日継続したかどうかがよりはっきり分かれるような分割のことです。すなわち、データそれぞれの行の末尾のカラムができるだけ同じものが集まるような分割です。以下のuniquecounts関数は、引数のデータに、翌日継続の有無がそれぞれいくつずつあるかを返します。
function uniquecounts($rows) {
$results = array();
foreach ($rows as $row) {
$r = $row[count($row) -1];
if (! isset($results[$r])) {
$results[$r] = 0;
}
$results[$r] += 1;
}
return $results;
}分割の良さを判定するにはエントロピーを計算するのが有用です。エントロピーが少ないほど、翌日継続有無がばらけておらず、より均一であるということが判定できます。
function entropy($rows) {
$results = uniquecounts($rows);
$ent = 0.0;
foreach (array_keys($results) as $r) {
$p = (float)$results[$r] / count($rows);
$ent -= $p * log($p, 2);
}
return $ent;
}以上の関数を用いて再帰的に、総当たりで、最適な木構造を作成するのが以下の関数buildtreeです。戻り値の木構造は、枝(分岐するところ)は
array(
'col' => 分岐に使ったカラム番目,
'value' => 分岐に使った値,
'tb' => col番目がvalueに等しい分岐,
'fb' => col番目がvalueに等しくない分岐,
)葉(末端)は
array( 'results' => 翌日継続の有無がそれぞれいくつずつあるか )というデータ構造で返します。
function buildtree($rows) {
if (count($rows) < 1) {
return array();
}最後に、木構造を整形して表示する関数を定義し、buildtreeを呼び出して結果を表示させます。
function printtree($tree, $indent='') {
if (isset($tree['results'])) {
foreach ($tree['results'] as $r => $cnt) {
echo $r, '(', $cnt, ') ';
}
echo PHP_EOL;
return;
}
echo $tree['col'], ':', $tree['value'], '? ', PHP_EOL;
echo $indent, 'T->', printtree($tree['tb'], $indent . ' ');
echo $indent, 'F->', printtree($tree['fb'], $indent . ' ');
}
printtree(buildtree($my_data));実行します。
$ php dectree.php
1:0?
T->3:0?
T->1(1) 0(1)
F->0(3)
F->1(4)この結果を解釈してみます。
1. 09-15時にプレイした人は翌日継続している。 2. それ以外では、21-03時にプレイした人は継続していない。
1.より09-15時に打っている施策が継続率に効果が高いのではないか、という仮説が立てられます(昼食時間帯のみ1回追加で無料ガチャが引ける、など)。対して2.より21-03時には何らかの問題があることが推測されます(サーバ負荷が高い、など)。
よって21-03時の問題を解決し、可能なら09-15時と同等のインセンティヴを付与する(ゲームバランスを破壊しない範囲で)ことが継続率改善に効果的であり、また広告は昼にうつのがよい、などと次のアクションにつなげることができます。
以上決定木とはどういうものか、どのように学習させるのかを簡略化した例で示しました。実際には継続率にはもっとたくさんの変数が寄与していますし(今回の例で言えば$my_dataの各行のカラムが増えて横に大きくなるイメージ)、多数のデータも得られますから(同、縦に長くなるイメージ) 計算量も大きくなり、得られる結果もこれほど直観的なものではなくなっていきます。
冒頭にも述べましたとおりまずは基本的で効果の高い集計に注力し、プレイヤーの皆さんにおもしろいと思っていただけるゲーム作りに寄与してまいります。
参考文献
Toby Segaran 著 當山 仁健, 鴨澤 眞夫 訳 『集合知プログラミング』 オライリー・ジャパン. pp.155-165 (2008)