آشنایی با بینایی ماشین

بینایی ماشین

اگر به طور خلاصه بخواهیم تعریفی از “بینایی ماشین” یا “Machine Vision” داشته باشیم ، به این صورت بیان می کنیم که : بینایی ماشین در واقع دادن قدرت دیدن به دستگاه ها و تجهیزات صنعتی با مجهز کردن آن ها به دوربین و کامپیوتر می باشد.

بینایی ماشین مجموعه ای از روش ها و تکنولوژی هاست که برای درک و آنالیز خودکار مبتنی بر تصاویر ، در زمینه هایی مثل بازرسی خودکار ، فرآیند کنترل و هدایت روبات در صنعت استفاده می شود. بینایی ماشین ارتباط نزدیکی با “بینایی رایانه ای ” دارد ولی با آن فرق دارد.

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

تصویربرداری

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

شکلی از تصویربرداری خطی و تصویر برداری سه بعدی

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

پردازش تصویر

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

تصمیم گیری

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

چند مثال برای بینایی ماشین در زیر ذکر شده است :

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

مزیت ها

فواید استفاده از یک سیستم بینایی ماشین چیست ؟

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

بینایی رایانه ای

بینایی رایانه ای یا “Computer Vision” یک فیلدی است که شامل دریافت ، پردازش ، آنالیز و فهم تصاویر است ؛ به طور کلی به دریافت تصاویر از محیط و استخراج اطلاعات کمی و کیفی از آن ها اطلاق می شود.

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

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

در زیر جدولی ارائه شده است که تا حدودی تفاوت های بینایی رایانه ای با بینایی ماشین ذکر شده است :

منبع : http://d-i-p.ir

/0 دیدگاه /توسط

درخت تصمیم قسمت 4

,

درخت تصمیم چیست؟

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

درخت تصمیم جهت تعیین نوع بیماری

درخت تصمیم یک مدل خودتوصیف است یعنی به‌تنهایی و بدون حضور یک فرد متخصص در آن حوزه، نحوه دسته‌بندی را به صورت گرافیکی نشان می‌دهد و به دلیل همین سادگی و قابل‌فهم بودن، روش محبوبی در داده‌کاوی محسوب می‌شود. البته به خاطر داشته باشید در مواردی که تعداد گره‌های درخت زیاد باشد، نمایش گرافیکی و تفسیر آن می‌تواند کمی پیچیده باشد.
برای روشن شدن مطالب، به مثال زیر توجه کنیدکه در آن قصد داریم به کمک ساخت یک درخت تصمیم، بازی‌کردن کریکت را برای یک دانش‌آموز، پیش‌بینی کنیم:
فرض کنید نمونه‌ای شامل ۳۰ دانش‌آموز با سه متغیر جنسیت (پسر/ دختر)، کلاس (X / IX) و قد (۵ تا ۶ فوت) داریم. ۱۵ نفر از ۳۰ نفر در اوقات فراغت خود کریکت بازی می‌کنند. حال می‌خواهیم با بررسی خصوصیات این پانزده نفر، پیش‌بینی کنیم چه کسانی در اوقات فراغت خود کریکت بازی می‌کنند.برای این کار ابتدا باید براساس خصوصیات ۱۵ نفری که کریکت بازی می‌کنند، یک الگو برای دسته‌بندی به دست آوریم. از آنجا که درخت تصمیم یک ساختار سلسله مراتبی شرطی دارد (شکل فوق) و در هر مرحله باید بر اساس مقدار یک خصوصیت تصمیم بگیریم، مهم‌ترین کاری که در ساخت این درخت تصمیم باید انجام دهیم، این است که تعیین کنیم کدام خصوصیت داده‌ها، تفکیک‌کنندگی بیشتری دارد. سپس این خصوصیت‌ها را اولویت‌بندی کرده و نهایتاً با لحاظ این اولویت‌ها از ریشه به پایین در اتخاذ تصمیم، ساختاری درخت‌مانند برای دسته‌بندی داده‌ها بنا کنیم. الگوریتم‌های مختلف ساخت درخت تصمیم، مهم-‌ترین تفاوتی که با هم دارند، در انتخاب این اولویت و روشی است که برای انتخاب اولویت خصوصیت‌ها در نظر می‌گیرند.
برای سنجش میزان تفکیک‌کنندگی یک خصوصیت، ساده‌ترین روش این است که دانش‌آموزان را براساس همهٔ مقادیر هر سه متغیر تفکیک کنیم. یعنی مثلاً ابتدا بر اساس جنسیت، داده‌ها را جدا کنیم و سپس مشخص کنیم چند نفر از دختران و چندنفر از پسران، کریکت بازی می‌کنند. سپس همین کار را برای قد و کلاس تکرار کنیم. با این کار، می‌توانیم درصد بازیکنان هر مقدار از یک خصوصیت (درصد بازیکنان دختر از کل دختر‌ها و درصد بازیکنان پسر از کل پسر‌ها) را محاسبه کنیم. هر خصوصیتی که درصد بیشتری را تولید کرد، نشانگر تفکیک‌کنندگی بیشتر آن خصوصیت (و البته آن مقدار خاص) است.
جور دیگری هم به این موضوع می‌توان نگاه کرد: این متغیر، بهترین مجموعه همگن از دانش‌آموزان از لحاظ عضویت در گروه بازی‌کنان را ایجاد می‌کند یعنی در گروه بازیکنان، بیشترین خصوصیتی که بین همه مشترک است، پسر بودن است. میزان همگنی و یکنواختی ایجاد شده توسط هر خصوصیت هم، شکل دیگر میزان تفکیک‌کنندگی آن خواهد بود.
در تصویر زیر شما می‌توانید مشاهده کنید که متغیر جنسیت در مقایسه با دو متغیر دیگر، قادر به شناسایی بهترین مجموعهٔ همگن هست چون میزان مشارکت دانش‌آموزان پسر دربازی کریکت ۶۵ درصد است که از تمام متغیرهای دیگر بیشتر است:

درخت تصمیم

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

درخت تصمیم چگونه کار می‌کند؟

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

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

هر گره داخلی متناظر با یک متغیر و هر یال، نمایانگر یک مقدار ممکن برای آن متغیر است. یک گره برگ، مقدار پیش‌بینی‌شدهٔ متغیر هدف (متغیری که قصد پیش‌بینی آنرا داریم)، را نشان می‌دهد یعنی برگ‌ها نشان‌دهندهٔ دسته‌بندی نهایی بوده و مسیر پیموده شده تا آن برگ، روند رسیدن به آن گره را نشان می‌دهند.

درخت تصمیم

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

انواع متغیر‌ها در درخت تصمیم

در مسائل مرتبط با درخت‌های تصمیم با دو نوع کلی از متغیر‌ها مواجه هستیم:

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

از طرفی می‌توانیم متغیر‌ها را به دون گروه کلی، متغیرهای مستقل و متغیرهای وابسته تقسیم کنیم. متغیرهای مستقل، متغیرهایی هستند که مقدار آن‌ها، مبنای تصمیم گیری ما خواهند بود و متغیر وابسته، متغیری است که بر اساس مقدار متغیرهای مستقل، باید مقدار آنرا پیش‌بینی کنیم. متغیرهای مستقل با گره‌های میانی نشان داده می‌شوند و متغیرهای وابسته، با برگ نشان داده می‌شوند. حال هر یک از این دو نوع متغیر مستقل و وابسته، می‌تواند گسسته یا پیوسته باشد.
چنانچه متغیری وابستهٔ عددی باشد دسته بندی ما یک مسالهٔ رگرسیون و چنانچه طبقه‌ای باشد، دسته بندی از نوع، رده‌بندی (Classification) است. به عبارتی دیگر، هنگامی‌که خروجی یک درخت، یک مجموعه گسسته از مجموعه مقادیر ممکن است؛ به آن درخت دسته‌بندی می‌گوییم (مثلاً مؤنث یا مذکر، برنده یا بازنده). این درخت‌ها تابع X→C را بازنمایی می‌کنند که در آن C مقادیر گسسته می‌پذیرد. هنگامی‌که بتوان خروجی درخت را یک عدد حقیقی در نظر گرفت آن را، درخت رگرسیون می‌نامیم (مثلاً قیمت خانه یا طول مدت اقامت یک بیمار در یک بیمارستان). این درختان اعداد را در گره‌های برگ پیش‌بینی می‌کنند و می‌توانند از مدل رگرسیون خطی یا ثابت (یعنی میانگین) یا مدل‌های دیگر استفاده کنند. وظیفهٔ یادگیری در درختان رگرسیون، شامل پیش‌بینی اعداد حقیقی بجای مقادیر دسته‌ای گسسته است که این عمل را با داشتن مقادیر حقیقی در گره‌های برگ خود نشان می‌دهند. بدین‌صورت که میانگین مقادیر هدف نمونه‌های آموزشی را در این گره برگ به دست می‌آورند. این نوع از درختان، تفسیر آسان داشته و می‌توانند توابع ثابت تکه‌ای را تقریب بزنند.
درخت CART (Classification And Regression Tree) نامی است که به هر دو روال بالا اطلاق می‌شود. نام CART سرنام کلمات درخت رگرسیون و دسته‌بندی است. البته نوع دیگری از درخت‌های تصمیم هم داریم که برای خوشه‌بندی (clustering) داده‌ها به کار می‌روند و به دلیل کاربرد محدود، در این مجموعه مقالات به آن‌ها نخواهیم پرداخت (بیشتر تحقیقات در یادگیری ماشین روی درختان دسته‌بندی متمرکز است).

اصطلاحات مهم مربوط به درخت تصمیم

در این بخش به معرفی اصطلاحات مهم در حوزهٔ کار با درخت تصمیم می‌پردازیم.
گره ریشه: این گره حاوی تمام نمونه‌های موجود هست و سطح بعدی اولین تقسیم مجموعهٔ اصلی به دو مجموعهٔ همگن‌تر است. در مثال قبل، گره ریشه دارای ۳۰ نمونه است.
گره تصمیم: زمانی که یک گره به زیرگره‌های بعدی تقسیم می‌شود، آن را یک گره تصمیم می‌نامیم.
برگ / گره پایانه: گره‌هایی که تقسیم نمی‌شوند یا به عبارتی تقسیم پیاپی از طریق آن‌ها پایان می‌یابد، برگ یا گره پایانه نام دارند.
در تصویر زیر، گره ریشه (Root Node) با رنگ آبی، شاخه، انشعاب (Branch) یا به عبارتی زیر درخت (Sub-Tree) با رنگ گل‌بهی، تقسیم (Splitting) و هرس (Pruning) نمایش داده‌شده‌اند. برگ‌ها هم به رنگ سبز در انتهای شاخه‌های مختلف درخت، قرار گرفته‌اند.

درخت تصمیم

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

مزایا و معایب درخت تصمیم

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

معایب درختان تصمیم

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

مقایسه درخت تصمیم و درخت رگرسیون

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

هر دو نوع درخت تصمیم و رگرسیون تقریباً مشابه هستند. در زیر به برخی شباهت‌ها و تفاوت‌های بین این دو می‌پردازیم:

ویژگی‌های درخت رگرسیون و درخت دسته‌بندی:

