نوشته‌ها

مقالات

۱٫بررسی روشهای متعادل سازی هیستوگرام در بهبود تصویر

چکیده: افزایش کنتراست به عنوان یکی از مسائل مهم در پردازش تصویر است.متعادل سازی هیستوگرام (HE) یکی از روش های معمول برای بهبود کنتراست در تصاویر دیجیتال است و یک روش افزایش کنتراست ساده و موثر است با این حال، این روش معمولا باعث کنتراست بیش از حد می شود که باعث ظاهر غیر طبیعی در تصویر پردازش شده می شود. هم چنین HE میانگین روشنایی تصویر را به خوبی حفظ نمی کند بنابراین روش های دیگری برای متعادل سازی تصویر با حفظ روشنایی تصویر ارائه شده است. این مقاله به بررسی فرم های جدید هیستوگرام برای افزایش کنتراست تصویر می پردازد. تفاوت عمده میان روش ها معیارهای مورد استفاده، تقسیم هیستوگرام ورودی است. متعادل سازی دو هیستوگرام با حفظ روشنایی(BBHE) میانگین مقادیر شدت به عنوان نقطه جداسازی استفاده می کند. متعادل سازی دو هیستوگرام با حداقل خطای متوسط روشنایی(MMBEBHE) است. متعادل سازی هیستوگرام متوسط – مجرای بازگشتی(RMSHE) بهبود یافته BBHE است. روش یکنواخت سازی پویلی هیستوگرام با حفظ روشنایی(BPDHE) بسط یافته MPHBP و DHE است.
واژه های کلیدی: بهبود کنتراست، متعادل سازی هیستوگرام، خطای متوسط روشنایی، تقسیم بندی هیستوگرام، حفظ روشنایی
فایل PDF – در ۲۲ صفحه- نویسنده : نوشین الله بخشی

بررسی روشهای متعادل سازی هیستوگرام در بهبود تصویر

رمز فایل : behsanandish.com


۲٫ بهبود کیفیت تصاویر آندوسکوپی از طریق تعدیل هیستوگرام فازی و توزیع ناهمسانگرد کنتراست

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

 

واژه های کلیدی: تصاویر آندوسکوپی، توزیع ناهمسانگرد کنتراست، تعدیل هیستوگرام فازی

فایل PDF – در ۶ صفحه- نویسندگان : حسین قیصری، میرحسین دزفولیان

بررسی روشهای متعادل سازی هیستوگرام در بهبود تصویر

رمز فایل : behsanandish.com


۳٫ تشخیص زود هنگام پوسیدگی دندان با استفاده از آنالیز هیستوگرام و طیف توان

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

واژه های کلیدی: پوسیدگی دندان، هیستوگرام، طیف توان، GUI، شدت پیکسل

فایل PDF – در ۶ صفحه- نویسندگان : محمد کریمی مریدانی، شبنم قهاری و فاطمه غلامی

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

رمز فایل : behsanandish.com


۴٫ بازیابی تصاویر چهره با استفاده از ترکیب هیستوگرام گرادیان و الگوی باینری محلی

چکیده: بازیابی چهره، یک موضوع تحقیقاتی مهم در پردازش تصویر است که هدف آن استخراج تصاویر چهره ای است که مشابه با یک تصویر جستار باشند. در این مقاله روشی برای بازیابی تصاویر چهره با استفاده از ترکیب هیستوگرام گرادیان و الگوی باینری محلی(LBP) پیشنهاد شده است. ترکیب این دو روش مقاومت در مقابل تغییرات موجود در تصاویر چهره را افزایش می دهد و در نتیجه عملکرد سیستم را در بازیابی تصاویر بهبود می بخشد. برای افزایش توانایی سیستم، یک طرح فیدبک ارتباطی مبتنی بر ماشین بردار پشتیبان(SVM) معرفی می کنیم. آزمایش ها بر روی پایگاه داده ی AR و در دو حالت بدون تصاویر با مانع و با تصاویر با مانع اناجم شده است. نتایج آزمایش ها نشان می دهد که روش پیشنادی ما به خوبی می تواند تصاویر چهره را بازیابی کند. در ادامه، روش پیشنهادی خود را با برخی از روش های موفق در توصیف چهره مقایسه کرده ایم. معیار دقت متوسط میانگین(MAP) برای روش پیشنهادی در حالت های اول و دوم آزمایش به ترتیب برابر است با ۹۴/۴۰%  و ۶۸/۱۲%. در حالی که بهترین نرخ برای روش های مقایسه شده برابر است با ۹۰/۳۷% و ۶۱/۹۹%. این نتایج نشان می دهد روش پیشنهادی ما نسبت به این روش ها بهتر عمل می کند و یک روش خوب برای بازیابی تصاویر چهره است.

واژه های کلیدی: الگوی باینری محلی، بازیابی چهره، فیدبک ارتباطی، ماشین بردار پشتیبان، هیستوگرام گرادیان.

فایل PDF – در ۱۱ صفحه- نویسندگان : محمد قاصری و حسین ابراهیم نژاد

