基于ART神經網絡的運行軌跡聚類

薛方，王鵬，王軍

基于ART神經網絡的運行軌跡聚類

薛方，王鵬，王軍

（陜西重型汽車有限公司，陜西 西安 710200）

在商用車大數據研究領域，需在相同路況下對車輛的性能、油耗、載重等進行深入研究，那么就需要將相同軌跡的路線取出來，然后去研究這些路線上車輛的行駛狀況。文章要在海量的車輛運行數據（具有時間序列）中，對路線進行聚類。首先使用射線法判斷GPS點與區域（可視為多邊形）的拓撲關系，得到A市到B市之間的GPS數據，然后對GPS軌跡進行網格化處理，將網格劃分為0.01度，得到0-1稀疏矩陣，最后建立自適應共振理論(ART)神經網絡模型，對99條樣本進行聚類，通過調節閾值的大小，得到合適的聚類結果。

多邊形拓撲關系；網格化；稀疏矩陣；聚類；自適應共振理論；閾值

前言

針對具有相同的起點，相同的終點，但中間軌跡不完全相同的GPS軌跡，要從中取出軌跡一致的，以便后續對車的載重、油耗、性能、駕駛習慣等進行研究。本文使用了自適應共振理論（ART）神經網絡模型對軌跡樣本進行聚類。聚類前需要對原始GPS軌跡數據進行數據預處理，本文用到了射線法[1-3]，網格化稀疏矩陣。首先利用MATLAB自帶函數inpolygon，判斷點（GPS數據）在多邊形（區域）內、多邊形（區域）上還是多邊形（區域）外，得到駛出A市的時間點，駛入B市的時間點，然后提取該時間段內的GPS信息，即為A市到B市的運行軌跡。其次，進行網格化稀疏矩陣，將運行區域劃分為一個個的“網格”。本文將全部樣本的運行軌跡的覆蓋面進行網格化，計算覆蓋面經緯度的最大值和最小值，得到一個區間，對其以0.01度為步長進行網格化，得到每個樣本網格化后的0?1矩陣（稀疏矩陣）。最后，使用ART神經網絡[4-5]對99個數據處理后的0?1稀疏矩陣進行聚類。

1 點與多邊形的拓撲關系判斷

為判斷車輛何時駛入某個地區，何時駛出某個地區，我們將地區看成一個不規則的多邊形，車輛的運行狀態借助GPS信息看成點，因此計算車輛何時駛入何時駛出某個區域轉化為判斷點和多邊形的拓撲關系。

（1）點在多邊形邊界外：就是GPS點未進入觀測區域。

（2）點在多邊形邊界上：就是GPS點在觀測區域的邊界上。

（3）點在多邊形邊界內：就是GPS點進入了觀測區域內。

本文使用MATLAB自帶函數inpolygon識別點和多邊形的拓撲關系，得到點在多邊形內，點在多邊形上，點在多邊形外，從而確定每個點和多邊形的位置關系。圖1是使用函數識別出的點和多邊形的位置關系。

圖1 點和多邊形的位置關系

2 車輛運行區域識別

圖2 99條路線映射到地圖上

在某重卡車型的某細分市場中選取一個月運行數據，根據國家基礎地理信息系統數據（網上開源下載）中的省，市，縣界限，依據射線法對點與多邊形的拓撲關系進行判斷，得到了駛出A市的時間，駛入B市的時間，然后提取這段時間內的GPS信息，就得到了99條從A市到B市的路線，見圖2。

3 合理劃分網格

對全部樣本的GPS經緯度覆蓋區域進行網格劃分，將原來的精度縮減為網格大小，大大減少了計算量。

本文中網格劃分的方法如下：

第1步：計算99條樣本所覆蓋區域的經緯度區間。

經對樣本計算得到，緯度（latitude）區間是[28.689 1,31.257 9]，經度（longitude）區間是[120.203 3,121.520 5]。

第2步：設定網格大小。

以經緯度區間為上下限，間隔0.01度生成257×132大小的網格，間隔可以根據實驗結果設定。

第3步：劃分網格。

如果每個網格里出現GPS經緯度的次數超過1次，那么該網格的值記為1，否則記為0，因此得到0-1矩陣，如圖4所示。將全部99個樣本都轉換為0-1矩陣，接下來要使用ART神經網絡算法對0-1矩陣進行聚類。