• زمانی که متغیر هدف ما پیوسته و عددی باشد، از درخت رگرسیون و زمانی که متغیر هدف ما گسسته یا غیرعددی باشد، از درختان تصمیم استفاده می‌کنیم.
• معیار تقسیم و شاخه زدن در درختان رگرسیون بر اساس معیار خطای عددی است.
• گره‌های برگ در درختان رگرسیون حاوی مقادیر عددی هستند که هر عدد، میانگین مقادیر دسته‌ای است که داده جاری، بیشترین شباهت را با آن‌ها داشته است اما در درختان تصمیم، مقدار برگ، متناظر با دسته‌ایست که بیشترین تکرار را با شرایط مشابه با داده داده شده، داشته است.
ن هر دو درخت، رویکرد حریصانهٔ بالا به پایین را، تحت عنوان تقسیم باینری بازگشتی دنبال می‌کنند. این روش از بالای درخت، جایی که همهٔ مشاهدات در یک بخش واحد در دسترس هستند شروع می‌شود و سپس تقسیم به دوشاخه انجام‌شده و این روال به‌صورت پی‌درپی تا پایین درخت ادامه دارد، به همین دلیل این روش را بالا به پایین می‌خوانیم. همچنین به این دلیل این روش را حریصانه می‌خوانیم که تلاش اصلی ما در یافتن بهترین متغیر در دسترس برای تقسیم فعلی است و در مورد انشعابات بعدی که به یک درخت بهتر منتهی شود، توجهی نداریم. (به عبارتی همواره بهترین انتخاب در لحظه، بهترین انتخاب در سراسر برنامه نیست و اثرات این تقسیم در تقسیم‌های آینده را در نظر نمی‌گیرد). به یاد دارید که درروش حریصانه و در مورد کوله‌پشتی نیز مورد مشابه را دیده‌ایم. در شیوه حریصانه در هر مرحله عنصری که بر مبنای معیاری معین ((بهترین)) به نظر می‌رسد، بدون توجه به انتخاب‌های آینده، انتخاب می‌شود.
• در هر دو نوع درخت، در فرآیند تقسیم این عمل تا رسیدن به معیار تعریف‌شدهٔ کاربر برای توقف عملیات، ادامه دارد. برای مثال، ما می‌توانیم به الگوریتم بگوییم که زمانی که تعداد مشاهدات در هر گره کمتر از ۵۰ شود، عملیات متوقف گردد.
• در هر دو درخت، نتایج فرآیند تقسیم، تا رسیدن به معیارهای توقف، باعث رشد درخت می‌شود. اما درخت کاملاً رشد یافته به‌احتمال‌زیاد باعث بیش‌برازش داده‌ها (over fit) خواهد شد که در این صورت، شاهدکاهش صحت و دقت بر روی ‌داده‌های آینده که قصد دسته‌بندی آن‌ها را داریم، خواهیم بود. در این زمان هرس‌کردن را بکار می‌بریم. هرس کردن، روشی برای مقابله با بیش-برازش داده‌هاست که در بخش بعد بیشتر به آن خواهیم پرداخت.

نحوهٔ تقسیم یک درخت تصمیم

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

انتخاب الگوریتم، به نوع متغیرهای هدف نیز بستگی دارد.

منبع

درخت تصمیم قسمت 1
درخت تصمیم قسمت 2
درخت تصمیم قسمت 3
درخت تصمیم قسمت 4

/2 دیدگاه /توسط

درخت تصمیم قسمت 3

,

بگذارید برای تبیین بهتر مفهوم «درخت تصمیم (decision tree)» یک مثال کاربردی را بررسی کنیم؛ مدیریت شرکت «Stygian Chemical Industries, Ltd» می‌خواهد بین انتخاب این دو گزینه تصمیم‌گیری کند:‌ ساخت یک واحد تولیدی کوچک یا یک واحد تولیدی بزرگ برای ساخت یک محصول شیمیایی با عمر بازار (market life) برابر با ده سال. توضیح این‌که اتخاذ این تصمیم مبتنی بر تخمین اندازه بازار در آینده است.

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

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

هیئت مدیره با تردید و نگرانی زیادی دست‌وپنجه نرم می‌کند. شرکت طی سال‌های 1۹4۰ تا 1۹۵۰ رشد مناسبی داشته و با سرعت مطابق با نیاز بازار رشد کرده است. اگر بازار محصول جدید واقعا بزرگ باشد این شانس برای شرکت وجود دارد تا به سرعت وارد عرصه عظیمی از سود سرشار گردد. مهندس پروژه توسعه (development project engineer) مصرانه به دنبال ترغیب مدیریت به ساخت واحد تولیدی با ظرفیت زیاد است. این واحد علاقه دارد اولین واحد غول‌پیکر طراحی شده توسط خود را به جهان معرفی نماید.

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

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

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

نمایش گزینه‌ها

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

این تصمیم خاص را می‌توان در یک جدول انتخاب/نتیجه (payoff table) نشان داد.

انتخاب باران بیاید باران نیاید
برگزاری جشن در باغ فاجعه لذت فروان و به یاد ماندنی
برگزاری جشن در خانه لذت نسبی، شادی لذت نسبی، پشیمانی

سوالات بسیار پیچیده تصمیم‌گیری را می‌توان در چنین جدول‌هایی خلاصه کرد. با این‌حال، به‌ویژه برای تصمیمات پیچیده سرمایه‌گذاری روش مناسب دیگری برای بررسی اثرات و احتمالات تصمیم‌گیری به همراه نتایج وجود دارد: درخت تصمیم. پیر ماسی ( Pierre Massé)، مامور عالی‌رتبه آژانس تصمیم‌گیری برای تولیدات و تجهیزات فرانسه (Commissioner General of the National Agency for Productivity and Equipment Planning in France)، می‌گوید:

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

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

درخت تصمیم

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

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

زنجیره تصمیم – پیشامد (Decision-event chains)

مثال قبل با اینکه تنها یک مرحله از تصمیم‌گیری را نشان می‌دهد، شامل پایه‌های ابتدایی تمام درخت‌های تصمیم‌گیری‌ پیچیده است. بیایید نگاهی به شرایط پیچیده‌تر بیندازیم.

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

درخت تصمیم

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

اگر آنچه در حال حاضر می‌دانم،‌ در آن‌ زمان هم درست باشد، چه پیشامدی رخ خواهد داد.

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

اضافه کردن داده‌های مالی

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

درخت تصمیم

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

  • بررسی بازار نشان می‌دهد که شانس یک بازار بزرگ در بلند مدت برابر با ۶۰٪ و شانس یک بازار کوچک در بلند مدت برابر با 4۰٪ (ردیف دو و سه جدول) است.
پیشامد شانس یا احتمال (٪)
تقاضای اولیه بالا، تقاضای درازمدت بالا 60
تقاضای اولیه بالا، تقاضای درازمدت پایین 10
تقاضای اولیه پایین، تقاضای درازمدت پایین 30
تقاضای اولیه پایین،‌ تقاضای درازمدت بالا 0

در نتیجه، شانس این‌که بازار با تقاضای بالای اولیه رو‌به‌رو شود برابر با ۷۰٪ (۶۰ + 1۰) است. اگر تقاضا در ابتدا بالا باشد، شرکت پیش‌بینی می‌کند که احتمال ادامه‌ی میزان بالای تقاضا برابر با ۸۶٪ (۷۰ ÷ ۶۰) است. مقایسه ۸۶٪ با ۶۰٪ نشان می‌دهد که تقاضای بالای اولیه، محاسبه‌ی احتمال ادامه بازار با تقاضای بالا را دست‌خوش تغییر می‌کند. به شکل مشابه اگر تقاضا در دوره دو ساله ابتدائی پایین باشد، شانس پایین بودن تقاضا در ادامه برابر با 1۰۰٪ (3۰ ÷ 3۰) است. در نتیجه میزان فروش در دوره اولیه می‌تواند نشان‌گر خوبی برای سطح تقاضا در ادامه دوره ده ساله باشد.

تخمین درآمد در صورت پیشامد هر سناریو در ادامه آمده است.

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

2. یک واحد تولیدی بزرگ با تقاضای پایین به دلیل هزینه‌های عملیاتی ثابت و بازده پایین تنها 1۰۰ هزار دلار در سال درآمد خواهد داشت.

3. یک واحد تولیدی کوچک با تقاضای پایین اقتصادی است و سالانه درآمدی معادل 4۰۰ هزار دلار خواهد داشت.

4. یک واحد تولیدی کوچک با تقاضای اولیه بالا در سال برابر با 4۵۰ هزار دلار درآمد خواهد داشت که در سال‌های سوم به بعد با توجه به افزایش حضور رقبا به میزان 3۰۰ هزار دلار کاهش پیدا خواهد کرد. (بازار بزرگتر خواهد شد اما بین رقبای جدید تقسیم می‌شود.)

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

۶. اگر واحد کوچک توسعه پیدا کند اما بازار کوچک شود،‌ درآمد حاصل سالانه برابر با ۵۰ هزار دلار خواهد بود.

در ادامه با محاسبات انجام گرفته خواهیم داشت: یک واحد بزرگ نیاز به سه میلیون دلار سرمایه‌گذاری دارد. یک واحد کوچک در ابتدا 1.3 میلیون دلار و در صورت ادامه توسعه نیاز به 2.2 میلیون دلار خواهد داشت.

اگر اطلاعات جدید را به درخت تصمیم وارد کنیم، نگاره شماره چهار به دست خواهد آمد. به خاطر داشته باشید که تمام اطلاعات موجود بر اساس دانسته‌های شرکت Stygian به دست آمده‌اند اما بدون درخت تصمیم این اطلاعات ارزش و مفهوم کنونی را به دست نمی‌داند. کم‌کم متوجه می‌شوید که درخت تصمیم چه تاثیر شگرفی بر توانایی مدیران در تحلیل سیستماتیک (systematic analysis) و تصمیم‌گیری بهتر می‌گذارد. در نهایت برای ایجاد یک درخت تصمیم به موارد زیر نیازمندیم.

1. شناسایی نقاط تصمیم و انتخاب‌های ممکن در هر سطح

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

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

4. تحلیل ارزش انتخاب‌ها برای انتخاب یک مسیر

انتخاب مسیر عملکرد (Choosing Course of Action)

هم اکنون آماده‌ی برداشتن قدم بعدی برای مقایسه نتایج هر مسیر هستیم. یک درخت تصمیم جواب نهایی مسئله‌ی سرمایه‌گذاری را به مدیر نمی‌دهد بلکه به وی کمک می‌کند مسیر با بهترین سود و کمترین هزینه‌ را مشاهده کند و با مسیرهای دیگر مقایسه نماید.

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

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

حضور اهداف متعارض، ناپایدار و متعدد منجر به ایجاد سیاست اصلی شرکت شیمیایی Stygian می‌گردد و عناصر این سیاست تحت تاثیر خواست و زندگی افراد درگیر تغییر می‌کند. در ادامه بد نیست اجزاء مختلف تصمیم‌گیر را بررسی و ارزیابی نماییم.

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

چنین سوال‌هایی حتما ذهن مدیران عالی را درگیر می‌کند و البته درخت تصمیم نشان داده شده در نگاره شماره 4 به این سوال‌ها پاسخ نخواهد داد. اما این درخت به مدیران خواهد فهماند که کدام‌یک از تصمیمات، اهداف بلند مدت را دست‌خوش تغییر می‌کنند. ابزار مناسب در قدم بعدی تحلیل مفهوم عقبگرد (rollback) است.

