0

وبلاگ

سامانه آموزش سیستم اطلاعات جغرافیایی و سنجش از دور مقالات دانش محور الگوریتم های یادگیری ماشین

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

الگوریتم های یادگیری ماشین (Machine Learning Algorithms)

مقدمه

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

یادگیری ماشین (Machine Learning)

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

آنالیز خوشه ای (Cluster Analysis)

آنالیز خوشه بندی (Clustering Analysis) یا قطعه بندی داده ها (Data Segmentation) را می تاون یک یادگیری ماشین نظات نشده در نظر گرفت که شامل روش ها و تکنیک های مختلفی به منظور یافتن الگوهای هنگام جمع آوری نمونه های داده و گروه بندی داده ها به گروههای مشابه و شبیه به هم با استفاده از اندازه گیری فواصل از پیش تعیین شده همچون فاصله اقلیدوسی و موادی همچون آن می باشد. داده ها و مشاهداتی که ویژگی های مشابهی دارند در یک کلاستر یا خوشه گروه بندی می شوند و از طریق فاصله ای که با داده های نمونه ای دارند تفسیر و توصیف می شوند.

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

انواع خوشه بندی (Types of Clustering)

روش های بسیاری در گروه بندی تکنیک های خوشه بندی به دسته های مختلف وجود دارد. برای مثال بر اساس سطوح اشتراک (Area of overlap)، دو دسته خوشه بندی مختلف وجود دارد :

1- خوشه بندی سخت (Hard Clustering): در این حالت خوشه ها دارای همپوشانی نیستند. روش های خوشه بندی همچون k-means، k-means++ از این گروه به حساب می آیند. در این حالت یک نقطه تنها متعلق به یک خوشه می باشد. در نتیجه تکلیف تعلق داده در این روش ها به طور کاملا صریح مشخص می گردد و امکان تعلق یک داده به چند خوشه وجود ندارد. 

2- خوشه بندی نرم (Soft Clustering): در این حالت خوشه های می توانند همپوشانی داشته باشند. روش های همچون Fuzzy-C-means، EM از این گروه به حساب می آیند. یک داده در این روش ها می تواند متعلق به بیش از یک خوشه باشد و در نتیجه یک درجه عضویت یا تعلق و یا احتمال برای هر یک از داده ها به خوشه های مختلف تعریف و تعیین می گردد.

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

1- خوشه بندی مونوتتیک (Monothetic Clustering): در این حالت بین اعضای خوشه ها یک سری ویژگی های مشترکی وجود دارد.

2- خوشه بندی پلیتتیک (Polythetic): در این حالت درجه ای از شباهت بین اعضای هر خوشه وجود دارد بدون آنکه دارای ویژگی ها و خواص مشترکی باشند.

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

1. الگوریتم های خوشه بندی مرکز-مبنا (Centroid-based Clustering Algorithms)

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

4.1. الگوریتم Fuzzy C-means

واژه فازی برای تاکید بر این واقعیت که همپوشانی های بسیای بین خوشه ها در واقعیت وجود دارد مورد استفاده قرار می گیرد. که امکان قرارگیری یک داده در یک یا چند خوشه را فراهم می آورد. در نتیجه به نوعی جز خوشه بندی های نرم (Soft Clustering) قرار می گیرد. برای مثال رنگ نارنجی را در نظر بگیرید، که ترکیبی از رنگ های زرد و قرمز می باشد که به این معنا است که رنگ نارنجی به نسبت یکسانی به خوشه های زرد و قرمز تعلق دارد. تابع درجه عضویت (Membership Degree Function) برای اندازه گیری میزان عضویت یا ارتباط داده ها به یک خوشه مورد استفاده قرار می گیرند. این توابع  احتمال تعلق یک رخداد یا داده به یک خوشه به خصوص را تعیین می کند.

5.1. الگوریتم k-medoids, PAM(Partitioning Around Medoids)

