تعیین تعداد خوشه‌ها در یک مجموعه داده

تعیین تعداد خوشه در یک مجموعه داده، مقداری اغلب دارای برچسب k در الگوریتم k-means و مشکلی پرتکرار در خوشه بندی داده‌ها و مسئله ای متمایز از فرایند حل مشکل خوشه بندی است.
برای یک کلاس خاص از الگوریتم‌های خوشه بندی (به ویژه در k-medoids, k-means و (الگوریتم امید ریاضی–بیشینه کردن) پارامتری به عنوان k معمولاً وجود دارد که تعداد خوشه‌ها را تشخیص می‌دهد. الگوریتم‌های دیگری مانند DBSCAN و اپتیک الگوریتم مشخصات این پارامتر را نیاز ندارند؛ خوشه بندی سلسله مراتبی این مشکل را به صورت کلی ندارد.
انتخاب صحیح عدد k اغلب مبهم است و با تفاسیری به شکل و مقیاس توزیع نقاط در یک مجموعه داده و نیت خوشه بندی کاربر بستگی دارد. به علاوه افزایش k بدون مجازات (penalty) به کاهش میزان خطا در نتیجهٔ خوشه بندی منجر می‌شود. در شدیدترین حالت از صفر خطا اگر هر نقطه داده، خود یک خوشه در نظر گرفته شود. (به عنوان مثال زمانی که k برابر با تعداد نقاط داده‌ها باشد). به‌طور مستقیم و سپس با انتخاب بهینه از k به تعادلی بین حداکثر فشرده سازی داده‌ها با استفاده از یک خوشه و حداکثر دقت، با اختصاص هر نقطه داده به یک خوشه خواهیم رسید. اگر یک مقدار مناسب از k با استفادهاز دانش قبلی از خواص آن مجموعه داده مشخص نباشد، باید به نحوی انتخاب شود. چند دسته روش رأی این تصمیم‌گیری وجود دارد.

روش آرنج (The elbow method)

روش آرنج درصد واریانس را به عنوان تابعی از تعداد خوشه‌ها توضیح می‌دهد:
یکی باید به عنوان تعداد خوشه‌ها انتخاب شود به طوری که با اضافه کردن خوشه ای دیگر مدل‌سازی داده بهتری بدست نیاید.
دقیق تر، اگر یک ترسیم (plot) درصد واریانس را تشریح کند طوریکه مخالف تعداد خوشه‌ها باشد اولین خوشه‌ها اطلاعات زیادی (توضیح بسیاری از واریانس) را اضافه می‌کنند، اما در بعضی نقطه‌ها حاشیه سود کاهش خواهد یافت و یک زاویه در نمودار به وجود می‌آورد. تعداد خوشه‌ها در این نقطه انتخاب شده‌اند یعنی همان «معیار آرنج».
این «آرنج» نمی‌تواند همیشه به روشنی مشخص شود.
درصد از واریانس نسبت واریانس بین-گروهی به کل واریانس را توضیح داده، همچنین به عنوان یک آزمون F شناخته شده‌است. تنوع اندکی از این روش انحنای درون واریانس گروهی را ترسیم (plot) می‌کند.
این روش را می‌توان به گمانه زنی توسط Robert L. Thorndike در سال ۱۹۵۳ نسبت داد.

خوشه بندی X-means

در آمار و داده کاوی، X-means clustering نوعی از خوشه بندی k-means است که خوشه‌ها را براساس عملیات مکرر تقسیم و دسته‌بندی، و نگه داشتن بهترین نتیجه تا زمانی که معیاری مانند معیار اطلاعاتی آکائیکه (AIC) یا معیار اطلاع بیزی-شوارتز (BIC) بدست آید.

رویکرد معیارهای اطلاعاتی (Information criterion)

یکی دیگر از مجموعه روش‌ها برای تعیین تعداد خوشه‌ها، اطلاعات معیاری مانند (Akaike information criterion (AIC,  اطلاعات معیارBIC) Bayesian) یا انحراف اطلاعات معیار (DIC) — اگر ایجاد تابع برای مدل خوشه بندی ممکن باشد.
به عنوان مثال: مدل k-means مدل «تقریباً» یک Gaussian mixture model است و ساخت احتمالی برای مدل مرکب گوسی مقدور است و نتیجه نیز تعیین مقادیر معیار است.

رویکرد نظری اطلاعات (information–theoretic)

نظریه نرخ اعوجاج برای انتخاب k به نام روش «پرش» نامگذاری شده‌است که تعداد خوشه‌ها را برای دستیابی به حداکثر راندمان و همزمان به حداقل رساندن خطا توسط استانداردهای اطلاعات نظری تعیین می‌کند. استراتژی الگوریتم این است که اعوجاج منحنی تولید می‌کند برای داده‌های ورودی در حال اجرا توسط استاندارد الگوریتم خوشه بندی مانند k-means برای تمام مقادیر k بین ۱ و n و اعوجاج را (در زیر توضیح داده شده) و در نتیجه خوشه بندی مشخص می‌کند. اعوجاج منحنی معیاری منفی برای تعیین ابعاد داده‌است. روش «پرش» مقادیری را برای انتخاب درست k خروجی می‌دهد. بزرگترین پرش به عنوان بهترین انتخاب است.

روش نیمرخ (silhouette)

متوسط نیمرخ (silhouette) از اطلاعات معیار مفید دیگری برای ارزیابی طبیعی تعداد خوشه هاست. نیمرخِ (silhouette) یک نمونه داده میزان نزدیک شدن داده‌ها درون خوشه و میزان آزادی و فاصله داده‌ها از خوشه همسایه است. یعنی خوشه ای که میانگین فاصله از مرجع "datum" پایین‌ترین است. یک نیمرخ نزدیک به ۱ به معنی است که datum در خوشه ای مناسب است در حالی که یک نیمرخ نزدیک به -۱ به این معنی است که datum در خوشه اشتباه قرار گرفته‌است. تکنیک‌های بهینه‌سازی مانند الگوریتم ژنتیک در تعیین تعداد خوشه‌ها مفیدند که بزرگترین نیمرخ را بدست می‌دهند.
همچنین ممکن است با مقیاس بندی مجدد داده، نیمرخ با احتمال دقیقتری تعداد صحیح خوشه‌ها را معین کند.

اعتبارسنجی متقاطع Cross-validation

همچنین می‌توان از فرایند «اعتبارسنجی متقاطع» cross-validation به تجزیه و تحلیل تعداد خوشه پرداخت. در این فرایند، داده‌ها به v قطعه تقسیم می‌شوند. هر یک از قطعات به نوبه خود به عنوان یک مجموعه تست هستند. مدل خوشه بندی محاسبه شده در v − 1 مجموعه دیگر و مقدار تابع هدف (برای مثال مجموع مربعات فاصله به centroids برای k-means) برای مجموعه تست محاسبه می‌شوند. این v مقادیر محاسبه و برای هر تعداد خوشه جایگزینی محاسبه و میانگین گرفته می‌شود. تعداد خوشه انتخاب شده به طوری که افزایش در تعداد خوشه منجر به کوچک سازی در تابع هدف شود.

پیدا کردن تعداد خوشه در متن پایگاه داده

در متن پایگاه داده، یک مجموعه سند توسط یک سند ماتریس D جملهterms) تعریف شده‌است (m: تعداد اسناد n: تعداد جملات) تعداد خوشه تقریباً می‌تواند توسط فرمول  که در آن t تعداد غیر صفر ورودی‌ها در D است تخمین زده می‌شود. توجه داشته باشید که D در هر سطر و هر ستون باید حداقل شامل یک عنصر غیر صفر باشد.

