A Computational Approach to Improving Fairness in K-means Clustering

ملخص تقني: نهج حوسبي لتحسين العدالة في تجميع الوسائط (K-means Clustering)

1. بيان المشكلة

تهدف خوارزميات التجميع القياسية، وأبرزها K-means، إلى تقليل التباين داخل العنقود (مجموع مربعات المسافات داخل العنقود الواحد). ومع ذلك، فإن هذه الخواروات "عمياء عن العدالة"؛ حيث إن عدم مراعاة السمات الحساسة (مثل العرق أو الجنس) يمكن أن يؤدي إلى عناقيد تمثل فئات معينة بشكل مفرط أو تستبعد فئات أخرى. ويمكن أن تؤدي هذه التحيزات إلى تحليل لاحق غير عادل أو عواقب اجتماعية ضارة.

وعلى الرغم من إمكانية صياغة التجميع العادل كـ مسألة تحسين مقيدة، إلا أن حلها مباشرة أمر مكلف حوسبياً لأنها مسألة برمجة صحيحة مختلطة (Mixed-Integer Programming) وتندرج ضمن المسائل الصعبة (NP-hard). كما أن طرق التجميع العادل الموجودة غالباً ما تكون معقدة رياضياً، أو مكلفة حوسبياً، أو مرتبطة ارتباطاً وثيقاً بخوارزميات محددة.

2. المنهجية

يقترح المؤلفون نهج تحسين ثنائي المراحل يعامل العدالة كتعديل مرحلي (Post-processing) بدلاً من كونها قيداً أساسياً خلال مرحلة التجميع الأولية.

• المرحلة الأولى: التجميع القياسي: إجراء عملية تجميع K-means التقليدية للحصول على تقسيم أولي للبيانات يعظم جودة العنقود.
• المرحلة الثانية: تعديل العضوية: تحديد مجموعة فرعية صغيرة من "النقاط الواعدة" الواقعة بالقرب من حدود العناقيد، ونقل انتماءاتها إلى عناقيد أخرى لموازنة نسب الفئات السكانية. ومن خلال التركيز فقط على النقاط الحدودية، تقلل الخوارزمية من التأثير على جودة التجميع الإجمالية (دالة الهدف).

ولتحديد هذه النقاط "الواعدة"، قدمت الورقة البحثية استدلالين (Heuristics) متميزين:

1. استدلال القرب من الغريب (fcNearForeign):

   • المنطق: يستهدف النقاط البعيدة عن مركز عنقودها الخاص، ولكنها تعد من بين أقرب الجيران لمركز عنقود مختلف.
   • الآلية: يحدد "النقاط الغريبة" لعنقود مستهدف. ومن غير المرجح أن يؤدي إعادة تعيين هذه النقاط إلى تدهور جودة العنقود بشكل كبير لأنها تعتبر بالفعل طرفية جغرافياً بالنسبة لمجموعتها الحالية.

2. استدلال مؤشر جيني (fcGini):

   • المنطق: يستخدم مؤشر جيني (المستخدم تقليدياً في أشجار القرار لقياس عدم النقاء في العقد) للكشف عن نقاط البيانات "المختلطة".
   • الآلية: لكل نقطة، تحسب الخوارزمية مؤشر جيني لـ $k$ من أقرب جيرانها. يشير مؤشر جيني المرتفع إلى أن النقطة تقع في بيئة "مختلطة" للغاية (حدود العنقود)، بينما يشير المؤشر المنخفض إلى نقطة "داخلية". وتمنح الخوارزمية الأولوية لتبديل النقاط ذات مؤشرات جيني الأعلى لتحسين العدالة.

3. المساهمات الرئيسية

• إطار عمل ثنائي المراحل: بديل فعال حوسبياً لحل مسائل التحسين المقيدة المعقدة.
• استدلالات مزدوجة: تقديم كل من طريقة تعتمد على المسافة (Near-Foreign) وطريقة تعتمد على عدم النقاء (Gini) لتحديد النقاط الحدودية.
• تعدد الاستخدامات الخوارزمي: النهج "مستقل عن الخوارزمية"، مما يعني إمكانية تطبيقه على أي طريقة تجميع (مثل التجميع الطيفي - Spectral Clustering) أو أي تعريف للعدالة.
• الكفاءة: تحافظ كلتا الخوارزميتين المقترحتين على تعقيد حوسبي خطي بالنسبة لعدد نقاط البيانات وعدد عمليات التبادل الضرورية.

4. النتائج التجريبية

اختبر المؤلفون خوارزمياتهم على سبع مجموعات بيانات مرجعية من مستودع UCI لتعلم الآلة (مثل: Heart, StudentPerf, CMC). وقاموا بتقييم الأداء باستخدام مقياسين:

1. مؤشر العدالة ($F$): مقياس للتفاوت بين نسب الفئات السكانية في العناقيد مقابل النسب في المجتمع العام (الأقل هو الأفضل).
2. جودة العنقود ($\kappa$): نسبة مجموع مربعات المسافات بين العناقيد إلى مجموع مربعات المسافات الكلي (الأعلى هو الأفضل).

النتائج:

• تحسن ملحوظ في العدالة: حققت كل من fcNearForeign و fcGini انخفاضاً كبيراً في مؤشر العدالة مقارنة بـ K-means القياسية عبر جميع مجموعات البيانات.
• فقدان ضئيل في الجودة: كان التأثير على جودة العنقود ($\kappa$) ضئيلاً جداً، مما يثبت أن استراتيجية "تبديل الحدود" تحافظ بفعالية على السلامة الهيكلية للعناقيد.
• المتانة: أثبت نهج مؤشر جيني عدم حساسيته لاختيار حجم الجوار ($k$).

5. الأهمية

يقدم هذا العمل حلاً عملياً وقابلاً للتوسع للممارسين الذين يحتاجون إلى ضمان العدالة في عمليات تجميع البيانات المؤتمتة. ومن خلال فصل تعديل العدالة عن عملية التجميع الأولية، يقدم المؤلفون طريقة سهسة التنفيذ ويمكن دمجها في مسارات تعلم الآلة الحالية دون الحاجة إلى إعادة صياغة رياضية ثقيلة. وهذا أمر مهم بشكل خاص في التطبيقات الحساسة في العلوم الاجتماعية، والرعاية الصحية، وتقسيم السوق حيث يمكن أن يؤدي التجميع المتحيز إلى عدم مساواة منهجية.