改進(jìn)聚類算法在公交數(shù)據(jù)挖掘中的應(yīng)用研究

劉 凱，龔蘭蘭，凌興宏,2，周家骎

(1.蘇州大學(xué)文正學(xué)院，江蘇 蘇州 215104；2.蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215104)

0 引 言

公交樞紐站是公交線路之間、公共交通與其他客運(yùn)方式換乘相對集中的場所。有多條公交路線通過公交樞紐站，因此公交樞紐站的效率，關(guān)系到整體公交運(yùn)營的效率以及對于乘客的便利性。而對于公交樞紐站站點(diǎn)位置的確定，除傳統(tǒng)的人為規(guī)劃方式外，文中對公交系統(tǒng)運(yùn)行的數(shù)據(jù)進(jìn)行分析，重新確定公交樞紐站點(diǎn)的方法。通過乘客換乘數(shù)據(jù)挖掘聚類來確定公交樞紐站更加科學(xué)合理。

K-means[1]是聚類算法中最常用的一種算法，該算法最大的特點(diǎn)是簡單，運(yùn)算快速，但是也有兩個(gè)主要缺陷[2]：類簇?cái)?shù)K值需要事先確定，隨機(jī)選擇的初始中心點(diǎn)會嚴(yán)重影響聚類結(jié)果。層次聚類算法[3]又稱為分級聚類算法，是一種較為常用、實(shí)現(xiàn)簡單的聚類算法。

文中主要研究使用基于K-means的層次聚類算法[4]確定交通規(guī)劃中樞紐站點(diǎn)確定的問題，并且提出了使用遺傳算法[5]設(shè)置基于層次的K-means聚類算法的雙類簇?cái)?shù)。

1 聚類算法及其評估

1.1 相似度

如何比較數(shù)據(jù)與數(shù)據(jù)，數(shù)據(jù)與簇之間特性的相似性成為了聚類算法的關(guān)鍵問題。對于一種聚類算法，其聚類的結(jié)果主要取決于數(shù)據(jù)間相似度的判斷。

用s(x,y)表示數(shù)據(jù)或簇x與數(shù)據(jù)或簇y的相似度。當(dāng)x與y的相似度越高時(shí)，s(x,y)的值就越大，而當(dāng)兩者相似度越低時(shí)，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的相似度，當(dāng)x與y相似度越高時(shí)，d(x,y)就越??；當(dāng)x與y相似度越低時(shí)，d(x,y)就越大。通常聚類算法使用的特征空間中的距離算法有Minkovski距離、余弦距離、皮爾斯相關(guān)系數(shù)、KL散度。

1.2 評估方式

一般的給出明確標(biāo)簽的數(shù)據(jù)進(jìn)行聚類，是可以通過給出的標(biāo)簽與聚類的結(jié)果評價(jià)聚類好壞，但大多數(shù)數(shù)據(jù)并沒有給出明確的標(biāo)簽。因此需要一種可以在原始數(shù)據(jù)的基礎(chǔ)上用來評價(jià)不同算法或者算法不同運(yùn)行方式對聚類結(jié)果所產(chǎn)生的影響的評估方式。

常用的聚類結(jié)果評價(jià)指標(biāo)分為兩種：內(nèi)部評價(jià)指標(biāo)和外部評價(jià)指標(biāo)。常用內(nèi)部評價(jià)指標(biāo)有Davies-Bouldin指標(biāo)、Silhouette指標(biāo)、Xie-Beni指標(biāo)，常用外部評價(jià)指標(biāo)有Rand指標(biāo)、Jaccard系數(shù)、ARI指數(shù)、Russel-Rao指標(biāo)。

文中采用了Silhouette[6]這一評價(jià)指標(biāo)，該指標(biāo)也稱作輪廓系數(shù)。輪廓系數(shù)最早由Peter J.Rousseeuw于1986年提出，是結(jié)合了內(nèi)聚度和分離度兩種因素的一種評價(jià)指標(biāo)。

1.3 K-means聚類算法簡述

K-means算法[7]是一種無監(jiān)督的機(jī)器學(xué)習(xí)算法，是基于劃分的聚類方法中應(yīng)用最廣泛的算法。該算法具有線性的時(shí)間復(fù)雜度，且實(shí)現(xiàn)簡單，因此被廣泛應(yīng)用于各種實(shí)際應(yīng)用問題。

