मास्को मेट्रो एक त्रि-आयामी दुनिया में कैसा दिखेगा

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

• सर्किट सुविधाजनक और याद रखने में आसान और उन्मुख होना चाहिए।
• योजना शहर के भूगोल के अनुरूप होनी चाहिए

जाहिर है, ये सिद्धांत पारस्परिक रूप से अनन्य हैं और पहले सिद्धांत के लिए भौगोलिक वास्तविकता का एक महत्वपूर्ण विरूपण आवश्यक है।

यह याद करने के लिए पर्याप्त है कि मॉस्को मेट्रो योजना सुंदर छल्ले और सीधी रेखाओं के साथ कैसी दिखती है:



और भौगोलिक रूप से सटीक योजना के साथ तुलना करें:



योजना से पता चलता है कि रिंग पूरी तरह से चिकनी और एकाग्र नहीं हैं, रेखाएं योजना की तुलना में बहुत अधिक झुकती हैं, और शहर के केंद्र में स्टेशनों का घनत्व इतना अधिक है कि योजना का पता लगाना लगभग असंभव है।

और यद्यपि दूसरी छवि वास्तविकता को अधिक सटीक रूप से दर्शाती है, यह स्पष्ट है कि मेट्रो में मार्ग की योजना बनाने के लिए पहली योजना का उपयोग करना अधिक सुविधाजनक है।

और फिर निम्नलिखित विचार मेरे दिमाग में आया: "अगर मेट्रो को एक स्टेशन से दूसरे स्टेशन पर ले जाने के लिए आवश्यक समय की आवश्यकता हो तो मेट्रो कैसी दिखेगी?" यही है, यदि आप एक स्टेशन से दूसरे स्टेशन पर जल्दी से पहुंच सकते हैं, तो स्थानिक रूप से वे आरेख पर पास में स्थित होंगे।

जाहिर है, द्वि-आयामी अंतरिक्ष में ऐसी योजना बनाना असंभव है जिसमें दो स्टेशनों के बीच की दूरी मेट्रो ग्राफ की जटिल टोपोलॉजी के कारण यात्रा के समय को एक से दूसरे तक बराबर कर देगी।

एक कूबड़ यह भी है कि उच्च आयाम वाले अंतरिक्ष में एक योजना का निर्माण करते समय यह बिल्कुल संभव है (ऊपरी अनुमान n-1 है, जहां n स्टेशनों की संख्या है)। कम संख्या वाले आयामों वाले स्थान के लिए, इस तरह की योजना का निर्माण लगभग ही किया जा सकता है।

यात्रा के समय में मेट्रो के नक्शे के निर्माण का कार्य एक विशिष्ट अनुकूलन कार्य जैसा दिखता है।
मान लें कि हमारे पास सभी स्टेशनों (एक्स, वाई, जेड) के निर्देशांक और जोड़ी वाइज टाइम (दूरी) का एक लक्ष्य मैट्रिक्स है। निर्देशांक के दिए गए सेट के "गलतता" मीट्रिक का निर्माण करना संभव है और फिर प्रत्येक स्टेशन के निर्देशांक के लिए ढाल मूल विधि द्वारा इसे कम से कम करें। मीट्रिक के रूप में, हम दूरियों के मानक विचलन का एक सरल कार्य कर सकते हैं।

ठीक है, केवल एक चीज बची हुई है, जिस पर मॉस्को मेट्रो के किसी भी स्टेशन से किसी अन्य पर यात्रा करने के लिए कितना समय खर्च किया जाना चाहिए।

पहले सोचा था कि यैंडेक्स मेट्रो एपीआई की जांच करें और इस डेटा को वहां से हटाएं। दुर्भाग्य से, एपीआई विवरण नहीं मिला। लंबे समय तक एप्लिकेशन में मैन्युअल रूप से बार देखें (मेट्रो में 268 स्टेशन हैं और समय मैट्रिक्स का आकार 268 * 268 = 71824 है)। इसलिए, मैंने यैंडेक्स मेट्रो के स्रोत डेटा को समझने का फैसला किया। चूंकि सर्वर तक कोई पहुंच नहीं है, इसलिए एप्लिकेशन के साथ एक एपीके फ़ाइल डाउनलोड की गई और आवश्यक डेटा मिला। मेट्रो के बारे में सभी जानकारी उल्लेखनीय रूप से संरचित है और एप्लिकेशन संपत्ति / मेट्रोकिट / एपीके आर्काइव फ़ोल्डर में जेएसएन प्रारूप में संग्रहीत है। सभी डेटा स्व-व्याख्यात्मक संरचनाओं में संग्रहीत हैं। Meta.json में उन शहरों के बारे में जानकारी है जिनकी योजनाएं आवेदन में मौजूद हैं, साथ ही इन योजनाओं की आईडी भी।

