GroupSeeker: چارچوبی قابل اجرا برای کشف همراهان سفر از داده های مسیر گسترده

خلاصه

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

کلید واژه ها:

کشف همسفر ; استخراج مسیر مکانی-زمانی ; چارچوب ; تجزیه و تحلیل انجمن ; خوشه بندی ; استراتژی تنظیم پارامتر

۱٫ معرفی

طبق آمار تجارت مخابراتی چین در سال ۲۰۱۹، تعداد کاربران تلفن همراه تا پایان سال ۲۰۱۹ به ۱٫۶ میلیارد نفر رسید [ ۱ ]. با توجه به توسعه تکنیک های مکان یابی و استفاده گسترده از دستگاه های هوشمند، داده های مسیر شخصی به منبع مهمی برای درک رفتارهای شخصی یا گروهی تبدیل شده است و داده کاوی مسیر به موضوع داغ بسیاری از زمینه های تحقیقاتی تبدیل شده است [ ۲ ]. به عنوان مثال، الراگال و همکاران. [ ۳ ] و شینگو انامی و همکاران. [ ۴ ] از فناوری های نسبی در مدیریت خودرو استفاده کرد. تیان کین و همکاران [ ۵ ] روشی را برای استخراج روال مکانی-زمانی افراد بر اساس داده های تلفن همراه پیشنهاد کرد. هوان و همکاران [ ۶] سعی کرد رفتارهای اجتماعی را بر روی داده های حسگرهای تلفن همراه بررسی کند. چن و همکاران [ ۷ ] پیش بینی بیماری را بر اساس داده های بزرگ تلفن همراه انجام داد. شودونگ لیو و همکاران [ ۸ ] از داده های مسیر تاکسی برای شناسایی مناطق عملکردی شهری در چنگدو استفاده کرد. علاوه بر این، تجزیه و تحلیل داده های مسیر در برخی کاربردهای عملی، مانند توصیه دوستان نزدیک بر اساس سرویس مبتنی بر مکان (LBS) [ ۹ ] و ناوبری مسیر در برنامه های نقشه و غیره اعمال شده است.

کشف الگوی رفتار همراه یا گروهی شاخه مهمی در استخراج داده های مسیر موبایل است. الگو به عنوان بیش از یک جسم متحرک تعریف می شود که برای یک دوره زمانی با هم حرکت می کنند. چنین کشف الگوی پشتیبانی قابل توجهی را برای مقدار زیادی از زمینه های نسبی، مانند کنترل پرسنل کلیدی، توسعه گردشگری، بررسی حوادث، ردیابی گروهی و غیره فراهم می کند. در سناریوهای کاربردی قابل توجهی استفاده شده است. تانگ و همکاران [ ۱۰ ] یک کشف همراه آزاد برای نظارت بر شی نظامی پیشنهاد کرد تا توصیف کند چند عضو ممکن است به طور موقت گروه را ترک کنند و در مدت زمان کوتاهی به عقب برگردند. میلینگ ژو و همکاران [ ۱۱] یک الگوریتم جدید برای یافتن الگوی همراه جوخه بر روی نوع خاصی از جریان داده های مکانی-زمانی پیشنهاد کرد. زو و همکاران از داده‌های گردشگران هاینان برای یافتن الگوی حرکت گروهی و طبقه‌بندی گردشگران [ ۱۲ ] و غیره استفاده کرد. بنابراین، استخراج و تحلیل الگوی رفتار همراه برای کاربردهای نسبی و زمینه‌های دانشگاهی ضروری است.

از آنجایی که دستگاه های تلفن همراه می توانند مقادیر انبوهی از داده ها را تولید کنند، یک چالش بزرگ در الگوکاوی همراه ایجاد می شود، به عنوان مثال، عملکرد بالای الگوریتم ها برای پردازش داده های عظیم در زمان محدود مورد نیاز است. چالش اصلی دیگر از بهینه سازی الگوریتم کشف همراه مسافر است. الگوریتم کشف همراه مسافر از روش خوشه‌بندی و تقاطع [ ۱۳ ] می‌آید، که نامزدهای همراه را برای توصیف همراهان مشابه در هر عکس فوری تعریف می‌کند. تانگ و همکاران [ ۱۴ ] الگوریتم Clustering-and-Intersection را با ترکیب ساختار دوستان برای بهبود اثربخشی روش به یک الگوریتم هوشمند و بسته بهینه کرد. در عین حال. برخی از مطالعات [ ۱۲ ، ۱۵] از روش مشابهی برای کشف همسفران یا سایر الگوهای رفتاری استفاده کنید. با این حال، ایجاد یک مشکل کاندید حذف با روش مبتنی بر زمان عکس فوری، به ویژه زمانی که دوره زمانی بسیار کوتاه مدت باشد، آسان است. به دلیل پراکندگی داده‌های مسیر سیار، خوشه‌بندی این داده‌های مسیر با استفاده از روش تقسیم‌بندی زمانی نامناسب یک خطر است. به طور مشخص، برخی از داده‌های مسیر قابل خوشه را نمی‌توان احتمالاً خوشه‌بندی کرد و حتی به عنوان نویز فیلتر می‌شوند. بنابراین، رویکردهای مبتنی بر برش بخش زمانی ممکن است همیشه کاملاً موفق نباشند.

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

الگوریتم پیشنهادی بسط و بهینه سازی کار قبلی ما است [ ۱۶ ]. بر این اساس، الگوریتم را بهبود می‌دهیم و یک چارچوب ۵ مرحله‌ای پیشنهاد می‌کنیم. در مرحله اول، خوشه بندی فضایی مبتنی بر چگالی سلسله مراتبی برنامه های کاربردی با نویز (HBDSCAN) [ ۱۷] برای استخراج کاربران متحرک مشابه در یک منطقه جغرافیایی خاص و در بازه زمانی استفاده می شود. سپس، یک الگوریتم تجزیه و تحلیل انجمن کلاسیک الگوی مکرر (FP-growth) برای پیش‌بینی روابط داخلی میان کاربران مشابه استفاده می‌شود که از ویژگی‌های داده‌های خوشه‌ای با شباهت زیاد برای یافتن الگوهای همراه بالقوه استفاده کامل می‌کند. مرحله زیر شامل یک استراتژی فیلترینگ است که برای انجام فیلترهای لازم برای به دست آوردن همراهان توصیه شده برای برخی سناریوهای شبه همراه استفاده می شود. آخرین مرحله برای ادغام داده های نتایج در گروه ها طراحی شده است.

مشارکت های اصلی پیشنهاد شده در این مقاله به شرح زیر است:

چارچوبی برای کشف همسفر به نام GroupSeeker پیشنهاد شده است. از طریق یک جریان پردازش پنج مرحله ای، GroupSeeker می تواند همراهان بالقوه سفر را در حجم عظیمی از داده های مسیر با عملکرد و دقت بالا بیابد.
استراتژی های تنظیم پارامتر ذاتاً در GroupSeeker تعبیه شده است. مراحل اولیه می توانند پارامترهای خود را با توجه به ویژگی مجموعه داده ها تعیین کنند، که این چارچوب را بسیار کاربردی تر و کاربردی تر می کند.
یک روش جدید خوشه‌بندی مکانی-زمانی برای مقابله با داده‌های مسیر برش‌های زمانی بلندمدت و حل مشکل حذف نامزدهای همراه ناشی از تقسیم‌بندی زمان کوتاه‌مدت نامناسب در کار قبلی استفاده می‌شود.
نتایج تجربی بر روی مجموعه داده های واقعی و شبیه سازی شده نشان می دهد که هزینه زمانی GroupSeeker در سطح مطلوبی است. داده های مسیر برای بیست و چهار ساعت را می توان در عرض یک ساعت و نیم پردازش کرد، به این معنی که GroupSeeker را می توان در کارهای نظارتی در همه شرایط آب و هوایی استفاده کرد.

نامه یادآوری به گونه ذیل تنظیم شده است. بخش ۲ کار مرتبط را معرفی می کند. بخش ۳ به تعریف مسئله و روش شناسی، از جمله چارچوب و روش ها می پردازد. بخش ۴ نتایج تجربی را ارائه می کند. بخش ۵ این مقاله را به پایان می رساند و در مورد کارهای آینده بحث می کند.

۲٫ کارهای مرتبط

در این بخش، کار مرتبط بر اساس دو مقوله اصلی، یعنی خوشه‌بندی مسیر و کشف الگوی همراه، معرفی می‌شود.

۲٫۱٫ خوشه بندی مسیر

برای خوشه بندی مسیرهای مشابه بر اساس بعد زمانی، Agrawal و همکاران. اندازه‌گیری تشابه مسیر را بر اساس فاصله اقلیدسی [ ۱۸ ] در سال ۱۹۹۳ پیشنهاد کرد. Faloutsos C و همکاران. و چان کی پی و همکاران. از تبدیل فوریه گسسته و تبدیل موجک گسسته به ترتیب برای پیش پردازش اندازه گیری شباهت مسیر بر اساس فاصله اقلیدسی [ ۱۹ ، ۲۰ ] استفاده کرد. النکاوه اس و همکاران. بیان MBR را با پیشنهاد مسیر صاف MBB (جعبه مرزی حداقل) برای مقابله بهتر با تأثیر نویز بهبود داد [ ۲۱ ].

برای خوشه‌بندی بر اساس شباهت مسیرها، استخراج تشابه کل ویژگی‌های مسیر بر کاهش نیاز در بعد زمانی متمرکز شده است، و فقط به ترتیب زمانی در میان نقاط ثبت مسیر نیاز دارد، بنابراین از DTWD عمومی برای مقابله با چنین خوشه‌بندی استفاده می‌شود. [ ۲۲ ]. برای خوشه بندی محلی با یک مسیر واحد، لی و همکاران. چارچوبی را ارائه کرد که ابتدا با استفاده از روش خوشه‌بندی چگالی [ ۲۳ ]، با تقسیم‌بندی و سپس انباشته‌ها به مسیرهای فرعی بر اساس اصل طول توصیف حداقل تقسیم می‌شود. علاوه بر این، چندین روش خوشه‌بندی مبتنی بر چگالی مانند DBSCAN، DENCLUE، OPTICS و غیره پیشنهاد شد. DBSCAN [ ۲۴] یک الگوریتم خوشه بندی مکان مکانی است که به طور گسترده مورد استفاده قرار می گیرد. این ویژگی عدم نیاز به تعیین تعداد خوشه ها از قبل را دارد و می تواند خوشه هایی از اشکال دلخواه را پیدا کند [ ۲۵ ]. در سال ۱۹۹۹، OPTICS توسط Ankerst M. و همکاران پیشنهاد شد. به جای تولید خوشه های یک مجموعه داده به طور صریح؛ با این حال، یک نظم افزوده از پایگاه داده ایجاد می کند که ساختار خوشه بندی مبتنی بر چگالی آن را نشان می دهد [ ۲۶ ]. Hinneburg، A و Gabriel، HH DENCLUE 2.0 را برای بهبود مضرات DENCLUE 1.0 [ ۲۷ ] پیشنهاد کردند که انجام گام های کوچک در ابتدا می تواند منجر به عدم همگرایی هرگز به حداکثر شود [ ۲۸ ].]. در سال ۲۰۱۷، Mclnnes و همکاران. یک الگوریتم خوشه‌بندی مبتنی بر چگالی سلسله مراتبی را پیشنهاد کرد و یک پایگاه کد مرتبط را به عنوان یک بسته در پایتون برای استفاده منتشر کرد [ ۱۷ ]. یوکینگ یانگ و همکاران یک الگوریتم خوشه‌بندی مسیر را برای استخراج Stays مسیر بر اساس تحلیل چگالی در داده‌های مسیر مکانی-زمانی پیشنهاد کرد و به دقت خوشه‌بندی بالاتری در مجموعه داده‌های دنیای واقعی دست یافت [ ۲۹ ].

