Relaxed Oracles for Semi-Supervised Clustering
Pairwise "same-cluster" queries are one of the most widely used forms of supervision in semi-supervised clustering. However, it is impractical to ask human oracles to answer every query correctly. In this paper, we study the influence of allowing "not-sure" answers from a weak oracle and propose an effective algorithm to handle such uncertainties in query responses. Two realistic weak oracle models are considered where ambiguity in answering depends on the distance between two points. We show that a small query complexity is adequate for effective clustering with high probability by providing better pairs to the weak oracle. Experimental results on synthetic and real data show the effectiveness of our approach in overcoming supervision uncertainties and yielding high quality clusters.
Code (1)
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Embedding Graph Auto-Encoder for Graph Clustering
Graph clustering, aiming to partition nodes of a graph into various groups via an unsupervised approach, is an attractive topic in recent years. To improve the representative ability, several graph auto-encoder (GAE) mod…
ClusteringDecoderGraph ClusteringSemi-Supervised Active Clustering with Weak Oracles
Semi-supervised active clustering (SSAC) utilizes the knowledge of a domain expert to cluster data points by interactively making pairwise "same-cluster" queries. However, it is impractical to ask human oracles to answer…
ClusteringMinimal Dirichlet energy partitions for graphs
Motivated by a geometric problem, we introduce a new non-convex graph partitioning objective where the optimality criterion is given by the sum of the Dirichlet eigenvalues of the partition components. A relaxed formulat…
Clusteringgraph partitioningSemi-Supervised Nonlinear Distance Metric Learning via Forests of Max-Margin Cluster Hierarchies
Metric learning is a key problem for many data mining and machine learning applications, and has long been dominated by Mahalanobis methods. Recent advances in nonlinear metric learning have demonstrated the potential po…
ClusteringImage RetrievalMetric LearningRetrievalSmile-GANs: Semi-supervised clustering via GANs for dissecting brain disease heterogeneity from medical images
Machine learning methods applied to complex biomedical data has enabled the construction of disease signatures of diagnostic/prognostic value. However, less attention has been given to understanding disease heterogeneity…
ClusteringDiagnostic