دانلود مقاله یک الگوریتم ژنتیک جدید همراه با بازچینی مجدد ژن ها برای خوشه بندی داده ها

در این گزارش ما یک روش جدید برای خوشه بندی داده ها بر پایه الگوریتم ژنتیک همراه با بازچینی مجدد ژن های هر کروموزوم در هر مرحله تکرار ارائه می دهیم.این امر باعث حذف انحطاط در مراکز خوشه ها در هر مرحله می شود در این گزارش یک عملگر ترکیب (crossover) جدید تعریف شده است که از میزان شباهت بین کروموزوم ها استفاده می کند.احتمال ترکیب و جهش در هر مرحله به صورت وفقی محاسبه می شود تا الگوریتم کمتر در بهینه های محلی گیر کند این الگوریتم به همراه الگوریتم K-mean و دیگر الگوریتم های تکاملی بر روی داده های UCI اعمال شده است و نتایج با همدیگر مقایسه شده است نتایج نشان می دهد الگوریتم ارایه شده کارایی و انعطاف بالاتری دارد.

خوشه بندی یکی از مهمترین تکنیک های یادگیری بدون سرپرستی می باشد که در آن داده ها به صورت بردار هایی در فضای چند بعدی در گروه هایی ( خوشه ) بر اساس شباهت ویژگی هایشان دسته بندی می شوند این گروه بندی بر اساس دو شرط انجام می شود 1-همگنی در گروه ِداده ها در هرگروه شبیه به هم باشند 2-غیر همگنی در گروهها ِیعنی داده ها در گروههای متفاوت شبیه به هم نباشند ما داده ها را به عنوان نقاطی در فضای چند بعدی در نظر می گیریم که بعد همان تعداد ویژگی ها می باشد بنابراین object ها اشاره دارند به نقاط و پایگاه داده به این صورت نمایش داده می شود X={x1,x2,x3,..,xk} در جایی که xk متعلق به Rd می باشد که k تعداد داده ها و d نشان دهنده بعد می باشد.[1,2]
در مجموع می توان گفت که کلاسترینگ دو روش اصلی دارد روشهای مرتبه ای و روشهای جداسازی(مجزا) به طوری که روش مرتبه ای یک درخت مرتبه ای از کلاسترهای تودرتوبه عنوان یک درخت یکنواخت.
الگوریتمهای کلاسترینگ مجزا تولید می کنند Cدسته (کلاستر)از مجموعه داده هادر جایی که C تعداد کلاستر ها می باشد اغلب غیر معمول است که ما درجه تمایل کلاسترها را با بهینه سازی تابع هدف پیدا کنیم.

از جمله این روش ها k-means جزء این دسته می باشد.

به طوری که در این روش دسته بندی داده ها بستگی به میزان شباهت یا عدم شباهت که عموما دلالت دارد به فاصله بین داده یعنی هرچه داده به هم نزدیک تر باشند در یک کلاستر قرار می گیرند این فاصله ها به صورت متری در نظر گرفته می شوند با افزایش بعد این فاصله ها بنابراین این فاصله ها را در هر ویژگی به صورت مجزا اندازه گیری می کنیم اصل در این روش این است که فاصله ها را تا مرکز کلاستر اندازه می گیریم از انواع فاصله ها می توان فاصله اقلیدسی را نام برد .یک فرمول عمومی در مسائل کلاسترینگ بدین ترتیب می باشد که مجموعه ای از n نقطه در فضای d بعدی ویک عدد صحیح k و اتخاذ یک مجموع از مراکز کلاسترها در فضای Rd به طوری که هدف این است تا مجموع فواصل اقلیدسی نفاط از نزدیکترین مرکز مینیمم شود(SSE) که دارای روابطی به شکل[1] :
به علت قابلیت و پیاده سازی آسان k-means برای کلاسترینگ مجموعه داده های بزرگ استفاده می شود، k-means به صورت تکراری جهت محاسبه مراکز کلاسترها به کار می رود هر مجموعهZ z یک مجموعه از همسایگی ها دارد که به عنوان مجموعه ای از ناقاط که به z نسبت به دیگر نقاط نزدیک تر هستند الگوریتم با مجموعای از مراکز شروع شده وسپس همسایگی آنها محاسبه می شود ، در مراحل پی در پی مراکز توسط همسایهای خود جایگزیین شده ودوباره همسایگی ها تعیین میشود و این تا جایی ادامه می یابد که که یک معیار همگرایی از قبیل زمانی که دردو مر حله پی در پی مراکز تغییر نکند برآورده شود[2,3] با اینکه الگوریتمk-means یکی از الگوریتم های معروف وپر کاربرد در خوشه بندی محسوب می شود ولی چند عیب اساسی نیز دارد.