{ "id": "sc77792237", "name": { "en": "Nizhny Novgorod", "ru": " ", "tr": "Nizhny Novgorod", "uk": "і " }, "size": { "packed": 30300, "unpacked": 145408 }, "tags": [ "published" ], "aliases": [ "nizhny-novgorod" ], "logoUrl": "https://avatars.mds.yandex.net/get-bunker/135516/f2f0e33d8def90c56c189cfb57a8e6403b5a441c/orig", "version": "2c27fe1", "geoRegion": { "delta": { "lat": 0.168291, "lon": 0.219727 }, "center": { "lat": 56.326635, "lon": 43.992153 } }, "countryCode": "RU", "defaultAlias": "nizhny-novgorod" } 

योजना की आईडी से, हमें मॉस्को से संबंधित JSON के साथ फ़ोल्डर मिलता है।

Data.json फ़ाइल में मेट्रो ग्राफ़ के बारे में बुनियादी जानकारी होती है, जिसमें ग्राफ़ के नोड्स के नाम, नोड आईडी, नोड्स के भौगोलिक निर्देशांक, एक स्टेशन से दूसरे स्टेशन पर संक्रमण (आईडी, संक्रमण समय, संक्रमण का प्रकार - ड्राइविंग या चलना, सड़क पर या नहीं, समय की जानकारी शामिल है। हम सेकंड में रुचि रखते हैं) और स्टेशन से प्रवेश और निकास के बारे में बहुत सी अतिरिक्त जानकारी भी। यह पता लगाने के लिए काफी आसान है। हमारे सर्किट बनाने के लिए कोड लिखना शुरू करें।

हम आवश्यक पुस्तकालयों का आयात करते हैं:

 import numpy as np import json import codecs import networkx as nx import matplotlib.pyplot as plt import pandas as pd import itertools import keras import keras.backend as K from mpl_toolkits.mplot3d import Axes3D from mpl_toolkits.mplot3d.proj3d import proj_transform from matplotlib.text import Annotation import pickle 

अजगर शब्दकोशों और सूचियों की संरचना पूरी तरह से जोंस प्रारूप की संरचना के अनुरूप है, इसलिए हम मेट्रो की जानकारी पढ़ते हैं और ऐसी वस्तुओं का निर्माण करते हैं जो जोंस वस्तुओं के अनुरूप हैं।

 names = json.loads(codecs.open( "l10n.json", "r", "utf_8_sig" ).read() ) graph = json.loads(codecs.open( "data.json", "r", "utf_8_sig" ).read() ) 

हम एक ऐसा शब्दकोश बनाते हैं जो ग्राफ़ और स्टेशन के नोड्स को मैप करता है (यह आवश्यक है क्योंकि स्टेशनों को नामों के लिए असाइन किया गया है, न कि ग्राफ़ के नोड्स)

साथ ही, केवल मामले में, हम एक भौगोलिक मानचित्र के निर्माण की संभावना के लिए नोड्स के निर्देशांक को बचाएंगे (0-1 की सीमा तक सामान्यीकृत)

 nodeStdict={} for stop in graph['stops']['items']: nodeStdict[stop['nodeId']]=stop['stationId'] coordDict={} for node in graph['nodes']['items']: coordDict[node['id']]=(node['attributes']['geoPoint']['lon'],node['attributes']['geoPoint']['lat']) lats=[] longs=[] for value in coordDict.values(): lats.append(value[1]) longs.append(value[0]) for k,v in coordDict.items(): coordDict[k]=((v[0]-np.min(longs))/(np.max(longs)-np.min(longs)),(v[1]-np.min(lats))/(np.max(lats)-np.min(lats))) 

