آقای محمد حسن پندی دانشجوی کارشناسی ارشد جناب آقای دکتر بهروز مینایی روز شنبه 25/4/90 ساعت 10 صبح در اتاق 304 واقع در طبقه سوم دانشکده کامپیوتر ازپروژه کارشناسی ارشد خود تحت عنوان ارائه یک معیار شباهت برای الگوهای دنباله ای دفاع خواهند نمود.

 چکیده پایان نامه:

  رتبه‌بندی شباهت الگوهای دنباله‌ای در زمینه‌های مختلف کاربرد وسیعی دارد . این کاربرد‌ها به خصوص به علت رشد این گونه داده‌ها اهمیت بالایی پیدا کرده است. بسیاری از داده‌هایی که به‌صورت روزانه تولید می‌شوند قابلیت مدل شدن در غالب دنباله‌ها را دارند. از رکورد اقلام خریداری شده توسط یک مشتری خاص از یک فروشگاه گرفته تا دنباله‌های زیستی (همچو ن DNA ) همگی انواعی از الگوهای دنباله‌ای را تشکیل می‌دهند. به منظور رتبه‌بندی شباهت الگوهای دنباله‌ای (و به طور کلی هر نوع الگویی) به یک معیار شباهت نیازمندیم. معیار شباهت مورد استفاده در چهارچوب رتبه‌بندی، کیفیت، کارایی و کاربرد آن چهارچوب را مشخص می‌کند. برای مثال استفاده از یک معیار شباهت جهت رتبه‌بندی الگوهای دنباله‌ای، کاربردهای وسیعی در زمینه‌ی بازیابی اطلاعات و انواع روش‌های داده‌کاوی دارد. روش‌های موجود تخمین شباهت، هر یک از جنبه‌ای به این مسئله می‌نگرند و همین امر باعث شده است که هر یک در حیطه‌ای خاص قابل استفاده باشند. به‌طور کلی دامنه‌ی مسئله و ابعاد مورد توجه در دنباله‌ها باعث بوجود آمدن گستره‌ی وسیعی از روش‌ها جهت سنجش میزان ش باهت شده است.

  در این پایان‌نامه قصد داریم روشی جدید را جهت اندازه‌گیری میزان شباهت میان الگوهای دنباله‌ای ارائه کنیم. این معیار شباهت می‌تواند چهارچوبی جدید جهت رتبه‌بندی شباهت الگوهای دنباله‌ای معرفی کند. در روش ارائه شده، به مسئله‌ی سنجش شباهت دنباله‌ها از زاویه‌ای جدید پرداخته شده و ویژگی‌هایی که در روش‌های موجود نادیده گرفته می‌شوند مورد نظر قرار می‌گیرند. در این روش یک دنباله به عنوان دنباله‌ی مرجع در نظر گرفته می‌شود و شباهت دنباله‌ی دیگر – که می‌توان آن را راجع نامید – در رجوع به دنباله‌ی مرجع محاسبه می‌شود. به‌طور خلاصه، پس از استخراج ویژگی‌های مد نظر از دنباله‌ی مرجع این ویژگی‌ها را در غالب یک مجموعه‌ی مرتب جزئی مدل کرده و با استفاده از نمودار هاس به مقایسه‌ی دنباله‌های دیگر با دنباله‌ی مرجع می‌پردازیم. با توجه به این که این روش به ترتیبِ‌ میان تمامی نشانه‌ها اهمیت می‌دهد لذا در کاربردهایی که این ترتیب‌ها معنادار هستند نسبت به دیگر روش‌ها برتری دارد. به عنوان مثال، کارآیی این روش در مسئله‌‌ی خوشه‌بندی کاربران از حیث رفتار وبگردی مورد آزمایش تجربی قرار می‌گیرد که حاکی از برتری آن نسبت به روش‌های مبتنی بر هم‌ترازی، مبتنی بر ویرایش و مبتنی بر آمار است.

  واژه‌های کلیدی: معیار سنجش شباهت داده‌های دنباله‌ای، دنباله‌کاوی، مجموعه‌های مرتب جزئی

  Abstract:

  Measuring the similarity of sequence data has a wide range of applications in various domains and determines a framework for similarity ranking of sequenence data. The applications are increasing just as the amount of sequence data. Many daily generated data are capable to be modeled using a sequence format. Examples of these data include Items purchased by a customer, transactions log of a specific account, temperature of a city over a year, text documents and protein sequences. A similarity metric can also help data mining tasks e.g. clustering and classification of sequences. Each existing metric takes a point of view to this problem and tries to extract some features from sequences which seem to be important in a particular application. This approach arises various metrics on different applications.

  In this thesis we introduce and propose a novel similarity measure for sequence data which take care about some features that have not been considered in other metrics. This metric supposes a sequence as the reference and the others as referring sequences. Then it tries to extract symbols distance information table from reference and build an ordered structure using referring sequence with respect to that table. The similarity is then formulated and derived from this ordered structure.

  We evaluate the effectiveness of our proposed metric through a clustering application. Experimental results show the superiority of our proposed sequence similarity metric in purity of clustering comparing to metrics such as d2, Smith-Waterman, Levenshtein, and Needleman-Wunsch.

  Keywords: Sequence Data, Similarity Metric, Sequence Mining, Ordered Set

 ارائه­دهنده:

 محمد حسن پندی

  اساتید راهنما:

 دکتر بهروز مینایی

  استاد ممتحن داخلی : دکتر مرتضی آنالویی

  استاد ممتحن خارجی :دکترمحمد رحمتی

 زمان : چهارشنبه 25 تیرماه ماه 1390

  ساعت 10 صبح

  مکان: دانشکده مهندسی کامپیوتر- طبقه سوم- اتاق 304

  از اساتید بزرگوار، دانشجویان گرامی و دیگر متخصصان و علاقه مندان به موضوع دفاعیه دعوت
می شود با حضور خود موجبات غنای علمی و ارتقای کیفی را فراهم سازند.

  دانشکده مهندسی کامپیوتر مدیریت تحصیلات تکمیلی