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

خوشه بندی (Clustering)

   ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﻳﮑﻲ ﺍﺯ ﺷﺎﺧﻪ ﻫﺎﻱ ﻳﺎﺩﮔﻴﺮﻱ ﺑﺪﻭﻥ ﻧﻈﺎﺭﺕ ﻣﻲ ﺑﺎﺷﺪ ﻭ ﻓﺮﺁﻳﻨﺪ ﺧﻮﺩﮐﺎﺭﻱ ﺍﺳﺖ ﮐﻪ ﺩﺭ ﻃﻲ ﺁﻥ، ﻧﻤﻮﻧﻪ ﻫﺎ ﺑﻪ ﺩﺳﺘﻪ ﻫﺎﻳﻲ ﮐﻪ ﺍﻋﻀﺎﻱ ﺁﻥ ﻣﺸﺎﺑﻪ ﻳﮑﺪﻳﮕﺮ ﻣﻲ ﺑﺎﺷﻨﺪ ﺗﻘﺴﻴﻢ ﻣﻲ ﺷﻮﻧﺪ ﮐﻪ ﺑﻪ ﺍﻳﻦ ﺩﺳﺘﻪ ﻫﺎ ﺧﻮﺷﻪ ﮔﻔﺘه ﻣﻲشود. ﺑﻨﺎﺑﺮﺍﻳﻦ ﺧﻮﺷﻪ ﻣﺠﻤﻮﻋﻪ ﺍﻱ ﺍﺯ ﺍﺷﻴﺎﺀ ﻣﻲ ﺑﺎﺷﺪ ﮐﻪ ﺩﺭ ﺁﻥ ﺍﻋﻀﺎﻱ ﻣﺠﻤﻮﻋﻪ ﺑﺎ ﻳﮑﺪﻳﮕﺮ ﻣﺸﺎﺑﻪ ﺑﻮﺩﻩ ﻭ ﺑﺎ ﺍﺷﻴﺎﺀ ﻣﻮﺟﻮﺩ ﺩﺭ ﺧﻮﺷﻪ ﻫﺎﻱ (ﻣﺠﻤﻮﻋﻪ ﻫﺎﻱ )ﺩﻳﮕﺮ غیر مشابه می باشد. ﺑﺮﺍﻱ ﻣﺸﺎﺑﻪ ﺑﻮﺩﻥ ﻣﻲ ﺗﻮﺍﻥ ﻣﻌﻴﺎﺭﻫﺎﻱ ﻣﺨﺘﻠﻔﻲ ﺭﺍﺩﺭ ﻧﻈﺮ ﮔﺮﻓﺖ ﻣﺜﻼ ﻣﻲ ﺗﻮﺍﻥ ﻣﻌﻴﺎﺭ ﻓﺎﺻﻠﻪ ﺭﺍ ﺑﺮﺍﻱ ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﻣﻮﺭﺩ ﺍﺳﺘﻔﺎﺩﻩ ﻗﺮﺍﺭ ﺩﺍﺩ ﻭ ﺍﺷﻴﺎﺋﻲ ﺭﺍ ﮐﻪ ﺑﻪ ﻳﮑﺪﻳﮕﺮ ﻧﺰﺩﻳﮑﺘﺮ ﻫﺴﺘﻨﺪ ﺭﺍ ﺑﻌﻨﻮﺍﻥ ﻳﮏ ﺧﻮﺷﻪ ﺩﺭ ﻧﻈﺮ ﮔﺮﻓﺖ ﮐﻪ ﺑﻪ ﺍﻳﻦ ﻧﻮﻉ ﺧﻮﺷﻪ ﺑﻨﺪﻱ، ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﻣﺒﺘﻨﻲ ﺑﺮ ﻓﺎﺻﻠﻪ ﻧﻴﺰ ﮔﻔﺘﻪ ﻣﻲ ﺷﻮﺩ.ﺑﻌﻨﻮﺍﻥ ﻣﺜﺎﻟﻲ ﺍﺯ ﺧﻮﺷﻪ ﺑﻨﺪﻱ، ﺩﺭ ﺷﮑﻞ ﺯﻳﺮ ﻧﻤﻮﻧﻪ ﻫﺎﻱ ﻭﺭﻭﺩﻱ ﺩﺭ ﺳﻤﺖ ﭼﭗ ﺑﻪ ﭼﻬﺎﺭ ﺧﻮﺷﻪ ﻣﺸﺎﺑﻪ ﺷﮑﻞ ﺳﻤﺖ ﺭﺍﺳﺖ ﺗﻘﺴﻴﻢ ﻣﻲ ﺷﻮﻧﺪ .ﺩﺭ ﺍﻳﻦ ﻣﺜﺎﻝ ﻫﺮ ﻳﮏ ﺍﺯ ﻧﻤﻮﻧﻪ ﻫﺎﻱ ﻭﺭﻭﺩﻱ ﺑﻪ ﻳﮑﻲ ﺍﺯ ﺧﻮﺷﻪ ﻫﺎ ﺗﻌﻠﻖ ﺩﺍﺭﺩ ﻭ ﻧﻤﻮﻧﻪ ﺍﻱ ﻭﺟﻮﺩ ﻧﺪﺍﺭﺩ ﮐﻪ ﻣﺘﻌﻠﻖ ﺑﻪ ﺑﻴﺶ ﺍﺯ ﻳﮏ ﺧﻮﺷﻪ ﺑﺎﺷﺪ.

