مقاله:روش نوین خوشه‌بندى تركيبي با استفاده از سیستم ایمنی مصنوعی و سلسله مراتبی

فایل زیر شامل

۱- عدد فایل ورد(قابل ویرایش+ و تایپ کامل فرمول ها) مقاله به همراه فایل پی دی اف به تعداد ۱۶ صفحه است

روش نوین خوشه‌بندى تركيبي با استفاده از سیستم ایمنی مصنوعی و سلسله مراتبی

احمد رضا جعفریان مقدم[۱]*، فرناز برزین‌پور۲، محمد فتحیان۳

۱* دانشکده عمران و حمل و نقل، دانشگاه اصفهان، اصفهان ۷۳۴۴۱-۸۱۷۴۶، ایران

۲، ۳ دانشکده مهندسی صنایع، دانشگاه علم و صنعت ایران، تهران ۱۳۱۱۴-۱۶۸۴۶، ایران

چکیده

سیستم ایمنی مصنوعی (AIS) یکی از مهمترین الگوریتم‌های متاهیوریستیک به منظور حل مسائل بسیار پیچیده می‌باشد. از این الگوریتم می‌توان در تحلیل خوشه‌بندی داده‌ها استفاده نمود. علی‌رغم اینکه AIS قادر است پیکربندی فضای جستجو را به خوبی نمایش دهد اما تعیین خوشه‌های داده‌ها به طور مستقیم با استفاده از خروجی آن بسیار مشکل است. بر این اساس در این مقاله الگوریتم دو مرحله‌ای پیشنهاد شده است. در مرحله اول با استفاده از الگوریتم AIS پیشنهادی، فضای جستجو مورد بررسی قرار گرفته و پیکربندی فضا تعیین می‌شود و در مرحله دوم با استفاده از روش خوشه‌بندی سلسله ‌مراتبی، خوشه‌ها و تعداد آنها مشخص می‌شود. در انتها الگوریتم پیشنهادی بر روی نمونه واقعی متشکل از داده‌های زلزله در ایران پیاده‌سازی و با نتایج الگوریتم مشابه مقایسه شده است. نتایج نشان داد که الگوریتم پیشنهادی توانسته است نقایص موجود در AIS و روش خوشه‌بندی سلسله مراتبی را پوشش دهد و از طرفی از دقت و سرعت قابل قبولی برخوردار است.

واژه‌‌های کلیدی: تحلیل خوشه‌بندی؛ سیستم ایمنی مصنوعی (AIS)؛ خوشه‌بندی سلسله مراتبی.

 

New Clustering Technique using Artificial Immune System and Hierarchical technique

Ahmad Reza Jafarian-Moghaddam1*, Farnaz Barzinpour2, Mohammad Fathian3

۱*, Faculty of Civil Engineering and Transportation, University of Isfahan, Isfahan 81746-73441, Iran

۲, ۳ School of Industrial Engineering, Iran University of Science and Technology, Tehran 16846-13114, Iran[2]

Abstract

Artificial immune system (AIS) is one of the most meta-heuristic algorithms to solve complex problems. With a large number of data, creating a rapid decision and stable results are the most challenging tasks due to the rapid variation in real world. Clustering technique is a possible solution for overcoming these problems. The goal of clustering analysis is to group similar objects.

AIS algorithm can be used in data clustering analysis. Although AIS is able to good display configure of the search space, but determination of clusters of data set directly using the AIS output will be very difficult and costly. Accordingly, in this paper a two-step algorithm is proposed based on AIS algorithm and hierarchical clustering technique. High execution speed and no need to specify the number of clusters are the benefits of the hierarchical clustering technique. But this technique is sensitive to outlier data.

So, in the first stage of introduced algorithm using the proposed AIS algorithm, search space was investigated and the configuration space and therefore outlier data are determined. Then in second phase, using hierarchical clustering technique, clusters and their number are determined. Consequently, the first stage of proposed algorithm eliminates the disadvantages of the hierarchical clustering technique, and AIS problems will be resolved in the second stage of the proposed algorithm.

In this paper, the proposed algorithm is evaluated and assessed through two metrics that were identified as (i) execution time (ii) Sum of Squared Error (SSE): the average total distance between the center of a cluster with cluster members used to measure the goodness of a clustering structure. Finally, the proposed algorithm has been implemented on a real sample data composed of the earthquake in Iran and has been compared with the similar algorithm titled Improved Ant System-based Clustering algorithm (IASC). IASC is based on Ant Colony System (ACS) as the meta-heuristics clustering algorithm. It is a fast algorithm and is suitable for dynamic environments. Table 1 shows the results of evaluation.

Table 4: Compare the two algorithms

Proposed algorithm IASC Alg.
۱۲ ۱۸ Execution time (s)
۵/۳ ۹/۴ SSE

 