مفهوم عقب‌گرد

مفهوم عقب‌گرد در این شرایط نیاز به توضیح دارد. در نقطه تصمیم گیری شماره یک در نگاره شماره چهار، مدیریت اجباری برای اخذ تصمیم شماره دو ندارد و حتی نمی‌داند مجبور به این کار خواهد شد یا نه. اما اگر قرار بر تصمیم‌گیری در نقطه دو باشد، با توجه به اطلاعات کنونی، شرکت تصمیم به توسعه ظرفیت تولید خواهد گرفت. این تحلیل در نگاره شماره ۵ نشان داده شده است. ( در این لحظه از سوال در مورد تنزیل سود آینده (discounting future profits) چشم‌پوشی می‌کنیم و در ادامه در مورد آن صحبت خواهیم کرد.) می‌بینیم که امید ریاضی کلی (total expected value) در تصمیم به توسعه ظرفیت 160 هزار دلار بیشتر از تصمیم برای عدم توسعه در هشت سال باقی‌مانده است. در نتیجه مدیریت با اطلاعات کنونی چنین تصمیمی خواهد گرفت (تصمیم تنها بر اساس سود بیشتر و به عنوان یک تصمیم منطقی اخذ می‌شود).

درخت تصمیم

ممکن است بی‌اندیشید چرا با اینکه تنها با تصمیم شماره یک روبرو هستیم، باید به جایگاه تصمیم‌گیری نقطه دو فکر کنیم. دلیل این موضوع این است که ما بایستی بتوانیم سود حاصل از تصمیم نقطه دو را محاسبه کنیم تا قادر باشیم سود حاصل از تصمیم نقطه یک (ساخت یک واحد تولیدی کوچک یا یک واحد تولید بزرگ) را با یک‌دیگر مقایسه کنیم. ارزش مالی تصمیم شماره دو را ارزش مکانی (position value) آن می‌نامیم. ارزش مکانی یک تصمیم برابر است با ارزش مورد انتظار یا امید ریاضی شاخه متناظر (در این مثال، چند شاخه یا چنگال توسعه واحد). امید ریاضی به شکل ساده برابر است با میانگین مقادیر نتایج در صورت تکرار زیاد شرایط (بازده ۵۶۰۰ دلار در سال با احتمال ۸۶٪ و 4۰۰ دلار با احتمال 14٪).

به بیان دیگر، معدل 2۶۷2 دلار سود نصیب شرکت شیمیایی Stygian تا رسیدن به نقطه دو خواهد شد. حال این سوال پیش می‌آید که با توجه به این مقادیر بهترین تصمیم در نقطه شماره یک کدام است؟

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

ساخت واحد تولیدی بزرگ:

($10 ×.60) + ($2.8 ×.10) + ($1 ×.30) – $3 = $3,600 thousand

ساخت واحد تولید کوچک :

($3.6 ×.70) + ($4 ×.30) – $1.3 = $2,400 thousand

درخت تصمیم

گزینه‌ی با امید ریاضی بزرگتر (سود مورد انتظار بیشتر) متناظر با ساخت واحد تولیدی بزرگ خواهد بود.

در نظر گرفتن زمان

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

برای ساده‌سازی، نرخ تنزیل مورد نظر شرکت شیمیایی Stygian را برابر با 1۰٪ در سال در نظر می‌گیریم. با استفاده از قانون عقب‌گرد، دوباره با تصمیم شماره دو شروع می‌کنیم. با تنزیل مقادیر با نرخ 1۰٪، نتایج نگاره شماره هفت، قسمت A، به دست خواهد آمد. توجه کنید که این مقادیر، ارزش کنونی را در صورت اتخاذ تصمیم شماره دو نشان می‌دهند.

درخت تصمیم

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

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

درخت تصمیم

واحد تولیدی بزرگ دوباره به عنوان انتخاب برتر شناسایی می‌گردد. اما حاشیه سود (margin) این‌بار نسبت به مرتبه بدون تنزیل مقدار کمتری (2۹۰ هزار دلار) است.

گزینه‌های عدم قطعیت (Uncertainty Alternatives)

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

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

نتیجه‌گیری

پیتر اف دراکر (Peter F. Drucker) به زیبایی رابطه بین برنامه‌ریزی زمان حال و پیشامدهای آینده را توضیح داده است: «برنامه‌ریزی بلند مدت با تصمیمات آینده سروکار ندارد. بلکه با آینده تصمیمات حاضر مرتبط است».  تصمیمات امروز باید متاثر از نتیجه محتمل در آینده اتخاذ شوند. از آنجا که تصمیمات امروز پایه انتخاب‌های آینده را خواهند ساخت، باید تعادلی بین سودآوری و انعطاف‌پذیری ایجان نمایند؛ این تصمیمات باید بین نیاز به سرمایه‌گذاری بر فرصت‌های پرسود با ظرفیت عکس‌العمل به شرایط و نیازهای آینده تعادل برقرار نمایند.

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

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

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

منبع

 

درخت تصمیم قسمت 1

درخت تصمیم قسمت 2

درخت تصمیم قسمت 3

درخت تصمیم قسمت 4

/0 دیدگاه /توسط

درخت تصمیم قسمت 2

,

 

Decision Tree (درخت تصمیم) چیست؟

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

آشنایی با مفهوم Decision Tree (درخت تصمیم)

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

یک درخت تصمیم‌گیری به طور معمول با یک نُود اولیه‌ شروع می‌شود که پس از آن پیامد‌های احتمالی به صورت شاخه‌هایی از آن منشعب شده و هر کدام از آن پیامد‌ها به نُود‌های دیگری منجر شده که آن‌ها هم به نوبهٔ خود شاخه‌هایی از احتمالات دیگر را ایجاد می‌کنند که این ساختار شاخه‌شاخه سرانجام به نموداری شبیه به یک درخت مبدل می‌شود. در درخت تصمیم‌گیری سه نوع Node (گِره) مختلف وجود دارد که عبارتند از:

– نُود‌های تصادفی – نُود‌های تصمیم‌گیری – نُود‌های پایانی

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

درخت تصمیم

درخت‌های تصمیم‌گیری را می‌توان با سَمبول‌ها یا علائم فلوچارت نیز رسم کرد که در این صورت برای برخی افراد، به خصوص دولوپرها، درک و فهم آن آسان‌تر خواهد بود.

چه‌طور می توان اقدام به کشیدن یک Decision Tree کرد؟

به منظور ترسیم یک درخت تصمیم، ابتدا وسیله و ابزار مورد نظرتان را انتخاب کنید (می‌توانید آن را با قلم و کاغذ یا وایت‌برد کشیده یا اینکه می‌توانید از نرم‌افزار‌های مرتبط با این کار استفاده کنید.) فارغ از اینکه چه ابزاری انتخاب می‌کنید، می‌بایست به منظور ترسیم یک درخت تصمیم اصولی، مراحل زیر را دنبال نمایید:

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

درخت تصمیم

۲- نُود‌‌های تصادفی و تصمیم‌گیری را به منظور شاخ و برگ دادن به این درخت، به طریق پایین رسم کنید:

ـ  اگر تصمیم اصلی دیگری وجود دارد، مستطیل دیگری رسم کنید. ـ   اگر پیامدی قطعی نیست، یک دایره رسم کنید (دایره‌ها نمایانگر نُود‌های تصادفی هستند.) ـ  اگر مشکل حل شده، آن را فعلاً خالی بگذارید.

درخت تصمیم

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

۳- به بسط این درخت ادامه دهید تا زمانی که هر خط به نقطه‌ٔ پایانی برسد (یعنی تا جایی که انتخاب‌های دیگری وجود نداشته و پیامد‌های احتمالی دیگری برای در نظر گرفتن وجود نداشته باشد.) در ادامه، برای هر پیشامد احتمالی یک مقدار تعیین کنید که این مقدار می‌تواند یک نمرهٔ فرضی یا یک مقدار واقعی باشد. همچنین به خاطر داشته باشید که برای نشان دادن نقاط پایانی، از مثلث استفاده کنید.

درخت تصمیم

حال با داشتن یک درخت تصمیم کامل، می‌توانید تصمیمی که با آن مواجه هستید را تجزیه و تحلیل کنید.

مثالی از پروسهٔ تجزیه و تحلیل Decision Tree با محاسبهٔ سود یا مقدار مورد انتظار از هر انتخاب در درخت مد نظر خود، می‌توانید ریسک را به حداقل رسانده و احتمال دستیابی به یک پیامد یا نتیجهٔ مطلوب و مورد انتظار را بالا ببرید. به منظور محاسبهٔ سود مورد انتظار یک گزینه، تنها کافی است هزینهٔ تصمیم را از مزایای مورد انتظار آن کسر کنید (مزایای مورد انتظار برابر با مقدار کلی تمام پیامد‌هایی است که می‌توانند از یک انتخاب ناشی شوند که در چنین شرایطی هر مقدار در احتمال پیشامد ضرب شده است.) برای مثالی که در تصاویر بالا زده‌ایم، بدین صورت این مقادیر را محاسبه خواهیم کرد:

درخت تصمیم

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

درخت تصمیم

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

آشنایی با برخی مزایا و معایب Decision Tree

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

با تمام این‌ها، درخت‌های تصمیم ممکن است گاهی به شدت پیچیده شوند! در چنین مواردی یک به اصطلاح Influence Diagram جمع و جور‌تر می‌تواند جایگزین بهتری برای درخت تصمیم باشد به طوری که این دست نمودار‌ها توجه را به تصمیمات حساس، اطلاعات ورودی و اهداف محدود می‌کنند.

کاربرد Decision Tree در حوزه‌ٔ ماشین لرنینگ و دیتا ماینینگ

از درخت تصمیم می‌توان به منظور ایجاد مُدل‌های پیش‌بینی خودکار استفاده کرد که در حوزه‌ٔ یادگیری ماشینی، استخراج داده و آمار کاربردی هستند. این روش که تحت عنوان Decision Tree Learning شناخته می‌شود، به بررسی مشاهدات در مورد یک آیتم به جهت پیش‌بینی مقدارش می‌پردازد و به طور کلی، در چنین درخت تصمیمی، نُود‌ها نشان‌دهنده‌ٔ دیتا هستند نَه تصمیمات. این نوع درخت‌ها همچنین تحت عنوان Classification Tree نیز شناخته می‌شوند به طوری که هر شاخه در برگیرنده‌ٔ مجموعه‌ای از ویژگی‌ها یا قوانین طبقه‌بندی دیتا است و مرتبط با یک دستهٔ خاص می‌باشد که در انتهای هر شاخه یافت می‌شود.

این دست قوانین که تحت عنوان Decision Rules شناخته می‌شوند قابل بیان به صورت جملات شرطی می‌باشند (مثلاً اگر شرایط ۱ و ۲ و ۳ محقق شوند، با قطعیت می‌توان گفت که X نتیجه‌ای همچون Y برخواهد گرداند.) هر مقدار دادهٔ اضافی به مدل کمک می‌کند تا دقیق‌تر پیش‌بینی کند که مسئلهٔ مورد نظر به کدام مجموعه از مقادیر متعلق می‌باشد و این در حالی است که از این اطلاعات بعداً می‌توان به عنوان ورودی در یک مدل تصمیم‌گیری بزرگ‌تر استفاده کرد.