در کنار مفهوم خوشه بندی(Clustering) ، مفهوم دسته بندی(Classification) وجود دارد. در خوشه بندی، هدف یافتن مجموعه متناهی از خوشه ها برای توصیف داده هاست. هدف در دسته بندی، ایجاد یک مدل پیشگویی کننده است که این مدل اولا توانایی دسته بندی داده های ورودی را داشته باشد و ثانیا بتوان از آن جهت پیشگویی برای تعیین دسته ی یک داده که تازه به سیستم اضافه شده، استفاده نمود.

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

 ﻫﺪﻑ ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﻳﺎﻓﺘﻦ ﺧﻮﺷﻪ ﻫﺎﻱ ﻣﺸﺎﺑﻪ ﺍﺯ ﺍﺷﻴﺎﺀ ﺩﺭ ﺑﻴﻦ ﻧﻤﻮﻧﻪ ﻫﺎﻱ ﻭﺭﻭﺩﻱ ﻣﻲ ﺑﺎﺷﺪ ﺍﻣﺎ ﭼﮕﻮﻧﻪ ﻣﻲ ﺗﻮﺍﻥ ﮔﻔﺖ ﮐﻪ ﻳﮏ ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﻣﻨﺎﺳﺐ ﺍﺳﺖ ﻭ ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﺩﻳﮕﺮ ﻣﻨﺎﺳﺐ ﻧﻴﺴﺖ؟ ﺩﺭ ﻭﺍﻗﻊ ﻫﻴﭻ ﻣﻌﻴﺎﺭ ﻣﻄﻠﻘﻲ ﺑﺮﺍﻱ ﺑﻬﺘﺮﻳﻦ ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﻭﺟﻮﺩ ﻧﺪﺍﺭﺩ ﺑﻠﮑﻪ ﺍﻳﻦ ﺑﺴﺘﮕﻲ ﺑﻪ ﻣﺴﺎﻟﻪ ﻭ ﻧﻈﺮ ﮐﺎﺭﺑﺮ ﺩﺍﺭﺩ ﮐﻪ ﺑﺎﻳﺪ ﺗﺼﻤﻴﻢ ﺑﮕﻴﺮﺩ ﮐﻪ ﺁﻳﺎ ﻧﻤﻮﻧﻪ ﻫﺎ ﺑﺪﺭﺳﺘﻲ ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﺷﺪﻩ ﺍﻧﺪ ﻳﺎ ﺧﻴﺮ .ﺑﺎ ﺍﻳﻦ ﺣﺎﻝ ﻣﻌﻴﺎﺭ ﻫﺎﻱ ﻣﺨﺘﻠﻔﻲ ﺑﺮﺍﻱ ﺧﻮﺏ ﺑﻮﺩﻥ ﻳﮏ ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﺍﺭﺍﺋﻪ ﺷﺪﻩ ﺍﺳﺖ ﮐﻪ ﻣﻲ ﺗﻮﺍﻧﻨﺪ ﮐﺎﺭﺑﺮ ﺭﺍ ﺑﺮﺍﻱ ﺭﺳﻴﺪﻥ ﺑﻪ ﻳﮏ ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﻣﻨﺎﺳﺐ ﺭﺍﻫﻨﻤﺎﻳﻲ ﮐﻨﺪ ﮐﻪ ﺩﺭ ﻗﺴﻤﺖ ﻫﺎﻱ ﺑﻌﺪ ﭼﻨﺪ ﻧﻤﻮﻧﻪ ﺍﺯ ﺍﻳﻦ ﻣﻌﻴﺎﺭﻫﺎ ﺁﻭﺭﺩﻩ ﺷﺪﻩ ﺍﺳﺖ .ﻳﮑﻲ ﺍﺯ ﻣﺴﺎﻳﻞ ﻣﻬﻢ ﺩﺭ ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﺍﻧﺘﺨﺎﺏ ﺗﻌﺪﺍﺩ ﺧﻮﺷﻪ ﻫﺎ ﻣﻲ ﺑﺎﺷﺪ .ﺩﺭ ﺑﻌﻀﻲ ﺍﺯ ﺍﻟﮕﻮﺭﻳﺘﻢ ﻫﺎ ﺗﻌﺪﺍﺩ ﺧﻮﺷﻪ ﻫﺎ ﺍﺯ ﻗﺒﻞ ﻣﺸﺨﺺ ﺷﺪﻩ ﺍﺳﺖ ﻭ ﺩﺭ ﺑﻌﻀﻲ ﺩﻳﮕﺮ ﺧﻮﺩ ﺍﻟﮕﻮﺭﻳﺘﻢ ﺗﺼﻤﻴﻢ ﻣﻲ ﮔﻴﺮﺩ ﮐﻪ ﺩﺍﺩﻩ ﻫﺎ ﺑﻪ ﭼﻨﺪ ﺧﻮﺷﻪ ﺗﻘﺴﻴﻢ ﺷﻮﻧﺪ .

