別解出力をサポートした高速 k-means の C++ 実装を公開 - ny23の日記
二年ほど前，k-means をさらに速くする - ny23の日記 で書いた三角不等式を利用した高速 k-means の C++ 実装を公開した．以下の三つの論文を組み合わせた実装になっている．二年前の実装と比べると別解が出力できるようになったのが大きな違い． G. Hamerly. Making k-means even faster. (SDM 2010) D. Arthur and S. Vassilvitskii. k-means++: the advantages of careful seeding. (SODA 2007) [New] Y. Cui et al. Non-redundant multi-view clustering via orthogonalization. (ICDM, 2007) 前者二つを実装したのが二年前，別解出力をサポートしたのも一年以上前になる．
二進対数の高速計算を用いた単語クラスタリングの高速化 - ny23の日記
先日実装した単語クラスタリングでは，相互情報量を計算する際の対数計算がボトルネックとなっている．``Premature optimization is the root of all evil'' とは良く言ったものだが，これ以上コードを更新するつもりもなかったので，高価な演算（対数計算）を単純な演算に置き換える定番の最適化を行ってみた． 今回の高速化の対象は， float pmi (float p_ij, float p_i, float p_j) { return p_ij == 0 ? 0 : p_ij * log2 (p_ij / (p_i * p_j)); } という関数．この手の計算を高速化するには，可能な引数に対する結果を事前に計算した lookup table を用意するのが常套手段*1．lookup table を用いた対数計算の高速化手法は，以下の論文で提案されている．
k-means をさらに速くする - ny23の日記
昨日，今日と電車に乗っている時間が長かったので，暇つぶしに論文を読んでいた． Making k-means even faster (SDM 2010) この論文では，Elkan の三角不等式を用いた k-means の高速化手法 Using the triangle inequality to accelerate k-means (ICML 2003) のアイデアを元に，空間計算量を悪化せず k-means を高速化する手法を提案している．手法自体の新規性はそれほどない感じだけど，空間使用率を大幅に改善しつつ，かつ実際に幾つかのデータで Elkan の手法以上の高速化が得られたことに意義があるのかな． [追記; 2013/02/20] 別解出力をサポートした高速 k-means の C++ 実装を公開 - ny23の日記 で実装を公開しました．自分の専門分野だと，クラスタリングする対象
Power Iteration Clustering - tsubosakaの日記
岡野原さんのtweetで紹介されていたPower Iteration Clusteringという文章分類の手法に関する論文[1,2]を読んでみた。 背景 n個のデータX={x_1,...,x_n}が与えられたときに各データ間の類似度s(x_i,x_j)を成分に持つ類似度行列Aを考える。 また次数行列としてAのi行目の値を合計したd_{ii} = \sum_j A_{ij}を対角成分にもつ対角行列をDとする。 このときW:=D^{-1} Aをnormalized affinity matrixと定義する。簡単のためWはフルランクであるとする。 この行列はすべての要素が1となる固有ベクトルをもち、この時固有値は1となる。実はこれが最大固有値である(行列Aの行和が1となること+Gershgorin circle theorem(en)より導かれる)。また、行列Wの固有値を1=λ_1>=...>=
pLSI をハードクラスタリングに使おうとしたけどイマイチだった - nokunoの日記
きっかけはPythonでpLSA(pLSI)を実装している人がいたので、文書クラスタリングに使えないかな、と考えたことでした。satomacoto: PythonでPLSAを実装してみるただpLSIはいわゆるソフトクラスタリングで、以下のような問題がありました。 結果の解釈が直接しづらい 処理時間がかかるこのうち1つ目の問題は文書が与えられたときのクラスタへの所属確率 P(z|d) の最大値を取ってハードなクラスタリングの結果を得れば解決します。しかし、処理時間のほうはEMアルゴリズムの途中で0でないパラメータが多いことが原因なので、単にP(z|d)をハード化しても他のパラメータ （P(z|w,d)など） がなくならないのでイマイチでした。そこで P(z|w,d), P(w|z), P(d|z) の各パラメータをハード化することで高速化できないかなと考えたのですが、結果はかなり劣化してしま
irisデータをクラスタリングしてみた - nokunoの日記
発表や議論を聞きながら試してみました。 階層的クラスタリング plot(hclust(dist(iris[1:4]))) データそのものではなく、距離行列dist()だけを使う ward法だと綺麗なデンドログラムになりやすい kmeansクラスタリング data.frame(kmeans(iris[1:4],3)[1],iris[5]) 特徴量（iris[1:4]）からラベル（iris[5]）を教師なしで推定します irisデータだけあって、かなりきれいに取れている> data.frame(kmeans(iris[1:4],3)[1],iris[5]) cluster Species1 1 setosa2 1 setosa3 1 setosa4 1 setosa5 1 setosa6 1 setosa7 1 setosa8 1 setosa9 1 setosa10 1 setosa（中略）
bayonやCLUTOが爆速な理由 - download_takeshi’s diary
クラスタリングツールbayonを使っていて、常々「どうしてこんなに高速に処理できんのかなぁ」と疑問に感じていました。repeated bisectionという手法自体がk-means法などと比べると効率がいいのですが、それにしても、それだけでは説明がつかないほど爆速なわけです。 うまく例えられませんが、自前でk-meansのスクリプトを書いて比べてみると、自転車と新幹線くらいちがうという印象です。はじめてCLUTOを触った時、数万件程規模のクラスタリング処理が本当に「あっ」という間に終わってしまい、びっくりした記憶があります。 きっと実装面でなにか特殊なことがあるんだろうなと思い、mixiエンジニアブログでbayonの記事を改めて読み漁っていたら、以下の部分が目に止まりました。 このクラスタの評価は、クラスタの各要素とクラスタの中心とのcosine類似度の和としています。この和が大きいほど
Streaming k-means approximation - tsubosakaの日記
実家に帰省中，電車の中で読んでた論文の紹介。 概要 k-meansはクラスタリングテクニックとして非常に基本的な手法である。 しかし、k-meansでは全データに対してラベリングを複数回繰り返す必要があり、全データ点を保存する必要がある、そこでk-meansの出力であるk個のクラスタ中心をワンパスで見つける方法を提案する。 ここで得られるクラスタ中心は最適値と比較したときにO(log k)の近似となっている ストリームアルゴリズムについて 本論文で言っているStreamingの意味としては入力を前から見ていって、すべて保存しないアルゴリズムのことを言っている。いわゆるオンラインアルゴリズムのように入力が入ってくるたびに何かしらの結果が得られるわけではない。また，ストリームの長さは有限である事を仮定している。 k-meansとは k-meansとはデータ点 X = {x_1 , ... x_
はてなブログ | 無料ブログを作成しよう
セメントドリンク、ブラウン管、吊るされた収納、OMORIカフェ、くり抜き、どや顔の初音ミク パチミラ福岡に出演する縁で博多に行きました。 楽しかったのでその時の写真をアップロードします。 博多駅のハートポスト 手描きのグリッチ カニの丸揚げ(おいしかった) フレッシュセメント という名前の飲み物(おいしかった)ごま+バナナスムージーっぽかった？ 泡系…
適切なクラスタ数を推定するX-means法 - kaisehのブログ
K-means法によるクラスタリングでは、あらかじめクラスタ数Kを固定する必要があります。HatenarMapsでもK-means法を使っているのですが、クラスタ数は（特に根拠もなく）200個に決め打ちになっていました。 これに対して、X-means法というK-means法の拡張が提案されていることを知りました。X-means法を使うと、データに応じて最適なクラスタ数を推定できます。 K-means and X-means implementations http://www-2.cs.cmu.edu/~dpelleg/download/xmeans.pdf X-means法の考え方は、K=2で再帰的にK-means法を実行していくというもので、クラスタの分割前と分割後でBIC（ベイズ情報量規準）を比較し、値が改善しなくなるまで分割を続けます。 調べたところ、Javaのデータマイニングツー
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
IIR の階層的クラスタリングを試す (nakatani @ cybozu labs)
Pathtraq で Web ページの自動分類を手がけてみて。 Web ページは日々どんどん変わっていくのでフィルタは常に更新されなければいけないんですが、そのためには適切なタイミングに、適切な学習データを用意しなければならない。大変。 メンテナンスフリーが理想ですが、もちろん難しい。 現実的なところとしては「追加学習が必要なことを検知して、適切な学習データの候補を提案してくれる」というものが作りたいなあ……などなど考えているわけです。 そこらへんも含めて、自然言語処理とか機械学習とかそこら辺のお勉強をしてるんですが、実際に手を動かさないとわかんないですよねー。 というわけで、 "Introduction to Information Retrieval" の Chapter 17 "Hierarchical clustering" に沿って、ドキュメントの分類器を作ってみました。 ポイン
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
DrSkippy.com is for sale | HugeDomains
今日のDBCLS & semi-supervised clustering - 糞ネット弁慶