دانلود ‫پروژه فازی - الگوریتم genetic fuzzy k-Modes برای خوشه بندی داده های گروهی

خوشه بندی روشی است که داده های یک مجموعه داده را به گروه یا خوشه تقسیم می کند .

از مرسوم ترین روش های خوشه بندی،الگوریتم های خوشه بندی k-Means وfuzzy k-Means می باشند.این دو الگوریتم فقط روی داده های عددی عمل می کنند و به منظور رفع این محدودیت، الگوریتم های k-Modes و fuzzy k-Modes ارائه شدند که مجموعه داده های گروهی (دسته ای) را نیز خوشه بندی می کنند.

.

با این وجود، این الگوریتم ها ،شبیه همه روال های بهینه سازی دیگر که برای مینیمم عمومی یک تابع جستجو می کنند، احتمال گیر افتادن در یک مینیمم محلی وجود دارد.

به منظوردستیابی به جوبب بهینه عمومی ، الگوریتم های تکاملی مانند ژنتیک و جدول جستجو با الگوریتم های مذکور ترکیب می شوند.

در این پژوهش، الگوریتم ژنتیک ، GA، را با الگوریتم fuzzy k-Modes ترکیب شده ،بطوریکه عملگر ادغام به عنوان یک مرحله از الگوریتم fuzzy k-Modes تعریف می شود.

آزمایش ها روی دو مجموعه داده واقعی انجام شده است تا همراه با مثال کارایی الگوریتم پیشنهادی را روشن نماید.
به عنوان یک ابزار اولیه در داده کاوی ،تجزیه و تحلیل خوشه ، که تجزیه و تحلیل سگمنت نیز نامیده می شود،روشی است که داده ها را به گروه هایی همگن تحت عنوان خوشه تقسیم می کند.در چنین روشی داده های موجود در یک کلاستر یا خوشه خیلی شبیه به هم و داده ها ی کلاستر های مختلف خیلی متفاوت نسبت به هم هستند.اغلب، شباهت بر مبنای معیار فاصله می باشد.
آنالیز خوشه،خوشه بندی، تکنیک عمومی برای آنالیز داده های آماری می باشد که در بسیاری زمینه ها مانند یادگیری ماشین ، داده کاوی ، شناسایی الگو و آنالیز تصویر کاربرد دارد.در کنار اصطلاح خوشه بندی داده (یا فقط خوشه بندی)،بعضی اصطلاحات دیگرنیزهمانند کلاس بندی اتوماتیک ،طبقه بندی عددی ، آنالیز نوع شناسی ، با معنای مشابه استفاده می شود[1].
به طور کلی ،یک الگوریتم خوشه بندی خوب معمولا برای طراحی شامل چهار فاز ذیل را شامل می شود:1- نمایش داده 2- مدل کردن .3- بهینه سازی .4- اعتبار سنجی[2] ..
فاز نمایش داده، تعیین می کند که چه نوعی از ساختارهای خوشه می تواند داده ها را شناسایی کند.سپس فاز مدلینگ ضوابط و معیار ها را برروی ساختار تعریف می کند بطوریکه که ساختارها ی گروه های مطلوب را از موارد نامطلوب مجزا می کند.در فاز مدلینگ ، در طول جستجو برای ساختار های مخفی در داده ،یک معیار کیفیت مانند معیار بهینه سازی یا معیار تقریب تولید می شود.

بعبارتی دیگرفاز بهینه سازش،ساختار های موثرتر و بهینه تر را انتخاب میکند.

از آنجا که فرآیند خوشه بندی ،یک فرایند بدون سرپرستی است فاز اعتبار سنجی خیلی ضروری است تا نتایج تولید شده به وسیله الگوریتم خوشه بندی ارزیابی شوند.
به طور کلی ،الگوریتم های خوشه بندی به دو دسته تقسیم بندی می شوند[3,4] : الگوریتم های خوشه بندی سخت و الگوریتم های خوشه بندی فازی .
در چهارچوب خوشه بندی سخت ،هر شی ء به یک و فقط یک خوشه تعلق دارد و برعکس در چهار چوب خوشه بندی فازی به هر شی ء اجازه داده می شود که توابع تعلقی به همه خوشه ها داشته باشد.هر دو روش الگوریتم خوشه بندی سخت و فازی ،مرکز های خوشه (نمونه های اولیه) را تعیین می کنند و مجموع مربع فاصله بین این مرکز ها و خوشه ها را مینیمم می کنند.
بسیاری از الگوریتم ها به منظور دستیابی به خوشه بندی سخت در یک مجموعه داده پیشرفت داده شده اند.در بین آنها الگوریتم k-meansو روش های خوشه بندی IsoData به طور گسترده ای مورد استفاده گرفته اند.این دو الگوریتم بر پایه تکرار می باشند.