ﺑﺎزﯾﺎﺑﯽ ﺗﺼﺎوﯾﺮ ﭼﻬﺮه ﺑﺎ اﺳﺘﻔﺎده از ﺗﺮﮐﯿﺐ ﻫﯿﺴﺘﻮﮔﺮام ﮔﺮادﯾﺎن و اﻟﮕﻮی ﺑﺎﯾﻨﺮی ﻣﺤﻠﯽ

رمز فایل : behsanandish.com


۵٫ بهبود وفقی کنتراست با استفاده از متعادل سازی بهینه هیستوگرام دو بعدی

چکیده: در این مقاله، برای بهبود وفقی کنتراست به ارائه و حل یک مسئله ی بهینه سازی در هیستوگرام دوبعدی پرداخته شده است. برای جلوگیری از بروز اثرات نامطلوب ناشی از دست کاری هیستوگرام تصویر، در بیان ریاضی مسأله در این مقاله همانند روش های مشابه دیگر، از یک سو هیستوگرام بهینه ی خروجی از روی هیستوگرامی دوبعدی که بیشترین شباهت را به هیستوگرام دوبعدی تصویر ورودی و نیز توزیع یکنواخت داشته باشد به دست می آید و از سویی دیگر بر خلاف دیگر روش ها، با وزن دهی وفقی، اطلاعات محلی مناسبی را نیز دراین جستجو در نظر می گیرد. نگاشت مناسب با حل این مسأله ی بهینه سازی به دست آمده و آزمایش های گوناگونی که بر روی تصاویر گوناگون انجام شده است، درستی مدل بهینه سازی را نشان می دهد. به کارگیری الگوریتم پیشنهادی بر روی تصاویر متعدد، در مقایسه با روش مرجع به صورت میانگین به بهبود ۷۵ درصدی و ۳ درصدی معیارهای AMBEN  و  DEN  منجر شده است.

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

فایل PDF – در ۱۰ صفحه- نویسندگان : سحر ایروانی و مهدی ازوجی

ﺑﻬﺒﻮد وﻓﻘﯽ ﮐﻨﺘﺮاﺳﺖ ﺑﺎ اﺳﺘﻔﺎده از ﻣﺘﻌﺎدل ﺳﺎزی ﺑﻬﯿﻨﻪ ی ﻫﯿﺴﺘﻮﮔﺮام دوﺑﻌﺪی

رمز فایل : behsanandish.com


۶٫ A Study for Applications of Histogram in Image Enhancement

مطالعه برای کاربرد هیستوگرام در بهبود تصویر

Abstract- Image Enhancement aims at improving the visual quality of input image for a particular area. The criterion used by enhancement algorithms to enhance the image is; using histogram details of that image. This paper defines the various applications of histograms through which they help in the enhancement process. The paper also represents three basic histogram processing techniques- histogram sliding, histogram stretching, and histogram equalization, and how these techniques help in enhancement process, which factors effect these techniques. We examine subjectively the effect of these processing techniques. Comparative analysis of these techniques is also carried out.

Keywords: Histogram Equalization, Histogram Sliding, Histogram Stretching, Image Enhancement, Visual Quality.

فایل PDF – در ۵ صفحه- نویسندگان : Harpreet Kaur, Neelofar Sohi

A Study for Applications of Histogram in Image Enhancement

رمز فایل : behsanandish.com


۷٫ An Adaptive Histogram Equalization Algorithm on the Image Gray Level Mapping

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

Abstract
The conventional histogram equalization algorithm is easy causing information loss. The paper presented an adaptive histogram-based algorithm in which the information entropy remains the same. The algorithm introduces parameter ȕ in the gray level mapping formula, and takes the information entropy as the target function to adaptively adjust the spacing of two adjacent gray levels in the new histogram. So it avoids excessive gray pixel merger and excessive bright local areas of the image. Experiments show that the improved algorithm may effectively improve visual effects under the premise of the same information entropy. It is useful in CT image processing.

Keywords: Histogram Equalization; Image Enhancement; Gray Level Mapping; Information Entropy

فایل PDF – در ۸ صفحه- نویسندگان : Youlian Zhu, Cheng Huang

An Adaptive Histogram Equalization Algorithm on the Image

رمز فایل : behsanandish.com


۸٫ Contrast Enhancement Algorithm Based on Gap Adjustment for Histogram Equalization

الگوریتم تقویت کنتراست براساس تنظیم گاف برای برابری هیستوگرام

Abstract: Image enhancement methods have been widely used to improve the visual effects of images. Owing to its simplicity and effectiveness histogram equalization (HE) is one of the methods used for enhancing image contrast. However, HE may result in over-enhancement and feature loss problems that lead to unnatural look and loss of details in the processed images. Researchers have proposed various HE-based methods to solve the over-enhancement problem; however, they have largely ignored the feature loss problem. Therefore, a contrast enhancement algorithm based on gap adjustment for histogram equalization (CegaHE) is proposed. It refers to a visual contrast enhancement algorithm based on histogram equalization (VCEA), which generates visually pleasing enhancedimages,andimprovestheenhancementeffectsofVCEA.CegaHEadjuststhegapsbetween two gray values based on the adjustment equation, which takes the properties of human visual perception into consideration, to solve the over-enhancement problem. Besides, it also alleviates the feature loss problem and further enhances the textures in the dark regions of the images to improve the quality of the processed images for human visual perception. Experimental results demonstrate that CegaHE is a reliable method for contrast enhancement and that it significantly outperforms VCEA and other methods.

