پایان نامه خوشه بندی فازی داده ها بر اساس منطق فازی

خلاصه پایان نامه خوشه بندی فازی داده ها بر اساس منطق فازی

پایان ‌نامه برای دریافت درجه کارشناسی ارشد رشته مهندسی کامپیوتر - هوش مصنوعی

چکیده

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

SVM یکی از روش‌ های یادگیری با نظارت است که از آن برای دسته‌بندی داده‌ها استفاده می‌شود. SVM شبکه جدید و قدرتمندی است که فرمولی که برای یادگیری استفاده می‌کند بر اساس به حداقل رساندن مقدار خطاست. آموزش SVM ارتباط مستقیم با تعداد داده‌های آموزش دارد و اگرتعداد مراکز خوشه‌ها زیاد باشد زمان آموزش و حجم حافظه به شدت افزایش می‌یابد. شبکه ترکیبی (FS-FCSVM) بدین شکل است که عمل خوشه‌بندی فازی بر روی داده‌های ورودی انجام می‌گیرد سپس پارامتر های شبکه با SVM آموزش می‌بینند، در نتیجه به شبکه ای با قابلیت تعمیم پذیری بالا دست می‌یابد. تعداد قوانین در این گونه سیستم‌ها به نسبت سیستم‌های فازی کوچکتر و زمان محاسبات آن کمتر است .

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

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

نتایج آزمایشات انجام شده بر روی مجموعه دادههای بزرگ پایگاه داده UCI نشان میدهد که علاوه بر کاهش زمان آموزش با انتخاب مناسب داده‌ها باعث تقویت ویزگی مقاوم بودن SVM در برابر داده‌های نویزی و پرت و همچنین کاهش تعداد بردار پشتیبان انتخابی SVM در فضای داده بزرگ می‌شود.

واژه‌های کلیدی: ماشین بردار پشتیبان، خوشه‌ بندی فازی، خوشه‌ بندی تفاضلی.

1 فصل اول: مقدمه

خوشه‌بندی

خوشه‌بندی داده یکی از رایج‌ترین تکنیک‌های داده‌کاوی[1]است.خوشه‌بندی از جمله روش‌های پرکاربرد در تجزیه و تحلیل داده‌ها است. خوشه‌بندی فرآیند خودکاری است که نمونه‌ها به دسته هایی که اعضای آنها شبیه هم باشد تقسیم می‌شود که به این دسته‌ها، خوشه گفته می‌شود. به بیانی دیگر خوشه مجموعه‌ای از اشیا می‌باشد که در آن اشیا با یکدیگر مشابه بوده و با اشیا موجود در خوشه‌های دیگر غیر مشابه می‌باشند.

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

در خوشه‌ بندی سعی می‌شود جمعی از داده‌ها به صورت بدون ناظر به خوشه‌هایی تقسیم شوند که شباهت داده‌های درون هر خوشه حداکثر و شباهت بین داده‌های درون خوشه‌های مختلف حداقل شود [5,6].

الگوریتم‌های خوشه‌بندی [7,8] اشیای داده‌ای (طرح‌ها، نهادها، نمونه‎ها، مشاهده‌ها، واحدها) را داخل تعداد خاصی از خوشه‌ها (گروه‌ها، زیر مجموعه‌ها یا مقاله‌ها) تفکیک می‌کنند. اوریت[3] (2001) در مورد خوشه‌بندی بیان می‌کند که خوشه‌بندی مجموعه‌ای از نهادهای مشابه است، ولی نهادهای خوشه‏های مختلف شبیه هم نیستند.

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

در شکل 1-1 هر یک از نمونه‌های ورودی به یکی از خوشه‌ها تعلق دارد و نمونه‌ای وجود ندارد که متعلق به بیش از یک خوشه باشد. بعنوان یک مثال دیگر شکل 1-2 را در نظر بگیرید در این شکل هر یک از دایره های کوچک یک وسیله نقلیه (شیء) را نشان می‌دهد که با ویژگی های وزن و حداکثر سرعت مشخص شده‌اند. هر یک از بیضی‌ها یک خوشه می‌باشد و عبارت کنار هر بیضی برچسب آن خوشه را نشان می‌دهد. کل دستگاه مختصات که نمونه‌ها در آن نشان داده شده‌اند را فضای ویژگی می‌گویند.

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

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

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

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

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

