آقای حسین علیزاده دانشجوی دکترای جناب آقای دکتر بهروز مینایی روز دوشنبه مورخ 15/02/93 ساعت 15 در دانشکده مهندسی کامپیوتر از رساله دکترای خود تحت عنوان انتخاب خوشه‌بندی ترکیبی مبتنی بر بهینه‌سازی ریاضی و اجتماعی دفاع کرد. 

  چکیده پایان نامه:  

  به مسئله خوشه‌بندی داده که در آن خوشه‌های نهایی با ترکیب یک مجموعه از نتایج خوشه‌بندی‌های پایه استخراج می‌شوند،‌ اصطلاحا مسئله خوشه‌بندی ترکیبی گفته می‌شود. همچنین، به چگونگی استخراج خوشه‌های نهایی با استفاده از تنها زیرمجموعه‌ای از نتایج مجمع اولیه خوشه‌ها، مسئله انتخاب خوشه‌بندی ترکیبی گفته می‌شود. در این رساله به مسئله خوشه‌بندی ترکیبی در حالت عام و مسئله انتخاب خوشه‌بندی ترکیبی در حالت خاص پرداخته شده است.

  در این رساله یک مدل‌سازی ریاضی مبتنی بر نمایش رشته‌ای (رشته‌های دودویی) برای مسئله خوشه‌بندی ترکیبی ارایه شده است. با توجه به غیرخطی بودن این مدل‌سازی و ناکارامدی ابزارهای ریاضی برای حل مسائل غیرخطی در حالت عمومی، از الگوریتم ژنتیک با عملگرهای ترکیب و جهش خاص‌منظوره، برای حل آن بهره گرفته شده است. همچنین، با الهام از علوم اجتماعی، یک روش خوشه‌بندی ترکیبی مبتنی بر خرد جمعی ارائه شده است. در این روش، علاوه بر بررسی پراکندگی (تنوع) نتایج حاضر در مجمع افرازهای اولیه، به استقلال آنها نیز توجه شده و روش‌های جدیدی برای ارزیابی هر دو معیار ارائه شده است.

  به خوشه‌ای که در افرازهای مختلف روی مجموعه داده‌های نمونه‌برداری‌شده به صورت متناوب تکرار شده باشد، اصطلاحا خوشه پایدار گفته می‌شود. در این رساله، یک چارچوب جدید برای مسئله انتخاب خوشه‌بندی ترکیبی ارائه شده است که در آن پس از ارزیابی پایداری خوشه‌های حاضر در مجمع، بخشی از خوشه‌های پایدارتر برای تشکیل مجمع نهایی خوشه‌ها انتخاب می‌شوند. همچنین، چند معیار جدید مبتنی بر تئوری اطلاعات برای ارزیابی پایداری خوشه ارائه شده است. برای تجمیع اطلاعات خوشه‌های انتخابی در ماتریس هم‌رویدادی، یک روش جدید به نام انباشت مدارک توسعه یافته ارائه شده است. با الهام از روش‌های مطرح شده در حوزه تحلیل شبکه‌های اجتماعی، یک مدل برنامه‌ریزی مجذوری 0-1 برای بهینه‌سازی استخراج خوشه‌هایی با بالاترین پیمانگی پیشنهاد گردیده، و سپس راهکاری برای تبدیل آن به مدل برنامه‌ریزی خطی 0-1 ارائه شد. به علاوه، یک روش جدید سلسله‌مراتبی تجمعی به نام اتصال مجموع به عنوان تابع توافقی برای بهینه‌سازی این مدل و استخراج خوشه‌های نهایی پیشنهاد شده است.

  نتایج تجربی که در آن از 17 تابع توافقی از 5 خانواده مختلف از الگوریتم‌های ترکیب‌کننده استفاده شده است، نشان می‌دهند که استفاده از چارچوب پیشنهادی انتخاب خوشه‌بندی ترکیبی منجر به بهبود بیش از 3درصدی دقت نسبت به بهترین روش مورد مقایسه روی میانگین 12 مجموعه داده استاندارد شده است.

  کلمات کلیدی: خوشه‌بندی ترکیبی، انتخاب خوشه‌بندی ترکیبی، ارزیابی خوشه، بهینه‌سازی ریاضی، بهینه‌سازی اجتماعی

  [1]

  : Abstract

  Data clustering problem in which the final partition is extracted from combining a set of base partitionings is called cluster ensemble. The procedure of extracting final clusters by combining only a subset of base partitionings is called cluster ensemble selection. This dissertation studies on cluster ensemble problem in general and cluster ensemble selection problem in particular.

  In this dissertation, a mathematical modeling based on (binary) string representation is developed for cluster ensemble problem. Since the proposed model is a nonlinear one and also the mathematical tools are inefficient in solving general nonlinear problems, we used a genetic algorithm with modified crossover and mutation operators to solve it. In addition, inspired from social science, a cluster ensemble based on the wisdom of crowd phenomenon is presented. Two important factors that are considered in this method are diversity and independency.

  A stable cluster is one that has a high likelihood of recurrence across consecutive applications of a clustering algorithm. In this dissertation a new framework for the problem of cluster ensemble selection is proposed that uses the most stable clusters to form the final ensemble. Moreover, new information-theory based criteria are suggested to evaluate the stability of individual clusters. To aggregate information from the selected clusters in a co-association matrix, a new method called extended evidence accumulation clustering is developed. Inspired from context of social network analysis, a new 0-1 quadratic programming is proposed that models the optimization problem of clustering with highest modularity. We then transformed it to a 0-1 linear model. In addition, an agglomerative hierarchical greedy algorithm named sum linkage is presented as the search strategy.

  We tested the proposed cluster ensemble selection framework using 17 consensus functions in 5 different categories over 12 standard data sets. The experimental results show that the proposed framework improves the accuracy of results more than 3% compared with a dozen of algorithms in average of all data sets.

  ارائه­دهنده:

 حسین علیزاده

  استاد راهنما:

  دکتر بهروز مینایی بیدگلی

 استاد مشاور:

دکتر مرتضی آنالویی

  هیات داوران:

دکتر محمدرضا کنگاوری، دکتر عادل رحمانی، دکتر ناصر مزینی

دکتر حمید سلطانیان‌زاده (دانشگاه تهران)، دکتر محمد رحمتی (دانشگاه صنعتی امیرکبیر)

  زمان : دوشنبه 15 اردیبهشت‏ماه 1393

  ساعت 15

  مکان: دانشکده مهندسی کامپیوتر- طبقه دوم- اتاق دفاعیه

  دانشکده مهندسی کامپیوتر مدیریت تحصیلات تکمیلی