基于改進(jìn)密度峰值聚類算法的軌跡行為分析

呂 奕，劉漫丹

華東理工大學(xué) 化工過程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，上海 200030

教育管理信息化是信息化社會(huì)的重要組成部分。隨著校園信息化程度的不斷提高，利用校園網(wǎng)通過無線網(wǎng)絡(luò)的方式進(jìn)行校園電子化信息管理成為主流，由此積累了大量的校園無線網(wǎng)絡(luò)數(shù)據(jù)。如何有效地分析和利用這些海量數(shù)據(jù)，從而讓其更好地服務(wù)于校園和教育，近年來成為一個(gè)熱點(diǎn)問題。根據(jù)用戶登錄無線網(wǎng)的位置及時(shí)間，并按照時(shí)間順序?qū)⑽恢靡来芜B接起來，可以得到用戶軌跡信息。根據(jù)軌跡信息之間的相似性對(duì)群體特征進(jìn)行深入探索和分析，可以有效推進(jìn)校園網(wǎng)的更新迭代以及指導(dǎo)學(xué)生的網(wǎng)絡(luò)使用行為。

軌跡數(shù)據(jù)聚類[1]是軌跡分析的重要方面，其是將具有不同時(shí)間和空間相似度特征的時(shí)空對(duì)象劃分為多個(gè)類或簇，使同一類內(nèi)的對(duì)象相似性程度高，而不同類之間數(shù)據(jù)的相似性程度低。針對(duì)軌跡行為分析已有不少研究成果。吳笛等人[2]對(duì)南海旋渦軌跡進(jìn)行時(shí)空聚類分析，在空間聚類的基礎(chǔ)上提出軌跡線段時(shí)間距離的度量方法和閾值確定原則，驗(yàn)證了基于密度的軌跡時(shí)空聚類方法的有效性。穆桃等人[3]通過分析多層網(wǎng)絡(luò)流量，利用多種機(jī)器學(xué)習(xí)方法，預(yù)測(cè)出用戶的地理位置類型和興趣愛好，并將兩者相結(jié)合提高用戶分類的準(zhǔn)確性。李旭等人[4]通過構(gòu)造用戶興趣度矩陣的方式改進(jìn)用戶間相似度的計(jì)算方法，提出了基于興趣矩陣的相似度聚類算法。

對(duì)校園無線網(wǎng)絡(luò)軌跡行為特征進(jìn)行聚類分析，一方面，可以根據(jù)不同集合中學(xué)生的軌跡特點(diǎn)將高校學(xué)生分為不同簇，分析判斷不同簇學(xué)生的特點(diǎn)，為高校教育教學(xué)方案提供依據(jù)，為學(xué)生管理系統(tǒng)提供決策支持[5]。另一方面，將離群點(diǎn)檢測(cè)算法與聚類算法相結(jié)合，可以因此判斷出學(xué)生中的離群學(xué)生并進(jìn)行針對(duì)性處理。由于校園軌跡具有較強(qiáng)的規(guī)律性[6]，通過檢測(cè)學(xué)生的異常軌跡，可分析學(xué)生是否按時(shí)上課或者是否在教學(xué)期間內(nèi)離校等問題，針對(duì)頻繁發(fā)生軌跡異常的學(xué)生進(jìn)行有效的管理，密切關(guān)注使用者動(dòng)態(tài)，防止意外事件發(fā)生[7]。

本文采用基于共享最近鄰的快速搜索密度峰值聚類算法（shared-nearest-neighbor-based clustering by fast search and find of density peaks，SNN-DPC）[8]對(duì)校園無線網(wǎng)絡(luò)軌跡進(jìn)行聚類分析，在傳統(tǒng)的局部密度的核密度計(jì)算方式的基礎(chǔ)上，改進(jìn)局部密度度量，使得算法適用于多比例、各密度以及數(shù)據(jù)集之間交叉纏繞等高維度的復(fù)雜數(shù)據(jù)集，更有利于對(duì)校園無線網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行聚類分析。聚類算法對(duì)離群點(diǎn)信息較為敏感，若將離群點(diǎn)算法與聚類算法相結(jié)合，可以有效減小離群點(diǎn)對(duì)整體聚類的影響。因此，本文將離群點(diǎn)檢測(cè)算法與SNN-DPC 聚類算法相結(jié)合，得到兩種改進(jìn)后的SNN-DPC算法，兩種改進(jìn)算法均克服了原有聚類算法對(duì)離群點(diǎn)敏感問題的不足。將算法應(yīng)用于實(shí)際校園無線網(wǎng)絡(luò)信息處理中，可以定位瀏覽信息異常學(xué)生，為高校信息化建設(shè)提供了信息支持。

1 SNN-DPC算法介紹

SNN-DPC 算法是在基于密度峰值的快速搜索聚類算法（clustering by fast search and find of density peaks，CFSFDP）[9]的基礎(chǔ)上，考慮了每個(gè)點(diǎn)的鄰居的影響，引入了一種間接距離和密度的測(cè)量方法，利用共享鄰居的概念來描述點(diǎn)的局部密度和它們之間的距離[9]。

定義1（共享最近鄰數(shù)SNN）對(duì)于數(shù)據(jù)集X中的任意兩個(gè)點(diǎn)xi和xj，點(diǎn)xi的K個(gè)最近鄰集合（Γ(xi)）與點(diǎn)xj的K個(gè)最近鄰集合（Γ(xj)）的交集定義為共享最近鄰數(shù)SNN(xi,xj)。通常來說，兩個(gè)點(diǎn)共享的鄰居數(shù)目越多，則這兩個(gè)點(diǎn)越相似。共享最近鄰數(shù)用式（1）表示：

定義2（SNN相似度Sim(xi,xj)）點(diǎn)xi和xj之間的相似性程度稱為SNN相似度。對(duì)于數(shù)據(jù)集X中的點(diǎn)xi和xj，相似度可以定義為式（2）：

其中，SNN(xi,xj)表示點(diǎn)xi和xj的共享最近鄰數(shù)，d表示數(shù)據(jù)點(diǎn)間距離，通常為歐氏距離，點(diǎn)p為點(diǎn)xi和點(diǎn)xj共享的鄰居點(diǎn)，也就是說，僅當(dāng)點(diǎn)xi和點(diǎn)xj出現(xiàn)在彼此的K鄰居集合中時(shí)，才計(jì)算SNN相似度。否則，點(diǎn)xi和點(diǎn)xj之間的SNN相似度為0。在定義任意兩個(gè)點(diǎn)的SNN 相似度之后，使用該相似度來計(jì)算點(diǎn)xi的局部密度ρi。

定義3（局部密度ρi）與點(diǎn)xi相似度最高的K個(gè)點(diǎn)的SNN相似度（Sim(xi,xj)）之和，用式（3）表示：

其中，L(xi)=(xi,…,xK)表示與點(diǎn)xi相似度最高的K個(gè)點(diǎn)的集合。

