基于草原牲畜放牧軌跡的數(shù)據(jù)挖掘研究

邢光磊，周李涌，李寶山

(內(nèi)蒙古科技大學(xué) 信息工程學(xué)院，內(nèi)蒙古 包頭 014010)

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

在大數(shù)據(jù)技術(shù)日益普及中，草原畜牧業(yè)也得到快速發(fā)展。牧羊人在放牧過(guò)程中使用定位系統(tǒng)產(chǎn)生大量軌跡數(shù)據(jù)。在處理軌跡數(shù)據(jù)上，結(jié)合傳統(tǒng)軌跡挖掘技術(shù)并針對(duì)草原畜牧業(yè)牲畜運(yùn)動(dòng)軌跡特有特點(diǎn)，筆者提出了一種適合牧區(qū)的軌跡挖掘模型，并利用Hadoop開(kāi)源平臺(tái)的數(shù)據(jù)計(jì)算處理框架[5,6]，對(duì)軌跡數(shù)據(jù)進(jìn)行預(yù)處理，提高算法處理效率。最后通過(guò)真實(shí)軌跡數(shù)據(jù)對(duì)于該模型進(jìn)行驗(yàn)證，結(jié)果證明了模型的有效性，對(duì)后續(xù)草原科學(xué)放牧的研究是具有重要意義的。

1 軌跡數(shù)據(jù)處理

對(duì)于放牧產(chǎn)生的軌跡數(shù)據(jù)可以提取數(shù)據(jù)中潛藏的信息。然而，并不是全部的數(shù)據(jù)都能應(yīng)用于研究。在牲畜上GPS定位設(shè)備產(chǎn)生的軌跡數(shù)據(jù)中存在一些無(wú)效數(shù)據(jù)、重復(fù)數(shù)據(jù)和噪聲數(shù)據(jù)。為了提高數(shù)據(jù)挖掘的準(zhǔn)確性，必須剔除無(wú)效數(shù)據(jù)，并根據(jù)現(xiàn)有的軌跡數(shù)據(jù)提取有用數(shù)據(jù)，以便于后續(xù)分析。

1.1 實(shí)驗(yàn)數(shù)據(jù)來(lái)源

筆者使用的數(shù)據(jù)是蘇尼特左旗某牧區(qū)放牧中產(chǎn)生的軌跡數(shù)據(jù)。數(shù)據(jù)時(shí)間是2021年5月—7月。通過(guò)牧區(qū)上頭羊所佩戴定位項(xiàng)圈產(chǎn)生的連續(xù)定位信息，其中有定位項(xiàng)圈編號(hào)、定位狀態(tài)、經(jīng)緯度等。模型使用軌跡數(shù)據(jù)的格式，見(jiàn)表1。

1.2 數(shù)據(jù)預(yù)處理

滿足草原牧區(qū)產(chǎn)生海量數(shù)據(jù)的存儲(chǔ)和計(jì)算處理需求，搭建了hadoop[7,8]平臺(tái)，可以通過(guò)平臺(tái)對(duì)原始軌跡數(shù)據(jù)進(jìn)行清洗。其中包括缺失值清洗、邏輯錯(cuò)誤清洗、格式內(nèi)容清洗。在平臺(tái)上，對(duì)于草原數(shù)據(jù)進(jìn)行不同主題區(qū)分，根據(jù)數(shù)據(jù)挖掘主題需求，抽取對(duì)應(yīng)的數(shù)據(jù)做支撐。在預(yù)處理這個(gè)環(huán)節(jié)將直接影響軌跡數(shù)據(jù)挖掘的效果。

表1 軌跡數(shù)據(jù)模型

2 基于BP-DBSCAN的畜牧軌跡數(shù)據(jù)挖掘模型