تفاوت خوشه بندی فازی داده و کلاسیک

 ﺑﺮﺍﻱ ﺩﺭﮎ ﺑﻬﺘﺮﺧﻮﺷﻪ ﺑﻨﺪﻱ ﻓﺎﺯﻱ ﻭ ﺍﻟﮕﻮﺭﻳﺘﻤﻬﺎﻱ ﻣﺨﺘﻠﻒ ﺁﻥ ﻻﺯﻡ ﺍﺳﺖ ﺗﺎ ﺍﺑﺘﺪﺍ ﺑﺎ ﻣﻔﻬﻮﻡ ﻣﺠﻤﻮﻋﻪ ﻫﺎﻱ ﻓﺎﺯﻱ ﻭ ﺗﻔﺎﻭﺕ ﺁﻧﻬﺎ ﺑﺎ ﻣﺠﻤﻮﻋﻪ ﻫﺎﻱ ﮐﻼﺳﻴﮏ ﺁﺷﻨﺎ ﺷﻮﻳﻢ .ﺩﺭ ﻣﺠﻤﻮﻋﻪ ﻫﺎﻱ ﮐﻼﺳﻴﮏ ﻳﮏ ﻋﻀﻮ ﺍﺯ ﻣﺠﻤﻮﻋﻪ ﻣﺮﺟﻊ ﻳﺎعضوی از مجموعه A  ﺍﺳﺖ ﻳﺎ ﻋﻀﻮ ﻣﺠﻤﻮﻋﻪ A ﻧﻴﺴﺖ .ﻣﺜﻼ ﻣﺠﻤﻮﻋﻪ ﻣﺮﺟﻊ ﺍﻋﺪﺍﺩ ﺣﻘﻴﻘﻲ ﺭﺍ ﺩﺭ ﻧﻈﺮ ﺑﮕﻴﺮﻳﺪ . ﻋﺪﺩ 2.5 ﻋﻀﻮ ﻣﺠﻤﻮﻋﻪ ﺍﻋﺪﺍﺩ ﺻﺤﻴﺢ ﻧﻤﻲ ﺑﺎﺷﺪ ﺣﺎﻝ ﺁﻧﮑﻪ عدد 2 ﻋﻀﻮ ﺍﻳﻦ ﻣﺠﻤﻮﻋﻪ ﺍﺳﺖ  .

