李紀華，劉建玲，肖瑞

（中國聯(lián)合網(wǎng)絡(luò)通信有限公司北京市分公司，北京 100038）

1 引言

基于信令數(shù)據(jù)在交通領(lǐng)域的挖掘應(yīng)用具有很大價值，由于目前智能移動終端的滲透率越來越高，因此移動信令的數(shù)據(jù)包含了用戶的出行行為特征、出行時間及出行地點等信息。這些信息不僅能夠用來分析用戶的出行偏好和出行方式，還可以預(yù)測用戶的出行時間分布，為交通部門、城市規(guī)劃部門提供巨大的參考意義。基于信令數(shù)據(jù)的交通出行分布異常檢測的方法不僅能夠輕量級反映用戶的出行分布規(guī)律以及出行異常情況，大大提高城市交通部門的信息化水平，而且能夠節(jié)省城市交通部門昂貴的硬件支出與維護，因此受到了越來越多研究者的關(guān)注。

2 異常檢測的方法

異常檢測又叫偏差檢測，其目的是把不滿足一定分布或者反常的對象找出來，以達到管理異常對象的目的。異常檢測的方法有以下5種：

（1）基于分布的方法

基于異常分布的方法的原理是通過分析整個數(shù)據(jù)集的分布規(guī)律，例如二項分布、泊松分布或正態(tài)分布等，利用概率等原理發(fā)現(xiàn)一些分布不一致的數(shù)據(jù)。該方法的優(yōu)點是具有較高的異常檢測效率，但缺點就是使用者很難確定數(shù)據(jù)集的分布。

（2）基于深度的方法

基于深度的方法的原理是通過把數(shù)據(jù)映射到數(shù)據(jù)集的K維向量中，然后賦給數(shù)據(jù)一個深度值，最后利用異常檢測的方法把深度較小的值找出來。該方法的優(yōu)點是可以計算高維數(shù)據(jù)的異常性，缺點是該算法隨著數(shù)據(jù)維度的增大計算復(fù)雜度迅速增加，導(dǎo)致檢測效率大大降低。

（3）基于距離的方法

基于距離的方法的原理是通過計算1個點O在一定距離D內(nèi)的數(shù)量，如果數(shù)量小于某一個閾值，則判定O點為異常點。該算法的優(yōu)點是容易使用，在實際場景使用較多，但缺點也很明顯：對線性分布的數(shù)據(jù)異常檢測的準確性很低。

（4）基于聚類的方法

基于聚類的方法的原理是通過對相似性的計算，找出數(shù)據(jù)集中不同的類簇，對小類簇進行判別從而得出異常對象。該算法的優(yōu)點是不需要考慮數(shù)據(jù)的分布以及聚類的種類，適用于海量數(shù)據(jù)的檢測，缺點是由于利用相似性進行數(shù)據(jù)的度量，因此處理高維數(shù)據(jù)時效率相對較低。

（5）基于密度的方法

基于密度的方法的原理是通過測量給定范圍的密度，如果該密度超出一定閾值，那么可以認定該范圍是異常區(qū)域。該算法的優(yōu)點是計算簡單，能夠很好處理不同密度的區(qū)域，缺點是計算復(fù)雜度很高，對于高維數(shù)據(jù)的計算效率相對較低。

3 基于空間密度聚類方法進行交通出行 分布異常檢測

基于空間密度聚類方法進行交通出行分布異常檢測主要解決的技術(shù)問題是如何利用移動運營商一系列的信令數(shù)據(jù)進行分析挖掘，從而識別交通出行分布的異常，通過結(jié)合移動通信技術(shù)和大數(shù)據(jù)挖掘技術(shù)，使得交通部門及城市建設(shè)規(guī)劃部門能夠降低分析用戶出行狀態(tài)的成本，通過用戶出行的規(guī)律間接反映城市道路交通結(jié)構(gòu)的合理性，為智慧交通的建設(shè)提供很好的支撐作用。

3.1 DBSCAN算法的介紹

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪聲的基于密度的聚類方法）的基本原理是：對于簇中的每一個點，在設(shè)定的半徑范圍內(nèi)至少包括設(shè)定數(shù)據(jù)的點。該算法把具有足夠密度的區(qū)域劃分成一類，優(yōu)點是對于帶“噪音”的空間數(shù)據(jù)可以發(fā)現(xiàn)任何形狀的聚類，聚類速度很快。

3.2 基于DBSCAN算法的交通出行分布異常檢測 過程

（1）通過小區(qū)切換法識別道路上的用戶

擁有智能手機的用戶在道路上發(fā)生語音或者數(shù)據(jù)業(yè)務(wù)的時候，信令會記錄用戶在連續(xù)多個小區(qū)發(fā)生的小區(qū)切換，如果一個用戶在一段時間內(nèi)連續(xù)發(fā)生多個小區(qū)切換的現(xiàn)象，則認為該用戶的地理位置在道路上。表1是通過對信令數(shù)據(jù)提取的字段表：

表1 基于小區(qū)切換法識別道路上用戶

（2）基于手機信令的用戶定位

1）路測方式獲得用戶定位的信息庫

本文首先把道路劃分成一個30m×30m的網(wǎng)格，然后利用路測方式確定每一個網(wǎng)格可能接收到的小區(qū)數(shù)量以及相應(yīng)的場強，建立小區(qū)-網(wǎng)格定位的位置信息庫。

2）位置信息庫匹配定位的過程

信息庫定位算法最大特點就是僅僅通過小區(qū)就能實現(xiàn)用戶的定位，無需增加額外的設(shè)備。位置識別依靠表征目標特征的數(shù)據(jù)庫進行，其定位過程主要包括訓(xùn)練階段和定位階段，具體如下：

