k-vidurkių klasterizavimas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Jump to navigation Jump to search


 Orange Icon Edit.svg  Manoma, kad šis straipsnis yra beviltiškas.
Jo turinys, struktūra, stilius ar kitos savybės yra tokios, kad jo neįmanoma pritaikyti enciklopedijai.
Priežastis atskirai nesukonkretinta, bet jei ji neakivaizdi, tai gali būti nurodyta istorijoje ar aptarime.
Jei galite parašyti šį straipsnį iš naujo, tegul ir kelis kartus mažesnį, taip ir padarykite!

k-vidurkių klasterizavimas (angl. k-means clustering) – vektorių kvantavimo metodas, kuris yra populiarus duomenų gavyboje (angl. data mining): klasterių analizėje. k-vidurkių klasterizavimo tikslas yra padalinti n objektų į k klasterių (grupių), kur kiekvienas objektas priklauso tam klasteriui, kurio vidurkis jam yra arčiausias. Vidurkis čia atspindi klasterio prototipą. k-vidurkių klasterizavimo algoritmo rezultatas yra duomenų erdvės padalinimas į Voronoi sritis.

k-vidurkių algoritmas yra laikomas EM (angl. expectation-maximization) algoritmo supaprastinimu, kai klasteriai dalinami į panašaus dydžio sritis, tuo tarpu EM metodas leidžia klasteriams būti skirtingų formų.

k-vidurkių algoritmas kartais maišomas su k-arčiausių kaimynų klasifikatoriumi, kuris yra gana populiarus mašininio mokymo metodas. Metodai yra maišomi, greičiausiai, dėl k raidės pavadinimuose. Nors, galima pritaikyti 1-artimiausio kaimyno (k=1) klasifikatorių, kai norima naują įrašą priskirti kuriam nors jau egzistuojančiam klasteriui (pirmiau suklasterizavus k-vidurkių algoritmu), matuojant objekto atstumą iki klasterių centrų. Toks metodas yra žinomas artimiausio centroido (ar tiesiog centro) klasifikatoriumi arba Rocchio algoritmu.[reikalingas šaltinis].

Aprašymas[redaguoti | redaguoti vikitekstą]

Duotas stebėjimų rinkinys (x1, x2, ..., xn), kur kiekvienas stebinys yra d-matis vektorius. k-vidurkių algoritmo tikslas yra išskirstyti (padalinti) visus n stebinių rinkinį į k (≤ n) poaibių S = {S1, S2, ..., Sk}  taip, kad būtų minimizuojama klasterių objektų atstumų nuo centrų kvadratų suma (angl. within-cluster sum of squares, WCSS). Kitaip tariant, ieškoma

kur μi - yra taškų vidurkis klasteryje Si.

Istorija[redaguoti | redaguoti vikitekstą]

Sąvoka ,,k-vidurkiai’’ pirmą kartą buvo pavartota mokslininko James MacQueen (1967 m.),[1] nors idėja buvo pristatyta kiek anksčiau, 1957-aisiais (Hugo Steinhaus).[2] Standartinis algoritmas pirmą kartą buvo pristatytas 1957 m. Atuart Lloyd jį prostate kaip metodą kodinei impulsinei moduliacijai, tačiau iki 1982-ųjų metų už Bell Labs kompanijos ribų nebuvo publikuotas[3].  1965-aisiais E. W. Forgy publikavo iš esmės tokį patį metodą, todėl algoritmas kartais vadinamas Lloyd-Forgy metodu.[4] Efektyvesnė metodo versija FORTRAN kalba vėliau buvo pasiūlyta ir publikuota Hartigan ir Wong.[5][6]

Algoritmas[redaguoti | redaguoti vikitekstą]

Standartinis algoritmas[redaguoti | redaguoti vikitekstą]

Dažniausias algoritmas naudoja iteratyvaus tobulinimo metodą. Dėl savo paplitimo dažnai vadinamas k-vidurkių algoritmu, taip pat gali būti sutinkamas Lloyd‘o algoritmo pavadinimu, pastarasis pavadinimas ypač paplitęs kompiuterių mokslo bendruomenėje. 

Duotas pradinis k vidurkių (centrų) rinkinys m1(1),...,m,k(1) Algoritmas veikia kartojant du etapus vieną po kito:[7]

Priskyrimo etapas: priskirti kiekvieną stebėjimą tam vidurkiui (centrui) kad WCSS būtų mažiausias. Jei, sakysime, kad atstumas matuojamas kvadratiniu Euklido atstumu, kiekvienas stebinys bus priskirtas prie pačio arčiausio centro.
[8] Matematiškai, tai reiškia stebėjimų dalinimą į Voronoi diagramą sugeneruotą pagal vidurkius.


