X
تبلیغات
وبلاگ شخصی داوود قاسمی

وبلاگ شخصی داوود قاسمی
خوش آمدید ... با عرض سلام امیدواریم لحظات خوش و خوبی را در سایت "ریاضیّات و مهندسی " داشته باشید .
[ شنبه 23 مرداد1389 ] [ 1:28 قبل از ظهر ] [ داوود قاسمی ]

کاربرد الگوريتم ايمني مصنوعي در خوشه يابي داده ها

سيدحميد ظهيري

گروه مهندسي الکترونيک ومخابرات، دانشکده مهندسي، دانشگاه بيرجند

shzahiri@yahoo.com

چکيده: در اين تحقيق از الگوريتم ايمني مصنوعي براي پايه

ريزي يک روش جديد خوشه يابي بهره گيري شده است.

مولفه هاي سلولهاي دفاعي به شکل مختصات مراکز خوشه ها

خود را با آنتي ژنها « قرابت » تعريف شده در يک روند تکاملي

به وسيله عملگر جهش بهبود مي بخشند. کميت قرابت در

سيستم ايمني شبيه سازي شده به شکل عکس خطاي کوانتيزه

کردن تعريف شده است. روش ارائه شده برروي انواع مختلفي

از داده هاي مصنوعي و داده هاي مشهور در پردازش الگو (با

تنوع در ابعاد فضاي ويژگي و تعداد نمونه ها) آزمايش شده

است. نتايج به دست آمده ضمن موفقيت روش پيشنهادي در

خوشه يابي مجموعه داده هاي مختلف، برتري نسبتا قابل

و k-means توجهي را در عملکرد اين روش نسبت به روش

روش خوشه يابي ژنتيک نشان مي دهند.

واژه هاي کليدي: خوشه يابي داده، الگوريتم ايمني

مصنوعي، بازشناسايي الگو.

-1 مقدمه

الگوريتم ايمني مصنوعي 1 به عنوان يک روش جستجو و بهينه

سازي کارآمد در بين روشهاي ديگري مانند الگوريتم ژنتيک 2و

هوش جمعي 3 از جايگاه ويژه اي برخوردار است. الگوريتم

ايمني مصنوعي روشي بر گرفته از نحوه عملکرد سيستم ايمني

بدن در مواجهه با عوامل بيماريزاي خارجي است. ظرافت و

دقت اين سيستم دانشمندان را بر آن داشت که با شبيه سازي

عملکرد سيستم ايمني موجودات روش بهينه سازي ايمني

مصنوعي را طراحي کنند به گونه اي که قادر به حل مسايل

دشوار مهندسي باشد. حجم و تنوع تحقيقاتي که در زمينه حل

مسايل مختلف مهندسي با استفاده از اين روش گزارش شده

اند، نشاني بر توانايي الگوريتم ايمني مصنوعي در حل مسايل

.([ پيچيده مهندسي است ([ 1] تا [ 3

در تحقيق حاضر استفاده از الگوريتم ايمني مصنوعي در مسئله

- خوشه يابي 4 - يکي از مسايل مهم در علم بازشناسي الگو 5

مورد نظر قرار گرفته است. مسئله خوشه يابي عبارت است از

Artificial immune algorithm1

Genetic algorithm2

Swarm intelligence 3

Clustering 4

Pattern recognition 5

پردازش داده ها در فضاي ويژگي به گونه اي که نمونه هاي

شبيه به هم در خوشه هايي جداگانه گردهم آيند. اين مسئله در

4] و تقسيم بندي داده ] موضوعات مهمي همچون داده کاوي 6

هاي تصوير[ 5] کاربرد دارد و روشهاي مختلفي نيز به اين

منظور پيشنهاد شده است که از آن ميان مي توان به روشهاي

6] و اخيرا روش خوشه يابي ] ISODATA و k-means

ژنتيک([ 7] و [ 8]) و روش خوشه يابي گروه ذرات[ 9] اشاره

کرد.

در اغلب روشهای خوشه يابی ژنتيک کرومزومها به صورت

مراکز خوشه ها تعريف و سپس بيان باينری آنها مورد استفاده

قرار گرفته تحت عملگرهای جهش و برش به سمت مقدار

بهينه ميل می کنند. در اين روش تابع برازندگی با مقدار خطای

