k-meansは「初期値に弱い」とよく言われる。ランダムに置いた初期セントロイドが悪い位置からスタートすると、そのまま悪い局所最適解に収束して抜け出せなくなる、という話だ。焼きなまし法の記事で見た「開始点が終着点を決めてしまう」問題と同じ構図だし、絡まった2リングの記事で見た「k-meansは距離でしか物を見られない」という弱点とも地続きの話だと思う。

ただ、この「初期値に弱い」という話、どのくらい弱いのかを自分の目で確かめたことはなかった。教科書的な結論をそのまま信じるのではなく、実際にk-meansが引っかかりやすいデータを自分で設計し、ランダム初期化とk-means++初期化を何百回も走らせて、悪い局所最適解に落ちる割合を実測してみた。

実験に使ったコードの全文はGitHubに置いています。

わざと引っかかりやすいデータを作る

k-meansのランダム初期化(Forgy法: データ点からk個をランダムに選んでそのまま初期セントロイドにする)が失敗しやすい状況を、狙って作る。ポイントは人口の偏りと距離の偏りだ。

• 大きくて薄い塊1つ: 中心$(0,0)$、200点、標準偏差1.2
• 小さくて濃い塊4つ: 中心$(\pm15,0)$と$(0,\pm15)$(東西南北)、それぞれ12点、標準偏差0.4

言葉だけだとイメージしづらいので、実際のデータを図にしておく。この後の図やアニメーションもすべて、この同じ248点の上で起きる話だ。

全248点のうち81%が中心の大きな塊に集中している一方で、5つの塊どうしはお互いに標準偏差の10倍以上離れていて、混同の余地なく分離している。この配置がなぜ意地悪かというと、ランダムに5点選んで初期セントロイドにすると、その大半が中心の大きな塊の中に落ちるからだ。5点とも東西南北のどれかに触れない確率は理屈上$(0.81)^5 \approx 35\%$あり、実際には1〜2点しか外側の塊に触れないケースも多い。実際、今回の実験で使った200通りのランダム初期配置を数えてみると、5点すべてが中心の塊に落ちたのが57回(28.5%)、外側の塊に触れたのが1点だけだったのが93回(46.5%)——合わせて75%の試行が、外側4つの塊に対して初期セントロイド1個以下という布陣からスタートしていた。ちなみに、外側4つの塊すべてに初期セントロイドが届いたケースは200回中0回だった。それでも(後で見る通り)半分強の試行は最終的に正解へ辿り着ける。Lloyd法の反復の途中で、セントロイドが中心の塊から外側の塊へ「引っ越し」できるケースがあるからだ。問題は、その敗者復活が間に合わない試行がどれだけあるか——それを次の節で数える。

def init_random(X, k, rng):
    """Forgy法: データ点からk個をランダムに選んで初期セントロイドにする"""
    idx = rng.choice(len(X), size=k, replace=False)
    return X[idx].copy()

def init_kmeanspp(X, k, rng):
    """k-means++: 最初の1点はランダム、以降は
    「既存セントロイドまでの最短距離の2乗」に比例する確率でサンプリングする"""
    n = len(X)
    centroids = np.empty((k, X.shape[1]))
    centroids[0] = X[rng.integers(n)]
    closest_sq = np.sum((X - centroids[0]) ** 2, axis=1)
    for i in range(1, k):
        probs = closest_sq / closest_sq.sum()
        idx = rng.choice(n, p=probs)
        centroids[i] = X[idx]
        closest_sq = np.minimum(closest_sq, np.sum((X - centroids[i]) ** 2, axis=1))
    return centroids

k-means本体(Lloyd法の反復)もnumpyでスクラッチ実装している。割り当て→重心再計算を、セントロイドの移動量が閾値を下回るまで繰り返すだけの、教科書通りの中身だ。

実験: 200回ずつ、bad局所最適解の定義

両方の初期化方法で、それぞれ異なる乱数シードから200回ずつk-means(k=5)を最後まで収束させ、最終inertia(クラスタ内二乗距離の総和)を記録した。「悪い局所最適解」の定義は、実測したinertiaの分布そのものから決めた。

