基于草原牲畜放牧軌跡的數據挖掘研究

邢光磊，周李涌，李寶山

(內蒙古科技大學 信息工程學院，內蒙古 包頭 014010)

近年來，隨著大數據技術發展迅速，產生了海量的時空軌跡數據，時空軌跡數據挖掘的研究已成為國內外的一個研究熱點[1]。Teimouri, Maryam等人[2]提出了一種利用從軌跡數據中提取的運動參數來推導動物的運動行為(行走，覓食和休息)的方法。對每只動物的個體運動路徑進行量化。選擇適當的運動參數表示。Clark, Patrick E.等人[3]對于麋鹿和牛的行為通過GPS跟蹤系統進行分類，在兩項隨機試驗中，識別成年牛和圈養麋鹿牧場的GPS記錄喂食、行走和靜態行為。在移動對象數據挖掘中，主要以移動對象的歷史行為數據，即軌跡數據作為研究對象，發現其中潛在的信息和有用的知識，如：移動對象行為特征、行為模式、環境影響等[4]。

在大數據技術日益普及中，草原畜牧業也得到快速發展。牧羊人在放牧過程中使用定位系統產生大量軌跡數據。在處理軌跡數據上，結合傳統軌跡挖掘技術并針對草原畜牧業牲畜運動軌跡特有特點，筆者提出了一種適合牧區的軌跡挖掘模型，并利用Hadoop開源平臺的數據計算處理框架[5,6]，對軌跡數據進行預處理，提高算法處理效率。最后通過真實軌跡數據對于該模型進行驗證，結果證明了模型的有效性，對后續草原科學放牧的研究是具有重要意義的。

1 軌跡數據處理

對于放牧產生的軌跡數據可以提取數據中潛藏的信息。然而，并不是全部的數據都能應用于研究。在牲畜上GPS定位設備產生的軌跡數據中存在一些無效數據、重復數據和噪聲數據。為了提高數據挖掘的準確性，必須剔除無效數據，并根據現有的軌跡數據提取有用數據，以便于后續分析。

1.1 實驗數據來源

筆者使用的數據是蘇尼特左旗某牧區放牧中產生的軌跡數據。數據時間是2021年5月—7月。通過牧區上頭羊所佩戴定位項圈產生的連續定位信息，其中有定位項圈編號、定位狀態、經緯度等。模型使用軌跡數據的格式，見表1。

1.2 數據預處理

滿足草原牧區產生海量數據的存儲和計算處理需求，搭建了hadoop[7,8]平臺，可以通過平臺對原始軌跡數據進行清洗。其中包括缺失值清洗、邏輯錯誤清洗、格式內容清洗。在平臺上，對于草原數據進行不同主題區分，根據數據挖掘主題需求，抽取對應的數據做支撐。在預處理這個環節將直接影響軌跡數據挖掘的效果。

表1 軌跡數據模型

2 基于BP-DBSCAN的畜牧軌跡數據挖掘模型

根據實際需求將畜牧軌跡數據經過預處理后，由于羊群的軌跡比較緩慢、迂直的特點，對現有的軌跡挖掘所采用各種聚類算法進行分析后，最終采用DBSCAN算法[9]作為數據的處理分析。DBSCAN聚類算法有發現不同密度、尺度和形狀聚類的能力。DBSCAN聚類算法發現類簇個數變化是基于使用者給出的最少樣本點數和近鄰半徑兩個參數[10]。但是，DBSCAN算法在使用者對數據集沒有先驗經驗的情況下確定上述兩個參數有一定困難。因此確定了一種BP-DBSCAN算法的模型，通過神經網絡確定訓練出最優參數，達到放牧產生軌跡數據聚類的準確性。

2.1 DBSCAN聚類算法

1996年由Ester M、Kriegel H P、Xu X.等人[11]提出了基于密度空間聚類算法——DBSCAN算法，該算法不用事先規定類簇的個數，當需要指定兩個參數(Eps，MinPts)，為了詳細的描述DBSAN算法，須給出以下定義[12,13]:

定義1：(Eps領域)假設給出數據集D={x1,x2,x3,…，xm},對于xj屬于D，xj的領域NEps(xj)定義為以xj為中心，以Eps為半徑的區域內，即：

NEps(xj)={xj∈D|dist(xi,xj)≤Eps}

(1)

其中D是數據集；dist(xi,xj)表示D中兩個數據對象xi和xj之間的距離；NEps(xj)在數據集D中對象xi與對象xj距離小于Eps的所有對象。

定義2：(核心點)對于數據xi∈D,設定MinPts最小閾值，如果|NEps(xj)≥MinPts|,稱為核心點，不是核心點可是某核心點的Eps鄰域內的對象稱為邊界點。

定義3：(直接密度可達)在數據集D中若對象xi在對象xj的Eps域內，并且是核心對象，稱對象xi從對象xj出發是直接密度直達的(directly density-reachable)。

定義4：(密度可達)如果存在一個對象序列P1,P2,P3，…,Pn,滿足P1=xj,Pn=xi，并且Pn+1由Pn直接密度可達，則對象xi從對象xj關于Eps和MinPts是密度可達的(density-reachable)。