برای خوشه بندی نقاط مسیر، Gao Y و همکاران. یک جستار محدود k-نزدیکترین همسایه در میان مسیرها پیشنهاد کرد [ ۳۰ ]. یک الگوریتم خوشه بندی زیر خطی بر اساس فاصله فریشت با استفاده از GPU توسط Gudmundsson J و همکاران ارائه شد. [ ۳۱ ] برای استفاده از فاصله فریشه پیوسته به عنوان اندازه گیری شباهت بین منحنی های مسیر که دارای مزایای عملکرد آشکار است. به طور مشابه، دنگ زی و همکاران. یک الگوریتم OPTICS اصلاح شده به نام Tra-OPTICS را برای خوشه‌بندی خط سیر پیشنهاد کرد. علاوه بر این، یک نسخه مبتنی بر GPU برای بهینه سازی عملکرد پیشنهاد شده است، به نام G-Tra-OPTICS، که بر اساس درخت STR به عنوان ساختار نمایه سازی [ ۳۲ ] است. یوان، جی و همکاران. این تکنیک های مهم خوشه بندی مسیر را خلاصه کرد [ ۳۳].

برای خوشه بندی مسیر معنایی، Xiao X و همکاران. روشی را برای یافتن کاربران مشابه با استفاده از تاریخچه مبتنی بر دسته پیشنهاد کرد [ ۳۴ ]. یینگ جی سی و همکاران خوشه‌بندی مسیر معنایی بر اساس پیش‌بینی مکان برای توصیه کاربر به بعد بعدی [ ۳۵ ]. لیو اس و همکاران رویکردی برای دستیابی به شناسایی نقاط داغ در میان مسیرها ارائه کرد [ ۳۶ ]. آندرینکو و همکاران تکنیک‌های عمومی و دستورالعمل‌های تجسم را برای پشتیبانی از تجزیه و تحلیل داده‌های حرکت، با استفاده از خوشه‌بندی مسیر در مجموعه داده‌های ترافیک هوایی واقعی [ ۳۷ ] ارائه کرد. Olive، X.، و Morio، J. خوشه‌بندی مسیر را در مدیریت ترافیک هوایی به کار بردند و اثربخشی روش پیشنهادی را بر روی مجموعه مسیرهای دنیای واقعی تأیید کردند.۳۸ ].

۲٫۲٫ کشف الگوی همراه

از طریق تجزیه و تحلیل الگوهای رفتاری گروه‌های شی متحرک، می‌توان به بررسی حادثه و ردیابی گروهی بر اساس محیط مکانی-زمانی پی برد. در مجموعه‌ای از خروجی‌های تحقیق، الگوهای مسیر معرف، عمدتاً شامل گله [ ۳۹ ]، کاروان [ ۴۰ ]، ازدحام [ ۴۱ ] و گردآوری [ ۴۲ ] تعریف شد. در سال ۲۰۱۶، ژنژن وانگ و همکاران. یک مرور ادبیات را برای خلاصه کردن مطالعات رفتار سفر موجود ارائه کرد که داده‌های تلفن همراه را به کار می‌برد و پتانسیل داده‌های تلفن همراه را در پیشرفت تحقیقات رفتار سفر مورد بحث قرار می‌داد [ ۴۳ ].

گودموندسون و همکاران [ ۳۹ ] مدل دسته جمعی را تعریف کرد که الگوهای اولیه جمعیت تحقیق را با از پیش تعریف شکل منطقه ای و اندازه جمعیت بهینه می کند. مدل کاروان تعریف شده توسط Jeung و همکاران. [ ۴۰ ] استخراج مسیر با اشکال دلخواه مبتنی بر خوشه‌بندی چگالی، اجتناب از آستانه‌های فضایی از پیش تعریف‌شده را تحقق بخشید، و این مدل به تعداد معینی از اشیاء متحرک نیاز دارد که با چگالی در طول مدت k به هم متصل شوند. بهینه سازی بیشتر بر اساس دو مدل اول، مدل Swarm بود که توسط لی و همکاران تعریف شد. [ ۴۱ ]. در روش آنها، زمانی که اجسام متحرک برای مدت معینی با هم حرکت می کنند، زمان لازم نیست پیوسته باشد. ژنگ و همکاران [ ۴۲] الگوی گردآوری تعریف شده ای که رویدادهای گروهی را در مسیرها شبیه سازی می کند، مانند جشن ها، رژه ها، اعتراضات، و غیره. فن چن و همکاران روشی را برای تشخیص تعاملات گروهی برای گروه هایی با تعداد متفاوت اشیاء پیشنهاد کرد [ ۴۴ ]. ژانگ و همکاران [ ۴۵ ] از نمودار مکانی-زمانی برای بازیابی گردآوری استفاده کرد. محققان CUTis [ ۴۶ ] (جریان داده مسیر خوشه ای) را ارائه کردند که یک الگوریتم پردازش برای یک جریان داده مسیر افزایشی است. روشی برای شناسایی الگوی حرکت گروهی از طریق سوابق جزئیات تماس تلفن همراه (CDRs) بر اساس شباهت به کشف گروه‌های توریستی توسط ژو و همکاران ارائه شد. [۱۲ ]. الگوریتمی برای یافتن الگوی خوشه‌های اجسام متحرک تدریجی در میان جریان‌های مسیر توسط یوجی ژانگ و همکاران ارائه شد. [ ۱۵ ]. به منظور کشف وسایل نقلیه همراه، در سیستم حمل و نقل هوشمند (ITS)، یک برنامه معمولی در فناوری مهندسی نرم افزار، Meiling Zhu et al. [ ۴۷ ] روشی را برای کشف همراهان مسافر از طریق جریان داده های تشخیص خودکار پلاک شماره (ANPR) با استفاده از کاوی توالی مکرر با محدودیت های زمانی پیشنهاد کرد. ژانگ و همکاران [ ۱۵ ] از پنجره کشویی برای استخراج الگوی خوشه در داده های مسیر استفاده کرد.

علاوه بر این، الگوریتم تحلیل همبستگی در تحلیل مسیر و کشف الگو استفاده می‌شود. شیا داون و همکاران [ ۴۸ ] روشی را با استفاده از الگوریتم رشد الگوی مکرر موازی مبتنی بر کاهش نقشه برای تحلیل داده‌های بزرگ مسیر پیشنهاد کرد. هو و همکاران [ ۴۹ ] از خوشه‌بندی و ارتباط OPTICS استفاده کرد. بر اساس موارد مکرر، Al-badwi et al. [ ۵۰ ] یک رویکرد توزیع شده هیبریدی در وسعت اول و عمق اول با استخراج مجموعه آیتم های مکرر (HD-FIM) در Spark را برای افزایش کارایی کشف وسایل نقلیه همراه پیشنهاد کرد.

با توجه به روش‌های کشف همراهان، Puntheeranurak و همکاران. [ ۴۶ ] یک الگوریتم خوشه‌بندی مبتنی بر ریز گروه را برای کاهش هزینه محاسباتی پیشنهاد کردند و آنها آزمایش‌هایی را روی داده‌های مسیر تاکسی واقعی و داده‌های مصنوعی انجام دادند. با این وجود، تحقیقات آنها برای جلوگیری از مشکل حذف نامزد همراه دشوار است و مقیاس نمونه های آزمایشی آنها کوچکتر از کار ما است. علاوه بر این، شینینگ ژو و همکاران. [ ۱۲] یک روش مبتنی بر آستانه و ماشین‌های بردار پشتیبان نیمه نظارتی ایمن (S4VMs) برای محاسبه بردارهای شباهت گردشگران و تشخیص حالت حمل‌ونقل آنها برای یافتن الگوی حرکت گروه از طریق CDRها پیشنهاد کرد. با این حال، این تحقیق و چارچوب پیشنهادی عمدتاً در کاربردهای ویژه ای مانند گردشگری استفاده می شود. بنابراین، انگیزه کار آنها در واقع با تحقیقات ما متفاوت است. در مقابل، تحقیق ما به مطالعه چارچوب زیربنایی در پرونده کشف همسفر نزدیکتر است.

۳٫ مواد و روشها

در این بخش، مشکلات برای توصیف وضعیت روش‌های ما نشان داده می‌شوند و برای تسهیل توضیحات بعدی، تعاریف مسئله ارائه می‌شود. در نهایت، یک چارچوب پیشنهاد شده است، شامل پنج مرحله برای کشف همسفر.

۳٫۱٫ بیان مسأله

۳٫۱٫۱٫ مشکل حذف کاندیدای همراه

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

پس از پیش پردازش داده‌های مسیری نمونه‌برداری شده در دنیای واقعی، دو ویژگی داده پیدا می‌شود:

سیگنال‌های داده‌های موقعیت‌یابی در دنیای واقعی ممکن است در حین اکتساب و انتقال مسدود شوند. دلیل مسدود کردن این است که کاربران می توانند به طور فعال دستگاه ها را خاموش کنند یا خدمات مکان را خاتمه دهند و انتقال اطلاعات مکان ممکن است توسط محیط های اطراف تداخل یا مسدود شود.
به دلیل تفاوت در روش‌های نمونه‌گیری و از دست دادن انتقال داده‌ها، داده‌های مسیر در طول جمع‌آوری داده‌ها پراکنده یا تا حدی از بین خواهند رفت.

