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

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

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

189301

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

نرم افزار

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