該算法易于理解與實(shí)現(xiàn)，同時(shí)時(shí)間復(fù)雜度低，但算法需要手工確定類簇?cái)?shù)，對初始值的設(shè)置敏感；主要發(fā)現(xiàn)圓形或球形的類簇，不能識別非球形的類簇。

算法流程[8]如下：

(1)假設(shè)給定的數(shù)據(jù)集為R；

(2)隨機(jī)選取K個(gè)點(diǎn)作為聚類質(zhì)心點(diǎn)(cluster centroids)，即u1,u2,…,uk∈R。

重復(fù)下面過程直到收斂：

·對于每一個(gè)數(shù)據(jù)計(jì)算其到每一個(gè)質(zhì)心點(diǎn)的距離，并將其歸入距離最小的類，也就是歸入與其特征最相似的類。ci=argmin(‖xi-uj‖2)

·對于每一個(gè)類j，重新計(jì)算該類的質(zhì)心。質(zhì)心的特性等于屬于該類的每個(gè)數(shù)據(jù)的平均值，即

1.4 凝聚層次聚類算法簡述

凝聚層次聚類算法[9]是一種自上而下的層次聚類算法。首先找到兩條最接近的類，將它們合并成一個(gè)類，然后，使用剩下的類加上合并好的類，尋找下一對最接近的類。不斷重復(fù)此過程，直到所有的類都被合并到一個(gè)大類或者滿足結(jié)束條件。因?yàn)榉旨壘垲惖膹?fù)雜度很高，通常用在數(shù)據(jù)點(diǎn)數(shù)目不太大的情況下。該算法無需事先確定類簇?cái)?shù)；可以發(fā)現(xiàn)層次間關(guān)系，但算法計(jì)算復(fù)雜度太高；孤立點(diǎn)對聚類結(jié)果影響較大。

算法流程如下：

(1)假設(shè)給定的數(shù)據(jù)集為R；

(2)將數(shù)據(jù)集R中每個(gè)數(shù)據(jù)作為一個(gè)類簇。

重復(fù)以下過程直到生成K或者1個(gè)類：

對于每一個(gè)類，計(jì)算其與其他所有類的距離，生成距離矩陣，將距離矩陣中最小距離的兩個(gè)類合并成一個(gè)類并重新計(jì)算該類簇的質(zhì)心。

1.5 基于K-means的凝聚層次聚類算法

根據(jù)評估算法的主要思想，聚類結(jié)果的好壞取決于聚類的凝聚度和分離度，即同一類中各數(shù)據(jù)間的相似度與類與類之間的相似度。為了高聚類結(jié)果，可以從聚類的凝聚度和分離度兩個(gè)方面出發(fā)對層次聚類算法進(jìn)行改進(jìn)。

與基于層次聚類的K均值算法不同的是：基于層次聚類的K均值算法以層次算法為基礎(chǔ)[10]，當(dāng)數(shù)據(jù)樣本中孤立點(diǎn)較多時(shí)則聚類效果會變差，產(chǎn)生類簇只包含單個(gè)數(shù)據(jù)的情況，而使用基于K-means算法的層次聚類時(shí)，K-means算法對于孤立點(diǎn)進(jìn)行了一定的處理，再使用層次聚類時(shí)，提高了聚類效果，避免了孤立點(diǎn)對聚類結(jié)果的影響。

針對本實(shí)驗(yàn)該算法消除了孤立點(diǎn)對實(shí)驗(yàn)結(jié)果的影響，同時(shí)區(qū)別于單純的層次聚類算法，會產(chǎn)生多種不同實(shí)驗(yàn)結(jié)果，有利于公交樞紐站點(diǎn)的確定。

算法主要思想：

首先對于數(shù)據(jù)進(jìn)行預(yù)估，預(yù)設(shè)兩個(gè)適合的K1、K2值且K1>K2(凝聚層次聚類算法的過程中類簇?cái)?shù)會不斷減少，因此凝聚層次聚類算法的類簇?cái)?shù)會少于K-means算法類簇?cái)?shù))，然后對數(shù)據(jù)使用K-means劃分，直到劃分出K1個(gè)類簇，再使用凝聚層次聚類算法對K1個(gè)類簇進(jìn)行凝聚，直到產(chǎn)生K2個(gè)類簇。

