IRE: Inductive Rule Extraction

معرفی کتاب "الگوریتم های ژنتیک کاربردی"



کتاب "الگوریتم‌های ژنتیک کاربردی" توسط رندی ال هاپت و سو الن هاپت از پژوهشگران ارشد آزمایشگاه تحقیقات کاربردی دانشگاه ایالتی پنسیلوانیا به رشته تحریر درآمده و ویرایش نخست آن در سال 1997 توسط انتشارات وایلی منتشر شده است. همچنین ویرایش دوم این کتاب در سال 2004 عرضه شده است؛ که مهمترین به روز رسانی آن نسبت به ویرایش نخست، کدهای متلبی است که همراه متن آمده‌اند.


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


این کتاب در 7 فصل به انضمام چندین ضمیمه، سازماندهی شده است.

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

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

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

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

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

فصل ششم به مسائل فنی سخت‌تر یورش می‌برد.

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

همچنین ضمیمه1 برخی روتین‌های الگوریتم ژنتیک را به صورت شبه برنامه لیست می‌کند.


در پایان، خواندن کتاب بسیار خوب "الگوریتم‌های ژنتیک کاربردی" توصیه می‌گردد. 

دریافت کتاب الگوریتم‌های ژنتیک کاربردی 



الگوریتم ژنتیک دودویی و پاسخ به پنج سوال مهم درباره آن




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

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

و در آینده نزدیک به کمک این مطالب الگوریتم ژنتیک دودویی را در متلب پیاده سازی خواهیم کرد. با ما در ادامه همراه باشید.

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

نمایش دودویی متغیر‌ها 
در مقایسه با تکامل بیولوژیک، الگوریتم ژنتیک دودویی نیز با یک جمعیت اولیه از اعضای تصادفی شروع به کار می‌کند. هر رشته باینری(کروموزوم)، ویژگی‌های انتخاب شده‌ی(Selected Characteristics) یکی از اعضای جمعیت را نشان می‌دهد. می‌توان دو رشته‌ای را که به تصادف انتخاب شد‌ه‌اند، با یکدیگر ترکیب کرد در این صورت دو رشته جدید به وجود می‌آیند که ترکیبی از ویژگی‌های دو رشته دیگر هستند؛ پس هر رشته‌ باینری جدید، بخش‌های از رشته‌های باینری والدین خود را شامل می‌شود.  

اجزای الگوریتم ژنتیک دودویی
الگوریتم ژنتیک همانند هر الگوریتم بهینه‌سازی دیگر با تعریف متغیر‌های بهینه‌سازی، تابع هزینه(Cost Function) و هزینه(Cost) شروع می‌شود و مانند سایر الگوریتم‌های بهینه‌سازی با آزمایش همگرایی(Convergence) به پایان می‌رسد. سلسه مراتب اجرای الگوریتم ژنتیک دودویی به صورت یک فلوچارت ساده، در شکل1 نشان داده شده است.


نقطه قوت الگوریتم ژنتیک این است که بر خلاف بسیاری از روش‌ها، هیچ مشکلی برای کار با داده‌های گسسته ندارد.

