Zasadniczym celem analizy skupień jest taki podział obiektów, który zapewnia maksymalną homogeniczność obiektów w wyróżnionych skupieniach i maksymalną heterogeniczność między skupieniami. Metody realizujące tą strategię nazywamy ogólnie metodami podziałowymi. Jedną z klasycznych i najczęściej stosowanych metod podziałowych jest metoda k-średnich. Jakość klasyfikacji obiektów uzyskana dzięki metodzie k-średnich zależy od wielu czynników. Do ważniejszych z nich należy zaliczyć: 1) wstępny (prototypowy) podział obiektów na skupienia, 2) kolejność obiektów w zbiorze danych, 3) metodę przenoszenia obiektów między skupieniami a także 4) przyjęte kryterium optymalności podziału obiektów. Każdy z wymienionych czynników wskazuje na problem z podziałem zbioru obiektów i w ramach każdego z nich znane jest kilka rozwiązań tego problemu. Z tego powodu nie istnieje jedna metoda k-średnich. Nazwa ta wskazuje raczej na pewien sposób postępowania prowadzący do podziału obiektów niż konkretną jego realizację. Niestety w praktyce przyjęło się rozumienie tej metody jedynie dla algorytmu MacQueen’a, który jest przecież tylko jedną z możliwych realizacji metody k-średnich. Wyrazem tego stanu jest fakt, że w kluczowych pakietach statystycznych znajduje się jedynie ten algorytm, co wydaje się zbytnim uproszczeniem.

Celem prezentowanych badań jest przegląd i krytyczna ocena różnych implementacji algorytmu k-średnich, uwzględniających powyższe cztery kluczowe czynniki wpływające na jakość uzyskanego grupowania. Analiza będzie oparta na danych symulacyjnych i empirycznych o znanej strukturze grupowej. Uzyskane struktury grupowe będą oceniane wskaźnikami jakości grupowania: Silhouette, Davies’a-Bouldin’a, Calinski’ego-Harabasza i Hubert’a-Levin’a a także porównywane ze wzorcem w oparciu o indeksy Rand’a, Jaccard’a i Fowkles’a-Mallows’a. Uzyskane wyniki powinny pomóc w lepszym zrozumieniu i właściwym stosowaniu algorytmów k-średnich.

Literatura:

1. Fisher D., Xu L., Zard N. (1992). Ordering effects in clustering. Proceedings of the Nineth International Conference on Machine Learning. Morgan Kauffman, San Mateo, USA, s. 163-168
2. Gordon A.D. (1999). Classification. 2^nd Edition, Chapman & Hall, London
3. MacQueen J. (1967). Some methods for classification and analysis of multivariate observations, in: L.M. LeCam, J. Neyman (Eds.), Proceedings of the Fifth Berkeley Symposium on Mathe,atical Statistics and Probability, vol. 1-Statistics, UCLA Press, Berkeley, USA, s. 281-297
4. Peña J.M., Lozano J.A., Larrañaga P. (1999). An empirical comparison of four initialization methods for the k-means algorithm. Pattern Recognition Lett. 20, s. 1027-1040
5. Selim S.Z., Ismail M.A. (1984). K-means type algorithm: generalized convergence theorem and characterization of local optimality, IEEE Trans. Pattern Anal. Mach. Intell. 6, s. 81-87
6. Tarsitano A. (2003). A computational study of several relocation methods for k-means algorithms. Pattern Recognition 36, s. 2955-2966

• Legal notice:
  

  Copyright (c) Pielaszek Research, all rights reserved.
  The above materials, including auxiliary resources, are subject to Publisher's copyright and the Author(s) intellectual rights. Without limiting Author(s) rights under respective Copyright Transfer Agreement, no part of the above documents may be reproduced without the express written permission of Pielaszek Research, the Publisher. Express permission from the Author(s) is required to use the above materials for academic purposes, such as lectures or scientific presentations.
  In every case, proper references including Author(s) name(s) and URL of this webpage: https://science24.com/paper/10603 must be provided.