周天綺 楊志民

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

0 引 言

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

1 算法設(shè)計(jì)

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

1.1 聚類(lèi)性能評(píng)價(jià)

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

(1)

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

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

(2)

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

1.2 算法流程

K-means聚類(lèi)算法具體流程如下：

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

輸出：k個(gè)簇C1，C2，…，Ck， 使平方誤差準(zhǔn)則最小。

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

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

{

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

(3)

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

(4)

}

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

1.3 算法缺點(diǎn)

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

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

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

1.4 算法改進(jìn)

1.4.1 采用類(lèi)間相異度確定k值

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

類(lèi)間相異度DCA計(jì)算公式如下：

(5)

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

改進(jìn)后的算法描述如下：

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

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

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

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

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

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

1.4.2 消除噪聲和孤立點(diǎn)的影響

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

(6)

(7)

2 實(shí) 驗(yàn)

2.1 數(shù)據(jù)準(zhǔn)備

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

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

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

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

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

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

2.2 實(shí)驗(yàn)環(huán)境

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

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

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

2.3 算法比較

2.3.1 K-means算法實(shí)驗(yàn)分析

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

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

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

2.3.2 改進(jìn)的K-means算法實(shí)驗(yàn)分析

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

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

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

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

3 算法驗(yàn)證

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

3.1 位置映射

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

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

3.2 職住平衡分析

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

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

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

(8)

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

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

3.3 熱力圖分析

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

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

圖5 杭州市8點(diǎn)早高峰時(shí)段熱力圖

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

4 結(jié) 語(yǔ)

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