عنوان پایان‌نامه
بهبود سامانه پیش بینی موقعیت به کمک کاوش دنباله های حرکتی
- رشته تحصیلی
- علوم تصمیم و مهندسی دانش
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه دانشکده علوم و فنون نوین شماره ثبت: 585;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 79270;کتابخانه دانشکده علوم و فنون نوین شماره ثبت: 585;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 79270
- تاریخ دفاع
- ۱۲ مهر ۱۳۹۵
- دانشجو
- رضا بکتاش
- استاد راهنما
- سامان هراتی زاده, مرتضی ابراهیمی
- چکیده
- از مهم‌ترین اجزاء خدمات هوشمند فراگیر، سامانه‌های پیش‌بینی مکان آتی افراد است که در سامانه‌هایی چون تبلیغات هدفمند و مدیریت ترافیک کاربرد دارد. سامانه پیش‌بینی مکان آتی کاربران، عموما با پردازش داده‌های خام مکانی، مکانهای مهم شهری را شناسایی کرده و بر اساس آن‌ها، الگوهای متداول حرکتی کاربران را استخراج می‌نماید. سپس بر اساس رفتار کنونی کاربر و الگوهای موجود در سیستم، مکان آتی وی را پیش‌بینی می‌کند تا بتواند در ارائه خدمات هوشمند فراگیر، ازآن بهره ببرد سیستم‌های کنونی پیش‌بینی مکان، عموما محدوده پراکندگی داده‌های موقعیت را به تعدادی مکان مجزا تقسیم کرده و از ارتباطات بین مکانها صرف نظر می‌کنند. درحالی که مکانهای شهری عموما از یک ساختار سلسله‌مراتبی تبعیت می‌کنند. برای مثال همه دانشکده‌های مختلف در محدوده یک دانشگاه، زیرمجموعه مکان بزرگتری چون دانشگاه قرار دارند. در نظر نگرفتن این ارتباطات سبب می شود تا برخی الگوهای حرکتی به ویژه در مکانهای کم‌تراکم از بین برود. به همین دلیل، سیستم‌های کنونی، در بسیاری از موارد قادر نیستند تا مکان آتی افراد را بر اساس الگوهای موجود، پیش‌بینی کنند. در همین راستا، در این پایان‌نامه سیستم نوینی برای پیش‌بینی مکان آتی کاربر ارائه می‌دهیم که از ارتباطات میان مکانها در کشف الگوهای حرکتی کاربران بهره می‌گیرد. این سیستم، برای شناسایی مکانهای مهم شهری، از یک الگوریتم خوشه‌بندی سلسله مراتبی استفاده می‌کند و مکانها را در قالب یک ساختار چندلایه(هرمی) ذخیره می‌کند. سپس با استفاده از یک روش جدید دنباله‌کاوی، الگوهای حرکتی متداول در این ساختار چندلایه را استخراج می‌کند. در نهایت، سیستم با تطبیق جابه‌جایی کنونی کاربر با الگوهای حرکتی موجود در سیستم، مکان آتی وی را پیش‌بینی می‌کند. نتایج آزمایش‌ها نشان می‌دهد روش پیشنهادی توانسته است خطای فاصله‌ای سیستم‌های کنونی را تا در حالت‌های مختلف به مقدار قابل توجهی کاهش دهد.
- Abstract
- Next location prediction is an essential component in pervasive location-based services, like traffic management and targeted advertising. What most prediction systems do is preprocessing geo-position data, detecting significant places and then extracting frequent mobility patterns based on those places. Then frequent mobility patterns are used for matching new movement sequences to common mobility patterns, which are used in next location prediction. Existing prediction systems detect a number of discrete significant locations on the area, ignoring natural hierarchical relation among locations. For example, each department of university can be significant location for a user. But they are all part of a bigger significant location, the university. Many interesting mobility patterns will be lost if we don't consider hierarchical relations for locations. That is why most of previous prediction algorithms fail to predict next locations in a large proportion of user movements. In this work, we introduce a new prediction system which considers hierarchical relevance of locations in mining frequent mobility patterns. Significant locations are detected using hierarchical clustering on staypoints. So, each stay point will have a hierarchy of significant locations or multi-layer location indices. Then a new algorithm is proposed to mine frequent sequential patterns from multi-layer location sequences. Finally, for each new movement pattern, best matched frequent mobility patterns are selected and used for next location prediction. The results show that the proposed method reduces prediction error considerably. Keywords: next location prediction, sequence mining, hierarchical location detection, datamining
