چکیده
خوشه بندی داده های بزرگ مربوط به مسئله بدست آوردن خوشه های نهایی یک سری داده از یک مجموعه داده بزرگ است که به عنوان ورودی به مسئله داده شده اند. در این مقاله، مسئله خوشه بندی داده های بزرگ به صورت یک مسئله بهینه سازی چند هدفه مدلسازی شده و یک الگوریتم پردازش تکاملی چندهدفه برای این مسئله استفاده می شود. الگوریتم پردازش تکاملی چندهدفه برای خوشه بندی داده های بزرگ که در اینجا معرفی شده است MOECEA نام دارد و شامل مجموعه جواب خوشه بندی بهینه همزمان روی ورودیهای دو ضابطه است. ضابطه اول ماکسیمم سازی تشابه خوشه های نهایی با تمامی خوشه های ورودی به مسئله است که این شباعت بین دو روش توسط شاخص ARI بدست می آید و ضابطه دوم مینیمم سازی انحراف معیار برای جلوگیری از تشابه بیش از حد خوشه های نهایی با یکی از خوشه های ورودی و عدم تشابه با دیگر خوشه ها است. کارایی این الگوریتم با دیگر الگوریتم ها ی خوشه بندی شناخته شده و در ازای چند مجموعه داده حقیقی و مجازی مقایسه شده است.
مقدمه
کلاس بندی بدون سرپرست در زمینه پردازش تصویر و داده کاوی و تشخیص الگوها توجه محققین را به طور وسیعی به خود جلب نموده است. در گذشته خوشه بندی برای گروه بندی المانها در مجموعه های داده ای و بر اساس شباهت انجام می شد.بنابراین خوشه بندی دقیق تر به این معناست که المانهای یک خوشه دارای حداکثر تشابه از لحاظ برخی شرایط باشند، در حالیکه نسبت به دیگر خوشه ها دارای حداکثر تفاوت هستند. هنگامیکه چندین الگوریتم خوشه بندی بر روی یک مجموعه داده اعمال می شود، نتایج خوشه بندی بسیار متفاوتی به دست می آید. این نتایج متفاوت ناشی از خوشه بندی با الگوریتم های مختلف به دلیل ملاحظات متفاوت در مجموعه داده های به صورت مدلهای متفاوتی فرض می شوند. این امر ممکن است باعث ایجاد برخی نتایج نادرست در خوشه بندی نهایی شود. الگوریتم های خوشه بندی داده های بزرگ به طور اساسی برای مجتمع نمودن راه حلهای خوشه بندی در جهت دستیابی به یک راه حل قابل اطمینان و دقیق است. یافتن یک مجموعه جواب بهینه از بین چند مجموعه جواب کار بسیار مهم و مشکلی است. هنگامی که مجموعه جوابهای متفاوتی از یک مجموعه داده ای به دست می آید به این معناست که دانش اولیه درباره توزیع داده ها در دسترس نیست. مجددا همان طور که المانهای متفاوت دارای خصوصیات متفاوتی هستند، بنابراین روش گروه بندیشان نیز در الگوریتمهای خوشه بندی متفاوت با هم فرق دارد. علاوه بر اینها در الگوریتمهای خوشه بندی ، روش گزوه بندی به روش های مختلفی انجام می شود. برای مثال الگوریتم های خوشه بندی K-means مجموعه داده ها را طوری گروه بندی می کند که MSE هسته هر خوشه حداقل باشد در حالیکه روش های پارتیشن بندی بر پایه گراف در خوشه بندیها، یک گراف را به K قسمت تقسیم میکند و این کار بر اساس اندازه مینیمم وزن یال انجام می گیرد. بنابراین دسترسی به نتیجه نهایی در مورد اینکه کدام روش خوشه بندی مناسب تر است بسیار مشکل خواهد بود. بنابراین در حال حاضر هدف از خوشه بندی داده های بزرگ باری ترکیب نقاط قوت چندین الگوریتم خوشه بندی خواهد بود. این مطلب نقطه تمرکز مطالعه اخیر در خوشه بندی داده های بزرگ و جستجو برای یک ترکیب مناسب از چندین پارتیشن است که بر روی خوشه بندی داده های بزرگ انجام گرفته. خوشه بندی داده های بزرگ می تواند فراتر از چیزی باشد که در حالت معمول توسط یک الگوریتم خوشه بندی روی داده های اولیه بدست می دهد، مثلا از لحاظ مقاوم بودن و جدید بودن و پایداری و اطمینان نسبت به روش تخمین. بنابراین دسترسی به مجموعه جواب نهایی توسط مجتمع سازی خوشه بندیهای متفاوت روی داده های بزرگ بسیار مناسب تر است.
در این مقاله ما یک مسئله خوشه بندی داده های بزرگ را به عنوان یک مسئله بهینه سازی مطرح نمودیم و هدف از این کار دسترسی به یک راه حل خوشه بندی مناسب است که مشابه با مجموعه جوابهای ورودی باشند و بنابراین انتظار می رود که اجماع مناسبی روی این روشهای خوشه بندی انجام گیرد.
بنابراین این مسئله می تواند به صورت یک مسئله بهینه سازی چند منظوره MOO مدلسازی شود که همزمان دو هدف کلی را بهینه سازی خواهد نمود. هدف اولیه برای ماکسیمم سازی شباهت خوشه های نهایی با تمام خوشه های ورودی است در حالیکه شباهت بین دو خوشه توسط شاخص ARI به دست می آید. هدف دوم حداقل نمودن انحراف معیار بین نرخ شباهتها برای جلوگیری از این مطلب است که یکی از خوشه های نهایی بسیار مشابه با یکی از خوشه ها و متفاوت از دیگر خوشه ها شود. در مسئله MOO، جستجو بر روی تعدادی و یا چند تابع هدف که با هم هم پوشانی دارند انجام می گیرد. در مسئله های یک هدفه معمولا بهترین مجموعه جواب به دست می آید. به هر حال در مسائل MOO مجموعه جواب نهایی شامل تعدادی از جوابهای بهینه نسبی است که هیچ یک بر روی اهداف مسئله پیشرفتی نداشته اند و در دیگر روش ها هم هم پوشانی نداشته باشند. الگوریتم ژنتیک مرتب سازی غیر حوزه ای NSGA.ll یک الگوریتم MOO بسیار مرسوم است که به صورت استراتژی بهینه سازی به کار می رود. شاخص ARI و انحراف معیار به عنوان تابع های هدف به کار می روند. الگوریتم تکاملی چندهدفه خوشه بندی داده های بزرگ MOECEA بر روی تعدادی از مجموعه داده های حقیقی و مجازی اعمال شده و کاربرد آن توسط چندین تکنیک خوشه بندی داده های بزرگ برای تعیین نمودن نقاط قوت بررسی شده است.