局部密度ρ不僅利用距離信息，而且還通過共享最近鄰數(shù)SNN 獲得有關(guān)聚類結(jié)構(gòu)的信息，充分揭示了點(diǎn)與點(diǎn)之間的內(nèi)在關(guān)系。

定義4（最近距離δi）計(jì)算點(diǎn)xi與其高于自身密度的點(diǎn)的最近距離δi（簡(jiǎn)稱xi的最近距離）需要找到局部密度大于點(diǎn)xi的點(diǎn)xj，然后將數(shù)據(jù)點(diǎn)xi和xj之間的歐氏距離乘以這兩點(diǎn)分別與它們的最近鄰距離之和，取最小值。具體定義如式（4）所示：

可以看出，最近距離δ不僅考慮了距離因素，同時(shí)考慮了每個(gè)點(diǎn)的鄰居信息，從而補(bǔ)償了低密度簇中的點(diǎn)，并提高了δ值的可行性，適應(yīng)不同密度數(shù)據(jù)集。

密度最大點(diǎn)的δ值需要特殊定義，因?yàn)槠涫菙?shù)據(jù)集X剩下所有點(diǎn)中δ最大的，如式（5）所示：

定義5（決策值γ）局部密度與最近距離之積。點(diǎn)xi的決策值γi用式（6）表示：

決策值γ的作用在于確定聚類中心點(diǎn)，通常來說，γ值越大，相應(yīng)的ρ和δ越大，對(duì)應(yīng)的數(shù)據(jù)點(diǎn)越有可能成為聚類中心。根據(jù)決策值確定聚類中心點(diǎn)之后，SNN-DPC 算法對(duì)未分配的點(diǎn)分為兩類考慮，確定的從屬點(diǎn)與可能的從屬點(diǎn)。

定義6（確定的從屬點(diǎn)與可能的從屬點(diǎn)）滿足不等式（7）所示的條件，就是確定的從屬點(diǎn)，否則就是可能的從屬點(diǎn)。假設(shè)點(diǎn)xi已經(jīng)被安排到一個(gè)簇中，xj還沒有被安置，如果點(diǎn)xj滿足不等式（7），那么xj不可避免地屬于xi所在的簇。換句話說，xi和xj各自的K鄰域中至少一半是共享的，兩點(diǎn)才有可能成為同一個(gè)簇的點(diǎn)。

除了定義上的差異外，確定的從屬點(diǎn)和可能的從屬點(diǎn)之間的另一個(gè)區(qū)別是，在非極端情況下，每個(gè)點(diǎn)都可能同時(shí)從屬于多個(gè)聚類，卻不可避免地只能從屬于一個(gè)簇。

2 基于共享鄰居的改進(jìn)聚類方法

SNN-DPC算法在計(jì)算樣本點(diǎn)間相似度時(shí)采用的是歐式距離代表數(shù)據(jù)點(diǎn)之間的相似程度，距離越大，表示相似性程度越低，因此不能利用相似度矩陣直接進(jìn)行計(jì)算。本文首先通過轉(zhuǎn)換函數(shù)，將相似度矩陣轉(zhuǎn)變?yōu)榫嚯x矩陣，再使用SNN-DPC算法，可以提高聚類算法對(duì)各種相似度矩陣的適應(yīng)度。聚類可以對(duì)相關(guān)性較強(qiáng)的樣本進(jìn)行劃分，而離群點(diǎn)檢測(cè)可以對(duì)相關(guān)性非常弱的樣本點(diǎn)進(jìn)行分類，聚類與離群點(diǎn)分析可以形成一種互補(bǔ)關(guān)系。SNN-DPC 算法中沒有對(duì)離群點(diǎn)進(jìn)行分析，在處理確定的從屬點(diǎn)與可能的從屬點(diǎn)時(shí)力求每一個(gè)點(diǎn)都可以安排到一個(gè)確定的簇，因此不可避免地會(huì)受到離群點(diǎn)對(duì)聚類結(jié)果的影響。本文通過將離群點(diǎn)檢測(cè)算法與SNN-DPC算法相結(jié)合，先對(duì)數(shù)據(jù)集中的離群點(diǎn)做“高亮”處理，對(duì)剩下的點(diǎn)進(jìn)行聚類，可以提高聚類的準(zhǔn)確性與快速性，達(dá)到較好的聚類效果。另外，檢測(cè)出的離群點(diǎn)也可做單獨(dú)分析。

2.1 相似度矩陣轉(zhuǎn)變?yōu)榫嚯x矩陣

本文采用的原始數(shù)據(jù)集為某校園無線網(wǎng)絡(luò)中記錄的用戶真實(shí)軌跡數(shù)據(jù)。數(shù)據(jù)集中將包含的校園全區(qū)域范圍內(nèi)的各地點(diǎn)分別用數(shù)字進(jìn)行編號(hào)。用戶某天的時(shí)空軌跡序列如表1所示，其中l(wèi)表示用戶所在區(qū)域編號(hào)，t表示用戶在該地的網(wǎng)絡(luò)登錄時(shí)間，m為用戶總量，W1,W2,…,Wm分別表示各用戶軌跡序列中的登錄記錄總數(shù)。

表1 用戶時(shí)空軌跡數(shù)據(jù)集Table 1 User spatial-temporal trajectory dataset

基于無線網(wǎng)絡(luò)中時(shí)空軌跡的數(shù)據(jù)特點(diǎn)，在分別計(jì)算不同用戶之間軌跡的時(shí)間相似性和空間相似性后，引入連續(xù)因子優(yōu)化空間相似性度量，結(jié)合軌跡的時(shí)間維度與空間維度求得用戶之間的軌跡相似度信息[10]。

相似度信息包括時(shí)間相似性與空間相似性。

對(duì)于整體軌跡序列而言，兩軌跡中時(shí)間距離小的軌跡點(diǎn)越多，說明相遇次數(shù)越多，軌跡整體的時(shí)間相似性越高。采用最短時(shí)間距離（shortest time distance，STD）[11]模型計(jì)算時(shí)間相似性。

假設(shè)存在兩個(gè)用戶ui和uj，其時(shí)空軌跡序列分別為Ri={ri,1,ri,2,…,ri,x,…,ri,Wi}和Rj={rj,1,rj,2,…,rj,y,…,rj,Wj}。并假設(shè)存在兩個(gè)軌跡點(diǎn)ri,x(li,x,ti,x)和rj,y(lj,y,tj,y)，其時(shí)間距離記為Dis(ri,x,rj,y)，如式（8）所示：

最短時(shí)間距離定義為軌跡Rj中所有軌跡點(diǎn)中與軌跡點(diǎn)ri,x時(shí)間距離最小的值，表示如式（9）：

軌跡Ri對(duì)于軌跡Rj的時(shí)間相似性可以近似為軌跡Ri中所有軌跡點(diǎn)與Rj中對(duì)應(yīng)STD 匹配軌跡點(diǎn)的時(shí)間相似性總和，記為Cor(Ri,Rj)，表示為式（10）：

