الگوریتمی تقریبی برای حل مساله ی خوشه بندی همبستگی با استفاده از عملیات ماتریسی
- سال انتشار: 1403
- محل انتشار: مجله موجک ها و جبر خطی، دوره: 11، شماره: 1
- کد COI اختصاصی: JR_WALA-11-1_005
- زبان مقاله: انگلیسی
- تعداد مشاهده: 104
نویسندگان
گروه علوم کامپیوتر،دانشگاه ولی عصر رفسنجان، رفسنجان، ایران.
چکیده
مساله ی خوشه بندی همبستگی، یکی از شهودی ترین مدل های افراز یک گراف مشابهت به اجتماعی از خوشه ها است. متاسفانه این مساله در رده ی مسائل NP-سخت قرار دارد. به همین دلیل، ارائه ی یک الگوریتم کارآ از زمان چندجمله ای که یک افراز دقیق و بهینه را برای گراف های دلخواه ایجاد نماید، بعید به نظر می رسد. در این مقاله، ابتدا یک فرمول بندی جدید از این مساله با استفاده از رویکردی حریصانه به منظور محاسبه ی پاسخی تقریبی در زمان چندجمله ای ارائه خواهیم داد. سپس، با استفاده از عملیات پایه ی ماتریسی، فرمول بندی معادل از الگوریتم ارائه شده را ارائه خواهیم کرد که در هر زبان برنامه نویسی مبتنی بر عملیات ماتریسی، به سادگی قابل پیاده سازی است. علاوه بر این، فرمول بندی ارائه شده امکان استفاده از توازی موجود در عملیات ماتریسی پایه را فراهم می نماید.کلیدواژه ها
Correlation clustering, Linear algebra, Approximation algorithmاطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.