基于動(dòng)態(tài)數(shù)據(jù)窗口的復(fù)合聚類(lèi)航線優(yōu)化設(shè)計(jì)

1、基于動(dòng)態(tài)數(shù)據(jù)窗口的復(fù)合聚類(lèi)航線優(yōu)化設(shè)計(jì)李政 陸百川 (重慶交通大學(xué) 交通運(yùn)輸學(xué)院，重慶 400074)摘要：針對(duì)航運(yùn)智能數(shù)據(jù)批量大、干擾強(qiáng)和實(shí)時(shí)性的固有特點(diǎn)以及傳統(tǒng)各聚類(lèi)算法的不同缺點(diǎn)，本文提出一種基于動(dòng)態(tài)數(shù)據(jù)窗口的復(fù)合聚類(lèi)方法，應(yīng)用于船舶航線的優(yōu)化設(shè)計(jì)，船位數(shù)據(jù)聚類(lèi)中心連線光滑，線性度很好，最后通過(guò)仿真實(shí)驗(yàn)給出該方法的結(jié)果。關(guān)鍵詞：聚類(lèi)分析，動(dòng)態(tài)數(shù)據(jù)窗口，航線，仿真中圖分類(lèi)號(hào)：U491 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：Design of Route Optimization Based on Dynamic Data WindowLI Zheng , LU Baichuan (School of

2、Traffic & Transportation, Chongqing Jiaotong University, Chongqing 400074, China)Abstract: Intelligent data of shipping are large, real-time and with strong interference, for these inherent characteristics, as well as shortcomings of each traditional clustering algorithm, this paper provides a f

3、usion clustering algorithm based on dynamic data window, which can be applied in optimization design of ship routes. The clustering center line of ship position data is smooth, and with good linearity. Results of this method are given through the simulation.Key words: Cluster analysis; Dynamic Data

4、Windows; Route; Simulation1引言 隨著國(guó)際貿(mào)易的不斷繁榮和航運(yùn)技術(shù)的不斷發(fā)展，使得航線的日常經(jīng)營(yíng)運(yùn)作也日益復(fù)雜化。在這樣的行業(yè)背景下，如何在操作層面上優(yōu)化船舶航線使其能低成本高效益的運(yùn)作，成了迫切需要解決的問(wèn)題。目前關(guān)于航線設(shè)計(jì)的理論已較為成熟，但是實(shí)際操作中卻缺少將具體運(yùn)營(yíng)層面與船舶航線分配這二者充分結(jié)合起來(lái)從船舶運(yùn)行的整體角度來(lái)解決問(wèn)題1。本文針對(duì)航海智能運(yùn)輸空間數(shù)據(jù)存在異常數(shù)據(jù)干擾的特點(diǎn)，引入?yún)^(qū)域劃分的思想、將密度方法與中心計(jì)算方法相結(jié)合，提出一種基于動(dòng)態(tài)數(shù)據(jù)窗口重疊移動(dòng)的復(fù)合聚類(lèi)方法。這種算法可以去除噪聲和異常數(shù)據(jù)的影響，并解決采用單一聚類(lèi)算法中計(jì)算凝聚中心點(diǎn)

5、時(shí)偏差過(guò)大的問(wèn)題；能避免邊緣點(diǎn)對(duì)計(jì)算最大凝聚點(diǎn)的不良影響，在計(jì)算最大凝聚點(diǎn)時(shí)平等對(duì)待所有區(qū)域分界點(diǎn)，使其所做貢獻(xiàn)一樣；不受輸入樣本數(shù)據(jù)值的影響；而且采用該方法計(jì)算的所有凝聚中心在整個(gè)區(qū)域的中心，凝聚中心的連線光滑，效果很好。2聚類(lèi)算法 聚類(lèi)（Clustering）算法是把每個(gè)分類(lèi)對(duì)象稱(chēng)為樣品，并根據(jù)對(duì)象的性質(zhì)和分類(lèi)的目的選定若干指標(biāo)（變量），對(duì)每一個(gè)樣品測(cè)出所有的指標(biāo)值，將得到的結(jié)果列成一個(gè)數(shù)據(jù)矩陣，這個(gè)資料陣就是聚類(lèi)分析的出發(fā)點(diǎn)，聚類(lèi)算法的分析過(guò)程如圖1所示。聚類(lèi)分析作為一個(gè)富有挑戰(zhàn)的研究領(lǐng)域，包含了許多方法：如劃分方法、層次方法、基于密度方法、基于網(wǎng)格方法、基于模型方法等。本文結(jié)合我國(guó)航運(yùn)

