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

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

شکل 1: در این شکل نمونه‌ای از اعمال خوشه‌بندی روی یک مجموعه از داده‌ها مشخص شده است که از معیار فاصله(Distance) به عنوان عدم شباهت(Dissimilarity) بین داده‌ها استفاده شده است.

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

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

a

b

شکل 2: a) در طبقه‌بندی با استفاده یک سری اطلاعات اولیه داده‌ها به دسته‌های معلومی نسبت داده‌ می‌شوند. در خوشه‌بندی داده‌ها با توجه به الگوریتم انتخاب شده به خوشه‌هایی نسبت داده‌ می‌شوند

کاربردها

از آنجا که خوشه‌بندی یک روش یادگیری بدون نظارت محسوب می‌گردد، در موارد بسیاری می‌تواند کاربرد داشته‌ باشد
در بازاریابی (Marketing): دسته‌‌بندی مشتری‌ها به دسته‌هایی بر حسب رفتارها و نیازهای آنها از طریق مجموعه زیادی از ویژگی‌ها و آخرین خرید‌های آنها.
زیست‌‌‌شناسی (Biology): دسته‌بندی حیوانات و گیاهان از روی ویژگی‌های آنها
کتابداری : دسته‌بندی کتابها
نقشه‌برداری شهری (City-Planning): دسته‌بندی خانه‌ها بر اساس نوع و موقعیت جغرافیایی آنها.
مطالعات زلزله‌نگاری (Earthquake studies): تشخیص مناطق حادثه‌خیز بر اساس مشاهدات قبلی.
وب (WWW): دسته‌بندی اسناد و یا دسته‌بندی مشتریان به سایتها و ….
داده کاوی (Data Mining): کشف اطلاعات و ساختار جدید از داده‌های موجود
در تشخیص گفتار (Speech Recognition): در ساخت کتاب کد از بردارهای ویژگی، در تقسیم کردن گفتار بر حسب گویندگان آن و یا فشرده‌سازی گفتار
در تقسیم‌بندی تصاویر(Image Segmentation): تقسیم‌بندی تصاویر پزشکی و یا ماهواره‌ای

روش‌های خوشه‌بندی

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

1- خوشه‌بندی انحصاری (Exclusive or Hard Clustering) و خوشه‌بندی با هم‌پوشی (Overlapping or Soft Clustering)
در روش خوشه‌بندی انحصاری پس از خوشه‌بندی هر داده دقیقأ به یک خوشه تعلق می‌گیرد مانند روش خوشه‌بندی K-Means. ولی در خوشه‌بندی با همپوشی پس از خوشه‌بندی به هر داده یک درجه تعلق بازاء هر خوشه نسبت داده می‌شود. به عبارتی یک داده می‌تواند با نسبتهای متفاوتی به چندین خوشه تعلق داشته باشد. نمونه‌ای از آن خوشه‌بندی فازی است.

2- خوشه‌بندی سلسله مراتبی (Hierarchical) و خوشه‌بندی مسطح(Flat)
در روش خوشه بندی سلسله مراتبی، به خوشه‌های نهایی بر اساس میزان عمومیت آنها ساختاری سلسله‌ مراتبی نسبت داده می‌شود. مانند روش Single Link. ولی در خوشه‌بندی مسطح تمامی خوشه‌های نهایی دارای یک میزان عمومیت هستند مانند K-Means. به ساختار سلسله مراتبی حاصل از روشهای خوشه‌بندی سلسله مراتبی دندوگرام (Dendogram) گفته می‌شود.

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

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

همان گونه که بیان شد، در روش خوشه بندی سلسله مراتبی، به خوشه‌های نهایی بر اساس میزان عمومیت آنها ساختاری سلسله‌ مراتبی، معمولا به صورت درختی نسبت داده می‌شود. به ا ین درخت سلسله مراتبی دندوگرام (dendogram) می‌گویند. روش کار تکنیکهای خوشه‌بندی سلسله‌مراتبی معمولا بر اساس الگوریتمهای حریصانه (Greedy Algorithms) و بهینگی مرحله‌ای (stepwise-optimal) است. روشهای خوشه‌بندی بر اساس ساختار سلسله مراتبی تولیدی توسط آنها معمولا به دو دستة زیر تقسیم می‌شوند:

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

