خوشه‌بندی ۲-مرکز

حالت خاص مسأله‌ی خوشه‌بندی k-مرکز است که در آن k=2 است. یعنی می‌خواهیم نقاط را به دو دسته تقسیم کنیم که فاصله‌ی بین مرکز خوشه و نقاط خوشه مینیمم شود.

نتایج:

۱- اگر خوشه‌ها متقاطع باشند، نقاط درون اشتراک خوشه‌ها مهم نیستند، چون توسط دو خوشه پوشیده شده‌اند، باید حتماً به دلیل نقاط دیگر خوشه‌ها متقاطع شده باشند.

۲- همیشه یک خط وجود دارد که به خط المرکزین خوشه‌ها عمود است و آنها را از هم جدا می‌کند. این خط از نقاط تقاطع دو خوشه (در صورت وجود) عبور می‌کند. اگر خوشه‌ها مجزا باشند، خط‌های عمود و غیرعمود زیادی جداکننده هستند.

۳- نقاط مرزی خوشه‌ها ممکن است در هیچ جهتی اکسترمم (ماکسیمم/مینیمم) نقاط نباشند. این اتفاق وقتی می‌افتد که دو خوشه متقاطع باشند و مماسی که از مرکز یکی رسم می‌شود دورتر از نقطه‌ی تقاطع دو دایره محیط دایره دیگر را قطع کند. در این صورت نقاط بین محل تماس مماس بر دایره و محل تقاطع دایره‌ها در هیچ راستایی اکسترمم نقاط نیستند. در واقع هیچ کدام از نقاط بین مماس مشترک‌های داخلی نقاط اکسترمم نیستند (چون نقطه‌ای روی محیط دایره‌ی دیگر هست که اکسترمم است) اما چون طبق ۱ نقاط اشتراک مهم نیستند، فقط این قسمت باقی می‌ماند.

۴- برای حل مشکل ۳ می‌شود توری جهتی ساخت و در هر سطر/ستون/... (بستگی به تعداد بعدها دارد) اکسترمم گرفت. تنها نکته‌ای که باقی می‌ماند این است که نقاط یک دایره ممکن است نقاط دایره‌ی دیگر را حذف کنند. برای حل این مشکل می‌شود در خانه‌های توری که بیشتر از یک نقطه دارند و به عنوان اکسترمم شناخته شده‌اند، نقاط اکسترمم درون آن (پوسته محدب) را برداریم.

۵- این کار برای شکل‌های دایره‌ای (خوشه دایره‌ای) بهترین راه حل نیست، اما می‌توانیم از آن برای شکل‌های دیگر استفاده کنیم. فقط باید بتوانیم مشابه اینها را برای آن ثابت کنیم.

۶- این کار برای بیشتر از ۲ دایره ممکن نیست. چون مثلاً حالتی که سه دایره متقاطع داشته باشیم که اشتراک سه تای آنها با هم تهی باشد، نقاط وسط سه دایره (خارج از دایره ها و بین نقاط تقاطع) نقاط مهمی در شکل خوشه (شعاع خوشه) هستند، در حالی که حذف می‌شوند.

مرجع: موضوع اولی بود که قرار بود برای پروژه‌ام انتخاب کنم!