به دلیل ویژگی‌های فوق، زمانی که الگوریتم کشف الگوی همراه مرسوم از روش برش بخش زمانی در مجموعه داده‌های مسیر بسیار پراکنده استفاده می‌کند، نقاط ضبط در لبه‌های خوشه‌های تشکیل‌شده احتمالاً به‌دلیل نامناسب بودن، به‌عنوان نویز فیلتر می‌شوند. مدت زمان برش ها

شکل ۱ یک نامزد همراه را نشان می دهد که نمونه ها را حذف می کند. عکس های فوری زمانی مجاور وجود دارد، به عنوان مثال، s1 ، s2 و s3 . یک یا چند خوشه در هر عکس فوری را می توان پس از پردازش خوشه به همراه چندین نقطه غیر خوشه ای مانند A ، B و C به دست آورد. از آنجایی که تقسیم‌بندی زمانی اتفاقاً در میانه زمان‌های نمونه‌برداری آنهاست، می‌توان مشاهده کرد که نمونه A و B به عکس‌های لحظه‌ای زمانی متفاوتی تقسیم می‌شوند، حتی اگر در واقع یک رابطه تنگاتنگ با هم دارند. در صورت ادغام s1 ، s2 و s3 در یک عکس فوری طولانی مدت، یک خوشه شامل نقاطA و B در طول خوشه بندی ایجاد می شوند و خوشه یک نامزد همراه بالقوه برای فرآیندهای زیر خواهد بود. در واقع، A و B دوستان مسافرتی هستند، در حالی که C یک نقطه صدای واقعی است. این کاندیدای همراه کلاسیک است که مشکلات ناشی از مرزهای عکس فوری زمانی نامناسب را حذف می کند. این مشکل بیشتر زمانی رخ می دهد که داده های مسیر پراکنده تر باشند.

احتمال این مشکل به طول بخش زمانی مربوط می شود. به عنوان مثال، اگر داده های خام حاوی رکوردهای مسیر در یک منطقه در یک روز باشد، محققان امیدوارند تا حد امکان از حذف مشکلات جلوگیری کنند. دو گزینه برای برش ۲۴ ساعت بر اساس ۵ دقیقه یا محاسبه مستقیم بر اساس کل ۲۴ ساعت وجود دارد. اگر انتخاب بخش زمانی بر اساس برش کوتاه مدت باشد، احتمال ایجاد مشکلات را افزایش می دهد. برعکس، اگر یک روش بتواند از ۱ روز یا چند ساعت داده مسیر به عنوان ورودی استفاده کند، این امکان تا حد زیادی کاهش می یابد. بدیهی است که برش مکرر کوتاه مدت می تواند به راحتی مشکل حذف نامزد همراه را ایجاد کند و در نتیجه رکوردهای بدون نویز فیلتر شوند.

از دیدگاه کل نگر، ما رکوردها را در یک بازه زمانی طولانی‌مدت به عنوان اهداف استخراج می‌گیریم. شباهت جغرافیایی نزدیکتر و ویژگیهای بعد زمانی نزدیکتر مورد توجه است. الگوریتم خوشه‌بندی مسیر برای استخراج ویژگی‌های مشابه در بعد مکانی-زمانی برای این رکوردها در بین کاربران استفاده می‌شود. در همین حال، موقعیت همراه مکرر به عنوان استاندارد مهم برای کشف نامزد همسفر همراه (ATCC) در نظر گرفته می شود. سپس ویژگی های سناریوهای همراه با هم ترکیب می شوند تا به طور خاص صحت وضعیت همراه را تأیید کنند. تا حد زیادی استحکام روش را تا درجه چگالی داده بهبود می بخشد.

۳٫۱٫۲٫ تعریف مشکل

تعریف ۱ (مجموعه عکس فوری): مجموعه عکس لحظه ای زمانی مجموعه ای از مجموعه ای از عکس های فوری کوتاه مدت است. که می تواند به عنوان یک پسوند برای یک عکس فوری کوتاه مدت دیده شود.
تعریف ۲ (گروه رکورد): یک گروه رکورد مجموعه ای از تمام رکوردهای شی متحرک در یک مجموعه عکس فوری است ، n تعداد اجسام متحرک در مجموعه زمانی را نشان می دهد. برای یک جسم متحرک ، تعداد رکوردها است ، و
تعریف ۳ (کاندیدا بالقوه محلی (LPC)): یک مجموعه نامزد مجموعه ای به عنوان مجموعه ای از نامزدهای همراه است که بر اساس اطلاعات مکان خوشه بندی شده اند، جایی که m تعداد خوشه ها را نشان می دهد. این مقاله از الگوریتم خوشه‌بندی مبتنی بر چگالی استفاده می‌کند. برخی از پارامترها باید تعریف شوند. به عنوان آستانه اندازه خوشه بندی تعریف می شود، به عنوان آستانه فاصله استفاده می شود. فرمول فاصله پیش‌فرض چندین الگوریتم خوشه‌بندی بر اساس فرمول فاصله اقلیدسی است که می‌تواند مزایای کارایی خاصی را ارائه دهد. با این حال، به منظور تسهیل تنظیم پارامترهای داده کاوی مسیر و بهبود دقت نتایج داده کاوی مسیر، فرمول فاصله در اینجا ممکن است با فرمول فاصله ای جایگزین شود که نیازهای صحنه را بهتر برآورده کند. مجموعه کاندیدای بالقوه مکانی یک مجموعه خوشه ای است که wrt را راضی می کند و .
تعریف ۴ (نامزد بالقوه زمان و مکان (TLPC)): بر اساس نامزدهای بالقوه برای موقعیت، خوشه‌های کاندیداها بر اساس زمان خوشه‌بندی را برآورده می‌کنند تا خوشه‌ها را تشکیل دهند. مجموعه اشیاء در این خوشه ها به عنوان کاندیدای بالقوه زمان و مکان در نظر گرفته می شود. در میان آنها، به عنوان حداقل اندازه خوشه تعریف می شود. علاوه بر این، چون HDBSCAN برای تضعیف پارامتر فاصله دیگری استفاده می شود، در اینجا تعریف نشده است.
تعریف ۵ (نامزد همراه مسافر (ATCC)): حداقل آستانه حمایت برای تجزیه و تحلیل انجمن و حداقل آستانه اطمینان است. نامزد مجموعه یک فرهنگ لغت قوانین انجمن را برآورده می کند . جفت کلید-مقدار فرهنگ لغت مربوط به آیتم مکرر و پشتیبانی آن است. یک مورد مکرر است که پشتیبانی آن کمتر از حداقل پشتیبانی نیست. کلید قانون انجمن یک مورد مکرر است با اطمینان آن کمتر از حداقل اطمینان نیست.
تعریف ۶ (سناریوهای شبه همراه): سناریوهای شبه همراه به سناریوهایی اطلاق می شود که قبلاً بالقوه همراهی دارند در حالی که برخی از ویژگی های مهم به طور کامل با الگوی همراه مطابقت ندارند.
تعریف ۷ (استراتژی تحمل): هنگام انجام داده کاوی مسیری در یک مجموعه داده پراکنده، برخی از پارامترها را نمی توان به طور دقیق تنظیم کرد. در غیر این صورت یافتن اشیاء تحقیقی که شرایط مربوطه را داشته باشند مشکل خواهد بود. به همین دلیل، برای کشف اجسام متحرک باید یک استراتژی تحمل در نظر گرفته شود.
تعریف ۸ (همسفر (TC)): مجموعه ای از همسفر، که در آن یک گروه همراه در سفر است گروهی است که ارضای تعداد رکوردهای ارضا کننده وضعیت همراه بالقوه بیشتر از آستانه فرکانس است. ، و نسبت رکوردهای رضایت بخش بیشتر از آستانه درصد است در بازه زمانی S.

۳٫۲٫ روش شناسی

۳٫۲٫۱٫ چارچوب

داده‌های خط سیر خام تولید شده از منابع سنجش مختلف، فرمت‌های داده و دقت موقعیتی متفاوتی دارند. یک چارچوب انعطاف‌پذیر به نام GroupSeeker برای کشف همراهان سفر از داده‌های مسیر غواصی پیشنهاد شده است. این چارچوب در درجه اول شامل یک جریان پردازش پنج مرحله‌ای است که از پیش پردازش داده، خوشه‌بندی مکانی-زمانی، رأی‌گیری نامزد، فیلتر شبه همراه و ادغام گروهی تشکیل شده است. سپس یک سری از استراتژی های تنظیم پارامتر در کل جریان پردازش برای مقابله با سناریوهای مختلف پیشنهاد می شود. کل پردازش در شکل ۲ نشان داده شده است. دسته‌بندی‌های مختلف روش‌های نمونه‌گیری می‌توانند چندین ویژگی مختلف از داده‌های مسیر را به همراه داشته باشند و این مقاله بر دو روش نمونه‌گیری یعنی GPS و CDR تمرکز دارد که ویژگی‌های جمع‌آوری آسان و داشتن مقیاس‌های بزرگ را دارند.

پیش پردازش داده، فیلدهای غیر ضروری را در داده های خط سیر خام حذف می کند و نویز و داده های اضافی را در فیلدهای باقی مانده فیلتر می کند. سپس کل داده های مسیر به بسیاری از مجموعه داده های زیر مسیر تقسیم می شود تا سربار محاسباتی کاهش یابد. در مرحله دوم، خوشه‌بندی مکانی-زمانی، داده‌های مسیر در ابعاد فضایی برای کشف نامزد بالقوه مکان (LPC) خوشه‌بندی می‌شوند. از طریق خوشه بندی این LPC، زمان و مکان نامزد بالقوه (TLPC) را می توان از بعد زمانی کشف کرد. علاوه بر این، مرحله رای گیری نامزد بر روی فرکانس همراه بین هر جفت کاربر در TLPC برای کشف نامزد همراه مسافر (ATCC) تمرکز می کند. مرحله بعدی IV فیلتر شبه همراه است که هدف آن ارائه قوانینی برای فیلتر کردن برخی از شبه همراهان گیج کننده از ATCC است. در آخرین مرحله، ادغام گروه نامیده می شود، مجموعه های همراه را با همان اشیاء متحرک ادغام می کند تا آنها را به عنوان یک گروه همراه با چندین شیء تبدیل کند. به عنوان یک چارچوب نیمه نظارت شده، استراتژی‌های تنظیم پارامتر می‌توانند استراتژی‌های مهمی را برای هدایت این روش‌ها در مرحله II، مرحله III و مرحله IV برای تنظیم پارامترهای نسبتا مناسب ارائه دهند.

۳٫۲٫۲٫ پیش پردازش داده ها

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

