Lloyd's algorithm (original) (raw)
In electrical engineering and computer science, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean spaces and partitions of these subsets into well-shaped and uniformly sized convex cells. Like the closely related k-means clustering algorithm, it repeatedly finds the centroid of each set in the partition and then re-partitions the input according to which of these centroids is closest. In this setting, the mean operation is an integral over a region of space, and the nearest centroid operation results in Voronoi diagrams.
| Property | Value |
|---|---|
| dbo:abstract | In electrical engineering and computer science, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean spaces and partitions of these subsets into well-shaped and uniformly sized convex cells. Like the closely related k-means clustering algorithm, it repeatedly finds the centroid of each set in the partition and then re-partitions the input according to which of these centroids is closest. In this setting, the mean operation is an integral over a region of space, and the nearest centroid operation results in Voronoi diagrams. Although the algorithm may be applied most directly to the Euclidean plane, similar algorithms may also be applied to higher-dimensional spaces or to spaces with other non-Euclidean metrics. Lloyd's algorithm can be used to construct close approximations to centroidal Voronoi tessellations of the input, which can be used for quantization, dithering, and stippling. Other applications of Lloyd's algorithm include smoothing of triangle meshes in the finite element method. (en) En algorithmique et en traitement du signal, l’algorithme de Lloyd-Max est un algorithme qui permet de construire le quantifieur scalaire optimal. C'est donc une méthode pour quantifier un signal en une dimension de manière à minimiser la distorsion, mesurée par l'erreur quadratique moyenne. L'optimalité du quantifieur est assurée par deux conditions sur les niveaux de reconstruction et de décision, découvertes par Lloyd en 1957. Il fournit aussi un algorithme, qui permet de construire itérativement le quantifieur optimal. L'algorithme peut être étendu à la quantification de vecteurs (algorithme de Linde-Buzo-Gray). (fr) In 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 spazi euclidei e partizioni di questi sottoinsiemi in celle. Come il simile K-means, questo algoritmo trova ripetutamente il 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 diagrammi di Voronoi. Sebbene l'algoritmo possa essere applicato più direttamente al piano euclideo, algoritmi simili possono essere applicati anche a spazi di dimensioni superiori o a spazi con altre metriche non euclidee. L'algoritmo di Lloyd può essere utilizzato per costruire approssimazioni affidabili delle (dove il punto che genera la partizione è anche il centroide, o baricentro) dell'input, che possono essere utilizzate per la quantizzazione, il dithering e lo stippling. L'algoritmo può essere applicato nello smussamento delle mesh triangolari nel metodo degli elementi finiti. (it) В інформатиці та електротехніці алгоритм Ллойда також відомий як ітерації Вороного чи релаксація. Цей алгоритм названий на честь Стюарта П. Ллойда, який знайшов спосіб знаходження рівномірного розподілу множин точок у підмножини Евклідових просторів і розділення цих підмножин на структуровані опуклі комірки рівномірного розміру. Як і кластеризація методом k-середніх, так і алгоритм Ллойда послідовно знаходять центри кожного набору розподілу, а тоді перерозподіляють вхідні дані відповідно до того, які з цих центрі знаходяться найближче. Відмінність між цими алгоритмами полягає в тому, що вхідними даними для алгоритму Ллойда є неперервна геометрична область, в той час, як для кластеризації методом k-середніх — дискретна множина точок. Тому під час перерозподілу вхідних даних алгоритм Ллойда використовує діаграми Вороного, а не просто визначає найближчий центр до кожної скінченної множини точок, як це відбувається під час кластеризації методом k-середніх. Хоча даний алгоритм безпосередньо застосовується в Евклідовій площині, схожі алгоритми можна застосовувати та в багатовимірних просторах чи в просторах з неевклідовою метрикою. Алгоритм Ллойда можна використовувати для побудови наближень для центроїдальної мозаїки Вороного вхідних даних, яка, у свою чергу, може бути використана для квантування, згладжування і зображення пунктиром (зернистості). Інше застосування алгоритму Ллойда — згладжування трикутних сіток в методі скінченних елементів. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/LloydsMethod1.svg?width=300 |
| dbo:wikiPageExternalLink | http://demogng.de/js/demogng.html%3Fmodel=LBG&showAutoRestart&showVoronoi |
| dbo:wikiPageID | 2607912 (xsd:integer) |
| dbo:wikiPageLength | 15709 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1119165105 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Mosaic dbr:Bell_Labs dbr:Linde–Buzo–Gray_algorithm dbr:Colors_of_noise dbr:Stippling dbr:Triangle_mesh dbr:Pulse-code_modulation dbr:Electrical_engineering dbr:Monte_Carlo_methods dbc:Geometric_algorithms dbr:Lp_space dbr:Computer_science dbr:Z-buffering dbr:Mean_shift dbc:Optimization_algorithms_and_methods dbr:Centroid dbr:Data_compression dbr:K-means++ dbr:K-means_clustering dbr:Laplacian_smoothing dbr:Euclidean_space dbr:Non-Euclidean_geometry dbr:Centroidal_Voronoi_tessellation dbr:Farthest-first_traversal dbr:Quantization_(signal_processing) dbr:Tetrahedron dbr:Triangle dbr:Dithering dbr:Information_theory dbr:Voronoi_diagram dbr:Euclidean_distance dbr:Euclidean_plane dbr:Finite_element_method dbr:Blue_noise dbr:Manhattan_metric |
| dbp:align | left (en) |
| dbp:alt | Lloyd's method, iteration 1 (en) Lloyd's method, iteration 15 (en) Lloyd's method, iteration 2 (en) Lloyd's method, iteration 3 (en) |
| dbp:caption | Iteration 1 (en) Iteration 15 (en) Iteration 2 (en) Iteration 3 (en) |
| dbp:direction | horizontal (en) |
| dbp:footer | In the last image, the sites are very near the centroids of the Voronoi cells. A centroidal Voronoi tessellation has been found. (en) |
| dbp:header | Example of Lloyd's algorithm. The Voronoi diagram of the current site positions at each iteration is shown. The gray circles denote the centroids of the Voronoi cells. (en) |
| dbp:headerAlign | left (en) |
| dbp:image | LloydsMethod1.svg (en) LloydsMethod15.svg (en) LloydsMethod2.svg (en) LloydsMethod3.svg (en) |
| dbp:width | 200 (xsd:integer) |
| dbp:wikiPageUsesTemplate | dbt:Clear dbt:Harvtxt dbt:Math dbt:Multiple_image dbt:Reflist |
| dct:subject | dbc:Geometric_algorithms dbc:Optimization_algorithms_and_methods |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGeometricAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | In electrical engineering and computer science, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean spaces and partitions of these subsets into well-shaped and uniformly sized convex cells. Like the closely related k-means clustering algorithm, it repeatedly finds the centroid of each set in the partition and then re-partitions the input according to which of these centroids is closest. In this setting, the mean operation is an integral over a region of space, and the nearest centroid operation results in Voronoi diagrams. (en) En algorithmique et en traitement du signal, l’algorithme de Lloyd-Max est un algorithme qui permet de construire le quantifieur scalaire optimal. C'est donc une méthode pour quantifier un signal en une dimension de manière à minimiser la distorsion, mesurée par l'erreur quadratique moyenne. (fr) In 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 spazi euclidei e partizioni di questi sottoinsiemi in celle. Come il simile K-means, questo algoritmo trova ripetutamente il 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 diagrammi di Voronoi. (it) В інформатиці та електротехніці алгоритм Ллойда також відомий як ітерації Вороного чи релаксація. Цей алгоритм названий на честь Стюарта П. Ллойда, який знайшов спосіб знаходження рівномірного розподілу множин точок у підмножини Евклідових просторів і розділення цих підмножин на структуровані опуклі комірки рівномірного розміру. Як і кластеризація методом k-середніх, так і алгоритм Ллойда послідовно знаходять центри кожного набору розподілу, а тоді перерозподіляють вхідні дані відповідно до того, які з цих центрі знаходяться найближче. Відмінність між цими алгоритмами полягає в тому, що вхідними даними для алгоритму Ллойда є неперервна геометрична область, в той час, як для кластеризації методом k-середніх — дискретна множина точок. Тому під час перерозподілу вхідних даних алгоритм Ллойда (uk) |
| rdfs:label | Algorithme de Lloyd-Max (fr) Algoritmo di Lloyd (it) Lloyd's algorithm (en) Алгоритм Ллойда (uk) |
| owl:sameAs | freebase:Lloyd's algorithm yago-res:Lloyd's algorithm wikidata:Lloyd's algorithm dbpedia-et:Lloyd's algorithm dbpedia-fr:Lloyd's algorithm dbpedia-he:Lloyd's algorithm dbpedia-it:Lloyd's algorithm dbpedia-uk:Lloyd's algorithm http://ur.dbpedia.org/resource/لائیڈ_الخوارزم https://global.dbpedia.org/id/2dx4T |
| prov:wasDerivedFrom | wikipedia-en:Lloyd's_algorithm?oldid=1119165105&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/LloydsMethod1.svg wiki-commons:Special:FilePath/LloydsMethod15.svg wiki-commons:Special:FilePath/LloydsMethod2.svg wiki-commons:Special:FilePath/LloydsMethod3.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Lloyd's_algorithm |
| is dbo:wikiPageRedirects of | dbr:Lloyds_algorithm dbr:Lloyd's_Algorithm dbr:Voronoi_iteration |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Vector_quantization dbr:David_Mount dbr:Delaunay_triangulation dbr:Linde–Buzo–Gray_algorithm dbr:Proximity_analysis dbr:Georgy_Voronoy dbr:Cluster_analysis dbr:K-means++ dbr:K-means_clustering dbr:K-medoids dbr:Dual_graph dbr:Centroidal_Voronoi_tessellation dbr:Farthest-first_traversal dbr:Quantization_(signal_processing) dbr:Voronoi_diagram dbr:Lloyds_algorithm dbr:Transport_network_analysis dbr:Tutte_embedding dbr:Lloyd's_Algorithm dbr:Voronoi_iteration |
| is foaf:primaryTopic of | wikipedia-en:Lloyd's_algorithm |
