Abstract
We consider the ensemble clustering problem where the task is to ‘aggregate’ multiple clustering solutions into a single consolidated clustering that maximizes the shared information among given clustering solutions. We obtain several new results for this problem. First, we note that the notion of agreement under such circumstances can be better captured using an agreement measure based on a 2D string encoding rather than voting strategy based methods proposed in literature. Using this generalization, we first derive a nonlinear optimization model to maximize the new agreement measure. We then show that our optimization problem can be transformed into a strict 0-1 Semidefinite Program (SDP) via novel convexification techniques which can subsequently be relaxed to a polynomial time solvable SDP. Our experiments indicate improvements not only in terms of the proposed agreement measure but also the existing agreement measures based on voting strategies. We discuss evaluations on clustering and image segmentation databases
چکیده
ما مسئله ی خوشه بندی گروهی را در نظر می گیریم که وظیفه ی اصلی آن جمع آوری همه ی راه حل های چندگانه ی خوشه بندی به یک خوشه بندی تکی تثبیت شده است که اطلاعات به اشتراک گذاشته شده را در میان راه حلهای خوشه بندی داده شده به حداکثر می رساند. ما نتایج جدید را از این مسئله به دست می آوریم. در ابتدا، ما باید توجه داشته باشیم که مفهوم توافق تحت چنین شرایطی می تواند با استفاده از معیار توافق بر پایه ی یک رمزگذاری رشته ی دو بعدی به جای استراتژی رأی گیری مبتنی بر پیشنهادات بدست آمده در ادبیات در نظر گرفته شود. با استفاده از این روند تعمیم، ما از ابتدا یک مدل بهینه سازی غیر خطی را به کار می گیریم که معیارهای توافقی جدید را به حداکثر برسانیم. سپس نشان میدهیم که مسئله ی بهینه سازی ما می تواند به برنامه ی نیمه معین 0-1 (SDP) با روش های محدب سازی جدید تبدیل شود که می تواند به یک چندجمله ای با SDP قابل حل تبدیل شود. آزمایشهای ما، پیشرفتها و بهبودهایی را نه تنها از نظر معیارهای انتخاب پیشنهادی نشان میدهد بلکه معیارهای توافق موجود بر پایه ی استراتژی های رأی گیری را نشان میدهدو ما در مورد ارزیابی خوشه بندی و پایگاه داده های تقسیم بندی صفحه به بحث می پردازیم.
1-مقدمه
در مسئله ی خوشه بندی گروهی، هدف، ترکیب راه حل های خوشه بندی چندگانه و یا پارتیشن ها به مجموعه ای از خوشه بندی منحصر به فرد تثبیت شده است که میزان اطلاعات اشتراکی ( یا توافقات) بین همه ی راه حلهای خوشه بندی موجود را به حداکثر می رساند. نیاز به این فرم خوشه بندی در بسیاری از برنامه ها حس می شود به خصوص در سناریوهای دنیای واقعی با درجه ی بالایی از عدم قطعیت مانند جداسازی تصویر با میزان ضعیف نسبت سیگنال به نویز و تشخیص بیماری به کمک کامپیوتر. بسیار شایع است که یک الگوریتم خوشه بندی تک ممکن است نتایج رضایت بخشی را تولید نکند، در حالیکه الگوریتم های متعدد ممکن است انتخاب های ناقص باشد که برخی عناصر را به خوشه های نادرست تخصیص می دهد...