基于K-D樹和機器學習的時空數據檢索-預測系統

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

?

基于K-D樹和機器學習的時空數據檢索-預測系統

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

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

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

時空數據；KD樹；機器學習；Linear Regression；SVR；Nearest Neighbors Regression

0 引言

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

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

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

1 檢索模塊

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

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

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

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

用戶接口 在此模塊我們為用戶提供了四種結構，分別為點查詢，線性查詢，空間查詢與時空查詢：

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

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

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

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

2 機器學習模塊

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

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

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

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

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

3 實驗

3.1 數據集

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

3.2 系統化模型

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

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

TCP模塊作為數據標準化模塊的服務端，等待數據標準化模塊的取數據指令，當收到取數據指令時，TCP模塊將緩存中所有緩存的數據以字節流的形式傳輸到數據標準化模塊，并清空TCP模塊的緩存區。

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

3.3 實驗結果

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

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

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

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

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

4 結論

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

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

綜上所述，我們通過實現對時空數據的采集、傳輸、存儲、檢索、查詢和預測，構建時空大數據檢索-預測系統

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

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

[3] 陳洋, 張道輝, 趙新剛, 韓建達. 基于IHDR自主學習框架的無人機3維路徑規劃[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樹實現對雙模態多媒體數據庫的有效查詢[J]. 計算機工程與應用, 2003(18): 187-189+232.

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

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

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

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

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

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

[13] 戴禮燦. 大數據檢索及其在圖像標注與重構中的應用[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-)，女，北京工業大學，本科，主要研究方向數據挖掘，深度學習。

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