بخشی از مقاله
چکیده
تحلیل دادههای خطسیر اشیاء متحرک و استخراج الگوهای حرکتی آنها با استفاده از روشهای دادهکاوی، در سال های اخیر مورد توجه محققان قرارگرفته است. در بسیاری از برنامههای مدیریت اشیاء متحرک، تحلیل خوشهبندی دادهها، به یکی از نیازهای اساسی تبدیل شده است. خوشهبندی یکی از مهمترین روش های تحلیل است که داده های مشابه را برای تهیه خلاصه ای از الگوهای توزیع داده در یک مجموعهداده، گروهبندی میکند. در این مقاله پس از بررسی الگوریتم های موجود برای خوشهبندی خطسیرها در فضایی که اشیاء متحرک آزادی حرکت دارند، یکی از شاخص ترین الگوریتم ها در این زمینه با نام Traclus انتخاب شد. این الگوریتم مبتنی بر چارچوب پارتیشن و گروهبندی است.
در این الگوریتم برای خوشهبندی زیر خطسیرها تنها طول و عرض جغرافیایی نقاط خطسیرها مدنظر قرارداده میشود بنابراین این الگوریتم تنها میتواند نقاط پرتراکم را شناسایی کند مستقل از اینکه آن مناطق در چه زمانهایی پرتراکم بودهاند. این در حالیست که در بسیاری از کاربردها نیاز است مشخص شود چه مناطقی در چه زمان هایی پرتراکم بودهاند. از این رو با در نظر گرفتن ویژگی زمان نقاط خط سیرها، این الگوریتم را توسعه داده و الگوریتم خود را با نام T-Traclus ارائه کردهایم. مزیت این روش نسبت به روش موجود قابلیت تشخیص مناطق پرتراکم در زمانهای مشابه است.
مقدمه
با توجه به پیشرفتهای سریع در زمینه فناوری موقعیت یابی و بیسیم، امروزه با گروه وسیعی از اطلاعات مکانی مواجه هستیم و امکان جمع آوری اطلاعات مکانی تولید شده توسط کاربران موبایل، خودروها، اتوبوسها، هواپیماها، حیوانات و دیگر اشیاء متحرک نیز فرآهم است. GPS، حسگرها، سیستم های نظارت تصویری و اینترنت همگی اغلب بیش از پیش برای ثبت موجودیت های متحرک استفاده می شوند؛ این حرکت موجودیتها که نمونه به نمونه ثبت می شود، می توانند به یکدیگر در قالب یک توالی، به عنوان یک خط سیر متصل شوند - L. Bermingham and I. Lee, . - 2015 ازدیاد اطلاعات مکانی همراه با افزایش تعداد وسایل نقلیه موتوری - افزایش سالانه 3.69 میلیون از سال - 1960 - X. Meng et al, 2014 - ، نیاز به تکنیکهای کارآمد برای تحلیل و مدیریت اطلاعات مکانی را افزایش داده است.
بنابراین، با توجه به اینکه مجموعه داده های اشیاء متحرک دارای حجم و پیچیدگی زیادی هستند، تکنیک های تحلیل بصری و الگوریتم های داده کاوی موثر و کارآمد برای استخراج اطلاعات مفید و کشف الگوها از این مجموعه داده های حجیم حرکتی، مورد نیاز است. در واقع فراوانی داده های خط سیر یک فرصت ارزشمند برای صنعت و جامعه علمی برای استخراج الگوهای از پیش ناشناخته و الگوهای روشن از حرکت موجودیت ها ایجاد میکند. رشتههای علمی مختلف شامل تحقیق درباره پایگاهدادهها، تحلیل حمل و نقل، سیستم های کنترل پرواز و تحقیق درباره رفتار مهاجرت حیوانات، تمایل زیادی برای بررسی الگوهای حرکت اشیاء متحرک از خود نشان دادهاند.
همچنین در سرویس های مبتنی بر مکان دانستن مکانهایی که بسیار پرتردد هستند حائز اهمیت است و می تواند در سیاستهای بازاریابی بسیار کمک کند . - X. Meng et al, 2014 - مطابق با بررسی های صورت گرفته می توان داده های فضایی - زمانی مربوط به اشیاء متحرک را بر اساس نوع حرکت آنها به دو دسته کلی تقسیم کرد: خط سیر حرکت اشیایی که در شبکه جاده ای حرکت می کنند و خطسیر حرکت اشیایی که در فضایی با آزادی حرکت سیر می کنند. پس از نگاهی اجمالی به روشهای هر یک از این دو حوزه، خوشهبندی دادههای فضایی - زمانی مربوط به حرکت اشیاء متحرک در فضایی با آزادی حرکت را به عنوان زمینه کار خود انتخاب کردیم. از اینرو به بررسی الگوریتمهای موجود برای خوشهبندی خط سیرها در فضایی که اشیاء متحرک آزادی حرکت دارند پرداختیم.
یکی از الگوریتم های برجسته در این حوزه Traclus است. به دلیل اهمیت در نظر گرفتن مکان و زمان خط سیر حرکت اشیاء متحرک بصورت همزمان، در این مقاله با در نظر گرفتن پارامترهای مکان و زمان خطسیرها، به خوشهبندی آنها بر اساس توسعه الگوریتم Traclus میپردازیم. خوشهبندی زیر خطسیرها با در نظر گرفتن اطلاعات مکان و زمان به ما این امکان را میدهد که مناطق پرتردد بر اساس زمان را شناسایی کنیم. در ادامه، در بخش دوم مروری بر پیشینه تحقیق شده است. در بخش سوم تعاریف مربوط به مفاهیم مرتبط با خوشهبندی دادههای خط سیر ارائه می شود. در بخش چهارم روش پیشنهادی ارائه شده است. بخش پنجم به ارزیابی روش پیشنهادی اختصاص دارد. در بخش ششم به نتیجهگیری و پیشنهادات پژوهشهای آتی پرداخته شده است.
پیشینه تحقیق
در سالهای اخیر، تحقیقات زیادی بر روی خوشهبندی اشیاء متحرک صورت گرفته است، که دارای کاربردهای مختلفی هستند. در بسیاری از موارد، اشیاء در شبکه هایی با فضای محدود حرکت می کنند. در زمینه خوشهبندی اشیاء متحرک در شبکه جادهای می توان به یک چارچوب یکپارچه ارائه شده برای خوشهبندی اشیاء متحرک در شبکههای فضایی - CMON - اشاره کرد. چارچوب CMON بر اساس مفهوم بلوک خوشه - clustering block - کار میکند.
این چارچوب بر اساس سه معیار مبتنی بر فاصله، تراکم و پارتیشنبندی K تایی - K-partitioning - ، توسعه یافته است - X. .Meng et al, 2014 - الگوریتم NEAT و FlowScan نیز برای خوشهبندی خطسیر اشیاء متحرک در شبکه های جادهای ارائه شده است. Binh Han و همکارانش به ارائه NEAT به عنوان یک رویکرد آگاه شبکه جاده ای، برای خوشهبندی سریع و مؤثر خطسیرهای فضایی مربوط به اشیا در حال جابجایی در شبکه های جادهای، پرداختند - B. Han - et al, 2012 آنها استدلال کردهاند هنگامی که هدف، کاربرد خوشهبندی فضایی خط سیر اشیاء متحرک در کاربردهای مبتنی بر مکان شبکه های آگاه از مسیر است، تراکم و فاصله اقلیدسی دیگر معیارهای سنجش موثری نیستند.
به این دلیل که جریان ترافیک در شبکه جادهای و خصوصیات تراکم مبتنی بر جریان به فاکتورهای مهمی برای یافتن خوشههای خطسیر اشیاء متحرک در حال مسافرت در یک شبکه راه تبدیل شدهاند. روش آنها محدودیتهای فیزیکی شبکه جادهای، مجاورت شبکه و جریان ترافیک میان بخش های جادهای متوالی را با هدف سازماندهی خط سیرها، در خوشههای فضایی مدنظر قرار داده است. در الگوریتم FlowScan مسیرهای پر تردد در شبکه جادهای را پیدا می کند . - Y.Zheng and X.Zhou, 2011 - این الگوریتم به جای خوشهبندی اشیاء متحرک، بخش های جاده براساس تراکم ترافیک مشترک در آنها، خوشهبندی میشوند.
بسیاری از تحقیقات کنونی درباره خوشهبندی اشیاء متحرک، یک فضای حرکت آزاد را فرض نمودهاند، مانند حرکت حیوانات و توده های آب و هوایی. Genoliniو همکارانش با تمرکز بر متغیرهایی که مکرراً اندازه گیری شدهاند، ایده جدیدی درباره تکامل مشترک از چندین متغیر ارائه شده و به این نتیجه رسیده است که مطالعه اشتراکی به مراتب معنی دارتر است . - C.Genolini et al, 2013 - در مقالات - C.Genolini et al, 2013 - و - O.Ossama et al, 2011 - الگوریتم k-MEANS برای پیدا کردن خوشه و خط سیرهای مشترک استفاده شده است. این روش مقادیر از دست رفته را مدیریت کرده و همچنین تعدادی معیار کیفی برای پیدا کردن پارتیشنهای بهتر ارائه کردهاند.
Chu و همکارانش از FCM - Fuzzy c-means - در خطسیر جابجایی طوفان و مقایسه آن با خوشهبندی، نرمالسازی تکنیک های برش و الگوریتم k-means استفاده کردهاند Karavasilis . - H.J.Chu et al, 2012 - و همکارانش الگوریتمی ارائه کردهاند که خطسیرها را از توالی عکس ها، بر اساس مدل خوشه استخراج می کند . - V.Karavasilis et al, 2012 - این مدل ترکیبی، رگرسیون برای خطسیرهای خوشه با طول متغیر است. پارامترها در این مدل با استفاده از الگوریتم حداکثر انتظار، انتخاب می شوند. برخی الگوریتمهای موجود برای خوشهبندی خط سیرها روی ویژگیهای هندسی و فضایی آنها تمرکز دارند. برخلاف بسیاری از الگوریتم های خوشهبندی موجود، Debnath و همکارانش یک چارچوب جدید برای خوشهبندی زیر خطسیرها بر اساس ترکیب مشخصات فضایی و غیرفضایی ارائه کردهاند.
