k-meansアルゴリズムは極小値にのみ収束し、大域的最小値には収束しないことを読みました。どうしてこれなの？初期化が最終的なクラスタリングにどのように影響するかを論理的に考えることができ、最適ではないクラスタリングの可能性がありますが、数学的にそれを証明するものは見つかりませんでした。
また、なぜk-は反復プロセスを意味するのですか？目的関数を重心と部分的に区別し、それをゼロに等しくして、この関数を最小化する重心を見つけることはできませんか？最小ステップバイステップに到達するために最急降下法を使用する必要があるのはなぜですか？
検討：
. c .
. c .
ここで、c はクラスター重心です。アルゴリズムは停止しますが、より良い解決策は次のとおりです。
. .
c c
. .
証明に関して - 何かが常に真であるとは限らないことを証明するために数学的な証明は必要ありません。上記のように、反例が 1 つだけ必要です。おそらく上記を数学的な証明に変換できますが、これは不要であり、通常は多くの作業が必要です。学術界でさえ、何かを反証するために単に反例を示すことが認められています。
k-means アルゴリズムは定義上、反復プロセスであり、単純に機能する方法です。クラスタリングの問題は NP 困難であるため、正確なアルゴリズムを使用して重心を計算すると、非常に時間がかかります。
問題とアルゴリズムを混同しないでください。
k-means 問題は、重心への最小二乗割り当てを見つけることです。
解を見つけるためのアルゴリズムは複数あります。
グローバルな最適値を見つけるための明白なアプローチがあります。すべての可能な割り当てを列挙します。これにより、グローバルな最小値k^nが得られますが、指数関数的なランタイムになります。
より速い時間で近似解を見つけることに、より多くの注意が払われました。
Lloyd/Forgy アルゴリズムは、有限数の状態が存在し、目的関数がすべてのステップで減少しなければならないという理由だけで、極小値に収束することが保証されている EM スタイルの反復モデル改良アプローチです。このアルゴリズムは通常O(n*k*i)どこで実行されi << nますが、極小値のみを検出する場合があります。
MacQueens メソッドは、技術的には反復的ではありません。これは、Lloyd の意味で局所的な最小値さえ見つけられない、一度に 1 要素ずつのシングルパス アルゴリズムです。(ただし、収束するまで、データ セットに対して複数回実行して、局所的な最小値も取得できます!) 1 回のパスを実行する場合は、O(n*k)複数回のパスの場合は を追加しiます。ロイドよりも多くのパスが必要な場合とそうでない場合があります。
次に、ハーティガンとウォンがいます。O(n*k*i)詳細は覚えていませんが、IIRC は Lloyd/Forgy の賢く、より怠惰な変種でしたn*k。
lランダムな割り当てをテストするランダム化されたアルゴリズムを実行することもできます。おそらく最小値はまったく見つかりませんが、「線形」時間で実行されO(n*l)ます。
ああ、さまざまなランダムな初期化を試して、グローバル最小値を見つける可能性を高めることができます。試行回数の係数を追加t...