دانلود پایان نامه

1.1.1        ابزار و تکنیک‌های داده‌کاوی

ابزارها و تکنیک‌های بیشماری برای انجام پروژه‌های داده‌کاوی وجود دارد. بیشتر تکنیک‌های داده‌کاوی از سال‌ها و یا دهه‌های قبل وجود داشته‌اند و ریشه در علومی دیگر چون آمار و ریاضی و زیرشاخه‌های علوم کامپیوتر مانند هوش مصنوعی و یادگیری ماشین دارند. در این تحقیق سعی کرده‌ایم به معرفی تکنیک‌هایی بپردازیم که پرکاربرد بوده و یا در تحقیق مورد استفاده قرار گرفته است.

1.1.1.1       درخت تصمیم

درخت تصمیم از تکنیک‌های پرکاربرد و رایج داده‌کاوی است که برای اهداف دسته‌بندی و پیش‌بینی مورد استفاده قرار می‌گیرد. الگوریتم‌های این تکنیک در حیطه الگوریتم‌های یادگیری با ناظر بشمار می‌رود و بر اساس الگوریتم یادگیری مفهوم طراحی شده‌اند. یک درخت تصمیم از تعدادی گره[1] و شاخه[2] تشکیل شده است. شاخه‌ها، گره‌ها را به یکدیگر متصل می‌کنند. گره‌هایی که در انتهای درخت واقع هستند را برگ[3] می‌نامیم. برگ‌ها بیانگر برچسب کلاس‌ها هستند. گره‌ای که در بالاترین سطح از درخت قرار دارد ریشه[4] نامیده می‌شود. ریشه شامل تمام داده‌های آموزشی است که باید به کلاس‌های مختلف تقسیم شوند. تمامی گره‌ها، بجز برگ‌ها را گره‌های تصمیم[5] می‌نامند. در هر کدام از این گره‌ها، تصمیم‌گیری در مورد فعالیتی که باید انجام شود با توجه به یک خصیصه صورت می‌گیرد. هر کدام از گره‌ها داری فرزندانی هستند که تعداد فرزندان هر گره برابر با تعداد مقادیری است که خصیصه مورد نظر می‌تواند اختیار کند (شهرابی and شجاعی 1388).

الگوریتم‌های مختلفی برای تولید درخت تصمیم وجود دارد. تمامی این الگوریتم‌ها بر اساس الگوریتم یادگیری مفهوم هانت طراحی شده‌اند. این الگوریتم، روشی را مد نظر قرار داده است که انسان‌ها از آن به منظور یادگیری مفاهیم ساده استفاده می‌کنند. در این روش خصیصه‌های اصلی که متمایزکننده دو گروه اصلی متفاوت هستند، مشخص می‌شوند. برای انجام این کار، از نمونه‌های آموزشی مثبت و منفی استفاده می‌شود. الگوریتم هانت بر پایه استراتژی تقسیم و غلبه[6] بنا نهاده شده است. مجموعه‌های آموزشی به طور بازگشتی با انتخاب بهترین خصیصه به عنوان متمایز کننده به گونه‌ای به زیرمجموعه‌های کوچک‌تر افراز می‌شوند که هر زیر مجموعه تنها حاوی نمونه‌هایی باشد که به یک کلاس تعلق دارند (شهرابی and شجاعی 1388). به این ترتیب، با انتخاب پی در پی خصیصه‌های متمایز کننده، درخت تصمیم شکل می‌گیرد.

