Clustering is a technique adopted in several application fields as for example artificial neural networks, data compression, pattern recognition, etc. This paper presents the Enhanced LBG (ELBG) a new clustering algorithm deriving directly from the well-known classical LBG algorithm. It belongs to the hard and K-means vector quantization groups. We started from the definition of a new mathematical concept we called utility of a codeword. Although some previous authors introduced a homonymous utility concept, our meaning and computational complexity are totally different. The utility we introduced permits us to identify well in which cases the LBG algorithm fails to find global optimum codebooks. Starting from a mathematical analysis of the properties of the utility, we propose a sub-optimal strategy that has a very low time complexity. Our results show that with an overhead of no more than 5% in respect of the LBG algorithm, we succeed in finding better results above all in complex application fields, as for example when the number of codewords increases.