Dokument: Fuzzy Clustering of Incomplete Data

Titel:Fuzzy Clustering of Incomplete Data
URL für Lesezeichen:https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=37036
URN (NBN):urn:nbn:de:hbz:061-20160203-101814-0
Kollektion:Dissertationen
Sprache:Englisch
Dokumententyp:Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:Text
Autor: Himmelspach, Ludmila [Autor]
Dateien:
[Dateien anzeigen]Adobe PDF
[Details]1,76 MB in einer Datei
[ZIP-Datei erzeugen]
Dateien vom 01.02.2016 / geändert 01.02.2016
Beitragende:Prof. Dr. Conrad, Stefan [Betreuer/Doktorvater]
Prof. Dr. Lercher, Martin [Gutachter]
Dewey Dezimal-Klassifikation:000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Beschreibungen:Clustering is one of the important and primarily used techniques for the automatic knowledge extraction from large amounts of data. Its task is identifying groups, so-called clusters, of similar objects within a data set. Clustering methods are used in many areas, including database marketing, web analysis, information retrieval, bioinformatics, and many others. However, if clustering methods are applied on real data sets, a problem that often comes up is that missing values occur in the data sets. Since traditional clustering methods were developed to analyze complete data, there is a need for data clustering methods handling incomplete data. Approaches proposed in the literature for adapting the clustering algorithms to incomplete data work well on data sets with equally scattered clusters. In this thesis we present a new approach for adapting the fuzzy c-means clustering algorithm to incomplete data
that takes the scatters of clusters into account. In the experiments on artificial and real data sets with differently scattered clusters we show that our approach outperforms the other clustering methods for incomplete data.

Since the quality of the partitioning of data produced by the clustering algorithms strongly depends on the assumed number of clusters, in the second part of the thesis we address the problem of finding the optimal nummber of clusters in incomplete data using cluster validity functions. We describe different cluster validity functions and adapt them to incomplete data according to the ``available-case'' approach. We analyze the original and the adapted cluster validity functions using the partitioning results of several artificial and real data sets produced by different fuzzy
clustering algorithms for incomplete data. Since both the clustering algorithms and the cluster validity functions are adapted to incomplete data, our aim is finding the factors that are crucial for determining the optimal number of clusters on incomplete data: the adaption of the clustering algorithms, the adaption of the cluster validity functions, or the loss of information in the data itself.

Discovering clusters of varying shapes, sizes and densities in a data set is more useful for some applications than just partitioning the complete data set. As a result, density-based clustering methods become more important. Recently presented approaches either require the input parameters involving the information about the structure of the data set, or are restricted to two-dimensional data. In the last part of the thesis, we present a novel density-based clustering algorithm, which uses the fuzzy proximity relations between the data objects for discovering differently dense clusters without any a-priori knowledge of a data set. In experiments, we show that our approach is able to correctly detect the clusters closely located to each other and clusters with wide density variations.

Clustering ist eine der wichtigen und primär benutzten Techniken für die automatische Wissensextraktion auf großen Datenmengen. Seine Aufgabe ist es Gruppen, so genannte Cluster, von ähnlichen Objekten auf Datenmengen zu identifizieren. Die Methoden der Clusteranalyse finden in vielen Bereichen ihre Anwendung, einschließlich Database Marketing, Web-Analyse, Information Retrieval, Bioinformatik, und vielen anderen. Wenn Clusteringmethoden jedoch auf realen Daten angewendet werden, entsteht oft das Problem, dass fehlende Werte in Datenmengen vorkommen. Da die klassischen Clusteringmethoden entwickelt wurden, um auf vollständigen Daten Analysen durchzuführen, werden Clusteringmethoden benötigt, die mit unvollständigen Daten umgehen können. Die in der Literatur vorgeschlagenen
Verfahren zum Anpassen der Clusteringmethoden auf unvollständige Daten funktionieren gut auf Datenmengen mit gleichgroßen Clustern. In dieser Dissertation stellen wir ein neues Verfahren zum Anpassen des Fuzzy C-Means Algorithmus an unvollständige Daten vor, das die Streuung der Cluster berücksichtigt. In Experimenten auf künstlichen und realen Datensätzen mit unterschiedlich großen Clustern zeigen wir, dass die Leistung unseres Verfahrens andere Clusteringmethoden für unvollständige Daten übertrifft.

Da die Qualität der Partitionierung von Daten, die von den
Clusteringalgorithmen erzeugt wird, stark von der angenommenen Clusteranzahl abhängt, befassen wir uns im zweiten Teil der Doktorarbeit mit dem Problem der Bestimmung der optimalen Clusteranzahl auf unvollständigen Daten mittels Indizes zur Clustervalidierung. Wir beschreiben unterschiedliche Gütekriterien
zur Clustervalidierung und passen sie entsprechend der "available-case"-Methode auf unvollständige Daten an. Wir analysieren
die originalen und die angepassten Indizes zur Clustervalidierung unter der Benutzung der Partitionierungsergebnisse von mehreren künstlichen und realen Datensätzen, die von unterschiedlichen Fuzzy Clusteringalgorithmen für unvollständige Daten erzeugt wurden. Da sowohl die Clusteringalgorithmen als auch die Bewertungsfunktionen auf unvollständige Daten angepasst wurden, ist es unser Ziel die Faktoren zu bestimmen, die für die Bestimmung der optimalen Clusteranzahl auf unvollständigen Daten ausschlaggebend sind: das Anpassen von Clusteringalgorithmen, das Anpassen von Funktionen zur Clustervalidierung oder der Informationsverlust in Daten.

Für einige Anwendungen ist die Bestimmung von Clustern unterschiedlicher Form, Größe und Dichte in Datenmengen nützlicher als die bloße Partitionierung des kompleten Datensatzes. Infolgedessen gewinnen die dichtebasierten Clusteringmethoden zunehmend an Bedeutung. Die jüngst
vorgestellten Verfahren erfordern entweder Eingabeparameter, die Information über die Datensatzstruktur erfordern, oder sind auf zweidimensionale Daten beschränkt. Im letzten Teil der Doktorarbeit stellen wir einen neuen dichtebasierten Clusteringalgorithmus vor, der sich Fuzzy Proximity Relationen
zwischen den Datenobjekten zu Nutze macht, um Cluster unterschiedlicher Dichte ohne jedes a-priori Wissen über den Datensatz aufzufinden. Wir zeigen in Experimenten, dass unser Verfahren fähig ist, die dicht beieinanderliegenden Cluster und Cluster stark variierender Dichte korrekt zu bestimmen.
Lizenz:In Copyright
Urheberrechtsschutz
Fachbereich / Einrichtung:Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Datenbanken und Informationssysteme
Dokument erstellt am:03.02.2016
Dateien geändert am:03.02.2016
Promotionsantrag am:20.11.2015
Datum der Promotion:10.12.2015
english
Benutzer
Status: Gast
Aktionen