The results showed that the proposed algorithm is able to cover the drawbacks in AIS and hierarchical clustering techniques and the other hand has high precision and acceptable run speed.

Keywords: Clustering Analysis; Artificial immune system (AIS); Hierarchical Clustering.

 

 

  1. مقدمه

سیستم ایمنی طبیعی ([۳]NIS) شبکه پیچیده‌ای از بافت‌ها، سلول‌ها و گلبولها است که وظیفه‌اش حفظ بدن در مقابل عوامل بیماری‌زا و همچنین کاهش صدمات وارده به بدن و اطمینان از عملکرد پیوسته اجزای خود است. بدین منظور سیستم ایمنی یک سیستم خودکنترل محسوب می‌شود. این سیستم بسته به نوع حملاتی که توسط عوامل بیماری‌زا به بدن صورت می‌گیرد دارای عملکرد متفاوتی بوده و برای این منظور دارای سطوح مختلف عملکردی می‌باشد. [۴]AIS دارای تعاریف مختلفی متناسب با زمینه‌های کاربرد آن است. در [۲]، AIS را یک متدولوژی هوشمند برگرفته از NIS می‌داند که قادر است مسائل جهان واقعی را حل کند. در این تعریف AIS به عنوان یک متدولوژی در نظر گرفته شده است. د [۳] AIS را یک سیستم محاسباتی برگرفته از NIS تشریح کرده است. تعریف کاملتر برای AIS در [۴] ارائه شده است. براساس این تعریف AIS یک سیستم تطابقی برگرفته از نظریه ایمنی‌شناسی است که وظایف، فرآیندها، مدل‌ها و اصول NIS را مورد توجه قرار می‌دهد. از AIS در زمینه‌های مختلفی چون مسائل یادگیری ماشین [۵]، مسائل بهینه‌سازی [۶، ۷]، داده‌کاوی [۸]، ایمنی کامپیوترها [۹-۱۱] و غیره استفاده شده است.

روش خوشه‌بندی از مهمترین روش‌های داده‌کاوی است که امروزه اهمیت آن در دنیای واقعی بر کسی پوشیده نیست. با بزرگتر شدن بانک‌های داده‌ای، تلاش محققین به منظور یافتن روش‌های خوشه‌بندی کارا و موثر متمرکز شده است تا بدین طریق بتوانند زمینه تصمیم‌گیری سریع و منطبق با واقعیت را فراهم آورند. تحلیل خوشه‌بندی شاخه‌ای از تحلیل آماری چند متغیره بوده و روشی به منظور گروه‌بندی داده‌های مشابه در خوشه‌های یکسان است [۱۲، ۱۳]. این روش روشی بر پایه داده می‌باشد که سعی دارد با جستجوی مشابهت‌های بین داده‌ها، آنها را خوشه‌بندی نماید [۱۲، ۱۳]. این شباهت می‌تواند براساس قوانین نظیر نزدیکترین فاصله، دورترین فاصله و غیره باشد. روش‌های خوشه‌بندی سعی دارند با کشف روابط موجود در بین داده‌های جدید، روش خوشه‌بندی خود را بهبود بخشند از این رو روش‌های خوشه‌بندی به روش‌های یادگیرنده نیز شهرت یافته‌اند [۱۴، ۱۵] به نحوی که قادرند پس از تعیین خوشه‌ داده‌های مختلف، خوشه داده جدید که به مجموعه اضافه می‌شود با صرف کمترین زمان مشخص نمایند [۱۶]. انواع روش خوشه‌بندی عبارتند از: خوشه‌بندی سلسله مراتبی[۵] [۱۴، ۱۷]، خوشه‌بندی مختلط[۶] [۱۸، ۱۹]، خوشه‌بندی شبکه یادگیرنده[۷] [۲۰-۲۳]، خوشه‌بندی براساس تابع هدف[۸] و خوشه‌بندی افراز[۹] [۲۴، ۲۵].

AIS یکی از مهمترین الگوریتم‌های فرا ابتکاری[۱۰] به منظور حل مسائل بسیار پیچیده می‌باشد که از مهمترین کابردهای آن می‌توان در تحلیل خوشه‌بندی داده‌ها بیان نمود. علی‌رغم اینکه AIS قادر است پیکربندی فضای جستجو را به خوبی نمایش دهد اما تعیین خوشه‌های داده‌ها به طور مستقیم با استفاده از خروجی آن بسیار مشکل و هزینه‌بر خواهد بود. این موضوع تاکنون در مطالعات گذشته مورد توجه قرار نگرفته است.