آنچه که باعث می‌شود الگوریتم‌های متفاوتی برای ایجاد درخت تصمیم وجود داشته باشد، عامل انتخاب خصیصه متمایزکننده است. معیارهای گوناگونی برای انتخاب خصیصه وجود دارد که مهم‌ترین آن عبارت است از:

  • شاخص جینی[7]: یک شاخص رایج تقسیم‌بندی، جینی نام دارد که از نام کورادو جینی[8]، متخصص آمار و اقتصاددان ایتالیایی گرفته شده است. این شاخص احتمال قرارگیری دو مورد انتخاب شده تصادفی از یک جمعیت یکسان را در یک دسته نشان می‌دهد. برای یک جمعیت خالص، این احتمال برابر یک است. اندازه‌گیری جینی یک گره، به صورت مجموع نسبت‌های دسته‌ها است. برای محاسبه تاثیر یک تقسیم، امتیاز جینی هر گره فرزند را محاسبه کرده و در نسبت اطلاعات که به آن گره می‌رسد ضرب کرده وسپس اعداد حاصل را با هم جمع می‌کنیم (شهرابی 1390b). الگوریتم CART[9] برای پیاده‌سازی از این معیار استفاده می‌کند.
  • بهره اطلاعات[10]: در منظر بهره اطلاعات، اگر یک برگ کاملا خالص باشد آنگاه دسته‌های این برگ را می‌توان به راحتی اینگونه توصیف کرد که همگی آنها در یک دسته جای می‌گیرند. از طرف دیگر، اگر یک برگ دارای ناخالصی بالایی باشد آنگاه توصیف آن بسیار مشکل خواهد بود. برای بیان این وضعیت اندازه‌ای به نام آنتروپی[11] تعریف می‌گردد. آنتروپی میزان بی‌نظمی یک سیستم است. آنتروپی یک گره خاص در یک درخت تصمیم عبارت است ازجمع نسبت‌های داده‌های متعلق به یک دسته خاص برای تمام دسته‌هایی که در گره نشان داده شده‌اند که در لگاریتم پایه دو آن نسبت ضرب شده است. آنتروپی یک تقسیم به صورت مجموع آنتروپی تمام گره‌های ناشی از تقسیم که بوسیله نسبت داده‌های هر گره وزن‌دهی شده است بدست می‌آید (شهرابی 1390b). الگوریتم [12]ID3 از بهره اطلاعات برای انتخاب خصیصه استفاده می‌کند.
  • نسبت بهره[13]: اندازه‌گیری آنتروپی زمانی با مشکل مواجه می‌شود که به یک تقسیم‌بندی با متغیرهای دسته‌ای مواجه شویم. مشکل در اینجا کاهش تعداد دسته‌های نمایش داده شده در هر گره و متعاقب آن کاهش آنتروپی است که صرفا از شکستن مجموعه داده‌های بزرگ‌تر به زیرمجموعه‌های کوچک‌تر ناشی می‌شود. کاهش آنتروپی که مربوط به تعداد شاخه‌ها باشد را اطلاعات نهادی[14] یک تقسیم‌بندی می‌نامند. اطلاعات نهادی موجب می‌شود تا درخت تصمیم ایجاد شده پر برگ و بار شود. درخت‌های پر برگ با تقسیمات متعدد چند مسیری مطلوب نیستند چرا که این تقسیمات به تعداد کم داده‌ها در هر گره منجر شده و مدل‌های حاصله از این طریق ناپایدار خواهند بود. برای رفع این مشکل، از نسبت کل بهره اطلاعاتی استفاده می‌کنند (شهرابی 1390b). الگوریتم‌ 5 از نسبت بهره برای انتخاب خصیصه استفاده می‌کند.

معیارهای انتخاب خصیصه دیگری هم وجود دارد، که می‌توان به درخت تصمیم CHAID، که برای انتخاب خصیصه از آزمون χ^2 استفاده می‌کند و یا C-SEP که برای انتخاب خصیصه از آماره G (که بسیار نزدیک به توزیع χ^2 است) استفاده می‌کند، اشاره کرد.

از درخت تصمیم ایجاد شده می‌توان برای پیش‌بینی برچسب نمونه‌های جدید بر اساس مقادیر خصیصه‌های آنها استفاده کرد. درخت تصمیم همچنین قوانین همبستگی میان خصیصه‌ها را آشکار می‌سازد. برخی از نقاط ضعف و قوت درخت‌های تصمیم عبارتند از:

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

1.1.1.2       شبکه‌های عصبی

شبکه‌های عصبی مصنوعی (ANN) شبکه‌ای عظیم از نرون‌های محاسباتی به هم پیوسته هستند که باساختار فرایندی بصورت  موازی توزیع شده نشان داده می‌شوند. ایده اصلی این شبکه‌ها از ساختار شبکه‌های عصبی بیولوژیک الهام گرفته شده است؛ زمانی که در سال 1943، وارن مک کالچ[15] به همراه والتر پیتس[16] برای توضیح نحوه عملکرد نرون‌های بیولوژیک به مدل‌سازی پرداختند (شهرابی 1390b). اگرچه این مدل فقط دارای یک نرون بود و توانایی محاسباتی محدودی داشت، ولی نقطه عطفی بود برای توسعه و پیشرفت شبکه‌های عصبی قوی‌تر و پیچیده‌تر؛ به گونه‌ای که امروزه شبکه‌های عصبی کاربرد گسترده‌ای در مسائل پیش‌بینی، دسته‌بندی و خوشه‌بندی دارد.