Keywords: cumulative distribution function (CDF); contrast enhancement; histogram equalization (HE); human visual perception; gap adjustment

فایل PDF – در ۱۸ صفحه- نویسندگان : Chung-Cheng Chiu , and Chih-Chung Ting

Contrast Enhancement Algorithm Based on Gap

رمز فایل : behsanandish.com


۹٫ Enhancement of Images Using Histogram Processing Techniques

بهبود تصاویر با استفاده از تکنیک های پردازش هیستوگرام

Abstract- Image enhancement is a mean as the improvement of an image appearance by increasing dominance of some features or by decreasing ambiguity between different regions of the image. Image enhancement processes consist of a collection of techniques that seek to improve the visual appearance of an image or to convert the image to a form better suited for analysis by a human or machine. Many images such as medical images, remote sensing images, electron microscopy images and even real life photographic pictures, suffer from poor contrast. Therefore it is necessary to enhance the contrast.The purpose of image enhancement methods is to increase image visibility and details. Enhanced image provide clear image to eyes or assist feature extraction processing in computer vision system. Numerous enhancement methods have been proposed but the enhancement efficiency, computational requirements, noise amplification, user intervention, and application suitability are the common factors to be considered when choosing from these different methods for specific image processing application.

Keywords: Enhancement, Histogram processing techniques, PSNR,MSE.

فایل PDF – در ۵ صفحه- نویسندگان :Komal Vij , Yaduvir Singh

Enhancement of Images Using Histogram Processing

رمز فایل : behsanandish.com


۱۰٫ USE OF HISTOGRAM EQUALIZATION IN IMAGE PROCESSING FOR IMAGE ENHANCEMENT

استفاده از تعادل هیستوگرام در پردازش تصویر برای افزایش تصویر

Abstract— Digital Image Processing is a rapidly evolving field with the growing applications in science & engineering. Image Processing holds the possibility of developing an ultimate machine that could perform visual functions of all living beings. The image processing is a visual task, the foremost step is to obtain an image i.e. image acquisition then enhancement and finally to process. In this paper there are details for image enhancement for the purpose of image processing. Image enhancement is basically improving the digital image quality. Image histogram is helpful in image enhancement. The histogram in the context of image processing is the operation by which the occurrences of each intensity value in the image is shown and Histogram equalization is the technique by which the dynamic range of the histogram of an image is increased.

Keywords- Image processing, image enhancement, image histogram, Histogram equalization

فایل PDF – در ۵ صفحه- نویسندگان :Sapana S. Bagade , Vijaya K. Shandilya

USE OF HISTOGRAM EQUALIZATION IN IMAGE PROCESSING FOR IMAGE ENHANCEMENT

رمز فایل : behsanandish.com


جزوات آموزشی

۱٫ Computer Vision – Histogram Processing

۱٫ بینایی کامپیوتر- پردازش هیستوگرام

فایل PDF – در ۴۰ صفحه- نویسنده : Dr. S. Das 

Computer Vision -histogram processing

رمز فایل : behsanandish.com


۲٫ Digital Image Processing (CS/ECE ۵۴۵)  Lecture ۲: Histograms and Point Operations (Part ۱)

پردازش تصویر دیجیتال(CS/ECE 545)  درس ۲: هیستوگرام و عملیات نقطه

فایل PDF – در ۵۶ صفحه- نویسنده : Prof Emmanuel Agu

Digital Image Processing-histograms and point operations

رمز فایل : behsanandish.com


۳٫ Part 3: Image Processing – Digital Images and Intensity Histograms

بخش ۳: پردازش تصویر – تصاویر دیجیتال و هیستوگرام های شدت

فایل PDF – در ۵۷ صفحه- نویسنده : Georgy Gimel’farb

Digital Images and Intensity Histograms

رمز فایل : behsanandish.com


۴٫  Digital Imaging and Multimedia Histograms of Digital Images

تصویربرداری دیجیتالی و هیستوگرام های چند رسانه ای از تصاویر دیجیتال

فایل PDF – در ۱۲ صفحه- نویسنده : Ahmed Elgammal

Digital Imaging and Multimedia

