一種改進的K-means算法在城市通勤研究中的應(yīng)用

周天綺 楊志民

1(浙江醫(yī)藥高等專科學(xué)校醫(yī)療器械學(xué)院 浙江 寧波 315100)2(浙江工業(yè)大學(xué)之江學(xué)院 浙江 杭州 310024)

0 引 言

通勤指的是從業(yè)人員離開居住地前往工作地的出行活動，可反映一個城市中勞動力的活動半徑[1]。通勤發(fā)生于就業(yè)人口中，受職住空間分布結(jié)構(gòu)的影響。通過聚類分析居住與就業(yè)集聚地可以描繪出城市居民出行的時空特性，統(tǒng)計空間單元的通勤屬性，由此反映城市的空間結(jié)構(gòu)[1]。

1 算法設(shè)計

K-means聚類算法是屬于劃分方法中的基于質(zhì)心技術(shù)的一種方法。劃分的思路是以k為參數(shù)，把n個數(shù)據(jù)樣本劃分為k個類，以使生成的每個聚類(又稱簇)類內(nèi)緊湊，類間獨立。

1.1 聚類性能評價

聚類是根據(jù)數(shù)據(jù)對象之間的相似程度來劃分類的，相似程度是用對象之間的距離來衡量的，一般采用的是歐式距離。假設(shè)給定的數(shù)據(jù)集X={xm|m=1,2,…,ntotal}，X中的樣本有d個屬性(維度)A1，A2，…，Ad[3]，則歐式距離公式如下：

(1)

d(xi,xj)距離越小，樣本xi和xj越相似，差異度越小[3]；反之，樣本xi和xj越不相似，差異度越大[3]。

K-means聚類算法使用誤差平方和準則函數(shù)來評價聚類性能[3]。給定數(shù)據(jù)集X，包含k個聚類子集X1，X2，…，Xk[4]；各個聚類子集的質(zhì)心分別為m1，m2,…,mk。誤差平方和準則函數(shù)公式為[4]：

(2)

E函數(shù)表示每個樣本點到其質(zhì)心的距離平方和[4]。算法需將E調(diào)整到最小使各聚類達到最優(yōu)。

1.2 算法流程

K-means聚類算法具體流程如下：

輸入：簇的數(shù)目k和包含m個數(shù)據(jù)樣本的數(shù)據(jù)集X={xm|m=1,2,…,ntotal}，每個xi∈Rd，d為數(shù)據(jù)緯度。

輸出：k個簇C1，C2，…，Ck， 使平方誤差準則最小。

① 隨機選取k個聚類質(zhì)心：m1，m2，…，mk[5]。

② 重復(fù)下面過程直到收斂[5]。

{

對于每一個樣例xi，按下式計算其應(yīng)該屬于的類[5]：

(3)

對于每一個類j，按下式重新計算該類的質(zhì)心:

(4)

}

k是預(yù)先選定的聚類數(shù)，ci代表樣例xi到k個類的質(zhì)心距離最近的那個類。mj為一個類的質(zhì)心，其初始值是隨機選取的。算法過程描述如下：① 在數(shù)據(jù)集中隨機選取k個對象作為k個類的質(zhì)心；② 對于數(shù)據(jù)集中的每個對象分別計算其到k個質(zhì)心點的距離，然后選取距離最近的那個類作為ci，這樣每一個對象都有歸屬的類[6]；③ 對于每一個聚類，對類中所有的數(shù)據(jù)點求均值，重新計算它的質(zhì)心mj；④ 重復(fù)迭代②和③直到質(zhì)心不變。

1.3 算法缺點

對處理大數(shù)據(jù)集來說，K-means算法是相對可伸縮和高效率的。但缺點也比較明顯：

(1) 必須事先設(shè)定k值，而且對聚類質(zhì)心的初始值敏感，對于不同的初始值，可能會導(dǎo)致不同的聚類結(jié)果，經(jīng)常會發(fā)生得到局部最優(yōu)解的情況。