由于STD模型的計(jì)算結(jié)果不具有對(duì)稱性，兩軌跡之間的時(shí)間相似性表示為式（11）：

空間相似性信息利用最長(zhǎng)公共子序列（longest common subsequences，LCSS）[12]算法，尋找兩個(gè)給定序列的公共子序列中最長(zhǎng)的子序列。

軌跡Ri和軌跡Rj的空間相似性由LCSS序列的長(zhǎng)度分別占兩條軌跡長(zhǎng)度比例的平均值與連續(xù)因子共同決定：

其中，Wθ表示LCSS序列的長(zhǎng)度。

用戶相似性可以通過軌跡段的時(shí)空相似性得到，用式（13）表示：

相似度矩陣用S表示，如式（14）所示：

其中，sij表示用戶i和用戶j之間的相似度，即式（13）中的UCor(Ri,Rj)，0 ≤sij≤1。矩陣的對(duì)角線元素為1。

由于相似度矩陣與距離矩陣負(fù)相關(guān)，即相似度矩陣中的值越大，距離矩陣中的值應(yīng)該越小。因此，采用如式（16）所示的轉(zhuǎn)換函數(shù)將相似度矩陣轉(zhuǎn)換為距離矩陣。

其中，i=1,2,…,m，j=1,2,…,m，dij表示用戶i和j之間的距離，D表示距離矩陣。

2.2 基于離群點(diǎn)檢測(cè)的SNN-DPC聚類算法

為了減少離群點(diǎn)對(duì)算法的影響，首先需要確定數(shù)據(jù)集中的離群點(diǎn)并且移除它們。許多真實(shí)世界的數(shù)據(jù)集展示了一個(gè)非常復(fù)雜的結(jié)構(gòu)，在實(shí)際應(yīng)用中，通常會(huì)按照實(shí)際情況選擇對(duì)應(yīng)的離群點(diǎn)數(shù)據(jù)挖掘算法。本文針對(duì)SNN-DPC 算法提出兩種離群點(diǎn)檢測(cè)算法，一種算法是基于局部密度離群點(diǎn)檢測(cè)的SNN-DPC 算法，簡(jiǎn)稱RSNN-DPC 算法，該算法是利用SNN-DPC 算法本身計(jì)算的局部密度值，設(shè)定閾值范圍，尋找離群點(diǎn)。另一種算法是基于LOF 離群點(diǎn)檢測(cè)的SNN-DPC 算法，簡(jiǎn)稱LSNN-DPC 算法，其是將LOF 算法與SNN-DPC 算法相結(jié)合，減少實(shí)驗(yàn)輸入?yún)?shù)并去除離群點(diǎn)的影響，成為新的去除離群點(diǎn)的聚類算法。

2.2.1 基于局部密度離群點(diǎn)檢測(cè)的改進(jìn)算法（RSNN-DPC）

在SNN-DPC 聚類算法中，有兩個(gè)重要指標(biāo)可以表征樣本點(diǎn)的密度情況，即局部密度ρ和最近距離δ，通過第1 章對(duì)SNN-DPC 算法的分析，最近距離是根據(jù)局部密度進(jìn)行定義的，因此可以通過局部密度來表征樣本點(diǎn)的密度情況。如果一個(gè)對(duì)象的局部密度相對(duì)于其相鄰對(duì)象的密度要低得多，那么這個(gè)對(duì)象很有可能就是一個(gè)離群值。

在SNN-DPC算法中，局部密度ρ具有以下特性[13]：

（1）當(dāng)鄰居數(shù)K較小時(shí)，點(diǎn)xi與其鄰居xj之間的共享鄰居數(shù)較小，同時(shí)點(diǎn)xj與點(diǎn)xi之間的距離也較近，此時(shí)，K反映了點(diǎn)xi較小鄰域內(nèi)的局部密度。相反，當(dāng)K較大時(shí)，點(diǎn)xj與點(diǎn)xi之間的距離較遠(yuǎn)，它反映了xi的較大鄰域內(nèi)的局部密度。低密度簇中的點(diǎn)之間的距離較大，因此K的變化將對(duì)低密度簇產(chǎn)生更大的影響。

（2）當(dāng)|SNN(xi,xj)|恒定時(shí)，如果點(diǎn)xi和點(diǎn)xj到它們的每個(gè)共享鄰居的距離都很小，則ρi較大。換句話說，如果點(diǎn)xi和點(diǎn)xj之間的距離很小，并且每個(gè)共享的相鄰點(diǎn)到xi和xj的距離也很小，那么點(diǎn)xi的密度就很大。因此，空間中距離數(shù)據(jù)點(diǎn)xi越近的點(diǎn)對(duì)ρi的貢獻(xiàn)越大。

通過對(duì)局部密度的分析可知，局部密度ρ不僅利用距離信息，而且還通過共享最近鄰數(shù)SNN 獲得有關(guān)聚類結(jié)構(gòu)的信息，充分揭示了點(diǎn)與點(diǎn)之間的內(nèi)在關(guān)系。在這種情況下，如果局部密度值為0，說明數(shù)據(jù)集X中與之相關(guān)的所有點(diǎn)SNN相似度為0，可能原因有以下兩點(diǎn)：

（1）該點(diǎn)獨(dú)立于其他各點(diǎn)，與數(shù)據(jù)集中剩余點(diǎn)沒有共享鄰居點(diǎn)，即SNN為0。

（2）點(diǎn)xi和xj到它們所有共享鄰居的距離接近于無窮

因此，可以將局部密度ρi作為離群點(diǎn)的一個(gè)判斷條件，通過判斷局部密度是否為0 選擇離群點(diǎn)并刪除，再進(jìn)行接下來的聚類。算法的具體步驟用算法1 和算法2表示，其中算法1表示的是RSNN-DPC算法的整體過程，算法2表示的是在確定聚類中心后分配確定的從屬點(diǎn)與可能的從屬點(diǎn)的具體算法步驟。

算法1基于局部密度離群點(diǎn)檢測(cè)的改進(jìn)算法（RSNN-DPC）

輸入：相似度矩陣X，鄰居數(shù)目K，聚類數(shù)NC。

輸出：聚類結(jié)果Φ={C1,C2,…,CNC} ，離群點(diǎn)集合Ψ={ψ1,ψ2,…}。

步驟1對(duì)相似度矩陣X進(jìn)行預(yù)處理，根據(jù)轉(zhuǎn)換式（16），計(jì)算距離矩陣D。

步驟2根據(jù)式（2）計(jì)算相似性矩陣Sim(xi,xj)。

步驟3根據(jù)式（3）計(jì)算局部密度ρ。

步驟4篩選出局部密度ρi=0 的數(shù)據(jù)點(diǎn)作為離群點(diǎn)，輸出離群點(diǎn)集合Ψ={ψ1,ψ2,…}，并將數(shù)據(jù)集中的離群點(diǎn)刪除，對(duì)剩余樣本聚類。

步驟5根據(jù)式（4）、（5）計(jì)算最近距離δ。