رمز فایل : behsanandish.com

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

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

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

  • یادگیری نظارت شده (هدایت شده – 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

 

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

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

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

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

رمز : 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 ها در سی شارپ – کلاس CancellationToken

زمانی که عملیاتی را به عنوان یک Task اجرا می کنیم، ممکن است بخواهیم آن Task را در حین اجرا متوقف کنیم، برای مثال، Task ای داریم که در حال پردازش ۱۰۰۰ فایل است و کاربر باید این امکان را داشته باشد که Task در حال اجرا را متوقف کند. عملیات متوقف کردن Task ها هم برای متدهای کلاس Parallel امکان پذیر است و هم کلاس Task. برای اینکار می بایست از کلاس CancellationToken استفاده کنیم. برای مثال Task زیر را در نظر بگیرید که حاصل میانگین جمع اعداد ۱ تا ۱۰۰ را محاسبه می کند:

Task < int > averageTask = new Task < int > (() =>
{
    Console.WriteLine("Calculating average...");
    Console.WriteLine("Press Ctrl+C to cancel...");
    var sum = 0;
    for (int counter = 1; counter < = 100; counter++)
    {
        sum += counter;
        Thread.Sleep(100);
    }
    Console.WriteLine("All done.");
    return sum/100;
});
averageTask.Start();
Console.WriteLine(averageTask.Result);

قبلاً با این کد آشنا شدیم، اما کاری که در این قسمت می خواهیم انجام دهیم اضافه کردن قابلیتی است که کاربر بتواند با فشردن کلید های Ctrl+C عملیات را متوقف کند. برای اینکار ابتدا شئ ای از نوع کلاس CancellationTokenSource که در فضای نام System.Threading قرار دارد، در کلاس Program به صورت زیر تعریف می کنیم:

Task < int > averageTask = new Task < int > (() = >
{
    Console.WriteLine("Calculating average...");
    Console.WriteLine("Press q to cancel...");
    var sum = 0;
    for (int counter = 1; counter < = 100; counter++)
    {
        sum += counter;
        Thread.Sleep(100);
    }
    Console.WriteLine("All done.");
    return sum/100;
}, source.Token);

شئ source که در کلاس Program ایجاد کردیم متدی دارد با نام Cancel که این متد را زمانی که قصد داریم Task متوقف شود باید فراخوانی کنیم. فراخوانی این متد باید زمانی انجام شود که کاربر کلید های Ctrl+C را فشار داده است. در محیط Console، زمانی که کاربر کلید های Ctrl+C را فشار می دهد، event ای با نام CancelPressKey در کلاس Console فراخوانی می شود، پس باید این از این event برای فراخوانی متد Cancel به صورت زیر استفاده کنیم:

Console.CancelKeyPress += (sender, eventArgs) = >
{
    source.Cancel();
    eventArgs.Cancel = true;
};

به خط دوم داخل event دقت کنید، زمانی که کلید های Ctrl+C فشرده می شوند، به صورت پیش فرض کل برنامه Console متوقف می شود، برای جلوگیری از این کار مقدار خصوصیت Cancel را در شئ eventArgs به مقدار true ست می کنیم، یعنی عملیات متوقف کردن محیط کنسول به صورت دستی توسط ما انجام شده و خود سیستم نیاز به انجام کاری در این باره ندارد.

بعد از Subscribe کردن event بالا، باید به برنامه بگوییم تا زمانی که task به اتمام نرسیده یا کاربر کلید های Ctrl+C را فشار نداده نباید از برنامه خارج شویم، به همین خاطر یک حلقه while به صورت زیر ایجاد می کنیم:

while (!averageTask.IsCompleted &amp;&amp; !source.IsCancellationRequested)
{                                                                                                
}

با خصوصیت IsCompleted در کلاس Task قبلاً آشنا شدیم، اما خصوصیت IsCancellationRequested در شئ source زمانی مقدارش true می شود که متد Cancel فراخوانی شود، پس تا زمانی که عملیات Task به اتمام نرسیده و زمانی که کاربر کلید های Ctrl+C را فشار نداده برنامه در حلقه while منتظر می ماند.

در ادامه باید Task ایجاد شده را به صورتی تغییر دهیم که داخل حلقه for بررسی شود که متد Cancel فراخوانی شده است یا خیر، اگر فراخوانی شده بود باید از Task خارج شویم، برای این کار نیز از خصوصیت IsCancellationRequested در شئ source استفاده می کنیم، Task ایجاد شده را به صورت زیر تغییر می دهیم:

Task < int > averageTask = new Task < int > (() = >
{
    Console.WriteLine("Calculating average...");
    Console.WriteLine("Press Ctrl+C to cancel...");
    var sum = 0;
    for (int counter = 1; counter < = 100; counter++)
    {
        if (source.IsCancellationRequested)
        {
            Console.WriteLine("Operation terminated!");
            return 0;
        }
        sum += counter;
        Thread.Sleep(100);
    }
    Console.WriteLine("All done.");
    return sum/100;
}, source.Token);

همانطور که مشاهده می کنید داخل حلقه for گفتیم که اگر IsCancellationRequested برابر true بود پیغامی را نمایش بده و مقدار ۰ را برگردان. کد نهایی ما به صورت زیر می باشد:

class Program
{
    private static CancellationTokenSource source = new CancellationTokenSource();
    static void Main(string[] args)
    {
        Task < int > averageTask = new Task < int >(() = >
        {
            Console.WriteLine("Calculating average...");
            Console.WriteLine("Press Ctrl+C to cancel...");
            var sum = 0;
            for (int counter = 1; counter <= 100; counter++) { if (source.IsCancellationRequested) { Console.WriteLine("Operation terminated!"); return 0; } sum += counter; Thread.Sleep(100); } Console.WriteLine("All done."); return sum/100; }, source.Token); averageTask.Start(); Console.CancelKeyPress += (sender, eventArgs) = >
        {
            source.Cancel();
            eventArgs.Cancel = true;
        };
        while (!averageTask.IsCompleted && !source.IsCancellationRequested)
        {                                                                                                
        }
 
        Console.WriteLine(averageTask.Result);
    }
}

در صورتی که برنامه بالا را اجرا کرده و کلید های Ctrl+C را فشار دهیم خروجی زیر برای ما نمایش داده می شود:

Calculating average...
Press Ctrl+C to cancel...
Operation terminated!
۰
Press any key to continue . . .

استفاده از CancellationToken در کلاس Parallel

علاوه بر کلاس Task می توان از قابلیت CancellationToken در متدهای کلاس Parallel نیز استفاده کرد، برای آشنایی بیشتر فرض کنید کدی به صورت زیر تعریف شده که لیست فایل های jpg داخل یک پوشه را پردازش می کند:

var jpegFiles = System.IO.Directory.GetFiles("D:\\Images", "*.jpg");
 
Parallel.ForEach(jpegFiles, file = >
{
    var fileInfo = new FileInfo(file);
    // process file
});

برای متوقف کردن عملیات پردازش فایل ها، ابتدا شئ ای از نوع CancellationTokenSource مانند مثال قبل ایجاد می کنیم:

private static CancellationTokenSource source = new CancellationTokenSource();

در قدم بعدی کلاسی از نوع ParallelOptions به صورت زیر تعریف کرده، خصوصیت CancellationToken را برابر خصوصیت Token در شئ source قرار داده و این کلاس را به عنوان پارامتر ورودی به متد ForEach به صورت زیر ارسال می کنیم:

ParallelOptions options = new ParallelOptions();
options.CancellationToken = source.Token;
 
try
{
    Parallel.ForEach(jpegFiles,options, file = >
    {
        options.CancellationToken.ThrowIfCancellationRequested();                                                
        var fileInfo = new FileInfo(file);
        // process file
    });
}
catch (OperationCanceledException ex)
{
    Console.WriteLine(ex);
}

دقت کنید در قسمت ForEach متدی با نام ThrowIfCancellationRequested فراخوانی شده است، در حقیقت این متد بعد از فراخوانی بررسی می کند که آیا متد Cancel برای شئ source فراخوانی شده است یا خیر، اگر فراخوانی شده بود خطایی از نوع OperationCanceledException ایجاد می شود که در خارج از بدنه ForEach کلاس Parallel، بوسیله ساختار try..catch این خطا مدیریت شده است. دقت کنید که روند مدیریت Cancel کردن در کلاس Parallel با کلاس Task متفاوت است و دلیل این موضوع نوع برخورد برنامه با این کلاس ها است. در قسمت بعدی با مبحث Parallel LINQ آشنا خواهیم شد.

منبع



قسمت اول آموزش-برنامه نویسی 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

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

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

 

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

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

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

 

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

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

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

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

۴- برخی از لبه های کشف شده واقعا لبه نیستند و در واقع نویز هستند که باید آنها توسط حد آستانه هیسترزیس فیلتر شوند.هیسترزیس از دو حد آستانه بالاتر (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 رو دارن. (دز این‌جا میتونیم این ویژگی‌ها رو به عنوان طول و عرض در یک صفحه دو بعدی در نظر بگیریم)

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

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

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

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

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

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

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

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

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

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

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

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

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

پیاده‌سازی الگوریتم  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},
            {۱٫۵, ۲٫۰},
            {۳٫۰, ۴٫۰},
            {۵٫۰, ۷٫۰},
            {۳٫۵, ۵٫۰},
            {۴٫۵, ۵٫۰},
            {۳٫۵, ۴٫۵}};
    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 در گیتلب