الگوریتم k-medoids یک نسخه ارتقا یافته از الگوریتم k-means می باشد که medoid نماینده داده یا نقطه ای است که دارای کمترین متوسط ناشباهت یا عدم شباهت در بین تمامی نقاط درون خوشه می باشد. هدف از این مدل حداقل کردن هزینه کلی برای هر خوشه می باشد. بر خلاف الگوریتم k-mean این الگوریتم از medoid به عنوان یک شاخص اندازه گیری برای تعریف مجدد مرکز یا Centroid خوشه استفاده می کند. Medoids حساسیت کمتی به داده های پرت دارد. این Medoid ها مشاهدات واقعی از خود داده های dataset هستند و نقاط محاسباتی که بر اساس داده ها به دست آمده باشند، نیستند دقیقا بر خلاف حالتی که در الگوریتم هایی همچون k-means وجود دارد. در این الگویتم ترجیح آن است که از فاصله منهتن به جای اقلیدوسی استفاده شود زیر حساسیت کمتری به داده های پرت نشان می دهد.

6.1. الگوریتم k-Medians

این الگویتم نیز یک ورژن ارتقا یافته از الگوریتم k-means می باشد که از میانه به عنوان نقطه میانی یا مرکزی یا Centroid خوشه استفاده می کند. میانه حساسیت کمتری به داده های پرت به نسبت میانگین نشان می دهد.

7.1. الگوریتم k-Modes

به دلیل آنکه الگوریتم k-means تنها بر روی داده های عددی اعتبار داشته و قابل اجا می باشد، یک نسخه تغییر یافته از الگویتم k-means ایجاد شده که بر روی داده های فهرستی یا Categorical نیز قابل اجرا می باشد. در این مدل به جای میانگین از مد استفاده می شود و برای تعیف مرکز خوشه به جای میانگین از مد استفاده می شود. در هر صورت امکان تبدیل داده های فهرستی به داده های عددی و سپس استفاده از الگویتم k-means نیز وجود دارد. این حالت در واقعی که داده ها دارای ابعاد کوچکی هستند، امان پذیر است. اما تبدیل بین انواع مختلف داده ها متضمن خوشه بندی با کیفیت برای داده های با ابعاد بزرگ نیست. بنابراین پیشنهاد می شود که از الگوریتم k-mode برای خوشه بندی داده های فهرستی استفاده شود.

8.1. الگوریتم k-prototypes

این روش بر اساس ترکیب و تلفیقی از داده های عددی و فهرستی کار می کند. این الگوریتم را می توان ترکیبی از الگریتم k-means و k-modes در نظر گرفت. با استفاده از این الگوریتم، هر نقطه دارای وزن تعلق به خوشه های عددی و فهرستی می باشد. علاوه بر آن، هر نوع مشاهده را می توان به صورت مجزا مد نظر قرار داد به طوری که نقطه مرکزی یا Centroid نقش جاذب را در هر خوشه ایفا می کند. درجه عضویت به هر نقطه از داده ها را می توان با استفاده از یک تابع عضویت فازی همچون روش Fuzzy Clustering محاسبه نمود.

9.1. الگوریتم CLARA (clustering large applications)

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

10.1. الگوریتم CLARANS (Clustering Large Applications based on Randomized Search)

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

2. الگوریتم های خوشه بندی توزیع-مبنا (Distribution Clustering Algorithms)

1.2. الگوریتم GMM: Gaussian Mixture model

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

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

2.2. الگوریتم EM: Expectation-Maximization in the context of clustering

این یک الگوریتم شناخته شده برای برازش توزیع های مختلطی است که قصد دارند پارامترهای یک توزیع فرضی ا با استفاده از مفاهیم و مبانی حداکثر شباهت (Maximum Likelihood) برآورد کنند در مواقعی که برخی از نقاط داده ها در دسترس نباشند. در زمینه GMM، فرض این است که به طور تصادفی k مدل گاوسی را در فضا قرار دهیم و میزان تعلق هر نقطه داده به یک مدل گوسی خاص را محاسبه کنیم. ب خلاف خوشه بندی سخت (Hard Clustering) این متد احتمالات برای هر نقطه برای داشتن تعلق به یک خوشه خاص را پیدا می کند. بعدتر این مقادیر برای برآورد مجدد پارامترهای مربوط به خوشه ها مود استفاده قار می دهد تا نهایتا هر نقطه را به هر خوشه اختصاص دهد. روش EM به طور گسترده برای حل مسائلی همچون مشکل داده های پنهان (Hidden-data) و مدل های مارکو پنهان مورد استفاده قرار می گیرد که در این موارد توالی از متغیرهای پنهان وجود دارد که وابسته به حالت متغیرهای مخفی قبلی هستند. علاوه بر این، هر مشاهده وابسته به وضعیت متغیر مخفی مربوط به خودش می باشد.

