داده کاوی^[۲] در یک تعریف ساده فرآیندی جهت کشف دانش از مجموعه‏های داده‏ای بزرگ می‏باشد. در بسیاری از موارد، اصطلاح داده کاوی مترادف با عبارت کشف دانش از داده^[۳] بکار می‏رود، اما در حقیقت داده کاوی یکی از مراحل اصلی کشف دانش است. شکل ۱-۱ . فرایند کشف دانش از داده را نشان می‏دهد و همانطور که مشخص است این فرایند شامل یک دنباله تکراری از مراحل زیر است [۳۷]:
پاکسازی داده‏ها^[۴] (جهت حذف نویز و داده‏های ناسازگار)
یکپارچه سازی داده‏ها^[۵] (مرحله‏ای که چند منبع داده‏ای با هم ترکیب می‏شوند)
انتخاب داده‏ها^[۶] (مرحله‏ای که داده‏های مرتبط با فرایند تحلیل، از پایگاه داده بازیابی می‏شوند)
تبدیل داده‏ها^[۷] (مرحله‏ای که داده‏ها به شکلی مناسب برای انجام تحلیل، تبدیل می‏شوند. به عنوان مثال عملیاتی نظیر خلاصه سازی^[۸] و همسان سازی^[۹] می‏توانند برای تبدیل استفاده شوند)
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

داده کاوی (فرایند اصلی که در آن از روش‏های هوشمند و آماری به منظور استخراج الگوهای داده‏ای استفاده می‏شود)
ارزیابی الگو^[۱۰] (جهت تشخیص الگوهای صحیح و مورد نظر با بهره گرفتن از معیارهای اندازه گیری)
ارائه دانش (مرحله‏ای که از روش‏های نمایش بصری و ارائه دانش جهت نمایش دانش کشف شده به کاربر استفاده می‏شود)
شکل ۱-۱ فرایند کشف دانش از داده [۳۷]
۱-۳- روش‏های داده کاوی
کارهایی که در داده کاوی انجام می‏شود را می‏توان به دو گروه توصیفی^[۱۱] و پیشگویانه^[۱۲] دسته بندی نمود. فعالیت‏های توصیفی می‏توانند ویژگی‏های اصلی داده‏ها را در پایگاه داده نمایان سازند. فعالیت‏های پیشگویانه نیز جهت پیشگویی، بر روی داده‏های موجود، اعمال استنتاجی انجام می‏دهند. برخی از مهمترین روش‏های داده کاوی عبارتند از : دسته ‏بندی^[۱۳]، خوشه‏بندی^[۱۴]، کشف قوانین انجمنی^[۱۵] و تشخیص داده‏های دور افتاده^[۱۶]. از بین روش‏های مطرح شده، خوشه‏بندی و کشف قوانین انجمنی فعالیت توصیفی ودسته‏بندی و تشخیص داده‏های دور افتاده فعالیت پیشگویانه محسوب می‏شوند.
۱-۴- خوشه‏بندی
تحلیل خوشه یکی از فعالیت‏های مهم انسان می‏باشد. در کودکی ما با بهبود ناخود آگاه خوشه‏بندی در ذهنمان یاد می‏گیریم که چگونه بین سگ‏ها و گربه‏ها، یا حیوانات و گیاهان تفاوت قائل شویم [۳۰]. خوشه‏بندی اغلب به عنوان اولین گام و یکی از مهمترین روش‏های تحلیل داده‏ها بشمار می‏آید. خوشه‏بندی فرآیندی است که در آن اشیاء در گروه‏هایی از اشیاء مشابه دسته بندی می‏شوند. هر گروه یا خوشه شامل اشیائی است که شبیه به یکدیگرند و متفاوت از اشیاء گروه‏های دیگر می‏باشند. خوشه‏بندی شکلی از مدل سازی داده است که ریشه در ریاضیات و آمار دارد [۸]. بر خلاف دسته بندی که یک روش یادگیری نظارت^[۱۷] شده است، خوشه‏بندی یک روش یادگیری نظارت نشده^[۱۸] بحساب می‏آید، چرا که داده‏ها در دسته ‏بندی دارای برچسب کلاس^[۱۹] می‏باشند اما در خوشه‏بندی برچسب کلاس برای داده‏ها مشخص نیست. هدف در خوشه‏بندی کمینه سازی فاصله داده‏های درون خوشه و بیشینه سازی فاصله داده‏ها بین خوشه‏های مختلف می‏باشد و از اینرو نوعی مسئله بهینه سازی محسوب می‏شود. برخی مواقع اصطلاحات بخش بندی^[۲۰] و قطعه‏بندی^[۲۱] نیز در تحقیقات مترادف با خوشه‏بندی در نظر گرفته می‏شوند.
انسان‏ها بدون استفاده از روش‏های خلاصه سازی قادر به کشف دانش از انبوه اطلاعاتی که در پایگاه‏داده‏ها قرار دارند، نیستند. آمارهای پایه‏ای (نظیر میانگین و واریانس) یا نمودارهای مقایسه فراوانی^[۲۲] اطلاعات اولیه و اندکی در مورد داده‏ها ارائه می‏دهند. اما تحلیل خوشه یا خوشه‏بندی می‏تواند روابط پیچیده‏تری را بین اشیاء داده‏ای، بین صفات خاصه داده‏ها و یا بین این دو کشف کند [۶۱].
خوشه‏بندی کاربرد‏های گسترده‏ای در هوش مصنوعی، زیست شناسی، مدیریت ارتباط با مشتری^[۲۳]، داده کاوی، یادگیری ماشین، بازاریابی، پزشکی، تشخیص الگو، بازیابی اطلاعات و پردازش تصویر دارد. به عنوان مثال در زیست شناسی، خوشه‏بندی می‏تواند بر مبنای خصوصیات جانداران یک طبقه بندی از گونه‏های مختلف ایجاد کند. کاربرد دیگر خوشه‏بندی، درک بهتر عملکرد ژن‏ها در فرآیندهای زیستی یک سلول است [۶۱]. در تجارت، خوشه‏بندی به فروشنده‏ها کمک می‏کند تا گروه‏های متفاوتی از مشتریان را بر اساس الگوهای خریدشان کشف کنند. خوشه‏بندی می‏تواند در تشخیص گروه‏هایی از خانه‏ها در یک شهر مطابق با نوع خانه، ارزش و موقعیت جغرافیایی و همچنین در تشخیص گروه‏هایی از دارندگان بیمه نامه اتومبیل با متوسط هزینه بالا کاربرد داشته باشد. خوشه‏بندی می‏تواند در گروه بندی نتایج موتورهای جستجو در وب نیز استفاده شود. شکل ۲-۱ ترسیمی دو بعدی از موقعیت مشتریان در یک شهر را نشان می‏دهد که از خوشه‏بندی اطلاعات مربوط به مشتریان یک فروشگاه بدست آمده است [۱].

