高维数据下决策树的快速构造
本文选题:高维数据 + 决策树 ; 参考:《中国科学技术大学》2017年硕士论文
【摘要】:从数据中挖掘知识和信息已成为解决许多实际问题的重要手段。决策树是最常用的数据挖掘算法之一。但现有决策树算法处理高维数据时存在计算量大、资源占用多的缺点。本论文面向高维数据,研究决策树的快速构造方法。首先,为减少构建决策树的计算量,我们提出了基于混淆度的启发式决策树构建算法。该算法利用父节点的计算结果估计部分子节点的上界,从而削减了找到子节点最优解的计算量。实验结果表明无论是单棵决策树还是集成决策树,该算法都不会对决策树的模型准确度、概念简洁性造成负面影响,并且在数据维度大于1000的高维情形下可以降低约70%的计算量。其次,为优化决策树构建过程中的资源占用和磁盘负载,我们提出了一种基于横纵划分的决策树并行构造方式。和传统方法相比,该方法的集群内存占用量从O(T)降为O(√T),其中T是并行进程数。对应的单并行进程的内存占用量从O(1)降至O(1/√T),即集群的扩大和并行数的增加可以降低单进程的内存占用量。数学分析和实验结果表明,该方法对网络通信量、磁盘读写量、计算量没有负面影响,并且在不同规模的集群上都取得了良好的并行效率。
[Abstract]:Mining knowledge and information from data has become an important means to solve many practical problems. Decision tree is one of the most commonly used data mining algorithms. However, the existing decision tree algorithms have the disadvantages of large computation and large resource consumption in dealing with high dimensional data. In this paper, the fast construction method of decision tree is studied for high dimensional data. Firstly, in order to reduce the computational cost of constructing decision tree, we propose a heuristic decision tree construction algorithm based on degree of confusion. In this algorithm, the upper bound of some child nodes is estimated by the result of the calculation of the parent node, thus reducing the computational cost of finding the optimal solution of the child node. The experimental results show that neither single decision tree nor integrated decision tree has a negative effect on the model accuracy and conciseness of the decision tree. And the computation can be reduced by about 70% when the data dimension is larger than 1000. Secondly, in order to optimize the resource occupation and disk load in the process of constructing decision tree, we propose a parallel construction method of decision tree based on horizontal and vertical partition. Compared with the traditional method, the cluster memory footprint of the proposed method is reduced from OT to O (T ~ 2, where T is the number of parallel processes). The memory footprint of the corresponding single parallel process is reduced from O1) to O1 / m2, that is, the expansion of cluster and the increase of parallel number can reduce the memory footprint of single process. The mathematical analysis and experimental results show that the proposed method has no negative effect on network traffic, disk read and write, and computation, and achieves good parallel efficiency on clusters of different scales.
【学位授予单位】:中国科学技术大学
【学位级别】:硕士
【学位授予年份】:2017
【分类号】:TP311.13
【相似文献】
相关期刊论文 前10条
1 肖化昆;;一种高维数据类模板的设计方法与应用[J];计算机科学;2006年08期
2 贺玲;蔡益朝;杨征;;高维数据空间的一种网格划分方法[J];计算机工程与应用;2011年05期
3 李郁林;;高维数据分析中的降维研究[J];计算机光盘软件与应用;2012年17期
4 何进荣;丁立新;胡庆辉;李照奎;;高维数据空间的性质及度量选择[J];计算机科学;2014年03期
5 刘洪波,王秀坤,赵晶;高维数据空间金字塔技术研究[J];计算机工程与应用;2003年16期
6 沈萍;;高维数据挖掘技术研究[J];电脑知识与技术;2009年06期
7 谢枫平;;聚类分析中的高维数据降维方法研究[J];闽西职业技术学院学报;2009年04期
8 余元辉;邓莹;;一种新的高维数据聚类自适应算法的研究[J];沈阳化工大学学报;2010年02期
9 王寅峰;刘昊;狄盛;胡昊宇;;一种支持高维数据查询的并行索引机制[J];华中科技大学学报(自然科学版);2011年S1期
10 周勇;卢晓伟;程春田;;非规则流中高维数据流典型相关性分析并行计算方法[J];软件学报;2012年05期
相关会议论文 前6条
1 周煜人;彭辉;桂卫华;;基于映射的高维数据聚类方法[A];04'中国企业自动化和信息化建设论坛暨中南六省区自动化学会学术年会专辑[C];2004年
2 梁俊杰;杨泽新;冯玉才;;大规模高维数据库索引结构[A];第二十三届中国数据库学术会议论文集(研究报告篇)[C];2006年
3 陈冠华;马秀莉;杨冬青;唐世渭;帅猛;;面向高维数据的低冗余Top-k异常点发现方法[A];第26届中国数据库学术会议论文集(A辑)[C];2009年
4 刘运涛;鲍玉斌;吴丹;冷芳玲;孙焕良;于戈;;CBFrag-Cubing:一种基于压缩位图的高维数据立方创建算法(英文)[A];第二十二届中国数据库学术会议论文集(研究报告篇)[C];2005年
5 刘文慧;;PCA与PLS用于高维数据分类的比较性研究[A];2011年中国卫生统计学年会会议论文集[C];2011年
6 刘喜兰;冯德益;王公恕;朱成喜;冯雯;;脸谱分析在中进期地震跟踪预报中的应用[A];中国地震学会第四次学术大会论文摘要集[C];1992年
相关重要报纸文章 前1条
1 本报记者 李双艺;引领高维数据分析先河[N];吉林日报;2013年
相关博士学位论文 前10条
1 刘胜蓝;余弦度量下的高维数据降维及分类方法研究[D];大连理工大学;2015年
2 黄晓辉;高维数据的若干聚类问题及算法研究[D];哈尔滨工业大学;2015年
3 杨崇;高维数据流上的K近邻问题研究[D];山东大学;2016年
4 路梅;面向高维数据的特征学习理论与应用研究[D];苏州大学;2016年
5 徐微微;高维数据降维可视化研究及其在生物医学中的应用[D];武汉大学;2016年
6 连亦e,
本文编号:1803981
本文链接:https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/1803981.html