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

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

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

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

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

ابتدا داده کاوی را در یک جمله شرح می دهیم:

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

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

داده کاوی چیست ؟

حال به سراغ الگوریتم های داده کاوی می رویم

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

1) الگوریتم‌های طبقه‌بندی(Classification algorithms)

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

2) الگوریتم‌های رگرسیون(Regression algorithms)

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

3) الگوریتم‌های دسته‌بندی(Segmentation algorithms)

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

4) الگوریتم‌های وابستگی(Association algorithms)

کشف روابط و وابستگی میان ویژگی های مختلف متغییرها بر عهده این الگوریتم ها است. این الگوریتم ها به دنبال این هستند که دریابند کدام متغییر ها و ویژگی ها به هم وابسته هستند و وابستگی آنها به چه شکل است.

5) الگوریتم‌های تحلیل زنجیره‌ای(Sequence analysis algorithms)

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

تمامی الگوریتم های داده کاوی جز 5 دسته بالا قرار دارند.

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

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

این 10 الگوریتم به شرح زیر می باشند :

• (K Nearest Neighbor (KNN
• (Classification And Regression Trees (CART
• Naive Bayes
• Pagerank
• AdaBoost
• Support Vector Machines
• C 4.5
• K-Means
• Apriori
• Expectation–Maximization

الگوریتم K Nearest Neighbor

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

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

الگوریتم CART

نام کامل این الگوریتم Classification And Regression Trees یا همان درخت تصمیم دسته بندی و رگرسیون است. درخت تصمیم انواع مختلفی دارد مانند همین CART  ، C4.5 و ID3 . تفاوت اصلی میان این درخت های تصمیم ، معیار انتخاب صفت آنها است. صفتی که بر اساس آن درخت شروع به تقسیم شدن می کند و جلو می رود. شاخص انتخاب صفت در درخت CART ، شاخص Gini Index است .  اولین بار این الگوریتم توسظ بریمن و همکارانش در سال 1984 معرفی شد و تا به امروز ما شاهد استفاده وسیع از این الگوریتم توانمند هستیم. در اصل این الگوریتم برای متغییر های کمی است اما در عمل برای هر نوع متغییری می تواند استفاده شود. با توجه به معیار Gini Index ، این الگوریتم بیشتر به سمت صفات چند مقداری متمایل است.

الگوریتم Naive Bayes

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

الگوریتم Page Rank

الگوریتم page rank در سال 1996 توسط لری پیج و سرگی برین (دو تن از بنیان گذاران گوگل ) توسعه پیدا کرده است. بر اساس این الگوریتم یک سری ویژگی ها و لینک های ورودی به یک سایت، امتیاز دهی می شود و سایت ها بر اساس آنها رتبه بندی می شوند. در این صورت کاربر هنگام جست و جو کلمه مورد نظر ، به سایتی بر میخورد که در زمینه جست و جود شده بیشترین امتیاز را دارد و کاربر به هدف نزدیک تر می شود. کاربرد این الگوریتم برای گوگل به حداقل رسیده و گوگل به سمت الگوریتم های دیگر رفته است. برای آشنایی به جدید ترین الگوریتم های گوگل به آموزش زیر مراجعه کنید :

الگوریتم های گوگل بخش اول

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

الگوریتم های گوگل بخش سوم

الگوریتم های گوگل بخش چهارم

الگوریتم AdaBoost

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

الگوریتم Support Vector Machines

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

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

• آنالیز ریسک
• کنترل اتوماتیک هواپیما
• سیستم بازرسی کیفیت
• مدیریت و برنامه ریزی
• کاهش هزینه بیمارستان
• سیستم های مسیریابی
• ارزیابی سرمایه
• تشخیص بیماری
• سیستم های تشخیص ترمز کامیون
• آنالیز بازار
• پیش بینی فروش آینده
• بازرسی اسناد
• تشخیص هدف
• پیش بینی شاخص اقتصادی
• پیش بینی هوا
• و….

الگوریتم C4.5

الگوریتم c4.5 یک نوع از الگوریتم درخت تصمیم است که جانشین الگوریتم درخت تصمیم ID3 است. معیار انتخاب صفت این الگوریتم gain ratio است که توسط یک فرمول محاسبه می شود و صفتی که بیشترین gain ratio را داشته باشد به عنوان صفت تقسیم کننده درخت استفاده می شود. این الگوریتم جز الگوریتم های طبقه بندی است . الگوریتم c4.5 می تواند از صفاتی که داده های نویزی دارند و صفات آنها گسسته نیست ، استفاده نماید.

الگوریتم K-Means

ایده اولیه الگوریتم K-Means اولین بار توسط هوگو استینگز در سال 1957 معرفی شد.

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

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

الگوریتم Apriori

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

الگوریتم Expectation–Maximization

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

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

چون هر الگوریتم کار متفاوتی دارد و وظیفه خود را به خوبی انجام می دهد.

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

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

شاد و پیروز باشید.