200回×2条件、合計400回の最終inertiaを並べてみると、値はきれいに2つの山に分かれていた。全真のクラスタを正しく復元できたケースは例外なくinertia=534.0(小数1桁まで完全に一致)で、そこから外れたケースはinertia 2980〜5743というはっきり高い山を作っている。この間には1個の試行も存在しない。というわけで、「悪い局所最適解」をinertia > 1000(最良値534の約1.9倍)と定義した。この閾値の上下どちらにも試行がほとんど張り付いておらず、恣意性の少ない切り方になっている。

結果: ランダム47.5% vs k-means++ 1.0%

global best inertia: 533.96

random init  : bad frac = 47.5%  mean inertia=1827.2  std=1447.2
kmeans++ init: bad frac =  1.0%  mean inertia= 559.2  std= 250.9

ランダム初期化は200回中95回(47.5%)が悪い局所最適解に落ちた。 平均inertiaは1827.2(標準偏差1447.2)と、最良値534の3倍以上に膨らんでいる。一方k-means++は200回中たった2回(1.0%)しか悪化しなかった。平均inertiaも559.2(標準偏差250.9)と、ほぼ最良値のすぐ近くに収まっている。

真のクラスタ所属との一致度(ARI、1が完全一致)で見ても同じ傾向だ。

random ari mean=0.748  perfect(ari=1.0) frac=52.5%
pp     ari mean=0.998  perfect(ari=1.0) frac=99.0%

ランダム初期化は52.5%しか5つの真のクラスタを完全再現できていない。k-means++は99.0%が完全一致だった。半分弱の確率で明確に間違えるランダム初期化と、100回に1回しか間違えないk-means++——数字にすると、想像していたよりはっきりした差になった。

悪い局所最適解の中身: 「吸収」と「分裂」のセット

数字だけでなく、実際に何が起きているのかを覗いてみる。ランダム初期化200回のうち最悪だった1回(inertia=5743、最良比10.8倍、ARI=0.80)と、k-means++の典型的な1回(inertia=534、最良比1.00倍、ARI=1.00)を、同じデータの上で並べた。

この最悪ケースの中身を数字で追うと、壊れ方には一貫したパターンがあった。

• 中心の大きな塊(200点)と、西側の小さな塊(12点)が同じクラスタに吸収されている
• 東側の小さな塊(12点)と、南側の小さな塊(12点)も同じクラスタに吸収されていて、そのセントロイドは$(7.46, -7.43)$——東の塊にも南の塊にも属さない、何もない空間の真ん中に着地している
• 北側の小さな塊(12点)だけは、3つの別々のセントロイドが$(0, 14.6)$〜$(0, 15.8)$というほぼ同じ場所に重なって刺さり、12点を6・1・5に切り刻んでいる

5個しかないセントロイドのうち3個が北の塊1つを取り合ってひしめき合ったせいで、残り2個で西・中心・東・南の4つの塊を担当することになり、当然どこかで「本来別々の塊」を無理やり1つにまとめるしかなくなる。「1箇所に固まりすぎて、別の場所が手薄になる」という、ランダムサンプリングの偏りがそのまま局所最適解の形に焼き付いていた。

収束の過程をアニメーションで見る

上のケースが焼き上がるまでの過程(Lloyd法の反復)をアニメーションにした。

重心の更新はわずか4回でLloyd法は収束している(5回目の反復では重心が1つも動かず、そこで停止した)。最初のセントロイド配置の時点で、すでに「北に密集・東と南が手薄」という偏りができあがっていて、そこから先はその偏りを追認するように、東と南の塊を一番近い(そして本来は別物の)セントロイドに割り振っていくだけだった。悪い局所最適解は、収束の終盤で生まれるのではなく、最初の一手の時点でほぼ決まっていることがよく分かる。

意外だったこと: inertiaとARIは完全には一致しない

素直に驚いたのが、「悪い局所最適解」をinertiaで定義した場合とARIで定義した場合で、判定が完全には一致しなかったことだ。ランダム初期化200回のうち7回は、inertiaが約3220(最良比6.0倍)と明確に「悪い」側にいるのに、ARIは0.987〜0.990と、ほぼ真のクラスタを言い当てていた。