کاربرد مجموعه های فازی در توابع کلاس بندی موجب می شود هر داده در یک زمان به چندین کلاس با درجه های متفاوت تعلق داشته باشد[3].
معروف ترین و پرکاربردترین الگوریتم خوشه بندی فازی ،الگوریتم fuzzy C-Means [7] است.

الگوریتم fuzzy C-Means با یک مقدار اولیه از Wشروع می شود و مکررا بین تخمین مراکز خوشه Z داده شده درZ و تخمین ماتریس تعلق داده شده درW تکرار می شود تا هنگامیکه دو مقدار متوالی از Z یا W مساوی شوند.
از نظر ریاضی ،یک مسئله خوشه بندی فازی را می توان به صورت یک مسئله بهینه سازی به صورت ذیل نمایش داد.[5,6]
F(W,Z)= به طوریکه 0 که n تعداد اشیاء در مجموعه داده مورد بررسی وk تعداد خوشه ها است .مجموعه از n شی ء است که هر یک با d ویژگی توصیف می شوند.

Z یک مجموعه با k مرکز کلاستر ، W یک ماتریس تعلق فازی و توان وزن و d معیار فاصله معین بین مرکز خوشه و شی ء می باشد.

از آنجا که الگوریتم fuzzy c-Means فقط روی داده های عددی کار می کند،یک الگوریتم fuzzy k-Modes را به منظور خوشه بندی مجموعه داده های گروهی پیشنهاد می دهیم [6-9] .

با این وجود،این الگوریتم ها ،شبیه همه روال های بهینه سازی دیگر که برای مینیمم عمومی یک تابع جستجو می کنند، احتمال گیر افتادن در یک مینیمم محلی وجود دارد.

برای مسئله بهینه سازی ،یک مسئله شناخته شده وابسته به هر دو الگوریتم fuzzy C-Means و fuzzy k-Modes این است که آنها ممکن است روی بهینه محلی متوقف شوند[5] .برای رفع این مشکل و رسیدن به یک راه حل عمومی،تکنیک های بر پایه الگوریتم های ژنتیک و تابو سرچ به کار برده شده اند.

برای مثال ،الگوریتم genetic k-Means،الگوریتم genetic و الگوریتمk-Means را ترکیب می کند بدین منظورکه راه حل عمومی و بهینه را پیدا کند[10].به منظور پیدا کردن راه حل بهینه عمومی برای الگوریتم fuzzy k-Modes،Ng و Wong تابو سرچ را بر پایه الگوریتم fuzzy k-Modes معرفی کردند[11].

هدف اصلی در این پروژه این است که الگوریتم genetic fuzzy k-Modes را بکار ببریم تا الگوریتم های fuzzy k-Modes و genetic را به منظور پیدا کردن راه حل بهینه در مسئله بهینه سازی ترکیب کند[5].

طرح کلی پروژه به صورت ذیل است که در قسمت 2، مروری برکارهای قبل و دیگر روش ها خواهیم داشت .بدین صورت که ابتدا الگوریتم های k-means, fuzzy C-means,k-modes,fuzzy k-modes با جزییات شرح می دهیم که مقدمه ای از روال کلی رسیدن به الگوریتم مورد بررسی در این مقاله هستند.

سپس در قسمت 3 ،روش پیشنهادی مان،الگوریتم ترکیبی genetic fuzzy k-Modes را تشریح می کنیم.

نتایج پیاده سازی الگوریتم برروی دو مجموعه داد ه واقعی از UCI را در قسمت 4 نشان می دهیم ودر نهایت در قسمت 5 بعضی نتایج را عنوان می کنیم.

