基于K-D樹和機(jī)器學(xué)習(xí)的時(shí)空數(shù)據(jù)檢索-預(yù)測系統(tǒng)

張蓬郁，王 煜，江旻宇，邵嘉琳，張洪濱

?

基于K-D樹和機(jī)器學(xué)習(xí)的時(shí)空數(shù)據(jù)檢索-預(yù)測系統(tǒng)

張蓬郁，王 煜，江旻宇，邵嘉琳，張洪濱

（北京工業(yè)大學(xué) 樊恭烋榮譽(yù)學(xué)院，北京 100124）

針對(duì)時(shí)空數(shù)據(jù)數(shù)據(jù)量大和多維屬性造成的索引效率低、關(guān)聯(lián)關(guān)系建模難等問題，本文提出引入KD樹結(jié)構(gòu)進(jìn)行靜態(tài)多維數(shù)據(jù)建模與檢索。同時(shí)結(jié)合機(jī)器學(xué)習(xí)中Linear Regression，SVR，Nearest Neighbors Regression等六種算法進(jìn)行未來狀態(tài)的預(yù)測。我們對(duì)比了六種常用學(xué)習(xí)算法，對(duì)預(yù)測結(jié)果的擬合情況進(jìn)行分析，以天氣預(yù)測為應(yīng)用背景，對(duì)比得出具體環(huán)境下，KD樹與SVR算法的結(jié)合檢索速度快，預(yù)測精確。

時(shí)空數(shù)據(jù)；KD樹；機(jī)器學(xué)習(xí)；Linear Regression；SVR；Nearest Neighbors Regression

0 引言

如今，人們普遍認(rèn)為，人類已經(jīng)進(jìn)入“大數(shù)據(jù)世代”。智能感知傳感器、物聯(lián)網(wǎng)、云計(jì)算等相關(guān)于大數(shù)據(jù)的前言技術(shù)正在高速發(fā)展。隨著衛(wèi)星定位系統(tǒng)、地理信息系統(tǒng)技術(shù)及計(jì)算機(jī)和通信網(wǎng)絡(luò)技術(shù)的發(fā)展，我們?cè)絹碓蕉嗟慕佑|到一種具有高緯度、數(shù)據(jù)量龐大的時(shí)空數(shù)據(jù)。因此，時(shí)空數(shù)據(jù)的規(guī)范化設(shè)計(jì)、數(shù)據(jù)查詢和數(shù)據(jù)預(yù)測已成為急需解決的問題。

如何提取有效數(shù)據(jù)也是一個(gè)熱點(diǎn)話題。數(shù)據(jù)挖掘的價(jià)值在于它可以從海量數(shù)據(jù)中篩選出有價(jià)值的數(shù)據(jù)，學(xué)者通常使用一下以分類、評(píng)估、預(yù)測關(guān)聯(lián)和聚類進(jìn)行數(shù)據(jù)挖掘[1-2]。

因此，我們最終提出了一個(gè)應(yīng)用于實(shí)時(shí)溫度監(jiān)控環(huán)境下的時(shí)空數(shù)據(jù)檢索-預(yù)測系統(tǒng)。以KD樹進(jìn)行數(shù)據(jù)檢索，再將有效數(shù)據(jù)進(jìn)行整理擬合，預(yù)測未來溫度走向。

1 檢索模塊

數(shù)據(jù)降維 時(shí)空數(shù)據(jù)通常含有（x坐標(biāo)，y坐標(biāo)，時(shí)間，本身屬性）的屬性。而對(duì)于這樣多維數(shù)據(jù)，維數(shù)越高，操作越復(fù)雜。因此我們首先將數(shù)據(jù)降維至三維。因?yàn)閭鞲衅魇庆o止的，它的所在地的二維空間坐標(biāo)是不變的[3]。因此，我們以傳感器編號(hào)代替它的二維坐標(biāo)，并作為一個(gè)樹根節(jié)點(diǎn)，樹根以下延伸出傳感器收集到的所有數(shù)據(jù)，每條數(shù)據(jù)具有兩種屬性：（時(shí)間，本身屬性）。

K-D Tree構(gòu)建 二分法是一維數(shù)組的快速高效查找方法。我們希望將二分法的對(duì)折查找方法應(yīng)用于時(shí)空數(shù)據(jù)，首先需要解決的就是高維數(shù)據(jù)中的二分法實(shí)現(xiàn)方式。

KD樹的思想是分割k維數(shù)據(jù)空間。首先考慮，如何確定分割空間的分割線.對(duì)于一個(gè)二維平面的劃分，我們首先選擇x軸作為垂直分區(qū)面，則分區(qū)點(diǎn)為x軸上的中點(diǎn)位置。那么，任何在x軸上小于該分區(qū)點(diǎn)的點(diǎn)則會(huì)被劃分到左區(qū)域，同時(shí)會(huì)被添加入該樹的左子樹中以此類推[4-6]。

