انواع خوشه بندی در داده کاوی — معرفی ۶ نوع خوشه بندی پر کاربرد

مقدمه

در علوم کامپیوتر برای جداسازی داده‌های دارای خصوصیت‌های یکسان در یک گروه یا دسته می‌توان از خوشه‌بندی استفاده کرد. در واقع خوشه بندی (Clustering) فرآیندی برای یافتن گروه‌های مشابه از اشیاء برای تشکیل دادن خوشه‌ها است. خوشه بندی یک الگوریتم مبتنی بر یادگیری ماشین (Machine Learning) می‌باشد که بر روی داده‌های بدون برچسب (unlable) عمل می‌کند.

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

خوشه بندی (Clustering) چیست؟

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

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

از طرفی چون خوشه بندی به صورت الگوریتم‌های یادگیریِ بدون ناظر (unsupervised learning) و بدون برچسب گذاری است به همین دلیل خوشه بندی، تقسیم داده‌ها را با استفاده الگوی ذاتی داده‌ها انجام می‌دهد.

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

• پاورپوینت خوشه بندی در داده کاوی — کلیک کنید.

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

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

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

مفهوم خوشه بندی با مثال

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

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

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

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

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

در راستای همین موضوع می‌توانید مقاله ترجمه شده‌ای را در مجموعه پی استور مطالعه کنید. فایل موردنظر در لینک زیر قرار داده شده است.

• خوشه بندی طیفی با شبکه های عصبی گرافی برای اجتماع گراف ها — کلیک کنید.

انواع خوشه بندی در داده کاوی

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

انواع مختلف الگوریتم های خوشه بندی به شرح زیر می‌باشد:

• خوشه‌بندی سلسله مراتبی (Hierarchical Clustering) یا خوشه بندی تودرتو
• خوشه‌بندی تفکیکی (Partitional Clustering) یا خوشه بندی غیر تودرتو
• خوشه‌بندی برمبنای چگالی (Density-Bases Clustering)
• خوشه بندی انحصاری (Exclusive)
• خوشه بندی همپوشانی (Overlapping)
• خوشه بندی فازی (Fuzzy)

۱- خوشه بندی سلسله مراتبی (Hierarchical Clustering) یا خوشه بندی تودرتو

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

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

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

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

• خوشه بندی تجمعی (agglomerative): روش تجمعی یک روش “پایین به بالا” می‌باشد یعنی در ابتدا هر نمونه به تنهایی یک خوشه نامیده می‌شود سپس همین نمونه یک سطح به بالاتر می‌رود و در مرحله بعد به نمونه دیگر می‌چسبد تا خوشه‌های بزرگتر را ایجاد کنند و در نهایت نمونه‌ها باهم یک خوشه بزرگتر را درست می‌کنند.
• به عبارت دیگر دو خوشه کنار هم با یکدیگر تجمیع می شود و خوشه جدید را درست می‌کند و همین روند در سطح‌های بالا تکرار می‌شود. شکل زیر یک مثال از الگوریتم خوشه بندی سلسله مراتبی تجمعی می‌باشد.

• خوشه بندی تجزیه‌ای (partitioning): برعکس روش تجمعی رویکرد این دسته “بالا به پایین” می‌باشد: با شروع از بالا، در هر سطح یک خوشه به خوشه‌های کوچکتری تجزیه می‌شود که در سطح پایین‌تر قرار می‌گیرند. یعنی ابتدا تمامیِ نمونه‌ها با هم یک خوشه‌ی بزرگ در نظر گرفته می‌شوند و بعد در هر مرحله به خوشه‌های کوچک‌تر تقسیم می‌شوند تا جایی که هر نمونه یک خوشه باشد. شکل زیر یک مثال از الگوریتم خوشه بندی سلسله مراتبی تجزیه‌ای می‌باشد.

۲- خوشه بندی تفکیکی (Partitional Clustering) یا خوشه بندی غیر تودرتو

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

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

الگوریتم‌های خوشه بندی تفکیکی زیادی وجود دارند که تحت روش خوشه بندی تفکیکی قرار می‎‌گیرند، برخی از محبوب‌ترین آنها عبارتند از K-Mean, PAM(K-Mediods), CLARA algorithm (Clustering Large Applications) و غیره. شکل زیر یک مثال از خوشه بندی تفکیکی را نشان می‌دهد.

۳- خوشه‌بندی مبتنی بر چگالی (Density-Bases Clustering)

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

خوشه‌بندی مبتنی بر چگالی به روش‌های یادگیری بدون نظارت اشاره می‌کند که گروه‌ها/خوشه‌های متمایز را در داده‌ها شناسایی می‌کنند، این نوع خوشه‌بندی ذاتاً برای فضای پیوسته تعریف شده است بر اساس این ایده، خوشه‌ها در یک فضای داده که دارای چگالی بالایی هستند (تراکم داده زیاد) از نقاط دارای چگالی کمتر (تراکم داده کمتر) از هم جدا شده اند.

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

۴- خوشه بندی انحصاری (Exclusive)

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

۵- خوشه بندی غیر انحصاری یا خوشه بندی همپوشانی (Overlapping)

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

خوشه‌بندی غیر انحصاری نیز معمولاً در صورتی استفاده می‌شود که یک شی «بین» دو یا بیشتر از دو خوشه باشد و به طور بارز می‌تواند به هر یک از این خوشه‌ها اختصاص داده شود. شکل زیر مثالی از این نوع خوشه بندی را مشخص می‌کند.

۶- خوشه بندی فازی (Fuzzy)

در خوشه بندی فازی، هر شی متعلق به هر خوشه با وزن عضویت بین ۰ تا ۱ می‌باشد. به عبارت دیگر، خوشه‌ها به عنوان مجموعه‌های فازی در نظر گرفته می‌شوند. از نظر ریاضی، مجموعه فازی به مجموعه‌ای گفته می‌شود که در آن یک شی با هر مجموعه‌ای, با وزنی که مابین ۰ تا ۱ متغیر است تعریف می‌شود. در خوشه بندی فازی، معمولاً محدودیت اضافی را تعیین می‌کنیم و مجموع وزن‌های هر شی باید برابر با ۱ باشد.

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

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

• پاورپوینت انواع خوشه بندی در داده کاوی ( داده‏ های جریانی ) — کلیک کنید.

سخن آخر در مورد انواع خوشه بندی در داده کاوی

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

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

خوشه بندی در شبکه های حسگر بی سیم – مدیریت توپولوژی بر اساس روش های خوشه بندی

خوشه بندی در شبکه های حسگر بی سیم – مدیریت توپولوژی بر اساس روش های خوشه بندی

کلیک کنید