基于方差優(yōu)化譜聚類的熱點區(qū)域挖掘算法*

梁卓靈,元昌安,覃 曉

(1.廣西大學(xué)，廣西南寧 530004；2.廣西科學(xué)院，廣西南寧 530007;3.南寧師范大學(xué)，廣西南寧 530000)

0 引言

近年來，城市的交通擁堵問題日益嚴重，影響居民的出行以及城市的發(fā)展。為改善交通擁堵的情況，可以通過聚類分析的方法對城市居民出行軌跡數(shù)據(jù)進行挖掘，分析總結(jié)居民的出行規(guī)律及行為習(xí)慣，從而合理地規(guī)劃城市的公交線路并優(yōu)化交通資源的配置，為居民推薦合理的出行方式[1,2]。

Ng-Jordan-Weiss (NJW)譜聚類算法是由Ng等[3]提出的，屬于經(jīng)典的多路譜聚類算法。NJW譜聚類算法通過樣本數(shù)據(jù)點的相似矩陣和度矩陣計算求得Laplician矩陣，并由Laplician矩陣的前k個最大特征值對應(yīng)的特征向量建立一個n*k階的矩陣。最后把矩陣中的每一行看作是空間中的點，用K-means聚類算法進行聚類。但K-means聚類算法[4]利用簇內(nèi)點的平均值作為簇的中心點，對孤立點敏感，且其受初始值影響，易陷入局部最優(yōu)解，不利于對熱點區(qū)域的聚類挖掘。

軌跡數(shù)據(jù)是在空間無規(guī)則分布的且分布不均勻的數(shù)據(jù)。K-medoids聚類算法[5]總是選擇簇中位置最接近簇中心的對象作為簇的中心點，能消除對孤立點和噪聲點的敏感性，比K-means聚類算法更適用于軌跡數(shù)據(jù)的聚類。但K-medoids聚類算法對初始中心點的選取仍是隨機的，而利用方差優(yōu)化初始中心的K-medoids聚類算法可改善其對中心點的選取，實現(xiàn)對于熱點區(qū)域的挖掘。

本文把方差優(yōu)化初始中心的K-medoids聚類算法[6]運用到NJW譜聚類算法的最后聚類階段，提出基于方差優(yōu)化譜聚類的熱點區(qū)域挖掘算法(Hot Region Mining algorithm based on improved K-medoids Spectral Clustering，HRM-KSC)，然后在真實的軌跡數(shù)據(jù)集上進行試驗，證明HRM-KSC算法的聚類效果。

1 K-medoids聚類算法的基本原理

K-medoids聚類算法通常用一個代價函數(shù)來評估聚類質(zhì)量的好壞，以重復(fù)迭代的方式尋找到最好的聚簇劃分及聚簇中心點。這里使用聚類誤差平方和來評估聚類結(jié)果質(zhì)量，定義如下：

(1)

其中，x為各個簇類Ci中的樣本，Oj為其聚類中心。

K-medoids聚類算法步驟可描述如下：

Step 1：從數(shù)據(jù)集中隨機選擇k個對象，作為初始的聚類中心點；

Step 2：根據(jù)與中心點距離的遠近，將數(shù)據(jù)集中的其他非中心點對象分配到最近中心點所在的簇類；

Step 3：重新計算每個簇的中心點位置，使其到該簇其他樣本的距離總和最??；

Step 4：重復(fù)執(zhí)行Step 2和Step 3，直到聚類誤差平方和基本不變，達到指定要求為止。

一般K-means聚類算法是通過計算簇類點的平均值來選取中心點，其對孤立點敏感，選取的中心點可能不存在。與K-means聚類算法不同，K-medoids聚類算法在迭代選取中心點時，總是在中心點的周圍選擇樣本點作為新的中心點，消除了對孤立點的敏感性。

2 基于方差優(yōu)化初始中心點的K-medoids聚類算法

方差優(yōu)化初始中心點的K-medoids聚類算法是對K-medoids聚類算法的改進，稱之為Standard-Deviation as radius of neighborhood (SD_K-medoids)算法。該算法利用方差是反映樣本分布密集或疏散程度的特性[7]，以方差度量樣本分布的密集程度，采用樣本標(biāo)準(zhǔn)差為鄰域半徑，從不同的樣本分布密集區(qū)域中選擇樣本作為K-medoids聚類算法的初始聚類中心。

2.1 基本概念描述

設(shè)樣本數(shù)據(jù)集為X={xi|xi∈Rp,i=1,2,…,n}，則樣本xi和xj間的歐式距離dist(i,j)可定義為

(2)

(3)

