基于互信息和散度改進K-Means在交通數據聚類中的應用①

徐文進,許 瑤,解 欽

(青島科技大學 信息科學技術學院,青島 266061)

引言

聚類分析是數據挖掘研究的一項重要技術,屬于無監督機器學習方法,其目的是根據已知數據,計算各觀察個體或變量間相似度的統計量,然后根據某種準則(如最短距離法、最長距離法、中間距離法、重心法),使得同一類內的相似度最大,類間相似度最小,最終將觀察個體或變量分為若干類.常用的聚類分析方法包括基于劃分的方法,基于密度的方法,基于網格的方法,基于模型的方法和基于變換的聚類算法.K-means聚類算法的基本思想:首先,根據聚類數目k,選擇一定數目初始聚類中心;然后,計算某一點到每一聚類中心的距離,并將該點歸入最小的類中;接著,基于新的聚類計算新的聚類中心,并基于新的聚類中心進行新的聚類.上述過程依次進行,直到達到最佳的聚類效果.

K-means聚類算法在交通大數據的應用中,聚類效果明顯,聚類快速且易于實現.但是K-means算法也存在一定的局限性,如對“噪聲”和孤立感(異常點)敏感,無法掌握數據分布情況,人為設定分簇數目,需要增加迭代次數以取得良好的聚類效果;算法時間復雜度高,經常以局部最優結束,難以達到全局最優.為解決以上問題,文獻[1]提出基于自適應布谷鳥搜索的Kmeans聚類改進算法,試圖解決K-means聚類算法受初始類中心影響的問題,該算法適用于海量數據聚類,但是集群節點數量對算法的效率具有一定的影響,算法的穩定性同時有待提高;文獻[2]基于最小化生成樹初始化類中心,有效提高了聚類算法的準確率,但算法效率有待改進;文獻[3]提出使用cannopy方法對數據預處理從而得到初始聚類中心的方法,該方法對于交通數據聚類具有一定的復雜性;文獻[4]提出將遺傳算法和K-means算法融合,解決K-means容易陷入局部最優的問題,但是需要多次進行遺傳操作,具有一定的復雜性.文獻[5]將人工蜂群算法和K-means算法相結合,克服人工蜂群初始化隨機性和K-means算法的敏感性,加快了收斂速度,同時,引入了較高的時間復雜度;文獻[6]將粒子群算法和K-means算法結合,利用粒子群全局搜索和K-means局部搜索的優勢達到最好的聚類結果,但是算法運行時間還有待優化.文獻[7]通過樣本數據分層獲取聚類數搜索范圍從而獲得最佳聚類數;文獻[8] 通過設定AP算法的參數,基于最大最小距離算法思想設定初始聚類中心和確定聚類數目,但是參數的設定對聚類效果會有一定的影響.將K-means算法應用于交通數據聚類中,文獻[9] 用K-means算法分析杭州市通勤特征,杭州市總體達到職住平衡;文獻[10]通過引入Canopy-K-means改進聚類算法,得到客源地的出行熱點區域,并將該區域和已有公交站點對比,分析公交站點存在的合理性.

基于不同的思想,已經有學者提出了多種不同的聚類數選擇方法.在避免局部最優問題中,提高了聚類準確度,但聚類效率仍有待提高.本文通過計算點之間的互信息來尋找聚類中心;尋找聚類數目時,基于互信息和散度的比值,用比值來衡量聚類效果,從而決定最佳聚類數目.此方法不需要人為設定聚類數據,避免了主觀設置聚類數目對聚類產生的影響,提高了聚類效率,保證了K-means算法聚類結果的有效性和穩定性.

1 本文算法

1.1 相關概念

(1)互信息

互信息[11]是信息論中的一個基本概念,利用兩個隨機變量 的聯合分布 與乘積分布 的相對熵,測量兩隨機變量的相互依賴程度.將互信息應用在交通數據聚類中,其互信息可表示為:

其中,X為經度,Y緯度,p(x,y)為下車點的經緯度,p(x)為經度出現的概率,p(y)為緯度出現的概率,p(x,y)、p(x)、p(y)可以根據原始交通數據求得,進而可以求得互信息的值,參考計算得到的互信息值決定是否將待分類點歸入這個類.通常互信息越小,兩變量間相似度越大,將互信息較小的點歸為一類,使得類內之間相似性較高,類內點較緊湊.

1.2 相對熵

相對熵[12],是兩個概率分布間差異性度量,其非負性,使得相對熵可用于描述兩組變量之間的聚類.傳統的樣本相似性度量方式如歐氏距離、曼哈頓距離、余弦相似性等難以對不同分布間的相似性進行度量.相對熵的定義為:

DKL(fm(x)∥gq(x))可以度量簇m中點分布和簇q中點分布的差異.將相對熵用于交通數據分類中,可以通過相對熵的大小,判斷兩簇之間的相似性,當相對熵較大時,兩簇分布差異較大,分類效果較好.

1.3 聚類次數的決定