الگوریتمk-means به شدت به انتخاب مراکز حساس می باشد و یک انتخاب ضعیف در ابتدا ممکن است منجر به بهینه محلی شود که بشدت از بهینه عمومی پایین تر است از طرفی با بزرگ شدن حجم داده ها الگوریتم نیاز به زمان زیادی جهت پیدا کردن بهینه محلی دارد الگوریتم ژنتیک بر پایه اصل بقاء در طبیعت بوجود آمده است الگوریتم های تکاملی کاربرد گسترده ای در بهینه سازی مسائل دارند در سال های اخیر تلاش های زیادی جهت بهبود خوشه بندی بر پایه الگوریتم ژنتیک انجام شده است [4,5,6,7]میشل لازلو یک روش الگوریتم ژنتیک برای انتخاب همسایگی مراکز بنابر جستجوی عمومی k-means برای کلاسترینگ داده ها ارائه داد[4].

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

اکثر الگوریتم هایی که بر پایه ژنتیک هستند مشکل انحطاط دارند این مشکل زمانی رخ می دهند که چندین کروموزوم راه حل های یکسانی را ارائه کنند [5]انحطاط باعث می شود تا الگوریتم نتواند فضای جستجو را به طور بهینه وکارا جستجو کند و این بدلیل این است که یک خوشه به طور تکراری در چندین کروموزوم وجود دارد در روشی که در این گزارش بررسی شده است (GAGR) انحطاط در کروموزوم ها بشدت کم شده است و این امر باعث افزایش سرعت در جستجوی فضای جستجو شده است علاوه بر این چون کروموزوم ها دارای مقادیر حقیقی هستند ترکیب در آنها به صورت اکتشافی و مسیری انجام شده است در بخش بعدی تعاریف روابط لازم که در الگوریتم استفاده شده شرح داده شده است در بخش سوم جزییات الگوریتم تشریح شده در بخش چهارم این گزارش در مورد ویژگی ها و توانایی های این الگوریتم بحث شده است آزمایشات تجربی را در بخش پنجم آمده است و در نهایت نتیجه گیری و بحث در بخش ششم این گزارش آمده است.

تعاریف مقدماتی در این بخش ابتدا چند تعریف که در قسمت های بعدی بکار می رود ارائه می کنیم این تعاریف در عملگرهای الگوریتم ژنتیک و در بازچینی ژن ها کاربرد دارد [5] تعریف 1 :اگر x1 و x2 دو بردار در فضای RN باشند آنگاه داریم : تعریف 2 :اگر x1 و x2 دو بردار در فضای RN باشند آنگاه فاصله بین x1 و x2 به صورت زیر تعریف می شود تعریف 3 :از ترکیب دو بردارx1 و x2 یک بردار جدید x1x2 به صورت زیر تعریف می شود واضح است که : تعریف 4 :اگر x1 و x2 دو بردار در فضای RN باشند و x1 نا مساوی با x2 باشد و j کوچکترین عددی باشد که x1(j) و اگر x1(i)>x2(i) برای بعضی مقادیر i برقرار باشد و k بزرگترین عددی باشد که x1(k)>x2(k) آنگاه تابع زیر را داریم: برای روشن تر شدن تعاریف بالا از یک مثال برای این تعاریف استفاده شده است این مثال در جدول شماره 1 آمده است جدول 1 مثالی از تعاریف بالا تعریف 5 :اگر x1 و x2 دو بردار در فضای RKN به صورت زیر باشند به طوریکه : آنگاه با استفاده از شبه کد زیر مقادیر p1 و p2 را محاسبه می کنیم حال می توان با استفاده از مقادیر p2 سطر های بردار y را به صورت زیر بازچینی کرد این عمل را بازچینی بردار y را بوسیله بردار مرجع x می نامیم قضیه 1 :اگر x1 و x2 دو بردار در فضای RN باشند و x1 نا مساوی با x2 باشد و x1(i)>x2(i) برای بعضی مقادیر i برقرار باشد آنگاه : الگوریتم خوشه بندی GAGR 1-3 نمایش کروموزوم ها در هر الگوریتم تکاملی نمایش کروموزوم یکی ساز مسائل مهم آن الگوریتم است در واقع نحوه نمایش کروموزوم ساختار الگوریتم و مسئله را نشان می دهد هر کروموزوم از یک سری ژن هایی تشکیل شده است این ژن ها می توانند یک مقدار دودویی یک عدد اعشاری و یا یک عدد صحیح و یا یک سیمبل باشند در بسیاری از الگوریتم های تکاملی از اعداد دودویی در ژن ها استفاده می شود میشل ویز بررسی های گسترده ای برای مقایسه مقادیر حقیقی و دودویی در ژن ها انجام داد و این بررسی ها نشان داد اعداد حقیقی کارایی بهتری در زمان الگوریتم دارند.

