★ k-means法のアルゴリズム ★

　189　k-means法のアルゴリズム　　KAota　　2002/10/17 (木) 18:39
　　192　Re: k-means法のアルゴリズム　　青木繁伸　　2002/10/17 (木) 18:56
　　　195　Re^2: k-means法のアルゴリズム　　青木繁伸　　2002/10/17 (木) 23:22
　　　　196　Re^3: k-means法のアルゴリズム　　青木繁伸　　2002/10/17 (木) 23:29
　　　　　201　Re^4: k-means法のアルゴリズム　　KAota　　2002/10/18 (金) 11:41
　　　　　198　Re^4: k-means法のアルゴリズム　　SIZMI　　2002/10/18 (金) 09:24
　　　　　　203　Re^5: k-means法のアルゴリズム　　青木繁伸　　2002/10/18 (金) 11:59
　　　　　　202　Re^5: k-means法のアルゴリズム　　KAota　　2002/10/18 (金) 11:57
　　　　　　　204　Re^6: k-means法のアルゴリズム　　青木繁伸　　2002/10/18 (金) 12:04
　　　　　　　　205　Re^7: k-means法のアルゴリズム　　KAota　　2002/10/18 (金) 12:42

189.　k-means法のアルゴリズム　　KAota　　2002/10/17 (木) 18:39
k-means法のプログラムを作ってみようと思っていますが，そのアルゴリズムがよく解りません。
プログラム作成に必要最低限な程度の簡単なアルゴリズムを教えていただければ幸いです。
よろしくお願いいたします。

　　　　　[このページのトップへ]

192.　Re: k-means法のアルゴリズム　　青木繁伸　　2002/10/17 (木) 18:56
> プログラム作成に必要最低限な程度の簡単なアルゴリズムを教えていただければ幸いです。

http://www.ynk.ic.kanagawa-it.ac.jp/~kasuga/kmeans.html
はいかがですか。

　　　　　[このページのトップへ]

195.　Re^2: k-means法のアルゴリズム　　青木繁伸　　2002/10/17 (木) 23:22
例のごとく，エラー検出などをさぼって，R で書いてみる
K.means <- function(x, k, maxloop=100)
{
    pos <- function(dist)
    {
        min.dist <- min(dist)
        for (i in 1:k) {
            if (dist[i] == min.dist) {
                return(i)
            }
        }
    }

    n <- nrow(x)
    p <- ncol(x)
    dist <- 1:k
    group <- 1:n
    centroid <- matrix(1:(k*p), nr=k)
    for (i in 1:k) {
        centroid[i,] <- x[ceiling(runif(1)*n),]
    }
    w <- x
    for (loop in 1:maxloop) {
        centroid0 <- centroid
        for (i in 1:n) {
            for (j in 1:k) {
                dist[j] <- sum((x[i,]-centroid[j,])^2)
            }
            group[i] <- pos(dist)
        }
        for (j in 1:k) {
            w <- matrix(x[group == j,], nc=p)
            centroid[j,] <- apply(w, 2, mean)
        }
        if (all(abs((centroid-centroid0)/centroid) < 1e-5)) break
    }
    list(centroid=centroid, cluster=cbind(x, group))
}

　　　　　[このページのトップへ]

196.　Re^3: k-means法のアルゴリズム　　青木繁伸　　2002/10/17 (木) 23:29
K.means(x, k, maxloop=100)

x　データ行列
k　クラスター数
maxloop 収束計算の上限の回数（省略時は100）

=====使用例========
n <- 500
p <- 5
k <- 20
x <- matrix(rnorm(n*p), nr=n)
K.means(x, k)

　　　　　[このページのトップへ]

201.　Re^4: k-means法のアルゴリズム　　KAota　　2002/10/18 (金) 11:41
k-means法に関するURLを教えていただき，また，実際にコードまで書いていただきありがとうございます。とても助かりました。
そのURLには高速k-means法のアルゴリズムも記載されていて，とても勉強になります。
まずは単純そうなオーソドックスなk-means法のアルゴリズムを用いてプログラミングをしてみようと思います。
ありがとうございました。

