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