Lossy Countingを実装してみた - 省メモリな頻度計測

大規模データで頻度を数えると、欲しいのはよく登場するアイテムの情報なのに、ほとんど出現しないアイテムの種類数が非常に多くて、それらがメモリを大量に必要としてしまうという問題がある

これに対してアイテムの種類数の最大値に制限を加えたり、頻度に誤差を許すなどの条件のもとで、省メモリに頻度計測を行う方法がいくつも提案されている
これらについては以下の記事が詳しい

• 大規模データで単語の数を数える - ny23の日記

今回はそういった手法の一つであるLossy Countingを実装した
日本語では上記の記事と以下の記事が詳しい

• [を] 誤り許容カウント法(lossy count method)のサンプルプログラム
• [O] イプシロン劣シノプス性を保持した頻度カウント
• lossy countingアルゴリズム - 機械学習の「朱鷺の杜Wiki」

元論文はこちら。年を見ると結構前なので、現在ではもっと効率的な方法がたくさんあるかと思いますが、この方法は実装が簡単です

• "Approximate Frequency Counts over Data Streams", Gurmeet Singh Manku and Rajeev Motwani, VLDB2002

以下のサーベイ論文を読むとLossy Countingの変種、誤差の大きさをアイテムごとに明示的に持つのをやめて、省メモリにする方法なども書いてありますが、今回は元論文の方法を実装しました

• "Methods for Finding Frequent Items in Data Streams", Graham Cormode and Marios Hadjieleftheriou

Lossy Countingの説明

簡単に説明すると、全体のアイテムの出現回数を\(N\)としたときに、それぞれのアイテムの頻度に\(\epsilon N\)の誤差を許して頻度を数える方法です。
ただし\(0 < \epsilon < 1\)
このアルゴリズムは、最大でも\(\frac{1}{\epsilon} \log(\epsilon N)\)のメモリしか使用しないらしい

アルゴリズムは簡単で、データを\(\frac{1}{\epsilon}\)個ずつのバケツに分けて処理していきます。
このバケツごとの境界で、頻度が一定の基準以下のアイテムについての情報を捨てることで、必要なメモリを削減しています

辞書を使ってアイテムを数えていくとすると、アルゴリズムは以下のようになります

• 各バケツについて
  • アイテムが
    • 辞書内に無ければ、頻度を1とし、そのアイテムが追加されたバケツ番号を記録しておく
    • すでに辞書内にあれば、頻度を+1する。
  • バケツの境界で、条件を満たさないアイテムのエントリーを辞書から削除する
    • 具体的には、アイテムの頻度 <= 現在のバケツ番号 - そのアイテムが追加されたバケツ番号 + 1の条件を満たすエントリーを削除
      • アイテムの頻度 + 誤差の最大値 が現在のバケツ番号よりも小さいエントリーを削除すると考えたほうがわかりやすい
• \(sN\)回以上出現したアイテムが欲しい時
  • 頻度\(f\)が\(f \geq (s - \epsilon)N\)の条件を満たすエントリーを返す
    • アイテムごとの追加された時のバケツ番号を使えば、誤差の最大値がわかって、もっと厳密に返せるような気がするのですが、上のようになっている理由はよくわかりません。私の理解が間違っているのかも

以下の記事にもアルゴリズムの説明が書いてあるのでこちらのほうがわかりやすいかもしれません
ただし、個人的には辞書内と同じアイテムが出現した時に頻度を+1するのと同時に、\(\Delta\)(アイテムが追加された時のバケツ番号)を書き換えているのが間違っているような気がします

• lossy countingアルゴリズム - 機械学習の「朱鷺の杜Wiki」

実行結果

ニコニコ動画のコメントデータ1000万件に対して実行した結果をいかに示します
MeCabで形態素解析した結果を使って、単語のbigram(連続した2つの単語のペア)の頻度を計測します
誤差の大きさの割合\(\epsilon=10^{-6}\)とします

形態素解析後の全アイテム数は\(100000000=10^8\)強程度あったので\(\epsilon=10^{-6}\)だと、最大でおよそ\(100\)強程度の誤差がそれぞれの単語の頻度についてあることがわかります

以下に上位10件の頻度の表を示します
バケツ番号 - 1は誤差の最大値を表しているので、上位についての誤差はたかだか7とほとんど誤差なく計測できていることがわかります

