منبع پایان نامه ارشد با موضوع مشاهده عمل و مؤلفه های

2-2-8- خوشهبندی همپوشانی
مسائل خوشهبندی از یک دیدگاه میتواند به دو گروه تقسیم شود: خوشه بندی سخت (خوشه بندی پیچیده) و خوشه بندی فازی (خوشه بندی  نرم یا همپوشی ). در خوشهبندی سخت یک داده به یک و فقط یک خوشه تعلق میگیرد. درحالیکه در خوشه بندی فازی یک نقطه داده ممکن است به دو خوشه یا بیشتر تعلق داشته باشد. الگوریتم Fuzzy c-means نمونه ای از الگوریتم همپوشی است که در ادامه بیان می شود.
Widget not in any sidebars

2-2-8-1- خوشهبندی فازی
در خوشهبندی کلاسـیک هر نمونه ورودی متعلق به یـک و فقط یک خوشه میباشد و نمیتواند عضو دو خوشه و یا بیشتر باشد. بهعبارت دیگر، خوشهها همپوشانی ندارند[32]،[33]،[34]. حال حالتی را در نظر بگیرید که میزان تشابه یک نمونه با دو خوشه و یا بیشتر یکسان باشد. در چنین حالتی، در خوشهبندی کلاسیک بهدلیل آنکه هر نمونه باید به یک و فقط یک خوشه متعلق باشد، باید تصمیمگیری شود که این نمونه متعلق به کدام خوشه است. تفاوت اصلی خوشهبندی کلاسیک و خوشهبندی فازی در همین جا است که در خوشه بندی فازی یک نمونه می تواند متعلق به بیش از یک خوشه باشد. برای روشن شدن مطلب شکل زیر را در نظر بگیرید:
شکل2-5 مجموعه داده پروانهای
اگر نمونههای ورودی مطابق شکل فوق باشند مشخص است که می توان دادهها را به دو خوشه تقسیم کرد. اما مشکلی که پیش میآید این است که دادهی مشخص شده در وسط میتواند عضو هر دو خوشه باشد. بنابراین، باید تصمیم گرفت که دادهی مورد نظر متعلق به کدام خوشه است؛ خوشهی سمت راست یا خوشهی سمت چپ. اما اگر از خوشه بندی فازی استفاده کنیم، دادهی مورد نظر با تعلق 0.5 عضو خوشهی سمت راست و با تعلق مشابه عضو خوشهی سمت چپ است. تفاوت دیگر در این است که مثلاً نمونه های ورودی در سمت راست شکل می توانند با یک درجه تعلق خیلی کم عضو خوشهی سمت چپ نیز باشند که همین موضوع برای نمونه های سمت چپ نیز صادق است.
زمانی که در سال 1965 پروفسور لطفی‌زاده، استاد ایرانی‌الاصل دانشگاه برکلی، اولین مقاله خود را در زمینهی فازی تحت عنوان مجموعه‌های فازی منتشر کرد، هیچ کس باور نداشت که این جرقه‌ای خواهد بود که دنیای ریاضیات را به طور کلی تغییر دهد.
یکی از مهمترین و پرکاربردترین الگوریتمهای خوشهبندی فازی، الگوریتم c میانگین میباشد[35]. در این الگوریتم نمونهها به c خوشه تقسیم میشوند به گونهای که تعداد c از قبل مشخص شده باشد. در نسخه فازی این الگوریتم نیز تعداد خوشهها (c) از قبل مشخص شده است. در الگوریتم خوشه بندی c میانگین فازی تابع هدف بصورت زیر می باشد:
(2-8)
در فرمول فوق m یک عدد حقیقی بزرگتر از 1 است که در اکثر موراد برای m عدد 2 انتخاب میشود. اگر در فرمول فوق m را برابر 1 قرار دهیم تابع هدف خوشهبندی c میانگین (کلاسیک) غیرفازی بهدست میآید. در فرمول فوق نمونه ام ونماینده یا مرکز خوشه ام و تعداد نمونـهها میباشد. میـزان تعلق نمونه ام در خوشه ام را نشان می دهد. علامت ||*|| میزان تشابه (فاصله) نمونه با (از) مرکز خوشه میباشد که میتوان از هر تابعی که بیانگر تشابه نمونه و مرکز خوشه باشد، استفاده کرد. از روی میتوان یک ماتریس تعریف کرد که دارای سطر وستون میباشد و مؤلفههای آن هر مقداری بین صفر تا 1 را میتوانند اختیار کنند. اگر تمامی مؤلفههای ماتریس به صورت صفر و 1 باشند، الگوریتم مشابه c میانگین کلاسیک خواهد بود. با اینکه مؤلفه های ماتریس می توانند هر مقداری بین صفر تا 1 را اختیار کنند، اما مجموع مؤلفههای هر یک از ستونها باید برابر 1 باشد و داریم:
(2-9)
این شرط به این معنا است که مجموع تعلق هر نمونه به c خوشه باید برابر 1 باشد. برای بهدست آوردن فرمولهای مربوط به و باید تابع هدف تعریف شده، حداقل گردد. با استفاده از شرط فوق و برابر صفر قرار دادن مشتق تابع هدف خواهیم داشت:
(2-10)
(2-11)

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

با اسـتفاده از دو فرمول فوق، مراحل انجام الگوریتم خوشـهبندی c میانگین فازی بصورت زیر می باشد:
مرحلهی اول: مقدار دهی اولیه برایc، m و U، با توجه به قید 2-9.
مرحلهی دوم: مراکز خوشه ها با استفاده از فرمول 2-10 محاسبه شوند.
مرحلهی سوم: محاسبهی تابع هدف با توجه به فرمول 2-8. در صورتیکه از مقدار آستانهایکوچکتر است، الگوریتم خاتمه یابد در غیر اینصورت برو به مرحلهی دوم.
مرحلهی چهارم: محاسبهی مقدار جدید با استفاده از فرمول 2-11.
برای مشاهده عملکرد خوشهبندی فازی به مثال زیر توجه کنید. در شکل 2-6 یک توزیع یک بعدی از نمونههای ورودی آورده شده است.
شکل 2-6 توزیع یک بعدی نمونه ها.
اگر از الگوریتم c میانگین کلاسیک استفاده کنیم دادههای فوق به دو خوشهی مجزا تقسیم خواهند شد و هر نمونه تنها متعلق به یکی از خوشهها خواهد بود. بهعبارت دیگر، تابع تعلق هر نمونه مقدار صفر یا 1 خواهد داشت. نتیجهی خوشه بندی کلاسیک در شکل 2- 7نشان داده شده است:
شکل 27 خوشه بندی کلاسیک نمونه های ورودی.