نحوه تعیین خودکار تعداد خوشه ها توسط قانون آرنج

تعیین تعداد خوشه‌ها هنگام انجام خوشه‌بندی بدون نظارت یک مشکل پیچیده است. بسیاری از مجموعه‌های داده، خوشه‌های جدا از هم را نشان نمی‌دهند. وقتی از دو فرد خواسته می‌شود که تعداد خوشه‌ها را با نگاه کردن به نمودار بگویند، احتمالاً دو پاسخ متفاوت را دریافت خواهید کرد. گاهی اوقات خوشه ها با یکدیگر همپوشانی دارند و خوشه های بزرگ شامل خوشه های فرعی هستند که تصمیم گیری در مورد آنها چندان آسان نیست.

به عنوان مثال، چند خوشه در تصویر زیر می بینید؟ تعداد بهینه خوشه ها چقدر است؟ نه هوش مصنوعی، نه یک انسان، نه یک الگوریتم نمی تواند با اطمینان جواب این سوال را بدهد.

 

شکل 1: چند خوشه اینجا است؟!

 

در تصویر بالا، داده های اساسی (underlying data) نشان می دهد که سه خوشه اصلی وجود دارد. اما پاسخی مانند 6 یا 7 به همان اندازه میتواند معتبر به نظر بیاید.

تعدادی از رویکردهای تجربی برای تعیین تعداد خوشه ها در یک مجموعه داده استفاده شده است. آنها معمولاً به دو دسته تقسیم می شوند:

(1) تکنیک های برازش و یا تناسب مدل (Model fitting techniques): گاهی اوقات، تناسب با مدلی مقایسه می‌شود که مشاهدات به طور یکنواخت در کل حوزه پشتیبانی توزیع می‌شوند، بنابراین بدون خوشه است. ممکن است مجبور شوید دامنه پشتیبانی (support domain) مورد نظر را تخمین بزنید و فرض کنید که از زیر دامنه‌های مجزا ساخته نشده است. در بسیاری از موارد، بدنه محدب مجموعه داده شما، به عنوان تخمینی از دامنه پشتیبانی، به اندازه کافی خوب است.

(2) تکنیک های بصری (Visual techniques): به عنوان مثال، قانون سیلوئت (silhouette) یا قانون آرنج (elbow)

 

شکل 2: قانون آرنج

 

در هر دو مورد، برای تعیین تعداد بهینه خوشه ها به یک معیار نیاز دارید. در مورد قانون آرنج، معمولاً از درصد واریانس غیرقابل توضیح استفاده می شود. این عدد با خوشه صفر 100% است و با افزایش تعداد خوشه‌ها در مدل خود، کاهش می‌یابد (در ابتدا به شدت و سپس به میزان متوسطی). وقتی هر نقطه یک خوشه را تشکیل می‌دهد، این عدد به 0 می‌رسد. جایی در این بین، منحنی که معیار شما را نشان می‌دهد، یک آرنج را نشان می‌دهد (تصویر زیر را ببینید)، و آن آرنج تعداد خوشه‌ها را تعیین می‌کند. به عنوان مثال، در نمودار زیر، تعداد بهینه خوشه ها 4 است.

 

شکل 2: قانون آرنج به شما می گوید که در اینجا، مجموعه داده های شما دارای 4 خوشه است (قدرت آرنج به رنگ قرمز نشان داده شده است). منحنی با سرعت بسیار بیشتری نزول یافته است.

 

من نتونستم مقاله ای پیدا کنم که نقطه آرنج را به صراحت محاسبه کند. بیشتر مقالات میگویند این نقاط عمدتاً با بررسی چشمی انتخاب می شود. در بخش بعدی این مشکل را حل می کنیم.

1- خودکار کردن قانون آرنج

این مثال دیگری است که نشان می دهد چگونه علم داده می تواند برخی از وظایف انجام شده توسط آماردانان را در زمینه تجزیه و تحلیل داده های اکتشافی خودکار کند. راه حل در واقع بسیار ساده است و برای بسیاری از مشکلات که حتی به خوشه بندی مربوط نمی شوند، اعمال می شود که در بخش بعدی به آنها خواهیم پرداخت. همچنین، به استفاده از درصد واریانس تشریح نشده (unexplained variance) (محور Y) برای رسم منحنی آرنج محدود نمی شود، بلکه معیارهای دیگری مانند آنتروپی یا خطای ناشی از تناسب مدل نیز به همان اندازه خوب کار می کنند. در واقع، راه حل ارائه شده در اینجا برای ادغام در سیستم های تصمیم گیری جعبه سیاه طراحی شده است. تنها شرط این است که منحنی آرنج باید مثبت (بالاتر از محور X) و در حال کاهش باشد.

2- قدرت آرنج 

فرمول محاسبه قدرت آرنج (مفهوم اصلی در این مقاله) با استفاده از جدول زیر (مرتبط با شکل 2) نشان داده شده است.

 

 