بر این اساس در این مقاله یک الگوریتم دو مرحله‌ای پیشنهاد شده است. در مرحله اول با استفاده از الگوریتم AIS پیشنهادی، فضای جستجو مورد بررسی قرار گرفته و پیکربندی فضا تعیین می‌شود و در مرحله دو با استفاده از روش خوشه‌بندی سلسله ‌مراتبی، خوشه‌ها و تعداد آنها مشخص می‌شود. از مزایای روش خوشه‌بندی سلسله مراتبی عدم نیاز به تعیین تعداد خوشه‌ها است ولی از طرفی این روش به داده‌های پرت حساس می‌باشد و قادر به تعیین ساختار داده‌ها در بانک داده‌های بزرگ نیست [۲۶]. بنابراین در مرحله اول الگوریتم با استفاده از الگوریتم پیشنهادی AIS با تعیین پیکربندی فضای داده‌ها، ضعف روش خوشه‌بندی سلسله‌مراتبی در تعیین داده‌های پرت و ساختار داده‌ها مرتفع خواهد شد و از طرفی در مرحله دوم قادر خواهیم بود با استفاده از روش خوشه‌بندی سلسله مراتبی نقایص موجود در AIS در تعیین خوشه‌ها و تعداد آن را پوشش دهیم.  در انتهای مقاله، الگوریتم پیشنهادی بر روی نمونه واقعی متشکل از داده‌های زلزله در ایران پیاده‌سازی شده است. نتایج نشان داد که الگوریتم پیشنهادی توانسته است نقایص موجود در AIS و روش خوشه‌بندی سلسله مراتبی را پوشش دهد و از طرفی از دقت و سرعت بالا در اجرا برخوردار است.

ادامه مقاله به صورت زیر بخش بندی شده است؛ بررسی مطالعاتی که از الگوریتم‌های فرا ابتکاری به منظور خوشه‌بندی داده‌ها استفاده کرده‌اند، در بخش دوم مورد توجه قرار می‌گیرد. بخش سوم مقاله مروری بر AIS و انواع الگوریتم‌های آن دارد. الگوریتم پیشنهادی در بخش چهارم ارائه شده است و در بخش پنجم داده‌های مرتبط با نمونه واقعی متشکل از داده‌های زلزله در ایران با استفاده از الگوریتم پیشنهادی خوشه‌بندی می‌شود. نتایج حاصل از اجرای این الگوریتم در بخش پایانی مقاله مورد توجه قرار گرفته است.

 

  1. مروری بر ادبیات موضوع

همانطور که قبلاً اشاره شد، روش خوشه‌بندی از مهمترین روش‌های داده‌کاوی است که با بزرگتر شدن بانک‌های داده‌ای، تلاش محققین به منظور یافتن روش‌های خوشه‌بندی کارا و موثر متمرکز شده است. بر این اساس اخیرا استفاده از الگوریتم‌های فرا ابتکاری به منظور ارائه الگوریتم‌های خوشه‌بندی سریع و با دقت مناسب بسیار رواج یافته است.

در [۲۷، ۲۸] شبکه عصبی مصنوعی با بردار موقعیت دو بعدی به منظور تعیین تعداد خوشه‌ها در بانک داده ترکیب شده است. مدل ارائه شده در [۲۹] شبکه مصنوعی مبتنی بر تئوری تشدید انطباقی (ART) است که قادر است تعداد خوشه‌های واقعی را تعیین کند.

در [۷] یک الگوریتم k میانگین مبتنی بر الگوریتم ژنتیک پیشنهاد شده است و در [۳۰] الگوریتم ارائه شده در [۷] به منظور خوشه‌بندی با استفاده از تئوری زنجیره مارکو بهبود یافته است و توانسته جواب بهینه عمومی را ارائه دهد.

