时空数据分析算法及其应用研究
空间和时间是现实世界最基本、 最重要的属性， 许多空间应用系统都需要表 达地学对象的时空属性， 例如在地理位置变更、 环境监测、 城市演化等领域都需 要管理历史变化数据，以便重建历史、跟踪变化、预测未来。面向对象的技 是术
[1]表达中主要是为了克服给定实体 用在软件设计中的一种方法， 它用在时空数据
的空间或非空间属性在不同时间不同频率变化而出现的复杂问题
[2]
。下面从 KNN、
RNN、SkyLine三种时空数据分析算法出发，论述时空数据分析算法的应用。
1、KNN分析算法的基本概述及应用分析
KNN算法是非参数回归模型的基本算法之一，通过在状态空间中搜索与待测 点X相近的 k个样本 (Xi ，Yi ) 估计 gn(x) ，因此又称为 k最近邻非参数回归，其预测 [3]可表示为 函数
k
k
Y=g(X)=
i 1
W；Xk1，⋯ ， Xkk）Yi = i （X
i 1
ki Yi （1）
其中 Xk1．表示与 x距离最近的点，并赋予权值k1；Xk2则被赋予权值k2；以此 类推，得到k个权函数 k1，k2，?，kk，满足
k
k1≥ k2≥ ⋯ ≥ kk≥ 0，
i i 1
k =1 （2）
KNN算法通过计算样本个体之间的距离或者相似度来寻找与每个样本个体最 相近的 K个个体，在这个过程中需要完成一次样本个体的两两比较，所以算法的 时间复杂度，跟样本的个数直接相关。
K最近邻算法通常情况下是用于分类的， 这只是对 K近邻算法用途的本质 明说[4]。从实际来看， K近邻算法可以应用的地方还有很多，比如系统推荐等等。简 单的讲，就是挖掘出客户喜欢的相同商品， 来进行相似物品的推荐。 另外区分客 户群体，从而使我们更好的为客户服务。
下面是 KNN分类器构建实例。 KNN的实现分训练和识别两步。 训练时， 把每类 样本降维后的结果作为 KNN的输入。如图1所示，圆圈表示待识别数据所处的位置， 选择K值为3时，选中实线圆中的 3个数据，识别结果为三角形代表的类；选择K 5时，选中虚线为值圆中的 5个数据，识别结果为正方形代表的类。
- 1 -...
...
图1 KNN分类器构建
关于智能商务中的聚类算法等， 已经应用于很多系统中， 比如推荐系统、 文 本分类系统等等
[5]。这其中衍生出的产品或者项目都已经被广泛使用于电子商务
领域。为了增加交易， 满足不同的顾客的需求， 研究人员已经推出了利用消 者费访问和购买的行为的推荐系统。 广泛应用在大的超市或者企业中。 这些系统通常 通过给顾客一些与他购买物品高度相关联的推荐物品，
来增加购买和交易。 比如
并且在这过程
亚马逊是通过偏好和用户信息和购买信息来向顾客推荐相关书 。籍中，使用的技术并不复杂，而这不妨碍推荐系统的精确有效。
2、RNN分析算法的基本概述及应用分析
[6]合P和一个查询点 q，单色反 通常， RNN查 的定义为：给定一个数据点集询
向最近邻查询 (Monochromatic Reverse Nearest Neighbor Query,RNN) 以查询点 q为最近邻的数据点，即 RNN(q)={p∈P丨? p’∈P
找出所有
s.t.d(p,p ’) 图1展示了该查询算法的一个实例 ，图中显示有四个数据点，每个数据点 都对应一个限定圆，查询点 g落在数据点 p1，P2对应的限定圆中，因此p1，P2就 是g的RNN查询结果，即 RNN(q)={Pl ，P2)。 ... ... ... - 2 - ... 图2 查询实例 近年来，反向最近邻查询学术界得到了深入探讨和研究， 并且在诸如决策支 持、资源分配等许多领域得到了广泛应用。 例如利用随机神经元网络方法和辐射 [8]；再如 神经元网络方法设计分布式数据库系统，从而确定数据的物理分段方式 利用基于随机神经网络的时延预测模型对时延进行精确的预测， [9]。 控制、路由选择提供重要的依据 为实施网络拥塞 3、SkyLine 分析算法的基本概述及应用分析 近年来，流数据挖掘与管理成为学术界和工业界所共同关注的问题， 并且随 着信息技术的不断发展和应用的不断深入， 数据收集手段越来越丰富， 海量存储 也越来越普遍。由此，一种新的操作算子 --skyline 操作被引入了数据库领域， [10] 目的是要发现数据集中不被其他点支配的所有点的集合 。随着skyline 计算在 多标准决策系统、城市导航系统、数据挖掘和可视化、智能防御系统、以及地理 信息系统等领域的广泛应用，有效地在数据流上实现 领域的研究热点。 一个多维数据库的 skyline ，是该数据库上不被其它任何数据点支配 (dominate) 的点所组成的集合。数据点 p支配点q，当且仅当 p在任一维上的取值 都不比q差，且至少在一个维度上比 q更好。Skyline 计算就是从数据库中快速、 准确地z到所有的skyline 数据点。 [11]，图中的每一个点是一个二维的数据记录， 共同组 图1是一个skyline 例 子 成一个二维的数据库。在图 2．6中，p点支配q点，p点与r 点互不相支配，所有实 - 3 -... skyline 计算成为数据挖掘 ... 心的点组成了 skyline 集合。 图1 一个skyline 例子 数据流足连续、实时、有序的数据项序列，数据流上的 skyline 查询是近来 流数据挖掘领域的一项研究热点，它所独有的特征：数据实时到达、规模宏大、 次序独立以及数据往往只能一次读取，要求数据流上的 skyline 查询处理算法必 需高效地处理到达的每一个对象， 并且具有较低的时间复杂度。 但现有算法对数 据的去除率不足，使得在进行 skyline 计算时对部分操作重复，造成时间和空问 的浪费。 并且在实际应用中， 产生的数据流往往以分布式的形式出现， 例如无线 传感器网络中传感器节点的数据流。 Skyline 查询在诸如多标准决策支持、数据挖掘、用户优先选择查询、协作 数据检索以及 Web交互式系统等领域中有着广阔的应用前景，它已经成为了当前 数据库领域的一个研究重点与热点。 Skyline 查询返回一组有意义的对象，这些 对象在各维上都不被其他对象所控制，从而支持用户在复杂的情况下进行决策， 这使得它在许多领域都有着广泛的应用， 如多标准决策支持系统以及用户偏好查 询等．为了更好地适应在不同环境下的应用，最近两年，对 Skyline 问题的研究 逐渐地趋向于在具体应用环境下进行， 如Web信息系统、 分布式P2P网络、 数据流 [12]。 和公路网络等 4、结语与展望 近年来， 随着全球定位系统、 传感器网络和移动设备等的普遍使用， 时空数 据急剧增加。 特别是时空数据的处理方面更为复杂。 因此， 寻找有效的时空数据 挖掘方法具有十分重要的意义。 针对这一背景， 文章主要围绕 KNN、RNN、SkyLine - 4 - ... ... 三种时空数据分析算法分析了其概念，对其研究的现状进行了详细介绍。 当前，时空数据挖掘的研究已吸引了来自 GIS [13]、时空推理、数据挖掘、机 器学习和模式识别等众多领域的学者， 取得了诸多研究成果。 与此同时， 时空数 [14]，如移动电子商务（基于位置的服务）、土地 据挖掘也在许多领域得到应用 利用分类及地域范围预测、全球气候变化监控（如海洋温度、厄尔尼诺现象、生 物量、犯罪易发点发现、交通协调与管理（交通中的局部失稳、道路查找）、疾 病监控、水资源管理、自然灾害（如台风、森林火灾）预警、公共卫生与医疗健 康等时空数据挖掘作为一个新兴的研究领域， 正致力于开发和应用新兴的计算技 术来分析海量、高维的时空数据，揭示时空数据中的有价值知识。 当然，现有 的这些时空数据分析算法还处于发展阶段，随着各种信息系统的完善和飞速发 展，相关研究领域必须深入研究时空数据所蕴含的巨大的能量， 点，对现有的算法进行创新性的改造和优化。 并抓住研究的重 参考文献 [1] Langran ，G（. 1992）Time in Geographic Information System. London [2] 姜晓轶 .从空间到时间—时空数据模型研究 36(3)：480-484. [3] 王 新 颖 . KNN 算 法 的 数 据 优 化 策 略 . 吉 林 大 学 学 报 ( 信 息 科 学 版)[J].2010 ,28(3):309-313. [4] 刘振.商务智能应用中数据挖掘 工大学 2013.3. [5] 张雪婷，张晓平，王洪凯．数据挖掘算法的一种实现方法 学报， 2003，(01)：4—6． [6]Zheng Shan.Probability Reverse Nearest Neighbor Search for Probability Graph [D].ZheJiang University.2012 .1. [7] 蒋本天，李英梅．分布式数据库管理系统中的 然科学学报， 2013，29(2)：57—59． [8] 蒋本天，李英梅．分布式数据库管理系统中的 然科学学报， 2013，29(2)：57—59． [9] 胡治国，张大陆，侯翠平，沈斌，朱安奇．基于随机神经网络的多步网络时延预 测模型 [J]．计算机科学， 2009，36(7)：85—88． [10] 周红福 . 基于索引的 Skyline 算法研究 [D]. 复旦大学 2007.4. [11]王艳杰 . 基于数据流的 Skyline 计算及应用研究 [D]. 江苏大学 2011.5. [12] 魏小娟，杨婧，李翠平，陈红． 19(6)：1386—1399． Skyline 查询处理 [J]．Journal of Softwar ，2008， RNN 方法[J]．哈尔滨师范大学自 RNN 方法[J]．哈尔滨师范大学自 [J]．山东建筑工程学院 KNN 算法的改进与高性能程序的实 ，TayIor &Franic . .吉林大学学报 (地球科学版 )[J] .2006， 现[D] .浙江理 - 5 -... ... [13] 陈荣清， 谢刚生， 邹时林．时态 GIS 中时空数据表达综述 [J] ．华东地质学院 学报， 2001，24(4)：320—322． [14] 刘大有，陈慧灵，齐红， 杨博．时空数据挖掘研究进展 [J]．计算机研究与发展， 2013，31(2) ：42—57． ... - 6 - 因篇幅问题不能全部显示，请点此查看更多更全内容