به طور کلی، شبکه‌های عصبی توسط سه مولفه زیر معرفی می‌شوند (Karray and Silva 2004):

  • ساختار
    • رو به جلو
    • بازگشتی
  • نوع یادگیری
    • یادگیری با ناظر[17]
    • یادگیری بدون ناظر[18]
    • ترکیبی[19]
  • تابع فعال‌سازی[20]
    • باینری
    • پیوسته

ساختار شبکه‌های عصبی از تعدادی نرون و اتصالات موزون بین آنها تشکیل شده است (شکل 2-4). معمولا این نرون‌ها در لایه‌هایی شامل لایه ورودی، لایه‌های پنهان و لایه خروجی سازمان می‌یابند. در ساختار رو به جلو، تمامی اتصالات بین نرون‌ها به سمت جلو بوده و هیچ نرونی به نرون‌های لایه قبل اتصال ندارد. ولی چنین اتصالاتی را در ساختار بازگشتی خواهیم داشت. فرآیند یادگیری شبکه‌های عصبی نیز مانند آنچه در داده‌کاوی هدایت‌شده و غیر هدایت‌شده ذکر شد، می‌تواند بصورت با ناظر و بدون ناظر باشد. در یادگیری با ناظر، داده‌های آموزشی برچسبی به عنوان متغیر هدف دارند ولی یادگیری بدون ناظر فاقد متغیر هدف است. در یادگیری ترکیبی، از هر دو فرآیند در شبکه عصبی استفاده می‌شود. تابع فعال‌سازی نیز خروجی هر نرون را بر اساس ورودی‌های آن و همچنین حد آستانه[21] نرون مشخص می‌کند. تابع علامت[22] و تابع گامی[23] مثال‌هایی از تابع فعال‌سازی باینری هستند و تابع سیگموید[24] و تانژانت هایپربولیک[25] و خطی[26] جزو توابع فعال‌سازی پیوسته هستند (Karray and Silva 2004).

 

 

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

1.1.1.3       الگوریتم‌های خوشه‌بندی

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

فرض کنید داده‌های ورودی دارای n ویژگی باشند، بنابراین هر داده را می‌توان بوسیله یک بردار n بعدی نمایش داد. اگر x و y دو نمونه از داده‌ها باشند خواهیم داشت:

جدول 2-3 تعاریف ریاضی انواع فاصله‌ها را نمایش می‌دهد (شهرابی and شجاعی 1388).

 

ما در این تحقیق به معرفی مختصر دو تکنیک خوشه‌بندی اکتفا کرده‌ایم.

K – Means:

در این الگوریتم تعداد خوشه‌ها (K) مشخص بوده و الگوریتم با تابع هدف حداقل نمودن فواصل درون یک خوشه به انتخاب K مرکز خوشه می‌پردازد. گام‌های این الگوریتم به صورت زیر است:

  1. انتخاب k مرکز خوشه اولیه به صورت تصادفی
  2. خوشه‌بندی داده‌ها: هر داده به خوشه‌ای تعلق دارد که کمترین فاصله را با مرکز آن خوشه داشته باشد.
  3. به روز کردن k مرکز خوشه از طریق محاسبه میانگین وزنی اعضای هر خوشه

مراحل 2 و 3 تا زمان یافتن حداقل فاصله درون خوشه‌ای ادامه می‌یابد.

نگاشت‌های خودسازمانده[27] (SOM):

