K-keskmiste klasterdamine

***k''-keskmiste''' '''klasterdamine''' on meetod [[Vektori kvantimine|vektorite kvantimiseks]], algselt [[Signaalitöötlus|signaalitöötluseks]]. Meetod on populaarne [[andmekaeve]] [[Klasteranalüüs|klasteranalüüsis]]. 

''k''-keskmiste klasterdamise eesmärk on jagada ''n'' objekti ''k'' klastrisse nii, et iga objekt kuuluks klastrisse, mille keskpunktile see kõige lähedamal on. Selle tulemusena jaotub andmeruum [[Voronoi diagramm|Voronoi rakkudeks]].

Algoritm on sarnane [[k-lähima naabri klassifitseerija|''k''-lähima naabri]] algoritmiga, mis on tuntud [[Masinõppimine|masinõppe]] klassifitseerimises. ''k''-lähima naabri algoritmi saab kasutada ''k''-keskmiste algoritmist saadud klastrite keskpunktide peal, et klassifitseerida uusi andmeid olemasolevatesse klastritesse. Seda kutsutakse [[Rocchio algoritm|Rocchio algoritmiks]] või [[Lähima tsentroidi klassifitseerija|lähima tsentroidi klassifitseerijaks]].

== Kirjeldus ==
Olgu antud hulk objekte ('''x'''<sub>1</sub>,'''x'''<sub>2</sub>,...,'''x'''<sub>n</sub>), kus iga objekt on ''d''-mõõtmeline vektor. Siis jagab ''k''-keskmiste klasterdamise algoritm ''n'' objekti ''k(≤n)'' hulka S = {('''S'''<sub>1</sub>,'''S'''<sub>2</sub>,...,'''S'''<sub>k</sub>)} nii, et klastrisisene hälvete ruutude summa oleks minimaalne (klastrisisene ruutude summa).

Eesmärk on leida
<div style="text-align: center;">
<math>\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 </math>,
</div>
kus <math>\mu_i</math> on ''S<sub>i</sub>'' punktide keskmine. See on võrdväärne samas klastris olevate punktipaaride hälvete minimeerimisega:
<div style="text-align: center;">
<math>\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</math>.
</div>
Selle võrdväärsuse saab tuletada valemist <math> \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)</math>. Kuna koguhälve on konstantne, siis see on samuti võrdväärne '''erinevates''' klastrites olevate punktipaaride hälvete maksimeerimisega (klastritevaheline ruutude summa).

== Algoritm ==

=== Standardne algoritm ===
See algoritm on levinuim klasterdamise algoritm. See kasutab iteratiivset täiustamise meetodit. Seda algoritmi kutsutakse ***k*-keskmiste algoritmiks.*' Just arvutiteaduses kutsutakse seda ka **[[Lloydi algoritm|Lloydi algoritmiks]]**.

Esiteks seadistatakse *k* keskpunkti *m<sub>1</sub>,m<sub>2</sub>,...,m<sub>k</sub>*, seejärel algoritm kordab kahte sammu:**Ülesande samm:** määrata iga objekt klastrisse, mille keskpunktile on antud objekt eukleidilise kaugusega kõige lähemal. (Matemaatiliselt tähendab see, et jaotame objektid vastavalt Voronoi diagrammiga, mille keskpunktid tekitavad.

S_i^{(t)} = \big \{ x_p : \big \| x_p - m^{(t)}_i \big \|^2 \le \big \| x_p - m^{(t)}_j \big \|^2 \ \forall j, 1 \le j \le k \big\},

kus iga objekti *x<sub>p</sub>* kohta on määratud täpselt üks klaster *S<sup>(t)</sup>* isegi siis, kui objekti oleks võimalik määrata rohkematesse klastritesse.

**Uuenduse samm:** Arvutada uued keskpunktid, milleks saavad tekkinud klastrite tsentroidid.

m^{(t+1)}_i = \frac{1} \sum_{x_j \in S^{(t)}_i} x_j Algoritm on koondunud, kui ülesande sammus klastrid enam ei muutu. Pole garanteeritud, et algoritm leidis kõige optimaalsema lahenduse.

See algoritm on tihti esitatud kui objektide lähimasse klastrisse määramine kauguse alusel. Mingi teise kauguse funktsiooni kasutamine (välja arvatud eukleidiline kaugus) võib takistada algoritmi koondumast. *k*-keskmiste algoritmile on pakutud välja erinevaid täiustusi, näiteks sfäärilist *k*-keskmist ja *k*-medoidi, mis lubavad kasutada teisi kaugusmeetmeid.

#### Initsialiseerimine
Kõige sagedamini kasutatakse esimeste keskpunktide seadistamiseks Forgy ja suvalist jaotust. Forgy meetod valib suvaliselt *k* objekti ja kasutab neid algsete keskmistena. Suvaline jaotuse meetod jagab kõik objektid suvaliselt *k* klastrisse ja seejärel teeb uuenduse sammu. Forgy meetod kipub algseid keskmisi hajutama, kuid suvalise jaotuse meetod paigutab kõik andmete keskele. 

## Viited