يادگيري تقابلي عميق آگاه از اجتماع براي خوشه بندي گراف

اصفهان : دانشگاه صنعتي اصفهان

مهندسي كامپيوتر

دكتري

خوشه¬بندي گراف يا تشخيص اجتماع يكي از مسائل مهم در تحليل گراف است. خوشه¬بندي گراف به معني انتساب گره¬هاي يك گراف به خوشه¬هاي ناهمپوشان يا همپوشان است. روش¬هاي يادگيري بازنمايي گراف، به عنوان پايه¬ي روش¬هاي خوشه¬بندي، به دو دسته¬ الگوريتم¬هاي مبتني بر بازسازي و يادگيري تقابلي دسته¬بندي مي¬شوند. بسياري از روش¬هاي موجود مبتني بر بازسازي هستند. اين روش¬ها بيش از حد بر روي اطلاعات محلي مجاورت تاكيد داشته و اطلاعات ساختاري كلي را تا حد زيادي از دست مي¬دهند. اين موضوع در مسئله¬ي خوشه¬بندي كه بدون ناظر و وابسته به اطلاعات ساختاري كلي گراف است، اهميت زيادي دارد. يادگيري تقابلي گرافي با الهام از روش¬هاي تقابلي در حوزه¬ي بينايي ماشين، به نتايج چشمگيري در حوزه¬ي گراف دست يافته است. ولي نسخه هاي اصلي روش هاي تقابلي گرافي، مبتني بر خوشه بندي نيستند. به اين معني كه بسياري از الگوريتم¬هاي تقابلي موجود براي خوشه¬بندي گراف، در دو مرحله¬ي مجزا به يادگيري بازنمايي گره¬ها و خوشه¬بندي مي¬پردازند. به اين ترتيب، يادگيري بازنمايي مستقل از خوشه-بندي صورت گرفته، از اطلاعات خوشه¬بندي بهره نمي¬برد و در نتيجه، فضاي بازنمايي حاصل براي خوشه¬بندي بهينه نيست. براي مقابله با اين مسئله، در اين رساله راهكاري جهت يادگيري تقابلي گرافي آگاه از اجتماع معرفي مي¬گردد كه از يادگيري تقابلي براي يادگيري بازنمايي بهره گرفته و به طور همزمان، ساختار خوشه¬هاي گراف را نيز براي بهينه¬سازي بازنمايي گره¬ها مدنظر قرار مي¬دهد. به اين ترتيب يادگيري بازنمايي به گونه¬اي انجام مي¬شود كه به صورت توام نه تنها اهداف يادگيري تقابلي را دنبال كند بلكه سازگار با خوشه¬بندي نيز باشد. براي اين كار، روش پيشنهادي فضاي بازنمايي حاصل از يك چارچوب تقابلي را ناچار به تبعيت از يك توزيع مخلوط گاوسي مي¬نمايد. به اين ترتيب فضاي تعبيه¬ي نهايي، سازگاري مناسبي با الگوريتم خوشه¬بندي¬اي كه در ادامه بر روي آن اعمال مي¬شود خواهد داشت. مسئله¬ي موجود ديگر آن است كه مستقل از روش يادگيري، شبكه¬هاي عصبي گرافي محدود به پيام¬هاي محلي هستند كه امر مطلوبي در تعبيه¬ و خوشه¬بندي گراف نيست. جهت تعديل اين مسئله، روش پيشنهادي به منظور دستيابي به يك منظر جهاني¬تر از گراف، از انتشار گراف بهره مي¬گيرد. استفاده از گراف انتشار به جاي گراف مجاورت در مورد بسياري از گراف¬ها به بهبود نتيجه¬ي خوشه¬بندي مي¬انجامد. روش پيشنهادي قادر است به صورت خودكار درباره استفاده يا عدم استفاده از گراف انتشار تصميم¬گيري نمايد. نتايج به دست آمده بر روي داده¬هاي حقيقي نشان¬ مي¬دهد عملكرد روش پيشنهادي به طور قابل ملاحظه¬اي نسبت به روش¬هاي اخير، به¬ويژه روش¬هاي مبتني بر يادگيري تقابلي براي خوشه¬بندي گراف، بيشتر است.

232179

هوش مصنوعي و رباتيك

مهندسي برق و كامپيوتر

دانشگاه صنعتي اصفهان