بنابراین با توجه به این موضوع و ساختار مسئله ما از مقادیر حقیقی در ژن ها استفاده می کنیم برای نمایش کروموزوم ما از روش های معمول در خوشه بندی استفاده می کنیم بدین صورت که هر کروموزوم رشته ای از اعداد حقیقی به طول M=N*K است به طوری که N بعد فضای ویژگی مسئله را نشان می دهد و K معرف تعداد خوشه ها است مرکز اولین خوشه بوسیله N مقدار اول در بردار نشان داده شده، مرکز دومین خوشه بوسیله N مقدار دوم در بردار نشان داده شده و همینطور مرکز بقیه خوشه ها .

2-3 مقداردهی جمعیت برای ایجاد جمعیت اولیه از تابع راندوم برای تولید کروموزوم ها استفاده شده است نکته ای که در تولیید جمعیت باید ملاحظه شود ایت است که در تولید یک کروموزوم دو نقطه ( مرکز خوشه) برابر تولید نشوند پس از این که جمعیت اولیه به صورت کامل تولید شد برای هر کروموزوم تولید شده با توجه به مراکز خوشه ها طبق رابطه زیر هر داده را به نزدیکترین خوشه مجاور نسبت می دهیم mk مرکز k امین خوشه است.

3-3 تابع ارزش برای انتخاب یک جواب مناسب برای مسئله نیاز به یک تابع ارزش قوی است که بتواند کروموزوم ها را به خوبی ارزیابی کند یک ملاک ارزیابی که در اکثر الگوریتم های خوشه بندی استفاده می شود مجموع مجذور خطا است که به صورت زیر محاسبه می شود در رابطه بالا مجذور فاصله داده های ی خوشه i تا مرکز خوشه محاسبه می شود و این فاصله ها برای تمام خوشه ها با یکدیگر جمع می شود.

زمانی که هر خوشه فقط یک داده داشته باشند مقدار بالا صفر می شود.در الگوریتم خوشه بندی اگر مراکز خوشه ها به درستی انتخاب نشود این عدد بسیار بزرگ می شود و هر چه مراکز خوشه ها به داده های خوشه نزدیکتر باشد مقدار مجذور فاصله کم می شود به همین دلیل ما از معکوس مقدار بالا به عنوان تابع ارزش استفاده می کنیم اگر مراکز خوشه ها در یک کروموزوم به درستی انتخاب شود مجموع مجذور خطا کم شده و ارزش کروموزوم افزایش می یابد 4-3 عملگرهای تکاملی 1-4-3 ترکیب هدف اصلی عمگر ترکیب در الگوریتم ژنتیک ایجاد کروموزوم های جدید از روی کروموزوم های والد است یک عملگر ترکیب ساده مقداری از ژن های یک والد را با والد دیگری جابجا می کند و دو کروموزوم جدید ایجاد می کند در این الگوریتم ما از دو نوع عملگر ترکیب استفاده می کنیم : ترکیب بر پایه مسیر و ترکیب اکتشافی .

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

