شکل ۴-۲ کلاس‌بندی داده‌های مربوط به Fourclass با بهره گرفتن از الگوریتم پیشنهادی ……… ۳۱
فهرست جداول
عنوان صفحه
جدول ۲-۱ مقایسه چند روش مختلف فازی ………………………………………………………………………………. ۲۰
جدول ۴-۱ مشخصات داده‌های مورد استفاده …………………………………………………………………………… ۲۸
جدول ۴-۲ پارامترهای کرنل ………………………………………………………………………………………………………. ۲۸
جدول ۴-۳ مقایسه الگوریتم پیشنهادی و SVM از نظر زمان ………………………………………………….. ۲۸
جدول ۴-۴ مقایسه الگوریتم پیشنهادی و SVMاز نظر دقت …………………………………………………. ۲۹
جدول ۴-۵ مقایسه الگوریتم پیشنهادی و SVM از نظر تعداد بردار پشتیبان ………………………… ۲۹
فصل اول: مقدمه

خوشه‌بندی
خوشه‌بندی داده یکی از رایج‌ترین تکنیک‌های داده‌کاوی^[۱]است.خوشه‌بندی از جمله روش‌های پرکاربرد در تجزیه و تحلیل داده‌ها است. خوشه‌بندی فرایند خودکاری است که نمونه‌ها به دسته هایی که اعضای آنها شبیه هم باشد تقسیم می‌شود که به این دسته‌ ها، خوشه گفته می‌شود. به بیانی دیگر خوشه مجموعه‌ای از اشیا می‌باشد که در آن اشیا با یکدیگر مشابه بوده و با اشیا موجود در خوشه‌های دیگر غیر مشابه می‌باشند.
خوشه‌بندی در زمینه‌های بسیاری از جمله در شناسایی الگو^[۲]، یادگیری ماشین، داده‌کاوی، بازیابی اطلاعات و انفورماتیک زیستی کاربرد دارد. هدف از انجام خوشه‌بندی ارائه چشم انداز مناسبی از اتفاقات در حال وقوع در پایگاه داده‌ها به مصرف کننده نهایی اطلاعات می‌باشد. کاربرد دیگر خوشه‌بندی را می‌توان در تعیین داده‌هایی که با سایر داده‌ها تفاوت چشمگیر دارند عنوان نمود.
در خوشه‌بندی سعی می‌شود جمعی از داده‌ها به صورت بدون ناظر به خوشه‌هایی تقسیم شوند که شباهت داده‌های درون هر خوشه حداکثر و شباهت بین داده‌های درون خوشه‌های مختلف حداقل شود [۵,۶].
الگوریتم‌های خوشه‌بندی [۷,۸] اشیای داده‌ای (طرح‌ها، نهادها، نمونه‎ها، مشاهده‌ها، واحدها) را داخل تعداد خاصی از خوشه‌ها (گروه‌ها، زیر مجموعه‌ها یا مقاله‌ها) تفکیک می‌کنند. اوریت^[۳] (۲۰۰۱) در مورد خوشه‌بندی بیان می‌کند که خوشه‌بندی مجموعه‌ای از نهادهای مشابه است، ولی نهادهای خوشه‏های مختلف شبیه هم نیستند.
برای مشابه بودن می‌توان معیارهای مختلفی را در نظر گرفت مثلا می‌توان معیار فاصله را برای خوشه‌بندی مورد استفاده قرار داد و اشیایی را که به یکدیگر نزدیکتر هستند را به عنوان یک خوشه در نظر گرفت که به این نوع خوشه‌بندی خوشه‌بندی مبتنی بر فاصله نیز گفته می‌شود.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

