خوشه‌بندی

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

در خوشه‌بندی، هدف تقسیم داده به گروه‌های مختلف است که با رنگ‌های مختلف در اینجا نشان داده شده‌اند.

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

اصطلاحات خوشه‌ها شامل گروه‌هایی با فاصله‌های کم بین اعضای خوشه، مناطق متراکم فضای داده، فواصل یا توزیع‌های آماری خاص است؛ بنابراین خوشه بندی می‌تواند به عنوان یک مسئله بهینه‌سازی چند هدفه صورت گیرد. الگوریتم خوشه‌بندی مناسب و تنظیمات پارامتر (از جمله پارامترهایی مانند تابع فاصله مورد استفاده، آستانه تراکم یا تعداد خوشه مورد انتظار) بستگی به تنظیم مجموعه داده‌ها توسط فرد و استفادهٔ خاص فرد از نتایج دارد. تجزیه و تحلیل خوشه‌ای یک روش اتوماتیک نیست، بلکه یک فرایند تکراری از کشف دانش یا بهینه‌سازی چند هدفهٔ تعاملی است که شامل آزمایش و شکست است. اغلب لازم است که داده‌های پیش پردازش شده و پارامترهای مدل اصلاح شوند تا نتیجه حاصل، همان نتیجهٔ دلخواه باشد.

افزون‌بر اصطلاحات خوشه‌بندی، تعدادی از اصطلاح با معانی مشابه وجود دارد، از جمله طبقه‌بندی خودکار، طبقه‌بندی عددی، روش‌شناسی و تجزیه و تحلیل توپولوژیکی. تفاوت‌های کم اغلب در نتایج استفاده می‌شود: در داده‌کاوی، نتیجه گروه‌ها مورد توجه هست و در طبقه‌بندی خودکار، قدرت تشخیصی مورد توجه است.

تجزیه و تحلیل خوشه‌ای در انسان‌شناسی توسط Driver و کروبر در سال ۱۹۳۲ آغاز شد و در روان‌شناسی توسط زوبین در سال ۱۹۳۸ و رابرت تراین در سال ۱۹۳۹ معرفی شد و در سال ۱۹۴۳ برای طبقه‌بندی نظریهٔ رفتاری در روانشناسی شخصیت توسط ریموند کاتل استفاده شده‌است.

تعریف

مفهوم «خوشه» را دقیقاً نمی‌توان تعریف کرد، یکی از دلایلش این است که الگوریتم‌های خوشه‌بندی زیادی وجود دارد. همهٔ آن‌ها یک قسمت مشترک دارند و آن یک گروه از اشیاء داده‌است. با این حال، محققان از مدل‌های مختلف خوشه استفاده می‌کنند و برای هر یک از این مدل‌های خوشه، الگوریتم‌های مختلفی را می‌توان ارائه داد. مفهوم یک خوشه، همان‌طور که توسط الگوریتم‌های مختلف یافت می‌شود، به‌طور خاصی در خواص تفاوت دارند. درک این مدل‌های خوشه، کلید فهمیدن تفاوت بین الگوریتم‌های مختلف است. مدل‌های خوشه‌ای معمول عبارتند از:

• مدل‌های متصل: به عنوان مثال، خوشه‌بندی سلسله‌مراتبی، مدل‌هایی براساس فاصله متصل را ایجاد می‌کند.
• مدل‌های مرکزی: به عنوان مثال، الگوریتم k-means، هر خوشه را با یک بردار متوسط نشان می‌دهد.
• مدل‌های توزیع: خوشه‌ها با استفاده از توزیع‌های آماری، مانند توزیع نرمال چند متغیره که در الگوریتم حداکثر انتظار، استفاده شده‌است.
• مدل‌های تراکم: به عنوان مثال، DBSCAN و OPTICS خوشه را به عنوان مناطق متراکم متصل در فضای داده تعریف می‌کنند.
• مدل‌های زیر فضایی: در biclustering (که به عنوان خوشهٔ مشترک یا خوشه ای دو حالت شناخته می‌شود)، خوشه‌ها با هر دو اعضای خوشه و ویژگی‌های مرتبط مدل‌سازی می‌شوند.
• مدل‌های گروهی: برخی از الگوریتم‌ها یک مدل تصحیح شده برای نتایج خود را ارائه نمی‌دهند و فقط اطلاعات گروه‌بندی را ارائه می‌دهند.
• مدل‌های مبتنی بر گراف: یک کلاس، یعنی یک زیر مجموعه از گره‌ها در یک گراف به طوری که هر دو گره در زیر مجموعه با یک لبه متصل می‌شود که می‌تواند به عنوان یک شکل اولیه از خوشه مورد توجه قرار گیرد.
• مدل‌های عصبی: شبکهٔ عصبی غیرقابل نظارت، شناخته شده‌ترین نقشهٔ خود سازمانی است و معمولاً این مدل‌ها می‌توانند به عنوان مشابه با یک یا چند مدل فوق شامل مدل‌های زیر فضایی، زمانی که شبکه‌های عصبی یک فرم تجزیه و تحلیل مؤلفه اصلی یا مستقل تجزیه و تحلیل المان می‌باشد.