منبع

دو مثال از کاربردهای سیستم ایمنی مصنوعی

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

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

مثال (۱) : مدل تركيبي مبتني بر سيستم ايمني مصنوعي و اتوماتاي سلولي فازی (FCA-AIS)

الگوريتم هاي سيستم ايمني مصنوعي در گروه الگوريتم هاي بهينه سازي اتفاقي قرار دارند كه در آنها از قوانين موجود در سيستم ايمني بيولوژيکي بمنظور بهينه سازي استفاده مي شود. رفتار الگوريتم سيستم ايمني مصنوعي وابستگي شديدي به پارامترهايي نظیر نحوه تعريف و احتمال عملگرهاي ابَرجهش، اندازه جامعه ايجاد شده براي هر آنتي بادي، اندازه جمعيت ها و تعداد دوره هاي توليد شده دارد.

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

سال ۲۰۰۳ تیمیس در مقاله ” A Comment on opt-AiNET: An Immune Network Algorithm for Optimisation” براي حل اين مشكل روشي ارائه نموده که با محاسبه ميزان وابستگي تناسبي، که با نرمال کردن مقادير وابستگي هر آنتي بادي در هر مرحله زماني بدست مي آيد تا اندازه اي اين مشکل حل شده است. همچنين جوادزاده در سال ۲۰۰۸ میلادی در مقاله “Hybrid Models based on Artificial Immune systems and Cellular Automata and Their Applications to Optimization Problems” مدل ترکيبيCA-AIS را به منظور تعيين پارامترهاي اساسي براساس ارزيابي وابستگي محلي توسط مفاهیم اتوماتای سلولی ارائه نموده است. اما هدف از ارائه مدل در مثال ارائه شده ، حل اين مشكل با استفاده از روش ارزيابي وابستگي محلي و همچنين دانش خبره مي باشد.

