基于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种回归方法来拟合数据集，以解决检索模块中的四种查询任务。回归方法集包括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