یک روش خوشه‌بندی جدید: الگوریتم کلونی زنبور مصنوعی(ABC)
چکیده
الگوریتم کلونی زنبور عسل (ABC)[1] را می‌توان یکی از جدیدترین الگوریتم‌های بهینه‌سازی در نظر گرفت که رفتار گروهی هوشمند یک دسته از زنبورهای عسل را شبیه‌سازی می‌کند. تجزیه‌وتحلیل خوشه‌بندی که در بسیاری از اپلیکیشن ها و رشته‌ها کاربرد دارد، ابزاری مهم و یک وظیفه‌ی تشریحی بوده که به منظور تشخیص گروه‌های همگن از اشیائ بر مبنای مقادیر صفات آنها کاربرد دارد. در این راستا، از ABC برای خوشه‌بندی داده‌ها بر روی مسائل بنچ مارک استفاده شده و کارائی الگوریتم ABC نیز با الگوریتم بهینه‌سازی ازدحام ذرات (PSO)[2] و نه تکنیک دسته‌بندی دیگر مورد مقایسه قرار گرفت. سیزده مجموعه‌ی داده‌ای تست از مخزن یادگیری ماشین UCI نیز به منظور اثبات نتایج تکنیک‌ها بکار گرفته شد. نتایج شبیه‌سازی نشان می‌دهد که الگوریتم ABC می‌تواند به شکلی کارآمد برای خوشه‌بندی داده‌ای چند متغیره بکار گرفته شود.
واژگان کلیدی: دسته‌بندی، تجزیه‌وتحلیل خوشه‌بندی، الگوریتم کلونی زنبور عسل، بهینه‌سازی ازدحام ذرات
مقدمه
خوشه‌بندی به عنوان ابزاری مهم برای کاربردهای مختلف در داده‌کاوی، تجزیه‌وتحلیل داده‌های آماری، فشرده‌سازی داده‌ها و رقمی سازی بردار، می‌تواند داده‌ها را در قالب خوشه‌ها ( یا گروه‌ها) جمع آوری نماید به طوری که داده‌های موجود در هر خوشه از سطح بالایی از تشابه برخوردار بوده و بسیار متفاوت از سایر خوشه‌ها باشند [۱-۳]. هدف خوشه‌بندی این بوده که داده‌ها را در قالب خوشه‌ها دسته‌بندی کرد به طوری که تشابه بین اعضای داده‌ای داخل یک خوشه در بیشترین سطح ممکن قرار داشته باشد و در عین حال تفاوت بین اعضای موجود در یک خوشه با اعضای سایر خوشه‌ها در کمترین سطح قرار داشته باشد.
الگوریتم‌های خوشه بندی را می‌توان به دو دسته‌ی خوشه‌بندی سلسله مراتبی و پارتیشنی تقسیم کرد [۳-۵]. خوشه‌بندی سلسله مراتبی اقدام به گروه بندی اشیائ داده‌ای در یک دنباله ای از پارتیشن‌ها می‌کند، یعی از خوشه‌های تکی گرفته تا یک خوشه ای که شامل همه‌ی عناصر می‌باشد ( و بر عکس). رویه‌های سلسله مراتبی می‌توانند متفرقه و متراکم باشند. الگوریتم‌های متراکم، هر المان را به صورت یک خوشه‌ی تکی آغاز کرده و آنها را در قالب خوشه‌های بزرگ‌تر و متوالی ادغام می‌سازد؛ الگوریتم‌های متفرقه نیز با کل مجموعه شروع شده و مجموعه را به خوشه‌های کوچک‌تر متوالی [۶,۷] تقسیم می‌کند. رویه‌های پارتیشنی که مد نظر این مقاله می‌باشد تلاش کرده تا مجموعه‌های داده‌ای را به یک مجموعه از خوشه‌های گسسته و بدون ساختار سلسله مراتبی تبدیل سازد. رایج‌ترین الگوریتم‌های خوشه‌بندی، الگوریتم‌های خوشه‌بندی مبتنی بر نمونه می‌باشند که در آن، هر خوشه به وسیله‌ی یک مرکز از خوشه نشان داده شده و تابع هدف استفاده شده (یک تابع خطای جذر) نیز برابر با جمع فاصله از الگو تا مرکز می‌باشد [۸].
رایج‌ترین کلاس از الگوریتم‌های خوشه‌بندی، الگوریتم k-mean بوده که مبتنی بر مرکز بوده و یک الگوریتم ساده و سریع می‌باشد [۹]. اگرچه این الگوریتم در سطح زیادی بسته به وضعیت اولیه بوده و معمولاً از موقعیت شروع جستجو، به سمت یک بهینگی محلی حرکت می‌کند. به منظور غلبه بر مسئله‌ی بهینگی محلی، پژوهشگران حوزه‌های مختف در حال بکار گیری خوشه‌بندی سلسله مراتبیف خوشه‌بندی مبتنی بر پارتیشن، خوشه‌بندی مبتنی بر چگالی و خوشه‌بندی مبتنی بر هوش مصنوعی می‌باشند، که در این راستا می‌توان به روش‌هایی مانند استاتیک[۱۰]، نظریه‌ی گراف [۱۱]، الگوریتم‌های بیشینه سازی انتظار [۱۲]، شبکه‌های عصبی مصنوعی [۱۳-۱۶]، الگوریتم‌های تکاملاتی [۱۷-۱۸]، الگوریتم‌های هوش ازدحام [۱۹-۲۴] و غیره اشاره کرد.
در این مقاله، الگوریتم بهینه‌سازی کلونی زنبور عسل (ABC) که به وسیله‌ی رفتار گروهی زنبورهای عسل برای تعدادی مسئله‌ی بهینه‌سازی عددی تشریح می‌شود بکار گرفته می‌شود تا از آن برای مسائل بنچ مارک دسته‌بندی استفاده شود (۱۳ مجموعه‌ی داده‌ای). کارائی این الگوریتم بر روی خوشه‌بندی نیز با نتایج الگوریتم بهینه‌سازی ازدحام ذرات بر روی همان مجموعه‌ی داده‌ای مورد مقایسه قرار گرفته است و نتایج آن در [۲۶] ارائه شده است.
الگوریتم‌های ABC و PSO در کلاس یکسانی از الگوریتم‌های بهینه‌سازی هوش مصنوعی، الگوریتم‌های مبتنی بر جمعیت قرار گرفته و بر اساس ایده گیری و الهام از هوش ازدحام طراحی شده‌اند. علاوه بر مقایسه‌ی این الگوریتم‌ها، کارائی الگوریتم ABC نیز با مجموعه ای از تکنیک‌های دسته‌بندی که در [۲۶] داده شده است مقایسه شده است. این مقاله به صورت زیر سازمان دهی شده است. در بخش دوم به تشریح مسئله‌ی خوشه‌بندی پرداخته و پیاده سازی الگوریتم ABC را در بخش سوم ارائه می‌دهیم و به دنبال آن آزمایش‌ها و نتایج آنرا در بخش چهار ارائه داده و در نهایت در بخش پنچم نیز با ارائه‌ی خلاصه ای از مشاهدات و جهت گیری‌های پژوهشی آینده، نتایج پایانی را ارائه می‌دهیم.
A novel clustering approach: Artificial Bee Colony (ABC) algorithm
Abstract
Artificial Bee Colony (ABC) algorithm which is one of the most recently introduced optimization algorithms, simulates the intelligent foraging behavior of a honey bee swarm. Clustering analysis, used in many disciplines and applications, is an important tool and a descriptive task seeking to identify homogeneous groups of objects based on the values of their attributes. In this work, ABC is used for data clustering on benchmark problems and the performance of ABC algorithm is compared with Particle Swarm Optimization (PSO) algorithm and other nine classification techniques from the literature. Thirteen of typical test data sets from the UCI Machine Learning Repository are used to demonstrate the results of the techniques. The simulation results indicate that ABC algorithm can efficiently be used for multivariate data clustering.
لینک مقاله لاتین:
https://www.sciencedirect.com/science/article/pii/S1568494609002798
لطفاً براي ارسال دیدگاه، ابتدا وارد حساب كاربري خود بشويد