چکیده خوشه بندی داده های بزرگ مربوط به مسئله بدست آوردن خوشه های نهایی یک سری داده از یک مجموعه داده بزرگ است که به عنوان ورودی به مسئله داده شده اند.
در این مقاله، مسئله خوشه بندی داده های بزرگ به صورت یک مسئله بهینه سازی چند هدفه مدلسازی شده و یک الگوریتم پردازش تکاملی چندهدفه برای این مسئله استفاده می شود.
الگوریتم پردازش تکاملی چندهدفه برای خوشه بندی داده های بزرگ که در اینجا معرفی شده است MOECEA نام دارد و شامل مجموعه جواب خوشه بندی بهینه همزمان روی ورودیهای دو ضابطه است.
ضابطه اول ماکسیمم سازی تشابه خوشه های نهایی با تمامی خوشه های ورودی به مسئله است که این شباعت بین دو روش توسط شاخص ARI بدست می آید و ضابطه دوم مینیمم سازی انحراف معیار برای جلوگیری از تشابه بیش از حد خوشه های نهایی با یکی از خوشه های ورودی و عدم تشابه با دیگر خوشه ها است.
کارایی این الگوریتم با دیگر الگوریتم ها ی خوشه بندی شناخته شده و در ازای چند مجموعه داده حقیقی و مجازی مقایسه شده است.
مقدمه کلاس بندی بدون سرپرست در زمینه پردازش تصویر و داده کاوی و تشخیص الگوها توجه محققین را به طور وسیعی به خود جلب نموده است.
در گذشته خوشه بندی برای گروه بندی المانها در مجموعه های داده ای و بر اساس شباهت انجام می شد.بنابراین خوشه بندی دقیق تر به این معناست که المانهای یک خوشه دارای حداکثر تشابه از لحاظ برخی شرایط باشند، در حالیکه نسبت به دیگر خوشه ها دارای حداکثر تفاوت هستند.
هنگامیکه چندین الگوریتم خوشه بندی بر روی یک مجموعه داده اعمال می شود، نتایج خوشه بندی بسیار متفاوتی به دست می آید.
این نتایج متفاوت ناشی از خوشه بندی با الگوریتم های مختلف به دلیل ملاحظات متفاوت در مجموعه داده های به صورت مدلهای متفاوتی فرض می شوند.
این امر ممکن است باعث ایجاد برخی نتایج نادرست در خوشه بندی نهایی شود.
الگوریتم های خوشه بندی داده های بزرگ به طور اساسی برای مجتمع نمودن راه حلهای خوشه بندی در جهت دستیابی به یک راه حل قابل اطمینان و دقیق است.
یافتن یک مجموعه جواب بهینه از بین چند مجموعه جواب کار بسیار مهم و مشکلی است.
هنگامی که مجموعه جوابهای متفاوتی از یک مجموعه داده ای به دست می آید به این معناست که دانش اولیه درباره توزیع داده ها در دسترس نیست.
مجددا همان طور که المانهای متفاوت دارای خصوصیات متفاوتی هستند، بنابراین روش گروه بندیشان نیز در الگوریتمهای خوشه بندی متفاوت با هم فرق دارد.
علاوه بر اینها در الگوریتمهای خوشه بندی ، روش گزوه بندی به روش های مختلفی انجام می شود.
برای مثال الگوریتم های خوشه بندی K-means مجموعه داده ها را طوری گروه بندی می کند که MSE هسته هر خوشه حداقل باشد در حالیکه روش های پارتیشن بندی بر پایه گراف در خوشه بندیها، یک گراف را به K قسمت تقسیم میکند و این کار بر اساس اندازه مینیمم وزن یال انجام می گیرد.
بنابراین دسترسی به نتیجه نهایی در مورد اینکه کدام روش خوشه بندی مناسب تر است بسیار مشکل خواهد بود.
بنابراین در حال حاضر هدف از خوشه بندی داده های بزرگ باری ترکیب نقاط قوت چندین الگوریتم خوشه بندی خواهد بود.
این مطلب نقطه تمرکز مطالعه اخیر در خوشه بندی داده های بزرگ و جستجو برای یک ترکیب مناسب از چندین پارتیشن است که بر روی خوشه بندی داده های بزرگ انجام گرفته.
خوشه بندی داده های بزرگ می تواند فراتر از چیزی باشد که در حالت معمول توسط یک الگوریتم خوشه بندی روی داده های اولیه بدست می دهد، مثلا از لحاظ مقاوم بودن و جدید بودن و پایداری و اطمینان نسبت به روش تخمین.
بنابراین دسترسی به مجموعه جواب نهایی توسط مجتمع سازی خوشه بندیهای متفاوت روی داده های بزرگ بسیار مناسب تر است.
در این مقاله ما یک مسئله خوشه بندی داده های بزرگ را به عنوان یک مسئله بهینه سازی مطرح نمودیم و هدف از این کار دسترسی به یک راه حل خوشه بندی مناسب است که مشابه با مجموعه جوابهای ورودی باشند و بنابراین انتظار می رود که اجماع مناسبی روی این روشهای خوشه بندی انجام گیرد.
بنابراین این مسئله می تواند به صورت یک مسئله بهینه سازی چند منظوره MOO مدلسازی شود که همزمان دو هدف کلی را بهینه سازی خواهد نمود.
هدف اولیه برای ماکسیمم سازی شباهت خوشه های نهایی با تمام خوشه های ورودی است در حالیکه شباهت بین دو خوشه توسط شاخص ARI به دست می آید.
هدف دوم حداقل نمودن انحراف معیار بین نرخ شباهتها برای جلوگیری از این مطلب است که یکی از خوشه های نهایی بسیار مشابه با یکی از خوشه ها و متفاوت از دیگر خوشه ها شود.
در مسئله MOO، جستجو بر روی تعدادی و یا چند تابع هدف که با هم هم پوشانی دارند انجام می گیرد.
در مسئله های یک هدفه معمولا بهترین مجموعه جواب به دست می آید.
به هر حال در مسائل MOO مجموعه جواب نهایی شامل تعدادی از جوابهای بهینه نسبی است که هیچ یک بر روی اهداف مسئله پیشرفتی نداشته اند و در دیگر روش ها هم هم پوشانی نداشته باشند.
الگوریتم ژنتیک مرتب سازی غیر حوزه ای NSGA.ll یک الگوریتم MOO بسیار مرسوم است که به صورت استراتژی بهینه سازی به کار می رود.
شاخص ARI و انحراف معیار به عنوان تابع های هدف به کار می روند.
الگوریتم تکاملی چندهدفه خوشه بندی داده های بزرگ MOECEA بر روی تعدادی از مجموعه داده های حقیقی و مجازی اعمال شده و کاربرد آن توسط چندین تکنیک خوشه بندی داده های بزرگ برای تعیین نمودن نقاط قوت بررسی شده است.
2- روش خوشه بندی داده های بزرگ چندهدفه معرفی شده این بخش کاربرد روش NSGA.ll را بر روی مجموعه ای از مجموعه جوابهای خوشه بندی بهینه داده های بزرگ توضیح می دهد.
روش معرفی شده به صورت دقیق تر در ادامه توضیح داده می شود: 2.1 – کد نمودن کروموزوم ها هر کروموزوم دنباله ای از اعداد صحیح است که لیبل هر یک از K کلاس را نشان می دهد.
برای مثال یک کروموزوم به صورت مجموعه (r1,r2,…,rn) نشان داده می شود و ri به صورت لیبل این کلاس برای این داده ها تعیین می شود.
در روش های متفاوت خوشه بندی ممکن است دو لیبل با هم همپوشانی داشته باشند مثلا در دو موقعیت متفاوت کروموزوم ها، لیبل کلاس ها از لحاظ تعداد مساوی باشند.
فرض کنید دو کروموزوم 1 و 2و به صورت دنباله های (1،1،1،2،2،2،3،3) و (1،2،2،2،2،3،3،3) باشند.
در اینجا شمای کدگذاری کروموزوم اول در خوشه اول 1،2،3 و 4،5،6 در خوشه دوم و 7،8 در خوشه سوم خواهد بود.
بنابراین ماکسیمم تعداد خوشه ها 3 خوشه می شود.
2.2 – جمعیت اولیه در جمعیت اولیه، کل مجموعه ورودی از خوشه ها را برای داده های بزرگ و برای تولید جمعیت های بعدی در نظر می گیریم.
علاوه بر اینها، هم چنین چند راه حل خوشه بندی تصادفی هم برای جلوگیری از ایجاد بایاس در نظر می گیریم.
2.3 – تابع انتخاب در پروسه انتخاب کروموزوم ها برای تولید مثل دوره بعدی توسط بهترین و مناسب ترین نمونه ها باید از مفهوم ژنتیک در سیستم های طبیعی استفاده کنیم.
در استراتژی تورنمنت باینری ، این کار به صورت چندین تورنمنت از بین چند نمونه انجام می شود که این نمونه ها به صورت تصادفی از جمعیت اولیه انتخاب شده باشند.
اما در مفهوم خوشه بندی داده های بزرگ چند هدفه، انتخاب بر اساس استراتژی انتخاب تورنمنت باینری انجام می گیرد که مشابه با روش NSGA.ll است.
2.4 – تولید مثل تولید مثل یک پروسه احتمالی است که اطلاعات در کروموزوم والد را برای تولید فرزند تغییر می دهد.
در این مفهوم، تولید مثل توسط احتمال ثابت Kc انجام می گیرد.
در الگوریتم ژنتیک اولیه مفهوم تولید مثل معمولا به صورت یک نقطه داده یا به صورت تولید مثل چند نقطه ای انجام می شود.
اما در روش خوشه بندی داده های بزرگ، این نوع تولید مثل ممکن است ترکیب اولیه جمعیت را بر هم زند و هم گرایی نهایی مجموعه جواب را تحت تاثیر قرار دهد.
برای مثال، دو کروموزوم 1 (1،1،1،2،2،3) و کروموزوم 2 (3،3،3،1،1،2) را در نظر می گیریم.
حال این دو کروموزوم که در اصل نتایج خوشه بندی های یکسان هستند، در هر دو حالت در ابتدا 3 نمونه در یک خوشه قرار می گیرد و نمونه 4و 5 در خوشه دوم و نمونه 6 در خوشه آخر.
بنابراین همگی میزان تابع ارزش یکسانی خواهند داشت.
اما در تولید مثل یک نقطه ای، این کار تنها در موقعیت 5 انجام می گیرد و سپس کروموزوم ها به صورت (1،1،1،2،1،2) و (3،3،3،1،2،3) خواهند بود.
همانطور که مشاهده می شود، در فرزند اول ، تعداد خوشه ها تغییر نموده است.
برای جلوگیری از وقوع این تغییرات فرض کنید کروموزوم 1 (1،3،1،2،1،2،3،1،3) و کروموزوم 2 (2،2،2،3،3،3،1،1،1)را داریم، میزان تفاوت دو خوشه متفاوت برای این دو کروموزوم به صورت زیر خواهد بود: در اینجا نرخ تفاوت خوشه i از کروموزوم 1 با خوشه j از کروموزوم 2 محاسبه می شود.
Ci به معنای سایز خوشه i است.
برای مثال تفاوت خوشه 1 از کروموزوم 1 و خوشه 1 از کروموزوم 2 به صورت 0.708 = 2 / (3/4 + 2/3 ) خواهد بود.
در کروموزوم 1، نمونه های 1،3،5،8 در خوشه اول قرار می گیرند در خالیکه در کروموزوم 2، نمونه های 7،8،9 در خوشه اول قرار می گیرند.
بنابراین تنها 8 نمونه در هر دو کروموزوم قرار می گیرند.
سایز خوشه 1 از کروموزوم 1 به اندازه 4 است در حالیکه سایز خوشه 1 از کروموزوم 2 به اندازه 3 است.
پس از محاسبه ماتریس تفاوت، یک گراف برای بررسی نرخ تفاوتها طراحی می کنیم.
در مثال ما، این گراف دارای 3 رای در هر مجموعه خواهد بود.
در مجموعه سمت چپ، سه راس و در مجموعه سمت راست هم 3 راس داریم.
هر یک از رئوس نشان دهنده کدینگ یک خوشه در یک کروموزوم هستند.
از این گراف می توان جابجایی درایه های ماتریس را به دست آورد که در اصل همان لیبلهای نهایی کروموزوم 2 بر کروموزوم 1 است.
مراحل ساخت و جابجایی در ماتریس به صورت زیر است : جستجو برای لبه با حداقل وزن در گراف ذخیره دو رای منتی به این یال پس از ذخیره وزن یال، تمامی یالهای وابسته به رئوس سمت راست مجموعه حذف می وند.
تکرا مرحل بالایی برای دیگر یالها این جابجایی در ماتریس باعث می شود اطلاعات لیبلهای کروموزوم 2 ذخیره شوند که توسط اطلاعات کروموزوم 1 جابجا می شوند.
بنابراین اگر دو کروموزوم در تولید مثل شرکت کنندریال پس از تولید مثل تنها لیبل کروموزوم دوم تغییر می کند.
مجددا این روش تولید مثل ، تضمین می کند که دو کروموزوم والد که نشانگر یک روش حل هستند، حتما تحت تاثیر روش تولید مثل قرار نخواهند گرفت.
به عبارت دیگر برای دو کروموزوم که یک روش حل را نشان ندهند می توان با یک پروسه مشابه مجددا لیبل گذاری انجام داد و دو کروموزوم فرزند جدید را پس از تغییر اطلاعات والد ها تولید نمود.
2.5 – جهش هر کروموزوم با یک احتمال خیلی کم Mp تحت تاثیر عملگر جهش قرار می گیرد.
در این عملگر ما می توانیم برخی کمیات را روی لیبل کروموزوم ها کم یا زیاد کنیم.
برای اهداف محاسباتی ، تعداد ارقام اعشار بدست آمده برای یک لیبل خاص به نزدیکترین عدد صحیح گرد می شود.
2.6 – انتخاب تابع هدف الگوریتم ما شامل دو تابع هدف است.
در اینجا تشابه بین خوشه های مرجع و خوشه های اولیه را در ابتدا محاسبه می کنیم و سپس مجموعه تشابهات آنها توسط تعداد مجموعه جوابها بررسی می شود.
که به صورت تابع هدف اولیه در نظر گرفته خواهد شد.
برای محاسبه شباهت میان دو خوشه نهایی، از شاخص ARI استفاده می کنیم.
برای جلوگیری از شباهت خوشه های نهایی کد شده با یکی از خوشه های اولیه ورودی و افزایش میزان تابع هدف اولیه، باید میزان انحراف معیار شباهت ها بین مجموعه جوابهای کد شده در خوشه های ورودی را به حداقل برسانیم و این کار همان تابع هدف دوم است.
بنابراین تابع هدف اولیه بر اساس ماکسیمم سازی و تابع هدف دوم بر اساس مینیمم سازی بنا شده است.
2.7 – انتخاب یک مجموعه جواب از بین مجموعه جوابهای غیر اصلی در نسل نهایی، روش خوشه بندی با چند تابع هدف و یک مجموعه غیر اصلی و مشابه با جواب بهینه از کل مجموعه داده ها استفاده میی کند.
بنابراین، لازم است که یک راه حل خاص از بین مجموعه جوابهای غیراصلی انتخاب شود.
راه حل بهینه توسط آنالیز و تحلیل نواحی شاخه شاخه شده بدست می آید.
ایده این کار برای تتاکید بر این مطلب است که مجموعه جواب نهایی با مجموعه شاخه شاخه شده همگرایی دارد.
این شاخه شاخه شدن توسط مجموعه جوابهایی به وجود می آید که مشابه مجموعه جواب نهایی بهینه هستند و البته تغییر مثبت کوچکی در آنها انجام شده که البته باعث بدتر شدن دیگر تابع هدف می شود.
بنابراین در این الگوریتم پیشنهادی ، قابل قبول ترین مجموعه جواب از بین جوابهایی انتخاب می شود که مشابه با جواب بهینه هستند و تغییر مثبت اندک انها باعث بدتر شدن تابع هدف دیگر شده است.
3- طراحی تجربی و نتایج در این بخش ، در ابتدا مجموعه داده های استفاده شده در تحقیق خود را معرفی می کنیمو ما در این تحقیق بر روی چند مجموعه داده حقیقی و نیز چند مجموعه داده مجازی انجام دایم تا کارایی و عملکرد الگوریتم معرفی شده را بررسی کنیم.
این الگوریتم توسط سه الگوریتم خوشه بندی داده های بزرگ موجود که CSPA,HGPA,MCLA نام دارند و نیز با دیگر نسخه همین الگوریتم که از یک تابع هدف استفاده می کند، بررسی و ارزیابی شده است.
معیارهای قابل قبول شامل ARI,MI,Sillhoutte و دیگر شاخص های معتبر خوشه بندی هستند.
در اینجا روش خوشه بندی داده های بزرگ با یک تابع هدف از نرخ تابع هدف اولیه MOECEA روی تعدادی از خوشه های ورودیها استفاده می کند ، برای مثال میانگین شباهت مجموعه جواب کدشده با مجموعه جوابهای خوشه بندی ورودیها.
مجموعه جوابهای خوشه بندی ورودیها توسط یکی از زیر مجموعه های الگوریتم های K-means و دیگر الگوریتم های خوشه بندی به دست می آید.
تمام این بررسی ها در محیط متلب نسخه 2008a انجام شده و محیط اجرایی آن یک سیستم cpu 1.6 Ghz (intel.R) و 1 GB حافظه رم و ویندوز xp Professional می باشد.
3.1 – مجموعه داده ها سه مجموعه داده حقیقی برای تحقیق مورد استفاده قرار گرفت.
یک توضیح بیرا مختصر از مجموعه های داده های اولیه از لحاظ تعداد داده ها، ابعاد آنها و تعداد خوشه ها در جدول 1 نشان داده شده است.
این سه مجموعه داده از داده های UCI برگرفته شده اند.
توضیح مجموعه داده های مجازی هم در جدول 2 ارائه شده است.
جدول 1 – توضیحات مربوط به مجموعه داده های حقیقی جدول 2- توضیحات مربوط به مجموعه داده های مجازی 3.2 – معیارهای بررسی عملکرد برخی شاخص های بیرونی و درونی برای ارزیابی خوشه ها به صورت معیارهای عملکردی به کار گرفته شده است.
شاخص های بیرونی مثل ARI, RI, MS, CA, ML, HI هستند که برای ارزیابی عملکرد الگوریتم با توجه به خوشه بندی صحیح مجموعه داده ها به کار گرفته شده اند.
در اینجا مقادیر بیشتر شاخص های ARI, RI, CA, HI و مقادیر کمتر برای شاخص های MS, MI نشان دهنده خوشه بندی بهتر است.
از طرف دیگر ، شاخص های اعتبار سنجی درونی مثل شاخص DB, Dunn index, Sillhoutte index از میان این شاخص ها، مقادیر کمتر شاخص DB و مقادیر بیشتر شاخص های Dunn, Sillhoutte نشان دهنده خوشه بندی دقیق تر هستند.
3.3 – تنظیم پارامترها تعدادی از پارامترها در خوشه های متفاوت برای مجموعه داده های خاص ثابت هستند.
در الگوریتم پیشنهادی، نرخ تولید مثل 0.9 ، نرخ جهش 0.01 و اندازه جمعیت هم 40 در نظر گرفته شده است.
3.4 – نتایج در جداول 3 تا 6 معیارهای عملکردی به دست آمده از الگوریتم های مختلف خوشه بندی داده های بزرگ، در معیار مجموعه داده گزارش شده اند.
از این جدولها کاملا مشخص است که با وجود نمونه های کم در دسترس اما برخی از الگوریتم ها بهتر عمل نموده اند اما در اکثر حالات، الگوریتم چند هدفه پیشنهادی تقریبا عملکرد مناسب تری داشته ایت.
علاوه بر اینها، از نسخه یک تابع هدف در الگوریتم نیز بهتر نتیجه داده است که نشان دهنده جامع بودن قالب کاری چند تابع هدف برای پیشبرد الگوریتم پیشنهادی می باشد.
جدول 3- مقادیر مربوط به معیارهای کاربردی در مجموعه داده wine جدول 4- مقادیر مربوط به معیارهای کاربردی در مجموعه داده Iris جدول 5 - مقادیر مربوط به معیارهای کاربردی در مجموعه داده Seed جدول 6- مقادیر مربوط به معیارهای کاربردی در مجموعه داده R15 3.5 – جبهه تشابهی در مجموعه داده های متفاوت جهت توضیحات بیشتر، شکلهای 1 و 2 نشان می دهند که روش های غیر همگرای بدست آمده از الگوریتم های خوشه بندی چند تابع هدف برای داده های بزرگ در مجموعه داده های wine , Iris, Seed , R15 چگونه است.
این اشکال هم چنین نشان می دهند که مجموعه جوابهای بدست آمده از دیگر الگوریتم ها روی همان مجموعه داده و همان تابع هدف چگونه است.
علاوه بر اینها، مجموعه جوابهای شاخه شاخه شده انتخاب شده نیز در شکلها علامتگذاری شده اند.
شکل 1- a: مجموعه داده wine – b: مجموعه داده Iris شکل 2 – a: مجموعه داده Seed – b: مجموعه داده R15 4 – نتایج دراین مقاله، یک الگوریتم تکاملی خوشه بندی داده های بزرگ چند تابع هدف MOECEA معرفی شده که روی قالب کاری الگوریتم ژنتیک معمولی با چند تابع هدف انجام گرفت NSGA.ll.
تابع های هدف ماکسیمم سازی شباهت مجموعه جوابهای خوشه بندی داده های بزرگ با داده های ورودی و مینیمم سازی انحراف معیار این شباهت ها برای جلوگیری از ایجاد بایاس بود.
عملکرد الگوریتم معرفی شده توسط الگوریتم های موجود برای مجموعه داده های حقیقی و مجازی مورد بررسی قرار گرفت.
نتایج نشان دهنده کارایی بیشتر تکنیک معرفی شده نسبت به دیگر الگوریتم ها است.