kur kiekvienas yra priskiriamas tik vienam klasteriui , net jei iš tiesų jis gali būti priskirtas dviems ar daugiau.
Atnaujinimo etapas: apskaičiuoti sudarytų klasterių vidurkį, kuris bus laikomas naujuoju stebėjimų centroidu (centru):

Kadangi aritmetinis vidurkis yra mažiausių kvadratų įvertinys, toks atnaujinimas leidžia sumažinti WCSS tikslo funkcijos reikšmę. Algoritmas sukonverguoja tada, kai stebėjimai nebekeičia klasterių, o ir patys klasterių centrai nebesikeičia. Kadangi abu etapai (priskyrimo ir atnaujinimo) siekia optimizuoti (minimizuoti) WCSS įvertį ir egzistuoja tik baigtinis skaičius dalinimų, tai algoritmas konverguoja į lokalų optimumą. Šio algoritmo naudojimas negarantuoja globalaus optimumo suradimo.

Algoritmas dažnai pristatomas, kaip priskiriantis stebinius prie artimiausio klasterio pagal atstumą. Standartinis algoritmas siekia minimizuoti WCSS vertę, todėl stebiniai ir yra priskyrimi pagal mažiausią kvardatų sumą, kas yra ekvivalentu priskyrimui pagal mažiausią Euklidinį atstumą. Atsižvelgiant į poreikį panaudoti kitus atstumo matavimo matus, buvo pristatytos įvairios k-vidurkių algoritmo versijos, pvz., sferinis k-vidurkių algoritmas, kuris naudoja kosinusinį panašumo matą.[reikalingas šaltinis]

Iniciacijos metodai[redaguoti | redaguoti vikitekstą]

Dažniausiai naudojamas iniciacijos metodas yra Forgy ir atsitiktinis dalinimas.[9]  Forgy metodas atsitiktinai pasirenka k stebinių iš duomenų rinkinio ir juos naudoja kaip pradinius vidurkius (centrus). Atsitiktinio dalinimo metodas pirmiau atsitiktinai priskiria klasterį kiekvienam stebiniui ir tada atlieka atnaujinimo etapą taip apskaičiuojant pradinį vidurkį (centroidą) atsitiktinai priskirtiems klasterių stebiniams. Forgy metodas yra linkęs išsklaidyti plačiai pradinius vidurkius, tuo tarpu atsitiktinis dalinimas centrus talpina labiau stebinių pasiskirstymo erdvės centre. Pagal Hamerly et al.,[9] atsitiktinio dalinimo metodas labiau tinkamas (pageidaujamas) tokiems algoritmams, kaip k-harmininiai vidurkiai (angl., k-harmonic means) arba negriežtam k-vidurkių (angl. fuzzy k-means). EM ir standartiniam k-vidurkių algoritmui patogesnis (labiau pageidautinas) yra Forgy metodas.

Žinant, kad tai yra euristinis algoritmas, nėra garantijos, kad rezultatas konverguos į globalų optimumą ir rezultatas gali priklausyti nuo pradinių klasterių. Kadangi algoritmas, iš tiesų, yra labai greitas, yra priimtina jį atlikti keletą kartų su skirtingomis pradinėmis sąlygomis. Visgi, blogiausiu atveju, k-vidurkių algoritmas gali labai lėtai konverguoti: tam tikrais atvejais buvo parodyta, kad egzistuoja tam tikras taškų rinkinys (net ir 2-matėje erdvėje), kur k-vidurkių algoritmo konvergavimo laiko sąnaudos yra eksponentinės (t. y., 2Ω(n)).[10] Tačiau tokie taškų rinkiniai neturėtų būti randami praktikoje. Yra patvirtinta, kad suglodintas k-vidurkių algoritmo atlikimo laikas yra polinominis.[11]

Norint k-vidurkių algoritmą interpretuoti, kaip apibendrinto EM algoritmo variaciją, galima traktuoti, kad priskyrimo etapas atitinka tikėtinumo žingsnį (angl. expectation step) EM algoritme, o atnaujinimo etapas – maksimizavimo žingsnį (angl. maximization step).

Sudėtingumas[redaguoti | redaguoti vikitekstą]

