NLP第二課（搜索）
- 2019 年 10 月 5 日
- 筆記
最近壓力太大了，持續性修改0注釋的程式碼，變數為阿拉伯數字的程式碼，壓力山大，擺正心態，沒有那些bug，還需要我們來做些什麼呢？如果一個特別出色的項目，也體現不出來你個人的出色。幾句牢騷，我們今天來繼續說下NLP。
我們先來拋出一個問題，我們要坐地跌，從西直門站到蘇州街站，我們在北京的小夥伴都知道，坐4號線，然後在海淀黃庄換成10號線就到了，或者我們直接打開導航，搜一下就可以了。說起來很簡單，想起來也很簡單，但是做起來不是那麼簡單了。我們現有所有線路的站點，以及換成車站的數據（爬取過程略去）。我們現有的數據是這樣的：
1號線：
蘋果園-古城-八角遊樂園-八寶山-玉泉路-五棵松-萬壽路-公主墳-軍事博物館-木樨地-南禮士路-復興門-西單-天安門西-天安門東-王府井-東單-建國門-永安里-國貿-大望路-四惠-四惠東
2號線：
西直門-積水潭-鼓樓大街-安定門-雍和宮-東直門-東四十條-朝陽門-建國門-北京站-崇文門-前門-和平門-宣武門-長椿街-復興門-阜成門-車公庄-（西直門）
4號線：
國家圖書館-動物園-西直門-新街口-平安里-西四-靈境衚衕-西單-宣武門-菜市口-陶然亭-北京南站-馬家堡-角門西-公益西橋
5號線：
宋家莊-劉家窯-蒲黃榆-天壇東門-磁器口-崇文門-東單-燈市口-東四-張自忠路-北新橋-雍和宮-和平里北街-和平西橋-惠新西街南口-惠新西街北口-大屯路東-北苑路北-立水橋南-立水橋-天通苑南-天通苑-天通苑北
6號線：
金安橋-蘋果園-楊庄-西黃村-廖公庄-田村-海淀五路居-慈壽寺-花園橋-白石橋南-車公庄西-車公庄-平安里-北海北-南鑼鼓巷-東四-朝陽門-東大橋-呼家樓-金台路-十里堡-青年路-褡褳坡-黃渠-常營-草房-物資學院-通州北關-通運門-北運河西-北運河東-郝家府-東夏園-潞城
7號線：
北京西站-灣子-達官營-廣安門內-菜市口-虎坊橋-珠市口-橋灣-磁器口-廣渠門內-廣渠門外-雙井-九龍山-大郊亭-百子灣-化工-南樓梓庄-歡樂谷景區-垡頭-雙合-焦化廠
8號線北：
朱辛庄-育知路-平西府-回龍觀東大街-霍營-育新-西小口-永泰庄-林萃橋-森林公園南門-奧林匹克公園-奧體中心-北土城-安華橋-安德里北街-鼓樓大街-什剎海-南鑼鼓巷-中國美術館
8號線南：
珠市口-天橋-永定門外-木樨園-海戶屯-大紅門-大紅門南-和義-東高地-火箭萬源-五福堂-德茂-瀛海
9號線：
郭公庄-丰台科技園-科怡路-丰台南路-丰台東大街-七里庄-六里橋-六里橋東-北京西站-軍事博物館-白堆子-白石橋南-國家圖書館
10號線：
巴溝-蘇州街-海淀黃庄-知春里-知春路-西土城-牡丹園-健德門-北土城-安貞門-惠新西街南口-芍藥居-太陽宮-三元橋-亮馬橋-農業展覽館-團結湖-呼家樓-金台夕照-國貿-雙井-勁松-潘家園-十里河-分鐘寺-成壽寺-宋家莊-石榴庄-大紅
門-角門東-角門西-草橋-紀家廟-首經貿-丰台站-泥窪-西局-六里橋-蓮花橋-公主墳-西釣魚台-慈壽寺-車道溝-長春橋-火器營-（巴溝）
13號線：
西直門-大鐘寺-知春路-五道口-上地-西二旗-龍澤-回龍觀-霍營-立水橋-北苑-望京西-芍藥居-光熙門-柳芳-東直門
14號線西：
張郭庄-園博園-大瓦窯-郭莊子-大井-七里庄-西局
14號線東：
北京南站-陶然橋-永定門外-景泰-蒲黃榆-方庄-十里河-北工大西門-平樂園-九龍山-大望路-金台路-朝陽公園-棗營-東風北橋-將台-高家園-望京南-阜通-望京-東湖渠-來廣營-善各庄
15號線：
俸伯-順義-石門-南法信-後沙峪-花梨坎-國展-孫河-馬泉營-崔各庄-望京東-望京-望京西-關庄-大屯路東-安立路-奧林匹克公園-北沙灘-六道口-清華東路西口
16號線：
西苑-農大南路-馬連窪-西北旺-永丰南-永豐-屯佃-稻香湖路-溫陽路-北安河
八通線：
四惠-四惠東-高碑店-傳媒大學-雙橋-管庄-八里橋-通州北苑-果園-九棵樹-梨園-臨河裡-土橋
昌平線
昌平西山口-十三陵景區-昌平-昌平東關-北邵窪-南邵-沙河高教園-沙河-鞏華城-朱辛庄-生命科學園-西二旗
亦庄線：
宋家莊-肖村-小紅門-舊宮-亦庄橋-亦庄文化園-萬源街-榮京東街-榮昌東街-同濟南路-經海路-次渠南-次渠-亦庄火車站
房山線：
郭公庄-大葆台-稻田-長陽-籬笆房-廣陽城-良鄉大學城北-良鄉大學城-良鄉大學城西-良鄉南關-蘇庄-閻村東
機場線
東直門-三元橋-3號航站樓-2號航站樓
大興線
公益西橋-新宮-西紅門-高米店北-高米店南-棗園-清源路-黃村西大街-黃村火車站-義和庄-生物醫藥基地-天宮院
S1線
石廠-小園-栗園庄-上岸-橋戶營-四道橋-金安橋
西郊線
巴溝-頤和園西門-茶棚-萬安-植物園-香山
數據大概就這些，那麼我們怎麼來搜索我們想要的數據呢？我們還是先分析一下我們的問題。我們要從西直門出發，到達蘇州街，很容易我們就知道了我們要做4號線，然後呢？然後我們去哪？
我們在西直門上車以後，有積水潭，新街口，動物園，大鐘寺，車公庄。這5個方向可以選擇。我們先（隨便）寫一個程式，不管是哪，先走著。
我們現將數據清洗一下，變成我們想要的樣子：{'蘋果園': ['古城', '金安橋', '楊庄'], '古城': ['蘋果園', '八角遊樂園'], '八角遊樂園': ['古城', '八寶山'], '八寶山': ['八角遊樂園', '玉泉路'], '玉泉路': ['八寶山', '五棵松'], '五棵松': ['玉泉路', '萬壽路'], '萬壽路': ['五棵松', '公主墳'], '公主墳': ['萬壽路', '軍事博物館', '蓮花橋', '西釣魚台'], '軍事博物館': ['公主墳', '木樨地', '北京西站', '白堆子'], '木樨地': ['軍事博物館', '南禮士路'], '南禮士路': ['木樨地', '復興門'], '復興門': ['南禮士路', '西單', '長椿街', '阜成門'], '西單': ['復興門', '天安門西', '宣武門', '靈境衚衕'], '天安門西': ['西單', '天安門東'], '天安門東': ['天安門西', '王府井'], ...}，也就是這樣的。我們用每一個站當作key，可以到達的車站我們設置為value列表。
然後我們先來看一下我們的程式碼吧
def breadth_first_search(start, arrive, connrction_grpah): pathes = [[start]] visitied = set() while pathes: path = pathes.pop(0) froninter = path[-1] if froninter in visitied: continue successors = connrction_grpah[froninter] for city in successors: new_path = path + [city] pathes.append(new_path) if city == arrive: return new_path visitied.add(froninter)
我們可以看得出來，我們拿到我們的始發站，然後去我們剛才清洗的字典里遍歷，可以得到我們由始發站可以到達的第一站，然後我們在依次遍歷這些站。我們可以看到，我們先遍歷一站就到的車站，然後再依次遍歷兩站可以到達的車站，依次類推，我們可以看到，我們遍歷了所以我們到達的車站，是一層層遍歷的，這裡引出我們今天想說的，也就是廣度優先遍歷。舉一個栗子，就是我們遍歷一個大樹，我們先優先獲得主幹，先看主幹有沒有我們想要的，沒有，好，我們繼續，在看枝幹，然後再看葉子，也就是說我們的每一層是幾乎同時遍歷的搜索遍歷的，與此相反，我們還有一個深度優先搜索，我們來看一下程式碼
def depth_first_search(start, arrive, connrction_grpah): pathes = [[start]] visitied = set() while pathes: path = pathes.pop(0) froninter = path[-1] if froninter in visitied: continue successors = connrction_grpah[froninter] for city in successors: if city in path: continue new_path = path + [city] pathes.append(new_path) if city == arrive: return new_path visitied.add(froninter) pathes = sorted(pathes, key=len, reverse=True)
和上一個程式碼幾乎一樣的，只不過加了一個排序，也是說，我們拿到了新的線路，我們還是會繼續搜索該線路，直到該條路走不通了，我們才會繼續走另外的路，也就是上面說的，我們先看大樹的主幹，然後看枝幹，看葉子，再回過頭來，再看另一個枝幹，另一個葉子，這也就是我們說的深度優先搜索。
這篇部落格寫的比較倉促，時間比較緊，工作壓力大，而且我也是第一次接觸演算法，很多知識還有待學習，開始的時候我認為我的python基礎還可以，實操起來卻不是那樣了。
我們下篇部落格回來說說導數和梯度下降，來得及就再說一下基於導數來作擬合的操作。