評判聚類效果優的標準為:類內的差異盡可能小,類間差異盡可能大.聚類數K值發生變化時,簇類間的差異值以及簇類內的差異值隨之變化,我們把簇類內差異值與簇類間的差異值之比定義為聚類效果優劣程度的評判標準S(式(3)),簇類內差異值用樣本間的互信息I表示,簇類間的差異值用相對熵表示.

根據評判聚類效果優的標準,結合交通數據,當互信息I盡可能小,相對熵盡可能大時,聚類效果較好,在式(3)中,當S達到最小值,此時的聚類效果最好.

1.4 算法實現過程

實現得到最優聚類數的改進算法的步驟大致如下:

(1)加載樣本數據集.

(2)計算樣本信息熵,選擇能最大限度降低信息熵的簇劃分為兩個簇.

(3)確定聚類中心,選擇聯合概率 較大的點為聚類中心點.

(4)對現有簇計算S值.

(5)設置判斷值H,H=S.

(6)重復步驟(2)(3)(4),若計算的的S

(7)輸出最優聚類數K值下的聚類結果.

2 實驗

2.1 實驗數據準備

為了檢測本文提出算法的有效性和可靠性,本文分別采用滴滴公司蓋亞計劃(https://gaia.didichuxing.com)開放的成都市2016年10月1日8點出租車下車點數據集,數據描述如表1所示,并在Python3.5開發環境下對改進算法進行了編程實現.

表1 成都市10月1日8點下車點出租車數據

2.2 實驗結果

將表1中的數據在傳統K-means聚類下,聚類效果如圖1所示.

圖1 傳統K-means聚類結果

將表1中數據用DBSCAN聚類結果如圖2所示.

將表1中數據利用改進K-means算法聚類效果如圖3所示.

圖4(a)為表1 數據進行數據可視化后的顯示圖,四個圓為聚類中心點.圖4(b)為利用表1數據進行熱力圖可視化的顯示圖.

傳統的K-means算法,通過手動設置聚類數目K,聚類效果如圖1所示,其中橫坐標表示經度(/°),縱坐標表示緯度(/°).SK-means算法聚類效果如圖3 所示,SK-means算法通過迭代自動尋找聚類數目為4,通過對比可以看出,傳統的K-means算法需要手動設置聚類數目,同時,相同聚類數目時,聚類效果不夠穩定,SK-means自動尋找聚類數目,多次運行聚類效果較為穩定.DBSCAN算法是基于密度分類,其對任意形狀數據聚類和識別噪聲點的優勢使其廣泛應用于交通大數據中,其聚類效果如圖2所示,DBSCAN算法需要對距離閾值和鄰域樣本數閾值進行大量聯合調參,由于交通數據的特殊性,使其聚類過程具有一定的復雜性.圖2中左圖聚為4類,右圖聚為3類,和SK-means算法相比,類間距離相差較近,類內距離相差較遠,不能滿足較好的聚類條件.

2.3 算法分析

表2是傳統K-means與本文SK-means算法的性能對比,通過對比兩者的信息熵,SK-means類內信息熵較小、類間信息熵較大,說明類內下車點更加聚集,類間下車點較離散.通過對比minSSE,SK-means具有更小的最小均方誤差.SK-means聚類時間相比傳統Kmeans較長,當考慮到聚類精度,同時不需手動設置聚類數目時,所用的時間是可以接受的.

圖2 DBSCAN聚類結果

圖3 SK-means聚類結果

圖4 下車點數據圖及熱力圖

對比SK-means算法和傳統K-means算法進行聚類分析后得到的聚類結果,我們不難發現:從信息論角度來看,通過計算兩變量的聯合概率,選出其最大的點作為聚類中心,用互信息衡量類內變量之間的相關性,互信息越小,兩變量相關性越大,用相對熵來衡量類間相似性,相對熵越大,類間分布差異性越大.通過互信息和相對熵的比值來決定聚類次數,當互信息較小,相對熵較大時,即比值最小時,聚類效果最好,可以有效避免局部收斂.在改進后的算法中,我們并沒有預先設定聚類數K值,主要是通過算法本身的循環迭代計算以及判定比較,最終輸出了較好的聚類效果.與此同時,在多次運行我們的的改進算法的情況下,所得到的聚類結果都是一致的,這也證明了改進算法的穩定性.由此,我們可以得到結論,改進的K-means算法,具有一定的穩定性和可靠性.

表2 算法性能對比

3 結論

交通數據在時空上具有一定的多變性,利用有效的聚類方法能夠更好地揭示潛在的用戶行為模式,傳統的K-means聚類由于基于聚類數量,不能合理解釋變化的人流熱點.本文通過基于信息論的方式計算每一次聚類效果,并將其作為反饋來判斷是否繼續進行迭代,從而找到最佳聚類數和最佳聚類中心,在性能上提高了對空間聚類的判別效率,其聚類方法還有一定的改進性,但其聚類精度還需進一步完善.