در کنفرانس بین المللی داده کاوی تلاشی صورت گرفت تا الگوریتم های داده کاوی مطرح وپرقدرتی که مورد استفاده قرار میگیرند شناسایی شوند. و در مرحله بعد از یک سری کسانی که جایزه IEEE را در تحقیقات و نوآوری کسب کرده بودند دعوت شد تا حداکثر ده الگوریتم قوی و مطرح در داده کاوی را به عنوان کاندیدا معرفی کنند. ۱۰ الگوریتم زیر از بین چندین الگوریتم قدرتمند انتخاب شده اند که به توضیح مختصری از هرکدام می پردازم .
این الگوریتم ها عبارت اند از:
۱. C4.5
۲. k-means
۳. Support vector machines
۴. Apriori
۵. EM
۶. PageRank
۷. AdaBoost
۸. kNN
۹. Naive Bayes
۱۰. CART
۱. الگوریتم C4.5 :
الگوریتم C4.5 یک دسته‌بندی (classifier) را در قالب یک درخت تصمیم تولید می‌کند که دارای ۲ نوع گره است. یک گره به‌صورت برگ که یک دسته را مشخص می‌کند و یک گره تصمیم که آزمون‌هایی روی یک صفت انجام می‌دهد تا یک شاخه یا زیر درخت به ازای هر خروجی آزمون تولید می‌کند. حالا
classifier چیست؟
واژه classifier مفهومی فراتر و کلی تر از کلاس را دارد که علاوه بر کلاس، واسط ها و انواع داده ای را نیز پوشش می دهد.
الگوریتم C4.5 بهینه شده الگوریتم ID3 می باشد که از قانون هرس بعدی بهره می برد و می تواند صفاتی را که داده های نویزی و مقدار و همچنین صفات گسسته ندارند، استفاده نماید. در C4.5 فرض بر این است که کل داده های آموزشی در داخل حافظه باشند.
به جهت ساخت درخت تصمیم، فرض می کنیم که مجموعه داده های آموزشی که دارای برچسب کلاس مربوطه و بردار ویژگی ها هستند، در دسترس می باشند. معیارهای گوناگونی برای تقسیم بندی گره ها در درخت تصمیم وجود دارد که از عمومی ترین آنها، معیار ضریب بهره اطلاعات است که در C4.5 به کار می رد.
درخت تصمیم بر پایه آنالیز داده های ورودی و برای یافتن یک ویژگی بر مبنای تصمیم گیری برای هر نود استفاده می شود. ویژگی های گوناگونی از داده در هر نود بررسی می شود و یک ویژگی که اگر انتخاب شود، باعث خواهد شد که بی نظمی (آنتروپی) کاهش یابد، گزینش می شود. مبنای فعالیت نیز بر این اساس ایجاد شده است.
۲. الگوریتم k-means :
این روش علی‌رغم سادگی آن‌یک روش پایه برای بسیاری از روش‌های خوشه‌بندی دیگر محسوب می‌شود. این روش روشی انحصاری و مسطح محسوب می‌شود. برای این الگوریتم شکل‌های مختلفی بیان‌شده است. ولی همه آنها دارای روالی تکراری هستند که برای تعدادی ثابت از خوشه‌ها سعی در تخمین موارد زیر دارند:
به دست آوردن نقاطی به‌عنوان مراکز خوشه‌ها این نقاط درواقع همان میانگین نقاط متعلق به هر خوشه هستند.
نسبت دادن هر نمونه داده به یک خوشه که آن داده کمترین فاصله تا مرکز آن خوشه را دارا باشد.
مشکلات روش خوشه‌بندی K-Means
علی‌رغم اینکه خاتمه پذیری الگوریتم بالا تضمین‌شده است ولی جواب نهایی آن واحد نبوده و همواره جوابی بهینه نمی‌باشد. به‌طورکلی روش ساده بالا دارای مشکلات زیر است.
جواب نهایی به انتخاب خوشه‌های اولیه وابستگی دارد.
روالی مشخص برای محاسبه اولیه مراکز خوشه‌ها وجود ندارد.
اگر در تکراری از الگوریتم تعداد داده‌های متعلق به خوشه‌ای صفر شد راهی برای تغییر و بهبود ادامه روش وجود ندارد. در این روش فرض شده است که تعداد خوشه‌ها از ابتدا مشخص است. اما معمولاً در کاربردهای زیادی تعداد خوشه‌ها مشخص نمی‌باشد.
۳. الگوریتم Support vector machines :
ماشین بردار پشتیبانی (Support vector machines – SVMs) یکی از روش‌های یادگیری بانظارت است که از آن برای طبقه‌بندی و رگرسیون استفاده می‌کنند.
این روش ازجمله روش‌های نسبتاً جدیدی است که در سال‌های اخیر کارایی خوبی نسبت به روش‌های قدیمی‌تر برای طبقه‌بندی ازجمله شبکه‌های عصبی پرسپترون نشان داده است. مبنای کاریدسته‌بندی کننده SVM دسته‌بندی خطی داده‌ها است و در تقسیم خطی داده‌ها سعی می‌کنیم خطی را انتخاب کنیم که حاشیه اطمینان بیشتری داشته باشد.
حل معادل پیدا کردن خط بهینه برای داده‌ها به‌وسیله روش‌های QP که روش‌های شناخته‌شده‌ای در حل مسائل محدودیت دار هستند صورت می‌گیرد.
قبل از تقسیمِ خطی برای اینکه ماشین بتواند داده‌های با پیچیدگی بالا را دسته‌بندی کند داده‌ها را به‌وسیلهٔ تابعِ phi به فضای با ابعاد خیلی بالاتر می‌بریم.
برای اینکه بتوانیم مسئله ابعاد خیلی بالا را با استفاده از این روش‌ها حل کنیم از قضیه دوگانی لاگرانژ برای تبدیلِ مسئلهٔ مینیمم‌سازی موردنظر به فرم دوگانی آن‌که در آن به‌جای تابع پیچیدهٔ phi که ما را به فضایی با ابعاد بالا می‌برد، تابعِ ساده‌تری به نامِ تابع هسته که ضرب برداری تابع phi است ظاهر می‌شود استفاده می‌کنیم. از توابع هسته مختلفی ازجمله هسته‌های نمایی، چندجمله‌ای و سیگموید می‌توان استفاده نمود.
۴. الگوریتم Apriori:
آپریوری یک الگوریتم کلاسیک برای یادگیری قوانین وابستگی است. آپریوری روی پایگاه‌های داده شامل تراکنش‌ها (مثلاً مجموعه محصولات خریداری شده توسط مشتریان در یک سوپرمارکت) ساخته شده‌است. الگوریتم‌های دیگری نیز در این زمینه وجود دارند که روی پایگاه داده‌هایی کار می‌کنند که یا شامل تراکنش نیستند (Winepi و Minepi) و یا دارای ثبت زمانی نیستند (DNA sequencing).
ورودی این الگوریتم مجموعه‌ای از مجموعه آیتم‌ها است. الگوریتم تلاش می‌کند تا زیرمجموعه‌هایی از آیتم‌ها را که حداقل بین C مجموعه آیتم مشترک است بیابد. آپریوری یک الگوریتم پایین به بالا است، آنگونه که در هر مرحله یک آیتم به زیرمجموعه‌های مکرر اضافه می‌شود. مجموعه کاندیدها روی داده مورد ارزیابی قرار میگیرند. شرط خاتمه الگوریتم، عدم وجود شیوه توسعه موفق دیگری است.
هدف الگوریتم آپریوری، یافتن وابستگی‌ها بین مجموعه‌های مختلف از داده‌است. گاهی به آن، تحلیل سبد خرید هم می‌گویند. هر مجموعه‌ای از داده تعدادی آیتم دارد و تراکنش نامیده می‌شود.
۵. الگوریتم EM:
الگوریتم امید ریاضی-بیشینه‌سازی (EM) یک روش تکرارشونده (iterative) است که به دنبال یافتن برآوردی با بیشترین درست نمایی برای پارامترهای یک توزیع پارامتری است. این الگوریتم روش متداول برای زمان‌هایی است که برخی از متغیرهای تصادفی پنهان هستند.
۶. الگوریتم PageRank:
پیج‌رنک یا رتبه صفحه (به انگلیسی: PageRank) به فناوری گفته می‌شود که بر پایه آن موتورهای جستجویی همچون گوگل وب‌گاه‌هایی که به هدف جستجوگر نزدیک‌ترند را در رده‌های بالاتری نسبت به دیگران قرار می‌دهد. اصطلاح انگلیسی این مفهوم به دنبال لری پیج نویسنده اولیه این الگوریتم و از مؤسسین اولیه گوگل نام‌گذاری شده است.
به این روش کاربرانی که کلمه ویژه‌ای را جستجو می‌کنند می‌توانند ابتدا وب‌گاه‌هایی را ببینند که هم به خواسته آنها نزدیک‌تر است و هم بازدید بیشتری داشته است.
پیج رنک که به‌اختصار PR می‌گویند برای اولین بار در سال ۱۹۹۶ میلادی توسط Sergey Brin ابداع گردید، پیج رنک نتیجه تجزیه‌وتحلیل لینک‌های ورودی به یک سایت است، پیج رنک رتبه‌ای است که گوگل برای یک سایت بین اعداد ۰ تا ۱۰ در نظر می‌گیرد. هرقدر این عدد نزدیک به ۱۰ باشد نشان‌دهنده این است که این سایت لینک‌های ورودی زیادی دارد و سایتهای زیادی به این سایت لینک داده‌اند.
روش دیگر موتورهای جستجو، پردازش رتبه صفحه، با استفاده از تعداد یافته‌های خود در سایتهای اینترنتی می‌باشد. این روش، یک فناوری زیرساخت برای پدیدار گشتن «بمب گوگلی» نیز بود. ناگفته نماند که هدف از ساختن «بمب‌های گوگلی» بالاتر رفتن رتبه یک وبلاگ یا وب‌گاه در موتور جستجوی گوگل می‌باشد که معمولاً با همکاری گروه‌های مردمی ایجاد می‌شود.
البته به‌جز گوگل شرکت‌های دیگری هم به رتبه دهی به سایتها می‌پردازند، که یکی از آنها الکسا (به انگلیسی: Alexa) (یک سایت معتبر بین‌المللی و دارای نمودار رتبه جهانی برای سایتها می‌باشد) نام دارد که الگوریتم بالا بردن رتبه سایتها را بر اساس تعداد درست بازدیدکنندگان انجام می‌دهد. این رتبه‌بندی شماره‌ای بین ۱ تا چند میلیون می‌باشد که هرچه این شماره به یک نزدیک‌تر باشد رتبه وب‌سایت شما بالاتر می‌باشد.
۷. الگوریتم AdaBoost:
آدابوست مخفف بوستینگ تطبیقی بوده و یک الگوریتم یادگیری ماشین است که توسط یاو فروند و رابرت شاپیر ابداع شد. درواقع آدابوست یک متا الگوریتم است که بمظور ارتقاء عملکرد، و رفع مشکل رده‌های نامتوازن همراه دیگر الگوریتم‌های یادگیری استفاده می‌شود. در این الگوریتم، طبقه بند هر مرحله جدید به نفع نمونه‌های غلط طبقه‌بندی‌شده در مراحل قبل تنظیم می‌گردد.
۸. الگوریتم kNN:
جستجوی نزدیک‌ترین همسایه یا Nearest Neighbor، که همچنین با نامه‌ای جستجوی مجاورت، جستجوی همسانی یا جستجوی نزدیک‌ترین نقطه شناخته می‌شود، یک مسئله بهینه‌سازی برای پیدا کردن نزدیک‌ترین نقطه‌ها در فضاهای متریک است. مسئله بدین‌صورت است که: مجموعه S شامل تعدادی نقطه در یک فضای متریک مانند M و نیز یک نقطهٔ پرس و جوی q∈ M داده‌شده است، هدف پیدا کردن نزدیک‌ترین نقطه در S به q است.
در بسیاری از موارد، فضای M به‌صورت یک فضای اقلیدسی d-بعدی و فاصله بین نقاط با معیار فاصله اقلیدسی، فاصله منهتن یا دیگر فاصله‌های متریک سنجیده می‌شود.
جستجوی k نزدیک‌ترین همسایه، K همسایه نزدیک‌تر به نقطه پرس‌وجو را برمی‌گرداند. این روش معمولاً در تجزیه‌وتحلیل پیش‌بینی، به‌منظور تخمین و یا دسته‌بندی یک نقطه بر اساس اجماع همسایگان آن استفاده می‌شود. گراف k نزدیک‌ترین همسایه گرافیست که در آن هر نقطه در گراف K نزدیک‌ترین همسایگان خود متصل است.
۹. الگوریتم Naive Bayes:
به طور ساده روش بیز روشی برای دسته بندی پدیده‌ها، بر پایه احتمال وقوع یا عدم وقوع یک پدیده‌است.
بر اساس ویژگی‌های ذاتی احتمال (به‌ویژه اشتراک احتمال) نایو بیز (به انگلیسی: Naive Bayes classifier) با دریافت تمرین اولیه نتایج خوبی ارائه خواهد کرد. شیوه یادگیری در روش نایو بیز از نوع یادگیری با ناظر (به انگلیسی: Supervised learning) است.
برای نمونه یک میوه ممکن است پرتغال باشد. اگر نارنجی و کروی با شعاع حدود ده سانتی‌متر باشد. اگر این احتمالات به‌درستی به همدیگر وابسته باشند نایو بیز در تشخیص اینکه این میوه پرتغال است یا نه به‌درستی عمل خواهد کرد.
برنامه‌های کاربردی بسیاری هستند که پارامترهای نایو بیز را تخمین می‌زنند، بنابراین افراد بدون سروکار داشتن با تئوری بیز می‌توانند از این امکان به‌منظور حل مسائل موردنظر بهره ببرند. باوجود مسائل طراحی و پیش‌فرض‌هایی که در خصوص روش بیز وجود دارد، این روش برای طبقه‌بندی کردن بیشتر مسائل در جهان واقعی، مناسب است.
۱۰. الگوریتم CART:
این روش که موجب تشکیل یک درخت تصمیم با تقسیمات دوتایی می‌گردد، توسط بریمن و همکارانش در سال ۱۹۸۴ به‌طور کامل معرفی شد. این روش برای متغیرهای کمی طراحی گردیده ولی قابل‌استفاده برای هر نوع متغیری است. بر اساس این الگوریتم، نرم‌افزار آماری تحت نام CART نیز ساخته‌شده است که از شناخته‌شده‌ترین برنامه‌ها است.
بدون دیدگاه