تعیین تعداد خوشه‌ها در یک مجموعه داده: تفاوت میان نسخه‌ها
ایجاد شده توسط ترجمهٔ صفحهٔ «Determining the number of clusters in a data set» |
(بدون تفاوت)
|
نسخهٔ ۳۰ اکتبر ۲۰۱۸، ساعت ۱۸:۲۵
تعیین تعداد خوشه در یک مجموعه داده، مقداری اغلب دارای برچسب k در الگوریتم k-means و مشکلی پرتکرار در خوشه بندی داده ها و مسئله ای متمایز از فرایند حل مشکل خوشه بندی است.
برای یک کلاس خاص از الگوریتم های خوشه بندی (به ویژه در k-medoids، k-means و (الگوریتم امید ریاضی–بیشینه کردن) پارامتری به عنوان k معمولا وجود دارد که تعداد خوشه ها را تشخیص می دهد. الگوریتم های دیگری مانند DBSCAN و اپتیک الگوریتم مشخصات این پارامتر را نیاز ندارند; خوشه بندی سلسله مراتبی این مشکل را بصورت کلی ندارد.
انتخاب صحیح عدد k اغلب مبهم است و با تفاسیری به شکل و مقیاس توزیع نقاط در یک مجموعه داده و نیت خوشه بندی کاربر بستگی دارد. به علاوه افزایش k بدون مجازات (penalty) به کاهش میزان خطا در نتیجهء خوشه بندی منجر می شود. در شدید ترین حالت از صفر خطا اگر هر نقطه داده، خود یک خوشه درنظر گرفته شود. (به عنوان مثال زمانی که k برابر با تعداد نقاط داده ها باشد). به طور مستقیم و سپس با انتخاب بهینه از k به تعادلی بین حداکثر فشرده سازی داده ها با استفاده از یک خوشه و حداکثر دقت، با اختصاص هر نقطه داده به یک خوشه خواهیم رسید. اگر یک مقدار مناسب از k با استفادهاز دانش قبلی از خواص آن مجموعه داده مشخص نباشد، باید به نحوی انتخاب شود. چند دسته روش رای این تصمیم گیری وجود دارد.
روش آرنج (The elbow method)
روش آرنج درصد واریانس را به عنوان تابعی از تعداد خوشه ها توضیح می دهد: یکی باید بعنوان تعداد خوشه ها اتخاب شود به طوری که با اضافه کردن خوشه ای دیگر مدل سازی داده بهتری بدست نیاید. دقیق تر، اگر یک ترسیم (plot) درصد واریانس را تشریح کند طوریکه مخالف تعداد خوشه ها باشد اولین خوشه ها اطلاعات زیادی (توضیح بسیاری از واريانس) را اضافه می کنند، اما در بعضی نقطه ها حاشیه سود کاهش خواهد یافت و یک زاویه در نمودار بوجود می آورد. تعداد خوشه ها در این نقطه انتخاب شده اند یعنی همان "معیار آرنج". این "آرنج" نمی تواند همیشه به روشنی مشخص شود.[۱] درصد از واریانس نسبت واریانس بین-گروهی به کل واریانس را توضیح داده , همچنینبه عنوان یک آزمون F شناخته شده است. تنوع اندکی از این روش انحنای درون واریانس گروهی را ترسیم (plot) می کند.[۲]
این روش را می توان به گمانه زنی توسط Robert L. Thorndike در سال 1953 نسبت داد.[۳]
خوشه بندی X-means
در آمار و داده کاوی، X-means clustering نوعی از k-means خوشه بندی است که خوشه ها را براساس عملیات مکرر تقسیم و دسته بندی، و نگه داشتن بهترین نتیجه تا زمانی که معیاری مانند Akaike information criterion (AIC) و یا بیزی اطلاعات معیار (BIC) بدست آید.[۴]
رویکرد معیارهای اطلاعاتی (Information criterion)
یکی دیگر از مجموعه روشها برای تعیین تعداد خوشه ها، اطلاعات معیاری مانند (Akaike information criterion (AIC, اطلاعات معیارBIC) Bayesian) و یا انحراف اطلاعات معیار (DIC) — اگر ایجاد تابع برای مدل خوشه بندی ممکن باشد. به عنوان مثال: مدل k-means مدل "تقریبا" یک Gaussian mixture model است و ساخت احتمالی برای مدل مرکب گوسی مقدور است و نتیجه نیز تعیین مقادیر معیار است.[۵]
رویکرد نظری اطلاعات (information–theoretic)
نظریه نرخ اعوجاج برای انتخاب k به نام روش "پرش" نامگذاری شده است که تعداد خوشه ها را برای دستیابی به حداکثر راندمان و همزمان به حداقل رساندن خطا توسط استانداردهای اطلاعات نظری تعیین می کند.[۶] استراتژی الگوریتم این است که اعوجاج منحنی تولید می کند برای داده های ورودی در حال اجرا توسط استاندارد الگوريتم خوشه بندی مانند k-means برای تمام مقادیر k بین 1 و n و اعوجاج را (در زیر توضیح داده شده) و در نتیجه خوشه بندی مشخص می کند. اعوجاج منحنی معیاری منفی برای تعیین ابعاد داده است. روش "پرش" مقادیری را برای انتخاب درست k خروجی می دهد. بزرگترین پرش بعنوان بهترین انتخاب است.
روش نیمرخ (silhouette)
متوسط نیمرخ (silhouette) از اطلاعات معیار مفید دیگری برای ارزیابی طبیعی تعداد خوشه هاست. نیمرخِ (silhouette) یک نمونه داده میزان نزدیک شدن داده ها درون خوشه و میزان آزادی و فاصله داده ها از خوشه همسایه است. یعنی خوشه ای که میانگین فاصله از مرجع "datum" پایین ترین است.[۷] یک نیمرخ نزدیک به 1 به معنی است که datum در خوشه ای مناسب است در حالی که یک نیمرخ نزدیک به -1 به این معنی است که datum در خوشه اشتباه قرار گرفته است. تکنیک های بهینه سازی مانند الگوریتم ژنتیک در تعیین تعداد خوشه ها مفیدند که بزرگترین نیمرخ را بدست می دهند.[۸] همچنین ممکن است با مقیاس بندی مجدد داده، نیمرخ با احتمال دقیقتری تعداد صحیح خوشه ها را معین کند.[۹]
اعتبارسنجی متقاطع Cross-validation
همچنین می توان از فرایند "اعتبارسنجی متقاطع" cross-validation به تجزیه و تحلیل تعداد خوشه پرداخت. در این فرآیند، داده ها به v قطعه تقسیم می شوند. هر یک از قطعات به نوبه خود به عنوان یک مجموعه تست هستند. مدل خوشه بندی محاسبه شده در v − 1 مجموعه دیگر و مقدار تابع هدف (برای مثال مجموع مربعات فاصله به centroids برای k-means) برای مجموعه تست محاسبه می شوند. این v مقادیر محاسبه و برای هر تعداد خوشه جایگزینی محاشبه و میانگین گرفته می شود. تعداد خوشه انتخاب شده به طوری که افزایش در تعداد خوشه منجر به کوچک سازی در تابع هدف شود. [۱۰]
پیدا کردن تعداد خوشه در متن پایگاه داده
در متن پایگاه داده، یک مجموعه سند توسط یک سند ماتریس D جملهterms) تعریف شده است (با اندازه m n m: تعداد اسناد n: تعداد جملات) تعداد خوشه تقریبا می تواند توسط فرمول زیر که در آن 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.
{{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.
{{cite journal}}: Unknown parameter|last-author-amp=ignored (|name-list-style=suggested) (help) - ↑ See e.g. "Finding the Right Number of Clusters in k-Means and EM Clustering: v-Fold Cross-Validation". Electronic Statistics Textbook. StatSoft. 2010. 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.