. [ کوانتيزه مرتبط است[ 7

در روشهای هوش جمعی مانند روش بهينه سازی گروه ذرات

مکان هر ذره به شکل مختصات مراکز خوشه تعريف شده با

معادلات تغيير مکان بهترين مختصات مراکز خوشه محاسبه

.[ می شود [ 9

در روش خوشه يابي پيشنهاد شده در اين تحقيق سلولهاي

دفاعي به شکل بردارهايي که شامل مختصات مراکز خوشه ها

سلولهاي دفاعي با آنتي « قرابت 7 » . هستند، تعريف مي شود

ژنها به صورت عکس خطاي کوانتيزه کردن تعريف مي گردد

و آنتي باديهاي با قرابت کمتر به وسيله عملگر جهش 8 ساختار

خود را براي دستيابي به قرابت بيشتر با آنتي ژنها بهبود مي

دهند.

داده هاي گوناگون مصنوعي و مشهور براي محک روش ارائه

شده و مقايسه نتايج به دست آمده با نتايج حاصل از ساير

روشهاي مرسوم خوشه يابي انتخاب شده اند. مجموعه هاي

داده انتخاب شده داراي تنوع گوناگون در تعداد نمونه ها، ابعاد

برداهاي ويژگي و تعداد کلاسهاي مرجع مي باشند.

پيکر بندي اين مقاله به اين ترتيب است که در بخش 2 به

مفاهيم اساسي الگوريتم ايمني مصنوعي اشاره مختصري

Data mining 6

Affinity 7

Mutation 8

خواهد شد. مطالب اين بخش ما را آماده مي کند که روش

خوشه يابي بر مبناي الگوريتم ايمني » پيشنهادي خود را با نام

در بخش 3 ارائه کنيم. پس از توضيحات تفصيلي « مصنوعي

درباره روش خوشه يابي ارائه شده در بخش 4 به ارزيابي

عملکرد آن در موجهه با انواع مجموعه هاي داده و مقايسه آن

با عملکرد ساير روشها پرداخته خواهد شد. بحث و نتيجه

گيري نهايي در بخش 5، مقاله را خاتمه خواهد داد.

-2 الگوريتم ايمني مصنوعي

هنگامي که عوامل بيماريزاي خارجي-مانند ويروسها و باکتريها

و در يک قالب کلي آنتي ژنها- ارگانيسم موجودات زنده را

مورد تهاجم قرار مي دهند، ضمن تخريب سلولها به تکثير نيز

مي پردازند. يکي از مکانيسمهاي جالب توجه سيستم تدافعي

موجودات زنده در مقابله با اين تهاجم تکثير سريع سلولهاي

تدافعي است که توفيق لازم در شناسايي آنتي ژنها و نابود

کردن آنها را دارا هستند. جالب اينجاست که ميزان تکثير

سلولهاي تدافعي و آنتي بادي به ميزان موفقيت آنها در نابود

کردن فاکتورهاي تهاجمي وابسته است. يعني سيستم ايمني

سلولهاي تدافعي با عملکرد بهتر را بيشتر و آنهايي که داراي

قابليت کمتري هستند را کمتر تکثير مي کند. ميزان تشخيص

يک آنتي ژن به وسيله سلولهاي تدافعي به وسيله فاکتوري به

شناخته مي شود. سلولهاي تدافعي با قرابت کمتر « قرابت » نام

شوند تا با تغييرات « جهش » بايد متحمل عملگر زيستي به نام

ساختاري بتوانند قرابت خود را با عوامل بيماريزا بيشترکرده

عملکرد دفاعي خويش را بهبود بخشند. ميزان جهش براي

عوامل دفاعي با قرابت بيشتر، کمتر است و بالعکس.

،« قرابت » با توجه به توضيحات فوق چهار مفهوم مهم

دخالت عمده اي در عملکرد « تکثير » و ،« جهش » ،« انتخاب »

سيستم ايمني موجودات زنده دارند. لذا در الگوريتم ايمني

مصنوعي نيز همين مفاهيم بايد نقش عمده را ايفا کنند. در

واقع براي پياده سازي يک الگوريتم ايمني مصنوعي مراحل

زير اجتناب ناپذير است:

1) مقدمه سازي:

در اين مرحله جمعيتي تصادفي از سلولهاي ايمني تشکيل

مي شوند.

2) حلقه جستجو

در اين حلقه مراحل زير در خصوص هر آنتي ژن انجام

مي گيرد:

1- 2 ) ارزيابي قرابت

سلولهاي تدافعي جديد مورد ارزيابي قرار مي گيرند.

2- 2 ) انتخاب

سلولهاي ايمني با قرابت بيشتر نسبت به آنتي ژنها انتخاب

