Evaluation of Stability of k-means Cluster Ensembles with Respect to Random Initialization

Kuncheva, L.; Vetrov, D.

Авторы: Kuncheva L., Vetrov D.
Журнал: IEEE Transactions on Pattern Analysis and Machine Intelligence
Том: 28
Номер: 11
Год издания: 2006
Издательство: Institute of Electrical and Electronics Engineers
Местоположение издательства: Piscataway, NJ, United States
Первая страница: 1
Последняя страница: 11
DOI: 10.1109/TPAMI.2006.226
Аннотация: Many clustering algorithms, including cluster ensembles, rely on a random component. Stability of the results across different runs is considered to be an asset of the algorithm. The cluster ensembles considered here are based on k-means clusterers. Each clusterer is assigned a random target number of clusters, k and is started from a random initialization. Here, we use 10 artificial and 10 real data sets to study ensemble stability with respect to random k, and random initialization. The data sets were chosen to have a small number of clusters (two to seven) and a moderate number of data points (up to a few hundred). Pairwise stability is defined as the adjusted Rand index between pairs of clusterers in the ensemble, averaged across all pairs. Nonpairwise stability is defined as the entropy of the consensus matrix of the ensemble. An experimental comparison with the stability of the standard k-means algorithm was carried out for k from 2 to 20. The results revealed that ensembles are generally more stable, markedly so for larger k. To establish whether stability can serve as a cluster validity index, we first looked at the relationship between stability and accuracy with respect to the number of clusters, k. We found that such a relationship strongly depends on the data set, varying from almost perfect positive correlation (0.97, for the glass data) to almost perfect negative correlation (-0.93, for the crabs data). We propose a new combined stability index to be the sum of the pairwise individual and ensemble stabilities. This index was found to correlate better with the ensemble accuracy. Following the hypothesis that a point of stability of a clustering algorithm corresponds to a structure found in the data, we used the stability measures to pick the number of clusters. The combined stability index gave best results
Добавил в систему: Ветров Дмитрий Петрович

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ИНХС РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

ИСТИНА ИНХС РАН

Evaluation of Stability of k-means Cluster Ensembles with Respect to Random Initializationстатья