Cicindelaに学ぶレコメンドエンジンの実装

Cicindelaとは

その昔、ライブドアがlivedoor Clipというソーシャルブックマークサービスを提供していました。livedoor Clipでは、今現在の国内スタンダードなはてなブックマークとは異なり、かなり初期の段階からレコメンデーションエンジンやコメント1000文字化や関連商品などの機能を搭載していました。

そのうちレコメンドエンジンに関する部分、「あなたにオススメのクリップ」「このページをクリップしたユーザーはこのページもクリップしています」は「Cicindela」として、livedoor Clipのデータセットと共にオープンソースで公開されました。livedoor Clipのデータセット提供はソーシャルブックマーク研究会に参加したときに「研究用にデータセットを公開してほしい」という研究者の要請を受けてのものです。

livedoor Clipのデータセットは、Clipのサービス廃止に伴って提供廃止になりましたが、Cicindela自体はオープンソースとしてGitHubで公開されています。（開発は継続されていませんが、現在はCicindela2）

Cicindelaの特徴

CicindelaはApache+Perl+MySQL環境で動作するレコメンドエンジンです。レコメンドの結果の取得にWEBインターフェースを使用しています。アプリケーション自体はPerlで書かれていますが、レコメンドの実際の処理自体はDB側で行っているのが特徴です。この記事ではネット上に多数記事が出ているCicindelaのインストール方法には立ち入らずに、公開当時あまり注目されていなかったCicindelaのDB構成とレコメンド処理の実装SQL部分について見ていこうと思います。

Cicindelaのデータベース構成

Cicindelaのデータベース構成は、 cicindela2/misc/cicindela.sqlに入っています。次のような構成です。

[mysql]create database $DB_NAME character set utf8;
use $DB_NAME;

drop table if exists last_processed;
create table last_processed (
    set_name varchar(128) primary key,
    last_processed timestamp
) engine = innodb;

drop table if exists picks;
create table picks (
    user_id int not null,
    item_id int not null,
    timestamp timestamp not null default CURRENT_TIMESTAMP,
    unique key (user_id, item_id),
    key (item_id),
    key (user_id, timestamp),
    key (timestamp)
) engine = innodb;

drop table if exists picks_buffer;
create table picks_buffer (
    id int not null auto_increment primary key,
    user_id int,
    user_char_id varchar(255),
    item_id int,
    item_char_id varchar(255),
    is_delete tinyint(1) not null default 0,
    timestamp timestamp not null default CURRENT_TIMESTAMP
) engine = innodb;

drop table if exists uninterested;
create table uninterested (
    user_id int not null,
    item_id int not null,
    timestamp timestamp not null default CURRENT_TIMESTAMP,
    unique key (user_id, item_id),
    key (item_id),
    key (user_id, timestamp),
    key (timestamp)
) engine = innodb;

drop table if exists uninterested_buffer;
create table uninterested_buffer (
    id int not null auto_increment primary key,
    user_id int,
    user_char_id varchar(255),
    item_id int,
    item_char_id varchar(255),
    is_delete tinyint(1) not null default 0,
    timestamp timestamp not null default CURRENT_TIMESTAMP
) engine = innodb;

drop table if exists user_id_char2int;
create table user_id_char2int (
    id int not null auto_increment primary key,
    char_id varchar(255) not null,
    timestamp timestamp not null default CURRENT_TIMESTAMP,
    unique key (char_id),
    key (timestamp)
) engine = innodb;

drop table if exists item_id_char2int;
create table item_id_char2int (
    id int not null auto_increment primary key,
    char_id varchar(255) not null,
    timestamp timestamp not null default CURRENT_TIMESTAMP,
    unique key (char_id),
    key (timestamp)
) engine = innodb;

drop table if exists ratings;
create table ratings (
    user_id int not null,
    item_id int not null,
    rating double,
    timestamp timestamp not null default CURRENT_TIMESTAMP,
    unique key (user_id, item_id),
    key (item_id),
    key (user_id, timestamp),
    key (timestamp)
) engine = innodb;

drop table if exists ratings_buffer;
create table ratings_buffer (
    id int not null auto_increment primary key,
    user_id int,
    user_char_id varchar(255),
    item_id int,
    item_char_id varchar(255),
    rating double,
    is_delete tinyint(1) not null default 0,
    timestamp timestamp not null default CURRENT_TIMESTAMP
) engine = innodb;


drop table if exists tagged_relations;
create table tagged_relations (
    tag_id int not null,
    user_id int not null,
    item_id int not null,
    timestamp timestamp not null default CURRENT_TIMESTAMP,
    key (user_id, item_id),
    key (item_id),
    key (tag_id)
) engine = innodb;