شکل ۱-۱ : خوشه‌بندی نمونه‌های ورودی[۱]
در شکل ۱-۱ هر یک از نمونه‌های ورودی به یکی از خوشه‌ها تعلق دارد و نمونه‌ای وجود ندارد که متعلق به بیش از یک خوشه باشد. بعنوان یک مثال دیگر شکل ۱-۲ را در نظر بگیرید در این شکل هر یک از دایره های کوچک یک وسیله نقلیه (شیء) را نشان می‌دهد که با ویژگی های وزن و حداکثر سرعت مشخص شده‌اند. هر یک از بیضی‌ها یک خوشه می‌باشد و عبارت کنار هر بیضی برچسب آن خوشه را نشان می‌دهد. کل دستگاه مختصات که نمونه‌ها در آن نشان داده شده‌اند را فضای ویژگی می‌گویند.
cluster
شکل ۱-۲ : خوشه‌بندی وسایل نقلیه [۲]
همانطور که در شکل می‌بینید وسایل نقلیه به سه خوشه تقسیم شده‌اند. برای هر یک از این خوشه‌ها می‌توان یک نماینده در نظر گرفت مثلا می‌توان میانگین وسایل نقلیه باری را محاسبه کرد و بعنوان نماینده خوشه وسایل نقلیه باری معرفی نمود.در واقع الگوریتم‌های خوشه‌بندی اغلب بدین گونه‌اند که یک سری نماینده اولیه برای نمونه‌های ورودی در نظر گرفته می‌شود و سپس از روی میزان تشابه نمونه‌ها با این نماینده‌های مشخص می‌شود که نمونه به کدام خوشه تعلق دارد و بعد از این مرحله نماینده‌های جدید برای هر خوشه محاسبه می‌شود و دوباره نمونه‌ها با این نماینده‌ها مقایسه می‌شوند تا مشخص شود که به کدام خوشه تعلق دارند و این کار آنقدر تکرار می‌شود تا زمانی که نماینده‌های خوشه‌ها تغییری نکنند.
معیارشباهت در خوشه‌بندی : اگر معیار تشابه در تابع هدف بر اساس فاصله تعریف شود می‌توان از تعاریف مختلفی که در مورد فاصله وجود دارد استفاده کرد که در زیر چند نمونه از این توابع آورده شده است.
شکل ۱-۳ : معیارهای تشابه بر اساس توابع فاصله مختلف[۳]

