Yandex.Traffic पर अल्पकालिक पूर्वानुमान कैसा है

2006 में यांडेक्स पर ट्रैफ़िक की जानकारी दिखाई दी। हमने आवश्यक के साथ शुरू किया - हमने सीखा कि शहर की सड़कों की भीड़ की योजना कैसे बनाई जाए और मार्गों को बिछाने पर वर्तमान स्थिति को ध्यान में रखा जाए । इस जानकारी के लिए जाने से पहले निर्देशित किए गए मोटर यात्री, रास्ते में पहले से ही समय बचा सकते हैं:


फिर, वाहन चलाते समय ड्राइवरों की सीधे मदद करने के लिए, हमने Yandex.Maps (और, परिणामस्वरूप, Yandex.Navigator के लिए ) मोबाइल Yandex.Maps में स्वचालित पुन: रूटिंग जोड़ी। अनुप्रयोगों ने शहर में स्थिति के हर ध्यान देने योग्य परिवर्तन के लिए मार्ग को अनुकूलित करना सीखा।

डेस्कटॉप और मोबाइल पर "अब" के बारे में जानकारी एकत्र करने के बाद, हम इस सवाल के हल पर गए कि "क्या होगा?"


पहला कदम ट्रैफिक जाम का एक सांख्यिकीय मानचित्र था - इस पर आप देख सकते हैं कि शहर के औसतन सप्ताह के किसी विशेष दिन में एक घंटे में कैसे खड़े होते हैं और सवारी करते हैं। हमने मान लिया था कि "साधारण" ट्रैफिक जाम का नक्शा एक उपयोगी दुष्प्रभाव हो सकता है - निकट भविष्य में उन पर भीड़ की भविष्यवाणी करने की क्षमता। लेकिन अभ्यास से पता चला है कि औसत चित्र केवल मोटे तौर पर योजना बनाने में मदद करता है, उदाहरण के लिए, कल हवाई अड्डे की यात्रा - लेकिन यह नए ट्रैफ़िक जाम से बचने के लिए अब यात्रा करने वालों की मदद नहीं करता है। हमारे माप के अनुसार, प्रति घंटा मार्ग के अंत में भी, प्रस्थान के समय ट्रैफिक जाम की तस्वीर आमतौर पर औसत से वास्तविक के करीब होती है:



Yandex.Maps पर एक हफ्ते पहले, अगले घंटे में ट्रैफिक जाम को देखना संभव हो गया - भविष्य के मुद्दे को हल करने में हमारा अगला कदम। इस साल जो लोग अभी तक एक और सम्मेलन में नहीं आ पाए थे, आज हम आपको बताएंगे कि हमारे पूर्वानुमान के अंदर क्या है और यह कैसे निकला।

वास्तव में, कार्य

हम सड़कों के विभिन्न वर्गों पर औसत गति में बदलाव की भविष्यवाणी करते हैं। तकनीकी रूप से, एक रोड मैप एक ग्राफ है। प्रत्येक चौराहा इस ग्राफ के ऊपर है, और दो चौराहों के बीच की सड़क के किनारे किनारे हैं। उत्तरार्द्ध में एक विशेषता "लंबाई" और एक विशेषता "गति" है। लंबाई, ज़ाहिर है, पहले से ज्ञात है, और वास्तविक समय में गति की गणना की जाती है - इसके आधार पर, सड़क का भाग हरे, पीले और लाल रंग में चित्रित किया गया है। वास्तव में, हमने दूसरी विशेषता का अनुमान लगाने का उपक्रम किया।

बेशक, हमारे द्वारा इस समस्या का आविष्कार नहीं किया गया था, दुनिया भर के विभिन्न विशेषज्ञ इसमें लगे हुए हैं। रूस में, उदाहरण के लिए, इस क्षेत्र में मुख्य क्षेत्रों में से एक में एक अध्ययन गाइड के लेखक - ट्रांसपोर्ट फ्लो के गणितीय मॉडलिंग का परिचय - मॉडलिंग और पूर्वानुमान यातायात पर काम करते हैं। और यद्यपि यह विषय लंबे समय से जाना जाता है, रूसी उपयोगकर्ता अभी तक कार नेविगेशन उपलब्ध नहीं है, जो हाल के आंकड़ों के आधार पर पूर्वानुमान का उपयोग करता है। केवल दुर्लभ मामलों में, एक मार्ग का निर्माण करते समय, औसत ट्रैफ़िक आंकड़ों को ध्यान में रखा जाता है।

