K-means: Các trung tâm ban đầu không khác biệt

Question

Tôi đang sử dụng GA Package và mục tiêu của tôi là tìm vị trí ban đầu tối ưu cho các thuật toán phân cụm k. Dữ liệu của tôi là một thưa thớt-ma trận của các từ trong số TF-IDF và tải here. Dưới đây là một số trong những giai đoạn tôi đã thực hiện:

0. Thư viện và tập dữ liệu

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

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

1. Mã hóa nhị phân và tạo số lượng ban đầu.

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. Thể Function Giảm thiểu Davies-Bouldin (DB) Index. Nơi tôi đánh giá DBI cho mỗi giải pháp được tạo ra từ initial_population.

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. Chạy GA. Với các cài đặt này.

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. Vấn đề. Lỗi trong km (corpus [-1], initial_centroid): trung tâm ban đầu không khác biệt`.

Tôi đã tìm thấy sự cố tương tự here, trong đó người dùng cũng phải sử dụng thông số để tự động chuyển số lượng cụm để sử dụng. Nó được giải quyết bằng cách mã hóa cứng số lượng các cụm. Tuy nhiên đối với trường hợp của tôi, tôi thực sự cần phải tự động chuyển số lượng cụm, vì nó đến từ một vector nhị phân được tạo ngẫu nhiên, trong đó 1's sẽ đại diện cho các centroid đầu tiên.

Kiểm tra với kmeans()code, tôi nhận thấy rằng lỗi là do các trung tâm trùng lặp:

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

Tôi chỉnh sửa các chức năng kmeans với trace để in ra các trung tâm nhân đôi. Kết quả:

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

nào cho thấy không có sự trùng lặp trong lựa chọn ngẫu nhiên initial_centroids và tôi không có ý tưởng tại sao lỗi này tiếp tục xảy ra. Có điều gì khác dẫn đến lỗi này không?

P/S: Tôi hiểu một số người có thể đề xuất GA + K-means không phải là một ý tưởng hay. Nhưng tôi hy vọng sẽ hoàn thành những gì tôi đã bắt đầu. Tốt hơn là xem vấn đề này như một vấn đề K-means (ít nhất là trong việc giải quyết lỗi initial centers are not distinct).

Answer 1

Thuật toán di truyền không phù hợp để tối ưu hóa phương tiện k do tính chất của vấn đề - hạt khởi tạo tương tác quá nhiều, ga sẽ không tốt hơn lấy mẫu ngẫu nhiên của tất cả các hạt giống có thể.

Vì vậy, lời khuyên chính của tôi là không sử dụng các thuật toán di truyền ở đây!

Nếu bạn nhấn mạnh, những gì bạn cần làm là phát hiện các thông số xấu, sau đó chỉ cần trả lại điểm xấu để khởi tạo xấu để chúng không "tồn tại".

Answer 2

Để trả lời câu hỏi của bạn chỉ làm:

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

của bạn 520 và 564 hàng corpus đều giống nhau, với sự khác biệt duy nhất trong một thuộc tính row.names, xem:

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

Về GA và k-means, xem ví dụ:

1. Bashar Al-Shboul, Myaeng Sung-Hyon, "Initializing K-Means using Genetic Algorithms", World Academy of Science, Engineering & Technology, Jun2009, Issue 30, p. 114, (đặc biệt là phần II B); hoặc
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