自分のkmeansアルゴリズムを書くR

Question

私は最初のkmeansアルゴリズムをRで書いてみようとしています。私はこの分野では新しいので、明白ではないと私を判断してはいけません。

アルゴリズムは2つのベクトルx,yを受け取り、各データ点のクラスタ中心までの距離を計算し、その中心からデータ点までの距離を最小にしてクラスタを割り当てます。アルゴリズムは、割り当てに変化がなく、したがってクラスタ中心に変化がないときに停止する。

# Sample data  
set.seed(100) 
xval <- rnorm(12, mean = rep(1:3, each = 4), sd = 0.2) 
yval <- rnorm(12, mean = rep(c(1,2,1), each = 4), sd = 0.2) 

# Kmeans function 
kclus <- function(x, y, nclus) { 

    # start with random cluster centers 
    xcen <- runif(n = nclus, min = min(x), max = max(x)) 
    ycen <- runif(n = nclus, min = min(y), max = max(y)) 

    # data points and cluster assignment in "data" 
    # cluster coordinates in "clus" 
    data <- data.frame(xval = x, yval = y, clus = NA) 
    clus <- data.frame(name = 1:nclus, xcen = xcen, ycen = ycen) 

    finish <- FALSE 

    while(finish == FALSE) { 

     # assign cluster with minimum distance to each data point 
     for(i in 1:length(x)) { 
      dist <- sqrt((x[i]-clus$xcen)^2 + (y[i]-clus$ycen)^2) 
      data$clus[i] <- which.min(dist) 
     } 

     xcen_old <- clus$xcen 
     ycen_old <- clus$ycen 

     # calculate new cluster centers 
     for(i in 1:nclus) { 
      clus[i,2] <- mean(subset(data$xval, data$clus == i)) 
      clus[i,3] <- mean(subset(data$yval, data$clus == i)) 
     } 

     # stop the loop if there is no change in cluster coordinates 
     if(identical(xcen_old, clus$xcen) & identical(ycen_old, clus$ycen)) finish <- TRUE 
    } 
    data 
} 

# apply kmeans function to sample data 
cluster <- kclus(xval, yval, 4) 

# plot the result 
ggplot(cluster, aes(xval, yval, color = as.factor(clus))) + geom_point() 

これはこれまで比較的うまくいきました。しかし、私はどのように特定の数のクラスタにアルゴリズムを強制することができないのか、手がかりはありません。私のkclus()機能ではすでにパラメータnclusとして実装されていますが、どのように使用するのか分かりません。

与えられたサンプルデータについて、このアルゴリズムは私に3つのクラスターを与えます。私は彼に私に4つのクラスターを戻すように強制したい。私はその上の助言を与えることができ、ここで

誰？

は 、そんなに作品を、kは、意味だけの方法であるマーカス

Answer 1

これは、実装したアルゴリズムが常に3つのクラスタを提供するというわけではありません。十分な回数実行していない可能性があります。

# Sample data  
set.seed(100) 
xval <- rnorm(12, mean = rep(1:3, each = 4), sd = 0.2) 
yval <- rnorm(12, mean = rep(c(1,2,1), each = 4), sd = 0.2) 

# Kmeans function with random.seed for initialization 
kclus <- function(x, y, nclus, random.seed=123) { 

    set.seed(random.seed) 
    # start with random cluster centers 
    xcen <- runif(n = nclus, min = min(x), max = max(x)) 
    ycen <- runif(n = nclus, min = min(y), max = max(y)) 

    # data points and cluster assignment in "data" 
    # cluster coordinates in "clus" 
    data <- data.frame(xval = x, yval = y, clus = NA) 
    clus <- data.frame(name = 1:nclus, xcen = xcen, ycen = ycen) 

    finish <- FALSE 

    while(finish == FALSE) { 

    # assign cluster with minimum distance to each data point 
    for(i in 1:length(x)) { 
     dist <- sqrt((x[i]-clus$xcen)^2 + (y[i]-clus$ycen)^2) 
     data$clus[i] <- which.min(dist) 
    } 

    xcen_old <- clus$xcen 
    ycen_old <- clus$ycen 

    # calculate new cluster centers 
    for(i in 1:nclus) { 
     clus[i,2] <- mean(subset(data$xval, data$clus == i)) 
     clus[i,3] <- mean(subset(data$yval, data$clus == i)) 
    } 

    # stop the loop if there is no change in cluster coordinates 
    if(identical(xcen_old, clus$xcen) & identical(ycen_old, clus$ycen)) finish <- TRUE 
    } 
    data 
} 