درخت‌های تصمیم‌گیری که پیامد‌های محتمل پی‌درپی و بی‌نهایت دارند، Regression Tree نامیده می‌شوند. به طور کلی، متدهای کاربردی در این حوزه به صورت زیر دسته‌بندی می‌شوند:

– Bagging: در این متد با نمونه‌سازی مجدد دیتای سورس، چندین درخت ایجاد شده سپس با برداشتی که از آن درختان می‌شود، تصمیم نهایی گرفته شده یا نتیجهٔ‌ نهایی به دست می‌آید.

– Random Forest: در این متد طبقه‌بندی از چندین درخت تشکیل شده که به منظور افزایش نرخ کلاسیفیکیشن طراحی شده‌اند.

– Boosted: درخت‌هایی از این جنس می‌توانند برای رگرسیون مورد استفاده قرار گیرند.

– Rotation Forest: در این متد، همگی درخت‌ها توسط یک به اصطلاح Principal Component Analysis با استفاده از بخشی از داده‌های تصادفی آموزش داده می‌شوند.

درخت تصمیم‌گیری زمانی مطلوب تلقی می‌شود که نشان‌دهنده‌ٔ بیشترین دیتا با حداقل شاخه باشد و این در حالی است که الگوریتم‌هایی که برای ایجاد درخت‌های تصمیم‌گیری مطلوب طراحی شده‌اند شامل CART ،ASSISTANT ،CLS و ID31415 می‌شوند. در واقع، هر کدام از این متد‌ها باید تعیین کنند که بهترین راه برای تقسیم داده در هر شاخه کدام است که از متد‌های رایجی که بدین منظور استفاده می‌شوند می‌توان به موارد زیر اشاره کرد:

– Gini Impurity – Information Gain – Variance Reduction

استفاده از درخت‌های تصمیم‌گیری در یادگیری ماشینی چندین مزیت عمده دارد من‌جمله هزینه یا بهای استفاده از درخت به منظور پیش‌بینی داده با اضافه کردن هر به اصطلاح Data Point کاهش می‌یابد و این در حالی است که از جمله دیگر مزایایش می‌توان به موارد زیر اشاره کرد:

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

اما Decision Tree در ML معایبی نیز دارا است که از جملهٔ مهم‌ترین آن‌ها می‌توان به موارد زیر اشاره کرد:

– حین مواجه با داده‌های طبقه‌بندی شده با سطوح مختلف، داده‌های حاصله تحت‌تأثیر ویژگی‌ها یا صفاتی که بیشترین شاخه را دارند قرار می‌گیرد. – در صورت رویارویی با پیامد‌های نامطمئن و تعداد زیادی پیامد بهم مرتبط، محاسبات ممکن است خیلی پیچیده شود. – ارتباطات بین نُود‌ها محدود به AND بوده حال آنکه یک Decision Graph این اجازه را به ما می‌دهند تا نُود‌هایی داشته باشیم که با OR به یکدیگر متصل شده‌اند.

 

درخت تصمیم قسمت 1

درخت تصمیم قسمت 2

درخت تصمیم قسمت 3

درخت تصمیم قسمت 4

/0 دیدگاه /توسط

درخت تصمیم قسمت 1

,

درخت تصمیم گیری (Decision Tree) یک ابزار برای پشتیبانی از تصمیم است که از درخت‌ها برای مدل کردن استفاده می‌کند. درخت تصمیم به‌طور معمول در تحقیق‌ها و عملیات مختلف استفاده می‌شود. به‌طور خاص در آنالیز تصمیم، برای مشخص کردن استراتژی که با بیشترین احتمال به هدف برسد بکار می‌رود. استفاده دیگر درختان تصمیم، توصیف محاسبات احتمال شرطی است.

کلیات

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

۱-گره تصمیم: به‌طور معمول با مربع نشان داده می‌شود.

۲-گره تصادفی: با دایره مشخص می‌شود.

۳-گره پایانی: با مثلث مشخص می‌شود.

Manual decision tree
Traditionally, decision trees have been created manually

نمودار درخت تصمیم گیری

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

مکان‌های مورد استفاده

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

یکی دیگر از موارد استفاده از درخت تصمیم، در علم داده‌کاوی برای classification است.

الگوریتم ساخت درخت تصمیم‌گیری

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

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

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

مسئله دسته‌بندی

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

ناخالصی گینی:

ناخالصی آنتروپی:

ناخالصی خطا:

مسئله رگرسیون

در مسئله رگرسیون ناخالصی می‌تواند یکی از موارد پایین باشد:

میانگین خطای مربعات:

میانگین خطای قدر مطلق:

مزایا

در میان ابزارهای پشتیبانی تصمیم، درخت تصمیم و دیاگرام تصمیم دارای مزایای زیر هستند:

۱- فهم ساده: هر انسان با اندکی مطالعه و آموزش می‌تواند، طریقه کار با درخت تصمیم را بیاموزد.

۲- کار کردن با داده‌های بزرگ و پیچیده: درخت تصمیم در عین سادگی می‌تواند با داده‌های پیچیده به راحتی کار کند و از روی آن‌ها تصمیم بسازد.

۳-استفاده مجدد آسان: در صورتی که درخت تصمیم برای یک مسئله ساخته شد، نمونه‌های مختلف از آن مسئله را می‌توان با آن درخت تصمیم محاسبه کرد.

۴- قابلیت ترکیب با روش‌های دیگر: نتیجه درخت تصمیم را می‌توان با تکنیک‌های تصمیم‌سازی دیگر ترکیب کرده و نتایج بهتری بدست آورد.

معایب

۱- مشکل استفاده از درخت‌های تصمیم آن است که به صورت نمایی با بزرگ شدن مسئله بزرگ می‌شوند. ۲- اکثر درخت‌های تصمیم تنها از یک ویژگی برای شاخه زدن در گره‌ها استفاده می‌کنند در صورتی که ممکن است ویژگی‌ها دارای توزیع توأم باشند. ۳- ساخت درخت تصمیم در برنامه‌های داده کاوی حافظه زیادی را مصرف می‌کند زیرا برای هر گره باید معیار کارایی برای ویژگی‌های مختلف را ذخیره کند تا بتواند بهترین ویژگی را انتخاب کند.

 

منبع

 

درخت تصمیم قسمت 1

درخت تصمیم قسمت 2

درخت تصمیم قسمت 3

درخت تصمیم قسمت 4

/0 دیدگاه /توسط

رگرسیون لجستیک (LR)

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

کاربرد این روش عمدتاً در ابتدای ظهور در مورد کاربردهای پزشکی برای احتمال وقوع یک بیماری مورد استفاده قرار می‌گرفت. لیکن امروزه در تمام زمینه‌های علمی کاربرد وسیعی یافته‌است. به عنوان مثال مدیر سازمانی می‌خواهد بداند در مشارکت یا عدم مشارکت کارمندان کدام متغیرها نقش پیش‌بینی دارند؟ مدیر تبلیغاتی می‌خواهد بداند در خرید یا عدم خرید یک محصول یا برند چه متغیرهایی مهم هستند؟ یک مرکز تحقیقات پزشکی می‌خواهد بداند در مبتلا شدن به بیماری عروق کرنری قلب چه متغیرهایی نقش پیش‌بینی‌کننده دارند؟ تا با اطلاع‌رسانی از احتمال وقوع کاسته شود.

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

این مدل به صورت

{\displaystyle \operatorname {logit} (p)=\ln \left({\frac {p}{1-p}}\right)=\beta _{0}+\beta _{1}x_{1,i}+\cdots +\beta _{k}x_{k,i},}

{\displaystyle i=1,\dots ,n,\,}

است که

{\displaystyle p=\Pr(y_{i}=1).\,}

{\displaystyle p=\Pr(y_{i}=1|{\vec {x_{i}}};{\vec {\beta }})={\frac {e^{\beta _{0}+\beta _{1}x_{1,i}+\cdots +\beta _{k}x_{k,i}}}{1+e^{\beta _{0}+\beta _{1}x_{1,i}+\cdots +\beta _{k}x_{k,i}}}}={\frac {1}{1+e^{-\left(\beta _{0}+\beta _{1}x_{1,i}+\cdots +\beta _{k}x_{k,i}\right)}}}.}

برآورد پارامترهای بهینه

برای بدست آوردن پارامترهای بهینه یعنی  می‌توان از روش برآورد درست نمایی بیشینه (Maximum Likelihood Estimation) استفاده کرد. اگر فرض کنیم که تعداد مثال‌هایی که قرار است برای تخمین پارامترها استفاده کنیم  است و این مثال‌ها را به این شکل نمایش دهیم . پارامتر بهینه پارامتری است که برآورد درست نمایی را بیشینه کند، البته برای سادگی کار برآورد لگاریتم درست نمایی را بیشینه می‌کنیم. لگاریتم درست نمایی داده برای پارامتر  را با  نمایش می‌دهیم:

 

{\displaystyle L(D,{\vec {\beta }})=\log \left(\prod _{i=1}^{n}Pr(y_{i}=1|{\vec {x_{i}}};{\vec {\beta }})^{y_{i}}\times Pr(y_{i}=0|{\vec {x_{i}}};{\vec {\beta }})^{1-y_{i}}\right)=\sum _{i=1}^{n}y_{i}\times \log Pr(y_{i}=1|{\vec {x_{i}}};{\vec {\beta }})+(1-y_{i})\log Pr(y_{i}=0|{\vec {x_{i}}};{\vec {\beta }})}

 

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

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

{\displaystyle {\begin{cases}{\mbox{Initialize}}\,\,{\vec {\beta ^{\,old}}}\,\,{\mbox{randomly}}\\{\mbox{loop until convergence :}}\\\,\,{\mbox{for}}\,\,\,\,i=0\,\,\,\,{\mbox{to}}\,\,\,\,n:\\\,\,\,\,\,\,{\mbox{for}}\,\,\,\,j=0\,\,\,\,{\mbox{to}}\,\,\,\,m:\\\,\,\,\,\,\,\,\,\,\,\,\,{\vec {\beta _{j}^{\,new}}}={\vec {\beta _{j}^{\,old}}}+\alpha \left(y_{i}-{\frac {1}{1+e^{-\left(\beta _{0}^{\,old}+\beta _{1}^{\,old}x_{1,i}+\cdots +\beta _{k}^{\,old}x_{k,i}\right)}}}\right){\vec {x_{i,j}}}\\\,\,\,\,\,\,\beta ^{\,old}=\beta ^{\,new}\end{cases}}}

تنظیم مدل (Regularization)

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

در تنظیم مدل به روش  تابع هزینه را به این شکل تغییر می‌دهیم:

{\displaystyle L_{r}(D,{\vec {\beta }})=-L(D,{\vec {\beta }})+\lambda ||{\vec {\beta }}||_{1}=-\sum _{i=1}^{n}y_{i}\times \log Pr(y_{i}=1|{\vec {x_{i}}};{\vec {\beta }})+(1-y_{i})\log Pr(y_{i}=0|{\vec {x_{i}}};{\vec {\beta }})+\lambda \sum _{k=0}^{m}|\beta _{k}|}

