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

کلید واژه ها:

شبکه جاده ای ؛ انتخاب مکان بهینه ؛ داده های ورود ؛ مشخصات کاربر ; درخت جی

1. مقدمه

بسیاری از مطالعات داده های بزرگ را برای کاربردهای تجاری اعمال کرده اند، از جمله کمک به نمایندگان املاک و مستغلات در یافتن مناطق مسکونی مناسب برای مشتریان [ 1 ] و کمک به شرکت ها برای تخمین تعداد مشتریانی که یک محصول ممکن است بر اساس ویژگی های آن جذب کند [ 2 ]. این برنامه‌ها با تکامل مستمر در عملکرد سخت‌افزار و محاسباتی فعال می‌شوند، که به کاربران اجازه می‌دهد تا مقادیر متنوع و انبوهی از اطلاعات مکانی و زمانی مانند مکان تقاطع‌های خیابان‌ها در شهر، فواصل بین تقاطع‌ها و بازدید را ذخیره و محاسبه کنند. سوابق کاربران این مطالعه ابزاری برای استفاده از این اطلاعات برای کمک به کسب‌وکارها برای یافتن مکان‌های مناسب برای فروشگاه‌های جدید مورد بحث قرار می‌دهد. این مشکل در ادبیات به خوبی در نظر گرفته شده است [ 3, 4 , 5 , 6 ]. به عنوان مثال، شبکه جاده ارائه شده در شکل 1 را در نظر بگیرید ، که در آن نقاط جامد نشان دهنده فروشگاه های موجود و نقاط توخالی مکان های نامزد را نشان می دهد. اگر کاربر U بخواهد یک رستوران خانوادگی جدید باز کند، الگوریتم هدف می تواند به U کمک کند تا بهترین مکان را پیدا کند. این الگوریتم مکان A را پیشنهاد می‌کند که در وسط گروهی از جاذبه‌های خانوادگی قرار دارد و از سایر رستوران‌های معروف خانوادگی دور است. برای راحتی، جاذبه ها و فروشگاه های موجود به عنوان «نقاط مورد علاقه» (POI) نامیده می شوند.
برخی از مطالعات قبلی موضوعات فوق را مورد بحث قرار داده اند. به عنوان مثال، Qi و همکاران. [ 7 ] و لی [ 4 ] با به حداقل رساندن میانگین فاصله اقلیدسی بین مشتری و نزدیکترین فروشگاه مشتری، مکان های بهینه فروشگاه را پیدا کردند. شیائو و همکاران [ 3 ] فاصله اقلیدسی را با فاصله جاده ای جایگزین کرد، زیرا این برای کاربران شبکه جاده ای شهودی تر است. لین و همکاران [ 5 ]، ساچاریدیس و همکاران. [ 6 ] و سو [ 8 ] برجسته کردند که [ 3 ، 4 ، 7] فقط تأثیر POIهای مثبت (یعنی آنهایی که مشتریان را جذب می کنند) در نظر بگیرید، از تأثیر POIهای منفی (یعنی آنهایی که مشتریان را دفع می کنند یا رقبا را نمایندگی می کنند) غفلت کنید. در نتیجه، صاحبان فروشگاه‌ها ممکن است اشتباهات مهمی را مرتکب شوند، مانند باز کردن یک نانوایی یا رستوران در کنار یک انبار زباله یا یک آرایشگر خانگی در کنار یک آرایشگاه شیک. با این حال، در حالی که در نظر گرفتن تأثیر هر دو POI مثبت و منفی نشان دهنده بهبود است، سطح تأثیر پیش بینی شده معمولاً غیر واقعی است. مطالعات قبلی نشان داده است که از آنجایی که فروشگاه جدید در زمان راه حل باز نیست، نمی توان میزان تأثیر هر POI بر فروشگاه جدید را محاسبه کرد. بنابراین، این تأثیرات را فقط می توان روی یک مقدار ثابت تنظیم کرد که منجر به عدم دقت می شود.
این مقاله استفاده از پایگاه‌های داده شبکه اجتماعی مبتنی بر مکان (مجموعه‌های داده LBSN) را برای تخمین تأثیر POIهای مثبت و منفی بر فروشگاه جدید پیشنهاد می‌کند. خدمات LBSN کاربران را قادر می‌سازد تا اطلاعات داوطلبانه (معروف به نمایه‌های کاربر) را در مجموعه داده‌های LBSN ارائه کنند و مکان‌هایی را که بازدید می‌کنند و همچنین بررسی این مکان‌ها (معروف به داده‌های ورود) را به اشتراک بگذارند. Foursquare [ 9 ] و Facebook [ 10 ] نمونه های خوبی هستند. مجموعه داده های LBSN داده های رفتاری دنیای واقعی را ارائه می دهند و به طور گسترده در انواع برنامه های تجاری استفاده می شوند [ 11 ، 12 ، 13]. ما پیشنهاد می کنیم درجه تأثیر هر POI بر پایگاه مشتری فروشگاه جدید را با درخواست از کاربر درخواست کننده برای شناسایی POIهای مرجع ارزیابی کنیم. به عنوان مثال، برای یک رستوران خانوادگی، POI های مرجع ممکن است رستوران های خانوادگی دیگر یا زمین های بازی کودکان باشند. تأثیر یک POI بر فروشگاه جدید به عنوان میانگین امتیاز تأثیر آن POI با همه POI های مرجع انتخاب شده تعریف می شود. این رویکرد مرسوم مقادیر ثابت را برای تأثیر POI اصلاح می کند.
در حالی که دقت توصیه‌ها را افزایش می‌دهد، استفاده از داده‌های LBSN برای مسئله هدف، هزینه محاسباتی الگوریتم پیشنهادی را تا حد زیادی افزایش می‌دهد. نه تنها باید داده های اضافی از مجموعه داده LBSN بازیابی شود، بلکه تأثیر هر POI باید یک به یک محاسبه شود. در این مقاله سه الگوریتم ارائه شده است. اولی الگوریتم پایه است که مفاهیم اساسی را برای حل مسئله پیشنهادی معرفی می کند. الگوریتم های دوم و سوم بر اساس ساختار داده جدید G + -tree (که نمایانگر گسترش G-tree است) برای کاهش هزینه محاسباتی و تسریع سرعت پرس و جو هستند. کارایی روش های پیشنهادی بر روی دو مجموعه داده شبیه سازی شده و یک مجموعه داده واقعی تأیید می شود.
این مقاله کمک های جدیدی به موضوع، هم از نظر مفهومی و هم از نظر طراحی الگوریتم می کند. جدول 1 فاکتورهای در نظر گرفته شده در این مطالعه را فهرست می کند: فاصله جاده، POI های مثبت و منفی، و میزان تأثیر POI بر اساس مجموعه داده های LBSN. در مقایسه با مطالعاتی که درجه نفوذ را با استفاده از یک مقدار ثابت تعیین می‌کنند، رویکرد پیشنهادی بیشتر با نیازهای دنیای واقعی کاربران مطابقت دارد. از نظر طراحی الگوریتم، ما ساختار داده جدید G + -tree را برای کاهش بار محاسباتی معرفی شده با استفاده از مجموعه داده های LBSN پیشنهاد می کنیم.
این مقاله علیرغم کمک های ارزشمند خود، دارای دو محدودیت مهم است. به طور کلی، داده های LBSN در معرض سوگیری کاربر [ 16 ، 17 ، 18 ] هستند و ممکن است همیشه با موقعیت های دنیای واقعی مطابقت نداشته باشند. این می تواند یک شکاف بین خروجی راه حل توسط الگوریتم و بهترین راه حل واقعی ایجاد کند. با این حال، این شکاف معمولاً مجاز در نظر گرفته می شود، زیرا مجموعه داده LBSN نسبت به سایر مجموعه داده های عمومی به واقعیت نزدیک تر است. اطلاعات بیشتر در [ 16 ، 17 ، 18 موجود است]. علاوه بر این، گروه های مشتریان و نزدیکی به POI های مثبت و منفی تنها عوامل موثر بر انتخاب بهینه مکان برای یک فروشگاه جدید نیستند. سایر عوامل مهم عبارتند از حمل و نقل، اجاره، کاربری زمین و مجوزها. از آنجایی که مقاله فعلی بر سهم جدید شامل میزان تأثیر POI بر پایگاه مشتری برای فروشگاه جدید بر اساس داده‌های LSBN متمرکز است، این عوامل اضافی فراتر از محدوده این مقاله در نظر گرفته می‌شوند. رویکرد کلی پیشنهاد شده در این مقاله می‌تواند برای شامل متغیرهای خاصی مانند اینها، توسط خواننده یا مطالعات آینده سازگار شود.
بقیه این مطالعه به شرح زیر سازماندهی شده است. بخش 2 ادبیات مربوطه را بررسی می کند و بخش 3 به طور رسمی مشکل را تعریف می کند. بخش 4 چارچوب سیستم را توضیح می دهد و الگوریتم پایه را به تفصیل شرح می دهد. بخش 5 الگوریتم هرس منطقه (AP) را ارائه می دهد. بخش 6 الگوریتم هرس ناحیه و لبه (AEP) را ارائه می کند. بخش 7 نتایج آزمایش ما را ارائه می دهد و بخش 8 شامل نتیجه گیری های ما است.

2. کارهای مرتبط

2.1. شبکه های اجتماعی مبتنی بر مکان (مجموعه داده های LBSN)

خدمات LBSN کاربران را قادر می سازد تا تجربیات سفر خود را در هر زمان و هر مکان از طریق دستگاه های تلفن همراه به اشتراک بگذارند. تجربیات آنها با زمان ورود، مکان POI بازدید شده توسط کاربر، و شناسه کاربر نشان داده می شود. همچنین امکان جمع آوری اطلاعات جمعیت شناختی مانند سن، جنسیت و سابقه تحصیلی کاربران را فراهم می کند که معمولاً در قالب نمایه های کاربر ارائه می شود. برنامه های کاربردی متعددی برای چنین داده های LBSN وجود دارد. لی و همکاران [ 19 ] و بائو و همکاران. [ 20 ] برای کمک به کاربران برای یافتن POI های دلخواه خود و کمک به دارندگان POI برای جذب مشتریان بیشتر، از داده های ورود استفاده کرد. حسیه و همکاران [ 21 ] و لو و همکاران. [ 22 ] سفرهای شخصی‌شده را با استخراج رفتارهای ورود کاربر توصیه می‌کند. ون و همکاران [ 23] مشاهده کرد که هنگام برنامه ریزی سفر، کاربران ممکن است از کلمات کلیدی برای نشان دادن ترجیحات خود استفاده کنند. آنها از داده های LBSN برای یافتن خطوط افق مسیرهای سفر استفاده کردند که اندازه گیری های چند بعدی (جذابیت POI، زمان مناسب بازدید و تأثیر اجتماعی جغرافیایی) مسیرها را ترکیب می کند.

2.2. برنامه های کاربردی تجاری

آروانیتیس و همکاران [ 2 ] مفهوم جذابیت محصول را بر اساس مفهوم پرس و جوهای خط افق معکوس فرموله کرد و به شرکت ها کمک کرد تا تعداد مشتریانی را که یک محصول ممکن است بر اساس ویژگی های آن جذب کند تخمین بزنند. ژانگ و همکاران [ 1 ] پرس و جوی مکان بهینه چند معیاره (MOLQ) را ارائه کرد، که می تواند برای کمک به مصرف کنندگان در انتخاب یک مکان مسکونی اعمال شود. وانگ و همکاران [ 24 ] به شرکت‌ها در شناسایی مجموعه‌ای از افراد در یک شبکه اجتماعی کمک کرد که می‌تواند نفوذ مورد انتظار را در بازاریابی ویروسی به حداکثر برساند. ارتقای مشترک یک استراتژی تجاری ارزشمند است که شرکت ها را قادر می سازد مشتریان بیشتری را با هزینه عملیاتی کمتر جذب کنند. هوانگ و همکاران [ 11] چارچوب Joint Promotion Partners Finding (JPPF) را توسعه داد که از داده های شبکه های اجتماعی مبتنی بر مکان برای شناسایی خودکار شرکا استفاده می کند.

2.3. جستجوهای مکان فروشگاه بهینه

تنها با در نظر گرفتن PPOI، چندین مطالعه در مورد مکان‌های فروشگاهی بهینه فقط تأثیر PPOI را در نظر می‌گیرند. لی و همکاران [ 4 ] و Qi و همکاران. [ 7 ] مکان بهینه را با حداقل فاصله کل بین همه مشتریان و نزدیکترین فروشگاه های مربوطه تعریف کرد. شیائو و همکاران [ 3 ] سه نوع جستجوی مکان بهینه را به شرح زیر بررسی کرد: (1) پرس و جوی موقعیت مکانی رقابتی یک مکان نامزد p را می خواهد که وزن کل مشتریان جذب شده توسط یک فروشگاه جدید ساخته شده بر روی p را به حداکثر برساند . (2) پرس و جو مکان MinSum یک مکان نامزد p را می خواهدکه در آن می توان یک فروشگاه جدید برای به حداقل رساندن مجموع فاصله جذب کننده وزن مشتریان ایجاد کرد. (3) پرس و جوی مکان MinMax یک مکان نامزد p را می خواهد تا یک فروشگاه جدید ایجاد کند که حداکثر فاصله جذب کننده وزنی مشتریان را به حداقل برساند. چن و همکاران [ 14 ] الگوریتم های کارآمدتری را برای پرس و جوی مکان MinMax و پرس و جو مکان رقابتی پیشنهاد کرد. خو و همکاران [ 15 ] الگوریتم کارآمدتری برای پرس و جو مکان MinSum پیشنهاد کرد.
با در نظر گرفتن PPOI و NPOI، برخی از مطالعات تأثیر هر دو PPOI و NPOI را برای مشکل مکان فروشگاه بهینه در نظر گرفته اند. لین و همکاران [ 5 ] و سو و همکاران. [ 8 ] فواصل را از دورترین PPOI و نزدیکترین NPOI در نظر گرفت و آنها را در خطوط آسمان ادغام کرد. ساچاریدیس و همکاران [ 6 ] از تفاوت بین فاصله از نزدیکترین PPOI و نزدیکترین NPOI استفاده کرد.

