چکیدهخوشهبندی داده‌ها روشی برای دسته‌بندی داده‌های مشابه می باشد که این روش سال‌ها در علوم مختلف به کار رفته و الگوریتم‌های زیادی در این زمینه طراحی شده است . تحقیقات اخیر خوشه‌بندی به سمت روش های ترکیبی که دارای قابلیت استحکام و دقت بیشتر هستند، هدایت می‌کند. خوشه‌بندی ترکیبی سعی می‌کند ابتدا خوشه‌بندی های اولیه تولید کند که تا حد ممکن دارای پراکندگی باشند سپس با اعمال یک تابع توافقی نتایج را با هم ترکیب می‌کند. در این پژوهش از ترکیب خوشه‌بندی فازی و ماشین بردار پشتیبان برای دسته‌بندی استفاده می‌شود.SVM یکی از روش‌های یادگیری با نظارت است که از آن برای دسته‌بندی داده‌ها استفاده می‌شود. SVM شبکه جدید و قدرتمندی است که فرمولی که برای یادگیری استفاده می‌کند بر اساس به حداقل رساندن مقدار خطاست. آموزش SVM ارتباط مستقیم با تعداد داده‌های آموزش دارد و اگرتعداد مراکز خوشه‌ها زیاد باشد زمان آموزش و حجم حافظه به شدت افزایش می‌یابد. شبکه ترکیبی (FS-FCSVM) بدین شکل است که عمل خوشه‌بندی فازیبر روی داده‌های ورودی انجام می‌گیرد سپس پارامتر های شبکه با SVM آموزش می‌بینند، در نتیجه به شبکه ای با قابلیت تعمیم پذیری بالا دست می‌یابد. تعداد قوانین در این گونه سیستم‌ها به نسبت سیستم‌های فازی کوچکتر و زمان محاسبات آن کمتر است .در این پژوهش از روش خوشه‌بندی کاهشی قبل از خوشه‌بندی فازی استفاده می‌شود.ایده اصلی خوشه‌بندی کاهشی جستجوی نواحی با چگالی بالا در فضای مشخصه اطلاعات داده‌ها است. هر نقطه که بیشترین تعداد همسایه را داشته باشد به عنوان مرکز خوشه انتخاب می‌شود.بعبارت دیگر با استفاده از تکنیک خوشه‌بندی کاهشی جهت انتخاب نقاط ویژگی که دارای تمایز بیشتر و شباهت کمتر نسبت به دیگر نقاط دارند استفاده شده است.در این پایان نامه ایده کار استفاده از خوشه‌بندی تفاضلی جهت پیدا کردن دقیق نقاط مرکزی خوشه‌ها و تعداد خوشه‌هاست که با این کار تعداد تکرار خوشه‌بندی فازی را کاهش می دهیم و همچنین از همین نقاط مرکزی به عنوان بخشی ازداده‌های آموزشی استفاده می کنیم و بخش دوم کار مربوط به انتخاب قسمت دیگر داده‌های آموزشی می‌باشد که برای انتخاب آنها نیز از ماتریس تعلق حاصل از خوشه‌بندی فازی بهره گرفته ایم که با تعیین یک محدوده عددی داده‌های دور از مرکز هر داده را نیز به عنوان بخش دیگر داده‌ها انتخاب کردیم که نهایتا با انتخاب این نقاط توانستیم تعداد داده‌های آموزشی را تا حد قابل ملاحظه ای تقلیل دهیم.نتایجآزمایشاتانجامشدهبررويمجموعهدادههايبزرگپایگاهداده UCI نشان میدهد که علاوه بر کاهش زمان آموزش با انتخاب مناسب داده‌ها باعث تقویت ویزگی مقاوم بودن SVM در برابر داده‌های نویزی و پرت و همچنین کاهش تعداد بردار پشتیبان انتخابی SVM در فضای داده بزرگ می‌شود. واژه‌های کلیدی:ماشین بردار پشتیبان، خوشه‌بندی فازی، خوشه‌بندی تفاضلی. فهرست مطالبعنوان صفحهفصل اول: مقدمه1-1 خوشه‌بندی ....................................................................................................................................... 21-2 خوشه‌بندی فازی ............................................................................................................................. 51-2-1 الگوریتم‌های پایه‌ای خوشه‌بندی فازی ............................................................................... 51-2-2 روش کار خوشه‌بندی فازی .................................................................................................... 91-2-3 مروريبرمقالات خوشه‌بندی فازیسالهاياخير .......................................................... 81-3 خوشه‌بندی تفاضلی ........................................................................................................................ 111-4 ماشین بردار پشتیبان ................................................................................................................... 121-4-1 روش کار ماشین بردار پشتیبان ......................................................................................... 121-4-2 ماشین بردار پشتیبان جدایی‌پذیر .................................................................................... 141-4-3 ماشین بردار پشتیبان غیرخطی ...................................................................................... 15فصل دوم: مروری بر کارهای انجام شده2-1 مقدمه ............................................................................................................................................ 192-2 کارهای انجام شده ...................................................................................................................... 19فصل سوم: روش پیشنهادی3-1 مقدمه ......................................................................................................................................... 243-2 چارچوب کلی روش پیشنهادی .............................................................................................. 24فصل چهارم: نتایج شبیه‌سازی4-1 مقدمه ............................................................................................................................................ 284-2 پایگاه‌داده و پارامترهای شبیه‌سازی ...................................................................................... 28فصل پنجم: نتیجه‌گیری و کارهای آینده5-1 تیجه‌گیری...............................................................................................................................................335-2 کارهای آینده.................................................................................................................................. 33واژه‌نامه ......................................................................................................................................................... 34مراجع ............................................................................................................................................................ 35 فهرست اشكالعنوان صفحهشکل 1-1 خوشه‌بندی نمونه‌های ورودی ..............................................................................................................3شکل 1-2 خوشه‌بندی وسایل نقلیه .................................................................................................................. 3شکل 1-3 معیارهای تشابه بر اساس توابع فاصله مختلف ............................................................................. 4شکل 1-4 روش کار خوشه‌بندی فازی ................................................................................................................ 9شکل 2-1 مقایسه دو روش FNN و SVM................................................................................................ 20شکل 2-2 مقایسه وزن‌ها به روش درونیابی و ژنتیک ..................................................................................... 21شکل 2-3 خوشه‌بندی مثلثی داده‌ها ............................................................................................................ 22شکل 3-1 نمودار چارچوب کلی طرح پیشنهادی ........................................................................................ 24شکل 4-1 اجرای الگوریتم GRID SEARCH برای تعیین پارامترهای کرنل در SVM .......... 30شکل 4-2 کلاس‌بندی داده‌های مربوط به Fourclass با استفاده از الگوریتم پیشنهادی ......... 31 فهرست جداولعنوان صفحهجدول 2-1 مقایسه چند روش مختلف فازی ........................................................................................... 20جدول 4-1 مشخصات داده‌های مورد استفاده ....................................................................................... 28جدول 4-2 پارامترهای کرنل ...................................................................................................................... 28جدول 4-3 مقایسه الگوریتم پیشنهادی و SVM از نظر زمان ........................................................... 28جدول 4-4 مقایسه الگوریتم پیشنهادی و SVMاز نظر دقت .......................................................... 29جدول 4-5 مقایسه الگوریتم پیشنهادی و SVM از نظر تعداد بردار پشتیبان .............................. 29 1 فصل اول: مقدمه 1-1 خوشهبندیخوشهبنديدادهيكيازرايجترينتكنيكهايدادهكاوي[1]است.خوشه‌بنديازجملهروش‌هايپرکاربرددر تجزیه و تحلیل داده‌ها است. خوشه‌بندی فرآیند خودکاری است که نمونه‌ها به دسته هایی که اعضای آنها شبیه هم باشد تقسیم می‌شود که به این دسته‌ها، خوشه گفته می‌شود. به بیانی دیگر خوشه مجموعه‌ای از اشیا می‌باشد که در آن اشیا با یکدیگر مشابه بوده و با اشیا موجود در خوشه‌های دیگر غیر مشابه می‌باشند.خوشه‌بنديدرزمينه‌هايبسياريازجملهدرشناساييالگو[2]،يادگيريماشين،داده‌كاوي،بازيابياطلاعاتوانفورماتيكزيستيكاربرددارد. هدفازانجامخوشه‌بنديارائهچشماندازمناسبيازاتفاقاتدرحالوقوعدرپايگاهداده‌هابه مصرفكنندةنهايياطلاعاتمي‌باشد. كاربردديگرخوشه‌بنديرا می‌تواندرتعيينداده‌هاييكهباسايرداده‌هاتفاوتچشمگيردارندعنواننمود.درخوشه‌بنديسعيمي‌شودجمعيازداده‌ها بهصورتبدونناظربهخوشه‌هاييتقسيمشوندكهشباهت داده‌هايدرونهرخوشهحداكثروشباهتبينداده‌هاي درونخوشه‌هايمختلفحداقلشود [5,6].الگوریتم‌های خوشه‌بندی [7,8] اشیای داده‌ای (طرح‌ها، نهادها، نمونه‌ها، مشاهده‌ها، واحدها) را داخل تعداد خاصی از خوشه‌ها (گروه‌ها، زیر مجموعه‌ها یا مقاله‌ها) تفکیک می‌کنند. اوریت[3] (2001) در مورد خوشه‌بندی بیان می‌کند که خوشه‌بندی مجموعه‌ای از نهادهای مشابه است، ولی نهادهای خوشه‌های مختلف شبیه هم نیستند.برای مشابه بودن می‌توان معیارهای مختلفی را در نظر گرفت مثلا می‌توان معیار فاصله را برای خوشه‌بندی مورد استفاده قرار داد و اشیایی را که به یکدیگر نزدیکتر هستند را به عنوان یک خوشه در نظر گرفت که به این نوع خوشه‌بندی خوشه‌بندی مبتنی بر فاصله نیز گفته می‌شود.شکل 1-1 : خوشه‌بندی نمونه‌های ورودی[1]در شکل 1-1 هر یک از نمونه‌های ورودی به یکی از خوشه‌ها تعلق دارد و نمونه‌ای وجود ندارد که متعلق به بیش از یک خوشه باشد. بعنوان یک مثال دیگر شکل 1-2 را در نظر بگیرید در این شکل هر یک از دایره های کوچک یک وسیله نقلیه (شیء) را نشان میدهد که با ویژگی های وزن و حداکثر سرعت مشخص شده‌اند. هر یک از بیضی‌ها یک خوشه می‌باشد و عبارت کنار هر بیضی برچسب آن خوشه را نشان میدهد. کل دستگاه مختصات که نمونه‌ها در آن نشان داده شده‌اند را فضای ویژگی می‌گویند.clusterشکل 1-2 : خوشه‌بندی وسایل نقلیه [2]همانطور که در شکل می‌بینید وسایل نقلیه به سه خوشه تقسیم شده‌اند. برای هر یک از این خوشه‌ها می‌توان یک نماینده در نظر گرفت مثلا می‌توان میانگین وسایل نقلیه باری را محاسبه کرد و بعنوان نماینده خوشه وسایل نقلیه باری معرفی نمود.در واقع الگوریتم‌های خوشه‌بندی اغلب بدین گونه‌اند که یک سری نماینده اولیه برای نمونه‌های ورودی در نظر گرفته می‌شود و سپس از روی میزان تشابه نمونه‌ها با این نماینده‌های مشخص می‌شود که نمونه به کدام خوشه تعلق دارد و بعد از این مرحله نماینده‌های جدید برای هر خوشه محاسبه می‌شود و دوباره نمونه‌ها با این نماینده‌ها مقایسه می‌شوند تا مشخص شود که به کدام خوشه تعلق دارند و این کار آنقدر تکرار می‌شود تا زمانی که نماینده‌های خوشه‌ها تغییری نکنند.معیارشباهت در خوشه‌بندی : اگر معیار تشابه در تابع هدفبر اساس فاصله تعریف شود می‌توان از تعاریف مختلفی که در مورد فاصله وجود دارد استفاده کرد که در زیر چند نمونه از این توابع آورده شده است. شکل 1-3 : معیارهای تشابه بر اساس توابع فاصله مختلف[3]1-2 خوشه‌بندی فازیخوشهبنديفازيراميتوانبخشيازتحليلدادهفازيدانستكهدارايدوبخشاست: يكيتحليلداده‌هايفازيوديگريتحليلداده‌هاي قطعيبااستفادهازتكنيك‌هايفازي.خوشه‌بنديفازيبهكشفمدلهايفازيازداده‌هامي‌پردازد.ایده بنياديندرخوشه‌بنديفازيبهاينترتيباستكهفرضكنيمهرخوشهمجموعه‌ايازعناصراست. سپسباتغييردرتعريفعضويتعناصردراينمجموعهازحالتيكهيكعنصرفقطبتواندعضويكخوشهباشد بهحالتيكههرعنصرمي‌تواندبادرجهعضويتهايمختلف داخلچندينخوشهقراربگيرد،دستهبندي‌هاييكهانطباقبيشتريباواقعيتدارندارائهكنيم.درخوشه‌بندیکلاسیکهرنمونه‌یورودیمتعلقبهیکوفقطیکخوشهمی‌باشدو نمی‌تواندعضودوخوشهویابیشترباشدوبهزباندیگرخوشه‌هاهمپوشانیندارند. حالحالتیرادرنظربگیریدکهمیزانتشابهیکنمونهبادوخوشه ویابیشتریکسانباشد. درخوشه‌بندیکلاسیکبایدتصمیم‌گیریشودکهایننمونهمتعلقبهکدامخوشهاست. تفاوتاصلیخوشه‌بندیکلاسیکوخوشه‌بندیفازیدرایناستکهیکنمونهمی‌تواندمتعلقبهبیشازیکخوشهباشد[1]كاربردهايمتعددخوشه‌بنديفازيدرتحليلداده‌هاوتشخيص الگوونيززمينههايپژوهشيموجوددراينزمينهازجملهاستفادهازآندرحلمسائلمسيريابي،تخصيصوزمان‌بندینيازبهمطالعه الگوريتم‌هايموجودوبهبودواصلاحآنهاراآشكارترمي‌نمايد[4].1-2-1 الگوریتم‌های پایه‌ای خوشه‌بندی فازیيكيازاولينروشهايخوشهبنديفازيكهبرمبنايتابعهدفواستفادهازفاصلهاقليدسيبناشدهبود درسال 1974توسطدانارائهوسپستوسطبزدكتعميمدادهشد. الگوریتم حاصل ابرهای کروی از نقاط را در یک فضای P بعدی شناسایی می کند اينخوشه‌هابهطورمفروضتقريباًهماندازههستند . هرخوشهبا مركزشنمايشدادهميشود. ايننحوهنمايشخوشه‌ها،مدليانمونه نيزناميدهميشود،زيرااغلببهعنواننمايندههمهداده‌هايتخصيصداده شدهبهخوشهانگاشتهميشود .درانتخابمركز خوشه،مقدارميانگينمورداستفادهقرارميگيرد. برايمحاسبهمركزخوشهمجموعدرجاتعضويتهر عنصر به توان m در خودش به حاصلضرب توان m درجه عضویت ها تقسیم می‌شود. مشكليكهدرارتباطبااينالگوريتممطرحاستايناستكهالگوريتمنمي‌تواندخوشه‌هاييبااشكالواندازههاوچگاليهايمتفاوتشناسايي كند. برايشناسايياشكالديگربهجايماتريسهمانيدرتعيينفاصلهميتوانازماتريسهايديگربهرهجستمانندماتريسقطريبرايتشخيص خوشه‌هايبيضوي . ازمزاياياينالگوريتم،سهولتآناستكهمنجربهكاهشزمانمحاسباتيميشود. درعملباتكرارهايكميمي‌توانبهحلي تقريباًنهاييرسيد. پسازآنيانگيكبررسياجماليرويروش‌هايخوشه‌بنديفازيانجامداد.