روشی نوین جهت خوشه بندی داده مبتنی بر ترکیب الگوریتم‌های بهینه‌سازی ژنتیک و کرم شب‌تاب
محورهای موضوعی : سامانه های پردازشی و ارتباطی چند رسانه ای هوشمند
مهسا افسردیر
1
(دانشگاه آزاد اسلامی واحد علوم تحقیقات، دانشکده فنی مهندسی، گروه مهندسی کامپیوتر، تهران، ایران)
منصوره افسردیر
2
(دانشگاه آزاد اسلامی واحد دزفول، دانشکده فنی مهندسی، گروه مهندسی پزشکی دزفول، ایران)
کلید واژه: الگوریتم ژنتیکی کرم شب تاب, الگوریتم کرم شب تاب, الگوریتم ژنتیک, داده کاوی, خوشه بندی k-means,
چکیده مقاله :
یکی ازمسائل مهم درداده‌کاوی خوشه‌بندی است که بدون هدف ازپیش تعیین شده‌ای داده‌ها را بر اساس شباهت درون خوشه‌ها تقسیم‌بندی می‌کند. از روش‌های متداول خوشه‌بندی الگوریتم k-means است که بادریافت ورودی، داده‌هارابه k خوشه تقسیم‌بندی می‌کند. یکی ازمعایب این روش حساسیت به شرایط اولیه است که منجربه کاهش دقت درخوشه‌بندی می‌شود. از روش‌های بهبود عملکرد k-means می‌توان استفاده ازالگوریتم‌های فراابتکاری را نام برد. در این پژوهش به دو روش بهینه‌سازی ژنتیک و کرم شب‌تاب پرداخته شده است و الگوریتم جدیدی تحت عنوان الگوریتم ژنتیکی کرم‌شب‌تاب جهت بهینه‌سازی خوشه‌بندی k-means ارائه شده است. الگوریتم کرم‌شب‌تاب از الگوریتم‌های هوش جمعی است که از ویژگی نورچشمک زن کرم‌شب‌تاب الهام گرفته است و الگوریتم ژنتیک نوعی از الگوریتم‌های فراابتکاری است که از تکنیک-های زیست‌شناسی مانند وراثت و جهش استفاده می‌کند. در الگوریتم k-means برای اینکه مراکز خوشه به صورت تصادفی انتخاب می شوند، خوشه‌بندی دقت لازم را ندارد. با استفاده از الگوریتم‌های فراابتکاری سعی در بدست آوردن مراکز دقیق خوشه‌ها داشته و در نتیجه آن، خوشه-بندی صحیح می‌باشیم. در روش پیشنهادی، ابتدا الگوریتم k-means را روی داده‌های ورودی اجراکرده و خوشه‌بندی انجام می‌شود. سپس مضربی از مراکز خوشه که دراین الگوریتم بدست آمده است را به عنوان حد پایین و حد بالای الگوریتم پیشنهادی استفاده می‌کنیم. جمعیت اولیه به صورت تصادفی بین حد پایین و حد بالا تولید می‌شود. در حلقه اصلی الگوریتم جمعیت را به دو دسته جمعیت مساوی تقسیم می نماییم، بر روی دسته اول الگوریتم ژنتیک را اجرا می‌کنیم، بر روی دسته دوم بر اساس الگوریتم کرم‌شب‌تاب موقعیت‌های جدید را بدست می‌آوریم. حال جمعیت قبلی و جمعیت جدید بدست امده از الگوریتم ژنتیک و جمعیت جدید بدست امده از الگوریتم کرم‌شب‌تاب را تلفیق کرده وآن‌ها را از خوب به بد مرتب می‌کنیم و به تعداد مورد نیاز از آن‌ها را انتخاب و به ابتدای حلقه می‌رویم. این فرایند را تا برقراری شرط توقف ادامه می‌دهیم. درپایان الگوریتم k-means، الگوریتم کرم شب‌تاب، الگوریتم ژنتیک و الگوریتم پیشنهادی بر روی سه مجموعه داده اعمال شده و نتایج مورد مقایسه قرار گرفته است.نتایج شبیه‌سازی نشان می‌دهد که الگوریتم ژنتیکی کرم‌شب‌تاب عملکرد بهتری در مقایسه با سایر روش‌ها داشته است.
Introduction: With the progress of technology and increasing the volume of data in databases, the demand for fast and accurate discovery and extraction of databases has increased. Clustering is one of the data mining approaches that is proposed to analyze and interpret data by exploring the structures using similarities or differences. One of the most widely used clustering methods is the k-means. In this algorithm, cluster centers are randomly selected and each object is assigned to a cluster that has maximum similarity to the center of that cluster. Therefore, this algorithm is not suitable for outlier data since this data easily changes centers and may produce undesirable results. Therefore, by using optimization methods to find the best cluster centers, the performance of this algorithm can be significantly improved. The idea of combining firefly and genetics algorithms to optimize clustering accuracy is an innovation that has not been used before.Method: In order to optimize k-means clustering, in this paper, the combined method of genetic algorithm and firefly worm is introduced as the firefly genetic algorithm.Findings: The proposed algorithm is evaluated using three well-known datasets, namely, Breast Cancer, Iris, and Glass. It is clear from the results that the proposed algorithm provides better results in all three datasets. The results confirm that the distance between clusters is much less than the compared approaches.Discussion and Conclusion: The most important issue in clustering is to correctly determine the cluster centers. There are a variety of methods and algorithms that performs clustering with different performance. In this paper, based on firefly metaheuristic algorithms and genetic algorithms a new method has been proposed for data clustering. Our main focus in this study was on two determining factors, namely the distance within the data cluster (distance of each data to the center of the cluster) and the distance that the headers have from each other (maximum distance between the centers of the clusters). In the k-means algorithm, clustering is not accurate since the cluster centers are selected randomly. Employing firefly algorithms and genetics, we try to obtain more accurate centers of the clusters and, as a result, correct clustering.
_||_
