Streaming k-means approximation - tsubosakaの日記
実家に帰省中，電車の中で読んでた論文の紹介。 概要 k-meansはクラスタリングテクニックとして非常に基本的な手法である。 しかし、k-meansでは全データに対してラベリングを複数回繰り返す必要があり、全データ点を保存する必要がある、そこでk-meansの出力であるk個のクラスタ中心をワンパスで見つける方法を提案する。 ここで得られるクラスタ中心は最適値と比較したときにO(log k)の近似となっている ストリームアルゴリズムについて 本論文で言っているStreamingの意味としては入力を前から見ていって、すべて保存しないアルゴリズムのことを言っている。いわゆるオンラインアルゴリズムのように入力が入ってくるたびに何かしらの結果が得られるわけではない。また，ストリームの長さは有限である事を仮定している。 k-meansとは k-meansとはデータ点 X = {x_1 , ... x_
Simple-9について解説 - tsubosakaの日記
前回に引き続き転置インデックスの圧縮を実装してみる。今回紹介するのは[2]で提案されているSimple-9というアルゴリズムである。 Simple-9は32bitのwordにできるだけ数字を詰めていくという圧縮アルゴリズムである。例えば2bitの数が16個ならんでいれば32bitで表現できる。しかし、実際は大きい数字も出現するため数字の長さの情報も格納する必要がある。Simple-9では4bitを用いて残りの28bitがどう詰められているかを表す。 28bitの表し方としては 上位bit 符号の個数 符号のビット長 0000 28 1 0001 14 2 0010 9 3 0011 7 4 0100 5 5 0101 4 7 0110 3 9 0111 2 14 1000 1 28 の9通りがあり、これがSimple-9の名前の由来となっている。 例えば ( 3 , 5 , 0 , 0 ,
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