步驟6根據(jù)式（6）計(jì)算所有點(diǎn)的決策值并按降序排列，得到排序后的γ′。

步驟7根據(jù)聚類個(gè)數(shù)NC，選擇γ′最大的前NC個(gè)點(diǎn)確定為聚類中心，由此產(chǎn)生聚類中心數(shù)據(jù)集Center={c1,c2,…,cNC}。

步驟8根據(jù)算法2，分配確定的從屬點(diǎn)和可能的從屬點(diǎn)，并將從屬點(diǎn)歸類到對(duì)應(yīng)的集合中，得到聚類結(jié)果Φ。

算法2分配確定的從屬點(diǎn)和可能的從屬點(diǎn)

輸入：聚類中心數(shù)據(jù)集Center={c1,c2,…,cNC}, 鄰居數(shù)目K，距離矩陣D。

輸出：最終聚類結(jié)果Φ={C1,C2,…,CNC}。

步驟1初始化隊(duì)列Q，將聚類中心Center中所有點(diǎn)置入隊(duì)列Q。

步驟2將隊(duì)列Q中第一個(gè)點(diǎn)xa從隊(duì)列中取出，根據(jù)距離矩陣D查找點(diǎn)xa的K個(gè)最近鄰，定義最近鄰集合為Ka。

步驟3依次選擇最近鄰集合中的未分配點(diǎn)x′∈Ka x′∈Ka，如果x′滿足條件（7），則將數(shù)據(jù)點(diǎn)x′歸類到xa所在的簇中，并將x′添加至隊(duì)列Q尾部，作為已知分配情況的樣本點(diǎn)；否則x′為可能的從屬點(diǎn)，暫時(shí)無法分配簇集，繼續(xù)選擇最近鄰集合Ka中的下一個(gè)點(diǎn)判斷分配情況，Ka中所有樣本點(diǎn)判斷完畢后轉(zhuǎn)步驟2，進(jìn)行隊(duì)列Q中下一個(gè)確定的從屬點(diǎn)的分配。

步驟4當(dāng)Q=?時(shí)，代表所有確定的從屬點(diǎn)已經(jīng)分配完畢，數(shù)據(jù)集中剩余點(diǎn)為可能的從屬點(diǎn)，接下來對(duì)可能的從屬點(diǎn)進(jìn)行分配。

步驟5找到未分配的可能的從屬點(diǎn)并重新編號(hào)。定義一個(gè)矩陣M，行表示未分配點(diǎn)的編號(hào)，列表示簇序號(hào)。

步驟6計(jì)算每一個(gè)未分配的點(diǎn)的鄰居中屬于各個(gè)簇的鄰居數(shù)，并將其寫入分配矩陣M的對(duì)應(yīng)簇的列元素中。

步驟7尋找中M每一行元素的最大值Mimax，用最大值所在的簇表示該行未分配點(diǎn)i的簇。分配完成后更新矩陣M，直到所有點(diǎn)均被分配。

步驟8輸出最終聚類結(jié)果Φ={C1,C2,…,CNC}。

2.2.2 基于LOF離群點(diǎn)檢測(cè)的改進(jìn)聚類算法（LSNN-DPC）

2.2.1小節(jié)采用局部密度來表示樣本點(diǎn)的密度情況，可以根據(jù)樣本點(diǎn)局部密度的差異檢測(cè)出密度明顯異常的點(diǎn)，但是由于局部密度受到鄰居數(shù)的影響較大，當(dāng)鄰居數(shù)取值不合理時(shí)，可能檢測(cè)不出離群點(diǎn)。在眾多的離群點(diǎn)檢測(cè)方法中，LOF（local outlier factor）方法[14]是一種典型的基于密度的離群點(diǎn)檢測(cè)方法，此方法能有效識(shí)別局部離群點(diǎn)和全局離群點(diǎn)，因此在離群點(diǎn)檢測(cè)問題中廣泛應(yīng)用。其主要定義如下：

定義7（ε-鄰域Nε(i)和數(shù)據(jù)點(diǎn)xi的k-距離Nk(i)）ε-鄰域定義為與數(shù)據(jù)點(diǎn)的距離小于ε的數(shù)據(jù)點(diǎn)集合。數(shù)據(jù)點(diǎn)的k-距離定義為與數(shù)據(jù)點(diǎn)的距離小于k_dist(i)的數(shù)據(jù)點(diǎn)集合。ε-鄰域用于確定數(shù)據(jù)點(diǎn)的密度特征比較范圍，即每個(gè)數(shù)據(jù)點(diǎn)的密度特征與其ε-鄰域內(nèi)的數(shù)據(jù)點(diǎn)比較。同樣，k_dist(i)表示數(shù)據(jù)點(diǎn)xi與距其第k近的數(shù)據(jù)點(diǎn)的距離，具體定義如式（18）所示：

其中，k為自然數(shù)。

定義8（數(shù)據(jù)點(diǎn)xi的核心距離cd(xi)）當(dāng)xi的ε-鄰域內(nèi)數(shù)據(jù)點(diǎn)數(shù)目大于MinPts時(shí)，xi的核心距離定義為xi的MinPts-距離，否則定義為0，具體如式（19）所示：

其中，MinPts為給定自然數(shù)。

定義9（數(shù)據(jù)點(diǎn)xi關(guān)于xj的可達(dá)距離rd(xi,xj)）當(dāng)xi的ε-鄰域內(nèi)數(shù)據(jù)點(diǎn)數(shù)目大于MinPts時(shí)，xi關(guān)于xj的可達(dá)距離定義為xi的核心距離與兩點(diǎn)之間真實(shí)距離的最大值，否則不作定義。也就是說，數(shù)據(jù)點(diǎn)xi關(guān)于xj的可達(dá)距離至少是xi的核心距離，或者是兩點(diǎn)之間的歐式距離。具體定義如式（20）所示：

定義10（數(shù)據(jù)點(diǎn)xi的局部可達(dá)密度lrd(xi)）局部可達(dá)密度定義為數(shù)據(jù)點(diǎn)xi的MinPts-鄰域內(nèi)數(shù)據(jù)點(diǎn)個(gè)數(shù)和xi與其鄰域內(nèi)其余數(shù)據(jù)點(diǎn)可達(dá)距離之和的比值，表征了數(shù)據(jù)點(diǎn)xi的局部密度。局部可達(dá)密度值越大，局部區(qū)域點(diǎn)的分布就越密集。定義如式（21）所示：

定義11（數(shù)據(jù)點(diǎn)xi的離群因子LOF(xi)）數(shù)據(jù)點(diǎn)xi的離群因子定義為xi的MinPts-鄰域內(nèi)數(shù)據(jù)點(diǎn)與xi點(diǎn)局部可達(dá)密度的平均比值。數(shù)據(jù)點(diǎn)的離群因子值越高，說明xi點(diǎn)與其鄰域內(nèi)數(shù)據(jù)點(diǎn)密度特征差異越顯著，其成為離群點(diǎn)的可能性也就越大。

