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 
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 = {S1, S2, ..., 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.

 Hanes 
Defnyddiwyd y term "k-means" yn gyntaf gan James MacQueen ym 1967, er nodwyd y cysyniad gan Hugo Steinhaus ym 1956. 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. Published in journal much later:  Ym 1965, cyhoeddodd Edward W. Forgy bron yr un dull, felly cyfeirir ato weithiau fel yr algorithm Lloyd-Forgy.

 Algorithm safonol (k-cymedr naïf) 
de|bawd|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.

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

 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.

 Trafodaeth 
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.bawd|450x450px|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.
bawd|450x450px|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.|dim

 Cyfeiriadau 

Categori:Algorithmau