بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
حرکت از الگوريتم ه اي k-Means و k-Medoids به سمت الگوريتم CLARANS براي خوشه بندي پايگاه داده ه اي بزرگ
چکيده
خوشه بندي داده ها بر اساس شباهت از جمله مراحل مهم در تحليل داده ها و يکي از ابزارهاي پرکاربرد در حوزه ي داده کاوي است به ويژه در مورد مجموعه داده هايي که در آن ها کشف ويژگ ي هاي مشترک بين داده ها پيش از پردازش دشوار است ، تکنيک هاي خوشه بندي جايگزين مناسبي براي تکنيک هاي نظارت شده اي چون کلاسه بندي هست د. در اين مقاله پس از بررسي جايگاه خوشه بندي در داده کاوي، دو الگوريتم k-Means و k-Medoids که از جمله پرکاربردترين الگوريتم ها در خوشه بندي هستند تحليل شده ، و در نهايت الگوريتم CLARANS به عنوان روشي براي حل مشکل خوشه بندي پايگاه داده هاي بزرگ معرفي خواهد شد.
کلمات کليدي
خوشه بندي ، کلاسه بندي ، داده کاوي، k-Means،k-Medoids ،CLARANS
a. مقدمه
خوشه بندي يکي از بهترين روش هايي است که براي مدل سازي داده ها ارائه شده است و اطلاعات را بر اساس شباهت به خوشه ها تقسيم مينمايد. قابليت آن در ورود به فضاي داده و تشخيص ساختار آنها، خوشه بندي را يکي از ايده آل ترين مکانيزم ها براي کار با دنياي عظيم داده ها کرده است . . در خوشه بندي بدون اينکه هيچ مدل از پيش معيني داشته باشيم به دنبال يافتن مدهل اي مشترکي هستيم که در داده ها وجود دارد. ايده ي اين روش در دهه ي ١٩٣٥ ارائه ش د[٢] و در حال حاضر با پيشرفت ها و جهش هاي عظيمي که در آن پديد آمده ، کاربردهاي مختلفي پيدا کرده است . در مجموعه اي از داده ها، خوشه بندي در واقع يافتن ساختار و کشف روابطي است که از طريق مشاهده عيني قابل استنتاج نيستند. و هر خوشه مجموعه اي است که اعضاي آن با يکديگر مشابه بوده و با اعضاي خوشه هاي ديگر تشابهي ندارند( يا حداقل تشابه را دارند)
a.تعريف خوشه بندي
مجموعه شامل n نقطه داده است و هر کدام از اين نقاط برابر است با يک بردار به طول s از ويژگيها (xiRs). اين نقاط بايد در k گروه به نام هاي که با يکديگر همپوشاني ندارند خوشه بندي شوند بطوريکه دو شرط را برآورده کند: ١- هر خوشه بايد حداقل يک عضو داشته باشد.٢- هر شيء از پايگاه داده بايد منحصرا متعلق به يک خوشه باش[د٢].
البته شرط دوم در تکنيک هايي که بر اساس منطق فازي تحل يل و پياده مي شوند قابل تخفيف است .
در بسياري از روشهاي ارائه شده براي خوشبه ندي، مقدار k (تعداد خوشه ها) بايد توسط کاربر تعيين شود[٥].
a.رده بندي انواع الگوريتم هاي خوشه بندي
انواع متنوعي از الگوريتم هاي خوشه بندي وجود دارد و ارائه ي يک رده بندي شفاف و تفکيک کردن کامل آنها دشوار است ، چراکه اين ردهه ا در مواردي با هم همپوشاني دارند. در نتيجه اين امکان وجود دارد که يک الگوريتم خاص ويژگيهايي از چند رده را داشته باشد. به هر حال از آنجا که ارائه ي اين رده بندي ميتواند يک تصويرکلي از انواع و جايگاه الگوريتم هاي مختلفي که در حوزه ي خوشه بندي به کار ميروند در ذهن خواننده ايجاد کند در ادامه به آن پرداخته شده اس.ت در حالت کلي الگوريتم هاي خوشه بندي را به رده هاي زير تفکيک کردند[٢،٦]:
١ -خوشه بندي سلسله مراتبي ١: فضاي مسئله را به يک ساختار سلسله مراتبي افراز ميکند.
٢ -خوشه بندي پارتيشنال ٢: درابتدا مجموعه ي داده ها را به بخش هايي تبديل کرده ، سپس با استفاده از برخي معيارها آن دستبه ندي را مورد ارزيابي قرار ميدهد و در صورت لزوم در دسته بندي اوليه تغييراتي ايجاد مينمايد.
٣ -خوشه بندي مبتني بر تراکم ٣: به جاي به کاربردن فاصله براي سنجش شباهت ، مجموعه ي داده ها را بر اساس مفه وم چگالي دسته بندي کرده ، مورد ارزيابي قرار ميدهد، و ميتوانند خوشه هايي را پيدا کنند که داراي شکلهاي پيچيده تري هستند. الگوريتم - هاي DBSCAN٤ و OPTICS٥ از جمله اين روشها ميباشند.
٤ -خوشه بندي مبتني بر شبکه بندي ٦: فضاي مسئله را به تعداد متناهي سلول تقسيم کرده و يک ساختار شبکه بندي شده ميسازد.
الگوريتم هاي STING٧ و CLIQUE٨ نمونه هايي از اين روشها هستند.
٥ -خوشه بندي مبتني بر مدل ٩ : براي هر خوشه ، مدلي فرضي را در نظر ميگيرد و هدف آن يافتن مناسب ترين مدل براي هر خوشه است . دو راه عمده براي اين کار وجود دارد : راه اول روشهاي آماري مانند COBWEB و CLASSIT، و راه دوم شبکه هاي عصبي مانند SOFM١٠ ميباشد.
٦ -خوشه بندي مبتني بر محدوديت ١١: با اعمال شرايط و محدوديت هايي که توسط کاربر تعيين ميشود، خوشه ها را ميسازد.
در ادامه به بررسي الگوريتم هاي خوشه بندي پارتيشنال پرداخته شده است ، براي مطالعه ي بيشتر در مورد ساير الگوريتم ها به [٢،٦] مراجعه شود.
a.خوشه بندي پارتيشنال
روي يک پايگاه داده با n شيء ، خوشه بندي پارتيشنال k پارتيشن از داده ها ميسازد به طوريکه هر يک از پارتيشن ها معرف يک خوشه است .
الگوريتم هاي پارتيشنال مقدارk را به عنوان ورودي گرفته و يک پارتيشن بندي اوليه روي داده ها انجام ميدهند، در ادامه در يک حلقه تکرار تا رسيدن به بالاترين شباهت بين داده هاي هر پارتيشن و بالاترين اختلاف بين داده هاي پارتيشن هاي مجزا، کيفيت پارتيشن ها (خوشه ها) تا حد امکان به حداکثر مي رسد. روش هايي براي محاسبه ي اينکه داده ها چه اندازه خوب در خوشه ها قرار گرفتند وجود دارد، از جمله روش هاي اکتشافي ١٢ و پرکاربرد الگوريتم هاي k-means و k-Medoids هستند. روش k-means در کتاب ١٠ الگوريتم پرکاربرد در داده کاوي[٣] به عنوان دومين الگوريتم پرکاربرد در داده کاوي معرفي شده است و از يک معيار اندازه گيري فاصله براي نسبت دادن نقاط داده به نزديک ترين خوشه استفاده ميکند. هر دو روش نامبرده جزءمتدهاي کلاسيک خوشه بندي پارتيشنال هستند که در ادامه بررسي شدند
الگوريتم K-means
دو هدف اصلي در اين الگوريتم دنبال ميشود، هدف اول بدست آوردن نقاطي به عنوان مراکز خوشه ها است ، که اين نقاط در واقع همان مقدار ميانگين نقاط متعلق به هر خوشه هستند و دوم نسبت دادن هر نمونه داده به يک خوشه به طوريکه داده کمترين فاصله ات مرکز آن خوشه را دارا باشد. فضاي مسئله اي n بعدي را در نظر بگيريد، نقاط داده در اين فضا به صورت قابل تعريف است . در -kmeans هر يک از خوشه ها با يک نقطه واحد که همان مرکز ١٣ يا مقدار ميانگين ١٤ خوشه است نمايش داده مي شوند. مجموعه ي
معرف مرکز خوشه هاست . برداري نيز به نام M براي ذخيره ي شماره خوشه ي منتسب به هر يک از نقاط داده در نظر گرفته ميشود، که در آن هر mi شماره ي خوشه براي داده ي xi است . در الگوريتم k-means معيار پيش فرض براي اندازه گيري شباهت داده ها فاصله ي اقليدسي ١٥ است و ال گوريتم به دنبال مينيمم کردن مجموعِ توان دوِ فاصله اقليدسي بين هر و منتسبِ آن است [٣]:
در شکل ١ خلاصه اي از الگوريتم k-means ارائه شده است و شکل ٢ مثالي از اعمال الگوريتم روي مج موعه اي از داده هاست
شکل ١ : الگوريتم k-means
