فهرست
مقدمه……………………………………………………………………………………………………………………………………………………………………………………5
خوشه بندی چیست؟…………………………………………………………………………………………………………………………………………………………….6
هدف از خوشه بندی چیست؟……………………………………………………………………………………………………………………………………………….7
خوشه بندی در مقابل طبقه بندی………………………………………………………………………………………………………………………………………..8
یادگیری با نظارت در مقابل یادگیری بدون نظارت……………………………………………………………………………………………………………….9
کاربردها……………………………………………………………………………………………………………………………………………………………………………….10
مسائل درگیر با روش های خوشه بندی موجود……………………………………………………………………………………………………………………11
خوشه بندی در مقابل چندی سازی برداری………………………………………………………………………………………………………………………..11
روش های خوشه بندی………………………………………………………………………………………………………………………………………………………….12
روش خوشه بندی(K-Means یا C-Means)………………………………………………………………………………………………………………..13
مثالی برای خوشه بندی K-Means……………………………………………………………………………………………………………………………….14
مشکلات روش خوشه بندی K-Means………………………………………………………………………………………………………………………….18
الگوریتم خوشه بندی LBG………………………………………………………………………………………………………………………………………………19
خوشه بندی فازی چیست؟………………………………………………………………………………………………………………………………………………..20
روشهای خوشه بندی سلسله مراتبی…………………………………………………………………………………………………………………………………..32
خوشه بندی با روش Single-Link………………………………………………………………………………………………………………………………….25
خوشه بندی با روش Link Complete_…………………………………………………………………………………………………………….29
خوشه بندی با روش Average-Link…………………………………………………………………………………………………………………………….34
خوشه بندی بر اساس چگالی……………………………………………………………………………………………………………………………38
الگوریتم خوشه بندی براساس چگالی……………………………………………………………………………………………………………………………..42
مثالی از الگوریتم خوشه بندی براساس چگالی ………………………………………………………………………………………………………………..43
الگوریتم سلسله مراتبی خوشه بندی براساس چگالی………………………………………………………………………………………………………..44
معیارهای کارایی………………………………………………………………………………………………………. 46
خلاصه و نتیجه گیری…………………………………………………………………………………………………………………………………………………………54
مراجع: 55
مقدمه
در این پروژه روش های خوشه بندی مورد برسی قرار می گیرد هدف از خوشه بندی یافتن خوشه های مشابه از اشیاء در بین نمونه های ورودی می باشد تفاوت های خوشه بندی وطبقه بندی مورد مطالعه قرار میگیرد همچنین خوشه بندی در مقابل چندی سازی برداری قرار دارد در خوشه بندی نوعی سازمان داریم ولی در روشهای ارتباطی از چندی سازی استفاده میشود ،در خوشه بندی از روشهای فازی استفاده می شود( kmeans,cmens)
خوشه بندی به انتخاب اولیه خوشه ها بستگی دارد واین باعث می شود که نتایج خوشه بندی در تکرارهای مختلف از الگوریتم متفاوت شود که این در بسیاری از کاربردها قابل استفاده نیست ،برای رفع مشکل روش فازی cmens از الگوریتم LBG استفاده می شود.
خوشه بندی1 چیست؟
خوشه بندی یکی از شاخه های یادگیری بدون نظارت می باشد و فرآیند خودکاری است که در طی آن، نمونه ها به دسته هایی که اعضای آن مشابه یکدیگر می باشند تقسیم می شوند که به این دسته ها خوشه2 گفته میشود. بنابراین خوشه مجموعه ای از اشیاء می باشد که در آن اشیاء با یکدیگر مشابه بوده و با اشیاء موجود در خوشه های دیگر غیر مشابه می باشند. برای مشابه بودن می توان معیارهای مختلفی را در نظر گرفت مثلا می توان معیار فاصله را برای خوشه بندی مورد استفاده قرار داد و اشیائی را که به یکدیگر نزدیکتر هستند را بعنوان یک خوشه در نظر گرفت که به این نوع خوشه بندی، خوشه بندی مبتنی بر فاصله3 نیز گفته می شود. بعنوان مثال در شکل 1 نمونه های ورودی در سمت چپ به چهار خوشه مشابه شکل سمت راست تقسیم می شوند. در این مثال هر یک از نمونه های ورودی به یکی از خوشه ها تعلق دارد و نمونه ای وجود ندارد که متعلق به بیش از یک خوشه باشد.
شکل 1: خوشه بندی نمونه های ورودی
بعنوان یک مشال دیگر شکل 2 را در نظر بگیرید در این شکل هر یک از دایره های کوچک یک وسیله نقلیه (شیء) را نشان می دهد که با ویژگی های وزن و حداکثر سرعت مشخص شده اند. هر یک از بیضی ها یک خوشه می باشد و عبارت کنار هر بیضی برچسب آن خوشه را نشان می دهد. کل دستگاه مختصات که نمونه ها در آن نشان داده شده اند را فضای ویژگی می گویند.
شکل 2: خوشه بندی وسایل نقلیه
همانطور که در شکل می بینید وسایل نقلیه به سه خوشه تقسیم شده اند. برای هر یک از این خوشه ها می توان یک نماینده در نظر گرفت مثلا می توان میانگین وسایل نقلیه باری را محاسبه کرد و بعنوان نماینده خوشه وسایل نقلیه باری معرفی نمود. در واقع الگوریتمهای خوشه بندی اغلب بدین گونه اند که یک سری نماینده اولیه برای نمونه های ورودی در نظر گرفته می شود و سپس از روی میزان تشابه نمونه ها با این نماینده های مشخص می شود که نمونه به کدام خوشه تعلق دارد و بعد از این مرحله نماینده های جدید برای هر خوشه محاسبه می شود و دوباره نمونه ها با این نماینده ها مقایسه می شوند تا مشخص شود که به کدام خوشه تعلق دارند و این کار آنقدر تکرار می شود تا زمانیکه نماینده های خوشه ها تغییری نکنند.
خوشه بندی با طبقه بندی4 متفاوت است. در طبقه بندی نمونه های ورودی برچسب گذاری شده اند ولی در خوشه بندی نمونه های ورودی دارای بر چسب اولیه نمی باشند و در واقع با استفاده از روشهای خوشه بندی است که داده های مشابه مشخص و بطور ضمنی برچسب گذاری می شوند. در واقع می توان قبل از عملیات طبقه بندی داده ها یک خوشه بندی روی نمونه ها انجام داد و سپس مراکز خوشه های حاصل را محاسبه کرد و یک بر چسب به مراکز خوشه ها نسبت داد و سپس عملیات طبقه بندی را برای نمونه های ورودی جدید انجام داد.
هدف از خوشه بندی چیست؟
هدف خوشه بندی یافتن خوشه های مشابه از اشیاء در بین نمونه های ورودی می باشد اما چگونه می توان گفت که یک خوشه بندی مناسب است و دیگری مناسب نیست؟ می توان نشان داد که هیچ معیار مطلقی برای بهترین خوشه بندی وجود ندارد بلکه این بستگی به مساله و نظر کاربر دارد که باید تصمیم بگیرد که آیا نمونه ها بدرستی خوشه بندی شده اند یا خیر. با این حال معیار های مختلفی برای خوب بودن یک خوشه بندی ارائه شده است که می تواند کاربر را برای رسیدن به یک خوشه بندی مناسب راهنمایی کند که در بخشهای بعدی چند نمونه از این معیارها آورده شده است. یکی از مسایل مهم در خوشه بندی انتخاب تعداد خوشه ها می باشد. در بعضی از الگوریتم ها تعداد خوشه ها از قبل مشخص شده است و در بعضی دیگر خود الگوریتم تصمیم می گیرد که داده ها به چند خوشه تقسیم شوند.
خوشه بندی در مقابل طبقه بندی
در طبقه بندی هر داده به یک طبقه (کلاس) از پیشین مشخص شده تخصیص می یابد ولی در خوشه بندی هیچ اطلاعی از کلاسهای موجود درون داده ها وجود ندارد و به عبارتی خود خوشه ها نیز از داده ها استخراج می شوند. در شکل زیر تفاوت بین خوشه بندی و طبقه بندی بهتر نشان داده شده است.
a
b
در طبقه بندی با استفاده یک سری اطلاعات اولیه داده ها به دسته های معلومی نسبت داده می شوند. در خوشه بندی داده ها با توجه به الگوریتم انتخاب شده به خوشه هایی نسبت داده می شوند
یادگیری با نظارت در مقابل یادگیری بدون نظارت
در یادگیری با نظارت از ابتدا دسته ها مشخص هستند و هر یک از داده های آموزشی به دسته ای خاص نسبت داده شده است و اصطلاحا گفته می شود ناظری وجود دارد که در هنگام آموزش اطلاعاتی علاوه بر داده های آموزش در اختیار یادگیرنده (Learner) قرار می دهد. ولی در یادگیری بدون نظارت هیچ اطلاعاتی بجز داده های آموزشی در اختیار یادگیرنده قرار ندارد و این یادگیرنده است که بایستی در داده ها به دنبال ساختاری خاص بگردد.
کاربردها
از آنجا که خوشه بندی یک روش یادگیری بدون نظارت محسوب می گردد، در موارد بسیاری می تواند کاربرد داشته باشد.
· در بازاریابی: دسته بندی مشتری ها به دسته هایی بر حسب رفتارها و نیازهای انها از طریق مجموعه زیادی از ویژگی ها و اخرین خرید های انها.
· زیست شناسی: دسته بندی حیوانات و گیاهان از روی ویژگی های انها
· کتابداری : دسته بندی کتابها
· نقشه برداری شهری: دسته بندی خانه ها بر اساس نوع و موقعیت جغرافیایی انها.
· مطالعات زلزله نگاری:تشخیص مناطق حادثه خیز بر اساس مشاهدات قبلی.
· وب: دسته بندی اسناد، دسته بندی مشتریان مراجعه کننده به سایتها و ….
· داده کاوی: کشف اطلاعات و ساختار جدید از داده های موجود
· در تشخیص گفتار:در ساخت کتابِ کد از بردارهای ویژگی، در تقسیم کردن گفتار بر حسب گویندگان ان و یا فشرده سازی گفتار
· در تقسیم بندی تصاویر:تقسیم بندی تصاویر پزشکی و یا ماهواره ای
· بیمه:تشخیص افراد متقلب، تشخیص افرادی که بیمه موتور دارند و بیشترین میزان درخواست از بیمه را نیز در سال مشخصی داشته اند.
مسائل درگیر با روش های خوشه بندی موجود
متاسفانه چندین مسئاله در خصوص روش های خوشه بندی مطرح است که هنوز به شکل کامل پاسخ داده نشده اند. و همچنان تلاش های بسیاری به منظور حل آنها انجام می گیرد.
· روش های خوشه بندی قادر نیستند تمامی نیازهای مسائل را به طور هم زمان برآورده کنند.
· به دلیل پیچیدگی محاسباتی زیاد در برخورد با مجموعه داده های بزرگ با تعداد داده زیاد و تعداد ویژگی های زیاد برای هر داده عملی نیستند.
· به دلیل وابستگی شدید به تعریف معیار شباهت بین داده ها در مسائلی که تعریف معیار شباهت مشکل باشد نتایج مطلوبی تولید نمی کنند.(در داده ها با تعداد ویژگی زیاد(
· برای نتایج آنها می توان تفسیرهای مختلفی بیان کرد.
خوشه بندی در مقابل چندی سازی برداری
همان گونه که بحث شد، خوشه بندی نوعی سازماندهی داده ها است، بر اساس شباهتی که بین آنها تعریف می شود به گونه ای که شباهت بین داده هایی که درون یک خوشه قرار می گیرند، نسبت به داده هایی که درون خوشه های متفاوت قرارمی گیرند،بیشترباشد.
در کاربردهای ارتباطی و فشرده سازی داده ها از روشهایی به نام چندی سازی برداری استفاده می شود که از بعضی جنبه ها می توان آنها را معادل خوشه بندی در نظر گرفت. در چندی سازی برداری نیز داده ها بر اساس میزان شباهت بین آنها به دسته هایی تقسیم می شوند و هر دسته بوسیله یک بردار که به آن کلمه کد (CodeWord) گفته می شود جایگزین می گردد. به مجموعه این کلماتِ کد اصطلاحا کتابِ کد(CodeBook) گفته می شود.
دربعضی از بخث های علمی بین خوشه بندی و چندی سازی برداری تفاوتهایی قائل می شوند. زیرا خوشه بندی را یک رهیافت بدون نظارت برای تحلیل داده ها در نظر می گیرند ولی چندی سازی برداری را روشی برای کشف خوشه ها نمی شناسند بلکه آن را راهی برای نمایش داده ها با تعداد عناصر کمتر به گونه ای که اطلاعات از دست رفته حداقل شود، می شناسند. علی رغم تفاوت بیان شده می توان روشهای بکار رفته در هر یک آنها را در دیگر نیز بکار برد در اینجا بین خوشه بندی و چندی سازی برداری تفاوتی قائل نمی شویم.
روش های خوشه بندی
روش های خوشه بندی را می توان از چندین جنبه تقسیم بندی کرد:
-1 خوشه بندی انحصاری (Exclusive or Hard Clustering) و خوشه بندی با هم پوشی (Overlapping or Soft Clustering)
در روش خوشه بندی انحصاری پس از خوشه بندی هر داده دقیقا به یک خوشه تعلق می گیرد مانند روش خوشه بندی
K-Means. ولی در خوشه بندی با همپوشی پس از خوشه بندی به هر داده یک درجه تعلق بازاء هر خوشه نسبت داده می شود. به عبارتی یک داده می تواند با نسبتهای متفاوتی به چندین خوشه تعلق داشته باشد. نمونه ای از آن خوشه بندی فازی است .
-2 خوشه بندی سلسله مراتبی (Hierarchical) و خوشه بندی مسطح(Flat)
در روش خوشه بندی سلسله مراتبی، به خوشه های نهایی بر اساس میزان عمومیت آنها ساختاری سلسله مراتبی نسبت داده می شود. مانند روش Single Link. ولی در خوشه بندی مسطح تمامی خوشه های نهایی دارای یک میزان عمومیت هستند مانند K-Means. به ساختار سلسله مراتبی حاصل از روشهای خوشه بندی سلسله مراتبی دندوگرام (Dendogram)گفته می شود.
با توجه با اینکه روش های خوشه بندی سلسله مراتبی اطلاعات بیشتر و دقیق تری تولید می کنند برای تحلیل داده های با جزئیات پیشنهاد می شوند ولی از طرفی چون پیچیدگی محاسباتی بالایی دارند برای مجموعه داده های بزرگ روش های خوشه بندی مسطح پیشنهاد می شوند.
روش خوشه بندی(K-Means یا C-Means)
این روش علی رغم سادگی آن یک روش پایه برای بسیاری از روش های خوشه بندی دیگر (مانند خوشه بندی فازی) محسوب می شود. این روش روشی انحصاری و مسطح محسوب می شود.برای این الگوریتم شکلهای مختلفی بیان شده است. ولی همه آنها دارای روالی تکراری هستند که برای تعدادی ثابت از خوشه ها سعی در تخمین موارد زیر دارند:
· بدست آوردن نقاطی به عنوان مراکز خوشه ها این نقاط در واقع همان میانگین نقاط متعلق به هر خوشه هستند.
· نسبت دادن هر نمونه داده به یک خوشه که آن داده کمترین فاصله تا مرکز آن خوشه را دارا باشد.
در نوع ساده ای از این روش ابتدا به تعداد خوشه های مورد نیاز نقاطی به صورت تصادفی انتخاب می شود. سپس در داده ها با توجه با میزان نزدیکی (شباهت) به یکی از این خوشه ها نسبت داده می شوند و بدین ترتیب خوشه های جدیدی حاصل می شود. با تکرار همین روال می توان در هر تکرار با میانگین گیری از داده ها مراکز جدیدی برای آنها محاسبه کرد و مجدادا داده ها را به خوشه های جدید نسبت داد. این روند تا زمانی ادامه پیدا می کند که دیگر تغییری در داده ها حاصل نشود. تابع زیر به عنوان تابع هدف مطرح است.
که ║║ معیار فاصله بین نقاط و cj مرکز خوشه j ام است.
الگوریتم زیر الگوریتم پایه برای این روش محسوب می شود:
در ابتدا K نقطه به عنوان مراکز خوشه ها انتخاب می شوند.
هر نمونه داده به خوشه ای که مرکز آن خوشه کمترین فاصله تا آن داده را داراست، نسبت داده می شود.
پس تعلق تمام داده ها به یکی از خوشه ها برای هر خوشه یک نقطه جدید به عنوان مرکز محاسبه می شود. (میانگین نقاط متعلق به هر خوشه)
مراحل 2 و 3 تکرار می شوند تا زمانی که دیگر هیچ تغییری در مراکز خوشه ها حاصل نشود.
مثالی برای روش خوشه بندی K-Means:
در شکل زیر نحوه اعمال این الگوریتم خوشه بندی روی یک مجموعه داده که شامل دو گروه داده است نشان داده شده است. یک گروه از داده ها با ستاره و گروه دیگر با دایره مشخص شده اند(a). در مرحله اول نقطه ای به عنوان مرکز خوشه ها انتخاب شده اند که با رنگ قرمز نشان داده شده اند(b). سپس در مرحله دوم هر یک از نمونه داده ها به یکی از این دو خوشه نسبت داده شده است و برای هر دسته جدید مرکزی جدید محاسبه شده سات که در قسمت(c)نشان داده شده اند. این روال تا رسیدن به نقاطی که دیگر تغییر نمی کنند، ادامه پیدا کرده است.
a))
(b)
(c)
(d)
(e)
(f)
مشکلات روش خوشه بندی K-Means
علی رغم اینکه خاتمه پذیری الگوریتم بالا تضمین شده است ولی جواب نهایی آن واحد نبوده و همواره جوابی بهینه نمی باشد. به طور کلی روش ساده بالا دارای مشکلات زیر است.
* جواب نهایی به انتخاب خوشه های اولیه وابستگی دارد.
* روالی مشخص برای محاسبه اولیه مراکز خوشه ها وجود ندارد.
* اگر در تکراری از الگوریتم تعداد داده های متعلق به خوشه ای صفر شد راهی برای تغییر و بهبود ادامه روش وجود ندارد.
* در این روش فرض شده است که تعداد خوشه ها از ابتدا مشخص است. اما معمولا در کاربردهای زیادی تعداد خوشه ها مشخص نمی باشد.
الگوریتم خوشه بندی LBG
همان گونه که ذکر شد الگوریتم خوشه بندی K-Means به انتخاب اولیه خوشه ها بستگی دارد و این باعث می شود که نتایج خوشه بندی در تکرارهای مختلف از الگوریتم متفاوت شود که این در بسیاری از کاربردها قابل نیست. برای رفع این مشکل الگوریتم خوشه بندی LBG پیشنهاد شد که قادر است به مقدار قابل قبولی بر این مشکل غلبه کند.
در این روش ابتدا الگوریتم تمام داده ها را به صورت یک خوشه در نظر می گیرد و سپس برای این خوشه یک بردار مرکز محاسبه می کند.(اجرای الگوریتم K-Means با تعداد خوشه 1K=). سپس این بردار را به 2 بردار می شکند و داده ها را با توجه به این دو بردار خوشه بندی می کند (اجرای الگوریتم K-Means با تعداد خوشه K=2 که مراکز اولیه خوشه ها همان دو بردار هستند). در مرحله بعد این دو نقطه به چهار نقطه شکسته می شوند و الگوریتم ادامه پیدا می کند تا تعداد خوشه مورد نظر تولید شوند.
الگوریتم زیر را می توان برای این روش خوشه بندی در نظر گرفت:
1. شروع: مقدار M(تعداد خوشه ها) با عدد 1 مقدار دهی اولیه می شود. سپس برای تمام داده ها بردار مرکز محاسبه می شود.
2.شکست: هر یک از M بردار مرکز به 2 بردار جدید شکسته می شوند تا 2M بردار مرکز تولید شود. هر بردار جدید بایستی درون همان خوشه قرار داشته باشد و به اندازه کافی از هم دور باشند.
3. K-Means : با اجرای الگوریتم K-Means با تعداد خوشه 2M و مراکز اولیه خوشه های محاسبه شده در مرحله ii خوشه های جدیدی با مراکز جدید تولید می شود.
4. شرط خاتمه: در صورتی که M برابر تعداد خوشه مورد نظر الگوریتم LBG بود الگوریتم خاتمه می یابد و در غیر این صورت به مرحله ii رفته و الگوریتم تکرار می شود.
خوشه بندی فازی چیست؟
برای درک بهترخوشه بندی فازی و الگوریتمهای مختلف آن لازم است تا ابتدا با مفهوم مجموعه های فازی و تفاوت آنها با مجموعه های کلاسیک آشنا شویم. در مجموعه های کلاسیک یک عضو از مجموعه مرجع یا عضوی از مجموعه A است یا عضو مجموعه A نیست. مثلا مجموعه مرجع اعداد حقیقی را در نظر بگیرید. عدد 2.5 عضو مجموعه اعداد صحیح نمی باشد حال آنکه عدد 2 عضو این مجموعه است. به زبان دیگر تعلق عدد 2.5 به مجموعه اعداد صحیح 0 است و تعلق عدد 2 به این مجموعه 1 است. در واقع می توان برای هر مجموعه یک تابع تعلق تعریف کرد که مقدار این تابع تعلق برای اعضای مجموعه 1 می باشد و برای بقیه 0. در مجموعه های کلاسیک مقدار این تابع تعلق یا 0 است یا 1. حال مجموعه انسان های جوان و پیر را در نظر بگیرید. سوالی که در اینجا مطرح می شود این است که آیا فردی با سن 25 جزء این مجموعه است یا خیر؟ سن 30 چطور؟ 35؟ همانطور که حدس زدید نمی توان بطور قطع و یقین مرزی برای انسان های جوان و پیر در نظر گرفت. دلیل آن هم این است که اگر فرضا 35 جوان محسوب شود 36 نیز می تواند جوان باشد و همینطور 37 و 38 و غیره . در واقع در اینجا با مفهوم عدم قطعیت5 مواجه هستیم. ما خودمان نیز از عدم قطعیت در زندگی روزمره بارها استفاده کرده ایم مثلا هوای سرد، آب داغ و غیره. در واقع تمامی مثالهای بالا مثالهایی از مجموعه های فازی می باشند. تفاوت اصلی مجموعه های فازی و مجموعه های کلاسیک در این است که تابع تعلق مجموعه های فازی دو مقداری نیست (0 یا 1) بلکه می تواند هر مقداری بین 0 تا 1 را اختیار کند. حال مجموعه انسانهای جوان و پیر را در نظر بگیرید اگر 25 سال را سن جوانی در نظر بگیریم می توانیم به 25 تعلق 1 بدهیم و مثلا به 30 تعلق 0.8 و به 35 تعلق 0.75 و به 90 تعلق 0.1 را بدهیم. اگر اعضای یک مجموعه فازی تنها دارای تابع تعلق 0 و 1 باشند این مجموعه فازی یک مجموعه کلاسیک خواهد بود. نکته جالب توجه این است که مثلا سن 50 می تواند با تعلق 0.5 عضو مجموعه جوان باشد و با تعلق 0.5 عضو مجموعه پیر یعنی یک عضو مجموعه مرجع می تواند با درجه های تعلق مختلف عضو مجموعه های فازی تعریف شده روی مجموعه مرجع باشد.
در خوشه بندی کلاسیک هر نمونه ورودی متعلق به یک و فقط یک خوشه می باشد و نمی تواند عضو دو خوشه و یا بیشتر باشد. مثلا در شکل دو هر یک وسایل نقلیه عضو یک خوشه می باشد و نمونه ای عضو دو خوشه نیست و به زبان دیگر خوشه ها همپوشانی ندارند. حال حالتی را در نظر بگیرید که میزان تشابه یک نمونه با دو خوشه و یا بیشتر یکسان باشد در خوشه بندی کلاسیک باید تصمیم گیری شود که این نمونه متعلق به کدام خوشه است. تفاوت اصلی خوشه بندی کلاسیک و خوشه بندی فازی در این است که یک نمونه می تواند متعلق به بیش از یک خوشه باشد. برای روشن شدن مطلب شکل 3 را در نظر بگیرید:
شکل 3: مجموعه داده پروانه ای
اگر نمونه های ورودی مطابق شکل فوق باشند مشخص است که می توان داده ها را به دو خوشه تقسیم کرد اما مشکلی که پیش می آید این است که داده مشخص شده در وسط می تواند عضو هر دو خوشه باشد بنابراین باید تصمیم گرفت که داده مورد نظر متعلق به کدام خوشه است، خوشه سمت راست یا خوشه سمت چپ. اما اگر از خوشه بندی فازی استفاده کنیم داده مورد نظر با تعلق 0.5 عضو خوشه سمت راست و با تعلق مشابه عضو خوشه سمت چپ است. تفاوت دیگر در این است که مثلا نمونه های ورودی در سمت راست شکل 3 می توانند با یک درجه تعلق خیلی کم عضو خوشه سمت چپ نیز باشند که همین موضوع برای نمونه های سمت چپ نیز صادق است.
بعنوان یک مثال دیگر شکل زیر را در نظر بگیرید. در این شکل نمونه هایی که با علامت بعلاوه مشخص شده اند به بیش از یک خوشه تعلق دارند.
خوشه بندی فازی داده
روشهای خوشه بندی سلسله مراتبی
همان گونه که بیان شد، در روش خوشه بندی سلسله مراتبی، به خوشه های نهایی بر اساس میزان عمومیت آنها ساختاری سلسله مراتبی، معمولا به صورت درختی نسبت داده می شود. به ا ین درخت سلسله مراتبی دندوگرام (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 می باشد. در واقع در این روش شباهت بین دو خوشه، کمترین فاصله بین یک عضو از یکی با یک عضو از دیگری است. در شکل زیر این مفهوم بهتر نشان داده شده است.
شباهت بین دو خوشه در روش Single-Link برابر است با کمترین فاصله بین داده های دو خوشه
مثال: در این قسمت سعی شده است تا در مثالی با فرض داشتن 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 نشان داده شده است.
دندوگرام مثال Single-Link
خوشه بندی با روش Complete-Link
این روش همانند Single-Link جزء روشهای خوشه بندی سلسله مراتبی و انحصاری محسوب می شود. به این روش خوشه بندی، تکنیک دورترین همسایه (furthest Neighbour) نیز گفته می شود. در این روش برای محاسبه شباهت بین دو خوشه A و B از معیار زیر استفاده می شود:
که i یک نمونه داده متعلق به خوشه A و j یک نمونه داده متعلق به خوشه B می باشد. در واقع در این روش شباهت بین دو خوشه بیشترین فاصله بین یک عضو از یکی با یک عضو از دیگری است. در شکل زیر این مفهوم بهتر نشان داده شده است.
شباهت بین دو خوشه در روش Complete-Link برابر است با بیشترین فاصله بین داده های دو خوشه.
مثال: در این قسمت سعی شده است تا در مثالی با فرض داشتن 6 نمونه داده و ماتریس فاصله بین آنها که در جدول 6 نشان داده شده است، نحوه اعمال روش خوشه بندی Complete-Link بهتر تشریح شود.
در ابتدا هر داده به عنوان یک خوشه در نظر گرفته می شود و یافتن نزدیکترین خوشه در واقع یافتن کمترین فاصله بین داده های بالا خواهد بود. با توجه به جدول 6 مشخص است که داده های 3 و 5 کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می شود که فاصله آن از سایر خوشه ها برابر است با بیشترین فاصله بین 3 و یا 5 از سایر خوشه ها. نتیجه در جدول 7 نشان داده شده است.
با توجه به جدول 7 مشخص است که داده های 1 و 2 کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می شود که فاصله آن از سایر خوشه ها برابر است با بیشترین فاصله بین 1 و یا 2 از سایر خوشه ها. نتیجه در جدول 8 نشان داده شده است.
با توجه به جدول 8 مشخص است که خوشه های (3 و 5) و 4 کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می شود که فاصله آن از سایر خوشه ها برابر است با بیشترین فاصله بین (3 و 5) و یا 4 از سایر خوشه ها. نتیجه در جدول 9 نشان داده شده است.
با توجه به جدول 9 مشخص است که خوشه های (1 و 2) و 6 کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می شود که فاصله آن از سایر خوشه ها برابر است با بیشترین فاصله بین (1 و 2) و یا 6 از سایر خوشه ها. نتیجه در جدول 10 نشان داده شده است.
در نهایت این دو خو شه حاصل ا هم ترکیب می شوند. نتیجه در دندوگرام شکل 7 نشان داده شده است.
دندوگرام مثال Complete-Link
خوشه بندی با روش Average-Link
این روش همانند Single-Link جزء روشهای خوشه بندی سلسله مراتبی و انحصاری محسوب می شود. از آنجا که هر دو روش خوشه بندی Single-link و Complete-link بشدت به نویز حساس می باشد، این روش که محاسبات بیشتری دارد، پیشنهاد شد. در این روش برای محاسبه شباهت بین دو خوشه A و B از معیار زیر استفاده می شود:
که i یک نمونه داده متعلق به خوشه A و j یک نمونه داده متعلق به خوشه B می باشد. و NA تعداد اعضاء خوشه A و NB تعداد اعضاء خوشه B است. در واقع در این روش، شباهت بین دو خوشه میانگین فاصله بین تمام اعضاء یکی با تمام اعضاء دیگری است. در شکل زیر این مفهوم بهتر نشان داده شده است.
شباهت بین دو خوشه در روش Average-Link برابر است با میانگین فاصله بین داده های دو خوشه
مثال:در این قسمت سعی شده است تا در مثالی با فرض داشتن 6 نمونه داده و ماتریس فاصله بین آنها که در جدول 11 نشان داده شده است، نحوه اعمال روش خوشه بندی Average-Link بهتر تشریح شود.
در ابتدا هر داده به عنوان یک خوشه در نظر گرفته می شود و یافتن نزدیکترین خوشه در واقع یافتن کمترین فاصله بین داده های بالا خواهد بود. با توجه به جدول 11 مشخص است که داده های 3 و 5 کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می شود که فاصله آن از سایر خوشه ها برابر است با میانگین فاصله بین 3 و 5 از سایر خوشه ها. نتیجه در جدول 12 نشان داده شده است.
با توجه به جدول 12 مشخص است که داده های 1 و 2 کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می شود که فاصله آن از سایر خوشه ها برابر است با بیشترین فاصله بین 1 و یا 2 از سایر خوشه ها. نتیجه در جدول 13 نشان داده شده است.
با توجه به جدول 13 مشخص است که خوشه های (3 و 5) و 4 کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می شود که فاصله آن از سایر خوشه ها برابر است با بیشترین فاصله بین (3 و 5) و یا 4 از سایر خوشه ها. نتیجه در جدول 14 نشان داده شده است.
با توجه به جدول 14 مشخص است که خوشه های (1 و 2) و 6 کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشه جدیدی حاصل می شود که فاصله آن از سایر خوشه ها برابر است با بیشترین فاصله بین (1 و 2) و یا 6 از سایر خوشه ها. نتیجه در جدول 15 نشان داده شده است.
در نهایت این دو خو شه حاصل ا هم ترکیب می شوند. نتیجه در دندوگرام زیر نشان داده شده است.
دندوگرام مثال Average-Link
خوشه بندی بر اساس چگالی
این روشهای خوشه بندی بر این اصل استوارند که خوشه ها ، ناحیه هایی از فضای داده با چگالی زیادی هستند که توسط نواحی با چگالی کمتر از همدیگر جدا شده اند. برای پیاده سازی این روشهای خوشه بندی لازم است تا ابتدا اصطلاحاتی تعریف شوند:
چگالی نقاط محلی در نقطه) p (Local Point Density : اگر P را نقطه هسته یک همسایگی و ε شعاع همسایگی برای نقطه P در نظر گرفته شود آنگاه همسایگی به شعاع ε برای نقطه P به صورت زیر تعریف می شود:
به تعداد نقاط قرار گرفته شده درون یک همسایگیِ داده شده چگالی نقاط آن همسایگی گفته می شود.
یک همسایگی برای P دارای چگالی نقاط 5
* در دسترسِ مستقیمِ چگالی (Directly Density-Reachable): داده p را در دسترسِ مستقیمِ چگالیِ q گویند اگر p درون یک همسایگی به شعاع ε با هسته q باشد. در شکل زیر بهتر می توان این مفهوم را درک کرد.
p در دسترسِ مستقیمِ چگالیِ q قرار دارد.
* در دسترسِ چگالی (Density-Reachable): داده p را در دسترسِ چگالیِ q گویند اگر داده ای وجود داشته باشد که هم درون یک همسایگی به شعاع ε با هسته p و هم درون یک همسایگی به شعاع ε با هسته q باشد. در شکل زیر بهتر می توان این مفهوم را درک کرد.
p در دسترسِ چگالیِ q قرار دارد.
* متصلِ چگالی (Density-Connected): داده p را متصلِ چگالیِ q گویند اگر داده ای مانند o وجود داشته باشد که هم در دسترسِ چگالیِ p و هم در دسترسِ چگالیِ q باشد. در شکل زیر بهتر می توان این مفهوم را درک کرد.
p متصلِ چگالیِ q است.
* خوشه مبتنی بر چگالی (Density-Based Cluster): زیر مجموعه ای غیرتهی(S) از مجموعه داده ها (D) که دارای دو شرط زیر باشد:
§ حداکثر: اگر p درون S باشد و q در دسترسِ چگالیِ p باشد آنگاه q نیز متعلق به S باشد.
§ اتصال: هر داده درون S متصلِ چگالیِ سایر داده های درون S باشد.
* خوشه بندی بر اساس چگالی (Density-Based Clustering): خوشه بندی بر اساس چگالی بر روی مجموعه داده D مجموعه ای به صورت {S1, …, Sn, N} است که :
§ S1, …, Sn تمام خوشه های مبتنی چگالیِ درون D است.
§ N=D{ S1, …, Sn } مجموعه نویز خوانده می شود.
خوشه بندی بر اساس چگالی
الگوریتم خوشه بندی براساس چگالی DBSCAN:
در این روش خوشه بندی هر داده متعلق به خوشه C در دسترس چگالی سایر داده های متعلق به آن خوشه است و در دسترس چگالی هیچ داده دیگری قرار ندارد. شبه کد این الگوریتم را زیر مشاهده می کنید.
مثالی از الگوریتم خوشه بندی براساس چگالی DBSCAN:
در شکل زیر سعی شده است تا نحوه اعمال الگوریتم خوشه بندی DBSCAN را بر روی یک مجموعه داده نشان داده شود. همان گونه که مشاهده می شود، این الگوریتم نوانسته است به خوبی داده ها را خوشه بندی کند.
A
B
C
D
E
الگوریتم سلسله مراتبی خوشه بندی براساس چگالی OPTICS
در این روش سعی می شود تا با تکنیکی سلسله مراتبی خوشه های بزرگتری را از ترکیب خوشه ای دارای چگالی زیاد ولی کوچک تر محاسبه کرد. در شکل زیر با یک بار اعمال الگوریتم خوشه بندی DBSCAN خوشه های C1 و C2 حاصل گشته اند که در مرحله دیگری با هم ترکیب شده و خوشه بزرگتر C را ساخته اند. در این روش با افزایش تعداد تکرار مقدار پارامتر ε افزایش می یابد.
در روش سلسله مراتبی خوشه بندی براساس چگالی OPTICS از ترکیب خوشه های با چگالی زیاد و کوچک خوشه های بزرگتری حاصل می شود.
مزایای خوشه بندی بر اساس چگالی
a. خوشه ها می توانند دارای اشکال دلخواه باشند.
b. تعداد خوشه ها به صورت اتوماتیک همزمان با عمل خوشه بندی تعیین می شود.
c. در تشخیص نویزها بسیار کارا هستند.
معیارهای کارایی:
همانطور که قبلا اشاره شد یکی از مهمترین مسایل در خوشه بندی انتخاب تعداد خوشه های مناسب می باشد. تعداد خوشه ای مناسب می باشد که 1) نمونه های موجود در یک خوشه تا حد امکان شبیه به یکدیگر باشند و 2) نمونه های متعلق به خوشه های متفاوت تا حد امکان با یکدیگر نامتشابه باشند. عبارات فوق را بدین صورت نیز بیان می کنند که خوشه ها باید ماکزیمم فشردگی6 باشند و تا حد امکان جدایی7 آنها نیز زیاد باشد. اگر تنها معیار فشردگی مورد استفاده قرار گیرد در آنصورت هر داده می تواند به صورت یک خوشه در نظر گرفته شود چرا که هیچ خوشه ای فشرده تر از خوشه ای با یک داده نمی باشد. اگر تنها معیار جدایی در نظر گرفته شود در آنصورت بهترین خوشه بندی این می باشد که کل داده ها را یک خوشه بگیریم با این فرض که فاصله هر خوشه از خودش صفر است. بنابراین باید از ترکیب دو معیار فوق استفاده شود. برای مشخص کردن تعداد درست خوشه ها توابع ارزیابی8 مختلفی تعریف شده است که می توان با استفاده از آنها تعداد خوشه ها را برای مسایل مختلف مشخص کرد.
1. تابع ارزیابی ضریب افراز9
انتخاب تعداد خوشه های مناسب با ماکزیمم کردن تابع فوق بدست می آید. یعنی برای تعداد خوشه های مختلف خوشه بندی را اجرا می کنند و با استفاده از ماتریس تعلق بدست آمده مقدار تابع فوق را محاسبه می کنند. تعداد خوشه هایی که به ازای آن این تابع بیشترین مقدار را داشته است بعنوان تعداد خوشه های مناسب برای آن مساله مورد استفاده قرار می گیرد. مقدار تابع فوق بین 1/c و 1 می باشد.
2. تابع ارزیابی آنتروپی افراز10
انتخاب تعداد خوشه های مناسب با مینیمم کردن تابع فوق بدست می آید. تعداد خوشه هایی که به ازای آن این تابع کمترین مقدار را داشته است بعنوان تعداد خوشه های مناسب برای آن مساله مورد استفاده قرار می گیرد. مقدار این تابع بین 0 تا log2c می باشد. یک حالت دیگر از این تابع نیز تعریف شده است که به تابع ارزیابی آنتروپی نرمال شده معروف است. در این تابع مقدار تابع ارزیابی فوق را بر لگاریتم تعداد خوشه ها (c) تقسیم می کنند.
نکته قابل توجه در مورد این دو تابع این است که زمانی که PC برابر 1 باشد PE برابر 0 خواهد بود و در این حالت خوشه بندی معادل خوشه بندی کلاسیک است. اگر PC برابر 1/c باشد PE برابر log2c خواهد بود که در این حالت خوشه بندی در فازی ترین حالت خود خواهد بود. از طرف دیگر گفته شد که باید برای رسیدن به حالت خوشه بندی مطلوب PC ماکزیمم شود و PE می نیمم. بنابراین در خوشه بندی های فازی سعی می شود تا خوشه ها به خوشه های کلاسیک نزدیکتر باشند.
نقاط ضعف دو تابع فوق این است که از خود داده ها بطور مستقیم برای ارزیابی خوشه بندی استفاده نشده است.
3. تابع Fukuyama and Sugeno
در تابع فوق میانگین کل نمونه ها میباشد.انتخاب تعداد خوشه های مناسب با مینیمم کردن تابع فوق بدست می آید. تعداد خوشه هایی که به ازای آن این تابع کمترین مقدار را داشته است بعنوان تعداد خوشه های مناسب برای آن مساله مورد استفاده قرار می گیرد. در واقع جمله اول در تابع فوق معیاری برای فشردگی خوشه ها می باشد و جمله دوم معیاری برای جدایی خوشه ها از هم می باشد. هر چه خوشه ها فشرده تر باشند جمله اول کوچکتر خواهد بود و هر چه جمله دوم بزرگتر باشد جدایی خوشه ها بیشتر می باشد. بنابراین مینیمم کردن تابع فوق میتواند معیار مناسبی برای ارزیابی خوشه بندی و تعداد خوشه ها باشد.
4. تابع Xie and Beni
انتخاب تعداد خوشه های مناسب با مینیمم کردن تابع فوق بدست می آید. تعداد خوشه هایی که به ازای آن این تابع کمترین مقدار را داشته است بعنوان تعداد خوشه های مناسب برای آن مساله مورد استفاده قرار می گیرد. در واقع صورت تابع فوق معیاری برای فشردگی خوشه ها می باشد و مخرج کسر معیاری برای جدایی خوشه ها از هم می باشد. هر چه خوشه ها فشرده تر باشند صورت کسر کوچکتر خواهد بود و هر چه مخرج کسر بزرگتر باشد جدایی خوشه ها بیشتر می باشد. بنابراین مینیمم کردن تابع فوق میتواند معیار مناسبی برای ارزیابی خوشه بندی و تعداد خوشه ها باشد.
5. تابع N.Zahid
آقای N.Zahid و همکارانش تابع ارزیابی دیگری را معرفی کرده اند که مبتنی بر معیارهای فشردگی و جدایی خوشه می باشد.
انحراف فازی11 نمونه k ام از مرکز خوشه Vi بصورت زیر تعریف می شود:
تغییرات خوشه فازی Ui بصورت زیر تعریف شده است:
کاردینالیتی فازی خوشه Ui نیز بصورت زیر تعریف شده است:
با استفاده از تعاریف فوق میتوان میزان فشردگی خوشه فازی Ui را بصورت زیر تعریف کرد:
فشردگی کلی تمامی خوشه ها بصورت زیر تعریف شده است:
برای تعریف تابع ارزیابی لازم است تا معیار جدایی خوشه ها را نیز تعریف شود که آقای N.Zahid و همکارانش جدایی خوشه ها را بصورت زیر تعریف کرده اند:
نسبت بین جدایی خوشه ها و فشردگی خوشه ها بعنوان تابع ارزیابی تعریف میشود:
انتخاب تعداد خوشه های مناسب با ماکزیمم کردن تابع فوق بدست می آید.
6. تابع M.Ramze Rezaee
آقای Ramze Rezaee و همکارانش تابع دیگری را برای ارزیابی الگوریتم خوشه بندی c میانگین ارائه داده اند. روش آنها مبتنی بر معیارهای جدایی و فشردگی خوشه ها می باشد که در ادامه روش مورد نظر آورده شده است.
فرض کنید که داده های ورودی p بعدی باشند و می خواهیم آنها را به c خوشه گروهبندی کنیم:
خوشه ها با vi مشخص می شوند و میزان تعلق نمونه ها با خوشه ها نیز با ماتریس U نشان داده می شود. اگر واریانس نمونه های X را Rp (x)σ درنظر بگیریم برای p امین مولفه واریانس خواهیم داشت:
که در فرمول فوق ، p امین مولفه متوسط نمونه ها می باشد. متوسط نمونه ها نیز با فرمول زیر محاسبه می شود:
اگر تغییرات خوشه i ام را Rp (vi)σ در نظر بگیریم برای p امین مولفه تغییرات خواهیم داشت:
با استفاده از معادلات تعریف شده متوسط پراکندگی تمامی خوشه ها بصورت زیر تعریف شده است:
همچنین یک تابع فاصله نیز بصورت زیر تعریف شده است:
که برای Dmax و Dmin داریم:
که در واقع فرمول فوق ماکزیمم(می نیمم) فاصله بین مراکز خوشه ها را محاسبه می کند. از روی فرمول های فاصله و پراکندگی آقای Ramze Rezaee و همکارانش تابع ارزیابی را بصورت زیر تعریف کرده اند:
جمله اول فرمول فوق متوسط پراکندگی خوشه ها را نشان می دهد که هر چه این مقدار کوچک باشد نشان دهنده این است که خوشه ها فشرده تر هستند. اما همانطور که قبلا گفته شد این جمله بتنهایی نمی تواند معیار خوبی برای خوشه بندی باشد و باید جدایی خوشه ها نیز در نظر گرفته شود که این معیار توسط جمله دوم فرمول فوق محقق می شود. ضریب α نیز که برابر است با D(cmax) برای متعادل کردن دو جمله بکار گرفته شده است. الگوریتم پیدا کردن تعداد خوشه های بهینه بصورت زیر می باشد:
فرض کنید که تعداد خوشه های بهینه بین cmin و cmax باشد. تابع ارزیابی فوق را برای تمامی مقادیر بین cmin و cmax محاسبه و ذخیره می کنیم. مقدار c متناظر می نیمم مقادیر ذخیره شده تعداد خوشه های بیهنه خوشه بندی می باشد.
خلاصه و نتیجه گیری
خوشه بندی همان گونه که بیان شد، به کشف گروه هایی از داده های مشابه درون مجموعه ای از داده ها می پردازد، بدون هیچ اطلاع قبلی از کلاسهای مربوط به داده ها. انواعی از روشهای خوشه بندی تاکنون ارائه شده اندکه وابسته به کاربرد می توان از آنها استفاده کرد. در ادامه گروهی از این روشهای که به الگوریتم های سلسله مراتبی خوشه بندی معروف هستند و یک نمودار که اولویت ترکیب داده ها برای تولید خوشه ها را ارائه می دهد، بررسی شد. سپس روش خوشه بندی K-Means که روشی پایه ای برای بسیاری از روشهای خوشه بندی جدید محسوب می شود، معرفی شد. پس از آن چند تکنیک خوشه بندی دیگر که از چگالی داده ها برای خوشه بندی استفاده می کنند، ارائه شدند که این روش برای خوشه بندی داده های با اشکال دلخواه بسیار بهتر از سایر روشها عمل می کنند.
در ادامه تکنیک هایی برای ارزیابی و سنجش خوشه های حاصل از خوشه بندی ارائه شده که از طریق آنها می توان پارامترهای هر یک از روشهای مذکور را به صورتی که نتیجه بهتری حاصل شود تعیین کرد.
با توجه به کاربرد روز افزون خوشه بندی، امروزه شاهد ارائه روشهای جدید و کاراتری هستیم که هر یک برای کاربردی خاص ارائه می شود. همچین شاخص های اعتبارسنجی زیادی نیز برای بهترکردن نتیجه خوشه بندی معرفی می شوند ولی با همه این تلاشها هنوز خوشه بندی در بسیاری از علوم آنچنان که باید بکار گرفته شود، مورد استفاده قرار نگرفته است قابلیت گسترش بسیار زیادی برای آن وجود دارد.
مراجع:
[1]Algorithms for clustering clickstream data
[2]Unsupervised data pruning for clustering of noisy data
[3]Tariq Rashid: "Clustering"
http://www.cs.bris.ac.uk/home/tr1690/documentation/fuzzy_clustering_initial_report/node11.html
[4]Osmar R. Zaïane: "Principles of Knowledge Discovery in Databases – Chapter 8: Data Clustering"
http://www.cs.ualberta.ca/~zaiane/courses/cmput690/slides/Chapter8/index.html
[5]Pier Luca Lanzi: "Ingegneria della Conoscenza e Sistemi Esperti – Lezione 2: Apprendimento non supervisionato"
http://www.elet.polimi.it/upload/lanzi/corsi/icse/2002/Lezione%202%20-%20Apprendimento%20non%20supervisionato.pdf
[6]M. Halkidi, Y. Batistakis and M. Vazirgiannis, "On Clustering Validation Techniques", Journal of Intelligent Systems, vol. 17:2/3, pp 107-145, 2001.
[7]George E. Tsekouras and Haralambos Sarimveis, "A new approach for measuring the validity of the fuzzy c-means algorithm", Advances in Engineering Software 35 (2004) 567-575.
[8]N. Zahid, M. Limouri and A. Essaid, "A new cluster-validity for fuzzy clustering", Pattern Recognition 32 (1999) 1089-1097.
[9]M. Ramze Rezaee, B.P.F. Lelieveldt, J.H.C. Reiber, "A new cluster validity index for the fuzzy c-mean", Pattern Recognition Letters 19 1998 237-246.
[10]Bezdek, J.C., 1981. "Pattern Recognization with Fuzzy Objective Function Algorithms". Plenum press, New York.
[11]Bezdek JC. "Fuzzy mathematics in pattern classification". PhD dissertation, Cornell University, Ithaca, NY; 1973.
[12]S.L. Chiu, "Fuzzy model identification based on cluster estimation", J. Intell. Fuzzy Systems 2 (1994) 267- 278.
[13]J. Yao, M. Dash, S.T. Tan, H. Liu, "Entropy-based fuzzy clustering and fuzzy modeling", Fuzzy Sets and Systems 113 (2000) 381_388.
[14]Dat Tran and Michael Wagner, "Fuzzy Entropy Clustering", University of Canberra, ATC 2601, Australia.
[15]Xizhao Wang, Yadong Wang and Lijuan Wang, "Improving fuzzy c-means clustering based on feature-weight learning", Pattern Recognition Letters 25 (2004) 1123-1132.
[16]George E. Tsekouras and Haralambos Sarimveis, "A new approach for measuring the validity of the fuzzy c-means algorithm", Advances in Engineering Software 35 (2004) 567-575.
1 Clustering
2 Cluster
3 Distance-based Clustering
4 Classification
5 Uncertainty
6 Compactness
7 Separation
8 Validation function
9 Partition coefficient
10 Partition entropy
11 Fuzzy Deviation
—————
————————————————————
—————
————————————————————
14