بخشی از مقاله
چکیده
خوشهبندی یکی از تکنیکهای دستهبندی بدون ناظر است، که دادگان را بر اساس معیار شباهت یا عدم شباهت به تعداد مشخصی خوشه تقسیم میکند. اتوماتای یادگیر سلولی - CLA - یک سیستم تصمیمگیری تطبیقی بوده که در مسائل بهینهسازی کاربرد دارد. این سیستم، عمل بهینه موجود در مجموعه اعمالش را از طریق تعامل با محیط تصادفی و ارتباط با همسایگان خود یاد میگیرد و عملکرد آتی خود را بر پایه انتخاب عمل بهینه، بهبود میبخشد. اتوماتای یادگیر سلولی نامنظم - ICLA - یکی از انواع تعمیمیافته اتوماتای یادگیر سلولی است که برای مدلسازی مسائلی که ساختار منظم ندارند، مانند مسائل مبتنی بر گراف، استفاده میگردد. در این مقاله از مدل ICLA برای حل مسئله خوشهبندی دادگان استفاده شده است. الگوریتم بر روی دیتاستهای متعدد آزمایش شده و نتایج بدست آمده با روشهای Kmeans، FCM و SOM مقایسه شده است. نتایج حاصل شده بیان از کارایی و دقت قابل قبول روش پیشنهادی دارد.
واژگان کلیدی: خوشهبندی دادگان، اتوماتای یادگیر سلولی، اتوماتای یادگیر سلولی نامنظم.
-1 مقدمه
خوشهبندی یک تکنیک دستهبندی بدون نظارت است که در آن مجموعهای از دادهها که معمولأ بردارهایی در فضای چند بعدی میباشند، بر اساس یک معیار شباهت یا عدم شباهت، به تعداد مشخصی خوشه تقسیم میشوند. فرض کنید که مجموعه دادهها، بردارهایی در فضای N بعدی هستند و خوشهها نواحی پیوستهای از این فضا را تشکیل میدهند که در آن نواحی، چگالی دادهها بیشتر از سایر نقاط است. این خوشهها توسط نواحی از یکدیگر جدا شده که معمولأ چگالی نقاط در این نواحی جدا کننده پایین است.روشهای متعددی برای تعریف شباهت بین دادهها به صورت کمی وجود دارد که فاصله اقلیدسی و فاصله کسینوسی از مرسومترین آنها میباشد. نوع دادگان مورد استفاده در خوشه بندی، سرعت خوشهبندی، دقت و بسیاری پارامترهای دیگر باعث ارائه روشها و الگوریتمهای متنوعی برای خوشهبندی دادگان شده است.
روشهای خوشهبندی عمومأ به دو دسته کلی سلسله مراتبی و روش جزءبندی تقسیم میشوند . - Han, Kamber, & Tung , 2001 - در روشهای سلسله مراتبی، خوشهبندی ساختاری شبیه درخت دارد، بطوریکه تمامی دادهها به اولین گره درخت متعلق بوده و هرچه در شاخههای درخت پیش میرویم، خوشهبندی دقیقتر میشود. در روشهای جزءبندی، دادهها بر پایه مراکز خوشه تقسیم شده و بر اساس معیار شباهت، تعلق داده به یکی از خوشهها تعیین میشود. از روشهای کارآمد در زمینه خوشهبندی، میتوان به خوشهبندی -Kمیانگین - Jain, 2010 - - Kmeans - ، خوشهبندی -Cمیانگین فازی Bezdek, - - FCM - page10 - Ehrlich, & Full, 1984، خوشهبندی نگاشت خودسازمانده - Vesanto & Alhoniemi, 2000 - - SOM - ، خوشهبندی طیفی - Ng, Jordan, & Weiss, 2002 - ، خوشهبندی سلسله مراتبی - Johnson, 1967 - ، خوشهبندی مورچگان - Chen, Xu, & Chen, 2004 - و خوشهبندی تکاملی - Rastegar, Arasteh, Hariri, & - Meybodi, 2004 اشاره کرد.
اتوماتای یادگیر سلولی - Meybodi, Beigy, & Taherkhani, 2001 - - CLA - 1، سیستمی با رفتار برآیندی است. در این مدل اجزاء سادهای به نام سلول از طریق ارتباط محلی و بر اساس قانون محلی حاکم، اطلاعات درون خود را پردازش مینمایند. هر اتوماتای یادگیر سلولی، از یک اتوماتای سلولی تشکیل شده که هر سلول آن به یک یا چند اتوماتای یادگیر مجهز میباشد. وضعیت هر سلول در هر مرحله بر اساس عمل انتخابی اتوماتای یادگیر متناظرش مشخص میشود. در این مدل قانون محلی در محیط حاکم بوده و بر اساس این قانون، عمل انتخاب شده سلول، پاداش و یا جریمه دریافت مینماید. دریافت پاداش و یا جریمه باعث بروز شدن ساختار اتوماتای یادگیر سلولی به منظور نیل به یک هدف مشخص میگردد. از زمان معرفی اتوماتای یادگیر سلولی تاکنون، انواع گوناگونی از این مدل ارائه شده است.
از آن جمله میتوان به انواع اتوماتای یادگیر سلولی ناهمگام - Beigy & Meybodi, 2008 - ، اتوماتای یادگیر سلولی همگام باز - Beigy & Meybodi, 2007 - و مدلهای ترکیبی محاسبات تکاملی بر مبنای اتوماتای یادگیر سلولی - Shibani, - 2007 و بهینه سازی دسته جمعی ذرات با اتوماتای یادگیر سلولی - Shibani, 2007 - اشاره نمود. این مدلها در کاربردهای وسیعی چون پردازش تصاویر - کاهش نویز، تشخیص لبه و قطعهبندی - - Meybodi & Kharazmi,page9 - 2004، تخصیص منابع در شبکه های موبایل - تخصیص کانال و پذیرش کانال - ; Beigy & Beigy, 2004 - 2004Meybodi, 2003 , - ، مدل ???? پدیدهها - انتشار شایعه و بازار اقتصادی - - Meybodi & Khojasteh, - ; Meybodi & Taherkhani, 20012001 و خوشه بندی استفاده شده است.
یک اتوماتای یادگیر سلولی نامنظم - Esnaashari & Meybodi, 2014 - - ICLA - 2، یک اتوماتای یادگیر سلولی است که محدودیت ساختار گرید مستطیلی در CLA سنتی در آن حذف شده است. این تعمیم مورد نیاز است، زیرا کاربردهایی نظیر شبکههای حسگر بیسیم، سیستمهای شبکه ایمن، کاربردهای مبتنی بر گراف، و غیره وجود دارد که قابلیت مدلسازی با گریدهای مستطیلی شکل را ندارند.در این مقاله از مدل ICLA برای حل مسئله خوشهبندی دادگان استفاده شده است. الگوریتم بر روی دیتاستهای Iris، Wine، Glass و نرمال چندین بار آزمایش شده است. برای ارزیابی نتایج از معیار های زمان اجرا، درصد کمینه خطا، سیلهوت، فاوکز مالوز و همچنین F-measure استفاده شده است. برای ارزیابی کارایی روش پیشنهادی، نتایج بدست آمده با روشهای Kmeans، FCM و SOM مقایسه شده است. ادامه مقاله بدین صورت سازماندهی شده است. در بخش 2، مدل خوشهبندی ICLA بیان میگردد. در بخش 3، آزمایشات صورت گرفته همراه با تجزیه و تحلیل نتایج ارائه میشود. نهایتأ در بخش 4 نتیجهگیری مقاله بیان میشود.
-2 مدل خوشهبندی اتوماتای یادگیر سلولی نامنظم - ICLA -
در روش خوشهبندی پیشنهادی از اتوماتای یادگیر سلولی نامنظم بسته و همگام استفاده شده است. یک ICLA بعنوان یک گراف بدون جهت تعریف میشود که در آن، هر رأس بیانگر یک سلول است که با یک اتوماتای یادگیر مجهز شده است، بطوریکه در شکل 1 نشان داده شده است. اتوماتای یادگیر مقیم در یک سلول خاص وضعیت - عمل - خود را بر اساس بردار احتمال خود مشخص میکند. شبیه به CLA، قانونی وجود دارد که ICLA تحت آن عمل میکند. قانون CLA و عملهای انتخاب شده بوسیله LA های همسایه یک LA خاص، سیگنال تقویتی به LA مقیم در یک سلول را مشخص میکنند. LA های همسایه هر LA خاص محیط محلی آن سلول را تشکیل میدهند. محیط محلی یک سلول غیر ایستا است زیرا بردارهای احتمال عمل LA های همسایه در طول تکامل ICLA تغییر میکنند.