◆訓(xùn)練階段的目標在于建立一個位置信息識別數(shù)據(jù)庫。首先選擇參考點分布，確保能為定位階段的準確位置估計提供足夠的信息。接著依次在各個參考點上測量來自不同接收小區(qū)的電平，將相應(yīng)的小區(qū)號碼與參考點的位置信息記錄在數(shù)據(jù)庫中，直至遍歷關(guān)注區(qū)域內(nèi)所有的參考點。

◆在定位置信息識別數(shù)據(jù)庫后，依據(jù)一定的匹配算法將待測點上接收的小區(qū)號碼、電平值與數(shù)據(jù)庫中的已有數(shù)據(jù)進行比較，計算位置估計值。

3）基于KNN算法的位置識別

KNN（K-Nearest Neighbor，最鄰近規(guī)則）算法的基本原理是：首先計算測試點與識別庫中參考點之間的相似度距離，按照距離的降序選出前k個近鄰值，有以下公式：

其次計算測試點的k個近鄰值每類的權(quán)重，計算公式如下：

（3）基于DBSCAN的交通出行分布異常檢測

1）交通出行分布異常點的確定

通過計算道路上出行用戶的局部密度，當局部密度大于設(shè)定的值時，則認為該點是交通出行分布異常點（異常點也就是異常網(wǎng)格），有如下公式：

其中，γi表示道路網(wǎng)格數(shù)據(jù)集與網(wǎng)格xi之間的距離小于設(shè)定距離的網(wǎng)格個數(shù)；δi表示設(shè)定的局部距離，一般該道路的總網(wǎng)格長度的1%～2%為最佳距離。

2）交通出行分布邊界的確定

一旦確定出行異常點，下一步就是對非異常網(wǎng)格進行歸類，具體步驟是：按照網(wǎng)格的密度從大到小進行遍歷；通過密度獲得每一個異常點的網(wǎng)格編號；按照密度大小的方法對異常點進行降序，按照每一個異常點所包含的網(wǎng)格密度的順序確定異常點的邊界。按照降序方法的好處在于異常點之間的交叉區(qū)域由于先進行了降序的處理而能夠快速確定邊界。

4 實驗結(jié)果

本文采用某地市某運營商提供的2015年8月1號到8月28號的IUCS接口數(shù)據(jù)和IUPS接口數(shù)據(jù)，IUCS數(shù)據(jù)約為3TGB，IUPS數(shù)據(jù)約為15TGB，包含400多萬用戶的數(shù)據(jù)，其中IUCS數(shù)據(jù)約150億條，IUPS數(shù)據(jù)約200億條，實驗結(jié)果如圖1所示：

圖1 交通出行分布異常檢測圖

該系統(tǒng)是基于20個集群搭建的Hadoop平臺進行數(shù)據(jù)處理和分析，采用SSH框架實現(xiàn)Web的加載與渲染，以每0.5h為顆粒度來展現(xiàn)某地市道路出行分布異常檢測情況。本文把基于DBSCAN算法找出的交通異常點發(fā)生的區(qū)域與實際的交通路況進行驗證，情況基本比較吻合。

5 結(jié)束語

基于信令數(shù)據(jù)的交通出行分布異常檢測的方法不僅能夠快速發(fā)現(xiàn)交通出行分布的異常檢測，而且具有投資小、數(shù)據(jù)采集簡便、實用性強及計算復(fù)雜度小的優(yōu)點，因此應(yīng)強化其在智慧交通領(lǐng)域的應(yīng)用。

[1] ESTER M, KRIEGEL H, SANDER J, et al. A densitybased algorithm for discovering clusters in large spatial databases with noise[C]. Portland: AAAI Press, 1996: 226-231.

[2] QIAN Wei-ning, GONG Xue-qing, AO Ying-zhou. Clustering in very large databases based on distance and density[J]. Journal of Computer Science and Technology, 2003,18(1): 67-76.

[3] ZHOU Shui-geng, ZHOU Ao-ying, CAO Jing, et al. A fast density-based clustering algorithm[J]. Journal of Computer Research and Development, 2000,37(11): 1287-1292.

[4] ESTER M, KRIEGEL H P, SANDER J, et al. Incremental clustering for mining in a data warehousing environment[C]. New York: Morgan Kaufmann, 1998: 323-333.

[5] Alex Rodriguez, Alessandro Laio. Clustering by fast search and find of density peaks[J]. Science, 2014,344(6191): 1492-1498.

[6] Rakesh A, Johanners G, Dimitrios G, et al. Automatic subspace clustering of high dimensional data for data mining applications[J]. Data Mining & Knowledge Discovery, 1994,27(2): 94-105.

[7] Hans-Peter Kriegel, Peer Kroger, Alexey Pryakhin, et al. Effective and efficient distributed model-based clustering[C]. Houston: Data Mining, 2005(11): 8-19.

[8] Maria Halkidi, Michalis Vazirgiannis. Clustering validity assessment: Finding the optimal partitioning of a data set[C]. California: Data Mining, 2001: 187-194.

[9] 熊忠陽,孫思,張玉芳,等. 一種基于劃分的不同參數(shù)值得DBSCAN算法[J]. 計算機工程與設(shè)計, 2005,26(9): 2319-2321.

[10] 楊靜. 分層模糊最小——最大聚類算法及其在圖像聚類中的應(yīng)用研究[D]. 合肥: 合肥工業(yè)大學(xué), 2007.

[11] 許慧. 基于數(shù)據(jù)分區(qū)和QR*樹的并行DBSCAN算法研究[D]. 哈爾濱: 哈爾濱工程大學(xué), 2007. ★