劉 凱,龔蘭蘭,凌興宏,2,周家骎
(1.蘇州大學文正學院,江蘇 蘇州 215104;2.蘇州大學 計算機科學與技術學院,江蘇 蘇州 215104)
公交樞紐站是公交線路之間、公共交通與其他客運方式換乘相對集中的場所。有多條公交路線通過公交樞紐站,因此公交樞紐站的效率,關系到整體公交運營的效率以及對于乘客的便利性。而對于公交樞紐站站點位置的確定,除傳統(tǒng)的人為規(guī)劃方式外,文中對公交系統(tǒng)運行的數(shù)據(jù)進行分析,重新確定公交樞紐站點的方法。通過乘客換乘數(shù)據(jù)挖掘聚類來確定公交樞紐站更加科學合理。
K-means[1]是聚類算法中最常用的一種算法,該算法最大的特點是簡單,運算快速,但是也有兩個主要缺陷[2]:類簇數(shù)K值需要事先確定,隨機選擇的初始中心點會嚴重影響聚類結果。層次聚類算法[3]又稱為分級聚類算法,是一種較為常用、實現(xiàn)簡單的聚類算法。
文中主要研究使用基于K-means的層次聚類算法[4]確定交通規(guī)劃中樞紐站點確定的問題,并且提出了使用遺傳算法[5]設置基于層次的K-means聚類算法的雙類簇數(shù)。
如何比較數(shù)據(jù)與數(shù)據(jù),數(shù)據(jù)與簇之間特性的相似性成為了聚類算法的關鍵問題。對于一種聚類算法,其聚類的結果主要取決于數(shù)據(jù)間相似度的判斷。
用s(x,y)表示數(shù)據(jù)或簇x與數(shù)據(jù)或簇y的相似度。當x與y的相似度越高時,s(x,y)的值就越大,而當兩者相似度越低時,s(x,y)的值就越小。s(x,y)具有以下特性:
(1)0≤s(x,y)≤1;
(2)s(x,y)=s(y,x)。
通常在聚類算法中,相似度通過數(shù)據(jù)或類之間的特征空間中的距離來表示,用d(x,y)表示數(shù)據(jù)或簇x與數(shù)據(jù)或簇y的相似度,當x與y相似度越高時,d(x,y)就越??;當x與y相似度越低時,d(x,y)就越大。通常聚類算法使用的特征空間中的距離算法有Minkovski距離、余弦距離、皮爾斯相關系數(shù)、KL散度。
一般的給出明確標簽的數(shù)據(jù)進行聚類,是可以通過給出的標簽與聚類的結果評價聚類好壞,但大多數(shù)數(shù)據(jù)并沒有給出明確的標簽。因此需要一種可以在原始數(shù)據(jù)的基礎上用來評價不同算法或者算法不同運行方式對聚類結果所產(chǎn)生的影響的評估方式。
常用的聚類結果評價指標分為兩種:內部評價指標和外部評價指標。常用內部評價指標有Davies-Bouldin指標、Silhouette指標、Xie-Beni指標,常用外部評價指標有Rand指標、Jaccard系數(shù)、ARI指數(shù)、Russel-Rao指標。
文中采用了Silhouette[6]這一評價指標,該指標也稱作輪廓系數(shù)。輪廓系數(shù)最早由Peter J.Rousseeuw于1986年提出,是結合了內聚度和分離度兩種因素的一種評價指標。
K-means算法[7]是一種無監(jiān)督的機器學習算法,是基于劃分的聚類方法中應用最廣泛的算法。該算法具有線性的時間復雜度,且實現(xiàn)簡單,因此被廣泛應用于各種實際應用問題。
該算法易于理解與實現(xiàn),同時時間復雜度低,但算法需要手工確定類簇數(shù),對初始值的設置敏感;主要發(fā)現(xiàn)圓形或球形的類簇,不能識別非球形的類簇。
算法流程[8]如下:
(1)假設給定的數(shù)據(jù)集為R;
(2)隨機選取K個點作為聚類質心點(cluster centroids),即u1,u2,…,uk∈R。
重復下面過程直到收斂:
·對于每一個數(shù)據(jù)計算其到每一個質心點的距離,并將其歸入距離最小的類,也就是歸入與其特征最相似的類。ci=argmin(‖xi-uj‖2)
·對于每一個類j,重新計算該類的質心。質心的特性等于屬于該類的每個數(shù)據(jù)的平均值,即
凝聚層次聚類算法[9]是一種自上而下的層次聚類算法。首先找到兩條最接近的類,將它們合并成一個類,然后,使用剩下的類加上合并好的類,尋找下一對最接近的類。不斷重復此過程,直到所有的類都被合并到一個大類或者滿足結束條件。因為分級聚類的復雜度很高,通常用在數(shù)據(jù)點數(shù)目不太大的情況下。該算法無需事先確定類簇數(shù);可以發(fā)現(xiàn)層次間關系,但算法計算復雜度太高;孤立點對聚類結果影響較大。
算法流程如下:
(1)假設給定的數(shù)據(jù)集為R;
(2)將數(shù)據(jù)集R中每個數(shù)據(jù)作為一個類簇。
重復以下過程直到生成K或者1個類:
對于每一個類,計算其與其他所有類的距離,生成距離矩陣,將距離矩陣中最小距離的兩個類合并成一個類并重新計算該類簇的質心。
根據(jù)評估算法的主要思想,聚類結果的好壞取決于聚類的凝聚度和分離度,即同一類中各數(shù)據(jù)間的相似度與類與類之間的相似度。為了高聚類結果,可以從聚類的凝聚度和分離度兩個方面出發(fā)對層次聚類算法進行改進。
與基于層次聚類的K均值算法不同的是:基于層次聚類的K均值算法以層次算法為基礎[10],當數(shù)據(jù)樣本中孤立點較多時則聚類效果會變差,產(chǎn)生類簇只包含單個數(shù)據(jù)的情況,而使用基于K-means算法的層次聚類時,K-means算法對于孤立點進行了一定的處理,再使用層次聚類時,提高了聚類效果,避免了孤立點對聚類結果的影響。
針對本實驗該算法消除了孤立點對實驗結果的影響,同時區(qū)別于單純的層次聚類算法,會產(chǎn)生多種不同實驗結果,有利于公交樞紐站點的確定。
算法主要思想:
首先對于數(shù)據(jù)進行預估,預設兩個適合的K1、K2值且K1>K2(凝聚層次聚類算法的過程中類簇數(shù)會不斷減少,因此凝聚層次聚類算法的類簇數(shù)會少于K-means算法類簇數(shù)),然后對數(shù)據(jù)使用K-means劃分,直到劃分出K1個類簇,再使用凝聚層次聚類算法對K1個類簇進行凝聚,直到產(chǎn)生K2個類簇。
算法流程如下:
(1)從數(shù)據(jù)集R中,選定K1個點作為聚類質心點;
(2)重復下述過程直到收斂:
·對于每一個數(shù)據(jù)計算其到每一個質心點的距離,并將其歸入距離最小的類,也就是歸入與其特征最相似的類;
·對于每一個類j,重新計算該類的質心。質心的特性等于屬于該類的每個數(shù)據(jù)的平均值。
(3)計算所有類簇之間的距離,生成距離矩陣;
(4)將距離矩陣中距離最短的兩個類簇合并生成新的類簇并重新計算該類簇的質心;
(5)重復4、5直到凝聚到K2個類簇為止。
遺傳算法是Holland在20世紀60年代末提出的,是受遺傳學中自然選擇和遺傳機制啟發(fā)發(fā)展起來的一種搜索算法。它的基本思想是模擬生物種群進化的原則,包含了交叉、變異等操作,在不斷的種群迭代中,搜索歷代種群中的最優(yōu)個體即為最優(yōu)解。
輪廓系數(shù)[11]是評估聚類效果好壞的一種方式,其結合了聚類的凝聚度和分離度。該值處于-1~1之間,該值越大,表示聚類的效果越好,該值越小,表示聚類效果越差。
具體計算方法如下:
(1)對于每一個數(shù)據(jù)i,計算其與所在類簇中其余數(shù)據(jù)間的特征空間距離的平均值,用于度量類簇內的凝聚度,記為a(i);
(2)遍歷每一個非i所在的類簇,計算i與該類簇中所有數(shù)據(jù)的特征空間距離的平均值,記作b(i),用于度量類簇間的分離度;
(3)對于樣本點i,輪廓系數(shù)為:
(4)計算所有i的輪廓系數(shù),求出平均值即為當前聚類的整體輪廓系數(shù),度量數(shù)據(jù)聚類的緊密程度。
(1)隨機產(chǎn)生一個由確定長度的特征串組成的初始種群;
(2)對種群中的每一個個體采用改進的聚類算法進行聚類并將聚類結果的輪廓系數(shù)作為適應值;
(3)對初始種群進行交叉操作、變異操作、復制操作;
對學生與數(shù)據(jù)分析觀念相關的調查研究主要是從三個方面進行研究:一是就某一些統(tǒng)計概念的理解展開調查,如曲元海對初中生統(tǒng)計量理解的調查研究[12].二是單獨對學生的數(shù)據(jù)分析觀念進行調查,如李紅梅對七年級學生數(shù)據(jù)分析觀念的現(xiàn)狀調查[4].三是在調查數(shù)學核心素養(yǎng)中包含數(shù)據(jù)分析,如張淑梅對高中數(shù)學核心素養(yǎng)統(tǒng)計分析過程中發(fā)現(xiàn),數(shù)學建模與數(shù)據(jù)分析的相關性較大[13].
(4)在所有操作結束后判斷是否滿足迭代終止的條件。
·若滿足,則終止迭代并將所求的最優(yōu)解作為遺傳算法的執(zhí)行結果并輸出,這個結果就是對應問題的最優(yōu)解或者近似解;
·若不滿足,則終止條件并對當前的種群進行步驟2中的操作。
編碼是遺傳算法要解決的首要問題。編碼方法有很多[12],如二進制編碼、實數(shù)編碼、符號編碼等等。針對文中的問題,最適合的編碼方式為二進制編碼。
通過初步的實驗,發(fā)現(xiàn)優(yōu)秀個體的兩個K值(K1、K2)具有一定合適的比率大小關系。因此每個個體有兩條染色體,一條K1值染色體,一條比率染色體,K2的值由K1和比率所確定。
遺傳算法中,適應值決定個體遺傳的概率[13]。在文中適應值越小,則個體遺傳概率越大,適應值越大,則個體遺傳概率越小。
針對本問題,選擇了輪盤賭選擇[14]從而避免了使用確定性選擇產(chǎn)生的樣本單一問題。
輪盤賭選擇的基本思想是:各個體被選中的概率與其適應度大小成正比。具體操作方法如下:
(1)計算出種群中每個個體的適應度f(Ci)。I取值范圍為1~n,n為種群大小。
(2)計算出每個個體被遺傳到下一代群體中的概率。
(3)計算出每個個體的累計概率。
(4)在[0,1]區(qū)間之間產(chǎn)生一個偽隨機數(shù)r。
(5)若r (6)重復步驟4到步驟5共n次。 交叉運算指的是將兩個染色體按某種規(guī)則提取相應的部分然后按某種方式進行交叉互換,從而產(chǎn)生兩個新的個體。交叉運算時遺傳算法區(qū)別于其他進化算法的重要特征,其設計包括兩個方面[15]:①如何確定交叉基因的位置;②如何對交叉部分的基因進行互換。 該算法采用的是雙點交叉。雙點交叉的思想:從兩組染色體的開頭到相同的位置i提取這一段基因進行互換,再從相同的位置j到染色體結束的位置提取這一段基因進行互換。交叉后發(fā)現(xiàn)會產(chǎn)生K值超過數(shù)據(jù)集最大個數(shù)或者比率超過額定范圍的情形,對此則重新選擇個體進行交叉。 變異算子是對染色體的某些基因做改動從而產(chǎn)生一串新的染色體,作用是維持種群的多樣性,避免算法過早收斂甚至無法得到全局最優(yōu)解。交叉運算的設計包括兩個方面:①如何確定變異基因的位置;②如何對所需變異基因值進行替換。 在此所采用的是倒位變異,即在一串染色體中隨機選取兩個位i,j,將從第i位到第j位的染色體反轉從而實現(xiàn)變異效果。對于變異后產(chǎn)生K值大于數(shù)據(jù)集個數(shù)或者比率大于額定范圍的情形,則重新選取個體變異。 針對過早收斂問題,根據(jù)遺傳算法的模式定理,適應度更高的個體有更多復制的機會,因此,在種群還沒有達到最優(yōu)解時便有可能由某一當前最優(yōu)解過早占領了種群的統(tǒng)治地位從而得到了局部的最優(yōu)解,但在后續(xù)種群的迭代過程中,無法最終收斂到全局最優(yōu)解。這個現(xiàn)象就稱為過早收斂。文中采用了遷移思想,在算法中設置一個變量times記錄當前最優(yōu)解在后面的代數(shù)中保持統(tǒng)治地位的次數(shù),當次數(shù)達到一定的時候,保留當前適應度大于平均適應度的樣本,刪除其余樣本重新組合成種群,然后繼續(xù)算法。采用遷移的想法,從一定程度上避免了過早收斂這一現(xiàn)象,在迭代次數(shù)足夠多時能夠穩(wěn)定地求出問題的最優(yōu)解。 過慢結束是指在樣本迭代到一定次數(shù)之后,整個種群已經(jīng)大部分收斂了,但還是無法穩(wěn)定收斂到全局最優(yōu)解,最優(yōu)解的適應度與樣本平均適應度差別不大,導致了無法篩選出較好的算子進行復制操作。針對過慢結束問題,在復制算子中增加了一個函數(shù)用于判定是否出現(xiàn)了樣本的適應度最優(yōu)值與平均值相差不大的情形,若相差小于平均適應度的10%,則執(zhí)行放大函數(shù),用來臨時放大種群中各個樣本的適應值與平均值之間的差距,從而能更好地選擇出樣本進行復制操作。 文中數(shù)據(jù)來自于蘇州市吳中區(qū)公交數(shù)據(jù)。實驗目的是確定所有公交站點中的樞紐站點。 對實驗數(shù)據(jù)進行預處理之后,一共包含1 124個數(shù)據(jù)對象,每個數(shù)據(jù)對象包含了單個屬性。采用上文提及的凝聚層次聚類和K-means聚類結合改進后的聚類算法。 K-means算法與改進后的聚類算法的實驗結果見表1。遺傳算法確定K值的實驗結果見表2。 表1 K-means算法與改進算法 表1中K值由均方根方法確定。從表1可以看出改進后的算法比較改進之前,以輪廓系數(shù)作為評價依據(jù)有了較明顯的提升。 表2 遺傳算法設計K值 從表2可以看出使用遺傳算法設置改進聚類算法的K值,以輪廓系數(shù)為依據(jù),可行度較高。 通過文中的研究可以得出以下結論: (1)在樞紐站點確定的問題中,將K-means算法與凝聚層次聚類算法相結合,其聚類效果相比于單一算法有了很好的提升。 (2)使用遺傳算法來設置K值,達到了較優(yōu)解的效果,種群中的最優(yōu)個體的輪廓系數(shù)與采用均方根的效果差距較小。 (3)與目前已經(jīng)規(guī)劃的公交樞紐站點相比,本實驗結果又通過對數(shù)據(jù)的分析,列出了潛在的公交樞紐站點,同時對于各個公交站點流量進行了分析,為公交樞紐站點的二次規(guī)劃提供了有效的數(shù)據(jù)支持。 針對城市交通規(guī)劃中樞紐站點確定的問題,提出了使用改進的基于K-means的凝聚層次聚類算法對公交數(shù)據(jù)進行處理;同時為得到更優(yōu)的聚類結果,有別于傳統(tǒng)確定類簇數(shù)K的方法,使用遺傳算法確定K-means算法與層次聚類算法結合時的類簇數(shù)以及兩個類簇數(shù)之間的關系。通過實驗表明,使用改進的聚類算法確定樞紐站點為公交樞紐站點二次規(guī)劃提供了可靠的數(shù)據(jù)支持,并且使用遺傳算法改進的聚類算法的聚類效果有了較好的提升。2.6 交叉算子
2.7 變異算子
2.8 遺傳算法優(yōu)化
3 實驗分析
4 結束語