اولاً، این فیلدهای اضافی رها می شوند و فیلدهای باقیمانده نامگذاری یکسانی دریافت می کنند، مانند زمان، شناسه کاربر، طول جغرافیایی، عرض جغرافیایی و شماره فهرست.. هنگام تمیز کردن این مسیرها، برخی از نقاط نویز واضح باید فیلتر شوند، مانند رکوردهای حاوی نوع داده خطا مربوط به یک پرونده خاص، سوابق شامل طول و عرض جغرافیایی اشتباه در محدوده منطقه جغرافیایی شناخته شده، و رکوردهای حاوی مهر زمانی که با واقعی مطابقت ندارد. زمان نمونه علاوه بر این، فیلتر میانی برای مقابله با نقطه تک نویز و فیلتر کالمن برای مقابله با نقاط نویز پیوسته استفاده می شود. با استفاده از روش تشخیص نقطه ماندن از طریق این داده های فیلتر شده، نقاط ماندن در این مسیرها را می توان یافت که می تواند برای هدایت کشف الگوهای بعدی مورد استفاده قرار گیرد. برای کاهش مقیاس محاسباتی برای خوشه‌بندی مسیر و استخراج تا حد امکان در مورد الگوهای رفتاری در میان بخش‌های زیرمسیر، عملیات قطعه مسیر برای تقسیم کل رکوردهای مسیر به چندین مسیر فرعی اجرا می شود. ما یک مجموعه داده مسیر پراکنده را به ۱۸ زیر مجموعه داده و مجموعه داده های مسیر Geolife را با توجه به تعداد رکوردها به ۱۹ مجموعه داده فرعی تقسیم کردیم. بخشی از داده های مسیر برای تطبیق نقشه انتخاب می شود تا به طور خلاصه قابل اعتماد بودن داده های مسیر را تأیید کند. علاوه بر این، داده های فیلتر شده اساساً با نقشه مطابقت دارند و هیچ جابجایی بزرگی وجود ندارد.

۳٫۲٫۳٫ خوشه بندی مکانی-زمانی

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

شکل ۳ فرآیند خوشه بندی را به تفصیل نشان می دهد. در این پردازش، HDBSCAN برای کشف نامزد بالقوه مکان (LPC) و زمان و مکان نامزد بالقوه (TLPC) استفاده می شود. LPC شباهت را در ویژگی های مکان نشان می دهد. بر این اساس، TLPC به تشابه در بعد زمانی به شدت نیاز دارد. شکل ۴ نمونه ای از یک فرآیند خاص برای ترکیب فیلدهای داده را نشان می دهد. در شکل ۴الف، مجموعه ای از نمونه داده ها ارائه می شود که چندین فیلد (User ID، Latitude، Longitude، Time) فیلدهای باقی مانده پس از پیش پردازش هستند و فیلد Fill برای این رکوردها به عنوان LPC اضافه می شود. برای کشف LPC، از دو پارامتر برای محدود کردن حداقل اندازه خوشه و آستانه فاصله همسایگی استفاده می‌شود، که باعث می‌شود HDBSCAN نتایج ثابت و مؤثری را برای کشف LPC و فیلتر کردن مقداری نویز که نمی‌توان خوشه‌بندی کرد، دریافت کند. یک فیلد Fill به مجموعه LPC افزایش می‌یابد تا ابعاد مورد نیاز را برآورده کند. مقدار فیلد FILL روی ۱ تنظیم می شود تا محاسبه ساده شود. در هر خوشه LPC، HDBSCAN یک بار برای یافتن TLPC، از جمله ویژگی‌های مشابه زمان و مکان، و فیلتر کردن برخی رکوردهای نویز اجرا می‌شود. شکل ۴ب این روند را به صورت بصری نشان می دهد. در الگوریتم ۱، مراحل ۴ تا ۸ مرحله را از سطح الگوریتم نشان می دهد. قابل ذکر است که تعداد این رکوردهای فیلتر شده می تواند بر ارتقای رکوردهای رضایت بخش تأثیر بگذارد. برای اهداف تحقیقاتی مختلف، ارزش آنها متفاوت است.

الگوریتم ۱: الگوریتم فضایی-زمانی Clusteirng و Companion Voting.

۳٫۲٫۴٫ رای همراه

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

مرحله III از الگوریتم رشد FP برای کشف نامزد همراه مسافر (ATCC) استفاده می کند و الگوریتم رشد FP یک روش مبتنی بر درخت است که از موارد مکرر استفاده می کند. از تکنیکی برای کوتاه کردن زمان جستجوی این الگوریتم در درخت پسوند استفاده می‌شود. به طور خاص، از آنجایی که FP-growth از مجموعه تک موردی مکرر به مجموعه n موردی مکرر جستجو می کند، وضعیت همراه بالقوه بین دو کاربر متمرکز خواهد شد و زمان همگرایی تا حد زیادی کاهش می یابد، اگر طول پسوند باشد. روی ۲ تنظیم کنید. به منظور استخراج بیشتر کاربران با الگوهای همراه، وقوع ارتباط بین کاربران قابل توجه است. علاوه بر این، مجموعه ای شامل تمام مجموعه کاربری از هر TLPC به عنوان هدف برای یافتن ATCC در نظر گرفته می شود.نسبت کل فرکانس همراه (TPAF) بین دو کاربر در این مجموعه با معادله ( ۱ ) محاسبه می شود که با یک پارامتر مقایسه می شود و برای رای دادن به ATCC استفاده می شود. ارتقای متقابل فرکانس همراه (MPAF) با استفاده از معادله ( ۲ ) برای قضاوت در مورد وقوع الگوی همراه بین دو کاربر محاسبه می شود. علاوه بر این، با یک آستانه برای تصمیم گیری در مورد رأی دادن به این دو کاربر که با ATCC ملاقات می کنند مقایسه می شود. در الگوریتم ۱، مراحل ۱۲-۱۵ نحوه کشف ATCC با استفاده از FP-growth را نشان می دهد. شکل ۳ فرآیند رأی گیری Companion را با جزئیات نشان می دهد، مانند ساخت FP-tree، محاسبه TPAF و TPAF برای دریافت ATCC.

اگر دو رکورد از کاربر X و Y که بخواهند TPAF را تجزیه و تحلیل کنند، TPAF مربوطه است :

(۱)

برای X و Y ، MPAF به صورت زیر به دست می آید:

(۲)

۳٫۲٫۵٫ فیلتر شبه همراه

هدف فیلتر شبه همراه ارائه قوانین مهم برای فیلتر کردن برخی سناریوهای گیج کننده شبه همراه است. این موقعیت های شبه همراه در کشف الگوهای همراه مسافر از ATCC از نتایج میانی در فرآیندهای قبلی است. شکل ۳ فرآیند فیلترسازی شبه همراه را به تفصیل نشان می دهد و فرآیند نیاز به استفاده از مجموعه قوانین فیلتر برای منابع داده های مختلف (DTS) دارد.

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

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

برای منابع داده های مختلف، تفاوت هایی در عوامل متمایز کننده سناریوهای شبه همراه وجود دارد. به عنوان مثال، در یک دوره طولانی مدت، کاربران ATCC ممکن است سوابق همراه زیادی برای مجموعه های نمونه پراکنده نداشته باشند. ضمناً می توان تشخیص داد که دارای شرایط همراه هستند. مطمئناً ممکن است به عنوان یک برخورد کوتاه مدت شناخته شود.

در الگوریتم ۲، مراحل ۱-۲۰ این مرحله را نشان می دهد. در میان آنها، مراحل ۱-۲، شبه کدهای کوتاه این مرحله هستند. مراحل ۴-۲۰ به وضوح یکی از مجموعه قوانین را نشان می دهد، که سناریوی فیلتر کردن تماس کوتاه در مجموعه نتایج میانی از منبع داده پراکنده است.

۳٫۲٫۶٫ ادغام گروه

هدف Stage V کشف همراهان مسافرتی است که شامل چندین کاربر می‌شود، نه فقط یک جفت شامل دو کاربر. مجموعه شامل چندین کاربر به عنوان یک گروه در نظر گرفته می شود. شکل ۳فرآیند ادغام گروه را با جزئیات نشان می دهد. لازم است تشخیص داده شود که آیا وضعیت همراه گروه وجود دارد و تصمیم به ادغام آنها گرفته شود. در مرحله III برای کشف نامزد همراه مسافر (ATCC)، ترفندی برای بهینه‌سازی سربار محاسباتی برای کاهش زمان همگرایی استفاده می‌شود که منجر به بحث در مورد سناریوهای تحقیقاتی بین دو کاربر می‌شود. با این حال، تعداد مجازی کاربران همراه ممکن است چندگانه باشد، مانند گروه های توریستی، شرکت کنندگان در فعالیت های گروهی یک خانواده سه نفره در خرید و غیره. -وضعیت کاربری که ممکن است در میان کاندیدای همراهی که قبلاً کشف شده بود وجود داشته باشد. اگر این کاربران در فیلتر شبه همراه فیلتر شده و باقی بمانند، آنها باید با استفاده از زیر مجموعه های رایج موجود ادغام شوند. به عنوان مثال، برای مجموعه ، زیرا دو مورد از زیرمجموعه ها دارای یک زیر مجموعه مشترک هستند ، دو زیرمجموعه را ادغام می کنیم و زیر مجموعه های واقعی دیگر را حذف می کنیم. در نهایت، مجموعه به تغییر می کند . در الگوریتم ۲، مراحل ۱۹-۲۵ این فرآیند را در آخرین مرحله نشان می دهد.

الگوریتم ۲: فیلترینگ شبه همراه و الگوریتم ادغام گروه.

۳٫۲٫۷٫ استراتژی تنظیم پارامتر

از آنجایی که در سناریوی کشف الگوهای همراه مسافر با ترکیب با نمونه های داده های واقعی باید عوامل زیادی در نظر گرفته شود، الگوریتم های مربوط به تنظیمات پارامتر در سه مرحله مهم این چارچوب (خوشه بندی مکانی- زمانی، رای گیری همراه، شبه) استفاده می شود. فیلتر همراه). برخی از این الگوریتم‌ها روش‌های نیمه نظارتی آشکاری دارند. اگرچه ما تعداد پارامترها را کاهش داده ایم و پیچیدگی استفاده از آنها را تا حد امکان در طول کاشت الگوریتم های مهم ساده کرده ایم. به عنوان مثال، ما دیگر استفاده از DBSCAN را در نظر نمی گیریم، بلکه از HDBSCAN به عنوان یک الگوریتم خوشه بندی استفاده می کنیم، فکر بهینه سازی پارامترهای موجود و ایجاد مجموعه ای از استراتژی ها اجتناب ناپذیر است. استراتژی پارامتر لازم، اثربخشی و کارایی روش را افزایش می‌دهد. که می تواند هزینه یادگیری این روش را کاهش دهد. علاوه بر این، تمام نمادهای پارامتر در بایگانی می شوندجدول ۳ .

