خوشه بندی داده های هندسی نادقیق براساس مسئله k -مرکز

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

کلیدواژه ها:

الگوریتم تقریبی ، الگوریتم k -مرکز ، خوشه بندی ، داده های غیرقطعی