خوشه بندی روشی است که داده های یک مجموعه داده را به گروه یا خوشه تقسیم می کند .
از مرسوم ترین روش های خوشه بندی،الگوریتم های خوشه بندی 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 بروید.اگر باشد آنگاه از