بررسي تکنيکهاي اندازه‌گيري اعتبار خوشهها
نتايج حاصل از اعمال الگوريتمهاي خوشه‌بندي روي يک مجموعه داده با توجه به انتخاب‌هاي پارامترهاي الگوريتمها مي‌تواند بسيار متفاوت از يکديگر باشد. هدف از اعتبارسنجي خوشهها يافتن خوشه‌هايي است که بهترين تناسب را با داده‌هاي مورد نظر داشته باشند. دو معيارِ پاية اندازه‌گيري پيشنهاد شده براي ارزيابي و انتخاب خوشه‌هاي بهينه عبارتند از:[8]
*
تراکم (Compactness): داده‌هاي متعلق به يک خوشه بايستي تا حد ممکن به يکديگر نزديک باشند. معيار رايج براي تعيين ميزان تراکم داده‌ها واريانس داده‌ها است.
*
جدايي (Separation): خوشهها خود بايستي به اندازه کافي از يکديگر جدا باشند. سه راه براي سنجش ميزان جدايي خوشهها مورد استفاده قرار مي‌گيرد که عبارتند از:
*
فاصلة بين نزديک‌ترين داده‌ها از دو خوشه
*
فاصلة بين دور‌ترين داده‌ها از دو خوشه
*
فاصلة بين مراکزخوشه‌ها
همچنين روشهاي ارزيابي خوشه‌هاي حاصل از خوشه‌بندي را به صورت سه دسته تقسيم مي‌کنند که عبارتند از:
*
معيارهاي خروجي (External Criteria)
*
معيارهاي دروني (Internal Criteria)
*
معيارهاي نسبي (Relative Criteria)
هم معيارهاي خروجي و هم معيارهاي دروني بر مبناي روشهاي آماري عمل مي‌کنند و پيچيدگي محاسباتي بالايي را نيز دارا هستند. معيارهاي خروجي عمل ارزيابي خوشهها را با استفاده از بينش خاص کاربران انجام مي‌دهند. معيارهاي دروني عمل ارزيابي خوشهها را با استفاده از مقاديري که از خوشهها و نماي آنها محاسبه مي‌شود، انجام مي‌دهند.
پايه معيارهاي نسبي، مقايسة بين شما‌هاي خوشه‌بندي (الگوريم به علاوة پارامترهاي آن) مختلف است. يک و يا چندين روش مختلف خوشه‌بندي چندين بار با پارامترهاي مختلف روي يک مجموعة داده اجرا مي‌شوند و بهترين شماي خوشه‌بندي از بين تمام شماها انتخاب مي‌شود. در اين روش مبناي مقايسه، شاخصهاي اعتبارسنجي (Validity-Index) هستند. شاخصهاي ارزيابي بسيار متنوعي پيشنهاد شده‌اند که در اين قسمت سعي مي‌شوند تعدادي از رايج‌ترين آنها معرفي شوند.
شاخصهاي اعتبارسنجي
شاخصهاي اعتبارسنجي براي سنجش ميزان صحت (Goodness) نتايج خوشه‌بندي به منظور مقايسة بين روشهاي خوشه‌بندي مختلف يا مقايسة نتايج حاصل از يک روش با پارامترهاي مختلف مورد استفاده قرار مي‌گيرند.
در جدول زير مجموعه‌اي از علائم استفاده شده در ادامة اين بخش ارائه شده است:
1-1-1- شاخص دون (Dunn Index)
اين معيار توسط رابطة زير تعريف مي‌شود:
که d(x,y) و diam(ci) در آن به ترتيب با روابط 9 و 10 محاسبه مي‌شوند.
اگر مجموعة داده‌اي، داراي خوشه‌هايي جداپذير باشد، انتظار مي‌رود فاصلة بين خوشهها زياد و قطر خوشه‌هاي (Diameter) آن کوچک باشد. در نتيجه مقداري بزرگ‌تر براي رابطة اين معيار مقداري مطلوب‌تر است. معايب اين معيار عبارتند از:
*
محاسبة زمانبر
*
حساسيت به نويز (قطر خوشهها در صورت وجود يک دادة نويزي مي‌تواند بسيار تغيير کند.)
1-1-2- شاخص ديويس بولدين (Davies Bouldin Index)
اين معيار از شباهت بين دو خوشه (Rij) استفاده مي‌کند که بر اساس پراکندگي يک خوشه (si) و عدم شباهت بين دو خوشه (dij) تعريف مي‌شود. شباهت بين دو خوشه را مي‌توان به صورتهاي مختلفي تعريف کرد ولي بايستي شرايط زير را دارا باشد.
*
*
*
اگر si و sj هر دو برابر صفر باشند آنگاه Rij نيز برابر صفر باشد.
*
اگر
و
آنگاه
*
اگر
و
آنگاه
معمولا شباهت بين دو خوشه به صورت زير تعريف مي‌شود:
که در آن dij و si با روابط زير محاسبه مي‌شوند.
با توجه به مطالب بيان شده و تعريف شباهت بين دو خوشه شاخص ديويس بولدين به صورت زير تعريف مي‌شود.
که Ri در آن به صورت زير محاسبه مي‌شود.
اين شاخص در واقع ميانگين شباهت بين هر خوشه با شبيه‌ترين خوشة به آن را محاسبه مي‌کند. مي‌توان دريافت که هرچه مقدار اين شاخص بيشتر باشد، خوشه‌هاي بهتري توليد شده است.
1-1-3- شاخصهاي اعتبارسنجي ريشة ميانگين مربع انحراف از معيار (RMSSDT) و ريشة R (RS):
هرچند اين شاخص‌ها معمولا در اعتبارسنجي الگوريتمهاي سلسله مراتبي مورد استفاده قرار مي‌گيرند ولي قابليت ارزيابي نتايج ساير تکنيکهاي خوشه‌بندي را نيز دارا مي‌باشند. در شاخص اعتبارسنجي RMSSDT (root – mean– square standard deviation) از واريانس خوشهها استفاده مي‌شود که به شکل رسمي مي‌توان از رابطة 16 براي محاسبه آن استفاده کرد.
با توجه به رابطة بالا و اينکه اين معيار ميزان همگني خوشهها را اندازه مي‌گيرد، مي‌توان دريافت که هرچه مقدار آن کمتر باشد نشان دهندة خوشه‌بندي بهتر داده‌ها است.
شاخص اعتبارسنجي RS (R Square) که با استفاده از رابطة 17، 18 و 19 تعريف مي‌شود، معياري براي بيان عدم‌تشابه بين خوشهها است. به اين شاخص درجة همگني بين گروهي نيز گفته مي‌شود. مقادير آن به بازة اعداد بين 0 تا 1 محدود مي‌باشد. که 0 نشان دهندة نبودن هيچ تفاوتي بين خوشهها و 1 نشان دهندة وجود تفاوتي قابل توجه بين خوشهها است.
1-1-4- شاخص اعتبارسنجي sd
اساس شاخص اعتبارسنجي SD، مياگين پراکندگي (Avrage Scattering) و جدايي کلي (Total Sepration) خوشهها است. پراکندگي از طريق محاسبة واريانس خوشهها و واريانس کل محموعة داده‌ها بدست مي‌آيد. با توجه به اينکه اين معيار هم از ميزان همگني داده‌ها و هم از ميزان تراکم خوشهها بهره مي‌برد معيار مناسبي براي ارزيابي خوشهها محسوب مي‌شود. واريانس مجموعة داده‌ها را با روابط 20 و 21 و نيز واريانس يک خوشه را با روابط 22 و 23 مي‌توان محاسبه کرد.
واريانس مجموعه داده ها:
واريانس يک خوشه:
با توجه به واريانسهاي محاسبه شده با روابط بالا، ميانگين پراکندگي خوشهها از رابطة زير محاسبه مي‌شود.
همچنين ميزان جدايي کلي داده‌ها که بر اساس فاصلة مراکز خوشهها از هم تعريف مي‌شود، از رابطة زير محاسبه مي‌شود.
در نهايت شاخص SD با رابطة زير تعريف مي‌شود.
که α عمل وزني براي رابطه است که برابر ميزان جدايي خوشهها در صورت داشتن حداکثر تعداد خوشهها مي‌باشد. مقدار محاسبه شده توسط اين معيار هرچه کوچک‌تر باشد به معني خوشه‌بندي بهتر است.
1-1-5- شاخص اعتبارسنجي S_Dbw
همانند شاخص SD اين معيار هم بر اساس تراکم درون‌خوشه‌اي و ميزان جدايي خوشهها اما در اين شاخص سعي شده تا چگالي خوشهها نيز دخيل شود. به شکل رسمي مي‌توان گفت که شاخص S_Dbw از واريانس بين خوشه‌اي و واريانس درون خوشه‌اي استفاده مي‌کند. واريانس بين خوشهها مقدار ميانگين پراکندگي خوشهها را بدست مي‌آورد که در رابطة 24 نحوة محاسبة آن بيان شده است. مقدار چگالي درون خوشه‌اي نيز با رابطة زير محاسبه مي‌شود.
که uij که در آن نقطة وسط خطي است که vi و vj را به هم وصل مي‌کند. براي محاسبة تابع چگالي اطراف يک نقطه، تعداد نقاط درون ابر کره‌اي را که شعاع آن برابر ميانگين انحراف از معيار خوشهها است، شمارش مي‌شود. ميانگين انحراف از معير خوشهها به صورت زير تعريف مي‌شود.
در نهايت معيار S_Dbw به صورت زير تعريف مي‌شود.
در شاخص S_Dbw سعي شده هر دو معيار خوبي خوشهها با هم ترکيب شوند و تخميني دقيق از خوشه‌هاي خاصل بدست آيد. مقدار کم براي اين شاخص به معني خوشه‌بندي بهتر است.