(2) 對于“躁聲”和孤立點數(shù)據(jù)是敏感的，少量的該類數(shù)據(jù)就能對聚類質(zhì)心和聚類結(jié)果產(chǎn)生極大的影響[8]。

1.4 算法改進

1.4.1 采用類間相異度確定k值

利用類間相異度來確定最終的k值。思路如下：① 初始化聚類質(zhì)心：計算所有樣本的平均值作為數(shù)據(jù)集的中間點m0，利用歐式距離公式找出距離中間點m0最遠的對象m1，再找出與m1距離最遠的對象m2，選取m0、m1、m2作為初始聚類的質(zhì)心。② 計算其他對象到每一個質(zhì)心點的距離，取最小距離D，計算質(zhì)心點之間的距離，取最小距離C，如果D

類間相異度DCA計算公式如下：

(5)

式中：kt表示當前聚類的個數(shù)，mi、mj分別為類Ci和Cj的質(zhì)心,d(mi,mj)表示類Ci和Cj的歐式距離。

改進后的算法描述如下：

(2) 計算剩余對象到各質(zhì)心的歐式距離，選擇距離最近的質(zhì)心歸類，重新計算各聚類質(zhì)心。

(3) 計算剩余對象到質(zhì)心的最小距離D及質(zhì)心之間的最小距離C，并計算出類間相異度DCA_o。

(4) 如果D>C，則把該對象作為備選質(zhì)心點，重新計算類間相異度DCA_n，運行步驟(5)，否則轉(zhuǎn)到步驟(6)。

(5) 如果DCA_n>DCA_o，則把該對象作為新的質(zhì)心，生成新類，此時k=k+1,重復(fù)迭代步驟(2)-步驟(5)，否則保持原態(tài)，執(zhí)行步驟(6)。

(6) 取下一個類Ci，如果沒有新的類，轉(zhuǎn)到步驟(7)，否則重復(fù)迭代步驟(2)-步驟(5)。

(7) 輸出各個聚類：C1，C2，…，Ck。

1.4.2 消除噪聲和孤立點的影響

通過改進原始算法找出數(shù)據(jù)集中的噪聲和孤立點進行消除。對于數(shù)據(jù)集X={xm|m=1,2,…,ntotal}中的每一個對象xi，計算其與剩余對象的距離和Si，另外計算出所有對象的距離均和H，如果Si>H，則xi被認為是孤立點，予以刪除。公式如下：

(6)

(7)

2 實 驗

2.1 數(shù)據(jù)準備

本次實驗數(shù)據(jù)選取杭州移動公司提供的手機通信數(shù)據(jù)。按照觸發(fā)手機定位的方式，手機定位數(shù)據(jù)可分為主動方式(主叫、被叫、短信、位置區(qū)切換)和被動方式(定時掃描)[9]。被動方式是GSM通信系統(tǒng)通過定時掃描周期性地更新手機用戶的位置信息[9]。由于被動方式觸發(fā)周期約為55 min，具有獲取數(shù)據(jù)完整且穩(wěn)定的優(yōu)點[9]，本次研究采用被動方式觸發(fā)的手機定位數(shù)據(jù)。

首先需要對數(shù)據(jù)進行清洗，刪除無效和冗余數(shù)據(jù)。其次，還需刪除手機號碼等用戶私密信息，用戶ID可采用加密后的IMSI號表示[10]。數(shù)據(jù)預(yù)處理流程如下：

(1) 從原始數(shù)據(jù)中提取被動方式觸發(fā)的手機定位數(shù)據(jù)，包括定位的時間和位置信息(經(jīng)緯度坐標)。

(2) 分別建立工作時段和夜間睡眠時段的手機定位信息數(shù)據(jù)表。設(shè)置工作和夜間睡眠時段，根據(jù)居民作息時間，設(shè)置工作時段為09:00-17:00，睡眠時段為23:00-次日06:00。篩選出相應(yīng)時段的手機定位數(shù)據(jù)存入對應(yīng)的數(shù)據(jù)表。

經(jīng)處理后的手機定位數(shù)據(jù)表格式如表1所示。

表1 手機定位數(shù)據(jù)表格式

