K-mean法

K-mean法の問題点

昨夜、なかなか寝付けないでいる間に考えたことなのですが、K-mean法でいくら時間をかけても、良い初期状態を与えていないと無意味ですね。

二次元の問題で、６つのサンプルが、正三角形の頂点の位置に、３，２，１個分布しているのを２つの位置で代表させて、代表との誤差の総和を最小にするという単純化した問題を考えてみてください。3個と、2個＋1個に分けるのが正解ですが、初期状態で3個＋2個と、1個とに分けたとしたら、K-mean法では永遠に正解に到達しません。

ずーっと昔にも、3次元の場合で、ほとんど均一に分布しているサンプルを4つの代表点で表現する場合に、平面に４点を初期値として与えても、K-mean法ではなかなか、四面体配置に移行しないという風な限界は感じていたのですが。

2003/5/12追記

「日経サイエンス」2001/11 を読んでいたら、ベオウルフの記事のところで、問題をK-mean法で解こうとすると時間がかかるので、多数のLinuxパソコンを並列動作させることにしたみたいなことが書いてありました。僕に言わせれば、悪いアルゴリズムのために、高速なコンピュータの母となったという話になります。

中央値分割　このページで、昔、他のアルゴリズムとの比較を行っていますが、さすがにK-mean法については検討していません。遅すぎます。

というか、そもそも、サイエンスの記事の場合、軸の重みをどう決めたのかという疑問がわきあがります。無意味な計算のために、高速なコンピュータを使ったのではという疑問です。

距離を求めるために軸の重みの問題が出てくるわけで、あくまでも近似と割り切って、因子分析で少数の軸にまとめて、それから、K-meanでも良かったのでは？

類題

なお、同様のことを考えている人に、別の問題を出題しておきます。暇があれば自分で解くのですが。

すべての自治体ごとに、電話帳にいろいろな職業が何件載っているかのデータを電話帳CD-ROMなどから入手して、自治体をクラスタリング、また逆に、職業をクラスタリングしてみてください。この問題は、政府がやっていそうなものですが、ディザかけた後に、JPEG保存するような発表をみると、ボンクラが関わっていて、悪いアルゴリズムで手間だけかけているのでは？　と見ています。

ターミナル駅周辺に集積するソフト系ＩＴ産業

外部リンク

BIGLOBEサーチ：“K-mean法”での検索結果 2003/6/3現在50件中１位２位は重要度７

K-mean法

K-mean法の問題点

類題

外部リンク

関連ページ