اتوماتای سلولی

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

قوانين اتوماتاي سلولي، نحوه تأثير پذيرفتن سلول از سلول هاي همسايه خود را مشخص مي‌کند. يک سلول، همسايه سلول ديگر گفته مي شود هرگاه بتواند آن را در يک مرحله و براساس قانون حاکم تحت تأثير قرار دهد.

اتوماتاي سلولي فازی

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

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

مدل ترکيبي مبتنی بر سيستم ايمني مصنوعي و اتوماتاي سلولي فازي(FCA-AIS)

در روش پيشنهادي از اتوماتاي سلولي فازي به منظور تعيين مقادير مناسب نرخ ابر جهش براي آنتي بادي ها استفاده مي شود. قوانين فازي در هر سلول اتوماتاي سلولي فازي عهده دار تعيين مقدار مناسب نرخ ابر جهش براي آنتي بادي ها متناظر با آن سلول مي باشد. در واقع اتوماتاي سلولي فازي تعيين مي کند که براي کدام آنتي بادي ها نرخ ابرجهش بايستي پايين و براي کدام آنتي بادي ها نرخ ابرجهش بايستي بالا در نظر گرفته شود. براي اين منظور در موقعيت هايي كه ميزان وابستگي آنتي بادي ها نسبت به وابستگي بهترين آنتي بادي در همسايگي از ارزش بالايي برخوردار نيست بايد از مقادير بالا براي نرخ ابرجهش استفاده نمود و در مقابل در موقعيت هايي كه ميزان وابستگي آنتي بادي ها نسبت به وابستگي بهترين آنتي بادي در همسايگي از ارزش بالايي برخوردار است بايد از مقادير پايين براي نرخ ابر جهش آن آنتي بادي استفاده نمود.

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

 

همسایگی ون نیومن

 

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

نمایی از یک سلول در مدل ترکیبی FCA-AIS

براي تعيين نرخ ابر جهش با استفاده از FCA نياز به مشخص نمودن کيفيت وابستگي آنتي بادي ها، وجود دارد. براي اين منظور، از ميزان تعلق وابستگي آنتي بادي به مجموعه هاي فازي Near و Far استفاده مي شود که در نمودار ۱ نشان داده شده است. مرکز اين مجموعه ها بر ميزان وابستگي بهترين آنتي بادي در همسايگي آن آنتي بادي  منطبق شده است و ميزان ابر جهش بر اساس رابطه های (۱) و (۲) تعيين مي شود.

رابطه (۱) : If Affinity is Near then Mutatin is Low
رابطه (۲) : If Affinity is Far then Mutatin is High

 

توابع عضویت Near و Far

نمودار ۱ – توابع عضويت Near و Far

در توابع عضويت مجموعه هاي فازي Near و Far (نمودار ۱) ، Ab* بهترين آنتي بادي در همسايگي آنتي بادي مورد پردازش مي باشد، همچنين مقدار α برابر با قدرمطلق تفاضل بهترين و بدترين آنتي بادي  در همسايگي آنتي بادي  مورد نظر است. اين امر باعث مي شود دامنه توابع عضويت مجموعه هاي فازيNear و Far در روند تکاملي راه کار پيشنهادي به صورت پويا خود را با شرايط محيط وفق دهند. توابع عضويت Low و High در نمودار ۲ آمده است و نقاط a، b، c و d به ترتيب برابر مقادیر ۰، ۱ ، ۲ و ۳ انتخاب شده اند.

 

نمودار ۲ – توابع عضويت Low و Highنمودار ۲ – توابع عضويت Low و High

 

نتایج آزمایش ها

در اين بخش نتايج شبيه سازي سيستم ايمني مصنوعي مبتني بر اتوماتاي سلولي فازی (FCA-AIS)براي چهار تابع محك استاندارد (روابط ۳ تا ۶) که دارای بهینه سراسری در صفر است به ازاء كيفيت جواب بدست آمده در مقابل مدل ترکیبی سيستم ايمني مصنوعي ، اتوماتای سلولی و الگوريتم سيستم ايمني مصنوعي استاندارد مورد مطالعه قرار گرفته است.

