Algoritmo di Lloyd: differenze tra le versioni

Versione delle 22:09, 18 gen 2022

Versione delle 22:15, 18 gen 2022

Riga 1:

{{Immagine multipla

|didascalia1 = Iterazione 1

|align = right

|immagine4 = LloydsMethod15.svg

|caption1 = Iteration 1

|didascalia3 = Iterazione 3

|alt4 = Lloyd's method, iteration 15

|image4immagine3 = LloydsMethod15LloydsMethod3.svg

|didascalia2 = Iterazione 2

|caption3 = Iteration 3

|immagine2 = LloydsMethod2.svg

|alt3 = Lloyd's method, iteration 3

|titolo = Esempio di applicazione dell'algoritmo. Sono mostrati i diagrammi di Voronoi dei punti. I segni positivi indicano i baricentri delle partizioni di Voronoi

|image3 = LloydsMethod3.svg

|alignallinea = right

|caption2 = Iteration 2

|directiondirezione = vertical

|alt2 = Lloyd's method, iteration 2

|image2immagine1 = LloydsMethod2LloydsMethod1.svg

|didascalia4 = Iterazione 15

|alt1 = Lloyd's method, iteration 1

|direction = vertical

|image1 = LloydsMethod1.svg

|width = 200

|footer_background =

|footer_align =

|footer = In the last image, the points are very near the centroids of the Voronoi cells. A centroidal Voronoi tessellation has been found.

|header_background =

|header_align = left

|header = Example of Lloyd's algorithm. The Voronoi diagram of the current points at each iteration is shown. The plus signs denote the centroids of the Voronoi cells.

|caption4 = Iteration 15

}}

In [[Elettrotecnica|ingegneria elettrica]] e [[informatica]], l''''algoritmo di Lloyd''', noto anche come '''iterazione''' (o rilassamento) '''di Voronoi''', è un algoritmo che prende il nome da Stuart P. Lloyd per trovare insiemi di punti equidistanti in sottoinsiemi di [[Spazio euclideo|spazi euclidei]] e partizioni di questi sottoinsiemi in celle.<ref name="l82">{{cita pubblicazione|autore=Stuart P. Lloyd|anno=1982|titolo=Least squares quantization in PCM|rivista=[[IEEE Transactions on Information Theory]]|volume=28|numero=2|pp=129–137|doi=10.1109/TIT.1982.1056489|url=http://www.cs.toronto.edu/~roweis/csc2515-2006/readings/lloyd57.pdf}}</ref> Come il simile [[K-means]], questo algoritmo trova ripetutamente il [[Baricentro (geometria)|baricentro]] di ciascun insieme nella partizione e quindi ripartiziona l'insieme dei punti in base a quale di questi baricentri è più vicino. In questa impostazione, l'operazione media è un integrale su una regione di spazio e l'operazione del centroide più vicino risulta nei [[Diagramma di Voronoi|diagrammi di Voronoi]].