El algoritmo Linde–Buzo–Gray (llamado así por sus creadores Yoseph Linde, Andrés Buzo y Robert M. Gray , quienes lo diseñaron en 1980) [1] es un algoritmo iterativo de cuantificación vectorial para mejorar un pequeño conjunto de vectores (libro de códigos) para representar un conjunto más grande de vectores (conjunto de entrenamiento), de modo que sea localmente óptimo . Combina el algoritmo de Lloyd con una técnica de división en la que se construyen libros de códigos más grandes a partir de libros de códigos más pequeños dividiendo cada vector de código en dos. La idea central del algoritmo es que al dividir el libro de códigos de modo que todos los vectores de código del libro de códigos anterior estén presentes, el nuevo libro de códigos debe ser tan bueno como el anterior o mejor. [2] : 361–362
El algoritmo Linde-Buzo-Gray se puede implementar de la siguiente manera:
El algoritmo Linde-Buzo-Gray tiene como entrada : un conjunto de vectores de entrenamiento , un libro de códigos para mejorar el libro de códigos antiguo , y como resultado , un libro de códigos que tiene el doble de tamaño y es mejor o tan bueno como el libro de códigos antiguo. nuevo libro de códigos ← {} para cada vector de código antiguo en el libro de códigos antiguo inserte el vector de código antiguo en el libro de códigos nuevo inserte el vector de código antiguo + 𝜖 en el libro de códigos nuevo donde 𝜖 es un vector pequeño devuelve lloyd( nuevo libro de códigos , entrenamiento )El algoritmo Lloyd se ingresa como un libro de códigos para mejorar, un conjunto de vectores de entrenamiento y como resultado del entrenamiento se mejora el libro de códigos. hacer libro de códigos anterior ← libro de códigos clústeres ← divide el entrenamiento en | libro de códigos | clústeres, donde cada clúster contiene todos los vectores en entrenamiento que están mejor representados por el vector correspondiente en el libro de códigos para cada grupo de grupos en grupos, haga el vector de código correspondiente en el libro de códigos ← el centroide de todos los vectores de entrenamiento en el grupo mientras que la diferencia en el error que representa el entrenamiento entre el libro de códigos y el libro de códigos anterior > 𝜖 devolver libro de códigos