وبلاگ

1-8-4 روش های مبتنی بر شبکه های مشبک (Grid based)
این روشها فضای اشیا را در تعداد متناهی سلول که ساختمانی مشبک را شکل می­ دهند تقسیم بندی می­ کنند که امکان کار بر روی اطلاعات با درجه تفکیک شفایت های متفاوت را فراهم میکند. در این روش ابتدا فضا به سلول هایی تقسیم شده وسپس عملیات خوشه بندی روی این سلول ها انجام میگیرد .مهم­ترین مزیت این روش افزایش سرعت پردازش می­باشد زیرا پیچیدگی محاسباتی را کاهش میدهد چرا که پیچیدگی وابسته به تعداد سلولهاست نه تعداد نقاط داده ها. روش هایی که بر اساس این متد عمل میکنند عبارتند از الگوریتم­های Wave,Clique,Sting
1-8-5 روش های مبتنی بر مدل
این روشها برای هر خوشه یک مدل فرض می­ کنند و سعی می­ کنند داده ­ها را به بهترین نحو ممکن در آنجا جای دهند. یک الگوریتم مبتنی بر مدل ممکن است خوشه ­ها را با یک تابع چگالی تعیین محل کند و یا راهی برای تعیین تعداد خوشه ­ها با بهره گرفتن از استاندارد­های آماری ارائه کند. البته با توجه به پیش فرض که در این روشها در مورد خوشه ­ها در نظر گرفته می­ شود گاه این روش­ها را خارج از دامنه خوشه­بندی و مثلا زیر مجموعه ­ای از کلاس­بندی فرض می­ کنند .

1-8-6 روش های فازی
اساس عملکرد این خوشه­بندی­ها بر آنست که هر ­داده می ­تواند متعلق به چندین خوشه با درجه عضویت­های مختلف باشد با این تعریف اغلب روش های قبل برای فضای فازی نیز با ایجاد تغییراتی در تابع فاصله قابل استفاده خواهند بود . در واقع الگوریتم های خوشه بندی فازی روش های افراز کننده ای هستند که جهت تخصیص داده ها به مجموعه ای از خوشه ها به کار میروند. در این الگوریتم ها با بهره گرفتن از یک تابع هدف که به عنوان شاخص ارزیابی به کار میرود ، داده های موجود به صورت بهینه خوشه بندی میشوند.
1-9 هدف خوشه بندی
همان طور که پیش از این گفته شد هدف خوشه بندی یافتن خوشه های مشابه از اشیاء در بین نمونه های ورودی می باشد اما چگونه می توان گفت که یک خوشه بندی مناسب است و خوشه بندی دیگر مناسب نیست؟ در واقع هیچ معیار مطلقی برای بهترین خوشه بندی وجود ندارد بلکه این بستگی به مساله و نظر کاربر دارد که باید تصمیم بگیرد که آیا نمونه ها بدرستی خوشه بندی شده اند یا خیر. با این حال معیار های مختلفی برای خوب بودن یک خوشه بندی ارائه شده است که می توانند کاربر را برای رسیدن به یک خوشه بندی مناسب راهنمایی کند که کیفیت در خوشه­بندی با این معیارها تعریف می شود که داده ­های هر خوشه، بیشترین شباهت را به یکدیگر داشته و از کمترین شباهت با خوشه­های دیگر برخوردار باشند. در قسمت معیارهای کارایی چند نمونه از این معیارها آورده شده است. یکی از مسایل مهم در خوشه بندی انتخاب تعداد خوشه ها می باشد. در بعضی از الگوریتم ها تعداد خوشه ها از قبل مشخص شده است و در بعضی دیگر خود الگوریتم تصمیم می گیرد که داده ها به چند خوشه تقسیم شوند. یک روش خوشه­بندی خوب خوشه­های با کیفیت بالا بر اساس دو معیار زیر را تولید می کند : شباهت بالای نقاط داخلی هر کلاس و شباهت کم بین نقاط کلاسهای مختلف .
کیفیت نتایج خوشه­بندی بستگی به روش اندازه ­گیری شباهت به کار رفته و همچنین پیاده­سازی آن روش دارد. در محل کیفیت روش خوشه­بندی همچنین با قابلیت توانایی آن روش در کشف تعدادی یا همه الگوهای پنهان اندازه ­گیری می­ شود .
یکی از مهمترین مسایل در خوشه بندی انتخاب تعداد خوشه های مناسب می باشد. تعداد خوشه ای مناسب می باشد که 1) نمونه های موجود در یک خوشه تا حد امکان شبیه به یکدیگر باشند و 2) نمونه های متعلق به خوشه های متفاوت تا حد امکان با یکدیگر نامتشابه باشند. عبارات فوق را بدین صورت نیز بیان می کنند که خوشه ها باید ماکزیمم فشردگی داشته باشند و تا حد امکان جدایی آنها نیز زیاد باشد. برای یک خوشه بندی مناسب هر دو معیار با هم باید ارضا شوند چرا که اگر تنها معیار فشردگی مورد استفاده قرار گیرد در آنصورت هر داده می تواند به صورت یک خوشه در نظر گرفته شود چرا که هیچ خوشه ای فشرده تر از خوشه ای با یک داده نمی باشد و اگر تنها معیار جدایی در نظر گرفته شود در آنصورت بهترین خوشه بندی این می باشد که کل داده ها را یک خوشه بگیریم با این توضیح که فاصله هر خوشه از خودش صفر است. بنابراین باید از ترکیب دو معیار فوق استفاده شود. اگر چه در روش c میانگین فازی و نسخه های مختلف آن تعداد خوشه ها از قبل مشخص شده است ولی در ابتدای کار تعداد خوشه ها برای طراح مشخص نیست و بیشتر با روش سعی و خطا تعداد مناسب خوشه ها تعیین می شود. برای مشخص کردن تعداد درست خوشه ها توابع ارزیابی مختلفی تعریف شده است که می توان با بهره گرفتن از آنها تعداد خوشه ها را برای مسایل مختلف مشخص کرد.
1-10 اندازه ­گیری کیفیت خوشه­بندی