ﺩﺭ ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﮐﻼﺳﻴﮏ ﻫﺮ ﻧﻤﻮﻧﻪ ﻭﺭﻭﺩﻱ ﻣﺘﻌﻠﻖ ﺑﻪ ﻳﮏ ﻭ ﻓﻘﻂ ﻳﮏ ﺧﻮﺷﻪ ﻣﻲ ﺑﺎﺷﺪ ﻭ ﻧﻤﻲ ﺗﻮﺍﻧﺪ ﻋﻀﻮ ﺩﻭ ﺧﻮﺷﻪ ﻭ ﻳﺎ ﺑﻴﺸﺘﺮ ﺑﺎﺷﺪ .ﻣﺜﻼ ﺩﺭ ﺷﮑﻞ ﻗﺒﻞ ﻫﺮ ﻳﮏ ﻭﺳﺎﻳﻞ ﻧﻘﻠﻴﻪ ﻋﻀﻮ ﻳﮏ ﺧﻮﺷﻪ ﻣﻲ ﺑﺎﺷﺪ ﻭ ﻧﻤﻮﻧﻪ ﺍﻱ ﻋﻀﻮ ﺩﻭ ﺧﻮﺷﻪ ﻧﻴﺴﺖ ﻭ ﺑﻪ ﺯﺑﺎﻥ ﺩﻳﮕﺮ ﺧﻮﺷﻪ ﻫﺎ ﻫﻤﭙﻮﺷﺎﻧﻲ ﻧﺪﺍﺭﻧﺪ.ﺣﺎﻝ ﺣﺎﻟﺘﻲ ﺭﺍ ﺩﺭ ﻧﻈﺮ ﺑﮕﻴﺮﻳﺪ ﮐﻪ ﻣﻴﺰﺍﻥ ﺗﺸﺎﺑﻪ ﻳﮏ ﻧﻤﻮﻧﻪ ﺑﺎ ﺩﻭ ﺧﻮﺷﻪ ﻭ ﻳﺎ ﺑﻴﺸﺘﺮ ﻳﮑﺴﺎﻥ ﺑﺎﺷﺪ .ﺩﺭ ﭼﻨﻴﻦ ﺣﺎﻟﺘﻲ ﺩﺭ ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﮐﻼﺳﻴﮏ ﺑﺪﻟﻴﻞ ﺁﻧﮑﻪ ﻫﺮ ﻧﻤﻮﻧﻪ ﺑﺎﻳﺪ ﺑﻪ ﻳﮏ ﻭ ﻓﻘﻂ ﻳﮏ ﺧﻮﺷﻪ ﻣﺘﻌﻠﻖ ﺑﺎﺷﺪ ﺑﺎﻳﺪ ﺗﺼﻤﻴﻢ ﮔﻴﺮﻱ ﺷﻮﺩ ﮐﻪ ﺍﻳﻦ ﻧﻤﻮﻧﻪ ﻣﺘﻌﻠﻖ ﺑﻪ ﮐﺪﺍﻡ ﺧﻮﺷﻪ ﺍﺳﺖ .ﺗﻔﺎﻭﺕ ﺍﺻﻠﻲ ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﮐﻼﺳﻴﮏ ﻭ ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﻓﺎﺯﻱ ﺩﺭ ﻫﻤﻴﻦ ﺟﺎﺳﺖ ﮐﻪ ﺩﺭ ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﻓﺎﺯﻱ ﻳﮏ ﻧﻤﻮﻧﻪ ﻣﻲ ﺗﻮﺍﻧﺪ ﻣﺘﻌﻠﻖ ﺑﻪ ﺑﻴﺶ ﺍﺯ ﻳﮏ ﺧﻮﺷﻪ ﺑﺎﺷﺪ .

بعنوان مثال ، شکل زیر را در نظر بگیرید. در این شکل پس از عملیات خوشه بندی نمونه هایی که با علامت “ + “ مشخص شده اند به بیش از یک خوشه تعلق دارد.

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

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

اﻟﮕﻮﺭﻳﺘﻤﻬﺎﻱ خوشه بندی ،ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﮐﺎﺭﺑﺮﺩ ﻭ ﺗﻨﻮﻉ ﻣﺴﺎﺋﻞ ﻣﺮﺗﺒﻂ ﺑﺎ ﺁﻥ، ﺑﺴﻴﺎﺭ ﺯﻳﺎﺩﻧﺪ ﻭ ﻋﻠﻴﺮﻏﻢ ﭘﻴﮕﻴﺮﻱ ﻳﮏ ﻫﺪﻑ ﺍﺯ ﻟﺤﺎﻅ ﺗﮑﻨﻴﮑﻲ ﺗﻔﺎﻭﺕ ﻫﺎﻳﻲ ﮔﺎﻫﺎ ﻣﺘﻀﺎﺩ ﺩﺍﺭﻧﺪ  که برخی از آنها عبارتند از:

•          مبتنی برناحیه (الگوریتم K-means و K-mediods)

•          روش سلسله مراتبی

•          مبتنی بر چگالی

•          روش Grid-based

•          روش مبتنی بر مدل

روش K-means

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

در الگوریتم K-means ابتدا k عضو (که k تعداد خوشه‌ها است) بصورت تصادفی از میان n عضو به عنوان مراکز خوشه‌ها انتخاب می‌شود. سپس n-k عضو باقیمانده به نزدیک‌ترین خوشه تخصیص می‌یابند. بعد از تخصیص همه اعضا مراکز خوشه مجدداً محاسبه می‌شوند و با توجه به مراکز جدید به خوشه‌ها تخصیص می‌یابند و این کار تا زمانی که مراکز خوشه‌ها ثابت بماند ادامه می‌یابد. بهترین خوشه‌بندی آن است که مجموع تشابه بین مرکز خوشه و همه اعضای خوشه را حداکثر و مجموع تشابه بین مراکز خوشه‌ها را حداقل کند. برای انتخاب بهترین خوشه ابتدا براساس نظرات خبره و مطالعات قبلی یک محدوده پیشنهادی برای تعداد خوشه‌ها مشخص می‌شود. معمولاَ این محدوده بین انتخاب می‌شود. سپس مقدار ρ(k) برای هریک از مقادیر k محاسبه می‌شود. مقداری از k که در آن ρ(k) حداکثر شود، به عنوان تعداد بهینه خوشه‌ها انتخاب می‌شود. به این ترتیب می‌توان تعداد خوشه‌ای را انتخاب نمود که به ازای آن فاصله بین مراکز خوشه‌ها و شباهت مراکز خوشه با اعضای درون هر خوشه حداکثر است.

