بخشی از مقاله
چکیده
یکی از مهمترین اعمال در داده کاوی خوشه بندی داده های موجود در یک دیتاست می باشد. این تکنیک به دنبال کشف ساختارهایی بوده که منجر به گروه بندی نمونه های موجود در یک پایگاه داده بوده، به گونه ای که نمونه های مشابه درون دسته هایی که بیشترین شباهت را با هم داشته قرار گرفته، در حالی که دارای تفاوتی قابل قبول با نمونه های سایر گروه ها داشته باشند. الگوریتم های خوشه بندی را می توان به چند دسته کلی الگوریتم های خوشه بندی تفکیکی، سلسله مراتبی، مبتنی بر چگالی و مبتنی بر گرید تقسیم نمود.
این تحقیق ابتدا به مرور روشهای خوشه بندی مطرح پرداخته و چند الگوریتم از هر روش را معرفی کرده است. در ادامه همچنین به معرفی روشهای دیگری از جمله روشهای خوشه بندی مبتنی بر الگوریتم های فرا ابتکاری و خوشه بندی های آنلاین پرداخته شده و سپس چالشهای موجود در خوشه بندی از قبیل انتخاب تعداد بهینه خوشه ها، کاهش ابعاد، مدیریت داده های پرت و روشهای مقابله با آنها معرفی شده اند. در نهایت روشها و الگوریتم های موجود از نظر برخی از پارامترها مقایسه شده و به بررسی مزایا و معایب هر الگوریتم پرداخته شده است.
مقدمه ای بر داده کاوی
جامعه در دنیای امروز جامعه اطلاعاتی نامیده شده وجامعه مبتنی بر اطلاعات را می توان به عنوان جامعه ای تعریف نمود که در آن بخش غالب اجتماع به جای در گیر بودن با کارهای فیزیکی در گیر کارهای فکری هستند. واضح است که در چنین جامعه ای بیشترین توجه به فعالیت های اطلاعاتی از قبیل فراهم اوری، پردازش، تولید، ثبت، انتقال، اشاعه و مدیریت اطلاعات مبذول گردیده و بیشترین هزینه ها صرف فرایندهای اطلاعاتی شود.
با گسترش سیستم های پایگاه داده و حجم بسیار بالای داده های ذخیره شده در این سیستم ها، نیاز به ابزار قدرتمندی که بتواند این حجم عظیم داده ها را پردازش کرده و اطلاعات حاصل از آنها را در اختیار کاربران قرار داده بیشتر احساس می شود. داده کاوی دانشی است که با ان می توان الگوهای مفیدی را در میان داده ها تشخیص داده و استخراج کرد. داده کاوی با حداقل دخالت کاربر و استفاده از بخشی از علم آمار به نام تحلیل اکتشافی داده ها اطلاعات ناشناخته و نهفته درون حجم عظیمی از داده ها را استخراج و در اختیار تحلیل گران قرار داده تا بتوانند براساس این اطلاعات تصمیمات مهم و حیاتی اتخاذ نمایند.
علاوه بر این داده کاوی با هوش مصنوعی و یادگیری ماشین نیز ارتباط تنگاتنگی داشته که این ارتباط موجب ترکیب تئوری های پایگاه داده ها، هوش مصنوعی، یادگیری ماشین و علم آمار شده تا زمینه های کاربردی آن فراهم شود. امروزه داده کاوی در بسیاری از حوزه های خصوصی و عمومی رایج شده و استفاده می گردد. حوزه هایی مانند بانکداری، بیمه، پزشکی و تجارت به طور گسترده برای کاهش هزینه ها، افزیش تولید و فروش و همچنین گسترش دامنه تحقیقاتی خود از داده کاوی استفاده می کنند . - Jeffery W, 2004 - - Paul S, 1998 - در داده کاوی اغلب با حجم بزرگی از داده ها مواجه بوده که این حجم عظیم داده ها و به تنهایی قابل استفاده نبوده بلکه دانش نهفته شده در آنها مورد توجه است.
بنابراین بهره گیری از قدرت فرایند داده کاوی جهت شناسایی الگوها و مدلها و نیز ارتباط عناصر مختلف در پایگاه داده جهت کشف دانش نهفته در داده ها و نهایتا تبدیل داده به اطلاعات، روز به روز ضروری تر می شود. با در نظر گرفتن تمام ویژگی های موجود و قابلیت های بالای داده کاوی، موارد مهم دیگری نیز وجود دارند که می توانند تاثیر زیادی در ایجاد یک نتیجه مطلوب و موفق داشته باشند. از جمله این موارد می توان به کیفیت داده ورودی، کارایی نرم افزار بکارگرفته شده، دقت پایگاه داده، نویز و داده های پرت اشاره کرد. - Jeffery .W, 2004 -
در این تحقیق ابتدا مروری بر خوشه بندی، روشهای مختلف آن و و چند نمونه از الگوریتمهای مربوط به هر روش پرداخته می شود. برای تعیین میزان کارایی یک الگوریتم خوشه بندی معیارهایی وجود داشته که از جمله این معیارها تعیین بهینه ترین تعداد خوشه ها برای هر مجموعه داده بوده که در بخش بعدی به بررسی برخی از روشهای موجود جهت تعیین تعداد خوشه بهینه مورد بررسی قرار گرفته است. سپس به چالشهایی که در روشهای مختلف خوشه بندی ممکن است ایجاد شود پرداخته شده و در نهایت مزایا و معایب الگوریتمهای متفاوت بررسی و روشهای متفاوت با هم مقایسه گردیده اند.
خوشه بندی
داده ها و الگوهای قابل استخراج از بین آنها از مهمترین شاخصهای دنیای اطلاعات هستند و خوشه بندی یکی از بهترین روشهایی است که برای کار با داده ها و این الگوها ارائه شده است. قابلیت خوشه بندی در ورود به فضای داده و تشخیص ساختار آنها، آنرا به یکی از ایده ال ترین مکانیزم ها برای کار با دنیای عظیم داده ها کرده است. خوشه بندی یکی از شاخه های یادگیری بدون نظارت می باشد و فرایند خودکاری است که در طی آن، نمونه ها به دسته هایی که اعضای آن مشابه یکدیگر می باشند تقسیم می شوند و به این دسته ها خوشه گفته میشود.
بنابراین خوشه مجموعه ای از نمونه داده های مشابه هم بوده که داده های موجود در آن با داده های موجود خوشه های دیگر غیر مشابه می باشند. معیار های تشابه مختلفی برای مشابهت نمونه های داده در یک خوشه می توان در نظر گرفت که از مهمترین آنها می توان به معیار فاصله اشاره کرد. این معیار اشیائی را که به یکدیگر نزدیکتر هستند را بعنوان یک خوشه در نظر گرفته که به این نوع خوشه بندی، خوشه بندی مبتنی بر فاصله نیز گفته می شود.
محاسبه فاصله بین دو داده ها در خوشه بندی بسیار مهم هست. فاصله که همان معرف عدم تجانس است به ما کمک می کند در فضای داده ای حرکت کنیم و خوشه ها را تشکیل دهیم. با محاسبه فاصله بین دو داده می توان فهمید که چقدر این دو داده به هم نزدیک هستند و بر این اساس انها را در یک خوشه قرار بدهیم. توابع ریاضی مختلفی برای محاسبه فاصله وجود دارند که در ادامه مطالب به آنها اشاره خواهد شد . - 6 - همانطور که قبلا ذکر شد در واقع عمل خوشه بندی یک دسته بندی و کلاسیفای کردن بدون نظارت داده ها می باشد که در آن کلاسها از قبل تعریف نشده اند. اگر بخواهیم تفاوت های بین خوشه بندی و دسته بندی داده ها را بررسی کنیم موارد زیر قابل ذکر هستند:
· Classification یک مسئله با یادگیری با ناظر بوده اما clustering یک یادگیری بدون ناظر است.
· Classification یک نوع یادگیری بر پایه مثال بوده در حالی که Classification یادگیری بر پایه مشاهده می باشد.
· در Classification هم داده ورودی مشخص بوده و هم خروجی هدف - Input, Target - وجود داشته و بقیه داده ها بر همین اساس گروه بندی می شوند ولی در خوشه بندی فقط ورودی ها - Input - وجود داشته و بر اساس شباهتهای بین این ورودی ها باید آنها را گروه بندی کرد. در مجموع شاید نشود یک تقسیم بندی صحیح از روشهای خوشه بندی ایجاد کرد زیرا اغلب این روشها در برخی از موارد با هم همپوشانی داشته و رفتارهای موجود در یک الگوریتم در الگوریتم دیگر هم به شکلی دیگر مشاهده می شود. اما در حال حاضر روشهای متعددی برای خوشه بندی دادهها وجود داشته که این روشها بر اساس نوع ، شکل و فاصله دادهها عمل خوشه بندی را انجام میدهند. در ادامه به مهمترین روشهای خوشه بندی اشاره می شود - دکتر جمال شهرابی، . - Pavel Berkhin
