陳嘉輝，譚曉軍，呂 威

（1.中山大學(xué)智能工程學(xué)院，廣州 510275；2.吉林大學(xué)珠海學(xué)院阿里云大數(shù)據(jù)應(yīng)用學(xué)院，廣東珠海 519041）

0 引言

隨著國(guó)民經(jīng)濟(jì)的快速發(fā)展，我國(guó)的汽車保有量逐年增加，隨之而來(lái)的城市交通擁堵問(wèn)題日益嚴(yán)重，影響人們的日常出行，給城市居民的日常生活造成了很大的不便.同時(shí)，交通擁堵問(wèn)題還會(huì)嚴(yán)重影響交通運(yùn)輸行業(yè)的運(yùn)輸效率，對(duì)國(guó)民經(jīng)濟(jì)的發(fā)展產(chǎn)生不好的影響.我們希望通過(guò)對(duì)已經(jīng)收集到的交通路口的數(shù)據(jù)作為信息來(lái)源，對(duì)收集到的交通路口數(shù)據(jù)通過(guò)無(wú)監(jiān)督的機(jī)器學(xué)習(xí)算法進(jìn)行聚類，發(fā)現(xiàn)不同交通路口之間的內(nèi)在聯(lián)系，以期在后續(xù)的交通治堵的過(guò)程中，可以借鑒通過(guò)聚類算法聚合到同一類別的相似的交通路口的治堵經(jīng)驗(yàn)，來(lái)指導(dǎo)相關(guān)技術(shù)人員，快速地找出擁堵的原因，并制定出合理、可行的交通治堵方案.

1 聚類分析概述

當(dāng)今世界，計(jì)算機(jī)科學(xué)在各行各業(yè)中都有著廣泛的應(yīng)用.而伴隨信息時(shí)代的到來(lái)，數(shù)據(jù)量呈現(xiàn)指數(shù)型增長(zhǎng)，不可避免地需要收集、分析、處理數(shù)據(jù)，大量的數(shù)據(jù)在商業(yè)、民生、各個(gè)學(xué)科以及各領(lǐng)域不斷地涌現(xiàn).伴隨著計(jì)算機(jī)科學(xué)的發(fā)展以及普及，數(shù)據(jù)的處理有了更加先進(jìn)的方法，傳統(tǒng)的數(shù)據(jù)處理方法已經(jīng)不能達(dá)到各個(gè)領(lǐng)域的需求，人工數(shù)據(jù)處理方法已經(jīng)被淘汰，而數(shù)據(jù)挖掘、數(shù)控分析技術(shù)在不斷的崛起.

聚類分析(Clustering analysis)是處理數(shù)據(jù)的重要方法.它是一種可以研究數(shù)據(jù)集的近似程度的一種方法，可分為聚類和分析兩個(gè)部分來(lái)理解，其中聚類則是利用物以類聚的方式，將大量的信息根據(jù)它們之間的相似性來(lái)分成若干組信息集，而分析則是對(duì)這些組信息集進(jìn)行分析和理解.當(dāng)然，聚類分析屬于無(wú)監(jiān)督的模式識(shí)別方法[1]，聚類在沒(méi)有任何先驗(yàn)信息條件下，對(duì)現(xiàn)有的無(wú)標(biāo)記數(shù)據(jù)進(jìn)行歸類，類別歸屬標(biāo)志在聚類分析處理的數(shù)據(jù)集中是不存在的[2].通過(guò)進(jìn)行數(shù)據(jù)的聚類分析，便可以將原有的看似不相關(guān)的海量數(shù)據(jù)集劃分為若干組差異度較大的數(shù)據(jù)集，其中每組數(shù)據(jù)集所包含的數(shù)據(jù)都具有一定的相關(guān)性.聚類技術(shù)已經(jīng)廣泛應(yīng)用于商業(yè)、工業(yè)、人文科技等各個(gè)領(lǐng)域[3]，如對(duì)商業(yè)的數(shù)據(jù)分析、醫(yī)療層面的數(shù)據(jù)分析、教育知識(shí)的數(shù)據(jù)分析以及交通數(shù)據(jù)的分析.

