Clustering är ett grundläggande verktyg inom datautvinning. Den delar upp poäng i grupper (kluster) och kan användas för att fatta beslut för varje punkt baserat på sin grupp. Denna process kan dock skada skyddade (minoritets)klasser om klusteralgoritmen inte på ett tillfredsställande sätt representerar dem i önskvärda kluster – särskilt om uppgifterna redan är partiska. På NIPS 2017, Chierichetti et al. [14] föreslog en modell för rättvis klusterbildning som kräver representation i varje kluster för att (ungefär) bevara den globala fraktionen av varje skyddad klass. De begränsade sig till två skyddade klasser och utvecklade både en 4- approximation för problemet med fair k-center och en O(t)- approximation för problemet med fair k-median, där t är en parameter för rättvisemodellen. För flera skyddade klasser är det mest kända resultatet en 14- approximation för fair k-center [34]. Vi utökar och förbättrar de kända resultaten. För det första ger vi en 5- approximation för fair k-center problem med flera skyddade klasser. För det andra föreslår vi ett avslappnat rättvisebegrepp enligt vilket vi kan ge approximationer med konstanta faktorer för alla klassiska klustermål kcenter, k-leverantör, k-median, k-medel och anläggningsplats. De senare approximationer uppnås genom en ram som tar en godtycklig befintlig orättvis (integrerad) lösning och en rättvis (fraktionell) LP-lösning och kombinerar dem till en i huvudsak rättvis klusterbildning med ett svagt övervakat avrundningssystem. På så sätt kan en rättvis klusterbildning etableras sent, i en situation där centrumen redan är fasta.
Mer allmänt, Bercea et al. I REF föreslogs en approximation på bikriterier för rättvisa k-median/medel/center/leverantör/facilitet.
On the cost of essentially fair clusterings
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}