K-means

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

k-means (anglicky „k průměrů“) je často používaný algoritmus nehierarchické shlukové analýzy. Předpokládá, že shlukované objekty lze chápat jako body v nějakém eukleidovském prostoru a že počet shluků k je předem dán (případně lze vyzkoušet různá k, pro každé spustit algoritmus znovu a výsledky porovnat). Shluky jsou definovány svými centroidy, což jsou body ve stejném prostoru jako shlukované objekty. Objekty se zařazují do toho shluku, jehož centroidu jsou nejblíže. Algoritmus postupuje iterativně tak, že se vyjde z nějakých (obvykle náhodně zvolených) centroidů, přiřadí do nich body, přepočítá centroidy tak, aby šlo o těžiště shluku bodů, pak opět přiřadí body k nově stanoveným centroidům a tak dál, až dokud se poloha centroidů neustálí.

Konvergence algoritmu je zaručena a v praxi bývá obvykle poměrně rychlá. Nemusí však najít globální optimum ve smyslu nejmenšího součtu čtverců vzdáleností od centroidů a navíc pro různé volby počátečních centroidů mohou vzniknout různá řešení.

Pojem k-means poprvé použil James MacQueen roku 1967,[1] a myšlenka pochází od Huga Steinhause (1957).[2] Popsaný základní algoritmus navrhl Stuart Lloyd z Bell Labs roku 1957 (publikováno až 1982).[3] Roku 1965 E. W. Forgy uveřejnil stejnou metodu, proto se někdy nazývá Lloydův-Forgyho algoritmus.[4] Efektivnější verzi navrhli a ve Fortranu naprogramovali Hartigan a Wong (1975/1979).[5]

Reference[editovat | editovat zdroj]

  1. MacQueen, J. B. (1967). "Some Methods for classification and Analysis of Multivariate Observations" in Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. 1: 281–297, University of California Press. Retrieved on 2009-04-07. 
  2. Steinhaus, H. (1957).  "Sur la division des corps matériels en parties"(in French). Bull. Acad. Polon. Sci. 4 (12): 801–804. 
  3. Lloyd, S. P. (1957).  "Least square quantization in PCM". Bell Telephone Laboratories Paper.  Published in journal much later: Lloyd., S. P. (1982).  "Least squares quantization in PCM". IEEE Transactions on Information Theory 28 (2): 129–137. doi:10.1109/TIT.1982.1056489. 
  4. E.W. Forgy (1965).  "Cluster analysis of multivariate data: efficiency versus interpretability of classifications". Biometrics 21: 768–769. 
  5. J.A. Hartigan(1975). Clustering algorithms. John Wiley & Sons, Inc..