در خوشه‌بندی کلاسیک هر نمونه‌ی ورودی متعلق به یک و فقط یک خوشه می‌باشد و نمی‌تواند عضو دو خوشه و یا بیشتر باشد و به زبان دیگر خوشه‌ها همپوشانی ندارند. حال حالتی را در نظر بگیرید که میزان تشابه یک نمونه با دو خوشه و یا بیشتر یکسان باشد. در خوشه‌بندی کلاسیک باید تصمیم‌گیری شود که این نمونه متعلق به کدام خوشه است. تفاوت اصلی خوشه‌بندی کلاسیک وخوشه‌بندی فازی در این است که یک نمونه می‌تواند متعلق به بیش از یک خوشه باشد[1]

کاربردهای متعدد خوشه‌بندی فازی در تحلیل داده‌ها و تشخیص الگو و نیز زمینه های پژوهشی موجود در این زمینه از جمله استفاده از آن در حل مسائل مسیریابی، تخصیص و زمان‌بندی نیاز به مطالعه الگوریتم‌های موجود و بهبود و اصلاح آنها را آشکارتر می‌نماید[4].

1-2-1 الگوریتم‌های پایه‌ای خوشه‌بندی فازی

یکی از اولین روشهای خوشه‌بندی فازی که بر مبنای تابع هدف و استفاده از فاصله اقلیدسی بنا شده بود در سال 1974توسط دان ارائه و سپس توسط بزدک تعمیم داده شد. الگوریتم حاصل ابرهای کروی از نقاط را در یک فضای P بعدی شناسایی می کند این خوشه‌ها به طور مفروض تقریباً هم اندازه هستند . هر خوشه با مرکزش نمایش داده می شود. این نحوه نمایش خوشه‌ها،مدل یا نمونه نیز نامیده می شود، زیرا اغلب به عنوان نماینده همه داده‌های تخصیص داده شده به خوشه انگاشته می شو د .در انتخاب مرکز خوشه، مقدار میانگین مورد استفاده قرار می گیرد. برای محاسبه مرکز خوشه مجموع درجات عضویت هر عنصر به توان m در خودش به حاصلضرب توان m درجه عضویت ها تقسیم می‌شود. مشکلی که در ارتباط با این الگوریتم مطرح است این است که الگوریتم نمی‌تواند خوشه‌هایی با اشکال و اندازه ها و چگال ی های متفاوت شناسایی کند. برای شناسایی اشکال دیگر به جای ماتریس همانی در تعیین فاصله می توان از ماتریس های دیگر بهره جست مانند ماتریس قطری برای تشخیص خوشه‌های بیضوی . از مزایای این الگوریتم، سهولت آن است که منجر به کاهش زمان محاسباتی می شود. در عمل با تکرارهای کمی می‌توان به حلی تقریباً نهایی رسید. پس از آن یانگ یک بررسی اجمالی روی روش‌های خوشه‌بندی فازی انجام داد.

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

در این روش هر خوشه علاوه بر مرکز خوشه توسط یک ماتریس متقارن، معین و مثبت مشخص می شود. این ماتریس برای هر خوشه یک نرم ایجاد می کند. باید این موضوع را هم در نظر گرفت که با انتخاب دلخواه و اختیاری ماتریس ها، فاصله ها می توانند به طور دلخواه کوچک شوند . برای اجتناب از حداقل سازی تابع هدف با ماتریس های با ورودی های تقریباً صفر، نیاز به مقداری ثابت برای خوشه‌ها با ماتریسی با دترمینان یک داریم . بنابراین حالا فقط شکل خوشه‌ها متغیر است نه اندازه هایشان. اما گوستافسون و کسل اشکال متفاوت برای خوشه‌ها را نیز مقدور ساختند بدین ترتیب که یک مقدار ثابت e برای هر ماتریس A معرفی کردند و در حالت کلی باید det(A)=e .اگرچه انتخاب ثابت ها نیز نیاز به یک دانش پیشین در مورد خوشه‌ها دارد. کیفیت نتیجه حاصل از این روش به شدت وابسته به داده‌های در دسترس است.اشکال بیضوی حاصل از GK در مورد مثال های یکسان با FCM که اشکال کروی حاصل میشد خوشه‌بندی بهتری را حاصل می کند البته موضوع تجمع نقاط در مراکز خوشه‌ها در مورد خوشه بندی امکانی باGK نیز به صورت مسئله باقی میماند. اگر داده‌ها با رویکرد امکان خوشه بندی شوند، فاکتورهای توسعه برای خوشه‌ها می‌توانند برای تشخیص اشکال در تصاویر مورد استفاده قرار گیرند موقعیت و جهت را از مرکز خوشه و ماتریس می توان بدست آورد در مقایسه با FCM هزینه های محاسباتی GK بسیار بیشتر است یک روش پیشنهادی مؤثر در کاهش گام های تکرار و افزایش سرعت همگرایی، آغاز الگوریتمGK با نتایج حاصل از یک بار اجرای FCM است .