दुनिया में, कुछ शहरों में यातायात को स्वचालित रूप से नियंत्रित करने के लिए भीड़ के पूर्वानुमान का उपयोग किया जाता है। पहला प्रोटोटाइप जिसमें पूर्वानुमान लगाए गए थे , 1998 में यूएसए में दिखाई दिए । और "भविष्य की तलाश" प्रणाली का पहला पायलट उपयोग 2006 में सिंगापुर में शुरू हुआ ।

हमने पहली बार 2010 के इंटरनेट गणित प्रतियोगिता में पूर्वानुमान को छुआ था। उस अनुभव ने हमें यह समझने में मदद की कि कार्य कैसे निर्धारित किया जाना चाहिए और एक अच्छा परिणाम प्राप्त करने के लिए कौन से डेटा की आवश्यकता है।

डेटा स्रोत

कई देश स्थिर प्रवाह सेंसर का उपयोग करते हैं जो प्रमुख राजमार्गों पर गति और यातायात घनत्व को मापते हैं। यह यातायात भीड़ पर स्वच्छ डेटा का एक अच्छा स्रोत है, लेकिन यहां तक ​​कि अकेले मास्को को कवर करने के लिए विशाल निवेश की आवश्यकता होगी। लेकिन हम मोबाइल मैप्स और नेविगेटर के उपयोगकर्ताओं से आने वाले गुमनाम जीपीएस ट्रैक्स को पूरी तरह से प्रबंधित करते हैं। प्रत्येक ट्रैक एक विशिष्ट समय में कार के स्थान (अक्षांश और देशांतर) के बारे में संकेतों की एक श्रृंखला है। हम जीपीएस ट्रैक्स को रोड ग्राफ से जोड़ते हैं , अर्थात हम यह निर्धारित करते हैं कि वे किन सड़कों से गुजरे। फिर हम एक ही किनारों के साथ गुजरने वाली सभी पटरियों की गति को औसत करते हैं।

इस डेटा में कई विशेषताएं हैं जो गुणवत्ता पूर्वानुमान प्राप्त करना मुश्किल बनाती हैं। उपभोक्ता जीपीएस उपकरण एक त्रुटि के साथ निर्देशांक निर्धारित करते हैं, इसलिए ट्रैक बहुत "शोर" हैं। यह न केवल औसत गति की गणना को जटिल करता है, बल्कि ग्राफ़ को पटरियों की बाइंडिंग भी करता है, उदाहरण के लिए, जब सड़कें एक-दूसरे के करीब से गुजरती हैं:


इसके अलावा, कभी-कभी कुछ सड़कों पर कुछ कारें होती हैं जो डेटा संचारित करती हैं। हां, और सड़कों पर स्थिति हमेशा स्थिर नहीं होती है। उदाहरण के लिए, राजमार्गों की गलियां अलग-अलग गति से चलती हैं, इसलिए, ट्रैक एक ही खंड में एक साथ काफी अलग गति दिखा सकते हैं।

विधि चयन

इस क्षेत्र में विभिन्न तरीकों का इस्तेमाल किया जाता है। उनमें से हैं:

पैरामीट्रिक रिग्रेशन मॉडल । यह अग्रिम में एक विशिष्ट प्रकार के फ़ंक्शन को निर्धारित करता है, जो V _{भविष्य} = F ( V _अतीत , V _{वर्तमान} ) पर निर्भर करता है, और F में पैरामीटर का चयन किया जाता है। मॉडल की ख़ासियत यह है कि फ़ंक्शन का विकल्प परिणाम पर प्रतिबंध लगाता है। एक ओर, यह उन गंभीर त्रुटियों से बचाता है जो शोर डेटा का उपयोग करते समय अपरिहार्य हैं - एक पैरामीट्रिक फ़ंक्शन भविष्यवाणियों के मूल्यों के प्रसार को कम करने की अनुमति देता है। दूसरी ओर, यदि फ़ंक्शन गलत तरीके से चुना गया है, तो मॉडल व्यवस्थित रूप से गलत उत्तर दे सकता है।