«خوشه بندی» اساساً مجموعه‌ای از خوشه‌ها است که معمولاً شامل تمام اشیاء در مجموعه داده‌ها می‌شود. افزون‌بر این، می‌توان رابطهٔ خوشه‌ها را به یکدیگر تعریف کند، به عنوان مثال، سلسله‌مراتب خوشه‌های تعبیه شده در یکدیگر.

خوشه‌بندی را می‌توان براساس سختی تمایز به صورت زیر مشخص کرد:

• خوشه‌بندی سخت: هر شیء متعلق به خوشه است یا نه.
• خوشه‌بندی نرم (همچنین: خوشه فازی): هر شیء به درجه خاصی از هر خوشه متعلق است (به عنوان مثال، احتمال وابستگی به خوشه)

همچنین امکان تمایز دقیق‌تر وجود دارد، مثلاً:

• خوشه‌بندی جداسازی دقیق (پارتیشن‌بندی): هر شیء دقیقاً به یک خوشه متعلق است.
• خوشه‌بندی جداسازی دقیق با ناپیوستگی: اشیاء می‌توانند به هیچ خوشه‌ای تعلق نداشته باشند.
• خوشه‌بندی همپوشانی (همچنین: خوشه‌بندی جایگزین، خوشه‌بندی چندگانه): اشیاء ممکن است متعلق به بیش از یک خوشه باشد؛ معمولاً خوشه‌های سخت را شامل می‌شود
• خوشه‌بندی سلسله‌مراتبی: اشیایی که متعلق به خوشه فرزند هستند، متعلق به خوشه پدر و مادر هم هستند.
• خوشه‌بندی زیر فضا: در حالی که خوشه‌بندی همپوشانی، که در یک زیر فضای منحصر به فرد تعریف شده، انتظار نمی‌رود که خوشه‌ها با همپوشانی داشته باشند.

الگوریتم

همان‌طور که در بالا ذکر شد، الگوریتم‌های خوشه‌بندی را می‌توان بر اساس مدل خوشه‌ای طبقه‌بندی کرد. در ادامه نمونه‌های برجسته‌ای از الگوریتم‌های خوشه‌بندی بیان شده‌است، زیرا احتمالاً بیش از ۱۰۰ الگوریتم خوشه‌بندی منتشر شده وجود دارد. همه مدل‌ها برای خوشه‌هایشان بیان نشده‌اند، بنابراین نمی‌توان به راحتی دسته‌بندی کرد.

الگوریتم خوشه‌بندی عینی «صحیح» وجود ندارد، اما همان‌طور که اشاره شد، «خوشه‌بندی در چشم بیننده است.» بهترین الگوریتم خوشه‌بندی برای یک مسئلهٔ خاص، اغلب باید به صورت تجربی انتخاب شود، مگر اینکه یک دلیل ریاضی برای ترجیح دادن یک مدل خوشه بر دیگری وجود داشته باشد. لازم است ذکر شود که یک الگوریتم که برای یک نوع مدل طراحی شده‌است و در یک مجموعه داده‌ای که شامل تفاوت اساسی مدل است، شکست می‌خورد. به عنوان مثال، k-means نمی‌تواند خوشه‌های غیرمحدب را پیدا کند.

خوشه‌بندی براساس اتصال (خوشه‌بندی سلسه‌مراتبی)

خوشه بندی براساس اتصال، که همچنین به عنوان خوشه‌بندی سلسله‌مراتبی شناخته می‌شود، بر مبنای ایده اصلی اشیائی است که بیشتر مربوط به اشیای نزدیک، نسبت به اشیاء دورتر است. این الگوریتم‌ها «اشیا» را برای ایجاد «خوشه‌ها» بر اساس فاصلهٔ آن‌ها متصل می‌کنند. خوشه را می‌توان به طورکلی با حداکثر فاصله مورد نیاز برای اتصال قطعات خوشه توصیف کرد. در فاصله‌های مختلف، خوشه‌های متفاوتی شکل می‌گیرند که می‌تواند با استفاده از یک دندروگرام نشان داده شود، که توضیح می‌دهد که نام معمول «خوشه‌بندی سلسله‌مراتبی» از آن می‌آید: این الگوریتم‌ها یک پارتیشن‌بندی مجموعه داده را ارائه نمی‌دهند، بلکه یک سلسله‌مراتب گسترده‌ای از خوشه‌هایی که در فاصله‌های معینی با یکدیگر ادغام می‌شوند، ارائه می‌دهد. در یک دندروگرام محور y نشان‌دهندهٔ فاصله‌ای است که خوشه‌ها ادغام می‌کنند، در حالی که اشیاء در امتداد محور x قرار می‌گیرند به طوری که خوشه‌ها با هم مخلوط نمی‌شوند.

خوشه‌بندی سلسله‌مراتبی شامل دو نوع خوشه‌بندی می‌باشد:

