بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
بهينه سازي Fuzzy c-means در جهت پيدا کردن مراکز اوليه مناسب براي خوشه ها
چکيده
Fuzzy c-means يک موضوع مطالعاتي مهم در خوشه بندي داده ها در تکنولوژي داده کاوي است که کاربردهاي عملي در زمينه هـاي مختلف دارد. بزرگترين عيب اين الگوريتم خوشه بندي فازي ، حساسيت آن به مقداردهي او يه به تعـداد خوشـه هـا و مراکـز اوليـه خوشه ها است . انتخاب نامناسب مراکز اوليه خوشه ها در اين الگوريتم منجر به مينيمم محلي مي شود.
اين مقاله نسخه اي بهبود يافته از الگوريتم FCM با رويکرد رفع برخي از مشکلات اين الگوريتم ، ازجمله حساسيت بـه شـرايط اوليه ارائه مي کند. الگوريتم پيشنهادي مي تواند راه حل هاي بهينه سراسري ، از طريق يک قانون ساده و جديد براي انتخاب مناسـب مراکز اوليه خوشه بدست آورد. روش پيشنهادي در مقايسه با الگوريتم FCM متداول دقت بالاتري دارد، بـراي مقايسـه دو روش از داده هاي دو مجموعه داده حقيقي استفاده شده است .
کلمات کليدي
Fuzzy c-means يا FCM ، داده کاوي ، خوشه بندي ، مرکز خوشه ، شاخص اعتبار.
۱- مقدمه
FCM [١] نقش مهمي در بسياري از زمينـه هـاي مهندسـي هماننـد تشخيص الگو، مدلسازي سيستم ، پردازش تصـوير، داده کـاوي و غيـره ايفا مي کند. اين الگوريتم مجموعه داده هـاي را به c گروه تقسيم مي کند، اما نتيجه تقسـيم بنـدي FCM بـه مقـادير به اوليه شامل تعداد خوشه ها و مراکزشان حساس است .
پيدا کردن تعداد مناسب خوشه هـا در نتيجـه ي الگـوريتم FCM نقش به سزايي دارد. براي پيدا کردن تعداد درست خوشه ها از شاخص - هاي اعتبار گونـاگوني هماننـد PC،PE ، وXB اسـتفاده مـي شـود[٢].
هريک از اين شاخص ها ملاکي بـراي ارزيـابي خوشـه بنـدي دارنـد، در برخي از آنها فقط درجه عضويت به خوشه ها لحاظ مي شـود و سـاختار هندسي داده ها در شاخص دخالت داده نمي شوند، و در برخي ديگر هر دو مقدار براي ارزيابي خوشه بندي در نظر گرفته مي شوند. به هر حـال هيچ يک از اين شاخص ها برتري خود را بر ديگري تحت همـه شـرايط اثبات نکرده است .
از سوي ديگر FCM فقط مي تواند به سوي يک مينيمم محلي بـر اساس مقداردهي او يه به مراکز خوشه ها همگرا گـردد، و ايـن مشـکل تنها در صورتي مي تواند حل شـود کـه انتخـابي زيرکانـه بـراي مراکـز خوشه ها صورت گيرد.
هدف اين مقاله اين است که با انجام مراحل پيش پردازشي ساده مراکز اوليه خوشه ها در FCM به نحوي انتخاب شوند که از گرايش بـه مينيمم محلي اجتناب شود و نتيجه ي مطلوب تري براي خوشـه بنـدي داده ها بدست آيد.
در ادامه اين مقاله به صورت زير سازماندهي شده است : در بخـش دوم به معرفي الگوريتم خوشه بندي فازي و برخي از شاخص هاي اعتبار آن پرداخته شده است . در بخش سوم روش پيشنهادي که شـامل يـک پيش پردازش براي تعيين مراکز اوليه خوشه هـا در FCM اسـت ارائـه گرديده است . در بخش چهارم براي اثبات مطلوبيت روش پيشـنهادي ، الگوريتم خوشه بندي FCM و روش بهينه ي پيشنهادي بـر روي داده - هاي دو مجموعـه داده [١١] Iris و [١٢] Glass اعمـال شـده انـد و نتايج مقايسه اي ارائه گرديده اند. در بخش آخر به نتيجه گيري پرداخته شده است .
۲- الگوريتم خوشه بندي فازي FCM و برخي از شاخص هاي اعتبار آن
۲-۱- خوشه بندي فازي FCM
برخلاف الگوريتم هاي خوشه بندي غيرفازي که هر شي را به يک خوشه منحصر به فرد نسبت مي دهند، الگوريتم هاي خوشه بندي فـازي منجـر به مقادير عضويتي بين ۰ و ۱ مي شوند که درجه عضـويت هـر داده بـه هر خوشه را مشخص مي کنند.
است [تا٣ب]ع : هدف الگوريتم خوشـه بنـدي فـازي FCM بـه صـورت زير
که در آن يـک مجموعـه نمونـه از n نمونـه درجـه عضـويت داده j بـه داده است ، C تعداد خوشه ها مـي باشـد، uij خوشه i اسـت و بايسـتي ١ مرکـز خوشه i مي باشد. در رابطه فوق m ضريب وزن دار درجه عضويت است روادبرط جه زيفرازبه ي ربووزدرن ساخنوي شمه ي بنشدوي ند:را کنترل مي کنـد. uij و vi بـر اسـاس روابط زیر به روز رسانی میشوند .
پارامترهاي اصلي الگوريتم FCM مجموعه داده ها و تعداد خوشه - ها مي باشند. خوشه بندي با انتخاب C داده از مجموعه داده هـاي اولي ه به عنوان مراکز اوليه خوشه ها آغاز مي شود. در ايـن الگـوريتم از فاصـله اقليدسي استفاده مي شود و درجه عضويت يک داده به يـک خوشـه بـر اساس فاصله اقليدسي آن داده به خوشه طبق رابطـه (۲) تعيـين مـي - شود. بعد از تعيين درجه عضويت ، مراکز جديد خوشه هـا طبـق رابطـه (۳) پيدا مي شوند.
اين الگوريتم طي روند بهينه سازي تناوبي با به روز رساني پيوسته درجه عضويت و مراکز خوشه ها ادامه مي يابد، تا اينکه به خوشـه بنـدي مطلوب و حداقل تابع هدف دست پيدا کند.
۲-۲- شاخص هاي اعتبار خوشه بندي فازي
بعد از اينکه تقسيم بندي فازي توسط يک الگوريتم خوشه بندي فـازي مانند FCM انجام شد، اين سوال مطرح مي شود که آيا ايـن الگـوريتم ، خوشه بندي ساختار داده اي را به درستي ارائه داده است ياخير، اين امر يـک مســاله اعتبارســنجي خوشــه اسـت . در ادامـه چنــدين شــاخص اعتبارسنجي خوشه بندي معروف ارائه شده اند.
اولين شاخص اعتبار سنجي مرتبط با FCM ضريب تقسيم بنـدي است [٣,٤] که عبارتست از:
کـه در آن . بـه طـور کلـي ، مـا تعـداد بهينـه خوشـــه هـــا (*C) بـــراي مجموعـــه داده X را، بـــا حـــل کـــردن براي توليد خوشه بندي با کارايي بالا پيدا مي - کنيم .
شاخص ديگر انتروپي تقسيم بندي [٥,٦] مي باشد که عبارتست از:
که در آن به طور کلي ما تعـداد بهينـه خوشـــه هـــا (*C) بـــراي مجموعـــه داده X را بـــا حـــل کـــردن براي توليد خوشه بندي با کارايي بـالا پيـدا مي کنيم .
شاخص هاي فوق از درجه عضويت فازي استفاده مي کنند و داراي فقدان اتصال با ساختار هندسي داده ها هستند. شاخص هاي زير به طور همزمان درجه عضويت فازي و ساختار داده ها را درنظر مي گيرند. يـک شاخص اعتبار با اين ويژگي که در [٧] با ٢=m ارائه شده اسـت و در [٨] اصلاح شده است عبارتست از:
به طور کلي ، ما تعداد بهينه خوشه ها (*C) براي مجموعه داده X را با حل کـردن بـراي توليـد خوشـه بنـدي بـا کارايي بالا پيدا مي کنيم .
شاخص اعتبار پيشنهاد شده در [٩] عبارتست از:
که در آن
SC1 و SC2 هردو ميزان فشردگي و جدايي را انـدازه مـي گيرنـد.
SC1 ويژگي هاي هندسي ساختار داده اي و درجـه عضـويت را در نظـر SC2 فقط درجه عضويت فازي را در نظر مـي گيـرد. بـه طـور کلي ، ما تعداد بهينه خوشه ها (*C) براي مجموعـه داده X را بـا حـل کردن براي توليد خوشه بندي با کارايي بالا پيدا مي کنيم .
شاخص اعتبار ارائه شده در [١٠] عبارتست از:
که در آن
ماتريس F نمايانگر ماتريس کواريانس فازي خوشـه i اسـت . بـه طــور کلــي ، مــا تعــداد بهينــه خوشــه هــا (*C) را بــا حــل کــردن براي توليد خوشه بندي با کـارايي بـالا، بـراي مجموعه داده X پيدا مي کنيم .
۳- روش پيشنهادي براي انتخاب مراکز اوليه مناسب براي خوشه ها
در اين بخش مراحل پيش پردازش پيشنهادي براي پيدا کـردن مراکـز اوليه مناسب براي خوشه ها به شرح زير ارائه مي گردد:
- ابتدا فاصله اقليدسي هر نقطه را نسبت به تمام نقـاط ديگـر محاسبه مي کنيم و در ماتريسي به نام D مي ريزيم . در اين ماتريس هر سطر بيانگر فاصله يک نقطه نسبت به تمام نقاط ديگر است .
- در مرحله بعد هر سطر ماتريس D را به طور صعودي مرتب مي کنيم و مـاتريس فواصـل مرتـب شـده بـه نـام D sort را بدست مي آوريم .
- سـپس k مقـدار اول (کـوچکتر) هـر سـطر از D sort را بـا يکـديگر جمـع مـي کنـيم و کـوچکترين مقـدار را در بـين مجموع هاي محاسبه شده در فوق بدست مي آوريم . مقدار k بايستي به صورت درصدي از n انتخاب شود، در اين مقاله و آزمايشات مربـوط بـه آن k برابـر شصـت درصـد n در نظـر گرفته شده است .
- داده مربوط به سطري از Dsort که کوچکترين مقدار مجموع k فاصله ي فوق را دارد به عنوان يـک مرکـز خوشـه ( ci) در نظر مي گيريم .
- حال بايستي داده هاي متعلق به خوشه اي که مرکـزش را در مرحله قبل بدست آورديم تعيين کنيم , براي اين کار به يک
معيار نياز داريم . معيار مزبور به اين شرح است :
به فرض انتخاب شدن داده به عنوان مرکـز يک خوشه ، فواصل موجود در ماتريس Dsort براي داده انتخاب شده بـه صورت زير داريم :
نمودار اين فواصل براي داده ي مزبور در صورتيکه ١٠=k باشد، بـه صورت شکل (۱) است .