3. بیان مشکل

این بخش مسئله هدف را تعریف می کند و متغیرهای مورد نیاز برای حل آن را معرفی می کند. جدول 2 تعاریفی از متغیرها را ارائه می دهد که می توان آنها را به سه دسته تقسیم کرد: مربوط به کاربر، مرتبط با POI و مرتبط با امتیاز. متغیر اول فقط شامل یک متغیر است: کاربرانی که قصد دارند یک فروشگاه جدید باز کنند که ما آن را به عنوان query user q تعریف می کنیم . هنگامی که q یک پرس و جو می کند، او باید سه نوع POI را به سیستم ارائه دهد: POI های مثبت (PPOI)، POI های منفی (NPOI) و POI های مرجع (RPOI)، که POI هایی هستند که q می خواهد فروشگاه جدید نزدیک باشد. به ترتیب به، دور از، و شبیه به سبک. به احتمال زیاد از هر نوع POI فقط یکی وجود ندارد، بنابراین این سه نوع POI به عنوان بردار ذخیره می شوند (یعنیpP ، nP و rP ). همه POIهای روی نقشه با q مهم در نظر گرفته نمی شوند و ما به این POIها به عنوان POIهای نامرتبط (UPOI) اشاره می کنیم. شکل 1 روابط بین این متغیرهای مرتبط با POI را نشان می دهد. هر نقطه جامد در شبکه جاده ها نشان دهنده یک فروشگاه یا یک جاذبه در شهر است. فرض کنید یک کاربر q می‌خواهد یک رستوران خانوادگی جدید با موضوع حیوانات در این شهر باز کند و با استفاده از سیستم پیشنهادی با pP = {پارک کودکان، فروشگاه اسباب‌بازی، موزه هنر، موزه ترافیک، موزه حیوانات} یک پرس و جو انجام می‌دهد. همه این مکان ها POI هایی هستند که خانواده ها دوست دارند به آنجا بروند. qممکن است بخواهند رستوران خانوادگی جدیدشان تا حد امکان از سایر رستوران‌های خانوادگی دور باشد، بنابراین ممکن است nP = {McDonald’s, KFC, Wendy’s, Subway, Panda Express} را تنظیم کنند. در مرحله بعد، چون رستورانی که می خواهند باز کنند با تم حیوانات است، ممکن است باغ وحش شهر را به عنوان RPOI تعیین کنند (یعنی rP = {شهر باغ وحش}). در نهایت، POI های باقی مانده، شهرداری، اداره پست و بانک، خانواده ها را جذب نمی کنند، با رستوران های خانوادگی برای مشتریان رقابت نمی کنند، یا به عنوان مرجع برای رستوران های جدید عمل نمی کنند، بنابراین q آنها را به عنوان UPOI در نظر می گیرد.
سه متغیر مرتبط با امتیاز وجود دارد: امتیاز شباهت مشتری، امتیاز تأثیر و امتیاز مکان. فرض کنید کاربر q می خواهد یک فروشگاه جدید باز کند و PPOI، NPOI، RPOI و UPOI فروشگاه را تنظیم کند. دو متغیر اول در این دسته برای محاسبه روابط بین مشتریان POI و مشتریان فروشگاه جدید استفاده می شود. آخرین متغیر برای محاسبه امتیاز پیشنهادی هر نقطه از شبکه جاده ای استفاده می شود. این امتیاز میزان مناسب بودن مکان برای فروشگاه جدید را اندازه گیری می کند.

امتیاز شباهت مشتری CS ( p i , p j ) نشان دهنده رابطه بین مشتریان یک POI p i موجود و دیگری POI p j است . در مرحله بعد، امتیاز تأثیر CI ( Q ، pj ) تأثیر pj را بر مشتریان فروشگاه جدیدی که توسط q افتتاح می‌شود، نشان می‌دهد ، که در آن Q = { pP، nP، rP } شرط پرس و جو است که توسط q ارائه می‌شود . معادله ارزیابی CI( Q , p j ) را می توان به صورت زیر بیان کرد:

CI ( Q , p j ) = α × ∑ pi ∈ rP CS ( p i , p j )/| rP |،

کجا | rP | تعداد کل RPOI های تعیین شده توسط q را نشان می دهد . ∑ pi ∈ rP CS ( p i , p j )/| rP | مقدار متوسط ​​روابط بین مشتریان p j و همه RPOI های تعیین شده توسط q است . و α یک متغیر کنترلی است. وقتی p j یک PPOI برای q باشد، آنگاه α = 1 است. وقتی p j یک NPOI برای q باشد، α = -1 است. وقتی p j یک UPOI برای q باشدواضح است که با این فرمول می‌توانیم تأثیر احتمالی هر POI بر مشتریان فروشگاه جدید را بر اساس فروشگاه‌های مرجع، قبل از اینکه q فروشگاه جدید باز کند، تخمین بزنیم. PPOI ها تأثیر مثبتی بر مشتریان فروشگاه جدید دارند، NPOI ها تأثیر منفی بر مشتریان فروشگاه جدید دارند و UPOI ها تأثیری بر مشتریان فروشگاه جدید ندارند. در نهایت، پس از محاسبه تأثیر همه POI ها بر مشتریان فروشگاه جدید، می توانیم امتیاز توصیه هر نقطه (یعنی امتیاز مکان) در شبکه جاده را محاسبه کنیم تا مشخص شود که آیا مکان مناسبی برای فروشگاه جدید است یا خیر. امتیاز مکان به شرح زیر محاسبه می شود:

LS ( o ، pP ، nP ) = ∑ pj ∈ pP ∪ nP dist ( o ، pj ) × CI ( Q ، pj ) ،

که در آن o هر نقطه داده شده در شبکه جاده را نشان می دهد و dist ( o ، pj ) نشان دهنده کوتاه ترین فاصله جاده بین o و pj در نقشه راه است . توجه داشته باشید که ما از فاصله جاده به جای فاصله اقلیدسی استفاده کردیم زیرا اکثر مردم هنگام سفر در یک شهر، فاصله جاده را در نظر می گیرند. توجه داشته باشید که مقدار کمتر برای LS ( o ، pP ، nP ) مکان بهتری را نشان می دهد. این به این دلیل است که در معادله (2)، CI ( Q ، pj )، تأثیر هر POI pjدر مشتریان فروشگاه جدید در هر پرس و جوی منفرد که توسط q انجام می شود باید یک مقدار ثابت باشد، زیرا CI ( Q , p j ) فقط روابط بین مشتریان p j و RPOI های تنظیم شده توسط q را در نظر می گیرد. در مرحله بعد، اگر p j در معادله (2) یک PPOI باشد، ما می خواهیم o تا حد امکان به p j نزدیک شود زیرا این امر باعث کوچکتر شدن فاصله ( o , pj ) و LS ( o , pP , nP ) می شود.) کوچکتر نیز هست.

فرمول مسأله. کاربر Query q مجموعه ای از PPOI، NPOI و RPOI (یعنی { pP , nP , rP } ) را وارد می کند. سپس، سیستم پرس و جوی هدف از داده‌های ورود و پروفایل کاربر در مجموعه داده‌های LBSN برای محاسبه LS ( o , pP , nP ) هر نقطه o در شبکه جاده‌ها استفاده می‌کند. مکان o با کوچکترین LS ( o ، pP ، nP ) انتخاب بهینه برای فروشگاه جدید است.

4. الگوریتم پایه

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

4.1. چارچوب سیستم با استفاده از الگوریتم پایه

همانطور که در شکل 2 نشان داده شده است ، چارچوب سیستم مورد استفاده در این مطالعه شامل دو مرحله است: پردازش آفلاین و پرس و جو آنلاین. پردازش آفلاین با تجزیه و تحلیل شباهت‌های بین گروه‌های مشتریان POI مختلف شروع می‌شود تا آنها را به امتیازات شباهت مشتری تبدیل کند. این امتیازها در یک ماتریس ذخیره می شوند تا امتیاز تأثیرگذاری POI در مرحله دوم تنظیم شود. سپس شاخص G-tree برای محاسبه سریع فاصله جاده بین دو نقطه در مرحله دوم ایجاد می شود. پس از اینکه مجموعه پرس و جو Q = { pP , nP , rP } توسط کاربر وارد شد، مرحله دوم برای شناسایی مکان ذخیره بهینه برای Q مقداردهی اولیه می شود .

4.2. تجزیه و تحلیل شباهت ها بین گروه های مشتری

تجزیه و تحلیل گروه های مشتری شامل سه مرحله است: (1) خوشه بندی مشتریان، (2) یافتن ویژگی های مشترک مشتریان در هر گروه، و (3) محاسبه امتیاز شباهت مشتری برای ذخیره در یک ماتریس.
اگر کاربر u در POI p ثبت نام کرده باشد، می توانیم شما را به عنوان مشتری p در نظر بگیریم . بنابراین می‌توانیم از داده‌های اعلام حضور برای شناسایی مشتریان هر فروشگاه استفاده کنیم و آنها را بر اساس ویژگی‌هایشان با استفاده از نمایه‌های کاربری‌شان خوشه‌بندی کنیم. این ویژگی‌ها به ما امکان می‌دهد امتیازهای شباهت را در بین گروه‌های مشتریان POIهای مختلف محاسبه کنیم.

4.2.1. خوشه بندی مشتریان

قبل از خوشه بندی مشتریان، ابتدا پروفایل های کاربری آنها را عادی می کنیم. فرض کنید ویژگی های پروفایل کاربر شامل سن، جنسیت، سابقه تحصیلی و درآمد سالانه است. برای سن و درآمد سالانه که به طور طبیعی مثبت هستند، آنها را بر مقادیر حداکثر تقسیم می کنیم تا بین 0 و 1 نرمال شود. برای چنین ویژگی‌هایی، اگر n گزینه وجود داشته باشد، می‌توانیم مقدار i امین گزینه را به صورت i /( n – 1) قرار دهیم تا آن را بین 0 و 1 نرمال کنیم.
پس از عادی سازی، مشتریان را به چند گروه تقسیم می کنیم. از آنجایی که ما از توزیع مشتریان هر فروشگاه اطلاعی نداریم، از پیشنهاد [ 25 ] پیروی می کنیم و از روش خوشه بندی حداکثر انتظارات استفاده می کنیم. ما از این گروه ها به عنوان گروه های مشتری یاد می کنیم.
4.2.2. شناسایی ویژگی های مشترک
اگر مقادیر مشخصه a i برای گروه مشتری متمرکز باشد، تعداد بیشتری از اعضای گروه مشتری این ویژگی را دارند و یک i را نماینده گروه مشتری به عنوان یک کل می کند. ما ضریب تغییرات را برای ارزیابی درجه پراکندگی بین مقادیر اتخاذ می کنیم. ضریب تغییرات کوچکتر برای i از گروه مشتری به این معنی است که مشخصه بیشتر نماینده گروه مشتری است. ما ضریب تغییرات هر یک از مشخصه های هر گروه مشتری را به ترتیب صعودی رتبه بندی می کنیم و از n مشخصه برتر برای نشان دادن گروه مشتری استفاده می کنیم. ضریب تغییرات برابر با σ / μ است، که σ انحراف معیار و μ میانگین است.
4.2.3. محاسبه امتیاز شباهت مشتری

در این مرحله، CS ( p i ، pj ) ، امتیاز شباهت مشتری بین POIs p i و pj را محاسبه می‌کنیم . نتیجه در ماتریس M ذخیره می شود . ما CS ( p i , p j ) را به عنوان تعداد مورد انتظار مشتریانی که p i می تواند از p j جذب کند تعریف می کنیم . فرض کنید که گروه مشتریان p i و p j را می توان به ترتیب به صورت { cg i 1 بیان کرد،cg i 2 , …, cg ik } and { cg j 1 , cg j 2 , …, cg jk }. برای هر cg jn از p j ، ابتدا شباهت بین cg jn و همه گروه های مشتریان p i را ارزیابی می کنیم. سپس بالاترین مورد را از بین آنها به عنوان احتمال اینکه اعضای cg jn مشتری p i شوند انتخاب می کنیم. تعداد مشتریان مورد انتظار برابر است با مجموع تعداد مشتریان ضرب در این احتمال. بنابراین، CS( p i , p j ) را می توان به صورت زیر محاسبه کرد:

CS ( p i , p j ) = ∑ n =1~ k | cg jn | × حداکثر cgim∈ pi cgSIM ( cg jn ، cg im )،

کجا | cg jn | تعداد مشتریان در cg jn است و cgSIM ( cg jn , cg im ) نشان دهنده درجه شباهت بین گروه های مشتری cg jn و cg im است.

در ادامه ابزارهای محاسبه درجات شباهت بین گروه‌های مشتری (یعنی cgSIM ( cg jn ، cg im ) در معادله (3)) را معرفی می‌کنیم. این با استفاده از شکل اصلاح شده شباهت جاکارد به دست می آید. ما از مجموعه مشخصه مشترک برای نشان دادن گروه مشتری استفاده می کنیم و با محاسبه میزان شباهت بین دو مجموعه مشخصه مشترک، درجه شباهت بین دو گروه مشتری را محاسبه می کنیم. شباهت جاکارد J ( A , B ) درجه تشابه بین دو مجموعه A و B را محاسبه می کند [ 26 ]. مقدار J ( A, B ) از 0 تا 1 متغیر است. وقتی A و B یکسان هستند، J ( A , B ) برابر 1 است. وقتی A و B کاملاً متفاوت هستند J ( A , B ) برابر 0 است . J ( A , B ) بنابراین برابر است تقاطع A و B تقسیم بر اتحاد A و B. با این حال، شباهت جاکارد تنها تلاقی و اتحاد دو مجموعه را در نظر می گیرد و توزیع ویژگی های مشترک را در نظر نمی گیرد. بنابراین، ما پیشنهاد می‌کنیم شباهت جاکارد را با جایگزین کردن تعداد تقاطع‌های دو مجموعه مشخصه مشترک با شباهت کل بین توزیع‌های مشترک ویژگی‌های مشترک اصلاح کنیم. شباهت cgSIM ( cg i , cg j ) بین دو گروه مشتری cg i و cg j را می توان به صورت زیر محاسبه کرد:

که در آن D ( cg , f ) توزیع مشتریان در گروه مشتری cg با توجه به مشخصه مشترک f را نشان می دهد و fSIM (∙,∙) شباهت بین توزیع ویژگی های مشترک است.

ما درجات شباهت بین دو توزیع از ویژگی‌های مشترک (یعنی fSIM (∙،∙) در معادله (4)) را با استفاده از شکل اصلاح‌شده واگرایی جنسن-شانون (JS) محاسبه می‌کنیم. واگرایی JS [ 27 ] شکل اصلاح شده واگرایی Kullback-Leibler (KL) است. واگرایی KL KLD(Da | Db ) تفاوت بین دو توزیع D a و Db را به صورت زیر اندازه گیری می کند :

با این حال، واگرایی KL تفاوت غیر متقارن را اندازه گیری می کند، به این معنی که KLD ( Da | Db ) برابر با KLD نیست ( Db | D a ) . برای حل این مشکل واگرایی JS (که متقارن است) به صورت زیر محاسبه می شود:

که در آن D m = ( D a + D b )/2. مقدار JSD ( Da | Db ) از 0 تا 1 متغیر است. مقدار JSD ( Da | Db ) متناسب با تفاوت بین توزیع‌های D a و Db است . JSD ( D a | D b ) برابر 0 در حداقل اختلاف بین D a و D b استو 1 در حداکثر اختلاف بین D a و D b . از آنجایی که شباهت برعکس تفاوت است، می‌توانیم فرمولی برای نمایش شباهت بین دو توزیع از ویژگی‌های مشترک به صورت زیر طراحی کنیم:

fSIM ( D a , D b ) = 1 – JSD ( D a , D b ).

4.3. ایجاد شاخص نقشه راه

ما از شاخص درخت G برای کمک به سیستم برای محاسبه سریع فاصله جاده بین نقاط استفاده کردیم. G-tree یک شاخص درخت کارآمد است که توسط Zhong و همکارانش پیشنهاد شده است. [ 28 ] برای جستجوهای KNN در شبکه های جاده ای. آنها به صورت بازگشتی شبکه جاده را به شبکه های فرعی تقسیم می کنند و یک ساختار درختی در بالای زیرشبکه ها می سازند که در آن هر گره درخت G با یک شبکه فرعی مطابقت دارد. با توجه به محدودیت های طول، لطفاً برای جزئیات بیشتر در مورد G-tree به [ 28 ] مراجعه کنید.

4.4. فرآیند جستجوی آنلاین الگوریتم پایه

در مرحله پرس و جو آنلاین، کاربر query q یک مجموعه پرس و جو ارائه می دهد ( pP ، nP ، rP )، که در آن pP مجموعه ای از PPOI ها، nP مجموعه ای از NPOI ها و rP مجموعه ای از RPOI ها است. این سیستم از الگوریتم زیر برای یافتن مکان ذخیره بهینه برای q استفاده می کند.
راه حل بهینه ممکن است هر نقطه ای از هر لبه در نقشه راه باشد که مجموعه ای از راه حل های نامحدود را نشان می دهد. در زیر یک قضیه ارائه می کنیم که کمترین امتیاز مکان در لبه e در نقاط خاصی ظاهر می شود. بنابراین، ما فقط باید امتیازهای مکان این نقاط خاص را محاسبه کنیم تا راه حل بهینه را پیدا کنیم.

قضیه  1.

کمترین امتیاز مکان در لبه e باید در نقطه شکست یا راس e باشد.

اثبات