1. خوشه‌بندی تک‌پیوندی (Single-Linkage Clustering): این روش که به روش Bottom-Up و Agglomerative نیز معروف است روشی است که در آن ابتدا هر داده به عنوان یک خوشه در نظر گرفته می‌شود. در ادامه با به‌کارگیری یک الگوریتم هر بار خوشه‌های دارای ویژگی‌های نزدیک به هم با یکدیگر ادغام شده و این کار ادامه می‌یابد تا به چند خوشهٔ مجزا برسیم. مشکل این روش حساس بودن به نویز و مصرف زیاد حافظه می‌باشد.

1. خوشه‌بندی کامل پیوند (Complete-Linkage Clustering): در این روش که به روش Top-Down و Divisive نیز معروف است ابتدا تمام داده‌ها به عنوان یک خوشه در نظر گرفته شده و با به‌کارگیری یک الگوریتم تکرار شونده هربار داده‌ای که کمترین شباهت را با داده‌های دیگر دارد به خوشه‌های مجزا تقسیم می‌شود. این کار ادامه می‌یابد تا یک یا چند خوشه یک عضوی ایجاد شود. مشکل نویز در این روش برطرف شده‌است.

مثال هایی از خوشه linkage

single linkage بر روی داده‌های گوسی

single linkage بر روی خوشه براساس density

خوشه بندی براساس مرکزوار (centroid)

در خوشه بندی براساس مرکزوار، خوشه‌ها با یک بردار مرکزی نشان داده می‌شوند، که ممکن است لزوماً جزء مجموعه داده نباشد. هنگامی که تعدادی از خوشه‌ها به k متصل می‌شوند، خوشه بندی k-means یک تعریف رسمی را به عنوان یک مسئله بهینه‌سازی ارائه می‌دهد.

روش میانگین k در عین سادگی یک روش بسیار کاربردی و پایه چند روش دیگر مثل خوشه بندی فازی و Segment-wise distributional clustering Algorithm می‌باشد. روش کار به این صورت است که ابتدا به تعداد دلخواه نقاطی به عنوان مرکز خوشه در نظر گرفته می‌شود. سپس با بررسی هر داده، آن را به نزدیک‌ترین مرکز خوشه نسبت می‌دهیم. پس از اتمام این کار با گرفتن میانگین در هر خوشه می‌توانیم مراکز خوشه و به دنبال آن خوشه‌های جدید ایجاد کنیم. (با تکرار مراحل قبل) از جمله مشکلات این روش این است که بهینگی آن وابسته به انتخاب اولیه مراکز بوده و بنابراین بهینه نیست. مشکلات دیگر آن تعیین تعداد خوشه‌ها و صفر شدن خوشه‌ها می‌باشد.

K-means دارای تعدادی خواص نظری است. اول، فضای داده را به یک ساختار معروف به یک نمودار Voronoi تقسیم می‌کند. دوم، به لحاظ مفهومی نزدیک به طبقه‌بندی نزدیکترین همسایه است و به همین علت در یادگیری ماشین محبوب است. سوم، می‌توان آن را به عنوان تنوع خوشه بندی براساس مدل مشاهده کرد.

• مثال هایی از خوشه بندی k-means
• 
  جداسازی داده‌های K-means در Voronoi-cells
• 
  عدم نمایش K-means برای خوشه‌های براساسdensity

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

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

یک روش شناخته شده، مدل مخلوط گاوس (با استفاده از الگوریتم حداکثر سازی انتظار) است. مجموعه داده‌ها معمولاً با یک ثابت (برای جلوگیری از overfitting) تعداد توزیع‌های گاوسی که به صورت تصادفی استفاده شده و به منظور مناسب تر کردن مجموعه داده مدل، پارامترهای آن به‌طور تکراری بهینه شده‌است که به یک بهینه محلی همگرا می‌شود، بنابراین در طول چند اجرا ممکن است نتایج متفاوتی تولید کند. به منظور به دست آوردن خوشه بندی سخت، اشیاء اغلب به توزیع گاوسی که به احتمال زیاد متعلق به آنهاست، اختصاص داده‌است که برای خوشه بندی نرم، اینکار لازم نیست. خوشه بندی مبتنی بر توزیع، مدل‌های پیچیده‌ای را برای خوشه‌ها ایجاد می‌کند که می‌تواند همبستگی و وابستگی ویژگی را نشان دهد.

• مثال های Expectation-maximization (EM)
• 
  برای داده‌های گوسی، em به خوبی عمل کرده‌است.
• 
  خوشه بندی براساس Density توزیع گوسی را به خوبی مدل نمی‌کند.

خوشه بندی براساس Density

در این تکنیک این اصل مطرح می‌شود که خوشه‌ها مناطقی با چگالی بیشتر هستند که توسط مناطق با چگالی کمتر از هم جدا شده‌اند. یکی از مهم‌ترین الگوریتم‌ها در این زمینه الگوریتم DBSCAN است.

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

• مثال هایی برای خوشه بندی براساس Density
• 
  خوشه بندی براساس Density با DBSCAN
• 
  DBSCAN و خوشه‌هایی باdensity مشابه .
• 
  OPTICS

پیشرفت‌های اخیر