最終，將森林結(jié)構(gòu)存儲(chǔ)的空間信息與KD-tree存儲(chǔ)的時(shí)間數(shù)據(jù)點(diǎn)結(jié)合，構(gòu)成了我們整個(gè)系統(tǒng)的檢索體系。森林結(jié)構(gòu)存儲(chǔ)傳感器根節(jié)點(diǎn)信息，其中包含傳感器所在的空間坐標(biāo)和編號(hào)。在檢索過程中，首先根據(jù)地點(diǎn)選擇傳感器的編號(hào)，進(jìn)行KD樹上的時(shí)間-屬性索引，利用二分法來高效迅速的檢索到用戶需要的數(shù)據(jù)[7]。

用戶接口 在此模塊我們?yōu)橛脩籼峁┝怂姆N結(jié)構(gòu)，分別為點(diǎn)查詢，線性查詢，空間查詢與時(shí)空查詢：

查找某一時(shí)間，某一地點(diǎn)的溫度。

（a）查找一段時(shí)間，某一地點(diǎn)的溫度。

（b）查找某一時(shí)間，某地區(qū)的溫度。

（c）查找一段時(shí)間，某地區(qū)的溫度。

2 機(jī)器學(xué)習(xí)模塊

為了對(duì)天氣數(shù)據(jù)進(jìn)行整理擬合，并根據(jù)擬合出的曲線查訊信息。我們使用了6種機(jī)器學(xué)習(xí)方法：Linear Regression, SVR, Nearest Neighbors Regression, Nearest Neighbors Regression, K Neighbors Regression, Decision Tree Regression, Random Forest Regression, Gradient Boosting Regression，對(duì)檢索模塊查詢得到的結(jié)果進(jìn)行擬合，得出相應(yīng)的特征曲線。其中，通過了解不同機(jī)器學(xué)習(xí)方法中參數(shù)的意義，我們針對(duì)不同的數(shù)據(jù)集，調(diào)整相應(yīng)的參數(shù)，找到最適合該數(shù)據(jù)集的機(jī)器學(xué)習(xí)方法與其對(duì)應(yīng)的參數(shù)。

SVR（Support Vector Regression）[8-10]SVR（支撐向量機(jī)）是支持向量分類的一種方法，其基本原理是找到一個(gè)回歸平面，使得數(shù)據(jù)集中的每一個(gè)點(diǎn)到平面的最小距離之和最小。

對(duì)于SVR的參數(shù)選擇，我們使用核函數(shù)rbf。這對(duì)應(yīng)了我們實(shí)驗(yàn)數(shù)據(jù)集的參數(shù)少、樣本數(shù)量相對(duì)較少的特點(diǎn)。rbf將樣本非線性地映射到一個(gè)更高維的空間。它能夠處理分類標(biāo)注和屬性的非線性關(guān)系。

通常， = 0.01是業(yè)界公認(rèn)符合大多數(shù)數(shù)據(jù)集的值，實(shí)際實(shí)驗(yàn)中盡管我們也測試了其他可能性，但是這個(gè)值得出的結(jié)果的確是最好的。

最近鄰回歸 我們所用到的K近鄰回歸是最近鄰近鄰回歸之一，它是在每個(gè)查詢點(diǎn)的附近選擇臨近的數(shù)據(jù)點(diǎn)來實(shí)現(xiàn)學(xué)習(xí)，其中k是由用戶指定的整數(shù)值。在KNN算法中，常用的距離有三種，分別為曼哈頓距離、歐式距離和閔可夫斯基距離。我們選用歐式距離：

3 實(shí)驗(yàn)

3.1 數(shù)據(jù)集

該實(shí)驗(yàn)中，我們使用傳感器實(shí)際采集到的溫度數(shù)據(jù)。通過python來控制樹莓派上的溫度傳感器DHT11，從而收集某一時(shí)段或者一整天的實(shí)時(shí)溫度數(shù)據(jù)。實(shí)驗(yàn)中我們每五分鐘收集一個(gè)溫度數(shù)據(jù)，我們可以規(guī)定一個(gè)收集總數(shù)或者讓整個(gè)系統(tǒng)一直運(yùn)行下去[11]。

3.2 系統(tǒng)化模型

TCP模塊 TCP模塊用于連接傳感器模塊和數(shù)據(jù)標(biāo)準(zhǔn)化模塊，把從傳感器模塊收集到的實(shí)時(shí)數(shù)據(jù)進(jìn)行初步篩選并進(jìn)行緩存，等待數(shù)據(jù)標(biāo)準(zhǔn)化模塊的傳輸指令[12]。

