搜索
一、研究现状1预测算法研究现状在过去的几十年中，预测逐渐成为各国的研究热点，许多模型和理论被应用于国防、科技预测的研究中，归纳下来，主要有以下三种类型:(l)基于线性理论模型:主要有卡尔曼滤波模型、指数平滑模型、自适应权重模型(2)基于非线性理论模型:主要有小波理论模型、突变理论模型、混沌理论模型等(3)基于知识发现的智能预测模型:主要有神经网络模型、非参数回归模型等。卡尔曼滤波预测模型是通过观测方程和状态方程组成的线性随机系统来描述滤波器，并结合递推算法对该状态变量进行估计，从而得到交通流的预测值。基于卡尔曼滤波递推算法的预测模型的理论简单、容易被理解，该方法在预测时只能通过本路段的历史数据进行模型训练，没有考虑其他影响，因此随着预测时间间隔的减少，该模型的性能会明显变差。指数平滑预测模型是利用最新观测的状况对预测结果进行纠正，将上一次的预测误差综合到下一次的预测中，反复迭代后，形成一个前面所有观测值的线性组合，然后得到最终的预测结果。该模型对存储的要求较低，不需要训练，计算较简单，在早期的预测中应用较多。自适应预测模型通过实时监测指标，如突发事故、天气变化、平均时间等因素来动态的调整各个预测因子在模型中的权重，从而解决了线性模型不能够很好随机性和非线性的缺陷。但该模型缺乏科学的选择机制。小波理论预测模型通过小波分析理论将数据分解为分辨率不同的信号，对分解后的信号分别采用预测算法进行预测，最后将分解信号的预测结果合成就得到了最终的预测结果。小波理论预测模型的抗干扰能力较强，但该模型的计算量大，运算效率较低，且对于每一个预测段均需要建立相应的模型，因此当对海量数据进行预测时，需要建立的模型会非常多，训练模型的时间花销也会很大。神经网络预测模型需要通过大量的数据去对神经网络模型进行训练，生成的模型是输出数据与输入数据之间的映射关系，输入数据通过该映射关系就能得到与之对应的预测结果。该模型预测精度高，但前期需要大量的历史数据进行模型训练。非参数回归预测模型是从历史数据中通过近邻匹配找到与当前状态最相似的近邻数据集合，通过这些近邻数据去预测道路下一时刻的交通流。该模型不需要任何的先验知识，也不需要建立复杂的数学模型，能够适应多变的状况，预测精度高，但是需要大量的历史数据。预测精度与计算效率是矛盾的。预测精度高的模型一般都较为复杂或者需要处理大量的历史数据，从而导致计算效率较低，而计算效率高的模型其预测精度一般会较低。为了能够在保证预测精度的同时，提高算法的计算效率，使预测算法能够更好的应用于实际预测中，我们讲通过试验神经网络、非回归参数模型选取准确率最高的算法并采用分布式计算环境来解决计算计算效率的问题。2计算平台Hadoop,Spark等技术的快速发展为海量数据的存储与处理提供了技术支持Hadoop框架能够对大规模数据进行分布式计算和存储，用户可以根据数据规模方便的扩展集群规模，扩展计算能力。但是Hadoop在实际应用过程中仍存在很多不足:第一、一个MapReduce任务只有Map和Reduce两个阶段，复杂的计算需要大量的Job共同完成，Job之间的依赖关系需要由开发者自己管理，这增加了开发者的研发难度。第二、Hadoop在进行MapReduce计算的过程中，会将map的计算结果写入到本地磁盘或Hadoop分布式文件系统(HadoopDistributedFileSystem,HDFS)上，然后再通过shuffle过程将计算结果发送到reduce上进行处理，反复的磁盘读写使Hadoop不能够满足低延迟的交互式数据挖掘任务的要求。第三、时间延迟高，ReduceTask需要等待所有MapTask都完成后才可以开始。相比Hadoop,Spark是一个分布式内存型计算框架，它在HadoopMapReduce优点的基础上，提出了RDD数据模型，提供了多种算子，并且可以将计算的中间结果存放到内存中，这使得迭代计算的效率更高，更适合于实时计算、交互式计算等场景，所以拟采用spark平台进行分布式计算。Spark项目是使用函数式语言Scala开发的，利用Scala开发的Spark应用程序可以像操作本地数据集一样操作分布在Spark集群中的分布式数据集。Spark基于RDD的一栈式解决方案，将批处理、交互式查询、Streaming流计算、GraphProcessing等模型统一到一个平台下，这些模型通过一致的API接口和相同的部署方案，使得各个框架可以在内存中无缝的集成，协作完成系统任务。MLlib是Spark对常用的机器学习算法的实现库。机器学习是一个多学科交叉的领域，涉及信息学、概率论、计算机、统计学等众多知识，这对机器学习开发者提出了很高的要求。MLlib为用户提供了便捷的API接口，降低了应用程序开发者进行机器学习开发的难度。MLlib对二元分类、回归、聚类、协同过滤等常见机器学习算法提供了很好的支持，并提供了相关的测试和数据的生成器。Deeplearning4j（简称DL4J）是Java和Scala环境下的开源、分布式深度学习项目，DL4J集成了HadoopandSpark，设计用于运行在分布式GPU和CPU上的商业环境。通过深度学习算法，可以实现无监督学习，让数据专家免于特征提取过程中的大量枯燥工作，从而把更多精力放在更有意思的任务之上。更广泛说来，我们认为这些算法可以帮助建设更为安全、智能、透明和高效的社会环境。在定型深度学习网络的过程中，有许多可供调节的参数。我们已尽可能对这些参数进行解释，从而使Deeplearning4j能够成为在Hadoop和其他文件系统环境内Java、Scala编程人员的DIY工具。二、拟采取算法模型（成熟方案）1、随机森林随机森林是一种集成学习方法，以决策树为基本学习单元，包含多个由Bagging集成学习理论和随机子空间方法训练得到的决策树，输入待分类的样本，由各个决策树产生各分类结果，最终的分类结果由各个决策树的结果进行投票决定。随机森林是多个决策树的集成学习方法，不仅可以克服决策树的一些不足，而且具有良好的可扩展性和并行性，能够有效解决大数据的快速处理问题，针对大数据环境下的预测有较好的应用前景。随机森林算法不仅可以实现数据处理的并行化，还可以实现训练单元的并行化。如图所示，将随机森林算法的在Spark平台并行实施的步骤如下:Step1：在每个节点上对原始数据集进行并行采样:反复利用Bootstrap采样的方法对原始训练集D进行采样，获得k个子训练集。与此同时，没有被抽到的数据就构成了袋外(Out-Of-Bag,OOB)数据集。最终，我们可以获得k个OOB数据集。这些袋外数据可以用于检测随机森林模型的预测性能。Step2:在每个节点上进行决策树建模:用上述k个子训练集构建k个决策树模型。值得注意的是，在建树的过程中并不是使用所有的特征，每棵树随机的从所有的特征中选出m个进行建模。Step3:获得随机森林模型:收集k个决策树模型构建随机森林模型。Step4:对预测样本进行投票，以票数最多的为最终类别，。训练数据集RDD决策树RDD决策树模型tree1,F1tree2,F1获取特征的各个切分点OOB数据随机森林模型{tree1,w1...}Bagging和特征子空间抽样并行建模预测组合并加权预测样本加权投票输出预测结果并行化投票基于spark的并行随机森林流程图2、softmax回归softmax回归算法主要用于处理多元分类问题，它能输出分类结果并给出相应概率值。它的主要思想是，对于由m个已标记的样本组成的训练集其中x为样本特征，y为每个样本对应的类标，并且类标用假设函数对测试样本x’估算其属于类别j的概率值，取概率最大的类别为测试样本的预测类别。一般把假设函数记作，如下式所示。式一中的参数是一个矩阵，矩阵的每一行可以看作是一个类别所对应的分类器的参数，总共有k个类别，因而参数有k行，如式二所示。式一·式二由式一可知，只要确定参数就可以得到预测模型，从而对测试样本进行类别预测，同时也需要对参数进行评估，以便确定预测模型是否准确，所以要对假设函数进行评估，一般把评估假设函数好坏的函数称之为损失函数或者错误函数，记作：其中，是一个指示性函数，当大括号中的值为真时，该函数的结果就为1，当大括号中的值为假时，其结果就为0}例如1{5=5}=1,1{2=3}=0要求得参数就是要求解使得取得最小值，求解的方法有很多种，包括梯度下降法、牛顿法和最小二乘法等。HDFS上读取训练数据集生成指定RDD的分区数目Map数据格式转换、持久化、初始化广播权重到各节点梯度计算、生成全局梯度返回给主节点迭代次数N?y输出参数模型NHDFS上读取训练数据集生成指定RDD的分区数目Map数据格式转换、持久化、初始化Map计算数据对象属于各个类别的概率输出概率最大的作为预测结果基于spark的并行softmax流程图softmax回归算法的训练阶段在Spark平台下的并行化设计如下:step1：首先从分布式文件系统HDFS上读取训练数据集生成内部数据结构是信息模型的RDD，并且生成RDD时指定RDD的分区数目，这个分区数目就是并行任务的数目;step2：通过map操作对数据进行格式上的转化，使RDD的每个分区中的数据都是自定义的结构;step3：对RDD调用cache函数，进行持久化操作，同时初始化权重矩阵;step4：利用广播变量将权重矩阵分发到各个计算节点;step5：在各个计算节点上，根据权重矩阵计算每一条数据对应的各个类别的梯度;step6：在各个计算节点上，计算各个类别的梯度和，生成全局梯度，返回给主节点;step7：在主节点上根据全局梯度更新权重矩阵;step8：重复步骤3-6，直至到达设定的迭代次数;step9：迭代完成，输出模型参数(权重矩阵)。Spark平台下softmax回归算法预测阶段并行化流程如下所示：step1：在主节点上将训练阶段所得到的模型参数广播到各个计算节点;step2：从HDFS上读取待分类数据集生成内部数据结构是客户信息模型的RDD，并根据数据集大小指定RDD的分区数目;step3：通过map操作对数据进行解析，生成内部是自定义数据结构的RDD，因为不需要进行迭代，因而此时不需要调用cache持久化数据集;step4：在各个从节点上根据模型参数对每一条数据计算其属于各个类别的概率，取概率最大的类别为数据项的预测类别;step5：输出分类结果。3、KNNK最近邻分类算法是最常用的分类算法，K近邻是指历史数据集合中与样本数据最相似的K个邻居样本。KNN分类算法的基本原理是对于给定的样本，如果该样本在历史数据集合中的K个最相似的样本大多数属于某一个类别，则认为该样本也属于这个类别。KNN算法既可用于样本分类还可用于样本回归，样本回归是指将样本的K个最相似样本的属性平均值赋值给该样本，这样就得到该样本的属性值。将传统的单机数据挖掘算法重新进行并行化实现，并在分布式集群中运行，可以按需获取分布式集群中的硬件资源和计算能力。KNN算法模型简单且预测精度高，但由于在样本相似度计算过程中，每一个待分类的样本都需要计算它到所有历史样本间的距离，以确定待分类样本的K个最近邻点。随着数据量的增大，会造成相似度计算量过大，从而导致计算效率较低的问题，这样严重限制了KNN算法在数据挖掘工作中的应用。而在Spark平台上将KNN算法进行并行化实现，可以有效的解决KNN算法近邻查找过程中搜索历史数据库效率过低的问题，提高算法的计算效率，有效的改善KNN预测算法的实用性。并行化的KNN算法主要有两个数据分发回收过程:一是将历史数据集中的所有数据对象进行切分，并分发到Spark集群中的计算节点上，然后在各个计算节点上分别计算与测试数据集中每个数据对象的相似度。该过程首先需要将历史数据集与测试数据集存放到分布式文件系统中，然后对数据集进行数据预处理工作，目的是为了选取出与后续工作有关的数据字段，最后将数据分发到集群的各个计算节点中进行样本相似度的计算。二是将各个节点计算所得的相似度结果进行汇总并排序，然后确