कनेक्शन के साथ एक मेट्रो ग्राफ बनाएं। हम प्रत्येक कनेक्शन का वजन निर्धारित करते हैं। वजन यात्रा समय से मेल खाती है। हम उन नोड्स को हटा देंगे जो स्टेशन नहीं हैं (मेरी राय में, ये मेट्रो से बाहर निकलते हैं और समय की गणना करते समय यैंडेक्स कार्ड के लिए उन्हें कनेक्शन की आवश्यकता होती है, लेकिन यह बिल्कुल समझ में नहीं आया), एक नोड आईडी शब्दकोश बनाएं - रूसी में वास्तविक नाम

 G=nx.Graph() for node in graph['nodes']['items']: G.add_node(node['id']) #graph['links'] for link in graph['links']['items']: #G.add_edges_from([(link['fromNodeId'],link['toNodeId'])]) G.add_edge(link['fromNodeId'], link['toNodeId'], length=link['attributes']['time']) nodestoremove=[] for node in G.nodes(): if len(G.edges(node))<2: nodestoremove.append(node) for node in nodestoremove: G.remove_node(node) labels={} for node in G.nodes(): try: labels[node]=names['keysets']['generated'][nodeStdict[node]+'-name']['ru'] except: labels[node]='error' 

हम परिभाषित करते हैं कि प्रत्येक नोड किस शाखा (किस शाखा आईडी) से संबंधित है (इसे बाद में आरेख में मेट्रो लाइनों को रंगने के लिए आवश्यक होगा)

 def getlines(graph, G): nodetoline={} id_from={} id_to={} for lk in graph['tracks']['items']: id_from[lk['id']]=lk['fromNodeId'] id_to[lk['id']]=lk['toNodeId'] for line in graph['linesToTracks']['items']: if line['trackId'] in id_from.keys(): nodetoline[id_from[line['trackId']]]=line['lineId'] nodetoline[id_to[line['trackId']]]=line['lineId'] return nodetoline lines=getlines(graph,G) 

नेटवर्कएक्स लाइब्रेरी आपको nx.shortest_path_length (जी, आईडी 1, आईडी 2, वजन = 'लंबाई') फ़ंक्शन का उपयोग करके एक नोड से दूसरे तक सबसे छोटी पथ लंबाई खोजने की अनुमति देती है, इसलिए हम मान सकते हैं कि हमने डेटा तैयारी पूरी कर ली है। अगली बात यह है कि एक मॉडल तैयार करना है जो स्टेशनों के निर्देशांक को अनुकूलित करेगा।

ऐसा करने के लिए, हम यह पता लगाएंगे कि इनपुट को आउटपुट के लिए क्या दिया जाएगा, और हम स्टेशन समन्वय मैट्रिक्स को कैसे अनुकूलित करेंगे।

मान लीजिए हमारे पास सभी निर्देशांक (3x268) का एक मैट्रिक्स है। इस समन्वय मैट्रिक्स द्वारा आयाम 268 के स्थान पर वन-हॉट वेक्टर (एक वेक्टर जहां 0 हर जगह n की समन्वित इकाई को छोड़कर) है, को गुणा करना, स्टेशन n के अनुरूप 3 निर्देशांक देगा। यदि हम एक-गर्म वैक्टर की एक जोड़ी लेते हैं और उन्हें आवश्यक मैट्रिक्स द्वारा गुणा करते हैं, तो हमें निर्देशांक के दो त्रिभुज मिलते हैं। निर्देशांक की एक जोड़ी से आप स्टेशनों के बीच यूक्लिडियन दूरी की गणना कर सकते हैं। इस प्रकार, हम अपने मॉडल की वास्तुकला निर्धारित कर सकते हैं:



प्रवेश द्वार पर हम कुछ स्टेशनों को देते हैं, आउटपुट पर हम उनके बीच की दूरी प्राप्त करते हैं।