در سال‌های اخیر تلاش‌های قابل توجهی در بهبود عملکرد الگوریتم‌های موجود انجام شده‌است. با توجه به نیازهای جدید به پردازش داده‌های خیلی بزرگ، تمایل به کاربرد خوشه‌های تولید شده برای عملکرد تجاری افزایش یافته‌است. این امر منجر به توسعه روش‌های پیش خوشه سازی مانند خوشه بندیcanopy می‌شود که می‌تواند داده‌های حجیم را به‌طور مؤثر پردازش کند.

برای داده‌های با ابعاد بزرگ، بسیاری از روش‌های موجود به علت ابعاد شکست خورده‌است، که باعث می‌شود که توابع خاص فاصله در فضاهای بزرگ بعدی مشکل ساز باشند. این باعث شد که الگوریتم‌های خوشه بندی جدید برای داده‌های با ابعاد بزرگ، بر خوشه بندی زیر فضایی تمرکز کنند و استفاده شود.

چندین سیستم خوشه بندی مختلف مبتنی بر اطلاعات متقابل پیشنهاد شده‌است. یکی از آن‌ها، تغییرات اطلاعات مارینا مالگا است که یکی دیگر از خوشه بندی سلسله‌مراتبی را فراهم می‌کند. با استفاده از الگوریتم‌های ژنتیکی، طیف گسترده‌ای از تناسب توابع مختلف، از جمله اطلاعات متقابل، می‌تواند بهینه‌سازی شود، پیشرفت اخیر در علوم کامپیوتری و فیزیک آماری، منجر به ایجاد انواع جدیدی از الگوریتم‌های خوشه بندی شده‌است.

ارزیابی مدل خوشه‌بندی

ارزیابی (یا «اعتبار سنجی») نتایج خوشه بندی به همان اندازه خوشه بندی سخت است. رویکردهای محبوب شامل ارزیابی "درونی" است که در آن خوشه بندی به یک عدد کیفیت واحد خلاصه می‌شود، ارزیابی "خارجی"، که در آن خوشه بندی با طبقه‌بندی "ground truth" موجود، ارزیابی "دستی" توسط متخصص و ارزیابی "غیر مستقیم " با استفاده از خوشه بندی در برنامه مورد نظر مقایسه می‌شود.

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

بنابراین هیچ‌کدام از این روش‌ها نهایتاً نمی‌توانند کیفیت واقعی خوشه بندی را قضاوت کنند، اما اینکار نیاز به ارزیابی انسانی دارد که بسیار ذهنی است.

ارزیابی داخلی

هنگامی که یک نتیجه خوشه بندی ای که بر اساس داده‌های خودش خوشه بندی شده‌است، ارزیابی شود، ارزیابی داخلی نامیده می‌شود. اگر از استاندارد gold استفاده شود، اندازه‌گیری خارجی نامیده می‌شوند و در بخش بعدی مورد بحث قرار می‌گیرد .(اگر متقارن باشد، می‌تواند اندازه‌گیری بین خوشه ایی برای ارزیابی داخلی استفاده شود) روش‌ها معمولاً بهترین عدد را برای الگوریتمی که درون خوشه شباهت زیاد و بین خوشه‌ها، شباهت کم باشد، تولید می‌کند. این ارزیابی به سمت الگوریتم‌هایی است که از یک مدل خوشه‌ای استفاده می‌کنند. به عنوان مثال، خوشه بندی k-means به‌طور طبیعی به فضاهای شئی بهینه می‌کند و معیار داخلی مبتنی بر فاصله، احتمالاً از خوشه‌بندی به دست می‌آید.

بنابراین، اقدامات ارزیابی داخلی برای درک وضعیتی که یک الگوریتم بهتر از دیگری عمل می‌کند، مناسب است، اما این به این معنی نیست که یک الگوریتم نتیجه‌های معتبرتری را نسبت به دیگری تولید کند.

بیش از دوازده اندازه‌گیری ارزیابی داخلی وجود دارد. به عنوان مثال، برای ارزیابی کیفیت خوشه بندی می‌توان از روش‌های زیر استفاده کرد.

شاخص Davies–Bouldin

شاخصDavies–Bouldin را می‌توان با فرمول زیر محاسبه کرد:

$D={\frac {\min _{1\leq i<j\leq n}d(i,j)}{\max _{1\leq k\leq n}d^{\prime }(k)}}\,,$

که n تعداد خوشه و $c_{x}$ مرکز خوشه x و σx فاصله متوسط همه عناصر در خوشه x و $d(c_{i},c_{j})$ فاصله بین مرکزهای $c_{i}$ و$c_{j}$ است. از آنجا که الگوریتم‌هایی که خوشه‌ها را با فاصله‌های درونی خوشه ای کم (شباهت بین خوشه ای بالا) و فاصله‌های بین خوشه ای بالا (شباهت بین خوشه ای پایین) تولید می‌کنند، یک شاخص Davies–Bouldin پایین خواهیم داشت، الگوریتم خوشه بندی که مجموعه ای از خوشه‌های با کوچکترین شاخصDavies–Bouldin، بهترین الگوریتم بر اساس این معیار است.

شاخص Dunn

