A novel initialisation based on hospital-resident assignment for the k-modes algorithm
This paper presents a new way of selecting an initial solution for the k-modes algorithm that allows for a notion of mathematical fairness and a leverage of the data that the common initialisations from literature do not. The method, which utilises the Hospital-Resident Assignment Problem to find the set of initial cluster centroids, is compared with the current initialisations on both benchmark datasets and a body of newly generated artificial datasets. Based on this analysis, the proposed method is shown to outperform the other initialisations in the majority of cases, especially when the number of clusters is optimised. In addition, we find that our method outperforms the leading established method specifically for low-density data.
Code (0)
등록된 구현이 없습니다.
Tasks
FairnessSimilar Papers 제목 키워드 기반
Boltzmann Exploration Expectation-Maximisation
We present a general method for fitting finite mixture models (FMM). Learning in a mixture model consists of finding the most likely cluster assignment for each data-point, as well as finding the parameters of the cluste…
Boltzmann Exploration Expectation–Maximisation
We present a general method for fitting finite mixture models (FMM). Learning in a mixture model consists of finding the most likely cluster assignment for each data-point, as well as finding the parameters of the clus…
Iris SegmentationThe Price of Quota-based Diversity in Assignment Problems
We introduce and analyze an extension to the matching problem on a weighted bipartite graph: Assignment with Type Constraints. The two parts of the graph are partitioned into subsets called types and blocks; we seek a ma…
DiversityAnytime Capacity Expansion in Medical Residency Match by Monte Carlo Tree Search
This paper considers the capacity expansion problem in two-sided matchings, where the policymaker is allowed to allocate some extra seats as well as the standard seats. In medical residency match, each hospital accepts a…
Stability in Repeated Matching Markets
This paper develops a framework for repeated matching markets. The model departs from the Gale-Shapley matching model by having a fixed set of long-lived hospitals match with a new generation of short-lived residents in …