基于数据挖掘的城市交通流预测研究.docx

基于数据挖掘的城市交通流预测研究摘要基于数据挖掘的城市交通流预测研究摘 要城市交通管理是时空数据挖掘的一个主要的应用领域，为城市交通信息管理、交通出行决策疏导等提供了很好的技术支持。随着城市交通出行需求的不断增长，人们对出行决策服务的需求也越来越强烈。出行决策服务的研究与发展，依赖于数据挖掘技术、导航定位技术、自动控制技术、图像分析技术以及计算机网络技术等的发展应用，集中体现了智能交通系统的服务理念。在交通信息领域，人们不单要求实现数据的存储和基本信息查询，更需要利用时空数据挖掘技术来帮助理解时空对象间的联系以及潜在的时空知识。针对城市交通领域的相关需求和具体特点，本文根据面向城市交通领域的特殊要求，基于时空数据挖掘的基本理论，研究BP神经网络预测算法，实现对现有交通监测数据库中数据的挖掘与分析。具体工作为：1）建立城市交通出行决策系统的体系结构和其时空数据模型；2）结合含有时空约束的Apriori算法和BP神经网络预测方法，设计交通流的短期预测算法；3）给出具体的短期交通流预测应用实例，从某城市交通模型中抽取相关数据，利用建立的模型加以学习，对15分钟后的交通流量进行了预测，对比实际数据表明，预测结果较为可靠，预测平均误差在1.5到3（辆/秒）之间，达到了较高的预测精度。关键词：时空数据挖掘，时空建模，时空数据挖掘算法，交通流预测 第V页基于数据挖掘的城市交通流预测研究ABSTRACTTHE RESEARCH ON URBAN TRAFFIC FLOW PREDICTION BASED ON DATA MININGABSTRACTUrban transportation management is a major application area for the spatio-temporal data mining. It provides high level technical support for the information management of urban transportation system, the decision-making&diversion of the transport &travel system and etc. With the growing level of the urban transportation system, the citizens express more and more intense requirements for the services of travelling decision-making. The research and development of the service of travelling decision-making depends on such modern technologies as, the technology of data mining, the technology of navigation and positioning, the technology of automatic controlling, the technology of image analysisand the technology of computer network. These technologies show the concept of the services of the smartpublic transportation systems. In the field of transportation information, it will not only require data storage and basic information query, but also need to take advantage of the space-time data mining technology to help the understanding of the relation of the space-time objects, as well as the potential of the space-time knowledge. According to the requirement and characteristics of the field of urban transportation, this article is to solve the special problems of that. It is based on the basic theory of spatial and temporal data mining and the research of the algorithm of the BP neural network, to mine and analyze the database of the transportation monitoring system that currently used. The specific work are : 1) To establish the architecture and temporal data model of the urban transportation decision system; 2) Combined with spatial and temporal constraints Apriori algorithm and BP neural network prediction method, to design a short-term traffic flow prediction algorithm; 3) To provide an application example of short-term traffic flow forecasting that get data from a real city traffic model, using the model to study,and predict the traffic flow in 15 minutes. By comparing to the actual data, it shows that the predictions are reliable. The average error of forecasting is around 1.5 to 3 (cars per second). That means it has achievedhigh prediction accuracy.Keywords: spatial and temporal data mining, modeling spatial and temporal, spatial and temporal data mining algorithm, traffic flow forecasting基于数据挖掘的城市交通流预测研究目录目录基于数据挖掘的城市交通流预测研究I摘 要IABSTRACTII第一章、绪论11.1研究背景与意义11.2相关研究综述21.2.1数据挖掘的研究现状21.2.2交通出行决策系统的研究现状41.3 本文的主要工作及组织结构51.3.1主要工作51.3.2本文的组织结构5第二章、相关理论研究72.1 时空数据挖掘72.1.1时空数据挖掘体系结构72.1.2通用的时空数据挖掘82.1.3基于本体的时空数据挖掘112.1.4面向领域的时空数据挖掘122.2 经典时空数据挖掘算法152.2.1 K-Means算法152.2.3 K最邻近分类算法172.3 时空数据挖掘算法的分析与比较20第三章、交通出行决策系统的体系结构及建模223.1 交通出行决策系统的体系结构223.2 面向城市交通领域的时空建模233.2.1 综合的导航定位数据模型243.2.2面向对象的导航数据时空建模24第四章、城市交通流的时空数据挖掘模型及应用284.1 交通流的时空数据挖掘方法284.2 基于数据挖掘的短期交通流量预测思想294.3基于BP神经网络的交通流知识挖掘304.3.1数据的收集304.3.2样本分类304.3.3算法的学习334.4基于关联规则的路段流量关系的挖掘344.5 基于BP神经网络的预测方法应用384.5.1 训练样本384.5.2样本学习过程404.6分析与验证42第五章、结论445.1论文工作总结445.2研究的不足之处及研究展望44参考文献46致谢48基于数据挖掘的城市交通流预测研究 第一章 绪论第一章、绪论1.1 研究背景与意义时空数据挖掘是数据挖掘中的重要研究内容。随着时空信息数据的大规模增长，数据挖掘理论的不断发展，时空数据挖掘已经成为计算机和地理信息系统领域中研究的热点。传统的数据挖掘技术已经不能处理和反映时间和空间对象历史信息的变化，而时空数据挖掘技术就是以此为前提发展起来的。时空数据挖掘技术可以同时为对象提供有效的时态和空间上的管理支持，因此在很多领域有着广泛的应用前景。研究时空数据挖掘技术的发展历史不得不追溯到数据挖掘和空间数据挖掘的发展历史。数据挖掘是海量数据快速增长的产物。20世纪60年代以数字方式采集数据就已经实现。20世纪80年代，随着能够适应动态按需分析数据的结构化查询语言（Structured Query Language, SQL）的发展，关系数据库的研究应用也迅速发展起来。数据仓库开始用来存储大量的数据，由于面临处理数据仓库中大量数据的挑战，于是数据挖掘应运而生，对于这些问题，它的主要方法是数据统计分析和人工智能搜索技术。在1989年举行的第一届KDD国际学术会议上，数据库中的知识发现（KDD, Knowledge Discovery in Database）1这一概念首次被提出。近年来，KDD国际研讨会的研究重点从发现方法转向系统应用，并越来越重视多种发现策略与技术的集成以及多学科间的相互渗透。在KDD96国际会议上，Fayyad、Piatetsky-Shapiro和Smyth给出了DM和KDD的具体定义：KDD是指从数据库中发现知识的全过程；而Data Mining则是整个过程中的一个特定步骤2。通常不会将二者明确区别开来，它们都指的是从数据中挖掘知识的过程。目前，大部分数据挖掘的研究工作都是基于关系型和事务型数据库来展开的。然而随着空间数据采集和处理能力在地理信息系统、交通决策系统、医疗影像系统和环境监测系统等方面的广泛应用和体现，使得空间数据挖掘技术也在数据挖掘领域内占有越来越重要的地位。空间数据挖掘（Spatial Data Mining and Knowledge Discovery, SDMKD/SDM）有别于传统意义上的数据挖掘，需要综合利用统计学方法、人工智能方法、模式识别技术、神经网络技术等理论知识来分析获取可靠的，新颖的，可理解的和所需要的知识信息，从而揭示出蕴含在数据中的规律、内在的联系和发展的趋势3-5。空间数据挖掘利用空间数据结构，空间推理，计算机几何学等技术，把传统的数据挖掘技术扩展到空间数据库中，并提出了很多新的有效的空间数据挖掘方法。空间数据挖掘技术与地理信息系统的结合，更使得GIS系统成为能够自动学习，自动获取知识的真正的智能空间信息系统6。大部分的空间数据挖掘只针对空间对象的空间特征进行研究，而并未考虑到时间特性对于数据挖掘研究的影响。但是在很多应用领域内，对各种问题求解的过程中越来越需要考虑时间因素的影响，例如交通决策，地震救援，环境监测等。很多空间现象是随着时间来动态变化的，只有将时间纳入到空间系统中来研究空间数据随着时间变化的规律，才能更好地重现历史，跟踪变化和预测未来7。因此，近年来时空数据挖掘已经越来越受到国际学术界和工业界的广泛关注，将空间对象的时间和空间信息一体化处理来进行的时空数据挖掘（Spatio-Temporal Data Mining, STDM）是一项非常重要且很有实际意义的研究8。时空数据挖掘作为数据挖掘的重要组成部分，是一种动态的空间数据挖掘。以时空信息的认知和数据模型的研究为基础的时空数据挖掘研究，主要受到空间数据挖掘和时态数据挖掘研究的影响，并在经典数据挖掘理论的支持下对时空知识和规则进行挖掘。1.2相关研究综述1.2.1数据挖掘的研究现状空间数据挖掘的主要研究成果集中体现在原型系统开发和各种空间数据挖掘算法的实现和改进上。在原型系统开发方面，加拿大的西蒙弗雷泽大学开发出了一种空间数据挖掘系统原型GeoMiner9，该系统在空间数据库建模中使用了SAND体系结构，包括空间数据立方体建构模块、空间联机分析处理（OLAP）模块和空间数据挖掘模块，对空间数据挖掘做了一些探讨和扩展。在算法的实现和改进方面，主要包括了对空间关联规则、空间分类和聚类、空间特征规则、空间预测和演变规则以及空间异常点检测等的研究和改进，从而提出了一些依赖于数据表示的空间数据挖掘算法。Ester等人最早提出了一种空间对象分类方法，该方法采用了引入领域图（Neighborhood Graphs）概念的ID3算法，同时考虑了被分类对象及其邻接对象的非空间属性。但是，该算法的不足是缺少对邻接对象非空间属性聚合值进行相关分析的能力，且忽略了空间属性和非空间属性之间可能存在的概念层次关系10。为了改进该算法，Koperski和Han11提出了空间数据的两步决策分类法：第一步，通过较少代价的空间计算获得一个近似的空间谓词，并同时进行相关分析来提高决策树的质量；第二步，对模型进行进一步的精化计算即逐步求精，不仅大大降低了计算的复杂度，而且能够获得一个更小和更精确的决策树。另外，石云，孙玉芳12还提出了一种基于Rough Set的空间数据分类方法，采用Rough Set方法进行空间对象分类，可以较好地反映空间数据和非空间数据之间的关系。空间聚类分析是根据某些特征把空间数据库中的对象划分成具有不同意义的子类，同一个子类中的对象具有高度相似的特征，并且不同子类之间在特征上有着明显差异。迄今为止，已经提出的空间聚类算法有：基于分割的K-平均算法、K-中心点算法和CLARANS算法；基于层次的BIRCH算法和CURE算法；基于密度的DBSCAN 算法、OPTICS 算法、GDBSCAN算法、DBRS 算法和DENCLUE算法；基于网格的STING算法、WaveCluster 算法和CLIQUE算法13。空间关联规则是在传统数据挖掘中关联规则上的扩展，指的是空邻接图中对象之间的关联。目前已经提出的空间关联规则的算法有：Koperski14提出一种五个步骤的空间关联规则挖掘算法；Malcrba15等人提出了一种归纳逻辑程序设计方法（ILP, Inductive Logic Programming），该算法利用空间领域内的先进知识，系统探查空间数据的层次结构；L.K.Sharma等人提出了挖掘多层空间正负关联规则的算法13-15；刘君强等人设计了基于前缀树的单层布尔型关联规则挖掘算法(FPT-Generate)13；Lementin等人提出了在宽边界的空间实体中挖掘多层次的空间关联规则的算法；Esen Kacar等人提出了挖掘空间模糊关联规则的方法。时态信息（Temporal Information）指的是随着时间变化的信息，用于记录时态信息的数据就是时态数据（Temporal Data）16。时态数据不仅能反映事物发生发展的过程，而且更能有助于揭示事物发展的本质规律。时态数据挖掘作为数据挖掘的一个重要的扩展，它不但能够挖掘与状态有关的信息而且能够挖掘与行为有关的信息，揭示了时间上的相关关系，其中的部分的时态关系还能够进一步转化成因果关系。随着时态数据应用的普及，时态数据挖掘（Temporal Data Mining）将会成为今后数据挖掘发展的一个非常自然而又十分重要的研究方向17。近年来，国际上对时态数据挖掘研究的关注度逐渐高涨，工作重心主要集中在挖掘算法的分布式应用等方面；而在国内的研究工作还主要集中在时态数据挖掘理论的探索上，较为突出的研究进展是欧阳为民等人对时态数据挖掘从理论框架的角度做出的深入介绍与分析18。1.2.2交通出行决策系统的研究现状在城市交通管理中对管理决策者来说，最为重要的任务就是提供可靠的出行决策，以缓解城市交通拥堵的情况。一般来说有两种基本解决方案：一是实时监控和合理调度，以确保城市路网不出现超饱和的交通流；二是快速应对突发性事件，处理恢复正常交通秩序。从20世纪80年代中期开始，以欧洲、美国、日本等为代表的发达国家开始采用高科技来改造现有交通管理和出行决策体系，逐步发展起以智能交通系统（Intelligent Transport System,ITS）管理监控城市交通状况的研究应用趋势。智能交通系统是融合了先进的数据通信技术、导航定位技术、自动控制技术、图像分析技术以及计算机网络技术等的交通管理系统。在城市交通管理中，ITS作为一种新型的交通信息系统，可以发挥全方位实时高效的管理作用，并统一提供出行决策服务，使得人们的生活更加便利。出行决策服务是智能交通系统应用的重要组成部分，集中体现了ITS的服务理念。出行决策服务主要是指在电子地图平台上，集成地理信息技术、交通诱导技术、计算机网络技术、数据通信技术、传感器技术、导航定位技术等高新技术,向用户提供出行指导的技术系统或增值服务业务的总称19，包括位置服务系统（LBS）、网络地图系统和公众出行信息平台。出行决策服务产业的发展动力主要表现为人们对于导航服务的强烈需求，近年来GPS产品在全球范围内迅猛发展的趋势就很好地说明了这一点。最早的导航服务多是建立在静态地图和数据流的基础上，不考虑频繁变化的动态交通数据流对出行服务的影响，因此具有一定的局限性。随着日益发展进步的高新科技应用越来越广泛，动态的导航服务成为出行决策服务的重点研究方向之一。出行决策服务的研究与应用在日本、欧美等发达国家和地区具有领先优势。日本最早于1991年开始建设的道路交通情报通信系统（VICS），目前已是世界上运营最成功的出行决策服务系统，能够发布实时路况、交通管制、占道施工等信息，预测短时交通流量。丰田公司利用了VICS提供的预测信息推出的动态导航系统增强版G-BOOK mX，实现了导航地图数据的动态增量更新。欧洲国家普遍使用交通信息广播专用频道（TMC）来提供出行决策服务。美国的ATIS（Advanced Travelling Information System）通过在道路、机动车、换乘站、停车场以及气象中心的传感器和传输设备来获取动态数据，提供全面的交通信息和出行决策服务。Motorola等公司联合开发了美国最大的动态导航系统ADVANCE，能够利用实时交通信息来完成整个动态的导航过程。同时，美国的主要城市都有动态的出行信息平台，通过Google Earth等公共平台发布和共享，从而提供实时高效的出行决策服务20。有关智能交通系统的研究与应用在我国也得到了很好的发展，已初步形成了数据采集、处理、发布以及应用的产业链。我国自主研发的动态交通信息标准RTIC（Real Time Traffic Information Channel）支持对路段的交通信息进行编码，从而实现了动态交通信息与静态路网的无缝融合。目前，已经有多个门户网站和专业地图网站开始提供城市路况信息查询功能，如Mapabc等21。1.3 本文的主要工作及组织结构1.3.1主要工作本文的主要围绕城市交通出行决策领域展开研究工作，具体包括：1） 对时空数据挖掘进行了具体的建模；2） 对Apriori.K-means和K最邻近分类算法进行了具体推演；3） 应用BP算法对某城市交流通络15分钟后的短期交通流进行了预测，预测精度达到了较高的程度。1.3.2本文的组织结构本文共分五章，具体的组织框架结构图如下图1-1所示：问题的提出w时空挖掘技术的进步w城市交通流预测的需要w相关研究综述w文献研究法w国内外研究综述w国内外研究现状理论研究w时空建模w时空数据挖掘w性能需求算法研究w常见算法总结w现有算法的问题及不足w建模w体系构造w模型建立w数据分析系统预测应用研究wBP算法w具体应用案例w总结w评价w不足之处图1-1 本文组织框架结构图Fig 1-1 Organized framework structure diagram第48页基于数据挖掘的城市交通流预测研究 第二章 相关理论研究第二章、相关理论研究2.1 时空数据挖掘2.1.1时空数据挖掘体系结构时空数据挖掘体系结构时空数据挖掘具有与传统数据挖掘不同的特点，因此除了要研究时空数据挖掘的技术与方法以外，还必须关注时空数据建模方法的研究。一般来说，时空数据挖掘理论可以分为时空建模理论和时空挖掘理论两部分。为了系统地、全面地、完整地研究时空数据挖掘的理论体系，徐薇22在其学位论文中提出了一个完整的时空数据挖掘体系结构框架，如图2-1所示。时空挖掘时态GISGIS空间数据库空间数据仓库时态数据库空间分析空间分析空间分析空间分析空间分析空间分析时空建模时空数据描述时空系统描述时空本体描述本体论时空模型细胞自动机图2-1 时空数据挖掘体系结构Fig 2-1:Spatio-temporal data mining architecture时空挖掘理论主要由时态数据挖掘、空间数据挖掘和时空数据挖掘理论三部分组成。时空数据挖掘在经典数据挖掘理论的支撑下，全面考虑时态和空间因素的影响来研究时空信息系统。而时空建模理论作为基础理论依据，主要包含了时空数据描述、时空系统描述和时空本体描述三种方法，能结合时空对象的时态和空间属性进行深入研究。只有在时空建模理论的支持下，才能更好地对时空数据进行表示和存储，从而实现对时空数据的有效地分析和挖掘。2.1.2通用的时空数据挖掘1. 时空数据挖掘的过程传统数据挖掘的过程主要分为三个阶段：数据准备阶段、数据挖掘阶段和结果评估阶段。时空数据挖掘则是一个多步骤多反复的处理过程，将其一般过程在传统数据挖掘的基础上，用流程图表示如图2-2所示。用户界面GIS可视化表现用户层建模层空间特征时态特征属性特征数据层时空数据库或时空数据仓库服务器时空数据库时空数据仓库挖掘层时空模式模式评估时空数据挖掘引擎时空知识库图2-2 时空数据挖掘的一般过程Fig2-2:The general process of spatio-temporal data mining根据图2-2所描述的时空数据挖掘的一般过程，可将其处理步骤主要分为以下几步：(1) 数据准备，了解熟悉相关领域的背景知识，明确用户需求。(2) 数据选择，根据用户的需求，利用数据库操作对数据进行处理，从时空数据库中提取相关数据。(3) 数据预处理，对数据选择中产生的数据进一步加工，例如检查数据的完整性及一致性，过滤其中的噪声数据，用统计学的方法填补缺失数据。(4) 数据缩减，在经过预处理的数据中，通过投影等操作减少数据量，从而更符合用户的目标需求。(5) 确定目标知识类型，根据用户的需求，确定要发现何的目标知识类型，以便采取不同的时空数据挖掘算法来更好更准确地发现所需知识。(6) 选择合适算法，不仅要选择合适的时空数据挖掘算法，同时还要选择合适的时空数据模型和参数。(7) 数据挖掘，运用选定的算法从已处理的数据中提取出用户所需要的知识，并用特定的方式表示如产生式规则等。(8) 模式解释，是指解释所发现的知识的过程，更可能需要重复前面的处理步骤以获取更有效的知识。(9) 知识评价，将挖掘到的知识呈现给用户，为了避免所发现的知识与现实和以前所发现的知识冲突，还需要对知识进行一致性检验，确保得到的知识准确有效。值得注意的是，在数据准备阶段，时空数据挖掘需要同时处理和关注时态、空间和属性特征，以建立合适的时空数据模型。因此，与传统数据挖掘的过程相比，时空数据挖掘要处理更为繁复的时空对象，其过程也相对更为复杂。2. 时空数据挖掘的研究方法与策略时空数据挖掘作为一个多学科多技术交叉的领域，综合了数据库技术、模式识别、统计学、地理信息系统、机器学习、专家系统、可视化等领域的技术，其研究方法也是多种多样。根据时空数据挖掘的特点，可以归纳出以下五种可用的研究方法24：(1). 数学统计方法该方法一般需要在建立一个数学模型或统计模型的基础上，根据模型提取出相关知识。数学统计方法作为时空数据挖掘研究中常用的方法，其理论基础强大且拥有大量的算法，更能够有效处理数字型数据。但该方法对字符型数据的处理能力不足，且一般需要由经验丰富的数学统计领域的专家来完成。(2). 归纳方法归纳方法是指在相关领域的背景下，对数据进行综合概括，发现深层次的模式或特征，通常结果用概念树的形式表示。当在时空数据挖掘中应用归纳方法时，用户提供了所需的背景知识，最后的结果可用两类概念树表示：属性概念树和时空关系概念树。(3). 聚类分析方法聚类分析方法是先将数据按照一定的距离或相似性区分成不同的组，再进行深入的分析。聚类分析方法在传统数据挖掘中，面对属性数据库中的大量数据存在不够高效的问题。因而时空聚类分析方法在时空数据库中应用时，采用拓扑结构分析、叠置分析等方法来发现目标对象在时空上的相连、相邻和共生等关系。(4). Rough集方法Rough集理论（Rough Sets Theory）25是在1982年由波兰华沙大学的Z. Pawlak教授所提出的一种智能数据决策分析工具，在对不完整信息的分类分析及知识获取等方面应用广泛。在时空数据挖掘中，Rough集方法是一种新的时空数据属性分析和知识发现的研究方法。为了最大程度地保持数据内涵和提取知识，Rough集方法可用于时空数据库属性表的一致性分析、最小决策树分类算法的生成等。(5). 云理论云理论对于处理数据不确定性来说是一种新的理论，由云模型（Cloud model）、不确定性推理（Reasoning under Uncertainty）和云变换（Cloud Transform）构成。云理论结合了模糊性和随机性来弥补模糊集理论中的固有缺陷，是时空数据挖掘中定量与定性相结合的方法基础26。另外，决策树方法、遗传算法、人工神经网络、空间分析方法、图像分析和模式识别等方法都可以应用于时空数据挖掘中27。为了在时空数据库中发现用户需要的知识经常要综合应用上述方法，形成高效的研究方法。而在研究策略方面，主要用于时空数据挖掘的有三种：一是采用分而治之的策略，把时空数据挖掘看成是时态和空间数据挖掘的融合来进行研究；二是研究以时态属性为主，在时态数据挖掘的基础上进行空间扩展；三是研究以空间属性为主，在空间数据挖掘的基础上做时态上的扩展。采用这三种研究策略不需要建立复杂的数据模型，可以最大程度地利用已有的信息系统和数据挖掘算法。但缺点是数据建模过程中将实体的属性分开处理，有一定的片面性且易丢失数据的特征关系。2.1.3基于本体的时空数据挖掘随着本体方法越来越受到计算机科学研究的关注和重视，时空本体研究也正在成为时空数据挖掘的研究热点。目前，时空本体及时空描述逻辑的研究已取得了一定成果，基于本体的时空数据挖掘能较好地解决在数据建模过程中分而治之所产生的问题。基于本体的时空数据挖掘就是指用本体方法和技术实现在挖掘过程中时空数据、时空数据模型和时空知识的共享。与一般时空数据挖掘所采用的方法不同，本体方法将在时空数据挖掘过程的每个重要阶段中都有体现，用流程图结构表示，如图2-3所示。用户层用户界面GIS可视化表现系统间的共享表达挖掘层时空模式模式评估时空数据挖掘引擎时空知识库共享知识库数据层时空数据库或时空数据仓库服务器时空数据库时空数据仓库共享数据仓库建模层时空特征时空本体语义粒度图2-3 基于本体的时空数据挖掘过程Figure 2-3 ontology-based spatio-temporal data mining process从图2-3中可以看出，在时空建模阶段，时空本体建模完成的是时空一体化建模，不仅反映了时空对象的时空特征，也描述了语义关系。由于用本体表示的时空数据更容易实现数据库间的共享和重用，基于本体的时空数据挖掘在数据准备阶段可以调用共享数据库来实现数据的共享。在数据挖掘阶段，本体方法更好地实现了共享知识库中的方法与知识。基于本体的时空数据挖掘还可以在不同的子系统间共享已发现的时空模式。时空一体化的数据挖掘方法可以综合空间、时间和属性特征进行研究分析，保留了特征间的完整关系，但是需要进行复杂的时空本体建模，无法直接利用已有的时空数据建模方法和挖掘算法。2.1.4面向领域的时空数据挖掘当前，相关应用领域对时空数据挖掘技术的需求越大越大，因此对时空数据挖掘的任务和技术的研究经常是针对某个领域内的具体问题而展开的，如地理学领域的地震预测问题，医学领域的疾病预测控制，城市交通领域的出行决策引导等。面向领域的时空挖掘技术相对其综合性研究而言，发展得更为迅猛。1. 面向领域的时空数据挖掘的方法与过程面向领域的时空数据挖掘是指对某个具有时空知识背景的专业领域采用专用的时空数据挖掘方法与技术。这些领域通常包含了时间和空间属性，同时还有其特殊的专业领域知识，例如：地理学、医学、环境学等。面向领域的时空数据挖掘不仅要研究传统数据挖掘需要的方法与技术，还要对表达、存储、利用其专业的领域知识等问题进行深入的研究和讨论。根据传统数据挖掘的一般过程，结合面向领域时空数据挖掘的特殊性，可以将其过程归纳为四个主要阶段：领域数据表示、领域数据准备、领域数据挖掘和领域知识解释评估。面向领域时空数据挖掘的过程如图2-4所示，既能够体现与传统数据挖掘过程的区别，又可以看出两者明显的联系。面向领域的时空数据挖掘过程中必须经历的四个主要阶段所要完成的任务如下28：(1) 领域数据表示：需要了解属性涉及领域内的相关背景知识，在此基础上分析领域需要的时空数据挖掘任务，选择设计合适的时空数据结构和构造面向领域的数据库或数据仓库。(2) 领域数据准备：根据用户需要选取的领域数据，对选出的数据进行预处理和变换，选取的数据要更能符合时空数据挖掘任务的要求。通常对领域数据的预处理操作有消除噪声数据、查补缺失数据、检查数据一致性和完整性等。这一阶段的工作结果将直接影响接下来时空数据挖掘的效率。(3) 领域数据挖掘：根据不同的时空数据挖掘任务，如时空特征化、时空分类、时空聚类、时空关联规则挖掘、时空预测等，选择合适的面向领域数据的挖掘策略和数据挖掘算法。运用选定的算法从已处理的领域数据中提取出用户所需要的知识，并用特定的方式表示。(4) 领域知识解释和评估：结合领域时空信息系统分析领域知识的时空语义，并用可视化的知识表达技术提供用户需要的知识。同时，对时空数据挖掘的结果进行模式评估和知识一致性检验，去掉冗余或无关的模式，确保得到的知识准确有效。用户界面GIS可视化表现用户层建模层空间数据时间数据领域数据数据层时空数据库或时空数据仓库服务器领域数据库领域数据仓库挖掘层时空模式模式评估时空数据挖掘引擎领域知识库图2-4 面向领域时空数据挖掘的过程Figure 2-4 for the field of space-time data mining process尽管各个行业领域对时空数据挖掘技术的需求越来越多，但到目前为止，时空数据挖掘的综合性研究仍发展得不够全面，使得面向领域的时空数据挖掘仍有许多问题需要解决，如对海量动态的领域时空数据的有效挖掘等。2. 面向城市交通领域的时空数据挖掘本文的研究背景是城市交通领域内的交通出行决策系统，因此在研究综合性的时空数据挖掘方法与技术的同时，还对面向城市交通领域的时空数据挖掘做了分析研究。目前，国际上该领域内较为突出的研究成果主要有：Shekhar29等将时空数据挖掘方法应用到面向城市智能交通领域做数据分析研究，构造了符合监测交通流量数据要求的多维数据模型，并在经典数据挖掘算法的基础上实现了关于监测交通流量数据的时空关联规则挖掘；Brakatsoulas30等为了实现从车辆的轨迹数据库中提取车辆的运动模式、预测交通堵塞和提供出行路线，设计了以车辆为研究对象的时空数据挖掘原型系统Kinesis-Miner，其结构框架如图2-5所示。用户图形界面轨迹表征轨迹发现轨迹关联轨迹分析轨迹发现模式数据服务器时空数据轨迹非时空数据图2-5 Kinesis-Miner系统结构图Figure 2-5 Kinesis-Miner system structure应用于城市交通出行决策系统的时空数据挖掘的具体任务包括以下几项：(1) 时空特征化，找出城市交通区域或各个路段在某时间段内的交通流量特征。(2) 时空关联规则挖掘，找出影响某时间段内交通流量的因素，分析交通拥堵高峰时期各个路段交通流量数据间的关联，科学动态地分析出行车辆分布，挖掘时间、空间与经济、人文等其他影响因素之间的关系。(3) 时空分类和聚类，对城市交通的各个路段按照时间和空间特征进行分类和聚类，并且按照历史交通拥堵数据来定义出行中心路段。(4) 时空预测分析，通过对各个路段的时空数据分析，对出行流量进行预测，建立交通流量高峰期的时空数据模型，辅助出行决策的管理。通过时空一体化的挖掘方法和技术预测未来的交通流量，同时模拟未来的出行状况，评估动态提供出行决策的有效性。(5) 时空趋势分析，发掘交通流量的动态变化特征规律，观测中心地段的出行流量，同时进行相关的时空趋势分析，了解掌握动态变化信息，以此为依据适时调整提供的出行方案。2.2 经典时空数据挖掘算法2.2.1 K-Means算法1967年，J.B.MacQueen首先提出了K-means算法，根据传统K-means算法的思想，得到其基本流程如图2-8所示。输出聚类结果结束是否开始输入聚类个数k，n初始化k个聚类中心分配各个数据对象到距离最近的类中重新计算各个聚类的中心是否收敛图2-8 K-means算法的基本流程Figure 2-8 K-means algorithm is the basic flow根据图2-8所示的流程图，可以将传统K-means算法的具体步骤归纳如下：输入：聚类数目k，包含n个对象的数据集X=x1, x2, x3, x4, . , xn输出：k个聚类簇S1, S2, S3, . , Sk(1) 从数据集X中随机选择k个对象作为初始聚类中心：c1, c2, c3, . , ck；(2) 分别计算每个对象xi=(i=1,2,3n)到各个聚类中心的距离，逐个将对象分配给最近的一个聚类中心cj，1j k；(3) 分配完成之后，重新计算k个聚类的中心cj，1j k；(4) 与前一次计算得到的k个聚类中心比较，若聚类中心发生变化，转到第二步执行，直到k个聚类中心不再变化，准则函数收敛；(5) 输出聚类结果。K-means算法作为一种经典的数据挖掘聚类算法，其优点是简单快速，且能够处理大量的数据。当结构集是密集的且簇与簇之间差别明显时，该算法聚类的效果比较好。在处理大量数据时，该算法具有较高的可伸缩性和高效性，它的时间复杂度为O(nkt)，n是对象的个数，k是聚类数目，t是算法的迭代次数，一般情况下，k n，t n，也可以表示为O(n)。此外，K-means算法不依赖于顺序，即给定一个初始的聚类分布，无论样本点的顺序以何种顺序出现，其最终生成的数据聚类结果都一样。虽然传统的K-means算法简单快速有效，但是也存在着明显的缺点：(1) 聚类结果依赖于聚类个数k的初始化，初始值的设定通常要经过反复多次的实验才能找到最佳的聚类个数k，且存在一定的主观性。K-means算法对初始值的选定很敏感，对于不同的初始值，可能产生不同的聚类结果。(2) K-means算法随机选取初始聚类中心，而选取中心的不同可能产生不同的聚类结果，这会对聚类结果的稳定性产生明显的影响。只有在定义了初始聚类中心的情况下才能使用该算法，这对于一些数据挖掘的应用不大适用，例如涉及有分类属性的数据等。(3) K-means算法采用簇中对象的平均值作为参考点，不适合发现非凸面形状的簇或大小差别很大的簇，且对于噪声和孤立点数据十分的敏感，少量的该类数据就能对平均值产生极大影响，从而改变最终的聚类结果。(4) 当要处理的数据量非常大时，K-means算法的时间开销也非常大的，这种情况下用该算法，会使得计算效率低下且聚类结果不稳定。(5) K-means算法容易产生局部最优而非全局最优的聚类结果，这使得算法结果可能不平衡。在时空数据挖掘中，时空聚类分析方法也是主要的研究手段之一，K-means等聚类算法对含有时空属性的数据进行应用时，可以先采用拓扑结构分析、叠置分析等方法来发现目标对象在时空上的相连、相邻和共生等关系，然后按照一定的距离或相似性区分成不同的组，再进行深入的分析。2.2.3 K最邻近分类算法邻近分类算法是一种常用的分类算法，若令X=x1, , xn，其中每一个样本xi所属的类别均已知。对于样本数据点x，在集合中X中距离它最近的数据点记为x，最邻近分类算法采用的最邻近规则是把数据点x分到x所属的类别。通常最邻近算法的误差率比最小可能误差率（即贝叶斯误差率）要大。K最邻近分类算法是最邻近算法的扩展，都以最邻近规则为算法基础。最邻近规则是将一个数据点x分类到与它最近的K个邻近数据点中出现最多的那个类别。K近邻算法从样本数据点x开始不断的扩大区域，直到包含K个样本数据点为止，并把样本数据点x归为这K个最近的样本数据点中出现频率最高的类别。1968年Cover和Hart提出的K最邻近分类算法（K-Nearest Neighbor，KNN）是一种非参数分类算法，现已是一种理论上比较成熟的算法，广泛应用于数据挖掘的各个领域33。具体的算法流程如图2-9所示，从图中可归纳基本步骤如下：训练样本样本数据集待测样本数据，类标记数据计算样本间距离，类标记选取最小的K个距离检测各类标记的数目属于第K类设定K的初始值图2-9 KNN算法的基本流程Figure 2-9 KNN algorithm the basic flow(1) 构建样本数据集合X；(2) 设定K的初值，由于K值的选定没有一个统一的方法，一般是先选定一个初始值，然后根据实验结果不断调试，最终达到最优。(3) 在样本数据集中选出与待测样本数据点x最近的K个样本。假设样本数据点x属于n维空间Rn，一般样本间的邻近关系由欧式距离来度量。设第i个样本xi=(x1i,x2i, ,xni)Rn，其中xni表示第i个样本的第n个特征属性值，两个样本xi和xj之间的欧式距离定义如公式2.1所示：(2.1)(4) 给定一个待分类的样本xq，x1, , xk表示与xq距离最近的K个样本，设离散的目标函数为f:Rnvi，vi表示第i个类别的标签，定义V=v1, , vs为标签集合，fxq=argmaxvVi=1k(v,f(xi)为对fxq的估计，当a=b时，(a,b)=0；(5) fxq即是待测样本的类别。KNN分类算法是一种非参数的分类技术，对于未知和非正态分布的数据可以取得较高的分类准确率，具有明显的优点：(1) 算法的构建方法简单直观，易于实现。(2) 不需要产生额外描述规则的数据，规则就是样本数据本身，可以存在噪声。(3) KNN算法在类别决策时，只与极少的相邻样本有关，可以较好地避免样本数量不平衡的问题。(4) 从分类过程来看，KNN算法最直接地利用了样本之间的关系，最大程度地减少了类别特征选择不当对分类结果造成的不良影响。由于并不要求得出显示的规则，KNN算法更能体现出其分类的准确性。(5) 若给定足够大的样本数据集合，或者对海量数据仓库进行分类时，KNN算法仍可以非常有效。但同时传统的KNN算法也存在着许多问题，已经有很多研究人员对其提出了改进和完善。传统的KNN算法的主要缺点有：(1) 分类速度慢：KNN算法是先将所有样本存储起来，当要进行分类时才计算每一个样本的相似度，得到与其最近的K个样本。当样本集规模较大时，其时间和空间复杂度较高，大大影响的分类的速度。(2) 样本库容量依赖性较强：当很多类别无法提供足够的样本时，KNN算法所需要的相对均匀的特征空间就无法得到满足，会导致算法结果的误差较大。(3) 属性等同权重影响了准确率：传