روال خوشه بندی در الگوریتم K-means

نقاط قوتK-means  

این روش نسبتا برای پایگاههای داده بزرگ و کارا ارتقا پذیر می باشد زیرا پیچیدگی محاسباتی آن عبارت است ازO(tkn) که n تعداد اشیا و k تعداد خوشه ها و t نعداد تکرارهای الگوریتم است.

نقاط ضعف K-means

از نقاط ضعف این الگوریتم می­توان به موارد زیر اشاره کرد:

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

الگوریتم k-mediods

برای بهبود خوشه­بندی K-means انواع متفاوتی در راستای بهبود نقاط ضعف پیشنهاد شده است از جمله الگوریتم K-mediods.

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

از ویژگیهای این الگوریتم میتوان به موارد زیر اشاره کرد:

•           این الگوریتم نسبت به نویز مقاوم تر است
•           پیچیدگی محاسباتی بالاتری دارد
•           برای پایگاه داده های کوچک عملکرد مناسب تری دارد
•          نحوه عملکرد بدین صورت است که ابتدا از کل داده ها نمونه هایی به صورت تصادفی انتخاب و با این الگوریتم خوش بندی می کنیم .سپس بقیه داده ها را به نزدیکترین خوشه اضافه می کنیم.
•          این کار را چند بار تکرار می کنیم و هر کدام هزینه کمتری در خوشه بندی داشت انتخاب می شود.

روش سلسله مراتبی

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

بخش بندی چیست؟

.بخش بندی تصویر (Image Segmentation)

ﺑﺨﺶﺑﻨﺪی ﺗﺼﻮﯾﺮ اوﻟﯿﻦ ﻣﺮﺣﻠﻪ و ﺑﺤﺮاﻧﯽﺗﺮﯾﻦ ﻣﺮﺣﻠﻪ از آﻧﺎﻟﯿﺰ ﺗﺼﻮﯾﺮ ﻣﯽﺑﺎﺷﺪ ﮐﻪ ﻫﺪﻓﺶ اﺳﺘﺨﺮاج اﻃﻼﻋﺎت داﺧﻞ ﺗﺼﻮﯾﺮﻣﺎﻧﻨﺪ (ﻟﺒﻪﻫﺎ ، ﻧﻤﺎﻫﺎ و ﻫﻮﯾﺖ ﻫﺮ ﯾﮏ از ﻧﻮاﺣﯽ) ﻣﯽﺑﺎﺷﺪﮐﻪ از ﻃﺮﯾﻖ ﺗﻮﺻﯿﻒ، ﻧﺎﺣﯿﻪﻫﺎی ﺑﺪﺳﺖ آﻣﺪه را ﺑﺮای ﮐﺎﻫﺶ آﻧﻬﺎ ﺑﻪ ﺷﮑﻞ ﻣﻨﺎﺳﺐ ﺑﺮای ﭘﺮدازش ﮐﺎﻣﭙﯿﻮﺗﺮ و ﺗﺸﺨﯿﺺ ﻫﺮ ﯾﮏ از ﻧﻮاﺣﯽ آﻣﺎده ﻣﯽﮐﻨﺪ.نتیجه بخش بندی ﺗﺎﺛﯿﺮ ﻗﺎﺑﻞ ملاحظه ای ﺑﺮ دﻗﺖ ارزﯾﺎﺑﯽ وﯾﮋﮔﯽﻫﺎﺧﻮاﻫﺪ داﺷﺖ ..ﺑﺨﺶﺑﻨﺪی اﻏﻠﺐ ﺷﺮح ﻓﺮآﯾﻨﺪ ﺗﻘﺴﯿﻢ ﺗﺼﻮﯾﺮ ﺑﻪ  اﺟﺰاء اﺻﻠﯽ و اﺳﺘﺨﺮاج ﻗﺴﻤﺘﻬﺎی ﻣﻮرد ﻋﻼﻗﻪ  اﺷﯿﺎء ﻣﯽﺑﺎﺷﺪ. بخش بندی یکی از مشکل ترین مباحث در پردازش تصویراست که در موفقیت عمل تحلیل تصویر بسیار موثر است. برای بخش بندی تصویر روشهای مختلفی وجود دارد که می توان انهارا به دو دسته روشهای مبتنی بر هیستوگرام(based -Histogram ) و روشهای مبتنی بر خوشه بندی(Clustering-Based) تقسیم کرد. که البته هر کدام از این دو روش دارای زیر مجموعه هایی نیز می باشند. در روشهای مبتنی بر هیستوگرام، بخش بندی تصاویر براساس توزیع پیکسلها صورت می گیرد. قدم اصلی در این روشها یافتن سطح استانه ای مناسب برای اعمال به تصویر میباشد. در روشهای مبتنی بر خوشه بندی برای گروه بندی کردن داده ها از شباهتها و روابط موجود بین آنها استفاده می شود. در این روشها داده ها به نحوی گروه بندی می شوند تا انهایی که در داخل یک بخش قرار می گیرند دارای بیشترین شباهت به هم باشند.