xi的離群因子LOF(xi)表示的是一種密度對(duì)比，表示數(shù)據(jù)點(diǎn)與整體的一種密度差異。若LOF 值遠(yuǎn)遠(yuǎn)大于1，表示該點(diǎn)的密度與數(shù)據(jù)的整體密度差異較大，則認(rèn)為該點(diǎn)為離群點(diǎn)。假如LOF值接近于1，表示該點(diǎn)與整體的差異較小，因此可認(rèn)為該點(diǎn)為正常點(diǎn)。

為直觀表示說明，隨機(jī)生成一個(gè)100×2 的數(shù)據(jù)集，指定第99 個(gè)和第100 個(gè)數(shù)據(jù)為離群數(shù)據(jù)。圖1 用二維坐標(biāo)圖的形式說明了原始數(shù)據(jù)的分布情況，可以看出，大部分?jǐn)?shù)據(jù)分布在一個(gè)1×1的正方形區(qū)域內(nèi)，而第99個(gè)點(diǎn)和第100 個(gè)點(diǎn)遠(yuǎn)離樣本集合，明顯為離群點(diǎn)。圖2 展示了通過LOF算法計(jì)算的100個(gè)樣本點(diǎn)的離群度。

圖1 100個(gè)隨機(jī)數(shù)據(jù)分布二維示意圖Fig.1 Two-dimensional schematic diagram of 100 random data distribution

圖2 各數(shù)據(jù)樣本點(diǎn)LOF值比較Fig.2 Comparison of LOF value of each sample point

大部分LOF值在1附近波動(dòng)，表示大部分點(diǎn)密度與整體密度差異不大，而99 和100 個(gè)點(diǎn)的LOF 值遠(yuǎn)大于1，接近5和8，表示這兩點(diǎn)的密度與整體密度差異較大，因此可以認(rèn)為這兩點(diǎn)為離群點(diǎn)，這與之前的假設(shè)也是契合的。

在現(xiàn)實(shí)場(chǎng)景中，數(shù)據(jù)分布往往是非均勻的。LOF算法可以很好地解決基于距離和統(tǒng)計(jì)離群檢測(cè)方法無法檢測(cè)局部離群點(diǎn)的問題[15]，但其算法本身也存在一些不足：

對(duì)于分布較密的數(shù)據(jù)集，如果選擇的MinPts值較小，可能會(huì)出現(xiàn)部分對(duì)象的MinPts-距離為空值，導(dǎo)致其MinPts-鄰域內(nèi)的所有點(diǎn)到該點(diǎn)的距離都為0，在計(jì)算可達(dá)距離時(shí)會(huì)出現(xiàn)分母為0，導(dǎo)致LOF值無窮大的現(xiàn)象，會(huì)導(dǎo)致局部異常因子運(yùn)算異常。

LOF 算法的性能受參數(shù)MinPts影響較大，對(duì)于參數(shù)值的確定，需要一定的鄰域知識(shí)，這使得算法的難度加大。而且人工干預(yù)和經(jīng)驗(yàn)值的參與也會(huì)直接影響到算法在離群檢測(cè)中的性能。

基于LOF算法的兩個(gè)不足，本文提出利用SNN-DPC中定義的鄰居數(shù)K代替MinPts-鄰域中MinPts值的改進(jìn)方法。由于SNN-DPC 中定義的鄰居數(shù)是與某點(diǎn)xi距離最近的K個(gè)點(diǎn)的個(gè)數(shù)，MinPts-鄰域中的MinPts表示的含義與鄰居數(shù)K相近，因此用鄰居數(shù)K來替換鄰域值MinPts是合理的。將LOF 算法與SNN-DPC 算法相結(jié)合，此時(shí)只需要設(shè)置一個(gè)鄰居數(shù)K即可，有效減少了參數(shù)的輸入個(gè)數(shù)，降低了獲取參數(shù)的困難性。同時(shí)，由于定義的鄰居數(shù)不可能為0，也可以杜絕算法在運(yùn)行時(shí)出現(xiàn)分母為0的運(yùn)算錯(cuò)誤。

LSNN-DPC的具體算法步驟用算法3表示，其中包含的算法2在2.2.1節(jié)已作說明。

算法3基于LOF離群點(diǎn)檢測(cè)的改進(jìn)算法（LSNN-DPC）

輸入：相似度矩陣X，鄰居數(shù)目K，聚類數(shù)NC。

輸出：聚類結(jié)果Φ={C1,C2,…,CNC} ，離群點(diǎn)集合Ψ={ψ1,ψ2,…}。

步驟1對(duì)相似度矩陣進(jìn)行預(yù)處理，根據(jù)轉(zhuǎn)換公式（16），計(jì)算距離矩陣D。

步驟2根據(jù)離群因子計(jì)算式（22），計(jì)算各樣本點(diǎn)的LOF 值，找到超出閾值范圍的點(diǎn)，輸出離群點(diǎn)集合Ψ={ψ1,ψ2,…}，并將數(shù)據(jù)集中的離群點(diǎn)刪除，對(duì)剩余樣本點(diǎn)進(jìn)行聚類。

步驟3根據(jù)式（2）計(jì)算相似性矩陣Sim(xi,xj)。

步驟4根據(jù)式（3）計(jì)算局部密度ρ。

步驟5根據(jù)式（4）、（5）計(jì)算最近距離δ。

步驟6根據(jù)式（6）計(jì)算所有點(diǎn)的決策值并按降序排列，得到排序后的γ′。

步驟7根據(jù)聚類個(gè)數(shù)NC，選擇γ′最大的前NC個(gè)點(diǎn)確定為聚類中心，由此產(chǎn)生聚類中心數(shù)據(jù)集Center={c1,c2,…,cNC}。

步驟8根據(jù)算法2，分配確定的從屬點(diǎn)和可能的從屬點(diǎn)，并將從屬點(diǎn)歸類到對(duì)應(yīng)的集合中，得到聚類結(jié)果Φ。

3 實(shí)驗(yàn)分析

為了驗(yàn)證算法的有效性及可行性，本文選擇真實(shí)校園無線網(wǎng)絡(luò)中記錄下的數(shù)據(jù)集產(chǎn)生的相似度矩陣轉(zhuǎn)化后距離矩陣的Stu_500 和Stu_2000 進(jìn)行驗(yàn)證與評(píng)估。由分析可知，距離矩陣是通過最短時(shí)間距離子序列軌跡相似性度量模型得到的相似度矩陣通過轉(zhuǎn)換函數(shù)得到的。兩個(gè)數(shù)據(jù)集均由山東某高校2019 年9 月1 日至2019 年9 月30 日共一個(gè)月的學(xué)生軌跡記錄以及學(xué)生相關(guān)信息組成。表2 說明了兩個(gè)數(shù)據(jù)集包含學(xué)生種類的大致情況。

表2 數(shù)據(jù)集情況描述Table 2 Description of dataset

