Clystyru k-cymedr

Dull dysgu peirianyddol heb oruchwyliaeth yw clystyru k-cymedr, sy'n ceisio ymrannu n o arsylwadau i mewn i k clwstwr, lle mae pob arsylwad perthyn i'r clwstwr gyda'r cymedr agosaf. Mae hyn yn arwain at rannu'r gofod data i mewn i gelloedd Voronoi. Mae'n ddull poblogaidd mewn dadansoddiad clwstwr mewn cloddio data. Mae clystyru k-cymedr yn lleiafsymio'r amrywiannau o fewn pob clwstwr, h.y. pellteroedd Ewclidaidd sgwâr.

Mae'r broblem yn gyfrifiadurol yn anodd, mae'n galed-NP. Fodd bynnag, bodoler algorithmau hewristig effeithlon yn cydgyfeirio'n gyflym i optimwm lleol.

Disgrifiad

golygu

O ystyried set o arsylwadau (x1, x2, ..., xn), lle mae pob arsylwad yn fector d-dimesiwn real, mae clystyru k-cymedr yn ceisio ymrannu'r arsylwadau i mewn k (≤ n) set (clwstwr) S = {S1S2, ..., Sk}, er mwyn lleiafsymio'r amrywiant swm sgwariau o fewn pob clwstwr. Yn ffurfiol, yr amcan yw darganfod:

 

lle μi yw cymedr y pwyntiau o fewn Si. Mae hyn yn gyfatebol i leiafsymio swm pellteroedd sgwâr fesul pâr y pwyntiau sydd o fewn yr un clwstwr:

 

Mae'r cywerthedd hwn yn dilyn o'r unfathiant  . Gan fod cyfanswm yr amrywiant yn gyson, mae hyn yn cyfateb i mwyafsymio swm y pellteroedd sgwâr rhwng pwyntiau sydd mewn gwahanol glystyrau.[1]

Defnyddiwyd y term "k-means" yn gyntaf gan James MacQueen ym 1967,[2] er nodwyd y cysyniad gan Hugo Steinhaus ym 1956.[3] Datblygwyd yr algorithm safonol gyntaf gan Stuart Lloyd o Bell Labs ym 1957 fel techneg ar gyfer modiwleiddio côd-pwls. Serch hynny, na chafodd ei gyhoeddi mewn erthygl mewn cyfnodolyn academaidd tan 1982.[4] Ym 1965, cyhoeddodd Edward W. Forgy bron yr un dull, felly cyfeirir ato weithiau fel yr algorithm Lloyd-Forgy.[5]

Algorithm safonol (k-cymedr naïf)

golygu
 
Yr algorithm k-cymedr yn cydgyfeirio

Mae'r algorithm mwyaf cyffredin yn defnyddio techneg mireinio iteru. Mae mor boblogaidd fel arfer caiff ei alw yr "algorithm k-cymedr". Cyfeirir ato hefyd fel algorithm Lloyd, yn enwedig yn y gymuned cyfrifiadureg. Weithiau cyfeirir ato hefyd fel "k-cymedr naïf" oherwydd bodoler algorithmau eraill llawer cyflymach.[6]

O ystyried bod set cychwynnol o k cymedr m1(1), ..., mk(1), mae'r algorithm yn mynd yn ei flaen trwy ailadrodd dau gam:[7]

Cam aseinio : Rhowch bob arsylwad i mewn i'r clwstwr gyda'r cymedr agosaf: hynny gyda'r pellter Ewclidaidd sgwâr lleiaf. (Yn fathemategol, mae hyn yn golygu rhannu'r arsylwadau yn ôl y diagram Voronoi a gynhyrchir o'r cymedrau.)
 
lle mae pob   wedi'i rhoi i mewn i un   yn union, hyd yn oed os oes modd ei aseinio i ddau neu fwy ohonynt.
Cam diweddaru: Ail-gyfrifo'r cymedrau (weithiau elwir y rhain yn greiddiau neu ganolbwyntiau) ar gyfer yr arsylwadau sydd i nawr ym mhob clwstwr.
 

Mae'r algorithm wedi cydgyfeirio pan nad yw'r aseiniadau'n newid mwyach. Nid yw'n bendant y bydd yr algorithm yn dod o hyd i'r gorau posibl, hynny yw'r optimwm byd-eang, ond bydd yn canfod optimwm lleol.[8]

Trafodaeth

golygu

Mae'r tair priodwedd allweddol o glystyru k-cymedr sy'n ei gwneud yn effeithlon yn aml yn cael eu hystyried fel yr anfanteision mwyaf:

  • Defnyddir pellter Ewclidaidd fel metrig, a defnyddir amrywiant fel mesur o wasgariad clwstwr.
  • Mae nifer y clystyrau k yn baramedr mewnbwn: gall dewis amhriodol o k arwain at ganlyniadau gwael. Felly, wrth berfformio clystyru k-cymedr, mae'n bwysig cynnal gwiriadau diagnostig ar gyfer pennu nifer y clystyrau yn y set ddata.
  • Gall cydgyfeirio i leiafswm lleol gynhyrchu canlyniadau anreddfol (y gall rhai ei weld yn "anghywir").

