بایگانی برچسب برای: kvl htchv vsa dhv

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

انواع الگوریتم های یادگیری ماشین

سه نوع اصلی الگوریتم های یادگیری ماشین از قرار زیرند :

  • یادگیری نظارت شده (هدایت شده – Supervised Learning) : در این نوع از الگوریتم ها که بار اصلی یادگیری ماشین را بر دوش می کشند (از لحاظ تعداد الگوریتم های این نوع)، با دو نوع از متغیرها سروکار داریم . نوع اول که متغیرهای مستقل نامیده میشوند، یک یا چند متغیر هستند که قرار است بر اساس مقادیر آنها، یک متغیر دیگر را پیش بینی کنیم. مثلا سن مشتری و تحصیلات و میزان درآمد و وضعیت تاهل برای پیش بینی خرید یک کالا توسط یک مشتری ، متغیرهای مستقل هستند. نوع دوم هم متغیرهای وابسته یا هدف یا خروجی هستند و قرار است مقادیر آنها را به کمک این الگوریتم ها پیش بینی کنیم . برای این منظور باید تابعی ایجاد کنیم که ورودیها (متغیرهای مستقل) را گرفته و خروجی موردنظر (متغیر وابسته یا هدف) را تولید کند. فرآیند یافتن این تابع که در حقیقت کشف رابطه ای بین متغیرهای مستقل و متغیرهای وابسته است را فرآیند آموزش (Training Process) می گوئیم که روی داده های موجود (داده هایی که هم متغیرهای مستقل و هم متغیرهای وابسته آنها معلوم هستند مثلا خریدهای گذشته مشتریان یک فروشگاه) اعمال میشود و تا رسیدن به دقت لازم ادامه می یابد.  نمونه هایی از این الگوریتم ها عبارتند از رگرسیون، درختهای تصمیم ، جنگل های تصادفی، N نزدیک ترین همسایه، و رگرسیون لجستیک می باشند.
  • یادگیری بدون ناظر (unsupervised learning) : در این نوع از الگوریتم ها ، متغیر هدف نداریم و خروجی الگوریتم، نامشخص است. بهترین مثالی که برای این نوع از الگوریتم ها می توان زد، گروه بندی خودکار (خوشه بندی) یک جمعیت است مثلاً با داشتن اطلاعات شخصی و خریدهای مشتریان، به صورت خودکار آنها را به گروه های همسان و هم ارز تقسیم کنیم . الگوریتم Apriori و K-Means از این دسته هستند.

 

type of machine learning

  • یادگیری تقویت شونده (Reinforcement Learning) : نوع سوم از الگوریتم ها که شاید بتوان آنها را در زمره الگوریتم های بدون ناظر هم دسته بندی کرد، دسته ای هستند که از آنها با نام یادگیری تقویت شونده یاد میشود. در این نوع از الگوریتم ها، یک ماشین (در حقیقت برنامه کنترل کننده آن)، برای گرفتن یک تصمیم خاص ، آموزش داده می شود و ماشین بر اساس موقعیت فعلی (مجموعه متغیرهای موجود) و اکشن های مجاز (مثلا حرکت به جلو ، حرکت به عقب و …) ، یک تصمیم را می گیرد که در دفعات اول، این تصمیم می تواند کاملاً تصادفی باشد و به ازای هر اکشن یا رفتاری که بروز می دهد، سیستم یک فیدبک یا بازخورد یا امتیاز به او میدهد و از روی این فیدبک، ماشین متوجه میشود که تصمیم درست را اتخاذ کرده است یا نه که در دفعات بعد در آن موقعیت ، همان اکشن را تکرار کند یا اکشن و رفتار دیگری را امتحان کند.  با توجه به وابسته بودن حالت و رفتار فعلی به حالات و رفتارهای قبلی، فرآیند تصمیم گیری مارکوف ، یکی از مثالهای این گروه از الگوریتم ها می تواند باشد . الگوریتم های شبکه های عصبی هم می توانند ازین دسته به حساب آیند. منظور از کلمه تقویت شونده در نام گذاری این الگوریتم ها هم اشاره به مرحله فیدبک و بازخورد است که باعث تقویت و بهبود عملکرد برنامه و الگوریتم می شود .

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

 

Machine learning algorithms

 

الگوریتم های اصلی و رایج یادگیری ماشین

در این سری از مقالات به آموزش الگوریتم های زیر با نمونه کدهای لازم و مثالهای تشریحی، خواهیم پرداخت :

  1. رگرسیون خطی
  2. رگرسیون لجستیک
  3. درخت تصمیم
  4. SVM
  5. Naive Bayes
  6. KNN
  7. K-Means
  8. جنگل تصادفی
  9. الگوریتم های کاهش ابعاد
  10. Gradient Boost & Ada Boost

 

طبقه بندی الگوریتم های مختلف یادگیری ماشین

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

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

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

رمز : behsanandish.com

این ده الگوریتم عبارتند از :

در سال ۲۰۱۱، در سایت پرسش و پاسخ معروف Qura در پاسخ به سوالی که ده الگوریتم برتر داده کاوی را پرسیده بود، موارد زیر توسط کاربران برشمرده شده اند :

  1. Kernel Density Estimation and Non-parametric Bayes Classifier
  2. K-Means
  3. Kernel Principal Components Analysis
  4. Linear Regression
  5. Neighbors (Nearest, Farthest, Range, k, Classification)
  6. Non-Negative Matrix Factorization
  7. Dimensionality Reduction
  8. Fast Singular Value Decomposition
  9. Decision Tree
  10. Bootstapped SVM
  11. Decision Tree
  12. Gaussian Processes
  13. Logistic Regression
  14. Logit Boost
  15. Model Tree
  16. Naïve Bayes
  17. Nearest Neighbors
  18. PLS
  19. Random Forest
  20. Ridge Regression
  21. Support Vector Machine
  22. Classification: logistic regression, naïve bayes, SVM, decision tree
  23. Regression: multiple regression, SVM
  24. Attribute importance: MDL
  25. Anomaly detection: one-class SVM
  26. Clustering: k-means, orthogonal partitioning
  27. Association: A Priori
  28. Feature extraction: NNMF

و در سال ۲۰۱۵ این لیست به صورت زیر در آمده است :

  1. Linear regression
  2. Logistic regression
  3. k-means
  4. SVMs
  5. Random Forests
  6. Matrix Factorization/SVD
  7. Gradient Boosted Decision Trees/Machines
  8. Naive Bayes
  9. Artificial Neural Networks
  10. For the last one I’d let you pick one of the following:
  11. Bayesian Networks
  12. Elastic Nets
  13. Any other clustering algo besides k-means
  14. LDA
  15. Conditional Random Fields
  16. HDPs or other Bayesian non-parametric model

سایت DataFloq اخیراً یک طبقه بندی گرافیکی از الگوریتم های ضروری یادگیری ماشین ارائه کرده است که به صورت طبقه بندی شده ، این الگوریتم ها را فهرست کرده است :

 

12-algorithms-every-data-scientist-should-know

 

این طبقه بندی را به صورت نقشه ذهن یا Mind Map هم می توانیم مشاهده کنیم :

 

Machine Learning Algorithms

 

 

منبع

 

 

برنامه نویسی Parallel در سی شارپ :: مقدمه ای بر Task Parallel Library و کلاس Parallel در دات نت

پیش از این ما در سری مطالب مرتبط با بحث کار با Thread با نحوه ایجاد و مدیریت Thread ها در دات نت آشنا شدیم. از نسخه 4 دات نت قابلیتی اضافه شد با نام Task Parallel Programming یا TPL که روش جدیدی برای نوشتن برنامه Multi-Theaded است. این قابلیت بوسیله یکسری از کلاس ها که در فضای نام System.Threading.Tasks قرار دارد فراهم شده و به ما این اجازه را می دهد که بدون درگیر شدن مستقیم با Thread ها و Thread Pool ها برنامه های Multi-Threaded بنوسیم.

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

فضای نام System.Threading.Tasks

همانطور که گفتیم TPL در حقیقت مجموعه ای از کلاس ها است که در فضای نام System.Threading.Tasks قرار گرفته. یکی از قابلیت های TPL این است که کارهای محوله را به صورت خودکار بین CPU های سیستم (در صورت وجود) توزیع می کند که این کار در پشت زمینه بوسیله CLR Thread Pool انجام می شود.

کارهای انجام شده توسط TPL در پشت زمینه عبارتند از تقسیم بندی وظایف، زمانبندی Thread ها، مدیریت وضعیت (State Management) و یکسری از کارهای اصطلاحاً Low-Level دیگر. نتیجه این کار برای شما بالا رفتن کارآیی برنامه ها بوده بدون اینکه درگیر پیچیدگی های کار با Thread ها شوید. همانطور که گفتیم فضای نام System.Threading.Tasks شامل یکسری کلاس ها مانند کلاس Parallel، کلاس Task و … می باشد که در ادامه با این کلاس ها بیشتر آشنا می شویم.

نقش کلاس Parallel

یکی از کلاس های TPL که نقش کلیدی را در نوشتن کدهای Parallel ایفا می کند، کلاس Parallel است، این کلاس یکسری متدها در اختیار ما قرار می دهد که بتوانیم بر روی آیتم های یک مجموعه (علی الخصوص مجموعه هایی که اینترفیس IEnumerable را پیاده سازی کرده اند) به صورت parallel عملیات هایی را انجام دهیم.

متدهای این کلاس عبارتند از متد های For و ForEach که البته Overload های متفاوتی برای این متدها وجود دارد. بوسیله این متدها می توان کدهایی نوشتن که عملیات مورد نظر را به صورت parallel بر روی آیتم های یک مجموعه انجام دهند. دقت کنید کدهایی که برای این متدها نوشته می شوند در حقیقت همان کدهایی هستند که معمولاً در حلقه های for و foreach استفاده می شوند، با این تفاوت که به صورت parallel اجرا شده و اجرا و مدیریت کدها بوسیله thread ها و CLR Thread Pool انجام شده و البته بحث همزمانی نیز به صورت خودکار مدیریت می شود.

کار با متد ForEach

در ابتدا به سراغ متد ForEach می رویم، این متد یک مجموعه که ایترفیس IEnumerable را پیاده سازی کرده به عنوان پارامتر اول و متدی که باید بر روی هر یک اعضای این مجموعه انجام شود را به عنوان پارامتر دوم قبول می کند:

var numbers = new List < int > {2, 6, 8, 1, 3, 9, 6, 10, 5, 4};
Parallel.For(3, 6, index  = >
{
    Console.WriteLine(numbers[index]);
    Console.WriteLine("Thread Id: {0}", System.Threading.Thread.CurrentThread.ManagedThreadId);
});

در کد بالا یک آرایه از لیست از نوع int تعریف کرده و در مرحله بعد بوسیله متد ForEach در کلاس Parallel اعضای لیست را پردازش می کنیم، با هر بار اجرا خروجی های متفاوتی دریافت خواهیم کرد:

8
5
Thread Id: 6
4
2
Thread Id: 1
6
3
Thread Id: 5
9
Thread Id: 5
10
Thread Id: 5
1
Thread Id: 5
Thread Id: 4
Thread Id: 6
6
Thread Id: 1
Thread Id: 3

همانطور که مشاهده می کنید شناسه های مربوط به thread در هر بار اجرای کدی مشخص شده در متد ForEach با یکدگیر متفاوت است، دلیل این موضوع ایجاد و مدیریت Thread ها توسط CLR Thread Pool است که ممکن است با هر بار فراخوانی متد مشخص شده به عنوان پارامتر دوم یک thread جدید ایجاد شده یا عملیات در یک thread موجود انجام شود.