مي شوند.

Kn K 2 ... z K1 z n … … z z22 K 2 21 z n z z12 K 1 11 z z

شکل 1ساختار سلولهاي دفاعي

3- 2 ) تکثير و تغيير حالت ساختاري

سلولهاي ايمني تکثير مي شوند. تشخيص آنتي ژن و

قرابت بيشتر با آن يعني تکثير بيشتر سلول تدافعي

متناظر با آن. سلولهاي با قرابت کمتر تحت عملگر

جهش تغيير ساختاري پيدا مي کنند. ميزان اِعمال

عملگر جهش با ميزان قرابت نسبت عکس دارد.

3) بستن حلقه براي تعدادتکرار پيش فرض

مرحله 2 براي تعداد پيش تعريف شده اي از تکرار حلقه و

يا نيل به همگرايي (از ميان رفتن همه آنتي ژنها) ادامه مي

يابد.

-3 خوشه يابي بر مبناي الگوريتم ايمني مصنوعي

روشهاي مختلفي براي حل مسئله خوشه يابي پيشنهاد شده

است. که در مقدمه به آنها اشاره شد از ميان آنها روش خوشه

از شهرت بيشتري برخوردار بوده استفاده k-means بندي

گسترده تري نسبت به ساير موارد دارد [ 6]. در اين روش ابتدا

به تعداد پيش فرض مراکز خوشه ها به صورت کاملا تصادفي

از ميان نقاط داده انتخاب مي شوند و سپس عمل تشکيل

خوشه ها با تعلق دادن نقاط داده به نزديکترين مرکز صورت

مي گيرد. در مرحله بعدي مراکز جديد خوش ها به مقدار

ميانگين همه نقاط موجود در يک خوشه تغيير مقدار مي دهند

و مجددا عمل تعلق داده ها در فضاي ويژگي به خوشه ها

تکرار مي شود. اين فرايند آنقدر تکرار مي شود که مراکز

k-means خوشه ها ثابت باقي بمانند. شايد بتوان گفت روش

به دليل ساختار ساده آن يکي از بهترين روشهاي خوشه يابي

بوده و به خاطر عملکرد خوب با اقبال بيشتري نسبت به ساير

روشها مواجه شده است. امروزه با افزايش حجم اطلاعات،

شبکه هاي اطلاع رساني و بانکهاي

داده نياز به روشهاي موثرتري جهت خوشه يابي در فضاهاي با

ابعاد زياد و در حضور حجم بالا نقاط داده است. از اين رو

محققان اقدام به معرفي روشهاي جديدي در اين خصوص

کرده اند. به طور مثال در [ 7] و[ 8] با استفاده از روش ژنتيک

روشهايي تازه به اين منظور پيشنهاد شده است که در مقدمه به

اجمال معرفی شد.

در اين بخش با استفاده از الگوريتم ايمني مصنوعي روشي

جديد براي خوشه يابي پيشنهاد مي شود.

با توجه به توضيحات ارائه شده در بخش 2 ابتدا لازم است

پارامترهاي حاضر در مسئله خوشه يابي با عوامل موجود در

الگوريتم ايمني مصنوعي معرفي شوند.

مراجع

[1] S. M. Thayer, S. P. N. Singh, "Development of an

immunology-based multi-robot coordination algorithm

for exploration and mapping domains," In the

Proceedings of Intelligent Robots and System,

International Conference (IEEE/RSJ 2002), vol. 3, pp.

2735 -2739. September 30 - October 5, 2002.

[2] D. R. Carvalho and A. A. Freitas,"An

immunological algorithm for discovering smalldisjunct

rules in data mining. GECCO’2001.

(Workshop Program.) San Francisco," California. July

7, 2001.

[3] R. Canham, A.H. Jackson, A. Tyrrell, "Robot Error

Detection using an Artificial Immune System.

Evolvable Hardware, Proceedings. NASA/DoD

Conference," pp 199 -207, July 9-11, 2003.

[4] I.E Evangelou, D.G. Hadjimitsis, A.A. Lazakidou,

and C. Clayton, "Data mining and knowledge

discovery in complex image data using artificial neural

networks," Workshop on Complex Reasoning and

Geographical Data, Cyprus, 2001.

[5] T. Lillesand, and R. Keifer, Remote Sensing and

Image Interpretation, John Wiley & Sons, 1994.

[6] J.A. Hartigan, Clustering Algorithms, John Wiley

Local 13

Global 14

.: Weblog Themes By Pichak :.