陳嘉輝，譚曉軍，呂 威

（1.中山大學智能工程學院，廣州 510275；2.吉林大學珠海學院阿里云大數據應用學院，廣東珠海 519041）

0 引言

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

1 聚類分析概述

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

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

對數據集進行的聚類分析主要遵循兩個步驟：第一步是選取某一種相似性度量方法，將信息集按照每個子信息之間的相似度來進行信息集的分類處理，將其中相似度較高的子信息聚集起來，構成一個信息子集；第二步是構建準則函數，其用來評價聚類分析的結果的好壞.使用準則函數來對第一步所構成的數據集合進行度量，用以評測聚類分析的結果.

2 幾種聚類算法概述

基于聚類算法的研究層出不窮，在各類文獻中所使用的聚類方法也有很多.而在實踐中，使用聚類算法，則要根據需處理信息集的種類，希望得到的聚類結果和所處理信息集涉及到的學科領域來使用不同種類的聚類算法.目前，聚類算法大致分為基于劃分的聚類算法、基于層次的聚類算法、基于密度的聚類算法、基于網格的聚類算法以及基于模型的聚類算法.

2.1 基于劃分的聚類算法

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

2.2 基于層次的聚類算法

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

2.3 基于密度的聚類算法

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

2.4 基于網格的聚類算法

基于網格的聚類算法和基于密度的聚類算法具有一定的相似性，這種方法會將信息集S 進行網格化的劃分，將信息集劃分成N 個網格，之后再在每個網格上對信息集進行聚類操作.

2.5 基于模型的聚類算法

基于模型的聚類算法需要先構造某種數學模型，再將數據集S 在該模型上進行擬合，從而自動將信息集S 劃分為k 個信息子集，從而得到信息集的聚類.

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

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

k-means 算法的目標函數為：

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

（1）根據用戶輸入的參數k（類簇數目）的值，隨機地在將要聚類的數據集合中選擇k 個數據對象作為初始的聚類中心.

（2）遍歷數據集合中的每一個數據對象，根據相似度來決定每一個數據對象應該分配到哪個類簇中.相似度一般用數據對象到類簇中心的歐氏距離來度量.歐式距離越小，說明該數據對象和該簇的相似度越大，將每個數據對象分配到最大相似度的簇中.

（3）重新計算每一個類簇的中心點，將每一個類簇的所有數據對象的平均值作為新的類簇中心點，重復執(zhí)行（1）和（2），直至聚類結果評價函數式收斂為止.

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

3 實驗環(huán)節(jié)

3.1 數據預處理

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

3.1.1 數據審核

從不同渠道取得的數據，其審核的內容和方法也略有不同.在這里我們對收集到的路口數據從完整性和準確性兩個方面來審核.

（1）完整性審核主要是檢查應調查的單位或個體是否有遺漏，所有的調查項目或指標是否填寫齊全.

（2）準確性審核主要是包括兩個方面：一是檢查數據資料是否真實地反映了客觀實際情況，內容是否符合實際；二是檢查數據是否有錯誤，計算是否正確等.審核數據準確性的方法主要有邏輯檢查和計算檢查.邏輯檢查主要是審核數據是否符合邏輯，內容是否合理，各項目或數字之間有無相互矛盾的現象，此方法主要適合對定性（品質）數據的審核.計算檢查是檢查調查表中的各項數據在計算結果和計算方法上有無錯誤，主要用于對定量（數值型）數據的審核.

3.1.2 數據篩選

對審核過程中發(fā)現的錯誤應盡可能予以糾正.調查結束后，當發(fā)現的錯誤數據不能予以糾正，或者有些數據不符合調查的要求而又無法彌補時，就需要對數據進行篩選.

數據篩選主要包括以下兩方面的內容：

（1）將某些不符合要求的數據或有明顯錯誤的數據予以剔除；

（2）將符合某種特定條件的數據篩選出來，對不符合特定條件的數據予以剔除.

3.1.3 去除唯一屬性

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

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

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

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

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

在這里我們使用均值插補法對樣本數據的缺失值進行補全，對于某一屬性的缺失值我們使用該屬性有效的平均值來插補缺失值.

3.1.4 數據標準化

為了消除具有不同量級的屬性對聚類算法的效果產生負面影響，我們需要將路口數據進行標準化變換.數據標準化是將樣本的屬性縮放到某個指定的范圍.

（1）數量級的差異將導致量級較大的屬性占據主導地位；

（2）數量級的差異將導致迭代收斂速度減慢；

（3）依賴于樣本距離的算法對于數據的數量級非常敏感.

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

新數據=（原數據-最小值）/（最大值-最小值）

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

3.2 k-means 聚類

經過數據預處理之后的數據如表1 所示（取路口臺賬模具表數據前九條作為展示）.

表1 路口預處理數據

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

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

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

我們對預處理后Excel 中的數據利用手肘法選取最佳聚類數k.具體做法是讓k 從5 開始取值，直到取到我們認為的k 值的上限50（一般來說這個上限不會太大，這里我們選取上限為50），對每一個k 值進行聚類并且記下對于的SSE 值；最后選取肘部對應的k 作為我們的最佳聚類數，即對應的SSE值最小的點所對應的k 的取值，也就是我們所需要確定的k-means 算法中的k 值.在經過實驗分析后我們得出：當k 值取得29 時，能夠得到最小的SSE 值.即對于該數據集而言，最佳聚類數應為29.然后我們將聚類之后的每類的標簽添加到經過預處理之后的數據表中，這樣我們就得到了將路口數據聚為29 個類的數據表示形式.部分聚類之后的數據見表2.

表2 部分聚類之后的數據

4 總結

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