کار با متد For

اما علاوه بر متد ForEach متد For نیست را می توان برای پردازش یک مجموعه استفاده کرد. در ساده ترین حالت این متد یک عدد به عنوان اندیس شروع حلقه، عدد دوم به عنوان اندیس پایان حلقه و یک پارامتر که متدی با پارامتر ورودی از نوع int یا long که نشان دهنده اندیس جاری است قبول می کند، برای مثال در متد زیر بوسیله متد For لیست numbers را در خروجی چاپ می کنیم، اما نه همه خانه های آن را پس عبارت اند از:

var numbers = new List < int >  {2, 6, 8, 1, 3, 9, 6, 10, 5, 4};
Parallel.For(3, 6, index  = >
{
    Console.WriteLine(numbers[index]);
    Console.WriteLine("Thread Id: {0}", System.Threading.Thread.CurrentThread.ManagedThreadId);
});

با اجرای کد بالا خروجی زیر نمایش داده می شود، البته با هر بار اجرا ممکن است خروجی ها با هم متفاوت باشند:

1
Thread Id: 1
9
3
Thread Id: 3
Thread Id: 4

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

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

منبع



قسمت اول آموزش-برنامه نویسی Asynchronous – آشنایی با Process ها، Thread ها و AppDomain ها

قسمت دوم آموزش- آشنایی با ماهیت Asynchronous در Delegate ها

قسمت سوم آموزش-آشنایی با فضای نام System.Threading و کلاس Thread

قسمت چهارم آموزش- آشنایی با Thread های Foreground و Background در دات نت

قسمت پنجم آموزش- آشنایی با مشکل Concurrency در برنامه های Multi-Threaded و راهکار های رفع این مشکل

قسمت ششم آموزش- آشنایی با کلاس Timer در زبان سی شارپ

قسمت هفتم آموزش-آشنایی با CLR ThreadPool در دات نت

قسمت هشتم آموزش- مقدمه ای بر Task Parallel Library و کلاس Parallel در دات نت

قسمت نهم آموزش- برنامه نویسی Parallel:آشنایی با کلاس Task در سی شارپ

قسمت دهم آموزش-برنامه نویسی Parallel در سی شارپ :: متوقف کردن Task ها در سی شارپ – کلاس CancellationToken

قسمت یازدهم آموزش- برنامه نویسی Parallel در سی شارپ :: کوئری های Parallel در LINQ

قسمت دوازدهم آموزش- آشنایی با کلمات کلیدی async و await در زبان سی شارپ

قسمت سیزدهم آموزش- استفاده از متد WhenAll برای اجرای چندین Task به صورت همزمان در سی شارپ

الگوریتم Canny

لبه یاب کنی توسط جان اف کنی در سال 1986 ایجاد شد و هنوز یک لبه یاب استاندارد و با دقت و کیفیت بالا میباشد.الگوریتم لبه یابی کنی یکی از بهترین لبه یابها تا به امروز است. در ادامه روش کار این الگوریتم و هم چنین کد الگوریتم Canny در Visual Basic را بررسی خواهیم کرد. این الگوریتم لبه یابی از سه بخش اصلی زیر تشکیل شده:

  • تضعیف نویز
  • پیدا کردن نقاطی که بتوان آنها را به عنوان لبه در نظر گرفت
  • حذب نقاطی که احتمال لبه بودن آنها کم است

 

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

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

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

 

مراحل الگوریتم Canny:

1- در ابتدا باید تصویر رنگی را به جهت لبه یابی بهتر به یک تصویر سطح خاکسترن تبدیب کرد.

2- نویز را از تصویر دریافتی حذف کرد. بدلیل اینکه فیلتر گاوسین از یک ماسک ساده برای حذف نویز استفاده می کند لبه یاب کنی در مرحله اول برای حذف نویز آن را بکار میگیرد.

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

4- برخی از لبه های کشف شده واقعا لبه نیستند و در واقع نویز هستند که باید آنها توسط حد آستانه هیسترزیس فیلتر شوند.هیسترزیس از دو حد آستانه بالاتر (Th) و حد آستانه پایین تر (Tl) استفاده کرده و کنی پیشنهاد می کند که نسبت استانه بالا به پایین سه به یک باشد.

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

 

الگوریتم Canny    عملکرد الگوریتم Canny

 

الگوریتم Canny در Visual Basic:

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

 

Imports System.Drawing
Imports System.Drawing.Imaging