تکنیک SOM که توسط کوهنن[28] معرفی شد، نوعی شبکه عصبی است که به خوشه‌بندی داده‌ها می‌پردازد. این شبکه عصبی در حیطه شبکه‌های عصبی بدون ناظر قرار دارد و بدین معنی است که برای به روز کردن وزن‌های اتصالات شبکه نیازی به تاثیر بازخورد ناظر نیست؛ به همین دلیل به عنوان خودسازمانده شناخته می‌شوند. ساختار این شبکه فقط دارای دو لایه است؛ یک لایه ورودی که به اندازه ابعاد (تعداد ویژگی‌ها) داده‌های ورودی نرون دارد و یک لایه خروجی که به اندازه تعداد خوشه‌ها نرون دارد و می‌توانند در ابعاد مختلف سازمان یابند. تمامی نرون‌های ورودی به تمامی نرون‌های خروجی متصل هستند؛ بنابراین، برای هر نرون خروجی یا به عبارت دیگر برای هر خوشه، اوزان کمان‌های متصل به آن خوشه را می‌توان در غالب یک بردار وزن برای آن خوشه در نظر گرفت. ابعاد بردارهای وزن خوشه‌ها هم‌بعد باداده‌های ورودی است (Karray and Silva 2004). شکل 2-5 ساختار این شبکه را نشان می‌دهد.

این مطلب مشابه را هم بخوانید :   توانمندسازی روانشناختی

 

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

قبل از بیان گام‌های الگوریتم لازم است با مفهوم همسایگی در این الگوریتم آشنا شویم. شعاع همسایگی برای یک نرون لایه خروجی مشخص کننده نرون‌های همسایه آن نرون است. مراحل الگوریتم SOM به صورت زیر است (Karray and Silva 2004):

  1. تمامی وزن‌ها (wijها) و نرخ یادگیری α و شعاع همسایگی Nc مقداردهی اولیه می‌شوند.
  2. یک داده ورودی x از مجموعه داده‌های ورودی به شبکه معرفی می‌شود.
  3. انتخاب نرون برنده بر اساس معیار فاصله (معمولا فاصله اقلیدسی در نظر گرفته می‌شود) :
  4. به روز کردن وزن نرون برنده و نرون‌های همسایه از تکرار k به تکرار k+1:
  5. تکرار گام‌های 2 تا 4 به ازای تمامی برداهای ورودی.
  6. کاهش نرخ یادگیری و شعاع همسایگی بر اساس رویکردی مشخص برای دوره بعد.
  7. تکرار گام‌های 2 تا 6 تا زمان تحقق شرط خاتمه (معمولا تعداد مشخصی تکرار).

1.1.1.4       K – نزدیکترین همسایه

این الگوریتم نیز بر اساس شباهت‌ها کار می‌کند. هر داده اگر دارای n ویژگی باشد یک نقطه در فضای n بعدی است. تمام داده‌های آموزشی در فضای n بعدی ذخیره می‌شوند. زمانی که داده‌ای با کلاس نامشخص داده شود، k همسایه نزدیک به آن در این فضا شناسایی می‌شوند و برچسب داده مورد نظر با توجه به برچسب این k همسایه تعیین می‌شود (Larose 2005). برای محاسبه فاصله بین رکوردها از فاصله متری و به طور معمول از فاصله اقلیدسی استفاده می‌شود.

مقدار پارامتر k، به‌صورت تجربی تعیین می‌شود. ابتدا با 1=k شروع و در هر مرحله با استفاده از داده‌های تست نرخ خطای دسته‌بندی محاسبه می‌شود؛ در هر مرحله مقدار k یک واحد افزایش داده می‌شود. در انتها کوچک‌ترین k که کمترین نرخ خطا را داشته باشد، انتخاب می‌شود. کوچک بودن مقدار k باعث می‌شود داده جدید به تعداد نقاط کم‌تری وابسته باشد، در این صورت خطا زیاد می‌شود. حال اگر مقدار k بزرگ باشد، داده جدید به کلاس‌های بیشتری وابسته می‌شود، در این صورت نیز خطا زیاد است. مقدار k باید یک مقدار میانی باشد.

از آنجایی که این الگوریتم مدلی برای دسته‌بندی داده‌ها ایجاد نمی‌کند و فقط داده‌های آموزشی را در یک  فضای n بعدی قرار می‌دهد، زمان اجرای الگوریتم در مرحله آموزش کم است. ولی زمانی که داده جدیدی به الگوریتم معرفی می‌شود، برای تعیین برچسب آن محاسبات بیشتری باید انجام دهد. بنابراین زمان اجرا در مرحله تست بیشتر خواهد بود.

1.1.1.5       ماشین بردار پشتیبان[29] (SVM)

