Fair Algorithms for Hierarchical Agglomerative Clustering
Preprint
Abstract
Hierarchical Agglomerative Clustering (HAC) algorithms are extensively utilized in modern data science, and seek to partition the dataset into clusters while generating a hierarchical relationship between the data samples. HAC algorithms are employed in many applications, such as biology, natural language processing, and recommender systems. Thus, it is imperative to ensure that these algorithms are fair -- even if the dataset contains biases against certain protected groups, the cluster outputs generated should not discriminate against samples from any of these groups. However, recent work in clustering fairness has mostly focused on center-based clustering algorithms, such as k-median and k-means clustering. In this paper, we propose fair algorithms for performing HAC that enforce fairness constraints 1) irrespective of the distance linkage criteria used, 2) generalize to any natural measures of clustering fairness for HAC, 3) work for multiple protected groups, and 4) have competitive running times to vanilla HAC. Through extensive experiments on multiple real-world UCI datasets, we show that our proposed algorithm finds fairer clusterings compared to vanilla HAC as well as other state-of-the-art fair clustering approaches.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- An Overview of Fairness in ClusteringIEEE Access, 2021
- A study on predicting loan default based on the random forest algorithmProcedia Computer Science, 2019
- Hierarchical Clustering: Objective Functions and Algorithms2018
- Analysis of genetic association using hierarchical clustering and cluster validation indicesGenomics, 2017
- Out With the Old and in With the New? An Empirical Comparison of Supervised Learning Algorithms to Predict RecidivismCriminal Justice Policy Review, 2015
- A data-driven approach to predict the success of bank telemarketingDecision Support Systems, 2014
- The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clientsExpert Systems with Applications, 2009
- Silhouettes: A graphical aid to the interpretation and validation of cluster analysisJournal of Computational and Applied Mathematics, 1987