2.2 實驗環(huán)境

本次實驗采用python語言分別實現(xiàn)K-means算法和改進后的K-means算法。在相同的實驗環(huán)境下對兩種算法在職住錨點分析中的聚類效果和運行效率進行分析比對。具體實驗環(huán)境：Arch Linux+ArcGIS 10.5.1+Python 3.7+Pycharm+Matplot。

為了客觀比較兩種算法的性能，從工作時段的手機定位數(shù)據(jù)表中隨機選取100個定位點進行工作地錨點聚類實驗，將手機定位數(shù)據(jù)映射到杭州市行政區(qū)劃圖，具體數(shù)據(jù)點分布如圖1所示。

圖1 測試數(shù)據(jù)分布

2.3 算法比較

2.3.1 K-means算法實驗分析

K-means算法需要預(yù)先設(shè)定k值，實驗中k取4，即隨機選取4個質(zhì)心點。整個聚類過程如圖2所示。圖中每一種顏色代表一個簇，圓點表示樣本點，代表手機用戶所在的位置；正方形表示聚類質(zhì)心，代表工作點錨點。

K-means算法經(jīng)過8次迭代實現(xiàn)收斂。由于聚類質(zhì)心是隨機選擇的，陷入局部最優(yōu)的概率較大。圖2中第一次迭代初始質(zhì)心選在了同一個類中，導(dǎo)致迭代次數(shù)過多，甚至可能因出現(xiàn)局部最優(yōu)導(dǎo)致錯誤的聚類，這是K-means算法中比較明顯的缺點。

噪聲點影響分析：由于K-means算法不能識別噪聲點，少量的噪聲點就能使聚類質(zhì)心產(chǎn)生偏移。圖2中最后一次迭代藍色代表的簇，其質(zhì)心相對于聚集點群往邊上偏移，據(jù)分析是受到右邊數(shù)據(jù)點的影響。

2.3.2 改進的K-means算法實驗分析

為了克服K-means算法對初始質(zhì)心依賴較大的缺點[4]，應(yīng)盡可能地將聚類質(zhì)心均勻分散在整個數(shù)據(jù)集上，避免陷入局部最優(yōu)，同時也可以降低K-means算法的迭代次數(shù)，提高收斂速度。

改進的K-means算法通過選取數(shù)據(jù)集的中心點m0、離中心點最遠的點m1及離m1最遠的點m2作為初始質(zhì)心，并通過類間相異度的計算迭代確定k值。聚類過程如圖3所示。

改進的K-means算法經(jīng)過3次迭代快速實現(xiàn)收斂，因為預(yù)先對初始聚類質(zhì)心進行了優(yōu)化，避免了K-means算法中出現(xiàn)的局部最優(yōu)問題。另外，按照1.4節(jié)介紹的方法找到噪聲點并予以刪除，圖3中用“×”標注被刪除的噪聲點。從圖3的最后一次迭代可看出四個簇的質(zhì)心均在聚集點群，未受到噪聲點的影響。

居住地聚類分析實驗也得到了上述相同的結(jié)果。由此得出：改進的K-means算法可有效避免初始化聚類中心引起的局部最優(yōu)問題，消除噪聲和孤立點對聚類結(jié)果的影響。

3 算法驗證

本次研究數(shù)據(jù)由中國移動杭州分公司提供，選取了2018年3月份的手機通信數(shù)據(jù)，按照上文介紹的方法對數(shù)據(jù)進行預(yù)處理，建立如表1所示的工作時段和夜間睡眠時段的手機定位數(shù)據(jù)表。

3.1 位置映射

將杭州市行政區(qū)劃圖和分街道地圖矢量化，并進行地圖匹配和幾何校正[10]。對GIS矢量數(shù)據(jù)圖層進行坐標轉(zhuǎn)換，使得手機定位數(shù)據(jù)坐標系與地圖矢量數(shù)據(jù)一致[10]，將手機定位數(shù)據(jù)映射到城市矢量地圖中。

