Not logged in.

Quick Search - Contribution

Contribution Details

Type Bachelor's Thesis
Scope Discipline-based scholarship
Title Clustering high-dimensional sparse data
Organization Unit
Authors
  • Manuel Gugger
Supervisors
  • Abraham Bernstein
  • Floarea Serban
Language
  • English
Institution University of Zurich
Faculty Faculty of Economics, Business Administration and Information Technology
Number of Pages 48
Date 2012
Abstract Text This work is a practical approach on evaluating clustering algorithms on different datasets to examine their behaviour on high-dimensional and sparse datasets. High-Dimensionality and sparsity poses high demands on the algorithms due to missing values and computational requirements. It has already been proven that algorithms perform significantly worse under high-dimensional and sparse data. Here approaches to circumvent these difficulties are analysed. Distance matrices and recommender systems have been examined to either reduce the complexity or to impute missing data. A special focus is then put on the similarity between clustering solutions with the goal of finding a similar behaviour. The emphasis lies on getting flexible results instead of highly tweaking certain algorithms as the problem can not be solemnly reduced to the mathematical performance due to missing values. Generally good and flexible results have been achieved with a combination of content-based-filtering and hierarchical clustering methods or the affinity propagation algorithm. Kernel based clustering results differed much from other methods and were sensitive to changes on the input data.
Zusammenfassung Diese Arbeit stellt eine praktische Herangehensweise an die Evaluation von Clustering-Algorithmen und deren Performance auf verschiedenen hoch-dimensionalen und kargen Datensätzen dar. Solche Datensätze stellen hohe Anforderungen an die Algorithmen in bezug auf den Rechenaufwand und Annahmen, welche getroffen werden müssen. Es werden Ansätze zur Lösung und Optimierung dieses mehrstufigen Problems diskutiert. Distanzmatrizen und Recommender-Systeme wurden eingesetzt, um die Komplexität des Problems zu reduzieren und um fehlende Werte zu berechnen. Der Hauptfokus lag im Vergleich der einzelnen Methoden in Bezug auf die ähnlichkeit der Resultate mit dem Ziel, ähnliches Verhalten zu finden. Ein weiterer Schwerpunkt lag auf der Flexibilität der Algorithmen bezüglich den Datensätzen, da auch die Kargheit der Daten sowie die Dimensionalität einen grossen Einfluss auf das Problem haben. Generell wurden mit einer Kombination von Recommender-Systemen, hierarchischen Methoden und Affinity Propagation gute Resultate erzielt. Kernel-basierte Algorithmen waren sensitiv bezüglich Änderungen im Ausgangsdatensatz.
PDF File Download
Export BibTeX