たつをの ChangeLog : 2010-05-12

1行1ラベル形式で、
1万種類のラベルを持つ、
100万行のデータがあるとします
（ラベルの頻度分布はジップの法則にだいたい準拠するとします）。

各ラベルの頻度をハッシュを使ってカウントするとなると、ハッシュエントリ1万個分のメモリ容量が必要になります。（1万じゃたいしたことないな、という人はもっと大きな数に置き換えて読んでください。）

しかし、カウント後に高頻度のものしか使わないということも多いと思います。例えば頻度5000以上のもののみ取り出してあとはいらない、とか。

そうなると、全部のラベルのカウントデータを最後まで保持するのは無駄に思えます。

そこで登場するのが「誤り許容カウント法(lossy count method)」。

低頻度のものを途中で適宜捨てていくことで必要なメモリ領域を小さくす
る方法なのです。
簡単に言うと、入力データをブロック単位に分け、各ブロックの読み込み後に低頻度のハッシュエントリを捨てる感じです。もちろん「現ブロックでは頻度ゼロだけど過去の実績があるから捨てない」などの要素もあります。

詳しくは「オンラインアルゴリズムとストリームアルゴリズム」[2010-05-11-1]の第6章をご参照ください。

■徳山豪 / オンラインアルゴリズムとストリームアルゴリズム (アルゴリズム・サイエンスシリーズ 5 数理技法編)


以下、サンプルプログラムで実演解説していきます。

サンプルデータ

まずは実演で使うサンプルデータを準備します。
1行1ラベル形式で、1万種類のラベルを持つ、100万行のデータで、ジップの法則に従うものを用意します。
先日の記事「ジップの法則に準拠した出現頻度を持つ要素のランダム順なリストを作成する」[2010-05-08-6]の zipf-gen.pl を使って生成します。

% ./zipf-gen.pl 10000 | head -1000000 > samp.txt
% head samp.txt 
32
2
105
3
33
586
1
1
924
247

単純カウント

まずは単純な方法でカウントしてみます。
全てをハッシュに入れてカウントする Perl プログラムです。

■コード(naive-freq.pl)：

#!/usr/bin/perl
use strict;
use warnings;
my $gamma = 0.005;
my %count;
my $N;

while (<>) {
    chomp;
    next if /^\s*$/;
    $count{$_}++;
    $N++;
}

foreach my $k (sort {$count{$b} <=> $count{$a}} keys %count) {
    last if $count{$k} < $gamma * $N;
    print "$k $count{$k}\n";
}

print "max hash size = ".scalar(keys %count)."\n";

■実行例

% ./naive-freq.pl samp.txt
1 102069
2 51389
3 33944
4 25432
5 20513
6 16856
7 14365
8 12780
9 11436
10 10353
11 9108
12 8528
13 8039
14 7259
15 6931
16 6377
17 6028
18 5704
19 5332
20 5050
21 5002
max hash size = 10000

出力フォーマットは、第1カラムがラベルで第2カラムがそのラベルの出現頻度です。
最後の "max hash size" はプログラム内で使用する最大ハッシュエントリ数で、実行時のメモリ使用量の目安となります。ラベルは1万種類なので当然10000になります。

LCMカウント

「誤り許容カウント法(lossy count method)」によるカウントプログラムです。
「オンラインアルゴリズムとストリームアルゴリズム」[2010-05-11-1]での記述の通りに Perl で実装したものです。

■コード(lcm-freq.pl)：

#!/usr/bin/perl
use strict;
use warnings;
my $gamma = 0.005;
my $epsilon = 0.004;
my $b_current = 1;
my %count;
my $N;
my $max_hash_size = 0;

while (<>) {
    chomp;
    next if /^\s*$/;
    add($_);
    $N++;
    if ($N % int(1/$epsilon) == 0) {
        next_backet();
    }
}

foreach my $k (sort {$count{$b}{f} <=> $count{$a}{f}} keys %count) {
    if ($count{$k}{f} >= ($gamma - $epsilon) * $N) {
        print "$k $count{$k}{f} $count{$k}{d}\n";
    }
}
print "max hash size = $max_hash_size\n";

sub add {
    my ($k) = @_;
    if (not $count{$k}) {
        $count{$k}{f} = 1;
        $count{$k}{d} = $b_current - 1;
    } else {
        $count{$k}{f}++;
    }
}

sub next_backet {
    my $hash_size = scalar(keys %count);
    $max_hash_size = $hash_size  if $max_hash_size < $hash_size;
    foreach my $k (keys %count) {
        if ($count{$k}{f} <= $b_current - $count{$k}{d}) {
            delete $count{$k};
        }
    }
    $b_current++;
}

■実行例

% ./lcm-freq.pl samp.txt
1 102069 0
2 51389 0
3 33944 0
4 25432 0
5 20513 0
6 16856 0
7 14365 0
8 12780 1
9 11436 0
10 10353 0
11 9108 0
12 8527 1
13 8039 0
14 7259 0
15 6929 4
16 6377 1
17 6027 1
18 5702 2
19 5327 5
20 5047 6
21 5002 0
22 4601 16
23 4379 11
24 3945 344
25 3632 421
max hash size = 203

