8634

8634

ارائه ي يك معيار شباهت براي الگوهاي دنباله اي

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

كامپيوتر گرايش هوش مصنوعي

1390

1390

دكتر بهروز مينائي بيدگلي

م يدهد. چكيده رتبه بندي شباهت الگوهاي دنباله اي در زمينه هاي مختلف كاربرد وسيعي دارد . اين كاربرد ها به خصوص به علت رشد اين گونه داده ها اهميت بالايي پيدا كرده است. بسياري از داده هايي كه به صورت روزانه توليد مي شوند قابليت مدل شدن در غالب دنباله ها را دارند. از ركورد اقلام خريداري همگي (DNA شده توسط يك مشتري خاص از يك فروشگاه گرفته تا دنباله هاي زيستي (همچون انواعي از الگوهاي دنباله اي را تشكيل مي دهند. به منظور رتبه بندي شباهت الگوهاي دنباله اي (و به طور كلي هر نوع الگويي) به يك معيار شباهت نيازمنديم. معيار شباهت مورد استفاده در چهارچوب رتبه بندي، كيفيت، كارايي و كاربرد آن چهارچوب را مشخص مي كند. براي مثال استفاده از يك معيار شباهت جهت رتبه بندي الگوهاي دنباله اي، كاربردهاي وسيعي در زمينه ي بازيابي اطلاعات و انواع روش هاي داده كاوي دارد. روش هاي موجود تخمين شباهت، هر يك از جنبه اي به اين مسئله مي نگرند و همين امر باعث شده است كه هر يك در حيطه اي خاص قابل استفاده باشند. به طور كلي دامنه ي مسئله و ابعاد مورد توجه در دنباله ها باعث بوجود آمدن گستره ي وسيعي از روش ها جهت سنجش ميزان شا بهت شده است. در اين پايان نامه قصد داريم روشي جديد را جهت اندازه گيري ميزان شباهت ميان الگوهاي دنباله اي ارائه كنيم. اين معيار شباهت مي تواند چهارچوبي جديد جهت رتبه بندي شباهت الگوهاي دنباله اي معرفي كند. در روش ارائه شده، به مسئله ي سنجش شباهت دنباله ها از زاويه اي جديد پرداخته شده و ويژگي هايي كه در روش هاي موجود ناديده گرفته مي شوند مورد نظر قرار مي گيرند. در اين روش يك دنباله به عنوان دنباله ي مرجع در نظر گرفته مي شود و شباهت دنباله ي ديگر – كه مي توان آن را راجع ناميد – در رجوع به دنباله ي مرجع محاسبه مي شود. به طور خلاصه، پس از استخراج ويژگي هاي مد نظر از دنباله ي مرجع اين ويژگي ها را در غالب يك مجموعه ي مرتب جزيي مدل كرده و با استفاده از نمودار هاس به مقايسه ي دنباله هاي ديگر با دنباله ي مرجع مي پردازيم. با توجه به اين كه اين روش به ترتيبِ ميان تمامي نشانه ها اهميت مي دهد لذا در كاربردهايي كه اين ترتيب ها معنادار هستند نسبت به ديگر روش ها برتري دارد. جهت مقايسه ي روش پيشنهادي با رو شهاي موجود، مسئله ي خوشه بندي رفتار وب گردي كاربران را در نظر گرفتيم. در اين مقايسه كاربران را از حيث توالي صفحات مورد بازديد خوشه بندي نموديم و در روند خوشه بندي از معيار شباهت پيشنهادي استفاده كرديم. ميزان خلوص به دست آمده از خوشه بندي در حالتي كه از معيار شباهت پيشنهادي استفاده شده باشد مقدار 91 درصد را نشان مي دهد. اي ن درحالي است