Dėl skaičiavimų sudėtingumo, optimalaus sprendinio radimas stebėjimams d-matėje erdvėje yra:

  • NP-hard bendroje euklidinėje d-matėje erdvėje net dviems klasteriams.[12][13]
  • NP-hard bendrai klasterių skaičiui k, net 2-matėje erdvėje (plokštuma).[14]
  • Jei k ir d (dimensija) yra fiksuoti, uždavinys gali būti išspręstas per , kur n – klasterizuojamų stebinių skaičius, d – dimensija (stebinių matavimų skaičius), k – klasterių skaičius.[15]

Taigi, paprastai naudojami euristiniai algoritmai, kaip Lloyd. 

Pastarojo algoritmo atlikimo sudėtingumas vertinamas

Yra keletas įžvalgų apie Lloyd algoritmo sudėtingumą:

  • Lloyd algoritmas yra suglotinto ploinominio sudėtingumo.  Yra parodyta, kad[11] sutartam n taškų rinkiniui, kai ∀x∈, jei visi taškai nepriklausomai pasiskirstę pagal normalujį pasiskirstymą su vidurkiu 0 ir dispersija , tada tikėtinas k-vidurkių algoritmo atlikimo laikas yra  , kuris yra polinominis in n, k, d and .
  • Geresnės ribos yra įrodytos paprastesniais atvejais. Pavyzdžiui, yra parodyta, kad atlikimo laikas yra apribotas  kur n – stebinių skaičius sveikųjų skaičių gardelėje .

Lloyd algoritmas yra standartinis klasterizavimo k-vidurkiais uždavinio sprendimas. Nepaisant to, jis užtrunka labai daug laiko atstumams tarp taškų ir centrų skaičiavimui. Kadangi daug stebinių, paprastai, lieka tame pačiame klasteryje po keleto iteracijų, daug laiko yra išeikvojama nenaudingai. Yra metodo papildymų, kurie naudoja trikampio nelygybę ribų sukūrimui ir Lloyds algoritmo paspartinimui.[16][17][18]

Variantai[redaguoti | redaguoti vikitekstą]

  • Jenks natūralaus lūžio optimizacija: k-vidurkių algoritmas vienmačiams duomenims.
  • k-medianų klasterizavimas: vietoj vidurkių naudojamos medianos.
  • k-medoidai (dalinimas aplink medoidus, PAM) naudoja medoidus vietoj vidurkio ir tokiu būdu minimizuoja atstumų sumą.
  • Negriežtas C-vidurkių klasterizavimas: negriežta k-vidurkių algoritmo versija, kur kiekvienas stebinys turi tikimybę patekti (patekimo lygį) į kiekvieną iš klasterių.
  • Gauso mišinio modelis su EM palaiko tikimybinį stebinių priskyrimą klasteriams, vietoj deterministinio priskyrimo.
  • k-vidurkiai++ pasirenka pradinius centrus tokiu būdu, kad būtų pasiekta viršutinė WCSS funkcijos riba.
  • Filtravimo algoritmas naudoja kd-medžius pagreitinti kiekvienam iš k-vidurkių žingsnių.[19].
  • Sferinis k-vidurkių algoritmas yra tinkamas tekstiniams duomenims.[20]
  • Hierarchinis variantas, kaip atskiriantis k-vidurkių algoritmas,[21] x-vidurkių klasterizavimas [22] G-vidurkių klasterizavimas,[23]pakartotinai atskiria klasterius, kad sukurtų hierarchiją ir gali būti naudojami klasterių skaičiaus nustatymui.
  • Vidinis klasterių vertinimo matas, kaip klasterio siluetas gali būti naudingas nustatant klasterių skaičių.
  • Minkowski svertinis k-vidurkių algoritmas automatiškai apskaičiuoja klasterio požymių svorius remiantis idėja, kad požymiai gali būti nevienodai svarbūs.[24] Šie svoriai taip pat gali būti naudojami duotam duomenų rinkiniui perdaryti, klasterių skaičiaus pagrįstumui padidinti.[25]

Diskusijos[redaguoti | redaguoti vikitekstą]

Tipinis k-vidurkių algoritmo konvergavimo į lokalų minimumą pavyzdys. Šiame pavyzdyje klasterizavimas dešiniame paveikslėlyje prieštarauja akivaizdžiai klasterių struktūrai. Apskritimai yra duomenų taškai, žvaigždės yra centroidai (vidurkiai). Pradinė konfigūracija pateikta kairiame paveikslėlyje. Algoritmas konverguoja po penkių iteracijų pateiktose žiūrint iš kairės į dešinę. Paveikslėliai buvo paruošti su Mirkes Java applet.
k-vidurkių klasterizavimo rezultatas Iris gėlių duomenų rinkiniui ir faktinių rūšių vizualizuoja naudojantis ELKI. Klasterių vidurkiai pažymėti naudojant didesnius grupių simbolius.
Klasterizavimo palyginimas:k-vidurkių klasterizavimas ir EM klasterizavimas ant dirbtinių duomenų rinkinio ("pelė").

