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.Abstract Cluster analysis has become one of the main tools used in extracting knowledge from data, which is known as data mining. In this area of data analysis, data of large dimensions are often processed, both in the number of objects and in the number of variables, which characterize the objects. Many methods for data clustering have been developed. One of the most widely used is a k-means method, which is suitable for clustering data sets containing large number of objects. It is based on finding the best clustering in relation to the initial distribution of objects into clusters and subsequent step-by-step redistribution of objects belonging to the clusters by the optimization function. The aim of this Ph.D. thesis was a comparison of selected variants of existing k-means methods, detailed characterization of their positive and negative characte- ristics, new alternatives of this method and experimental comparisons with existing approaches. These objectives were met. I focused on modifications of the k-means method for clustering of large number of objects in my work, specifically on the algorithms BIRCH k-means, filtering, k-means++ and two-phases. I watched the time complexity of algorithms, the effect of initialization distribution and outliers, the validity of the resulting clusters. Two real data files and some generated data sets were used. The common and different features of method, which are under investigation, are summarized at the end of the work. The main aim and benefit of the work is to devise my modifications, solving the bottlenecks of the basic procedure and of the existing variants, their programming and verification. Some modifications brought accelerate the processing. The application of the main ideas of algorithm k-means++ brought to other variants of k-means method better results of clustering. The most significant of the proposed changes is a modification of the filtering algorithm, which brings an entirely new feature of the algorithm, which is the detection of outliers. The accompanying CD is enclosed. It includes the source code of programs written in MATLAB development environment. Programs were created specifically for the purpose of this work and are intended for experimental use. The CD also contains the data files used for various experiments