استراتژی کلی: استراتژی کلی در اینجا به منظور برجسته کردن استراتژی تحمل توضیح داده شده است. اول، فرمول هارسین فرمولی است که به ویژه برای فاصله بین دو نقطه از طریق طول و عرض جغرافیایی آنها محاسبه می شود. بسیاری از الگوریتم‌های خوشه‌بندی شامل پارامتری به نام متریک هستند که می‌توان آن را به‌عنوان «haversine» تنظیم کرد. ثانیاً، برای کشف همسفران، حداقل تعداد خوشه‌بندی شده برای خوشه‌بندی باید بزرگتر از ۳ باشد تا تعداد خوشه‌ها کاهش یابد. علاوه بر این، برای تنظیم حمایت و اطمینان، جدول ۴یک مطابقت اولیه بین مشارکت و سطح اطمینان را نشان می دهد. امیدواریم سطح اطمینان بالاتری را تضمین کنیم، بنابراین مقدار اطمینان پیش‌فرض تعیین شده در این مطالعه ۰٫۶ است. برای سطح پشتیبانی، ما به طور همزمان روی فرکانس شی هدف تمرکز خواهیم کرد و لزوماً نیازی به دریافت نسبت نداریم. در نهایت، برای ثبات نتایج یک مجموعه داده برای اطمینان از پارامتر آستانه فاصله مهم است. به عنوان مثال، برای و ، با توجه به دقت نمونه برداری در مراحل مختلف روی یک مقدار تنظیم می شوند. قطعاً، اگر هدف برنامه‌ها نیاز به فیلتر کردن سخت‌گیرانه‌تری داشته باشد، باید پارامتر دوم را کوچک‌تر تنظیم کند.
استراتژی تحمل: در مقایسه با سخت‌گیری استراتژی کلی، استراتژی تحمل پشتیبانی خوبی برای مجموعه داده‌ها از برخی منابع داده خاص، مانند CDRها فراهم می‌کند. علاوه بر این، ارائه یک محدوده ارزش واضح برای برخی پارامترها برای مجموعه داده‌های مختلف دشوار است، در حالی که استراتژی تحمل پیشنهادی می‌تواند کاربران را راهنمایی کند تا برخی از ایده‌های تنظیم پارامتر را از هدف کاوی تضعیف کنند. هدف اصلی این استراتژی این است که برای نمونه‌های داده‌ای با پراکندگی بالاتر، محدودیت‌های آستانه سختی الزامی است تا مجموعه نتایج را تا حد امکان کوچک کند. در واقع تنظیم این استراتژی بیشتر از عملی بودن نتایج حاصل می شود. در این زمینه، پراکندگی داده های مسیر همیشه یک چالش بزرگ بوده است. همزمان، جمع آوری اطلاعات داده های همه کاربران در یک منطقه جغرافیایی خاص در مدت زمان طولانی برای برخی منابع داده خاص دشوار است. این منجر به پراکندگی داده های دنیای واقعی می شود که منطقی و اجتناب ناپذیر است. به همین دلیل، محققان باید امیدوار باشند که از هر اطلاعات ثبت شده (به جز نویز آشکار) استفاده کامل کنند. به طور خاص، برای برخی سناریوهای مهم، مانند استخراج الگوهای رفتاری گروه‌های خاص و افراد خاص برای کشف الگوی همسفر، گاهی اوقات عوامل مختلفی فرآیند جمع‌آوری را مختل می‌کنند به طوری که این داده‌ها پراکنده می‌شوند. در این حالت، استراتژی تلورانس بهتر می تواند از فیلتر شدن شدید برخی رکوردها جلوگیری کند که احتمال بیشتری برای یافتن سایر اجسام متحرک مرتبط وجود دارد. در مطالعه ما، برای این منجر به پراکندگی داده های دنیای واقعی می شود که منطقی و اجتناب ناپذیر است. به همین دلیل، محققان باید امیدوار باشند که از هر اطلاعات ثبت شده (به جز نویز آشکار) استفاده کامل کنند. به طور خاص، برای برخی سناریوهای مهم، مانند استخراج الگوهای رفتاری گروه‌های خاص و افراد خاص برای کشف الگوی همسفر، گاهی اوقات عوامل مختلفی فرآیند جمع‌آوری را مختل می‌کنند به طوری که این داده‌ها پراکنده می‌شوند. در این حالت، استراتژی تلورانس بهتر می تواند از فیلتر شدن شدید برخی رکوردها جلوگیری کند که احتمال بیشتری برای یافتن سایر اجسام متحرک مرتبط وجود دارد. در مطالعه ما، برای این منجر به پراکندگی داده های دنیای واقعی می شود که منطقی و اجتناب ناپذیر است. به همین دلیل، محققان باید امیدوار باشند که از هر اطلاعات ثبت شده (به جز نویز آشکار) استفاده کامل کنند. به طور خاص، برای برخی سناریوهای مهم، مانند استخراج الگوهای رفتاری گروه‌های خاص و افراد خاص برای کشف الگوی همسفر، گاهی اوقات عوامل مختلفی فرآیند جمع‌آوری را مختل می‌کنند به طوری که این داده‌ها پراکنده می‌شوند. در این حالت، استراتژی تلورانس بهتر می تواند از فیلتر شدن شدید برخی رکوردها جلوگیری کند که احتمال بیشتری برای یافتن سایر اجسام متحرک مرتبط وجود دارد. در مطالعه ما، برای محققان باید امیدوار باشند که از هر اطلاعات ثبت شده (به جز نویز آشکار) استفاده کامل کنند. به طور خاص، برای برخی سناریوهای مهم، مانند استخراج الگوهای رفتاری گروه‌های خاص و افراد خاص برای کشف الگوی همسفر، گاهی اوقات عوامل مختلفی فرآیند جمع‌آوری را مختل می‌کنند به طوری که این داده‌ها پراکنده می‌شوند. در این حالت، استراتژی تلورانس بهتر می تواند از فیلتر شدن شدید برخی رکوردها جلوگیری کند که احتمال بیشتری برای یافتن سایر اجسام متحرک مرتبط وجود دارد. در مطالعه ما، برای محققان باید امیدوار باشند که از هر اطلاعات ثبت شده (به جز نویز آشکار) استفاده کامل کنند. به طور خاص، برای برخی سناریوهای مهم، مانند استخراج الگوهای رفتاری گروه‌های خاص و افراد خاص برای کشف الگوی همسفر، گاهی اوقات عوامل مختلفی فرآیند جمع‌آوری را مختل می‌کنند به طوری که این داده‌ها پراکنده می‌شوند. در این حالت، استراتژی تلورانس بهتر می تواند از فیلتر شدن شدید برخی رکوردها جلوگیری کند که احتمال بیشتری برای یافتن سایر اجسام متحرک مرتبط وجود دارد. در مطالعه ما، برای گاهی اوقات عوامل مختلفی فرآیند جمع آوری را مختل می کند به طوری که این داده ها پراکنده می شوند. در این حالت، استراتژی تلورانس بهتر می تواند از فیلتر شدن شدید برخی رکوردها جلوگیری کند که احتمال بیشتری برای یافتن سایر اجسام متحرک مرتبط وجود دارد. در مطالعه ما، برای گاهی اوقات عوامل مختلفی فرآیند جمع آوری را مختل می کند به طوری که این داده ها پراکنده می شوند. در این حالت، استراتژی تلورانس بهتر می تواند از فیلتر شدن شدید برخی رکوردها جلوگیری کند که احتمال بیشتری برای یافتن سایر اجسام متحرک مرتبط وجود دارد. در مطالعه ما، برای و در منبع داده D1 تحمل را در نظر بگیرید. این دو پارامتر را می توان روی مقادیر بزرگتر تنظیم کرد تا سناریوهای سردرگمی را محدود کند، مثلاً تعداد کمی از رکوردها به هم مرتبط هستند و بیشتر رکوردها از هم فاصله دارند یا تعداد رکوردهای یک شی به قدری کم است که باید فیلتر شود. بیرون

۴٫ آزمایش و نتایج

تمامی الگوریتم‌ها در پایتون ۳٫۸٫۲ در PyCharm پیاده‌سازی شده‌اند و بر روی رایانه‌هایی با CPU Intel Core i7-8550U 1.80 گیگاهرتز، ۱۶٫۰ گیگابایت رم و ویندوز ۱۰ اجرا می‌شوند.

۴٫۱٫ مجموعه داده ها

بر اساس دو مجموعه داده دنیای واقعی، مجموعه‌های نمونه مختلفی بر اساس معیارهای مختلف استخراج می‌شوند. معیارها به شرح زیر نشان داده شده‌اند:

فرکانس نمونه برداری
تعداد سوابق برای افراد
مدت زمان موثر
دوره جمع آوری داده ها

D1 (مجموعه داده کاربران مسافر): این مجموعه داده از کاربران واقعی در منطقه خاصی از چین بین ۱۶ نوامبر ۲۰۱۴ تا ۱۸ نوامبر ۲۰۱۴ جمع آوری شده است که توسط یک ارائه دهنده ارتباطات در چین ارائه شده است. مکان ها از سایت های سلولی هستند که با تلفن های زیادی متصل هستند. داده‌های خط سیر فضایی خام عمدتاً شامل مختصات طول و عرض جغرافیایی، مهر زمان و اطلاعات کاربر است. هنگامی که ما این مجموعه داده را دریافت کردیم، اطلاعات حساس شخصی در مجموعه داده ناشناس شد و اطلاعات مختصات توسط این ارائه دهنده برای حفاظت از حریم خصوصی مجدداً تنظیم شد.
D2 (مسیر Geolife): این مجموعه داده در پروژه Geolife (Microsoft Research Asia) از ۱۸۲ کاربر بین آوریل ۲۰۰۷ و اوت ۲۰۱۲ جمع آوری شد [ ۵۱ ، ۵۲ ، ۵۳ ]. یک مسیر GPS از آن مجموعه با دنباله ای از نقاط مهر زمانی نشان داده می شود که حاوی اطلاعاتی در مورد طول و عرض جغرافیایی، طول و ارتفاع است. از مسیرها در یک نمایش متراکم هستند، به عنوان مثال، هر ۱-۵ ثانیه یا هر ۵-۱۰ متر در هر نقطه، نمای کلی این مجموعه داده در شکل ۵ نشان داده شده است :