方差是各個數(shù)據(jù)與平均數(shù)之差的平方和的平均數(shù)，而標(biāo)準(zhǔn)差是方差的算術(shù)平方根。因此樣本xi的方差Vi和標(biāo)準(zhǔn)差stdi可分別定義如下：

(4)

(5)

其中，N為樣本總數(shù)。

2.2 SD_K-medoids算法描述

SD_K-medoids算法首先將樣本標(biāo)準(zhǔn)化，然后計算數(shù)據(jù)集中各樣本的方差，選擇方差最小的樣本作為第一個初始聚類中心加入中心點集；然后計算聚類中心的領(lǐng)域半徑，從數(shù)據(jù)集中刪除該樣本點及該樣本領(lǐng)域中的所有數(shù)據(jù)樣本，在剩余數(shù)據(jù)樣本中尋找方差最小的數(shù)據(jù)樣本作為中心點，重復(fù)執(zhí)行，直到選出k個初始中心點。剩余步驟則與K-medoids聚類算法相同：將數(shù)據(jù)集中的樣本分配給與其距離最近的中心點，計算聚類誤差平方和，計算新的中心點位置；重復(fù)執(zhí)行，當(dāng)聚類誤差平方和不變，結(jié)束算法。

其中，SD_K-medoids算法通過方差反映樣本分布的特性，每次可以在最密集的區(qū)域選取到中心點，使得初始類簇的劃分更貼近數(shù)據(jù)集的真實分布，降低算法收斂的迭代次數(shù)，增加其收斂到全局最優(yōu)解的概率。

使用樣本標(biāo)準(zhǔn)差作為領(lǐng)域半徑，每次選取一個中心點后，要把其領(lǐng)域內(nèi)的樣本點去除，從而避免初始中心點可能位于同一簇類的缺陷，使初始中心點盡可能地分布在不同的簇類。

所以，面對軌跡數(shù)據(jù)無規(guī)則分布、分布密度不均勻的特點時，SD_K-medoids算法可以盡快找到好的熱點區(qū)域初始中心點，加快收斂速度，增加了收斂到全局最優(yōu)解的可能。

3 基于方差優(yōu)化譜聚類的熱點區(qū)域挖掘算法

對于居民出行熱點區(qū)域的挖掘，就是尋找居民頻繁出行的區(qū)域，發(fā)現(xiàn)居民出行停留時間較長的聚集地點，因此需對居民出行停留點進行聚類操作。在聚類操作之前，本文主要借鑒文獻[8]的方法，從移動對象的軌跡數(shù)據(jù)中提取居民出行停留點，詳細方法本文不再具體說明。

針對譜聚類最后聚類階段K-means聚類算法的不足，用SD_K-medoids算法來替代，提出基于方差優(yōu)化譜聚類的熱點區(qū)域挖掘算法(Hot Region Mining algorithm based on improved K-medoids Spectral Clustering，HRM-KSC)。HRM-KSC算法的基本思想是把居民出行停留點看作待聚類的空間樣本點，在NJW譜聚類算法[9]中把停留點集映射到相似度矩陣和拉普拉斯矩陣中，并將拉普拉斯矩陣的特征向量構(gòu)建為特征矩陣，最后改用SD_K-medoids算法對特征矩陣的每行元素進行聚類。

3.1 相似度矩陣的構(gòu)造

譜聚類把居民出行停留點集看作是一個無向圖G(V,E,A)的頂點集合V，由邊集E把停留點連接起來，而圖中權(quán)重集A表示停留點間的相似性。通過權(quán)重來構(gòu)建停留點集的相似度矩陣，停留點間的相似性常用高斯函數(shù)wij來計算：

(6)

其中，si和sj分別表示停留點i和j的特征向量，σ為尺度參數(shù)。

3.2 拉普拉斯矩陣的構(gòu)造

本文對停留點集的構(gòu)建采用的是規(guī)范的拉普拉斯矩陣Lsym，其構(gòu)造公式如下：

(7)

其中，W為相似度矩陣；D為圖的度矩陣，其主對角線上的元素為相似度矩陣W的第i行元素之和，計算如下：

(8)

在構(gòu)建停留點集的相似度矩陣及拉普拉斯矩陣后，將拉普拉斯矩陣前k個特征向量構(gòu)建為特征矩陣，最后用SD_K-medoids算法對矩陣的每行元素進行聚類。

HRM-KSC算法流程如圖1所示,具體過程描述如下：

圖1 HRM-KSC算法流程圖

Step 1：利用公式(6)計算停留點集的相似度矩陣；

Step 2：利用公式(7)和(8)計算停留點集的拉普拉斯矩陣；