براي ارزيابي راهکار پيشنهادي توابع مورد آزمايش به صورت سي بعدي و آنتي-بادي ها بصورت اعداد حقيقي کدگذاري شده اند و راهکار پيشنهادي با ۱۰۰ تکرار براي بدست آوردن پاسخ بهينه مورد آزمون قرار گرفته شده است. با توجه به ماهيت آزمون‌هاي آماري، پس از ۳۰ بار اجراي مكرر به ازاي هر تابع، از شاخص‌هاي بهترين پاسخ و ميانگين پاسخ‌ها براي مقايسه كارايي الگوريتم و از شاخص واريانس (كه يكي از شاخص‌هاي پراكندگي است) براي مقايسه پايداري استفاده شده است. نتايج شبيه‌سازي‌هاي انجام شده با استفاده از راه کار پيشنهادي، مدل ترکیبی سيستم ايمني مصنوعي و اتوماتای سلولی و الگوريتم سيستم ايمني مصنوعي به ترتيب در جدول های ۱ ، ۲ و ۳ آورده شده است.

 

روابط

 

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

تعداد سلول ها، پارامتري مهم است كه بر كارايي مدل FCA-AIS تاثير مستقيم دارد .نمودار ۳ تاثير تعداد سلول ها را بر سرعت همگرايي مدل پيشنهادي در بهینه یابی تابع نشان داده است. هر نقطه نشان داده شده در اين نمودارها ارزش بهترين جواب بدست آمده در هر تكرار الگوريتم را نشان مي دهد. نتايج شبيه سازي ها نشان داد با افزايش تعداد سلول ها، روند همگرايي به بهينه سراسري شتاب بخشيده مي شود. اما تا حدي افزايش تعداد سلول ها مي تواند بر سرعت همگرايي بيافزايد و با افزايش تعداد سلول ها از تعداد ۳۶ سلول، تاثير چشمگيري در سرعت رسيدن به بهينه سراسري مشاهده نمي شود و با توجه به حجم محاسبات کمتر، مدل با ۳۶ سلول  پیشنهاد می شود.

به منظور مطالعه تاثير شعاع همسايگي بر كارايي مدل پيشنهادي چندين شبيه سازي با شعاع همسایگی ۱ تا ۴ انجام شده كه نتايج آن در بهینه یابی تابع در نمودار ۴ ارائه شده است. نتايج شبيه سازي ها نشان مي-دهد كه مدل پيشنهادي FCA-AIS با شعاع همسايگي ۱ جواب هايي با كيفيتي قابل قبول توليد مي كند که در مقايسه با ديگر شعاع هاي همسايگي به دليل حجم محاسبات کمتر، داراي امتياز است.

 

جدول 1       جدول 2

 

جدول 3

 

نمودار 3            نمودار 4

 

نتيجه‌گيري

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

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

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

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

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

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

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

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

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

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

الگوریتم‌های ژنتیک ابتدا جمعیت اولیه‌ای تولید کرده و سپس سعی در بهبود بخشیدن این جمعیت دارند. برای مسئله 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 داریم که تصمیم می گیرد از دو والدین کدام ژن باید انتخاب شود.

 

مسئله چند وزیر قسمت ۱
مسئله چند وزیر قسمت ۲
مسئله چند وزیر قسمت ۳
مسئله چند وزیر قسمت ۴

۱٫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 – در ۱۴ صفحه- نویسنده : Omar Sultan Al-Kadi

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

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


۲٫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 – در ۵ صفحه- نویسنده : Neelu Arora , Mrs. G. Sarvani

A Review Paper on Gabor Filter Algorithm & Its Applications

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


۳٫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 – در ۶ صفحه- نویسنده : P. Kruizinga, N. Petkov and S.E. Grigorescu

Comparison of texture features based on Gabor filters

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


۴٫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 – در ۸ صفحه- نویسنده : Zehang Sun, George Bebis and Ronald Miller

Evolutionary Gabor Filter Optimization with Application to Vehicle Detection

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


۵٫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 – در ۶ صفحه- نویسنده : 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


۶٫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 – در ۱۰ صفحه- نویسنده : TOMASZ ANDRYSIAK, MICHAŁ CHORA´ S

IMAGE RETRIEVAL BASED ON HIERARCHICAL GABOR FILTERS

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


۷٫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 – در ۸ صفحه- نویسنده : Shuai Liu, Yuanning Liu, Xiaodong Zhu, Guang Huo, Jingwei Cui, and Yihao Chen

 

Iris Recognition Based On Adaptive Gabor Filter

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


۸٫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 – در ۱۲ صفحه- نویسنده : 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 در طبقه‌بندی بدانید، می‌توانید به آموزش‌های ریاضی مربوط به آن مراجعه کنید.

فناوری فشرده سازی تصویر چگونه عمل می کند؟

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

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

چرا باید تصاویر را فشرده سازی کرد؟

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

فشرده سازی تصویر چیست؟

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

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

روشهای فشرده سازی تصویر

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

فشرده سازی بدون اتلاف