هدف شاخص Dunn شناسایی خوشه‌های متراکم و جداسازی آنهاست و به عنوان نسبت بین کمترین فاصله بین خوشه ای تا حداکثر فاصله بین خوشه ای تعریف شده‌است. برای هر قسمت خوشه، شاخص دان را می‌توان با فرمول زیر محاسبه کرد:

$D={\frac {\min _{1\leq i<j\leq n}d(i,j)}{\max _{1\leq k\leq n}d^{\prime }(k)}}\,$

که d (i، j) فاصله بین خوشه‌های i و j را نشان می‌دهد و d '(k) فاصله بین خوشه ایی خوشه k را اندازه‌گیری می‌کند. فاصله بین خوشه ای d (i، j) بین دو خوشه ممکن است هر تعداد از اندازه‌گیری‌های فاصله، مانند فاصله بین centroids از خوشه‌ها باشد. به‌طور مشابه، فاصله بین خوشه ای d '(k) ممکن است از روش‌های مختلف اندازه‌گیری شود، مانند فاصله حداکثر بین هر جفت المان در خوشه k.

از آنجایی که معیار داخلی به دنبال خوشه‌هایی با شباهت بین خوشه ای بالا و شباهت بین خوشه ای کم است، الگوریتم‌هایی که خوشه‌ها را با شاخص Dunn بالایی تولید می‌کنند بیشتر مطلوب است.

ضریب سایه‌نما (Silhouette)

ضریب Silhouette در مقایسه با فاصله میانگین تا عناصر در خوشه‌های مشابه با میانگین فاصله تا عناصر در خوشه‌های دیگر، مقایسه می‌شود. اشیاء با Silhouette بالا به خوبی خوشه بندی می‌شوند، اشیاء باSilhouette کم ممکن است ناپایدار باشند. این شاخص با خوشه بندی k-means کار می‌کند و همچنین برای تعیین تعداد مطلوب خوشه‌ها استفاده می‌شود، برای محاسبه ضریب Silhouette باید مراحل زیر را طی کرد:

محاسبه و تفسیر ضریب Silhouette

• ابتدا داده ها توسط یکی از روش های خوشه بندی مانند k-means باید خوشه بندی شوند.
• حال اگر خوشه ها را با $C_{I}$ نمایش دهیم برای هر داده $i$ عضو $C_{I}$ میتوان $a(i)$ ،که معیاری برای ارزیابی این است که آیا داده به درستی به این گروه نسبت داده شده است یا نه، را به صورت روبرو تعریف کرد:
• $a(i)={\frac {1}{|C_{I}|-1}}\sum _{j\in C_{I},i\neq j}d(i,j)$
• در رابطه بالا $d(i,j)$ فاصله دو نقطه $i$ و $j$ می‌باشد و برای اینکه $d(i,i)=0$ است تقسیم بر $|C_{I}|-1$ میکنیم. با توجه به فرمول بالا $a(i)$ دارد میانگین نزدیکی داده $i$ به بقیه داده های خوشه ای که به آن نسبت داده شد را محاسبه میکند
• حال اگر $b(i)$ را مانند $a(i)$ تعریف کنیم، با این تفاوت که $b(i)$ میخواهد بهترین خوشه همسایه را پیدا کند، بدین صورت که مانند $a(i)$ فاصله $i$ را از بقیه نقاط خوشه های دیگر حساب می‌کند و $C_{J}$ ای را پیدا میکند که کمترین مقدار را میانگین فاصله را دارد:
• $b(i)=\min _{J\neq I}{\frac {1}{|C_{J}|}}\sum _{j\in C_{J}}d(i,j)$

• 

  ضریب $s(i)$ برای داده های خوشه بندی حیوانات

  حال که $a(i)$ و $b(i)$ را داریم برای اینکه مقایسه کنیم کدام گروه $I$ یا $J$ برای دسته بندی داده $i$ بهتر است از رابطه زیر استفاده میکنیم:
• $s(i)={\frac {b(i)-a(i)}{\max\{a(i),b(i)\}}}$
• اگر $a(i)\ll b(i)$ باشد یعنی داده $i$ به داده های گروه $I$ نزدیک تر است و خوشه بندی به درستی صورت گرفته است حال که شهود داریم به فرمول $s(i)$ بر میگردیم اگر $a(i)\ll b(i)$ باشد فرمول به فرم روبرو خواهد بود: $s(i)={\frac {b(i)-a(i)}{b(i)}}=1-{\frac {a(i)}{b(i)}}$ و به دلیل اینکه $a(i)\ll b(i)$ است کسر ${\frac {a(i)}{b(i)}}$ به صفر میل میکند و $s(i)$ به یک میل میکند پس با شهودی که داشتیم و حاصل $s(i)$ میتوان این نتیجه را گرفت که نزدیکی $s(i)$ به یک به معنای خوشه بندی درست است، همین استدلال را میتوان برای شرایطی که $b(i)\ll a(i)$ باشد نیز انجام داد و خواهیم دید که $s(i)$ به منفی یک میل میکند و به معنای خوشه بندی اشتباه ما است و بهتر است داده $i$ به خوشه $J$ تعلق داشته باشد، اما در شرایطی که $a(i)$ و $b(i)$ به هم نزدیک باشند $s(i)$ به صفر میل میکند و نمیتوان درمورد درستی خوشه بندی تصمیم گرفت.

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