تلفیق رویکرد امکان درخوشه‌بندی فازی نخستین بار توسط کیم و کریشناپورام در سال 1993 صورت گرفت. این روش بر معیار وزن η استوار است که در آن از تغییر تابع برازندگی و اضافه شدن وزن‌های ورودی برای کاهش تأثیر داده‌های دور افتاده بر مراکز خوشه‌ها استفاده شده است.

(فرمول ها در فایل اصلی موجود است )

در رابطه (1-1)، µ تابع عضویت هر نمونه داده،d فاصله اقلیدسی،n تعداد نمونه داده،m یک عدد حقیقی بزرگتر از یک است[16] . تابع برازندگی این الگوریتم به صورت رابطه (1-2) در نظر گرفته شده است.

(فرمول ها در فایل اصلی موجود است )

در رابطه فوق، c تعداد خوشه ‌نهایی، η وزن هر خوشه طبق رابطه (1-2)، J تابع برازندگی (هدف) است.

در ‌الگوریتم C میانگین امکانی با در نظر گرفتن وزن η و با استفاده از رابطه (1-3) تعلق (تابع ‌عضویت) برای هر داده‌ای، تأثیر داده‌های دور افتاده را به مراکز خوشه‌ها به حد کمتری می‌رساند و مجموع مولفه هر داده، عددی بین 0و 1 خواهد شد، در صورتی که در الگوریتم C میانگین فازی مجموع مولفه هر داده یک است.

(فرمول ها در فایل اصلی موجود است )

فهرست پایان نامه خوشه بندی فازی داده ها بر اساس منطق فازی

فهرست:

فصل اول: مقدمه

خوشه‌بندی ....................................................................................................................................... 2

خوشه‌بندی فازی ............................................................................................................................. 5

الگوریتم‌های پایه‌ای خوشه‌بندی فازی ............................................................................... 5

روش کار خوشه‌بندی فازی .................................................................................................... 9

مروری بر مقالات خوشه‌بندی فازی سالهای اخیر .......................................................... 8

خوشه‌بندی تفاضلی ........................................................................................................................ 11

ماشین بردار پشتیبان ................................................................................................................... 12

روش کار ماشین بردار پشتیبان ......................................................................................... 12

ماشین بردار پشتیبان جدایی‌پذیر .................................................................................... 14

ماشین بردار پشتیبان غیرخطی ...................................................................................... 15

فصل دوم: مروری بر کارهای انجام شده

2-1 مقدمه ............................................................................................................................................ 19

2-2 کارهای انجام شده ...................................................................................................................... 19

فصل سوم: روش پیشنهادی

3-1 مقدمه ......................................................................................................................................... 24

3-2 چارچوب کلی روش پیشنهادی .............................................................................................. 24

فصل چهارم: نتایج شبیه‌سازی

4-1 مقدمه ............................................................................................................................................ 28

4-2 پایگاه‌داده و پارامترهای شبیه‌سازی ...................................................................................... 28

فصل پنجم: نتیجه‌گیری و کارهای آینده

5-1 تیجه‌گیری...............................................................................................................................................33

5-2 کارهای آینده.................................................................................................................................. 33

واژه‌نامه ......................................................................................................................................................... 34

مراجع ............................................................................................................................................................ 35