این روش را روش فشرده سازی بازگشت پذیر نیز می گویند. زیرا با استفاده از این روش امکان بازگردانی تصویر فشرده شده به تصویر اصلی وجود دارد. این روش ضریب فشرده سازی کمتری دارد و کیفیت تصویر را کاهش نمی دهد. برای فشرده سازی عکس ها با این روش الگوریتم های مختلفی وجود دارند که نتیجه بالا را به دست می دهند. رایج ترین الگوریتم حذف محتواهای تکراری با روشی خاص است. به این صورت سیستم از عبارات و متون تکراری فاکتور می گیرد و محتواهای اضافی را حذف می کند. برای درک بهتر موضوع به این مثال توجه کنید. تصر کنید محتوای ما «whatisimage whatisimage2 whatisimage3» باشد. اگر بخواهیم این متن را با روش فوق فشرده سازی کنیم لازم است از عبارت تکراری «whatisimage» فاکتور بگیریم و بقیه آنها را حذف نماییم. نتیجه به صورت «w (w)2 (w)3» در می آید. در این روش عبارت «(w)» به جای «whatisimage» قرار گرفته است و همین باعث شده طول متن مورد نظر تا حد زیادی کاهش یابد.

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

فشرده سازی بااتلاف

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

فشرده سازی با اتلاف

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

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

ابزارهای فشرده سازی عکس

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

بدی این روش این است که شما باید ابتدا فایل اصلی خود را که احتمالا حجم بالایی نیز دارد ارسال کنید تا وب سایت سرویس دهنده عملیات فشرده سازی را انجام دهد. برای تصاویر حجم بالا و یا تصاویر خصوصی و شخصی این روش اصلا مناسب نیست و عملا امکان ارسال فایل وجود ندارد. به جای آن بهتر است از نرم افزارهای فشرده سازی تصویر استفاده کنید. Advanced JPEG Compressor و PicShrink دو برنامه فشرده سازی مخصوص دسکتاپ هستند که با استفاده از آنها می توانید تصاویر حجم بالا را نیز فشرده نمایید. مزیت استفاده از نرم افزار این است که دیگر نیازی به ارسال تصاویر و فایل ها به وب سایت سرویس دهنده وجود ندارد و می توان عملیات را در رایانه شخصی انجام داد.

انواع روشهای فشرده سازی تصویر

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

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

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

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

روشهای فشرده سازی تصویر

اما پس از توضیحات ابتدایی برویم سر اصل موضوع یعنی روشهای فشرده سازی تصویر. به طور کلی ۵ روش فشرده سازی تصویر (JPEG، MPEG، MP3، MPEG2، MPEG) مد نظر ما می باشد که یک یک آنها را ذکر کرده و توضیح می دهیم.

روش JPEG 
این فرمت مخفف عبارت JOINT PHOTOGRAPHIC EXPERT GROUP و به معنی «گروه مشترک کارشناسان گرافیک» است. از این نام برای نوعی فشرده سازی تصویر نیز استفاده شده است. روش JPEG اولین و البته ساده ترین روش فشرده سازی تصویر می باشد که جهت فشرده‌سازی تصاویر گرافیکی استفاده ایجاد شده است.

فشرده سازی به روش jpeg

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

روش MPEG
نام فرمت MPEG مخفف عبارت MOVING PICTURE EXOERT GROUP و به معنی «گروه کارشناسان تصویر متحرک» می باشد. روش مذکور در ابتدا آن داده های تصویری را با سرعت حدود ۵ مگابیت در ثانیه انتقال می داد که در نهایت منجر به ایجاد تصاویر ویدئویی می‌شد. با این روش از فشرده سازی تصاویر امکان ذخیره سازی تصاویر متحرک برای ۷۰ دقیقه و به اندازه ۶۵۰ مگابایت فراهم بود. در روش MPEG بیت‌ (Bit) های داده به صورت سریالی ارسال می‌شوند که در کنار آنها بیت‌های کنترل و هماهنگ‌کننده نیز ارسال می شوند که مکان و نوع جاگذاری بیت‌های اطلاعاتی را برای ثبت اطلاعات صدا و تصویر تعیین می کند. البته روش کار کمی پیچیده تر از این است که توسط رایانه انجام می شود.

روش MPEG2
در این روش که MPEG2 نام دارد از ضریب فشرده‌سازی بالاتری نسبت به روشهای پیشین استفاده می شود. در این روش امکان بررسی داده ها ۱۵ مگابیت در ثانیه وجود دارد و از آن در DVD ها استفاده می شود. لازم به ذکر است که در روش MPEG2 هر فریم (Frame) تصویر شامل چندین سطر از اطلاعات دیجیتالی می باشد که با روشهای پیشرفته جایگذاری می شوند.

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

روش MPEG-4 کاربرد فراوان دارد که نمونه آن در فیلم صحنه بازی تنیس است. در این حالت می توان صحنه را به دو مولفه بازیکن و زمین بازی تقسیم کرد که در آن زمین بازی دائما ثابت می باشد و در تمام تصاویر تکرار می شود. اما بازیکن همواره در حال حرکت می باشد. در این روش پهنای باند اشغالی بسیار کاهش می یابد و با روشهای پیشرفته حجم فایل ها کاهش می یابد.

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


در ادامه مطالعه فایل های زیر می تواند کمک کننده باشد:

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

رمز فایل: behsanandish.com

فشرده سازی بدون اتلاف

رمز فایل: behsanandish.com

فشرده سازی تصویر به روش MPEG

رمز فایل: behsanandish.com

فشرده سازی تصویر قسمت ۱
فشرده سازی تصویر قسمت ۲