خوشه بندی با الگوریتم خوشه بندی birch

خوشه بندی با الگوریتم خوشه بندی birch ، در این پروژه قصد داریم با استفاده از الگوریتم ‌های خوشه بندی سلسله مراتبی (الگوریتم خوشه بندی Birch برای خوشه بندی استفاده شده است) ، عمل خوشه بندی کلاسترینگ (Clustering) را انجام دهیم.لازم به ذکر است برای پیاده سازی الگوریتم مذکور از نرم‌افزار متلب استفاده شده است. و نیز از برنامه نویسی شی گرایی (استفاده از کلاس‎ها) بهره بردیم.

خوشه بندی با الگوریتم خوشه بندی birch

خوشه بندی

خوشه بندی یا کلاسترینگ (Clustering) یکی از شاخه های یادگیری بدون نظارت می باشد و فرآیند خودکاری است که در طی آن ، نمونه ها به دسته هایی که اعضای آن مشابه یکدیگر می با­شند تقسیم می شوند که به این دسته ها خوشه[Cluster] گفته می­شود. بنابراین خوشه مجموعه ای از اشیاء می باشد که در آن اشیاء با یکدیگر مشابه بوده و با اشیاء موجود در خوشه های دیگر غیر مشابه می باشند. برای مشابه بودن می توان معیارهای مختلفی را در نظر گرفت مثلا می توان معیار فاصله را برای خوشه بندی یا کلاسترینگ مورد استفاده قرار داد و اشیائی را که به یکدیگر نزدیکتر هستند را بعنوان یک خوشه در نظر گرفت که به این نوع خوشه بندی، خوشه بندی مبتنی بر فاصله [Distance-based Clustering] نیز گفته می شود. بعنوان مثال در شکل زیر نمونه های ورودی در سمت چپ به چهار خوشه مشابه شکل سمت راست تقسیم می شوند. در این مثال هر یک از نمونه های ورودی به یکی از خوشه ها تعلق دارد و نمونه ای وجود ندارد که متعلق به بیش از یک خوشه باشد.

خوشه بندی با الگوریتم کلاسترینگ birch

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

خوشه بندی با الگوریتم خوشه بندی birch

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

خوشه بندی با طبقه بندی [Classification] متفاوت است. در طبقه بندی نمونه های ورودی برچسب گذاری شده اند ولی در خوشه بندی نمونه های ورودی دارای بر چسب اولیه نمی باشند و در واقع با استفاده از روشهای خوشه بندی است که داده های مشابه مشخص و بطور ضمنی برچسب گذاری می شوند. در واقع می توان قبل از عملیات طبقه بندی داده ها یک خوشه بندی روی نمونه ها انجام داد و سپس مراکز خوشه های حاصل را محاسبه کرد و یک بر چسب به مراکز خوشه ها نسبت داد و سپس عملیات طبقه بندی را برای نمونه های ورودی جدید انجام داد.

هدف از خوشه بندی:

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

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

با داشتن N آیتم که قصد کلاستر بندی آنها را داریم و یک ماتریس فاصله N*N ، فرآیند کلی کلاستربندی سلسله مراتبی به صورت زیر است :

۱ ) هر آیتم را در یک کلاستر قرار می دهیم به طوری که وقتی N آیتم داریم ، N کلاستر خواهیم داشت . فواصل بین کلاسترها را همان فواصل بین آیتم ها قرار دهید.

۲ ) کلاسترهایی که خیلی به همدیگر نزدیک هستند را در یک کلاستر ادغام می کنیم پس اکنون یک کلاستر کمتر داریم.

۳ ) فاصله بین کلاستر جدید و کلاسترهای قدیمی را محاسبه کنید .

۴ ) گام های ۲ و ۳ را آنقدر تکرار کنید که تمام آیتم ها در کلاسترهای با سایز N قرار گیرد .

گام ۳ را می توان به روش های مختلفی انجام داد . سه روش وجود دارد :

• Single linkage
• Complete linkage
• Average linkage

در کلاسترینگ Single linkage ( که connectedness یا روش minimum هم نامیده می شود ) فاصله بین یک کلاستر و کلاستر دیگر برابر است با کوتاهترین فاصله هر عضو از یک کلاستر با هر عضو از کلاستر دیگر .

در کلاسترینگ complete linkage ( که diameter یا روش maximum هم نامیده می شود ) فاصله یک کلاستر با کلاستر دیگر مساوی بیشترین فاصله از هر عضوی از یک کلاستر با عضو دیگری از کلاستر دیگر است .

در کلاسترینگ average linkage فاصله بین یک کلاستر و کلاستر دیگر مساوی فاصله میانگین از هر عضوی از یک کلاستر با هر عضوی از کلاستر دیگری است .

روش های کلاسترینگ مبتنی بر سلسله مراتب

• الگوریتم خوشه بندی DIANA
• الگوریتم خوشه بندی AGNES
• الگوریتم خوشه بندی Chameleon
• الگوریتم خوشه بندی birch

الگوریتم خوشه بندی birch

در این بخش یک الگوریتم خوشه بندی birch را که پایگاه داده های خیلی بزرگ را اداره می کند توصیف می کنیم . طراحی الگوریتم خوشه بندی birch دو فرض زیر را بازتاب می کند :

• تعداد رکوردها ذاتا خیلی زیاد است و بنابراین ما می خواهیم تنها یک جستجو ( scan ) روی پایگاه داده داشته باشیم .
• مقدار حافظه اصلی محدودی در اختیار داریم .

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

پارامتر دوم Є آستانه اولیه برای شعاع کلاستر است . مقدار Є حد بالایی روی شعاع هر کلاستری است و تعداد کلاسترهایی که الگوریتم کشف می کند را کنترل می کند .

اگر Є کوچک است ، تعداد زیادی کلاستر کوچک کشف می کنیم .اگر Є بزرگ است ، تعداد کمی کلاستر کشف می کنیم که هر کدام نسبتا بزرگ هستند .می گوییم هر کلاستری متراکم  ( Compact ) است اگر شعاعش کوچکتر از Є باشد.

الگوریتم کلاسترینگ birch کامل تعادلی در درخت حافظه استفاده می کند که ساختار آن مشابه درخت B+ است تا خیلی سریع نزدیک ترین مرکز کلاستر را برای یک رکورد جدید تعیین کند.

مجموعه داده

مجموعه داده ای که برای انجام این پروژه مورد استفاده قرار گرفته است Electricity Board Hourly Reading نام دارد و شامل ۵ ویژگی ( بعد ) و تقریبا ۴۵٫۰۰۰ رکورد می باشد . لازم به ذکر است که ؛ با توجه به اینکه فرمت داده به صورت arff بوده و مناسب استفاده در نرم افزار weka ، و برای اینکه در متلب مورد استفاده قرار گیرد ابتدا، مجموعه داده را در weka فراخوانی کرده، سپس با فرمت csv که قابل بارگزاری در متلب است، ذخیره کرده و در نهایت به فرم قابل استفاده به متلب تبدیل کردیم.

نکات مربوط به پیاده سازی

این پروژه مربوط به مبحث داده کاوی می باشد و در نرم افزار متلب پیاده سازی شده است.

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

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

کارشناسان وب سایت MATLABDL قادر به انجام پروژه در زمینه های مشابه (پروژه های داده کاوی و…) نیز می باشند.

قیمت پروژه : ۷۴۰۰۰ تومان

حجم : ۱٫۷۴ مگابایت
توضیحات : پیاده سازی در نرم افزار متلب انجام شده است.
منبع : مطلب دی ال
رمز فایل : www.matlabdl.com