POI p و نقطه o را در نظر بگیرید که هر نقطه داده شده در لبه e است. کوتاه ترین فاصله بین p و o ، dist ( p , o )، می تواند یکی از چهار حالت بسته به سه شرط باشد، همانطور که در شکل 3 نشان داده شده است : (1) آیا o روی e است ؟ (2) آیا e در نقطه خاصی o b است به طوری که طول مسیر از p تا o b از طریق e . l برابر است با طول مسیر از p تا ob از طریق e . r (یعنی ∃ o ∈ e , dist ( p , e . l ) + dist ( e . l , o ) = dist ( p , e . r ) + dist ( e . r , o ))؟ (3) آیا همه نقاط o روی e باعث طول مسیر از p تا o از طریق e می شوند. لکمتر یا مساوی طول مسیر از p تا o از طریق e باشد. r (یعنی ∀ o ∈ e , dist ( p , e . l ) + dist ( e . l , o ) ≤ dist ( p , e . r ) + dist ( e . r , o ))؟
نمودارهای dist ( p , o ) برای هر یک از این موارد مانند شکل 4 a نشان داده شده است، که در آن محور x نشان‌دهنده کوتاه‌ترین فاصله ( e . l , o ) از راس چپ e تا o و y است. محور نشان دهنده dist ( p , o ) است. نمودارهای جاده مربوطه در شکل 4 b نشان داده شده است که در آن خط نقطه کوتاه کوتاه ترین مسیر از p تا o است. زمانی که oدر e است، dist ( p , o ) حالت 1 را نشان می دهد که یک تابع خطی تکه تکه است که در آن dist ( p , o ) برابر 0 است وقتی o p باشد. ما به o به عنوان p در نقطه شکست در e اشاره می کنیم. وقتی o روی e نیست ، dist ( p , o ) = min( dist ( p , e . l ) + dist ( e . l ,o )، dist ( p , e . r ) + dist ( e . r , o ))، و شرایط ممکن موارد 2، 3 و 4 هستند. اگر نقطه خاصی o b را بتوان در e یافت به طوری که dist ( p , e . l ) + dist ( e . l , o b ) = dist ( p , e . r ) + dist ( e .r , o b , dist ( p , o ) حالت 2 را نشان می دهد که یک تابع خطی تکه ای است. ما به o b به عنوان p در نقطه شکست در e اشاره می کنیم. اگر نقطه خاصی o را بتوان در e یافت ، dist ( p , e . l ) + dist ( e . l , o ) ≤ dist ( p , e . r ) + dist ( e. r , o , dist ( p , o ) حالت 3 را نشان می دهد که یک تابع خطی است. در غیر این صورت، dist ( p , o ) نشان دهنده مورد 4 است که همچنین یک تابع خطی است. بنابراین، dist ( p , o ) یا یک تابع خطی یا یک تابع خطی تکه ای است.
CI ( Q , p ) نمره تأثیر p است . برای مجموعه های پرس و جوی یکسان، CI ( Q ، p ) ثابت است. dist ( p , o ) × CI ( Q , p ) را می توان به عنوان یک تابع خطی یا یک تابع خطی تکه ای ضرب در یک ثابت در نظر گرفت که منجر به یک تابع خطی یا تابع خطی تکه ای می شود.
بر اساس رابطه (2)، LS ( o , pP , nP ) = ∑ p ∈ pP ∪ nP  dist ( o , p ) × CI ( Q , p ). امتیاز مکان مجموع توابع خطی چندگانه یا توابع خطی تکه ای است. بنابراین، شکل امتیاز مکان یک تابع خطی تکه‌ای است.
تابع خطی f و بازه بسته [ a , b ] را در نظر بگیرید، که در آن x هر نقطه ای در ( a ، b ) است. f ( a ) باید کمتر یا مساوی f ( x ) باشد، یا f ( b ) باید کمتر یا مساوی f ( x ) باشد، زیرا fخطی است یک تابع خطی تکه ای شامل چندین تابع خطی است. اگر بتوانیم یک تابع خطی تکه ای را به چندین تابع خطی در فواصل بسته مختلف تقسیم کنیم، حداقل مقدار تابع خطی تکه ای باید در انتهای این بازه ها قرار گیرد.
فرض کنید | pP ∪ nP | n 1 است و نقاط شکست pP ∪ nP در e { o 1 , o 2 , …, o n 2 } است. اگر i > j , پس dist ( o i , el ) ≥ dist ( o j , el ). علاوه بر این، n 2 ≤ n 1 زیرا هر POI در eفقط 0 یا 1 امتیاز شکست دارد. شکل امتیاز مکان یک تابع خطی تکه ای است. ما می‌توانیم امتیاز مکان را به چندین تابع خطی در فواصل بسته مختلف تقسیم کنیم، و انتهای این بازه‌ها { el , o 1 , o 2 , …, o n 2 , e . r }. بنابراین، نقطه با کمترین امتیاز مکان در e باید در نقاط شکست یا راس e باشد. QED
با استفاده از قضیه 1، ما فقط باید امتیاز مکان نقاط شکست و رئوس تمام یال ها را محاسبه کنیم تا جواب بهینه به دست آید. روند کامل الگوریتم خط پایه به شرح زیر است:
مرحله 1.
برای هر POI pj ، از معادله (1) و ماتریس امتیاز شباهت مشتری محاسبه شده آفلاین استفاده کنید تا امتیاز تأثیر آن CI ( Q , pj ) را ارزیابی کنید، که در آن Q توسط کاربر پرس و جو داده می شود و برابر با { pP , nP , rP است . }.
گام 2.
نقاط شکست و رئوس تمام یال ها را پیدا کنید.
مرحله 3.
امتیاز مکان تمام نقاط شکست و رئوس تمام لبه ها را محاسبه کنید و راه حل بهینه را انتخاب کنید.
نمونه ای از الگوریتم خط پایه در پیوست A ارائه شده است . □

5. الگوریتم هرس مساحت

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

5.1. کاستی های الگوریتم پایه

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

5.2. چارچوب سیستم با الگوریتم AP

برای استخراج سریع مرزهای بالایی و پایینی فاصله جاده بین POI p و هر نقطه مشخص در یک گره درخت G، اطلاعات اضافی را در گره ها ذخیره کردیم تا یک درخت G + – ایجاد کنیم . محدوده امتیازهای مکان برای تعیین اینکه آیا مکان ذخیره بهینه ممکن است در گره G + -tree وجود داشته باشد استفاده می شود. اگر نه، از بخش‌های جاده در این گره درختی G + می‌گذریم و در نتیجه سرعت الگوریتم پرس و جو را افزایش می‌دهیم. این تغییرات در شکل 5 نشان داده شده است.

5.3. G + -شاخص درخت

شاخص G + -tree از G-tree اصلاح شد. علاوه بر اطلاعات اصلی درخت G، ما سه مقدار را برای هر گره G + -tree G x بر اساس مرزهای G x محاسبه می کنیم ، یعنی low ( G x )، بالا ( G x ) و maxEdge ( G x ). ) و این مقادیر را ذخیره کنید. در زیر تعریف مرز و محاسبات این سه مقدار را معرفی می کنیم.
تعریف مرزها: با توجه به زیرگراف G x = ( Vx , Ex ) از G = ( V , E ) رأس u ∈ V x اگر ∃( u , v ) ∈ E و v ∉ V x .

Border low ( G x ): برای دست کم گرفتن فاصله جاده از هر مرز G x تا هر نقطه v در G x استفاده می شود. اگر G x یک گره برگ است، آنگاه کم ( G x ) فاصله جاده از هر مرز کوچکترین G x تا هر نقطه v در G x است. اگر G x یک گره برگ نیست، آنگاه کم ( G x ) فاصله جاده از مرز کوچکترین G است.x تا مرز زیرگره G x +1 به علاوه کم ( G x +1 ). روش محاسبه به شرح زیر است:

Border high ( G x ): برای تخمین بیش از حد فاصله جاده از هر مرز G x تا هر نقطه v در G x استفاده می شود. اگر G x یک گره برگ است، بالا ( G x ) فاصله جاده از هر مرزی از بزرگترین G x تا هر نقطه v در G x است. اگر G x یک گره برگ نیست، بالا ( G x ) فاصله جاده از مرز بزرگترین G است.x به مرز زیرگره G x +1 به علاوه بالا ( G x +1 ). روش محاسبه به شرح زیر است:

حاشیه maxEdge ( G x ): این طول طولانی ترین یال در G x است. اگر راس سمت چپ e . v l متعلق به G i است، سپس می گوییم که e متعلق به G x است. روش محاسبه به شرح زیر است:

MaxEdge ( G x ) = max e ∈ Gx e.length .

5.4. فرآیند آنلاین الگوریتم AP

الگوریتم AP از گره های غیر ضروری G + -tree برای افزایش کارایی اجتناب می کند. ما یک قضیه را استخراج کردیم تا به ما کمک کند تعیین کنیم بهترین امتیاز ممکن در گره G + -tree G i چیست . اگر این امتیاز ضعیف‌تر از بهترین امتیاز مکان فعلی باشد، می‌توانیم از G i بگذریم . این قضیه از یک LB کران پایین ( G i , p ) استفاده می کند که به صورت زیر تعریف می کنیم:

o را به عنوان هر نقطه داده شده در هر یال معین در G i در نظر بگیرید. برای POI p ، کران پایینی LB ( Gi ، p ) یک CI ( Q ، p ) × dist ( o ، p ) را تعریف می کنیم. اگر نمره تأثیر p یک عدد مثبت باشد، آنگاه LB ( Gi , p ) برابر است با امتیاز تأثیر ضرب در فاصله کم تخمین زده شده ( o , p ) . اگر نمره نفوذ ازp یک عدد منفی است، سپس LB ( Gi , p ) برابر است با امتیاز تأثیر ضرب در فاصله بیش از حد برآورد شده ( o , p ) . روش محاسبه به شرح زیر است:

در جایی که lowDist ( Gi , p ) یک عدد غیر منفی کوچکتر یا مساوی با فاصله p تا هر راس داده شده در Gi است ، highDist ( Gi , p ) یک عدد غیر منفی بزرگتر یا مساوی با فاصله از p تا هر راس داده شده در G i ، و maxEdge ( G i ) طول طولانی ترین یال در G i است.

قضیه  2.

مجموعه پرس و جو ( pP , nP , rP ) را در نظر بگیرید که در آن p یک POI در pP و nP است. مکان o هر نقطه داده شده در هر یال معین در G i است. بهترین امتیاز مکان در G i باید بزرگتر یا مساوی با مجموع همه LB(G i , p) باشد :

اثبات

لطفاً پیوست B را ببینید . □
قضیه 2 از lowDist ( G i , p ) و highDist ( G i , p ) استفاده می کند. برای محاسبه lowDist ( Gi , p ) و highDist ( Gi , p ) از G + -tree و low ( G i ) و high ( G i ) استفاده می کنیم . در زیر نمادهای مربوطه و روش های محاسبه را معرفی می کنیم. فرض کنید می‌خواهیم dist ( u , v، فاصله جاده از u تا v . leaf ( u ) و leaf ( v ) گره های G + -tree برای u و v هستند. همانطور که توسط [ 28 ] نشان داده شده است، اگر u و v به یک گره برگ G + -tree تعلق نداشته باشند ، هر مسیری از u به v باید از یک سری گره های G + -tree G x ( u )، G x عبور کند. −1 ( u )، …، G 1( u )، G 1 ( v )، G 2 ( v )، …، G x ( v )، همانطور که در شکل 6 نشان داده شده است ، که در آن G x ( u ) = برگ ( u )، G x ( v ) = برگ ( v )، و LCA ( u ، v ) پایین ترین اجداد مشترک G x ( u ) و G x ( v هستند.).
اگر u متعلق به G i باشد، lowDist ( Gi , u ) برابر با 0 است. اگر نه، همانطور که در شکل 7 نشان داده شده است ، G i را برابر با G n ( v ) قرار می دهیم ، به طوری که lowDist ( Gi , u ) برابر است . مسافت طی شده از u تا G x ( u )، G x −1 ( u )، …، G 1 ( u )، G1 ( v )، G 2 ( v )، …، G n ( v ) به علاوه کم ( G i ).

قضیه  3.

lowDist(G i ,u) باید عددی غیر منفی کوچکتر یا مساوی با فاصله u تا هر رأس داده شده در G i باشد.

اثبات

لطفاً به پیوست C مراجعه کنید . □
اگر u متعلق به G i باشد، همانطور که در شکل 8 نشان داده شده است ، G i را برابر با G n ( v ) قرار می دهیم، به طوری که highDist ( Gi , u ) مسافت طی شده از u تا G x ( u )، G x – 1 باشد. ( u )، …، G 1 ( u )، G 1 ( v )، G 2 ( v )، …،G n ( v ) به اضافه زیاد ( G i ). در غیر این صورت، همانطور که در شکل 9 نشان داده شده است ، highDist ( Gi , u ) مسافت طی شده از u تا G x ( u )، G x – 1 ( u )، …، G 1 ( u )، G i به علاوه زیاد ( G ) است. من ).

قضیه  4.

highDist(G i ,u) باید عددی غیر منفی بزرگتر یا مساوی با فاصله u تا هر راس داده شده در G i باشد.

اثبات

لطفاً به پیوست D مراجعه کنید . □
همانطور که با استفاده از درخت G برای محاسبه فاصله جاده بین دو نقطه، می‌توانیم از یک الگوریتم برنامه‌نویسی پویا برای محاسبه lowDist ( Gi , p ) و highDist ( Gi , p ) استفاده کنیم. کم ( Gi ) و زیاد ( Gi ) درگیر در محاسبات بصورت آفلاین مشتق می شوند . سپس می توانیم از lowDist ( Gi , p ) و highDist ( G i , p ) برای محاسبه استفاده کنیم .LB ( G i ، p ).

کد شبه برای الگوریتم AP در الگوریتم 1 نشان داده شده است، جایی که کاربر پرس و جو مجموعه پرس و جو را Q = { pP , nP , rP } وارد می کند.

الگوریتم 1: الگوریتم هرس مساحت
ورودی: پایگاه داده POI، ماتریس امتیاز شباهت مشتری
خروجی: مکان بهینه
1 برای هر p در مجموعه داده POI
2  ص . w ←set_impact( p ، ماتریس امتیاز شباهت مشتری)
3 پایان برای
4 برای هر گره G i در تراورس G + -tree
5  اگر قضیه 2 برآورده شود
6   هرس ( G i )
7  پایان اگر
8  if is_leaf_node ( G i )
9   نقاط شکست، رئوس←find( G i )
10   امتیازات مکان←محاسبه_نمرات (نقاط شکست، رئوس)
11   راه حل بهینه←به روز رسانی (نمرات مکان)
12  پایان اگر
13 پایان برای
14 بازگشت راه حل بهینه
مرحله 1.
برای هر POI p ، از معادله (1) و ماتریس امتیاز شباهت مشتری محاسبه شده آفلاین استفاده کنید تا امتیاز تأثیرگذاری آن CI ( Q ، p ) را ارزیابی کنید. (خطوط 1-3)
گام 2.
از G + -tree نقشه راه دیدن کنید و گره درخت بعدی G i را بازیابی کنید . (خط 4)
مرحله 3.
اگر بهترین امتیاز مکان فعلی ≤ ∑ p ∈ pP∪np LB ( G i , p ) باشد، طبق قضیه 2، می توانیم G i را هرس کرده و به مرحله 2 برگردیم. در غیر این صورت، به مرحله 4 بروید (خطوط 5- 7)
مرحله 4.
بررسی کنید که آیا G i یک گره برگ است. اگر یک گره غیر برگ است، به مرحله 2 برگردید. در غیر این صورت، نقاط شکست و رئوس تمام یال ها را در G i پیدا کنید ، امتیازات مکان این نقاط را محاسبه کنید و بهترین راه حل فعلی را به روز کنید. (خطوط 8-12)
مرحله 5.
اگر کل G + -tree بازدید شده است، سپس راه حل بهینه را برگردانید. (خطوط 13-14)
نمونه ای از الگوریتم AP در پیوست E ارائه شده است.

6. الگوریتم هرس مساحت و لبه

الگوریتم هرس ناحیه و لبه (AEP) مرحله 2.3 (همانطور که در شکل 5 نشان داده شده است ) AP را اصلاح کرد. در ادامه ابتدا به تحلیل کاستی های الگوریتم AP می پردازیم سپس به ارائه نمای کلی از الگوریتم AEP می پردازیم.

6.1. کاستی های الگوریتم AP

الگوریتم AP از گره های غیر ضروری G + -tree جلوگیری می کند و در نتیجه کارایی محاسباتی را افزایش می دهد. با این حال، هنگامی که گره برگ G + -tree G l هرس نمی شود، امتیاز مکان تمام نقاط شکست و رئوس لبه ها در Gl باید هنوز محاسبه شود. بنابراین ما یک روش هرس لبه را توسعه دادیم که از محاسبه امتیاز مکان نقاط شکست غیرضروری در لبه‌ها برای افزایش بیشتر بازده محاسباتی اجتناب می‌کند.

6.2. فرآیند آنلاین الگوریتم AEP

هنگامی که الگوریتم AP نمی تواند G + -tree node G i را هرس کند، الگوریتم AEP تعیین می کند که آیا می توان برخی از لبه های G i را هرس کرد یا خیر. ما یک قضیه را استخراج کردیم تا به ما کمک کند تعیین کنیم که آیا راه حل بهتری در نقاط شکست یک یال وجود دارد تا از محاسبه امتیاز مکان نقاط شکست غیر ضروری جلوگیری کنیم.

قضیه  5.

لبه e و مجموعه پرس و جو ( pP ، nP ، rP ) را در نظر بگیرید. ما به nP ∪ rP به عنوان POI اشاره می کنیم . ما از BP(p,e) برای نشان دادن نقطه شکست POI p در e و از BPs( POIs ,e) برای نمایش مجموعه ای از تمام p در e در POI استفاده می کنیم . بنابرین ما اینها را داریم:

که در آن عبارت قبلی بهترین امتیاز مکان در e است. دومی را می توان به عنوان کران پایین این امتیاز مکان در نظر گرفت.

اثبات

لطفاً به پیوست F مراجعه کنید . □
طبق قضیه 5، ما فقط باید فاصله ( o , p ) × CI ( Q , p ) دو راس و نقطه شکست از هر p تا e را محاسبه کنیم تا مشخص کنیم که آیا این یال می تواند هرس شود یا خیر. همانطور که در شکل 10 نشان داده شده است، فاصله ( o , p ) × CI ( Q , p ) را روی لبه e به عنوان مثال در نظر بگیرید . ما فقط باید نقاط سیاه را محاسبه کنیم: اگر e را بتوان هرس کرد، پس نقاط سفید نیازی به محاسبه نیست.
برای مجموعه پرس و جو Q = { pP , nP , rP }، رویه الگوریتم AEP به شرح زیر است:
مرحله 1.
برای هر POI p ، از معادله (1) و ماتریس امتیاز شباهت مشتری محاسبه شده آفلاین استفاده کنید تا امتیاز تأثیرگذاری آن CI ( Q ، p ) را ارزیابی کنید.
گام 2.
از G + -tree نقشه راه دیدن کنید و گره درخت بعدی G i را بازیابی کنید .
مرحله 3.
اگر بهترین امتیاز مکان فعلی ≤∑ p ∈ pP∪np LB ( G i , p ) باشد، طبق قضیه 2، می توانیم G i را هرس کرده و به مرحله 2 برگردیم. در غیر این صورت، به مرحله 4 بروید.
مرحله 4.
بررسی کنید که آیا G i یک گره برگ است. اگر یک گره غیر برگ است، به مرحله 2 برگردید. در غیر این صورت، به مرحله 5 بروید.
مرحله 5.
یال بعدی e j را در G i بازیابی کنید .
مرحله 6.
اگر امتیاز بهترین مکان فعلی ≤ ، سپس، طبق قضیه 5، e j را هرس کنید. در غیر این صورت، به مرحله 7 بروید.
مرحله 7.
نقطه شکست یا راس بعدی را در e j پیدا کنید، امتیازات مکان این نقطه را محاسبه کنید و بهترین راه حل فعلی را به روز کنید.
مرحله 8.
اگر تمام نقاط شکست و رئوس در e j در نظر گرفته شده اند، به مرحله 5 برگردید.
مرحله 9.
اگر کل G + -tree بازدید شده است، جواب بهینه را خروجی بگیرید.
نمونه ای از الگوریتم AEP در پیوست G ارائه شده است .

7. آزمایشات

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

7.1. تنظیمات پارامتر

داده‌های مورد استفاده در آزمایش‌ها شامل نقشه‌های راه، پایگاه‌های اطلاعاتی POI، نمایه‌های کاربر و داده‌های ورود بود. برای نقشه‌های راه، از سه مجموعه داده دنیای واقعی ارائه شده توسط [ 29 ] استفاده کردیم که در شکل 11 نشان داده شده‌اند . از کوچک‌ترین تا بزرگ‌ترین اندازه، سه مجموعه داده از اولدنبورگ (OL)، کالیفرنیا (CAL) و آمریکای شمالی (NA) بازیابی شدند. مجموعه داده OL شامل 6105 گره و 7035 لبه است. مجموعه داده CAL دارای 21048 گره و 21693 لبه است. مجموعه داده NA شامل 175813 گره و 179178 یال است.
از آنجایی که هیچ پایگاه داده POI، نمایه‌های کاربر، و داده‌های ورود مربوط به سه نقشه راه وجود نداشت، مجموعه داده‌های مصنوعی را به شرح زیر تولید کردیم. ابتدا 10 درصد از نقاط در نقشه راه به صورت تصادفی به عنوان POI انتخاب شدند. در مرحله بعد، گروه‌های مشتری α k برای هر POI ایجاد شد، که هر گروه شامل تعداد یکسانی از افراد بود. هر گروه مشتری دارای 10 ویژگی بود و α n از آنها به صورت تصادفی به عنوان ویژگی های مشترک انتخاب شدند. ما اجازه می‌دهیم مقادیر اینها از توزیع گاوسی بدون از دست دادن کلیت پیروی کنند. ما فرض کردیم که مقادیر سایر ویژگی ها به طور مساوی توزیع شده است. برای تولید کاربران، یک گروه مشتری را برای هر کاربر علامت گذاری کردیم تا به عنوان راه حل استاندارد برای خوشه بندی استفاده شود.
آزمایش ها در جاوا با سیستم عامل اوبونتو 16.04 64 بیتی در ساعت Intel Core i5-6400 با فرکانس 2.7 گیگاهرتز با 4 هسته و حافظه 16 گیگابایتی اجرا شد. هر آزمایش 30 بار انجام شد و نتایج به طور میانگین محاسبه شد. جدول 3تنظیمات پارامتر مورد استفاده در آزمایش‌ها را با فونت پررنگ نشان‌دهنده تنظیمات پیش‌فرض فهرست می‌کند. از آنجایی که این مقاله اولین تلاش برای استفاده از مجموعه داده های LBSN برای محاسبه تأثیر POI بر گروه مشتریان یک فروشگاه جدید را نشان می دهد، ما نتوانستیم یک مقایسه عملکرد با الگوریتم های مشابه انجام دهیم. AEP، دومین الگوریتم طراحی شده برای کاهش بار محاسباتی، حداکثر 20 ثانیه و به طور متوسط ​​کمتر از 5 ثانیه صرف نظر از شرایط نقشه و پرس و جو طول می کشد. این نتایج به خوبی در حد استانداردهای مورد انتظار است و تأیید می کند که الگوریتم به هدف مورد نظر خود دست می یابد.

7.2. آزمایش‌های مربوط به پردازش آفلاین

در این بخش، اثربخشی امتیاز شباهت مشتری را نشان می‌دهیم. ما (1) دقت روش‌های خوشه‌بندی را مقایسه می‌کنیم و (2) روش‌های مشاهده نتایج خوشه‌بندی داده‌های مختلف شبیه‌سازی را برای شناسایی تنظیمات پارامتر مناسب ( k و n ) مورد بحث قرار می‌دهیم. ما نشان می‌دهیم که وقتی k = α k و n = αn ، دو فروشگاه با درجه شباهت بیشتر بین گروه‌های مشتریان خود، امتیاز شباهت مشتری بالاتری خواهند داشت که اعتبار مفهوم را تأیید می‌کند .

7.2.1. مقایسه دقت روش خوشه بندی

ما یکی از شناخته‌شده‌ترین روش‌های خوشه‌بندی، k-means را با الگوریتم حداکثرسازی انتظار (EM) که در بخش 4 توضیح داده شد، مقایسه کردیم . مشتریان یک POI p به چندین گروه مشتری cg i تقسیم شدند . دقت خوشه‌بندی با توجه به p به عنوان تعداد مشتریان خوشه‌بندی صحیح تقسیم بر تعداد مشتریانی که p دارد تعریف شد. میانگین دقت خوشه‌بندی به عنوان میانگین میزان دقت خوشه‌بندی برای همه POIها تعریف شد.
ما داده‌های مصنوعی را برای پایگاه‌های اطلاعاتی POI، نمایه‌های کاربر و داده‌های ورود تولید کردیم. به منظور راحتی، ما مجموعه داده OL کوچکتر را برای این آزمایش انتخاب کردیم. مقادیر پیش‌فرض برای پارامترهای باقی‌مانده ( k و n ) اتخاذ شد. یعنی هر POI چهار گروه مشتری داشت که هر کدام چهار ویژگی مشترک داشتند. مشتریان هر POI با استفاده از روش‌های k -means و خوشه‌بندی EM به چهار گروه مشتری تقسیم شدند . همانطور که در شکل 12 نشان داده شده است ، میانگین دقت خوشه بندی k -means 70.83٪ و روش های خوشه بندی EM 96.73٪ بود. بنابراین ما روش‌های خوشه‌بندی EM را در آزمایش‌های بعدی اتخاذ کردیم.
7.2.2. تنظیم تعداد مناسب گروه‌های مشتری و ویژگی‌ها
در این بخش، ابزارهای شناسایی تنظیمات مناسب برای پارامترهای k و n را مورد بحث قرار می‌دهیم . با پارامترهای مناسب، یک امتیاز شباهت مشتری که به خوبی طراحی شده باشد، زمانی که درجه شباهت بیشتری بین گروه‌های مشتریان دو فروشگاه وجود داشته باشد، امتیاز بالاتری ایجاد می‌کند. مشتریان فروشگاه p را به طور تصادفی به دو گروه تقسیم کردیم و آنها را به عنوان مشتریان دو فروشگاه شبیه سازی شده p 1 و p 2 قرار دادیم . از آنجایی که آنها مشتریان یک فروشگاه بودند، امتیاز شباهت مشتری p 1 و p 2 باید تا حد امکان بالا باشد. بالاترین امتیاز ممکن برای CS (p 1 , p 2 ) تعداد مشتریانی است که p 2 دارد و بالاترین امتیاز ممکن برای CS ( p 2 , p 1 ) تعداد مشتریانی است که p 1 دارد. بنابراین ما یک امتیاز ارزیابی evalNS( p ) را به صورت ( CS ( p 1 , p 2 ) + CS ( p 2 , p 1 )) / تعداد مشتریانی که p 1 دارد به اضافه تعداد مشتریانی که p 2 دارد تنظیم می کنیمدارد.
AvgEvalNS میانگین evalNS ( p ) تمام POI p در نقشه راه است. AvgEvalNS بالاتر به این معنی است که تنظیمات پارامتر ( k و n ) برای امتیاز شباهت مشتری مناسب تر است.
هنگام تولید داده‌های مصنوعی برای پایگاه‌های اطلاعاتی POI، نمایه‌های کاربر، و داده‌های ورود، ما مجموعه داده‌های OL کوچک‌تر را برای راحتی انتخاب کردیم. مقادیر پیش‌فرض برای پارامترهای باقی‌مانده ( k ، n ، و روش خوشه‌بندی) اتخاذ شد. یعنی هر POI دارای چهار گروه مشتری بود که هر کدام دارای چهار ویژگی مشترک بودند که توسط EM دسته بندی شده بودند.
AvgEvalNS حاصل از تنظیمات پارامترهای مختلف ( k و n ) در شکل 13 ارائه شده است. در شکل 13 a، AvgEvalNS زمانی که k = 4، 5، 6 و n ≤ n 4، 5، 6 و n ≤ 4 است، به تدریج افزایش می یابد، اما زمانی که n > 4 است، به شدت کاهش می یابد . این به این دلیل است که وقتی یک گروه مشتری فقط x مشترک دارد، بیش از x ویژگی برای محاسبه امتیاز شباهت مشتری اتخاذ می کند . ویژگی‌ها باعث می‌شوند که مشخصه‌های نامربوط در محاسبات لحاظ شوند و در نتیجه مقادیر AvgEvalNS ضعیف باشد. اگر کمتر از x باشدویژگی‌ها استفاده می‌شوند، همه ویژگی‌های گنجانده شده مرتبط هستند، بنابراین مقادیر AvgEvalNS ثابت خواهند بود. با k = 2، 3، مقادیر AvgEvalNS روند فوق را نشان نمی دهند زیرا تنظیم برای k بسیار پایین است، که باعث خطاهای خوشه بندی و در نتیجه مقادیر ضعیف AvgEvalNS می شود. بنابراین، تنظیم بهینه برای k 4 است.
در شکل 13 ب، زمانی که k ≤ 4 باشد، مقادیر AvgEvalNS روند به شدت افزایشی را نشان می دهد. وقتی c > 4، مقادیر AvgEvalNS ثابت می ماند. این به این دلیل است که تقسیم مشتریان یک POI به گروه های مشتری کمتر از y باعث می شود بسیاری از مشتریانی که نباید متعلق به یک گروه باشند با هم گروه بندی شوند. خطاهای خوشه بندی بیشتر ارزش AvgEvalNS را کاهش می دهد. اگر مشتریان را به بیش از y گروه مشتری تقسیم کنیم، باعث می شود برخی از گروه های مشتری به زیر گروه های کوچکتر تقسیم شوند. با این حال، این نتایج خوشه بندی نادرست نیستند، بنابراین مقدار AvgEvalNS تفاوت زیادی نخواهد داشت. بنابراین، تنظیم kدر 4، 5، یا 6 قابل قبول است. با این حال، از آنجایی که مقدار k بیشتر هزینه های محاسباتی را افزایش می دهد (همانطور که در شکل 14 نشان داده شده است )، تنظیم بهینه برای k 4 است.
سپس از نقشه راه CAL و NA استفاده کردیم که بزرگتر از نقشه راه OL بودند. شکل 15 و شکل 16 نتایج نقشه راه CAL و شکل 17 و شکل 18 نتایج نقشه راه NA را نشان می دهد. باز هم روندهای مشابهی به دست آمد. زمان محاسبه با k و n مختلف از 52 ثانیه تا 215 ثانیه برای نقشه راه OL، از 330 ثانیه تا 916 ثانیه برای نقشه راه CAL، و از 1163 ثانیه تا 5949 ثانیه برای نقشه راه NA متغیر بود. محاسبه نقشه‌های راه بزرگ‌تر زمان بیشتری می‌برد، زیرا حاوی POI بیشتری هستند، و بنابراین، محاسبه امتیاز شباهت مشتری بیشتر طول می‌کشد.

7.3. آزمایش‌های مربوط به پرس و جو آنلاین

در این بخش، ما تأثیر سه پارامتر آزمایش (یعنی poiNum، poiCentralDegree (poiCent) و pRatio) را بر روی زمان محاسبه نشان‌داده‌شده توسط الگوریتم‌های مختلف بررسی می‌کنیم.

7.3.1. تأثیر تغییرات در poiNum

شکل 19 نتایج تجزیه و تحلیل نقشه های راه OL، CAL و NA را نشان می دهد. ما poiNum را روی 200، 400، 600، 800، و 1000 قرار دادیم. با این حال، از آنجایی که نقشه راه OL فقط شامل 610 POI است، ما poiNum را در 100، 200، 300، 400، و 500 برای این نقشه راه قرار دادیم. ما تأثیر تغییرات poiNum را بر زمان محاسبه بررسی کردیم. همانطور که در شکل 19 نشان داده شده استبا افزایش تدریجی تعداد کل PPOI و NPOI، زمان اجرای خط پایه به طور تصاعدی افزایش یافت. این به این دلیل است که تعداد بیشتر PPOI و NPOI به معنای نقاط شکست احتمالی بیشتر در هر لبه است و در نتیجه میزان محاسبات را به میزان زیادی افزایش می‌دهد. الگوریتم AP می‌تواند مناطقی را که نمی‌توانند راه‌حل‌ها را نگه دارند، هرس کند، که این امر میزان محاسبات را کاهش می‌دهد. بنابراین، زمان اجرای الگوریتم AP کندتر از الگوریتم پایه افزایش یافت. الگوریتم AEP بیشتر لبه هایی را که نمی توانند حاوی راه حل باشند، هرس می کند. بنابراین، اگرچه تعداد بیشتر PPOI و NPOI به معنای نقاط شکست احتمالی بیشتر در هر لبه است، بنابراین الگوریتم AEP می‌تواند محاسبات را با هر هرس حتی بیشتر کاهش دهد. در نتیجه، زمان اجرای الگوریتم AEP فقط اندکی افزایش یافت. در هر سه نقشه راه، نتایج آزمایش روندهای یکسانی را به غیر از افزایش زمان محاسبات مرتبط با محدوده نقشه راه ارائه کرد. بنابراین ما تنها از بزرگترین نقشه راه NA در آزمایش های باقی مانده استفاده کردیم.
7.3.2. تأثیر تغییرات در نسبت
در چارچوب مشکل در نظر گرفته شده، این احتمال وجود دارد که تعداد PPOI ها بیشتر از NPOI ها باشد. بسیاری از NPOI ها و NPOI های بیشتر از PPOI نشان می دهد که این منطقه انتخاب مناسبی برای یک فروشگاه جدید نیست. بنابراین، نسبت را 60٪، 70٪، 80٪، 90٪ و 100٪ قرار می دهیم.
نتایج زمان محاسبه برای نسبت های مختلف در شکل 20 ارائه شده است. pRatio بر زمان محاسبه مورد نیاز الگوریتم پایه تأثیری نداشت. این به این دلیل است که تعداد یکسان PPOI و NPOI در الگوریتم پایه به همان میزان محاسبات منجر می شود. هرچه تفاوت بین امتیازهای بدترین راه حل و راه حل بهینه بیشتر باشد، روند مکان راه حل بهینه آشکارتر است. ما متوجه شدیم که وقتی pRatio برابر 100٪ باشد، تفاوت بین امتیازات بدترین راه حل و بهترین راه حل 4.95 برابر اختلاف زمانی است که نسبت برابر 60٪ باشد. همانطور که در شکل 20 نشان داده شده استبا افزایش نسبت PPOI، زمان محاسبه الگوریتم AP کاهش یافت. این به این دلیل است که PPOI های بیشتر به این معنی است که روند مکان راه حل بهینه واضح تر است و مناطقی که حاوی راه حل بهینه نیستند احتمال بیشتری دارد که هرس شوند. به طور مشابه، زمان محاسبه الگوریتم AEP نیز با افزایش نسبت PPOI کاهش یافت. با این حال، از آنجایی که الگوریتم AEP لبه‌ها را به جای نواحی هرس می‌کند، و از آنجایی که واحدهای هرس کوچک‌تر باعث تخمین‌های کران دقیق‌تر می‌شوند، محاسبات بیشتری برای راه‌حل‌های بعید می‌توان کاهش داد. به طور کلی، زمان محاسبه برای همه ورودی ها کوتاه بود.
7.3.3. تأثیر تغییرات در poiCent
این آزمایش تأثیر درجه غلظت بین POIها را بر زمان محاسبه بررسی کرد. ما درجه غلظت i را به عنوان سطح گره های G + -tree تعریف کردیم که همه POI ها به آن تعلق دارند. مقدار i بیشتر به این معنی است که POI ها متمرکزتر هستند. شکل 21نتایج را نشان می دهد. درجه غلظت در بین POI ها بر زمان محاسبه الگوریتم پایه تأثیری نداشت زیرا تعداد یکسان PPOI و NPOI در مقدار محاسبات یکسانی نتیجه می دهد. با افزایش درجه غلظت، زمان محاسبه الگوریتم AP کاهش یافت (از 132 ثانیه به 48 ثانیه). این به این دلیل است که وقتی تأثیر مثبت کلی در پرس و جو بیشتر از تأثیر منفی است، راه حل بهینه باید در همان محدوده PPOI قرار گیرد. به عبارت دیگر، راه حل بهینه تنها می تواند در داخل گره ها ظاهر شود. درجه غلظت بالاتر به این معنی است که گره ها از نظر دامنه کوچکتر هستند و روند مکان راه حل بهینه واضح تر است. در نتیجه زمان محاسبه کوتاهتر می شود. به همین ترتیب، زمان محاسبه الگوریتم AEP نیز با افزایش درجه غلظت (از 7.92 ثانیه به 3.88 ثانیه) کاهش یافت. با این حال، روند کاهشی الگوریتم AEP ملایم‌تر بود زیرا زمان محاسبه الگوریتم AEP برای همه ورودی‌ها نسبتاً کوتاه بود.

7.4. مطالعه موردی

در این بخش، ما یک مطالعه موردی در دنیای واقعی را با استفاده از نقشه راه کالیفرنیا ارائه شده توسط [ 29 ] ارائه می کنیم. ما جاده های شهرستان سن دیگو را استخراج کردیم (طول جغرافیایی: -117.8 تا -116، عرض جغرافیایی: 32.4 تا 33.5). مک دونالد و مرغ سوخاری کنتاکی (KFC) دو فست فود زنجیره ای بین المللی معروف هستند. ما مکان شعب مک دونالد و KFC در شهرستان سن دیگو را از OpenStreetMap [ 30 ] استخراج کردیم و در مجموع 83 شعبه مک دونالد و 26 شعبه KFC را استخراج کردیم.
اگر مکان شعبه شناسایی شده توسط جستجوی مکان فروشگاه بهینه مبتنی بر LBSN نزدیک به یک شعبه موجود باشد، نشان می‌دهد که روش پیشنهادی تناسب خوبی با زمینه‌های دنیای واقعی دارد. به این ترتیب، ما یکی از شاخه های KFC، KFCx را برای اهداف این آزمایش ماسک کردیم. ما فرض کردیم که شعبه جدید KFC باید نزدیک به شعب مک دونالد باشد اما از سایر شعبه های KFC دور باشد. از آنجایی که مکان KFCx توسط متخصصان این حوزه انتخاب شده است، منطقه این مکان باید برای گروه مشتریان هدف KFC جذاب باشد. بنابراین ما KFCx را به عنوان یک PPOI تنظیم کردیم . به عبارت دیگر، pP این پرس و جو شامل تمام شاخه های مک دونالد به اضافه KFCx و nP است.شامل شعبه های KFC باقی مانده است. از آنجایی که هیچ داده ثبت نام یا پروفایل کاربری برای این آزمایش در دسترس نبود، امتیاز تأثیر همه شعب مک‌دونالد را 1 و امتیاز همه شعبه‌های KFC باقیمانده را -1 تنظیم کردیم. ما مقدار امتیاز تأثیر KFCx را تغییر دادیم تا تعیین کنیم که این مقدار چقدر باید باشد تا راه حل پرس و جو با شاخه موجود مطابقت داشته باشد. نتایج آزمایش در شکل 22 نشان داده شده است ، که در آن مکان هایی با امتیاز تأثیر تقریباً مشابه KFCx دایره شده اند. هرچه طرح دایره پررنگ تر باشد، مقدار آن کمتر است. ما متوجه شدیم که KFCxبا امتیاز نفوذ کمتر، بیشتر در مناطقی با شبکه های جاده ای متراکم، مانند A، B، و C ظاهر می شود. این نتایج کاربرد پرس و جوی مکان فروشگاه بهینه مبتنی بر LBSN را تأیید می کند.

8. نتیجه گیری

یافتن مکان‌های مناسب برای فروشگاه‌های جدید یک شرکت در حال رشد، یک برنامه پرس و جو فضایی رایج است. با این حال، هیچ پرس و جوی موجود هر دو PPOI و NPOI را در یک محیط شبکه جاده ای در نظر نمی گیرد. بنابراین ما یک پرس و جو جدید به نام پرس و جو مکان فروشگاه بهینه مبتنی بر LBSN را پیشنهاد کردیم. ما از داده‌های اعلام حضور و نمایه‌های کاربر از مجموعه داده‌های LBSN برای محاسبه امتیاز تأثیر هر فروشگاه در پرس و جو استفاده کردیم. سپس از این امتیاز تأثیر و فاصله جاده برای شناسایی مکان بهینه برای یک فروشگاه جدید استفاده شد. ما سه الگوریتم برای این پرس و جو طراحی کردیم. الگوریتم پایه ابتدا راه حل را از مکان های بی نهایت در شبکه راه پیدا می کند. سپس الگوریتم AP مناطقی را که هیچ شانسی برای داشتن راه حل بهینه برای کاهش فضای جستجو ندارند، هرس می کند. الگوریتم سوم بر اساس الگوریتم AP است. بخش‌های جاده‌ای را که هیچ شانسی برای داشتن راه‌حل بهینه ندارند، هرس می‌کند و کارایی را حتی بیشتر می‌کند. ما یک سری آزمایش را برای تأیید اثربخشی رویکرد پیشنهادی انجام دادیم.
در کار آینده، ما قصد داریم تا پسوندهای زیر را ایجاد کنیم: (1) روش پیشنهادی در این مقاله تنها یک راه‌حل بهینه را در یک زمان جستجو می‌کند. برای یافتن چندین راه حل بهینه، کاربر باید الگوریتم را چندین بار اجرا کند. بنابراین، ما قصد داریم مفهوم پرس و جوی top- k یا پرس و جوی خط آسمان را با رویکرد پیشنهادی ادغام کنیم. (2) این مقاله فقط تأثیرات بین POIهای موجود و فروشگاه جدید را در نظر گرفته است. با این حال، بسیاری از عوامل دیگر مانند حمل و نقل، اجاره، کاربری زمین یا مجوزها وجود دارد که با مشکل پیشنهادی مرتبط هستند. بنابراین، قصد داریم دامنه رویکرد را گسترش دهیم تا این عوامل را در بر گیرد.

پیوست A. مثالی از الگوریتم پایه

شکل A1 a یک نقشه راه با 9 نقطه و 12 لبه را نشان می دهد. مقادیر داخل پرانتز نشان دهنده طول لبه ها هستند. فرض کنید ماتریس امتیاز شباهت مشتری محاسبه شده توسط سیستم است

و کاربر پرس و جو مجموعه PPOI { p 1 , p 2 }، NPOI set { p 3 } و RPOI set { p 3 } را ارائه می دهد. مکان این POI در جدول A1 نشان داده شده است.

Ijgi 11 00314 g0a1 550
شکل A1. مثالی از الگوریتم پایه: ( الف ) شبکه جاده. ( ب ) نمودار disp ( p , o ) × CI ( Q , p ) در e 1 ; ( ج ) نمودار disp ( p , o ) × CI ( Q , p ) در e 2 .
در مرحله 1، سیستم امتیاز نفوذ POI ها را محاسبه می کند: CI ( Q , p 1 ) = (170)/1 = 170, CI ( Q , p 2 ) = (240)/1 = 240 و CI ( Q , p 3 ) = −(100)/1 = −100. بنابراین، امتیاز تأثیر p 1 ، p 2 و p 3 170، 240 و 100- است، همانطور که در جدول A1 نشان داده شده است.
در مرحله 2، سیستم نقاط شکست تمام لبه ها را محاسبه می کند. فاصله ( p , o ) e 1 همانطور که در شکل A1 b نشان داده شده است . سیستم تشخیص می دهد که رئوس e 1 v 1 و v 2 هستند و هیچ نقطه شکستی در e 1 وجود ندارد . فاصله ( p , o ) e 2 همانطور که در شکل A1 c نشان داده شده است . سیستم تشخیص می دهد که رئوس e 1 v 1 هستندو v 4 و اینکه نقاط شکست در e 1 o 2,1 , o 2,2 و o 2,3 هستند . لبه های باقی مانده به طور مشابه تجزیه و تحلیل می شوند. همه رئوس مطابق جدول A2 هستند. تمام نقاط شکست همانطور که در جدول A3 نشان داده شده است ، با o x،y نشان می دهد که p y در نقطه شکست در e x است.
در مرحله 3، سیستم امتیاز مکان تمام نقاط شکست و رئوس را محاسبه می کند. با راس v 1 به عنوان مثال، LS ( o 2,1 , pP , nP ) = 340 + 960 + (400-) = 900. با نقطه شکست o 2,1 به عنوان مثال، LS ( o 2,1 , pP , nP ) = 765 + 840 + (650-) = 955. امتیاز مکان رئوس باقیمانده و نقاط شکست به طور مشابه محاسبه می شود. جدول A4 فهرست کاملی از امتیازات مکان را نشان می دهد که در میان آنها امتیاز v 3 استپایین ترین است. بنابراین سیستم با راه حل v 3 پاسخ می دهد .

پیوست ب. اثبات قضیه A1

قضیه  A1.

مجموعه پرس و جو ( pP , nP , rP ) را در نظر بگیرید که در آن p یک POI در pP و nP است. مکان o هر نقطه داده شده در هر یال معین در G i است. بهترین امتیاز مکان در G i باید بزرگتر یا مساوی با مجموع همه LB (G i , p) باشد:

اثبات

برای اینکه ابتدا ثابت کنیم که dist ( o , p ) × CI ( Q , p ) ≥ LB ( G i , p ) ، اجازه می دهیم o متعلق به یال e باشد. این منجر به چهار مورد بسته به دو شرط می شود، همانطور که در جدول A5 نشان داده شده است : (1) آیا CI ( Q , p ) بزرگتر یا مساوی 0 است؟ (2) آیا p متعلق به G i است ؟
مورد 1. CI ( Q , p ) ≥ 0 و p به G i تعلق ندارد . این مورد را می توان بسته به دو شرط به چهار مورد فرعی تقسیم کرد. می گذاریم dist ( o , e . l ) y l و dist ( o , e . r ) y r باشد . همانطور که در جدول A6 نشان داده شده است ، دو شرط به شرح زیر است: (1) آیا y l کمتر یا مساوی با y r است.? (2) آیا نقاط شکست در e وجود دارد ؟ نمودارهای چهار فاصله ( o , p )× CI ( Q , p ) در شکل A2 ارائه شده است . محور x دور ( o ، e . l )، و محور y دور ( o ، p ) × CI ( Q ، p ) است . حداقل مقادیر موارد 1.1 و 1.3 CI ( Q , p ) × y است.l و حداقل مقادیر موارد 1.2 و 1.4 CI ( Q , p ) × y r است.
Ijgi 11 00314 g0a2 550
شکل A2. نمودارهای dist ( o , p ) × CI ( Q , p ) برای مورد 1: ( a ) مورد 1.1، ( b ) مورد 1.2، ( c ) مورد 1.3، و ( d ) مورد 1.4.
در موارد 1.1-1.4، lowDist ( Gi , p ) یک عدد غیر منفی کوچکتر یا مساوی با فاصله p تا هر رأس داده شده در G i است . بنابراین، lowDist (Gi، p ) ≤ y l ، y r ، که به این معنی است که lowDist ( Gi ، p ) ≤ dist ( o ، p ). زیرا CI ( Q , p ) ≥ 0, CI (Q , p ) × lowDist ( G i , p ) = LB ( G i , p ) ≤ CI ( Q , p ) × Dist ( o , p ).
مورد 2. CI ( Q ، p ) ≥ 0 و p متعلق به G i است. این مورد را می توان بسته به سه شرط به هشت مورد فرعی تقسیم کرد. دوباره می گذاریم dist ( o , e . l ) y l و dist ( o , e . r ) y r باشد. همانطور که در جدول A7 نشان داده شده است ، سه شرط به شرح زیر است: (1) آیا o روی e است ؟ (2) آیا نقاط شکست در e وجود دارد ؟ (3) استy l کمتر یا مساوی y r ؟
نمودارهای هشت فاصله ( o , p ) × CI ( Q , p ) همانطور که در شکل A3 نشان داده شده است . محور x دور ( o ، e . l ) و محور y dist ( o ، p ) × CI ( Q ، p ) است . حداقل مقادیر موارد 2.1 و 2.3 CI ( Q , p ) × y l است .حداقل مقادیر موارد 2.2 و 2.4 CI ( Q , p ) × y r و حداقل مقادیر موارد 2.5 و 2.6 0 است. موارد 2.7 و 2.8 وجود ندارند زیرا o نقطه شکست در e است.
Ijgi 11 00314 g0a3 550
شکل A3. نمودارهای فاصله ( o , p ) × CI ( Q , p ) برای مورد 2: ( a ) مورد 2.1، ( b ) مورد 2.2، ( c ) مورد 2.3، ( d ) مورد 2.4، ( e ) مورد 2.5، و ( و ) مورد 2.6 .
اثبات موارد 2.1-2.4 با موارد 1.1-1.4 یکسان است. در موارد 2.5-2.6، lowDist ( Gi , p ) یک عدد غیر منفی کوچکتر یا مساوی با فاصله p تا هر راس داده شده در G i است . علاوه بر این، p متعلق به G i است ، و dist ( p , p ) = 0. بنابراین lowDist ( Gi , p ) ≤ 0 ≤ dist ( o , p ). زیرا CI ( Q _p ) ≥ 0، CI ( Q ، p ) × lowDist ( G i ، p ) = LB ( Gi ، p ) ≤ CI ( Q ، p ) × dist ( o ، p ) .
مورد 3. CI ( Q , p ) < 0 و p به G i تعلق ندارد . این مورد را می توان بسته به دو شرط به چهار مورد فرعی تقسیم کرد. دوباره می گذاریم dist ( o , e . l ) y l و dist ( o , e . r ) y r باشد. همانطور که در جدول A8 نشان داده شده است ، دو شرط به شرح زیر است: (1) آیا نقاط شکست در e وجود دارد ؟ (2) آیا y l کمتر یا مساوی است ؟سال _ _
نمودارهای چهار فاصله ( o , p ) × CI ( Q , p ) همانطور که در شکل A4 ارائه شده است . محور x نشان دهنده dist ( o ، e . l )، و محور y نشان دهنده dist ( o ، p ) × CI ( Q ، p ) است. حداقل مقدار مورد 3.1 CI ( Q , p ) × y l استو حداقل مقدار مورد 3.2 CI ( Q , p ) × y r است . با حل معادلات همزمان، می‌توان نتیجه گرفت که حداقل مقادیر موارد 3.3 و 3.4 CI ( Q , p ) × (( y 1 + y 2 + e . طول )/2 است.
Ijgi 11 00314 g0a4 550
شکل A4. نمودارهای dist ( o , p ) × CI ( Q , p ) برای مورد 3: ( a ) مورد 3.1، ( b ) مورد 3.2، ( c ) مورد 3.3، و ( d ) مورد 3.4.
در مورد 3.1، highDist ( Gi , p ) یک عدد غیر منفی بزرگتر یا مساوی با فاصله p تا هر رأس داده شده در G i است . بنابراین، highDist (Gi, p ) ≥ y l ، که به این معنی است که highDist ( Gi , p ) ≥ dist ( o , p ). زیرا CI ( Q ، p ) < 0، LB ( Gi , p ) = CI ( Q , p ) × ( highDist ( G i , p ) + maxEdge ( G i )/2) ≤ CI ( Q , p ) × HighDist ( G i , p ) ≤ CI ( Q , p ) × dist ( o ، p ).
در مورد 3.2، highDist ( Gi , p ) یک عدد غیر منفی بزرگتر یا مساوی با فاصله p تا هر رأس داده شده در G i است . بنابراین، highDist (Gi, p ) ≥ y r ، به این معنی که highDist ( Gi , p ) ≥ dist ( o , p ) . زیرا CI ( Q ، p ) < 0، LB ( Gi , p ) = CI ( Q , p ) × ( highDist ( G i , p ) + maxEdge ( G i )/2) ≤ CI ( Q , p ) × HighDist ( G i , p ) ≤ CI ( Q , p ) × dist ( o ، p ).

در موارد 3.3-3.4، highDist ( Gi , p ) یک عدد غیر منفی بزرگتر یا مساوی با فاصله p تا هر راس داده شده در G i است و maxEdge ( Gi ) طول طولانی ترین یال در G است . من _ بدین ترتیب،

مورد 4. CI ( Q , p ) < 0 و p متعلق به G i است. مورد 4 را می توان بسته به سه شرط به هشت مورد فرعی تقسیم کرد. دوباره می گذاریم dist ( o , e . l ) y l و dist ( o , e . r ) y r باشد. همانطور که در جدول A9 نشان داده شده است ، سه شرط به شرح زیر است: (1) آیا o روی e است ؟ (2) آیا نقاط شکست در e وجود دارد ؟ (3) استy l کمتر یا مساوی y r ؟
نمودارهای هشت فاصله ( o , p ) × CI ( Q , p ) همانطور که در شکل A5 نشان داده شده است . محور x نشان دهنده dist ( o ، e . l )، و محور y نشان دهنده dist ( o ، p ) × CI ( Q ، p ) است. موارد 4.5 و 4.6 وجود ندارند زیرا o یک نقطه شکست در e است. اثبات موارد 4.1-4.4 با موارد 3.1-3.4 یکسان است. براهین موارد 4.7 و 4.8 با موارد 4.1 و 4.2 یکسان است.
Ijgi 11 00314 g0a5 550
شکل A5. نمودارهای فاصله ( o , p ) × CI ( Q , p ) برای مورد 4: ( a ) مورد 4.1، ( b ) مورد 4.2، ( c ) مورد 4.3، ( d ) مورد 4.4، ( e ) مورد 4.7، و ( و ) مورد 4.8 .

از طریق موارد 1-4، ما ثابت کرده ایم که dist ( o , p ) × CI ( Q , p ) ≥ LB ( Gi , p ) و از آنجایی که o هر نقطه داده شده در هر یال معین در G i است ، می توانیم استخراج کنیم که

پیوست ج. اثبات قضیه A2

قضیه  A2.

lowDist(G i ,u) باید عددی غیر منفی کوچکتر یا مساوی با فاصله u تا هر رأس داده شده در G i باشد.

اثبات

ما اثبات را با استفاده از دو حالت فرمول بندی کردیم:
  • مورد 1. u متعلق به G i است. حداقل فاصله بین هر دو نقطه 0 است زیرا lowDist ( G i , u ) = 0 ≤ 0.

  • مورد 2. u متعلق به G i نیست. همانطور که توسط [ 28 ] نشان داده شده است،

هر مسیری از u به v باید از یک سری گره های درختی G + -G x ( u )، G x -1 ( u )، …، G 1 ( u )، G 1 ( v )، G2 ( v ) عبور کند . ، …، G x ( v ). برای محاسبه فاصله جاده از u تا هر نقطه معین در G i ، از G x ( u )، G عبور می کنیمx −1 ( u )، …، G i . از آنجایی که u به G i تعلق ندارد، G i یکی از گره های بین G x ( u ) و G 1 ( u ) نیست. همانطور که در شکل 7 نشان داده شده است ، اگر G i برابر با G n ( v ) بگذاریم، سپس از همان سری گره های درخت G، G x ( u )، G x -1 ( u )، …، G 1 عبور می کنیم.( u )، …، G n ( v ). بنابراین، حداقل فاصله جاده از u تا هر نقطه معین در G i را می توان به صورت زیر بیان کرد:

که در آن مجموع سه جمله آخر باید بزرگتر یا مساوی باشد

که نشان دهنده کم ( Gn ( v ) ) است. بنابراین، می توانیم معادله (A6) را به صورت زیر بازنویسی کنیم:

سمت راست این معادله برابر با lowDist ( G i , u ) است. بنابراین، ما می توانیم آن را ثابت کنیم

□

پیوست D. اثبات قضیه A3

قضیه  A3.

highDist(G i ,u) باید عددی غیر منفی بزرگتر یا مساوی با فاصله u تا هر راس داده شده در G i باشد.

اثبات

ما اثبات را با استفاده از دو حالت فرمول بندی کردیم:
مورد 1. u متعلق به G i نیست

بر اساس شکل 8 ، مانند مورد 2 قضیه A2، اگر G i برابر با G n ( v ) بگذاریم، سپس از همان سری گره های G + -tree عبور می کنیم، G x ( u )، G x -1 ( u )، …، G 1 ( u )، …، G n ( v ). بنابراین، حداکثر فاصله جاده از u تا هر نقطه معین در G i را می توان به صورت زیر بیان کرد:

که در آن جمع چهار جمله آخر کمتر یا مساوی است

این برابر است با ( G n ( v )). در نهایت، پس از اینکه high ( Gn ( v )) را به معادله (A10) جایگزین کردیم، سمت راست معادله (A10) برابر highDist ( Gi , u ) است . بنابراین، می توانیم حداکثر v ∈ Gi dist ( u , v ) ≤ highDist ( G i , u ) را بدست آوریم.
مورد 2. u متعلق به G i است
از آنجایی که u متعلق به G i است، همانطور که در شکل 9 نشان داده شده است ، کوتاه ترین مسیر از u تا v باید از یک سری گره های درختی G + -G x ( u )، G x −1 ( u )، …، G m + عبور کند. 1 ( u )، G m +1 ( v )، …، G x ( v )، که در آن از G m ( u ) یا G m (v ) برای بیان LCA ( u ، v ). LCA ( u , v ) با v تغییر می کند و m ممکن است بین 1- x باشد. همانطور که در شکل A6 نشان داده شده است ، اجازه می دهیم مسیری از u به v به عنوان farPath ( u ، v )، که باید از G x ( u )، G x -1 ( u )، …، G 1 ( u )، G 1 عبور کند. (v )، G 2 ( v )، …، G x ( v ). طول farPath ( u ، v ) باید بزرگتر یا مساوی با shortestPath ( u ، v ) باشد. بنابراین، max v ∈ Gi dist ( u , v ) ≤ max v ∈ Gi farPath ( u , v ).
Ijgi 11 00314 g0a6 550
شکل A6. farPath ( u ، v ) و shortestPath ( u ، v ).

حداکثر فاصله جاده از u تا هر نقطه معین در G i را می توان به صورت زیر بیان کرد:

که در آن مجموع شش جمله آخر کمتر یا مساوی است

این کمتر یا مساوی با زیاد است ( G 1 ( v )). بنابراین، می توانیم معادله (A12) را به صورت زیر بازنویسی کنیم:

در نهایت، پس از اینکه معادله (A14) را با معادله (A12) جایگزین کردیم، سمت راست معادله (A12) برابر با highDist ( G i , u ) است. بنابراین، می‌توانیم معادله (A12) را به صورت max v ∈ Gi dist ( u , v ) ≤ highDist ( G i , u ) دوباره بنویسیم. □

پیوست E. مثالی از الگوریتم AP

ما از مثال ارائه شده در شکل A2 برای نشان دادن الگوریتم AP استفاده کردیم. درخت G + در شکل A7 ارائه شده است . اطلاعات اضافی در هر گره G + -tree همانطور که در جدول A10 نشان داده شده است و رئوس و یال ها در گره های G + -tree در جدول A11 نمایش داده شده اند. فرض کنید کاربر پرس و جو مجموعه PPOI { p 1 , p 2 }، NPOI set { p 3 } و RPOI set { p 3 } را وارد می کند. مکان این POI ها در نقشه راه در جدول A6 نشان داده شده است.
Ijgi 11 00314 g0a7 550
شکل A7. نمونه ای از روش الگوریتم AP.
جدول
جدول A10. اطلاعات اضافی در گره های G + -tree.
جدول
جدول A11. رئوس و لبه ها در گره های G + -tree.
در مرحله 1، سیستم امتیاز نفوذ POI ها را محاسبه می کند. فرآیند مشابه با مرحله 1 الگوریتم پایه است. در مرحله 2، سیستم شروع به بازدید از درخت G + می کند ، همانطور که در جدول A12 نشان داده شده است.
جدول
جدول A12. رویه پیمایش G + -tree.
در دور 1، ابتدا گره ریشه G 0 بازدید می شود. از آنجایی که هنوز امتیاز مکانی محاسبه نشده است، G 0 را نمی توان هرس کرد. G 0 یک گره غیر برگ است، بنابراین به مرحله 2 برمی گردیم و به بازدید از درخت G + – ادامه می دهیم .
در دور 2، G 1 بازدید می شود. از آنجایی که هنوز امتیاز مکانی محاسبه نشده است، G 1 را نمی توان هرس کرد. G 1 یک گره غیر برگ است، بنابراین به مرحله 2 برمی گردیم و به بازدید از درخت G + – ادامه می دهیم .
در دور 3، G 3 بازدید می شود. از آنجایی که هنوز امتیاز مکانی محاسبه نشده است، G 3 را نمی توان هرس کرد. G 3 یک گره برگ است، بنابراین سیستم نقاط شکست و رئوس تمام یال ها را در G 3 پیدا می کند. همانطور که در جدول A11 نشان داده شده است ، لبه های G 3 شامل e 1 ، e 2 و e 3 هستند. سیستم تمام نقاط شکست و رئوس روی e 1 , e 2 , و e 3 را پیدا می کند که شامل v 1 می شود., v 2 , v 4 , v 7 , o 2.1 , o 2.2 و o 2.3 و سپس امتیاز مکان این نقاط را محاسبه می کند. فرآیند مشابه مراحل 2 و 3 الگوریتم های پایه است. در حال حاضر، راه حل بهینه v 2 است که امتیاز مکان آن 120- است. ما به مرحله 2 برمی گردیم و به بازدید از درخت G + ادامه می دهیم .
در دور 4، G 4 بازدید می شود. همانطور که در جدول A13 نشان داده شده است . _ _ _ _ _ _ لبه های G 4 شامل e 4 , e 5 , e 6 , e 7 و e 8 می باشد . سیستم تمام نقاط شکست و رئوس این لبه ها را پیدا می کند که شامل v 2 , v 3 ,v 4 ، v 7 ، v 8 ، o 5.2 ، o 5.3 ، o 6.1 ، o 6.3 ، o 7.1 ، o 7.2 و o 8.3 . سپس امتیاز مکان این نقاط را محاسبه می کند. در حال حاضر راه حل بهینه v 3 است که امتیاز مکان آن 460- است. ما به مرحله 2 برمی گردیم و به بازدید از درخت G + ادامه می دهیم .
جدول
جدول A13. lowDist ، highDist ، و LB گره های G + -tree.
در دور 5، G 2 بازدید می شود، و ∑ p ∈ pP∪np LB ( G 2 , p = 1020 + 1440 + (-1150) = 1310 > -460؛ بنابراین، G 2 هرس می شود. کل درخت G + – بازدید شده است، بنابراین مکان بهینه برای فروشگاه جدید v 3 است.

پیوست F. اثبات قضیه A4

قضیه  A4.

لبه e و مجموعه پرس و جو ( pP ، nP ، rP ) را در نظر بگیرید. ما به nP ∪ rP به عنوان POI اشاره می کنیم . ما از BP(p,e) برای نشان دادن نقطه شکست POI p در e و از BPs( POIs ,e) برای نمایش مجموعه ای از تمام p در e در POI استفاده می کنیم . بنابرین ما اینها را داریم:

که در آن عبارت قبلی بهترین امتیاز مکان در e است. دومی را می توان به عنوان کران پایین این امتیاز مکان در نظر گرفت.

اثبات

به طور شهودی، می‌توانیم موارد زیر را درست ببینیم:

جایی که سمت راست نابرابری نیز برابر است .

در اثبات قضیه 1، نشان دادیم که dist ( o , p )× CI ( Q , p ) یک تابع خطی یا یک تابع خطی تکه ای است و حداقل مقدار آن باید در یک راس { e باشد. ل ، ای _ r } از e یا در BP ( p , e ) از p در e . بنابراین، معادله (A16) را می توان به صورت زیر بازنویسی کرد:

□

پیوست G. مثالی از الگوریتم AEP

ما الگوریتم AEP را با استفاده از مثال ارائه شده در شکل A2 نشان می دهیم . فرض کنید کاربر پرس و جو مجموعه PPOI { p 1 , p 2 }، NPOI set { p 3 } و RPOI set { p 3 } را وارد می کند. مکان این POI ها در نقشه راه در جدول A6 نشان داده شده است. جدول A14 مرزهای پایین هر لبه را نشان می دهد. اشاره می کنیم به عنوان eLB ( e ، p ) و به به عنوان eLB ( e ).
جدول
جدول A14. مرز پایین لبه ها.
روند اجرای الگوریتم AEP شبیه به الگوریتم AP است. همانطور که در جدول A15 نشان داده شده است ، تنها تفاوت ها در دورهای 3 و 4 بازدید از G + -tree رخ می دهد.
جدول
جدول A15. پیمایش G + -tree.
در دور 3، سیستم از G 3 بازدید می کند. همانطور که در جدول A15 نشان داده شده است ، لبه های G 3 شامل e 1 ، e 2 و e 3 هستند. سیستم به صورت متوالی از آنها بازدید می کند. ابتدا سیستم e 1 را بازدید می کند. از آنجایی که هنوز امتیاز مکانی محاسبه نشده است، e 1 را نمی توان هرس کرد. سیستم تمام نقاط شکست و رئوس روی e 1 را پیدا می کند که شامل v 1 و v 2 است.، و سپس امتیاز مکان این نقاط را محاسبه می کند. فرآیند مشابه مراحل 2 و 3 الگوریتم پایه است. در حال حاضر، راه حل بهینه v 2 است که امتیاز مکان آن 120- است. در مرحله بعد، سیستم از e 2 بازدید می کند. همانطور که در جدول A14 نشان داده شده است ، eLB ( e 2 ) = 340 + 720 + (650-) = 410 > -120. بنابراین، e 2 هرس می شود. در مرحله بعد، سیستم از e 3 بازدید می کند : eLB ( e 3 ) = 340 + 720 + (600-) = 460 > -120. بنابراین، e 3 هرس می شود.
در دور 4، سیستم از G 4 بازدید می کند. لبه های G 4 شامل e 4 , e 5 , e 6 , e 7 و e 8 می باشد . ابتدا سیستم e 4 را بازدید می کند. eLB ( e 4 ) = 0 + 0 + (-800) = -800 <-120، به این معنی که e 4 را نمی توان هرس کرد. سیستم تمام نقاط شکست و رئوس را در e 4 پیدا می کند که شامل v 2 و v 3 است.، و سپس امتیاز مکان این نقاط را محاسبه می کند. در حال حاضر راه حل بهینه v 3 است که امتیاز مکان آن 460- است. سیستم بعد از e 5 , e 6 , e 7 و e 8 بازدید می کند. این لبه ها به روشی مشابه هرس می شوند.

منابع

  1. ژانگ، جی. Ku، W.-S. سان، م. Qin، X. Lu, H. جستجوی مکان بهینه چند معیاره با نمودارهای voronoi همپوشانی. در مجموعه مقالات هفدهمین کنفرانس بین المللی گسترش فناوری پایگاه داده (EDBT)، ادینبورگ، بریتانیا، 29 مارس تا 1 آوریل 2014. صص 391-402. [ Google Scholar ]
  2. آروانیتیس، ا. دلیگیاناکیس، ا. Vassiliou، Y. پردازش مبتنی بر نفوذ کارآمد پرس و جوهای تحقیقات بازار. در مجموعه مقالات بیست و یکمین کنفرانس بین المللی ACM در مدیریت اطلاعات و دانش، مائوئی، HI، ایالات متحده آمریکا، 29 اکتبر تا 2 نوامبر 2012. صص 1193-1202. [ Google Scholar ]
  3. شیائو، ایکس. یائو، بی. Li, F. جستجوهای مکان بهینه در پایگاه داده های شبکه جاده ای. در مجموعه مقالات بیست و هفتمین کنفرانس بین المللی مهندسی داده IEEE 2011، واشنگتن، دی سی، ایالات متحده آمریکا، 11 تا 16 آوریل 2011. ص 804-815. [ Google Scholar ]
  4. لی، سی. یافتن k-مناسب ترین مکان ها با حداقل فاصله متوسط. پایان نامه کارشناسی ارشد، دانشگاه ملی چنگ کونگ، تاینان، تایوان، 2015. [ Google Scholar ]
  5. لین، ی. وانگ، ای تی. چیانگ، سی. چن، ALP یافتن اهداف با نزدیکترین همسایه مورد علاقه و دورترین همسایه نارضایتی توسط یک جستجوی خط افق. در مجموعه مقالات بیست و نهمین سمپوزیوم سالانه ACM در محاسبات کاربردی، Gyeongju، کره، 24-28 مارس 2014. صص 821-826. [ Google Scholar ]
  6. ساچاریدیس، دی. Deligiannakis، A. پرسش های انسجام فضایی. در مجموعه مقالات بیست و سومین کنفرانس بین المللی SIGSPATIAL در مورد پیشرفت در سیستم های اطلاعات جغرافیایی، پکن، چین، 2 تا 5 نوامبر 2015. صص 1-10. [ Google Scholar ]
  7. چی، جی. ژانگ، آر. کولیک، ال. لین، دی. Xue, Y. جستجوی انتخاب مکان کوچک. در مجموعه مقالات بیست و هشتمین کنفرانس بین المللی IEEE در سال 2012 در مهندسی داده، آرلینگتون، VA، ایالات متحده آمریکا، 2 تا 5 آوریل 2012. صص 366-377. [ Google Scholar ]
  8. سو، آی. هوانگ، ی. چانگ، ی. Shen, I. یافتن مجموع نزدیکترین مثبت و دورترین همسایگان منفی. در مجموعه مقالات کنفرانس بین المللی مهندسی اطلاعات و دانش (IKE)، لاس وگاس، NV، ایالات متحده آمریکا، 16-19 ژوئیه 2012. [ Google Scholar ]
  9. چهار مربع. در دسترس آنلاین: https://foursquare.com/ (دسترسی در 17 فوریه 2022).
  10. فیس بوک. در دسترس آنلاین: https://www.facebook.com/ (دسترسی در 17 فوریه 2022).
  11. چن، YC; هوانگ، اچ. چیو، اس ام. لی، سی. سیستم‌های توصیه شریک تبلیغاتی مشترک با استفاده از داده‌های شبکه‌های اجتماعی مبتنی بر مکان. ISPRS Int. J. Geo-Inf. 2021 ، 10 ، 57. [ Google Scholar ] [ CrossRef ]
  12. یین، دی. میترا، س. ژانگ، اچ. یادداشت پژوهشی – چه زمانی مصرف کنندگان برای نظرات مثبت در مقابل نظرات منفی ارزش قائل می شوند؟ یک بررسی تجربی سوگیری تایید در دهان به دهان آنلاین. Inf. سیستم Res. 2016 ، 27 ، 131-144. [ Google Scholar ] [ CrossRef ]
  13. کانگ، ال. لیو، اس. گونگ، دی. تانگ، ام. یک سیستم توصیه شخصی نقطه‌ای از علاقه برای تجارت O2O. الکترون. علامت. 2022 ، 31 ، 253-267. [ Google Scholar ] [ CrossRef ]
  14. چن، ز. لیو، ی. وانگ، RC; شیونگ، جی. مای، جی. طولانی، ج. الگوریتم های کارآمد برای پرس و جوهای مکان بهینه در شبکه های جاده ای. در مجموعه مقالات کنفرانس بین المللی ACM SIGMOD 2014 در مدیریت داده ها، Snowbird، UT، ایالات متحده، 22-27 ژوئن 2014. صص 123-134. [ Google Scholar ]
  15. خو، ال. مای، جی. چن، ز. لیو، ی. Dai, G. Minsum بر اساس پرس و جو مکان بهینه در شبکه های جاده ای. در مجموعه مقالات کنفرانس بین المللی سیستم های پایگاه داده برای کاربردهای پیشرفته، سوژو، چین، 27 تا 30 مارس 2017. ص 441-457. [ Google Scholar ]
  16. ژائو، جی. یانگ، اس. هوو، اچ. سان، س. Geng، X. TBTF: یک الگوریتم فاکتورسازی تانسور بایاس متغیر با زمان موثر برای سیستم توصیه‌گر. Appl. هوشمند 2021 ، 51 ، 4933-4944. [ Google Scholar ] [ CrossRef ]
  17. کوی، ال. Wang, X. چارچوب آبشاری برای حفظ حریم خصوصی سیستم توصیه‌کننده نقطه‌نظر. Electronics 2022 , 11 , 1153. [ Google Scholar ] [ CrossRef ]
  18. گلال، س. نگی، ن. الشرکاوی، ME CNMF: چارچوب کاهش اخبار جعلی مبتنی بر جامعه. اطلاعات 2021 ، 12 ، 376. [ Google Scholar ] [ CrossRef ]
  19. لی، اچ. هونگ، آر. زو، اس. Ge, Y. سیستم‌های توصیه‌گر نقطه‌ای از علاقه: دیدگاه فضایی جداگانه. در مجموعه مقالات کنفرانس بین المللی IEEE 2015 در مورد داده کاوی، آتلانتیک سیتی، نیوجرسی، ایالات متحده آمریکا، 14-17 نوامبر 2015. صص 231-240. [ Google Scholar ]
  20. بائو، جی. ژنگ، ی. Mokbel، MF توصیه مبتنی بر موقعیت و اولویت آگاه با استفاده از داده های شبکه های جغرافیایی-اجتماعی پراکنده. در مجموعه مقالات بیستمین کنفرانس بین المللی پیشرفت در سیستم های اطلاعات جغرافیایی، ردوندو بیچ، کالیفرنیا، ایالات متحده آمریکا، 6-9 نوامبر 2012. ص 199-208. [ Google Scholar ]
  21. حسیه، ح. لی، سی. Lin, S. Triprec: توصیه مسیرهای سفر از داده‌های ثبت ورود در مقیاس بزرگ. در مجموعه مقالات بیست و یکمین کنفرانس بین المللی وب جهانی، لیون، فرانسه، 16-20 آوریل 2012; صص 529-530. [ Google Scholar ]
  22. لو، ای اچ. چن، سی. Tseng، VS توصیه سفر شخصی با محدودیت‌های متعدد با استخراج رفتارهای ورود کاربر. در مجموعه مقالات بیستمین کنفرانس بین المللی پیشرفت در سیستم های اطلاعات جغرافیایی، ردوندو بیچ، کالیفرنیا، ایالات متحده آمریکا، 6-9 نوامبر 2012. ص 209-218. [ Google Scholar ]
  23. Wen، YT; چو، کی جی. پنگ، WC; یو، جی. Hwang, SW Kstr: توصیه مسیر سفر در افق آگاه از کلمه کلیدی. در مجموعه مقالات کنفرانس بین المللی IEEE 2015 در مورد داده کاوی، آتلانتیک سیتی، نیوجرسی، ایالات متحده آمریکا، 14-17 نوامبر 2015. ص 449-458. [ Google Scholar ]
  24. وانگ، ایکس. ژانگ، ی. ژانگ، دبلیو. لین، ایکس. به حداکثر رساندن تأثیر آگاه از فاصله در شبکه ژئو اجتماعی. در مجموعه مقالات سی و دومین کنفرانس بین المللی IEEE در مهندسی داده (ICDE)، هلسینکی، فنلاند، 16-20 مه 2016. صص 1-12. [ Google Scholar ]
  25. جین، ایکس. Han, J. خوشه‌بندی به حداکثر رساندن انتظار. در دایره المعارف یادگیری ماشین و داده کاوی ; Springer: برلین/هایدلبرگ، آلمان، 2017; صص 480-482. [ Google Scholar ]
  26. Jaccard, P. Étude comparative de la distribution florale dans une part des alpes et du Jura. گاو نر Soc. وود. علمی نات. 1901 ، 37 ، 547-579. [ Google Scholar ] [ CrossRef ]
  27. Endres، DM; Schindelin، JE یک معیار جدید برای توزیع احتمال. IEEE Trans. Inf. نظریه 2003 ، 49 ، 1858-1860. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
  28. ژونگ، آر. لی، جی. قهوهای مایل به زرد، KL; ژو، ال. Gong, Z. G-tree: یک شاخص کارآمد و مقیاس پذیر برای جستجوی فضایی در شبکه های جاده ای. IEEE Trans. بدانید. مهندسی داده 2015 ، 27 ، 2175-2189. [ Google Scholar ] [ CrossRef ]
  29. مجموعه داده های واقعی برای پایگاه های داده فضایی: شبکه های جاده ای و نقاط مورد علاقه. در دسترس آنلاین: https://www.cs.utah.edu/~lifeifei/SpatialDataset.htm (دسترسی در 17 فوریه 2022).
  30. پروژه OpenStreetMap. در دسترس آنلاین: https://www.openstreetmap.org/ (دسترسی در 14 ژانویه 2019).
Ijgi 11 00314 g001 550
شکل 1. مثالی برای توضیح مسئله پیشنهادی.
Ijgi 11 00314 g002 550
شکل 2. چارچوب سیستم الگوریتم خط پایه.
Ijgi 11 00314 g003 550
شکل 3. درخت تصمیم برای dist ( p , o ).
Ijgi 11 00314 g004 550
شکل 4. چهار مورد dist ( p , o ): ( a ) نمودارهای dist ( p , o ); ( ب ) نمودارهای جاده مربوطه.
Ijgi 11 00314 g005 550
شکل 5. چارچوب سیستمی الگوریتم AP.
Ijgi 11 00314 g006 550
شکل 6. گره های G + -tree از u به v عبور می کنند.
Ijgi 11 00314 g007 550
شکل 7. مورد 2 lowDist ( G i , u ).
Ijgi 11 00314 g008 550
شکل 8. مورد 1 highDist ( G i , u ).
Ijgi 11 00314 g009 550
شکل 9. مورد 2 highDist ( G i , u ).
Ijgi 11 00314 g010 550
شکل 10. مثالی از dist ( o , p ) × CI ( Q , p ) در e .
Ijgi 11 00314 g011 550
شکل 11. مجموعه داده های نقشه راه: ( الف ) اولدنبورگ، ( ب ) کالیفرنیا، ( ج ) آمریکای شمالی.
Ijgi 11 00314 g012 550
شکل 12. دقت خوشه بندی روش های مختلف خوشه بندی.
Ijgi 11 00314 g013 550
شکل 13. AvgEvalNS با ( α k = 4، α n = 4) ناشی از k , n مختلف. ( الف ) حاصل از n مختلف . ( ب ) حاصل از k مختلف .
Ijgi 11 00314 g014 550
شکل 14. زمان محاسبه برای نمرات شباهت مشتری با k , n متفاوت (α k = 4، α n = 4).
Ijgi 11 00314 g015 550
شکل 15. AvgEvalNS با ( α k = 4، α n = 4، CAL) ناشی از k ، n مختلف. ( الف ) حاصل از n مختلف . ( ب ) حاصل از k مختلف .
Ijgi 11 00314 g016 550
شکل 16. زمان محاسبه برای نمرات شباهت مشتری با ( α k = 4، α n = 4، CAL).
Ijgi 11 00314 g017 550
شکل 17. AvgEvalNS با ( α k = 4، α n = 4، NA) ناشی از k , n مختلف. ( الف ) حاصل از n مختلف . ( ب ) حاصل از k مختلف .
Ijgi 11 00314 g018 550
شکل 18. زمان محاسبه برای نمرات شباهت مشتری با ( α k = 4، α n = 4، NA).
Ijgi 11 00314 g019 550
شکل 19. زمان محاسبه برای پرس و جوها با poiNum مختلف. ( الف ) OL، ( ب ) CAL، ( ج ) NA.
Ijgi 11 00314 g020 550
شکل 20. زمان محاسبه برای پرس و جو با نسبت های مختلف.
Ijgi 11 00314 g021 550
شکل 21. زمان محاسبه برای پرس و جو با نقاط مختلف.
Ijgi 11 00314 g022 550
شکل 22. امتیاز تأثیر KFCx (اعداد داخل شکل) لازم برای مکان ذخیره بهینه شناسایی شده توسط پرس و جو رویکرد پیشنهادی، با شعبه KFC دنیای واقعی مطابقت دارد.

مقالات داخلی و بین المللی

مطالب مرتبط ...

بدون دیدگاه

دیدگاهتان را بنویسید