بهبود دقت رده بندي الگوريتم gBoost با استفاده از روش هاي استخراج زيرگراف با كارايي بهتر

كارشناسي ارشد

چكيده رده¬بندي داده¬هاي گرافي مي¬تواند به صورت نظارتي يا غيرنظارتي باشد. در روش غيرنظارتي، داده¬هاي گرافي براساس معيار شباهت (فاصله بين دو زيرگراف) رده¬بندي مي¬شوند. در روش نظارتي، داده¬هاي گرافي براساس برچسب رده، رده¬بندي مي¬شوند. روش¬هاي رده¬بندي نظارتي، شامل رده¬بندي براساس توابع مركزي و رده¬بندي براساس الگوهاي گرافي است. رده¬بندي براساس الگوهاي گرافي با توجه به مرتبه¬زماني كمتر و پيچيدگي كمتر نسبت به توابع مركزي، براي رده¬بندي گراف¬ها مناسب¬ترند. يكي از مهم¬ترين الگوريتم¬هاي رده¬بندي گراف¬ها براساس الگوهاي گرافي، الگوريتم gBoost است. اين الگوريتم شامل دو مرحله براي رده¬بندي گراف¬ها است. مرحله اول با استفاده از الگوريتم gSpan به استخراج الگوهاي گرافي مي¬پردازد و مرحله دوم با استفاده از الگوريتم LPBoost گراف¬ها را رده¬بندي مي¬كند. الگوريتم gSpan از معيار فراواني براي استخراج الگوهاي گرافي استفاده مي¬كند. تحقيقات نشان داده كه استفاده از معيار فراواني به تنهايي نمي¬تواند در استخراج الگوهاي گرافي براي رده¬بندي گراف¬ها مناسب باشد. هم¬چنين اشكال ديگري كه الگوريتم gSpan دارد، در نظر نگرفتن گراف¬هاي با برچسب منفي در استخراج الگوهاي گرافي است. بنابراين الگوهاي گرافي كه هم متعلق به گراف¬هاي مثبت و هم متعلق به گراف¬هاي منفي است استخراج نمي¬شوند. الگوريتم gBoost درسال¬هاي اخير نسخه¬هاي متفاوتي از آن ارائه شده است. در تمام نسخه¬هاي ارائه شده الگوريتم gBoost از gSpan جهت استخراج الگوهاي گرافي استفاده شده است. از جمله اشكالات الگوريتم gBoost، امكان پرشدن حافظه است. هم¬چنين با كم¬تر شدن مقدار متغير حداقل پشتيباني، زمان اجرا افزيش چشم¬گيري دارد. هدف اين پايان نامه بهبود دقت الگوريتم gBoost با استفاده از الگوريتم¬هاي استخراج زيرگراف بهينه¬تر (از لحاظ استخراج الگوهاي گرافي موثرتر براي رده¬بندي) است. در اين پايان نامه سه نسخه بهبود يافته از الگوريتم gBoost ارائه شده است. در هرسه نسخه براي استخراج الگوهاي گرافي از الگوريتم GAIA، استفاده شده است. هركدام از نسخه¬ها از روش متفاوتي براي انتخاب الگوهاي استخراج شده استفاده مي¬كنند. هرسه الگوريتم پيشنهادي توانسته¬اند مشكلات پرشدن حافظه، تعيين حداقل پارامتر پشتيباني الگوريتم gBoost را برطرف¬كنند. نتايج بدست آمده از آزمايشات برروي 6 مجموعه¬داده¬ي تركيبات شيميايي، نشان مي¬دهد كه دقت هرسه الگوريتم پيشنهادي نسبت به الگوريتم gBoost افزايش قابل توجهي داشته و درعين حال زمان اجراي هرسه الگوريتم نسبت به الگوريتم gBoost قابل مقايسه مي¬باشد.

193095

دانشگاه علم و صنعت ايران

نرم افزار

دكتر عين الله خنجري ميانه