این روش تنظیم مدل که به روش لاسو (Lasso) نیز شهرت دارد باعث می‌شود که بسیاری از پارامترهای مدل نهائی صفر شوند و مدل به اصطلاح خلوت (Sparse) شود.

در تنظیم مدل به روش  تابع هزینه را به این شکل تغییر می‌دهیم:

{\displaystyle L_{r}(D,{\vec {\beta }})=L(D,{\vec {\beta }})+\lambda ||{\vec {\beta }}||_{2}^{2}=-\sum _{i=1}^{n}y_{i}\times \log Pr(y_{i}=1|{\vec {x_{i}}};{\vec {\beta }})+(1-y_{i})\log Pr(y_{i}=0|{\vec {x_{i}}};{\vec {\beta }})+\lambda \sum _{k=0}^{m}\beta _{k}^{2}}

در روش تنظیم از طریق سعی می‌شود طول اقلیدسی بردار  کوتاه نگه داشته شود.  در روش  و  یک عدد مثبت است که میزان تنظیم مدل را معین می‌کند. هرچقدر  کوچکتر باشد جریمه کمتری برا بزرگی نرم بردار پارامترها یعنی  پرداخت می‌کنیم. مقدار ایدئال  از طریق آزمایش بر روی داده اعتبار (Validation Data) پیدا می‌شود.

تفسیر احتمالی تنظیم مدل

اگر بجای روش درست نمایی بیشینه از روش بیشینه سازی احتمال پسین استفاده کنیم به ساختار «تنظیم مدل» یا همان regularization خواهیم رسید. اگر مجموعه داده را با نمایش بدهیم و پارامتری که به دنبال تخمین آن هستیم را با ، احتمال پسین ، طبق قانون بیز متناسب خواهد بود با حاصلضرب درست نمایی یعنی و احتمال پیشین یعنی:

{\displaystyle Pr\left({\vec {\beta }}\,|\,D\right)={\frac {Pr\left(D\,|\,{\vec {\beta }}\right)\times Pr\left({\vec {\beta }}\right)}{Pr\left(D\right)}}}

ازین رو

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

با ساده کردن این معادله به نتیجه پایین می‌رسیم:

با تغییر علامت معادله، بیشینه‌سازی را به کمینه‌سازی تغییر می‌دهیم، در این معادله همان  است:

همان‌طور که دیدیم جواب همان تنظیم مدل با نرم  است.

حال اگر توزیع پیشین را از نوع توزیع لاپلاس با میانگین صفر در نظر بگیریم به تنظیم مدل با نرم  خواهیم رسید.

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

منبع

رگرسیون لوژستیک (لجستیک)

 زمانی که متغیر وابسته ی ما دو وجهی (دو سطحی مانند جنسیت، بیماری یا عدم بیماری و …) است و می خواهیم از طریق ترکیبی از متغیرهای پیش بین دست به پیش بینی بزنیم باید از رگرسیون لجستیک استفاده کنیم. چند مثال از کاربردهای رگرسیون لجستیک در زیر ارائه می گردد.

1. در فرایند همه گیر شناسی ما می خواهیم ببینیم آیا یک فرد بیمار است یا خیر. اگر به عنوان مثال بیماری مورد نظر بیماری قلبی باشد پیش بینی کننده ها عبارتند از سن، وزن، فشار خون سیستولیک، تعداد سیگارهای کشیده شده و سطح کلسترول.

2. در بازاریابی ممکن است بخواهیم بدانیم آیا افراد یک ماشین جدیدی را می خرند یا خیر. در اینجا متغیرهایی مانند درآمد سالانه، مقدار پول رهن، تعداد وابسته ها، متغیرهای پیش بین می باشند.

3. در تعلیم و تربیت فرض کنید می خواهیم بدانیم یک فرد در امتحان نمره می آورد یا خیر.

4. در روانشناسی می خواهیم بدانیم آیا فرد یک رفتار بهنجار اجتماعی دارد یا خیر.

در تمام موارد گفته شده متغیر وابسته یک متغیر دو حالتی است که دو ارزش دارد. زمانی که متغیر وابسته دو حالتی است مسایل خاصی مطرح می شود.

1. خطا دارای توزیع نرمال نیست. 2. واریانس خطا ثابت نیست. 3. محدودیت های زیادی در تابع پاسخ وجود دارد. مشکل سوم مطرح شده مشکل جدی تری است.

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

دو مساله ی مهم که باید در ارتباط با رگرسیون لجستیک در نظر داشته باشیم عبارتند از:

1. رابطه ی بین پیش بینی کننده ها و متغیر وابسته غیر خطی است.

2. ضرایب رگرسیونی از طریق روش ماکزیمم درستنمایی برآورد می شود.

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

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

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

رگرسیون لجستیک (LOGESTIC REGRESSION)

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

رگرسیون لجستیک

بسیاری از مطالعات پژوهشی در علوم اجتماعی و علوم رفتاری، متغیرهای وابسته از نوع دو مقوله ای را بررسی می­کنند. مانند: رأی دادن یا ندادن در انتخابات، مالکیت (مثلاٌ داشتن یا نداشتن کامپیوتر شخصی) و سطح تحصیلات (مانند: داشتن یا نداشتن تحصیلات دانشگاهی) ارزیابی می­شود. از جمله حالت­ های پاسخ دوتایی عبارتند از: موافق- مخالف، موفقیت – شکست، حاضر – غایب و جانبداری – عدم جانبداری.

 

متغیرهای تحلیل رگرسیون لجستیک

در تحلیل رگرسیون لجستیک، همیشه یک متغیر وابسته و معمولا مجموعه ای از متغیرهای مستقل وجود دارند که ممکن است دو مقوله ای، کمی یا ترکیبی از آن ها باشند. به علاوه لازم نیست متغیرهای دو مقوله ای به طور واقعی دوتایی باشند. به عنوان مثال ممکن است پژوهشگران متغیر وابسته کمی دارای کجی شدید را به یک متغیر دومقوله ای که در هر طبقه آن تعداد موردها تقریباً مساوی است تبدیل کنند. مانند آن چه که در مورد رگرسیون چندگانه دیدیم، برخی از متغیرهای مستقل در رگرسیون لجستیک می­ توانند به عنوان متغیرهای همپراش (covariates) مورد استفاده قرار گیرند تا پژوهشگران بتوانند با ثابت نگه داشتن یا کنترل آماری این متغیرها اثرات دیگر متغیرهای مستقل را بهتر ارزیابی کنند.

 پیش فرض های رگرسیون لجستیک

با این که رگرسیون لجستیک در مقایسه با رگرسیون خطی پیش فرض­ های کمتری دارد (به عنوان مثال پیش فرض­ های همگنی واریانس و نرمال بودن خطاها وجود ندارد)، رگرسیون لجستیک نیازمند موارد زیر است:

  1. هم خطی چندگانه کامل وجود نداشته باشد.
  2. خطاهای خاص نباید وجود داشته باشد (یعنی، همه متغیرهای پیش­ بین مرتبط وارد شوند و پیش­ بین­ های نامربوط کنار گذاشته شوند).
  3. متغیرهای مستقل باید در مقیاس پاسخ تراکمی یا جمع پذیر (cumulative response scale)، فاصله ای یا سطح نسبی اندازه­ گیری شده باشند (هر چند که متغیرهای دو مقوله ای نیز می­ توانند مورد استفاده قرار گیرند).

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

منبع

رگرسیون لجستیک چیست؟

رگرسیون لجستیک، شبیه رگرسیون خطی است با این تفاوت که نحوه محاسبه ضرایب در این دو روش یکسان نمی باشد. بدین معنی که   رگرسیون لجستیک، به جای حداقل کردن مجذور خطاها (کاری که   رگرسیون خطی انجام می دهد)، احتمالی را که یک واقعه رخ می دهد، حداکثر می کند. همچنین، در تحلیل   رگرسیون خطی، برای آزمون برازش مدل و معنی داربودن اثر هر متغیر در مدل، به ترتیب از آماره های Fوt استفاده می شود، در حالی که در   رگرسیون لجستیک، از آماره های کای اسکوئر(X2) و والد استفاده می شود (مومنی، ۱۳۸۶: ۱۵۸).

      رگرسیون لجستیک نسبت به تحلیل تشخیصی نیز ارجحیت دارد و مهم ترین دلیل آن است که در تحلیل تشخیصی گاهی اوقات احتمال وقوع یک پدیده خارج از طیف(۰) تا (۱) قرار می گیرد و متغیرهای پیش بین نیز باید دارای توزیع در داخل محدوده (۰) تا (۱) قرار دارد و رعایت پیش فرض نرمال بودن متغیرهای پیش بینی لازم نیست (سرمد، ۱۳۸۴: ۳۳۱).

انواع رگرسیون لجستیک

   همان طور که در ابتدای مبحث تحلیل   رگرسیون لجستیک گفته شد، در   رگرسیون لجستیک، متغیر وابسته می تواند به دو شکل دووجهی و چندوجهی باشد. به همین خاطر، در نرم افزارSPSS شاهد وجود دو نوع تحلیل   رگرسیون لجستیک هستیم که بسته به تعداد مقولات و طبقات متغیر وابسته، می توانیم از یکی از این دو شکل استفاده کنیم:

۱-رگرسیون لجستیک اسمی دووجهی: موقعی است که متغیر وابسته در سطح اسمی دووجهی (دوشقی) است. یعنی در زمانی که با متغیر وابسته اسمی دووجهی سروکار داریم.

۲-رگرسیون لجستیک اسمی چندوجهی : موقعی مورد استفاده قرار می گیرد که متغیر وابسته، اسمی چندوجهی (چندشقی) است.

 

منبع

 

 

 

/0 دیدگاه /توسط

یادگیری تحت نظارت

یادگیری با نظارت یا یادگیری تحت نظارت (Supervised learning) یکی از زیرمجموعه‌های یادگیری ماشینی است. با یک مثال عمومی وارد این بحث می‌شویم. یک میوه فروشی را در نظر بگیرید که تمام میوه ها را به صورت کاملاً جدا از هم مرتب کرده‌است و شما نوع میوه را کاملاً می‌دانید، یعنی زمانی که یک میوه را در دست می‌گیرید به نام نوشته شده در قفسهٔ آن نگاه می‌کنید و در میابید که مثلاً سیب است و اصطلاحاً می‌گویند تمام داده ها تگ گذاری شده هستند. به طبع فردی از قبل دستهٔ داده‌ها را مشخص کرده‌است. حال اگر با دید موجودی در حال یادگیری به ماجرا نگاه کنیم، انتظار می‌رود فرضاً مفهومی از سیب‌ها را یاد بگیرد و احتمالاً در آینده نیز اگر تصویری از سیب‌ها دید آن را تشخیص دهد.

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

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

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

منبع

 

در این قسمت می خواهیم در رابطه با یادگیری های نظارتی و بی نظارت توضیح دادیم.

  • supervised learning = یادگیری با نظارت
  • unsupervised learning = یادگیری بدون نظارت

پیش از این یادگیری با نظارت را اینگونه تعریف کردیم:

این مدل ماشین با استفاده از داده های برچسب گذاری شده و داشتن جواب های درست یاد می گیرند که در لاتین به آن Supervised learning می گویند.

