الگوریتمهای خوشهبندی
الگوریتمهای خوشهبندی دادهها را به گروههایی از اقلام مشابه تقسیم میکنند و ساختار طبیعی را بدون استفاده از هیچ برچسبی آشکار میسازند.
Definition
خوشهبندی، تقسیمبندی بدون نظارت یک مجموعه داده به گروههایی است که در آن نقاط درون یک گروه بیشتر به یکدیگر شبیه هستند تا به نقاط در گروههای دیگر، که در آن شباهت با یک معیار فاصله یا چگالی انتخاب شده برای کاربرد تعریف میشود.
Scope
این موضوع خانوادههای اصلی خوشهبندی را پوشش میدهد: روشهای مبتنی بر مرکز مانند k-means، خوشهبندی تجمعی سلسلهمراتبی که درختی از گروههای تودرتو را میسازد، روشهای مبتنی بر چگالی که خوشههایی با اشکال دلخواه را پیدا میکنند، و انتخاب معیارهای فاصله و تعداد خوشهها. این موضوع به این میپردازد که چه چیزی یک خوشهبندی خوب را تشکیل میدهد و چرا این مسئله ذاتاً مبهم است.
Core questions
- چه چیزی مجموعهای از نقاط را یک خوشه میسازد؟
- چگونه k-means به صورت تکراری واریانس درون خوشهای را به حداقل میرساند؟
- تعداد خوشهها چگونه انتخاب میشود؟
- چه زمانی روشهای سلسلهمراتبی یا مبتنی بر چگالی بهتر از روشهای مبتنی بر مرکز عمل میکنند؟
Key theories
- k-means و الگوریتم لوید
- k-means با تناوب در تخصیص نقاط به نزدیکترین مراکز و محاسبه مجدد مراکز، مجموع فاصله مربعات تا مراکز خوشه را به حداقل میرساند، رویهای که به یک بهینه محلی همگرا میشود.
- خوشهبندی سلسلهمراتبی
- خوشهبندی تجمعی به طور مکرر نزدیکترین گروهها را ادغام میکند تا یک دندروگرام بسازد، خوشهبندیها را در هر سطح از جزئیات ارائه میدهد و نیاز به تعیین تعداد خوشهها از پیش را از بین میبرد.
- خوشهبندی مدل آمیخته
- در نظر گرفتن خوشهها به عنوان مؤلفههای یک آمیخته احتمالی، امکان تخصیص نرم و خوشههایی با شکل و اندازه متفاوت را فراهم میکند و خوشهبندی را به تخمین چگالی متغیر پنهان مرتبط میسازد.
Clinical relevance
خوشهبندی زیربنای تقسیمبندی بازار، سازماندهی اسناد و تصاویر، گروهبندی بیان ژن، و تشخیص ناهنجاری است و ابزاری اولیه برای تحلیل اکتشافی دادهها محسوب میشود؛ از آنجا که خوشهبندیها به فاصله و تعداد گروههای انتخاب شده بستگی دارند، نتایج باید با دقت تفسیر شوند و نه به عنوان یک حقیقت مطلق منحصر به فرد تلقی گردند.
History
روش k-means به کار کوانتیزاسیون لوید در سال 1957 بازمیگردد که در سال 1982 منتشر شد، و به فرمولبندی مستقل مککوئین. خوشهبندی سلسلهمراتبی در طبقهبندی عددی پدید آمد، و روشهای مبتنی بر چگالی مانند DBSCAN خوشهبندی را به گروههایی با اشکال دلخواه گسترش دادند، که در مجموع ابزار استاندارد گروهبندی بدون نظارت را تشکیل میدهند.
Key figures
- Stuart Lloyd
- James MacQueen
- Trevor Hastie
Related topics
Seminal works
- lloyd1982
- hastie2009
- bishop2006
Frequently asked questions
- چرا k-means نیاز به انتخاب تعداد خوشهها دارد؟
- k-means جایگذاری تعداد ثابتی از مراکز را بهینه میکند، بنابراین آن عدد یک ورودی است. انتخاب آن بر اساس روشهای اکتشافی مانند روش آرنج، امتیازات سیلوئت، یا دانش دامنه است، زیرا افزودن خوشههای بیشتر همیشه فاصله درون خوشهای را کاهش میدهد.
- آیا روشهای خوشهبندی مختلف میتوانند پاسخهای متفاوتی بدهند؟
- بله. از آنجا که تعریف واحدی برای خوشه وجود ندارد، روشهای مبتنی بر مرکز، سلسلهمراتبی و مبتنی بر چگالی میتوانند تقسیمبندیهای متفاوتی از دادههای یکسان تولید کنند که هر یک تحت معیار خود معتبر است. انتخاب صحیح به اشکال مورد انتظار خوشه و هدف بستگی دارد.