خوشه‌بندی فازی
خوشه‌بندی فازی را می‌توان بخشی از تحلیل داده فازی دانست که دارای دو بخش است: یکی تحلیل داده‌های فازی و دیگری تحلیل داده‌های قطعی با بهره گرفتن از تکنیک‌های فازی.
خوشه‌بندی فازی به کشف مدلهای فازی از داده‌ها می‌پردازد. ایده بنیادین در خوشه‌بندی فازی به این ترتیب است که فرض کنیم هر خوشه مجموعه‌ای از عناصر است. سپس با تغییر در تعریف عضویت عناصردر این مجموعه از حالتی که یک عنصر فقط بتواند عضو یک خوشه باشد به حالتی که هر عنصر می‌تواند با درجه عضویتهای مختلف داخل چندین خوشه قرار بگیرد، دسته بندی‌هایی که انطباق بیشتری با واقعیت دارند ارائه کنیم.
در خوشه‌بندی کلاسیک هر نمونه‌ی ورودی متعلق به یک و فقط یک خوشه می‌باشد و نمی‌تواند عضو دو خوشه و یا بیشتر باشد و به زبان دیگر خوشه‌ها همپوشانی ندارند. حال حالتی را در نظر بگیرید که میزان تشابه یک نمونه با دو خوشه و یا بیشتر یکسان باشد. در خوشه‌بندی کلاسیک باید تصمیم‌گیری شود که این نمونه متعلق به کدام خوشه است. تفاوت اصلی خوشه‌بندی کلاسیک وخوشه‌بندی فازی در این است که یک نمونه می‌تواند متعلق به بیش از یک خوشه باشد[۱]
کاربردهای متعدد خوشه‌بندی فازی در تحلیل داده‌ها و تشخیص الگو و نیز زمینه های پژوهشی موجود در این زمینه از جمله استفاده از آن در حل مسائل مسیریابی، تخصیص و زمان‌بندی نیاز به مطالعه الگوریتم‌های موجود و بهبود و اصلاح آنها را آشکارتر می کند[۴].
۱-۲-۱ الگوریتم‌های پایه‌ای خوشه‌بندی فازی
یکی از اولین روش های خوشه‌بندی فازی که بر مبنای تابع هدف و استفاده از فاصله اقلیدسی بنا شده بود در سال ۱۹۷۴توسط دان ارائه و سپس توسط بزدک تعمیم داده شد. الگوریتم حاصل ابرهای کروی از نقاط را در یک فضای P بعدی شناسایی می کند این خوشه‌ها به طور مفروض تقریباً هم اندازه هستند . هر خوشه با مرکزش نمایش داده می شود. این نحوه نمایش خوشه‌ها،مدل یا نمونه نیز نامیده می شود، زیرا اغلب به عنوان نماینده همه داده‌های تخصیص داده شده به خوشه انگاشته می شو د .در انتخاب مرکز خوشه، مقدار میانگین مورد استفاده قرار می گیرد. برای محاسبه مرکز خوشه مجموع درجات عضویت هر عنصر به توان m در خودش به حاصلضرب توان m درجه عضویت ها تقسیم می‌شود. مشکلی که در ارتباط با این الگوریتم مطرح است این است که الگوریتم نمی‌تواند خوشه‌هایی با اشکال و اندازه ها و چگال ی های متفاوت شناسایی کند. برای شناسایی اشکال دیگر به جای ماتریس همانی در تعیین فاصله می توان از ماتریس های دیگر بهره جست مانند ماتریس قطری برای تشخیص خوشه‌های بیضوی . از مزایای این الگوریتم، سهولت آن است که منجر به کاهش زمان محاسباتی می شود. در عمل با تکرارهای کمی می‌توان به حلی تقریباً نهایی رسید. پس از آن یانگ یک بررسی اجمالی روی روش‌های خوشه‌بندی فازی انجام داد.
با جایگزین کردن فاصله اقلیدسی با متر دیگری (که توسط یک ماتریس متقارن و معین ایجاد شده است) می‌توان به شناسایی خوشه‌های بیضوی نیز دست یافت.این پیشنهاد توسط گوستافسون و کسل در سال ۱۹۷۹ارائه شد.که الگوریتم خوشه‌بندی فازی را با بهره گرفتن از ماتریس کوواریانس فازی ارائه نمودند.
در این روش هر خوشه علاوه بر مرکز خوشه توسط یک ماتریس متقارن، معین و مثبت مشخص می شود. این ماتریس برای هر خوشه یک نرم ایجاد می کند. باید این موضوع را هم در نظر گرفت که با انتخاب دلخواه و اختیاری ماتریس ها، فاصله ها می توانند به طور دلخواه کوچک شوند . برای اجتناب از حداقل سازی تابع هدف با ماتریس های با ورودی های تقریباً صفر، نیاز به مقداری ثابت برای خوشه‌ها با ماتریسی با دترمینان یک داریم . بنابراین حالا فقط شکل خوشه‌ها متغیر است نه اندازه هایشان. اما گوستافسون و کسل اشکال متفاوت برای خوشه‌ها را نیز مقدور ساختند بدین ترتیب که یک مقدار ثابت e برای هر ماتریس A معرفی کردند و در حالت کلی باید det(A)=e .اگرچه انتخاب ثابت ها نیز نیاز به یک دانش پیشین در مورد خوشه‌ها دارد. کیفیت نتیجه حاصل از این روش به شدت وابسته به داده‌های در دسترس است.اشکال بیضوی حاصل از GK در مورد مثال های یکسان با FCM که اشکال کروی حاصل میشد خوشه‌بندی بهتری را حاصل می کند البته موضوع تجمع نقاط در مراکز خوشه‌ها در مورد خوشه بندی امکانی باGK نیز به صورت مسئله باقی میماند. اگر داده‌ها با رویکرد امکان خوشه بندی شوند، فاکتورهای توسعه برای خوشه‌ها می‌توانند برای تشخیص اشکال در تصاویر مورد استفاده قرار گیرند موقعیت و جهت را از مرکز خوشه و ماتریس می توان بدست آورد در مقایسه با FCM هزینه های محاسباتی GK بسیار بیشتر است یک روش پیشنهادی مؤثر در کاهش گام های تکرار و افزایش سرعت همگرایی، آغاز الگوریتمGK با نتایج حاصل از یک بار اجرای FCM است .
تلفیق رویکرد امکان درخوشه‌بندی فازی نخستین بار توسط کیم و کریشناپورام در سال ۱۹۹۳ صورت گرفت. این روش بر معیار وزن η استوار است که در آن از تغییر تابع برازندگی و اضافه شدن وزن‌های ورودی برای کاهش تأثیر داده‌های دور افتاده بر مراکز خوشه‌ها استفاده شده است.
(۱-۱)
در رابطه (۱-۱)، µ تابع عضویت هر نمونه داده،d فاصله اقلیدسی،n تعداد نمونه داده،m یک عدد حقیقی بزرگتر از یک است[۱۶] . تابع برازندگی این الگوریتم به صورت رابطه (۱-۲) در نظر گرفته شده است.
(۱-۲)
(۱-۳)
در رابطه فوق، c تعداد خوشه ‌نهایی، η وزن هر خوشه طبق رابطه (۱-۲)، J تابع برازندگی (هدف) است.
در ‌الگوریتم C میانگین امکانی با در نظر گرفتن وزن η و با بهره گرفتن از رابطه (۱-۳) تعلق (تابع ‌عضویت) برای هر داده‌ای، تأثیر داده‌های دور افتاده را به مراکز خوشه‌ها به حد کمتری می‌رساند و مجموع مولفه هر داده، عددی بین ۰و ۱ خواهد شد، در صورتی که در الگوریتم C میانگین فازی مجموع مولفه هر داده یک است.
(۱-۴)
با بهره گرفتن از رابطه‌‌ (۱-۳) تابع عضویت برای هر داده و رابطه (۱-۴) مراکز خوشه محاسبه می‌شود. تابع برازندگی الگوریتم C میانگین امکانی مقدار بیشتری نسبت به الگوریتم C میانگین فازی ایجاد می‌کند. اما در الگوریتم C میانگین امکانی تعداد مراحل پیدا کردن خوشه ‌نهایی افزایش می‌یابد. اگر در این الگوریتم، خوشه اولیه تصادفی در نظر گرفته نشود و مراکز خوشه‌ها، خوشه‌های نهایی الگوریتم C میانگین فازی در نظر گرفته شود، بیشتر بودن مقدار تابع برازندگی الگوریتم C میانگین امکانی به وضوح دیده شده است.
پس از آن نیز اصلاحات و بهبودهای بسیاری روی الگوریتم‌های ارائه شده صورت گرفته‌اند طبق دسته‌بندی صورت گرفته در این مقاله، الگوریتم‌های پایه‌ای در زمینه خوشه‌بندی فازی محدود به Fuzzy C-Means و Possibilistic C-Means شد که از Hard C-Means که در ادبیات موضوع با عنوان الگوریتم K-Means معرفی شده است استخراج شده اند[۵].
الگوریتم Possibilistic C-Means مشخصه نسبی بودن درجه عضویت احتمالی را بیان می کند.

