Frequent Pattern-growthの略で、頻出アイテムセットを算出するアルゴリズムです。
アソシエーション分析で利用されます。
深さ優先型の探索で頻出アイテム集合を列挙、と言われていますが、
実感がわかないと思いますので、
終末に天国行きの人を選定するためにFP-Growthを使ったというケースで考えてみたいと思います。
場面1
選定人は下界のことがあまりわかっておらず、非常に多くの人を自分だけ判定することも難しいので、
天国行きの人を判定するにあたって、基準を設け、
天使達にその基準に見合う者を探してもらうこととしました。
選「どれだけ善い行いをしたのか、で判断する」
しかし、天国の選定人は下界のことがあまりわかっていませんでした。
彼らにわかるのは彼らが知っている数少ない善行に関しては
文句なしに、天国行きにしてもよいということだけでした。
ただ、その行いで判定すると天国行きの人はあまりにも少なくなってしまいます。
ということで
選「あきらかに天国行きと思える善行を行う人間は、他にもさまざま善行を行っているはずだ」
天使「善い行いを誰が行ったかのリストはございます。かなり雑多で大量のリスト数ではありますが」
選「ものにもよるが、善行は１回では意味がなく、ある程度の繰り返される必要がある」
天使「いかがしましょう」
選「まずは回数毎に調べて、回数の多い善行順のリストを作るのだ」
天使「行いの良し悪しや難易度などは考慮しなくてよろしいですね」
選「そうだ。そして次に、回数が多い善行同士の関連も形にしてもらう」
天使「はい。ある人間が善い行いをした場合に、他にどんな善い行いをするのか、ということですね」
選「人には時代や文化というものがあるので、いくつかのグループに分かれるだろう。そのグループ毎に善行を出していく」
場面2
天使が回数の多い善行順のリストを選定人にもってきました。
天使「上位3%ほどの善行順のリストをお持ちしました」
選「よし。そのリストにある善行は今後全て対象からはずすように」
天使「承知いたしました。善行の関連からもですね」
選「そうだ。回数が多いものは簡単にできる行いだった、という場合がほとんどだろうからな。もちろんそれ自体がマイナスということではないが」
天使「まことの善人であれば、他の善なる行いもやっていましょう」
選「下位20%も切り捨ててよい」
天使「得がたい奇跡もあるのではないでしょうか」
選「よいか。我々がやろうとしているのは、どんな行いが素晴らしいかのランクを付けることではない。ましてや素晴らしい行いをした人間に上から順位をつけていくことでもない。非常に多くの人間から天国行きにいける者、或いはそのグループを、効率的に選定することなのだ。得がたい奇跡を行った人間は残った善行もそれなりにやっているはずだ」
つづく(あと２回くらいで完結します)