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 de vectores 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 manera 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:
Se ingresa el algoritmo linde-buzo-gray : conjunto de vectores de entrenamiento , libro de códigos para mejorar la salida del libro de códigos antiguo : 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 return lloyd ( nuevo libro de códigos , capacitación )entrada del algoritmo Lloyd : libro de códigos para mejorar, conjunto de vectores de entrenamiento salida del entrenamiento : libro de códigos mejorado hacer libro de códigos anterior ← libro de códigos clusters ← dividir la formación en | libro de códigos | Clústeres, donde cada grupo contiene todos los vectores en entrenamiento que están mejor representados por el vector correspondiente en el libro de códigos . para cada grupo grupo 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 representa el entrenamiento entre el libro de códigos y el libro de códigos anterior > 𝜖 devolver libro de códigos