吐爾遜·買買提,謝建華
(新疆農(nóng)業(yè)大學(xué) 機(jī)械交通學(xué)院,烏魯木齊 830052)
?
基于DBSCAN的農(nóng)機(jī)作業(yè)軌跡聚類研究
吐爾遜·買買提,謝建華
(新疆農(nóng)業(yè)大學(xué) 機(jī)械交通學(xué)院,烏魯木齊 830052)
農(nóng)業(yè)機(jī)械在田間作業(yè)過程中,時(shí)間和空間維度上產(chǎn)生大量的作業(yè)數(shù)據(jù),對(duì)農(nóng)業(yè)機(jī)械作業(yè)軌跡數(shù)據(jù)進(jìn)行聚類分析在農(nóng)機(jī)作業(yè)狀態(tài)分析和效率研究中具有重要意義。為此,應(yīng)用DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法對(duì)模擬農(nóng)業(yè)機(jī)械作業(yè)軌跡進(jìn)行分析,設(shè)計(jì)了基于密度聚類的農(nóng)機(jī)作業(yè)狀態(tài)分類算法。對(duì)模擬數(shù)據(jù)的聚類結(jié)果表明:該方法正確分類農(nóng)機(jī)作業(yè)班次內(nèi)的有效作業(yè)軌跡、空行轉(zhuǎn)移軌跡和停歇軌跡的精度達(dá)到98.33%、70%和100%。聚類作業(yè)軌跡反映的農(nóng)機(jī)利用率為95.35%,為農(nóng)機(jī)田間作業(yè)軌跡研究提供了依據(jù)。
農(nóng)業(yè)機(jī)械;作業(yè)軌跡;密度聚類;軌跡識(shí)別
數(shù)據(jù)挖掘技術(shù)提供了從海量數(shù)據(jù)中挖掘發(fā)展趨勢(shì)、剖析其中隱藏的知識(shí)和模式的手段。針對(duì)農(nóng)業(yè)機(jī)械在農(nóng)業(yè)生產(chǎn)中產(chǎn)生的作業(yè)軌跡數(shù)據(jù)特征,挖掘其中隱含的知識(shí)并對(duì)其進(jìn)行分析,在此基礎(chǔ)上,設(shè)計(jì)相應(yīng)預(yù)測(cè)、聚類、關(guān)聯(lián)模型,為設(shè)計(jì)農(nóng)機(jī)管理決策服務(wù)模型提供了基礎(chǔ),對(duì)促進(jìn)農(nóng)業(yè)機(jī)械化、提高生產(chǎn)效率、提高決策水平、健全調(diào)控和基層服務(wù)能力、促進(jìn)農(nóng)業(yè)機(jī)械化進(jìn)入信息化領(lǐng)域的步伐有很大的推進(jìn)作用[1-2]。
目前,生產(chǎn)要素軌跡特征研究主要有2種方法:①首先從空間維度出發(fā),獲取對(duì)象在不同時(shí)隙中的聚類模式,然后按時(shí)間順序?qū)Λ@取的簇進(jìn)行排序,從而獲得研究對(duì)象的完整的軌跡聚類模式[3-5];②以時(shí)間維度為首要參數(shù),挖掘可能出現(xiàn)有規(guī)律軌跡的時(shí)間區(qū)間,然后對(duì)挖掘得出的時(shí)間片段內(nèi)的軌跡進(jìn)行聚類,從而發(fā)現(xiàn)對(duì)象的完整軌跡模式[6-8]。
吳笛[9]等提出,在聚類過程中同時(shí)考慮軌跡包含的時(shí)間和空間信息,在空間軌跡聚類的基礎(chǔ)上提出了軌跡線段時(shí)間距離的度量方法和閾值確定原則,對(duì)時(shí)空鄰域密度進(jìn)行聚類分析,挖掘物體的時(shí)空移動(dòng)模式。農(nóng)業(yè)機(jī)械軌跡方面的研究主要圍繞著特定農(nóng)業(yè)機(jī)械在局部作業(yè)環(huán)境中的作業(yè)軌跡聚類方面[10-12]。農(nóng)業(yè)機(jī)械作業(yè)軌跡聚類方面的研究中提出了基于軌跡的作業(yè)狀態(tài)識(shí)別方法[13],但引用傳統(tǒng)的聚類算法對(duì)農(nóng)業(yè)機(jī)械軌跡進(jìn)行分析方面的研究較少。
本文應(yīng)用數(shù)據(jù)挖掘中的基于密度的聚類(Density-Based Spatial Clustering of Applications with Noise,DBSCAN)方法,結(jié)合農(nóng)業(yè)機(jī)械作業(yè)狀態(tài)的特征,提出了對(duì)作業(yè)狀態(tài)軌跡點(diǎn)進(jìn)行聚類的方法,并結(jié)合模擬作業(yè)數(shù)據(jù)的聚類分析,提出了基于密度聚類的農(nóng)機(jī)作業(yè)狀態(tài)識(shí)別方法,同時(shí)對(duì)農(nóng)機(jī)利用率進(jìn)行測(cè)度。
聚類算法又稱群集分析,常用于將大量數(shù)據(jù)按照一定算法歸類到不同的簇。其與分類算法的差異在于:聚類算法可在非監(jiān)督模式下處理數(shù)據(jù),不需要人為輸入數(shù)據(jù)類標(biāo)簽。聚類算法發(fā)展至今約有60年余,其非監(jiān)督的特性為處理大量非結(jié)構(gòu)化數(shù)據(jù)提供了高效和便捷的途徑,并且在大數(shù)據(jù)時(shí)代顯示出更大的優(yōu)勢(shì)。
關(guān)于聚類,目前尚未有較統(tǒng)一的定義,但普遍認(rèn)同的定義有:將物理或抽象對(duì)象,或樣本空間中點(diǎn)組成的集合根據(jù)某種度量標(biāo)準(zhǔn)分成若干個(gè)互相盡可能不相似、但內(nèi)部盡可能相似的類的過程稱為聚類。同一簇中的兩點(diǎn)(或?qū)ο?的相似度(或距離)高于(或小于)不同簇中兩點(diǎn)之間的相似度(或距離)。類簇可以理解為高密度點(diǎn)集的高維連通區(qū)域,它們通過密度相對(duì)較低的點(diǎn)集組成的區(qū)域和其它類或簇相分離。
作為熱門的研究領(lǐng)域,數(shù)據(jù)挖掘中聚類方法有5種:劃分聚類方法、層次聚類方法、基于密度的方法、基于圖的聚類方法和模型聚類方法。在研究和應(yīng)用之中應(yīng)該根據(jù)數(shù)據(jù)類型、數(shù)據(jù)的分布及聚類的目的,選擇時(shí)間和空間效率能滿足實(shí)際要求的高精度、簡(jiǎn)單易用的聚類算法。
本研究根據(jù)農(nóng)業(yè)機(jī)械田間作業(yè)運(yùn)行軌跡空間和時(shí)間數(shù)據(jù)的不規(guī)律性及數(shù)據(jù)量大等特征,選取基于密度的聚類方法。
2.1 基于密度的聚類方法
依據(jù)樣本空間中點(diǎn)的密度,對(duì)樣本進(jìn)行聚類的算法中,預(yù)期要發(fā)現(xiàn)的簇是由滿足預(yù)定樣本數(shù)量閾值要求的點(diǎn)集組成,并且不同的類簇由樣本數(shù)閾值低于指定值的點(diǎn)集(離群點(diǎn)集合)分割。基于密度的算法最終要滿足過濾密度低于閾值的樣本區(qū)域,發(fā)現(xiàn)密度等于或高于指定閾值的區(qū)域。在此類算法中,無需指定簇的數(shù)量?;诿芏染垲惙椒梢杂糜诳臻g數(shù)據(jù)的聚類。
數(shù)據(jù)挖掘領(lǐng)域中典型的基于密度的算法有:
1)DBSCAN。依據(jù)用戶給定參數(shù),不斷發(fā)現(xiàn)給定半徑內(nèi)的點(diǎn)數(shù)達(dá)到指定數(shù)量的高密度區(qū)域,并不斷生長(zhǎng)高密度區(qū)域。
2)DENCLUE。聚類過程中依據(jù)樣本點(diǎn)在指定空間中的密度進(jìn)行聚類。
3)OPTICS、DBCLASD、CURD。這些算法中,針對(duì)數(shù)據(jù)在數(shù)據(jù)集中呈現(xiàn)出的高密度區(qū)域的形狀和密度,對(duì)DBSCAN做了些補(bǔ)充或修正。
以上3種基于密度的聚類算法中,DBSCAN聚類算法是一種常用的聚類算法。算法執(zhí)行過程中,首先需要指定類簇的半徑域Eps和最小對(duì)象數(shù)目MinPts;然后根據(jù)Eps和MinPts判斷對(duì)象集中的對(duì)象的屬性(即核心點(diǎn)、邊界點(diǎn)、噪聲);最后根據(jù)當(dāng)前對(duì)象屬性判斷當(dāng)前對(duì)象域是否構(gòu)成一個(gè)類簇,并依據(jù)此方法判斷數(shù)據(jù)集中每個(gè)點(diǎn)的屬性。
DBSCAN算法可以對(duì)農(nóng)業(yè)機(jī)械作業(yè)軌跡圖像點(diǎn)進(jìn)行密度識(shí)別,挖掘其分布特征,并找到軌跡點(diǎn)較密的區(qū)域,從而發(fā)現(xiàn)軌跡點(diǎn)較集中的簇,可以識(shí)別軌跡中離群點(diǎn)。該算法的特點(diǎn)是可以挖掘不同形狀的類簇,可以有效地排除離群點(diǎn),同時(shí)較適合空間和時(shí)間軌跡數(shù)據(jù)的聚類。
實(shí)踐證明:算法對(duì)Eps和MinPts的設(shè)置較敏感,如設(shè)置不當(dāng)可能造成聚類效果下降。依據(jù)農(nóng)業(yè)機(jī)械田間作業(yè)軌跡數(shù)據(jù)的特征,本研究選擇DBSCAN作為軌跡聚類算法。
農(nóng)業(yè)機(jī)械軌跡聚類流程如下:
1)算法輸入。作業(yè)周期內(nèi)時(shí)空軌跡數(shù)據(jù)、半徑Eps和最小軌跡數(shù)MinPts。
2)算法輸出。農(nóng)業(yè)機(jī)械作業(yè)軌跡類簇集。
方法:
1)放入所有軌跡點(diǎn)到DataPoint庫,從DataPoint隨機(jī)取出一個(gè)點(diǎn)。
2)IF Eps領(lǐng)域中至少包含MinPts個(gè)軌跡點(diǎn),THEN 記當(dāng)前點(diǎn)為核心軌跡點(diǎn),并創(chuàng)建一個(gè)簇,放入其到簇庫C中。ELSE IF 當(dāng)前點(diǎn)是邊界點(diǎn),THEN 歸入所屬簇。ELSE 判斷其為離群點(diǎn)。
3)從DataPoint庫中隨機(jī)取出下一個(gè)點(diǎn)。
4)并重復(fù)步驟2)和3),直到所有點(diǎn)處理完畢。
2.2 問題分解及軌跡數(shù)據(jù)
分析農(nóng)業(yè)機(jī)械作業(yè)過程可發(fā)現(xiàn):農(nóng)業(yè)機(jī)械班次內(nèi)的工作時(shí)間包括有效作業(yè)時(shí)間(t1)、田間空行時(shí)間(t2)、工藝所需時(shí)間(t3)、維修時(shí)間(t4)、轉(zhuǎn)移時(shí)間(t5)和組織不善造成的停車時(shí)間(t6)等。班次內(nèi)不同作業(yè)狀態(tài)中,農(nóng)業(yè)機(jī)械的移動(dòng)速度有較大的差異,通過設(shè)定移動(dòng)速度閾值,可以區(qū)分局部區(qū)域內(nèi)的狀態(tài),但此方法對(duì)速度閾值的設(shè)定精度有一定的要求,如t2和t5之間差異不能很好地區(qū)分。應(yīng)用GPS/北斗等手段獲取軌跡信息時(shí),其軌跡點(diǎn)的形態(tài)主要受到以下2個(gè)因素的影響。
1)采樣頻率的影響:在采樣周期固定情況下,如果采樣頻率較大,則單位面積中的軌跡點(diǎn)數(shù)就較多,軌跡的空間聚集特征越明顯,反之亦然。
2)采樣周期的影響:農(nóng)機(jī)軌跡采樣的頻率已知情況下,采樣周期的長(zhǎng)短與軌跡點(diǎn)的聚集程度成反比。另外,不同作業(yè)狀態(tài)下的采樣周期和頻率也會(huì)對(duì)農(nóng)機(jī)軌跡的聚集程度及性質(zhì)的判斷產(chǎn)生影響。
本文中假設(shè)農(nóng)業(yè)機(jī)械軌跡采集過程中t1~t6采用相同的采樣周期和采樣頻率。在此種假設(shè)下,可以判斷t1和t2所對(duì)應(yīng)的軌跡密度相似,計(jì)算時(shí)t2可以并入到t1。t3、t4和t6的作業(yè)軌跡呈現(xiàn)出高密度軌跡區(qū),并高度相似,計(jì)算時(shí)可以并入t6。因此,對(duì)作業(yè)軌跡做聚類分析時(shí)需要考慮的軌跡類型有t1、t5和t6。本文模擬的農(nóng)業(yè)機(jī)械軌跡點(diǎn)情況如表1所示,模擬軌跡的分配情況如圖1所示。圖1表明:班次作業(yè)時(shí)間內(nèi),相同的采樣周期和頻率下,農(nóng)業(yè)機(jī)械作業(yè)空間軌跡聚集程度的順序?yàn)椋簍6(圖1中停歇軌跡),t1(圖1中田地1、2、3),t5(圖1轉(zhuǎn)移軌跡1、2)。轉(zhuǎn)移軌跡1和轉(zhuǎn)移軌跡2的軌跡密度相似,并聚集程度最低;第1塊、第2塊和第3塊田地中軌跡密度高度相似。停車維修點(diǎn)的停歇軌跡密度最高。
表1 農(nóng)業(yè)機(jī)械模擬軌跡點(diǎn)分布
本研究根據(jù)農(nóng)業(yè)機(jī)械在田間作業(yè)中軌跡的形態(tài)特征,采用基于密度的作業(yè)軌跡聚類方法。
DBSCAN對(duì)聚類參數(shù)Eps和MinPts較敏感,微小的誤差會(huì)導(dǎo)致較大的聚類結(jié)果差異,算法中參數(shù)可以依據(jù)反復(fù)試驗(yàn)和類簇評(píng)估方法予以選取和確定。
圖1 農(nóng)業(yè)機(jī)械模擬作業(yè)軌跡分布
2.3 農(nóng)機(jī)利用率評(píng)價(jià)
農(nóng)機(jī)利用率是評(píng)價(jià)農(nóng)業(yè)機(jī)械作業(yè)效率的重要指標(biāo)。評(píng)價(jià)農(nóng)機(jī)利用率時(shí)可以從時(shí)間和空間維度進(jìn)行評(píng)價(jià)。從時(shí)間角度出發(fā)計(jì)算農(nóng)機(jī)利用率,則計(jì)算公式為
(1)
其中,U為農(nóng)機(jī)利用率;t有效作業(yè)時(shí)間;T為每班次時(shí)間。從空間維度出發(fā),農(nóng)機(jī)利用率為
(2)
其中,S為農(nóng)機(jī)利用率;w為有效作業(yè)軌跡點(diǎn);A為班次內(nèi)軌跡點(diǎn)。
3.1 軌跡聚類
本文應(yīng)用MatLab2014a中編程實(shí)現(xiàn)了DBSCAN聚類算法。設(shè)定MinPts的取值范圍為3~10,Eps的取值范圍內(nèi)為2~5,MatLab2014a平臺(tái)中不同參數(shù)組合下進(jìn)行聚類實(shí)驗(yàn),并對(duì)聚類結(jié)果應(yīng)用簇的凝聚度(cluster cohesion)和簇的分離度(cluster separation)等度量進(jìn)行評(píng)估。根據(jù)評(píng)估結(jié)果最終確定:當(dāng)MinPts=4、Eps=2.8時(shí),可以得到較好的聚類效果。表2為聚類結(jié)果統(tǒng)計(jì)結(jié)果和正確率。
表2 農(nóng)業(yè)機(jī)械模擬軌跡點(diǎn)分布
由表2可以看出:DBSCAN算法對(duì)農(nóng)業(yè)機(jī)械軌跡聚類有較好的魯棒性,可以較好地識(shí)別其不同的作業(yè)狀態(tài)。
聚類結(jié)果說明:有效作業(yè)軌跡點(diǎn)的識(shí)別率較高,接近100%,停歇時(shí)間軌跡的識(shí)別率也較高,但轉(zhuǎn)移軌跡的識(shí)別率為70%。主要原因是:①模擬軌跡數(shù)據(jù)未能較好地呈現(xiàn)出部分作業(yè)軌跡的合理狀態(tài);②DBSCAN算法本身對(duì)MinPts和Eps的選擇比較敏感,有時(shí)候出現(xiàn)局部收斂,會(huì)影聚類的整體效果,本例中有30%的轉(zhuǎn)移軌跡被識(shí)別為作業(yè)軌跡或停歇軌跡。圖2為聚類后的軌跡分布情況。觀察圖2后可發(fā)現(xiàn):被錯(cuò)誤的識(shí)別為作業(yè)軌跡的點(diǎn)位于真實(shí)作業(yè)軌跡區(qū)域和轉(zhuǎn)移軌跡區(qū)域的邊界處,結(jié)合模擬軌跡數(shù)據(jù)聚類后呈現(xiàn)出的這種簇結(jié)構(gòu)和農(nóng)業(yè)機(jī)械田間作業(yè)速度變化特征,可以認(rèn)為模擬數(shù)據(jù)能夠較好地反映真實(shí)情況。
圖2 農(nóng)業(yè)機(jī)械模擬軌跡聚類結(jié)果
同時(shí),結(jié)果也表明:轉(zhuǎn)移軌跡中部分點(diǎn)被識(shí)別為停歇軌跡,模擬數(shù)據(jù)反映的這種趨勢(shì)和真實(shí)數(shù)據(jù)的分布特征有一定的相似性。即農(nóng)機(jī)作業(yè)過程中,農(nóng)機(jī)轉(zhuǎn)移時(shí)可能會(huì)出現(xiàn)短暫的停車修正過程,這種狀態(tài)在模擬軌跡數(shù)據(jù)中反映出來,說明模擬數(shù)據(jù)一定程度具備實(shí)際數(shù)據(jù)的特征。
3.2 作業(yè)效率
因本文中根據(jù)軌跡點(diǎn)分布特征判斷其作業(yè)狀態(tài)(有效作業(yè)、轉(zhuǎn)移和停歇),而未考慮作業(yè)狀態(tài)的持續(xù)時(shí)長(zhǎng),所以計(jì)算其作業(yè)效率時(shí)可以用式(2)測(cè)度農(nóng)機(jī)利用效率。計(jì)算結(jié)果顯示,模擬作業(yè)軌跡所反映的農(nóng)機(jī)利用率為95.35%。
本文首先根據(jù)農(nóng)機(jī)作業(yè)狀態(tài)的特征,對(duì)其作業(yè)時(shí)間進(jìn)行人工分類,農(nóng)機(jī)作業(yè)狀態(tài)分為t1、t2、t3、t4、t5和t6等作業(yè)狀態(tài)。
以農(nóng)機(jī)模擬作業(yè)軌跡數(shù)據(jù)作為研究對(duì)象,應(yīng)用數(shù)據(jù)挖掘中的傳統(tǒng)聚類算法DBSCAN對(duì)其進(jìn)行聚類分析。通過聚類試驗(yàn),確定MinPts=4、Eps=2.8為最佳參數(shù)。同時(shí),以此參數(shù)作為聚類參數(shù)對(duì)模擬軌跡數(shù)據(jù)進(jìn)行聚類,結(jié)果表明:有效作業(yè)狀態(tài)的識(shí)別率達(dá)到98.33%,停歇時(shí)間識(shí)別率100%,轉(zhuǎn)移時(shí)間的識(shí)別率70%。通過計(jì)算模擬軌跡的農(nóng)機(jī)利用率為95.35%。
本文應(yīng)用基于密度的聚類算法對(duì)模擬農(nóng)機(jī)作業(yè)軌跡數(shù)據(jù)進(jìn)行聚類,為真實(shí)農(nóng)機(jī)軌跡聚類研究提供參考。但DBSCAN算法對(duì)參數(shù)選擇比較敏感,在模擬和真實(shí)軌跡作為研究對(duì)象時(shí),如何找到MinPts和Eps的合理的搭配以及最優(yōu)值需要進(jìn)一步研究。
[1] 孟慶佳, 高波, 侯琳. 河北省農(nóng)機(jī)化水平評(píng)價(jià)指標(biāo)體系關(guān)聯(lián)度分析[J]. 農(nóng)機(jī)化研究, 2011, 33(5):31-34.
[2] 劉大有, 陳慧靈, 齊紅,等. 時(shí)空數(shù)據(jù)挖掘研究進(jìn)展[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(2):225-239.
[3] Benkert M, Djordjevic B, Gudmundsson J, et al. Finding Popular Places[M]. In: Tokuyama T. Algorithms and Computation. Berlin, Heidelberg: Springer, 2007:776-787.
[4] Shaw S- L, Yu H, Bombom L S. A space- time GIS approach to exploring large individual-based spatiotemporal datasets[J]. Transactions in GIS, 2008,12(4):425-441.
[5] Shoshany M, Even- Paz A, Bekhor S. Evolution of clusters in dynamic point patterns:with a case study of Ants' simulation[J]. International Journal of Geographical Information Science, 2007,21(7):777-797.
[6] 楊辰, 沈潤(rùn)平, 郁達(dá)威,等. 利用遙感指數(shù)時(shí)間序列軌跡監(jiān)測(cè)森林?jǐn)_動(dòng)[J]. 遙感學(xué)報(bào), 2013(5):1246-1263.
[7] Nanni M, Pedreschi D. Time-focused clustering of trajectories of moving objects[J].Journal of Intelligent Information Systems, 2006,27(3):267-289.
[8] Spaccapietra S, Parent C, Damiani M L, et al. A conceptual view on trajectories[J].Data & Knowledge Engineering,2008,65(1):126-146.
[9] 吳笛, 杜云艷, 易嘉偉,等. 基于密度的軌跡時(shí)空聚類分析[J].地球信息科學(xué)學(xué)報(bào),2015,17(10):1162-1172.
[10] 李江,作立,瑞祥,等.零位移的膜上移栽裝置運(yùn)動(dòng)軌跡設(shè)計(jì)與仿真[J].農(nóng)機(jī)化研究,2016,38(7):147-150.
[11] 洪榮榮,孫文磊,陳勇.水平摘錠式采棉機(jī)摘錠軌跡特性研究-基于Adams與MatLab[J].農(nóng)機(jī)化研究,2016,38(4):44:48.
[12] 謝建華,侯書林,張學(xué)軍,等.基于預(yù)定軌跡的殘膜脫卸機(jī)構(gòu)的優(yōu)化設(shè)計(jì)[J].農(nóng)機(jī)化研究,2016,38(6):89-92.
[13] 王培,孟志軍,尹彥鑫,等.基于農(nóng)機(jī)空間運(yùn)行軌跡的作業(yè)狀態(tài)自動(dòng)識(shí)別試驗(yàn)[J].農(nóng)業(yè)工程學(xué)報(bào),2015,31(3):56-61.
Research on Clustering of Agricultural Machinery Operation Trajectory Based on DBSCAN Algorithm
Tursun Mamat , Xie Jianhua
Recognizing the operation status is one of the most important issues in agricultural management. During the operation of agricultural machinery, the large scale data on spatiotemporal dimension will be provided by the operation by using GPS. The data mining technology, especially clustering is used for discover the knowledge and model from the historical data. On this paper ,we applying the DBSCAN(Density-Based Spatial Clustering of Applications with Noise) algorithm for clustering the simulation trajectory data ,design useful method for identification operation status of agricultural machinery .the clustering result on simulation data shows that, identification rate for operation time ,transfer time and stop time is 98.33%,70% and 100%. Use efficiency of agricultural machinery on the clustering result is 95.35%.Result of this paper will afford a way to analyze the real trajectory of agricultural machinery in future work.
agricultural machinery; trajectory of operation; density based clustering; trajectory identification
2016-03-11
國家自然科學(xué)基金項(xiàng)目(51465057)
吐爾遜·買買提(1975-),男(維吾爾族),新疆阿克蘇人,講師,博士,(E-mail)tursun@xjau.edu.cn。
S126;TP391
A
1003-188X(2017)04-0007-05