根據(jù)實(shí)際需求將畜牧軌跡數(shù)據(jù)經(jīng)過(guò)預(yù)處理后，由于羊群的軌跡比較緩慢、迂直的特點(diǎn)，對(duì)現(xiàn)有的軌跡挖掘所采用各種聚類算法進(jìn)行分析后，最終采用DBSCAN算法[9]作為數(shù)據(jù)的處理分析。DBSCAN聚類算法有發(fā)現(xiàn)不同密度、尺度和形狀聚類的能力。DBSCAN聚類算法發(fā)現(xiàn)類簇個(gè)數(shù)變化是基于使用者給出的最少樣本點(diǎn)數(shù)和近鄰半徑兩個(gè)參數(shù)[10]。但是，DBSCAN算法在使用者對(duì)數(shù)據(jù)集沒(méi)有先驗(yàn)經(jīng)驗(yàn)的情況下確定上述兩個(gè)參數(shù)有一定困難。因此確定了一種BP-DBSCAN算法的模型，通過(guò)神經(jīng)網(wǎng)絡(luò)確定訓(xùn)練出最優(yōu)參數(shù)，達(dá)到放牧產(chǎn)生軌跡數(shù)據(jù)聚類的準(zhǔn)確性。

2.1 DBSCAN聚類算法

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

定義1：(Eps領(lǐng)域)假設(shè)給出數(shù)據(jù)集D={x1,x2,x3,…，xm},對(duì)于xj屬于D，xj的領(lǐng)域NEps(xj)定義為以xj為中心，以Eps為半徑的區(qū)域內(nèi)，即：

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

(1)

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

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

定義3：(直接密度可達(dá))在數(shù)據(jù)集D中若對(duì)象xi在對(duì)象xj的Eps域內(nèi)，并且是核心對(duì)象，稱對(duì)象xi從對(duì)象xj出發(fā)是直接密度直達(dá)的(directly density-reachable)。

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

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

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

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

圖1 DBSCAN算法流程

2.2 BP神經(jīng)網(wǎng)絡(luò)

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

圖2 BP神經(jīng)網(wǎng)絡(luò)模型

BP神經(jīng)網(wǎng)絡(luò)通過(guò)信號(hào)的正向傳播和誤差的反向傳播來(lái)降低誤差函數(shù)的函數(shù)值，網(wǎng)絡(luò)訓(xùn)練過(guò)程就是不斷地調(diào)整優(yōu)化權(quán)值和閾值。對(duì)于3層BP神經(jīng)網(wǎng)絡(luò)。算法計(jì)算公式如下：

隱含層第l個(gè)神經(jīng)元輸出:

(2)

輸出層第m神經(jīng)元輸出:

(3)

誤差反向傳遞更新隱含層到輸出層權(quán)重：

φl(shuí)m(m+1)=Φlm(m)+ΔΦlm

(4)

誤差反向傳遞更新輸入層到隱含層權(quán)重：

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

(5)

式中：ωpl和φl(shuí)m是連接權(quán)值；θl和Φm是閾值；f為該層的激活函數(shù)。

2.3 BP-DBSCAN軌跡挖掘模型

目前DBSCAN聚類算法的結(jié)果會(huì)受到初始化參數(shù)Eps和MinPts的影響，筆者通過(guò)密度聚類算法和BP神經(jīng)網(wǎng)絡(luò)模型的優(yōu)勢(shì)，提出了基于密度聚類算法和BP神經(jīng)網(wǎng)絡(luò)相結(jié)合的草原畜牧軌跡數(shù)據(jù)挖掘模型。該模型主要由DBSCAN算法模塊和BP神經(jīng)網(wǎng)絡(luò)模塊兩個(gè)部分組成。通過(guò)BP神經(jīng)網(wǎng)絡(luò)的得出最優(yōu)參數(shù)，再進(jìn)行對(duì)于放牧產(chǎn)生的軌跡數(shù)據(jù)進(jìn)行聚類。

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

step1 確定BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，初始化參數(shù)；

step2 輸入?yún)?shù)進(jìn)入BP神經(jīng)網(wǎng)絡(luò),得到參數(shù)Eps和MinPts；

step3 以訓(xùn)練出Eps和MinPts為參數(shù)輸入DBSCAN算法；

step4 掃描軌跡數(shù)據(jù)，依次訪問(wèn)所有軌跡點(diǎn)；

step5 判斷此軌跡點(diǎn)是否被訪問(wèn)過(guò)；

step6 結(jié)合Eps和MinPts參數(shù)，判斷此軌跡點(diǎn)是否為核心點(diǎn)；

step7 如果此點(diǎn)是核心點(diǎn)，訪問(wèn)其所有密度相連的軌跡點(diǎn)，將其與核心點(diǎn)定為一個(gè)類簇；