Public Class clsEdges

    Public Sub EdgeDetectDifference(ByVal b As Bitmap, ByVal threshold As Byte)
        ' first we create a clone o the image we want to find the edges on
        Dim b2 As Bitmap = b.Clone
        ' we create bitmapdata of the images at the same time locking them
        Dim bmData1 As BitmapData = b.LockBits(New Rectangle(0, 0, b.Width, b.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        Dim bmData2 As BitmapData = b2.LockBits(New Rectangle(0, 0, b2.Width, b2.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        ' the stride describes the distance between image bytes
        Dim stride As Integer = bmData2.Stride
        ' scan0 is some sort of OS handle or something to identify the actual data in the memory
        Dim scan01 As IntPtr = bmData1.Scan0
        Dim scan02 As IntPtr = bmData2.Scan0
        ' we need to know how big the data is so that we can create the correct size for the file
        Dim bytes As Integer = b.Height * b.Width * 3
        ' we create the byte arrays so that we can edit them
        Dim p01(bytes - 1) As Byte
        Dim p02(bytes - 1) As Byte
        ' put the images into the byte arrays
        System.Runtime.InteropServices.Marshal.Copy(scan01, p01, 0, bytes)
        System.Runtime.InteropServices.Marshal.Copy(scan02, p02, 0, bytes)

        ' the nWidth describes the width of the actual image multiplied by three for each byte in the pixel (3 bytes per pixel 24 bits ;))
        Dim nWidth As Integer = b2.Width * 3
        ' for some reason although the original code show a formula to come up with the offset this doesn't work very well.
        ' I found that it is just easier to make the offset 0 and so all bits are handled. Basically the problem comes when 
        ' using this on files that don't have
        Dim nOffset As Integer = 0
        Dim nPixel As Integer = 0, npixelmax As Integer = 0
        Dim pos1 As Integer = stride + 3
        Dim pos2 As Integer = stride + 3
        Dim p2minusplus As Integer, p2plusminus As Integer, p2plusplus As Integer, p2minusminus As Integer
        Dim p2minusstride As Integer, p2plusstride As Integer
        Dim p2plus As Integer, p2minus As Integer

        For y As Integer = 1 To b.Height - 1
            For x As Integer = 1 To nWidth - 3

                p2minusplus = pos2 - stride + 3
                p2plusminus = pos2 + stride - 3
                p2plusplus = pos2 + stride + 3
                p2minusminus = pos2 - stride - 3
                p2minusstride = pos2 - stride
                p2plusstride = pos2 + stride
                p2minus = pos2 - 3
                p2plus = pos2 + 3
                If p2minusplus <= p02.Length - 1 And p2minusplus >= 0 And p2plusminus <= p02.Length - 1 And p2plusminus >= 0 And _
                p2plusplus <= p02.Length - 1 And p2plusplus >= 0 And p2minusminus <= p02.Length - 1 And p2minusminus >= 0 And _
                p2minusstride <= p02.Length - 1 And p2minusstride >= 0 And p2plusstride <= p02.Length - 1 And p2plusstride >= 0 And _
                p2plus <= p02.Length - 1 And p2plus >= 0 And p2minus <= p02.Length - 1 And p2minus >= 0 And pos1 < p01.Length Then
                    npixelmax = Math.Abs(CInt(p02(p2minusplus)) - CInt(p02(p2plusminus)))
                    nPixel = Math.Abs(CInt(p02(p2plusplus)) - CInt(p02(p2minusminus)))
                    If nPixel > npixelmax Then npixelmax = nPixel
                    nPixel = Math.Abs(CInt(p02(p2minusstride)) - CInt(p02(p2plusstride)))
                    If nPixel > npixelmax Then npixelmax = nPixel
                    nPixel = Math.Abs(CInt(p02(p2plus)) - CInt(p02(p2minus)))
                    If nPixel > npixelmax Then npixelmax = nPixel
                    If npixelmax < CInt(threshold) Then npixelmax = 0
                    p01(pos1) = CByte(npixelmax)
                End If
                pos1 += 1
                pos2 += 1

            Next
            pos1 += nOffset
            pos2 += nOffset
        Next

        System.Runtime.InteropServices.Marshal.Copy(p01, 0, scan01, bytes)

        b.UnlockBits(bmData1)
        b2.UnlockBits(bmData2)

    End Sub
    Public Sub EdgeDetectHomogenity(ByVal b As Bitmap, ByVal threshold As Byte)
        Dim b2 As Bitmap = b.Clone
        Dim bmData1 As BitmapData = b.LockBits(New Rectangle(0, 0, b.Width, b.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        Dim bmData2 As BitmapData = b2.LockBits(New Rectangle(0, 0, b2.Width, b2.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        Dim stride As Integer = bmData2.Stride
        Dim scan01 As IntPtr = bmData1.Scan0
        Dim scan02 As IntPtr = bmData2.Scan0
        Dim bytes As Integer = b.Height * b.Width * 3
        Dim p01(bytes - 1) As Byte
        Dim p02(bytes - 1) As Byte

        System.Runtime.InteropServices.Marshal.Copy(scan01, p01, 0, bytes)
        System.Runtime.InteropServices.Marshal.Copy(scan02, p02, 0, bytes)
        Dim nWidth As Integer = b2.Width * 3
        Dim nOffset As Integer = 0
        Dim nPixel As Integer = 0, npixelmax As Integer = 0
        Dim pos1 As Integer = stride + 3
        Dim pos2 As Integer = stride + 3

        Dim p2plusminus As Integer, p2plusstride As Integer, p2plusplus As Integer, p2minusstride As Integer, _
        p2minusminus As Integer, p2minusplus As Integer

        For y As Integer = 1 To b.Height - 1
            For x As Integer = 1 To nWidth - 3

                p2plusminus = pos2 + stride - 3
                p2plusstride = pos2 + stride
                p2plusplus = pos2 + stride + 3
                p2minusstride = pos2 - stride
                p2minusminus = pos2 - stride - 3
                p2minusplus = pos2 - stride + 3

                If p2plusminus < p02.Length And p2plusminus >= 0 And p2plusstride < p02.Length And p2plusstride >= 0 And _
                p2plusplus < p02.Length And p2plusplus >= 0 And p2minusstride < p02.Length And p2minusstride >= 0 And _
                p2minusstride < p02.Length And p2minusstride >= 0 And p2minusminus < p02.Length And p2minusminus >= 0 And _
                p2minusplus < p02.Length And p2minusplus >= 0 Then

                    npixelmax = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2plusminus)))
                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2plusstride)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2plusplus)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2minusstride)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2plusstride)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2minusminus)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2minusstride)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2)) - CInt(p02(p2minusplus)))
                    If nPixel > npixelmax Then npixelmax = nPixel


                    If npixelmax < threshold Then npixelmax = 0

                    p01(pos1) = CByte(npixelmax)

                End If

                pos1 += 1
                pos2 += 1
            Next
            pos1 += nOffset
            pos2 += nOffset
        Next

        System.Runtime.InteropServices.Marshal.Copy(p01, 0, scan01, bytes)

        b.UnlockBits(bmData1)
        b2.UnlockBits(bmData2)

    End Sub


    Public Function EdgeEnhance(ByVal b As Bitmap, ByVal threshold As Byte) As Boolean
        Dim b2 As Bitmap = b.Clone
        Dim bmData1 As BitmapData = b.LockBits(New Rectangle(0, 0, b.Width, b.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        Dim bmData2 As BitmapData = b2.LockBits(New Rectangle(0, 0, b2.Width, b2.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb)
        Dim stride As Integer = bmData2.Stride
        Dim scan01 As IntPtr = bmData1.Scan0
        Dim scan02 As IntPtr = bmData2.Scan0
        Dim bytes As Integer = b.Height * b.Width * 3
        Dim p01(bytes - 1) As Byte
        Dim p02(bytes - 1) As Byte

        System.Runtime.InteropServices.Marshal.Copy(scan01, p01, 0, bytes)
        System.Runtime.InteropServices.Marshal.Copy(scan02, p02, 0, bytes)
        Dim nWidth As Integer = b2.Width * 3
        Dim nOffset As Integer = 0
        Dim nPixel As Integer = 0, npixelmax As Integer = 0
        Dim pos1 As Integer = stride + 3
        Dim pos2 As Integer = stride + 3
        Dim p2minusplus As Integer, p2plusminus As Integer, p2plusplus As Integer, p2minusminus As Integer
        Dim p2minusstride As Integer, p2plusstride As Integer
        Dim p2plus As Integer, p2minus As Integer

        For y As Integer = 1 To b.Height - 1
            For x As Integer = 1 To nWidth - 3

                p2minusplus = pos2 - stride + 3
                p2plusminus = pos2 + stride - 3
                p2plusplus = pos2 + stride + 3
                p2minusminus = pos2 - stride - 3
                p2minusstride = pos2 - stride
                p2plusstride = pos2 + stride
                p2minus = pos2 - 3
                p2plus = pos2 + 3
                If p2minusplus <= p02.Length - 1 And p2minusplus >= 0 And p2plusminus <= p02.Length - 1 And p2plusminus >= 0 And _
                p2plusplus <= p02.Length - 1 And p2plusplus >= 0 And p2minusminus <= p02.Length - 1 And p2minusminus >= 0 And _
                p2minusstride <= p02.Length - 1 And p2minusstride >= 0 And p2plusstride <= p02.Length - 1 And p2plusstride >= 0 And _
                p2plus <= p02.Length - 1 And p2plus >= 0 And p2minus <= p02.Length - 1 And p2minus >= 0 And pos1 < p01.Length Then
                    npixelmax = Math.Abs(CInt(p02(pos2 - stride + 3)) - CInt(p02(pos2 + stride - 3)))
                    nPixel = Math.Abs(CInt(p02(pos2 + stride + 3)) - CInt(p02(pos2 - stride - 3)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2 - stride)) - CInt(p02(pos2 + stride)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    nPixel = Math.Abs(CInt(p02(pos2 + 3)) - CInt(p02(pos2 - 3)))
                    If nPixel > npixelmax Then npixelmax = nPixel

                    If npixelmax > threshold And npixelmax > p01(pos1) Then
                        p01(pos1) = CByte(Math.Max(CInt(p01(pos1)), npixelmax))
                    End If

                End If

                pos1 += 1
                pos2 += 1
            Next
            pos1 += nOffset
            pos2 += nOffset
        Next

        System.Runtime.InteropServices.Marshal.Copy(p01, 0, scan01, bytes)

        b.UnlockBits(bmData1)
        b2.UnlockBits(bmData2)

        Return True
    End Function

End Class

 

 

این کد کامل نیست!

دانلود کد فوق از طریق لینک زیر:

CannyInVisualBasic

رمز فایل : behsanandish.com

 

معایب و مزایای خوشه‌بندی k-میانگین

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

به منظور ارزیابی نتایج خوشه‌بندی از معیارهای متفاوتی کمک گرفته می‌شود. ممکن است از قبل برچسب خوشه‌ها مشخص باشد و بخواهیم کارایی الگوریتم را با توجه به مقایسه برچسب‌های واقعی و حاصل از خوشه‌بندی، اندازه‌گیری کنیم. در این حالت، شاخص‌های ارزیابی بیرونی، بهترین راهنما و معیار برای سنجش صحت نتایج خوشه‌بندی محسوب می‌شوند. معمولا به این برچسب‌ها، استاندارد طلایی (Golden Standard) و در کل چنین عملی را ارزیابی Benchmark می‌گویند. برای مثال شاخص رَند (Rand Index) یکی از این معیارها و شاخص‌های بیرونی است که از محبوبیت خاصی نیز برخوردار است.

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

منبع


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

برای مثال، ماشین شماره‌ی ۴#، دارای طولِ ۹ و ارتفاع ۴ است. در الگوریتمِ KMeans بایستی تعدادی نقطه در فضا ایجاد کنیم. تعداد این نقاط باید به تعداد خوشه‌هایی که می‌خواهیم در نهایت به آن برسیم، باشد (مثلا فرض کنید می‌خواهیم داده‌ها را به ۲خوشه تقسیم‌بندی کنیم، پس ۲نقطه به صورت تصادفی در فضای ۲بُعدیِ شکلِ بالا رسم می‌کنیم). شکل زیر را نگاه کنید:

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

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

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

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

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

همان طور که می‌بینید در انتهای دورِ سوم، تغییری در خوشه‌ی هر کدام از نمونه‌ها رخ نداد. یعنی سبزها سبز ماندند و قرمزها، قرمز.این یکی از شروطی است که می‌تواند الگوریتم را خاتمه دهد. یعنی الگوریتمْ وقتی به این حالت رسید که در چند دورِ متوالی تغییری در خوشه‌ی نمونه‌ها (در این‌جا ماشین‌ها) به وجود نیامد، یعنی الگوریتمْ دیگر نمی‌تواند زیاد تغییر کند و این حالتِ پایانی برای خوشه‌هاست. البته می‌توان شرطی دیگر نیز برای پایان الگوریتم در نظر گرفت. برای مثال الگوریتمْ حداکثر در ۲۰دورِ متوالی می‌تواند عملیات را انجام دهد و دورِ ۲۰ام آخرین دورِ الگوریتم خواهد بود و الگوریتم دیگر بیشتر از آن پیشروی نخواهد کرد. به طور کل در الگوریتم‌های مبتنی بر دور (Iterative Algorithms) می‌توان تعدادِ دورها را محدود کرد تا الگوریتمْ بی‌نهایت دور نداشته باشد.

همان طور که دیدیم، این الگوریتم می‌تواند یک گروه‌بندیِ ذاتی برای داده‌ها بسازد، بدون اینکه برچسب داده‌ها یا نوع آن‌ها را بداند.

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

منبع


مروری بر الگوریتم K-Means

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

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

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

برای درک بهتر نحوه کار الگوریتم K-Means از مثال زیر استفاده می‌کنم:

فرض می‌کنیم که مجموعه داده‌ای داریم که شامل هر ۷ رکورد هست و همه رکوردهای اون ۲ ویژگی یا خصوصیت A و B رو دارن. (دز این‌جا میتونیم این ویژگی‌ها رو به عنوان طول و عرض در یک صفحه دو بعدی در نظر بگیریم)

رکورد A B
۱ ۱.۰ ۱.۰
۲ ۱.۵ ۲.۰
۳ ۳.۰ ۴.۰
۴ ۵.۰ ۷.۰
۵ ۳.۵ ۵.۰
۶ ۴.۵ ۵.۰
۷ ۳.۵ ۴.۵

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

رکورد مختصات
خوشه ۱ ۱ (۱.۰ و ۱.۰)
خوشه ۲ ۴ (۷.۰ و ۵.۰)

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

خوشه ۱ خوشه ۲
گام رکورد مرکز خوشه رکورد مرکز خوشه
۱ ۱ (۱.۰ و ۱.۰) ۴ (۷.۰ و ۵.۰)
۲ ۱ و ۲ (۱.۵ و ۱.۲) ۴ (۷.۰ و ۵.۰)
۳ ۱ و ۲ و ۳ (۲.۳ و ۱.۸) ۴ (۷.۰ و ۵.۰)
۴ ۱ و ۲ و ۳ (۲.۳ و ۱.۸) ۴ و ۵ (۶.۰ و ۴.۲)
۵ ۱ و ۲ و ۳ (۲.۳ و ۱.۸) ۴ و ۵ و ۶ (۵.۷ و ۴.۳)
۶ ۱ و ۲ و ۳ (۲.۳ و ۱.۸) ۴ و ۵ و ۶ و ۷ (۵.۴ و ۴.۱)

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

رکورد مرکز خوشه
خوشه ۱ ۱ و ۲ و ۳ (۲.۳ و ۱.۸)
خوشه ۲ ۴ و ۵ و ۶ و ۷ (۵.۴ و ۴.۱)

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

رکورد فاصله تا خوشه ۱ فاصله تا خوشه ۲
۱ ۱.۵ ۵.۴
۲ ۰.۴ ۴.۳
۳ ۲.۱ ۱.۸
۴ ۵.۷ ۱.۸
۵ ۳.۲ ۰.۷
۶ ۳.۸ ۰.۶
۷ ۲.۸ ۱.۱

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

رکورد مرکز خوشه
خوشه ۱ ۱ و ۲ خوشه ۱
خوشه ۲ ۳ و ۴ و ۵ و ۶ و ۷ خوشه ۲

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

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

پیاده‌سازی الگوریتم  K-Means به زبان Java

 

import java.util.ArrayList;
public class KMeans_Ex {
    private static final int NUM_CLUSTERS = 2;    // Total clusters.
    private static final int TOTAL_DATA = 7;      // Total data points.
    private static final double SAMPLES[][] = new double[][]{{1.0, 1.0},
            {1.5, 2.0},
            {3.0, 4.0},
            {5.0, 7.0},
            {3.5, 5.0},
            {4.5, 5.0},
            {3.5, 4.5}};
    private static ArrayList    &amp;amp;lt; Data &amp;amp;gt;    dataSet = new ArrayList   &amp;amp;lt; Data &amp;amp;gt;  ();
    private static ArrayList   &amp;amp;lt; Centroid &amp;amp;gt;    centroids = new ArrayList   &amp;amp;lt; Centroid &amp;amp;gt;  ();
    private static void initialize() {
        System.out.println(&amp;quot;Centroids initialized at:&amp;quot;);
        centroids.add(new Centroid(1.0, 1.0)); // lowest set.
        centroids.add(new Centroid(5.0, 7.0)); // highest set.
        System.out.println(&amp;quot;     (&amp;quot; + centroids.get(0).X() + &amp;quot;, &amp;quot; + centroids.get(0).Y() + &amp;quot;)&amp;quot;);
        System.out.println(&amp;quot;     (&amp;quot; + centroids.get(1).X() + &amp;quot;, &amp;quot; + centroids.get(1).Y() + &amp;quot;)&amp;quot;);
        System.out.print(&amp;quot;\n&amp;quot;);
        return;
    }
    private static void kMeanCluster() {
        final double bigNumber = Math.pow(10, 10);    // some big number that's sure to be larger than our data range.
        double minimum = bigNumber;                   // The minimum value to beat.
        double distance = 0.0;                        // The current minimum value.
        int sampleNumber = 0;
        int cluster = 0;
        boolean isStillMoving = true;
        Data newData = null;
        // Add in new data, one at a time, recalculating centroids with each new one.
        while (dataSet.size()  &amp;amp;lt;  TOTAL_DATA) {
            newData = new Data(SAMPLES[sampleNumber][0], SAMPLES[sampleNumber][1]);
            dataSet.add(newData);
            minimum = bigNumber;
            for (int i = 0; i  &amp;amp;lt;  NUM_CLUSTERS; i++) {
                distance = dist(newData, centroids.get(i));
                if (distance &amp;amp;lt; minimum) {
                    minimum = distance;
                    cluster = i;
                }
            }
            newData.cluster(cluster);
            // calculate new centroids.
            for (int i = 0; i  &amp;amp;lt;  NUM_CLUSTERS; i++) {
                int totalX = 0;
                int totalY = 0;
                int totalInCluster = 0;
                for (int j = 0; j   &amp;amp;lt; dataSet.size(); j++) { if (dataSet.get(j).cluster() == i) { totalX += dataSet.get(j).X(); totalY += dataSet.get(j).Y(); totalInCluster++; } } if (totalInCluster &amp;amp;gt;    0) {
                    centroids.get(i).X(totalX / totalInCluster);
                    centroids.get(i).Y(totalY / totalInCluster);
                }
            }
            sampleNumber++;
        }
        // Now, keep shifting centroids until equilibrium occurs.
        while (isStillMoving) {
            // calculate new centroids.
            for (int i = 0; i  &amp;amp;lt;  NUM_CLUSTERS; i++) {
                int totalX = 0;
                int totalY = 0;
                int totalInCluster = 0;
                for (int j = 0; j   &amp;amp;lt; dataSet.size(); j++) { if (dataSet.get(j).cluster() == i) { totalX += dataSet.get(j).X(); totalY += dataSet.get(j).Y(); totalInCluster++; } } if (totalInCluster &amp;amp;gt;   0) {
                    centroids.get(i).X(totalX / totalInCluster);
                    centroids.get(i).Y(totalY / totalInCluster);
                }
            }
            // Assign all data to the new centroids
            isStillMoving = false;
            for (int i = 0; i   &amp;amp;lt;   dataSet.size(); i++) {
                Data tempData = dataSet.get(i);
                minimum = bigNumber;
                for (int j = 0; j   &amp;amp;lt;   NUM_CLUSTERS; j++) {
                    distance = dist(tempData, centroids.get(j));
                    if (distance   &amp;amp;lt;   minimum) {
                        minimum = distance;
                        cluster = j;
                    }
                }
                tempData.cluster(cluster);
                if (tempData.cluster() != cluster) {
                    tempData.cluster(cluster);
                    isStillMoving = true;
                }
            }
        }
        return;
    }
    /**
     * // Calculate Euclidean distance.
     *
     * @param d - Data object.
     * @param c - Centroid object.
     * @return - double value.
     */
    private static double dist(Data d, Centroid c) {
        return Math.sqrt(Math.pow((c.Y() - d.Y()), 2) + Math.pow((c.X() - d.X()), 2));
    }
    private static class Data {
        private double mX = 0;
        private double mY = 0;
        private int mCluster = 0;
        public Data() {
            return;
        }
        public Data(double x, double y) {
            this.X(x);
            this.Y(y);
            return;
        }
        public void X(double x) {
            this.mX = x;
            return;
        }
        public double X() {
            return this.mX;
        }
        public void Y(double y) {
            this.mY = y;
            return;
        }
        public double Y() {
            return this.mY;
        }
        public void cluster(int clusterNumber) {
            this.mCluster = clusterNumber;
            return;
        }
        public int cluster() {
            return this.mCluster;
        }
    }
    private static class Centroid {
        private double mX = 0.0;
        private double mY = 0.0;
        public Centroid() {
            return;
        }
        public Centroid(double newX, double newY) {
            this.mX = newX;
            this.mY = newY;
            return;
        }
        public void X(double newX) {
            this.mX = newX;
            return;
        }
        public double X() {
            return this.mX;
        }
        public void Y(double newY) {
            this.mY = newY;
            return;
        }
        public double Y() {
            return this.mY;
        }
    }
    public static void main(String[] args) {
        initialize();
        kMeanCluster();
        // Print out clustering results.
        for (int i = 0; i    &amp;amp;lt;    NUM_CLUSTERS; i++) {
            System.out.println(&amp;quot;Cluster &amp;quot; + i + &amp;quot; includes:&amp;quot;);
            for (int j = 0; j    &amp;amp;lt;    TOTAL_DATA; j++) {
                if (dataSet.get(j).cluster() == i) {
                    System.out.println(&amp;quot;     (&amp;quot; + dataSet.get(j).X() + &amp;quot;, &amp;quot; + dataSet.get(j).Y() + &amp;quot;)&amp;quot;);
                }
            } // j
            System.out.println();
        } // i
        // Print out centroid results.
        System.out.println(&amp;quot;Centroids finalized at:&amp;quot;);
        for (int i = 0; i    &amp;amp;lt;    NUM_CLUSTERS; i++) {
            System.out.println(&amp;quot;     (&amp;quot; + centroids.get(i).X() + &amp;quot;, &amp;quot; + centroids.get(i).Y() + &amp;quot;)&amp;quot;);
        }
        System.out.print(&amp;quot;\n&amp;quot;);
        return;
    }

 

پیاده‌سازی الگوریتم K-Means به زبانPython

 

import math
NUM_CLUSTERS = 2
TOTAL_DATA = 7
LOWEST_SAMPLE_POINT = 0  # element 0 of SAMPLES.
HIGHEST_SAMPLE_POINT = 3  # element 3 of SAMPLES.
BIG_NUMBER = math.pow(10, 10)
SAMPLES = [[1.0, 1.0], [1.5, 2.0], [3.0, 4.0], [5.0, 7.0], [3.5, 5.0], [4.5, 5.0], [3.5, 4.5]]
data = []
centroids = []
class DataPoint:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def set_x(self, x):
        self.x = x
    def get_x(self):
        return self.x
    def set_y(self, y):
        self.y = y
    def get_y(self):
        return self.y
    def set_cluster(self, clusterNumber):
        self.clusterNumber = clusterNumber
    def get_cluster(self):
        return self.clusterNumber
class Centroid:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def set_x(self, x):
        self.x = x
    def get_x(self):
        return self.x
    def set_y(self, y):
        self.y = y
    def get_y(self):
        return self.y
def initialize_centroids():
    # Set the centoid coordinates to match the data points furthest from each other.
    # In this example, (1.0, 1.0) and (5.0, 7.0)
    centroids.append(Centroid(SAMPLES[LOWEST_SAMPLE_POINT][0], SAMPLES[LOWEST_SAMPLE_POINT][1]))
    centroids.append(Centroid(SAMPLES[HIGHEST_SAMPLE_POINT][0], SAMPLES[HIGHEST_SAMPLE_POINT][1]))
    print(&amp;quot;Centroids initialized at:&amp;quot;)
    print(&amp;quot;(&amp;quot;, centroids[0].get_x(), &amp;quot;, &amp;quot;, centroids[0].get_y(), &amp;quot;)&amp;quot;)
    print(&amp;quot;(&amp;quot;, centroids[1].get_x(), &amp;quot;, &amp;quot;, centroids[1].get_y(), &amp;quot;)&amp;quot;)
    print()
    return
def initialize_datapoints():
    # DataPoint objects' x and y values are taken from the SAMPLE array.
    # The DataPoints associated with LOWEST_SAMPLE_POINT and HIGHEST_SAMPLE_POINT are initially
    # assigned to the clusters matching the LOWEST_SAMPLE_POINT and HIGHEST_SAMPLE_POINT centroids.
    for i in range(TOTAL_DATA):
        newPoint = DataPoint(SAMPLES[i][0], SAMPLES[i][1])
        if (i == LOWEST_SAMPLE_POINT):
            newPoint.set_cluster(0)
        elif (i == HIGHEST_SAMPLE_POINT):
            newPoint.set_cluster(1)
        else:
            newPoint.set_cluster(None)
        data.append(newPoint)
    return
def get_distance(dataPointX, dataPointY, centroidX, centroidY):
    # Calculate Euclidean distance.
    return math.sqrt(math.pow((centroidY - dataPointY), 2) + math.pow((centroidX - dataPointX), 2))
def recalculate_centroids():
    totalX = 0
    totalY = 0
    totalInCluster = 0
    for j in range(NUM_CLUSTERS):
        for k in range(len(data)):
            if (data[k].get_cluster() == j):
                totalX += data[k].get_x()
                totalY += data[k].get_y()
                totalInCluster += 1
        if (totalInCluster    &amp;gt;     0):
            centroids[j].set_x(totalX / totalInCluster)
            centroids[j].set_y(totalY / totalInCluster)
    return
def update_clusters():
    isStillMoving = 0
    for i in range(TOTAL_DATA):
        bestMinimum = BIG_NUMBER
        currentCluster = 0
        for j in range(NUM_CLUSTERS):
            distance = get_distance(data[i].get_x(), data[i].get_y(), centroids[j].get_x(), centroids[j].get_y())
            if (distance     &amp;lt;     bestMinimum):
                bestMinimum = distance
                currentCluster = j
        data[i].set_cluster(currentCluster)
        if (data[i].get_cluster() is None or data[i].get_cluster() != currentCluster):
            data[i].set_cluster(currentCluster)
            isStillMoving = 1
    return isStillMoving
def perform_kmeans():
    isStillMoving = 1
    initialize_centroids()
    initialize_datapoints()
    while (isStillMoving):
        recalculate_centroids()
        isStillMoving = update_clusters()
    return
def print_results():
    for i in range(NUM_CLUSTERS):
        print(&amp;quot;Cluster &amp;quot;, i, &amp;quot; includes:&amp;quot;)
        for j in range(TOTAL_DATA):
            if (data[j].get_cluster() == i):
                print(&amp;quot;(&amp;quot;, data[j].get_x(), &amp;quot;, &amp;quot;, data[j].get_y(), &amp;quot;)&amp;quot;)
        print()
    return
perform_kmeans()
print_results()

 

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

این برنامه در سایت گیتلب قابل دسترس هست و شما می‌تونید اون رو تغییر بدین و بهترش کنید.

 

پیاده‌سازی الگوریتم KMEANS به زبان JAVA در گیتلب

پیاده‌سازی الگوریتم KMEANS به زبان PYTHON در گیتلب

منبع

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

سیستم ایمنی بدن انسان

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

خطوط دفاعی بدن انسان

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

 

سیستم تطبیقی بدن انسان

سیستم تطبیقی بدن انسان

 

سیستم ایمنی تطبیقی از دو نوع سلول به نام های سلول B و سلول T تشکیل شده است. سطح این سلول ها از پروتئین های آنتی بادی پوشیده شده است. بر روی تمام سلول های دیگر بدن پروتئین های آنتی ژن وجود دارد.آنتی بادی ها با آنتی ژن ها واکنش شیمیایی می دهند و می توانند به هم متصل شوند.

سیستم ایمنی تطبیقی به دو دسته عمده تقسیم می شود : ایمنی همورال و ایمنی با واسطه سلولی.
هریک از این انواع ایمنی تطبیقی ، بوسیله سلول ها و مولکول های متفاوتی اداره می شوند و به ترتیب برای دفاع در برابر میکروب های خارج سلولی و داخل سلولی طراحی شده اند.ایمنی همورال ، با استفاده از پروتئین هایی که آنتی بادی هستند و بوسیله سلول های B ساخته می شوند ، نقش خود را ایفاء می کنند.آنتی بادی ها به درون سیستم گردش خون و ترشحات مخاطی ترشح می شوند و میکروب ها و سموم میکروبی را که به خون و حفرات اندام های مخاطی مانند
مجاری تنفسی و روده ای راه یافته اند را حذف و خنثی می نمایند. یکی از مهمترین وظایف آنتی بادی ها ، مهار دسترسی و متمرکز شدن میکروب هایی است که از سطوح مخاطی و و خون به سلول های میزبان و بافت های همبند حمله ور می شوند.بدین ترتیب آنتی بادی ها از استقرار و ادامه عفونت جلوگیری می نمایند. آنتی بادی ها به به میکروب هایی که درون سلول آلوده وجود دارند و تکثیر می شوند دستیابی ندارند. این مشکل میکروب های درون سلولی توسط ایمنی با واسطه سلولی برطرف می شود. این ایمنی با واسطه سلول های T بوجود می آید.برخی از سلول های T ، سلول های بیگانه خوار را برای از بین بردن میکروب هایی که بوسیله سلول ها بلعیده شده اند را فعال می کند. سلول های بیگانه خوار در اصل گلبول های سفید خون هستند که سلول های تصویر بیگانه موجود در بدن را می بلعند. سایر سلول های T هر نوع سلول میزبان دارای میکروب درون سیتوپلاسم را از بین می برند. بنابراین سلول های B و T به ترتیب برای شناسایی اختصاصی آنتی زن های میکروب های خارج سلولی و درون سلولی طراحی شده اند. تفاوت دیگر این دو سلول در این است که سلول های T فقط آنتی ژن های پروتئینی میکروب ها را شناسایی می کنند اما سلول های B قادر هستند انواع متفاوتی از مولکول های میکروبی را شناسایی نمایند.

سلول B

سلول B

 

آشنایی با مفاهیم اولیه سیستم ایمنی بدن انسان

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

 

ارگان های سیستم دفاعی بدن انسان

ارگان های سیستم دفاعی بدن انسان

 

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

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

سلول های B

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

سلول های T

سلول های T دارای نوع های مختلف با عملکردهای متفاوت می باشند.گروهی از سلول های T از طریق واکنش متقابل با سلول های بیگانه خوار تک هسته ای ، به آنها در جهت تخریب عوامل بیماری زای داخل سلولی کمک می کنند.این دسته از سلول های T ، سلول های T کمکی یا TH نامیده می شوند.این گروه از سلول های T می توانند با سلول های B نیز واکنش متقابل داشته و به آنها در جهت تقسیم ، تمایز و تولید آنتی بادی کمک کنند.دسته ای دیگر از سلول هایT وظیفه تخریب آن دسته از سلول های میزبان را که با ویروس یا عوامل بیماری زای داخل سلولی آلوده شده اند را برعهده دارند. این نوع از سلول های T را سلول T کُشنده یا TK می نامند.گروه سوم از سلول های T وظیفه تنظیم پاسخ ایمنی بدن و تعدیل آن پس از برطرف شدن عامل بیماری زا را برعهده دارند.این گروه از سلول های T را سلول T بازدارنده یا TS می نامند.سلول های T در مغز استخوان تولید شده و برای بلوغ و تکامل به تیموس مهاجرت می کنند.سلول های T روی سطح خود دارای مولکول های به عنوان گیرنده هستند که TCR نامیده می شوند.این گیرنده ها با مولکول های دیگری به نام هم گیرنده های TCR، در شناسایی آنتی ژن ها نقش اساسی را ایفا می کنند.

به اجتماع گیرنده ها و هم گیرنده های هر سلول T ، مجموعه TCR گفته می شود. سلول های T در مجموعه TCR متفاوت هستند. به عنوان مثال هم گیرنده های سلول های T کمکی از نوع CD4+ و هم گیرنده های سلول های T کُشنده از نوع CD8+ می باشند. نوع سلول T ، در تیموس و در خلال فرآیندهای انتخاب مشخص می شود. بنابراین یک سلول T هنگامی بالغ است که هم گیرنده آن مشخص شده باشد.گیرنده های TCR ، پیش از بلوغ روی سلول های T قراردارند ولی هم گیرنده آن طی فرآیند بلوغ مشخص می شود.

 

عملکرد سلول T

عملکرد سلول T

آنتی بادی

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

آنتی ژن

کلمه آنتی ژن به معنی تولید کننده آنتی بادی است. هر مولکولی که به صورت اختصاصی توسط اجزای سیستم ایمنی مانند سلول های B و T و یا هردو شناسایی شود آنتی ژن محسوب می شود.

انواع مرگ سلول

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

پاکسازی سلول های مرده

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

به عنوان یک قانون کلی که در مقالهOptimum population size and mutation rate for a simple real genetic algorithm that optimizes array factors  به آن اشاره شده (لینک مقاله در انتها آورده شده) اندازه جمعیت به تعداد ژن ها بستگی دارد. بنابراین ۹ ژن  به ۱۶ کروموزوم نیاز دارد و ۱۶ ژن به ۳۲ کروموزوم. معمولا با انتخاب اندازه حمعیتی معادل با ۱٫۵ تا ۲ برابر تعداد ژن ها شروع می شود تا به ماکزیمم اندازه جمعیت ۱۰۰ برسیم.

برای فضاهای حالت پیچیده احتمال crossover بالاتر (بیش از ۰٫۵) به جستجو در ابتدای کار کمک می کند. با این وجود در ادامه باید به مقادیری نزدیک به ۰٫۱ یا ۰٫۲ کاهش یابد. احتمال میوتیشن باید پایین نگه داشته شود (۰٫۰۱ – ۰٫۱). در غیر اینصورت همگرایی بی دلیل به تعویق می افتد.

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

ولی به عنوان یک قانون کلی:

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

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

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

به این صورت عمل شده است که از آنجایی که تعداد ژن ها برابر با ۸ است ابتدا از ۱٫۵ برابر آن یعنی ۱۲ شروع شده است. یعنی مقدار جمعیت برای بار اول برابر با ۱۲ قرار داده شده است. تعداد نسل ها برابر با تعداد تکرار است. تعداد نسل را نصف تعداد جمعیت قرار می دهیم و از احتمال میویتش ۰٫۰۱ و احتمال crossover 0.5 استفاده می کنیم. لینک دانلود مرجع کد برنامه در انتها آورده شده است.

همان طور که مشاهده می شود نتیجه خوب نیست

تغییر تعداد جمعیت به دو برابر تعداد ژن ها:

هنوز به فیتنس ۲۸ یعنی تعداد برخوردهای ۰ نرسیده ایم.

در محله بعدی تکرار افزایش می یابد:

حال برای مقایسه مقدار crossover افزایش می یابد:

در این حالت هم به global maximum نرسیدیم و در دام بهینه محلی افتادیم.

مقدار crossover را مجددا کمتر کرده و مقدار میوتیشن را کمی افزایش می دهم:

نتیجه بدتر شد. مجددا به حالت قبل بر می گردانیم:

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

در مرحله بعد تعداد جمعیت را به ۲۰ افزایش میدهیم:

نتیجه تغییر چندانی ندارد.

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

به نظر می رسد تعداد جمعیت باید تغییر زیادی داشته باشد تا نتیجه بیشتر تغییر کند:

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

حال می توان میتویشن و crossover را تغییر داد:

کاهش crossover در این حالت نتیجه را خراب کرد

در حالت فوق میوتیشن کمی افزایش داده شد

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

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

در تصویر فوق مشاهده می شود که به علت قرار گیری عدد بزرگ در crossover به هیچ وجه همگرا نمی شود

تا کنون بهترین حالتی که مشاهده شد تصویر فوق است. که با در نظر گرفتن جمعیت نرمال ۱۰۰ ، تعداد تکرار نصف جمعیت یعنی ۵۰ و مقدار احتمال میوتیشن ۰,۰۱ و crossover برابر با ۰٫۰۷ به ۶ جواب بهینه رسیدیم. یعنی ۶ کروموزومی پیدا شدند که فیتنس ۲۸ و ماکزیمم دارند.

اجرای ۸ وزیر در متلب:

در کد زیر که با الهام از الگوریتم تپه نوردی نوشته شده پس از اجرا برای جمعیت برابر با ۱۰۰۰ و تعداد تکراری برابر با ۱۰۰ به ۲۰ جواب بهینه رسیدیم. در اینجا نیز تنظیم پارامترها دست شما است و می توان به جواب بهتری رسید


pop=1000;                                         %total population always

gen=100;                                           %total generations

n=8;

max_fitness=(((n-1)*n)/2);

initpop=zeros(pop,n);                            %initial population

pop_fitness=zeros(pop,1);                        %population fitness matrix

pop_fitness_sorted=zeros(pop,1);                 %for sorted fitness

fitness_temp=0;                                  %fitness temporary variable used in fitness loops between k and j

actual_pop_temp=zeros(1,n);

actual_pop_sorted=zeros(pop,n);

z=0;                                             %temporary variable used for simplicity

s=1;

w=0;

solution=zeros(1000,n);                           % solution matrix

cross_over_temp_mat=zeros(pop/2,n);              %cross-over variables

cross_over_ready_pop=zeros(pop,n);

cross_over_pop_final=zeros(pop,n);

cross_over_point=0;

cross_over_pop_temp_one=zeros(1,n);

cross_over_pop_temp_two=zeros(1,n);

cross_over_pop_temp_adjust=0;

cross_over_child_two_flipped=zeros(1,n);

cross_over_child_one=zeros(1,n);

cross_over_child_two=zeros(1,n);

mutation_temp_one=0;                             %mutation variables

mutation_temp_two=0;

mutation_temp_data=0;

for i=1:pop

initpop(i,:)=randperm(n);   %random initial population –indicates queen position on board

end;

actual_pop=initpop;                                 %duplication for working on this variable and keeping initial population intact

%generations loop

for q=1:gen

%for one generation

for i = 1:pop

fitness_temp=0;

%fitness calculation loop

for k=1:(n-1)                                               %calculates fitness by position manipulation

for j=k+1:n                                         %queen movements have been covered using j and k manipulation

z=abs(actual_pop(i,k)-actual_pop(i,j));          % for example   : when one queen is at (3,1)–(row,column)

if (ne(z,0)&amp;amp;&amp;amp; ne(z,(j-k)))                      %                next queens cant be at {(2,2),(3,2),(4,2) } {(1,3),(3,3),(5,3)}

fitness_temp=fitness_temp+1;               %                now you can observe that subtraction of each queen position and next

end                                             %                column queen position tells us a lot of information.

end                                                 %                remember the actual pop contains queen position dont confuse them with ‘i’ &amp;amp; ‘j’

end

pop_fitness(i,1)=fitness_temp;

end

%sort for individuals with good fitness

pop_fitness_sorted=pop_fitness;

actual_pop_sorted=actual_pop;

for i=1:(pop-1)

for j=i+1:pop

if(pop_fitness_sorted(i,1)&amp;lt;pop_fitness_sorted(j,1))

fitness_temp=pop_fitness_sorted(i,1);

pop_fitness_sorted(i,1)=pop_fitness_sorted(j,1);

pop_fitness_sorted(j,1)=fitness_temp;

actual_pop_temp(1,:)=actual_pop_sorted(i,:);

actual_pop_sorted(i,:)=actual_pop_sorted(j,:);

actual_pop_sorted(j,:)=actual_pop_temp(1,:);

end

end

end

% for unique solution gathering

%specified a vector of 100 rows ‘n’ columns

for i=1:pop

if(pop_fitness_sorted(i,1)==max_fitness)

for j=1:s

if actual_pop_sorted(i,:)==solution(j,:)

w=w+1;

else

w=w;

end

end

if w==0

solution(s,:)=actual_pop_sorted(i,:);

s=s+1;

else

continue;

end

end

w=0;

end

%selection

for i=1:(pop/2)

cross_over_temp_mat(i,:)=actual_pop_sorted(i,:);

end

cross_over_ready_pop=repmat(cross_over_temp_mat,2,1);

cross_over_pop_final=cross_over_ready_pop;

%cross over part begins

%for detail explaination cross over logic refer to the pdf attached

%logic—get random crossover point–then cross over at that point

%if two same values of rows in one individual..then adjust crossover

%according to the logic give in the pdf

while 1,

cross_over_point=floor(n*rand(1));

if cross_over_point~=0

break;

end

end

i=1;

while i&amp;lt;(pop-1),

cross_over_pop_temp_one(1,:)=cross_over_ready_pop(i,:);         %copied parents

cross_over_pop_temp_two(1,:)=cross_over_ready_pop(i+1,:);       %copied parents

%for child one

for j=1:cross_over_point

for k=j:n

if (cross_over_pop_temp_one(1,j)==cross_over_pop_temp_two(1,k))

cross_over_pop_temp_adjust=cross_over_pop_temp_two(1,j);

cross_over_pop_temp_two(1,j)=cross_over_pop_temp_two(1,k);

cross_over_pop_temp_two(1,k)=cross_over_pop_temp_adjust;

break;

end

end

end

for j=1:cross_over_point

cross_over_child_one(1,j)=cross_over_pop_temp_one(1,j);

end

for j=cross_over_point:n

cross_over_child_one(1,j)=cross_over_pop_temp_two(1,j);

end

%for child two

cross_over_pop_temp_two(1,:)=cross_over_ready_pop(i,:);         %copied parents

cross_over_pop_temp_one(1,:)=cross_over_ready_pop(i+1,:);       %copied parents

for j=1:cross_over_point

for k=j:n

if (cross_over_pop_temp_one(1,j)==cross_over_pop_temp_two(1,k))

cross_over_pop_temp_adjust=cross_over_pop_temp_two(1,j);

cross_over_pop_temp_two(1,j)=cross_over_pop_temp_two(1,k);

cross_over_pop_temp_two(1,k)=cross_over_pop_temp_adjust;

break;

end

end

end

for j=1:cross_over_point

cross_over_child_two(1,j)=cross_over_pop_temp_one(1,j);

end

for j=cross_over_point:n

cross_over_child_two(1,j)=cross_over_pop_temp_two(1,j);

end

cross_over_pop_final(i,:)=cross_over_child_one(1,:);

cross_over_child_two_flipped=wrev(cross_over_child_two);                 %flipped

cross_over_pop_final(i+1,:)=cross_over_child_two_flipped(1,:);

i=i+2;

end

%mutation introduced

%mutation occours  :at every 5th individual..swapping of two random

%                   column values(that is queen positions)

i=5;

while i&amp;lt;pop,

mutation_temp_one=floor(rand(1)*n/2);

mutation_temp_two=floor(2*(rand(1)*n/2));

if (mutation_temp_one==0 || mutation_temp_two==0)

continue;

else

mutation_temp_data=cross_over_pop_final(i,mutation_temp_one);

cross_over_pop_final(i,mutation_temp_one)=cross_over_pop_final(i,mutation_temp_two);

cross_over_pop_final(i,mutation_temp_two)=mutation_temp_data;

end

i=i+5;

end

i=0;

actual_pop=cross_over_pop_final;%the most important statement for my code

end

f=figure(‘Position’,[50 100 1000 600]);

cnames = {‘1′,’2′,’3′,’4′,’5′,’6′,’7′,’8′,’9′,’10’,’11’,’12’};

rnames = {‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’};

t = uitable(‘Parent’,f,’Data’,solution,’ColumnName’,cnames,…

‘RowName’,rnames,’Position’,[10 100 1000 500]);

 
 

با تغییر جمعیت به ۱۰۰ و تکرار به ۵۰:

به ۳ جواب بهینه رسیدیم:

با اجرای کد زیر ۹۲ کروموزوم به عنوان خروجی برگردانده می شود یعنی ۸ وزیر ۹۲ جواب دارد که ۱۲ جواب آن منحصر به‌فرد است یعنی بقیه جواب‌ها از تقارن جواب‌های اصلی به‌دست می‌آید.


function queen

clc;

counter = 0;

n = 8;

board = zeros(1,n);

[board,counter] = back(1, board,counter);

fprintf(‘Solution count: %d\n’,counter);

%%

function value =  isSolution(board)

for  i = 1:length(board)

for  j = (i+1): length(board)

if abs(board(i) – board(j)) == abs(i-j)

value = false;

return;

end

end

end

value = true;

%%

function [board,counter] =  back(depth, board,counter)

if  (depth == length(board)+1) &amp;amp;&amp;amp; isSolution(board)

counter = counter + 1;

disp(board);

end

if ( depth &amp;lt;= length(board))

for  i = 1:length(board)

if ~any(board==i)

board(1,depth) = i;

[~,counter] = back(depth+1, board,counter);

end

end

end

 

بخشی از جواب ها بصورت زیر است:

۱     ۵     ۸     ۶     ۳     ۷     ۲     ۴

۱     ۶     ۸     ۳     ۷     ۴     ۲     ۵

۱     ۷     ۴     ۶     ۸     ۲     ۵     ۳

۱     ۷     ۵     ۸     ۲     ۴     ۶     ۳

۲     ۴     ۶     ۸     ۳     ۱     ۷     ۵

۲     ۷     ۵     ۸     ۱     ۴     ۶     ۳

۲     ۸     ۶     ۱     ۳     ۵     ۷     ۴

۳     ۱     ۷     ۵     ۸     ۲     ۴     ۶

۳     ۵     ۲     ۸     ۱     ۷     ۴     ۶

۳     ۵     ۲     ۸     ۶     ۴     ۷     ۱

۳     ۵     ۷     ۱     ۴     ۲     ۸     ۶

۳     ۵     ۸     ۴     ۱     ۷     ۲     ۶

۳     ۶     ۲     ۵     ۸     ۱     ۷     ۴

۳     ۶     ۲     ۷     ۱     ۴     ۸     ۵

۳     ۶     ۲     ۷     ۵     ۱     ۸     ۴

۳     ۶     ۴     ۱     ۸     ۵     ۷     ۲

۳     ۶     ۴     ۲     ۸     ۵     ۷     ۱

۳     ۶     ۸     ۱     ۴     ۷     ۵     ۲

۳     ۶     ۸     ۱     ۵     ۷     ۲     ۴

۳     ۶     ۸     ۲     ۴     ۱     ۷     ۵

۳     ۷     ۲     ۸     ۵     ۱     ۴

Solution count: 92

منبع

مسئله چند وزیر قسمت 1
مسئله چند وزیر قسمت 2
مسئله چند وزیر قسمت 3
مسئله چند وزیر قسمت 4

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

  • نحوه نمایش مسئله:

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

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

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

۸ , ۷ , ۶ , ۵ , ۴ , ۳ , ۲ , ۱

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

  • تولید جمعیت اولیه:

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

برای محاسبه میزان بهینگی جواب تعداد جفت وزیرهایی را که به هم گارد می‌دهند، محاسبه می‌کنیم. برای مسئله ۸ وزیر در بدترین حالت هر وزیر با همه وزیرهای دیگر گارد می‌دهد (فرض کنید همه وزیرها در یک سطر قرار گیرند). در این حالت حداکثر تعداد جفت وزیرهایی که به همگدیکر کارد می‌دهند ۲۸ جفت است:

۷ + ۶ + ۵ + ۴ +۳ + ۲ + ۱

در حالت کلی برای مسئله n وزیر حداکثر تعداد جفت وزیرهایی که به همدیگر گارد می‌دهند به صورت زیر محاسبه می‌شود:

۱+ ۲ +.. +(n-۱) = (n * (n-۱)) /۲
  • برای محاسبه میزان بهینگی هر کروموزوم از فرمول زیر استفاده می‌کنیم:
Fitness[i] =1 – (Guard(chromosome[i])) / MaxGuards
  • حداکثر تعداد گاردها:
MaxGuards
  • تعداد جفت وزیرهایی که در کروموزوم ام همدیگر را گارد می‌دهند:
 Guard(chromosome[i])

 

منبع

 


پیاده سازی الگوریتم ۸ وزیر با استفاده از الگوریتم ژنتیک

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

یک الگوریتم GA دارای پارامترهای زیر است:

  • : Fitnessتابعی برای ارزیابی یک فرضیه  که مقداری عددی به هر فرضیه نسبت میدهد
  • : Fitness_threshold مقدار آستانه که شرط پایان را معین میکند
  • : population تعداد فرضیه هائی که باید در جمعیت در نظر گرفته شوند
  • : crossover rate  در صدی از جمعیت که در هر مرحله توسط الگوریتم crossover  جایگزین میشوند
  • :mutation rate  نرخ mutation

الگوریتم GA  به صورت زیر کار می کند:

  • : Initializeجمعیت را با تعداد population فرضیه بطور تصادفی مقدار دهی اولیه کنید.
  • : Evaluateبرای هر فرضیه h در population مقدار تابع Fitness(h) را محاسبه نمائید.
  • تا زمانیکه[maxh Fitness(h)] < Fitness_threshold یک جمعیت جدید ایجاد  کنید.
  • فرضیه ای که دارای بیشترین مقدار Fitness است را برگردانید.

روش های مختلف crossover:

Single-point crossover

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

روشهای دیگر Crossover

در crossover یکنواخت بیتها بصورت یکنواخت از والدین انتخاب می شوند.

اپراتورهای ژنتیکی Mutation :

  • اپراتور mutation برای بوجود آوردن فرزند فقط از یک والد استفاده میکند. اینکار با انجام تغییرات کوچکی در رشته اولیه  بوقوع میپیوندد.
  • با استفاده از یک توزیع یکنواخت یک بیت بصورت تصادفی اتنخاب و مقدار آن تغییر پیدا میکند.
  • معمولا mutation بعد از انجام crossover اعمال میشود.

تابع fitness  معیاری برای رتبه بندی فرضیه هاست که کمک میکند تا فرضیه های برتر برای نسل بعدی جمعیت انتخاب شوند. نحوه انتخاب این تابع بسته به کاربر مورد نظر دارد

در روش معرفی شده در الگوریتم ساده GA احتمال انتخاب یک فرضیه برای استفاده در جمعیت بعدی بستگی به نسبت fitness  آن به fitness  بقیه اعضا دارد. این روش Roulette Wheel selectionنامیده میشود.

روش جستجوی GA با روشهای دیگر مثل شبکه های عصبی تفاوت دارد:

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

مسئله ۸ وزیر:

بدین ترتیب دیدیم که مسیر میان اجزای الگوریتم ژنتیک به ترتیب زیر است:

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

ژن عددی از ۰ تا n-1 است در ۸ وزیر n برابر با ۸ است بنابراین ژن عددی از ۰ تا ۷ می شود و کروموزوم آرایه ای از ژن هاست. که می تواند پاسخ مسئله باشد.

جمعیت هر نسل می تواند  تعداد کروموزوم ها را تعیین کند.

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

برای پیدا کردن هزینه مربوط به هر کروموزوم یک تابع هزینه تعریف می شود. نتیجه تابع هزینه یک cost value است که در نهایت میانگین cost valueهای هر نسل به نتیجه مطلوب نزدیک می شود.

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

در فرایند cross over فرزندان توسط والدین تولید می شوند که ترکیب آنها شامل ترکیب ژن های آنهاست. اگر نسل جدید حاوی کروموزومی باشد که نزدیک یا برابر با نتایج مطلوب باشد آنگاه مسئله حل شده است. در غیر اینصورت فرایند قبلی در نسل جدید هم پیاده سازی می شود مانند فرایندی که برای والدین آنها اتفاق افتاد. تا زمانی که به راه حل مناسب برسیم این روال ادامه دارد.

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

برای تولید فرزندان از والیدن نیاز به crossover داریم که تصمیم می گیرد از دو والدین کدام ژن باید انتخاب شود.

 

مسئله چند وزیر قسمت 1
مسئله چند وزیر قسمت 2
مسئله چند وزیر قسمت 3
مسئله چند وزیر قسمت 4

1.A GABOR FILTER TEXTURE ANALYSIS APPROACH FOR HISTOPATHOLOGICAL BRAIN TUMOUR SUBTYPE DISCRIMINATION

Abstract Meningioma brain tumour discrimination is challenging as many histological patterns are mixed between the different subtypes. In clinical practice, dominant patterns are investigated for signs of specific meningioma pathology; however the simple observation could result in inter- and intra-observer variation due to the complexity of the histopathological patterns. Also employing a computerised feature extraction approach applied at a single resolution scale might not suffice in accurately delineating the mixture of histopathological patterns. In this work we propose a novel multiresolution feature extraction approach for characterising the textural properties of the different pathological patterns (i.e. mainly cell nuclei shape, orientation and spatial arrangement within the cytoplasm). The patterns’ textural properties are characterised at various scales and orientations for an improved separability between the different extracted features. The Gabor filter energy output of each magnitude response was combined with four other fixed-resolution texture signatures (2 model-based and 2 statistical-based) with and without cell nuclei segmentation. The highest classification accuracy of 95% was reported when combining the Gabor filters’ energy and the meningioma subimage fractal signature as a feature vector without performing any prior cell nuceli segmentation. This indicates that characterising the cell-nuclei self-similarity properties via Gabor filters can assists in achieving an improved meningioma subtype classification, which can assist in overcoming variations in reported diagnosis.
Keywords – texture analysis, Gabor filter, fractal dimension, meningioma histopathology, brain tumours

فایل PDF – در 14 صفحه- نویسنده : Omar Sultan Al-Kadi

A GABOR FILTER TEXTURE ANALYSIS APPROACH FOR HISTOPATHOLOGICAL BRAIN TUMOUR SUBTYPE DISCRIMINATION

پسورد فایل : behsanandish.com


2.A Review Paper on Gabor Filter Algorithm & Its Applications

Abstract— In applications of image analysis and computer vision, Gabor filters have maintained their popularity in feature extraction. The reason behind this is that the resemblance between Gabor filter and receptive field of simple cells in visual cortex. Being successful in applications like face detection, iris recognition, fingerprint matching; where, Gabor feature based processes are amongst the best performers. The Gabor features can be derived by applying signal processing techniques both in time and frequency domain. The models like human preattentive texture perception have been proposed which involves steps like convolution, inhibition and texture boundary detection. Texture features are based on the local power spectrum obtained by a bank of Gabor filters. The concept of sparseness to generate novel contextual multiresolution texture descriptors are described. In this paper we present the detailed study about the Gabor filter and its application.
Index Terms— Gabor filter, Gabor energy, image quality assessment, Gabor features, multiresolution techniques, segmentation, textured images..

فایل PDF – در 5 صفحه- نویسنده : Neelu Arora , Mrs. G. Sarvani

A Review Paper on Gabor Filter Algorithm & Its Applications

پسورد فایل : behsanandish.com


3.Comparison of texture features based on Gabor filters

 

Abstract -The performance of a number of texture feature operators is evaluated. The features are all based on the local spectrum which is obtained by a bank of Gabor filters. The comparison is made using a quantitative method which is based on Fisher’s criterion. It is shown that, in general, the discrimination effectiveness of the features increases with the amount of post-Gabor processing.

فایل PDF – در 6 صفحه- نویسنده : P. Kruizinga, N. Petkov and S.E. Grigorescu

Comparison of texture features based on Gabor filters

پسورد فایل : behsanandish.com


4.Evolutionary Gabor Filter Optimization with Application to Vehicle Detection

 

Abstract—Despite the considerable amount of research work on the application of Gabor filters in pattern classification, their design and selection have been mostly done on a trial and error basis. Existing techniques are either only suitable for a small number of filters or less problem-oriented. A systematic and general evolutionary Gabor filter optimization (EGFO) approach that yields a more optimal, problem-specific, set of filters is proposed in this study. The EGFO approach unifies filter design with filter selection by integrating Genetic Algorithms (GAs) with an incremental clustering approach. Specifically, filter design is performed using GAs, a global optimization approach that encodes the parameters of the Gabor filters in a chromosome and uses genetic operators to optimize them. Filter selection is performed by grouping together filters having similar characteristics (i.e., similar parameters) using incremental clustering in the parameter space. Each group of filters is represented by a single filter whose parameters correspond to the average parameters of the filters in the group. This step eliminates redundant filters, leading to a compact, optimized set of filters. The average filters are evaluated using an application-oriented fitness criterion based on Support Vector Machines (SVMs). To demonstrate the effectiveness of the proposed framework, we have considered the challenging problem of vehicle detection from gray-scale images. Our experimental results illustrate that the set of Gabor filters, specifically optimized for the problem of vehicle detection, yield better performance than using traditional filter banks.

 

فایل PDF – در 8 صفحه- نویسنده : Zehang Sun, George Bebis and Ronald Miller

Evolutionary Gabor Filter Optimization with Application to Vehicle Detection

پسورد فایل : behsanandish.com


5.Expression-Invariant Face Recognition via 3D Face Reconstruction Using Gabor Filter Bank from a 2D Single Image

Abstract— In this paper, a novel method for expression- insensitive face recognition is proposed from only a 2D single image in a gallery including any facial expressions. A 3D Generic Elastic Model (3D GEM) is used to reconstruct a 3D model of each human face in the present database using only a single 2D frontal image with/without facial expressions. Then, the rigid parts of the face are extracted from both the texture and reconstructed depth based on 2D facial land-marks. Afterwards, the Gabor filter bank was applied to the extracted rigid-part of the face to extract the feature vectors from both texture and reconstructed depth images. Finally, by combining 2D and 3D feature vectors, the final feature vectors are generated and classified by the Support Vector Machine (SVM). Favorable outcomes were acquired to handle expression changes on the available image database based on the proposed method compared to several state-of-the-arts in expression-insensitive face recognition.

Keywords—Face recognition; 3D shape recovery; Gesture and Behavior Analysis.

 

فایل PDF – در 6 صفحه- نویسنده : Ali Moeini, Hossein Moeini, Karim Faez

Expression-Invariant Face Recognition via 3D Face Reconstruction Using Gabor Filter Bank from a 2D Single Image

پسورد فایل : behsanandish.com


6.IMAGE RETRIEVAL BASED ON HIERARCHICAL GABOR FILTERS

Content Based Image Retrieval (CBIR) is now a widely investigated issue that aims at allowing users of multimedia information systems to automatically retrieve images coherent with a sample image. A way to achieve this goal is the computation of image features such as the color, texture, shape, and position of objects within images, and the use of those features as query terms. We propose to use Gabor filtration properties in order to find such appropriate features. The article presents multichannel Gabor filtering and a hierarchical image representation. Then a salient (characteristic) point detection algorithm is presented so that texture parameters are computed only in a neighborhood of salient points. We use Gabor texture features as image content descriptors and efficiently emply them to retrieve images.
Keywords: Gabor filters, image retrieval, texture feature extraction, hierarchical representation

فایل PDF – در 10 صفحه- نویسنده : TOMASZ ANDRYSIAK, MICHAŁ CHORA´ S

IMAGE RETRIEVAL BASED ON HIERARCHICAL GABOR FILTERS

پسورد فایل : behsanandish.com


7.Iris Recognition Based On Adaptive Gabor Filter

Abstract. Aiming at the problem of multi-category iris recognition, there proposes a method of iris recognition algorithm based on adaptive Gabor filter. Use DE-PSO to adaptive optimize the Gabor filter parameters. DE-PSO is composed of particle swarm optimization and differential evolution algorithm. Use 16 groups of 2D-Gabor filters with different frequencies and directions to process iris images. According to the direction and frequency of maximum response amplitude, transform iris features into 512-bit binary feature encoding. Calculate the Hamming distance of feature code and compare with the classification threshold, determine iris the type of iris. Experiment on a variety of iris databases with multiple Gabor filter algorithms, the results showed that this algorithm has higher recognition rate, the ROC curve is closer to the coordinate axis and the robustness is better, compare with other Gabor filter algorithm.

Keywords: Iris recognition Gabor filter Particle swarm optimization Differential evolutionFeature encodingHamming distance

 

فایل PDF – در 8 صفحه- نویسنده : Shuai Liu, Yuanning Liu, Xiaodong Zhu, Guang Huo, Jingwei Cui, and Yihao Chen

 

Iris Recognition Based On Adaptive Gabor Filter

پسورد فایل : behsanandish.com


8.USE OF GABOR FILTERS FOR TEXTURE CLASSIFICATION OF AIRBORNE IMAGES AND LIDAR DATA

KEY WORDS: Texture analysis, LIDAR, Algorithm, Urban and Vegetation Detection, Automated Classification
ABSTRACT: In this paper, a texture approach is presented for building and vegetation extraction from LIDAR and aerial images. The texture is very important attribute in many image analysis or computer vision applications. The procedures developed for texture problem can be subdivided into four categories: structural approach, statistical approach, model based approach and filter based approach. In this paper, different definitions of texture are described, but complete emphasis is given on filter based methods. Examples of filtering methods are Fourier transform, Gabor and wavelet transforms. Here, Gabor filter is studied and its implementation for texture analysis is explored. This approach is inspired by a multi-channel filtering theory for processing visual information in the human visual system. This theory holds that visual system decomposes the image into a number of filtered images of a specified frequency, amplitude and orientation.  The main objective of the article is to use Gabor filters for automatic urban object and tree detection. The first step is a definition of Gabor filter parameters: frequency, standard deviation and orientation. By varying these parameters, a filter bank is obtained that covers the frequency domain almost completely. These filters are used to aerial images and LIDAR data. The filtered images that possess  a significant information about analyzed objects are selected, and the rest are discarded.  Then, an energy measure is defined on the filtered images in order to compute different texture features. The Gabor features are used to image segmentation using thresholding.  The tests were performed using set of images containing very different landscapes: urban area and vegetation of varying configurations, sizes and shapes of objects. The performed studies revealed that textural algorithms have the ability to detect buildings and trees. This article is the attempt to use texture methods also to LIDAR data, resampling into regular grid cells. The obtained preliminary results are interesting.

 

فایل PDF – در 12 صفحه- نویسنده : Urszula Marmol


USE OF GABOR FILTERS FOR TEXTURE CLASSIFICATION OF AIRBORNE IMAGES AND LIDAR DATA

پسورد فایل : behsanandish.com

 

یادگیری ماشین – SVM یا ماشین بردار پشتیبان به زبان ساده

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

آشنایی با مفهوم دسته بندی

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

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

SVM-1

 

با نگاه به نمودار فوق، حقایق زیر به سادگی قابل مشاهده است :

  1. مردان در این مجموعه، میانگین قد بلندتری دارند.
  2. زنان از میانگین طول موی بیشتری برخوردار هستند.

اگر یک داده جدید با قد ۱۸۰cm و طول موی ۴cm به ما داده شود، بهترین حدس ما برای ماشینی این شخص، دسته مردان خواهد بود .

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

بردارهای پشتیبان به زبان ساده، مجموعه ای از نقاط در فضای n بعدی داده ها هستند که مرز دسته ها را مشخص می کنند و مرزبندی و دسته بندی داده ها براساس آنها انجام می شود و با جابجایی یکی از آنها، خروجی دسته بندی ممکن است تغییر کند . به عنوان مثال در شکل فوق ، بردار (۴۵,۱۵۰) عضوی از بردار پشتیبان و متعلق به یک زن است . در فضای دوبعدی ،‌بردارهای پشتیبان، یک خط، در فضای سه بعدی یک صفحه و در فضای n بعدی یک ابر صفحه را شکل خواهند داد.

SVM یا ماشین بردار پشتیبان ، یک دسته بند یا مرزی است که با معیار قرار دادن بردارهای پشتیبان ، بهترین دسته بندی و تفکیک بین داده ها را برای ما مشخص می کند.

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

چگونه یک ماشین بر مبنای بردارهای پشتیبان ایجاد کنیم ؟

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

 

SVM-2

 

سوال اینجاست که بهترین مرزبندی در این مسأله کدام خط است ؟

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

توزیع غیر خطی داده ها و کاربرد ماشین بردار پشتیبان

اگر داده ها به صورت خطی قابل تفکیک باشند، الگوریتم فوق می تواند بهترین ماشین را برای تفکیک داده ها و تعیین دسته یک رکورد داده، ایجاد کند اما اگر داده ها به صورت خطی توزیع شده باشند (مانند شکل زیر )، SVM را چگونه تعیین کنیم ؟

 

SVM-3

 

در این حالت، ما نیاز داریم داده ها را به کمک یک تابع ریاضی (Kernel functions) به یک فضای دیگر ببریم (نگاشت کنیم ) که در آن فضا، داده ها تفکیک پذیر باشند و بتوان SVM آنها را به راحتی تعیین کرد. تعیین درست این تابع نگاشت در عملکرد ماشین بردار پشتیبان موثر است که در ادامه به صورت مختصر به آن اشاره شده است.

با فرض یافتن تابع تبدیل برای مثال فوق،‌ فضای داده ما به این حالت تبدیل خواهد شد :

 

SVM-4

 

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

نگاهی دقیق تر به فرآیند ساخت SVM

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

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

SVM-5

SVM‌ در پایتون

برای استفاده از ماشین بردار پشتیبان در پایتون، توصیه بنده استفاده از کتابخانه یادگیری ماشین پایتون به نام scikitlearn است که تمام کرنل ها و توابع نگاشت را به صورت آماده شده دارد. سه تا تابعSVC , NuSVC , LinearSVC وظیفه اصلی دسته بندی را برعهده دارند . (SVC = Support Vector Classifier) . نمونه ای از دسته بندی با این توابع را در زیر می توانید مشاهده کنید :

 

SVM-6

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

برای استفاده از SVM در مورد داده های واقعی ، چندین نکته را باید رعایت کنید تا نتایج قابل قبولی را بگیرید

  1. ابتدا داده ها را پالایش کنید (نقاط پرت ،‌ داده های ناموجود و …..)
  2. داده را عددی و نرمال کنید . این مباحث را در مقالات پیش پردازش داده ها دنبال کنید. به طور خلاصه ، داده هایی مانند جنسیت، رشته تحصیلی و … را به عدد تبدیل کنید و سعی کنید مقادیر همه صفات بین یک تا منهای یک [۱,-۱] نرمال شوند تا بزرگ یا کوچک بودن مقادیر یک ویژگی داده ها،‌ ماشین را تحت تاثیر قرار ندهد .
  3. کرنل های مختلف را امتحان و به ازای هر کدام، با توجه به مجموعه داده آموزشی که در اختیار دارید و دسته بندی داده های آنها مشخص است، دقت SVM را اندازه گیری کنید و در صورت نیاز پارامتر های توابع تبدیل را تغییر دهید تا جواب های بهتری بگیرید. این کار را برای کرنل های مختلف هم امتحان کنید . می توانید از کرنل RBF شروع کنید .

نقاط ضعف ماشین بردار پشتیان

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

با این وجود، SVM‌ ها دارای یک شالوده نظری منسجم بوده و جواب های تولید شده توسط آنها ، سراسری و یکتا می باشد. امروزه ماشینهای بردار پشتیبان، به متداول ترین تکنیک های پیش بینی در داده کاوی تبدیل شده اند.

سخن پایانی

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

ساختار اصلی این نوشتار از روی یک مقاله سایت آنالیتیکزویدیا برداشته شده است و برای دو بخش پایانی مقاله هم از کتاب «داده کاوی پیشرفته : مفاهیم و الگوریتم ها» دکتر شهرابی استفاده شده است .

منبع


آشنایی با ماشین بردار پشتیبان (SVM) – مرور کلی

SVM یک مدل یادگیری نظارت شده است.

پس قبل از این که به سراغ آن برویم باید یک مجموعه داده(Dataset) که از قبل برچسب‌گذاری شده(Labeled) را داشته باشیم.

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

من به دنبال راهی هستم که این ایمیل‌ها را هرچه سریع‌تر تشخیص بدهم(پیدا کنم) و پاسخ آن‌ها را زودتر از بقیه ارسال کنم.

رویکرد اولمن می‌توانم برچسب‌هایی با عنوان‌های: اورژانسی، شکایت و راهنمایی در جیمیل(GMail) خود ایجاد کنم.

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

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

قدم اولبه تعدادی ایمیل نیاز دارم.(هرچه بیشتر بهتر)

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

قدم سومروی این مجموعه داده، مدلی را آموزش می‌دهم.

قدم چهارمکیفیت یا صحت پیش‌بینی های مدل آموزش داده‌شده را ارزیابی می‌کنم.(با استفاده از روش Cross Validation)

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

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

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

SVM یک مدل خطی را یاد می‌گیرد

در مثال قبل دیدیم که در قدم سوم یک الگوریتم یادگیری نظارت شده مثل SVM به کمک داده‌هایی که از قبل برچسب‌گذاری شده‌اند آموزشداده شد. اما برای چه چیزی آموزش داده شد؟ برای این که چیزی را یاد بگیرد.

چه چیزی را یاد بگیرد؟

در مورد SVM، یک مدل خطیرا یاد میگیرد.

مدل خطی چیست؟ اگر بخواهیم به زبان ساده بیان کنیم یک خط است.(و در حالت پیچیده‌تر یک ابر صفحه).

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

 

svm

SVM قادر است که خطی را پیدا کند که داده‌ها را جدا می‌کند.

 

خب پس اگر SVM فقط یک خط است، پس چرا ما داریم راجع به مدل خطی صحبت می‌کنیم؟

برای این که ما همینطوری نمی‌توانیم به یک خط چیزی را آموزش بدهیم.

در عوض:

  1. در نظر می‌گیریم که داده‌هایی که می‌خواهیم طبقه‌بندی کنیم، می‌توانند به وسیله یک خط از هم تفکیک شوند.
  2. می‌دانیم که یک خط می‌تواند به کمک معادله y=wx+by=wx+b نمایش داده شود.(این همان مدل ما است)
  3. می‌دانیم با تغییر دادن مقدار w و b بی‌نهایت خط وجود خواهد داشت.
  4. برای تعیین این که کدام مقدار w و b بهترینخط جداکننده داده‌ها را به ما می‌دهد، از یک الگوریتم استفاده می‌کنیم.

SVM یکی از این الگوریتم‌ها هست که می‌تواند این کار را انجام دهد.

الگوریتم یا مدل؟

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

SVM یا SVMها؟

بعضی وقت‌ها می‌بینیم که مردم راجع به SVM و بعضی وقت‌ها هم راجع به SVMها صحبت می‌کنند.

طبق معمول ویکی‌پدیا در روشن و شفاف کردن چیزها به ما کمک می‌کند:

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

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

SVMها – ماشین‌های بردار پشتیبان

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

  • SVM برای طبقه‌بندی استفاده می‌شود.
  • SVR یا(Support Vector Regression) برای رگرسیون.

پس گفتن ماشین‌های بردار پشتیبان هم دیگه الآن منطقی به نظر میاد. با این وجود این پایان داستان نیست!

طبقه‌بندی

در سال ۱۹۵۷ یک مدل خطی ساده به نام پرسپترون توسط فردی به نام فرانک روزنبلت برای طبقه‌بندی اختراع شد(که در واقع اساس شبکه‌های عصبی ساده‌ای به نام پرسپترون چند لایه است).

چند سال بعد، واپنیک و چروننکیس مدل دیگری به نام «طبقه‌بندی کننده حداکث حاشیه» پیشنهاد دادند و همان‌جا بود که SVM متولد شد.

در سال ۱۹۹۲ واپنیک و همکارانش ایده‌ای داشتند که یک چیزی به نام کلک کرنل(Kernel Trick) را به روش قبلی اضافه کنند تا به آن‌ها اجازه دهد که حتی داده‌هایی که به صورت خطی تفکیک‌پذیر نیستند را هم طبقه‌بندی کنند.

سرانجام در سال ۱۹۹۵، کورتز و واپنیک، طبقه‌بندی کننده حاشیه نرم را معرفی کردند که به SVM اجازه می‌دهد تا بعضی از اشتباهات در طبقه‌بندی را هم بپذیرد.

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

  1. طبقه‌بندی کننده حاشیه حداکثر.
  2. نسخه‌ای که از کلک کرنل استفاده می‌کند.
  3. نسخه‌ای که از حاشیه نرم استفاده می‌کند.
  4. نسخه‌ای که ترکیب همه موارد قبلی است.

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

به همین دلیل است که وقتی از یک زبان برنامه‌‌نویسی استفاده می‌کنید می‌پرسید از کدام کرنل باید استفاده کنیم(بخاطر کرنل‌های مختلفی که وجود دارند) و یا کدام مقدار ابرپارامتر C را باید استفاده کنید(برای کنترل تاثیر حاشیه نرم).

رگرسیون

در سال ۱۹۹۶، واپنیک و همکارانش، نسخه‌ای از SVM را پیشنهاد دادند که به جای طبقه‌بندی، عمل رگرسیون را انجام می‌دهد. این مورد به Support Vector Regression یا SVR معروف است. همانند SVM در این مدل نیز از کلک کرنل و ابرپارامتر C  استفاده می‌شود.

در آینده مقاله ساده‌ای در مورد توضیح چگونگی استفاده از  SVR در زبان R خواهم نوشت و آدرس آن را همین‌جا قرار خواهم داد.

اگر علاقمند هستید که راجع به SVR بیشتر بدانیند، می‌توانید به این آموزش خوب که نوشته Smola and Schölkopft است، مراجعه کنید.

خلاصه تاریخچه

  • طبقه‌بندی کننده حاشیه حداکثر (۱۹۶۳ یا ۱۹۷۹)
  • کلک کرنل (۱۹۹۲)
  • طبقه‌بندی کننده حاشیه نرم (۱۹۹۵)
  • رگرسیون بردار پشتیبان (۱۹۹۶)

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

انواع دیگری از ماشین‌های بردار پشتیبان

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

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

نتیجه‌گیری

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

امیدوارم این مقاله دید وسیع‌تری از چشم‌انداز  SVM به شما داده باشد و کمک کرده باشد که بهتر این ماشین‌ها را بشناسید و درک کنید.

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

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

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

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

 

 

 

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

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

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

deepfake

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

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

 

deepfake new

 

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

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

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

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

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