[WEKA] 클러스터링 알고리즘 - 클러스터 수 결정하기

 

 

클러스터링 알고리즘

다음은 WEKA에서 지원하는 클러스터링 알고리즘들이다.

 

CLOPE

Cobweb

DBSCAN

EM

FarthestFirst

FilteredClusterer

HierarchicalClusterer

MakeDensityBasedClusterer

OPTICS

sIB

SimpleKMeans

XMeans

 

 

 

자동으로 클러스터 수를 결정하는 알고리즘

자동으로 클러스터 수가 결정되는 알고리즘의 성능을 비교하는 실험을 진행하기 위해 실험에 앞서 우선 WEKA에서 지원하는 클러스터링 알고리즘 중에서 자동으로 클러스터 수가 결정되는 알고리즘을 찾아보았다.

그동안 내가 공부해왔던 것과 WEKA 툴 메뉴얼에 설명되어 있는 것으로 보았을 때 WEKA에서 자동으로 클러스터 수가 결정되는 듯한 것은 EM 알고리즘과 X-means 알고리즘이다.

 

 

1) EM 알고리즘

EM 알고리즘은 원하는 클러스터 수를 numClusters 파라미터로 넣을 수도 있지만, numClusters에 -1을 기입하면 cross-validation을 통해 가장 적합한 클러스터 수를 자동으로 생성해낸다.

 numClusters : set number of clusters. -1 to select number of clusters automatically by cross validation.

 

2) XMeans 알고리즘

또한 그동안 클러스터링 관련연구를 보면서 『Software Fault Prediction of Unlabeled Program Modules』에서 보았듯이 XMeans 알고리즘 역시 클러스터 수 결정이 자동화된다.

 

* 관련 연구

1. Software Fault Prediction of Unlabeled Program Modules, C. Catal, U. Sevim, and B. Diri

 ... X-means: One drawback of k-means algorithm is the selection of the number of clusters, k, as an input parameter. Pelleg and Moore [12] developed an algorithm to solve this problem and used the Bayesian Information Criterion (BIC) or the Akaike Information Criterion (AIC) measure for optimization [9]. Rather than choosing the specific number of clusters, k, x-means needs kmin and kmax values. The algorithm starts with kmin value and adds centroids if needed. The BIC or Schwarz criterion is applied to split some centroids into two and hence new centroids are created [9]. Final centroid set is the one that has the best score....

 

2. X-means: Extending K-means with Efficient Estimation of the Number of Clusters (2000) by Dau Pelleg , Andrew Moore

  Despite its popularity for general clustering, K-means suffers three major shortcomings; it scales poorly computationally, the number of clusters K has to be supplied by the user, and the search is prone to local minima. We propose solutions for the first two problems, and a partial remedy for the third. Building on prior work for algorithmic acceleration that is not based on approximation, we introduce a new algorithm that efficiently, searches the space of cluster locations and number of clusters to optimize the Bayesian Information Criterion (BIC) or the Akaike Information Criterion (AIC) measure. The innovations include two new ways of exploiting cached sufficient statistics and a new very efficient test that in one K-means sweep selects the most promising subset of classes for refinement. This gives rise to a fast, statistically founded algorithm that outputs both the number of classes and their parameters. Experiments show this technique reveals the true number of classes in the underlying distribution, and that it is much faster than repeatedly using accelerated K-means for different values of K.

 

 

추가적으로!

CLOPE, Cobweb, DBSCAN, OPTICS은 numClusters 파라미터가 따로 있진 않지만 결국 사용자가 넣은 파라미터에 따라 결정된다. 맞나? 좀 더 찾아봐야겠다.

 

 

 

WKEA에서 지원하는 클러스터링 알고리즘 비교가 되어있는 저널을 찾았다. 살펴 봐야지!

http://www.ijetae.com/files/Volume2Issue5/IJETAE_0512_13.pdf