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