step8 繼續(xù)循環(huán)，直至所有軌跡點(diǎn)訪問(wèn)完為止，得到分布E1；

step9 將E1和實(shí)際結(jié)果Y1輸入損失函數(shù)中，得誤差值；

step10 通過(guò)誤差值對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行反向傳播訓(xùn)練，得出最優(yōu)Eps和MinPts；

step11以最優(yōu)Eps和MinPts為參數(shù)的DBSCAN算法對(duì)再數(shù)據(jù)集進(jìn)行聚類。

3 實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)使用數(shù)據(jù)是蘇尼特左旗某牧區(qū)放牧中產(chǎn)生的軌跡數(shù)據(jù)。BP-DBSCAN軌跡挖掘算法模型通過(guò)Python語(yǔ)言實(shí)現(xiàn)，在Win10系統(tǒng)運(yùn)行，計(jì)算機(jī)硬件配置：Intel(R) Core(TM) i7-8550U CPU @ 1.80 GHz，8 GB內(nèi)存，1 TB硬盤(pán)。通過(guò)訓(xùn)練出最優(yōu)參數(shù)對(duì)軌跡數(shù)據(jù)進(jìn)行聚類，從而提升軌跡數(shù)據(jù)聚類效果。

3.1 誤差分析

鑒于目前基于草原畜牧軌跡的挖掘算法模型，是否能訓(xùn)練出最優(yōu)參數(shù)。損失函數(shù)[16]可以判斷模型預(yù)測(cè)與實(shí)際數(shù)據(jù)差距。如表2所示損失函數(shù)呈現(xiàn)遞減趨勢(shì)，說(shuō)明預(yù)測(cè)值越來(lái)越接近實(shí)際數(shù)據(jù)，得到的參數(shù)越準(zhǔn)確。

表2 BP-BDSAN模型誤差值

3.2 聚類分析

本次實(shí)驗(yàn)抽取某類簇的數(shù)據(jù)和其他類簇少量數(shù)據(jù)對(duì)軌跡數(shù)據(jù)聚類，圖3(a)圖是對(duì)原始軌跡數(shù)據(jù)的聚類效果圖，圖3(b)圖是通過(guò)模型訓(xùn)練出最優(yōu)參數(shù)聚類出的效果圖，實(shí)驗(yàn)結(jié)果表明通過(guò)神經(jīng)網(wǎng)絡(luò)結(jié)合DBSCAN算法模型，是可以滿足自適應(yīng)確定DBSCAN參數(shù)的需求，聚類效果圖，如圖3所示。

(a) (b)

4 結(jié)論

筆者對(duì)草原牧區(qū)牲畜放牧過(guò)程中產(chǎn)生的大量軌跡數(shù)據(jù)，確定一種基于BP-DBSCAN軌跡挖掘算法模型，對(duì)牲畜軌跡數(shù)據(jù)進(jìn)行聚類，以滿足牧區(qū)牲畜軌跡數(shù)據(jù)挖掘要求。為提升算法處理效率，搭建了大數(shù)據(jù)hadoop平臺(tái)對(duì)海量數(shù)據(jù)進(jìn)行預(yù)處理。BP-DBSCAN軌跡挖掘算法模型對(duì)于軌跡聚類效果提高，為后續(xù)牧區(qū)板塊規(guī)劃做基礎(chǔ)，使草場(chǎng)數(shù)據(jù)信息化?？茖W(xué)放牧，可以達(dá)到羊群與草場(chǎng)之間的相對(duì)的生態(tài)平衡，減輕草場(chǎng)壓力。

畜牧業(yè)屬于基礎(chǔ)產(chǎn)業(yè)同時(shí)也是重要產(chǎn)業(yè)，在畜牧業(yè)向現(xiàn)代化轉(zhuǎn)型過(guò)程中，如何結(jié)合現(xiàn)有技術(shù)，更好地服務(wù)于畜牧業(yè)是研究人員所需要考慮的。草原牧區(qū)以其獨(dú)特的特色和優(yōu)勢(shì)在畜牧業(yè)發(fā)展中占有重要地位。基于現(xiàn)研究背景，筆者依托于大數(shù)據(jù)結(jié)合軌跡挖掘技術(shù)，指導(dǎo)草原畜牧業(yè)生產(chǎn)科學(xué)發(fā)展，是具有非常重要意義的。