出力フォーマットは、第1カラムがラベル、第2カラムがそのラベルの出現頻度、第3カラムがバケット番号($b_current)です。
バケット番号が0ではないやつは頻度に若干の誤差があるかもしれないことを意味します（番号が小さい場合は誤差はないです）。
誤差の許容範囲は $epsilon で調整します。
この辺は本を読んでください。

プログラム内で使用する最大ハッシュエントリ数 "max hash size" が 10000 と比べかなり小さくなっていることが分かります。
少ないメモリ容量で実行できるということです。

比較

最大ハッシュサイズの比較です。
前述の例では50倍ほどの差があります（実際は各ハッシュエントリが持つデータ量が違うのですがそれでも25倍の差）。
LCM の gamma、epsilon で調整できます。

	単純カウント	LCMカウント
最大ハッシュサイズ	10000	203

カウント結果の比較です。
LCM側でバケット番号が0じゃないものは太字にしています。

ラベル	頻度（単純カウント）	頻度（LCMカウント）
1	102069	102069
2	51389	51389
3	33944	33944
4	25432	25432
5	20513	20513
6	16856	16856
7	14365	14365
8	12780	12780
9	11436	11436
10	10353	10353
11	9108	9108
12	8528	8527
13	8039	8039
14	7259	7259
15	6931	6929
16	6377	6377
17	6028	6027
18	5704	5702
19	5332	5327
20	5050	5047
21	5002	5002

おわりに

巨大データを扱うとなると、「マシンが何台も必要！」とか「MapReduce で Hadoop がホゲホゲ！」とか「クラウドで5万円！」とかいろいろ心配になりがちです。
しかし、高頻度のものを取り出したいだけならば、貧弱なマシン環境でもなんとかなる場合があります。
ウェブサーバのログ解析もこういう高頻度チェック用途ならサクッと行けそうです。

贅沢なマシン環境の整備がなかなか難しい週末プログラマーやウェブベンチャーの方！
「誤り許容カウント法(lossy count method)」などのストリームアルゴリズムは要チェックですよ！

■徳山豪 / オンラインアルゴリズムとストリームアルゴリズム (アルゴリズム・サイエンスシリーズ 5 数理技法編)

(ref. [2010-05-11-1])

ref.
- lossy countingアルゴリズム (機械学習の「朱鷺の杜Wiki」)
http://ibisforest.org/index.php?lossy%20counting%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
- [O] イプシロン劣シノプス性を保持した頻度カウント
http://diary.overlasting.net/2010-04-23-3.html

今夜は自宅でハイボールでした。
うちでハイボールを作るときの材料は、角瓶とソーダと氷と冷凍レモン。
冷凍レモンってのは、妻が櫛形に切って冷凍しておいてくれるレモンで、それをジョッキに入れるだけでレモンの香りのハイボールがいつでも作れるのです。
ありがたいことです。

最近、レモン以外にライムも同じようにくし形に切って冷凍してくれています。
ライム水用（水にライムを一片入れて冷蔵庫で冷やすだけ）なのですが、今日はそれをハイボールに使ってみました。



ジントニック的な雰囲気になりました。
なかなかおいしいです！



でも、ライム入りの他のカクテルを連想しちゃうなあ。
ちょっと主張が強いのかも。
ときどきだと良いけど、毎日飲むならやっぱレモンかなあ。

なお角瓶はいつも冷凍庫で冷やしてトロ角（とろとろ状態）にするのですが、冷凍庫用の小ビンが空になったので大きい瓶から移しました。
我が家の風物詩です。

近所のフレッシュネスバーガー（恵比寿西店）では朝8時からモーニングセットがあるので、今朝はフレッシュモーニング！
恵比寿西店の店内で食べるのは初めて。



フレッシュネスバーガー 恵比寿西店 FRESHNESS BURGER
http://r.tabelog.com/tokyo/A1303/A130302/13108141/
場所：東京都渋谷区恵比寿西1-21-5 West21 1,2F

以前は恵比寿駅の東側に住んでいたので、恵比寿店を夜によく使っていたのですが、引越してからは行ってないなあ。恵比寿店は朝が遅いので通勤前に寄れなかったのです。

モーニングセット、ポップオーバーセット(390円)とホットドッグセット(490円)です。
ポップオーバーは固めの空のシュークリームみたいなやつでクリームつけて食べます。


2F は分煙で道路に面した窓側が喫煙席。
我々は（妊婦もいるので）いつも禁煙席を選ぶのですが、この日はたまたま喫煙席に誰もいなかったので、煙を気にせず窓際のカウンターで食べることができました。

窓からの景色：


窓側（喫煙席）から奥側（禁煙席）を望む：


奥側（禁煙席）から窓側（喫煙席）を望む。カウンターにいるのは妻：