Aktuelle Themen der Theoretischen Informatik:
Faires Clustering
Prof. (apl) Dr. Beate Bollig
Wintersemester 2021/22
Hinweis
Für die Teilnahme an dem Seminar ist eine Anmeldung bis zum 04.10.21 per e-mail an die Veranstalterin
notwendig.
Neu:
Das Seminar wird auf ein kommendes Semester verschoben.
Termine
Mo 10-12 Uhr (geplant)
Inhalt
Unter Clustering versteht man die Partitionierung einer Menge von Objekten in Teilmengen
einander ähnlicher Objekte. Anwendungen von Clustering-Algorithmen findet man
z.B. in der Datenkompression, der Mustererkennung, der Analyse von Netzwerken und dem Maschinellen
Lernen. Die Ähnlichkeit von Objekten wird dabei von der jeweiligen Anwendung bestimmt.
Beim Fair Clustering gibt es unterschiedliche Typen von Objekten und das Ziel besteht darin, die
Objekte so in Teilmengen ähnlicher Objekte zu partitionieren, dass bestimmte Fairnessbedingungen eingehalten werden.
So kann z.B. gefordert werden, dass die Proportionierung der verschiedenen Typen
in den Partitionsmengen ungefähr ihrer Proportionierung in der Gesamtmenge entspricht.
Literatur
Die folgenden Originalarbeiten sind eine Auswahl wissenschaftlicher Arbeiten,
die im Seminar besprochen werden sollen.
Die Arbeiten sind aus dem Hochschulnetz der TU Dortmund zugreifbar.
-
Backurs, A., Indyk, P., Onak, K., Schieber, B., Vakilian, A., Wagner, T. (2019)
Scalable Fair Clustering
Proc. of ICML, 405-413
-
Bajpai, T., Chakrabarty, D., Chekuri, C., Negahbani, M. (2021)
Revisiting priority k-center: fairness and outliers
Proc. of ICALP, 21:1-21:20
-
Bera, S.K., Chakrabarty, D., Flores, N.J., Negahbani, M. (2019)
Fair algorithms for clustering
Proc. of NIPS, 4955-4966
-
Bercea, I.O., Groß, M., Khuller, S., Kumar, A., Rösner, C., Schmidt, D.R., Schmidt, M. (2019)
On the cost of essentially fair clustering
Proc. of APPROX/RANDOM, 18:1-18:22
-
Böhm, M., Fazzone, A., Leonardi, St.,
Schwiegelshohn, C. (2020)
Fair clustering with multiple colors
CoRR, abs/2002.07892
-
Chakrabarty, D., Negahbani, M. (2021)
Better algorithms for individually fair k-clustering
CoRR, abs/2106.03337
-
Chakrabarty, D., Negahbani, M. (2021)
Robust k-center with two types of radii.
Proc. of IPCO, 268-282
-
Chen, X., Fain, B., Lyu, B., Munagala, K. (2019)
Proportionally fair clustering
Proc. of ICML, 1032-1041
-
Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S. (2017)
Fair clustering through fairlets
Proc. of NIPS, 5036-5044
-
Jones, M., Nguyen, H., Nguyen, T. (2020)
Fair k-centers via maximum matching
Proc. of ICML, 4940-4949
-
Kleindessner, M., Awasthi, P., Morgenstern, J. (2020)
A notion of individual fairness for clustering
CoRR, abs/2006.04960
-
Kleindessner, M., Awasthi, P., Morgenstern, J. (2019)
Fair k-center clustering for data summarization
Proc. of ICML, 3448-3457
-
Micha, E., Shah, N. (2020)
Proportionally fair clustering revisted
Proc. of ICALP, 85:1-85:16
-
Mahabadi, S., Vakilian, A. (2020)
Individual fairness for k-clustering
Proc. of ICML, 6586-6596
-
Rösner, C., Schmidt, M. (2018)
Privacy preserving clustering with constraints
Proc. of ICALP, 96:1-96:14
-
Schmidt, M., Schwiegelhohn, C., Sohler, C. (2019)
Fair coresets and streaming algorithms for fair k-means
Proc. of WAOA, 232-251
Organisation
- Voraussetzung für die Teilnahme an dem Seminar
ist die Bereitschaft, sich selbstständig mit dem Themenschwerpunkt auseinanderzusetzen
und sich aktiv an den wissenschaftlichen Diskussionen zu beteiligen.
-
Neben der mündlichen Präsentation einer wissenschaftlichen Originalarbeit, moderieren die Teilnehmer und Teilnehmerinnen
die anschließende wissenschaftliche Diskussion und
verfassen jeweils eine schriftliche Ausarbeitung zu ihrem Thema im Umfang von ca 15 DIN A4 Seiten.
- Die Abgabe der Ausarbeitung ist als pdf-Dokument bis spätestens drei Wochen nach dem Vortrag im Seminar erforderlich.
- Der Ausarbeitung ist eine unterschriebene Erklärung mit folgendem Wortlaut beizufügen:
Hiermit erkläre ich, dass ich meine Seminarausarbeitung eigenständig und nur mit den angegebenen Hilfsmitteln
und der angegebenen Literatur verfasst habe.
- Darüberhinaus liest jeder Teilnehmer und jede Teilnehmerin
eine Ausarbeitung eines anderen Teilnehmers oder einer anderen
Teilnehmerin und gibt zeitnah eine konstruktive Rückmeldung.
Seitenanfang
Letzte Änderung: 02.09.2021 von B. Bollig