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

تعیین تعداد خوشه در یک مجموعه داده، مقداری اغلب دارای برچسب 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: تعداد جملات) تعداد خوشه تقریباً می‌تواند توسط فرمول ${\frac {nm}{t}}$ که در آن t تعداد غیر صفر ورودی‌ها در D است تخمین زده می‌شود. توجه داشته باشید که D در هر سطر و هر ستون باید حداقل شامل یک عنصر غیر صفر باشد.^[۱۱]

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

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

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

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

هسته ماتریس می‌تواند در جهت پیدا کردن تعداد بهینه خوشه‌ها تحلیل و پردازش شود.^[۱۴] این روش با تجزیه مقدار ویژه (eigenvalue) هسته ماتریس کار می‌کند. سپس آن مقادیر ویژه و بردارهای ویژه (eigenvectors) برای به دست آوردن میزان فشردگی در توزیع ورودی‌ها تحلیل می‌شود. در نهایت یک طرح کشیده خواهد شد که در آن آرنج این طرح نشان دهنده تعداد بهینه خوشه‌ها در مجموعه داده‌است. بر خلاف روش‌های قبلی این روش نیازی به انجام هر خوشه یک-پیشینی (سابقه داده) ندارد. این روش به‌طور مستقیم تعداد خوشه‌ها را از داده‌ها می‌یابد.

کتاب‌شناسی[ویرایش]

↑ See, e.g. , David J. Ketchen Jr; Christopher L. Shook (1996). "The application of cluster analysis in Strategic Management Research: An analysis and critique". Strategic Management Journal. 17 (6): 441–458. doi:10.1002/(SICI)1097-0266(199606)17:6<441::AID-SMJ819>3.0.CO;2-G.^{^{[پیوند مرده]}}
↑ See, e.g. , Figure 6 in
↑ Robert L. Thorndike (December 1953). "Who Belongs in the Family?". Psychometrika. 18 (4): 267–276. doi:10.1007/BF02289263.
↑ {{cite conference}}: Empty citation (help)
↑ Cyril Goutte, Lars Kai Hansen, Matthew G. Liptrot & Egill Rostrup (2001). "Feature-Space Clustering for fMRI Meta-Analysis". Human Brain Mapping. 13 (3): 165–183. doi:10.1002/hbm.1031. PMID 11376501. Archived from the original on 17 December 2012. Retrieved 30 October 2018.{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)CS1 maint: Multiple names: authors list (link)
↑ Catherine A. Sugar; Gareth M. James (2003). "Finding the number of clusters in a data set: An information-theoretic approach". Journal of the American Statistical Association. 98 (January): 750–763. doi:10.1198/016214503000000666.
↑ Peter J. Rousseuw (1987). "Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis". Computational and Applied Mathematics. 20: 53–65. doi:10.1016/0377-0427(87)90125-7.
↑ R. Lleti; M.C. Ortiz; L.A. Sarabia; M.S. Sánchez (2004). "Selecting Variables for k-Means Cluster Analysis by Using a Genetic Algorithm that Optimises the Silhouettes". Analytica Chimica Acta. 515: 87–100. doi:10.1016/j.aca.2003.12.020.
↑ R.C. de Amorim & C. Hennig (2015). "Recovering the number of clusters in data sets with noise features using feature rescaling factors". Information Sciences. 324: 126–145. arXiv:1602.06989. doi:10.1016/j.ins.2015.06.039.
↑ See e.g. "Finding the Right Number of Clusters in k-Means and EM Clustering: v-Fold Cross-Validation". Electronic Statistics Textbook. StatSoft. 2010. Archived from the original on 1 May 2015. Retrieved 2010-05-03.
↑ Can, F.; Ozkarahan, E. A. (1990). "Concepts and effectiveness of the cover-coefficient-based clustering methodology for text databases". ACM Transactions on Database Systems. 15 (4): 483. doi:10.1145/99935.99938.
↑ "hestiri/kluster". GitHub (به انگلیسی). Retrieved 2018-09-20.
↑ Estiri, Hossein; Abounia Omran, Behzad; Murphy, Shawn N. (June 2018). "kluster: An Efficient Scalable Procedure for Approximating the Number of Clusters in Unsupervised Learning". Big Data Research. doi:10.1016/j.bdr.2018.05.003. ISSN 2214-5796.
↑ Honarkhah, M; Caers, J (2010). "Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling". Mathematical Geosciences. 42: 487–517. doi:10.1007/s11004-010-9276-7.

[1] See, e.g. , David J. Ketchen Jr; Christopher L. Shook (1996). "The application of cluster analysis in Strategic Management Research: An analysis and critique". Strategic Management Journal. 17 (6): 441–458. doi:10.1002/(SICI)1097-0266(199606)17:6<441::AID-SMJ819>3.0.CO;2-G.^{^{[پیوند مرده]}}

[2] See, e.g. , Figure 6 in

[3] Robert L. Thorndike (December 1953). "Who Belongs in the Family?". Psychometrika. 18 (4): 267–276. doi:10.1007/BF02289263.

[4] {{cite conference}}: Empty citation (help)

[5] Cyril Goutte, Lars Kai Hansen, Matthew G. Liptrot & Egill Rostrup (2001). "Feature-Space Clustering for fMRI Meta-Analysis". Human Brain Mapping. 13 (3): 165–183. doi:10.1002/hbm.1031. PMID 11376501. Archived from the original on 17 December 2012. Retrieved 30 October 2018.{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)CS1 maint: Multiple names: authors list (link)

[6] Catherine A. Sugar; Gareth M. James (2003). "Finding the number of clusters in a data set: An information-theoretic approach". Journal of the American Statistical Association. 98 (January): 750–763. doi:10.1198/016214503000000666.

[7] Peter J. Rousseuw (1987). "Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis". Computational and Applied Mathematics. 20: 53–65. doi:10.1016/0377-0427(87)90125-7.

[8] R. Lleti; M.C. Ortiz; L.A. Sarabia; M.S. Sánchez (2004). "Selecting Variables for k-Means Cluster Analysis by Using a Genetic Algorithm that Optimises the Silhouettes". Analytica Chimica Acta. 515: 87–100. doi:10.1016/j.aca.2003.12.020.

[9] R.C. de Amorim & C. Hennig (2015). "Recovering the number of clusters in data sets with noise features using feature rescaling factors". Information Sciences. 324: 126–145. arXiv:1602.06989. doi:10.1016/j.ins.2015.06.039.

[10] See e.g. "Finding the Right Number of Clusters in k-Means and EM Clustering: v-Fold Cross-Validation". Electronic Statistics Textbook. StatSoft. 2010. Archived from the original on 1 May 2015. Retrieved 2010-05-03.

[11] Can, F.; Ozkarahan, E. A. (1990). "Concepts and effectiveness of the cover-coefficient-based clustering methodology for text databases". ACM Transactions on Database Systems. 15 (4): 483. doi:10.1145/99935.99938.

[12] "hestiri/kluster". GitHub (به انگلیسی). Retrieved 2018-09-20.

[13] Estiri, Hossein; Abounia Omran, Behzad; Murphy, Shawn N. (June 2018). "kluster: An Efficient Scalable Procedure for Approximating the Number of Clusters in Unsupervised Learning". Big Data Research. doi:10.1016/j.bdr.2018.05.003. ISSN 2214-5796.

[14] Honarkhah, M; Caers, J (2010). "Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling". Mathematical Geosciences. 42: 487–517. doi:10.1007/s11004-010-9276-7.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

[۱۰]

[۱۱]

[۱۲]

[۱۳]

[۱۴]