• برای محاسبه میزان نزدیکی داده‌ها می‌توان میانگین $s(i)$ را برای تمام داده‌های یک خوشه محاسبه کرد.
• برای محاسبه درستی خوشه‌بندی مدلمان میانگین $s(i)$ را برای کل داده‌هایمان محاسبه می‌کنیم و هرچه به ۱ نزدیک‌تر باشد بهتر است.

حال به برتری اصلی ضریب اعتبارسنجی سایه‌نما نسبت به بقیه شاخص‌های خوشه‌بندی می‌رسیم، ضریب اعتبارسنجی سایه‌نما به ما این امکان را می‌دهد که مدلمان را با تعداد خوشه‌های متفاوت را با یک شاخص عددی مقایسه کنیم و با توجه به قسمت مورد قبلی آن تعداد خوشه را انتخاب کنیم که میانگین $s(i)$ برای آن بیشترین مقدار باشد.

ارزیابی خارجی

در ارزیابی خارجی، نتایج خوشه‌بندی بر اساس داده‌هایی که برای خوشه بندی استفاده نشدند، مانند برچسب‌های کلاس شناخته شده و معیارهای خارجی ارزیابی می‌شود. چنین معیارهایی قبل از طبقه‌بندی اغلب توسط متخصص تعیین می‌شود؛ بنابراین مجموعه معیارها می‌تواند به عنوان یک استاندارد gold برای ارزیابی استفاده شود. این نوع روش‌های ارزیابی اینکه چقدر خوشه بندی به کلاس‌های معیاری پیش تعیین شده نزدیک است، را تعیین می‌کند. با این حال، این‌که آیا این برای داده‌های واقعی مناسب است یا فقط بر روی مجموعه داده‌های مصنوعی با ground truth است، مورد بحث قرار گرفته‌است، از آنجا که کلاس‌ها می‌توانند ساختار داخلی داشته باشند، ویژگی‌های موجود ممکن است اجازه جدا شدن خوشه‌ها یا کلاس‌ها را ندهند.

همانند ارزیابی داخلی، چند اندازه‌گیری برای ارزیابی خارجی وجود دارد که در ادامه چند روش بیان شده‌است.

Purity: خلوص برای خوشه‌هایی که دارای یک کلاس واحد هستند، اندازه‌گیری می‌شود. برای محاسبهٔ آن، برای هر خوشه، تعداد نقاط داده از کلاس معمول در خوشهٔ مورد نظر شمرده می‌شود، سپس تمام خوشه‌ها را جمع شده و بر تعداد نقاط داده تقسیم می‌شود. با توجه به مجموعه ای از خوشه‌های M و برخی از مجموعه ای از کلاس‌های D، هر دو پارامتر با N نقطه داده، خلوص را می‌توان به صورت زیر تعریف کرد:

${\frac {1}{N}}\sum _{m\in M}\max _{d\in D}{|m\cap d|}$

اندازه‌گیری رند (ویلیام رند، 1971)

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

$RI={\frac {TP+TN}{TP+FP+FN+TN}}$

TP تعداد مثبت صحیح و TN تعداد منفی صحیح وFP تعداد مثبت کاذب وFN تعداد منفی‌های کاذب می‌باشد.

اندازه‌گیری F

اندازه‌گیری F را می‌توان برای تعادل مشارکت منفی‌های کاذب با استفاده از وزن دادن از طریق پارامتر β≥۰ استفاده کرد.

$P={\frac {TP}{TP+FP}}$

$R={\frac {TP}{TP+FN}}$

که pنرخ دقت و R نرخ فراخوان است. F را با استفاده از فرمول زیر محاسبه شده‌است:

$F_{\beta }={\frac {(\beta ^{2}+1)\cdot P\cdot R}{\beta ^{2}\cdot P+R}}$

اندیس ژاکار (Jaccard Index)

اندیس ژاکار برای اندازه‌گیری شباهت بین دو مجموعه داده استفاده می‌شود. شاخص Jaccard مقداری بین ۰ و ۱ دارد. شاخص ۱ بدین معنی است که دو مجموعه داده یکسان هستند و شاخص ۰ نشان می‌دهد که مجموعه داده‌ها هیچ عنصر مشترکی ندارند. شاخص Jaccard توسط فرمول زیر تعریف می‌شود:

$J(A,B)={\frac {|A\cap B|}{|A\cup B|}}={\frac {TP}{TP+FP+FN}}$

ضریب Dice

اندازه‌گیری متقارنDice دو برابر وزن TP است در حالی کهTN نادیده گرفته می‌شود و برابر با F1 است - اندازه‌گیری F با β = ۱:

$J(A,B)={\frac {|A\cap B|}{|A\cup B|}}={\frac {2TP}{2TP+FP+FN}}$

شاخصFowlkes-Mallows (E. B. Fowlkes & C. L. Mallows 1983)

