الگوریتم خوشه‌بندی Lumbermark، روش‌های نام‌آشنای HDBSCAN و k-means را در ۶۱ بنچمارک شکست داد

توسعه‌دهندگان و متخصصان یادگیری ماشین هنگام انتخاب یک روش خوشه‌بندی، اغلب ناچارند میان تعیین تعداد دقیق خوشه‌ها و شناسایی مرزهای منعطف یکی را فدا کنند. الگوریتم k-means مقدار ورودی k را می‌پذیرد، اما صرفاً به سمت تشکیل گروه‌های فشرده و تقریباً کروی متمایل است. از سوی دیگر، روش HDBSCAN به‌خوبی از پس خوشه‌های مقعر و نامنظم برمی‌آید و داده‌های پرت را تشخیص می‌دهد؛ با این حال سلسله‌مراتب مبتنی بر چگالی آن هیچ تضمینی برای برآورده کردن تعداد خوشه‌های درخواستی ارائه نمی‌کند. روش پیوند تکی (Single linkage) نیز با وجود پذیرش k و مدیریت اشکال دلخواه، نقطه‌ضعفی اساسی دارد: وجود زنجیره‌ای باریک و پراکنده از نقاط می‌تواند دو گروه کاملاً مجزا را به‌اشتباه به یکدیگر متصل کند.

در همین راستا، مارک گاگولفسکی در مقاله‌ای پژوهشی، الگوریتم جدیدی به نام Lumbermark را معرفی کرده است؛ راهکاری که امکان مشخص کردن تعداد خوشه‌ها را با تکنیک برش درختِ آگاه از چگالی ترکیب می‌کند. این الگوریتم تقسیمی (Divisive)، ابتدا یک درخت پوشای کمینه بر پایه فاصله دسترسی متقابل می‌سازد، سپس رأس‌های حاشیه‌ای را از محاسبات تقسیم کنار می‌گذارد و در نهایت k - 1 برش با محدودیت اندازه ایجاد می‌کند. در ارزیابی جامع نویسنده روی ۶۱ مجموعه‌داده، قوی‌ترین پیکربندی این الگوریتم توانست روش‌های تثبیت‌شده و معتبری همچون HDBSCAN و Genie را پشت سر بگذارد.

چرا برش درخت پوشای کمینه اهمیت دارد؟

یک درخت پوشای کمینه یا MST، تمام نقاط داده را با استفاده از n - 1 یال و با کمترین وزن مجموع ممکن به هم متصل می‌سازد. در این ساختار، یال‌های درون یک خوشه معمولاً کوتاه‌تر از یال‌های میان دو خوشه مجزا هستند. اگر k - 1 یال با بیشترین طول را حذف کنیم، خوشه‌بندی حاصل دقیقاً مشابه روش پیوند تکی خواهد بود؛ به این معنی که این ساختار همچنان حساسیت منفی شدیدی به زنجیره‌های داده‌های نوفه‌ای و نقاط پراکنده خواهد داشت.

الگوریتم Lumbermark برای غلبه بر این چالش، وزن‌های ساده اقلیدسی یال‌ها را با مفهومی تحت عنوان فاصله دسترسی متقابل (Mutual-reachability distance) جایگزین می‌کند. برای دو نقطه x و y، این فاصله به‌صورت d_M(x, y) = max(d(x, y), c_M(x), c_M(y)) محاسبه می‌شود؛ جایی که c_M نشان‌دهنده فاصله نقطه تا Mامین نزدیک‌ترین همسایه آن است. از آنجا که نقاط پراکنده فاصله مرکزی بزرگ‌تری دارند، وزن یال‌های متصل به آن‌ها افزایش می‌یابد و این امر توانایی این نقاط خلوت را برای ایجاد پل اشتباه میان گروه‌های متراکم خنثی می‌کند.