Kasutaja:Hmanaad/Lloyd'i algoritm

Lloydi algoritm ehk Voronoi iteratsioon on arvutiteaduses ja elektrotehnikas kasutatav algoritm, mis leiab eukleidilises ruumis asuvate punktide puhul neile vastavad kumerad alamhulgad, kuid on kasutatav ka teistes geomeetriates. Mitmemõõtmelistes eukleidilistes geomeetriates ja mitte-eukleidilistes geomeetriates ei pruugi algoritm koonduda või koondub mingiks lokaalseks optimumiks. Algoritm sobib pideva hulga kvantiseerimiseks, sest koondub optimaalseks diskreetseks lähendiks vastavale pidevale hulgale.

Algoritm on sarnane k-keskmise klasterdamise algoritmiga. Kahe algoritmi vahe seisneb selles, et k-keskmise klasterdamise algoritm töötab lõpliku hulga punktide peal, aga Lloydi algoritm põhineb pidevatel hulkadel. Sellest tulenevalt kasutatakse Lloydi algoritmis tsentrite ümberpaigutamiseks Voronoi diagramme, mitte lõplikke punktihulkasid.

Algoritm on nime saanud selle koostaja, Stuart P. Lloydi järgi. Tegu on Lloydi tuntuima teadustööga ning algoritm aitas parandada sideühendust satelliitidega, kõrgendada krediitkaartide turvalisust ning edendada arvutigraafikat.[1]

Algoritmi kirjeldus

Algoritmi käivitamiseks on vaja sellele ette anda alglähend, mis koosneb k punktist. Järgnevalt viiakse läbi algoritmi sammud, millest iga käigus:

• arvutatakse Voronoi diagramm antud lähendi puhul (k punkti),
• leitakse iga Voronoi diagrammi tüki keskpunkt,
• leitud k keskpunkti võetakse uueks lähendiks.

Rohkem kui kahemõõtmelistes ruumides muutuvad Voronoi diagrammi konstrueerimine ja sellest tulenevalt ka diagrammi iga tükelduse tsentri leidmine mitte-triviaalseks. Sellest tulenevalt kasutatakse praktikas Voronoi tükelduse leidmiseks diskreetseid lähendeid või Monte Carlo meetodeid.

Koondumine

Algoritmi igal sammul muutub lähendite paikenemine aina ühtlasemaks. Punktid, mis on üksteisest kaugel, liiguvad rohkem lähestikku ja punktid, mis on üksteisele lähedal, liigutatakse üksteisest eemale. Ühedimensionaalses eukleidilises ruumis koonduvad lähendid algoritmi tulemusena tsentraalseks Voronoi diagrammiks. Kõrgemates dimensioonides on teada mõningad nõrgemad koondumistunnused ja on ka võimalik, et algoritm koondub lokaalsesse optimumi.

Algoritmi rakendamisel ei pruugi koondumine olla absoluutne ja seega kasutatakse enamasti spetsiaalseid koondumistingimusi. Kõige laialtlevinumaks koondumistingimuseks on $max_{i\in \{1,...,k\}}\{a_{i,n-1},a_{i,n}\}<\varepsilon$, kus $k$ on punktide arv, $n$ iteratsioonide arv ja $\varepsilon$ on valitud koondumispiir. Koondumise kiirendamiseks kasutatakse meetodit, mille puhul igal iteratsioonil liigutatakse igat punkti koondumise sihis, aga kaks korda kaugemale kui algoritmi tavalise talituse puhul.

Kasutusalad

Algoritmi kasutati algselt ainult ühedimensionaalseks kvantimiseks, aga see leidis hiljem rakendust ka mitmemõõtmeliste probleemide puhul. Laialdast kasutust on algoritm leidnud andmete pakkimisel informatsiooniteoorias, kus analoogseid signaale on vaja diskreetseteks signaalideks konverteerida.

Lloydi algoritm on leidnud kasutust ka arvutigraafikas, kus seda kasutatakse hulknurkadest koosnevate kolmedimensionaalsete kujundite silumiseks. Selle asemel, et lasta algoritmil koonduda, lastakse algoritmil joosta teatud arv kordi, mille käigus hulknurkade suurust ja kuju muudetakse ühtlasemaks. Algoritmi rakendamise eesmärgiks on saavutada kumerama siluetiga kujundid.