算法流程如下：

(1)從數(shù)據(jù)集R中，選定K1個(gè)點(diǎn)作為聚類質(zhì)心點(diǎn)；

(2)重復(fù)下述過程直到收斂：

·對于每一個(gè)數(shù)據(jù)計(jì)算其到每一個(gè)質(zhì)心點(diǎn)的距離，并將其歸入距離最小的類，也就是歸入與其特征最相似的類；

·對于每一個(gè)類j，重新計(jì)算該類的質(zhì)心。質(zhì)心的特性等于屬于該類的每個(gè)數(shù)據(jù)的平均值。

(3)計(jì)算所有類簇之間的距離，生成距離矩陣；

(4)將距離矩陣中距離最短的兩個(gè)類簇合并生成新的類簇并重新計(jì)算該類簇的質(zhì)心；

(5)重復(fù)4、5直到凝聚到K2個(gè)類簇為止。

2 基于遺傳算法的改進(jìn)聚類算法

遺傳算法是Holland在20世紀(jì)60年代末提出的，是受遺傳學(xué)中自然選擇和遺傳機(jī)制啟發(fā)發(fā)展起來的一種搜索算法。它的基本思想是模擬生物種群進(jìn)化的原則，包含了交叉、變異等操作，在不斷的種群迭代中，搜索歷代種群中的最優(yōu)個(gè)體即為最優(yōu)解。

2.1 聚類效果評價(jià)指標(biāo)確定

輪廓系數(shù)[11]是評估聚類效果好壞的一種方式，其結(jié)合了聚類的凝聚度和分離度。該值處于-1～1之間，該值越大，表示聚類的效果越好，該值越小，表示聚類效果越差。

具體計(jì)算方法如下：

(1)對于每一個(gè)數(shù)據(jù)i，計(jì)算其與所在類簇中其余數(shù)據(jù)間的特征空間距離的平均值，用于度量類簇內(nèi)的凝聚度，記為a(i)；

(2)遍歷每一個(gè)非i所在的類簇，計(jì)算i與該類簇中所有數(shù)據(jù)的特征空間距離的平均值，記作b(i)，用于度量類簇間的分離度；

(3)對于樣本點(diǎn)i，輪廓系數(shù)為：

(4)計(jì)算所有i的輪廓系數(shù)，求出平均值即為當(dāng)前聚類的整體輪廓系數(shù)，度量數(shù)據(jù)聚類的緊密程度。

2.2 算法基本流程

(1)隨機(jī)產(chǎn)生一個(gè)由確定長度的特征串組成的初始種群；

(2)對種群中的每一個(gè)個(gè)體采用改進(jìn)的聚類算法進(jìn)行聚類并將聚類結(jié)果的輪廓系數(shù)作為適應(yīng)值；

(3)對初始種群進(jìn)行交叉操作、變異操作、復(fù)制操作；

對學(xué)生與數(shù)據(jù)分析觀念相關(guān)的調(diào)查研究主要是從三個(gè)方面進(jìn)行研究：一是就某一些統(tǒng)計(jì)概念的理解展開調(diào)查，如曲元海對初中生統(tǒng)計(jì)量理解的調(diào)查研究[12].二是單獨(dú)對學(xué)生的數(shù)據(jù)分析觀念進(jìn)行調(diào)查，如李紅梅對七年級學(xué)生數(shù)據(jù)分析觀念的現(xiàn)狀調(diào)查[4].三是在調(diào)查數(shù)學(xué)核心素養(yǎng)中包含數(shù)據(jù)分析，如張淑梅對高中數(shù)學(xué)核心素養(yǎng)統(tǒng)計(jì)分析過程中發(fā)現(xiàn)，數(shù)學(xué)建模與數(shù)據(jù)分析的相關(guān)性較大[13].

(4)在所有操作結(jié)束后判斷是否滿足迭代終止的條件。

·若滿足，則終止迭代并將所求的最優(yōu)解作為遺傳算法的執(zhí)行結(jié)果并輸出，這個(gè)結(jié)果就是對應(yīng)問題的最優(yōu)解或者近似解；

·若不滿足，則終止條件并對當(dāng)前的種群進(jìn)行步驟2中的操作。

2.3 編碼預(yù)處理以及編碼