شاخص Fowlkes-Mallows شباهت میان خوشه‌های بازگشتی توسط الگوریتم خوشه بندی و معیارهای طبقه‌بندی را محاسبه می‌کند. هر چه مقدار شاخص Fowlkes-Mallows بیشتر باشد خوشه‌ها و معیارهای طبقه‌بندی مشابه هستند. این شاخص را می‌توان با استفاده از فرمول زیر محاسبه کرد:

$FM={\sqrt {{\frac {TP}{TP+FP}}\cdot {\frac {TP}{TP+FN}}}}$

کهTP تعداد مثبت واقعی وFP تعداد مثبت کاذب وFN تعداد منفی‌های کاذب است. FM شاخص میانگین هندسی دقت و فراخوانی P, R است و همچنین به عنوان اندازه‌گیری G شناخته شده‌است، در حالی که اندازه‌گیری F میانگین هارمونیک آن‌ها است. علاوه بر این، دقت و یادآوری نیز به عنوان شاخص والاس $B^{I}$ و $B^{II}$ شناخته شده‌است.

اطلاعات متقابل، اندازه‌گیری نظری اطلاعاتی است که چقدر اطلاعات بین خوشه بندی و طبقه‌بندی ground-truth است که می‌تواند تشابه غیر خطی بین دو خوشه بندی را تشخیص دهد.

ماتریس درهم‌ریختگی (Confusion Matrix)

یک ماتریس درهم‌ریختگی می‌تواند برای به سرعت نتایج یک طبقه‌بندی (یا خوشه بندی) الگوریتم را نمایش دهد و نشان می‌دهد که چگونه یک خوشه از خوشه استاندارد gold متفاوت است.

تمایل خوشه (Cluster Tendency)

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

آمار Hopkins

فرمول‌های متعدد از آمار هاپکینز وجود دارد. یک نمونه به این صورت می‌باشد که: X مجموعه ای از n نقاط داده درd بعد است. یک نمونه تصادفی (بدون جایگزینی)

m≪n با اعضای xi را در نظر بگیرید. همچنین یک مجموعه Y از m نقطه داده با توزیع یکنواخت رندوم یکنواخت تولید کنید. دو فاصله اندازه‌گیری، ui فاصله از yi∈Y از نزدیک‌ترین همسایه اش در X و $w_{i}$ فاصله ازxi∈X از نزدیک‌ترین همسایه اش در X است. آمار Hopkins به صورت زیر تعریف می‌شود:

$H={\frac {\sum _{i=1}^{m}{u_{i}^{d}}}{\sum _{i=1}^{m}{u_{i}^{d}}+\sum _{i=1}^{m}{w_{i}^{d}}}}\,$

کاربرد

زیست‌شناسی، زیست‌شناسی محاسباتی و بیوانفورماتیک

بوم‌شناسی گیاه و حیوانات

تجزیه و تحلیل خوشه ای برای توصیف و مقایسه مقادیر مکانی و زمانی جوامع ارگانیسم‌ها در محیط‌های ناهمگن استفاده می‌شود؛ از آن نیز در سیستماتیک گیاه برای تولید فیلوژنتیک مصنوعی یا خوشه‌های ارگانیسم (افراد) در گونه، جنس یا سطح بالاتر که دارای تعدادی از ویژگی‌های مشترک است، استفاده می‌شود.

رونوشتگان‌شناسی (Transcriptomics Technologies) خوشه‌بندی برای ساخت گروهی از ژن‌ها با الگوی بیان مربوط به عنوان الگوریتم خوشه‌بندی HCS استفاده می‌شود. اغلب این گروه‌ها حاوی عملکرد پروتئین‌های مرتبط هستند، مانند آنزیم‌ها برای یک مسیر خاص، یا ژن‌هایی که هم تنظیم می‌شوند. آزمایش‌ها با توان بالا با استفاده از نشانگرهای ترتیبی بیان شده (ESTs) یا ریزآرایه‌های دی‌ان‌ای (DNA MicroArray) می‌تواند یک ابزار قدرتمند برای حاشیه‌نویسی ژنوم، یک جنبه عمومی ژنومیک باشد.

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

خوشه‌بندی برای دسته‌بندی هم‌ساخت‌شناسی توالی به خانواده‌های ژن، مورد استفاده قرار می‌گیرد. به‌طور کلی این مفهوم بسیار مهمی در بیوانفورماتیک و زیست‌شناسی تکاملی است.

سیستم عامل‌های ژنوتیپ با بازده بالا

الگوریتم خوشه‌بندی به‌طور خودکار برای تعیین ژنوتیپ‌ها استفاده می‌شود.

خوشه‌بندی ژنتیک انسانی

شباهت داده‌های ژنتیکی در خوشه‌بندی برای به دست آوردن ساختار جمعیت استفاده می‌شود.

پزشکی

تصویربرداری پزشکی

در PET، تجزیه خوشه ای می‌تواند برای تمایز بین انواع مختلف بافت در یک تصویر سه بعدی برای بسیاری از اهداف مختلف مورد استفاده قرار گیرد.