روش kluster (برای داده‌های بزرگ)

بر اساس شبیه‌سازی‌های گسترده، فرایند kluster (موجود در بسته R kluster) مکانیزمی خودکار برای برآورد تعداد خوشه‌ها به خصوص در هنگام کار با داده‌های بزرگ اعمال می‌کند.

تجزیه و تحلیل هسته ماتریس

هسته ماتریس، مجاورت اطلاعات ورودی را تعریف می‌کند. برای مثال در تابع پایه شعاعی گوسی، نقطه ورودی‌ها را در فضایی با ابعادی بالاتر به نام «فضای ویژگی‌ها» تعیین می‌کند. اعتقاد بر این است که داده در فضای ویژگی‌ها به خطوطی قابل تفکیک تبدیل می‌شود. از این رو الگوریتم‌های خطی را می‌توان بر روی داده‌ها با موفقیت بالاتری بکار گرفت.
هسته ماتریس می‌تواند در جهت پیدا کردن تعداد بهینه خوشه‌ها تحلیل و پردازش شود. این روش با تجزیه مقدار ویژه (eigenvalue) هسته ماتریس کار می‌کند. سپس آن مقادیر ویژه و بردارهای ویژه (eigenvectors) برای به دست آوردن میزان فشردگی در توزیع ورودی‌ها تحلیل می‌شود. در نهایت یک طرح کشیده خواهد شد که در آن آرنج این طرح نشان دهنده تعداد بهینه خوشه‌ها در مجموعه داده‌است. بر خلاف روش‌های قبلی این روش نیازی به انجام هر خوشه یک-پیشینی (سابقه داده) ندارد. این روش به‌طور مستقیم تعداد خوشه‌ها را از داده‌ها می‌یابد.