जब हमने मॉडल को प्रशिक्षित करने के लिए डेटा प्रारूप पर निर्णय लिया है, तो हम ग्राफ पर दूरी खोज का उपयोग करके डेटा तैयार करेंगे:

 myIDs=list(G.nodes()) listofinputs1=[] listofinputs2=[] listofoutputs=[] for pair in itertools.product(G.nodes(), repeat=2): vec1=np.zeros((len(myIDs))) vec2=np.zeros((len(myIDs))) vec1[myIDs.index(pair[0])]=1 vec2[myIDs.index(pair[1])]=1 listofinputs1.append(vec1) listofinputs2.append(vec2) #listofinputs.append([vec1,vec2]) listofoutputs.append(nx.shortest_path_length(G, pair[0], pair[1], weight='length')/3600) #myDistMatrix[myIDs.index(pair[0]),myIDs.index(pair[1])]=nx.shortest_path_length(G, pair[0], pair[1], weight='length') 

हम ढाल वंश विधि का उपयोग करके स्टेशन समन्वय मैट्रिक्स का अनुकूलन करते हैं।

अगर हम मशीन लर्निंग के लिए केरस फ्रेमवर्क का उपयोग करते हैं, तो हमें निम्नलिखित मिलते हैं:

 np.random.seed(0) initweightmatrix=np.zeros((len(myIDs),3)) for i in range(len(myIDs)): initweightmatrix[i,:2]=coordDict[myIDs[i]] initweightmatrix[i,2]=np.random.randn()*0.001 def euclidean_distance(vects): x, y = vects sum_square = K.sum(K.square(x - y), axis=1, keepdims=True) return K.sqrt(K.maximum(sum_square, K.epsilon())) def eucl_dist_output_shape(shapes): shape1, shape2 = shapes return (shape1[0], 1) inp1=keras.layers.Input((len(myIDs),)) inp2=keras.layers.Input((len(myIDs),)) layer1=keras.layers.Dense(3,use_bias=None, activation=None) x1=layer1(inp1) x2=layer1(inp2) x=keras.layers.Lambda(euclidean_distance, output_shape=eucl_dist_output_shape)([x1, x2]) out=keras.layers.Dense(1,use_bias=None,activation=None)(x) model=keras.Model(inputs=[inp1,inp2],outputs=out) model.layers[2].set_weights([initweightmatrix]) model.layers[2].trainable=False model.compile(optimizer=keras.optimizers.Adam(lr=0.01), loss='mse') 

ध्यान दें कि हम वास्तविक भौगोलिक निर्देशांक का उपयोग लेयर 1 में प्रारंभिक निर्देशांक के रूप में करते हैं - यह मानक विचलन समारोह के स्थानीय न्यूनतम में न आने के लिए आवश्यक है। हम एक गैर-शून्य ग्रेडिएंट प्राप्त करने के लिए एक गैर-शून्य वाले तीसरे को समन्वित करते हैं (यदि शुरुआत में नक्शा बिल्कुल सपाट है, तो किसी भी स्टेशन के ऊपर या नीचे की शिफ्ट समान होगी, इसलिए ग्रेडिएंट 0 है और z को अनुकूलित नहीं किया जाएगा)। हमारे मॉडल का अंतिम तत्व (डेंस (1)) टाइमलाइन को फिट करने के लिए स्कीम के स्केलिंग को प्रभावित करता है।

हम दूरी को घंटों में मापेंगे, सेकंड नहीं, क्योंकि दूरी के आदेश लगभग 1 घंटे हैं, और मॉडल के अधिक प्रभावी प्रशिक्षण के लिए यह महत्वपूर्ण है कि सभी मान (इनपुट डेटा, भार, लक्ष्य) परिमाण के लगभग एक ही क्रम हैं। यदि ये मान 1 के करीब हैं, तो आप अनुकूलन के लिए मानक चरण मान (0.001-0.01) का उपयोग कर सकते हैं।

लाइन मॉडल.लेयर [2] .trainable = गलत स्टेशनों के निर्देशांक को जमा देता है और पहले चरण में एक पैरामीटर विविध है - पैमाना। हमारी योजना के पैमाने का चयन करने के बाद, हम निर्देशांक को अनफ्रीज करते हैं और पहले से ही उनका अनुकूलन करते हैं:

 hist=model.fit([listofinputs1,listofinputs2],listofoutputs,batch_size=71824,epochs=200) model.layers[2].trainable=True model.layers[-1].trainable=False model.compile(optimizer=keras.optimizers.Adam(lr=0.01), loss='mse') hist2=model.fit([listofinputs1,listofinputs2],listofoutputs,batch_size=71824,epochs=200) 

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

