30

k-Means クラスタリングアルゴリズムのオンライン バージョンはありますか?

オンラインとは、すべてのデータ ポイントがシステムに入力されるたびに 1 つずつシリアルに処理されることを意味し、リアルタイムで使用すると計算時間を節約できます。

私は自分自身で良い結果を書いたことがありますが、修士論文で使用されるため、参照するために「標準化された」ものを持っていることを本当に望んでいます.

また、他のオンライン クラスタリング アルゴリズムに関するアドバイスはありますか? (lmgtfy に失敗しました;))

4

1 に答える 1

42

はいあります。より一般的には「順次 k-means」として知られているため、Google はそれを見つけることができませんでした。

Richard Dudaによるプリンストン CS クラス ノートのこのセクションで、順次 K-means の 2 つの疑似コード実装を見つけることができます。以下の 2 つの実装のうちの 1 つを再現しました。

Make initial guesses for the means m1, m2, ..., mk
Set the counts n1, n2, ..., nk to zero
Until interrupted
    Acquire the next example, x
    If mi is closest to x
        Increment ni
        Replace mi by mi + (1/ni)*( x - mi)
    end_if
end_until

これの優れた点は、各クラスターの平均と、クラスターに割り当てられたデータ ポイントの数を覚えておくだけでよいことです。これら 2 つの変数を更新したら、データ ポイントを破棄できます。

どこで引用を見つけることができるかわかりません。私は、Duda の古典的なテキストPattern Classification and Scene Analysisまたは新しい版のPattern Classificationを調べ始めます。そこにない場合は、Chris Bishop の最新の本、または Daphne Koller と Nir ​​Friedman の最近のテキストを試すことができます。

于 2010-09-14T07:24:30.017 に答える