2- مروری بر روش های قبل 1.2- الگوریتمk-means Hard الگوریتم k-means،الگوریتمی است که n نمونه داده را بر پایه ویژگی هایشان به c قسمت (c روال کلی الگوریتم بدین صورت می باشد که : تعداد خوشه ها را ، k در نظر بگیرید.

به طور تصادفی k خوشه تولید کنید و مراکز خوشه ها را تعیین نمایید.یا به طور مستقیم، k نقطه رندم را به عنوان مراکز خوشه ها تولید کنید.

در مجموعه داده،هر نمونه داده را به نزدیکترین مرکز کلاسترآن نسبت دهید.

دوباره مراکز خوشه های جدید را بدست آورید.

دو مرحله قبل را تا زمانیکه همگرایی مناسب حاصل شود(تفاوتی در دو خوشه بندی متوالی وجود نداشته باشد)،تکرار نمایید.

الگوریتم بالا را می توان بصورت ذیل نیز شبیه سازی نمود.

var m = initialCentroids(x, K); var N = x.length; while (!stoppingCriteria) { var w = [][]; // calculate membership in clusters for (var n = 1; n v = arg min (v0) dist(m[v0], x[n]); w[v].push(n); } // recompute the centroids for (var k = 1; k m[k] = avg(x in w[k]); } } return m; الگوریتم k-Means Hard(سخت) فرض می کند که مرکز خوشه مشخص است و یک کلاس بندی سخت را اجرا می کند که هر داده به یک کلاس تعلق دارد یا ندارد.بنابراین مقدار عضویت به یک کلاس ،یکی از مقادیر 0 یا 1 می باشد.

2.1.1- مثالی عددی از الگوریتم k-means از آنجا هدف اصلی در پژوهش خوشه بندی است، و معروفترین الگوریتم خوشه بندی و پایه ای برای دیگر الگوریتم های خوشه بنددی ،الگوریتم k-means می باشد، این الگوریتم را با یک مثال با جزییات شرح می دهیم[12].

فرض کنید بخواهیم 4 نمونه داده زیر هر کدام با 2 ویژگی را ،همانطور که در شکل نشان داده شده است،در دو گروه k=2 بر پایه ویژگی هایشان مطابق با الگوریتم k-means خوشه بندی کنیم.

مقادیر مرکز های اولیه: فرض کنید از A و B به عنوان مراکز اولیه استفاده می کنیم.

فاصله بین مراکز و داده ها: فاصله اقلیدسی بین هر مرکز را با هریک از نمونه های داده محاسبه می کنیم.برای تکرار 0 خواهیم داشت: هر ستون در ماتریس فاصله نشان دهعنده یک داده است.سطر اول ماترس فاصله ،متناظر با فاصله بین هر داده با مرکز خوشه اول می باشد و سطر دوم ،فاصله نقاط با مرکز خوشه دوم می باشد.برای مثال فاصله نقطه c از مرکز خوشه اول برابر, است.

خوشه بندی داده ها: ما هر شیئ را بر پایه مینیمم فاصله برچسب گذاری می کنیم.بنبراین داده A به گروه 1 و داده b به گروه 2 و...تعلق دارند.درایه های ماتریس ذیل 1 هستند اگر و فقط اگر داده به آن گروه نبت داده شده باشد.

تکرار1.

تعیین مراکز: اکنون با دانستن داده های هر گروه، مراکز جدید هر گروه را بر پایه تعلق های جدید آنها محاسبه می کنیم.به عنوان مثال در گروه 2،مرکز جدید برایر .

می باشد.

فاصله مراکز- داده ها : این مرحله محاسبه فاصله هریک از داده ها از مراکز جدید می باشد(همانند مرحله2).

تکرار1- خوشه بندی داده ها: شبیه مرحله 3 ،براساس مینیمم فاصله ،دوباره داده ها را گروه بندی می کنیم.

7-تکرار2.تعیین مراکز: شبیه مرحله 4،مراکز جدید گروه ها را بدست می آوریم.خواهیم داشت: و 8-تکرار 2.فاصله مراکز- داده ها: مرحله 2 را تکرار نمایید.ماتریس فاصله جدید به صورت ذیل خواهد بود: 9-تکرار 2.خوشه بندی داده ها: بر اساس مینیمم فاصله، ماتریس گروه بندی داده ها به صورت ذیل خواهد بود: اکنون به نتیجه رسیده ایم.

مقایسه گروه بندی این تکرار و آخرین تکرار نشان می دهد که داده ها در هیچ یک از گروه ها تغییر نکرده اند.بنابراین نتیجه خوشه بندی k-means به صورت ذیل خواهد بود: مزایای اصلی الگوریتم k-means ، سادگی و سرعت آن می باشدکه بسیار مورد توجه مجموعه داده های بزرگ می باشد.از معایب این روش این است که نتیجه یکسانی در هر بار اجرا ندارد،زیرا نتایج خوشه بندی به انتخاب تصادفی اولین مراکز بستگی دارد.همچنین این روش ،در عین مینیمم سازی واریانس درونی خوشه،تضمینی برای رسیدن به مینیمم واریانس عمومی ندارد و به صورت محلی جواب بهینه بدست می آورد.

3.2- الگوریتم Clustering (FCM) Fuzzy c-Means الگوریتم fuzzy c-Means یک روش بهبودیافته ،آسان ویکی از معروفترین الگوریتم های فازی می باشد که در بسیاری از زمینه ها کاربرد دارد.این تکنیک توسط پورفسور Bezdek در سال 1981 معرفی شد[4,7].

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

برای هر نقطه x یک ضریب درجه تعلق به خوشه k ، ، داریم.معمولا مجموع ضرایب تعلق آنها 1 می شود.

1: در fuzzy c-Means ،مرکز یک کلاستر میانگین همه نقاط وزن داربا استفاده از درجه تعلق شان به کلاستر بدست می آید.

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

سپس ضرایب با استفاده ازیک پارامتر اعشاری m>1 نرمال و فازی می شوند بطوریکه مجموعشان 1 شود.بنابراین هنگامی که به 1 نزدیک می شود،آنگاه مرکز کلاستربه نقطه ای با بیشترین وزن نزدیک می شود و الگوریتم همانند k-Means عمل می کند.

الگوریتم FCMتلاش می کند تا عناصر یک مجموعه محدود X={ , ,… , }را به یک مجموعه از c خوشه فازی با توجه به ضوابط خاص داده شده تقسیم کند.

در این روش،یک مجموعه داده متناهی را به عنوان ورودی به الگوریتم می دهیم و الگوریتم یک لیستی از c مرکز خوشه V ،مانند V = , i =1, 2, ...

, c و یک ماتریس u را نتیجه می دهد U = , i =1, ..., c, j =1,..., n که یک مقدار عددی بین [0,1] است که درجه تعلق داده به i امین کلاستر را نشان می دهد.

الگوریتم FCM را می توان به فرم کلی زیر بیان نمود: تعداد خوشه ها را ،c (2 c n)، توان وزنی (1 مراکز خوشه های فازی{| i=1, 2, ..., c} را توسط محاسبه نمایید.

ماتریس خوشه بندی جدید را با استفاده از{| i=1, 2, ..., c}محاسبه نمایید.

ماتریس خوشه بندی جدید = ||- || = |- | را محاسبه کنید.اگر باشدآنگاهI=I+1 و به مرحله 2 بروید.اگر باشد آنگاه از حلقه خارج شوید.

الگوریتم شبیه همه روال های بهینه سازی دیگر که برای مینیمم عمومی یک تابع جستجو می کنند، احتمال گیر افتادن در یک مینیمم محلی وجود دارد.همچنین همانند الگوریتم ،نتیجه هر اجرا به انتخاب اولیه وزن ها بستگی دارد.

Hard k-Modes 3.2- الگوریتم این الگوریتم،یک تکنیک عمومی در حل مسائل خوشه بندی گروهی ،در حوزه های کاربردی مختلف می باشد که در سال 1997 ارائه گردید[6].الگوریتم k-Modes ،الگوریتم k-Meansرا با استفاده از یک معیار انطباق ساده متفاوت برای داده های گروهی توسعه می دهد.در اینجا از باقیمانده به جای میانگین برای خوشه بندی استفاده می شود و یک روش بر مبنای تکرار برای به روز رسانی باقیمانده ها در پروسه خوشه بندی استفاده می شود تا تابع ارزیاب خوشه بندی را مینیمم کند[8,9].

این توسعه موجب می شود تا محدودیتی که داده ها باید فقط عددی باشند،که از محدودیت های الگوریتم است، برطرف شود و قادر باشیم که پروسه خوشه بندی k-Means را برای خوشه بندی مجموعه داده های دسته ای (گروهی-نه فقط عددی) بزرگ از مجموعه داده های واقعی بکار ببریم.

اغلب فاصله بین دو نمونه داده به عنوان معیار شباهت در نظر گرفته می شود که دارای نتایج ضعیفی در شباهت بین خوشه ای دارد.بدین دلیل در پروسه خوشه بندی k-Modes برای بهبود دقت نتایج خوشه بندی از معیار تشابه جدیدی استفاده می شود.این معیار نسبت تکرار ویژگی ها ی باقیمانده ی خوشه ها می باشد.

به طور کلی الگوریتم k-Modes با الگویتمk-Means در موارد ذیل متفاوت است:1- استفاده از معیار انطباق ساده متفاوت برای داده های گروهی 2- جایگزینی میانگین خوشه ها با باقیمانده 3- استفاده از روشی تکراری برای پیدا کردن باقیمانده ها.

روال کلی الگوریتم بدین صورت کی باشد که: فرض کنید که X={ یک مجموعه ازn داده باشد.

داده به صورت [ نمایش داده می شود.فرض می کنیم که اگر و فقط اگر برای 1.

معیارساده میزان انطباق بین X وY به صورت ذیل تعریف می شود: d(X,Y) که بدیهی است که تابع یک فاصله استاندارد را بین نمونه های دسته ای بدست می دهد که نوعی از فاصله همینگ می باشد.

هدف از خوشه بندی یک مجموعه از n داده گروهی به k خوشه این است که Z و Wرا پیدا کنیم که F(W,Z) را مینیمم کند.

F( W,Z ) = به طوریکه 0 که k( تعداد خوشه ها، W=[ یک ماتریس باینری k و Z=[ ، و مرکزi امین خوشه با ویژگی های گروهی می باشد.

مینیمم سازی F در (2) با شرایط (3)،(4) و(5) ،یک مسئله بهینه سازی غیرخطی را شکل می دهد که راه حل های متفاوتی برای آن ارائه گردیده است.

مرسوم ترین روش بهینه سازی F در (2) این است که از بهینه سازی جزئی W و Z استفاده کنیم.در این روش ابتدا Z را ثابت در نظر گرفته وW ی را ،که شرایط بیان شده را داشته باشد، پیدا می کنیم که F را مینیمم می کند.سپس W را ثابت در نظر گرفته وF را با استفاده ازZ مینیمم می کنیم.

این رو ش به صورت ذیل فرموله می شود[6].

الگوریتم k-Modes یک نقطه اولیه را انتخاب کنید.

را طوری تعیین کنید که F(W,) مینیمم شود.همچنین، t را 1 قرار دهید.

را طوری تعیین کنید که F(,) مینیمم شود.

اگر= F(,) F(,) آنگاه توقف .در غیر اینصورت به مرحله 3 بروید.

اگر= F(,) F(,) آنگاه توقف .در غیر اینصورت t=t+1 و به مرحله 2 بروید.

ماتریس های W وZ طبق تئوری های زیر محاسبه می شوند.

تئوری 1- فرض کنید که ثابت باشد .با در نظر گرفتن این مسئله که ) در رابطه های (3)،(4) و(5) برقرار باشد ، مینیمم با رابطه ذیل بدست می آید.

تئوری 2- فرض کنید X یک مجموعه از داده های دسته ای باشد که با ویژگی های دسته ای نشان داده می شود و DOM(،که تعداد ویژگی های دسته ای برای1 می باشد.فرض کنید مراکز خوشه های ، به صورت [ برای 1نشان داده شوند.آنگاه کمیت مینیمم می شود اگر و فقط اگر که برای 1 .

تعداد عناصر مجموعه با |X | نشان داده شده است.

4.2- الگوریتم Fuzzy k-Modes الگوریتم fuzzy k-Modes در سال 1999 معرفی شد.برای شرح این الگوریتم [5]،ابتدا چند نشانه گذاری را به صورت ذیل تعریف می کنیم[5]: D={ , ,…,}یک مجموعه داده گروهی با n شی ء داده می باشد که هر یک با d ویژگی دسته ای (گروهی),…, , شرح داده می شوند.ویژگی (1≤j≤d)دارای دسته می باشد.

به عبارت دیگر : DOM()={ , ,…, } مرکزهای کلاستر به وسیله=( , ,… ,) برای هر 1≤l≤k نمایش داده می شود که k تعداد کلاستر ها می باشد.ساده ترین انطباق فاصله بین x و y در Dبه صورت (x,y)= تعریف می شود که و به ترتیب j امین مولفه xو yهستند،و آنگاه هدف از خوشه بندی fuzzy k-Modes این است که در هر خوشه WوZ را پیدا کنیم که را مینیمم می کند.

در 1a,1b و1c هدف از >1 α،مولفه وزنی و رابطه تعریف شده 2 ،W=() یک ماتریس k×n تعلق فازی وZ={ , ,…,} مجموعه ای از مرکزهای خوشه می باشد.توجه کنید هنگامیکه α=1است، الگوریتم خوشه بندیk-Modes سخت یا به عبارتی دیگر الگوریتم k-Modes را نتیجه می دهد.

به منظور به روز کردن مرکز های خوشه داده شده در تخمین W، Huang وNg تئوری ذیل را معرفی کردند: تئوری 1- کمیت تعریف شده در رابطه 3 مینیمم می شود اگر و فقط اگر DOM() Є = که R=arg بعبارتی دیگر: , 1 برای به روز کردن ماتریس عضویت فازی W داده شده برای تخمین Z ،تئوری ذیل را معرفی کردند.

تئوری 2- فرض کنید Z={ , ,…,} ثابت باشد ،آنگاه ماتریس تعلق فازی W،که کمیت تعریف شده در 3 را مینیمم می کند،به صورت ذیل بدست می آید: بر اساس دو تئوری شرح داده شده بالا ،الگوریتمfuzzy k-Modes می تواند به صورت ذیل پیاده سازی شود[5].

الگوریتم 1-الگوریتم Fuzzy k-Modes R را بعنوان ماکسیمم تعداد تکرارهادر نظر بگیرید.

نقطه اولیه را انتخاب نمانید.

را طوری تعیین کنید که تابع هدف F(,) مینیمم شود.

برای r بار مراحل ذیل را تکرار نمایید.

اگر =F(,) F(,) آنگاه "از حلقه خارج شوید" در غیر اینصورت را طوری تعیین کنید که تابع هدف F(,) مینیمم شود.

اگر =F(,) F(,) آنگاه "از حلقه خارج شوید" در غیر اینصورت پایان اگر پایان اگر - پایان حلقه 3-الگوریتمGenetic fuzzy k-Modes این الگوریتم برپایه ترکیب الگوریتم های fuzzy k-Modesو genetic ،در سال 2007 ارائه گردید[5].

به طور کلی ،الگوریتم ژنتیک شامل 5 عنصر پایه است:نمایش رشته ای،جمعیت اولیه ،انتخاب،ادغام و جهش.

به منظور افزایش سرعت در فرآیند های همگرایی،ما از یک الگوریتم fuzzy k-Modesیک مرحله ای در فرآیند ادغام استفاده می کنیم.در این بخش این 5 عنصر الگوریتم ژنتیک را برای خوشه بندی معرفی می کنیم.

3.1- نمایش رشته ای: یک روش کدینگ مرسوم بدین صورت است که ماتریس تعلق فازی W را در یک کروموزوم قرار دهیم که n تعداد اشیاء در مجموعه داده و k تعداد خوشه ها می باشد.

طول کوروموزوم k×n می باشد که k موقعیت اول ( kتا ژن اول) بیانگرk تعلق فازی نقطه اول،kموقعیت بعدی نمایانگرk تا تعلق فازی نقطه دوم و...

به همین صورت می باشد.

برای مثال:اگر n=4 وk=3 باشد،آنگاه کروموزوم( , ,…,) ماتریس تعلق فازی 34 زیر را نمایش می دهد که W شرایط 1b,1aو1c را نیز تایید می کند.

ما کروموزومی را کروموزوم قانونی می نامیم که ماتریس تعلق فازی ارائه شده توسط کروموزوم آن ،3 شرط 1b,1aو1c را تایید کند.

3.2-فرآیند مقدار دهی اولیه در فاز مقدار دهی اولیه ،یک جمعیت ازN کروموزوم قانونی تولید می شود که Nسایز جمعیت است.به منظور تولید کروموزوم ( , ,…,)،در این پروژه از روش Zhao و Tsujimura [9]استفاده می کنیم که در زیر توصیف شده است.

الگوریتم مقداردهی اولیه برای n تکرار دستورات ذیل را انجام دهید: k عدد تصادفی ,,…, در محدوده [0,1] برای i امین نقطه کروموزوم تولید کنید.

برای k مقدار را محاسبه نمایید.

پایان حلقه اگر کروموزوم تولید شده،3 شرط 1b,1aو1c را ارضاء کند ،کروموزوم بعدی تولید می شود در غیر اینصورت مراحل بالا تکرار می شود.فرایند توصیف شده در بالا به منظور تولید جمعیت اولیه N بار تکرار می شود.

3.3 – فرایند انتخاب به منظور توصیف فرایند انتخاب ،ابتدا تابع ارزیاب کروموزوم را معرفی می کنیم.مطابق با الگوریتم مان از تابع ارزیاب شناخته شده رتبه بندی ذیل استفاده می کنیم.

F( که ، iامین کروموزوم در جمعیت است.

رتبه وپارامتر وزنی می باشد.

بدیهی است که کروموزومی با مقدار رتبه 1 بهترین نوع و کروموزوم با رتبه N بدترین کروموزوم می باشد.

دراین الگوریتم ، فرایند انتخاب را بر پایه چرخ رولت انجام می دهیم.

بدین صورت که N بار و هر بار یک کروموزوم برای جمعیت بعدی انتخاب می شود.

به عنوان احتمال تجمعی به صورت ذیل تعریف می شود: سپس جمعیت جدید به صورت زیر تولید می شود: الگوریتم تولید جمعیت جدید برای N بار مراحل زیر را تکرار نمایید یک عدد تصادفی اعشاری v در محدوده [0,1]تولید نمایید.

اگر آنگاه را انتخاب کنید.

پایان حلقه 3.4- فرایند ادغام پس از مرحله انتخاب ،جمعیت به سمت فرایند ادغام پیش می رود.مشابه با الگوریتم genetic k-Means ،در الگوریتم مان در مرحله ادغام،الگوریتم fuzzy k-Modesیک مرحله ای را به کار می گیریم.

بر پایه تئوری های 1 و 2 ،هر کروموزوم را در جمعیت به صورت ذیل به روزرسانی می کنیم.

الگوریتم ادغام t را از 1تا N بار تکرار کنید: را به عنوان ماتریس تعلق فازی در نظر بگیرید.( کروموزومی است که این ماتریس را می سازد).

مجموعه جدید مراکز خوشه ها() را که از بدست می آید ،طبق تئوری 1 بدست بیاورید.

ماتریس تعلق فازی که ازبدست می آید را طبق تئوری 2 بدست آورید .

را مطابق با نمایش جایگزین کنید.

پایان حلقه 3.5- فرایند جهش در فرایند جهش،هر ژن یک احتمال کوچک جهشدارد، تصمیم گیری براساس تولید یک عدد تصادفی می باشد.(اگر عدد تصادفی کوچکتر از 0.01 باشد ،ژن جهش خواهد کرد در غیر انصورت جهش صورت نمی گیرد).در الگوریتم پیشنهادی ما،یک تغییر یک ژن از یک کروموزوم ،باعث تغییر یک سری از ژن ها می شود تا شرط 1b برقرار باشد.بنابراین در پروسه جهش ،همه ی تعلق های فازی یک نقطه در یک کروموزوم انتخاب خواهد شد تا عمل جهش با احتمال انجام شود.

پروسه جهش: برایt از 1 تا N مراحل ذیل را تکرار نمایید: ( , ,…, )رابه عنوان کروموزوم در نظر بگیرید.

برای i از 1 تا nمراحل زیر را تکرار نمایید: یک عدد اعشاری تصادفی v در محدوده [0,1] تولید کنید.

اگر v آنگاه اعداد تصادفی , ,…, در محدوده [0,1]برای iامین نقطه کرووزوم تولید کنید.

برای j=1,2,…,k،مقدار را با جایگزین کنید.

پایان اگر پایان حلقه پایان حلقه 3.6 – معیار توقف دراین الگوریتم ،فرایندهای انتخاب ،fuzzy k-Modes یک مرحله ای و جهش برای ،،ماکسیمم تعداد تکرار(ماکسیمم تعداد نسل ها) اجرا شدند.

بهترین کروموزوم تا آخرین نسل راه حلی را برای مسئله کلاسترینگ تولید می کند.ما همچنین استراتژی نخبه گزینی را پیاده سازی کردیم بطوریکه در هر نسل N-1 فرزند تولید کرده و بهترین کروموزوم نسل جاری را برای نسل بعدی حفظ کردیم.

4-آزمایش ها برای تست امکان سنجی و کارایی الگوریتم پیشنهادی مان از دو مجموعه داده ازUCI استفاده کردیم[13].

1-4- معیار کیفیت خوشه بندی نتایج خوشه بندی الگوریتم genetic fuzzy k-Modes ،یک ماتریس تعلق فازی است از آنچه که از تعلق های خوشه ها به صورت ذیل بدست می آوریم.

داده ی بهr امین خوشه اختصاص داده می شود اگر R=arg در نمونه ای که ماکزیمم یکتا نیست،شی ء به اولین کلاستری که ماکسیمم را بدست می آورد،اختصاص داده می شود.همچنین از اندیس تصادفی تصحیحی استفاده می کنیم تا بهبود ساختار کلاستر ها را تعیین کنیم.

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

اندیس تصادفی تصحیح شده از صفر ،که دو کلاستر هیچ شباهتی ندارند(به این معنا که وقتی که یکی از دو کلاستر ، کلاسترمنفردی است که شامل همه اشیاءمجموعه داده می باشد و کلاستر دیگر شامل کلاسترهایی است که هر کدام نقاط منفردی را دارند)،تا یک ،که دو کلاستر یکسان هستند، تغییر می کند.بعبارتی از آنجا که خوشه بندی صحیح را با توجه به مجموعه داده می دانیم ،از این خوشه بندی صحیح و نتایج خوشه بندی الگوریتم برای محاسبه مقدار استفاده می کنیم.

2-4- مجموعه داده دو مجموعه داده از UCI برای تست الگوریتم و خوشه بندی مورد استفاده قرار گرفته اند[13].

اولین مجموعه داده ،داده معروف soybean است .این مجموعه داده شامل 47 رکورد است که هریک با 35 ویژگی توصیف می شود.هر رکورد به صورت یکی از 4 کلاس برچسب گذاری می شود.به جزآخرین کلاس که دارای 17 نمونه داده می باشد،مابقی کلاس ها هرکدام 10 نمونه داده دارند.(47=17+10+10+10).در بین ویژگی ها،14 ویژگی فقط یک مقدار دارند(تک مقداری هستند) و به همین علت آنها را حذف کرده و 21 ویژگی را به منظور خوشه بندی مورد بررسی قرار می دهیم.

دومین مجموعه داده ، Congressional voting مربوط به آراء نمایندگان مجاس می باشد .برای هر عضو مجلس نمایندگان آمریکا برروی 16 رأی کلید به وسیله CQA تعریف شده است.این مجموعه داده دارای 435 نمونه داده (168 جمهوری خواه و 267 دمکرات) می باشد که هرکدام از آنها با 16 ویژگی باینری توصیف شده اند.

بعضی از داده ها مقادیر نامشخص دارند که با ؟

نشان داده می شوند و آنها را به عنوان یک گروه و دسته مجزا در نظر می گیریم.

4-3- نتایج برای مجموعه داده soybean از پارامتر هایی با مقادیر ذیل استفاده کردیم.

K=4 , N=20 , نتایج پس از 10 بار اجرا در جدول 1 خلاصه شده اند.

جدول 1- نتایج 10 بار اجرای الگوریتم genetic fuzzy k-Modes بر روی مجموعه داده soybean ستون اول بهترین نمونه از 10 اجرا برحسب تابع هدف تعریف شده در معادله 3 می باشد.برچسب تصادفی تصحیح شده متناظر بهترین مورد در ستون سوم جدول نشان داده شده است.ستون دوم و ستون چهارم به ترتیب میانگین مقادیر تابع هدف ومیانگین شاخص (اندیس)تصادفی تصحیح شده را برای 10 اجرا می دهند.پنجمین ستون ، تعداد خوشه بندی های صحیح از 10 بار اجرا را نمایش می دهد.

بهترین مورد ، یک اندیس تصادفی تصحیح شده 1 دارد که بدین معنا است که همه داده ها بطور صحیح در 4 کلاستر داده شده خوشه بندی شده اند.

تعلق فازی بهترین مورد در جدول 2 داده شده است.از جدول 2 دیده می شود که بیشتر داده ها تعلق بالایی (سنگینی) برای یک خوشه و تعلق پائینی(سبکی) برای دیگر خوشه ها دارند.داده تعلق با مقدار 1 برای یک خوشه و 0 برای دیگر خوشه ها دارد که بیانگر این مطلب است که مرکز خوشه متعلق به آن می باشد.

جدول 2-بهترین تابع تعلق فازی از 10 بار اجرای الگوریتم genetic fuzzy k-Modes بر روی مجموعه داده Soybean اگر یک نمونه داده دو تعلق برابربرای دو خوشه متفاوت داشته باشد، می تواند به یکی از دو خوشه نشانه گذاری (متعلق) شود.

همچنین الگوریتم genetic k-Modes را بر روی مجموعه داده soybean با تغییردر مقادیر پارامترهای تست کردیم.نتایج حاکی از آن است که بهترین خوشه بندی نسبت به دیگر ساختار های تولید شده با پارامتر های بدست می آید.

ما k=2,n=20, مشخص کردیم و الگوریتم را 10 بار برروی مجموعه داده آراء اجرا کردیم.جدول 3 بطور خلاصه نتایج خوشه بندی 10 بار اجرا را نشان می دهد.مفهوم ترتیب ستون ها مانند جدول 1 می باشد.

جدول 3- نتیجه 10 اجرا ی الگوریتم genetic fuzzy k-Modes روی مجموعه داده آراء نمایندگان با مشاهده جدول 3 ،تفاوت بین بهترین نمونه و میانگین را می بینیم که بسیار کم می باشد و نشان می دهد که الگوریتم پایدار است.

با این جود،اجرایی از 10 بار اجرا وجود ندارد که همه داده های آن به طور صحیح در 2 خوشه داده شده خوشه بندی شده باشند(ستون آخر=0).جدول 4 ماتریس کلاس بندی اشتباه بهترین نمونه در 10 اجرا را نشان می دهد.

با دقت بر روی این جدول ملاحظه می شود که 53 مورد از 435 مورد داده اشتباه خوشه بندی شده است.

جدول 4_ ما تر یس اشتباه کلاس بندی شده از بهترین مورد از 10 بار اجرای الگور یتم genetic fuzzy k-Modes روی مجموعه داده ی آراء نمایدگان با 2 k= جدول 5- ما تریس اشتباه کلاس بندی شده از بهترین مورد از 10 بار اجرای الگور یتم genetic fuzzy k-Modes روی مجموعه داده ی آراء نمایدگان با 4 k= جدول 6 - ما تریس اشتباه کلاس بندی شده بهترین مورد از 10 بار اجرای الگور یتم genetic fuzzy k-Modes روی مجموعه داده ی آراء نمایدگان با 6 k= ما همچنین الگوریتم را برروی مجموعه داده آراء با k=4 و دیگر پارامترهای ثابت، نیز 10 بار اجرا کردیم.

داده های اشتباه کلاس بندی شده در بهترین نمونه از 10 بار اجرا در جدول 5 داده شده اند.مشاهده می شود که فقط 14+16+3+7=40 مورد از 435 نمونه اشتباه کلاس بندی شده است.

جدول 6 این موارد را درk=6 و دیگر پارامترها ی ثابت نشان می دهد.

در این حالت فقط 5+3+3+6+2+4=23 مورد از 435 داده اشتباه کلاس بندی شده است.

با توجه به نتایج بدست آمده از مجموعه داده آراء می توان فاکتور قابل توجهی را مشاهده کرد: وقتی که مقدارk را افزایش می دهیم تعداد نمونه هایی که اشتباه کلاس بندی می شوند،کاهش می یابد.

با در نظر گرفتن این مجموعه داده ،به عنوان مثال در k=2,4,6 نمونه هایی که اشتباه کلاسبندی شده اند، به ترتیب برابر 53,40,23 می باشند.

5-نتیجه گیری در این پژوهش الگوریتمgenetic fuzzy k-Modes را برای خوشه بندی مجموعه داده های گروهی ارائه کردیم.

ما خوشه بندی fuzzy k-Modes را به عنوان مسئله بهینه سازی اعمال نموده و ،به دلیل گیر افتادن در بهینه محلی، همزمان از الگوریتمGenetic استفاده کردیم تا راه حل بهینه عمومی را بدست آوریم.

برای بالا بردن فرایند همگرایی الگوریتم ،الگوریتم جدید fuzzy k-Modes یک مرحله ای را در پروسه ادغام به جای عملگر معمول ادغام بکار بردیم.

از آنجا که الگوریتم fuzzy k-Modes توسه یافته الگوریتم fuzzy c-Means است،برای درک بیشتر مطلب به ترتیب ابتدا الگوریتم های k-Means,fuzzy c-Means,k-Modes ,fuzzy k-Modes را شرح داده و در نهایت الگوریتم اصلی مورد نظر ،genetic fuzzy k-Modes ، را با جزییات تشریح کردیم.