編碼是遺傳算法要解決的首要問題。編碼方法有很多[12]，如二進(jìn)制編碼、實(shí)數(shù)編碼、符號編碼等等。針對文中的問題，最適合的編碼方式為二進(jìn)制編碼。

通過初步的實(shí)驗(yàn)，發(fā)現(xiàn)優(yōu)秀個(gè)體的兩個(gè)K值(K1、K2)具有一定合適的比率大小關(guān)系。因此每個(gè)個(gè)體有兩條染色體，一條K1值染色體，一條比率染色體，K2的值由K1和比率所確定。

2.4 適應(yīng)值計(jì)算以及評估

遺傳算法中，適應(yīng)值決定個(gè)體遺傳的概率[13]。在文中適應(yīng)值越小，則個(gè)體遺傳概率越大，適應(yīng)值越大，則個(gè)體遺傳概率越小。

2.5 選擇算子

針對本問題，選擇了輪盤賭選擇[14]從而避免了使用確定性選擇產(chǎn)生的樣本單一問題。

輪盤賭選擇的基本思想是：各個(gè)體被選中的概率與其適應(yīng)度大小成正比。具體操作方法如下：

(1)計(jì)算出種群中每個(gè)個(gè)體的適應(yīng)度f(Ci)。I取值范圍為1～n,n為種群大小。

(2)計(jì)算出每個(gè)個(gè)體被遺傳到下一代群體中的概率。

(3)計(jì)算出每個(gè)個(gè)體的累計(jì)概率。

(4)在[0,1]區(qū)間之間產(chǎn)生一個(gè)偽隨機(jī)數(shù)r。

(5)若r

(6)重復(fù)步驟4到步驟5共n次。

2.6 交叉算子

交叉運(yùn)算指的是將兩個(gè)染色體按某種規(guī)則提取相應(yīng)的部分然后按某種方式進(jìn)行交叉互換，從而產(chǎn)生兩個(gè)新的個(gè)體。交叉運(yùn)算時(shí)遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，其設(shè)計(jì)包括兩個(gè)方面[15]:①如何確定交叉基因的位置；②如何對交叉部分的基因進(jìn)行互換。

該算法采用的是雙點(diǎn)交叉。雙點(diǎn)交叉的思想：從兩組染色體的開頭到相同的位置i提取這一段基因進(jìn)行互換，再從相同的位置j到染色體結(jié)束的位置提取這一段基因進(jìn)行互換。交叉后發(fā)現(xiàn)會產(chǎn)生K值超過數(shù)據(jù)集最大個(gè)數(shù)或者比率超過額定范圍的情形，對此則重新選擇個(gè)體進(jìn)行交叉。

2.7 變異算子

變異算子是對染色體的某些基因做改動從而產(chǎn)生一串新的染色體，作用是維持種群的多樣性，避免算法過早收斂甚至無法得到全局最優(yōu)解。交叉運(yùn)算的設(shè)計(jì)包括兩個(gè)方面：①如何確定變異基因的位置；②如何對所需變異基因值進(jìn)行替換。

在此所采用的是倒位變異，即在一串染色體中隨機(jī)選取兩個(gè)位i,j,將從第i位到第j位的染色體反轉(zhuǎn)從而實(shí)現(xiàn)變異效果。對于變異后產(chǎn)生K值大于數(shù)據(jù)集個(gè)數(shù)或者比率大于額定范圍的情形，則重新選取個(gè)體變異。

2.8 遺傳算法優(yōu)化

針對過早收斂問題，根據(jù)遺傳算法的模式定理，適應(yīng)度更高的個(gè)體有更多復(fù)制的機(jī)會，因此，在種群還沒有達(dá)到最優(yōu)解時(shí)便有可能由某一當(dāng)前最優(yōu)解過早占領(lǐng)了種群的統(tǒng)治地位從而得到了局部的最優(yōu)解，但在后續(xù)種群的迭代過程中，無法最終收斂到全局最優(yōu)解。這個(gè)現(xiàn)象就稱為過早收斂。文中采用了遷移思想，在算法中設(shè)置一個(gè)變量times記錄當(dāng)前最優(yōu)解在后面的代數(shù)中保持統(tǒng)治地位的次數(shù)，當(dāng)次數(shù)達(dá)到一定的時(shí)候，保留當(dāng)前適應(yīng)度大于平均適應(yīng)度的樣本，刪除其余樣本重新組合成種群，然后繼續(xù)算法。采用遷移的想法，從一定程度上避免了過早收斂這一現(xiàn)象，在迭代次數(shù)足夠多時(shí)能夠穩(wěn)定地求出問題的最優(yōu)解。

