K-означает: начальные центры не различаются

Question

Я использую GA Package, и моя цель - найти оптимальные начальные позиции центроидов для алгоритма кластеризации k-средних. Мои данные разреженная матрица слов в 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. Фитнес Функция Минимизирует Davies-Bouldin (DB) Index. Где я оцениваю DBI для каждого решения, полученного от 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. Запуск 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 (corpus [-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 - это не очень хорошая идея. Но я надеюсь закончить то, что начал. Лучше рассматривать эту проблему как проблему K-средних (ну, по крайней мере, при решении ошибки initial centers are not distinct).

Answer 1

Генетические алгоритмы не очень подходят для оптимизации k-средних по характеру проблемы - семена инициализации слишком много взаимодействуют, ga не будет лучше, чем выбор случайной выборки всех возможных семян.

Так что мой основной совет - не использовать генетические алгоритмы вообще здесь!

Если вы настаиваете, что вам нужно будет сделать, это обнаружить плохие параметры, а затем просто вернуть плохую оценку для плохой инициализации, чтобы они не «выжили».

Answer 2

Чтобы ответить на ваш вопрос просто сделать:

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

Your 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-сред, см., например:

1. Bashar Al-Shboul, Myaeng Sung-Hyon, "Initializing K-Means using Genetic Algorithms", World Academy of Science, Engineering & Technology, Jun2009, Issue 30, p. 114, (особенно раздел II B); или
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