انتخاب مجموعه داده های مناسب ضروری است. برای D1 و D2 پس از پیش پردازش داده ها بر اساس تعداد رکوردها به زیر مجموعه های زیادی تقسیم می شوند. به عنوان مثال، مجموعه داده های Geolife را با توجه به تعداد ۸۰۰۰۰۰ رکورد به ۱۹ زیر مجموعه تقسیم کردیم. در این زیر مجموعه ها، ۵ زیر مجموعه از D1 و D2 را به طور نسبی انتخاب می کنیم که در جدول ۴ نشان داده شده است. قابل ذکر است، یک مجموعه داده شبیه سازی شده به نام Sim1 بر اساس زیر مجموعه ای از D2 تولید می شود. Sim1 به عنوان زیر مجموعه ای از منابع واقعی و شبیه سازی شده D3 در نظر گرفته می شود.

با وجود این واقعیت که Sim1 اندازه کوچکی دارد، شامل دو کاربر شبیه‌سازی همراه است که ما برای یک کاربر خاص اضافه کرده‌ایم، که می‌توانند به سرعت کارایی الگوریتم را تأیید کنند. تولید دو داده شبیه سازی از درک مسیر یک کاربر واقعی به دست می آید، به ویژه برای اینکه بتوانیم درک ساده ای از تغییرات حالت آن داشته باشیم که اساسی ترین آن تغییر جهت آن در دو بعد طول و عرض جغرافیایی است. با ثبت یک ماتریس تغییر حالت، تغییرات حالت اولیه را می توان از داده های شبیه سازی آموخت و از این رو رفتار همراه مسافر را می توان شبیه سازی کرد.

به جز Sim1 و Set5، سایر زیرمجموعه ها اندازه داده مشابه و تعداد رکوردهای مشابهی دارند. ۱۰ زیرمجموعه نمونه (Set1-Set5 و Geo1-Geo5) به ترتیب از D1 و D2 به طور تصادفی انتخاب می شوند تا با تأثیر پراکندگی و چگالی مجموعه داده در صحنه دنیای واقعی بر نتایج الگوریتم مقایسه شوند. Set5 که اندازه آن حدود نیمی از ۹ مجموعه نمونه باقیمانده است، برای نشان دادن تأثیر اندازه داده ها بر روش استفاده می شود. مطمئناً برای پرداختن به مقیاس ۸۰۰۰۰۰ رکورد، محیط آزمایشی ما می تواند به محدودیت حافظه خود نزدیک شود.

۴٫۲٫ نمایش فیلترینگ سناریوهای شبه همراه

برخی از نتایج متوسط معمولی در شکل ۶ و شکل ۷ به تصویر کشیده شده اند، که موقعیت هایی هستند که باید فیلتر شوند. به منظور تسهیل نمایش، یک نوع داده از مجموعه قوانین را برای استفاده انتخاب می کنیم. این مورد از سناریوهای دو نوع در مجموعه داده های پراکنده است.

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

۴٫۳٫ نتایج کشف و اعتبارسنجی همراهان مسافرتی

۴٫۳٫۱٫ اندازه گیری زمان سربار

جدول ۵سربار زمانی ۱۰ زیر مجموعه داده در چارچوب را برجسته می کند، که در مرحله II تا مرحله V نشان داده شده است. بدیهی است که مرحله II بزرگترین مرحله سربار زمانی در این ۱۰ زیر مجموعه داده است و تفاوت های زیادی بین D1 و D2 دارد. سربار زمانی در مرحله III تحت تأثیر مقیاس زیر مجموعه داده است. در مرحله V، زمانی که نتیجه مرحله قبل منجر به عدم وجود چندین هدف شود، سربار زمانی آن ۰ خواهد بود. علاوه بر این، از میانگین تعداد رکوردهای کاربران برای نشان دادن پراکندگی هر زیر مجموعه داده استفاده می کنیم. بدیهی است که D1 یدک تر از D2 است. بنابراین، تنظیم پارامتر نباید برای D1 خیلی سخت باشد. در غیر این صورت، کشف TC دشوار خواهد بود. در عمل، قوانین فیلتر برای این نتیجه فیلتر کردن تماس مختصر برای D1 است. از آنجایی که این مجموعه قوانین در D2 با اثر نمونه گیری متراکم استفاده نمی شود، بنابراین هزینه زمانی ۰ در مرحله IV برای D2 است. در نهایت، شایان ذکر است که سربار زمانی در ادغام گروه بسیار کوتاهتر از سایر مراحل است که در این مقیاس از مجموعه داده قابل اغماض است. بنابراین، سربار در مرحله V نشان داده نمی شودجدول ۶ . تنظیمات پارامتر مربوطه در جدول ۷ نشان داده شده است. فاصله بر حسب متر و آستانه زمانی بر حسب ثانیه اندازه گیری می شود.

۴٫۳٫۲٫ تجزیه و تحلیل نتایج مهم

تعداد TC در هر زیر مجموعه داده در جدول ۵ نشان داده شده است . اگرچه برخی از زیرمجموعه‌ها نتایج کمی تولید می‌کنند یا هیچ نتیجه‌ای ندارند، اما با سناریوهای داده‌های دنیای واقعی بدون الگوی همراه مطابقت دارد. در ادامه با تجسم نتایج تجربی، برخی TC ویژه و معنادار ارائه شده است. به عنوان مثال، u0، u3، u4، و u30 از Geo3 به عنوان یک TC توصیه می‌شوند. در این دوره طولانی مدت Geo3، همه آنها در یک بازه زمانی نزدیک از طریق شبکه جاده ای در این منطقه جغرافیایی حرکت می کنند. بنابراین، مسیر حرکت آنها که در شکل ۸ نشان داده شده است ، بسیار شبیه به هم هستند و میزان پوشش در بین آنها بسیار بالا است. تفاوت اصلی در شکل ۸ نشان داده شده استآ. این بخش کوچکی از تفاوت مسیر است که ممکن است ناشی از جدایی کوتاه مدت یا مقدار معینی از دست دادن داده ناشی از تفاوت در سیگنال موقعیت یابی باشد. از طرف دیگر، u0 و u3 در یک دوره بلند مدت رکوردهای یکسانی دارند. برای تأیید این وضعیت، مجموعه داده‌های تقسیم‌نشده D2 را بیشتر بررسی کردیم. مشخص شده است که سوابق آنها از ساعت ۰:۵۲ در ۳۰ مارس ۲۰۰۹ تا ساعت ۲:۵۸ در ۵ ژوئیه ۲۰۰۹ یکسان ظاهر شده است. بنابراین، منطقی است حدس بزنیم که این احتمالاً در مورد فردی است که دو دستگاه تلفن همراه را حمل می کند. می تواند در مدیریت اشیاء خاص، مانند تمرکز بر افراد یا گروه هایی با رفتارهای حساس، حمایت مثبتی ارائه دهد. داده های نمونه در جدول ۸ نشان داده شده است .

۵٫ نتیجه گیری و بحث

در حال حاضر، دستگاه‌های موقعیت‌یابی موبایلی که توسط دستگاه‌های ناوبری، دستگاه‌های پوشیدنی هوشمند و زیرساخت‌های هوشمند نشان داده می‌شوند، به طور فزاینده‌ای در زندگی روزمره محبوب هستند. LBS به یک عنصر مهم تبدیل شده است که برای اکثر مردم در دسترس نیست. دستگاه‌های قابل مکان‌یابی و LBS شرایط کافی را برای تولید حجم عظیمی از داده‌های مسیر سیار فراهم می‌کنند. الگوریتم کشف همراه سفر به طور گسترده به عنوان یک روش مهم برای کشف الگوهای رفتاری همراه استفاده می شود. با این حال، لازم است کاربرد و کارایی روش با فرض انفجار اطلاعات فعلی و روش‌های نمونه‌گیری متنوع تا حد امکان بهبود یابد.

بنابراین، این مقاله به عنوان یکی از فناوری‌های پایه پشتیبانی بسیاری از برنامه‌های داده‌کاوی مسیر، یک چارچوب کاربردی GroupSeeker را برای کشف همراهان سفر در داده‌های مکانی-زمانی گسترده پیشنهاد می‌کند. این چارچوب شامل یک جریان پردازش پنج مرحله‌ای است و الگوریتم‌های اصلی در سه مرحله زیر قرار دارند، خوشه‌بندی فضایی-زمانی، رأی‌گیری همراه، و فیلتر شبه همراه. GroupSeeker با موفقیت از این مشکل جلوگیری می کند که خوشه های مفید به دلیل تقسیم بندی بد زمان به عنوان نویز در نظر گرفته می شوند. علاوه بر این، با توجه به پراکندگی متفاوت منابع داده، استراتژی‌های تنظیم پارامتر برای بهبود قابلیت اطمینان چارچوب و کاهش هزینه یادگیری پیشنهاد شده‌اند. علاوه بر این، مجموعه ای از روش های ناقص اما در واقع موثر برای فیلتر کردن سناریوهای گیج کننده پیشنهاد شده است. در عمل، پارامترها در GroupSeeker را می توان با توجه به هدف استخراج و سناریوهای خاص تنظیم کرد. در نهایت، چارچوب بر روی چندین مجموعه داده دنیای واقعی با پراکندگی و اندازه داده‌های مختلف ارزیابی می‌شود. نتایج تجربی عملاً کارایی و پایداری را نشان می دهد.

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

اختصارات

در این نسخه از اختصارات زیر استفاده شده است:

ANPR	تشخیص خودکار پلاک
ATCC	نامزد همراه مسافر
CDR ها	تماس با سوابق جزئیات
DBSCAN	انطباق فضایی مبتنی بر چگالی کاربرد با نویز
DENCLUE	خوشه بندی مبتنی بر چگالی
DTS	منبع داده های مختلف
DTWD	فاصله زمانی تابش پویا
HDBSCAN	خوشه بندی فضایی مبتنی بر چگالی سلسله مراتبی برنامه های کاربردی با نویز
HD-FIM	یک رویکرد ترکیبی توزیع شده وسعت اول و عمق اول با استخراج مجموعه آیتم های مکرر
IT ها	سیستم هوشمند
LBS	سرویس مبتنی بر مکان
LPC	کاندیدای بالقوه مکان
MBB	جعبه محدود کننده حداقل
MBR	حداقل مستطیل مرزی
MPAF	ارتقای متقابل فرکانس همراه
اپتیک	ترتیب نقاط برای شناسایی ساختار خوشه بندی
TLPC	زمان و مکان نامزد بالقوه
TC	همسفر
TPAF	نسبت کل فرکانس همراه

منابع

