20735

20735

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

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

نرم افزار

1394-1397

1397/12/08

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

كامپيوتر

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

1398/04/03

Improving the Accuracy of GBoost Algorithm Using Subgraph Patterns Mining Algorithms

2/27/2019 12:00:00 AM

Classification Tasks are methods for classifying data. Graph classification tasks can either be unsupervised or supervised. Unsupervised methods classify graphs into a certain number of categories by similarity (distance similarity). In supervised classification, a classification model is contructed by learning from training data. In the training data, each graph has a target value or a class label (e.g., biochemical activity). Supervised methods are more fundamental from a technical point of view, because unsupervised learning problems can be solved by supervised methods via probabilistic modeling of latent class labels. Supervised methods for graph classification: graph kernels and graph similarity, which are similarity and feature-based respectively. Kernel methods, construct a prediction rule based on a similarity function between two objects. Graph similarity use subgraph patterns mining for graph classification. This method has less complexity and low run time. The researchs showed that in a classifier, same graph may not have similarity but have same discriminative subgraph. GBoost algorithm classifies graphs based on subgraphs mining methods. In recent years GBoost algoritm has some developing for graph data. In this paper we focused on accuracy of GBoost graph classification. We used GAIA algorithm for extracting subgraph patterns .in GBoost algorithm, Processing of graph mining executed by gSpan algoritm. gSpan algorithm used frequency measure for subgraph mining. Researchs showed that only using frequency measure for selecting subgraph mining, can’t be effective. If we just use of frequency measure, many negative subgraph patterns that can’t be mined for graph classification and we just used positive subgraph patterns. Refers to use of discriminative measure beside of frequency measure. Frequency and discirminative used in GAIA algorithm. Althought using of two measures, can’t guaranty to get all discriminative patterns, but gets more discriminative patterns compare to using just frequency measure. We recommended three methods for impoving GBoost algorithm. All of them have same processing of extracting subgraph patterns, but patterns selecting process of them are differenet. In the first recommended algorithm, we select k subgraph patterns for graph classification that k is number of positive graphs. In the second recommended algorithm we used all subgraph patterns for graph classification. Because we don’t lose any valueable subgraph patterns. In third recommended algorithm we used a new criterion to select k subgraph patterns for graph classification. We examine 6 chemical datasets for experimnet. The result of experiment showed all of three algorithm have more accuracy compare to GBoost algorithm and this recommended algorithm have comparable runtime respect to GBoost algorithm.