kmeans 関数の 'singleton' オプション

kmeans について何にも知らないのに、今回は kmeans について書いてみることにします。

Matlab では、kmeans 法を行う関数 kmeans() が準備されていて、
参考：Statistics and Machine Learning Toolbox Documentation
いろいろオプションも充実していて便利なようです。
kmeans() のアルゴリズムは、朱鷺の杜↓
k-means法 - 機械学習の「朱鷺の杜Wiki」
に書かれているのと多分同じなので、以後、このサイトの表記を使うことにします。

kmeans アルゴリズムを行うときは、セントロイドの初期値 *1 を決めなくてはいけないのですが、Matlab では、これをランダムにも手動ででも決めることが出来ます。
ただし、クラスターの種を変に設定すると、空のクラスターが出てくる場合があります。

クラスターが空になる例

1 次元ユークリッド直線上でクラスタリングを行う。
$X=\{0,1,3\}$
を 2 つのクラスターに分類する。
クラスターの種を
$c_1=-1,$ $c_2=0$
とする。
このとき、《kmeans アルゴリズムの 3》を行うと、
$X$ 上のどの点 $p$ においても、
$||p, c_1||>||p, c_2||$
なので、
$X_1$ は空集合になってしまう。

このままだと、《kmeans アルゴリズムの 2》で 0 で割り算をすることになってしまうので、通常はエラーとなってしまうのですが、「何とかしてクラスター数を減らさずに計算を続行したい！」というときのためのオプションが、タイトルにある 'singleton' オプションです。

kmeans([データ], [クラスター数], 'emptyaction', 'singleton' [ ,その他オプション])

とするだけです。
こうすると、空のクラスターがある空でないクラスターと入れ替わって、kmeans アルゴリズムが続行するのですが、恥ずかしながら最初は内部でどういう操作が行われているか全然意味が分かりませんでした。
マニュアルには

Action to take if a cluster loses all its member observations.
'singleton'： Create a new cluster consisting of the one point furthest from its centroid.

と書かれてたんだけど、まず、『its centroid』がどれを指してるのか意味不明。
だから、『a new cluster consisting of the one point』がどれか良く分かっていませんでした。

『its centroid』ですが、ぼくは最初はてっきり、「空のクラスターのセントロイド」のことかと思ってました。
下図
(ここで、 $c_i$ は、 $X_i$ の種を表しています。初めて《kmeans アルゴリズムの 3》を行った直後の状況です。)
で言うならば、『its centroid』とは、スッカラカンのクラスター $X_1$ の種 $c_1$ のことで、『そこから最も遠い点』というのは $p_6$ のことかと思っていました。

だから、この操作で、 $X_1$ が $p_6$ を $X_3$ から奪って、

$X_1=\{ p_6 \}$
$X_2=\{ p_1, p_2, p_3 \}$
$X_3=\{ p_4, p_5 \}$

となると思ってたんだけど、どうやらこういう意味ではないみたいです。
実際、この状況で、 $c_2$ とか $c_3$ とかを動かして計算してみると、結果が変わってくるので、「空のクラスターのセントロイドと、各点との距離」という問題ではない、ということが分かります。

それで、いろいろ観察してみたんですけど、多分こういうアルゴリズムを行っているんじゃないかと思います。

任意の $X$ の点 $p_i$ は、必ずどこかのクラスターに入っている。

従って、 $p_i$ の入っているクラスターのセントロイドと、 $p_i$ との距離は、各 $p_i$ に対して一意に定まる。これを $d(p_i)$ と書く。

$d(p_i)$ が最大となる $p_i$ が、求めるべき『the one point』である。複数個ある場合は、そのなかで添字の最も小さいものを選ぶ。