呂 奕，劉漫丹

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

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

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

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

本文采用基于共享最近鄰的快速搜索密度峰值聚類算法（shared-nearest-neighbor-based clustering by fast search and find of density peaks，SNN-DPC）[8]對校園無線網(wǎng)絡(luò)軌跡進(jìn)行聚類分析，在傳統(tǒng)的局部密度的核密度計算方式的基礎(chǔ)上，改進(jìn)局部密度度量，使得算法適用于多比例、各密度以及數(shù)據(jù)集之間交叉纏繞等高維度的復(fù)雜數(shù)據(jù)集，更有利于對校園無線網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行聚類分析。聚類算法對離群點(diǎn)信息較為敏感，若將離群點(diǎn)算法與聚類算法相結(jié)合，可以有效減小離群點(diǎn)對整體聚類的影響。因此，本文將離群點(diǎn)檢測算法與SNN-DPC 聚類算法相結(jié)合，得到兩種改進(jìn)后的SNN-DPC算法，兩種改進(jìn)算法均克服了原有聚類算法對離群點(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ǔ)上，考慮了每個點(diǎn)的鄰居的影響，引入了一種間接距離和密度的測量方法，利用共享鄰居的概念來描述點(diǎn)的局部密度和它們之間的距離[9]。

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

定義2（SNN相似度Sim(xi,xj)）點(diǎn)xi和xj之間的相似性程度稱為SNN相似度。對于數(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鄰居集合中時，才計算SNN相似度。否則，點(diǎn)xi和點(diǎn)xj之間的SNN相似度為0。在定義任意兩個點(diǎn)的SNN 相似度之后，使用該相似度來計算點(diǎn)xi的局部密度ρi。

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

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

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

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

可以看出，最近距離δ不僅考慮了距離因素，同時考慮了每個點(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)的ρ和δ越大，對應(yīng)的數(shù)據(jù)點(diǎn)越有可能成為聚類中心。根據(jù)決策值確定聚類中心點(diǎn)之后，SNN-DPC 算法對未分配的點(diǎn)分為兩類考慮，確定的從屬點(diǎn)與可能的從屬點(diǎn)。

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

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

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

SNN-DPC算法在計算樣本點(diǎn)間相似度時采用的是歐式距離代表數(shù)據(jù)點(diǎn)之間的相似程度，距離越大，表示相似性程度越低，因此不能利用相似度矩陣直接進(jìn)行計算。本文首先通過轉(zhuǎn)換函數(shù)，將相似度矩陣轉(zhuǎn)變?yōu)榫嚯x矩陣，再使用SNN-DPC算法，可以提高聚類算法對各種相似度矩陣的適應(yīng)度。聚類可以對相關(guān)性較強(qiáng)的樣本進(jìn)行劃分，而離群點(diǎn)檢測可以對相關(guān)性非常弱的樣本點(diǎn)進(jìn)行分類，聚類與離群點(diǎn)分析可以形成一種互補(bǔ)關(guān)系。SNN-DPC 算法中沒有對離群點(diǎn)進(jìn)行分析，在處理確定的從屬點(diǎn)與可能的從屬點(diǎn)時力求每一個點(diǎn)都可以安排到一個確定的簇，因此不可避免地會受到離群點(diǎn)對聚類結(jié)果的影響。本文通過將離群點(diǎn)檢測算法與SNN-DPC算法相結(jié)合，先對數(shù)據(jù)集中的離群點(diǎn)做“高亮”處理，對剩下的點(diǎn)進(jìn)行聚類，可以提高聚類的準(zhǔn)確性與快速性，達(dá)到較好的聚類效果。另外，檢測出的離群點(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)行編號。用戶某天的時空軌跡序列如表1所示，其中l(wèi)表示用戶所在區(qū)域編號，t表示用戶在該地的網(wǎng)絡(luò)登錄時間，m為用戶總量，W1,W2,…,Wm分別表示各用戶軌跡序列中的登錄記錄總數(shù)。

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

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

相似度信息包括時間相似性與空間相似性。

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

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

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

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

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

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

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

其中，Wθ表示LCSS序列的長度。

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

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

其中，sij表示用戶i和用戶j之間的相似度，即式（13）中的UCor(Ri,Rj)，0 ≤sij≤1。矩陣的對角線元素為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)檢測的SNN-DPC聚類算法

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

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

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

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

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

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

