时空数据分析算法及其应用研究.doc

时空数据分析算法及其应用研究 空间和时间是现实世界最基本、最重要的属性，许多空间应用系统都需要表达地学对象的时空属性，例如在地理位置变更、环境监测、城市演化等领域都需要管理历史变化数据，以便重建历史、跟踪变化、预测未来。面向对象的技术是用在软件设计中的一种方法，它用在时空数据[1]表达中主要是为了克服给定实体的空间或非空间属性在不同时间不同频率变化而出现的复杂问题[2]。下面从KNN、RNN、SkyLine三种时空数据分析算法出发，论述时空数据分析算法的应用。 1、KNN分析算法的基本概述及应用分析 KNN算法是非参数回归模型的基本算法之一，通过在状态空间中有哪些信誉好的足球投注网站与待测点X相近的k个样本(Xi，Yi)估计gn(x)，因此又称为k最近邻非参数回归，其预测函数[3]可表示为 Y=g(X)=Wi（X；Xk1，…，Xkk）Yi=kiYi （1） 其中Xk1．表示与x距离最近的点，并赋予权值k1；Xk2则被赋予权值k2；以此类推，得到k个权函数k1，k2，?，kk，满足 k1≥k2≥…≥kk≥0，=1 （2） KNN算法通过计算样本个体之间的距离或者相似度来寻找与每个样本个体最相近的K个个体，在这个过程中需要完成一次样本个体的两两比较，所以算法的时间复杂度，跟样本的个数直接相关。 K最近邻算法通常情况下是用于分类的，这只是对K近邻算法用途的本质说明[4]。从实际来看，K近邻算法可以应用的地方还有很多，比如系统推荐等等。简单的讲，就是挖掘出客户喜欢的相同商品，来进行相似物品的推荐。另外区分客户群体，从而使我们更好的为客户服务。 下面是KNN分类器构建实例。KNN的实现分训练和识别两步。训练时，把每类样本降维后的结果作为KNN的输入。如图1所示，圆圈表示待识别数据所处的位置，选择K值为3时，选中实线圆中的3个数据，识别结果为三角形代表的类；选择K值为5时，选中虚线圆中的5个数据，识别结果为正方形代表的类。 图1 KNN分类器构建 关于智能商务中的聚类算法等，已经应用于很多系统中，比如推荐系统、文本分类系统等等[5]。这其中衍生出的产品或者项目都已经被广泛使用于电子商务领域。为了增加交易，满足不同的顾客的需求，研究人员已经推出了利用消费者访问和购买的行为的推荐系统。广泛应用在大的超市或者企业中。这些系统通常通过给顾客一些与他购买物品高度相关联的推荐物品，来增加购买和交易。比如亚马逊是通过偏好和用户信息和购买信息来向顾客推荐相关书籍。并且在这过程中，使用的技术并不复杂，而这不妨碍推荐系统的精确有效。 2、RNN分析算法的基本概述及应用分析 通常，RNN查询[6]的定义为：给定一个数据点集合P和一个查询点q，单色反向最近邻查询(Monochromatic Reverse Nearest Neighbor Query,RNN)找出所有以查询点q为最近邻的数据点，即RNN(q)={p∈P丨?∈P s.t.d(p,p’)d(p,q)}，其中d是一个距离度量。给定两个数据集P和Q以及一个查询点q，双色反向最近邻查询(Bichromatic Reverse Nearest Neighbor Query,bRNN)找出所有的数据点p∈P，满足p与q之间的距离比p与Q中任意一个点的距离都要短，即bRNN(q)={p∈P丨?∈Q s.t.d(p,q’)d(p,q)}。 图1展示了该查询算法的一个实例[7]，图中显示有四个数据点，每个数据点都对应一个限定圆，查询点g落在数据点p1，P2对应的限定圆中，因此p1，P2就是g的RNN查询结果，即RNN(q)={Pl，P2)。 图2 查询实例 近年来，反向最近邻查询学术界得到了深入探讨和研究，并且在诸如决策支持、资源分配等许多领域得到了广泛应用。例如利用随机神经元网络方法和辐射神经元网络方法设计分布式数据库系统，从而确定数据的物理分段方式[8]；再如利用基于随机神经网络的时延预测模型对时延进行精确的预测，为实施网络拥塞控制、路由选择提供重要的依据[9]。 3、SkyLine分析算法的基本概述及应用分析 近年来，流数据挖掘与管理成为学术界和工业界所共同关注的问题，并且随着信息技术的不断发展和应用的不断深入，数据收集手段越来越丰富，海量存储也越来越普遍。由此，一种新的操作算子--skyline操作被引入了数据库领域，目的是要发现数据集中不被其他点支配的所有点的集合[10]。随着skyline计算在多标准决策系统、城市导航系统、数据挖掘和可视化、智能防御系统、以及地理信息系统等领域的广泛应用，有效地在数据流上实现skyline计算成为数据挖掘领域的研究热点。 一个多维数据库的skyline，是该数据库上不被其它