بخشی از مقاله
چکيده
در این گزارش ما یک روش جدید برای خوشه بندی داده ها بر پایه الگوریتم ژنتیک همراه با بازچینی مجدد ژن های هر کروموزوم در هر مرحله تکرار ارائه می دهیم.این امر باعث حذف انحطاط در مراکز خوشه ها در هر مرحله می شود در این گزارش یک عملگر ترکیب (crossover) جدید تعریف شده است که از میزان شباهت بین کروموزوم ها استفاده می کند.احتمال ترکیب و جهش در هر مرحله به صورت وفقی محاسبه می شود تا الگوریتم کمتر در بهینه های محلی گیر کند این الگوریتم به همراه الگوریتم K-mean و دیگر الگوریتم های تکاملی بر روی داده های UCI اعمال شده است و نتایج با همدیگر مقایسه شده است نتایج نشان می دهد الگوریتم ارایه شده کارایی و انعطاف بالاتری دارد.
واژه های کليدی: خوشه بندی ، الگوریتم ژنتیک ، K-mean
1- مقدمه
خوشه بندی یکی از مهمترین تکنیک های یادگیری بدون سرپرستی می باشد که در آن داده ها به صورت بردار هایی در فضای چند بعدی در گروه هایی ( خوشه ) بر اساس شباهت ویژگی هایشان دسته بندی می شوند این گروه بندی بر اساس دو شرط انجام می شود 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) انحطاط در کروموزوم ها بشدت کم شده است و این امر باعث افزایش سرعت در جستجوی فضای جستجو شده است علاوه بر این چون کروموزوم ها دارای مقادیر حقیقی هستند ترکیب در آنها به صورت اکتشافی و مسیری انجام شده است
در بخش بعدی تعاریف روابط لازم که در الگوریتم استفاده شده شرح داده شده است در بخش سوم جزییات الگوریتم تشریح شده در بخش چهارم این گزارش در مورد ویژگی ها و توانایی های این الگوریتم بحث شده است آزمایشات تجربی را در بخش پنجم آمده است و در نهایت نتیجه گیری و بحث در بخش ششم این گزارش آمده است.
2- تعاریف مقدماتی
در این بخش ابتدا چند تعریف که در قسمت های بعدی بکار می رود ارائه می کنیم این تعاریف در عملگرهای الگوریتم ژنتیک و در بازچینی ژن ها کاربرد دارد [5]
تعریف 1 :اگر x1 و x2 دو بردار در فضای RN باشند آنگاه داریم :
تعریف 2 :اگر x1 و x2 دو بردار در فضای RN باشند آنگاه فاصله بین x1 و x2 به صورت زیر تعریف می شود
تعریف 3 :از ترکیب دو بردارx1 و x2 یک بردار جدید x1x2 به صورت زیر تعریف می شود
واضح است که :
تعریف 4 :اگر x1 و x2 دو بردار در فضای RN باشند و x1 نا مساوی با x2 باشد و j کوچکترین عددی باشد که x1(j)<x2(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 برقرار باشد آنگاه :
3- الگوریتم خوشه بندی 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 :
1- ایجاد جمعیت اولیه به صورت راندوم با این شرط که در یک کروموزوم دو مرکز خوشه همسان نداشته باشیم و نسبت دادن داده ها به خوشه ها در هر کروموزوم به طوری که هر داده به خوشه ای نسبت داده می شود که کمترین فاصله را تا مرکز آن خوشه داشته باشد
2- ارزیابی کروموزوم ها و قرار دادن بهترین کروموزوم در pbest
3- اگر شرط توقف وپایان برقرار نیست برو به مرحله 4 ، در غیر این صورت pbest را به عنوان جواب بهینه انتخاب کن
4- کروموزوم های والد را برای عمل ترکیبو جهش انتخاب کن
5- انجام عمل ترکیب بر روی کروموزوم های انتخاب شده با توجه به احتمال ترکیب
6- انجام عمل جهش بر روی کروموزوم های انتخاب شده با توجه به احتمال جهش
7- ارزیابی جمعیت جدید
8- مقایسه بدترین کروموزوم از نسل جدید با pbest اگر بدترین کروموزوم از pbest بهتر بود جایگزینی آن در pbest و حذف pbest قبلی
9- پیدا کردن بهترین کروموزوم از نسل جدیدو تعویض آن با pbest
10- انتخاب pbest به عنوان مرجع وبازچینی جمعیت طبق رابطه 5
11- بازگشت به مرحله 3
4- تحلیل کارایی الگوریتم 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,