過慢結(jié)束是指在樣本迭代到一定次數(shù)之后，整個(gè)種群已經(jīng)大部分收斂了，但還是無法穩(wěn)定收斂到全局最優(yōu)解，最優(yōu)解的適應(yīng)度與樣本平均適應(yīng)度差別不大，導(dǎo)致了無法篩選出較好的算子進(jìn)行復(fù)制操作。針對過慢結(jié)束問題，在復(fù)制算子中增加了一個(gè)函數(shù)用于判定是否出現(xiàn)了樣本的適應(yīng)度最優(yōu)值與平均值相差不大的情形，若相差小于平均適應(yīng)度的10%，則執(zhí)行放大函數(shù)，用來臨時(shí)放大種群中各個(gè)樣本的適應(yīng)值與平均值之間的差距，從而能更好地選擇出樣本進(jìn)行復(fù)制操作。

3 實(shí)驗(yàn)分析

文中數(shù)據(jù)來自于蘇州市吳中區(qū)公交數(shù)據(jù)。實(shí)驗(yàn)?zāi)康氖谴_定所有公交站點(diǎn)中的樞紐站點(diǎn)。

對實(shí)驗(yàn)數(shù)據(jù)進(jìn)行預(yù)處理之后，一共包含1 124個(gè)數(shù)據(jù)對象，每個(gè)數(shù)據(jù)對象包含了單個(gè)屬性。采用上文提及的凝聚層次聚類和K-means聚類結(jié)合改進(jìn)后的聚類算法。

K-means算法與改進(jìn)后的聚類算法的實(shí)驗(yàn)結(jié)果見表1。遺傳算法確定K值的實(shí)驗(yàn)結(jié)果見表2。

表1 K-means算法與改進(jìn)算法

表1中K值由均方根方法確定。從表1可以看出改進(jìn)后的算法比較改進(jìn)之前，以輪廓系數(shù)作為評價(jià)依據(jù)有了較明顯的提升。

表2 遺傳算法設(shè)計(jì)K值

從表2可以看出使用遺傳算法設(shè)置改進(jìn)聚類算法的K值，以輪廓系數(shù)為依據(jù)，可行度較高。

通過文中的研究可以得出以下結(jié)論：

(1)在樞紐站點(diǎn)確定的問題中，將K-means算法與凝聚層次聚類算法相結(jié)合，其聚類效果相比于單一算法有了很好的提升。

(2)使用遺傳算法來設(shè)置K值，達(dá)到了較優(yōu)解的效果，種群中的最優(yōu)個(gè)體的輪廓系數(shù)與采用均方根的效果差距較小。

(3)與目前已經(jīng)規(guī)劃的公交樞紐站點(diǎn)相比，本實(shí)驗(yàn)結(jié)果又通過對數(shù)據(jù)的分析，列出了潛在的公交樞紐站點(diǎn)，同時(shí)對于各個(gè)公交站點(diǎn)流量進(jìn)行了分析，為公交樞紐站點(diǎn)的二次規(guī)劃提供了有效的數(shù)據(jù)支持。

4 結(jié)束語

針對城市交通規(guī)劃中樞紐站點(diǎn)確定的問題，提出了使用改進(jìn)的基于K-means的凝聚層次聚類算法對公交數(shù)據(jù)進(jìn)行處理；同時(shí)為得到更優(yōu)的聚類結(jié)果，有別于傳統(tǒng)確定類簇?cái)?shù)K的方法，使用遺傳算法確定K-means算法與層次聚類算法結(jié)合時(shí)的類簇?cái)?shù)以及兩個(gè)類簇?cái)?shù)之間的關(guān)系。通過實(shí)驗(yàn)表明，使用改進(jìn)的聚類算法確定樞紐站點(diǎn)為公交樞紐站點(diǎn)二次規(guī)劃提供了可靠的數(shù)據(jù)支持，并且使用遺傳算法改進(jìn)的聚類算法的聚類效果有了較好的提升。