基于方差優化譜聚類的熱點區域挖掘算法*

梁卓靈,元昌安,覃 曉

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

0 引言

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

2.1 基本概念描述

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

(2)

(3)

方差是各個數據與平均數之差的平方和的平均數，而標準差是方差的算術平方根。因此樣本xi的方差Vi和標準差stdi可分別定義如下：

(4)

(5)

其中，N為樣本總數。

2.2 SD_K-medoids算法描述

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

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

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

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

3 基于方差優化譜聚類的熱點區域挖掘算法

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

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

3.1 相似度矩陣的構造

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

(6)

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

3.2 拉普拉斯矩陣的構造

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

(7)

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

(8)

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

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

圖1 HRM-KSC算法流程圖

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

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

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

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

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

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

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

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

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

Step 10：重復執行Step 8-Step 9，若聚類誤差平方和變化不大，結束算法；否則繼續迭代。

4 實驗分析

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

為度量2種算法在實驗中的表現，采用SC輪廓系數作為評價指標。SC輪廓系數常用于度量未知類別的聚類數據集，表示聚類結果中各簇類的稠密程度及簇間的離散程度。

SC輪廓系數計算公式如下：

(9)

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

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

表1 算法在停留點數據集上聚類結果

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

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

圖2 k=3,σ=10 時的實驗結果

圖3 k=4,σ=15 時的實驗結果

圖4 k=5,σ=20 時的實驗結果

5 結論

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