عنوان پایان‌نامه
جستجوی شباهت در شبکه های نا همگن
- رشته تحصیلی
- مهندسی فناوری اطلاعات - سامانه های شبکه ای
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه دانشکده علوم و فنون نوین شماره ثبت: 581;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 79244;کتابخانه دانشکده علوم و فنون نوین شماره ثبت: 581;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 79244
- تاریخ دفاع
- ۰۴ مهر ۱۳۹۵
- دانشجو
- گلناز نیک مهر
- استاد راهنما
- مصطفی صالحی
- چکیده
- جستجوی شباهت یک موضوع پایه در یادگیری ماشین، پایگاه داده و داده‌کاوی است. این موضوع در کاربردهای متفاوتی همچون خوشه‌بندی اشیا، سیستم‌های توصیه‌گر و موتورهای جستجوی وب مورد استفاده قرار می‌گیرد. این موضوع از سال‌های گذشته مورد علاقه بسیاری از محققان بوده است اما در ابتدا تمرکز محققان برای جستجوی شباهت در شبکه‌ها (به عنوان شبکه‌های اطلاعات همگن) بود. با ظهور مفهوم شبکه‌های اطلاعات ناهمگن موضوع جستجوی شباهت در چنین شبکه‌هایی اهمیت خاصی به خود گرفت. منظور از شبکه‌های اطلاعات ناهمگن، شبکه‌ای است که در آن اشیا و روابط بین آن‌ها از انواع مختلفی تشکیل می‌شود، به عنوان مثال شبکه اطلاعات کتاب‌شناسی می‌تواند شامل اشیایی چون مقاله، نویسنده و کنفرانس باشد. اهمیت مطالعه این نوع شبکه‌ها در این است که در دنیای واقعی شبکه‌ها به شکل شبکه اطلاعات ناهمگن وجود دارند. پس دیگر روش‌های گذشته جستجوی شباهت در شبکه‌های اطلاعات همگن، قابل اعمال در شبکه‌های اطلاعات ناهمگن نمی‌باشند، زیرا بسیاری از اطلاعات مهم شبکه را در نظر نمی‌گیرند. با مروری بر کارهای پیشین در حوزه جستجوی شباهت نشان داده می‌شود که جستجوی شباهت در شبکه‌های اطلاعات ناهمگن در چارچوبی جدید و مبتنی بر فرامسیر مطرح می‌شود که فرامسیر، مسیری شامل دنباله‌ای از ارتباطات تعریف شده بین انواع متفاوت از اشیا است. Pathsim معیاری پایه در جستجوی شباهت مبتنی بر فرامسیر در شبکه‌های اطلاعات ناهمگن است که در سال 2011 میلادی ارایه شده است. در سال‌های اخیر، چندین معیار شباهت مبتنی بر فرامسیر ارایه شده‌اند که هر کدام با در نظر گرفتن ویژگی و شرایط خاص سعی بر بهبود جستجوی شباهت را داشته‌اند. در میان کارهای پیشین کم‌ترین توجه به ویژگی زمان شده است زیرا تنها یک کار این ویژگی را در نظر گرفته است که فقط برای برخی از فرامسیرها کاربرد دارد. این در حالی است که مفهوم زمان در شبکه بسیار مهم است، زیرا در طول زمان شبکه تغییر می‌کند و به نوعی رفتار اشیا شبکه در حال تغییر است و این تغییر رفتار می‌تواند در رفتارهای بعدی تاثیر بگذارد. از آنجایی که در این پژوهش هدف بهبود جستجوی شباهت در شبکه‌های اطلاعات ناهمگن است، معیاری جدید به نام Timsim را با در نظر گرفتن ویژگی زمان در این شبکه‌ها در چارچوب مبتنی بر فرامسیر، تعریف کردیم. ابتدا نقش زمان در فرامسیرهای متفاوت را بررسی کردیم و رابطه کلی معیار جدید مبتنی بر زمان را ارایه دادیم. در رابطه ارایه شده از توابع زمانی خطی و نمایی استفاده می‌کنیم، که دلیل استفاده از این توابع، تحلیلی است که بر روی داده‌های واقعی مورد استفاده انجام شده است. پس می‌توان نتیجه گرفت که انتخاب تابع زمانی مناسب بستگی به رفتار داده مورد نظر از نظر زمانی دارد. سپس این معیار را بر روی این داده‌های واقعی پیاده‌سازی کرده و سناریوهای مختلفی را برای ارزیابی آن به کار بردیم. نتایج اولیه را در قالب تاثیر توابع زمانی مختلف برای معیار ارایه شده نشان می‌دهیم. در نهایت نتایج نهایی را در قالب مقایسه معیار ارایه شده Timsim (با بهترین تابع بدست آمده در نتایج اولیه) با روش پایه Pathsim و تنها روش موجود مبتنی بر زمان برای فرامسیرهای مختلف گزارش کردیم. از نتایج بدست آمده، افزایش دقت رتبه‌بندی به طور میانگین 3 تا 10 درصد با استفاده از معیار ارایه شده، دیده می‌شود.
- Abstract
- Many real-world phenomena can be modeled as network systems. Some of these systems consist of heterogeneous nodes/edges. Similarity search is a fundamental operation in network systems, which is a basis for various applications such as link prediction and recommendation. This manuscript introduces a time-aware similarity measure for heterogeneous networks. The proposed metric is based on metapath strategy and considers time of the interaction. We also prove properties of the proposed time-aware similarity measures. our experimental results on a number of real heterogeneous social networks show that incorporating time in the computation of the similarity greatly improves the performance. Keywords: Similarity Search, Heterogeneous Networks, Meta Path, Time.
