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

?

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

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

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

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

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

0 引言

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

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

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

1 檢索模塊

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

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

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

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

用戶接口 在此模塊我們?yōu)橛脩籼峁┝怂姆N結構，分別為點查詢，線性查詢，空間查詢與時空查詢：

查找某一時間，某一地點的溫度。

（a）查找一段時間，某一地點的溫度。

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

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

2 機器學習模塊

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

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

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

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

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

3 實驗

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

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

3.2 系統(tǒng)化模型

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

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

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

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

3.3 實驗結果

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

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

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

圖1 查詢B的機器學習模型效果

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

4 結論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[13] 戴禮燦. 大數(shù)據(jù)檢索及其在圖像標注與重構中的應用[D]. 中國科學技術大學, 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è)大學，本科，主要研究方向數(shù)據(jù)挖掘，深度學習。

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