नॉनपरमेट्रिक मॉडल ( "k निकटतम पड़ोसी" )। वह वर्तमान की स्थिति के समान ही अतीत में दिखती है, और पूर्वानुमान के रूप में बताती है कि आगे कैसे घटनाएँ विकसित हुईं। ऐसा एक मॉडल अधिक लचीला है - इसका उपयोग करते हुए, हम कह सकते हैं: "यदि एक तूफान के बाद 10 बार एक तूफान उत्पन्न हुआ, तो एक नई लुल्ल के बाद एक तूफान भी होगा।" यदि, उदाहरण के लिए, हम पैरामीट्रिक मॉडल में एक रेखीय कार्य करते हैं, तो हम इसकी भविष्यवाणी नहीं कर सकते, क्योंकि हम इस परिकल्पना से सीमित हैं कि भविष्य केवल अतीत का रैखिक संयोजन हो सकता है। हालांकि, "शोर" डेटा पर, रेखीय मॉडल गैर-पैरामीटर से अधिक सटीकता प्रदान करता है।

प्रतिगमन विधियों का एक और वर्गीकरण स्केलर और वेक्टर है । पहला, यह माना जाता है कि चयनित क्षेत्र की स्थिति इस बात पर निर्भर नहीं करती है कि पड़ोसी क्षेत्रों में क्या हो रहा है, और दूसरी बात, इसके विपरीत, निर्भरता को ध्यान में रखा जाता है। इसलिए गणना की मात्रा में अंतर। यदि किसी शहर में सड़कों के 10 हजार खंड हैं, तो एक स्केलर मॉडल बनाने के लिए 10 हजार मापदंडों का चयन करना पर्याप्त है। और एक वेक्टर मॉडल के लिए, आपको 100 मिलियन मापदंडों तक की आवश्यकता हो सकती है। हमारे मामले में, यह स्पष्ट है कि विभिन्न क्षेत्रों में स्थितियाँ एक दूसरे को प्रभावित करती हैं। और कुंजी यह सवाल है कि पड़ोसियों के सर्कल को कैसे सीमित किया जाए, ताकि गणना उचित समय के भीतर हो।

प्रवाह मॉडलिंग के तरीके प्रक्रिया की प्रकृति को ध्यान में रखते हैं, और न केवल अमूर्त संख्याओं पर काम करते हैं। चर चिपचिपाहट के साथ बहने वाले तरल पदार्थ के समीकरण का उपयोग किया जाता है: अधिक घनत्व - कम गति। तरीकों का व्यापक रूप से सड़क नियोजन और पूर्वानुमान के लिए वादा करने के लिए उपयोग किया जाता है, लेकिन डेटा की सटीकता और पूर्णता पर भी मांग की जाती है। वे स्ट्रीमिंग सेंसर पर अच्छी गुणवत्ता देते हैं, लेकिन लगभग "शोर" जीपीएस पटरियों पर काम नहीं करते हैं।

विभिन्न तरीकों के साथ प्रयोग करने और उनकी सटीकता और कम्प्यूटेशनल जटिलता का मूल्यांकन करने के बाद, हम लीनियर वेक्टर ऑटोरेग्रेशन पर बस गए। यह मानता है कि भविष्य की गति वर्तमान और कई क्षेत्रों में कई अतीत की गति का एक रैखिक संयोजन है: सीधे एक माना जाता है, साथ ही साथ इसके निकट।

क्या और कैसे गणना की जाती है

दिन में एक बार, हमारे मॉडल को प्रशिक्षित किया जाता है। अतीत में कुछ समय अवधि के लिए घटनाओं के विकास के आधार पर, वह एक पूर्वानुमान बनाती है। इस पूर्वानुमान की तुलना घटनाओं के बाद के विकास से की जाती है। पूर्वानुमान के बीच विसंगति को कम करने के लिए मॉडल में गुणांक का चयन किया जाता है और यह वास्तव में कैसे निकला। दिन के प्रत्येक समय के लिए, सिस्टम अपने गुणांक की गणना करता है, क्योंकि दिन के दौरान आंदोलन की प्रकृति थोड़ी भिन्न होती है। हर कुछ मिनटों में, अगले घंटे के लिए पूर्वानुमान की गणना तैयार मॉडल और ताज़ा पटरियों का उपयोग करके की जाती है।