表3說明了本次實(shí)驗(yàn)的硬軟件環(huán)境及開發(fā)工具。

表3 實(shí)驗(yàn)環(huán)境Table 3 Experimental environment

為量化評(píng)價(jià)算法的檢測(cè)結(jié)果，需要使用評(píng)價(jià)指標(biāo)表示聚類效果的優(yōu)劣程度。校園無線網(wǎng)絡(luò)數(shù)據(jù)集是無標(biāo)簽的，因此不能依靠外部指標(biāo)，只能通過內(nèi)部指標(biāo)來判斷聚類形成的簇間距離和簇內(nèi)距離大小。一般來說，聚類的目標(biāo)是使得簇間距離增大而簇內(nèi)距離減小，通過對(duì)簇內(nèi)距離和簇間距離不同角度的組合判斷，提出以下幾種評(píng)價(jià)指標(biāo)。評(píng)價(jià)指標(biāo)根據(jù)趨勢(shì)分為兩類：一類指標(biāo)數(shù)值越大，聚類效果越好，稱為正相關(guān)指標(biāo)；另一類指標(biāo)數(shù)值越小，聚類程度越高，稱為負(fù)相關(guān)指標(biāo)。正相關(guān)指標(biāo)包括鄧恩指數(shù)（Dunn validity index）[16]、輪廓系數(shù)（Silhouette index，Sil）[17]；負(fù)相關(guān)指標(biāo)包括緊密性程度（compactness，CP）[18]、戴維森堡丁指數(shù)（Davies-Bouldin index，DBI）[19]。各個(gè)指標(biāo)都能夠從一個(gè)方面對(duì)聚類結(jié)果進(jìn)行一定的評(píng)估，但是也都存在一定的局限性，因此，應(yīng)將各種內(nèi)部指標(biāo)結(jié)合起來綜合評(píng)估，而不應(yīng)該因?yàn)橐粋€(gè)評(píng)價(jià)指標(biāo)沒有得到較好的評(píng)價(jià)結(jié)果而否定聚類效果[20]。

3.1 數(shù)據(jù)集預(yù)處理

學(xué)生相似度矩陣中存在數(shù)據(jù)缺失或者不完整的部分，會(huì)影響數(shù)據(jù)的正確性繼而不利于聚類，為了清除數(shù)據(jù)缺失等問題的影響，同時(shí)提高數(shù)據(jù)挖掘的質(zhì)量，需要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理操作。

缺失的數(shù)據(jù)一般指的是沒有采集到的數(shù)據(jù)或者是無限小的無效數(shù)據(jù)，對(duì)學(xué)生軌跡相似度的缺失處理分為兩種情況。對(duì)相似度矩陣中全零行或者全零列判斷為學(xué)生軌跡數(shù)據(jù)整體信息缺失，對(duì)于這部分?jǐn)?shù)據(jù)記錄其學(xué)生編號(hào)，采用整體賦值的辦法處理。而對(duì)相似度矩陣中某一行或一列有部分?jǐn)?shù)據(jù)缺失，即此人與其他大部分人有相似度，僅與小部分人相似度為0，對(duì)這部分?jǐn)?shù)據(jù)的處理與缺失值處理相同，當(dāng)相似度矩陣轉(zhuǎn)化為距離矩陣時(shí)賦一個(gè)比較大的數(shù)據(jù)，表示此人與這部分人相似度極低。

3.2 算法參數(shù)的選擇與分析

SNN-DPC算法中提出采用決策圖的方式確定聚類數(shù)。決策圖是將γ值降序排列后，以數(shù)據(jù)點(diǎn)個(gè)數(shù)為橫坐標(biāo)，以排序后的γ′值為縱坐標(biāo)。γ′值越大表示該點(diǎn)的局部密度ρ和最近距離δ越大，即越有可能成為聚類中心點(diǎn)。實(shí)驗(yàn)中的決策圖，即Stu_500 數(shù)據(jù)集與Stu_2000數(shù)據(jù)集得到的排序后的γ′值如圖3和圖4所示。

圖3 Stu_500決策圖Fig.3 Decision diagram of Stu_500

圖4 Stu_2000決策圖Fig.4 Decision diagram of Stu_2000

可以看到在決策圖中，γ′值比較大且遠(yuǎn)大于剩余點(diǎn)的γ′值的點(diǎn)均有兩個(gè)，已用紅色圓圈在圖中標(biāo)明。

因此以聚類數(shù)為2（NC=2）為例說明使用RSNNDPC與LSNN-DPC算法聚類后內(nèi)部指標(biāo)的差異。

明確聚類簇?cái)?shù)后，本實(shí)驗(yàn)可調(diào)整的參數(shù)僅包含鄰居數(shù)K。選擇合適的鄰居數(shù)范圍能夠有效減少尋找最優(yōu)鄰居數(shù)的時(shí)間，因此先對(duì)各個(gè)內(nèi)部指標(biāo)隨鄰居數(shù)變化情況進(jìn)行預(yù)實(shí)驗(yàn)，即令鄰居數(shù)K從小到大變化，觀察各指標(biāo)變化情況。對(duì)于鄰居數(shù)范圍選擇的下限，考慮到若鄰居數(shù)目過少，某些數(shù)據(jù)集中點(diǎn)密度過于稀疏，不具備相似性，而且對(duì)于某些數(shù)據(jù)集，可能因?yàn)镵過小導(dǎo)致錯(cuò)誤，因此下限確定為5。

圖5 和圖6 分別表示Stu_500 和Stu_2000 數(shù)據(jù)集Sil、DBI 兩個(gè)指標(biāo)的變化情況，圖（a）均為Stu_500 數(shù)據(jù)集，其K值從5到200變化，圖（b）對(duì)應(yīng)Stu_2000數(shù)據(jù)集各指標(biāo)隨鄰居數(shù)增加的變化情況，其K值從5到500變化。以Stu_500 數(shù)據(jù)集為例分析，Sil 指標(biāo)越大，表示聚類效果越好。由圖5（a）可知，當(dāng)鄰居數(shù)較少時(shí)，Sil指標(biāo)的震動(dòng)幅度較大，并且出現(xiàn)了多個(gè)峰值點(diǎn)，隨后，當(dāng)鄰居數(shù)K ＞50 時(shí)，Sil數(shù)值較平緩，意味著選擇鄰居數(shù)范圍為[5，50]就足以找到最優(yōu)鄰居數(shù)。

圖5 Sil指標(biāo)隨鄰居數(shù)增加的變化Fig.5 Change of Sil index as number of neighbors increases

DBI指標(biāo)值越小，表示聚類效果越好。觀察圖6（b）可以發(fā)現(xiàn)，當(dāng)鄰居數(shù)接近為10時(shí)，DBI達(dá)到一個(gè)最小值，可見此時(shí)對(duì)應(yīng)的K鄰居數(shù)為DBI 指標(biāo)最優(yōu)時(shí)的鄰居數(shù)，隨著鄰居數(shù)的增加，DBI的值越來越大，后期穩(wěn)定在一個(gè)比較高的數(shù)值，根據(jù)趨勢(shì)分析，不能再出現(xiàn)最小值點(diǎn)，因此，選擇鄰居數(shù)范圍為[5，60]足以找到使得DBI達(dá)到最優(yōu)時(shí)的鄰居數(shù)。