使用ArcGIS將手機用戶位置坐標轉(zhuǎn)化為杭州市手機用戶空間點數(shù)據(jù)文件。研究范圍定為杭州市，涵蓋蕭山、余杭、臨平、富陽，不包括其他縣市。點空間數(shù)據(jù)準確標明了手機用戶在城市空間中的地理位置，以此作為空間聚類的基礎(chǔ)，能夠更加真實地反映城市人口職住地的聚集。

3.2 職住平衡分析

職住平衡指的是城市中某個空間單元內(nèi)，居民人口數(shù)量和就業(yè)崗位數(shù)量大致相等，大部分居民可以就近工作，通勤交通采用步行或自行車，通勤距離和時間也較短[11]。度量指標一般采用職住比，即在某個空間單元內(nèi)就業(yè)崗位數(shù)量與居民人口數(shù)量之比[1]。職住比越大，表示該空間單元傾向就業(yè)，反之傾向居住。當職住比介于0.8～1.2之間時，認為是平衡的。

某空間單元內(nèi)職住比的計算按以下過程進行處理：① 按用戶進行分組排序。② 統(tǒng)計出樣本中每一個用戶在工作時段和夜間睡眠時段出現(xiàn)次數(shù)最多的定位數(shù)據(jù)作為用戶當天的工作地錨點和居住地錨點。③ 通過改進的K-means算法對樣本中所有用戶的工作地錨點和居住地錨點分別進行聚類分析，得到居住地和工作地聚類。對于跨空間單元的聚類，聚類質(zhì)心位于某個空間單元內(nèi)，就認為是該空間單元的聚類。④ 在聚類中刪除用戶ID相同的多個定位點，只保留離質(zhì)心最近的定位點，這樣聚類中樣本數(shù)與手機用戶數(shù)一致。⑤ 利用空間單元內(nèi)工作地聚類中的手機用戶數(shù)占居住地聚類中的手機用戶數(shù)的比值來計算職住比。

某空間單元內(nèi)職住比的計算公式如下：

(8)

杭州市各個行政區(qū)職住比分布如圖4所示。臨安區(qū)職住比為1，拱墅、江干、富陽三個區(qū)職住比為0.99，杭州市總體接近職住平衡狀態(tài)。

圖4 杭州市各個行政區(qū)職住比分布圖

3.3 熱力圖分析

通過熱力圖可以顯示一個城市在某一時刻通勤人口的聚集情況。通過改進的K-means算法聚類統(tǒng)計空間單元內(nèi)某一時段的手機用戶數(shù)量,通過手機用戶數(shù)量渲染地圖顏色制作通勤人口熱力圖。顏色越深表示通勤人口越集中。

選取2018年3月杭州市(不含富陽、臨安)某工作日8:00-9:00的手機定位數(shù)據(jù)，制作的熱力圖如圖5所示。

圖5 杭州市8點早高峰時段熱力圖

從圖中可看出通勤人口主要聚集分布在：① 主城區(qū)，主要是西湖景區(qū)，武林、湖濱商圈、黃龍商圈等主要商業(yè)區(qū)域；② 濱江區(qū)大部以及蕭山區(qū)城區(qū)部分；③ 余杭區(qū)的臨平副城；④ 城西的文一路、文二路、文三路及周邊區(qū)域；這些區(qū)段的通勤壓力較大，上、下班高峰期容易造成交通擁堵。

4 結(jié) 語

將上述采用改進的K-means聚類算法獲得的職住比、熱力圖通勤人口分析分別與杭州市第六次人口普查數(shù)據(jù)和《杭州交通運行分析報告》(2017年12月發(fā)布)進行分析對比，結(jié)果基本一致。說明上述改進的K-means算法可用于移動通信大數(shù)據(jù)下的城市通勤行為特征分析，可為城市交通規(guī)劃、空間發(fā)展規(guī)劃等眾多領(lǐng)域提供服務(wù)，應(yīng)用前景廣泛。下一步將通過研究分析通勤距離、時間、成本等指標對杭州市通勤情況進行全面評估，為優(yōu)化杭州市空間結(jié)構(gòu)布局提供科學(xué)依據(jù)。