एक मॉडल को प्रशिक्षित करते समय, डेटा की एक बड़ी मात्रा का उपयोग किया जाता है। रोड ग्राफ लगभग 100 गीगाबाइट्स पर है: यह टोपोलॉजी के बारे में जानकारी है - कौन सा किनारा किससे जुड़ा है, साथ ही साथ ज्यामिति - जीपीएस प्रत्येक सड़क खंड के शुरुआती, अंत और झुकने वाले बिंदुओं का समन्वय करता है। ट्रैक इतिहास जिसे हम स्टोर करते हैं वह दर्जनों टेराबाइट लेता है। ऐसे संस्करणों में, प्रति सप्ताह गुणांक का चयन 2 सप्ताह के लिए एकल सर्वर पर किया जाएगा। स्वीकार्य कुछ घंटों को पूरा करने के लिए, हम 30 सर्वरों के क्लस्टर का उपयोग करते हैं। लेकिन हमारे कार्य में, हम केवल सर्वर के बीच इनपुट डेटा को समान रूप से विभाजित नहीं कर सकते हैं, प्रत्येक सर्वर को उसके हिस्से में पूर्ण गणना चक्र प्रदान करते हैं, और अंतिम परिणाम एकत्र करते हैं। हमारा वितरित कंप्यूटिंग प्लेटफॉर्म मदद करता है। यह मध्यवर्ती परिणामों के संग्रह और पुनर्वितरण का ख्याल रखता है, यह स्वचालित रूप से विफल सर्वरों से काम करने वाले लोगों को भी स्थानांतरित करता है और गणना की मात्रा में वृद्धि के साथ स्केलिंग को सरल करता है।

लेकिन यहां तक ​​कि समानांतरकरण के साथ, ऐसे वॉल्यूम, निश्चित रूप से, रैम में फिट नहीं होंगे। इसलिए, हम अपने स्वयं के पुस्तकालय मेमोरी मैप्ड स्टोरेज का उपयोग करते हैं, जो एप्लिकेशन को डिस्क पर डेटा के साथ काम करने की अनुमति देता है, जैसे कि यह रैम में संग्रहीत किया गया था।

आमतौर पर, हम कई डेटा केंद्रों (DC) के बीच किसी भी डेटा प्रोसेसिंग की नकल करते हैं, ताकि उनमें से किसी में भी विफलता उपयोगकर्ता के लिए सेवा की अनुपलब्धता का कारण न बने। लेकिन मॉडल तैयार करने में, हमने जानबूझकर ऐसा नहीं किया। यदि आप कई घंटों के लिए कल के मॉडल का उपयोग करते हैं, तो पूर्वानुमान की गुणवत्ता शायद ही खराब होगी। लेकिन पूर्वानुमान खुद हमेशा ताजा होना चाहिए - सड़क पर स्थिति लगातार बदल रही है। इसलिए, यह एक दूसरे से पूरी तरह से स्वायत्त रूप से, अलग-अलग डीसी में गणनाओं के ट्रिपल दोहराव के साथ तैयार किया जाता है। यहां तक ​​कि अगर दो डीसी में एक साथ विफलता होती है, तो उपयोगकर्ता इसे नोटिस नहीं करेगा। अलग-अलग प्रतिकृतियों की गणना के परिणाम एक-दूसरे के साथ सिंक्रनाइज़ नहीं होते हैं, प्रत्येक अनुरोध के लिए तीन पूर्वानुमानों के नवीनतम को बस लिया जाता है।

हर 10 मिनट में एक नए पूर्वानुमान की गणना की जाती है। सबसे पहले, उपयोगकर्ताओं से ताजा ट्रैक संसाधित किए जाते हैं: उन्हें ग्राफ के लिए संदर्भित किया जाता है, कारों के एक सेगमेंट में यात्रा करने वालों की गति का औसत होता है, और वर्तमान दिन के लिए बनाए गए मॉडल के पूर्वानुमान की गणना की जाती है। इसमें 1-2 मिनट लगते हैं। फिर यह डेटा ट्रैफिक जाम मैप पर रेंडर करने के लिए तैयार किया जाता है। गति में अचानक परिवर्तन को सुचारू किया जाता है; प्रत्येक गति के लिए रंग को सड़कों की श्रेणी और नक्शे को देखने के पैमाने को ध्यान में रखते हुए चुना गया है। इसमें 2 मिनट लगते हैं।

गुणवत्ता का आकलन

पूर्वानुमान गुणवत्ता का एक विश्वसनीय माप अपने आप में एक दिलचस्प कार्य है। कई विधियों का अध्ययन करने के बाद, हमने निम्नलिखित को चुना।

गुणवत्ता मीट्रिक को प्रतिबिंबित करना चाहिए कि पूर्वानुमान लोगों को कितना मदद करता है। पूर्वानुमान की अनुपस्थिति में, एक घंटे में सड़क की गति की भविष्यवाणी करने की कोशिश करते हुए, हमें वर्तमान ट्रैफ़िक जानकारी का उपयोग करने के लिए मजबूर किया जाता है। यह स्पष्ट है कि एक घंटे में ट्रैफिक जाम बदल जाएगा और हमारा मूल्यांकन गलत होगा। पूर्वानुमान का उपयोग करके प्राप्त अनुमान भी आदर्श नहीं है, लेकिन यह वास्तविकता के करीब होना चाहिए। हम कितना करीब से मापने की कोशिश करेंगे।


