Minimum Average Cost Clustering
A number of objective functions in clustering problems can be described with submodular functions. In this paper, we introduce the minimum average cost criterion, and show that the theory of intersecting submodular functions can be used for clustering with submodular objective functions. The proposed algorithm does not require the number of clusters in advance, and it will be determined by the property of a given set of data points. The minimum average cost clustering problem is parameterized with a real variable, and surprisingly, we show that all information about optimal clusterings for all parameters can be computed in polynomial time in total. Additionally, we evaluate the performance of the proposed algorithm through computational experiments.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Reactive Global Minimum Variance Portfolios with $k-$BAHC covariance cleaning
We introduce a $k$-fold boosted version of our Boostrapped Average Hierarchical Clustering cleaning procedure for correlation and covariance matrices. We then apply this method to global minimum variance portfolios for v…
ClusteringMotion Trajectory Segmentation via Minimum Cost Multicuts
For the segmentation of moving objects in videos, the analysis of long-term point trajectories has been very popular recently. In this paper, we formulate the segmentation of a video sequence based on point trajectories …
ClusteringSegmentationUnsupervised Video Object SegmentationConstant Approximation for Individual Preference Stable Clustering
Individual preference (IP) stability, introduced by Ahmadi et al. (ICML 2022), is a natural clustering objective inspired by stability and fairness constraints. A clustering is $\alpha$-IP stable if the average distance …
ClusteringFairnessNear-Optimal Explainable $k$-Means for All Dimensions
Many clustering algorithms are guided by certain cost functions such as the widely-used $k$-means cost. These algorithms divide data points into clusters with often complicated boundaries, creating difficulties in explai…
AllClusteringApproximation Algorithms for Fair Range Clustering
This paper studies the fair range clustering problem in which the data points are from different demographic groups and the goal is to pick $k$ centers with the minimum clustering cost such that each group is at least mi…
Clustering