6、的具體特點(diǎn)，通過(guò)尋求船舶航線在各個(gè)掛靠港口合理的安置，對(duì)船舶航線的運(yùn)行進(jìn)行了整體優(yōu)化，增加交通的機(jī)動(dòng)性、減少船舶運(yùn)輸對(duì)環(huán)境的影響、提高航道通行能力和交通效率。圖1 聚類(lèi)算法分析過(guò)程然而，聚類(lèi)分析也存在一些缺點(diǎn)，比如：k- means算法可擴(kuò)展性好，可以克服局部最優(yōu)的問(wèn)題，但是對(duì)噪聲和異常數(shù)據(jù)也很敏感，只適用于聚類(lèi)均值有意義的情況，而不適用于發(fā)現(xiàn)非凸形狀的聚類(lèi)或具有不同大小的聚類(lèi)?；诿芏确椒軌虬l(fā)現(xiàn)具有任意形狀的聚類(lèi)，但對(duì)用戶所要設(shè)置的參數(shù)敏感2。許多數(shù)據(jù)處理對(duì)象僅僅采用一種聚類(lèi)方法很難得到理想的聚類(lèi)效果，這也正是本文產(chǎn)生的初衷。 3基于動(dòng)態(tài)數(shù)據(jù)窗口的復(fù)合聚類(lèi)方法本文針對(duì)上述幾種聚類(lèi)算法存在的

7、問(wèn)題，提出基于動(dòng)態(tài)數(shù)據(jù)窗口的復(fù)合聚類(lèi)方法?；舅悸肥牵涸谡麄€(gè)樣本空間，通過(guò)數(shù)據(jù)窗口的劃分和重疊移動(dòng)、密度計(jì)算和求取最大凝聚點(diǎn)，進(jìn)行聚類(lèi)分析。具體步驟是：首先將整個(gè)聚類(lèi)點(diǎn)劃分得到一系列的數(shù)據(jù)窗口；隨著數(shù)據(jù)窗口的重疊移動(dòng)，在每個(gè)數(shù)據(jù)窗口內(nèi)尋求密度點(diǎn)；最后利用中心計(jì)算公式求取最大凝聚點(diǎn)。3.1 數(shù)據(jù)窗口劃分及重疊移動(dòng) 本文數(shù)據(jù)窗口的劃分方法是：聚類(lèi)點(diǎn)的選取是先按照樣本的范圍劃分等大小的數(shù)據(jù)窗口(每個(gè)數(shù)據(jù)窗口的樣本點(diǎn)個(gè)數(shù)不一定相同)，然后在這些數(shù)據(jù)窗口內(nèi)選取聚類(lèi)點(diǎn)，按照X軸排序，固定的在X軸上每隔距離的范圍作為一個(gè)數(shù)據(jù)窗口。這樣劃分的優(yōu)點(diǎn)是：聚類(lèi)點(diǎn)選取在各個(gè)數(shù)據(jù)窗口內(nèi)比較平均，各聚類(lèi)點(diǎn)之間距離差距不會(huì)

8、很大，且適應(yīng)于空間內(nèi)樣本的聚類(lèi)。 由于航運(yùn)智能數(shù)據(jù)處理的實(shí)時(shí)性，所以要使劃分所得到的數(shù)據(jù)窗口能夠移動(dòng)。但是，窗口移動(dòng)往往會(huì)使數(shù)據(jù)窗口分界處的樣本點(diǎn)被忽略。本文采用相臨的兩個(gè)數(shù)據(jù)窗口部分重疊，并可沿一定方向推移的辦法來(lái)解決這一問(wèn)題。如圖2所示?？删唧w表示為：00.2為第一個(gè)數(shù)據(jù)窗口；0.10.3為第二個(gè)數(shù)據(jù)窗口；0.20.4為第三個(gè)數(shù)據(jù)窗口；0.30.5為第四個(gè)數(shù)據(jù)窗口。以此類(lèi)推，第個(gè)數(shù)據(jù)窗口與第個(gè)數(shù)據(jù)窗口部分重疊，這樣重疊處的樣本點(diǎn)被重復(fù)計(jì)算，使得數(shù)據(jù)窗口分界處的樣本點(diǎn)不被忽略。隨著數(shù)據(jù)窗口沿某一方向的移動(dòng)，我們可以不斷地實(shí)時(shí)處理動(dòng)態(tài)數(shù)據(jù)。圖2 數(shù)據(jù)窗口重疊的區(qū)域劃分示意圖3.2 密度點(diǎn)選取在