1.2. ﺷﺮاﯾﻂ ﺑﺨﺶﺑﻨﺪی

ﺑﺮای ﺑﺨﺶﺑﻨﺪی ﻫﺮ ﺗﺼﻮﯾﺮ ﺑﺎﯾﺪ ﺷﺮاﯾطی داﺷﺘﻪﺑﺎﺷﯿﻢازجمله:ﻣﺠﻤﻮع ﮐﻞ ﻗﻄﻌﺎت ﮐﻞ ﭘﯿﮑﺴﻠﻬﺎی ﺗﺼﻮﯾﺮ را ﺗﺸﮑﯿﻞ ﻣﯽدﻫﻨﺪ. ﻧﻮاﺣﯽ ﻗﻄﻌﺎت ﻧﺒﺎﯾﺪ ﺗﺪاﺧﻞ داﺷﺘﻪ ﺑﺎﺷﻨﺪ. ﭘﯿﮑﺴﻠﻬﺎی ﻗﻄﻌﺎت ﯾﮑﺴﺎن ﺑﺎﯾﺪ ﺧﻮاص ﯾﮑﺴﺎﻧﯽ داﺷﺘﻪ ﺑﺎﺷﻨﺪ.ﭘﯿﮑﺴﻠﻬﺎی ﻗﻄﻌﺎت ﻣﺘﻔﺎوت ﺑﺎﯾﺪ ﺧﻮاص ﻣﺘﻔﺎوﺗﯽ داﺷﺘﻪ ﺑﺎﺷﻨﺪ. ﭘﯿﮑﺴﻠﻬﺎی ﻗﻄﻌﺎت ﯾﮑﺴﺎنﻣﺮﺗﺒﻂ ﻫﺴﺘﻨﺪ. در ﺑﺨﺶﺑﻨﺪی ﺗﺼﻮﯾﺮ، ﺗﺼﻮﯾﺮ ﺑﻪ ﺗﻌﺪادی ﻧﻮاﺣﯽ ﺗﻘﺴﯿﻢ ﻣﯽﺷﻮد ﮐﻪ اﯾﻦ ﺗﻘﺴﯿﻢ ﺑﻨﺪی ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ وﯾﮋﮔﯽﻫﺎی ﺑﺮداری ﺗﺼﻮﯾﺮ ﻣﺜﻞ رﻧﮓ ﺗﺼﻮﯾﺮ و ﻏﯿﺮه ﺻﻮرت ﻣﯽﮔﯿﺮد .در ﺑﺨﺶﺑﻨﺪی ﻫﺪف ﻣﺎ ﺑﺪﺳﺖ آوردن ﺷﯽء ﯾﺎ اﺷﯿﺎء ﻣﻮرد ﻧﻈﺮ از ﺗﺼﻮﯾﺮ ﻣﯽﺑﺎﺷﺪ.ﯾﮑﯽ از راهﻫﺎی رﺳﯿﺪن ﺑﻪ اﯾﻦ ﻫﺪفﻋﻤﻞ ﻟﺒﻪﯾﺎﺑﯽ ﺗﺼﻮﯾﺮ ﻣﯽﺑﺎﺷﺪ.

اوﻟﯿﻦ ﺗﮑﻨﯿﮏﻫﺎی ﮔﺴﺘﺮش ﺑﺨﺶﺑﻨﺪی ﺗﺼﺎوﯾﺮ، به سال 1965ﺑﺮﻣﯽﮔﺮدد ﮐﻪ ﯾﮏ ﻋﻤﻠﮕﺮ ﺑﺮای ﻟﺒﻪﯾﺎﺑﯽ ﺑﯿﻦ ﻗﺴﻤﺘﻬﺎی ﻣﺨﺘﻠﻒ ﯾﮏ ﺗﺼﻮﯾﺮ اﺳﺘﻔﺎده ﺷﺪ ﮐﻪ ﻟﺒﻪﯾﺎب راﺑﺮت ﻧﺎﻣﯿﺪه ﺷﺪ.اﯾﻦ اوﻟﯿﻦ ﻣﺮﺣﻠﻪ ﺑﺮای ، ﮔﺴﺘﺮش ﺗﺠﺰﯾﻪ ﺗﺼﻮﯾﺮ ﻣﯽﺑﺎﺷﺪ.ﺑﺮ اﺛﺮ دﯾﺪ ﻣﻨﻔﯽ و ﮐﻢﻟﻄﻔﯽ ﻣﺤﻘﻘﺎن ،ﻣﺪﺗﯽ ﺑﺮرﺳﯽ و ﺗﺤﻘﯿﻖ در ﻣﻮرد ﺑﺨﺶﺑﻨﺪی ﺗﺼﺎوﯾﺮ ﺑﻪ ﮐﻨﺪی ﭘﯿﺶ رﻓﺖ اﻣﺎ ﺟﺪﯾﺪأ ﺗﻮﺟﻪ ﺧﺎﺻﯽ ﺑﻪ اﯾﻦ ﻣﺒﺤﺚ ﻣﯽﺷﻮد.

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

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

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