مشخصه نسبی بودن درجه عضویت احتمالی با وجود مناسب بودن در اکثر مواقع، گاه می تواند ایجاد مشکلاتی نماید[ ۷]. به عنوان نمونه ای از این دسته مشکلات می توان به مورد ذیل اشاره نمود.نقطه از هر دو خوشه به یک فاصله است لذا درجه عضویتش به هر دو خوشه ۵٫ است این منطقی است ولی مشکل وقتی پیش می آید که همان درجه تعلقات به هم داده میشود در حالیکه فاصله این دو نقطه از خوشه‌ها به یک اندازه نیست. دلیل این موضوع نرمال سازی و لزوم برابر یک بودن مجموع درجات عضویت یک نقطه در خوشه‌های مختلف است. نرمال کردن درجات عضویت می تواند منجر به اثرات نامطلوب در ارائه داده‌های پرت و دور از مرکز شود. اگر شرط نرمال سازی را در الگوریتم FCM آزاد کنیم، این اثرات نامطلوب هم کمتر خواهند شد. این رویکرد امکان نام دارد[۸,۹,۱۰] تابع هدف نیز که قبلاً فقط مربع فواصل را حداقل می‌نمود با رویکرد امکان چندان موافق به نظر نمی رسد. با حذف شرط نرمال سازی با اخذ درجات عضویت صفر برای همه نقاط در هر خوشه ای حداقل تابع هدف حاصل می شود و البته این معقول نیست که همه خوش هها خالی باشند. پس بایستی جریمه ای در نظر گرفته شود تا درجات عضویت از صفر دور شوند[۱۰]
الگوریتم k-means توسط مک کویین^[۴] مطرح شد، علی‌ رغم سادگی یک روش پایه برای بسیاری از روش‌های خوشه‌بندی دیگر (مانند خوشه‌بندی فازی) محسوب می‌شود. این روش برای مجموعه داده‌های بزرگ، معمولاً سریع‌ترین راه خوشه‌بندی است برای این الگوریتم شکل‌های مختلفی بیان شده است. ولی همه آنها دارای روال تکراری هستند که برای تعدادی ثابت از خوشه‌ها سعی در تخمین موارد زیر دارند:
بدست آوردن نقاطی به عنوان مراکز خوشه‌ها، این نقاط در واقع همان میانگین نقاط متعلق به هر خوشه هستند.