Fairlet Decomposition#

Note

Learning tasks: Clustering.

Introduction#

The preprocessing (r, b)-fairlet decomposition method is designed to partition a set of points into smaller, balanced subsets called fairlets. This method is particularly useful in fair clustering, where the goal is to ensure that each cluster has a balanced representation of different groups (e.g., red and blue points). The method leverages a hierarchical structure to efficiently compute these fairlets, ensuring that the resulting clusters are balanced according to specified parameters.

Description#

  • Problem definition

    The problem addressed by the (r, b)-fairlet decomposition method is to partition a set of points into smaller subsets (fairlets) such that each subset is balanced according to the given parameters \(r\) and \(b\). Specifically, a subset is considered (r, b)-balanced if the ratio of the number of red points to blue points in each subset is at least \(\frac{b}{r}\). The goal is to minimize the total number of points that need to be removed to achieve this balance.

  • Main features

    The main features of the (r, b)-fairlet decomposition method include:

    • Efficiently partitioning points into balanced fairlets.

    • Minimizing the number of points removed to achieve balance.

    • Utilizing a hierarchical structure (HST) to facilitate the decomposition process.

    • Ensuring that the resulting fairlets are balanced according to the specified parameters.

  • Step-by-step description of the approach

    Given a node \(v\) which is a leaf node of the tree \(T\), an arbitrary (r, b)-fairlet decomposition of the points in \(T(v)\) is returned.

    1. Minimize Heavy Points:

      • For each non-empty child \(i\) of \(v\), compute the number of red and blue points \(\{N_i^r, N_i^b\}\).

      • Use a function to approximately minimize the total number of heavy points with respect to \(v\).

    2. Decompose Heavy Points:

      • Initialize an empty set \(P_v\).

      • For each non-empty child \(i\) of \(v\), remove an arbitrary set of \(x_i^r\) red and \(x_i^b\) blue points from \(T(v_i)\) and add them to \(P_v\).

      • Output an arbitrary (r, b)-fairlet decomposition of points in \(P_v\).

Basic Usage#

You can find an example of using the Fairlet Decomposition method in the following demo.

Read more about the class attributes and methods in the API reference: FairletClusteringPreprocessing.

References#

  1. Backurs, Arturs, et al. “Scalable fair clustering.” International Conference on Machine Learning. PMLR, 2019.