Úloha spočívá v převodu lineárního algoritmu k-means na nelineární pomocí jádrových funkcí. Což znamená, že shluky hledáme ve vysokodimenzionálním prostoru, indukovaném zobrazením
Φ: Rd → RD,
kde d je počáteční dimenze (v našem případě se jedná o 2-D prostor) a D je jádrový prostor a zároveň D > d.Pro výpočet je důležité vypočíst pro každý bod x jeho vzdálenost od center shluků xa. To lze zapsat jako
|| Φ(x) - 1/ptj ∑ xa∈Xtj
Φ(xa)||2,
kde Xtjje množina bodů patřících v čase t do shluku
j.
K(x,x)+1/p2tj∑ xa∈Xtj∑x b ∈Xtj K(xa,xb) - 2/p tj ∑xa∈Xtj K( xa,x ) (1).
Pro vlastní výpočet pak používáme zadané jádrové funkce.
| Název | 2-D prostor | zápis v Matlabu |
| lineární funkce |
|
(x1)'*(x2) |
| polynom d-tého stupně |
|
(((x1)'*(x2))+2)^d |
| RBF funkce |
|
exp(-((x1-x2)'*(x1-x2))*s) |
Vstupem programu jsou data, která generujeme pomocí programu creatset z balíku sprttool [ 4 ], uložená v souboru soubor typu *.mat, dále počet požadovaných shluků nsh, počet průběhů algoritmu IT a parametr s , který se používá při výpočtu jádrové verze funkce RBF. Počet požadovaných shluků je nutno zadat podle charakteru vstupních dat. Počet průběhů algoritmu v podstatě určuje, z kolika řešení bude program vybírat nejlepší řešení.
Na počátku každého průběhu určíme náhodně počáteční podmínky: všechny body
přiřadíme do třídy 1 a náhodně vybraných (nsh-1) bodů přiřadíme do
zbylých tříd. Následně počítáme vzdálenost všech bodů x od jednotlivých
shluků pomocí výrazu (1
) a každý bod přiřadíme do shluku vůči jehož těžišti má nejmenší vzdálenost.
Tento proces opakujeme do té doby, dokud se příslušnosti jednotlivých bodů
ke shlukům mění. Dá se dokázat, že tento proces má konečný počet kroků. Nakonec
počítáme součet kvadrátů vzdáleností vzd všech bodů od příslušejících
těžišť.
Celý algoritmus se opakuje IT krát a vybírá se řešení s minimálním
vzd.
Po ukončení algoritmu k-means počítáme kontury shluků. Jelikož není vždy
možné znát transformaci z vysokodimenzionálního prostoru do 2-D prostoru,
zvolili jsme následující postup.
Nejdříve spočítáme minimální poloměr vysokodimenzionální koule, která obepíná
každý shluk. Zvolíme čtvercovou síť bodů ve 2D prostoru a přiřadíme jim konstantní
hodnotu. Pro každý bod počítáme jeho vzdálenost od každého shluku. Pokud
je příslušná vzdálenost od shluku menší než minimální poloměr tohoto shluku,
přiřadíme tomuto bodu jinou konstantní hodnotu. Hodnoty této čtvercové sítě
bodů jsou pak vstupními parametry funkce contour.
Existuje možnost, že se kontury překrývají, pak místo překrývajících se kontur
zobrazí funkce contour jejich obal.
Algoritmus k-means nelinearizovaný pomocí jádrových funkcí dokáže
řešit libovolně složité úlohy, které by pomocí klasického k-means
algoritmu řešit nešly, protože data jsou pomocí jádrových funkcí tránsformována
do prostoru vyšší (až nekonečné) dimenze, kde lze nalézt separační nadplochy.
Data ale musí vystupovat ve formě skalárních součinů, což velmi zpomaluje
výpočet.
Výsledky algoritmu jsou velmi závislé na počátečních podmínkách. Pro optimální
rozdělení do shluků je nutné zadávat parametr IT dostatečně velký,
protože po každém průchodu algoritmu se dospěje do minima, které nemusí být
globální. Vyšším počtem průchodů algoritmem je proto pravděpodobnost nalezení
globálního minima větší, ale nikdy není 100%.
Úspěšnost algoritmu je také závislá na parametrech použitých jádrových funkcí.
Jedná se o parametr s. Ten u polynomiální jádrové funkce udává řád
polynomu. Jeho vhodná volba je také důležitá při použití RBF funkce.
Při použití polynomiálního jádra jsme nedosáhli očekávaného zlepšení vůči
jádru lineárnímu. Daleko větší zlepšení shlukování lineárně neseparabilních
dat se projevilo při použití RBF jádra.
Zobrazení kontur není vzhledem k výpočetním možnostem zcela přesné, ale pro
názornou představu je dostačující.