2.2.1 . آﺳﺘﺎﻧﻪ ﮔﯿﺮی روﺷﻨﺎﯾﯽ دو ﺳﻄﺤﯽ

ﺑﯿﺸﺘﺮ ﺗﺼﺎوﯾﺮ ﺷﺎﻣﻞ اﺷﯿﺎء دارای ﺳﻄﺢ روﺷﻨﺎﯾﯽ ﯾﮑﻨﻮاﺧﺖ ﻣﯽ ﺑﺎﺷﻨﺪ ﮐﻪ ﺑـﺮ روی ﯾﮏ ﭘﯿﺶ زﻣﯿﻨﻪ ﺑﺎ ﺳﻄﺢ روﺷـﻨﺎﯾﯽ ﻣﺘﻔـﺎوﺗﯽ ﻗـﺮار دارﻧـﺪ؛ ﺑـﺮای ﻣﺜـﺎل  ﺗﺼﺎوﯾﺮ ﻣﺘﻦ دﺳﺖ ﻧﻮﺷﺘﻪ، ﻣﺘﻦ ﺗﺎﯾﭙﯽ، ﻫﻮاﭘﯿﻤﺎﻫﺎی ﺑﺎﻧﺪ ﻓﺮودﮔﺎه ﻧﻤﻮﻧﻪ ﻫﺎﯾﯽ از اﯾﻦ ﻧﻮع ﻣﯽ ﺑﺎﺷﻨﺪ .ﺑﺮای ﭼﻨﯿﻦ ﺗﺼﺎوﯾﺮی روﺷﻨﺎﯾﯽ، وﯾﮋﮔﯽ ﺗﻔﮑﯿﮏ ﮐﻨﻨـﺪه ای  ﻣﯽ ﺑﺎﺷﺪ ﮐﻪ ﻣﯽ ﺗﻮاﻧﺪ ﺑﺮای ﻗﻄﻌﻪ ﺑﻨﺪی ﺷﯽء از ﭘﯿﺶ زﻣﯿﻨﻪ اش ﺑﻪ ﮐـﺎر ﮔﺮﻓﺘـﻪ   ﺷﻮد.

راﻫﮑﺎر: ﺑﺮای ﻗﻄﻌﻪ ﺑﻨﺪی ﯾﮏ ﺷﯽء ﺳﻔﯿﺪ ﻗﺮار ﮔﺮﻓﺘﻪ ﺑﺮ روی ﭘﯿﺶ زﻣﯿﻨﻪ ﺳﯿﺎه  ﯾﺎ ﺑﺮﻋﮑﺲ، ﺷﯽء ﺳﻔﯿﺪ ﻗﺮار ﮔﺮﻓﺘـﻪ ﺑـﺮ روی ﭘـﯿﺶ زﻣﯿﻨـﻪ ﮐﺎﻓﯿﺴـﺖ ﻣﻘـﺪار آﺳﺘﺎﻧﻪ ی ﻣﻮرد ﻧﻈﺮ را ﻣﯿﺎﻧﻪ ﺳﻄﺢ ﺗﯿﺮﮔﯽ ﻗﺮار دﻫﯿﻢ.

ﺿﻌﻒ :ﻫﺮ ﭼﻨﺪ ﻫﻨﮕﺎﻣﯽ ﮐﻪ ﺗﺼﻮﯾﺮ ﻣﻮرد ﻧﻈﺮ دارای ﻧﻮﯾﺰ ﺑﺎﺷﺪ و ﯾﺎ ﻫﻨﮕﺎﻣﯽ ﮐﻪ ﺷﯽء و ﭘﯿﺶ زﻣﯿﻨﻪ دارای ﻣﻘﺎدﯾﺮ ﺳﻄﺢ ﺗﯿﺮﮔـﯽ ﯾﮑﺴـﺎﻧﯽ ﺑﺎﺷـﻨﺪ، ﻧﻤـﯽ ﺗـﻮان ﺗﺼﻮﯾﺮ را ﺑﺎ ﺑﻪ ﮐﺎرﮔﯿﺮی آﺳﺘﺎﻧﻪ ﺳﻄﺢ ﻣﯿﺎﻧﯽ ﺗﯿﺮﮔﯽ ﮐﺎﻣﻼً ﻗﻄﻌﻪ ﺑﻨﺪی ﻧﻤﻮد.

2.3.2. واﺗﺮﺷﯿﺪ

