Clustering without Over-Representation
In this paper we consider clustering problems in which each point is endowed with a color. The goal is to cluster the points to minimize the classical clustering cost but with the additional constraint that no color is over-represented in any cluster. This problem is motivated by practical clustering settings, e.g., in clustering news articles where the color of an article is its source, it is preferable that no single news source dominates any cluster. For the most general version of this problem, we obtain an algorithm that has provable guarantees of performance; our algorithm is based on finding a fractional solution using a linear program and rounding the solution subsequently. For the special case of the problem where no color has an absolute majority in any cluster, we obtain a simpler combinatorial algorithm also with provable guarantees. Experiments on real-world data shows that our algorithms are effective in finding good clustering without over-representation.
Code (0)
등록된 구현이 없습니다.
Tasks
ArticlesClusteringSimilar Papers 제목 키워드 기반
An Introductory Survey to Autoencoder-based Deep Clustering -- Sandboxes for Combining Clustering with Deep Learning
Autoencoders offer a general way of learning low-dimensional, non-linear representations from data without labels. This is achieved without making any particular assumptions about the data type or other domain knowledge.…
ClusteringDeep ClusteringAttributed Graph Clustering via Generalized Quaternion Representation Learning
Clustering complex data in the form of attributed graphs has attracted increasing attention, where appropriate graph representation is a critical prerequisite for accurate cluster analysis. However, the Graph Convolution…
AttributeClusteringGraph ClusteringRepresentation LearningDiEC: Diffusion Embedded Clustering
Deep clustering methods typically rely on a single, well-defined representation for clustering. In contrast, pretrained diffusion models provide abundant and diverse multi-scale representations across network layers and …
Contrastive LearningDeep ClusteringHow to Achieve the Intended Aim of Deep Clustering Now, without Deep Learning
Deep clustering (DC) is often quoted to have a key advantage over $k$-means clustering. Yet, this advantage is often demonstrated using image datasets only, and it is unclear whether it addresses the fundamental limitati…
Deep ClusteringCEIL: A General Classification-Enhanced Iterative Learning Framework for Text Clustering
Text clustering, as one of the most fundamental challenges in unsupervised learning, aims at grouping semantically similar text segments without relying on human annotations. With the rapid development of deep learning, …
ClusteringDeep ClusteringGeneral ClassificationLanguage Modeling+4