Trys esminiais k-vidurkių algoritmo požymiai, kurie verčia jį būti labai efektyviu yra didžiausi algoritmo trūkumai:

  • Euklidas atstumas naudojamas, kaip metrika ir dispersija, kuri naudojama kaip klasterių išsibarstymo matas.
  • Klasterių skaičius k turi būti žinomas iš anksto. Netinkamas klasterių skaičiaus nustatymas veda į blogus klasterizavimo rezultatus, todėl labai svarbu prieš klasterizavimą atlikti diagnostinius patikrinimuis, kad būtų galima nustatyti, bent jau apytiksliai, klasterių skaičių.
  • Konvergavimas į lokalų minimumą.

Esminis trūkumas yra metodo klasterių modelis. Koncepcija yra paremta sferiniais klasteriais, kurie yra atskirti tokiu būdu, kad kiekvieno klasterio vidurkis konverguotų į to klasterio centrą. Tikimasi, kad klasteriai yra panašaus (idealu, jei vienodo) dydžio, tada sprendimas objektą priskirti prie artimiausio klasterio yra tinkamas. Jei bandoma k-vidurkių algoritmą pritaikyti žinomiems Irisų duomenims, metodas dažnai klysta bandydamas atskirti tris klasterius (nors žinoma, kad duomnis sudaro trijų rūšių Irisų įrašai). Su k=2, du matomi klasteriai (kurių vienas talpina dvi Irisų rūšis) bus atskirti. Nepaisant fakto, kad duomenyse yra trys Irisų rūšys, k=2 yra labiau tinkamas klasterių skaičius, nei k=3. Tačiau, kitiems duomenis k-vidurkių algoritmas gali suveikti puikiai atskirdamas intuityviai nujaučiamas klases.

k-vidurkių algoritmo klasterizavimo rezultatai taip pat gali būti atvaizduojami Voronoi diagramomis. Kadangi duomenys yra atskirti, praktiškai, per vidurį tarp klastrių centrų, tai sub-optimalūs padalinimai ne visada yra tikslūs. Tuo tarpu EM algoritmas yra lankstesnis, nes leidžia nevienodas kovariacijas. Vizualiai pavaizdavus „pelių“ duomenis galima pamatyti Voronoi skirstymo ir EM padalinimo skirtumus.

Pritaikymas[redaguoti | redaguoti vikitekstą]

k-vidurkių klasterizavimas yra nesunkiai panaudojamas net ir su dideliais duomenų rinkiniais. Todėl jis buvo pritaikytas įvairiose srityse, kaip rinkos segmentavimas, geostatistika,,[26]  astronomija ir pan. Jis dažniausiai naudojamas kitų algoritmų pasiruošimo etape.

Vektorių kvantavimas[redaguoti | redaguoti vikitekstą]

k-vidurkių algoritmas atsirado iš signalų apdorojimo ir vis dar yra naudojamas šioje srityje. Pavyzžiui, kompiuterinėje grafikos, k-vidurkių algoritmas yra naudojamas padalinti spalvų paletę į nustatytą spalvų skaičių k. k-vidurkių algoritmas lengvai pritaikomas šiam uždaviniui ir sugeneruoja gana gerus rezultatus. 

Klasterių analizė[redaguoti | redaguoti vikitekstą]

Klasterinėje analizėje k-vidurkių algoritmas naudojamas duomenų rinkinį padalinti į k klasterių. Bet grynas k-vidurkių algoritmas nėra labai lankstus ir turi nemažai ribojimų.


Požymių išmokimas[redaguoti | redaguoti vikitekstą]

k-vidurkių algoritmas gali būti naudojamas požymių (arba žodyno) išmokimo etape. k-vidurkių panaudojimas gali būti kombinuojamas su tiesiniu klasifikatoriumi pusiau prižiūrimam mokymuisi sudaryti (natūralios kalbos apdorojimo uždavinyje). 

Programinė įranga[redaguoti | redaguoti vikitekstą]

Nemokama (atviro kodo) programinė įranga[redaguoti | redaguoti vikitekstą]

Sekančiose programinėse įrangose (kalbose) yra įgyvendintas k-vidurkių algoritmas (ir/arba jo variacijos), kodai yra atviri ir viešai prieinami.

  • Accord.NET.
  • CrimeStat.
  • ELKI.
  • Julia.
  • Mahout.
  • MLPACK.
  • OpenCV .
  • PSPP.
  • R.
  • SciPy ir scikit-learn.
  • Spark MLlib.
  • Torch.
  • Weka.

