Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

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