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

Thesis title: Miery podobnosti pre dátové súbory s binárnymi premennými a ich aplikácia v aglomeratívnej zhlukovej analýze
Author: Cibulková, Jana
Thesis type: Dissertation thesis
Supervisor: Řezanková, Hana
Opponents: Pecáková, Iva; Žambochová, Marta
Thesis language: Slovensky
Abstract:
Dizertačná práca je zameraná na miery podobnosti pre objekty charakterizované binárnymi premennými. Cieľom práce je analyzovať vlastnosti týchto mier, analyzovať vzťahy medzi nimi a navrhnúť spôsob ich klasifikácie s ohľadom na ich aplikáciu v hierarchickej aglomeratívnej zhlukovej analýze. Vedľajším cieľom práce je navrhnúť metodológiu generovania dátových súborov vhodných pre zhlukovú analýzu. Práca spracúva 104 unikátnych názvov mier podobnosti vyskytujúcich sa v základnej literatúre. Po odhalení a odstránení redundantných názvov je nakoniec v práci analyzovaných celkom 78 mier, ktoré sú v práci usporiadané do sumáru mier. Tento sumár poskytuje jednak lexikologický zoznam mier a navyše uvádza aj ich základné vlastnosti (typ miery, obor hodnôt, singularita, konvergencia v limite atď.), ktoré v zdrojovej literatúre často chýbajú. Práca sa v krátkosti venuje aj piatim mieram podobnosti pre objekty charakterizované nominálnymi premennými a hľadá ich binárne náprotivky. Ďalej sú odhalené a popísané funkčné vzťahy medzi všetkými skúmanými mierami. V práci sú zadefinované požiadavky na miery použiteľné v aglomeratívnej zhlukovej analýze, čo spĺňa 69 jedinečných mier (65 mier pre binárne dáta a štyri miery pre nominálne dáta). Tieto miery sú najprv analyzované pomocou korelačnej a faktorovej analýzy a roztriedené do štyroch skupín podľa tvaru funkcie, pričom cieľom je odhaliť skryté asociácie medzi mierami. Analýza vplyvu výberu podobnostnej miery na výstupy zhlukovej analýzy je realizovaná experimentom vo forme simulačnej štúdie na 270 generovaných dátových súboroch so špecifickými vlastnosťami. Pretože nie sú dostupné postupy, ktoré by umožnili generovať dátové súbory s požadovanými vlastnosťami, bol v rámci tejto dizertačnej práce navrhnutý vlastný postup generovania dátových súborov pre použitie v zhlukovej analýze. Novo navrhnutá metodológia principiálne vychádza zo zhlukových metód založených na modeloch a kombinuje NORTA algoritmus s Choleského dekompozíciou. V experimente sú použité tri základné metódy zhlukovania: metóda priemernej väzby medzi zhlukmi, metóda najbližšieho suseda a metóda najvzdialenejšieho suseda. Vzájomná podobnosť zhlukových riešení bola pre každú mieru analyzovaná na posledných šiestich krokoch zhlukovacieho procesu pomocou Randovho indexu. Vychádzajúc zo zhody priradenia objektov do zhlukov medzi mierami boli identifikované tri skupiny mier, ktoré vedú k veľmi podobným až identickým zhlukovým riešeniam. Vďaka roztriedeniu 69 mier do troch skupín, ktoré vedú k prakticky rovnakým zhlukovým riešeniam, je možné výrazne zjednodušiť proces výberu miery.
Keywords: hierarchická zhluková analýza; miera vzdialenosti; generovanie dát; binárne dáta; miera podobnosti; miera nepodobnosti
Thesis title: Miery podobnosti pre dátové súbory s binárnymi premennými a ich aplikácia v aglomeratívnej zhlukovej analýze
Author: Cibulková, Jana
Thesis type: Disertační práce
Supervisor: Řezanková, Hana
Opponents: Pecáková, Iva; Žambochová, Marta
Thesis language: Slovensky
Abstract:
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.
Keywords: generování dat; hierarchická shluková analýza; binární data; míra podobnosti; míra nepodobnosti; míra vzdálenosti
Thesis title: Similarity measures for data sets with binary variables and their application in agglomerative cluster analysis
Author: Cibulková, Jana
Thesis type: Dissertation thesis
Supervisor: Řezanková, Hana
Opponents: Pecáková, Iva; Žambochová, Marta
Thesis language: Slovensky
Abstract:
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.
Keywords: hierarchical cluster analysis; data generator; binary data; similarity measure; dissimilarity measure; distance measure

Information about study

Study programme: Kvantitativní metody v ekonomice/Statistika
Type of study programme: Doktorský studijní program
Assigned degree: Ph.D.
Institutions assigning academic degree: Vysoká škola ekonomická v Praze
Faculty: Faculty of Informatics and Statistics
Department: Department of Statistics and Probability

Information on submission and defense

Date of assignment: 16. 9. 2016
Date of submission: 15. 6. 2023
Date of defense: 5. 9. 2023
Identifier in the InSIS system: https://insis.vse.cz/zp/58416/podrobnosti

Files for download

    Last update: