Cluster analysis of large data sets: new procedures based on the method k-means

Abstrakt Shluková analýza se stala jedním z hlavních nástrojů používaných při získávání znalostí z dat, které je označováno jako data mining. V této nové oblasti analýzy dat se často zpracovávají datové soubory velkých rozměrů, a to jak co do počtu sledovaných objektů, tak co do počtu proměnných, kterými jsou objekty charakterizovány. Pro shlukování dat bylo vyvinuto mnoho metod. Jednou z často používaných technik je metoda k-průměrů. Jejím základem je hledání nejlepšího přiřazení objektů do shluků na principu inicializačního rozdělení objektů a následného postupného přerozdělování s využitím optimalizační funkce. Cílem této disertační práce bylo jednak porovnání vybraných existujících variant metody k-průměrů, detailní charakteristika jejich pozitivních a negativních vlastností, jednak návrh nových modifikací této metody a jejich experimentální srovnání s již existujícími přístupy. Tyto cíle byly splněny. Ve své práci jsem se zaměřila na modifikace metod k-průměrů pro shlukování velkého počtu objektů, konkrétně na algoritmy BIRCH k-průměrů, filtrovací, dvou- fázový a k-průměrů++. Experimentálně jsem sledovala časovou náročnost jednotlivých algoritmů, vliv inicializačních rozdělení, vliv odlehlých objektů a validitu výsledných shluků. Při experimentech byly použity dva reálné datové soubory a dále několik souborů generovaných. V závěru práce jsou shrnuty společné a rozdílné rysy zkoumaných variant metody k-průměrů s důrazem na výše uvedená hlediska. Přínosem práce je tedy kromě zhodnocení současných variant metody k-průměrů především návrh výše uvedených nových modifikací, jejich naprogramování a experi- mentální ověření. Modifikace přinesly zejména urychlení výpočtu způsobené zjedno- dušením práce s účelovou funkcí a kritérií ukončení programu. Aplikování hlavní myšlenky algoritmu k-průměrů++ do jiných variant metody k-průměrů přineslo lepší vý-sledky shlukování z hlediska variability. Nejzásadnější z navržených změn je modifi-kace filtrovacího algoritmu, která přináší zcela novou vlastnost této metody, a to odhalení odlehlých objektů. Součástí práce je CD, které obsahuje zdrojové kódy jednotlivých programů vytvořených ve vývojovém prostředí MATLAB. Programy byly vytvořeny speciálně pro účely této práce a jsou určeny pro experimentální použití. CD také obsahuje datové soubory využívané k jednotlivým pokusům.