با توجه به قضیه 1 اگر و برای بعضی مقادیر i ، انگاه وجود دارد و طبق تعریف 2 فاصله آن تا کمتر است نسبت به فاصله آن تا M1 .طبق رابطه تعریف 4 می توان یک سری متناهی به صورت و بدست آورد سری بدست آمده از روابط بالایک مسیر بین M1 تا را نشان می دهد به طور مشابه می توانیم یک مسیر بین و M2 ایجاد کنیم از ترکیب این دو مسیر می توان یک مسیر بین M1و M2 ایجاد کرد عملگر ترکیب بر پایه مسیر ابتدا یک مسیر بین دو کروموزوم والد ایجاد مند و سپس دو نقطه در این مسیر را به عنوان کروموزوم های فرزند انتخاب می کند انتخاب نقاط می تواند به صورت راندوم باشد و یا می توان از چرخ رولت و یا تورنمنت استفاده کرد روش بالا را با یک مثال شرح می دهیم M1 و M2 دو کروموزوم هستند که هر کدام سه مرکز خوشه دوبعدی را نشان می دهند مسیر بین M1 و M2 طبق روابط بالا به صورت زیر است اما بعضی اوقات در روش ترکیب بر پایه مسیر که در بالا معرفی شد یک مشکل پیش می آید آنهم زمانی که والدین بسیار به همدیگر نزدیک باشند واضح است که در چنین شرایطی مسیر بین دو والد به شدت کم می شود برای رفع این مشکل ما از یک حد آستانه استفاده می کنیم به گونه ای که اگر فاصله دو والد از حد آستانه بیشتر بود از ترکیب مسیری استفاده شود و در غیر این صورت ما از ترکیب دیگری استفاده کنیم ترکیب دیگری در زمان نزدیک بودن والدین استفاده می شود ترکیب اکتشافی است در این روش اگرx و y دو کروموزوم والد باشند و x از y بهتر باشد (طبق تابع ارزش) آنگاه دو کروموزوم جدید به صورت زیر بدست می آید : R یک عدد تصادفی با توزیع یکنواخت در بازه {0,1} است 2-4-3 جهش جهش در الگوریتم تکاملی عبارت است از تغییر یک یا چند ژن در یک کروموزوم انتخاب شده بایک احتمال خاص.

عمل جهش باعث می شود تا الگوریتم بتواند فضاهای بیشتریو گسترده تری در فضای جستجو بررسی کند و این امر تا حدی به الگوریتم کمک می کند تا در بهینه محلی گیر نکند در این روش ما احتمال جهش را هم مانند احتمال ترکیب به صورت وفقی محاسبه می کنیم نحوه محاسبه این احتمال در رابطه زیر آمده است مقدار k2 و k4 در رابطه بالا برابر 0.5 است و fmax بیشترین میزان ارزش در جمعیت جاری و f^ میانگین ارزش در جمعیت و f میزان ارزش کروموزومی که برای عمل جهش انتخاب شده است با توجه به روابط pc و pm این گونه به نظر می رسد که برای راه حل هایی با تابع ارزش بالا مقدار pc و pm کم می شود و برای راه حل هایی با تابع ارزش پایین مقدار احتمال pc و pm افزایش می یابد.

در الگوریتم ژنتیک اگر از کروموزوم هایی با تابع ارزش بالا جهت عمل ترکیب و جهش استفاده شود همگرایی الگوریتم افزایش پیدا می کند و اگر از کروموزوم هایی با تابع ارزش کم استفاده شود مسئله ما با احتمال بسیار کمتری در بیشنه های محلی گیر می کند برای فرار از بیشینه های محلی اغلب از راه حل هایی با ارزش کمتر از میانگین جهت ترکیب و جهش استفاده می شود مقدار احتمال pc و pm برای کروموزوم هایی با بیشترین مقدار ارزش برابر صفر است که این باعث می شود تا این کروموزوم های بدون تغییر به نسل بعد خود منتقل شوند.

عملگر جهش در این مسئله به این صورت است اگر fmin و fmax بیشترین و کمترین مقدار ارزش در جمعیت جاری باشد آنگاه یک عدد (δ) با توزیع یکنواخت در بازه [+R , -R] تولید می کنیم.