對(duì)數(shù)據(jù)集進(jìn)行的聚類分析主要遵循兩個(gè)步驟：第一步是選取某一種相似性度量方法，將信息集按照每個(gè)子信息之間的相似度來(lái)進(jìn)行信息集的分類處理，將其中相似度較高的子信息聚集起來(lái)，構(gòu)成一個(gè)信息子集；第二步是構(gòu)建準(zhǔn)則函數(shù)，其用來(lái)評(píng)價(jià)聚類分析的結(jié)果的好壞.使用準(zhǔn)則函數(shù)來(lái)對(duì)第一步所構(gòu)成的數(shù)據(jù)集合進(jìn)行度量，用以評(píng)測(cè)聚類分析的結(jié)果.

2 幾種聚類算法概述

基于聚類算法的研究層出不窮，在各類文獻(xiàn)中所使用的聚類方法也有很多.而在實(shí)踐中，使用聚類算法，則要根據(jù)需處理信息集的種類，希望得到的聚類結(jié)果和所處理信息集涉及到的學(xué)科領(lǐng)域來(lái)使用不同種類的聚類算法.目前，聚類算法大致分為基于劃分的聚類算法、基于層次的聚類算法、基于密度的聚類算法、基于網(wǎng)格的聚類算法以及基于模型的聚類算法.

2.1 基于劃分的聚類算法

使用基于劃分的聚類算法，一般需要先設(shè)定信息子集的劃分個(gè)數(shù)k，即將原有信息集合S 劃分為k 組，對(duì)于每組的信息子集pn，信息子集中的子信息{t1，t2，t3，…，tn}都是依據(jù)某種相似度度量來(lái)進(jìn)行劃分的，每個(gè)子信息都是具有相似度的個(gè)體；然后需要對(duì)所劃分出的信息子集進(jìn)行迭代，對(duì)于信息子集中的每個(gè)子信息tn，在迭代收斂時(shí)要保證其在正確的信息子集中.目前k-means 算法以及k-medoids 算法應(yīng)用最為廣泛.

2.2 基于層次的聚類算法

基于層次的聚類算法是對(duì)已有的信息集S進(jìn)行層次的分解的一種動(dòng)態(tài)規(guī)劃方法.在迭代結(jié)束后，信息集S 會(huì)被分解成K 層，每層信息集都是一類相似子集.基于層次的聚類算法主要分為自底向上分層和自頂向下分層.其中自底向上的方法稱為凝聚層次算法，該種方法開(kāi)始時(shí)會(huì)將信息集S 中的每個(gè)子信息{t1，t2，t3，…，tn}都當(dāng)作一個(gè)信息子集pn，之后再對(duì)每個(gè)信息子集pn按照一定條件進(jìn)行合并，直到滿足終止條件.自頂向下的方法稱為分裂層次聚類，這種方法開(kāi)始時(shí)會(huì)將整個(gè)信息集S 視為一個(gè)信息子集p1，之后再不斷對(duì)信息子集p1進(jìn)行迭代，信息子集p1最終會(huì)被分解為信息子集{p1，p2，p3，…，pn}.

2.3 基于密度的聚類算法

基于密度的聚類算法一般會(huì)劃分出幾個(gè)區(qū)域，而后以信息集S 中每個(gè)子信息按照信息在每個(gè)區(qū)域的密度進(jìn)行聚類.這是利用信息的分布，將信息域連接到一起的一種方法.但這種方法在稀疏型信息集上的應(yīng)用不理想.

2.4 基于網(wǎng)格的聚類算法

基于網(wǎng)格的聚類算法和基于密度的聚類算法具有一定的相似性，這種方法會(huì)將信息集S 進(jìn)行網(wǎng)格化的劃分，將信息集劃分成N 個(gè)網(wǎng)格，之后再在每個(gè)網(wǎng)格上對(duì)信息集進(jìn)行聚類操作.

2.5 基于模型的聚類算法

基于模型的聚類算法需要先構(gòu)造某種數(shù)學(xué)模型，再將數(shù)據(jù)集S 在該模型上進(jìn)行擬合，從而自動(dòng)將信息集S 劃分為k 個(gè)信息子集，從而得到信息集的聚類.

經(jīng)典聚類算法各有優(yōu)缺點(diǎn)，為了將不同算法的優(yōu)點(diǎn)相結(jié)合，提出了集成聚類算法；當(dāng)數(shù)據(jù)集維度較高時(shí)，為了進(jìn)一步提升算法效率和減小存儲(chǔ)空間，必須對(duì)數(shù)據(jù)集進(jìn)行降維處理.具體而言，聚類有效性函數(shù)部分研究了誤差平方和、Calinski-Harabasz、Davies-Bouldin這三種有效性指標(biāo)，并比較了它們對(duì)實(shí)際數(shù)據(jù)集聚類結(jié)果的評(píng)估效果.