ماشین‌های بردار پشتیبان در ابتدا توسط وپنیک[30] در دهه 90 میلادی توسعه داده شدند (شهرابی and شجاعی 1388). این الگوریتم ابزاری قدرتمند برای حل مسائل دسته‌بندی دو کلاسه است بگونه‌ای که بتوان کلاس‌ها را بطور خطی از یکدیگر جدا کرد. هدف SVM عبارت است از یافتن ابرصفحه جداکننده نقاط داده‌ای متعلق به دو کلاس با بیشترین حاشیه[31] و بهترین توانایی تعمیم. حاشیه، از دیدگاه هندسی عبارت است از فاصله موجود بین ابر صفحه و نزدیک‌ترین نمونه آموزشی. از یک منظر دیگر، حاشیه اینگونه تعریف می‌شود: مقدار فضا یا جدایی موجود میان دو کلاس که توسط ابرصفحه تعریف می‌شود. به نزدیک‌ترین نمونه‌های آموزشی به ابر صفحه جداکننده به اصطلاح بردار پشتیبان[32] گفته می‌شود (شهرابی and شجاعی 1388). شکل 2-6 خط جداکننده را به همراه بردارهای پشتیبان در فضای دو بعدی نشان می‌دهد.

 

 

تکنیک SVM در برخورد با داده‌هایی که به صورت خطی از یکدیگر جدا نمی‌شوند از یک نگاشت غیرخطی برای تبدیل داده‌های آموزشی به داده‌هایی با ابعاد بالاتر استفاده می‌کند. بدین ترتیب داده‌های تبدیل شده در ابعاد بالاتر به صورت خطی جدا پذیر خواهند بود. تابعی که وظیفه‌ی این نگاشت را به عهده دارد تابع کرنل[33] نامیده می‌شود. همچنین، تعمیم‌هایی از الگوریتم SVM برای حل مسائل دسته‌بندی چندکلاسه توسعه یافته است. اگرچه بنابر آنچه که گفته شد تکنیک SVM ابزاری قدرتمند برای حل اکثر مسائل دسته‌بندی است، ولی از جمله مهمترین معایب آن می‌توان به این نکته اشاره کرد که این تکنیک به محاسبات پیچیده و زمان‌بر نیاز دارد. به عبارت دیگر، SVM دارای پیچیدگی الگوریتمی بالا است و همچنین نیاز به حافظه زیادی دارد.

1.1.1.6       بیز ساده‌لوحانه[34]

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

این الگوریتم احتمال عضویت داده جدید را در هر کلاس محاسبه می‌کند و داده متعلق به کلاسی خواهد بود که بیشترین احتمال عضویت را داشته باشد. در این الگوریتم برای محاسبه احتمال عضویت فرض شده است که ویژگی‌ها از هم‌ مستقل هستند، به‌عبارت دیگر فرض می‌شود بین ویژگی‌ها هیچ هم‌بستگی وجود ندارد. اگرچه این الگوریتم از قدرت دسته‌بندی بالایی برخوردار است ولی گاهی اوقات مفروضات آن ممکن است بر دقت دسته‌بندی اثر منفی داشته باشند.

1.1.1.7       سیستم‌های چند دسته‌بند

سیستم‌های چند دسته‌بند (MCSs) راه حل قدرتمندی برای مسائل تشخیص الگوی[35] پیچیده هستند. قدرت این سیستم‌ها در اجازه استفاده همزمان از روش‌های دسته‌بند متنوع برای حل یک مسئله خاص است. این سیستم‌ها با ترکیب خروجی مجموعه‌ای از دسته‌بندهای متفاوت سعی در بهبود کارایی و رسیدن به دقت بالاتر را دارند. بطور کلی MCSs شامل گروهی از الگوریتم‌های دسته‌بند متفاوت و همچنین یک تابع تصمیم برای ترکیب خروجی دسته‌بندها است. بنابراین، طراحی چنین سیستمی شامل دو بخش است: طراحی گروه دسته‌بندها و طراحی تابع ترکیب[36] (Ghosh 2002).

در بخش طراحی گروه دسته‌بندها دو ساختار متفاوت قابل اجراست: ساختار موازی[37] و ساختار آبشاری[38] (Ghosh 2002). در شکل 2-7 این دو ساختار نمایش داده شده است. همچنین در بخش ترکیب نتایج دسته‌بندها، توابع ترکیب گوناگونی وجود دارد. میانگین و میانگین وزنی، روشهای ترکیب غیر خطی و روش انتگرال فازی از جمله روش‌هایی هستند که در این بخش مورد استفاده قرار می‌گیرند. روش‌های ترکیب غیر خطی شامل متدهای رأی گیری، متدهای رتبه دهی و متدهای احتمالی می‌باشد. توضیح کامل روشهای ترکیب نتایج دسته‌بندها در (Xu, Krzyzk et al. 1992) و (Ruta and Gabrys 2000)ارائه شده است.

 