3.2. الگوریتم DMM: Dirichlet Mixtures Models

فرایند Dirichlet یک فایند تصادفی است که یک توزیع آمای بر اساس توزیع گسسته ایجاد می کند و برای تعریف مدل های بیزین ناپارامتریک مورد استفاده قرار می گیرند. توزیع Dirichlet یک تابع چگالی چند متغیره پیوسته است که پارامترهای متمرکز و دقیق پارامتر بندی شده اند و داای مولفه های مثبت و توزیع پایه H: DP (a, H) می باشند. این توزیع شبیه توزیع بتا برای پیش آمدهای بیش از دو حالت است.

3. الگوریتم های خوشه بندی چگالی-مبنا (Density-based Clustering Algorithms)

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

1.3. الگوریتم DBSCAN: Density-Based Spatial Clustering of Applications with Noise

این روش خوشه بندی در بین روش های خوشه بندی چگالی-محور دارای بیشتین ارجاع یا Citation در Google Scholar با بیش از 41k می باشد. ایده اصلی این الگوریتم در قطعه بندی مشاهدات در سه گروه از نقاط می باشد:

1- نقاط هسته ای (Core points): نقاطی بیش از مینیمم نقاط در حول شعاع (minPts) در مجاورت e وجود دارد.

2- نقاط مرزی (Boundary Points): کمتر از minPts در مجاورت e اما در مجاورت نقاط هسته ای هستند.

3- نقاط پرت یا نویز (Noise or Outlier points): همه نقاط باقیمانده شامل این دسته می شوند. نقاطی که نه جز نقاط هسته ای و نه جز نقاط مرزی هستند. 

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

2.3. الگوریتم ADBSCAN: Adaptive DBSCAN

به طوری که از نام این الگویتم بر می آید با الگوریتم قبلی متفاوت است به این صورت که  مقادیر Eps و MinPts را به نمایندگی از توزیع چگالی برای هر خوشه تطبیق می دهد. این الگوریتم به صورت خودکار مقادیر مناسب برای Eps و MinPts را پیدا می کند. این الگوریتم ابتدا به صوت تصادفی مقداری برای Eps انتخاب می کند. سپس DBSCAN را بر روی داده ها اجرا می کند و در صورتی که در یافتن خوشه Fail شود، مقدار Eps را با گام های 0.5 افزایش می دهد. این الگوریتم روند افزایش مقدار Eps را ادامه می دهد تا خوشه بعدی را پیدا کند هنگامی که الگوریتم به صورت موفقیت آمیز اسکن 95 درصی داده ها را به اتمام رساند داده هی بای مانده به عنوان داده های پرت در نظر گرفته می شوند. در هر حال ADBSCAN نیازمند یک مقدار اولیه برای تعداد خوشه ها می باشد.

3.3. الگوریتم DENCLUE: Density- based Clustering

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

4.3. الگوریتم OPTICS

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

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

برچسب ها:

مطالب زیر را حتما مطالعه کنید

چرا پنجره اتمسفری در علوم زمین دارای اهمیت است ؟

تصاویر ماهواره DigitalGlobe: ووردویو(Worldview)، ژئوآی(GeoEye) و آیکونوس (IKONOS)

راهنمای طبقه بندی نزدیکترین همسایه در e-Cognition

نقشه های کروپلت – مقدمه ای بر طبقه بندی داده

تصاویر چند طیفی (Multi-spectral) در مقایسه با تصاویر ابر طیفی (Hyper-spectral)

فتوگرافی هوایی (Aerial Photography) در مقابل ارتوفوتوگرافی (Orthophotography)

دیدگاهتان را بنویسید

Copy Protected by Chetan's WP-Copyprotect.

با عضویت در خبرنامه از آموزش های جدید رایگان در ایمیل خود مطلع شوید