Clystyru k-cymedr

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:

${\displaystyle {\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:

${\displaystyle {\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 ${\displaystyle \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.^[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]

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

${\displaystyle 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 ${\displaystyle x_{p}}$ wedi'i rhoi i mewn i un ${\displaystyle 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.

${\displaystyle 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.^[8]

• 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.

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 ${\displaystyle 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.^[9]