در [۲۲] الگوریتم خوشه‌بندی مبتنی بر ACS پیشنهاد داده‌اند که در آن از استراتژی مورچه‌های مطلوب استفاده شده است. در این مقاله از الگوریتم [۱۱]SA به منظور کاهش تعداد شهرهای بازدید شده توسط مورچه‌ها و از استراتژی انتخاب مسابقه[۱۲] به منظور یافتن بهترین مسیرها بهره گرفته شده تا الگوریتم سریعتری ارائه شود. خوشه‌بندی در این الگوریتم با استفاده از فرومون‌های در نظر گرفته شده برای هر شهر براساس بازدید مورچه‌های مطلوب صورت می‌گیرد. در [۳۱] الگوریتمی به منظور خوشه‌بندی داده‌های ارائه شده است که در آن هر شهر (داده) بیانگر یک مورچه است و از طرفی مورچه‌ها دارای خصوصیات و ویژگی‌های متفاوتی هستند. در [۳۲] الگوریتم خوشه‌بندی بر پایه سیستم مورچگان ارائه شده است و در [۳۳] الگوریتم ارائه شده در [۳۲] با الگوریتم خوشه‌بندی k میانگین ترکیب شده تا الگوریتم قویتری ارائه گردد. در [۳۴] الگوریتم‌های ارائه شده در [۳۲] و [۳۳] را مورد توجه قرار داده و یک الگوریتم دو مرحله‌ای را ارائه کرده است. در مرحله اول الگوریتم، داده‌ها با استفاده از الگوریتم خوشه‌بندی بر پایه سیستم مورچگان و الگوریتم k میانگین مورچگان، خوشه‌بندی شده و در مرحله دوم با استفاده از الگوریتم مبتنی بر ACS قوانین انجمنی در هر یک از خوشه‌ها را استخراج کرده است. در [۹-۱۱، ۳۵-۳۷] به موضوع استفاده از الگوریتم‌های ایمنی مصنوعی در خوشه‌بندی پرداخته است. مقایسات نتایج الگوریتم‌های مختلف فرا ابتکاری به منظور خوشه‌بندی داده‌ها نشان از سرعت بسیار بالای اجرا الگوریتم‌های ایمنی مصنوعی دارد. در این مقاله نیز با توجه به اینکه الگوریتم‌های ایمنی مصنوعی از سرعت بسیار بالایی و دقت مناسبی در اجرا برخوردار هستند، از این الگوریتم‌ها به منظور خوشه‌بندی داده‌ها استفاده شده است. از طرفی یکی از مهمترین مزایای روش‌های خوشه‌بندی سلسله مراتبی، سرعت اجرای بالای آنها و عدم نیاز به تعیین تعداد خوشه است. بر این اساس مرحله دوم الگوریتم پیشنهادی در این مقاله، به منظور افزایش سرعت خوشه‌بندی از این روش استفاده کرده است. الگوریتم ایمنی مصنوعی با تعیین تعدادی پادتن‌ که بسیار کمتر از پادزا‌ها هستند، فضای جستجو را مورد بررسی قرار می‌دهند و الگوریتم سلسله مراتبی پادتن‌ها را و در واقع فضای جستجو را خوشه‌بندی می‌کند.

 

  1. مروری بر AIS و الگوریتم‌های آن

همانطور که قبلا اشاره شد AIS یکی از مهمترین الگوریتم‌های فرا ابتکاری به منظور حل مسائل بسیار پیچیده می‌باشد که یک سیستم تطابقی برگرفته از نظریه ایمنی‌شناسی است که وظایف، فرآیندها، مدل‌ها و اصول NIS را مورد توجه قرار می‌دهد [۳۸]. اجزای اصلی NIS عبارتند از: پادزا ([۱۳]Ag)، پادتن ([۱۴]Ab)، تکثیر سلولی[۱۵] و لیمفوسیت ([۱۶]ALC) که نوعی گلبول سفید است و دارای سلول‌های ایمنی B و T می‌باشد.

در NIS میزان ارتباط بین یک پادتن‌ و یک پادزا‌ را نزدیکی ([۱۷]affin) می‌نامند. هر چه مقدار نزدیکی کمتر باشد، گلبول‌های سفید بیشتر برانگیخته خواهند شد. بر این اساس نحوه عمل NIS به این صورت است. با حمله عامل خارجی به بدن پادزا‌ها تولید می‌کند. پادزا‌ها شناسایی شده و به ALC اطلاع داده می‌شود. ALC برانگیخته شده و با استفاده از سلول‌های B و T خود برای نابودی پادزا‌ اقدام می‌کند. سلول‌های B تکثیر شده و برخی بدون تغییر مانده و برخی به صورت پلاسما[۱۸] تغییر می‌یابند. پلاسماها تولید پادتن‌ کرده و پادتن‌ها مانع رشد پادزا‌ها شده و از طرفی باعث تقویت سیستم ایمنی می‌شوند (فرایند یادگیرنده). عملکرد AIS بسیار شبیه NIS است. به منظور طراحی یک الگوریتم AIS، سه پارامتر مهم را باید مورد توجه قرار داد. نمودار (۱) این پارامتر‌ها و ارتباط آنها را نشان داده است.

[۱] نویسنده مسئول: شماره تماس: ۳۷۹۳۵۳۱۸-۰۳۱، رایانامه: ar.jafarian@trn.ui.ac.ir

۱ Corresponding author: Tel: 031-37934301, Email: ar.jafarian@trn.ui.ac.ir

[۳] Natural Immune System

[۴] Artificial Immune System

[۵] hierarchical clustering

[۶] mixture-model clustering

[۷] learning network clustering

[۸] objective-function-based clustering

[۹] partition clustering

[۱۰] Meta-heuristics

[۱۱] Simulated Annealing

[۱۲] Tournament selection strategy

[۱۳] Antigens

[۱۴] Antibodies

[۱۵] Clone

[۱۶] Lymphocytes

[۱۷] Affinity

[۱۸] Plasma

۱۲۰۰۰ تومان – خرید
درباره این محصول نظر دهید !