劃分聚類可以分為硬劃分算法k-means 和模糊劃分算法FCM（fuzzy c-means）.

k-means 算法的目標(biāo)函數(shù)為：

k-means 算法是聚類分析中最常用的算法之一，該算法的執(zhí)行流程如下：

（1）根據(jù)用戶輸入的參數(shù)k（類簇?cái)?shù)目）的值，隨機(jī)地在將要聚類的數(shù)據(jù)集合中選擇k 個(gè)數(shù)據(jù)對(duì)象作為初始的聚類中心.

（2）遍歷數(shù)據(jù)集合中的每一個(gè)數(shù)據(jù)對(duì)象，根據(jù)相似度來(lái)決定每一個(gè)數(shù)據(jù)對(duì)象應(yīng)該分配到哪個(gè)類簇中.相似度一般用數(shù)據(jù)對(duì)象到類簇中心的歐氏距離來(lái)度量.歐式距離越小，說(shuō)明該數(shù)據(jù)對(duì)象和該簇的相似度越大，將每個(gè)數(shù)據(jù)對(duì)象分配到最大相似度的簇中.

（3）重新計(jì)算每一個(gè)類簇的中心點(diǎn)，將每一個(gè)類簇的所有數(shù)據(jù)對(duì)象的平均值作為新的類簇中心點(diǎn)，重復(fù)執(zhí)行（1）和（2），直至聚類結(jié)果評(píng)價(jià)函數(shù)式收斂為止.

鑒于所收集到的城市交通路網(wǎng)的路口的數(shù)據(jù)的連續(xù)性的特點(diǎn)，選取了k-means 來(lái)作為我們對(duì)交通路口進(jìn)行聚類的算法.由于收集到的路口數(shù)據(jù)存在不完整以及不一致的臟數(shù)據(jù)，在對(duì)城市路口數(shù)據(jù)進(jìn)行聚類之前我們需要先對(duì)已有的數(shù)據(jù)進(jìn)行預(yù)處理來(lái)對(duì)缺失數(shù)據(jù)進(jìn)行補(bǔ)充和對(duì)錯(cuò)誤數(shù)據(jù)進(jìn)行刪除.數(shù)據(jù)預(yù)處理（data pre-processing）是指在主要的處理以前對(duì)數(shù)據(jù)進(jìn)行的一些處理.現(xiàn)實(shí)世界中數(shù)據(jù)大體上都是不完整、不一致的臟數(shù)據(jù)，無(wú)法直接進(jìn)行數(shù)據(jù)挖掘，或挖掘結(jié)果差強(qiáng)人意.為了提高數(shù)據(jù)挖掘的質(zhì)量產(chǎn)生了數(shù)據(jù)預(yù)處理技術(shù).數(shù)據(jù)預(yù)處理在數(shù)據(jù)挖掘之前使用，大大提高了數(shù)據(jù)挖掘模式的質(zhì)量，降低實(shí)際挖掘所需要的時(shí)間.經(jīng)過(guò)預(yù)處理之后的數(shù)據(jù)會(huì)對(duì)我們所采取的算法具有更好的適應(yīng)性，能夠得到更好的聚類效果.

3 實(shí)驗(yàn)環(huán)節(jié)

3.1 數(shù)據(jù)預(yù)處理

數(shù)據(jù)預(yù)處理主要包括數(shù)據(jù)審核、數(shù)據(jù)篩選、去除唯一屬性、處理缺失值、數(shù)據(jù)標(biāo)準(zhǔn)化等環(huán)節(jié).

3.1.1 數(shù)據(jù)審核

從不同渠道取得的數(shù)據(jù)，其審核的內(nèi)容和方法也略有不同.在這里我們對(duì)收集到的路口數(shù)據(jù)從完整性和準(zhǔn)確性兩個(gè)方面來(lái)審核.

（1）完整性審核主要是檢查應(yīng)調(diào)查的單位或個(gè)體是否有遺漏，所有的調(diào)查項(xiàng)目或指標(biāo)是否填寫(xiě)齊全.