圖6 DBI指標(biāo)隨鄰居數(shù)增加的變化Fig.6 Change of DBI value as number of neighbors increases

綜合上述分析，對(duì)Stu_500 矩陣，鄰居數(shù)K的取值范圍確定為[5，60]即可，后續(xù)實(shí)驗(yàn)操作也將基于這個(gè)實(shí)驗(yàn)范圍進(jìn)行內(nèi)部指標(biāo)分析。運(yùn)用同樣的方法，對(duì)Stu_2000 矩陣進(jìn)行鄰居數(shù)K的取值判定，發(fā)現(xiàn)取值范圍為[5，300]可以滿足選擇最優(yōu)指標(biāo)的最低要求。

根據(jù)2.2.2 節(jié)對(duì)LOF 算法的分析，若離群因子值接近于1，表示樣本點(diǎn)與整體的差異較小，因此可認(rèn)為其為正常點(diǎn)，否則視為離群點(diǎn)。本文設(shè)置閾值為2，若計(jì)算出LOF≥2，則認(rèn)為該樣本點(diǎn)為離群點(diǎn)。

若分開使用LOF 算法和SNN-DPC 算法，需要設(shè)定LOF算法的MinPts距離，為保證實(shí)驗(yàn)的統(tǒng)一性，采用距離樣本點(diǎn)第10 遠(yuǎn)的樣本點(diǎn)（即MinPts=10）距離作為L(zhǎng)OF算法的MinPts距離。

3.3 離群點(diǎn)檢測(cè)數(shù)量的對(duì)比實(shí)驗(yàn)

本文采用兩種離群點(diǎn)檢測(cè)算法與SNNDPC 算法相結(jié)合，去除離群點(diǎn)的影響，增加聚類結(jié)果的可信度。離群點(diǎn)檢測(cè)在聚類之前進(jìn)行，因此不需要指定明確的聚類簇?cái)?shù)，兩種離群點(diǎn)檢測(cè)算法的變量?jī)H為鄰居數(shù)K。本節(jié)探討隨著鄰居數(shù)K的增加，RSNN-DPC 和LSNN-DPC兩種算法在檢測(cè)離群點(diǎn)個(gè)數(shù)方面的變化情況。

圖7（a）表示Stu_500矩陣，鄰居數(shù)K從5到60變化時(shí)，離群點(diǎn)數(shù)量變化情況?？梢园l(fā)現(xiàn)，隨著鄰居數(shù)的增加，LSNN-DPC算法得到的離群點(diǎn)個(gè)數(shù)，除了K ＜6 時(shí)離群點(diǎn)數(shù)量較大，剩余情況檢測(cè)出的離群點(diǎn)數(shù)量基本保持平穩(wěn)，可以說明該算法的穩(wěn)定性較高，不會(huì)隨著鄰居數(shù)的增大而產(chǎn)生太大變化。而通過RSNN-DPC尋找到的離群點(diǎn)數(shù)目受到鄰居數(shù)的影響較大，當(dāng)鄰居數(shù)較小時(shí)，離群點(diǎn)數(shù)量很大，隨著鄰居數(shù)目的增加，離群點(diǎn)的個(gè)數(shù)呈現(xiàn)出單調(diào)遞減的趨勢(shì)，但是在K ＞35 時(shí)，隨著鄰居數(shù)的增大得到離群點(diǎn)的數(shù)量穩(wěn)定。

圖7 離群點(diǎn)數(shù)量變化Fig.7 Change in number of outliers

圖7（b）表示Stu_2000矩陣，當(dāng)鄰居數(shù)K從5到300變化時(shí)，兩種算法得到的離群點(diǎn)數(shù)量變化情況?？梢园l(fā)現(xiàn)，隨著鄰居數(shù)K的增加，LSNN-DPC算法得到的離群點(diǎn)數(shù)目基本保持穩(wěn)定，而通過RSNN-DPC 算法得到的離群點(diǎn)數(shù)量呈遞減趨勢(shì)，兩者最終判斷的離群點(diǎn)數(shù)量接近一致。

通過兩個(gè)數(shù)據(jù)集的對(duì)比發(fā)現(xiàn)，隨著數(shù)據(jù)點(diǎn)總量的增加，LSNN-DPC檢測(cè)出的離群點(diǎn)數(shù)量更為統(tǒng)一。RSNNDPC前期離群點(diǎn)數(shù)量變化較大，后期離群點(diǎn)數(shù)量保持穩(wěn)定。兩者最終判斷的離群點(diǎn)個(gè)數(shù)趨于相同。

3.4 聚類內(nèi)部指標(biāo)的對(duì)比實(shí)驗(yàn)

通過比較聚類內(nèi)部指標(biāo)的具體數(shù)值，可以推斷出各個(gè)算法聚類的優(yōu)劣。本文用Stu_500 和Stu_2000 兩個(gè)校園無線網(wǎng)絡(luò)軌跡距離矩陣進(jìn)行實(shí)驗(yàn)，在計(jì)算各指標(biāo)時(shí)，將每個(gè)離群點(diǎn)單獨(dú)設(shè)置為一類，聚類中心為離群點(diǎn)本身。例如假設(shè)LSNN-DPC算法得到h個(gè)離群點(diǎn)，那么在計(jì)算各指標(biāo)時(shí)，計(jì)算的是h+NC個(gè)聚類中心與其對(duì)應(yīng)點(diǎn)之間的關(guān)系，這樣可以保證各個(gè)算法計(jì)算得到的指標(biāo)值考慮到所有樣本點(diǎn)，而不是完全不考慮離群點(diǎn)后指標(biāo)的變化。

表4至表6分別表示使用Stu_500矩陣，令K從5到60變化，每一種算法當(dāng)CP指標(biāo)、DBI指標(biāo)、Dunn指標(biāo)分別最優(yōu)時(shí)，對(duì)應(yīng)的鄰居數(shù)K及其對(duì)應(yīng)的CP指標(biāo)、DBI指標(biāo)、Dunn 指標(biāo)、Sil 指標(biāo)值。SNN-DPC 行表示原SNNDPC 算法未去除離群點(diǎn)的影響時(shí)聚類得到的各指標(biāo)，LSNN-DPC行代表LSNN-DPC算法得到的各指標(biāo)情況，RSNN-DPC行表示RSNN-DPC算法得到的各指標(biāo)對(duì)應(yīng)情況，LOF+SNN-DPC 行代表通過單獨(dú)使用LOF 算法（K=10），去掉離群點(diǎn)后再使用SNN-DPC 聚類算法得到的各指標(biāo)數(shù)值。