مفهوم واترشید ،ﻧﮕﺎﺷﺖ ﯾﮏ ﺗﺼﻮﯾﺮ در ﻣﺨﺘﺼﺎت ﺳﻪ ﺑﻌﺪی، ﺷﺎﻣﻞ دو ﻣﺨﺘﺼﺎت ﻓﻀﺎﯾﯽ در ﻣﻘﺎﺑﻞ ﺳﻄﻮح ﺗﯿﺮﮔﯽ ﺑﻪ ﻋﻨﻮان ﺑﻌﺪ ﺳﻮم ﻣﯽ ﺑﺎﺷﺪ.ﻫﺪف اﺻﻠﯽ از اﻟﮕﻮرﯾﺘﻢ ﻫﺎی ﻗﻄﻌﻪ ﺑﻨﺪی ﺑﺮ ﭘﺎﯾﻪ ی ﻣﻔﻬﻮم واﺗﺮﺷﯿﺪ ﭘﯿﺪا ﻧﻤﻮدن ﺧﻄﻮط واﺗﺮﺷﯿﺪ ﯾﺎ ﻫﻤﺎن ﻧﻘﺎط ﺧﻂ اﻟﺮأس ﻣﯽ ﺑﺎﺷﺪ . در ﺣﺎﻟﺖ ﮐﻠّـﯽ دو دﯾـﺪﮔﺎه اﻟﮕـﻮرﯾﺘﻤﯽ  اﺳﺎﺳـﯽ ﺑـﺮای ﻣﺤﺎﺳـﺒﻪ واﺗﺮﺷﯿﺪ ﯾﮏ ﺗﺼﻮﯾﺮ وﺟـﻮد دارد ﮐـﻪ ﻋﺒﺎرﺗﻨـﺪ از:ﺑـﺎرش و ﻏﺮﻗـﻪ   ﺳﺎزی. ﯾﮑﯽ از ﮐﺎرﺑﺮدﻫﺎی اﺻﻠﯽ ﻗﻄﻌﻪ ﺑﻨﺪی واﺗﺮﺷﯿﺪی اﺳﺘﺨﺮاج اﺷـﯿﺎی ﺗﻘﺮﯾﺒﺎً ﯾﮑﻨﻮاﺧﺖ از ﭘﯿﺶ زﻣﯿﻨﻪ ﻣﯽ ﺑﺎﺷﺪ .ﻧﻮاﺣﯽ ﻣﺸﺨّﺺ ﺷـﺪه ﺑـﺎ ﺗﻐﯿﯿــﺮات ﮐﻢ در ﺳـﻄﻮح ﺗﯿﺮﮔـﯽ دارای ﻣﻘـﺎدﯾﺮ ﮔﺮادﯾـﺎن ﮐﻤـﯽ ﻣـﯽ ﺑﺎﺷــﻨﺪ .ﺑﻨــﺎﺑﺮاﯾﻦ، در ﻋﻤــﻞ ﻣــﺎ اﻏﻠــﺐ ﻣــﯽ ﺑﯿﻨــﯿﻢ ﮐــﻪ ﻗﻄﻌﻪ ﺑﻨﺪی واﺗﺮﺷﯿﺪ ﺑﺮای ﮔﺮادﯾﺎن ﯾﮏ ﺗﺼـﻮﯾﺮ ﺑـﯿﺶ ﺗـﺮ از ﺧـﻮد ﺗﺼﻮﯾﺮ ﺑﻪ ﮐﺎر ﮔﺮﻓﺘﻪ ﻣﯽ ﺷﻮد.

الگوریتم ژنتیک

الگوریتم های ژنتیک (GAs) الگوی نسبتا جدیدی برای جستجو ، بر اساس اصول انتخاب مناسب و اصلح در طبیعت بنا شده است. برای اولین بار این الگوریتم توسط جان هلند در سال 1960 معرفی شده است.

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

همانطورکه گفته شد الگوریتم ژنتیک بر اساس اصول انتخاب اصلح در طبیعت بنا شده است . با به کارگرفتن  انتخاب طبیعی از نمونه های مناسب میتوان برای حل مشکلات بهینه سازی استفاده کرد. بهینه سازی از طریق تبادل مواد ژنتیکی طبیعی مابین منشاء موجود انجام می شود .Offsprings شکلی از ژنهای مبدا یا والد است. قابلیت Offsprings مورد ارزیابی قرار میگیرد. به fittest تکبرای تولید تنها اجازه داده می شود.

در جهان کامپیوتر ، ماده ژنتیکی  توسط رشته هایی از بیت ها و انتخاب طبیعی توسط تابع fitness جایگزین میشود. یک نمونه ازعملکرد الگوریتم ژنتیک در قالب فلوچارت زیر می باشد.

شکل1-  یک نمونه ازعملکرد الگوریتم ژنتیک در قالب فلوچارت