9、劃分的數(shù)據(jù)窗口內(nèi)，選取個(gè)密度點(diǎn)的過(guò)程如下：,依次為,個(gè)圓的半徑，值根據(jù)實(shí)際情況選取，其中,，通常，其中或3。在在數(shù)據(jù)窗口內(nèi)選取密度點(diǎn)，假設(shè)中有個(gè)樣本點(diǎn)，如圖3所示。圖3 密度點(diǎn)選取示意圖對(duì)于每一個(gè)樣本點(diǎn)，以為球心，為半徑做球。代表其他樣本點(diǎn)。如果（之間的歐式距離），計(jì)算落入樣本點(diǎn)球域內(nèi)的其他樣本點(diǎn)的個(gè)數(shù)。選擇中最大的那個(gè)樣本點(diǎn)作為第一凝聚點(diǎn)；除去第一凝聚點(diǎn)之外的其他點(diǎn)。如果，忽略這些樣本點(diǎn)，對(duì)于剩下的樣本點(diǎn)如果且，忽略這些樣本點(diǎn)，對(duì)于再次剩下的樣本點(diǎn)如果，計(jì)算落入樣本點(diǎn)球域內(nèi)的其他樣本點(diǎn)的個(gè)數(shù)。選擇最大的那個(gè)樣本點(diǎn)作為第二凝聚點(diǎn)。按照樣品密度由大到小一直選下去，直到找到第密度點(diǎn)為止。因?yàn)榭紤]到

10、第密度點(diǎn)可能有多個(gè),即第密度點(diǎn)包含個(gè)并列密度點(diǎn)， 所以最終選出的密度點(diǎn)個(gè)數(shù)為。最后將所有密度點(diǎn)寫(xiě)成向量形式為，其中，,(假設(shè)第密度點(diǎn)有多個(gè)，表示最后一個(gè))，這樣在每個(gè)數(shù)據(jù)窗口內(nèi)選出的個(gè)密度點(diǎn)代表了這個(gè)數(shù)據(jù)窗口的樣本點(diǎn)分布情況。3.3 計(jì)算最大凝聚點(diǎn)考慮到不同密度點(diǎn)聚類(lèi)效果的地位不同，我們將得到的密度點(diǎn)作如下處理：給每一個(gè)密度點(diǎn)乘上一個(gè)比重系數(shù)，第密度點(diǎn)的比重系數(shù)為。設(shè)為數(shù)據(jù)窗口內(nèi)所選出的個(gè)密度點(diǎn)的重心，其中。 在二維平面上的數(shù)據(jù)窗口內(nèi)，求出第個(gè)密度點(diǎn)的比重系數(shù)。本文取，。將代入式，（表示與處理完的密度點(diǎn)）中，可求出預(yù)處理后的個(gè)密度點(diǎn)為，其中是第個(gè)密度點(diǎn)的橫坐標(biāo)和縱坐標(biāo)，是第個(gè)密度點(diǎn)預(yù)處理后的橫