通過對局部密度的分析可知，局部密度ρ不僅利用距離信息，而且還通過共享最近鄰數(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)的一個判斷條件，通過判斷局部密度是否為0 選擇離群點(diǎn)并刪除，再進(jìn)行接下來的聚類。算法的具體步驟用算法1 和算法2表示，其中算法1表示的是RSNN-DPC算法的整體過程，算法2表示的是在確定聚類中心后分配確定的從屬點(diǎn)與可能的從屬點(diǎn)的具體算法步驟。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1小節(jié)采用局部密度來表示樣本點(diǎn)的密度情況，可以根據(jù)樣本點(diǎn)局部密度的差異檢測出密度明顯異常的點(diǎn)，但是由于局部密度受到鄰居數(shù)的影響較大，當(dāng)鄰居數(shù)取值不合理時，可能檢測不出離群點(diǎn)。在眾多的離群點(diǎn)檢測方法中，LOF（local outlier factor）方法[14]是一種典型的基于密度的離群點(diǎn)檢測方法，此方法能有效識別局部離群點(diǎn)和全局離群點(diǎn)，因此在離群點(diǎn)檢測問題中廣泛應(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)的密度特征比較范圍，即每個數(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時，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時，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)個數(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)表示的是一種密度對比，表示數(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ī)生成一個100×2 的數(shù)據(jù)集，指定第99 個和第100 個數(shù)據(jù)為離群數(shù)據(jù)。圖1 用二維坐標(biāo)圖的形式說明了原始數(shù)據(jù)的分布情況，可以看出，大部分?jǐn)?shù)據(jù)分布在一個1×1的正方形區(qū)域內(nèi)，而第99個點(diǎn)和第100 個點(diǎn)遠(yuǎn)離樣本集合，明顯為離群點(diǎn)。圖2 展示了通過LOF算法計算的100個樣本點(diǎn)的離群度。

