خوشه­ بندی  

خوشه­بندی به عنوان یکی از فعالیت­های داده ­کاوی میباشد و به گروه­بندی کردن تراکنش­ها و مشاهدات یا حالت­ها درکلاس­های مشابه می پردازد. همچنین یک خوشه مجموعه ­ای از رکوردها است که به هم شبیه می باشند و از رکوردهای بیرون خوشه تفاوت دارند. در خوشه­بندی متغیر هدف وجود ندارد و به طبقه ­بندی تخمین و پیشگوئی مقدار متغیر هدف نمی پردازد (لاروس، ۲۰۰۵).

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

شکل (۲-۲) : خوشه بندی وسایل نقلیه

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

۱٫۳٫۲  هدف از خوشه­بندی

هدف خوشه­بندی یافتن خوشه­های مشابه از اشیاء در بین نمونه­های ورودی می باشد اما چگونه می توان گفت که یک خوشه­بندی مناسب است و دیگری مناسب نیست؟ می توان نشان داد که هیچ معیار مطلقی برای بهترین خوشه بندی وجود ندارد بلکه این بستگی به مساله و نظر کاربر دارد که باید تصمیم بگیرد که آیا نمونه­ها بدرستی خوشه­بندی شده ­اند یا خیر. با این حال معیارهای مختلفی برای خوب بودن یک خوش­ بندی ارائه شده است که می تواند کاربر را برای رسیدن به یک خوشه­بندی مناسب راهنمایی کند که در بخش­های بعدی چند نمونه از این معیارها آورده شده است. یکی از مسایل مهم در خوشه بندی انتخاب تعداد خوشه ­ها می باشد. در بعضی از الگوریتم­ها تعداد خوشه ­ها از قبل مشخص شده است و در بعضی دیگر خود الگوریتم تصمیم می گیرد که داده­ ها به چند خوشه تقسیم شوند (قاسمی و خانگلدی، ۱۳۸۸).

۲٫۳٫۲ انواع خوشه­بندی

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

روش­های خوشه­بندی متفاوتی وجود دارد که برای تمایز آن­ها از یکدیگر از پنج خصوصیت استفاده می شود. ابتدا به تعریف این خصوصیات پرداخته سپس روش­های خوشه­بندی را بر اساس آن­ها معرفی می­کنیم.

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

[۱] . Larose

[۲] . Exclusive versus Non-exclusive

[۳] . Recrusive sequence versus Simultaneous