表4 CP指標(biāo)最優(yōu)時(shí)對(duì)應(yīng)其余各指標(biāo)值（Stu_500）Table 4 Other index values corresponding to optimal CP index（Stu_500）

表6 Dunn指標(biāo)最優(yōu)時(shí)對(duì)應(yīng)其余各指標(biāo)值（Stu_500）Table 6 Other index values corresponding to optimal Dunn index（Stu_500）

通過對(duì)表格的分析可知，最優(yōu)指標(biāo)集中出現(xiàn)在LSNN-DPC 和RSNN-DPC 中，說明文中所提出的兩種基于離群點(diǎn)檢測(cè)的SNN-DPC聚類算法在提高聚類效果上有一定的優(yōu)勢(shì)。其中LSNN-DPC 的CP 指標(biāo)表現(xiàn)最優(yōu)，說明使用LSNN-DPC得到的類簇，類內(nèi)距離近，簇內(nèi)聚合度最高。LOF+SNN-DPC 算法雖然能在一定程度上減少離群點(diǎn)對(duì)聚類效果的影響，但是由于參數(shù)K固定，并且參數(shù)的取值困難，導(dǎo)致參數(shù)取值不合適或者離群點(diǎn)判斷存在偏差，使聚類結(jié)果劣于LSNN-DPC 和RSNN-DPC。

表7 至表9 表示的是Stu_2000 矩陣聚為兩類時(shí)，當(dāng)K從5 到300 變化時(shí)，每一種算法得到的聚類結(jié)果中，CP、DBI、Dunn指標(biāo)最優(yōu)的鄰居數(shù)對(duì)應(yīng)的其余各指標(biāo)數(shù)值。表格各行的含義與Stu_500數(shù)據(jù)集定義相同。

表7 CP指標(biāo)最優(yōu)時(shí)對(duì)應(yīng)其余各指標(biāo)值（Stu_2000）Table 7 Other index values corresponding to optimal CP index（Stu_2000）

表9 Dunn指標(biāo)最優(yōu)時(shí)對(duì)應(yīng)其余各指標(biāo)值（Stu_2000）Table 9 Other index values corresponding to optimal Dunn index（Stu_2000）

通過對(duì)表格的分析可以發(fā)現(xiàn)，針對(duì)CP 指標(biāo)來說，LOF+SNN-DPC 算法是最優(yōu)的，說明針對(duì)Stu_2000，令MinPts=10 能夠單獨(dú)使用LOF算法找到對(duì)聚類影響最大的離群點(diǎn)。盡管LSNN-DPC 和RSNN-DPC 在CP 指標(biāo)上的表現(xiàn)差強(qiáng)人意，但是樣本點(diǎn)規(guī)模的擴(kuò)大沒有明顯影響到改進(jìn)后算法的聚類效果，LSNN-DPC 算法和RSNN-DPC 的大部分指標(biāo)均優(yōu)于SNN-DPC 和LOF+SNN-DPC。也就是說，兩種改進(jìn)算法對(duì)數(shù)據(jù)集中數(shù)據(jù)量增加的魯棒性較高，進(jìn)一步驗(yàn)證了基于離群點(diǎn)檢測(cè)的改進(jìn)SNN-DPC算法在無線網(wǎng)絡(luò)軌跡相似度數(shù)據(jù)集上的可行性。

表5 DBI指標(biāo)最優(yōu)時(shí)對(duì)應(yīng)其余各指標(biāo)值（Stu_500）Table 5 Other index values corresponding to optimal DBI value（Stu_500）

表8 DBI指標(biāo)最優(yōu)時(shí)對(duì)應(yīng)其余各指標(biāo)值（Stu_2000）Table 8 Other index values corresponding to optimal DBI value（Stu_2000）

另外，以Stu_500矩陣為例，通過上面數(shù)據(jù)的分析，當(dāng)NC=2 ，鄰居數(shù)K=37 時(shí)，比較LSNN-DPC 算法、RSNN-DPC 算法與未去除離群點(diǎn)的SNN-DPC 算法，對(duì)比結(jié)果如表10所示，其中聚類中心點(diǎn)8，279表示聚類中心點(diǎn)為編號(hào)為8和編號(hào)為279的兩個(gè)點(diǎn)。

表10 聚類結(jié)果對(duì)比Table 10 Comparison of clustering results

可以看到，LSNN-DPC 和RSNN-DPC 兩種算法不會(huì)影響聚類中心點(diǎn)的選取，只會(huì)去除邊緣的離群點(diǎn)，避免離群點(diǎn)對(duì)整體聚類效果的影響，優(yōu)化聚類效果。因此，基于離群點(diǎn)檢測(cè)的SNN-DPC 算法可以應(yīng)用于此類基于校園無線網(wǎng)絡(luò)軌跡數(shù)據(jù)的聚類研究中。

4 結(jié)束語

現(xiàn)有聚類算法大多數(shù)是利用歐氏距離、馬氏等距離來定義相似度，也就是說，大部分聚類算法直接利用距離矩陣對(duì)數(shù)據(jù)集進(jìn)行處理，而無法直接處理相似度矩陣。針對(duì)此問題，本文在校園無線網(wǎng)絡(luò)時(shí)空軌跡用戶相似性度量研究的基礎(chǔ)上，研究了聚類算法應(yīng)用于相似性矩陣上的可能性，將相似度矩陣轉(zhuǎn)化為距離矩陣，再通過基于密度的聚類算法進(jìn)行聚類分析。其次，由于大部分聚類算法未考慮到離群點(diǎn)對(duì)聚類結(jié)果的影響，本文提出了兩種基于離群點(diǎn)檢測(cè)的SNN-DPC 聚類算法，其中LSNN-DPC檢測(cè)出的離群點(diǎn)數(shù)目較為穩(wěn)定，RSNN-DPC算法檢測(cè)出的離群點(diǎn)數(shù)目前期變化較大，后期趨于穩(wěn)定。兩種改進(jìn)算法一方面可以減少輸入實(shí)驗(yàn)參數(shù)，另一方面在剔除離群點(diǎn)的影響后進(jìn)行聚類，可以提高聚類的聚合程度。通過實(shí)驗(yàn)驗(yàn)證，LSNN-DPC 和RSNN-DPC兩種改進(jìn)聚類算法各項(xiàng)指標(biāo)整體優(yōu)于SNN-DPC算法和LOF+SNN-DPC 算法。將改進(jìn)后的算法應(yīng)用到實(shí)際校園無線網(wǎng)絡(luò)軌跡行為特征的挖掘中，可以聚類校園中大部分用戶的軌跡數(shù)據(jù)，通過分析大部分用戶的行為特征，有利于分析學(xué)生之間的關(guān)聯(lián)性，可以為校園建設(shè)方案提供可靠依據(jù)。另外，對(duì)于算法得到的離群點(diǎn)，也可以找到相應(yīng)的用戶對(duì)其進(jìn)行處理，及時(shí)發(fā)現(xiàn)學(xué)生的異常，有針對(duì)性地對(duì)不同屬性的學(xué)生進(jìn)行管理。