Open Access

Harish Sharma

• Clustering algorithms partition unlabelled data into groups based on similarity, yet standard methods provide no guarantee that different demographic subpopulations are treated equitably across those groups. A second, often overlooked gap is interpretability: the partition produced by an algorithm such as k-means gives no human-readable account of why a data point was assigned to its cluster. This thesis addresses both gaps jointly by building a unified evaluation framework in which fairness and explainability are assessed alongside conventional clustering quality. The framework implements and compares four clustering methods k-means, k-medians, a fairlet-based fair k-medians method derived from quadtree decomposition, and a bounded-representation method across four real-world datasets: Bank Marketing, Adult Census Income, COMPASClustering algorithms partition unlabelled data into groups based on similarity, yet standard methods provide no guarantee that different demographic subpopulations are treated equitably across those groups. A second, often overlooked gap is interpretability: the partition produced by an algorithm such as k-means gives no human-readable account of why a data point was assigned to its cluster. This thesis addresses both gaps jointly by building a unified evaluation framework in which fairness and explainability are assessed alongside conventional clustering quality. The framework implements and compares four clustering methods k-means, k-medians, a fairlet-based fair k-medians method derived from quadtree decomposition, and a bounded-representation method across four real-world datasets: Bank Marketing, Adult Census Income, COMPAS Recidivism, and German Credit. Each configuration is evaluated on three axes: clustering quality (silhouette score, sum of squared errors, PAM cost), group fairness (Balance, violation rate, and cost of fairness), and explainability (surrogate decision-tree fidelity and complexity). Protected attributes reflect established fairness benchmarks: marital status for Bank Marketing, gender for Adult, race for COMPAS, and gender for German Credit. The results show that enforcing fairness does not uniformly degrade clustering quality. The bounded-representation method achieves a cost-of-fairness ratio close to 1.0 across all four datasets, meaning the quality penalty for a formal fairness guarantee is small in practice. Surrogate decision trees maintain high fidelity on both constrained and unconstrained clusterings, showing that post-hoc explainability is compatible with fairness-aware assignment. A recurring finding is that k-medians produces more balanced clusters than k-means without any explicit fairness constraint — a structural effect of the L1 objective yet it offers no provable guarantee. This contrast illustrates why formal methods such as bounded representation remain necessary. Together, the results provide an empirical basis for choosing clustering methods when both accountability and interpretability are required.…
• Clustering-Algorithmen partitionieren unbeschriftete Daten anhand von Ähnlichkeit in Gruppen, bieten jedoch keine Garantie dafür, dass verschiedene demographische Teilgruppen über diese Gruppen hinweg fair behandelt werden. Eine zweite, häufig vernachlässigte Lücke betrifft die Interpretierbarkeit: Die von einem Algorithmus wie k-Means erzeugte Partition liefert keine für Menschen lesbare Begründung dafür, warum ein Datenpunkt seinem Cluster zugewiesen wurde. Diese Arbeit adressiert beide Lücken gemeinsam, indem ein einheitlicher Evaluierungsrahmen entwickelt wird, in dem Fairness und Erklärbarkeit gemeinsam mit herkömmlicher Clustering-Qualität bewertet werden. Der Rahmen implementiert und vergleicht vier Clustering-Methoden — k-Means, k-Medians, eine Fairlet-basierte faire k-Medians-Methode, die aus einer Quadtree-Zerlegung abgeleitetClustering-Algorithmen partitionieren unbeschriftete Daten anhand von Ähnlichkeit in Gruppen, bieten jedoch keine Garantie dafür, dass verschiedene demographische Teilgruppen über diese Gruppen hinweg fair behandelt werden. Eine zweite, häufig vernachlässigte Lücke betrifft die Interpretierbarkeit: Die von einem Algorithmus wie k-Means erzeugte Partition liefert keine für Menschen lesbare Begründung dafür, warum ein Datenpunkt seinem Cluster zugewiesen wurde. Diese Arbeit adressiert beide Lücken gemeinsam, indem ein einheitlicher Evaluierungsrahmen entwickelt wird, in dem Fairness und Erklärbarkeit gemeinsam mit herkömmlicher Clustering-Qualität bewertet werden. Der Rahmen implementiert und vergleicht vier Clustering-Methoden — k-Means, k-Medians, eine Fairlet-basierte faire k-Medians-Methode, die aus einer Quadtree-Zerlegung abgeleitet wird, sowie eine Bounded-Representation-Methode — auf vier realen Datensätzen: Bank Marketing, Adult Census Income, COMPAS Recidivism und German Credit. Jede Konfiguration wird anhand von drei Achsen bewertet: Clustering-Qualität (Silhouette-Score, Summe der quadratischen Fehler, PAM-Kosten), Gruppenfairness (Balance, Verletzungsrate und Fairness-Kosten) sowie Erklärbarkeit (Fidelität und Komplexität von Surrogatentscheidungsbäumen). Die geschützte Attribute orientieren sich an etablierten Fairness-Benchmarks: Familienstand für Bank Marketing, Geschlecht für Adult, Rasse für COMPAS und Geschlecht für German Credit. Die Ergebnisse zeigen, dass die Durchsetzung von Fairness die Clustering-Qualität nicht einheitlich verschlechtert. Die Bounded-Representation-Methode erreicht auf allen vier Datensätzen ein Cost-of-Fairness-Verhältnis nahe 1,0, was bedeutet, dass der Qualitätsverlust durch eine formale Fairness-Garantie in der Praxis gering ist. Surrogat-Entscheidungsbäume behalten eine hohe Fidelität sowohl bei eingeschränkten als auch bei uneingeschränkten Clusterings bei und zeigen, dass nachträgliche Erklärbarkeit mit fairer Zuweisung vereinbar ist. Ein wiederkehrendes Ergebnis ist, dass k-Medians ohne explizite Fairness-Einschränkung ausgewogenere Cluster als k-Means erzeugt — ein struktureller Effekt des L1-Zielfunktionals — jedoch keine beweisbare Garantie bietet. Dieser Kontrast verdeutlicht, warum formale Methoden wie Bounded-Representation weiterhin notwendig sind. Zusammen liefern die Ergebnisse eine empirische Grundlage für die Auswahl von Clustering-Methoden, wenn sowohl Rechenschaftspflicht als auch Interpretierbarkeit erforderlich sind.…