Step 3：把拉普拉斯矩陣前k個特征向量組成的特征矩陣歸一化為矩陣Y=[y1,y2,…,yk],把矩陣Y的每一行向量作為一個數(shù)據(jù)點yi′；

Step 4：把所有數(shù)據(jù)點yi′(i=1,2,…,k)作為新的樣本點，根據(jù)式(3)對樣本進行標(biāo)準(zhǔn)化。

Step 5：根據(jù)式(4)計算數(shù)據(jù)集中各樣本的方差，如Vi表示第i個樣本的方差值；其次初始化中心點集M為空，即M={}。

Step 6：從數(shù)據(jù)集X={x1,x2,…,xn}中尋找方差最小的樣本xmin，將其作為第一個類簇的初始聚類中心C1加入到中心點集中，即M=M∪{C1}；根據(jù)式(5)計算鄰域半徑r1，從數(shù)據(jù)集中刪除該樣本以及該樣本領(lǐng)域中的所有數(shù)據(jù)樣本。

Step 7：重復(fù)執(zhí)行Step 6，直到選出k個初始中心點，即|M|=k。

Step 8：將數(shù)據(jù)集中的樣本分配給與其距離最近的中心點，由公式(1)計算聚類誤差平方和。

Step 9：計算每個簇的新中心點位置，使其到該簇其他樣本的距離總和最小。

Step 10：重復(fù)執(zhí)行Step 8-Step 9，若聚類誤差平方和變化不大，結(jié)束算法；否則繼續(xù)迭代。

4 實驗分析

為測試HRM-KSC算法的性能，本文使用微軟亞洲研究院的geolife數(shù)據(jù)集，從2008年8月到10月的軌跡數(shù)據(jù)中提取出居民出行停留點集。其中，居民停留點的提取參照文獻[8]中的方法。本次實驗在Win10 64 bit操作系統(tǒng)，8 GB內(nèi)存，CPU 2.60 GHz的環(huán)境下進行，用Python語言實現(xiàn)。

為度量2種算法在實驗中的表現(xiàn)，采用SC輪廓系數(shù)作為評價指標(biāo)。SC輪廓系數(shù)常用于度量未知類別的聚類數(shù)據(jù)集，表示聚類結(jié)果中各簇類的稠密程度及簇間的離散程度。

SC輪廓系數(shù)計算公式如下：

(9)

其中，a(i)表示計算樣本i到同簇類其他樣本的平均距離，b(i)表示計算樣本i到其他樣本的平均距離。SC在[-1,1]區(qū)間內(nèi)取值。當(dāng)SC越接近1時，表示聚類效果越好。

本次實驗測試了2種算法在用戶停留點集上的聚類效果，在一定區(qū)間內(nèi)選取3種較好的結(jié)果，如表1所示。

表1 算法在停留點數(shù)據(jù)集上聚類結(jié)果

觀察表1中2種算法在停留點數(shù)據(jù)集上的表現(xiàn)，發(fā)現(xiàn)HRM-KSC算法在選取相同參數(shù)的情況下，輪廓系數(shù)指標(biāo)均比NJW譜聚類算法高，表明HRM-KSC算法的聚類結(jié)果中同簇類點更緊密，不同簇類點更離散，聚類結(jié)果更合理。

為更進一步展示2種算法的聚類結(jié)果，采用Python的matplotlib庫，以經(jīng)緯度為坐標(biāo)畫出不同參數(shù)條件下的聚類結(jié)果(圖2—4)。從圖中可以看出，在相同參數(shù)條件下，HRM-KSC聚類劃分結(jié)果更合理，尤其在圖2和圖3中表現(xiàn)更明顯，其原因是NJW譜聚類算法在最后階段所使用的K-means算法，對于初始中心點的選取不夠理想，影響了聚簇的劃分效果。

圖2 k=3,σ=10 時的實驗結(jié)果

圖3 k=4,σ=15 時的實驗結(jié)果

圖4 k=5,σ=20 時的實驗結(jié)果

5 結(jié)論

本文針對NJW譜聚類算法最后階段的K-means聚類算法對初始點敏感的缺陷，利用SD_K-medoids算法計算樣本方差和領(lǐng)域半徑，優(yōu)化對初始中心點的選取，提出基于方差優(yōu)化譜聚類的熱點區(qū)域挖掘算法(HRM-KSC)。在居民停留點數(shù)據(jù)集上進行HRM-KSC算法和NJW譜聚類算法的對比實驗，結(jié)果表明HRM-KSC算法的聚類質(zhì)量更高，聚類效果更好。后續(xù)期望改善譜聚類算法中高斯函數(shù)尺度參數(shù)的選取，以及研究如何確定聚類數(shù)目，以進一步提高譜聚類算法的聚類質(zhì)量。