TCP模塊作為傳感器模塊的的客戶端，實(shí)時(shí)接收傳感器所采集的數(shù)據(jù)，傳感器端將采集到的數(shù)據(jù)無差別地以字節(jié)流的格式傳輸?shù)絋CP模塊。TCP模塊在接收數(shù)據(jù)的同時(shí)根據(jù)校驗(yàn)和的進(jìn)行數(shù)據(jù)的初篩，并把篩選后的數(shù)據(jù)進(jìn)行緩存。

TCP模塊作為數(shù)據(jù)標(biāo)準(zhǔn)化模塊的服務(wù)端，等待數(shù)據(jù)標(biāo)準(zhǔn)化模塊的取數(shù)據(jù)指令，當(dāng)收到取數(shù)據(jù)指令時(shí)，TCP模塊將緩存中所有緩存的數(shù)據(jù)以字節(jié)流的形式傳輸?shù)綌?shù)據(jù)標(biāo)準(zhǔn)化模塊，并清空TCP模塊的緩存區(qū)。

數(shù)據(jù)存儲(chǔ) 數(shù)據(jù)的可視化和大小是難以平衡的。僅使用數(shù)字進(jìn)行存儲(chǔ)對(duì)于減少數(shù)據(jù)量非常有用，但很難讓人識(shí)別。因此，我們選擇使用JSON來保存具有時(shí)間和空間兩個(gè)特征的數(shù)據(jù)[13]。而對(duì)于每種類型的數(shù)據(jù)，我們給它不同的JSON文件來保存。對(duì)于這種類型的數(shù)據(jù)中的每一行，我們只保存數(shù)據(jù)的關(guān)鍵值，并在JSON文件中顯示數(shù)據(jù)的時(shí)間和控件屬性。

3.3 實(shí)驗(yàn)結(jié)果

在數(shù)據(jù)收集完后，我們使用一套6種回歸方法來擬合數(shù)據(jù)集，以解決檢索模塊中的四種查詢?nèi)蝿?wù)?；貧w方法集包括SVR、決策樹回歸、線性回歸、K近鄰回歸、隨機(jī)森林回歸、梯度升力回歸。

評(píng)價(jià)指標(biāo) 通過調(diào)用scikit-learn庫中score函數(shù)，我們可以計(jì)算得出每個(gè)函數(shù)對(duì)于數(shù)據(jù)集的擬合情況。score函數(shù)主要的評(píng)估方法是：計(jì)算回歸模型與真實(shí)數(shù)據(jù)的方差得分，其取值范圍是[0,1]，當(dāng)評(píng)價(jià)結(jié)果越接近1時(shí)，說明自變量越能解釋因變量的變化，也就是說明擬合的函數(shù)越接近真實(shí)值。值越小說明擬合結(jié)果越差，數(shù)據(jù)出現(xiàn)欠擬合，模型的復(fù)雜度太低，不能很好地?cái)M合所有數(shù)據(jù)，訓(xùn)練誤差較大。過擬合表明模型復(fù)雜度太高，訓(xùn)練數(shù)據(jù)太少，訓(xùn)練誤差小，測試誤差大。

查詢B：特定地點(diǎn)一段時(shí)間內(nèi)的溫度 擬合結(jié)果如下，我們可以得出結(jié)論，SVR和K近鄰回歸擬合數(shù)據(jù)集優(yōu)于其他方法。

圖1 查詢B的機(jī)器學(xué)習(xí)模型效果

由于SVR在三種查詢中模型表現(xiàn)良好，因此我們對(duì)SVR進(jìn)行了更深入的研究。由于在查詢D中SVR的擬合結(jié)果仍處于線性水平，仍不連續(xù)，這樣的結(jié)果不能反映數(shù)據(jù)的總體趨勢(shì)。因此，我們將通過SVR得到的曲線擬合成基于數(shù)據(jù)集的超平面可以幫助我們預(yù)測任何時(shí)間和傳感器的溫度。

4 結(jié)論

對(duì)于時(shí)空數(shù)據(jù)，KD樹在檢索時(shí)空數(shù)據(jù)上效率高，且在查詢數(shù)據(jù)上表現(xiàn)出最高的準(zhǔn)確率和最快的查詢速度。同時(shí)，我們將地點(diǎn)中的經(jīng)度、緯度用傳感器ID表示，可以有效地對(duì)數(shù)據(jù)進(jìn)行基礎(chǔ)降維。

通過對(duì)實(shí)際采集數(shù)據(jù)和帶有擾動(dòng)點(diǎn)的模擬數(shù)據(jù)的測試，實(shí)驗(yàn)結(jié)果表明，SVR和K近鄰回歸對(duì)擬合查詢某時(shí)間點(diǎn)某區(qū)域內(nèi)溫度效果最好，SVR對(duì)擬合查詢某時(shí)間段內(nèi)某地區(qū)溫度數(shù)據(jù)準(zhǔn)確率效果最好。因此，應(yīng)選用不同給的算法針對(duì)不同情景下的查詢要求進(jìn)行數(shù)據(jù)擬合。