圖3 原始GPS軌跡

圖4 網格化后的軌跡（網格大小為257×132）

4 聚類

4.1 自適應共振理論（ART）神經網絡

自適應共振理論（Adaptive Resonance Theory，縮寫為ART）網絡具有較大地靈活性，可以適應新輸入的模式，同時也避免了對網絡學習過的模式進行修改。記憶容量可以隨樣本的增加而自動增加，可以在不破壞原記憶樣本的情況下學習新的樣本。

ART模型算法步驟：

（1）初始化，設置前向連接權的初值為：w(0)=1/(1+)，其中為輸入層單元數，反饋連接權最終將記憶已經學過的輸入模式，其值最終為0和1二值的形式，為在開始時不丟失信息，設：t(0)=1,=1,2,…,;=1,2, …,。按需求設識別閾值0＜≤1，識別閾值越大，分類越細；識別閾值越小，分類越粗。

（5）如果小于，取消識別結果，將神經元排除在識別范圍之外，返回第（3）步。當所有已記憶過的神經元都不滿足（4）時，則在輸出層增加一個神經元，并令這個神經元為神經元的連接權和反饋連接權均為X。

（6）按下式調整連接權和反饋連接權：

（7）返回第2步，對下一個輸入模式進行識別。

4.2 實驗結果

對合理劃分網格得到的99個0?1矩陣使用自適應共振理論（ART）網絡算法，建立=339 24，=99的網絡，然后設置識別閾值進行聚類，識別閾值的大小決定聚類的程度，針對本文樣本，識別閾值等于0.94的情況下得到以下分類結果：99個樣本分為17類，其中第1類有66個樣本，在進行車輛性能測試，油耗比對，載重估計，駕駛行為等研究時，我們通常選擇聚類樣本較多的某些類進行深入研究。

5 結語

本文以真實的GPS軌跡為輸入數據，經過數據預處理得到0?1稀疏矩陣，再使用自適應共振理論（ART）神經網絡算法對其進行聚類，得到軌跡一致的路線，方便對車輛性能的深入研究和應用，聚類效果好。

[1] 常勝,宋鄂平.射線法的完善及其在地理信息系統中的應用[J].湖北民族學院學報（自然科學版）,2004.3,22(1):91-93.

[2] 翟艷,徐衛亞,張強.點與多邊形或多面體的拓撲關系判斷[J].計算機工程與設計,2015.4,36(4):972-975.

[3] 向俊,王靜,夏幼明.判斷點與多邊形拓撲關系的改進算法[J].計算機工程與設計,2014.5,35(5):1732-1737.

[4] 楊戈,莫青青,黃靜.基于ART1網絡的字符識別器[J].計算機系統應用,2014,12(23):136-141.

[5] 韓可軼,周德儉,張烈平,等.基于人工神經網絡自適應共振理論的手寫字符識別[J].桂林工商學院學報.2006,26(1):122-124.

Trajectory Clustering Based on ART Neural Network

XUE Fang, WANG Peng, WANG Jun

( Shaanxi Heavy Duty Automobile Co., Ltd., Shaanxi Xi’an 710200 )

In the research field of big data of commercial vehicles, the performance, fuel consumption and load of vehicles should be studied in depth under the same road conditions. Then, the routes with the same trajectory should be taken out and the driving conditions of vehicles on these routes should be studied. In this paper, the route is clustered in the massive vehicle operation data (with time series). Firstly, the topological relationship between GPS points and regions (which can be regarded as polygons) is determined by ray method, and the GPS data between A city and B city is obtained. Then, the GPS track is processed by grid. The mesh is divided into 0.01 degree and 0-1 sparse matrix is obtained. Finally, an adaptive resonance theory (ART) neural network model was established to cluster the 99 samples, and the appropriate clustering results were obtained by adjusting the threshold value.

Polygon topological relation; Grid; Sparse matrix; Cluster; ART; The threshold value

P228.4

A

1671-7988(2021)20-37-04

P228.4

A

1671-7988(2021)20-37-04

10.16638/j.cnki.1671-7988.2021.020.010

薛方（1989—），女，碩士，工程師，就職于陜西重型汽車有限公司，研究方向：數據挖掘，機器學習，深度學習，控制策略。