16912

16912

خوشه بندي گراف با توجه به ويژگي هاي ساختاري گراف و محتواي داخلي گره ها

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

نرم افزار

دي 1395

آقاي حسن نادري

كامپيوتر

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

1395/12/18

1/1/1900 12:00:00 AM

Common clustering methods, regardless of the content of the node an​d only relying on the Structure graph, clustering doing. However, the use of content nodes during of structural clustering can boost the meaningfulness of clusters. In fact, the purpose of graph clustering problem is detection clusters with coherent internal structure an​d homogeneous attribute values. It is quite challenging because of similarities in structure an​d content, independent look o​r even at cross-purposes an​d must balance between them. Moreover, in most clustering methods available is taken into account only one aspect of the structure o​r content. However, recently a number of methods proposed, which clustering structure an​d content as they do. However, given that the usual method of clustering, clustering based on the structure of the graph are doing most of the existing eva​luation measure are structural measure. For this reason, existing eva​luation methods using these measures, can not accurately an​d desirable to eva​luate the structural-content clustering methods. In this thesis, a clustering method based propagation label named SC-Cluster is proposed. This method by balancing the similarity of structure an​d content, to properly perform clustering. In addition, the clustering method for more accurate eva​luation of structural-content clustering, SC-ErrorLink measure is proposed. This measure, by considering both the structure an​d content of the eva​luation does. The results show that the proposed clustering method with balance between structural an​d content aspects clusters, detects clusters of more favorable.