K-keskmiste klasterdamine

k-keskmiste klasterdamine on meetod vektorite kvantimiseks, algselt signaalitöötluseks.^[1] 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

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

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

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

Selle võrdväärsuse saab tuletada valemist ${\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} )}$. Kuna koguhälve on konstantne, siis see on samuti võrdväärne erinevates klastrites olevate punktipaaride hälvete maksimeerimisega (klastritevaheline ruutude summa).^[2]

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:^[3]

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

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

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.

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

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.^[5] 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.^[5]

Viited

1. Lloyd, S. P. (1957). "Least square quantization in PCM". Bell Telephone Laboratories Paper. Published in journal much later: Lloyd., S. P. (1982). "Least squares quantization in PCM" (PDF). IEEE Transactions on Information Theory. 28 (2): 129–137. DOI:10.1109/TIT.1982.1056489. Vaadatud 15.04.2009.
2. Kriegel, H. P; Schubert, E; Zimek, A (2016). The (black) art of runtime evaluation: Are we comparing algorithms or implementations?. Kd 52. Institute for InformaticsLudwig-Maximilians-Universität München, Munich, Germany: Knowledge and Information Systems. Lk 341–378. DOI:10.1007/s10115-016-1004-2. ISSN 0219-1377.
3. MacKay, D (2003). Information Theory, Inference and Learning Algorithms. Cambridge University: Cambridge University Press. Lk 284–292. ISBN 0-521-64298-1.
4. Hartigan, J. A.; Wong, M. A. (1979). Algorithm AS 136: A K-Means Clustering Algorithm. Kd 28. Yale University: Journal of the Royal Statistical Society, Series C. Lk 100–108.
5. Hamerly, G.; Elkan, C. (2002). "Alternatives to the k-means algorithm that find better clusterings" (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM). {{cite conference}}: eiran tundmatut parameetrit |booktitle=, kasuta parameetrit (|book-title=) (juhend)