تابع هزینه و انتخاب متغیرها 
تابع هزینه(f) خروجی را بر حسب مجموعه‌ای از متغیر‌های ورودی(کروموزوم) تولید می‌کند. هدف این است که خروجی را با برخی از روش‌های مطلوب، با پیدا کردن مقادیر مناسب برای متغیر‌های ورودی، تغییر دهیم. خواهیم دید که تعریف یک تابع هزینه‌یِ مناسب و تصمیم برای تعیین متغیرهایی که باید استفاده شوند، کاملا مرتب هستند.
نکته: در ادبیات مربوط به الگوریتم ژنتیک اصطلاح برازندگی به طور گسترده برای اشاره به خروجی تابع هزینه استفاده می‌شود؛ ولی از آن‌جای‌که بیشتر مسائل بهینه‌سازی از نوع کمینه‌سازی هستند ما در اینجا از اصطلاح هزینه استفاده کرده‌ایم.
الگوریتم ژنتیک به وسیله تعریف یک کروموزوم یا آرایه‌ای از مقادیر متغیرها برای بهینه‌سازی شروع می‌شود. اگر یک کروموزوم $$N_{var}$$ متغیر داشته باشد که توسط$$P_{1},P_{2},P_{3},...,P_{N_{var}}$$   داده شده باشند؛ سپس کروموزوم به صورت یک بردار ردیفی $$N_{var}$$  عنصری نوشته می‌شود.
$$Chromosome=[P_{1},P_{2},P_{3},...,P_{N_{var}}]$$
   هر کروموزوم هزینه‌ای دارد که با ارزیابی تابع هزینه در $$P_{1},P_{2},P_{3},...,P_{N_{var}}$$   تعیین می‌شود.
  $$Cost=f(chromosome)=f(P_{1},P_{2},P_{3},...,P_{N_{var}})$$
اغلب تابع هزینه بسیار پیچیده است. کاربر بایستی تصمیم بگیرد کدام متغیر‌های مسئله مهم‌تر هستند. متغیر‌هایِ بیش از حد، الگوریتم ژنتیک را به دردسر می‌اندازند. برخی اوقات، تعداد صحیح و انتخاب متغیر‌ها از تجربه یا اجراهای بهینه‌سازی آزمایشی  به دست می‌آیند؛ اوقات دیگر، یک تابع هزینه تحلیلی برای این کار وجود دارد. بیشتر مسائل بهینه‌سازی نیاز به محدودیت‌ها یا مرزهای برای متغیر دارند.

به زودی در پست بعدی به ادامه مطلب خواهیم پرداخت با ما همراه باشید.



معیارهای ارزیابی قوانین در داده‌کاوی



به نام خدا
مقدمه
معیارهای بسیاری برای ارزیابی عملکرد در یادگیری ماشین و کشف دانش استفاده می‌شود. در استنتاج پیشگویانه (Predictive induction) مبتنی بر دسته‌بندی، اغلب معیار دقت(Accuracy) دسته‌بندی، استفاده می‌شود. در حالیکه سایر معیارهای استاندارد عبارتند از: دقت(Precision)، یادآوری(Recall)، حساسیت(Sensitivity) و اختصاصی کردن(Specificity).
در سایر عملیات‌های کشف دانش مانند قوانین انجمنی که از  جمله روش‌های استنتاج توصیفی(Descriptive Induction) است از معیارهای دیگری نظیر پشتیبانی(Support)، اعتماد(Confidence)، جذابیت(Interestingness) و قابلیت فهم(Comprehensibility) تعریف می‌شود.
در این پست به معرفی چندین معیار انتخاب شده برای ارزیابی قوانین در داده‌کاوی قوانین انجمنی می‌پردازیم. این معیارها جائیکه یک قانون بایستی رتبه‌بندی شود، با توجه با اینکه به چه خوبی توسط داده‌ها پشتیبانی می‌شوند؛ به کار برده می‌شوند.

