Anzeige
Erschienen in:
2020 | OriginalPaper | Buchkapitel
An Approximation Algorithm for a Semi-supervised Graph Clustering Problem
verfasst von : Victor Il’ev, Svetlana Il’eva, Alexander Morshinin
Erschienen in: Mathematical Optimization Theory and Operations Research
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Clustering problems form an important section of data analysis. In machine learning clustering problems are usually classified as unsupervised learning. Semi-supervised clustering problems are also considered. In these problems relatively few objects are labeled (i.e., are assigned to clusters), whereas a large number of objects are unlabeled.
We consider the most visual formalization of a version of semi-supervised clustering. In this problem one has to partition a given set of n objects into k clusters (\(k < n\)). A collection of k pairwise disjoint nonempty subsets of objects is fixed. No two objects from different subsets of this collection may belong to the same cluster and all objects from any subset must belong to the same cluster. Similarity of objects is determined by an undirected graph. Vertices of this graph are in one-to-one correspondence with objects, and edges connect similar objects. One has to partition the vertices of the graph into pairwise disjoint groups (clusters) minimizing the number of edges between clusters and the number of missing edges inside clusters.
The problem is NP-hard for any fixed \(k \ge 2\). For \(k = 2\) we present a polynomial time approximation algorithm and prove a performance guarantee of this algorithm.