圖1 100個隨機(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附近波動，表示大部分點(diǎn)密度與整體密度差異不大，而99 和100 個點(diǎn)的LOF 值遠(yuǎn)大于1，接近5和8，表示這兩點(diǎn)的密度與整體密度差異較大，因此可以認(rèn)為這兩點(diǎn)為離群點(diǎn)，這與之前的假設(shè)也是契合的。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟8根據(jù)算法2，分配確定的從屬點(diǎn)和可能的從屬點(diǎn)，并將從屬點(diǎn)歸類到對應(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)證與評估。由分析可知，距離矩陣是通過最短時間距離子序列軌跡相似性度量模型得到的相似度矩陣通過轉(zhuǎn)換函數(shù)得到的。兩個數(shù)據(jù)集均由山東某高校2019 年9 月1 日至2019 年9 月30 日共一個月的學(xué)生軌跡記錄以及學(xué)生相關(guān)信息組成。表2 說明了兩個數(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

為量化評價算法的檢測結(jié)果，需要使用評價指標(biāo)表示聚類效果的優(yōu)劣程度。校園無線網(wǎng)絡(luò)數(shù)據(jù)集是無標(biāo)簽的，因此不能依靠外部指標(biāo)，只能通過內(nèi)部指標(biāo)來判斷聚類形成的簇間距離和簇內(nèi)距離大小。一般來說，聚類的目標(biāo)是使得簇間距離增大而簇內(nèi)距離減小，通過對簇內(nèi)距離和簇間距離不同角度的組合判斷，提出以下幾種評價指標(biāo)。評價指標(biāo)根據(jù)趨勢分為兩類：一類指標(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]。各個指標(biāo)都能夠從一個方面對聚類結(jié)果進(jìn)行一定的評估，但是也都存在一定的局限性，因此，應(yīng)將各種內(nèi)部指標(biāo)結(jié)合起來綜合評估，而不應(yīng)該因?yàn)橐粋€評價指標(biāo)沒有得到較好的評價結(jié)果而否定聚類效果[20]。

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

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

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

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

SNN-DPC算法中提出采用決策圖的方式確定聚類數(shù)。決策圖是將γ值降序排列后，以數(shù)據(jù)點(diǎn)個數(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)均有兩個，已用紅色圓圈在圖中標(biāo)明。

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

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

圖5 和圖6 分別表示Stu_500 和Stu_2000 數(shù)據(jù)集Sil、DBI 兩個指標(biāo)的變化情況，圖（a）均為Stu_500 數(shù)據(jù)集，其K值從5到200變化，圖（b）對應(yīng)Stu_2000數(shù)據(jù)集各指標(biāo)隨鄰居數(shù)增加的變化情況，其K值從5到500變化。以Stu_500 數(shù)據(jù)集為例分析，Sil 指標(biāo)越大，表示聚類效果越好。由圖5（a）可知，當(dāng)鄰居數(shù)較少時，Sil指標(biāo)的震動幅度較大，并且出現(xiàn)了多個峰值點(diǎn)，隨后，當(dāng)鄰居數(shù)K ＞50 時，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時，DBI達(dá)到一個最小值，可見此時對應(yīng)的K鄰居數(shù)為DBI 指標(biāo)最優(yōu)時的鄰居數(shù)，隨著鄰居數(shù)的增加，DBI的值越來越大，后期穩(wěn)定在一個比較高的數(shù)值，根據(jù)趨勢分析，不能再出現(xiàn)最小值點(diǎn)，因此，選擇鄰居數(shù)范圍為[5，60]足以找到使得DBI達(dá)到最優(yōu)時的鄰居數(shù)。

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

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

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

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

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

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

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

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

通過比較聚類內(nèi)部指標(biāo)的具體數(shù)值，可以推斷出各個算法聚類的優(yōu)劣。本文用Stu_500 和Stu_2000 兩個校園無線網(wǎng)絡(luò)軌跡距離矩陣進(jìn)行實(shí)驗(yàn)，在計算各指標(biāo)時，將每個離群點(diǎn)單獨(dú)設(shè)置為一類，聚類中心為離群點(diǎn)本身。例如假設(shè)LSNN-DPC算法得到h個離群點(diǎn)，那么在計算各指標(biāo)時，計算的是h+NC個聚類中心與其對應(yīng)點(diǎn)之間的關(guān)系，這樣可以保證各個算法計算得到的指標(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)時，對應(yīng)的鄰居數(shù)K及其對應(yīng)的CP指標(biāo)、DBI指標(biāo)、Dunn 指標(biāo)、Sil 指標(biāo)值。SNN-DPC 行表示原SNNDPC 算法未去除離群點(diǎn)的影響時聚類得到的各指標(biāo)，LSNN-DPC行代表LSNN-DPC算法得到的各指標(biāo)情況，RSNN-DPC行表示RSNN-DPC算法得到的各指標(biāo)對應(yīng)情況，LOF+SNN-DPC 行代表通過單獨(dú)使用LOF 算法（K=10），去掉離群點(diǎn)后再使用SNN-DPC 聚類算法得到的各指標(biāo)數(shù)值。

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

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

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

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

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

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

通過對表格的分析可以發(fā)現(xiàn)，針對CP 指標(biāo)來說，LOF+SNN-DPC 算法是最優(yōu)的，說明針對Stu_2000，令MinPts=10 能夠單獨(dú)使用LOF算法找到對聚類影響最大的離群點(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)算法對數(shù)據(jù)集中數(shù)據(jù)量增加的魯棒性較高，進(jìn)一步驗(yàn)證了基于離群點(diǎn)檢測的改進(jìn)SNN-DPC算法在無線網(wǎng)絡(luò)軌跡相似度數(shù)據(jù)集上的可行性。

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

表8 DBI指標(biāo)最優(yōu)時對應(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 時，比較LSNN-DPC 算法、RSNN-DPC 算法與未去除離群點(diǎn)的SNN-DPC 算法，對比結(jié)果如表10所示，其中聚類中心點(diǎn)8，279表示聚類中心點(diǎn)為編號為8和編號為279的兩個點(diǎn)。

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

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

4 結(jié)束語

現(xiàn)有聚類算法大多數(shù)是利用歐氏距離、馬氏等距離來定義相似度，也就是說，大部分聚類算法直接利用距離矩陣對數(shù)據(jù)集進(jìn)行處理，而無法直接處理相似度矩陣。針對此問題，本文在校園無線網(wǎng)絡(luò)時空軌跡用戶相似性度量研究的基礎(chǔ)上，研究了聚類算法應(yīng)用于相似性矩陣上的可能性，將相似度矩陣轉(zhuǎn)化為距離矩陣，再通過基于密度的聚類算法進(jìn)行聚類分析。其次，由于大部分聚類算法未考慮到離群點(diǎn)對聚類結(jié)果的影響，本文提出了兩種基于離群點(diǎn)檢測的SNN-DPC 聚類算法，其中LSNN-DPC檢測出的離群點(diǎn)數(shù)目較為穩(wěn)定，RSNN-DPC算法檢測出的離群點(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)聚類算法各項指標(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ù)。另外，對于算法得到的離群點(diǎn)，也可以找到相應(yīng)的用戶對其進(jìn)行處理，及時發(fā)現(xiàn)學(xué)生的異常，有針對性地對不同屬性的學(xué)生進(jìn)行管理。