k-means法：結果は開始位置で決まる

k-means法は誰もが最初に学ぶクラスタリングアルゴリズムですが、あまり語られない性質を持っています。偶然どの位置から処理を始めたかによって、異なる答えを導き出すということです。下のダイヤルを回して確認してみてください。まったく同じデータ点を同じ数に分割しても、行き着く先は変わります。

計算例 — k-means法：結果は開始位置で決まる

クラスタ内誤差平方和	1.0989
収束までの反復回数	2
クラスタのサイズ	3個すべて割り当てあり
結果の開き	430.8%
見つかった異なる答え	24種類中の3種類
つまりこの開始位置は	見つかった中で最良

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

レッスン

理論 — k-means法：結果は開始位置で決まる

k平均法は、変化がなくなるまで二つの手順を繰り返すことで、データをk個のグループに分類します。まず各点を最も近い中心に割り当て、次に各中心をその集まった点群の平均位置へ移動させるのです。この手法が最小化しようとしているのはクラスタ内平方和（各点から自身の中心までの距離の二乗和）であり、二つの手順はどちらもこの値を減らす方向にしか働きません。アルゴリズムが必ず停止することの証明は、まさにこれに尽きます。

各記号の意味

k: 指定するクラスタの数。この値がいくつであるべきか、データ自体が教えてくれることはありません
WCSS: 各点から自身の中心までの距離の二乗和

前提: クラスタがほぼ同じ大きさの丸い塊であること。平均からのユークリッド距離の二乗という指標では、それ以外の形を表現できないからです。細長いグループや入れ子状のグループ、大きさが極端に異なるグループをk平均法がうまく見つけられないのは、処理に失敗しているからではありません。最初からそのようなものを探してはいないのです。

どの試行も間違いなく収束している 🖖

データ点を塊に、k を 3 に設定したまま、開始位置のダイヤルを1から24まで回してみてください。22回の試行は1.0989に落ち着きます。しかし17番と21番は5.8172と5.8331に落ち着き、結果は5.3倍も悪化します。これらは二つの塊を結合させ、三つ目の塊を半分に分割しているのです。この2回の試行で何らかのエラーが起きたわけではありません。ロイドのアルゴリズムは確実に収束します。クラスタ内誤差平方和はステップごとに必ず減少し、永遠に減り続けることはないため、いつかは必ず停止します。実際、すべてのデータセット、すべての k、両方の初期化方法を網羅した1,536回の試行のうち、収束に失敗したものは一つもありませんでした。保証されていないのは、良い場所で停止することだけです。したがって、「アルゴリズムが収束した」という言葉は、あなたのデータについてではなく、算術についての事実を述べているに過ぎません。k-means法を1回だけ実行したとしたら、自分がどちらの答えを手にしているかを知る術はないのです。

k-means++ は被害を半減させるが確約はしない 🖖

開始方法を k-means++ に切り替えると、このデータセットにおけるばらつきは完全に消滅します。24回の試行すべてが1.0989を見つけ出すのです。これは誰もが頼る解決策であり、初期の中心をランダムに配置するのではなく、互いに離れた場所に配置することで機能します。しかし、この改善は統計的な傾向であって保証ではありません。どの程度の効果があるのかを知っておく価値があります。データ点、サンプルサイズ、k の組み合わせ112通りで測定した結果、k-means++ がランダムな開始位置よりも明確に優れた最適解を見つけたのは38通りでした。逆にランダムの方が良かったのは17通りで、57通りは引き分けに終わっています。24回の試行における結果の開きは、平均して55.5%から31.7%に減少しました。つまり、不運な試行による悪影響をほぼ半減させる一方で、6回に1回は適当にダーツを投げて決めた方がマシだったということです。リングのデータセットで点数を90に、k を 5 に設定してみてください。ランダムな初期化では0.9884に到達しますが、k-means++ は1.0213で停止してしまいます。

答えのない問いに対する、安定的でバランスの取れた自信に満ちた答え 🖖

最後のプリセットを読み込んでみてください。データ点は規則的な格子であり、クラスタは一切存在しません。それでも、k-means法はこれをきっちり25個ずつの4つのグループに分割します。さて、この結果について、手元にあるすべての診断指標が何を示しているかを見てみましょう。まず、11回の反復で収束しました。安定的でもあります。24回の開始位置はすべて同じ答えに到達するため、何度やり直しても異常には気づけません。クラスタは完全にバランスが取れており、これは通常、良いクラスタリングに見られる特徴です。三つの独立したシグナルが同じ方向を指し示しているにもかかわらず、そこには何もないのです。これが、技術的な解決策が存在しないクラスタリングの側面です。k-means法は「k 個の中心をどこに配置すべきか」という問いには答えてくれますし、常に何らかの答えを出します。「このデータにはいくつのグループが存在するか」という問いに、そもそも答えがあるかどうかにかかわらず、です。

全プロセスの詳細解説

データにクラスターがいくつ存在するのか不明なため、スコア曲線のエルボー（屈曲点）からそれを読み取ることにします。四つの点集合すべてで実際に読み取りを行い、何回正解できるか数えてみましょう。下のパネルには 1 から 8 までの各 k における最良スコアと、その背景に一つ前の k からの減少幅が示されています。

