K-means：初始中心並不明顯

Question

我正在使用GA Package，我的目標是找到k-means聚類算法的最佳初始質心位置。我的數據是在TF-IDF得分的話稀疏矩陣和可下載here.下面是一些我已經實現了階段：

0庫和數據集

library(clusterSim)   ## for index.DB() 
library(GA)     ## for ga() 

corpus <- read.csv("Corpus_EnglishMalay_tfidf.csv")  ## a dataset of 5000 x 1168 

1.二進制編碼並生成初始種羣。

k_min <- 15 

initial_population <- function(object) { 
    ## generate a population to turn-on 15 cluster bits 
    init <- t(replicate(object@popSize, sample(rep(c(1, 0), c(k_min, object@nBits - k_min))), TRUE)) 
    return(init) 
} 

2.健身功能最大限度地減少戴維斯 - 爾丁（DB）指數。我在哪裏評估從initial_population生成的每個解決方案的DBI。

DBI2 <- function(x) { 
    ## x is a vector of solution of nBits 
    ## exclude first column of corpus 
    initial_centroid <- corpus[x==1, -1] 
    cl <- kmeans(corpus[-1], initial_centroid) 
    dbi <- index.DB(corpus[-1], cl=cl$cluster, centrotypes = "centroids") 
    score <- -dbi$DB 
    return(score) 
} 

3.運行GA。使用這些設置。

g2<- ga(type = "binary", 
    fitness = DBI2, 
    population = initial_population, 
    selection = ga_rwSelection, 
    crossover = gabin_spCrossover, 
    pcrossover = 0.8, 
    pmutation = 0.1, 
    popSize = 100, 
    nBits = nrow(corpus), 
    seed = 123) 

4.問題。 kmeans（語料庫[-1]，initial_centroid）中的錯誤：初始中心不明確。

我發現了一個類似的問題here，其中用戶還必須使用一個參數動態傳遞要使用的簇數。這是通過硬編碼簇的數量來解決的。但是對於我的情況，我確實需要動態傳遞簇的數量，因爲它是從隨機生成的二進制向量中進入的，其中那些1's將表示初始質心。

與kmeans()code檢查，我注意到，錯誤是由重複的中心造成的：

if(any(duplicated(centers))) 
     stop("initial centers are not distinct") 

我編輯的kmeans功能與trace打印出複製中心。輸出：

[1] "206" "520" "564" "1803" "2059" "2163" "2652" "2702" "3195" "3206" "3254" "3362" "3375" 
[14] "4063" "4186" 

這都說明在隨機選擇initial_centroids沒有重複，我不知道爲什麼這個錯誤持續發生。還有什麼會導致這個錯誤？

P/S：我明白有些人可能會建議GA + K-means並不是一個好主意。但我希望能完成我已經開始的工作。最好把這個問題看作K均值問題（至少在解決initial centers are not distinct錯誤時）。

Answer 1

遺傳算法不適合根據問題的性質優化k-均值 - 初始化種子相互作用太多，ga不會比隨機取樣所有可能的種子好。

所以我的主要建議是不要在這裏使用遺傳算法！

如果你堅持，你需要做的是檢測不良參數，然後簡單地返回一個壞分數，因爲它不會「生存」。

Answer 2

要回答你的問題只是做：

any(corpus[520, -1] != corpus[564, -1]) 

你的520和564行的corpus是相同的，在屬性row.names唯一的區別，請參閱：

identical(colnames(corpus[520, -1]), colnames(corpus[564, -1])) # just to be sure 
rownames(corpus[520, -1]) 
rownames(corpus[564, -1]) 

關於GA和k-means，參見例如：

1. Bashar Al-Shboul, Myaeng Sung-Hyon, "Initializing K-Means using Genetic Algorithms", World Academy of Science, Engineering & Technology, Jun2009, Issue 30, p. 114，（特別是第IIB部分）;或
2. BAIN KHUSUL KHOTIMAH, FIRLI IRHAMNI, AND TRI SUNDARWATI, "A GENETIC ALGORITHM FOR OPTIMIZED INITIAL CENTERS K-MEANS CLUSTERING IN SMEs", Journal of Theoretical and Applied Information Technology, 2016, Vol. 90, No. 1