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 (x_1, x_2, ..., x_n), 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 = {S₁, S₂, ..., S_k}, er mwyn lleiafsymio'r amrywiant swm sgwariau o fewn pob clwstwr. Yn ffurfiol, yr amcan yw darganfod:

${\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}={\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}|S_{i}|\operatorname {Var} S_{i}$

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

${\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\,{\frac {1}{2|S_{i}|}}\,\sum _{\mathbf {x} ,\mathbf {y} \in S_{i}}\left\|\mathbf {x} -\mathbf {y} \right\|^{2}$

Mae'r cywerthedd hwn yn dilyn o'r unfathiant $\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}=\sum _{\mathbf {x} \neq \mathbf {y} \in S_{i}}(\mathbf {x} -{\boldsymbol {\mu }}_{i})({\boldsymbol {\mu }}_{i}-\mathbf {y} )$. 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. 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)

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 m₁⁽¹⁾, ..., m_k⁽¹⁾, 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.)

$S_{i}^{(t)}={\big \{}x_{p}:{\big \|}x_{p}-m_{i}^{(t)}{\big \|}^{2}\leq {\big \|}x_{p}-m_{j}^{(t)}{\big \|}^{2}\ \forall j,1\leq j\leq k{\big \}},$

lle mae pob $x_{p}$ wedi'i rhoi i mewn i un $S^{(t)}$ 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.

$m_{i}^{(t+1)}={\frac {1}{\left|S_{i}^{(t)}\right|}}\sum _{x_{j}\in S_{i}^{(t)}}x_{j}$

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.

• Arddangosiad o'r algorithm naïf.
• 
  1. Generadir k "cymedr" dechreuol (yn yr achos yma k=3) ar hap o fewn parth y data (dangosir y cymedrau hyn mewn lliw).
• 
  2. Caiff k clwstwr eu creu trwy gysylltu pob un o'r arsylwadau i'r cymedr agosaf. Mae'r ymraniadau hyn yn cynrychioli'r diagram Voronoi a generadir gan y cymedrau.
• 
  3. Mae craidd pob un o'r k clwstwr yn dod y cymedrau newydd.
• 
  4. Ailadroddir camau 2 a 3 nes i'r algorithm cydgyfeirio.

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 $k=3$ 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.

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.