K-keskmiste klasterdamine

k-keskmiste klasterdamine on meetod vektorite kvantimiseks, algselt signaalitöötluseks. Meetod on populaarne andmekaeve 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 rakkudeks.

Algoritm on sarnane k-lähima naabri algoritmiga, mis on tuntud 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 algoritmiks või lähima tsentroidi klassifitseerijaks.

Kirjeldus

Olgu antud hulk objekte (x₁,x₂,...,x_n), kus iga objekt on d-mõõtmeline vektor. Siis jagab k-keskmiste klasterdamise algoritm n objekti k(≤n) hulka S = {(S₁,S₂,...,S_k)} nii, et klastrisisene hälvete ruutude summa oleks minimaalne (klastrisisene ruutude summa).

Eesmärk on leida

${\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}$,

kus $\mu _{i}$ on S_i punktide keskmine. See on võrdväärne samas klastris olevate punktipaaride hälvete minimeerimisega:

${\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}$.

Selle võrdväärsuse saab tuletada valemist $\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} )$. 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 algoritmiks.

Esiteks seadistatakse k keskpunkti m₁,m₂,...,m_k, 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_{i}^{(t)}{\big \|}^{2}\leq {\big \|}x_{p}-m_{j}^{(t)}{\big \|}^{2}\ \forall j,1\leq j\leq k{\big \}},$

kus iga objekti x_p kohta on määratud täpselt üks klaster S^(t) isegi siis, kui objekti oleks võimalik määrata rohkematesse klastritesse.

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

$m_{i}^{(t+1)}={\frac {1}{|S_{i}^{(t)}|}}\sum _{x_{j}\in S_{i}^{(t)}}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.