ستون (دلتا 1) در جدول نشان دهنده تفاوت بین خوشه های k و k + 1 است که بر اساس معیار متریک (criterion metric) اندازه گیری می شود (ستون دوم). قدرت (راست ترین ستون) در خط k(که k تعداد خوشه ها است) به عنوان تفاوت بین دلتا 2 و دلتا 1 در خط k +1 محاسبه می شود. فقط در صورت مثبت بودن نشان داده می شود.

 

3- تعداد خوشه ها

تعداد بهینه خوشه ها مقدار k است که قدرت را به حداکثر می رساند. همینه 😊 !

قدرت نشان می دهد که برای یک k خاص، آیا یک آرنج پتانسیل در سطح k وجود دارد و سیگنال آرنج در آن سطح چقدر قوی است. گاهی اوقات قوی ترین سیگنال اولین سیگنال نیست، اگرچه معمولاً در بسیاری از موارد چنین است. در زیر مثالی وجود دارد که در آن چنین نیست.

 

شکل 3: منحنی با سرعت بسیار کمتری نزول یافته است

تصویر بالا وضعیتی را نشان می دهد که در آن داده ها می توانند 2 یا 3 خوشه داشته باشند. با این حال، بر اساس ارتفاع میله های قرمز، فرض 3 خوشه (به جای 2) بسیار قابل قبول تر است.

4- تست کردن

سه نوع تست برای ارزیابی این روش وجود دارد:

(1) تست با منحنی های آرنج مختلف: ما منحنی هایی با آرنج های متعدد یا بدون آرنجی ایجاد کردیم تا نتایج حاصل از روش را بررسی کنیم. اگر شکل منحنی آرنج مانند 1/k باشد، دو خوشه شناسایی می شود. اگر منحنی با سرعت بسیار کمتری نزول یابد، برای ایجاد نوارهای قرمز بسیار صاف است و هیچ آرنجی تشخیص داده نمی شود.

(2) تست بر روی داده های واقعی: تفسیر این تست ها می تواند دشوارتر باشد، زیرا در بسیاری از موارد، هیچ کس نمی تواند تعداد خوشه ها را تشخیص دهد، مگر اینکه خوشه ها به خوبی از هم جدا شده باشند، یا از قبل شناخته شده باشند.

(3) تست با داده های شبیه سازی شده: تولید داده ها با تعداد مشخصی از خوشه ها آسان است. سپس می توان از معیاری مانند درصد واریانس تشریح نشده استفاده کرد و به منحنی آرنج نگاه کرد تا بررسی کرد که چه زمانی تعداد خوشه ها را به درستی پیش بینی می کند. در زیر نمونه ای از خوشه های شبیه سازی شده آورده شده است.

 

شکل 4: ساختار خوشه ای شبیه سازی شده برای آزمایش قانون آرنج

 

5- قانون توقف (Stopping rule) برای الگوریتم های خوشه بندی

یک سوال دیگر این است که وقتی داده ها بیش از دو بعد دارند، این روش چگونه عمل می کند؟!. مسئله مربوط به خود منحنی آرنج نیست، بلکه در مورد معیاری است که استفاده می شود. در نهایت، هنگامی که خوشه های بزرگ در یک مجموعه داده یافت می شوند (مخصوصاً با الگوریتم های خوشه بندی سلسله مراتبی (hierarchical clustering algorithms))، بهترین روش این است که علاوه بر کل مجموعه داده، قانون آرنجی را به هر خوشه بزرگ (تقسیم خوشه بزرگ به خوشه های کوچکتر)، اعمال کنید. در عمل، هنگامی که اولین نوار قرمز را زدید (یا اگر میله قرمز دیگری درست بعد از اولین و بزرگتر از اولین وجود داشت)، می توانید از پالایش و تقسیم خوشه های خود دست بکشید: در این حالت به یک مقدار بهینه تجربی رسیده اید.

 

6- کاربردهای دیگر قانون آرنج

قانون آرنج علاوه بر تشخیص تعداد خوشه ها، کاربردهای دیگری نیز دارد. به عنوان مثال در هنگام استفاده از کتابخانه های محاسباتی با دقت بالا در Perl و Python برای محاسبه درست تعداد اعشار می توان از آن استفاده کرد. در واقع، روش آرنجی را می توان در هر الگوریتمی استفاده کرد که دارای یک قانون توقف است، که در آن معیاری که برای اندازه گیری بهبود عملکرد در هر تکرار جدید استفاده می شود، یک تابع کاهشی مثبت است. به طور خاص، می‌توان از آن برای تشخیص عمق درخت تصمیم گیری (decision tree) و یا در الگوریتم‌های عددی برای تشخیص اینکه چه زمانی سطح دقت به‌اندازه کافی خوب است، استفاده کرد.