# with default random seed 123, you should be able to reproduce the result 
# as you can see, in this case, no data points were assigned to the 4th cluster 
cluster <- kclus(xval, yval, 4) 
cluster.centers <- aggregate(.~clus, cluster, mean) 
ggplot(cluster, aes(xval, yval, color = as.factor(clus))) + 
    geom_point(size=5) + 
    geom_point(data=cluster.centers, aes(xval, yval, col=as.factor(clus)), pch=8, size=5) 

：ここでは、クラスタの出力の数は（ランダムに選択され、random.seedで制御することができる）、クラスタ重心の初期化に依存していることを見ることができるようにしなければならない、あなたのコードのわずかな変更があります

# run with a different random seed = 12 
# as you can see, in this case, the algorithm outputs 4 clusters, with the 2nd cluster having a single datapoint assigned to 
    cluster <- kclus(xval, yval, 4, 12) 
    cluster.centers <- aggregate(.~clus, cluster, mean) 
    ggplot(cluster, aes(xval, yval, color = as.factor(clus))) + 
     geom_point(size=5) + 
     geom_point(data=cluster.centers, aes(xval, yval, col=as.factor(clus)), pch=8, size=5) 

# run with a different random seed = 12345 
# as you can see, in this case, the algorithm outputs 2 clusters, with the all the datapoints assigned to the 1st and the 2nd cluster 
    cluster <- kclus(xval, yval, 4, 12345) 
    cluster.centers <- aggregate(.~clus, cluster, mean) 
    ggplot(cluster, aes(xval, yval, color = as.factor(clus))) + 
     geom_point(size=5) + 
     geom_point(data=cluster.centers, aes(xval, yval, col=as.factor(clus)), pch=8, size=5) 

上記の例からわかるように、クラスタがコンバージェンス時にポイントが割り当てられずに終わるかどうかは、初期中心位置およびデータ分布によって決まります。一般に、kmeansが1つのクラスタ重心を空にすると、空のクラスタに1つのポイントを強制的に割り当てようとすると、品質クラスターの品質が低下する可能性があります。

この時点で試すことができることがいくつかあります。

1. まずアルゴリズムを複数回ランダムに初期化したセンターで実行し、最高のクラスター品質（SSEなどで測定）の結果を選択できます。
2. もう1つお試しできるのは、 Kmeans ++のスマートな初期化です。 A-それほど良くない-選択は、クラスタの再割り当ては、それが kのそれぞれは、（= 4）のクラスタがそれにasigned少なくとも1点を持っている（そうでない場合は、その後 ことを保証しながら、確実 にあなたのアルゴリズムを変更することができ
3. 再割り当てしないでください）。
4. 最後に、 階層型クラスタリングのような他のアルゴリズムを試すと、 樹枝図を使用してより多くの柔軟性を与え、必要な数のクラスタを選択できます。

Answer 2

、ありがとうございました。あなたには2つの主要な選択肢があります。クラスタ数が要求されたクラスタ数を下回るたびに、より少ないクラスタ数であるまたはが有効になったら、新しいクラスタを開始します。新しいものを始めるには、その中心から最も離れた点を見つけて、それを新しいクラスターに変更します。しかし、これには問題があります。あなたが20ポイントを持っていて、ユーザーが25クラスタを要求したとします。あなたはただいくつかの人々を満足させることはできません。

Answer 3

問題は初期化です。

乱数で初期化することは、データが均一にランダムに分散されていない場合（クラスタを持たない場合）は最悪の選択です。

左上隅に中心を生成すると、0点があり、コードは次にNaN平均を生成します。

代わりに、データをkポイントとしてを選択してみてください。これは悪くなる可能性は非常に低いです（ただし可能です）。