مثال های مختلفی از یادگیری ماشین با نظارت:

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

نمونه دیگری از این دست یادگیری می توان زد پیشبینی مقدار عددی می باشد، به عنوان مثال قیمت یک ماشین با مجموعه ویژگی هایی مثل (مسافت طی شده، برند، سن ماشین و …). از این دست مثال ها با عنوان regression نامیده می شوند. (در پست های بعدی حتما یک مثال با regression توسط زبان پایتون حل می کنیم.)

برای آموزش سیستم، شما باید تعداد زیادی نمونه یا به عبارتی داده، در اختیار سیستم بگذارید که شامل label و predictor ها باشد.

نکته: دقت کنید بعضی از الگوریتم های regression را می توانند در classification استفاده شوند و برعکس.

برای مثال، رگرسیون منطقی (Logistic Regression) معمولا برای طبقه بندی استفاده می شود، زیرا می تواند یک مقدار را که مربوط به احتمال متعلق به یک کلاس داده شده است، تولید کند.

 

منبع

یادگیری  با نظارت چیست؟

در یادگیری با نظارت کار با ایمپورت کردن مجموعه داده‌های شامل ویژگی‌های آموزش (خصیصه‌های آموزش | training attributes) و ویژگی‌های هدف (خصیصه‌های هدف | target attributes) آغاز می‌شود. الگوریتم یادگیری نظارت شده رابطه بین مثال‌های آموزش و متغیرهای هدف مختص آن‌ها را به دست می‌آورد و آن رابطه یاد گرفته شده را برای دسته‌بندی ورودی‌های کاملا جدید مورد استفاده قرار می‌دهد (بدون هدف‌ها). برای نمایش اینکه یادگیری نظارت شده چگونه کار می‌کند، یک مثال از پیش‌بینی نمرات دانش‌آموزان برپایه ساعات مطالعه آن‌ها ارائه می‌شود. از منظر ریاضی:

Y = f(X)+ C

که در آن:

  • F رابطه بین نمرات و تعداد ساعاتی است که دانش‌آموزان به منظور آماده شدن برای امتحانات به مطالعه می‌پردازند.
  • X ورودی است (تعداد ساعاتی که دانش‌آموز خود را آماده می‌کند).
  • Y خروجی است (نمراتی که دانش‌آموزان در آزمون کسب کرده‌اند).
  • C یک خطای تصادفی است.

هدف نهایی یادگیری نظارت شده پیش‌بینی Y با حداکثر دقت برای ورودی جدید داده شده X است. چندین راه برای پیاده‌سازی یادگیری نظارت شده وجود دارد. برخی از متداول‌ترین رویکردها در ادامه مورد بررسی قرار می‌گیرند. برپایه مجموعه داده موجود، مساله یادگیری ماشین در دو نوع «دسته‌بندی» (Classification) و «رگرسیون» (Regression) قرار می‌گیرد. اگر داده‌های موجود دارای مقادیر ورودی (آموزش) و خروجی (هدف) باشند، مساله از نوع دسته‌بندی است. اگر مجموعه داده دارای «مقادیر عددی پیوسته» (continuous numerical values) بدون هرگونه برچسب هدفی باشد، مساله از نوع رگرسیون محسوب می‌شود.


Classification: Has the output label. Is it a Cat or Dog?
Regression: How much will the house sell for?

منبع

یادگیری نظارت شده: زمانی رخ می دهد که شما با استفاده از داده هایی که به خوبی برچسب گذاری شده اند به یک ماشین آموزش می دهید؛ به بیان دیگر در این نوع یادگیری، داده ها از قبل با پاسخ های درست (نتیجه) برچسب گذاری شده اند. برای نمونه به ماشین عکسی از حرف A را نشان می دهید. سپس پرچم ایران که سه رنگ دارد را به آن نشان می دهید. یاد می دهید که یکی از رنگ ها قرمز است و یکی سبز و دیگری سفید. هرچه این مجموعه اطلاعاتی بزرگ تر باشد ماشین هم بیشتر می تواند در مورد موضوع یاد بگیرد.

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

 

منبع

یادگیری نظارتی (Supervised ML)

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

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

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

درخت تصمیم‌ (ِDecision Tree)

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

درخت تصمیم

 

دسته‌بندی کننده بیز (Naive Bayes classifier)

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

دسته بندی کننده بیز

کمینه مربعات

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

کمینه مربعات

 

رگرسیون لجستیک (logistic regression)

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

رگرسیون لجستیک

 

ماشین بردار پشتیبانی (Support vector machines )

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

ماشین بردار پشتیبان

منبع

 

و در پایان یک شمای کلی از انواع یادگیری ماشین  وتقسیم بندی های آنها جهت تفهیم بیشتر یادآور می شویم:

 

انواع یادگیری ماشین

 

 

 

 

 

/0 دیدگاه /توسط

تولید Deepfake سخنگو از تصویر

,

هوش مصنوعی جدید وحشت آور سامسونگ می تواند Deepfakeهای سخنگو از یک تصویر تولید کند.

مشکل deepfake ما در مورد بدتر شدن است: مهندسان سامسونگ در حال حاضر سرهای سخنگوی واقع گرایانه ای را توسعه داده اند که می تواند از یک تصویر تولید شود، بنابراین AI حتی می تواند کلمات را در دهان مونا لیزا قرار دهد.

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

 

 

 

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

و در حالی که همه انواع برنامه های جالب وجود دارد که از تکنولوژی می توان برای آن استفاده کرد – مانند قرار دادن یک نسخه فوق واقع گرایانه از خودتان در واقعیت مجازی – این نگرانی وجود دارد که فیلم های ویدئویی کاملاً تقلبی را می توان از یک تصویر کوچک تولید کرد.

محققان در مقاله خود نوشتند: “چنین توانایی دارای کاربردهای عملی برای تلوزیون است،، از جمله ویدئو کنفرانس و بازی های چند نفره، و همچنین صنعت جلوه های ویژه.”

deepfake

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

از آنجا که این رویکرد جدید کار گذشته را با آموزش دادن به شبکه عصبی در مورد چگونگی تبدیل ویژگی های چهره برجسته به فیلم های متحرک با نگاه واقع گرایانه، بیش از چندین بار، بهبود می دهد. سپس این دانش می تواند بر روی چند عکس (یا فقط یک عکس) از کسی که AI قبل از آن هرگز ندیده است، مستقر شود.

 

deepfake new

 

این سیستم از یک شبکه عصبی کانولوشن، یک نوع شبکه عصبی بر اساس فرآیندهای بیولوژیکی در قشر بینایی حیوان استفاده می کند. این منحصراً در پردازش پشته های تصاویر و شناخت آنچه در آنها متخصص است – “convolution” اساساً بخش هایی از تصاویر را شناسایی و استخراج می کند (آن همچنین برای نمونه، در جستجوهای تصویری در وب و تکنولوژی خودرو خود راننده استفاده می شود).

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

این تکنیک موفق به غلبه بر دو مشکل بزرگ در سرهای سخنگوی تولید شده مصنوعی شده است: پیچیدگی سرها (با دهان ها، مو، چشم ها و غیره) و توانایی ما در به راحتی کشف کردن یک سر جعلی (به عنوان مثال، چهره های شخصیتی در میان سخت ترین عناصر برای طراحان بازی ویدیویی برای درست کردن هستند).

سیستم و دیگران مانند آن، برای بهتر شدن محدود می شوند به طوریکه الگوریتم ها بهبود یابند و مدل های آموزشی موثرتر شوند – و این بدان معنی است که مجموعه ای کامل از سوالات در مورد اینکه آیا می توانید به آنچه که می بینید یا می شنوید اعتماد کنید، اگر در فرم دیجیتال باشد.

از طرف دیگر، ستاره های تلویزیون و فیلم مورد علاقه شما هرگز نباید رشد کنند و بمیرند – AI شبیه به این است که به زودی به اندازه کافی هوشمند خواهد بود تا نمایش های کاملا واقعی را فقط از چند عکس تولید کند و همچنین در زمان ذخیره.

 

 

/0 دیدگاه /توسط

الگوریتم چکه‌ آب های هوشمند (چکاه)

الگوریتم چکه آب های هوشمند یا چکاه (به انگلیسی: Intelligent Water Drops)، یک الگوریتم بهینه‌سازی بر پایه هوش گروهی است. الگوریتم چکه، الگوریتمی است که به گونه گروهی کار می‌کند و الهام گرفته از طبیعت است. این الگوریتم در اصل برای بهینه‌سازی ترکیبیاتی (Combinatorial optimization) به کار برده می‌شود ولی می‌توان آن را برای بهینه‌سازی پیوسته (Continuous optimization) نیز آماده ساخت. این الگوریتم نخستین بار در سال ۲۰۰۷ میلادی، برابر ۱۳۸۶ خورشیدی برای یافتن گشایش و راه حل برای مسأله فروشنده دوره‌گرد پیشنهاد شد. از آن پس، شماری از پژوهشگران در پی بهبود و به کار بستن این الگوریتم برای مشکل‌ها و مسئله‌های گوناگون بوده‌اند.

آشنایی

کم و بیش، هر الگوریتم چکه از دو بخش درست شده است: یک گرافی که نقش یک حافظه گسترده (distributed memory) را بازی می‌کند که بر روی آن خاک‌های لبه‌ها نگهداری می‌شود. بخش دیگر، که چندین چکه آب هوشمند (چکه‌ها) هستند که روی لبه‌ها جاری شده و از گره‌ای از گراف به گره‌ای دیگر می‌روند و با این کار خاک لبه‌های گذر کرده را دگرگون کرده و کمی به خاک در خود دارنده می‌افزایند. این چکه‌ها با همکاری و همچنین رقیبگری کاری می‌کنند تا گشایش‌های بهتری بیابند. این کار با دگرگونی خاک‌های روی گراف به گونه‌ای پیش می‌رود که گشایش‌های بهتر دسترس پذیرتر شوند. می دانیم که الگوریتم چکه دست کم نیاز به دو چکه دارد تا بتواند کار کند.

شبه-کد (pseudo-code)

الگوریتم IWD دارای دو گونه پارامتر هست: پارامترهای ایستا (static) و پویا (dynamic). پارامترهای ایستا در هنگام پردازش الگوریتم IWD، پایا (constant) هستند. پارامترهای پویا پس از هر بار تکرار الگوریتم، مقداردهی اولیه می‌شوند. میتوان شبه-کد یک الگوریتم چکاه-پایه را در هشت گام زیر بیان کرد:

1) مقداردهی اولیه‌ی پارامترهای ایستا

الف. بازنشانی مسئله در قالب یک گراف
ب. مقدار‌دهی برای پارامترهای ایستا
2) مقداردهی اولیه‌ی پارامترهای پویا: سرعت و خاک چکاه‌ها
3) پخش کردن چکاه ها روی گراف مسئله
4) ساخت راه‌حل با چکاه‌ها به همراه به روزکردن سرعت و خاک

الف. به‌روزرسانی محلی خاک در گراف
ب. به‌روزرسانی سرعت و خاک روی چکاه‌ها
5) جستجوی محلی روی هر راه‌حل چکاه(این گام دلخواه هست)
6) به‌روزکردن خاک سراسری
7) به‌روزکردن بهترین راه‌حل کلی
8) به گام ۲ برو تا زمانی‌که شرط خاتمه ارضا شود