اگر بیشترین و کمترین مقدار در i مین بعد از داده ها را mimax و mimin بنامیم آنگاه جهش در i مین عنصر به صورت زیر انجام می شود 5-3 تشریح الگوریتم GAGR در این الگوریتم هر کروموزوم نشان دهنده مراکز خوشه هاست و هر خوشه توسط تابع ارزش ارائه شده ارزشش بررسی می گردد انتخاب کروموزوم ها برای عمل ترکیب توسط روش چرخ رولت انجام می شود در این روش کروموزوم هایی که ارزش بالاتری دارند از شانس بالاتری برای انتخاب دارند احتمال ترکیب وجهش در این الگوریتم به صورت وفقی محاسبه می شود برای عمل ترکیب از دو روش استفاده شده است روش ترکیب بر پایه مسیر و ترکیب اکتشافی در هر سری تکرار الگوریتم بهترین کروموزوم انتخاب شده و به عنوان کروموزوم مرجع در نظر گرفته می شود سپس کل جمعیت کروموزوم ها طبق تعریف 5 بازچینی می شوند این امر باعث جلوگیری از انحطاط در کروموزوم ها می شود این الگوریتم پس از مقدار مشخصی از تکرار خاتمه یافته و بهترین کروموزوم به عنوان پاسخ ارائه می شود مراحل الگوریم GAGR : ایجاد جمعیت اولیه به صورت راندوم با این شرط که در یک کروموزوم دو مرکز خوشه همسان نداشته باشیم و نسبت دادن داده ها به خوشه ها در هر کروموزوم به طوری که هر داده به خوشه ای نسبت داده می شود که کمترین فاصله را تا مرکز آن خوشه داشته باشد ارزیابی کروموزوم ها و قرار دادن بهترین کروموزوم در pbest اگر شرط توقف وپایان برقرار نیست برو به مرحله 4 ، در غیر این صورت pbest را به عنوان جواب بهینه انتخاب کن کروموزوم های والد را برای عمل ترکیبو جهش انتخاب کن انجام عمل ترکیب بر روی کروموزوم های انتخاب شده با توجه به احتمال ترکیب انجام عمل جهش بر روی کروموزوم های انتخاب شده با توجه به احتمال جهش ارزیابی جمعیت جدید مقایسه بدترین کروموزوم از نسل جدید با pbest اگر بدترین کروموزوم از pbest بهتر بود جایگزینی آن در pbest و حذف pbest قبلی پیدا کردن بهترین کروموزوم از نسل جدیدو تعویض آن با pbest انتخاب pbest به عنوان مرجع وبازچینی جمعیت طبق رابطه 5 بازگشت به مرحله 3 تحلیل کارایی الگوریتم GAGR همانطور که بیان شد اکثر الگوریتم هایی خوشه یابی که بر پایه ژنتیک عمل می کنند اما این مشکل در روش ارائه شده به طور چشمگیری کاهش پیدا کرده است برای مثال در الگوریتم ژنتیک ساده (که در آن ژن های کروموزوم بازچینی نمی شوند ) اگر M1=[1.2, 2.1, 3.3,3.3, 2, 3] نشان دهنده سه مرکز خوشه دو بعدی باشد و M2 = [3.3,3.3,2, 3 ,1.2, 2.1] کروموزوم دیگری از همین داده ها باشد آنگاه از ترکیب برشی این دو از نقطه دوم در کروموزوم ها بردارهای [3.3,3.3,3.3 , 3,3, 2, 3] و[1.2,2.1,2,3,1.2, 2.1] بدست می آید که در هر دو این کروموزوم ها مرکز خوشه هایی با مقادیر یکسان داریم و هر دو آنها نامعتبر هستند که در الگوریتم ارائه شده پس از بازچینی ژن ها در کروموزوم این مسئله تا حد زیادی رفع شده است.