شکل ۱-۲ ترسیمی دو بعدی از موقعیت مشتریان در یک شهر که شامل سه خوشه داده‏ای می‏شود. مرکز هر خوشه با “+” نشان داده شده است [۳۰].
برخی از چالش‏ها و نیازمندی‏های مطرح در زمینه خوشه‏بندی شامل موارد ذیل می‏شوند[۳۰]:
مقیاس پذیری^[۲۴]: بسیاری از الگوریتم‏های خوشه‏بندی تنها بر روی مجموعه‏های داده‏ای کوچک عملکرد خوبی دارند. اما در عمل یک مجموعه داده‏ای بزرگ ممکن است دارای میلیون‏ها شئ داده‏ای باشد.
قابلیت کار با انواع مختلف صفات خاصه: بسیاری از الگوریتم‏ها برای خوشه‏بندی داده‏های عددی طراحی شده اند. اما در بسیاری از کاربردها نیاز است انواع مختلفی از داده‏ها نظیر داده‏های دودویی، اسمی^[۲۵]، ترتیبی^[۲۶] و یا ترکیبی از آنها خوشه‏بندی شود.
حداقل نیاز به تعیین پارامترهای ورودی: بسیاری از الگوریتم‏های خوشه‏بندی نیازمند تعیین پارامترهای ورودی توسط کاربر هستند (به عنوان مثال تعداد خوشه‏های مورد نظر). نتایج خوشه‏بندی کاملا به این پارامترها وابسته است. تعیین این پارامترها در عمل کار مشکلی می‏باشد.
قابلیت تحمل نویز: برخی از الگوریتم‏های خوشه‏بندی حساس به نویز می‏باشند که این مسئله می‏تواند باعث بدست آمدن خوشه‏هایی با کیفیت پایین شود.
خوشه‏بندی افزایشی و غیرحساس به ترتیب ورود داده‏ها: برخی از الگوریتم‏های خوشه‏بندی نمی‏توانند داده‏های جدید را در خوشه‏های موجود قرار دهند و باید خوشه‏بندی بر روی تمام داده‏ها از ابتدا انجام گیرد. چنین الگوریتم‏هایی به ترتیب ورود داده‏ها حساس می‏باشند. اما برخی دیگر از الگوریتم‏ها به صورت افزایشی عمل می‏کنند و ترتیب‏های مختلف ورود داده‏ها در نتایج آنها تأثیری ندارد.
خوشه‏بندی بر روی مجموعه‏های داده‏ای با ابعاد زیاد: یک پایگاه داده می‏تواند شامل چندین بعد یا صفت خاصه باشد. بسیاری از الگوریتم‏های خوشه‏بندی تنها زمانی عملکرد خوبی دارند که تعداد صفات خاصه در مجموعه داده‏ای کم باشد. خوشه‏بندی بر روی داده‏هایی با صفات خاصه زیاد یک مسئله چالش برانگیر است.
روش‏های موجود در خوشه‏بندی از جنبه‏ه ای مختلفی می‏توانند بررسی شوند. الگوریتم‏های خوشه‏بندی می‏توانند به صورت تقسیم کننده^[۲۷] (بالا به پایین) یا تجمیع کننده^[۲۸] (پایین به بالا) باشند. در روش‏های بالا به پایین ابتدا تمام داده‏ها در یک خوشه واحد قرار می‏گیرند و سپس تا زمان رسیدن به تعداد خوشه‏های مورد نظر، به خوشه‏های مختلف تقسیم می‏شوند. روش‏های پایین به بالا نیز ابتدا هر یک از داده‏ها را در یک خوشه مجزا قرار می‏دهند و سپس خوشه‏ها به صورت پی در پی در هم ادغام می‏شوند. به چنین الگوریتم‏هایی، الگوریتم‏های سلسله مراتبی^[۲۹] نیز گفته می‏شود. نوع دیگری از الگوریتم‏های خوشه‏بندی روش‏های بخش بندی می‏باشند. این روش‏ها به دو گروه عمده تقسیم می‏شوند : ۱) گروهی که هر خوشه را با استفاده مرکز ثقل اشیاء داده‏ای موجود در آن نشان می‏دهند^[۳۰]. مطرح ترین الگوریتم این گروه، الگوریتم معروف k-means می‏باشد [۳۲،۳۱]، ۲) گروهی که هر خوشه را با نزدیک ترین شئ داده‏ای به مرکز خوشه نشان می‏دهند^[۳۱]. الگوریتم k-medoid از این گروه می‏باشد. الگوریتم‏های خوشه‏بندی در یک دسته بندی دیگر به دو گروه خوشه‏بندی سخت^[۳۲] و خوشه‏بندی نرم^[۳۳] تقسیم می‏شوند. در الگوریتم‏های خوشه‏بندی سخت، خوشه‏ها دارای اشتراک نیستند یعنی هر شئ داده‏ای تنها به یک خوشه تعلق دارد، اما در الگوریتم‏های خوشه‏بندی نرم خوشه‏ها می‏توانند دارای اشتراک نیز باشند به عبارت دیگر اشیاء داده‏ای با درجه عضویت مشخصی به هر خوشه تعلق دارند.
مطالعات گسترده‏ای از سال ۱۹۶۰ تاکنون بر روی روش‏های خوشه‏بندی انجام شده است. الگوریتم‏های مختلف خوشه‏بندی در [۸،۴۴،۵۶،۴۵،۷۰،۷۲] با جزئیات و به گونه‏ای مناسب مورد نقد و بررسی قرار گرفته اند.
۱-۵- خوشه‏بندی توافقی
یکی از روش‏های خوشه‏بندی که در تحقیقات اخیر مورد توجه قرار گرفته است، روش خوشه‏بندی توافقی^[۳۴] می‏باشد. الگوریتم‏های این روش می‏توانند نتایج چندین خوشه‏بندی را با هم ترکیب کرده و به یک خوشه‏بندی نهایی دست یابند. نتایج مختلف خوشه‏بندی، یا از چندین منبع مختلف و یا از اجراهای مختلف الگوریتم‏های غیر قطعی خوشه‏بندی بدست می‏آیند. هدف خوشه‏بندی توافقی، یافتن خوشه‏بندی‏ای می‏باشد که علاوه بر کیفیت بالاتر و پایداری بیشتر خوشه‏ها، مورد توافق خوشه‏بندی‏های اولیه نیز باشد. خوشه‏بندی توافقی در تحقیقات و مقالات با نام‏های دیگری نظیر خوشه‏بندی جمعی^[۳۵] و اجتماع خوشه‏بندی‏ها^[۳۶] نیز شناخته می‏شود.
جهت نشان دادن حالت بسیار ساده‏ای از خوشه‏بندی توافقی فرض کنید، مجموعه داده‏ای به شکل X={x₁, x₂, x_3, x₄, x₅, x₆} باشد. سه خوشه‏بندی π_۱، π_۲، π_۳ نیز بر روی داده‏ها بدست آمده است. خوشه‏بندی‏های π_۱ و π_۳هر کدام دارای سه خوشه می‏باشند و خوشه‏بندی π_۲ نیز دارای ۴ خوشه است. شماره خوشه‏ای که هر کدام از داده‏ها در آن قرار گرفته‏اند به ازاء هر خوشه‏بندی در جدول ۱-۱ آمده‏ است.
جدول ۱-۱ مثالی ساده از خوشه‏بندی توافقی