中身を見ると理由が分かる。この7回は、先ほどの最悪ケースのような「塊どうしの吸収」は起きておらず、北側の小さな塊(12点、全データの4.8%)だけが2〜3個の幽霊クラスタに分裂している。ARIは全体のペアの一致度を見る指標なので、全データの5%にも満たない小さな塊が内部で分裂しても、スコアはほとんど下がらない。一方でinertiaは、その分裂のために使われたセントロイドの数だけ他の場所からセントロイドが足りなくなり、結果的にどこかで別の塊を無理やり吸収する羽目になる——という因果関係までは拾えないが、ロスとしてはきっちり跳ね上がる。「真のクラスタをほぼ当てられているのに、目的関数としては悪い」という状態が実在するのは、実際に両方の指標を計算してみるまで気づかなかった。

もう1つ、k-means++も完璧ではなかった。1.0%(200回中2回)は悪化していて、その中身はランダム初期化の最悪ケースと同じ「1つの塊を丸ごと吸収し、代わりに別の塊を2分割する」というパターンだった(inertia 2999と3111、ARI 0.813と0.814)。k-means++は「既存セントロイドから遠い点を選びやすくする」だけの確率的な仕組みであって、遠い点を選ぶことを保証するわけではない。確率が低いだけで、運悪く2回連続で同じ塊の近くを引き続ければ、ランダム初期化と同じ壊れ方をする。

まとめ

• 大きく薄い塊1つ(200点)+遠く離れた小さく濃い塊4つ(各12点)という、人口が偏っていて距離もはっきり離れたデータを自作した
• ランダム初期化(Forgy法)とk-means++初期化をそれぞれ200回ずつ実行し、inertiaの分布から「悪い局所最適解」を inertia > 1000(最良値534の約1.9倍)と定義した(実測分布に明確な2山の隙間があり、この閾値付近には試行が存在しない)
• ランダム初期化は47.5%が悪い局所最適解に落ち、平均inertia 1827.2(std 1447.2)。真のクラスタを完全再現できたのは52.5%(ARI=1.0)
• k-means++は1.0%しか悪化せず、平均inertia 559.2(std 250.9)。真のクラスタの完全再現は99.0%
• 悪い局所最適解の中身は一貫していた: どこかの塊が別の塊に「吸収」され、その分どこかの塊が2〜3個の「幽霊クラスタ」に分裂する
• inertiaとARIは完全には一致しない: ランダム初期化7回は、inertiaでは明確に悪い(最良比6.0倍)のにARIは0.99近い——小さな塊の内部分裂だけならARIはほとんど下がらないが、inertiaはきっちり悪化する
• k-means++も無敵ではなく、200回中2回はランダム初期化と同じ壊れ方をした。確率を下げるだけで、ゼロにするわけではない

最初にどこへセントロイドを置くかだけで、その後どれだけ反復を重ねても結果の半分弱が「悪い方の山」に決まってしまう——というのは、人との出会いや物事の捉え方の初手にもそのまま重なる話だと思う。最初の印象や、問題を最初にどう切り分けたかは、その後どれだけ丁寧に付き合っても、時間をかけて「最適化」しても、なかなか覆らない。今回のデータでは、一度北の塊に3つのセントロイドが密集してしまうと、東と南の塊を正しく見つける手番はもう残っていなかった。k-means++がやっていたことは、実はそんなに大それたことではない。「今すでに近くにいる人・場所」から離れた場所に、次の一手を置く確率を少しだけ上げているだけだ。それだけで、悪い方の山に落ちる確率は47.5%から1.0%まで下がった。最初の見立てに全部を賭けず、あえて視野の外側にも初手を散らしておく——そのコストは実際には小さく、リターンは実測するとかなり大きかった。

• 実践記
• 最適化

関連記事

• スペクトラルクラスタリングで絡まった2つのリングを分けたら、k-meansはARI 0.08で壊滅した
• 焼きなまし法(シミュレーテッドアニーリング)と勾配降下法を200箇所から競走させたら、勾配降下は0箇所しか正解に届かなかった
• 宝くじ仮説の枝刈りをnumpyで自前実装したら、当たりくじの優位はスパース率98%から先だけだった(99%で62%対48%)

このブログでは、機械学習の仕組みを実際にコードで実装して確かめた実験をテーマ別に整理しています（拡散モデル・Transformer・強化学習・多様体学習・過学習など）。