علاوه بر این مشکل انحطاط در زمانی که کروموزوم های نا مساوی داریم هم اتفاق می افتد برای مثال اگر M1=[1.1,1, 2.2, 2,3.4 ,1.2] و M2=[3.2,1.4 ,1.8 ,2.2,0.5,0.7] و اگر M1 رابه عنوان مرجع در نظر بگیریم M2 به صورت M2'=[0.5,0.7,1.8 ,2.2,3.2,1.4] بازچینی می شود شکل یک نتایج حاصل از ترکیب M1 وM2 ونتایج حاصل از ترکیب M1 وM2' را نشان میده همانطور که در شکل پیداست نتایج مربوط به M1 وM2' مفیدتر و به مرکز داده ها نزدیک تر است شکل 1- مقایسه ترکیب در کروموزوم با استفاده از بازچینی ژن ها و بدون بازچینی ژن ها ،* نشان دهنده M1 ،+ نشان دهنده M2(M2') ،Δ نشان دهنده ترکیب M1 وM2 ،ο نشان دهنده M1 وM2' نتایج تجربی برای ارزیابی کارایی الگوریتم ارائه شده ما از داده های واقعی UCI استفاده کرده ایم بدین منظور ما چند سری از آن داده ها را انتخاب کرده و الگوریتم های K-maen , KGA , GA را بر روی این داده ها اعمال کردیم و سپس نتایج را با نتایج بدست آمده از الگوریتم ارائه شده مقایسه کردیم داده های UCI که استفاده شده است عبارت است از: Iris : این مجموعه داده شامل 150 داده است که در سه خوشه توزیع شده اند و مربوط به نوعی گل زنبق است این داده ها دارای چهار نوع ویژگی هستند (طول وعرض کاسبرگ و گلیرگ) این داده ها مربوط به سه نوع گل هستند که داده های دو از آن دارای همپوشانی هستند ولی داده ها نوع دیگر به صورت خطی جداپذیر است Wine : این مجموعه داده شامل 178 داده است که در سه خوشه توزیع شده اند هر یک از این داده ها دارای 13 ویژگی است که از یک سری آزمایشات شیمیایی بدست آمده است این 13 ویژگی جداکردن این 3 نوع را آسانتر می کند Breast cancer : این مجموعه داده شامل 683 داده است که در دو خوشه توزیع شده اند این داده ها با 9 ویژگی از هم متمایز شده اند Glass : این مجموعه داده شامل 214 داده است با نه ویژگی است (ویژگی ID از این داده ها حذف شده است) این داده ها در 6 طبقه دسته بندی شده اند Balance : این مجموعه داده شامل 569 داده است با 4 ویژگی است که بوسیله یک سری آزمایشات روانشناسی بدست آمده است.این داده ها در 3 طبقه ( انحراف به چپ ، انحراف به راست ، تعادل) دسته بندی شده اند Liverdisorder : این مجموعه داده شامل 345 داده است با شش ویژگی است که بوسیله یک سری آزمایشات از خون افراد بدست آمده است و مربوط به مشکلات کبدی بیماران است این داده ها در دو طبقه دسته بندی شده اند جدول شماره 2 خلاصه داده های استفاده شده را نشان می دهد در این جدول M نشان دهنده تعداد داده ها ، K نشان دهنده تعداد طبقه ها وd نشان دهنده تعداد ویژگی های هر داده است جدول 2 مشخصات داده های UCI استفاده شده برای ارزیابی الگوریتم ها چند روش وجود دارد که ما از آنها برای ارزیابی الگوریتم خود استفاده می کنیم 1- میانگین مجذور خطا(SSE) برای کل جمعیت 2- تعداد مراحل تکرار الگوریتم 3- RI(Rand Index) معیار ارزیابی RI از مقایسه نتایج بدست آمده با خوشه های اصلی بدست می آید در این روش ما تک تک داده ها را بر اساس اینکه در حقیقت به چه کلاستری تعلق دارند و الگوریتم ما چه کلاستری به آن نسبت داده است عملکرد الگوریتم را بررسی می کنیم اگر ns تعداد داده هایی باشده که به درستی خوشه بندی شده و nd تعداد داده هایی باشده که خوشه واقعی آن با نتیجه الگوریتم متفاوت است با شد و n تعداد کل داده ها باشد آنگاه داریم: خروجی RI عددی در بازه [0,1] است واضح است که بالا بودن این مقدار نشان دهنده بهتر بودن الگوریتم است روش های زیادی برای پیدا کردن تعداد خوشه ها در یک مجموعه داده وجود دارد روشی که در این الگوریتم استفاده شده است یک روش ساده است که بر مبنای SSE عمل می کند در این روش تعداد کلاستر ها را افزایش می دهیم تا زمانی که مقدار این پارامتر کاهش بیابد برای مقایسه همگرایی الگوریتم ما سه الگوریتم تکاملی را بر روی داده های UCI اجرا کرده و میانگین SSE را برای هر جمعیت در هر سری تکرار بدست می آوریم نتایج این کار در شکل شماره 2 و جدول شماره 3 نشان داده شده است همانطور که می بینید الگوریتم GAGR نسبت به بقیه الگوریتم ها تکاملی سرعت همگرایی بیشتری دارد و این الگوریتم با تکرار مراحل کمتری به همگرایی می رسد مقادیر زمانی جدول شماره 3 از اجرا الگوریتم های تکاملی بر روی کامپیوتر ی با مشخصات Windows XP, Intel (R) Xeon (R) CPU, 2.33GHz) بدست آمده است نتیجه‌گیری در این مقاله ما یک روش از روش ها ی تکاملی جهت خوشه بندی K-maen ارائه کردیم در این روش هر کروموزوم بوسیله یک سری اعداد حقیقی نشان داده می شود این گونه نمایش کروموزوم ها از نمایش دودویی محدودیت های کمتری برای نشان دادن مراکز خوشه ها دارد در این الگوریتم در هر مرحله کروموزوم ها بازچینی می شوند که این امر باعث کاهش انحطاط کروموزوم ها می شود و باعث می شود تا فضای جستجو سریعتر پیمایش شود علاوه بر این یک روش جدید جهت عمل ترکیب در این الگوریتم ارائه شده است در روش ترکیب بر پایه مسیر ابتدا یک مسیر بین دو والد ساخته می شود و سپس دو کروموزوم میانی به عنوان فرزند به صورت راندوم انتخاب می شود.