（2）準(zhǔn)確性審核主要是包括兩個(gè)方面：一是檢查數(shù)據(jù)資料是否真實(shí)地反映了客觀實(shí)際情況，內(nèi)容是否符合實(shí)際；二是檢查數(shù)據(jù)是否有錯(cuò)誤，計(jì)算是否正確等.審核數(shù)據(jù)準(zhǔn)確性的方法主要有邏輯檢查和計(jì)算檢查.邏輯檢查主要是審核數(shù)據(jù)是否符合邏輯，內(nèi)容是否合理，各項(xiàng)目或數(shù)字之間有無(wú)相互矛盾的現(xiàn)象，此方法主要適合對(duì)定性（品質(zhì)）數(shù)據(jù)的審核.計(jì)算檢查是檢查調(diào)查表中的各項(xiàng)數(shù)據(jù)在計(jì)算結(jié)果和計(jì)算方法上有無(wú)錯(cuò)誤，主要用于對(duì)定量（數(shù)值型）數(shù)據(jù)的審核.

3.1.2 數(shù)據(jù)篩選

對(duì)審核過(guò)程中發(fā)現(xiàn)的錯(cuò)誤應(yīng)盡可能予以糾正.調(diào)查結(jié)束后，當(dāng)發(fā)現(xiàn)的錯(cuò)誤數(shù)據(jù)不能予以糾正，或者有些數(shù)據(jù)不符合調(diào)查的要求而又無(wú)法彌補(bǔ)時(shí)，就需要對(duì)數(shù)據(jù)進(jìn)行篩選.

數(shù)據(jù)篩選主要包括以下兩方面的內(nèi)容：

（1）將某些不符合要求的數(shù)據(jù)或有明顯錯(cuò)誤的數(shù)據(jù)予以剔除；

（2）將符合某種特定條件的數(shù)據(jù)篩選出來(lái)，對(duì)不符合特定條件的數(shù)據(jù)予以剔除.

3.1.3 去除唯一屬性

在交通路口數(shù)據(jù)中，唯一屬性指的是路口的ID 屬性，這些屬性并不能刻畫(huà)樣本自身的分布規(guī)律，所以簡(jiǎn)單的刪除這些屬性即可，因而需要進(jìn)行缺失值處理.

缺失值處理通常使用以下三種方法:

（1）直接使用含有缺失值的特征；

（2）刪除含有缺失值的特征（該方法在包含缺失值的屬性含有大量缺失值而僅僅包含極少量有效值時(shí)是有效的）；

（3）缺失值補(bǔ)全(均值插補(bǔ)、同類均值插補(bǔ)、建模預(yù)測(cè)、高維映射、多重插補(bǔ)、極大似然估計(jì)、壓縮感知和矩陣補(bǔ)全).

在這里我們使用均值插補(bǔ)法對(duì)樣本數(shù)據(jù)的缺失值進(jìn)行補(bǔ)全，對(duì)于某一屬性的缺失值我們使用該屬性有效的平均值來(lái)插補(bǔ)缺失值.

3.1.4 數(shù)據(jù)標(biāo)準(zhǔn)化

為了消除具有不同量級(jí)的屬性對(duì)聚類算法的效果產(chǎn)生負(fù)面影響，我們需要將路口數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化變換.數(shù)據(jù)標(biāo)準(zhǔn)化是將樣本的屬性縮放到某個(gè)指定的范圍.

（1）數(shù)量級(jí)的差異將導(dǎo)致量級(jí)較大的屬性占據(jù)主導(dǎo)地位；

（2）數(shù)量級(jí)的差異將導(dǎo)致迭代收斂速度減慢；

（3）依賴于樣本距離的算法對(duì)于數(shù)據(jù)的數(shù)量級(jí)非常敏感.

我們對(duì)路口數(shù)據(jù)進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化所采取的方法為min-max 標(biāo)準(zhǔn)化（歸一化）：對(duì)于部分屬性，設(shè)minA 和maxA 分別為屬性A 的最小值和最大值，將A 的一個(gè)原始值x 通過(guò)min-max 標(biāo)準(zhǔn)化映射成在區(qū)間[0，1]中的值x′，其公式為：

新數(shù)據(jù)=（原數(shù)據(jù)-最小值）/（最大值-最小值）

在我們的路口臺(tái)賬模具表里，屬性X、屬性Y 做了歸一化處理.

3.2 k-means 聚類

經(jīng)過(guò)數(shù)據(jù)預(yù)處理之后的數(shù)據(jù)如表1 所示（取路口臺(tái)賬模具表數(shù)據(jù)前九條作為展示）.