drop table if exists tagged_relations_buffer;
create table tagged_relations_buffer (
    id int not null auto_increment primary key,
    tag_id int not null,
    user_id int,
    user_char_id varchar(255),
    item_id int,
    item_char_id varchar(255),
    is_delete tinyint(1) not null default 0,
    timestamp timestamp not null default CURRENT_TIMESTAMP
) engine = innodb;

drop table if exists categories;
create table categories (
    id int not null auto_increment primary key,
    item_id int,
    category_id int,
    timestamp timestamp not null default CURRENT_TIMESTAMP,
    key(item_id),
    unique key(category_id, item_id)
) engine = innodb;

drop table if exists categories_buffer;
create table categories_buffer (
    id int not null auto_increment primary key,
    item_id int,
    item_char_id varchar(255),
    category_id int,
    is_delete tinyint(1) not null default 0,
    timestamp timestamp not null default CURRENT_TIMESTAMP
) engine = innodb;[/mysql]

_bufferとついているのは負荷が高い時に使用されるバッファ領域用のテーブルです。レーティングやカテゴリ関係のテーブルがあるのはClipの名残ですが、それ以外はユーザーとアイテムに関する非常にシンプルなテーブル構成になっています。

レコメンド計算処理

Cicindelaにおいては、レコメンドの計算はPerl側では行わず、Perlから発行されるSQL側で行っています。一部その処理を見てみましょう。下記はブックマークをしたか、しなかったか見たか見なかったかなどでアイテム間の類似度を集計している処理です。

sub in_table { shift->{in_table} || 'extracted_picks' }
sub in_table_iuf { shift->{in_table_iuf} || 'iuf' }
sub out_table { shift->{out_table} || 'item_similarities' }
sub out_table_online { shift->out_table . '_online' }

sub sqls {
    my $self = shift;

    return {
        'create_table' => q{
create table if not exists %$_current_table (
   item_id1 int not null,
   item_id2 int not null,
   score double,

   unique (item_id1, item_id2),
   key using hash (item_id1)
) engine = memory
},

        'cleanup' => q{truncate table %&out_table},

        'for_each_item_id' => q{
select distinct item_id from %&in_table
},

        'insert_item_similarities' => q{
insert into %&out_table (item_id1, item_id2, score)
select ?, items.item_id,
    (log(items.count) / ?)
%$_iuf_commentout  * coalesce(iuf.iuf, 1)
    score
  from
  (select r2.item_id item_id, count(*) count
    from %&in_table r1, %&in_table r2
    where r1.item_id = ?
      and r2.user_id = r1.user_id
      and r2.item_id != ?
    group by r2.item_id
    having count >= ?
  ) items
%$_iuf_commentout  left outer join %&in_table_iuf iuf on items.item_id = iuf.item_id
  order by %&order_by
  limit ?
},
    };
}

ここで作成されたテーブルは、以下のようなSQLでレコメンデーションの結果としてスコアを取得しています。

sub sqls {
    my $self = shift;

    return {
        %{$self->SUPER::sqls},

        'recommend_for_item_ex' => q{
select item_id2 item_id, score from %&in_table_ex
  where item_id1 = ?
    and item_id2 != ?
  order by score desc limit ?
},

        'recommend_for_user_ex' => qq{
select result.item_id, result.score
  from
  (select s.item_id2 item_id,
--      avg(s.score) score
      sum(s.score) score
    from  (select * from %&in_table_user where user_id = ? order by timestamp desc limit ?) r,
      %&in_table_ex s
    where s.item_id1 = r.item_id
    group by s.item_id2
  ) result
  %&_omit_uninterested
  order by result.score desc
  limit ?
},

    };
}

最終的にこの結果をレコメンドのランキングに落とし込むために以下のSQLを発行しています。

sub in_table { shift->{in_table} || 'item_similarities_online' }
sub in_table_user { shift->{in_table_user} || 'picks' }

sub sqls {
    my $self = shift;

    return {
        %{$self->SUPER::sqls},

        'recommend_for_item' => q{
select item_id2 item_id, score from %&in_table s
  where s.item_id1 = ?
    and s.item_id2 != ?
  order by score desc limit ?
},

        'recommend_for_user' => q{
select result.item_id, result.score
  from
  (select s.item_id2 item_id, %&scoring score
    from (select * from %&in_table_user u where u.user_id = ? order by u.timestamp desc limit ?) r,
      %&in_table s
    where s.item_id1 = r.item_id
    group by s.item_id2
  ) result
  %&_omit_uninterested
  order by result.score desc
  limit ?
},

    };
}

細かな整形処理はPerl側で行っていますが、メイン処理はSQLで実装されているのが理解できるかと思います。

レコメンドエンジンの近況

2008年当時はレコメンドの実装はDBを使っていましたが、今はRedisなどのKVSで作った方が速く表示できるでしょう。ただ、Cicindelaは今なおオープンソースとして公開されていますので、初学者がレコメンドの仕組みを学ぶにあたって参考になるのではないでしょうか。