Mokamos programinės įrangos[redaguoti | redaguoti vikitekstą]

Sekančios programinės įrangos yra mokamos (su nuosavybės licenzijomis):

Šaltiniai[redaguoti | redaguoti vikitekstą]

  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. {{{booktitle}}} 1: 281–297, University of California Press. Tikrinta 2009-04-07. 
  2. Steinhaus, H.. „Sur la division des corps matériels en parties“ (French). Bull. Acad. Polon. Sci., 4 (12), 801–804 (1957). 
  3. Lloyd, S. P.. „Least square quantization in PCM“. Bell Telephone Laboratories Paper (1957). 
  4. E.W. Forgy. „Cluster analysis of multivariate data: efficiency versus interpretability of classifications“. Biometrics, 21, 768–769 (1965). 
  5. J.A. Hartigan (1975). Clustering algorithms. John Wiley & Sons, Inc..
  6. „Algorithm AS 136: A K-Means Clustering Algorithm“. Journal of the Royal Statistical Society, Series C, 28 (1), 100–108 (1979). 
  7. MacKay, David (2003). “Chapter 20. An Example Inference Task: Clustering”, Information Theory, Inference and Learning Algorithms. Cambridge University Press, 284–292. ISBN 0-521-64298-1.
  8. Since the square root is a monotone function, this also is the minimum Euclidean distance assignment.
  9. 9,0 9,1 (2002) "Alternatives to the k-means algorithm that find better clusterings". Proceedings of the eleventh international conference on Information and knowledge management (CIKM). 
  10. Vattani., A.. „k-means requires exponentially many iterations even in the plane“. Discrete and Computational Geometry, 45 (4), 596–616 (2011). DOI:10.1007/s00454-011-9340-1. 
  11. 11,0 11,1 (2009) "k-means has polynomial smoothed complexity". Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS). 
  12. „NP-hardness of Euclidean sum-of-squares clustering“. Machine Learning, 75, 245–249 (2009). DOI:10.1007/s10994-009-5103-0. 
  13. „Random Projection Trees for Vector Quantization“. Information Theory, IEEE Transactions on, 55, 3229–3242 (July 2009). DOI:10.1109/TIT.2009.2021326. 
  14. „The Planar k-Means Problem is NP-Hard“. Lecture Notes in Computer Science, 5431, 274–285 (2009). DOI:10.1007/978-3-642-00202-1_24. 
  15. (1994) "Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering" in Proceedings of 10th ACM Symposium on Computational Geometry. {{{booktitle}}}: 332–339. DOI:10.1145/177424.178042. 
  16. Phillips, Steven J. (2002-01-04). Acceleration of K-Means and Related Clustering Algorithms. Springer Berlin Heidelberg, 166–177. DOI:10.1007/3-540-45643-0_13. ISBN 978-3-540-43977-6.
  17. Elkan, C. (2003). "Using the triangle inequality to accelerate k-means". Proceedings of the Twentieth International Conference on Machine Learning (ICML). 
  18. Hamerly, Greg. „Making k-means even faster“. citeseerx.ist.psu.edu. Nuoroda tikrinta 2015-12-10. 
  19. Kanungo, T.; Mount, D. M.; Netanyahu, N. S.; Piatko, C. D.; Silverman, R.; Wu, A. Y.. „An efficient k-means clustering algorithm: Analysis and implementation“. IEEE Trans. Pattern Analysis and Machine Intelligence, 24, 881–892 (2002). DOI:10.1109/TPAMI.2002.1017616. Pasiektas 2009-04-24. 
  20. „Concept decompositions for large sparse text data using clustering“. Machine Learning, 42 (1), 143–175 (2001). DOI:10.1023/a:1007612920971. 
  21. Steinbach, M., Karypis, G., & Kumar, V. (2000, August).
  22. Pelleg, D., & Moore, A. W. (2000, June).
  23. Hamerly, G., & Elkan, C. (2004).
  24. „Minkowski Metric, Feature Weighting and Anomalous Cluster Initialisation in K-Means Clustering“. Pattern Recognition, 45 (3), 1061–1075 (2012). DOI:10.1016/j.patcog.2011.08.012. 
  25. „Recovering the number of clusters in data sets with noise features using feature rescaling factors“. Information Sciences, 324, 126–145 (2015). DOI:10.1016/j.ins.2015.06.039. 
  26. „Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling“. Mathematical Geosciences, 42, 487–517 (2010). DOI:10.1007/s11004-010-9276-7.