基于仿射傳播算法的城市航空便利性分析

《基于仿射傳播算法的城市航空便利性分析》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、基于仿射傳播算法的城市航空便利性分析摘要通過識(shí)別一組代表點(diǎn)來聚類數(shù)據(jù)對(duì)于探測數(shù)據(jù)模式是非常重要的，隨機(jī)抽取數(shù)據(jù)點(diǎn)集合后反復(fù)修正可以找到這些代表點(diǎn)。傳統(tǒng)的聚類算法存在聚類速度慢、效果差的問題，F(xiàn)rey與Dueck在Science發(fā)表的仿射傳播（Affinitypropagation，簡稱AP）算法對(duì)數(shù)據(jù)聚類的誤差要小于其它方法，并且所用時(shí)間較短。本文將分析和對(duì)比K-means、AP算法兩種聚類算法，并利用AP算法分析航空公司運(yùn)營的國內(nèi)城市航空便利性問題，城市的相似值用國內(nèi)43個(gè)城市營運(yùn)機(jī)場之間航班預(yù)估時(shí)間負(fù)值標(biāo)記?！　￡P(guān)鍵詞聚類；仿射傳播算法；K-means算法；航線　?。篢P39

2、1.41：A：1671—7597（2013）051-072-03　　航空公司的航線X絡(luò)對(duì)其盈利能力、運(yùn)行效率和客戶服務(wù)質(zhì)量有著重要的影響。近些年，國內(nèi)航空業(yè)務(wù)增長性趨勢明顯，各航空公司不斷加強(qiáng)航線的拓展和航空樞紐的建設(shè)，航線X絡(luò)越趨復(fù)雜，目前國內(nèi)對(duì)航線X絡(luò)的研究相對(duì)落后，缺乏對(duì)航線X絡(luò)運(yùn)行數(shù)據(jù)的定量分析，在航線的制定、評(píng)估和設(shè)計(jì)上仍以粗放的感性認(rèn)識(shí)和經(jīng)驗(yàn)判斷為主。因此，以市場需求以及航空公司的機(jī)隊(duì)規(guī)模、運(yùn)力為參考，合理布局航線X絡(luò)尤為重要。本文僅以航空公司生產(chǎn)排班計(jì)劃為基礎(chǔ)，采用先進(jìn)的聚類算法，對(duì)城市航空便利性進(jìn)行初步的探討和分析。　　1聚類算法　　聚類（Clustering）是

3、指根據(jù)“物以類聚”的原理，將本身沒有類別的數(shù)據(jù)聚集成不同的組，聚集后的一組數(shù)據(jù)對(duì)象稱為類（Cluster），其結(jié)果需滿足同一個(gè)類內(nèi)的數(shù)據(jù)對(duì)象之間高度相似，并且不同類之間的數(shù)據(jù)對(duì)象有較高的差異性?！　【垲惙治龅乃惴梢苑譃椋簞澐址ǎ≒artitioningMethods）、層次法（HierarchicalMethods）、基于密度的方法（density-basedmethods）、基于X格的方法（grid-basedmethods）、基于模型的方法（Model-BasedMethods）?！　〗?jīng)典的K-means和K-centers都是劃分法。　　1.1K-means算法　　由于該

4、算法的計(jì)算復(fù)雜度是O（nkt），其中n是對(duì)象的總數(shù)，k是預(yù)期結(jié)果聚類中心的個(gè)數(shù)，t是迭代的次數(shù)，通常k<

5、個(gè)數(shù)據(jù)點(diǎn)之間的相似度進(jìn)行聚類，數(shù)據(jù)點(diǎn)間的相似度既可以是對(duì)稱的，也可以是不對(duì)稱的，如在本文后續(xù)描述中的城市對(duì)間的距離（航班時(shí)間）就是不對(duì)稱的。這些相似度組成n×n的相似度矩陣S。AP算法將所有的數(shù)據(jù)點(diǎn)都作為潛在的聚類中心，稱之為exemplar，因此不需要事先指定聚類數(shù)目，而需要為每個(gè)點(diǎn)設(shè)置個(gè)實(shí)數(shù)值s（k，k），該值也被稱作參考度p（preference），s（k，k）值較大的點(diǎn)更有可能選為中心點(diǎn)。中心點(diǎn)的數(shù)量受preference影響。若已知所有的點(diǎn)被選為中心點(diǎn)的概率相同，則可將所有點(diǎn)的preference設(shè)置為相同的值（不同的值可能會(huì)導(dǎo)致不同的聚類數(shù)量），該值可以為所有相似度的

6、中值或者最小值。AP算法通過吸引度r（responsiility）和歸屬度a（availability）控制算法的收斂。r（i，k）是從點(diǎn)i發(fā)送到點(diǎn)k的數(shù)值消息，反映的是k點(diǎn)對(duì)i點(diǎn)的吸引程度。a（i，k）則從點(diǎn)k發(fā)送到點(diǎn)i的數(shù)值消息，反映的是i點(diǎn)對(duì)k點(diǎn)的歸屬程度。r（i，k）與a（i，k）越強(qiáng)，代表k點(diǎn)成為聚類中心的機(jī)會(huì)就越大，同時(shí)i點(diǎn)隸屬于以k點(diǎn)為聚類中心的聚類的機(jī)會(huì)也越大。該算法就是通過不斷的迭代過程來更新數(shù)據(jù)點(diǎn)之間的吸引度和歸屬度，逐步精煉產(chǎn)生m個(gè)高質(zhì)量的聚類中心，同時(shí)將其余的數(shù)據(jù)點(diǎn)歸類給這m個(gè)聚類中心，形成以這m個(gè)聚類中心為中心的聚類?！　』趤碜脏従拥恼捻憫?yīng)度來評(píng)價(jià)k

7、是否適于作中心點(diǎn)?！　?結(jié)束語　　本文利用AP聚類算法對(duì)國航通航的國內(nèi)43個(gè)城市航空便利性進(jìn)行聚類分析，實(shí)驗(yàn)結(jié)果較客觀的反映出各城市航空便利性的真實(shí)情況，進(jìn)一步的研究分析可以考慮覆蓋國內(nèi)所有通航城市，并通過引入航班實(shí)際飛行時(shí)間數(shù)據(jù)以及調(diào)整s（i，i）值優(yōu)化算法，提高算法的精確性。另外，也可通過采集和分析城市GDP數(shù)據(jù)、城市流摘要通過識(shí)別一組代表點(diǎn)來聚類數(shù)據(jù)對(duì)于探測數(shù)據(jù)模式是非常重要的，隨機(jī)抽取數(shù)據(jù)點(diǎn)集合后反復(fù)修正可以找到這些代表點(diǎn)。傳統(tǒng)的聚類算法存在聚類速度慢、效果差的問題，F(xiàn)r