عنوان : الگوریتم های مقیاس پذیر برای خوشهبندی عادلانه بر اساس مفهوم عدالت
استاد راهنما: دکتر حسین جوهری
استاد راهنما دوم :خانم دکتر راضیه خودسیانی
ارزیاب داخلی : دکتر مریم عبدالعلی
ارزیاب خارجی : دکتر علیرضا باقری
تاریخ: سه شنبه 19 اسفند ماه 1404 - ساعت: 14:30
چکیده:
خوشه بندی یکی از ابزارهای پرکاربرد برای حل مسائل گوناگونی همچون خلاصه سازی داده ها ، خوشه بندی مشتریان ، کشف الگوهای رفتاری کاربران ، تحلیل شبکه های اجتماعی و گروه بندی کاربران و .. است . الگوریتمهای خوشهبندی مرکزگرا به دلیل سادگی و کارایی بالا، جایگاه محوری در این حوزه دارند..
با این حال، استفاده از خوشهبندی کلاسیک ممکن است ناخواسته منجر به تبعیض علیه گروههای جمعیتی خاص (بر اساس جنسیت، نژاد، قومیت و...) شود. از سوی دیگر، افزایش نمایی حجم و ابعاد دادهها در عصر حاضر، مقیاسپذیری این الگوریتمها را به یک ویژگی اجتنابناپذیر تبدیل کرده است. در این پایاننامه، به بررسی و تحلیل الگوریتمهایی میپردازیم که هر دو چالش عدالت گروهی و مقیاسپذیری را در مسئله خوشهبندی k-مرکز هدف قرار میدهند.
در این پایان نامه ، با فرض وجود گروههای محافظتشدهای مانند جنسیت یا نژاد که به عنوان رنگ نقاط داده در نظر گرفته میشوند، سه مفهوم اصلی عدالت گروهی شامل تعادل، نمایش حداقلی و مراکز عادلانه مورد مطالعه قرار میگیرد. برای هر یک از این مفاهیم، ابتدا الگوریتمهای ترتیبی پایه مانند الگوریتم تجزیه فیرلت برای مفهوم تعادل و الگوریتم خوشهبندی اساساً عادلانه با برای نمایش حداقلی و الگوریتم خوشه بندی برای خلاصه سازی عادلانه داده ها تحلیل میشوند. سپس با توجه به محدودیت این الگوریتمها در مواجهه با دادههای حجیم، الگوریتم خوشه بندی k-مرکز عادلانه در مدل پردازش موازی در مقیاس بالا با تقریب 9 ، الگوریتم خوشه بندی k-مرکز عادلانه بر پایه مجموعه هسته در ابعاد پایین با تقریب 3و الگوریتم تقریبی مقیاس پذیر برای خوشه بندی k-مرکز عادلانه با تقریب 3 بر پایه مفهوم مراکز عادلانه معرفی می گردند.
در بخش عملی نیز الگوریتمهای بهبودیافتهای مبتنی بر کارهای اخیر وو و همکاران که در سال 2024 ارائه شدند ، پیادهسازی و بر روی هفت مجموعه داده مختلف ارزیابی میشوند. این الگوریتمها با دو راهکار کلیدی یعنی افزایش تعداد مراکز محلی و استفاده از جستجوی هندسی به جای جستجوی دودویی برای تخمین شعاع بهینه، بهبود قابل توجهی در کارایی نشان میدهند.