Un o gyfyngiadau allweddol clystyru k-cymedr yw'r fodel clwstwr ei hun. Mae'r cysyniad yn seiliedig ar glystyrau sfferig y gellir eu gwahanu fel bod y cymedr yn cydgyfeirio tuag at ganol y clwstwr. Disgwylir i'r clystyrau fod o faint tebyg, fel mai'r aseiniad i'r cymedr agosaf yw'r aseiniad cywir. Er enghraifft, mae defnyddio clystyru k-cymedr sydd â gwerth   ar y set ddata flodau enwog Iris, mae'r canlyniad yn aml yn methu â gwahanu'r tair rhywogaeth iris sydd wedi'u cynnwys yn y set ddata. Fel unrhyw algorithm clystyru arall, mae'r canlyniad clystyru k-cymedr yn gwneud tybiaethau bod y data'n bodloni rhai meini prawf penodol. Mae'n gweithio'n dda ar rai setiau data, ac yn methu ar eraill.

Gellir gweld canlyniad clystyru k-cymedr fel celloedd Voronoi cymedrau'r clystyrau. Gan fod data wedi'i rannu hanner ffordd rhwng cymedrau dau glwstwr, gall hyn arwain at holltiadau nad yw'n gorau posib fel y gwelir yn yr enghraifft "llygoden". Algorithm gwell ar gyfer y data hwn yw'r algorithm mwyafsymio gwerthoedd disgwyliedig (EM), a chymharir y rhain yn y ffigwr.[9]

 
Canlyniadau clystyru k-cymedr ar y set ddata blodau Iris, o gymharu â'r rhywogaethau gwirioneddol. Mae cymedrau'r clystyrau wedi'u marcio gan ddefnyddio symbolau mwy.
 
Cymhariaeth canlyniadau clystyru k-cymedr a chanlyniadau clystyru EM ar set ddata artiffisial ("llygoden"). Gan fod clystyru k-cymedr yn tueddu i gynhyrchu clystyrau o faint cyfartal, mae'n arwain at ganlyniadau gwael fan hyn.

Cyfeiriadau

golygu
  1. Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur (2016). "The (black) art of runtime evaluation: Are we comparing algorithms or implementations?". Knowledge and Information Systems 52 (2): 341–378. doi:10.1007/s10115-016-1004-2. ISSN 0219-1377.
  2. MacQueen, J. B. (1967). Some Methods for classification and Analysis of Multivariate Observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. 1. University of California Press. tt. 281–297. MR 0214227. Zbl 0214.46201. Cyrchwyd 2009-04-07.
  3. Steinhaus, Hugo (1957). "Sur la division des corps matériels en parties" (yn French). Bull. Acad. Polon. Sci. 4 (12): 801–804. MR 0090073. Zbl 0079.16403.
  4. Lloyd, Stuart P. (1957). "Least square quantization in PCM". Bell Telephone Laboratories Paper. Published in journal much later: Lloyd, Stuart P. (1982). "Least squares quantization in PCM". IEEE Transactions on Information Theory 28 (2): 129–137. doi:10.1109/TIT.1982.1056489. http://www.cs.toronto.edu/~roweis/csc2515-2006/readings/lloyd57.pdf. Adalwyd 2009-04-15.
  5. Forgy, Edward W. (1965). "Cluster analysis of multivariate data: efficiency versus interpretability of classifications". Biometrics 21 (3): 768–769. JSTOR 2528559. https://archive.org/details/sim_biometrics_1965-09_21_3/page/768.
  6. Pelleg, Dan; Moore, Andrew (1999). "Accelerating exact k -means algorithms with geometric reasoning" (yn en). Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD '99 (San Diego, California, United States: ACM Press): 277–281. doi:10.1145/312129.312248. ISBN 9781581131437. http://portal.acm.org/citation.cfm?doid=312129.312248.
  7. MacKay, David (2003). "Chapter 20. An Example Inference Task: Clustering". Information Theory, Inference and Learning Algorithms. Cambridge University Press. tt. 284–292. ISBN 978-0-521-64298-9. MR 2012999.
  8. Hartigan, J. A.; Wong, M. A. (1979). "Algorithm AS 136: A k-Means Clustering Algorithm". Journal of the Royal Statistical Society, Series C 28 (1): 100–108. JSTOR 2346830.
  9. Kulis, Brian; Jordan, Michael I. (2012-06-26). Revisiting k-means: new algorithms via Bayesian nonparametrics (PDF). tt. 1131–1138. ISBN 9781450312851.