• • ابتدا باید یک تابع تشابه تعریف شود که شباهت دو نقطه به یکدیگر را نشان دهد. عکس این تابع، تابع فاصله است که میزان عدم تشابه دو نقطه از یکدیگر و در نتیجه فاصله فرضی بین آن دو داده را در فضا از یکدیگر نشان می­دهد.

• • گاه نیز یک تابع جداگانه کیفیت وجود دارد که خوبی یک خوشه را اندازه ­گیری می­ کند. اما چنین توابعی نیز اغلب بر اساس همان معیار تشابه عمل می­ کنند .

• • تعریف تابع فاصله معمولا برای انواع داده ­های فاصله­ای، باینری، دسته­ای ، ترتیبی و نسبی متفاوت است

وزنها بر اساس کاربرد­های داده ­ها به متغیر­های مختلف تخصیص داده می­ شود. به این صورت که میزان اهمیت ابعاد مختلف یک فضا را مشخص می کند
مراحل انجام تجزیه و تحلیل خوشه­ای

• • انتخاب معیار شباهت یا نزدیکی مشاهدات .

• • انتخاب روش تجزیه و تحلیل خوشه­ای .

• • تصمیم ­گیری در مورد تعداد خوشه ­ها .

تفسیر دسته ها یا گروه های تشکیل شده .
1-11 بررسي تکنيکهاي اندازه‌گيري اعتبار خوشه‌ها
نتايج حاصل از اعمال الگوريتمهاي خوشه‌بندي روي يک مجموعه داده با توجه به انتخاب‌هاي پارامترهاي الگوريتمها مي‌تواند بسيار متفاوت از يکديگر باشد. هدف از اعتبارسنجي خوشه‌ها يافتن خوشه‌هايي است که بهترين تناسب را با داده‌هاي مورد نظر داشته باشند. دو معيارِ پاية اندازه‌گيري پيشنهاد شده براي ارزيابي و انتخاب خوشه‌هاي بهينه عبارتند از:[13]

• • تراکم (Compactness): داده‌هاي متعلق به يک خوشه‌ بايستي تا حد ممکن به يکديگر نزديک باشند. معيار رايج براي تعيين ميزان  تراکم داده‌ها واريانس داده‌ها است.

• • جدايي (Separation): خوشه‌ها خود بايستي به اندازه کافي از يکديگر جدا باشند. سه راه براي سنجش ميزان جدايي خوشه‌ها مورد استفاده قرار مي‌گيرد که عبارتند از:

• • فاصلة بين نزديک‌ترين داده‌ها از دو خوشه

• • فاصلة بين دور‌ترين داده‌ها از دو خوشه

• • فاصلة بين مراکزخوشه‌ها

همچنين روش‌هاي  ارزيابي خوشه‌هاي حاصل از خوشه‌بندي را به صورت سه دسته تقسيم مي‌کنند که عبارتند از:

• • معيارهاي خروجي (External Criteria)

• • معيارهاي دروني (Internal Criteria)

• • معيارهاي نسبي (Relative Criteria)

هم معيارهاي خروجي و هم معيارهاي دروني بر مبناي روش‌هاي آماري عمل مي‌کنند و پيچيدگي محاسباتي بالايي را نيز دارا هستند. معيارهاي خروجي عمل ارزيابي خوشه‌ها را با بهره گرفتن از بينش خاص کاربران انجام مي‌دهند. معيارهاي دروني عمل ارزيابي خوشه‌ها را با بهره گرفتن از مقاديري که از خوشه‌ها و نماي آنها محاسبه مي‌شود، انجام مي‌دهند.
پايه معيارهاي نسبي، مقايسة بين شما‌هاي خوشه‌بندي (الگوريم به علاوة پارامترهاي آن) مختلف است. يک و يا چندين روش مختلف خوشه‌بندي چندين بار با پارامترهاي مختلف روي يک مجموعة داده اجرا مي‌شوند و بهترين شماي خوشه‌بندي از بين تمام شماها انتخاب مي‌شود. در اين روش مبناي مقايسه، شاخص‌هاي اعتبارسنجي (Validity-Index) هستند. شاخص‌هاي ارزيابي بسيار متنوعي پيشنهاد شده‌اند که در اين قسمت سعي مي‌شوند تعدادي از رايج‌ترين آنها معرفي شوند.
1-12 شاخصهاي اعتبارسنجي
شاخص‌هاي اعتبارسنجي براي سنجش ميزان صحت (Goodness) نتايج خوشه‌بندي به منظور مقايسة بين روشهاي خوشه‌بندي مختلف يا مقايسة نتايج حاصل از يک روش با پارامترهاي مختلف مورد استفاده قرار مي‌گيرند.
در جدول زير مجموعه‌اي از علائم استفاده شده در ادامة اين بخش ارائه شده است:
جدول 1-1: مجموعة علائم بکار رفته در اين بخش