احتمال ترکیب و جهش در این الگوریتم به صورت وفقی محاسبه می شود که باعث می شود تا الگوریتم در بیشنه های محلی گیر نکند این الگوریتم به همراه چند الگوریتم تکاملی دیگر بر روی داده های UCI اجرا شده است نتایج نشان می دهد که این الگوریتم سرعت همگرایی بالاتری دارد و سرعت اجرا آن از بقیه الگوریتم ها را نشان می دهد علاوه بر این در تمام روش های ارزیابی که در این مقاله بررسی کردیم این روش کاراتر و بهتر از بقیه روشهای تکاملی بود کارهایی که در تحقیقات آینده می توان بررسی کرد : تعداد خوشه ها را برای یک مجموعه داده بوسیله الگوریتم GAGR نمی توان بدست آورد و برای مشخص کردن تعداد خوشه ها باید از روشی دیگر استفاده کرد بنابراین مشخص کردن تعداد خوشه با الگوریتم GAGR را می توان در آینده بررسی کرد عملگر ترکیب بر پایه مسیر را می توان از لحاظ تئوری موردتحقیق و بررسی قرار داد.

مراجع [1]R.Xu, D.Wunsch "Survey of Clustering Algorithms" IEEE TRANSACTIONS ON NEURAL NETWORKS, VOL.

16, NO.

3, MAY 2005 [2]A.

Likas, N.

Vlassis, J.J.

Verbeek, The global K-means clustering algorithm, Pattern Recognition 36 (2003) 452–461.

[3]T.Kanungo, M.

Mount, S.

Netanyahu,D.

Piatko "An Efficient k-Means Clustering Algorithm:Analysis and Implementation" IEEE, VOL.

24, NO.

7, JULY 2002 [4]M.Laszlo,S.Mukherjee "A genetic algorithm that exchanges neighboring centers for k-means clustering" Pattern Recognition Letters 28 (2007) [5]D.Chang,X.DaZhang"A genetic algorithm with gene rearrangement for K-means clustering" Pattern Recognition 42 (2009) 1210 -- 1222 [6]K.Sastry,G.Xiao"Cluster Optimization Using Extended Compact Genetic Algorithm" IlliGAL Report No.

2001016 January, 2001 [7]U.

Maulik, S.

Bandyopadhyay, Genetic algorithm based clustering technique, Pattern Recognition 33 (2000) 1455–1465.

[8]W.Lu,I.Traore " Determining the Optimal Number of Clusters Using a New Evolutionary Algorithm"