بخشی از مقاله
وشهبندی خودکار داده ها توسط الگوریتم ژنتیک دو مرحله ای
چکیده
سازماندهی دادهها به گروههای با معنی، یکی از پایههای اساسی در درک دادهها است. تحلیل خوشه، مطالعه روشها و الگوریتمهایی به منظور خوشهبندی و گروهبندی دادهها با توجه به میزان شباهت یا درجه نزدیکی آنها میباشد. یکی از چالشهای تحلیل خوشه، تشخیص درست تعداد خوشهها است، گرچه در چند دهه اخیر پژوهشهای متعددی جهت رفع این مشکل صورت گرفته است. لذا، در این مقاله، یک الگوریتم خوشهبندی ژنتیک دو مرحله ای((TGCA بررسی میشود. این الگوریتم به صورت خودکار، تعداد بهینه خوشهها و افراز مناسبی از دادهها را تعیین میکند. عملیات دو مرحلهای انتخاب و جهش به منظور استفاده از قابلیت جستجوی الگوریتم ژنتیک اجرا میشود که از طریق تغییر احتمالات انتخاب و جهش که براساس پایداری تعداد خوشهها در جمعیت است، حاصل میشود. ابتدا، الگوریتم خوشهبندی ژنتیک دو مرحلهای، تمرکز بر یافتن بهترین تعداد خوشهها دارد، و سپس بتدریج به سمت یافتن مراکز خوشه بهینه سراسری، سوق مییابد. علاوه بر این، روش افراز بندی با حداکثر بازه ویژگیها، جهت مقداردهی اولیه جمعیت استفاده میشود. نهایتا، کارآیی و اثربخشی TGCA با الگوریتم بهینه سازی ازدحام ذرات مقایسه میگردد که نتایج بدست آمده، نشان میدهد که این الگوریتم از نظر مدت زمان اجرا و هزینه خوشهبندی از الگوریتم بهینه سازی ازدحام ذرات، عملکرد بهتری دارد.
واژه های کلیدی : خوشهبندی، الگوریتم ژنتیک، انتخاب دو مرحله ای، جهش دو مرحله ای، پایداری تعداد خوشهها.
1
1 مقدمه
افزایش حجم و تنوع دادهها نیازمند پیشرفت روشهایی جهت افزایش سرعت در تحلیل، پردازش و خلاصه سازی داده هامیباشد. تکنیک تحلیل داده1 به دو بخش عمده تقسیم میشود: الف) اکتشافی و توصیفی: بدین معنی که پژوهشگر مدلها و یا فرضیههای از پیش تعیین شده و خاصی ندارد اما راغب به درک کلی ویژگیها یا ساختار دادههایی با ابعاد بالا است . ب) تاییدی یا استنباطی: بدین معنی که پژوهشگر در صدد تایید اعتبار یک فرضیه/مدل یا یک مجموعه از فرضیات داده شده روی دادههای موجود است. تکنیکهای آماری بسیاری جهت تحلیل داده پیشنهاد شدهاند، مانند تجزیه و تحلیل واریانس، رگرسیون خطی، بردارهای چند بعدی و تحلیل خوشه .
تحلیل داده مربوط به مدل پیشگویانه است. با توجه به برخی دادههای آموزشی داده شده، خواستار پیشبینی رفتار آنها با توجه به دادههای آزمایشی هستیم، که این کار "یادگیری" نامیده میشود. روش های یادگیری به دو دسته تفکیک می شوند. الف) یادگیری با نظارت)2یا طبقهبندی) و ب) یادگیری بدون نظارت)3یا خوشهبندی). یادگیری با نظارت شامل دادههای برچسبدار بوده در حالیکه یادگیری بدون نظارت با دادههای بدون برچسب سروکار دارد.) مسئله خوشهبندی تکنیک یادگیری بدون نظارت است که به مراتب سختتر و پرچالشتر از طبقهبندی میباشد.[1]
در روش خوشه بندی با استفاده از شباهت بین اطلاعات داده شده، مجموعه های محدودی از دسته ها (یا خوشه ها ) را ایجاد می کند. بطوریکه نمونه های موجود در هر مجموعه از بیشترین شباهت نسبت با نمونه های مجموعه های دیگر برخوردار هستند
در مقاله های بسیاری الگوریتمهای تکاملی به عنوان راهحلی برای مسائل خوشهبندی مطرح شده اند که تعداد خوشهها (K) در آن ها مشخص و از قبل تعیین شده است. 4Cole الگوریتمهای تکاملی را که تا سال 1997 در زمینه خوشهبندی منتشر شده اند را بررسی و بصورت تجربی ارزیابی کرده است.[2]
الگوریتمهای تکاملی خوشهبندی که از قوانین احتمال، برای پردازش تقسیمبندی دادههای نمونه برداری شده فضای جستجو استفاده میکنند را میتوان به عنوان راهحلهای خوشهبندی در نظر گرفت، که تمامی این احتمالات بر پایه عملگرهای این الگوریتمها میباشند. بطور کلی میتوان گفت که با این احتمالات، نمونهبرداری از تقسیمات صورت گرفته بسیار مناسبتر خواهد بود. بدین ترتیب، جستجوی تکاملی در راستای راهحلهای خوشهبندی امید بخشتر و در انجام محاسبات فضای جستجو کارآمدتر از دیگر رویکردهای تصادفی سنتی (همانند چندین بار اجرای الگوریتم (k-means عمل کرده است. بعلاوه، رویکردهای تصادفی سنتی از اطلاعات کیفی قسمتهایی که قبلاً ارزیابی شده اند، برای تولید تقسیمهای بهتر استفاده نمی کنند. به این دلیل این الگوریتمها در مقایسه با جستجوی تکاملی کارایی کمتری دارند. در مقابل، مزایای نظری (بصورت بازده محاسباتی) راهحلهای خوشهبندی تکاملی نشان دادند الگوریتمهای تکاملی در مقایسه با الگوریتمهای سنتی، تقسیماتی با کیفیت بهتر را فراهم میآورند. در واقع، ممکن است این امکان وجود داشته باشد که ماهیت موازی الگوریتمهای تکاملی به آنها اجازه دهد تا به راهحلهای متعددی رسیدگی کنند .[3] بدین منظور در این مقاله از الگوریتم ژنتیک استفاده شده است.
تحلیل خوشه، تکنیک گروهبندی بدون نظارت دادهها میباشدکه این گروهبندی با توجه به میزان فاصله، مشاهده ویژگیهای دادهها و شباهت انجام میگردد. مشکل اساسی در تحلیل خوشه، چگونگی تخمین بهترین تعداد خوشهها است، چرا که تخمین درست تعداد خوشهها تاثیر چشمگیری بر نتایج خوشهبندی دارد. گرچه، کمبود دامنه دانش پیشین، انتخاب تعداد درست و دقیق خوشهها را دشوار نموده است، مخصوصا زمانیکه دادهها بعد بالایی دارند و یا به خوبی تفکیک نشده اند .[1] روشهای متفاوتی به
2
منظور تخمین تعداد K خوشه پیشنهاد شده است.گاردون1 این روشها را به دو گروه دسته بندی کرده است: روشهای محلی و روشهای سراسری.
روشهای محلی خوشه بندی جهت تخمین تعداد بهینه خوشه ها براساس فرضیه ترکیب خوشهها و اینکه کدام زوج از خوشهها باید ترکیب شوند، استواراست. این روش برای ارزیابی افرازهای سلسله مراتبی تو در تو 2مناسب است. همانطور که گاردون نشان داد تشخیص تعداد خوشه ها در روشهای محلی بدلیل آزمونهای متعدد، پیچیده است. امادر روشهای سراسری خوشه بندی جهت تخمین تعداد خوشه ها، کیفیت خوشهبندی تعداد معینی از خوشهها، با یک معیار اندازه گیری میشود و تخمین تعداد بهینه K از طریق مقایسه مقادیر معیارهای محاسبه شده، حاصل میشودکه این روش درخوشهبندی افرازی مناسب است. بارمحاسباتی تشخیصK برای مجموعه دادههای بزرگ به طور چشمگیری افزایش خواهد یافت. علاوه بر این، الگوریتمهای خوشهبندی افرازی3، تکراری و مانند الگوریتمهای تپه نوردی4 هستند. بنابراین، به انتخاب افراز اولیه حساس میباشند. از آنجا که توابع ضوابط استفاده شده غیر خطی و چند مدله هستند این الگوریتمها به مینیمم محلی همگرا و نهایتا منجر به نتایج نادرست خوشهبندی میشوند.[3]
در این تحقیق، یک الگوریتم خوشهبندی ژنتیک دو مرحله ای(TGCA)5 به منظور غلبه بر مشکلات خوشهبندی بررسی میشود. در این روش کروموزمهایی با طول متغیر انتخاب میشوند تا تعداد بهینه خوشهها و مراکز خوشهها را جستجو کنند. با استراتژی عملیات انتخاب و جهش دو مرحلهای، احتمال انتخاب واحتمال جهش با پایداری تعداد خوشهها در جمعیت تغییر میکند: این الگوریتم، خوشهبندی را با تعداد خوشههای متفاوت انجام میدهد. بدین صورت که در ابتدا جستجوی تعداد بهینه خوشهها و سپس بهترین افراز از داده ها را مییابد. همچنین برای غلبه بر حساسیت الگوریتمها به انتخاب افراز اولیه از الگوریتم، افراز بندی با حداکثر بازه ی ویژگیها6برای مقداردهی اولیه مراکز خوشهها استفاده شده است. الگوریتم خوشهبندی ژنتیک دو مرحله ای، الگوریتم K-means را با الگوریتم ژنتیک ترکیب میکند. نمایش مقدار بهینه محلی K توسط الگوریتم K-means و جستجوی مقدار بهینه سراسری با k های متفاوت از طریق الگوریتم ژنتیک حاصل میشود.
این تحقیق با بحثی در مورد مفهوم خوشهبندی شروع شده و پس از آن الگوریتم ژنتیک به اختصار توضیح داده میشود و سپس به معرفی الگوریتم بررسی شده در این مقاله پرداخته می شود. بدنبال آن ارائه مثال تجربی و در انتها نتیجه گیری پیرامون الگوریتم معرفی شده ارائه میشود.
2 خوشهبندی
خوشه به مجموعهای از دادهها گفته میشود که به هم شباهت دارند. در خوشهبندی سعی میشود تا دادهها به خوشههایی تقسیم شوند که شباهت بین داده های درون خوشه ای حداکثر و شباهت میان داده های بین دو خوشه متفاوت حداقل شود. در فرهنگ لغت وبستر7 ، تحلیل خوشه، تکنیک دسته بندی آماری اعضای یک جمعیت است که از طریق مقایسه کمی ویژگیهای آنها که متعلق به گروههای متفاوتی هستند، صورت میگیرد. مثالی از خوشهبندی در شکل 1 الف و خوشههای مورد نظر در شکل1ب نمایش داده شده است که مشاهده می شود که داده های نزدیک به هم در یک گروه قرار گرفته اند که با شماره گروه در شکل 1 ب مشخص شده است. .[1]
3
شکل 1ب: خوشههای نهایی شکل 1 الف: خوشههای اولیه
هر الگوریتم خوشهبندی، دارای تعدادی از عناصر رایج و متداول است که لازم است پیش از طبقهبندی تعیین گردند. یک الگوریتم خوشهبندی که شامل چهار مرحله اصلی است : [4]
-1ارائه (نمایش) الگو
-2طراحی یا انتخاب الگوریتم خوشهبندی
-3ارزیابی خوشهبندی
-4تفسیر خوشهبندی بمنظور ارائه خوب، یک الگو شامل دو عمل اصلی انتخاب و استخراج ویژگیها می باشد. انتخاب مشخصه ها (یا ویژگی ها)
عبارتست از انتخاب ویژگیهایی که برای ارائه داده به آنها توجه بیشتری داریم و شناسایی بهترین خصیصهها برای خوشهبندی است، در حالیکه استخراج مشخصه ها عبارتست از وظیفه کشف ویژگیهای جدید از طریق نوعی تغییر شکل ویژگیهایی که قبلا انتخاب کردیم، یعنی به کاربر این امکان را میدهد که خصیصههای جدیدی را از خصیصههای اولیه تولید کند.
مرحله طراحی یا انتخاب الگوریتم خوشهبندی، ترکیب انتخاب یک مقیاس تشابه (نزدیکی) و ساخت یک تابع ارزیابی است. الگوها براساس شباهت به یکدیگر گروهبندی میشوند. بدیهی است که انتخاب مقیاس تشابه بر نتایج خوشهبندی تاثیرگذار است.
زمانیکه الگوریتم خوشهبندی اجرا می شود، اندازه گیری کیفیت خوشههای مشخص شده بسیار مهم خواهد بود چراکه روش های متفاوت، خوشه های متفاوتی ایجاد میکند. بنابراین شاخصهای ارزیابی بسیار موثر و مهم هستند که کاربر بتواند از نتایج خوشهبندی که از الگوریتمها مشتق شده استفاده کند.
در کل، زمانیکه خوشهبندی به پایان می رسد، تعداد خوشه ها نامشخص است. یکی از مهمترین برنامه های کاربردی برای اعتبارسنجی خوشه ها علاوه بر ارزیابی نتایج خوشهبندی، تشخیص تعداد بهینه خوشه ها است.
3 الگوریتم ژنتیک1
الگوریتم ژنتیک سعی در انتقال ویژگیها و ژنهای یک پاسخ و راهحل مناسب به نسلهای بعدی دارد و به تدریج پس از طی شدن نسلهای متوالی، متوسط کیفیت جامعه را به پاسخ بهینه نزدیک میسازد. به عبارتی میتوان گفت الگوریتم ژنتیک تکنیک برنامه نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده میکند که بر پایه عملکرد انتخاب ژنتیک طبیعی بنا شده است. الگوریتم ژنتیک برخلاف سایر روش های جستجو، با یک مجموعه ابتدایی از جواب های تصادفی که جمعیت اولیه2
4
نامیده میشود، آغاز میگردد. هر عضو در جمیعت، یک کروموزوم1 نامیده می شود. که نمایانگر یک راهحل برای مسئله موجود می باشد. یک کروموزوم رشتهای از علائم است که دربردارنده پارامترهای مسئله می باشد. طی هر تکرار الگوریتم ژنتیک، مجموعه جدیدی از کروموزوم ها تولید می شود. جمعیت در زمان معلوم را نسل2 می نامند. در هر نسل قابلیت کروموزوم ها توسط تابع برازندگی3 که یک کروموزوم را با توجه به تابع هدف مسئله برآورد می کند، تعیین می شود. انتخاب کروموزوم ها برای تولید کروموزوم های نسل بعد براساس میزان تطابق آن ها که بوسیله تابع تطابق شده4 ، تعیین می شود، صورت می پذیرد.
پس از انتخاب کروموزوم ها، طی فرآیند باز تولید5 عملگرهای الگوریتم ژنتیک روی آن ها اعمال می شــود. این عملگرها عبارتند از :عملگر تقاطعی 6 و عملگر جهش.7 به کروموزوم هایی که از این طریق تولید می شــوند فرزند 8 اطلاق می شــود. ســپس برازندگی فرزندان، ارزیابی شده و توسط یکی از رویه های انتخاب کروموزوم های بهتر انتخاب و به نسل بعد منتقل می گردند. هر تکرار این روند یک نسـل را ایجاد می نماید. تعداد نسل ها به دلخواه تعیین می شود. در این فرآیند الگوریتم به بهترین کروموزوم همگرا می شـود که نمایانگر جواب بهینه مسئله می باشد. الگوریتم زمانی متوقف می شود که یکی از معیارهای توقف برآورده شود .[5]
4 پیشینه تحقیق
با توجه به مسائل و مشکلاتی که پژوهشگران هنگام کار با مسائل خوشهبندی مواجه شدند و به منظور غلبه بر این مشکلات، برخی محققان، الگوریتم ژنتیک را در آنالیز خوشه به کار برده اند.[5] بدین ترتیب، بر اساس ویژگی بهینه سازی سراسری الگوریتمهای ژنتیک، ضوابط اعتباریابی خوشهبندی را به عنوان تابع برازندگی برای هدایت الگوریتم به منظور یافتن تعداد بهینه خوشهها استفاده کرده اند.
عثمان و همکارانش[6]9 الگوریتمی ترکیبی برای حل خوشهبندی خودکار هستی شناسی ژن پیشنهاد دادندکه در این روش از الگوریتم ترکیبی ژنتیک10 و الگوریتم تجزیه و ترکیب11 استفاده شده است. همچنین در این روش از فاصله انسجام و اتصال12 به منظور تعیین کیفیت خوشهبندی استفاده شده است. ایده کاربرد این فاصله، ایجاد خوشههای مناسب با ماکزیمم کردن میزان تعامل بین واژه ها در یک خوشه (انسجام زیاد) و کاهش میزان تعامل بین واژه ها در خوشههای متفاوت(اتصال کم) است.
لیو و همکارانش[5]13 تعداد بهینه خوشهها را ازطریق Niched Pareto K-means Genetic Algorithmبدست آوردند. در این روش یک الگوریتم ژنتیک چند-هدفه(MOKGA)14 به منظور حل مساله خوشهبندی استفاده شده است.
5
