یک روش جدید برای خوشه بندی با استفاده از مسئله مینیمم سازی هزینه شارminimum cost flow

دراینمقاله یک روش جدید خوشه بندی معرفی شده است که از الگوریتم های بهینه سازی ترکیبیاتی که برای حل مسئله مینیمم سازی هزینه جریان بکار می روند استفاده می کند درواقع با حل مساله مینیمم هزینه شار Minimum cost flow برای گراف کامل متشکل از داده ها درختی حاصل خواهد شد که در آن مسیر بین هر دو نود مینیمم خواهد بود و به عنوان معیاری برای تشخیص نزدیکی داده های مشابه به منظور هم خوشه قرار دادن آنها بکار خواهد رفت اما برای تشخیص خوشه ها از روی این درخت باید آنرا به زیرگرافهایی تقسیم کرد که این کار توسط حذف یالهای ناهمگون که اندازه هزینهآنها در مقایسه با میانگین اندازه هزینه یالهای همسایه اش خیلی بزرگ است انجام می گیرد.

کلیدواژه ها:

خوشه بندی ، مینیمم هزینه شار ، زیرگراف ، گراف درختی ، یال ناهمگون