Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-1237
Main Title: Clustering and Prototype Based Classification
Translated Title: Clustering und Prototyp-basierte Klassifikation
Author(s): Seo, Sambu
Advisor(s): Obermayer, Klaus
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Die Arbeit besteht aus zwei Themengebieten, die mehr oder weniger unabhängig voneinander sind. Im ersten Teil dieser Arbeit geht es um die Entwicklung von Algorithmen für einen Nächsten-Prototyp-Klassifikator (engl.: nearest prototype classifier (NPC)). Der zweite Teil behandelt Clustering und Visualisierung von Matrix-Daten. Um einen neuen Datenpunkt zu klassifizieren, muss NPC lediglich die Distanzen zwischen dem Datenpunkt und den Prototypen vergleichen und dem Datenpunkt die Klasse des nächsten Prototyps zuweisen. Weil die Entscheidungsregel sehr einfach und schnell ist, werden NPCs häufig für Echtzeit-Anwendungen wie Spracherkennung verwendet. Learning Vector Quantization (LVQ) ist eine Familie von heuristisch gut gewählten adaptiven Lernalgorithmen für NPC. Der weit verbreitete LVQ 2.1 ist ein Beispiel für einen LVQ Algorithmus, der gute Klassifikationsergebnisse liefert. Da er jedoch heuristisch ist, kann es sein, dass der resultierende NPC nicht optimal ist. Aus diesen Gründen leite ich drei Varianten der LVQ-Methode über einen prinzipielleren Ansatz her. Dabei modelliere ich die Wahrscheinlichkeitsdichte der Daten mittels eines Gauss'schen Mischungs-Modells. Für einen Datenpunkt x und sein Klassenlabel y definiere ich zwei eingeschränkte Wahrscheinlichkeitsdichten, dass x vom Gauss'schen Mischungs-Modell für die Klasse y bzw. die anderen Klassen als y generiert wird. Aus den beiden eingeschränkten Wahrscheinlichkeitsdichten definiere ich drei Kostenfunktionen: eine Fehlklassifikationsrate und zwei Likelihood-Quotienten. Aus den Kostenfunktionen leite ich die Lernalgorithmen für den NPC über eine stochastische Gradientenmethode her. Ich untersuche im weiteren die Eigenschaften der Kostenfunktionen und der Lernalgorithmen und gebe dabei erstmalig eine analytische Begründung für LVQ 2.1. Die vorgeschlagenen Methoden ermöglichen die Erweiterung der LVQ-Familie auf weiche Klassifikation und auf verschiedene Distanzmaße. Bei den Experimenten erzielten die vorgeschlagenen Lernalgorithmen bessere Klassifikationsergebnisse als bisherige LVQ Algorithmen. Ich habe einen neuen Clusteringalgorithmus für paarweise Daten mit Hilfe der Rate-Distortion-Theorie hergeleitet. Ausserdem habe ich die strukturellen Phasenübergänge von dem hergeleiteten Algorithmus und einem Entropie-basierten paarweisen Clusteringalgorithmus mittels einer linearen Stabilitätsanalyse untersucht und dadurch die kritischen Werte des Lagrange-Multipliers berechnet. Um die Konvergenz zu einem lokalen Optimum zu vermeiden, habe ich eine neue Optimierungsmethode, nämlich inkrementelles Splitting für paarweise Clusteringalgorithmen, vorgeschlagen. Für Visualisierungszwecke habe ich die Self-Organizing Map (SOM) Methode auf den hergeleiteten Clusteringalgorithmus und die Information Bottleneck Methode angewandt und so nachbarschaftserhaltende Clusteringalgorithmen für paarweise Daten und Co-ocurrence Daten hergeleitet. Die hergeleiteten neuen Lernalgorithmen und die vorgeschlagene Splitting Methode habe ich auf Protein-, DNA-Micro-Array- und Dokument-Daten angewandt.
The thesis contains to topics, which are more or less independent. The first part deals with the development of algorithms for a nearest prototype classifier (NPC). The second part is concerned with clustering and visualization of matrix data. In order to classify a new data point NPC just has to compare the distances between the data point and the prototypes, and to assign the class of the nearest prototype to the data point. Because the decision rule is very simple and fast, NPCs are often used in real-time applications like speech-recognition. Learning Vector Quantization (LVQ) is a family of heuristically well chosen adaptive learning algorithms for NPC. The widely used LVQ 2.1 is an example for an LVQ algorithm which provides good classification performance. Because it is heuristic, the resulting NPC classifier may not be optimal. For these reasons I derive three variants of the LVQ method via a principled approach. To this end, I model the probability density of the data via a Gaussian mixture model. For a data point x and its class label y I define two restricted probability densities, that x was generated by the mixture model for class y or the other classes, respectively. From the restricted probability densities I define three cost functions: a misclassification rate and two likelihood ratios. Using these cost functions, I derive learning algorithms for the NPC via a stochastic gradient method. Moreover, I study the characteristics of the cost functions and the learning algorithms, and for the first time give an analytical explanation for LVQ 2.1. The proposed methods permit the extension of LVQ to different distance measures. In the experiments, the proposed learning algorithms achieved better classification performance than previous LVQ algorithms. I derive a new clustering algorithm for pair-wise data via the rate-distortion theory. Additionally, I analyse the structural phase transitions of the derived algorithm and an entropy based pair-wise clustering algorithm using a linear stability analysis, calculating the critical values of the Lagrangian multiplier. In order to prevent the convergence to a local optimum, I propose a new optimization method, called incremental splitting for pair-wise clustering algorithms. For visualization purposes, I apply the Self-Organizing-Map (SOM) method on the derived clustering algorithm and the Information Bottleneck method, thus deriving neighbourhood-preserving clustering algorithms for pair-wise and co-occurrence data. I apply the derived novel learning algorithms and the proposed splitting method on protein, DNA-micro-array and document data.
URI: urn:nbn:de:kobv:83-opus-11453
http://depositonce.tu-berlin.de/handle/11303/1534
http://dx.doi.org/10.14279/depositonce-1237
Exam Date: 7-Nov-2005
Issue Date: 18-Nov-2005
Date Available: 18-Nov-2005
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): Clustering
LVQ
Prototyp
SOM Klassifikation
Classification
Clustering
LVQ
Prototype
SOM
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Softwaretechnik und Theoretische Informatik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_44.pdf1.67 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.