دفتر ملی آمار چین، بیانیه آماری جمهوری خلق چین در مورد توسعه ملی اقتصادی و اجتماعی در سال ۲۰۱۹٫ در دسترس آنلاین: http://www.stats.gov.cn/tjsj/zxfb/202002/t20200228_1728913.html (در دسترس ۲۸ فوریه ۲۰۲۰).
گائو، کیو. ژانگ، فلوریدا؛ وانگ، RJ; ژو، اف. داده های بزرگ مسیر: مروری بر فناوری های کلیدی در پردازش داده ها. Ruan Jian Xue Bao/J. نرم افزار ۲۰۱۷ ، ۲۸ ، ۹۵۹-۹۹۲٫ (به زبان چینی) [ Google Scholar ]
Elragal، A. تجزیه و تحلیل داده های مسیر در حمایت از مدیریت ترافیک. لکت. یادداشت ها محاسبه. علمی ۲۰۱۵ ، ۸۵۵۷ ، ۱۷۴-۱۸۸٫ [ Google Scholar ]
انامی، س. Shiomoto، K. پیش‌بینی تحرک فضایی-زمانی انسان بر اساس داده‌کاوی مسیر برای مدیریت منابع در شبکه‌های ارتباطی سیار. در مجموعه مقالات کنفرانس بین المللی IEEE در مورد سوئیچینگ و مسیریابی با عملکرد بالا، شی آن، چین، ۲۶ تا ۲۹ مه ۲۰۱۹؛ IEEE: Piscataway، نیوجرسی، ایالات متحده آمریکا، ۲۰۱۹؛ صص ۱-۶٫ [ Google Scholar ]
کین، تی. شانگگوان، دبلیو. آهنگ، جی. تانگ، جی. استخراج روتین فضایی-زمانی روی داده های تلفن همراه. ACM Trans. بدانید. کشف کنید. داده ۲۰۱۸ ، ۱۲ ، ۵۶٫۱–۵۶٫۲۴٫ [ Google Scholar ] [ CrossRef ]
لی، اچ. گو، ی. داده‌های حسگر موبایل استخراج برای رفتارهای اجتماعی. در مجموعه مقالات دومین کارگاه بین المللی سنجش اجتماعی، پیتزبورگ، PA، ایالات متحده آمریکا، ۲۱ آوریل ۲۰۱۷٫ [ Google Scholar ]
چن، ی. کرسپی، ن. Ortiz، AM; شو، ال. کاوی واقعیت: یک الگوریتم پیش بینی برای پویایی بیماری بر اساس داده های بزرگ تلفن همراه. Inf. علمی بین المللی J. ۲۰۱۷ ، ۳۷۹ ، ۸۲-۹۳٫ [ Google Scholar ] [ CrossRef ]
لیو، ایکس. تیان، ی. ژانگ، ایکس. Wan, Z. شناسایی مناطق عملکردی شهری در چنگدو بر اساس داده‌های سری زمانی مسیر تاکسی. بین المللی J. Geo-Inf. ۲۰۲۰ ، ۹ ، ۱۵۸٫ [ Google Scholar ] [ CrossRef ] [ نسخه سبز ]
ژنگ، ی. داده کاوی مسیر: مروری. ACM Trans. هوشمند سیستم تکنولوژی ۲۰۱۵ ، ۶ ، ۲۹:۱-۲۹:۴۱٫ [ Google Scholar ] [ CrossRef ]
تانگ، ال. ژنگ، ی. یوان، جی. هان، جی. لئونگ، آ. پنگ، دبلیو. Porta, TFL چارچوبی برای کشف همسفر در جریان داده های مسیر. ACM Trans. هوشمند سیستم تکنولوژی ۲۰۱۳ ، ۵ ، ۳:۱-۳:۳۴٫ [ Google Scholar ] [ CrossRef ]
زو، ام ال. لیو، سی. وانگ، X.-B. هان، ی.-بی. رویکردی برای کشف الگوی همراه بر اساس جریان داده anpr. Ruan Jian Xue Bao/J. نرم افزار ۲۰۱۷ . (به زبان چینی) [ Google Scholar ]
زو، ایکس. سان، تی. یوان، اچ. هو، ز. میائو، جی. بررسی الگوی حرکت گروهی از طریق داده های سلولی: مطالعه موردی گردشگران در هاینان. ISPRS Int. J. Geo-Inf. ۲۰۱۹ ، ۸ ، ۷۴٫ [ Google Scholar ] [ CrossRef ] [ نسخه سبز ]
گودموندسون، جی. van Kreveld، MJ محاسبات طولانی ترین گله های طول مدت در داده های مسیر. در مجموعه مقالات چهاردهمین سمپوزیوم بین المللی ACM در سیستم های اطلاعات جغرافیایی، ACM-GIS 2006، آرلینگتون، VA، ایالات متحده آمریکا، ۱۰-۱۱ نوامبر ۲۰۰۶٫ de By, RA, Nittel, S., Eds. ACM: نیویورک، نیویورک، ایالات متحده آمریکا، ۲۰۰۶; صص ۳۵-۴۲٫ [ Google Scholar ]
تانگ، ال. ژنگ، ی. یوان، جی. هان، جی. لئونگ، آ. هونگ، سی. پنگ، دبلیو. درباره کشف همراهان مسافر از مسیرهای جریانی. در مجموعه مقالات بیست و هشتمین کنفرانس بین المللی IEEE در مهندسی داده (ICDE 2012)، واشنگتن، دی سی، ایالات متحده آمریکا، ۱ تا ۵ آوریل ۲۰۱۲٫ Kementsietsidis, A., Salles, MAV, Eds. انجمن کامپیوتر IEEE: واشنگتن، دی سی، ایالات متحده آمریکا، ۲۰۱۲; ص ۱۸۶-۱۹۷٫ [ Google Scholar ]
ژانگ، ی. جی، جی. ژائو، بی. ژانگ، بی. الگوریتمی برای استخراج الگوی خوشه های شی متحرک تدریجی از جریان های مسیر. CMC-Comput. ماتر ادامه ۲۰۱۹ ، ۵۹ ، ۸۸۵–۹۰۱٫ [ Google Scholar ] [ CrossRef ]
یائو، آر. وانگ، اف. Chen, S. TCoD: روش کشف همراه مسافر بر اساس تجزیه و تحلیل خوشه‌بندی و انجمن. در مجموعه مقالات کنفرانس مشترک بین المللی شبکه های عصبی (IJCNN)، بوداپست، مجارستان، ۱۴ تا ۱۹ ژوئیه ۲۰۱۹؛ IEEE: Piscataway، نیوجرسی، ایالات متحده آمریکا، ۲۰۱۹؛ صص ۱-۷٫ [ Google Scholar ]
مکینز، ال. هیلی، جی. Astels, S. hdbscan: خوشه بندی مبتنی بر چگالی سلسله مراتبی. جی. ترش باز. نرم افزار ۲۰۱۷ ، ۲ ، ۲۰۵٫ [ Google Scholar ] [ CrossRef ]
آگراوال، آر. فالوتسوس، سی. سوامی، یک جستجوی کارآمد تشابه در پایگاه‌های داده توالی . Springer: برلین/هایدلبرگ، آلمان، ۱۹۹۳٫ [ Google Scholar ]
فالوتسوس، سی. رانگاناتان، ام. Manolopoulos، Y. تطبیق سریع دنباله‌ای در پایگاه‌های داده سری زمانی. در مجموعه مقالات کنفرانس بین المللی ACM SIGMOD 1994 در مدیریت داده ها، مینیاپولیس، MN، ایالات متحده، ۲۴-۲۷ مه ۱۹۹۴٫ صص ۴۱۹-۴۲۹٫ [ Google Scholar ]
چان، ک. Fu، AW تطبیق سری های زمانی کارآمد توسط موجک ها. در مجموعه مقالات پانزدهمین کنفرانس بین المللی مهندسی داده (Cat. No.99CB36337)، سیدنی، استرالیا، ۲۳-۲۶ مارس ۱۹۹۹٫ صص ۱۲۶-۱۳۳٫ [ Google Scholar ]
النکاوه، س. آخرین، م. Maimon، O. خوشه بندی افزایشی اشیاء متحرک. در مجموعه مقالات کنفرانس بین المللی IEEE در کارگاه مهندسی داده، ICDE 2007، استانبول، ترکیه، ۱۵-۲۰ آوریل ۲۰۰۷٫ صص ۵۸۵-۵۹۲٫ [ Google Scholar ]
De Vries، GKD; Van Someren، M. خوشه‌بندی مسیرهای کشتی با هسته‌های تراز تحت فشرده‌سازی مسیر. در مجموعه مقالات یادگیری ماشین و کشف دانش در پایگاه‌های داده، کنفرانس اروپایی، ECML PKDD 2010، بارسلون، اسپانیا، ۲۰-۲۴ سپتامبر ۲۰۱۰٫ جلد ۶۳۲۱، ص ۲۹۶–۳۱۱٫ [ Google Scholar ]
هایتاور، جی. Borriello، G. فیلترهای ذرات برای تخمین مکان در محاسبات همه جا حاضر: مطالعه موردی. در مجموعه مقالات UbiComp 2004: همه جا محاسباتی: ششمین کنفرانس بین المللی، ناتینگهام، انگلستان، ۷ تا ۱۰ سپتامبر ۲۰۰۴٫ جلد ۳۲۰۵، صص ۸۸–۱۰۶٫ [ Google Scholar ]
استر، ام. کریگل، اچ. ساندر، جی. Xu, X. الگوریتمی مبتنی بر چگالی برای کشف خوشه‌ها در پایگاه‌های داده فضایی بزرگ با نویز. Kdd ۱۹۹۶ ، ۹۶ ، ۲۲۶-۲۳۱٫ [ Google Scholar ]
پیپی، ز. چینگهای، دی. هایبو، ال. Xinglin، H. تشخیص دورتر مسیر بر اساس الگوریتم خوشه‌بندی DBSCAN. مهندسی لیزر مادون قرمز ۲۰۱۷ , ۴۶ , ۵۲۸۰۰۱٫ [ Google Scholar ] [ CrossRef ]
آنکرست، م. برونیگ، MM; کریگل، اچ. Sander, J. OPTICS: نقاط ترتیب برای شناسایی ساختار خوشه بندی. SIGMOD 1999. در مجموعه مقالات ACM SIGMOD کنفرانس بین المللی مدیریت داده ها، فیلادلفیا، PA، ایالات متحده آمریکا، ۱-۳ ژوئن ۱۹۹۹٫ صص ۴۹-۶۰٫ [ Google Scholar ]
هینهبورگ، ای. Keim, DA یک رویکرد کلی برای خوشه بندی در پایگاه های داده بزرگ با نویز. بدانید. Inf. سیستم ۲۰۰۳ ، ۵ ، ۳۸۷-۴۱۵٫ [ Google Scholar ] [ CrossRef ]
هینهبورگ، ای. گابریل، HH DENCLUE 2.0: خوشه بندی سریع بر اساس تخمین چگالی هسته. در مجموعه مقالات پیشرفت در تجزیه و تحلیل داده های هوشمند VII، هفتمین سمپوزیوم بین المللی تجزیه و تحلیل داده های هوشمند، IDA 2007، لیوبلیانا، اسلوونی، ۶-۸ سپتامبر ۲۰۰۷٫ جلد ۴۷۲۳، ص ۷۰–۸۰٫ [ Google Scholar ]
یانگ، ی. کای، جی. یانگ، اچ. ژانگ، جی. Zhao، X. TAD: یک الگوریتم خوشه‌بندی مسیر بر اساس تحلیل چگالی مکانی-زمانی. سیستم خبره Appl. ۲۰۲۰ , ۱۳۹ , ۱۱۲۸۴۶٫ [ Google Scholar ] [ CrossRef ]
گائو، ی. ژنگ، بی. چن، جی. Li, Q. الگوریتم‌هایی برای جست‌وجوهای محدود به نزدیکترین همسایه بر روی مسیرهای حرکت جسم. Geoinformatica ۲۰۱۰ ، ۱۴ ، ۲۴۱-۲۷۶٫ [ Google Scholar ] [ CrossRef ]
گودموندسون، جی. Valladares، N. یک رویکرد GPU برای خوشه‌بندی زیر مسیر با استفاده از فاصله Fréchet. در مجموعه مقالات کنفرانس بین‌المللی SIGSPATIAL 2012 در مورد پیشرفت‌ها در سیستم‌های اطلاعات جغرافیایی (که قبلاً GIS نامیده می‌شد)، SIGSPATIAL’12، Redondo Beach، CA، ایالات متحده آمریکا، ۷-۹ نوامبر ۲۰۱۲٫ صص ۲۵۹-۲۶۸٫ [ Google Scholar ]
دنگ، ز. هو، ی. زو، ام. هوانگ، ایکس. Du, B. یک اپتیک مقیاس پذیر و سریع برای خوشه بندی کلان داده های مسیر. خوشه. محاسبه کنید. ۲۰۱۵ ، ۱۸ ، ۵۴۹-۵۶۲٫ [ Google Scholar ] [ CrossRef ]
یوان، جی. سان، پ. ژائو، جی. لی، دی. وانگ، سی. مروری بر الگوریتم‌های خوشه‌بندی مسیر جسم متحرک. آرتیف. هوشمند Rev. ۲۰۱۷ , ۴۷ , ۱۲۳-۱۴۴٫ [ Google Scholar ] [ CrossRef ]
شیائو، ایکس. ژنگ، ی. لو، کیو. Xie، X. یافتن کاربران مشابه با استفاده از تاریخچه مکان مبتنی بر دسته. در مجموعه مقالات هجدهمین سمپوزیوم بین المللی ACM SIGSPATIAL در مورد پیشرفت ها در سیستم های اطلاعات جغرافیایی، ACM-GIS 2010، سان خوزه، کالیفرنیا، ایالات متحده آمریکا، ۳ تا ۵ نوامبر ۲۰۱۰٫ صص ۴۴۲-۴۴۵٫ [ Google Scholar ]
یینگ، JJC; لی، WC; Weng، TC; Tseng، VS استخراج مسیر معنایی برای پیش‌بینی مکان. در مجموعه مقالات نوزدهمین سمپوزیوم بین المللی ACM SIGSPATIAL در مورد پیشرفت در سیستم های اطلاعات جغرافیایی، ACM-GIS 2011، شیکاگو، IL، ایالات متحده آمریکا، ۱-۴ نوامبر ۲۰۱۱٫ صص ۳۴-۴۳٫ [ Google Scholar ]
لیو، حیله گر؛ Ni، LM به سمت خوشه بندی مبتنی بر تحرک. در مجموعه مقالات شانزدهمین کنفرانس بین المللی ACM SIGKDD در مورد کشف دانش و داده کاوی، واشنگتن، دی سی، ایالات متحده آمریکا، ۲۵ تا ۲۸ ژوئیه ۲۰۱۰٫ ص ۹۱۹-۹۲۸٫ [ Google Scholar ]
آندرینکو، جی. آندرینکو، ن. فوکس، جی. گارسیا، مسیرهای خوشه‌بندی JMC توسط قطعات مربوطه برای تجزیه و تحلیل ترافیک هوایی. IEEE Trans. Vis. محاسبه کنید. نمودار. ۲۰۱۸ ، ۲۴ ، ۳۴-۴۴٫ [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
زیتون، X. موریو، جی. خوشه‌بندی مسیر جریان‌های ترافیک هوایی در اطراف فرودگاه‌ها. هوانوردی علمی تکنولوژی ۲۰۱۹ ، ۸۴ ، ۷۷۶-۷۸۱٫ [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
گودموندسون، جی. Kreveld، MJV محاسبات طولانی‌ترین گله‌ها در داده‌های مسیر. در مجموعه مقالات چهاردهمین سمپوزیوم بین المللی ACM در سیستم های اطلاعات جغرافیایی، ACM-GIS 2006، آرلینگتون، VA، ایالات متحده آمریکا، ۱۰–۱۱ نوامبر ۲۰۰۶٫ [ Google Scholar ]
جونگ، اچ. Yiu، ML; ژو، ایکس. جنسن، CS; شن، اچ تی کشف کاروان ها در پایگاه داده های مسیر. Proc. VLDB Enddow. ۲۰۰۸ ، ۱ ، ۱۰۶۸-۱۰۸۰٫ [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
ژنهوی، ال. بولین، دی. هان، جی. ازدحام: استخراج خوشه‌های شی متحرک زمانی آرام. Proc. VLDB Enddow. ۲۰۱۰ ، ۳ ، ۷۲۳-۷۳۴٫ [ Google Scholar ]
کای، ز. یو، ز. یوان، نیوجرسی؛ Shang, S. در مورد کشف الگوهای جمع آوری از مسیرها. در مجموعه مقالات بیست و نهمین کنفرانس بین المللی IEEE در مهندسی داده، ICDE 2013، بریزبن، استرالیا، ۸ تا ۱۲ آوریل ۲۰۱۳٫ ص ۲۴۲-۲۵۳٫ [ Google Scholar ]
وانگ، ز. او، SY; لئونگ، ی. استفاده از داده های تلفن همراه برای تحقیقات رفتار سفر: مروری بر ادبیات. رفتار سفر. Soc. ۲۰۱۷ ، ۱۱ ، ۱۴۱-۱۵۵٫ [ Google Scholar ] [ CrossRef ]
فن، سی. کاوالارو، A. تشخیص تعاملات گروهی توسط انجمن آنلاین داده های مسیر. در مجموعه مقالات کنفرانس بین المللی IEEE 2013 در مورد آکوستیک، پردازش گفتار و سیگنال، ونکوور، BC، کانادا، ۲۶-۳۱ مه ۲۰۱۳٫ صفحات ۱۷۵۴-۱۷۵۸٫ [ Google Scholar ]
ژانگ، جی. لی، جی. وانگ، اس. لیو، ز. یوان، Q. Yang, F. در مورد بازیابی اشیاء متحرک الگوهای جمع آوری از داده های مسیر از طریق نمودار فضایی-زمانی. در مجموعه مقالات کنگره بین المللی IEEE در سال ۲۰۱۴ در مورد داده های بزرگ، انکوریج، AK، ایالات متحده، ۲۷ ژوئن تا ۲ ژوئیه ۲۰۱۴٫ صص ۳۹۰-۳۹۷٫ [ Google Scholar ]
Puntheeranurak، S. شین، تی تی. امامورا، ام. کشف کارآمد همراه مسافر از جریان داده سیر تکاملی. در مجموعه مقالات چهل و دومین کنفرانس سالانه نرم افزار و برنامه های کامپیوتری IEEE 2018، توکیو، ژاپن، ۲۳ تا ۲۷ ژوئیه ۲۰۱۸؛ جلد ۱، ص ۴۴۸-۴۵۳٫ [ Google Scholar ]
زو، ام. چن، ال. وانگ، جی. وانگ، ایکس. Han, Y. یک رویکرد خدمات پسند برای کشف همراهان مسافر بر اساس جریان داده ANPR. در مجموعه مقالات کنفرانس بین المللی IEEE در محاسبات خدمات، SCC 2016، سانفرانسیسکو، کالیفرنیا، ایالات متحده آمریکا، ۲۷ ژوئن تا ۲ ژوئیه ۲۰۱۶٫ صص ۱۷۱-۱۷۸٫ [ Google Scholar ]
شیا، دی. لو، ایکس. لی، اچ. وانگ، دبلیو. لی، ی. Zhang، Z. الگوریتم رشد الگوی مکرر موازی مبتنی بر کاهش نقشه برای تجزیه و تحلیل انجمن مکانی-زمانی داده های بزرگ مسیر موبایل. پیچیدگی ۲۰۱۸ ، ۲۰۱۸ ، ۲۸۱۸۲۵۱:۱–۲۸۱۸۲۵۱:۱۶٫ [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
Wen-Bo، HU; هوانگ، دبلیو. Guo-Chao، HU تحلیل الگوی ضمیمه مسیر بر اساس تجزیه و تحلیل خوشه‌بندی و انجمن اپتیک. محاسبه کنید. مد. ۲۰۱۷ . (به زبان چینی) [ Google Scholar ] [ CrossRef ]
البادوی، ع. لانگ، ز. ژانگ، ز. الحبیب، م. Alsabahi, K. یک رویکرد یکپارچه جدید برای کشف وسیله نقلیه همراه بر اساس استخراج مکرر مجموعه موارد در Spark. عرب J. Sci. مهندس ۲۰۱۹ ، ۴۴ ، ۹۵۱۷–۹۵۲۷٫ [ Google Scholar ] [ CrossRef ]
ژنگ، ی. ژانگ، ال. Xie، X. Ma، W. استخراج مکان های جالب و توالی سفر از مسیرهای GPS. در مجموعه مقالات کنفرانس بین المللی وب جهانی، مادرید، اسپانیا، ۲۰-۲۴ آوریل ۲۰۰۹; صص ۷۹۱-۸۰۰٫ [ Google Scholar ]
ژنگ، ی. لی، کیو. چن، ی. Xie، X. Ma, W. درک تحرک بر اساس داده های GPS. در مجموعه مقالات Ubicomp: Ubiquitous Computing، کنفرانس بین المللی، Ubicomp، سئول، کره، ۲۱-۲۴ سپتامبر ۲۰۰۸٫ صص ۳۱۲-۳۲۱٫ [ Google Scholar ]
ژنگ، ی. Xie، X. Ma، W. GeoLife: یک سرویس شبکه اجتماعی مشترک بین کاربر، مکان و مسیر. مهندسی (پایه) IEEE گاو نر ۲۰۱۰ ، ۳۳ ، ۳۲-۳۹٫ [ Google Scholar ]