11、坐標(biāo)和縱坐標(biāo)，。將個(gè)密度點(diǎn)預(yù)處理后，采用中心計(jì)算公式計(jì)算最大凝聚點(diǎn)。計(jì)算公式如下：2,為數(shù)據(jù)窗口內(nèi)計(jì)算所得的最大凝聚點(diǎn)的坐標(biāo)。計(jì)算結(jié)果如圖4所示。圖4 計(jì)算最大凝聚點(diǎn)示意圖4仿真實(shí)驗(yàn)本文仿真實(shí)驗(yàn)所用數(shù)據(jù)是某船舶的實(shí)際運(yùn)行軌跡散點(diǎn)數(shù)據(jù)，來(lái)自GPS檢測(cè)，其中包括暗礁、島嶼和水波等異常數(shù)據(jù)的干擾，平均每10S取一次船位數(shù)據(jù)，總共取360對(duì)散點(diǎn)數(shù)據(jù)(由經(jīng)度和緯度表示)。按照時(shí)間序列把這些船位進(jìn)行排序，圖5為船舶位置數(shù)據(jù)散點(diǎn)圖在MATIAB R2009a上的實(shí)現(xiàn)，橫坐標(biāo)表示經(jīng)度，縱坐標(biāo)表示緯度。圖5 船舶位置數(shù)據(jù)散點(diǎn)圖從上圖可以看出GPS檢測(cè)到的原始數(shù)據(jù)受了異常數(shù)據(jù)的干擾，船位數(shù)據(jù)雜亂無(wú)章。本文結(jié)合k-

12、means算法中的劃分方法以及中心計(jì)算方法中凝聚的思想,采用基于動(dòng)態(tài)數(shù)據(jù)窗口的方法對(duì)原始船位數(shù)據(jù)進(jìn)行聚類(lèi)優(yōu)化，先把圖5中的樣本點(diǎn)進(jìn)行數(shù)據(jù)預(yù)處理消除部分干擾，再按照基于動(dòng)態(tài)數(shù)據(jù)窗口的聚類(lèi)方法進(jìn)行數(shù)據(jù)窗口劃分，取， 即分成個(gè)數(shù)據(jù)窗口，這些數(shù)據(jù)窗口依次重疊平移。每個(gè)數(shù)據(jù)窗口大約有10個(gè)點(diǎn)，然后在每個(gè)數(shù)據(jù)窗口內(nèi)按照樣本點(diǎn)的分布情況選出3個(gè)密度點(diǎn)，計(jì)算出密度點(diǎn)比重系數(shù)，然后再求每個(gè)數(shù)據(jù)窗口的最大凝聚點(diǎn)，最后將其連線，圖6為基于動(dòng)態(tài)數(shù)據(jù)窗口的船位聚類(lèi)結(jié)果。最大凝聚點(diǎn)連線的基本是整個(gè)區(qū)域的中心，即使在樣本點(diǎn)分布異常的區(qū)域，聚類(lèi)效果也是很好的。圖6 基于動(dòng)態(tài)數(shù)據(jù)窗口的船位聚類(lèi)結(jié)果5結(jié)語(yǔ) 通過(guò)仿真實(shí)驗(yàn)可以看出，

13、基于動(dòng)態(tài)數(shù)據(jù)窗口的復(fù)合聚類(lèi)算法用于船舶航線的優(yōu)化設(shè)計(jì)效果很好的。采樣該方法聚類(lèi)優(yōu)化的航線線性度好，使得航線最短，節(jié)約了能源，提高了船舶運(yùn)輸?shù)男?，而且設(shè)計(jì)的航線是安全的。其次，該方法克服了k-means算法和密度算法的一些缺點(diǎn)，避免了噪聲和異常數(shù)據(jù)的影響。聚類(lèi)分析也可以作為單獨(dú)的工具以發(fā)現(xiàn)數(shù)據(jù)源的數(shù)據(jù)分布信息，因此聚類(lèi)分析的研究具有很重要的現(xiàn)實(shí)意義。參考文獻(xiàn)1聶躍光.基于密度聚類(lèi)的空間數(shù)據(jù)挖掘算法研究，太原科技大學(xué)碩士學(xué)位論文，2008.07.2王天真，湯天浩.一種基于動(dòng)態(tài)數(shù)據(jù)窗口的復(fù)合聚類(lèi)方法及在GIS中方的應(yīng)用J,模式識(shí)別與人工 ，2005.04.3于智航.改進(jìn)的密度聚類(lèi)算法研究J，大連理工大學(xué)碩士學(xué)位論文，2007.12.4劉合兵,尚俊平. 基于距離和密度的聚類(lèi)和孤立點(diǎn)檢測(cè)算法J，河南師范大學(xué)學(xué)報(bào)，2008.03. 5時(shí)銀水，姬