کاربردها

برخی از کاربردهایی که با الگوریتم‌های چکه-پایه پیاده‌سازی شده‌اند در زیر آورده شده‌اند:

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

منبع

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

1) به ازای هر نود بعدی آن نود با احتمال P طوری انتخاب می شود که قبلا مشاهده نشده باشد و ضمنا شروط مساله را نیز نقض نکند. P متناسب با معکوس میزان خاک بین دو نود مربوطه است.

2) سرعت قطره به روزرسانی می شود به طوری‌که هرچه خاک بیشتری بین دو نود وجود داشته باشد مقدار کمتری به سرعت آن افزوده می‌شود.

3) میزان  خاکی که قطره از مسیر جمع‌آوری می‌کند متناسب با مقدار هیوریستیک مساله و همچنین معکوس سرعت ذره محاسبه می‌گردد. (∆soil(i,j))

4) میزان خاک موجود بین دو نود و خاکی که توسط قطره حمل می‌شود  توسط ∆soil(i,j) به روزرسانی می‌شود.

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

soil(i,j) = (1+ρIWD).soil(i,j) – ρIWD .soilIBIWD/(NIB-1)    (i,j) ϵ TIB

که در آن ρIWD پارامتر به روزرسانی سراسری، NIB تعداد نودهای بهترین مسیر در تکرار جاری و soilIBIWD قطره ای است که بهترین مسیر را پیموده است. soil(i,j) میزان خاک بین دو نود در بهترین مسیر جاری است.

همچنین بهترین مسیر سراسری با توجه به بهترین مسیر در تکرار جاری امکان دارد تغییر کند.

منبع

اصول iwd

الگوریتم مبتنی بر ذرات است. سوال اصلی چگونه پیچ و تابهای رودخانه ایجاد شده است. می خواهیم از این مکانیزم هوش طبیعی استفاده کنیم. Iwd با دو ویژگی مهم شناخته می شود:

  1. سرعت(velocity)
  2. شن(soil)

هر دو خاصیت بالا در طول عمر یک IWD بارها تغییر می کند. یک IWd از یک منبع به یک مقصد جریان می یابد. IWD سفر خود را با یک سرعت اولیه و Soil صفر آغاز می کند.در دوران سفر به سرعت خود می افزاید.

از موقعیت جاری IWD تا موقعیت بعدی سرعتش با مقدار متنایب غیر خطی تا معکوس Soilهای بین دو محل افزایش می یابد.

نابراین یک مسیر با شن کمتر iwd را با سرعت بیشتری از مسیر خاکی تر پیش می برد .مقدار شن اضافه شده به IWD خاصیت غیر خطی به معکوس زمان لازم برای iwd برای عبور از محل جاری به محل بعدی است. این بازه زمانی با قواعد ساده فیزیک برای حرکت خطی محاسبه می گردد .بنابراین زمان سپری شده متناسب با سرعت iwd و به طور معکوس با فاصله بین دو محل در نظر گرفته می شود.پس محل دارای iwd بیشتر شن کمتر دارد. پس در مورد شن حافظه دارند .یک iwd در مورد انتخاب مسیر محل بعدی یا مرحله بعدی به مکانیزم انتخاب نیاز دارد .که در این مکانیزم محل با شن کمتر ترجیح داده می شود .این رفتار انتخاب مسیر، بوسیله تحمیل یک توزیع تصادفی یکنواخت روی شنهای موجود در مسیر ، پیاده سازی می شود. پس رودخانه بهترین مسیر از بین مسیرهای ممکن از مبدأ به مقصد است .این مسیر بهینه یا نزدیک به بهینه از تراکنش قطرات آب باهم و با بستر رودخانه ایجاد می گردد.

الگوریتم IWD

الگوریتم با نمایش گرافی (N,E) است. با نودهای N و یالهای E است. پس هر IWD شروع به ساختن راه حل تدریجی بوسیله گردش در راسهای گراف در طول یالها می کند. و تا آنجا که راه حلش را کامل کند ادامه می دهد .یک تکرار الگوریتم با کامل شدن همه IWDها راه حلها تمام می شود .بعد از هر تکرار، راه حل بهترین تکرار که فرمول نامیده می شود، یافت می شود که برای بروز رسانی بهترین راه حل کلی فرمول به کار می رود .مقدار خاک در روی لبه های راه حل بهترین تکرار فرمول بر مبنای کیفیت راه حل کاهش می یابد. سپس الگوریتم با تکرار دیگر با IWDهای جدید شروع می شود .ولی با خاکهای همانند روی مسیرهای گراف و همه فرآیندها تکرار می شود .الگوریتم وقتی به ماکزیمم تکرار iter(max) می رسد و یا به کیفیت مورد نظر رسید، پایان می یابد. الگوریتم IWD دو نوع پارامتر دارد. یکی در طول عمر الگوریتم ثابت و استاتیک است. دیگری در هر تکرار الگوریتم دوباره شروع می شود و پویا است.

مراحل الگوریتم IWD عبارت است:

1- مقدار دهی اولیه پارامترهای ثابت .گراف (N,E) مساله به الگوریتم داده می شود. کیفیت راه حل کلی بهتر یعنی فرمول در ابتدا به بدترین تنطیم می شود. فرمول 1  Iter(max) بوسیله کاربر تعیین می شود .که مقدارش ابتدا به صفر مقداردهی اولیه می شود. مقدار قطرات آب فرمول 2 یک مقدار مثبت صحیح می گیرد که معمولا تعداد نودها فرمول 3 گراف است .برای بروز رسانی سرعت پارامترها cv=1 و bv=0.01 و av=1 . برای بروز رسانی پارامتر شن  cs=1 و bs=0.01 و as=1 و فرمول 4 پارامتر بروزرسانی شن محلی است که یک عدد مثبت کوچک کمتر از یک است که فرمول 5 می گیرند .پارامترهای بروز رسانی شن کلی  است .که در بازه [0,1] انتخاب می شود مثل 0.9 . همچنین مقداردهی اولیه خاک در مسیر (لبه-یال )با ثابت InitSoil مشخص میشود. مانند خاک مسیر بین هر دو نود i,j که با  initsoil=soil(i,j) سرعت اولیه هر IWD با initvel مشخص می شود. هر دو پارامتر مذکور به انتخاب کاربر و تجربی بسته به کاربرد است مثلاً ما initsoil=10000 و initvel=200 می گیریم.

2- مقداردهی اولیه پارامترهای پویا. هر IWD یک لیست نودهای ملاقات شده Vc(IWD) که ابتدا تهی است. همه IWDها به مقدار شن اولیه صفر تنطیم شده اند.

3- IWDها را به طور تصادفی در رئوس گراف به عنوان اولین نود ملاقات شده پخش می کنیم.

4- بروزرسانی لیست ملاقات شده هر IWD برای شامل کردن نودهای ملاقات شده

5- مراحل زیر یعنی 5-1 تا 5-4 را برای همه IWDها با راه حل های جزئی تکرار می شود.

   1-5- برای هر IWD مقیم در نود i، نود بعدی j  را انتخاب می کنیم. به طوری که محدودیت های پر شده را نقض نکند و در لیست نودهای ملاقات شده Vc(IWD) نباشد. با احتمال زیر :

فرمول 6

سپس نود j تازه ملاقات شده به لیست Vc(IWD) اضافه می شود.

    2-5- برای هر IWD در حال حرکت از i به j سرعتش با فرمول زیر بروزرسانی می شود.

فرمول 8

    3-5- برای هر حرکت IWD روی مسیر از i به j شن از فرمول زیر بارگذاری می شود.

فرمول 9

که میزان نامطلوبیت اکتشافی با تقریب مناسب برای مسأله تعیین می شود.

بروزرسانی شن در مسیر از i به j پیمایش شده و شن حمل شده بوسیله IWD با فرمول زیر:

فرمول 10

6- پیدا کردن بهترین راه حل تکرار جاری در بین همه راه حل های بوسیله بقیه IWDها با فرمول زیر:

فرمول 11

که تابع q کیفیت مسیر را نشان می دهد.

7- بروزرسانی شن ها در مسیرهایی که از راه حل بهتر تکرار جاری حاصل می شود.

فرمول 12

که N تعداد نودها در راه حل بهینه محلی کنونی است.

8- بروزرسانی راه حل کلی بهتر بوسیله بهترین راه حل کنونی با استفاده از فرمول زیر:

فرمول 13

9- افزایش مقدار شمارنده:

فرمول 14

10- توقف الگوریتم با مقدار بهترین راه حل کلی فرمول 15

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

الگوریتم چکه آب های هوشمند

منابع

1.https://fa.wikipedia.org

2.http://fumblog.um.ac.ir

/0 دیدگاه /توسط

الگوریتم های تکاملی

استراتژی الگوریتم های تکاملی (evolutionary strategy) (ES)

۱−۱مقدمه

الگوریتم های تکاملی(ES) یکی از روش های تکاملی می باشد. که با یک جمعیت اولیه شروع می شود در این روش بعد از انتخاب والدین از روش های تکثیر برای تولید نسل جدید استفاده می شود که در برنامه های حاضر از روش Discrete Recombination استفاده شده است. جهش نیز در یافتن مکان های جدید و جستجوی بهتر فضای جستجو کمک می کند.

۱−۲شرح الگوریتم ES

۱−۲−۱تعیین جمعیت اولیه :

ابتدا یک جمعیت اولیه در بازه مورد نظر تعیین می کنیم. این جمعیت به صورت یک ماتریس با تعداد سطر برابر با تعداد جمعیت، و تعداد ستون برابر با تعداد متغیرهای مساله می باشد.

۱−۲−۲تولید مثل Recombination:

در اینجا از روش Discrete Recombination استفاده شده است.

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

در انتها از روش (µ+λ) یعنی افزودن تعداد فرزندان تولیدی به نسل قبل و انتخاب بهترین آنها برای نسل بعد استفاده می شود.

۱−۲−۳ جهش (mutation)

انجام این عمل ما را در رسیدن به نقطه جدید کمک می کند. اصولا جهش با اضافه نمودن یک عدد گوسی به جمعیت مورد نظر صورت می گیرد.

را می توان در هر مرحله آبدیت نمود. بدین منظور در این برنامه از روش Additive  استفاده شده است که روابط آن به صورت زیر می باشد.

σij(t + 1) = σij(t) + ησij(t)Nij(0, 1)

و در نهایت جهش به صورت زیر انجام می گیرد:

۱−۲−۴ انتخاب (selection)

حال مجموعه ای از والدین و فرزندان را داریم که بهترین آنها را با توجه به مساله مورد بررسی برای تولید نسل بعد انتخاب می کنیم.

۲– برنامه ریزی تکاملی (evolutionary programming)(EP)

۲-۱ مقدمه

الگوریتم EP بسیار شبیه الگوریتم ES می باشد تنها تفاوت این دو الگوریتم در مرحله Recombination و Selection  می باشد. EP دارای  هیچگونه  Recombination نمی باشد و اعضا تنها از طریق جهش تغییر پیدا می کنند.

۲−۲ جهش(mutation)

برای انجام این عمل  از روش Additive  استفاده شده است که روابط آن به صورت زیر بوده و توضیحات کامل تر آن در قسمت ES  آورده شد.