綜上所述，我們通過實(shí)現(xiàn)對(duì)時(shí)空數(shù)據(jù)的采集、傳輸、存儲(chǔ)、檢索、查詢和預(yù)測，構(gòu)建時(shí)空大數(shù)據(jù)檢索-預(yù)測系統(tǒng)

[1] 唐穎峰, 陳世平. 利用k-d樹索引改進(jìn)數(shù)據(jù)流skyline查詢算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2018, 39(03): 544-550.

[2] 吳波濤, 張煜, 陳文龍, 沈定濤, 魏思奇. 基于紅黑樹與K-D樹的LiDAR數(shù)據(jù)組織管理[J]. 長江科學(xué)院院報(bào), 2016, 33(11): 32-35.

[3] 陳洋, 張道輝, 趙新剛, 韓建達(dá). 基于IHDR自主學(xué)習(xí)框架的無人機(jī)3維路徑規(guī)劃[J]. 機(jī)器人, 2012, 34(05): 513-518.

[4] 劉宇, 熊有倫. 基于有界k-d樹的最近點(diǎn)搜索算法[J]. 華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2008(07): 73-76.

[5] 黃河, 史忠植, 鄭征. 基于形狀特征k-d樹的多維時(shí)間序列相似搜索[J]. 軟件學(xué)報(bào), 2006(10): 2048-2056.

[6] 何元烈, 應(yīng)自爐, 張有為. 用K-D樹實(shí)現(xiàn)對(duì)雙模態(tài)多媒體數(shù)據(jù)庫的有效查詢[J]. 計(jì)算機(jī)工程與應(yīng)用, 2003(18): 187-189+232.

[7] 王碧, 霍紅衛(wèi). 基于K-D樹的多維數(shù)據(jù)分布方法[J]. 計(jì)算機(jī)工程, 2003(03): 105-107.

[8] 師紅宇, 任小玲. 基于機(jī)器視覺的棉花異性纖維識(shí)別方法[J]. 軟件, 2018, 39(02): 32-34.

[9] 陳亞杰, 王鋒, 鄧輝, 劉應(yīng)波. ElasticSearch分布式搜索引擎在天文大數(shù)據(jù)檢索中的應(yīng)用研究[J]. 天文學(xué)報(bào), 2016, 57(02): 241-251.

[10] 張興忠, 王運(yùn)生, 曾智, 牛保寧. 一種高效過濾提純音頻大數(shù)據(jù)檢索方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(09): 2025-2032.

[11] 李兆興, 馬自堂. 面向批量處理的大數(shù)據(jù)檢索過濾模型研究[J]. 計(jì)算機(jī)科學(xué), 2015, 42(09): 183-190.

[12] 帥天平, 李翠靜, 余金果. Lp范數(shù)下2臺(tái)機(jī)器并行工件在線排序問題研究[J]. 軟件, 2014, 35(05): 13-16.

[13] 戴禮燦. 大數(shù)據(jù)檢索及其在圖像標(biāo)注與重構(gòu)中的應(yīng)用[D]. 中國科學(xué)技術(shù)大學(xué), 2013.

Spatio Temporal Data Retrieval and Prediction System Based on K-D Tree and Machine Learning

ZHANG Peng-yu, WANG Yu, JIANG Mi-yu, SHAO Jia-lin, ZHANG Hong-bin

(Fan Gongxiao Honors College, Beijing University of Technology, Beijing 100124)

In view of problems of low index efficiency and difficult relation modeling caused by large amount of spatiotemporal data and multidimensional attributes, the article introduces KD tree structure to model and retrieve static multidimensional data, and predicts future status combining six algorithms of Linear Regression, SVR, Nearest Neighbors Regression in machine learning at the same time. We compare six common learning algorithms, analyze fitting situation of prediction results. Under specific application background of weather forecast, combination of KD tree and SVR algorithm has advantages of fast retrieval speed and accurate prediction results.

Spatiotemporal data; KD tree; Machine learning; Linear Regression; SVR; Nearest Neighbors Regression

TP18

A

10.3969/j.issn.1003-6970.2018.08.045

張蓬郁(1997-)，女，北京工業(yè)大學(xué)，本科，主要研究方向數(shù)據(jù)挖掘，深度學(xué)習(xí)。

本文著錄格式：張蓬郁，王煜，江旻宇，等. 基于K-D樹和機(jī)器學(xué)習(xí)的時(shí)空數(shù)據(jù)檢索-預(yù)測系統(tǒng)[J]. 軟件，2018，39（8）：215-218