Metoda x-průměrů

Jak již bylo uvedeno výše, u nejrozšířenější nehierarchické shlukovací metody k-průměrů nastávají dva hlavní problémy: 1. počet shluků k musí být definován uživatelem a 2. hledání k shluků podléhá lokálnímu minimu. Řešení prvního problému a částečně i druhého problému nabízí metoda -průměrů.

V algoritmu metody -průměrů se počet shluků vypočítá dynamicky, přičemž je uživatelem zadávána pouze dolní a horní hranice pro . Algoritmus je tvořen dvěma kroky, které se opakují.

1. V prvním kroku je aplikována tradiční metoda k-průměrů pro shluků ( je nejprve rovno dolní hranici určené uživatelem).
2. V druhém kroku se zjišťuje, zda a kde se má objevit nový centroid, nový shluk. Toho je dosaženo tím, že se některé shluky nechají rozpadnout na dva. Proces začíná tak, že se každý centroid shluku (nazveme jej rodičovský centroid) rozdělí na dva centroidy (dceřiné centroidy) v opačném směru podél náhodně zvoleného vektoru. Poté se pro každou rodičovskou oblast, čili pro každý pár dceřiných centroidů, vypočítá lokální metoda k-průměru pro dva shluky. Hranice rodičovských oblastí se nemění. Srovnáním Bayesovského informačního kriteria (BIC) pro model s dceřinými centroidy a model s rodičovským centroidem se rozhodne o výsledné struktuře. Podle výsledku testu je buď zachován rodičovský centroid (a tedy rodičovský shluk), nebo je nahrazen dceřinými centroidy (tj. dvěma dceřinými shluky).
   Když (horní hranice určena uživatelem), proces se ukončí a vyhodnotí se nejlepší model v průběhu hledání, tj. sada centroidů s nejlepší hodnotou testového kriteria. Jinak se pokračuje znovu krokem 1.

Jako kritérium pro dělení shluku na dva dceřiné shluky může být kromě BIC použito i jiné, např. Akaikovo informační kriterium (AIC).

Výhodou tohoto postupu je také fakt, že regionální metoda k-průměrů s pouze dvěma shluky je méně citlivá na lokální minima.