منبع:

[1] Osmar R. Zaïane: “Principles of Knowledge Discovery in Databases - Chapter 8: Data Clustering” .

[2] Pier Luca Lanzi: “Ingegneria della Conoscenza e Sistemi Esperti – Lezione 2: Apprendimento non supervisionato”.

[3] Grossman R.L. and Hornick M.F. and Meyer G., Data mining standards initiatives, Communications of the ACM, Vol 45, No 8, 2002.

[4] F. Hoppner, F.Klawonn, R.Kruse, T.Runkler; Fuzzy Cluster Analysis: Methods for Classification, Data Analysis and Image Recognition, John Wiley & Sons, 2000.

[5] H.Timm, C.Borgelt, C.Do¨Ring,R.Andkruse, “An Extension To Possibilistic Fuzzy Cluster Analysis”, Fuzzy sets And Systems 147, 3–16, 2004.

[6] Chiu, S., "Fuzzy Model Identification Based on Cluster Estimation," Journal of Intelligent & Fuzzy Systems,Vol. 2, No. 3, Sept. 1994.

[7] R.P. Paiva, A. Dourado, Interpretability and learning in neuro-fuzzy systems, Fuzzy Sets Syst. 147 (1) 17–38.2004.

[8]J.C. Dunn; “A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well Separated Clusters”. Journ. Cybern. 3, 95-104, 1974.

[9]J. M. Geusebroek, G. J. Burghouts, and A.W. M.Smeulders. “The Amsterdam library of object images”, Int. J. Comput. Vision, 61(1):103–112, January 2005.

[10] C. Cortes, V. Vapnik, “Support-VectorNetworks”, Machine Learning, Vol. 20, pp. 273-297, 1995.

[11] C.J.C. Burges, “A Tutorial on Support VectorMachines for Pattern Recognition”, Data Miningand Knowledge Discovery, Vol. 2, pp. 121-167,1998.

[12] B. Schölkopf, A.J. Smola, Learning withKernels, MIT Press, Cambridge, MA, 2002.

[13] B. Schölkopf et al., “Comparing SupportVector Machines with Gaussian Kernels to RadialBasis Function Classifiers”, IEEE Trans. on SignalProcessing, Vol. 45, No. 11, pp. 2758-2765, Nov.1997.

[14] C.-F. Lin, S.-D. Wang, “Fuzzy Support VectorMachines”, IEEE Trans. on Neural Networks, Vol.13, No. 2, pp. 464-471, March 2002.

[15] S. Abe, T. Inoue, “Fuzzy Support VectorMachines for Multiclass Problems”, EuropeanSymposium on Artificial Neural Networks(ESANN’2002), pp. 113-118, Bruges, Belgium,April 2002.

[16] C. Juang, Member, IEEE, S. Chiu, and S. Shiu, “Fuzzy System Learned Through Fuzzy Clustering and Support Vector Machine for Human Skin Color Segmentation,” IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART A: SYSTEMS AND HUMANS, VOL. 37, NO. 6, NOVEMBER 2007.

[17] S.Chen, Senior Member, IEEE, and Y. Chang “A New Method for Weighted Fuzzy Interpolative Reasoning Based on Weights-Learning Techniques” vol. 12, no. 12, pp. 820-832, 2004.

[18] E. I. Papageorgiou, Ath. Markinos, and Th. Gemtos, “Learning Algorithms for Fuzzy Cognitive” IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 42, NO. 2, MARCH 2012.

[19] H.-P. Huang, Y.-H. Liu, “Fuzzy SupportVector Machines for Pattern Recognition and DataMining”, International Journal of Fuzzy Systems,Vol. 4, No. 3, pp. 826-835, Sep. 2002.

[20] J. Platt, “Fast training of support vector machines using sequential minimal optimization,” in Advances in Kernel Methods-Support Vector Learning, B. Schölkopf, C. Burges, and A. Smola, Eds. Cambridge,MA: MIT Press, 1999, pp.185–208.

[21] Ftp.ics.uci.edu/pub.

تگ‌ها

الگوریتم های خوشه بندی - خوشه بندی فازی داده - خوشه‌ بندی تفاضلی - خوشه‌ بندی فازی - منطق فازی