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 |
Alternativtitel: | Graph-basierte Methoden zur unüberwachten und teilüberwachten Datenanalyse |
VerfasserIn: | Rangapuram, Syama Sundar |
Sprache: | Englisch |
Erscheinungsjahr: | 2016 |
Kontrollierte 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 |
Dokumenttyp: | Dissertation |
Abstract: | 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 |
Datum des Eintrags: | 21-Okt-2016 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Informatik |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
PhDThesis_Rangapuram_2016.pdf | 3,79 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.