ساختار سیستم و همچنین نوع تابع ترکیب مورد استفاده با توجه به مسئله مورد بررسی انتخاب می‌شوند.

1.1.1.8       الگوریتم ژنتیک

محاسبات تکاملی[39]، بر مبنای تکامل یک جمعیت از جواب‌های کاندید برای حل مسئله‌های بهینه‌سازی با الهام از عملگرهای انتخاب طبیعی توسعه یافته‌اند. الگوریتم ژنتیک[40] با تکیه بر نظریه داروین برای تولید جمعیت بعدی تکامل‌یافته‌تر از فرآیند تولید مثل الهام می‌گیرد و کاربرد گسترده‌ای در حل مسائل NP-hard دارد(Mitra and Acharya 2003). این الگوریتم با انتخاب دو عضو تصادفی از میان بهترین‌های جمعیت و انجام عمل تقاطع[41] و جهش[42] و تکرار آن، نسل بعدی جمعیت را تولید می‌کند. برای درک بهتر الگوریتم ژنتیک به تعاریفی نیاز است که به قرار زیر است:

  • ژن: واحد پایه ژنتیک است.
  • کروموزوم: به گروهی از ژن‌ها اطلاق می‌شود. هر عضو از جمعیت یک کروموزون است و معمولا به صورت آرایه پیاده‌سازی می‌شود.
  • تقاطع: عملگری است که بر روی دو کروموزوم انتخاب شده به عنوان والدین اعمال می‌شود برای تولید فرزندان.
  • جهش: عملگری است که بر روی یک فرزند اعمال می‌شود برای تغییر مقدار یک ژن.

آنچه در این میان از اهمیت ویژه‌ای برخردار است نحوه ارزیابی اعضای جمعیت برای تعیین بهترین کروموزوم‌ها است. در الگوریتم ژنتیک این ارزیابی توسط تابعی به عنوان تابع برازندگی[43] انجام می‌شود. تابع برازندگی با توجه به مسئله تعریف می‌شود و به هر یک از اعضای جمعیت مقداری را بر اساس مقادیر ژن‌ها نسبت می‌دهد. مراحل الگوریتم ژنتیک به صورت زیر است:

  1. ایجاد جمعیت اولیه بصورت تصادفی
  2. محاسبه تابع برازندگی برای هر عضو
  3. انتخاب والدین با توجه بر مقادیر تابع برازندگی هر عضو
  4. انجام عمل تقاطع و تولید جمعیت فرزندان
  5. انجام عمل جهش با احتمالی خاص
  6. ایجاد جمعیت جدید
  7. اگر شرایط خاتمه برقرار نبود به گام 2 برگرد در غیر این صورت به گام 8 برو
  8. پایان.

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

 

[1] Node

[2] Branch

[3] Leaf

[4] Root

[5] Decision Node

[6] Divide and Conquer

[7] Gini Index

[8] Corrado Gini

[9] Classification And Regression Tree

[10] Information Gain

[11] Entropy

[12] Iterative Dichotomiser 3

[13] Gain Ratio

[14] Intrinsic Information

[15] Warren Mc. Culloch

[16] Walter Pitts

[17] Supervised learning

[18] Unsupervised learning

[19] Hybrid

[20] Activation Function

[21] Threshold

[22] Sign function

[23] Step function

[24] Sigmoid function

[25] Hyperbolic tangent function

[26] Linear function

[27] Self-Organizing Maps (SOM)

[28] Kohonen

[29] Support Vector Machine

[30] Vapnik

[31] Margin

[32] Support Vectors

[33] Kernel Function

[34] Naïve Bayes

[35] Pattern Recognition

[36] Fusion Function

[37] Parallel Structure

[38] Cascade Structure

[39] Evolutionary Computation

[40] Genetic Algorithm

[41] Crossover

[42] Mutation

[43] Fitness Function

برای دانلود متن کامل فایل این  پایان نامه می توانید  اینجا کلیک کنید