この問題をツールで開く
1. まず、なぜ最小値ではなくエルボーに着目するのでしょうか。点集合を三つの塊に設定して曲線を読んでみましょう。k = 1 で 10.3978、それから 5.6145、1.0989、0.9241、0.8052、0.6875、0.6077、0.5366 と続きます。値は決して上昇しません。上昇するはずがないのです。k 個のグループに分けた状態からどれか一つのグループを分割すれば、k + 1 個のグループを作れます。そして分割によって、点はそれぞれの中心により近づくことしかありません。k を点の数まで増やしきれば、すべての点がそれ自身で単独のクラスターとなり、スコアはきっかり 0 になります。
  
  $WCSS (k) = \sum_{j = 1}^{k} \sum_{x \in C_{j}} ∥ x - μ_{j} ∥^{2}, WCSS (k + 1) \leq WCSS (k) three blobs : 10.3978, 5.6145, 1.0989, 0.9241, 0.8052, 0.6875, 0.6077, 0.5366$
2. つまり曲線から最小値を見つけることはできず、代わりに減少幅を読み取らなければなりません。先ほどの塊のデータでは、減少幅は 46.0%、80.4%、そこから 15.9%、12.9%、14.6%、11.6%、11.7% と変化します。k = 3 の直後の減少幅はその直前の減少幅の五分の一にすぎず、5.06 分の一に急落しています。そして、k = 3 こそがまさにこのデータが生成された際の設定でした。この手法は見事に機能しており、これこそが皆が教わる典型例なのです。
  
  $drop (k) = 1 - \frac{WCSS ( k + 1 )}{WCSS ( k )}, elbow = ar g max_{k} \frac{drop ( k - 1 )}{drop ( k )} three blobs : 46 . 0%, 80 . 4%, 15 . 9%, 12 . 9%, 14 . 6%, 11 . 6%, 11 . 7% \Rightarrow k = 3, \times 5.06$
3. 次は、クラスターが全く存在しない格子です。減少幅は 41.6%、34.1%、36.8%、16.4%、16.9%、12.8%、15.7% となります。k = 4 の後で減少幅が 2.25 分の一に縮小しており、これこそ探すように言われたまさにその形状です。クラスターなど一つもないデータ集合に対して、エルボーの読み取りは「四つのクラスター」という答えを導き出してしまいます。
  
  $lattice : 41 . 6%, 34 . 1%, 36 . 8%, 16 . 4%, 16 . 9%, 12 . 8%, 15 . 7% \Rightarrow k = 4, \times 2.25$
4. 続いて、実際に二つのグループが存在するリングを見てみましょう。減少幅は 37.2%、32.8%、38.5%、33.4%、43.1%、25.3%、15.3% です。全体として全く傾向が見られないまま、終盤で二回下落しています。最も明確な急落は k = 6 の後に現れます。読み取りから得られる答えは六つですが、実際の正解は二つです。
  
  $ring : 37 . 2%, 32 . 8%, 38 . 5%, 33 . 4%, 43 . 1%, 25 . 3%, 15 . 3% \Rightarrow k = 6, \times 1.70$
5. 最後に、大きさの異なる三つのクラスターを持つ不揃いです。値は 43.8%、48.4%、35.4%、24.7%、16.1%、14.4%、21.8% となります。どこにも急落はなく、ただなだらかに減少していきます。最大の落ち込みでも 1.53 分の一の変化にとどまり、屈曲点（角）にはなりません。データの中に確かに三つのクラスターが存在しているにもかかわらず、この読み取り方では何も分からないのです。
  
  $uneven : 43 . 8%, 48 . 4%, 35 . 4%, 24 . 7%, 16 . 1%, 14 . 4%, 21 . 8% \Rightarrow k = 5, \times 1.53$
解答

四つのうち正解は一つだけでした。塊のデータでは正解したものの、格子では存在しない四つのクラスターをひねり出し、二つのグループからなるリングに対しては六つだと提案し、不揃いなデータでは沈黙してしまいました。この結果のばらつきは、決して偶然ではありません。クラスターが丸く、似たような大きさで、互いによく分離されているときに限り、エルボーは鋭くなります。しかしそれは、わざわざ計算しなくとも見ただけで数を数えられるような状況です。本当に助けが必要になるようなデータ集合では、エルボーは常にぼやけてしまいます。誰かに数値を主張する根拠としてこの曲線を使う前に、この事実は知っておくべきでしょう。そしてこれこそが、エルボー法がシルエットスコア、ギャップ統計量、情報量規準といった指標より上位にあるわけではなく、あくまでそれらと並ぶ選択肢の一つにすぎない理由なのです。このページにはそれらの指標は登場しません。それらはみな、スコア曲線には答えられない同じ問いを、それぞれ異なる方法で問いかけているのです。常に何らかの答えが出てしまう「k 個の中心はどこに配置されるか」ではなく、「そもそもここにグループは存在するのか」という問いを。

$set three blobs lattice ring uneven elbow says 3465 truth 3023 sharpness \times 5.06 \times 2.25 \times 1.70 \times 1.53$

学習の道すじ

データへの直線当てはめ

参考文献 (3)

The algorithm itself. Written in 1957 for quantising a signal into levels, circulated as a Bell Labs memorandum, and not published for twenty-five years: S. P. Lloyd, “Least squares quantization in PCM.” IEEE Transactions on Information Theory 28(2), 129–137, 1982.
The initialisation the second insight block measures — and the source of the bound that makes it worth using, which is a guarantee about the EXPECTED score rather than about any single run: D. Arthur and S. Vassilvitskii, “k-means++: The Advantages of Careful Seeding.” In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’07), 1027–1035. SIAM, 2007.
Where the elbow reading comes from, and it was proposed with more caution than it is usually repeated with: R. L. Thorndike, “Who belongs in the family?” Psychometrika 18(4), 267–276, 1953.

42Math チーム · 公表された資料と照合しています。訂正のご指摘を歓迎します。