معیارهای جالب در داده‌کاوی قوانین انجمنی
کشف قوانین انجمنی یکی از مهمترین وظایف داده‌کاوی است و الگوریتم‌های کارآمد زیادی برای آن پیشنهاد شده است. با این حال تعداد قوانین کشف شده اغلب خیلی زیاد است و بنابراین کاربر نمی‌تواند تمامی قوانین کشف شده را تجزیه‌وتحلیل کند. برای غلبه بر این مشکل، روش‌های متعددی برای داده‌کاوی قوانین جالب پیشنهاد شده و در مقالات معیارهای بسیاری برای تعیین جالب بودن قوانین معرفی شده است. 
طی سالیان گذشته کارهای بسیاری در زمینه داده‌کاوی به ویژه در زمینه یافتن انجمن‌ها و همبستگی‌ها در میان آیتم‌ها در یک پایگاه داده از تراکنش‌های مشتریان انجام شده است. در زمینه تحلیل سبد خرید(Market Basket Analysis) قوانین انجمنی آیتم‌های را متمایز می‌کند که در اغلب موارد، بخش قابل توجهی از مشتریان، همراه با آیتم‌های خاص دیگری خریداری کرده‌اند. به عنوان مثال ممکن است ما متوجه شویم که 95 درصد از مشتریانی که نان خریده‌اند شیر نیز خریداری کرده‌اند.
هر قانون در داده‌کاوی قوانین انجمنی بایستی دو محدودیت مشخص شده کاربر را برآورده کند؛ یکی معیاری از اهمیت آماری است که پشتیبانی(Support) نامیده می‌شود و دیگری معیاری از خوب بودن قانون است که اعتماد(Confidence) نامیده می‌شود.
در ادامه به تعریف رسمی(Formal Definition) و برخی توضیحات در خصوص تعدادی از معیارهای ارزیابی قوانین انجمنی که در ابتدا معرفی شدند، خواهیم پرداخت.
 
ادامه مطلب

مروری بر مقاله‌ای با عنوان "الگوریتم ممتیکی تکاملی برای استخراج قانون"


به نام خدا

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

 الگوریتم‌های ممتیکی تکاملی EMAs(Evolutionary Memetic Algorithm) بر روی طرح‌هایِ اضافه کردن جستجوی محلی، برای تکمیل قابلیت جستجوی سرتاسری الگوریتم‌های تکاملی EAs، تمرکز دارند.

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

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

در این مقاله دو الگوریتم جستجوی بهبود محلی به کارگرفته شده است؛ یکی از الگوریتم میکروژنتیک μGA استفاده می‌کند که منجر به بهبود کارایی و راهنمایی هدایت شده بر روی نسل‌ها می‌گردد؛ و دیگری AIS(Artificial Immune System) سیستم ایمنی مصنوعی، که به طور گسترده برای تجزیه و تحلیل داده‌ها در الگوریتم‌های یادگیری ماشین بدون ناظر استفاده شده است.

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

در این مقاله دو ضریب پشتیبانی(Support) و اعتماد(Confidence) که از داده‌کاوی قوانین انجمنی به عاریت گرفته شده‌اند در توابع ارزیابی برازندگی استفاده شده است؛ یعنی تابع برازندگی استفاده شده برای ارزیابی مجموعه قوانین، ترکیبی از معیار اصلی یعنی دقت دسته‌بندی به علاوه ایده‌های برگرفته شده از ارزیابی قوانین انجمنی است. قوانین انجمنی قوانینی هستند که تلاش می‌کنند روابط جالب بین متغیر‌ها در یک پایگاه داده را بیابند.

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

چندین معیار ارزیابی مختلف برای سنجش عملکرد الگوریتم‌ها استفاده شده از جمله : دقت دسته‌بندی، حساسیت و خاص بودن؛ علاوه بر این‌ها در این مقاله، دو معیار ارزیابی که کمتر مورد توجه بوده‌اند نیز بررسی شده‌اند؛ قابلیت فهم(درک) (comprehensibility) و جذابیت(interestingness).

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

پاسخ به 4 سوال در خصوص قوانین (Rules)


پرسش‌های در خصوص قوانین 

در ادامه بر برخی از پرسش‌ها در خصوص قوانین از ظن خودم پاسخ می‌دهم.


1) قوانین چگونه به وجود می‌آیند؟

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


2) قوانین کجا نگهداری می‌شوند؟

در خصوص انسان‌ها بیشتر قوانین در ضمیر خودآگاه ساخته و در ضمیر ناخودآگاه ساکن می‌شوند.


3)آیا قوانین ثابت هستند؟

خیر. قوانین متغیر هستند و ممکن است در طی زمان و به همراه تجربه‌های جدید تغییر کنند. ولی با توجه به قدرت یک قانون ممکن شواهد بیشتری برای تغییر نیاز باشد.


4) قوانین در کجا به کار گرفته می‌شوند؟

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


1 2 >>