خوشه بندی و روش های پیاده سازی(قسمت اول)

پست شده توسط در مرداد ۱, ۱۳۹۶ در آموزشی | ۰ دیدگاه


فرایند یادگیری در هوشمندسازی را میتوان به دو دسته تقسیم کرد:

  • یادگیری با نظارت (Supervised Learning)
  • یادگیری بدون نظارت (Unsupervised Learning)

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

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

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

از آنجا که خوشه‌بندی یک روش یادگیری بدون نظارت محسوب می‌گردد، و اکثر داده های خام بدون برچسب هستند، در موارد بسیاری می‌تواند کاربرد داشته‌ باشد.

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

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

۱٫  خوشه‌بندی با روش K_Nearest Neighbor

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

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

 

۲٫ روش خوشه بندی K-Means (C-Means یا C-Centeriod)

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

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

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

 

الگوریتم زیر الگوریتم پایه برای این روش محسوب می‌شود:

  1. در ابتدا K نقطه به عنوان به نقاط مراکز خوشه‌ها انتخاب می‌شوند.
  2. هر نمونه داده به خوشه‌ای که مرکز آن خوشه کمترین فاصله تا آن داده را داراست، نسبت داده‌ می‌شود.
  3. پس تعلق تمام داده‌ها به یکی از خوشه‌ها برای هر خوشه یک نقطه جدید به عنوان مرکز محاسبه می‌شود. (میانگین نقاط متعلق به هر خوشه)
  4. مراحل ۲ و ۳ تکرار می‌شوند تا زمانی که دیگر هیچ تغییری در مراکز خوشه‌ها حاصل نشود.

 

۳٫ روش K-Means مبتنی بر منطق فازی

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

جواب سوال در فهمیدن مفهوم اولیه ی منطق فازی است. در منطق صفر و یک و یا اصطلاحا منطق گسسته، پراکندگی داده ها به صورت گسسته است. در زمانگرد کردن اعداد غیر صحیح به اعداد صحیح این قانون به خوبی قابل مشاهده است. مثلا عدد ۲٫۸ چون به عدد ۳ نزدیک تر است، آنرا به صورت ۳ گرد می کنیم. عدد ۲٫۱ را نیز به عدد ۲ گرد می کنیم. عدد ۲٫۶ نیز به ۳ گرد می شود. اگر مرز را عدد ۲٫۵ در نظر بگیریم، دو کلاس داریم: کلاس عدد۲ و کلاس عدد۳٫ داده هایی در کلاس عدد۳ قرار می گیرند که بزرگ تر از ۲٫۵ باشند و داده هایی در کلاس عدد ۲ قرار می گیرند که از ۲٫۵ کوچکتر باشند. یعنی هیچ تفاوتی بین ۲٫۶ و ۲٫۹ وجود ندارد. در منطق فازی، این دو عدد مثل هم نیستند. هر چند کلاس هر دو یکی است ولی نرخ تعلق آنها به این کلاس با هم یکسان نیست. عدد۲٫۹ با قطعیت بیشتری نسبت به عدد۲٫۶ به کلاس ۲ تعلق دارد. این همان مفهوم ساده ای از منطق فازی است.

ارسال دیدگاه

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *