連載
» 2009年05月01日 00時00分 公開

コーディングに役立つ! アルゴリズムの基本(10):レコメンデーションとエディットグラフ (1/4)

プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか(編集部)

[山下寛人,オイシックス株式会社]

実際のアプリケーションで使われるアルゴリズム

 これまで見てきたアルゴリズムは、実際のアプリケーション開発の際にそのまま使われることはあまりなく、プログラム言語やライブラリなどですでに機能が用意されているものが大半でした。

 今回は最終回ということで、実際のアプリケーション開発でそのまま使えるものを紹介したいと思います。

レコメンデーション

 ECサイトで、「あなたにお勧めの商品」を表示していることがあります。いろいろなデータベースや行動履歴のデータから、その人ごとにお勧めの商品をはじき出して推薦する機能をレコメンデーションと呼びます。有機野菜の安全食材宅配を行っているオイシックスでもメールマーケティングやWebサイトでさまざまなレコメンデーションを行っています。

 レコメンデーションの手法にもいろいろなものがあります。例えばAさんがいて、Aさんと好みが似ているBさんがいたとします。Bさんが好きな商品はAさんも好きな可能性が高いので、Aさんにレコメンドします。

 こういったレコメンデーションのアルゴリズムを協調フィルタリングといいます。代表的な実装例として、Amazon.co.jpの「この商品を買った人はこんな商品も買っています」というレコメンデーションがあります。

協調フィルタリングの実装

 では「この商品を買った人はこんな商品も買っています」というプログラムを実装してみましょう。ここまでアルゴリズムを学んできたみなさんには、このプログラムは簡単なものだと思います。

 表示部分や汎用関数は割愛してソースコードを解説します。実行可能なソースコードの全体をごらんになりたい場合は「全文を別ページで開く」のリンクをクリックしてください。

レコメンデーションのソースコード(一部)
[全文を別ページで開く]
 22 var shouhin = [
 23     "にんじん", "じゃがいも", "だいこん",
 24     "たまご", "牛乳", "チーズ",
 25     "砂糖", "塩", "酢", "しょうゆ", "味噌"
 26 ];
 27 
 28 
 29 var data =  [
 30     [0,2,3,5,9],
 31     [1,2,9,10],
 32     [0,4,5,8],
 33     [1,3,4,7],
 34     [1,0,4,5,8],
 35     [1,6,7,9],
 36     [3,5],
 37     [3,4,7],
 38     [1,2,7],
 39     [4,5,9,10],
 40     [2,6,9],
 41     [3,4,5],
 42     [1,7,10]
 43 ];
 
 73 function execRecommendation() {
 74     var shouhin_select = document.getElementById('shouhin_select');
 75     var shouhin_select_id = shouhin_select.selectedIndex;
 76 
 77     var relation = new Array(shouhin.length);
 78     for (var i = 0; i < relation.length; i++) {
 79         relation[i] = 0;
 80     }
 81 
 82     for (var i = 0; i  data.length; i++) {
 83         var shouhin_id = data[i];
 84         if (!shouhin_id.contains(shouhin_select_id)) { continue; }
 85         for (var j = 0; j < shouhin_id.length; j++) {
 86             if (shouhin_select_id == shouhin_id[j]) { continue; }
 87             relation[shouhin_id[j]]++;
 88         }
 89     }
 90 
 91     var max_shouhin_id = 0;
 92     var max_value = 0;
 93     for (var i = 0; i < relation.length; i++) {
 94         if (max_value < relation[i]) { 
 95             max_shouhin_id = i;
 96             max_value = relation[i];
 97         }
 98     }
 99 
100     var recommend = document.getElementById('recommend');
101     recommend.innerHTML = "おすすめ:" + shouhin[max_shouhin_id];
102 }
  • 22〜26行目
    商品の種類を定義しています。データベースアプリケーションの場合の商品マスタに相当する部分です。

  • 29〜43行目
    購買履歴のデータです。1行が1回の購入で、数値はshouhinのインデックスを表しています。

  • 74、75行目
    画面で選択された商品を取得しています。この商品を買った人がほかに買ったものをレコメンドします。

  • 77行目
    配列relationはほかに買ったものの個数を表す変数です。

  • 82〜89行目
    購買履歴から個数を集計します。shouhin_idは1回の購入で買った商品の組み合わせです。shouhin_idに選択した商品が含まれる場合に、ほかに買った商品の個数をカウントアップします。

  • 91〜98行目
    ほかに買ったものの中で、最も多かったものを抽出しています。

 レコメンデーションというと難しそうなイメージがあるかもしれませんが、プログラムはそれほど難しくありません。しかし、実際にこのシンプルなアルゴリズムではなかなかいい感じのレコメンデーションにはなりません。

 例えば、どんな商品を選んでも一番売れている商品がレコメンドされてしまうことがあります。それではレコメンデーションの意味がないので、総販売数が一定量以下のものだけに制限するなど、さまざまな工夫をします。

 また、こういったデータベースの分析をするとなかなか面白い結果が出ます。例えば、ビールと一緒に買っているものを調べると、枝豆やキムチなどが出てきます。機会があればやってみるとよいでしょう。

       1|2|3|4 次のページへ

Copyright © ITmedia, Inc. All Rights Reserved.

RSSについて

アイティメディアIDについて

メールマガジン登録

@ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。