ध्यान दें कि आप वास्तविक स्थिति के विभिन्न अनुमान लगा सकते हैं। सबसे आसान काम कस्टम पटरियों पर भरोसा करना है। इसलिए हमें 15% की रेटिंग मिली।

हालाँकि, ये डेटा स्वयं व्यवस्थित विचलन हो सकते हैं। फिर हमारी गुणवत्ता मीट्रिक इन विचलन को पुन: लागू करने वाले पूर्वानुमान को प्राथमिकता देगी। इससे बचने के लिए, हमने मूल्यांकनकर्ताओं के माप का उपयोग किया - विशेष लोग जो सेवा की गुणवत्ता को मापने में मदद करते हैं। उन्होंने उच्च परिशुद्धता जीपीएस उपकरणों के साथ कारों को सबसे महत्वपूर्ण राजमार्गों तक पहुंचाया, और पटरियों को लाया। मूल्यांकनकर्ताओं के ट्रैक के साथ पूर्वानुमान की तुलना करने पर, हमें एक और गुणवत्ता रेटिंग मिली - 12%।

अनुशंसित पढ़ना

जो कोई भी डेटा विश्लेषण के विषय में गंभीरता से रुचि रखता है, वह क्लासिक टेक्स्टबुक द एलिमेंट ऑफ स्टैटिस्टिकल लर्निंग (हस्ती, टी।, टिब्शिरानी, ​​आर।, फ्रीडमैन, जे - स्प्रिंगर) की सिफारिश कर सकता है। यहां आप हमारे अध्ययन में प्रयुक्त सभी मशीन लर्निंग विधियों के बारे में अधिक विस्तृत जानकारी प्राप्त कर सकते हैं।

रूसी में बड़ी संख्या में सामग्री साइट MachineLearning.ru पर हैं ।

परिवहन मॉडलिंग की समस्याओं का एक अच्छा परिचय ए.वी. द्वारा संपादित एक मैनुअल होगा। गैसनिकोवा "यातायात प्रवाह के गणितीय मॉडलिंग का परिचय । "

विशेषज्ञ ट्रैफ़िक पूर्वानुमान के विषय से निपटने वाली विदेशी शोध टीमों के परिणामों में रुचि लेंगे। उपलब्ध कई प्रकाशनों में से, हम कुछ पर प्रकाश डालना चाहेंगे:

• वनली मिन, लौरा विंटर, यासुओ अमेमिया - स्पेटो-टेम्पोरल सहसंबंधों के साथ सड़क यातायात भविष्यवाणी । आईबीएम के इस शोध लेख में ऑटोरेजेशन के साथ सफल अनुभवों का वर्णन करते हुए हमें ट्रैफिक जाम के पूर्वानुमान की विलेयता पर विश्वास करने में मदद की।
• आरजे गिबेंस, वाई। सैक्टी - एमआईडीए डेटा का उपयोग करके सड़क यातायात विश्लेषण: यात्रा के समय की भविष्यवाणी । कैम्ब्रिज विश्वविद्यालय में शोध दल की एक रिपोर्ट में रैखिक प्रतिगमन विधि और निकटतम पड़ोसियों की k विधि की प्रयोगात्मक तुलना शामिल है।
• वेइज़हॉंग झेंग, डेर-हॉर्ंग ली और किक्सिन शि - शॉर्ट-टर्म फ्रीवे ट्रैफिक फ्लो प्रिडिक्शन: बायेसियन कंबाइंड न्यूरल नेटवर्क एप्रोच । हमारे द्वारा वर्णित विधियों के अलावा, सड़क की स्थिति का पूर्वानुमान लगाने के कार्य के लिए कई अन्य दृष्टिकोण हैं। उदाहरण के लिए, यह आलेख तंत्रिका नेटवर्क का उपयोग करने के सफल अनुभव का वर्णन करता है।
• यांग झांग, यूंकाई लियू - नॉन-पीक ट्रैफिक फोरकास्टिंग के लिए पैरामीट्रिक और नॉनपैरेमेट्रिक तकनीकों की तुलना । यहां, कई और अधिक पैरामीट्रिक और गैरपारंपरिक पूर्वानुमान विधियों की तुलना की जाती है।