Similarity measures for data sets with binary variables and their application in agglomerative cluster analysis

Disertační práce je zaměřena na míry podobnosti pro objekty charakterizované binárními proměnnými. Cílem práce je analyzovat vlastnosti těchto měr, analyzovat vztahy mezi nimi a navrhnout způsob jejich klasifikace s ohledem na jejich aplikaci v hierarchické aglomerativní shlukové analýze. Vedlejším cílem práce je navrhnout metodologii generování datových souborů vhodných pro shlukovou analýzu. Práce zpracovává 104 unikátních názvů měr podobnosti vyskytujících se v základní literatuře. Po odhalení a odstranění redundantních názvů je nakonec v práci analyzováno celkem 78 měr, které jsou v práci uspořádány do sumáře měr. Tento sumář poskytuje jednak lexikologický seznam měr a navíc uvádí i jejich základní vlastnosti (typ míry, obor hodnot, singularita, konvergence v limitě atd.), které v zdrojové literatuře často chybí. Práce se krátce věnuje také pěti měrám podobnosti pro objekty charakterizované nominálními proměnnými a hledá jejich binární protějšky. Dále jsou odhaleny a popsány funkční vztahy mezi všemi zkoumanými měřeními. V práci jsou zadefinovány požadavky na míry použitelné v aglomerativní shlukové analýze, což splňuje 69 jedinečných měř (65 měř pro binární data a čtyři míry pro nominální data). Tyto míry jsou nejprve analyzována pomocí korelační a faktorové analýzy a rozdělena do čtyř skupin podle tvaru funkce, přičemž cílem je odhalit skryté asociace mezi mírami. Analýza vlivu výběru podobnostní míry na výstupy shlukové analýzy je realizována experimentem ve formě simulační studie na 270 generovaných datových souborech se specifickými vlastnostmi. Protože nejsou dostupné postupy, které by umožnily generovat datové soubory s požadovanými vlastnostmi, byl v rámci této disertační práce navržen vlastní postup generování datových souborů pro použití v shlukové analýze. Nově navržená metodologie principiálně vychází ze shlukových metod založených na modelech a kombinuje NORTA algoritmus s Choleského dekompozicí. V experimentu jsou použity tři základní metody shlukování: metoda průměrné vazby mezi shluky, metoda nejbližšího souseda a metoda nejvzdálenějšího souseda. Vzájemná podobnost shlukových řešení byla pro každou míru analyzována na posledních šesti krocích shlukovacího procesu pomocí Randova indexu. Vycházejíc ze shody přiřazení objektů do shluků mezi měřeními byly identifikovány tři skupiny měř, které vedou k velmi podobným až identickým shlukovým řešením. Díky rozdělení 69 měření do tří skupin, které vedou k prakticky stejným shlukovým řešením, je možné výrazně zjednodušit proces výběru míry.

The dissertation thesis focuses on similarity measures for objects characterized by binary variables. The thesis aims to analyze the properties of these measures, examine the relationships between them, and propose a method for their classification with respect to their application in hierarchical agglomerative cluster analysis. A secondary aim of the thesis is to propose a methodology for generating data sets suitable for cluster analysis. The thesis deals with 104 unique names of similarity measures available in the literature. Due to the deletion of redundant measures’ names, there are 78 measures analyzed in the thesis, which are summarized in a summary of measures. This summary provides a list of measures and also presents their basic properties (type of measure, range of values, singularity, convergence in limit, etc.), which are often missing in the source literature. The thesis briefly addresses five similarity measures for objects characterized by nominal variables and seeks their binary counterparts. Furthermore, functional relationships between all the examined measures are identified and described. The thesis also defines requirements for measures suitable for agglomerative cluster analysis, which are fulfilled by 69 unique measures (65 measures for binary data and four measures for nominal data). Firstly, these measures are analyzed using correlation and factor analysis and classified into four groups based on the shape of the function, with the aim of revealing hidden associations between the measures. Then, the main analysis of the impact of similarity measure selection on the outputs of cluster analysis is conducted through a simulation study on 270 generated data sets with specific characteristics. Since no existing methods can generate data sets with such desired features, a new method for generating datasets suitable for cluster analysis was designed within this dissertation. The newly proposed methodology is based on model-based clustering methods and combines the NORTA algorithm with Cholesky decomposition. The experiment utilizes three basic clustering methods: average linkage, nearest neighbor, and farthest neighbor. The similarity between cluster solutions was analyzed for each measure in the last six steps of the clustering process using the Rand index. Based on the agreement of object assignments to clusters among the measures, three groups of measures were identified, leading to very similar or identical cluster solutions. By categorizing the 69 measures into three groups that result in practically the same cluster solutions, the process of measure selection can be significantly simplified.