基于聚類算法的路口相似度匹配算法的優(yōu)化與實現(xiàn)

陳嘉輝，譚曉軍，呂 威

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

0 引言

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

1 聚類分析概述

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

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

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

2 幾種聚類算法概述

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

2.1 基于劃分的聚類算法

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

2.2 基于層次的聚類算法

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

2.3 基于密度的聚類算法

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

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

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

2.5 基于模型的聚類算法

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

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

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

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

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

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

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

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

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

3 實驗環(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)容和方法也略有不同.在這里我們對收集到的路口數(shù)據(jù)從完整性和準(zhǔn)確性兩個方面來審核.

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

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

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

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

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

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

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

3.1.3 去除唯一屬性

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 k-means 聚類

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

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

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

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

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

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

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

4 總結(jié)

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