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

徐文進,許 瑤,解 欽

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

引言

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

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

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

1 本文算法

1.1 相關概念

(1)互信息

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

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

1.2 相對熵

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

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

1.3 聚類次數(shù)的決定

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

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

1.4 算法實現(xiàn)過程

實現(xiàn)得到最優(yōu)聚類數(shù)的改進算法的步驟大致如下:

(1)加載樣本數(shù)據(jù)集.

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

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

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

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

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

(7)輸出最優(yōu)聚類數(shù)K值下的聚類結果.

2 實驗

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

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

表1 成都市10月1日8點下車點出租車數(shù)據(jù)

2.2 實驗結果

將表1中的數(shù)據(jù)在傳統(tǒng)K-means聚類下,聚類效果如圖1所示.

圖1 傳統(tǒng)K-means聚類結果

將表1中數(shù)據(jù)用DBSCAN聚類結果如圖2所示.

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

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

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

2.3 算法分析

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

圖2 DBSCAN聚類結果

圖3 SK-means聚類結果

圖4 下車點數(shù)據(jù)圖及熱力圖

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

表2 算法性能對比

3 結論

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