लेकिन देखते हैं कि हमारा सर्किट कैसा दिखता है!

स्टेशनों के निर्देशांक प्राप्त करें, लाइनों का रंग कोडिंग लें और हस्ताक्षर के साथ एक 3 डी छवि बनाएं (हस्ताक्षर के एक सुंदर प्रदर्शन के लिए कोड यहां से लिया गया है ):

 class Annotation3D(Annotation): '''Annotate the point xyz with text s''' def __init__(self, s, xyz, *args, **kwargs): Annotation.__init__(self,s, xy=(0,0), *args, **kwargs) self._verts3d = xyz def draw(self, renderer): xs3d, ys3d, zs3d = self._verts3d xs, ys, zs = proj_transform(xs3d, ys3d, zs3d, renderer.M) self.xy=(xs,ys) Annotation.draw(self, renderer) def annotate3D(ax, s, *args, **kwargs): '''add anotation text s to to Axes3d ax''' tag = Annotation3D(s, *args, **kwargs) ax.add_artist(tag) fincoords=model.layers[2].get_weights() ccode={} for obj in graph['services']['items']: ccode[obj['id']]=('\#'+obj['attributes']['color'])[1:] xn = fincoords[0][:,0] yn = fincoords[0][:,1] zn = fincoords[0][:,2] l=[labels[idi] for idi in myIDs] colors=[ccode[lines[idi]] for idi in myIDs] xyzn = zip(xn, yn, zn) fig = plt.figure() ax = fig.gca(projection='3d') ax.scatter(xn,yn,zn, c=colors, marker='o') for j, xyz_ in enumerate(xyzn): annotate3D(ax, s=labels[myIDs[j]], xyz=xyz_, fontsize=9, xytext=(-3,3), textcoords='offset points', ha='right',va='bottom') plt.show() 

चूंकि ब्राउज़र के लिए एक इंटरैक्टिव 3 डी प्रारूप में परिवर्तित करने में कठिनाइयाँ थीं, इसलिए मैं gif पोस्ट करता हूं:



पाठ के बिना संस्करण अधिक सुंदर और पहचानने योग्य लगता है:

 xn = fincoords[0][:,0] yn = fincoords[0][:,1] zn = fincoords[0][:,2] l=[labels[idi] for idi in myIDs] colors=[ccode[lines[idi]] for idi in myIDs] xyzn = zip(xn, yn, zn) fig = plt.figure() ax = fig.gca(projection='3d') ax.scatter(xn,yn,zn, c=colors, marker='o') plt.show() 

UPD: वांछित रंग की मेट्रो लाइनें जोड़ें और एक gif बनाएं। काली रेखाएँ - स्टेशनों के बीच संक्रमण:

 myedges=[(myIDs.index(edge[0]),myIDs.index(edge[1]))for edge in G.edges] xn = fincoords[0][:,0] yn = fincoords[0][:,1] zn = fincoords[0][:,2] l=[labels[idi] for idi in myIDs] c=[ccode[lines[idi]] for idi in myIDs] fig = plt.figure() ax = fig.gca(projection='3d') ax.scatter(x,y,z, c=c, marker='o',s=25) for edge in myedges: col='black' if c[edge[0]]==c[edge[1]]: col=c[edge[0]] ax.plot3D([x[edge[0]], x[edge[1]]], [y[edge[0]], y[edge[1]]], [z[edge[0]], z[edge[1]]], col) ims = [] def rotate(angle): ax.view_init(azim=angle) rot_animation = animation.FuncAnimation(fig, rotate, frames=np.arange(0, 362, 3), interval=70) rot_animation.save('rotation2.gif', dpi=80, writer=matplotlib.animation.PillowWriter(80)) 

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

PS 3D आवश्यक नहीं है, 2D संस्करण के लिए यह कोड को थोड़ा ठीक करने के लिए पर्याप्त है। लेकिन 2 डी योजना के मामले में, दूरी की इतनी सटीकता हासिल करना असंभव है।