بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
بررسی شاخص هاي اعتبارسنجی خوشه بندي
چکیده
خوشه بندي یکی از رایج ترین تکنیک هاي داده کاوي و فرآیند بدون ناظر در دسته بندي داده ها است.هدف خوشه بندي قرار دادن دادههاي مشابه به هم در یک گروه است، بطوریکه نمونهها در یک خوشه بیشترین شباهت را با یکدیگر و بیشترین تفاوت را با نمونهها درخوشههاي دیگر داشته باشند، الگوریتمهاي خوشه بندي متعددي وجود دارد که نتایج بسیاري از الگوریتمهاي خوشهبندي وابسته به پارامترهاي اولیه الگوریتم می باشد ، بنابراین ارزیابی نتایج خوشه بندي الگوریتم ها بسیار با اهمیت است ،در این راستا شاخص هاي اعتبارسنجی متعددي مطرح شده اما تاکنون هیج شاخص رسمی براي ارزیابی نتایج خوشه بندي بیان نشده است. در این مقاله ما مروري بر تعدادي از شاخصهاي مطرح شده خواهیم داشت و مزایا ومعایب آنها را بیان و سپس شاخص اعتبارسنجی جدیدي را مطرح خواهیم کرد که قادر است تعداد تخمینی دقیق تري از تعداد خوشه هاي بهینه براي مساله ما را مشخص نماید جهت اثبات این موضوع ما از 3 مجموعه داده واقعی سایت یادگیري ماشین UCI استفاده نموده ایم.
کلمات کلیدي: خوشهبندي-دادهکاوي – فرآیند بدون ناظر- شاخصهاي اعتبارسنجی
مقدمه
خوشهبندي یک فرایند بدون ناظر در دادهکاوي و تشخیص الگو است ،الگوریتمهاي خوشهبندي متعددي وجود دارد که نتایج حاصل از آنها روي یک مجموعه داده، حساس به شرایط اولیه الگوریتم می باشد ، بنابراین ارزیابی نتاج خوشهبندي بسیار مهم است و بدون استفاده از شاخص اعتبارسنجی تعیین درجه کیفیت خوشه بندي بسیار دشوار، بنابراین هدف از اعتبارسنجی خوشهها یافتن خوشههایی است که بهترین تناسب را با دادههاي مورد نظر داشته باشنددو. معیارِ پایه اندازهگیري براي ارزیابی و انتخاب خوشههاي
بهینه عبارتند از:
تراکم:1 دادههاي متعلق به یک خوشه بایستی تا حد ممکن به یکدیگر نزدیک باشند. معیار رایج براي تعیین میزان تراکم دادهها واریانس دادهها است. جدایی:2 خوشهها خود بایستی به اندازه کافی از یکدیگر جدا باشند. سه راه براي سنجش میزان جدایی خوشهها مورد استفاده قرار میگیرد که عبارتند از:
1. فاصله بین نزدیکترین دادهها از دو خوشه
2. فاصله بین دورترین دادهها از دو خوشه
3. فاصله بین مراکز خوشهها
همچنین روشهاي ارزیابی خوشههاي حاصل از خوشهبندي را به سه دسته تقسیم میکنند که عبارتند از:
1. معیارهاي خروجی3
2. معیارهاي درونی4
3. معیارهاي نسبی5
(1 معیارهاي خروجی: معیارهاي خروجی بر پایه ساختارهاي از قبل مشخص شده است، که اطلاعات پیشین از دادهها را منعکس میکنند . این شاخصها به عنوان استاندارد تایید اعتبار جواب خوشهبندي استفاده می شوند .
(2 معیارهاي داخلی: معیارهاي داخلی به اطلاعات خارجی (دانش پیشین) وابستگی ندارندنها،آ مستقیماً ساختار خوشهبندي را از روي دادههاي اصلی آزمایش میکنند .
(3 معیارهاي نسبی: معیارهاي نسبی برروي مقایسه بین تفاوتهاي ساختارهاي خوشه بندي تاکید می کنند، بطوریکه مرجعی براي تصمیم گیري اینکه، کدام مشخصه از اشیا میتواند شایستگی خوشه ها را بهتر از همه اشکار نماید.
هم معیارهاي خروجی و هم معیارهاي درونی بر مبناي روشهاي آماري عمل میکنند و پیچیدگی محاسباتی بالایی را نیز دارا هستند . معیارهاي خروجی عمل ارزیابی خوشهها را با استفاده از بینش خاص کاربران و معیارهاي درونی عمل ارزیابی خوشهها را با استفاده از مقادیري که از خوشهها و نماي آنها محاسبه میشود، انجام میدهند. پایه معیارهاي نسبی، مقایسه بین شماهاي خوشهبندي (الگوریتم به علاوه پارامترهاي آن) مختلف است. یک و یا چندین روش مختلف خوشهبندي چندین بار با پارامترهاي مختلف روي یک مجموعه داده اجرا شده و بهترین شماي خوشهبندي از بین تمام شماها انتخاب میشود. در این روش مبناي مقایسه، شاخصهاي اعتبارسنجی هستند (فرانس و همکاران،. (2005
در ادامه تعدادي از شاخصهاي اعتبارسنجی داخلی و خارجی مطرح خواهد شد، سپس شاخص پیشنهادي بیان و به کمک 3 مجموعه داده واقعی از سایت یادگیري ماشین ،UCI عملکرد مناسب آن اثبات می شود.
ادامه مقاله به نحو ذیل سازماندهی شده است:
-2 پیشینه پژوهش -3 شاخص اعتبارسنجی پیشنهادي -4 آزمایشات -5 نتایج پژوهش -6 پیشنهادات -7 منابع.
پیشینهپژوهش:
شاخصهاي داخلی به دو دسته -1 شاخصهاي مربوط به ارزیابی الگوریتمهاي خوشهبندي قطعی مانند الگوریتم خوشه بندي kmeans و – 2 شاخص هاي مربوط به ارزیابی خوشهبندي الگوریتمهاي فازي مانند FCM تقسیم میشوند که در ادامه تعدادي از این دسته شاخصهاي که تاکنون مطرح شده است ، بیان خواهد شد.
شاخص Silhouette coefficient یکی از متداولترین روشهاي اعتبارسنجی خوشه بندي قطعی است که اولین بار در سال 1986 توسط Peter J. Rousseeuw و همکارانش مطرح گردید.
این شاخص کیفیت خوشه بندي نمونه ها را در خوشههاي قرار گرفته شده بررسی می نماید و با رابطه 1 محاسبه می شود.
(1)
در روابط فوق a(i) ،میانگین اختلاف نمونه i با همه نمونههاي در همان خوشه و b(i) حداقل میانگین اختلاف نمونه i با همه نمونه ها در خوشه هاي غیر متناظر می باشد که در تصویر 1به این مفاهیم اشاره شده است.
مقدار نهایی این شاخص به ازاي k خوشه بین بازه 1 -1 است، و هر چه مقدار این شاخص به 1 نزدیک تر باشد خوشه بندي مطلوب تر است.
شکل:1نحوه عملکر شاخص S (روسو و همکاران،(1987
در واقع در این شاخص براي هر خوشه میزان پراکندگی و همبستگی داده ها تعیین می شود مقدار بیشینه در این شاخص اشاره به تعداد خوشه بهینه براي مجموعه داده و خوشه بندي مطلوب دارد.
شاخص RMSSDT6 در سال 1996 توسط Sharma و همکارانش مطرح گردید. این شاخصمعمولاً در اعتبارسنجی الگوریتمهاي سلسله مراتبی مورد استفاده قرار میگیرند ولی قابلیت ارزیابی نتایج سایر تکنیکهاي خوشهبندي را نیز دارا است.
در این شاخص از واریانس خوشهها استفاده میشود که به شکل رسمی از رابطه 2 براي محاسبه آن استفاده میکنیم.
(2)
در این رابطه X ij اشاره به مقدار نمونه j در خوشه i و Xi ،اشاره به مرکز خوشه مورد نظر و nc تعداد خوشه ها می نماید. با توجه به اینکه این شاخص میزان همگنی خوشه ها را اندازهگیري مینماید ،می توان دریافت هرچه مقدار این شاخص کمتر باشد، در واقع اشاره به خوشه بندي مطلوب تر دارد. [3, 4 ]
شاخص PC7 در سال 1981 توسط Bezdek و همکارانش مطرح گردید .این شاخص فازي، میزان هم پوشانی بین خوشه ها را اندازه گیري می نماید و با رابطه 3 قابل محاسبه است.
(3)
در این رابطه c، تعداد خوشه ها ،n تعداد داده ها و u2ij میزان عضویت نمونه j به خوشه i را مشخص می نماید. خروجی این شاخص بین [1/c , 1] است زمانیکه مقدار این شاخص برابر 1 باشد نشان می دهد که هم پوشانی بین خوشه ها وجود نداشته و خوشه بندي معادل خوشه بندي کلاسیک و قطعی خواهد بود و اگر مقدار این شاخص برابر 1/c باشد به این معنی است که خوشه بندي در فازي ترین حالت خود، و هم پوشانی بین خوشه ها زیاد است (بیطو و همکاران،. (1981 بنابراین در این شاخص مقدار ماکزیمم اشاره به خوشه بندي مطلوب و تعداد خوشه بهینه دارد . طبق تحقیقات ku-lung-wu و همکارانش در سال 2005 این شاخص در ارزیابی خوشههاي حاصل از الگوریتمهاي فازي در محیطهاي داده اي نویزي عملکرد ضعیفی دارد.(لانگ و همکاران،.(2004
در تحقیقاتی که در سال Moumen El-Melegy 2007 و همکارانش انجام دادند به این نتیجه رسیدند که اگر این معیار براي ارزیابی خوشه هاي حاصل از الگوریتم خوشه بندي kmeans بکار برده شود با افزایش سطح نویز تعداد خوشه تشخیصی آنها ثابت می ماند و تغییري نمی کند(ژانگ و همکاران،.(2002
شاخصPE 8 در سال 1974 توسط Bezdek و همکارانش مطرح گردید. این شاخص میزان همپوشانی خوشههاي ایجاد شده را بررسی می نماید و با رابطه 4 محاسبه می شود.
(4)
در این رابطه c تعداد خوشه ها ،n تعداد نمونه ها وuij میزان عضویت نمونه j به خوشه i است..
خروجی این شاخص بین 0 تا logac می باشد .زمانیکه مقدار این شاخص برابر 0 شود یعنی خوشهبندي معادل خوشه بندي کلاسیک است و زمانیکه مقدار این شاخص برابر logacشود یعنی خوشه بندي در فازي ترین حالت خود قرار دارد. یک حالت دیگر از این تابع نیز تعریف شده، که به تابع ارزیابی آنتروپی نرمال شده معروف است. در این تابع مقدار تابع ارزیابی فوق را بر لگاریتم تعداد خوشه ها (c) تقسیم می کنند.
انتخاب تعداد خوشه هاي مناسب با مینیمم کردن تابع فوق بدست میآید. تعداد خوشههایی که به ازاي آن این تابع کمترین مقدار را داشته ، بعنوان تعداد خوشه هاي مناسب براي آن مساله مورد استفاده قرار می گیرد.
نکته قابل توجه در مورد این دو تابع این است که زمانی که PC برابر 1 باشد PE برابر 0 خواهد بود و در این حالت خوشه بندي معادل خوشه بندي کلاسیک است. اگر PC برابر 1/c باشد PE برابر log2c می شود که در این حالت خوشه بندي در فازي ترین حالت خود خواهد بود. از طرف دیگر گفته شد که باید براي رسیدن به حالت خوشه بندي مطلوب PC ماکزیمم شود و PE مینیمم. بنابراین در خوشهبندي هاي فازي سعی میشود تا خوشهها به خوشه هاي کلاسیک نزدیکتر باشند.
نقاط ضعف دو شاخص PC,PE این است که از خود داده ها بطور مستقیم براي ارزیابی خوشه بندي استفاده نشده است. هر دو شاخص مذکور تمایل به افزایش یکنواختی با تغییر تعداد خوشه ها دارند و براي کاهش این رشد یکنواخت معیار دیگري با تغییر در شاخص PC به نام MPC مطرح شد. (بیزه و همکاران،(1974
طبق تحقیقات ku-lung-wu و همکارانش در سال 2005 این شاخص در ارزیابی خوشههاي حاصل از الگوریتمهاي فازي در محیطهاي داده اي نویزي عملکرد ضعیفی دارد. (لانگ
æ همکاران،(2004
شاخصMPC9 در سال 1996 توسط Dave و همکارانش جهت رفع مشکل مذکور در شاخص PC مطرح گردید و با رابطه 5 قابل محاسبه است.
(5)
در این رابطه C تعداد خوشه ها و vPC مقدار شاخص PC است، خروجی این شاخص بین 0و 1 بوده و مقدار نزدیک به 1 در این شاخص اشاره به تعداد خوشه مناسب و خوشه بندي مطلوب داده ها خواهد نمود.شاخص فوق معادل با یک شاخص غیر فازي ساز است.(ژانگ و همکاران،(2002
در تحقیقاتی که در سال Moumen El-Melegy 2007 و همکارا نش روي تصاویر نویزي با سطوح نویز مختلف با دو الگوریتم خوشهبندي kmeans و fcm انجام دادند به این نتیجه رسیدند این معیار در تشخیص تعداد خوشههاي بهینه و تغییر سطح نویز رابطه سازگاري دارد و با افزایش سطح نویز تعداد خوشههاي بهینه تشخیصی این معیار تغییري نمی نماید (داوو و همکاران،.(2009
شاخص خارجی purity در سال 2002 توسط Zaho و همکارانش مطرح گردید. این شاخص دقت خوشه بندي را بررسی می نماید و بسیار شبیه معیار آنتروپی است و با رابطه6 قابل محاسبه می باشد.
(6)
در این رابطه P(Sr) دقت خوشه r را بررسی می نماید که با رابطه 7 قابل محاسبه است در این رابطه بیشترین توزیع نمونه ها را براي یک خوشه در نظر می گیریم و nr اشاره به تعداد نمونه ها در خوشه n, rتعدادکل نمونه ها می باشد.
(7)
مقدار خروجی این شاخص بین 0و1 است و مقدار نزدیک به 1 اشاره به دقت بالاتر خوشه بندي داده ها می نماید و به ازاي هر تعداد خوشه که مقدار این شاخص به 1 نزدیک شوذ اشاره به خوشه بندي مطلوب و تعداد خوشه بهینه دارد.
شاخص Entropy در سال 2002 توسط Zaho و همکارانش مطرح گردید و با رابطه 8 قابل محاسبه است.
(8)
در این رابطه E(Sr) اشاره به میزان آنتروپی خوشهr و n تعدادکل نمونه ها ، nr تعداد نمونه ها در خوشه k, rتعداد خوشه ها دارد.که میزان آنتروپی در خوشه r با رابطه 9 قابل محاسبه است.
