云计算环境下机票价格预测及任务分配研究

摘要

随着大数据研究方向的出现，传统的数据挖掘存在效率不高、无法直接处理大数据的问题。云计算技术为数据挖掘提供了一种新的思路。Hadoop是Apache组织下的一种开源分布式云计算框架的实现，以其可靠、高效、可伸缩的特点被应用于大数据处理环境。机票价格数据的获取与预测具有良好的市场需求与经济价值，属于大数据处理的研究范围，且目前研究成果不多，是本文的一个重要研究内容。另一方面，现有的Hadoop任务分配策略，尚不能很好地适应大数据处理。改进Hadoop任务分配策略，提高作业执行效率是本文的另一个研究内容。
　　本文分别针对Hadoop环境下的机票价格预测问题和异构环境下Hadoop任务分配问题展开了研究，具体工作包括:
　　1)针对航空收益的价格管理，力图挖掘出机票价格变化的规律，利用爬虫技术抓取机票数据，基于机票价格密度图像，提出用于决定是否购买机票的Cluster_ Predict_Ticket算法。
　　2)针对Cluster_ Predict_ Ticket算法在处理大数据量机票数据效率低下问题，提出Cluster_ Predict_Ticket算法的MapReduce版本PCluster_Predict_Ticket算法，将算法移植到Hadoop环境，利用MapReduce编程模式提高算法效率。实验表明在不损失预测精度的前提下PCluster_ Predict_ Ticket算法更具扩展性和效率。
　　3)针对异构环境下Hadoop任务调度问题，提出HTA(Hadoop TaskAssignment)问题，使用最小费用最大流对HTA问题进行建模。提出了λ-Flow算法，将原先一次完成的任务分配过程划分成多轮，每轮基于当前集群状态，以及上轮任务的执行情况，动态进行任务分配，直至全部任务分配结束，以期达到最优执行效率。通过与其他算法对比实验表明，λ-Flow算法能够更好地适应集群的动态变化，有效减少作业执行时间。
　　本文的成果验证了PCluster_ Predict_ Ticket算法的扩展性和λ-Flow算法的有效性，有效的解决大数据环境下机票价格预测的效率问题，提高了Hadoop作业的执行效率。本文关于数据挖掘算法MapReduce化的研究不仅仅适用于机票数据，可以扩展到其他数据挖掘场景，同时，本文工作也可为云计算环境下的任务调度问题提供一定的借鉴。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 本文的研究内容

1．3 本文的组织结构

第2章 相关技术及平台

2．1 云计算

2．1．1 云计算概述

2．1．2 云计算特点

2．1．3 云计算体系结构

2．1．4 Hadoop MapReduce

2．2 数据挖掘

2．2．1 数据挖掘任务与常见算法

2．2．2 数据挖掘与云计算

2．3 其他云平台

2．4 本章小结

第3章 基于Hadoop的机票预测系统

3．1 问题描述与分析

3．2 基于Hadoop的机票预测问题建模

3．2．1 机票预测系统的设计

3．2．2 机票数据获取

3．2．3 机票数据分析

3．3 机票价格预测方法

3．3．1 机票Tsa_Ticket算法

3．3．2 Cluster_Predict_Ticket算法

3．4 Cluster_Predict_Ticket算法在Hadoop上的实现

3．4．1 Hadoop数据预处理

3．4．2 PTKMeans算法在Hadoop上并行实现

3．4．3 PTRF算法在Hadoop环境下的实现

3．4．4 PCluster_Predict_Ticket算法在Hadoop环境下的实现

3．4．5 模型的更新

3．5 实验与分析

3．5．1 数据预处理效率实验

3．5．2 Hadoop PTKMeans算法实验

3．5．3 Hadoop PTRF算法实验

3．5．4 PCluster_Predict_Ticket算法实验

3．6 本章小结

第4章 异构环境下Hadoop任务分配策略的改进

4．1 Hadoop调度策略研究

4．1．1 Hadoop调度流程

4．1．2 Hadoop常见调度器及调度策略

4．2 Hadoop任务分配问题建模

4．2．1 网络流的基本概念

4．2．2 Hadoop任务分配流网络

4．3 λ-Flow算法

4．3．1 Hadoop任务流网络初始化

4．3．2 Flow-SPFA算法

4．3．3 TaskMinCostMaxFlow算法

4．3．4 Hadoop任务分配λ-Flow算法

4．4 实验与结果

4．4．1 实验环境

4．4．2 λ-Flow算法运行时间

4．4．3 作业完成时间

4．4．4 作业完成时间与步长λ的关系

4．5 本章小结

第5章 总结与展望

5．1 本文总结

5．2 研究展望

参考文献

致谢

在读期间发表的学术论文与取得的其他研究成果