برای انجام داده کاوی از ابزار مختلف نظیر تفکیک کردن، دستهبندی، درخت تصمیم گیری، تحلیل قواعد وابستگی، تحلیل خوشه ها و الگوریتمهای عمومی استفاده می شود. در ادامه چند نمونه از کاربردهای این فرایند ذکر میگردد که در صورت عدم حضور داده کاوی، دستیابی به اهداف غیر ممکن میگردید.
با بهره گرفتن از داده کاوی میتوان کاربرد نمودارهای کنترلی را بهبود بخشید. فرض کنید ۴ پارامتر در یک مشخصهی کیفیِ مرتبط با یک قطعهی تولید شده در یک کارخانه، تأثیرگذار باشند و هدف، بهبود کیفیت آن مشخصه باشد. با بهره گرفتن از اطلاعات موجود که از حجم بالایی برخوردار می باشد، در صورتیکه کیفیت مشخصهی مذکور از محدوده قابل قبول خارج گردد طبق اصول مرتبط با کنترل کیفیت آماری، لازم است علل مربوط به انحرافات که باعث خروج مشخصهی کیفی از محدوده کنترلی شده است را شناسایی نموده، و پس از رفع آن، وضعیت دوباره بررسی گردد. عملاً زمان بسیار زیادی در این راه صرف خواهد شد. تکنیک داده کاوی می تواند با بررسی اطلاعات موجود در مورد ۴ پارامتر مذکور به جای استفاده از روشهای قبلی، با رسم نمودار میلهای پارامتری که بیشترین انحراف را نسبت به میانگین خود دارد مورد بررسی قرار داده و با کنترل آن عملاً دامنه را محدود نماید.
کاربرد اصلی داده کاوی آن است که به جای بررسی حجم بالایی از پارامترهای تأثیر گذار، با خوشه بندی اطلاعات بر اساس اهمیت آنها و تأثیرگذاری آنها بر پارامتر کیفیِ موردنظر، بتوان دامنه عمل را محدود نموده و در کمترین زمان و با حداقل هزینه به هدف رسید.
در موارد پزشکی ارائه روشهای جدید جهت پیش بینی ابتلای شخص به بیماریهای واگیردار خطرناک با بهره گرفتن از اطلاعات اولیه موجود بسیار ضروری میباشد. پزشکان جهت تشخیص دقیق و مطمئن ابتلای یک شخص به بیماری سل به مدت زمان طولانی احتیاج دارند. اما در این مدت ممکن است شخص مبتلا بیماری ر ا به ۱۰ تا ۱۵ نفر منتقل نماید. بنابراین با به کارگیری روشهای داده کاوی میتوان بر اساس اطلاعات به دست آمده از آزمایشات، در ساعات اولیه مراجعه بیمار احتمال ابتلای وی را تشخیص دهیم. همچنین، از این تکنیکها، در بهدست آوردن روابط مفید جهت جلوگیری از مرگ و میر افراد مبتلا به بیماریهای قلب و عروق، میتوان بهره گرفت [۱۷].
در مسائل اقتصادی نیز کاربردهای داده کاوی به وضوح قابل رؤیت میباشد. با توجه به روند تغییرات در صنعت بانکداری، (رواج بانکداری الکترونیکی) حجم اطلاعات در حال رشد است. با بهره گیری از این اطلاعات، میتوان عملکردهـایی را اتخاذ نمود که در این راستا رضایتمندی دوجانبه از طرف مشتری و بانک بهدست آید. مواردی مانند بازاریابی، حفظ مشتری، تشخیص تقلب، مدیریت ریسک و … را میتوان برشمرد. به طور نمونه، با توجه به اطلاعات موجود و استفاده از تکنیکهای خوشهبندی میتوان مشتریان خوشحسابتر و سودآورتر را برگزید و با اعطای تسهیلات، آنها را مورد تشویق قرار داد. همچنین مدیران بانک میتوانند احتمال این را که کدام مشتری دارای ریسک بیشتر برای عدم پرداخت وام و بدهی میباشد تشخیص دهند [۱۸].
داده کاوی الگوهای حاوی اطلاعات را در داده های موجود جستجو می کند. این الگوها و الگوریتمها میتوانند توصیفی[۹] باشند؛ یعنی داده ها را توصیف کنند یا جنبه پیش بینی[۱۰] داشته باشند. داده کاوی توصیفی به دنبال یافتن اگرها در فعالیتها و اقدامات گذشته است و داده کاوی پیش بینانه با نگاه به سابقه، رفتار آینده را پیش بینی می کند.
خوشهبندی داده ها یکی از تکنیکهای داده کاوی است که در گروه اول (توصیف کننده) قرار میگیرد و برای استخراج مدل از داده ها بهکار گرفته می شود. الگوریتم Fuzzy c-means یکی از روشهای خوشهبندی اطلاعات میباشد که از آن میتوان بـهره گرفت. با توجه به اهمیــت داده کاوی در دنیای امروز، ارائه روشهای جدید که بهوسیله آن داده ها مورد استفاده مفید قرار گیرد ضروری است. دراین تحقیق با ترکیب الگوریتم Fuzzy c-means و الگوریتم خفاش به این مهم دست خواهیم یافت.
۱-۵-گفتارهای پایان نامه
این پایان نامه بصورت زیر تنظیم شده است.
در فصل دوم، روشهای موجود جهت خوشهبندی معرفی خواهد گردید. محاسن و معایب آن بررسی میگردد و در نهایت الگوریتم که در این رساله از آن بهره خواهیم گرفت شرح داده خواهد شد.
در فصل سوم، با تکنیکهای بهینهسازی آشنا شده و کلیه روشهای تکاملی که در این رساله مورد مقایسه قرار گرفتهاند به طور اجمالی تشریح میگردد. در نهایت الگوریتم رقابت خفاش که اساس این پایان نامه میباشد به تفصیل توضیح داده خواهد شد.
در فصل چهارم، الگوریتم پیشنهادی که مبتنی بر ترکیب الگوریتم Fuzzy c-means و خفاش میباشد، توصیف میگردد.
در فصل پنجم، نتیجه گیری و پیشنهادات برای کارهای آینده آورده خواهد شد.
فصل دوم: خوشهبندی بر مبنای الگوریتم
Fuzzy c-means
۲-۱- مقدمه
خوشه به مجموعه ای از داده ها گفته می شود که از زاویهی خاصی به هم شباهت دارند. به دسته بندی طبیعی داده های نامتجانس به تعدادی خوشه بر اساس خصوصیات مشابه نیز خوشهبندی میگویند. اغلب از خوشهبندی به عنوان اولین گام داده کاوی یاد می شود که قبل از سایر فرآیندها بر روی رکوردها اعمال می شود تا گروهی از رکوردهای مرتبط به هم به عنوان نقطه آغاز تحلیلها شناسایی شوند. هدف از خوشه بندی این است که داده های موجود را به چندین گروه تقسیم کنند و در این تقسیم بندی داده های گروه های مختلف باید حداکثر تفاوت ممکن را با هم داشته باشند و داده های موجود در یک گروه باید بسیار به هم شبیه باشند.
در این فصل، بعد از مقایسه روش خوشهبنـدی با روش طبقه بندی، روشهای مختلف خوشهبندی معرفی میگردد و در آخر به توضیح در مورد الگوریتم Fuzzy c-means که این تحقیق بر پایه آن بنا شده است، خواهیم پرداخت.
۲-۲- خوشهبندی اطلاعات
در حالت کلی یادگیری را میتوان به دوگروه اصلی تقسیم کرد: یادگیری با نظارت و یادگیری بدون نظارت. در یادگیری با نظارت از ابتدا دستهها مشخص هستند و هر یک از داده های آموزشی به دستهای خاص نسبت داده شدهاست. اصطلاحاٌ گفته می شود که ناظری وجود دارد که در هنکام آموزش اطلاعاتی علاوه بر داده های آموزش در اختیار یادگیرنده قرار میدهد. ولی در یادگیری بدون نظارت هیچ اطلاعاتی بهجز داده های آموزشی در اختیار یادگیرنده قرار ندارد و این یادگیرنده است که باید درون داده ها به دنبال ساختاری خاص بگردد. خوشهبندی را میتوان بهعنوان مهمترین مسأله در یادگیری بدون نظارت درنظر گرفت. شکل۲-۱(الف)، خوشهبندی اطلاعات بر اساس معیار شباهت بین داده ها و شکل۲-۱ (ب)، طبقه بندی اطلاعات بر اساس تعداد کلاس معین از قبل تعیین شده را نشان میدهد.
شکل ۲‑۱ تفاوت خوشه بندی و طبقه بندی.
خوشهبندی همانگونه که بیان شد، بدون دانش قبلی، درون مجموعه ای از داده ها به کشف گروه های مشابه می پردازد. در واقع، الگوریتمهای خوشهبندی اغلب بدینگونهاند که یک سری نماینده اولیه برای نمونههای ورودی در نظر میگیرند سپس با توجه به میزان تشابه نمونهها با این نمایندهها، مشخص می شود که نمونه به کدام خوشه تعلق دارد و بعد از این مرحله نمایندههای جدید برای هر خوشه محاسبه می شود و دوباره نمونهها با این نمایندهها مقایسه میشوند تا مشخص شود که به کدام خوشه تعلق دارند و این کار آنقدر تکرار می شود تا زمانیکه نمایندههای خوشه ها تغییری نکنند.
انواعی از روشهای خوشهبندی تاکنون ارائه شده اند که وابسته به کاربرد میتوان از آنها استفاده کرد. با این حال، با وجود گوناگونی روشهای خوشهبندی، هنوز روش یکتایی وجود ندارد که بتواند انواع خوشه‌ها را به خوبی شناسایی کند؛ از این رو، این کاربر است که باید با توجه به نیاز‌هایش روش مناسب را بر‌گزیند.
۲-۲-۱- تفاوت خوشهبندی و طبقه بندی
در طبقه بندی هر داده به یک کلاس از پیش تعیین شده ، تخصیص مییابد. در واقع، سیستمهایی که بر اساس طبقه بندی کار می کنند دو مجموعه ورودی دارند. مجموعه آموزشی، که در آن دادههایی که به طور پیش فرض در دسته های مختلفی قرار دارند، همراه با ساختار دسته بندی خود وارد سیستم میشوند و سیستم بر اساس آنها آموزش می بیند یا به عبارتی، پارامترهای دسته بندی را برای خود مهیا می کند. گروه دیگر، ورودیهایی هستند که پس از مرحله آموزش و برای تعیین دسته وارد سیستم می شوند.
خوشهبندی با طبقه بندی[۱۱] متفاوت است. در طبقه بندی نمونههای ورودی برچسب گذاری شده اند ولی در خوشهبندی نمونههای ورودی دارای بر چسب اولیه نمیباشند و در واقع با بهره گرفتن از روشهای خوشهبندی است که داده های مشابه مشخص و به طور ضمنی برچسبگذاری میشوند. در واقع میتوان قبل از عملیات طبقه بندی داده ها یک خوشهبندی روی نمونهها انجام داد و سپس مراکز خوشههای حاصل را محاسبه کرد و یک بر چسب به مراکز خوشه ها نسبت داد و سپس عملیات طبقه بندی را برای نمونههای ورودی جدید انجام داد.
۲-۲-۲-کاربردهای خوشهبندی
در بسیاری از موارد با کمبود اطلاعات در مورد داده ها مواجه میباشیم و تصمیم گیرنده میبایست تا آنجا که ممکن است فرضیاتی را در مورد داده متصور شود . تحت این محدودیت است که متدلوژی کلاسترینگ بهعنوان یک راهکار مناسب برای کشف ارتباطهای معنائی میان داده ها به شمار میرود و میتوان از آن به عنوان یک دانش اولیه[۱۲] از داده ها یاد کرد. در حال حاضرخوشهبندی در زمینه های متنوعی به کارگرفته شده است که به عنوان نمونه میتوان موارد زیر را برشمرد:
۱- مهندسی: بینش محاسباتی، یادگیری ماشین، تشخیص الگو، مهندسی مکانیک ، مهندسی برق. کاربردهای موضوعی خوشهبندی درمحدودهی مهندسی از شناسایی بیومتریک و شناسایی گفتار تا تحلیل سیگنال رادار، خلاصه کردن اطلاعات و رفع پارازیت می باشد .
۲ - علوم کامپیوتر: کاربردهای خیلی زیادی از خوشه بندی در وب کاوی ( دسته بندی اسناد و یا دسته بندی مشتریان به سایتها )، تحلیل پایگاه داده فضایی ، بازیابی اطلاعات ، گردآوری مستندات متنی وپردازش تصویر ( تقسیم بندی تصاویر پزشکی و یا ماهواره‌ای) مشاهده کردهایم .
۳ - علوم پزشکی و زندگی: ژنتیک ، زیست شناسی ( دسته بندی حیوانات و گیاهان از روی ویژگیهای آنها )، میکروب شناسی، دیرین شناسی، روانپزشکی، تکامل نژادی، آسیب شناسی. این حوزه ها، در وهلهی اول شامل کاربردهای عمدهی خوشهبندی هستند و تا یکی از زمینه های اصلی الگوریتمهای خوشهبندی گردند؛ ادامه پیدا می کنند. کاربردهای مهم شامل تعریف طبقه بندی، شناسایی کارکرد پروتئین و ژن ، تشخیص و درمان بیماری و … میباشند.
۴ - علوم زمین و ستاره شناسی: جغرافیا، زمین شناسی، دریافت متحرک. خوشه بندی می تواند برای طبقه بندی کردن ستارهها و سیارات، تحقیق درمورد ساختار زمین، تفکیک کردن مناطق و شهرها (دستهبندی خانه‌ها براساس نوع و موقعیت جغرافیایی آنها)، مطالعه رودخانه و کوهها، مطالعات زلزلهنگاری ( تشخیص مناطق حادثه خیز بر اساس مشاهدات قبلی ) به کار رود .
۵ - علوم اجتماعی: جامعه شناسی، روان شناسی، انسان شناسی، کتابداری ( دسته بندی کتابها)، آموزش و پرورش. همچنین، کاربردهای جالب توجهای می تواند در تحلیل الگوی رفتاری، ساختار تاریخ تکاملی زبانها، تحلیل شبکه های اجتماعی، تشخیص باستان شناسی، طبقه بندی مصنوعی و مطالعه روان شناسی جنایی یافت شود.
۶ - اقتصاد: بازاریابی، تجارت. کاربردهایی نظیر شناسایی الگوی خرید، گروه بندی شرکتها و تحلیل روند ذخیرهسازی، همه از تحلیل خوشه بندی سودمند میگردند.
۲-۲-۳- انواع خوشه ها
خوشههای بهخوبی جدا شده: مجموعه نقاط داخل این خوشه نسبت به نقاط خارج آن به یکدیگر شباهت بیشتری دارند.
خوشههای مبتنی به مرکز: مجموعه نقاط داخل این خوشه به مرکز خوشه نسبت به مراکز خوشههای دیگر بسیار نزدیکترهستند.
خوشههای مبتنی بر مجاورت و نزدیکی: مجموعه نقاط داخل این خوشه به یک یا تعداد بیشتری از نقاط داخل خوشه نسبت به نقاط خارج آن شبیه میباشند.
۲-۲-۴- مراحل خوشهبندی
خوشهبندی دارای چهارمرحلهی اساسی به شرح زیر است :
انتخاب یا استخراج ویژگی: ویژگیها باید به طور مناسبی انتخاب شوند تا اکثر داده ها کدگذاری گردند. در صورتی که در این مرحله، ویژگیهای انتخابی به طور نامناسب در نظر گرفته شوند، جواب نهایی هدف مورد نظر را نتیجه نخواهد داد. لذا، این بخش نقش اساسی را در روند خوشهبندی ایفا خواهد کرد [۱۹]. برای بهدست آوردن مجموعه مناسبی از ویژگیها در امر کلاسترینگ، از دو تکنیک استفاده می شود: گزینش ویژگی و استخراج ویژگی. گزینش ویژگی[۱۳] فرآیندی است که برای شناسائی مؤثرترین زیر مجموعه از ویژگیهای اولیه برای کلاسترینگ استفاده می شود و استخراج ویژگی[۱۴] استفاده از یک یا چند مرحله تبدیل ویژگیهای ورودی به منظور به دست آوردن ویژگیهای برجسته جدید میباشد .
مقیاس نزدیکی: معیاری است که میزان شباهت و یا عدم شباهت دو بردار خصوصیت را مشخص می کند. تمام خصوصیات انتخاب شده باید در محاسبه این معیار شرکت کنند و هیچ خصوصیتی نباید بر بقیه غلبه کند. سادهترین معیار برای مسافت، فاصله اقلیدسی است که بیانگر افتراق[۱۵] بین دو نمونه میباشد . این در حالی است که معیارهای تشابه هم میتوانند برای تشخیص تشابهات معنائی در میان نمونهها استفاده شوند. همین که، یک مقیاس نزدیکی تعیین می شود، خوشهبندی می تواند به عنوان یک مسأله بهینه سازی با یک تابع معیار خاص استنباط گردد. پس خوشههای به دست آمده وابسته به انتخاب تابع معیار میباشند.
الگوریتم خوشهبندی: پس از اینکه مقیاس نزدیکی انتخاب شدند، یک الگوریتم خاص جهت روشن کردن ساختار دستهبندی مجموعه داده ها انتخاب میگردد. بهعنوان نمونه خروجی خوشهبندی می تواند گروه های سخت[۱۶] و یا نرم [۱۷]باشد که هر روش دارای درجه عضویت متفاوتی بوده و درجه عضویت، میزان تعلق هر داده به خوشه است.
اعتبار سنجی نتایج: شاخص های اعتبار سنجی برای سنجش میزان صحت نتایج خوشهبندی به منظور مقایسه بین روشهای مختلف یا مقایسه نتایج حاصل از یک روش با پارامترهای مختلف مورد استفاده قرار می گیرد؛ زیرا نتایج حاصل از اعمال الگوریتمهای خوشهبندی روی یک مجموعه داده با توجه به مقادیر انتخابی برای پارامترهای هر الگوریتم می تواند بسیار متفاوت از یکدیگر باشد. هدف از اعتبارسنجی، یافتن خوشههایی است که بهترین تناسب را با داده های مورد نظر داشته باشند.
