Vi studerar frågan om rättvis klusterbildning under den olikartade effektdoktrinen, där varje skyddad klass måste ha ungefär lika representation i varje kluster. Vi formulerar det rättvisa kluster problemet under både k-center och k-median mål, och visar att även med två skyddade klasser problemet är utmanande, eftersom den optimala lösningen kan bryta mot gemensamma konventioner-till exempel en punkt får inte längre tilldelas sin närmaste kluster center! På vägen introducerar vi begreppet fairlets, som är minimala uppsättningar som tillfredsställer rättvis representation samtidigt som man ungefär bevarar klustermålet. Vi visar att alla rättvisa klusterproblem kan brytas ner till att först hitta bra fairlets, och sedan använda befintliga maskiner för traditionella kluster algoritmer. Samtidigt hitta bra fairlets kan vara NP-hård, vi fortsätter att få effektiva approximationsalgoritmer baserade på minsta kostnadsflöde. Vi kvantifierar empiriskt värdet av fair clustring på verkliga datauppsättningar med känsliga attribut.
Chierichetti m.fl. REF införde problemet med rättvis klusterbildning för en binär typ och erhållna approximationsalgoritmer för rättvis k-median/center.
Fair Clustering Through Fairlets
{'venue': 'NIPS 2017: 5036-5044', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}