2.پایین به بالا (Bottom-Up) یا متراکم شونده (Agglomerative): در این روش ابتدا هر داده‌ها به عنوان خوشه‌ای مجزا در نظر گرفته می‌شود و در طی فرایندی تکراری در هر مرحله خوشه‌هایی که شباهت بیشتری با یکدیگر با یکدیگر ترکیب می‌شوند تا در نهایت یک خوشه و یا تعداد مشخصی خوشه حاصل شود. از انواع الگوریتمهای خوشه‌بندی سلسله مراتبی متراکم شونده رایج می‌توان از الگوریتمهای Single-Link، Average-Link و Complete-Link نام برد. تفاوت اصلی در بین تمام این روشها به نحوة محاسبة شباهت بین خوشه‌ها مربوط می‌شود. که در بخشهای بعد به تشریح هر یک پرداخته خواهد شد.

خوشه‌بندی با روش Single-Link

این روش یکی از قدیمی‌ترین و ساده‌ترین روشهای خوشه‌بندی است و جزء روشهای خوشه‌بندی سلسله مراتبی و انحصاری محسوب می‌شود. به این روش خوشه‌بندی، تکنیک نزدیکترین همسایه (Nearest Neighbour) نیز گفته می‌شود. در این روش برای محاسبة شباهت بین دو خوشة A و B از معیار زیر استفاده می‌شود:

که i یک نمونه داده متعلق به خوشة A و j یک نمونه دادة متعلق به خوشة B می‌باشد. در واقع در این روش شباهت بین دو خوشه، کمترین فاصلة بین یک عضو از یکی با یک عضو از دیگری است. در شکل زیر این مفهوم بهتر نشان‌ داده شده است

شکل 4: شباهت بین دو خوشه در روش Single-Link برابر است با کمترین فاصلة بین داده‌های دو خوشه

1-1-1- مثال: در این قسمت سعی شده است تا در مثالی با فرض داشتن 6 نمونه داده و ماتریس فاصلة بین آنها که در جدول 1 نشان‌داده شده است، نحوة اعمال روش خوشه‌بندی Single-Link بهتر تشریح شود

جدول 1: ماتریس فاصلة بین 6 نمونة داده

در ابتدا هر داده به عنوان یک خوشه در نظر گرفته می‌شود و یافتن نزدیکترین خوشه در واقع یافتن کمترین فاصلة بین داده‌های بالا خواهد بود. با توجه به جدول 1 مشخص است که داده‌های 3 و 5 کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با کمترین فاصلة بین 3 و یا 5 از سایر خوشه‌ها. نتیجه در جدول 2 نشان ‌داده شده است.

با توجه به جدول 2 مشخص است که داده‌های 1 و 2 کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با کمترین فاصلة بین 1 و یا 2 از سایر خوشه‌ها. نتیجه در جدول 3 نشان ‌داده شده است.

با توجه به جدول 3 مشخص است که خوشه‌های (3 و 5) و 4 کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با کمترین فاصلة بین (3 و 5) و یا 4 از سایر خوشه‌ها. نتیجه در جدول 4 نشان ‌داده شده است.

با توجه به جدول 4 مشخص است که خوشه‌های (1 و 2) و 6 کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با کمترین فاصلة بین (1 و 2) و یا 6 از سایر خوشه‌ها. نتیجه در جدول 5 نشان ‌داده شده است.

در نهایت این دو خو‌شة حاصل ا هم ترکیب می‌شوند. نتیجه در دندوگرام شکل 5 نشان داده شده است.

شکل 5: دندوگرام مثال Single-Link