　　　　　[このページのトップへ]

198.　Re^4: k-means法のアルゴリズム　　SIZMI　　2002/10/18 (金) 09:24
Rの配布パッケージにも含まれているのでは‥‥。

私のRは1.4.1バージョン（windows版）で古いんですが，
ディレクトリをたどると，

[rw1041] - [library]] - [mva] + [R-ex] -- kmeans.R
|
+ [html] -- kmeans.html

と2つの関連ファイルが見つかります。htmlは解説文書のようです。

ここで一つ，使い方講座を開設していただけないでしょうか。

　　　　　[このページのトップへ]

203.　Re^5: k-means法のアルゴリズム　　青木繁伸　　2002/10/18 (金) 11:59
> Rの配布パッケージにも含まれているのでは‥‥。

ありますね。

> ここで一つ，使い方講座を開設していただけないでしょうか。

ご希望にお答えして（簡単ですが..）
> library(mva) # mva ライブラリを使うことを指示
> x <- matrix(c(    # データ行列（2変数10ケース）
+     -0.639, -0.242,
+      1.320,  0.519,
+      0.775, -1.996,
+      0.126,  0.728,
+      1.117,  1.576,
+     -1.809,  0.595,
+     -0.016, -0.871,
+     -0.319, -0.280,
+     -1.438,  0.583,
+     -0.233,  0.905
+     ), byrow=TRUE, ncol=2)
> result <- kmeans(x, 3) # 結果を付値しておく
> result # 結果を書く
$cluster　各ケースがどのクラスターに属しているかのベクトル
 [1] 1 3 2 3 3 1 2 1 1 3

$centers　各クラスターの重心座標
    [,1]   [,2]
1 -1.051  0.164
2  0.380 -1.433
3  0.583  0.932

$withinss　各クラスターの群内平方和
[1] 2.153 0.946 2.331

$size　各クラスターの要素数
[1] 4 2 4

> plot(x, xlim=c(-2,2), ylim=c(-2,2)) # 二次元データならプロットしてみる
> text(x[,1], x[,2], result$cluster, pos=4, offset=0.5)

　　　　　[このページのトップへ]

202.　Re^5: k-means法のアルゴリズム　　KAota　　2002/10/18 (金) 11:57
> Rの配布パッケージにも含まれているのでは‥‥。

すみません。当方，実は，VBを使ったアプリケーションプログラマーで，統計の門外漢なのです。またRを持ち合わせておりません。よって解説講座の件はご希望に沿うことが出来ませんのでご了承ください。

ところでぶしつけではありますがR とは何なのでしょうか?簡単にその特徴など教えていただければ幸いです。

　　　　　[このページのトップへ]

204.　Re^6: k-means法のアルゴリズム　　青木繁伸　　2002/10/18 (金) 12:04
> ところでぶしつけではありますがR とは何なのでしょうか?簡単にその特徴など教えていただければ幸いです。

http://datamining.tama.ac.jp/~yama/R/
などを見るといいでしょう。そこには，
「R は統計計算とグラフィックスのためのフリーソフト(GNU-style copyleft)です. RはSに操作環境などが良く似ており, Sで動作するものはRでもほとんど変更なしに動作します. 」のように紹介されています。

私のサイトにも R のページがあります。
http://aoki2.si.gunma-u.ac.jp/R/index.html
非常にコンパクトにプログラムを書くことができます。

　　　　　[このページのトップへ]

205.　Re^7: k-means法のアルゴリズム　　KAota　　2002/10/18 (金) 12:42
Rのサイト拝見させていただきました。面白そうなので，ちょっとカジってみようと思います。
私のような統計の門外漢にも，丁寧にご回答くださりありがとうございます。
感謝いたします。

　　　　　[このページのトップへ]

● 「統計学関連なんでもあり」の過去ログ--- 021 の目次へジャンプ
● 「統計学関連なんでもあり」の目次へジャンプ
● 直前のページへ戻る