[HOME][発明]

K-mean法

K-mean法の問題点

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

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

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

2003/5/12追記

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

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

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

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

類題

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

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

外部リンク

BIGLOBEサーチ:“K-mean法”での検索結果 2003/6/3現在50件中1位 2位は重要度7

関連ページ

日経サイエンス
Padie評
でっちあげ 下請けのシンクタンクのアルバイトの小学生そういう疑い。
中央値分割

作成 2001/9/25 - 更新 2004/01/26

発明ディレクトリ

Google
Web www.PAG1U.net

関連ディレクトリ

画質

計画

ダウンロード

通信

関連サイト

乱雑な本棚:計算幾何学

乱雑な本棚:画像圧縮

乱雑な本棚:発明

乱雑な本棚:最適化

 
 
 
 
 
seo

ホーム 発明 掲示板 (C)松岡肇、メール