σij(t + 1) = σij(t) + ησij(t)Nij(0, 1)

۲−۳ انتخاب(selection)

در الگوریتم EP برای انتخاب نسل بعد چندین روش وجود دارد که دو روش متداول ان در زیر توضیح داده شده است:

۲−۳−۱ انتخاب به روش مسابقه ای Selection  Tournament

در این روش دو عضو از جمعیت موجود( مجموع جمعیت اولیه و جمعیت جهش یافته) به صورت تصادفی انتخاب شده و مقدار شایستگی آنها با هم مقایسه شده و فرد شایسته تر برای حضور در نسل بعد انتخاب می شود. در الگوریتم EP نوشته شده فرد پیروز از جمعیت اولیه خارج شده و به فرد بازنده شانس دوباره داده می شود.

۲−۳−۲ انتخاب بر اساس امتیاز Rank based Selection

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

منبع

ﻳﻚ اﻟﮕﻮرﻳﺘﻢ ﺗﻜﺎملی ﭼﻴﺴﺖ؟

اﻳﺪه اﺻﻠﻲ ﻳﻚ اﻟﮕﻮرﻳﺘﻢ ﺗﻜﺎﻣﻠﻲ ﭼﻴﺴﺖ؟

اﻳﺪه اصلی ﻳﻚ ﻣﺤﻴﻂ از ﺟﻤﻌﻴﺘﻲ از اﻓﺮاد ﺑﺎ ﻣﻨﺎﺑﻊ ﻣﺤﺪود ﺗﺸﻜﻴﻞ ﻣﻲ ﺷﻮد.

رقابت ﺑﺮاي اﻳﻦ ﻣﻨﺎﺑﻊ ﺑﺎﻋﺚ اﻧﺘﺨﺎب اﻓﺮادي ﻣﻲ ﺷﻮد ﻛﻪ ﺑﻬﺘﺮ از ﺑﻘﻴﻪ ﺑﺎ ﻣﺤﻴﻂ تطبیق یافته اﻧﺪ. این اﻓﺮاد ﺑﻪ ﻋﻨﻮان واﻟﺪ ﺑﻪ ﻣﻨﻈﻮر اﻳﺠﺎد اﻓﺮاد ﺟﺪﻳﺪ از ﻃﺮﻳﻖ آﻣﻴﺰش و ﺟﻬﺶ عمل می کنند. برازندگی افراد جدید ارزیابی می شود و سپس این افراد جدید به منظور بقاء به رقابت می پردازند. در ﻃﻮل زﻣﺎن اﻧﺘﺨﺎب ﻃﺒﻴﻌﻲ ﺑﺎﻋﺚ اﻓﺰاﻳﺶ برازندگی ﺟﻤﻌﻴﺖ ﻣﻲ ﺷﻮد.

الگوریتم های تکاملی در دسته الگوریتم های “تولید و تست” قرار می گیرند.

شمای کلی الگوریتم های تکاملی

شمای کلی الگوریتم های تکاملی

ویژگی های الگوریتم های تکاملی:

اﻟﮕﻮرﻳﺘﻢ ﻫﺎی ﺗﻜﺎملی مبتنی ﺑﺮ ﺟﻤﻌﻴﺖ می ﺑﺎﺷﻨﺪ: ﻣﺠﻤﻮﻋﻪ ای از راه حل های کاندیدا را به طور همزمان پردازش می کنند.

الگوریتم های تکاملی اغلب از عملگر آمیزش به منظور ترکیب اطلاعات موجود در چندین راه حل در یک راه حل جدید استفاده می کنند.

3- الگوریتم های تکاملی اتفاقی(غیر قطعی) می باشند.

شبه کد یک الگوریتم تکاملی

BEGIN
     INITIALISE population with random candidate solutions;
     EVALUATE each candidare;
     REPEAT UNTIL ( TERMINATION CONDITION is satisfied ) DO
              SELECT  parents;
               RECOMBINE  pairs of parents;
               MUTATE  the resulting offspring;
               EVALUATE  new candidates;
               SELECT  individuals for the next generation;
     OD
END

انواع مختلف الگوریتم های تکاملی

از نظر تکنیکی، اناوع مختلف الگوریتم ها تکاملی در نحوه باز نمایی با یکدیگر تفاوت دارند:

  • رشته دودویی : الگوریتم های ژنتیک
  • بردارهایی از اعداد حقیقی: استراتژی های تکامل
  • ماشین های متناهی الحالت: برنامه نویسی تکاملی
  • درخت ها: برنامه نویسی ژنتیک

بهترین استراتژی

  • انتخاب بازنمابب مناسب(طبیعی یا ساده) برای مسأله

مثال 1: حل یک مسأله ارضاء پذیری پیکان رشته های بیتی به طول n پیکان الگوریتم ژنتیک

مثال 2: توسعه یک برنامه کامپیوتری برای انجام بازی چکر پیکان درخت پیکان برنامه نویسی ژنتیک

  • انتخاب عملگرهای مناسب برای نحوه بازنمایی
  • عملگرهای انتخاب تنها از مقدار برازندگی استفاده می کنند و بنابراین به بازنمایی بستگی ندارند.

مؤلفه های یک الگوریتم تکاملی

به منظور تعریف یک الگوریتم تکاملی خاص باید مؤلفه های زیر مشخص شوند:

  • بازنمایی (نحوه تعریف افراد)
  • تابع ارزیابی (یا تابع برازندگی)
  • جمعیت
  • مکانیزم انتخاب والد
  • عملگرهای ژنتیکی(آمیزش و جش)
  • مکانیزم انتخاب بازنده (استراتژی جایگزینی)

علاوه بر این موارد، باید نحوه تولید جمعیت اولیه  و شرط (شرایط) توقف الگوریتم نیز مشخص شوند.

روش های بازنمایی(تعریف افراد)

راه حل های کاندیدا(افراد9 در فضای فنوتایپ قرار دارند. این راه حل ها به صورت کروموزوم ها کد می شوند که در فضای زنوتایپ قرار دارند.

  • کد کردن: فنو تایپ پیکان ژنو تایپ (لزوماً یک به یک نمی باشد)
  • دیکود کردن: ژنو تایپ پیکان فنو تایپ (باید یک به یک باشد)

مثالی در این زمینه می تواند، بیشینه سازی تابع فرمول مثال در بازه ی صفر تا 15

کروموزوم ها حاوی ژن ها می باشند که محل قرار گرفتن زن در کروموزوم Locus و مقدار ژن Allele نام دارد.

برای یافتن بهینه سراسری، هر راه حل امکان پذیر باید بتواند در فضای ژنوتایپ بازنمایی شود. 

تابع ارزیابی(برازندگی)

بیانگر نیازمندیهایی است که جکعیت باید با آنها تطبیق یابد. نوعی تابع کیفیت یا تابع هدف است و به هر فنوتایپ یک مقدار برازندگی(عدد حقیقی) نسبت می دهد و اساس انتخاب را تشکیل می دهد. بنابراین هر قدر مقادیر متفاوت تری را نسبت دهد، بهتر است. نوعاً برازندگی کمیتی است که باید بیشینه شود. تبدیل یک مسأله کمینه سازی به یک مسأله بیشینه سازی و بر عکس کار ساده ای می باشد.

جمعیت

نقش جمعیت نگهداری راه حل های ممکن برای مسأله می باشد که معمولاً دارای اندازه ثابتی می باشد و یک چندمجموعه از ژنوتایپ ها می باشد.

معمولاً عملگرهای انتخاب کل جمعیت را در نظر می گیرند، یعنی احتمال تکثیر هر کروموزوم نسبت به نسل فعلی محاسبه می شود. تعداد برازندگی ها/فنوتایپ ها/ژنوتایپ های متفاوت در جمعیت معرف تنوع آن جمعیت می باشد.

مکانیزم انتخاب

افراد را بر اساس مقدار برازندگی آنها به عنوان والد برای تولید نسل انتخاب می کند. معمولاً احتمالاتی می باشد:

  • راه حل هایی که دارای کیفیت بالاتری هستند نسبت به راه حل هایی که دارای کیفیت پایین تری می باشند، شانس بیشتری برای انتخاب شدن دارند.
  • اما چنین چیزی تضمین شده نیست.
  • حتی بدترین فرد حاضر در جمعیت نیز شانس انتخاب شدن دارد.

همین طبیعت غیر قطعی به فرار از بهینه های محلی کمک می کند.

عملگرهای ژنتیکی

نقش آنها تولید راه حل های کاندیدای جدید می باشد. این عملگرها معمولاً بر اساس چندی(تعداد ورودی) در دو دسته قرار می گیرند:

  • چندی = 1: عملگرهای جهش
  • چندی> 1: عملگرهای امیزش
  • چندی = 2: عملگر crossover

بحث های بسیاری در مورد اهمیت نسبی عملگرهای ژنتیکی(آمیزش و جهش) وجود دارد. امروزه اغلب الگوریتم های تکاملی از هر دو استفاده می کنند. انتخاب عملگرهای ژنتیکی خاص، وابسته به نحوه بازنمایی می باشد.

عملگر جهش

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

  • در GA دودویی- یک عملگر پس زمینه و مسئول حفظ و ایجاد تنوع می باشد
  • در EP برای ماشین های متناهی الحالت و متغیرهای پیوسته –  تنها عملگر جستجو
  • در GP – به ندرت استفاده می شود.

عملگر جهش می تواند تضمین کننده پیوستگی فضای جستجو باشد(اثبات همگرایی).

عملگر آمیزش

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

جایگزینی

اغلب الگوریتم های تکاملی از یک اندازه ثابت برای جمعیت استفاده می کنند و بنابراین به روشی برای رفتن به نسل بعدی(با انتخاب افراد از میان والدین و فرزندان) نیاز دارند. اغلب قطعی می باشد :

  • مبتنی بر برازندگی: مثلاً رتبه بندی والدین + فرزندان بر اساس برازندگی ها و انتخاب بهتریت ها
  • مبتنی بر سن: به تعداد والدین فرزند ایجاد می شود و سپس تمامی والدین حذف می شوند.

برخی مواقع به صورت ترکیبی(elitism)

مقدار دهی جمعیت اولیه و توقف

مقدار دهی جمعیت اولیه معمولاً به صورت تصادفی می باشد. می تواند شامل راه حل های موجود باشد و یا از هیوریستسک های خاص مسأله برای ایجاد جمعیت اولیه استفاده کند. شرایط توقف در هر نسلی بررسی می شود:

  • رسیدن به یک مقدار خاص از برازندگی
  • رسیدن به یک حداکثر تعداد مجاز از نسل ها
  • رسیدن به یک سطح حداقل از نظر تنوع
  • رسیدن به یک تعداد مشخص از نسل های متوالی بدون بهبود برازندگی

الگوریتم های تکاملی در مفهوم

دیدگاه های زیادی در مرود استفاده از الگوریتم های کاملی به عنوان یک ابزار قوی در حل مسأله وجود دارد. برای اغلب مسائل یک ابزار خاص مسأله ممکن است :

  • از یک الگوریتم جستجوی عمومی بر روی اغلب نمونه ها بهتر عمل کند.
  • کاربرد محدودی داشته باشد
  • بر روی تمام نمونه ها به خوبی عمل نکند.

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

/0 دیدگاه /توسط