定義5：(密度相連)如果存在對象xk=D使得點xj和xi都是從xk關于Eps和MinPts密度可達的，那么點xj到xi是關于Eps和MinPts密度連通的(density-connected)。

定義6：(噪聲點)不屬于在任何簇的樣本點則標記成噪聲點(noise)。

該算法流程圖，如圖1所示。

圖1 DBSCAN算法流程

2.2 BP神經網絡

BP神經網絡[14，15]是1986年Rumelhart和Williams提出的，是應用較為廣泛的人工網絡模型。BP神經網絡由輸入層、隱含層與輸出層3部分組成。BP神經網絡模型,如圖2所示。

圖2 BP神經網絡模型

BP神經網絡通過信號的正向傳播和誤差的反向傳播來降低誤差函數的函數值，網絡訓練過程就是不斷地調整優化權值和閾值。對于3層BP神經網絡。算法計算公式如下：

隱含層第l個神經元輸出:

(2)

輸出層第m神經元輸出:

(3)

誤差反向傳遞更新隱含層到輸出層權重：

φlm(m+1)=Φlm(m)+ΔΦlm

(4)

誤差反向傳遞更新輸入層到隱含層權重：

ωpl(m+1)=ωpl(m)+Δωpl

(5)

式中：ωpl和φlm是連接權值；θl和Φm是閾值；f為該層的激活函數。

2.3 BP-DBSCAN軌跡挖掘模型

目前DBSCAN聚類算法的結果會受到初始化參數Eps和MinPts的影響，筆者通過密度聚類算法和BP神經網絡模型的優勢，提出了基于密度聚類算法和BP神經網絡相結合的草原畜牧軌跡數據挖掘模型。該模型主要由DBSCAN算法模塊和BP神經網絡模塊兩個部分組成。通過BP神經網絡的得出最優參數，再進行對于放牧產生的軌跡數據進行聚類。

基于BP-DBSCAN軌跡挖掘模型的步驟如下：

step1 確定BP神經網絡結構，初始化參數；

step2 輸入參數進入BP神經網絡,得到參數Eps和MinPts；

step3 以訓練出Eps和MinPts為參數輸入DBSCAN算法；

step4 掃描軌跡數據，依次訪問所有軌跡點；

step5 判斷此軌跡點是否被訪問過；

step6 結合Eps和MinPts參數，判斷此軌跡點是否為核心點；

step7 如果此點是核心點，訪問其所有密度相連的軌跡點，將其與核心點定為一個類簇；

step8 繼續循環，直至所有軌跡點訪問完為止，得到分布E1；

step9 將E1和實際結果Y1輸入損失函數中，得誤差值；

step10 通過誤差值對神經網絡進行反向傳播訓練，得出最優Eps和MinPts；

step11以最優Eps和MinPts為參數的DBSCAN算法對再數據集進行聚類。

3 實驗及結果分析

實驗使用數據是蘇尼特左旗某牧區放牧中產生的軌跡數據。BP-DBSCAN軌跡挖掘算法模型通過Python語言實現，在Win10系統運行，計算機硬件配置：Intel(R) Core(TM) i7-8550U CPU @ 1.80 GHz，8 GB內存，1 TB硬盤。通過訓練出最優參數對軌跡數據進行聚類，從而提升軌跡數據聚類效果。

3.1 誤差分析

鑒于目前基于草原畜牧軌跡的挖掘算法模型，是否能訓練出最優參數。損失函數[16]可以判斷模型預測與實際數據差距。如表2所示損失函數呈現遞減趨勢，說明預測值越來越接近實際數據，得到的參數越準確。

表2 BP-BDSAN模型誤差值

3.2 聚類分析

本次實驗抽取某類簇的數據和其他類簇少量數據對軌跡數據聚類，圖3(a)圖是對原始軌跡數據的聚類效果圖，圖3(b)圖是通過模型訓練出最優參數聚類出的效果圖，實驗結果表明通過神經網絡結合DBSCAN算法模型，是可以滿足自適應確定DBSCAN參數的需求，聚類效果圖，如圖3所示。

(a) (b)

4 結論

筆者對草原牧區牲畜放牧過程中產生的大量軌跡數據，確定一種基于BP-DBSCAN軌跡挖掘算法模型，對牲畜軌跡數據進行聚類，以滿足牧區牲畜軌跡數據挖掘要求。為提升算法處理效率，搭建了大數據hadoop平臺對海量數據進行預處理。BP-DBSCAN軌跡挖掘算法模型對于軌跡聚類效果提高，為后續牧區板塊規劃做基礎，使草場數據信息化。科學放牧，可以達到羊群與草場之間的相對的生態平衡，減輕草場壓力。

畜牧業屬于基礎產業同時也是重要產業，在畜牧業向現代化轉型過程中，如何結合現有技術，更好地服務于畜牧業是研究人員所需要考慮的。草原牧區以其獨特的特色和優勢在畜牧業發展中占有重要地位。基于現研究背景，筆者依托于大數據結合軌跡挖掘技術，指導草原畜牧業生產科學發展，是具有非常重要意義的。