Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26672
Titel: Graph-based methods for unsupervised and semi-supervised data analysis
Sonstige Titel: Graph-basierte Methoden zur unüberwachten und teilüberwachten Datenanalyse
Verfasser: Rangapuram, Syama Sundar
Sprache: Englisch
Erscheinungsjahr: 2016
SWD-Schlagwörter: Maschinelles Lernen
Optimierung
Graphpartitionierung
Cluster-Analyse
Freie Schlagwörter: machine learning
optimization
graph partitioning
clustering
constrained clustering
community detection
data analysis
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: Clustering and community detection are two important problems in data analysis with applications in various disciplines. Often in practice, there exists prior knowledge that helps the process of data analysis. In this thesis we develop generic graph-based methods for these data analysis problems both in unsupervised and semi-supervised settings. The main advantage of our methods is that they provide a common framework for integrating soft as well as hard prior knowledge. In the latter case, ours is the first method to have provable guarantees on the satisfaction of the given prior knowledge. The foundation of our methods is the exact continuous relaxation result that we derive for a class of combinatorial optimization problems. More specifically, we show that the (constrained) minimization of a ratio of set functions can be equivalently rewritten as a continuous optimization problem. We also present efficient algorithms for solving the continuous relaxations. While the global optimality is not guaranteed, in practice our methods consistently outperform the corresponding convex or spectral relaxations by a large margin. Moreover, our method has an additional guarantee that the solution respects the prior knowledge.
Clustering und Community Detection sind zwei bedeutende Probleme in der Datenanalyse, mit vielfältigen Anwendungen in unterschiedlichen Bereichen. In der Praxis existiert häufig Vorwissen das in den Prozess der Datenanalyse einfließen kann. In dieser Arbeit entwickeln wir generische Graph-basierte Methoden für diese Problemstellungen der Datenanalyse, sowohl für den unüberwachten als auch den teilüberwachten Fall. Der Hauptvorteil unserer Verfahren ist dass sie ein allgemeines Framework zur Integration von weichen und harten Nebenbedingungen bereitstellen. In letzterem Fall ist unsere Methode die erste die beweisbare Garantien zur Erfüllung des gegebenen Vorwissen liefern kann. Die Grundlage unserer Methoden ist ein Resultat über exakte kontinuierliche Relaxierungen das wir für eine Klasse von kombinatorischen Optimierungsproblemen herleiten. Konkret zeigen wir dass die (beschränkte) Minimierung eines Bruches von Mengenfunktionen in ein äquivalentes kontinuierliches Optimierungsproblem umgeformt werden kann. Des Weiteren präsentieren wir effiziente Algorithmen zur Lösung der kontinuierlichen Relaxierungen. Während die globale Optimalität nicht garantiert werden kann, werden die entsprechenden konvexen oder spektralen Relaxierungen in der Praxis mit einem deutlichen Vorsprung übertroffen. Darüber hinaus hat unsere Methode eine zusätzliche Garantie dass die berechnete Lösung das Vorwissen stets berücksichtigt.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-66590
hdl:20.500.11880/26728
http://dx.doi.org/10.22028/D291-26672
Erstgutachter: Hein, Matthias
Tag der mündlichen Prüfung: 10-Okt-2016
SciDok-Publikation: 21-Okt-2016
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
PhDThesis_Rangapuram_2016.pdf3,79 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.