bigram	頻度	バケツ番号 - 1
うう/うう	9965548	0
/	6305996	0
悪霊/退散	5122435	0
退散/☆	3444928	0
☆/悪霊	3156555	0
ま/ん	2977881	0
徹子/！	1821991	0
G/G	1797460	0
！/徹子	1717485	7
ん/！	1580415	0

使用されているメモリ量を比較するため、辞書のアイテム数のグラフをかきました
ただしLossy Countingの方は単語とバケツ番号の2つの情報を記録しているので2倍しています(実装によっては2倍必要ないですが
軸を書き忘れましたが、縦軸が辞書内のアイテム数、横軸が処理したアイテム数です
最終的なLossy Countingの辞書内のアイテム数が30万強なのに対して、すべての要素を辞書に入れっぱなしにするナイーブな方法の方は280万以上と9倍程度の差となっています

まとめ

というわけで省メモリな頻度計測に使えるLossy Countingを実装しました
ソースコードは記事の一番下にあります

今回は元論文の方法を実装しましたが、アイテムごとのバケツ番号を持たない方法では更に省メモリになります
具体的には、アイテムとその頻度を数えておく辞書と現在のバケツ番号だけで処理でき、実装はさらに簡単になります(下の論文のAlgorithm 2)

• "Methods for Finding Frequent Items in Data Streams", Graham Cormode and Marios Hadjieleftheriou

追記: こちらの方法もコード書きました

参考にした記事によって微妙に記述が違っていて、理解が怪しい部分もあるので元論文や書籍を確認した方がいいかもしれません

参考

• 大規模データで単語の数を数える - ny23の日記
• [を] 誤り許容カウント法(lossy count method)のサンプルプログラム
• [O] イプシロン劣シノプス性を保持した頻度カウント
• lossy countingアルゴリズム - 機械学習の「朱鷺の杜Wiki」
• "Approximate Frequency Counts over Data Streams", Gurmeet Singh Manku and Rajeev Motwani, VLDB2002
• "Methods for Finding Frequent Items in Data Streams", Graham Cormode and Marios Hadjieleftheriou

ソースコード

Lossy CountingのPythonコードです
いちおうgithubにも上げておいたので、コードが間違ってたらプルリクエストなり、この記事にコメントを書くなりしていただけると嬉しいです。

Lossy Countingを行うクラスと簡単なサンプルがついています
サンプルは、aからiまでの文字がそれぞれ2のn乗倍の回数出現するデータに対して、およそ5の誤差を許して10回以上登場するものを列挙する
以下のような出力が得られます
一番左が文字の種類、真ん中が頻度、右がバケツ番号 - 1になります

c 6 3
d 16 0
e 32 0
f 64 0
g 128 0
h 256 0
i 512 0

class LossyCounting(object):
    def __init__(self, epsilon):
        self.N = 0
        self.count = {}
        self.bucketID = {}
        self.epsilon = epsilon
        self.b_current = 1
    
    def getCount(self, item):
        return self.count[item]
    
    def getBucketID(self, item):
        return self.bucketID[item]
    
    def trim(self):
        for item in self.count.keys():
            if self.count[item] <= self.b_current - self.bucketID[item]:
                del self.count[item]
                del self.bucketID[item]
        
    def addCount(self, item):
        self.N += 1
        if item in self.count:
            self.count[item] += 1
        else:
            self.count[item] = 1
            self.bucketID[item] = self.b_current - 1
        
        if self.N % int(1 / self.epsilon) == 0:
            self.trim()
            self.b_current += 1
    
    def iterateOverThresholdCount(self, threshold_count):
        assert threshold_count > self.epsilon * self.N, "too small threshold"
        
        self.trim()
        for item in self.count:
            if self.count[item] >= threshold_count - self.epsilon * self.N:
                yield (item, self.count[item])
    
    def iterateOverThresholdRate(self, threshold_rate):
        return self.iterateOverThresholdCount(threshold_rate * self.N)
    

if __name__ == '__main__':
    import random

    counter = LossyCounting(5e-3)

    stream = ''
    for i, c in enumerate('abcdefghi', 1):
        stream += c * 2 ** i
    stream = list(stream)
    random.shuffle(stream)

    for c in stream:
        counter.addCount(c)
    
    for item, count in sorted(counter.iterateOverThresholdCount(10), key=lambda x:x[1]):
        print item, count, counter.getBucketID(item)