たつをの 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カウント
最大ハッシュサイズ10000203

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

ラベル頻度(単純カウント)頻度(LCMカウント)
1102069102069
25138951389
33394433944
42543225432
52051320513
61685616856
71436514365
81278012780
91143611436
101035310353
1191089108
1285288527
1380398039
1472597259
1569316929
1663776377
1760286027
1857045702
1953325327
2050505047
2150025002

おわりに


巨大データを扱うとなると、「マシンが何台も必要!」とか「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

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

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

ライム

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

ハイボールなう!今日はレモンじゃなくライムです #highball

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

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

角瓶
この記事に言及しているこのブログ内の記事

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

フレッシュネスバーガー恵比寿西 フレッシュネスバーガー恵比寿西

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

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

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

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

窓からの景色:
フレッシュネスバーガー恵比寿西

窓側(喫煙席)から奥側(禁煙席)を望む:
フレッシュネスバーガー恵比寿西

奥側(禁煙席)から窓側(喫煙席)を望む。カウンターにいるのは妻:
フレッシュネスバーガー恵比寿西

たつをの ChangeLog
Powered by chalow