表1 路口預(yù)處理數(shù)據(jù)

對(duì)于k-means 算法來(lái)說(shuō)，k 值的確定對(duì)于該聚類算法來(lái)說(shuō)是最重要的環(huán)節(jié).根據(jù)行業(yè)經(jīng)驗(yàn)確定的聚類數(shù)過(guò)多并且并不一定是我們獲取到數(shù)據(jù)的真實(shí)聚類數(shù)，所以，我們希望能從數(shù)據(jù)自身出發(fā)去確定真實(shí)的聚類數(shù)，也就是對(duì)數(shù)據(jù)而言的最佳聚類數(shù).在此我們利用手肘法來(lái)確定k-means 聚類算法中k 值的選取.手肘法的核心指標(biāo)是SSE（sum of the squared errors，誤差平方和）

其中，Ci是第i 個(gè)簇，P 是Ci中的樣本點(diǎn)，mi是Ci的質(zhì)心（Ci中所有樣本的均值），SSE 是所有樣本的聚類誤差，代表了聚類效果的好壞.

手肘法的核心思想是：隨著聚類數(shù)k 的增大，樣本劃分會(huì)更加精細(xì)，每個(gè)簇的聚合程度會(huì)逐漸提高，那么誤差平方和SSE 自然會(huì)逐漸變小.并且，當(dāng)k 小于真實(shí)聚類數(shù)時(shí)，由于k 的增大會(huì)大幅增加每個(gè)簇的聚合程度，故SSE 的下降幅度會(huì)很大，而當(dāng)k 到達(dá)真實(shí)聚類數(shù)時(shí)，再增加k 所得到的聚合程度回報(bào)會(huì)迅速變小，所以SSE 的下降幅度會(huì)驟減，然后隨著k 值的繼續(xù)增大而趨于平緩，也就是說(shuō)SSE 和k 的關(guān)系圖是一個(gè)手肘的形狀，而這個(gè)肘部對(duì)應(yīng)的k值就是數(shù)據(jù)的真實(shí)聚類數(shù).

我們對(duì)預(yù)處理后Excel 中的數(shù)據(jù)利用手肘法選取最佳聚類數(shù)k.具體做法是讓k 從5 開(kāi)始取值，直到取到我們認(rèn)為的k 值的上限50（一般來(lái)說(shuō)這個(gè)上限不會(huì)太大，這里我們選取上限為50），對(duì)每一個(gè)k 值進(jìn)行聚類并且記下對(duì)于的SSE 值；最后選取肘部對(duì)應(yīng)的k 作為我們的最佳聚類數(shù)，即對(duì)應(yīng)的SSE值最小的點(diǎn)所對(duì)應(yīng)的k 的取值，也就是我們所需要確定的k-means 算法中的k 值.在經(jīng)過(guò)實(shí)驗(yàn)分析后我們得出：當(dāng)k 值取得29 時(shí)，能夠得到最小的SSE 值.即對(duì)于該數(shù)據(jù)集而言，最佳聚類數(shù)應(yīng)為29.然后我們將聚類之后的每類的標(biāo)簽添加到經(jīng)過(guò)預(yù)處理之后的數(shù)據(jù)表中，這樣我們就得到了將路口數(shù)據(jù)聚為29 個(gè)類的數(shù)據(jù)表示形式.部分聚類之后的數(shù)據(jù)見(jiàn)表2.

表2 部分聚類之后的數(shù)據(jù)

4 總結(jié)

通過(guò)對(duì)收集到的城市交通路網(wǎng)的路口數(shù)據(jù)進(jìn)行聚類分析，我們將收集到的不同的路口數(shù)據(jù)聚為29 簇（實(shí)驗(yàn)證明當(dāng)k=29 時(shí)，k-means 具有給定范圍內(nèi)的最小的SSE 值）.當(dāng)將城市相似度較高的路口進(jìn)行聚合之后，給相同或者相似的路口打上相同的標(biāo)簽；當(dāng)再有新的路口存在交通擁堵的問(wèn)題時(shí)，我們便可以在相同的簇中找到同簇路口以往的交通治堵經(jīng)驗(yàn)以供參考，用來(lái)給相關(guān)的專業(yè)人員快速的確定城市交通路網(wǎng)中不同類型的路口擁堵問(wèn)題提供治堵方案.