تجزیه و تحلیل فعالیت ضد میکروبی

تجزیه خوشه‌ای می‌تواند برای تجزیه و تحلیل الگوهای مقاومتی آنتی‌بیوتیکی، طبقه‌بندی ترکیبات ضد میکروبی مطابق با مکانیسم عمل آن‌ها، طبقه‌بندی آنتی‌بیوتیک‌ها بر اساس فعالیت ضد باکتری آن‌ها استفاده شود.

بخش‌بندی پرتودرمانی با شدت مدوله‌شده (IMRT)

خوشه‌بندی می‌تواند برای تقسیم یک نقشه روانی (Fluency Map) به مناطق مجزا برای تبدیل به زمینه‌های قابل ارائه در پرتودرمانی براساس MLC استفاده شود.

کسب و کار و بازاریابی

تحقیقات بازار

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

گروه‌بندی اقلام خرید

خوشه‌بندی را می‌توان برای دسته‌بندی تمام اقلام خرید موجود در وب به مجموعه‌ای از محصولات منحصر به فرد استفاده کرد. به عنوان مثال، تمام اقلام در eBay را می‌توان به محصولات منحصر به فرد گروه‌بندی کرد.

شبکه جهانی وب (اینترنت)

تجزیه و تحلیل شبکه اجتماعی

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

گروه‌بندی نتایج جستجو

در فرایند گروه‌بندی هوشمند از فایل‌ها و وب سایت‌ها، خوشه بندی ممکن است برای ایجاد یک مجموعه مناسب تر از نتایج جستجو در مقایسه با موتورهای جستجوی معمول مانند Google استفاده شود. در حال حاضر تعدادی از ابزارهای خوشه سازی مبتنی بر وب مانند Clusty وجود دارد.

بهینه‌سازی نقشه Slippy

در نقشه فلیکر از عکس‌ها و سایر Krai سایت‌ها از خوشه‌بندی برای کاهش تعداد نشانگرها در یک نقشه استفاده شده‌است. این باعث می‌شود که هر دو سریع‌تر و میزان خطای بصری را کاهش دهد.

علوم کامپیوتر

تکامل نرم‌افزار

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

بخش‌بندی تصویر

خوشه بندی می‌تواند برای تقسیم یک تصویر دیجیتال به مناطق مشخص برای تشخیص مرز یا تشخیص شی مورد استفاده قرار گیرد.

الگوریتم‌های تکاملی

خوشه بندی ممکن است برای شناسایی nichهای مختلف در جمعیت یک الگوریتم تکاملی استفاده شود تا فرصت تولید مجد را به‌طور یکنواخت تر بین گونه‌ها یا گونه‌های در حال رشد توزیع کرد.

سیستم توصیه‌گر

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

روش مارکوف مونت کارلو زنجیره ای

خوشه‌بندی اغلب برای تعیین مکان و تشخیص بیشینه در توزیع هدف، مورد استفاده قرار می‌گیرد.

تشخیص ناهنجاری

ناهنجاری‌ها معمولاً - به صراحت یا به‌طور ضمنی - با توجه به ساختار خوشه‌ای در داده‌ها تعریف می‌شود.

علوم اجتماعی

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

از تجزیه و تحلیل خوشه‌ای می‌توان برای شناسایی مناطق که در آن موارد بیشتر از انواع خاصی از جرم وجود دارد استفاده شود. با شناسایی این مناطق متمایز یا "هات اسپات" که جرم مشابهی در طی یک دوره زمانی اتفاق افتاده است، می‌توان منابع اجرای قانون را به‌طور مؤثرتر مدیریت کرد.

داده‌کاوی آموزشی

به عنوان مثال، تجزیه و تحلیل خوشه‌ای برای شناسایی گروه‌های مدارس یا دانشجویانی با ویژگی مشابه استفاده می‌شود.

گونه‌شناسی

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

و کاربردهای دیگر

در زمینه رباتیک

الگوریتم خوشه‌بندی برای آگاهی موقعیت رباتیک برای ردیابی اشیاء و تشخیص خروجی‌ها در داده‌های سنسور استفاده می‌شود.

شیمی محاسباتی

به عنوان مثال، برای پیدا کردن شباهت ساختاری و غیره، به عنوان نمونه، ۳۰۰۰ ترکیب شیمیایی در فضای ۹۰ شاخص توپولوژیکی، خوشه‌بندی شدند.

اقلیم‌شناسی

برای پیدا کردن آب و هوایی یا الگوهای فشار جو در سطح دریا مورد نظر است.

زمین‌شناسی نفت

تجزیه و تحلیل خوشه‌ای برای بازسازی داده‌های اصلی ازدست رفته سوراخ پایین یا منحنی‌های لگاریتمی از دست رفته به منظور بررسی خواص مخزن استفاده می‌شود.

جغرافیای فیزیکی

خوشه‌بندی خواص شیمیایی در مکان‌های مختلف نمونه.

جستارهای وابسته

• یادگیری ماشینی
• یادگیری بی‌نظارت
• کاهش ابعاد

منابع

https://en.wiki.x.io/wiki/Cluster_analysis