分布式决策树算法在分类问题中的研究与实现
发布时间：2021-04-08 18:08
分类问题是模式识别、机器学习、图像处理以及信息检索等数据挖掘领域中一个重要的研究课题。在众多分类算法中,决策树（Decision Trees）是最有效且应用最为广泛的经典算法之一,其具有分类精度高、参数少、可解释性强等优点。决策树在商业、医疗、制造和生产、金融分析、遥感影像分类、分子生物学等方面已经有了广泛的应用并且取得了显著的成效。随着科技的进步和网络的发展,日常生活中产生的数据正在急剧增长,这为决策树解决大规模数据分类问题带来了机遇与挑战。然而由于内存空间、时间复杂度以及数据复杂度等限制,传统的决策树算法还无法直接应用于大规模数据集的分类问题。为有效进行大规模数据集的分析与处理,算法分布式化研究的重要性日益显著。本文针对分类问题,对决策树算法的分布式化进行了研究与实现,主要研究工作包括以下几个方面:（1）为应对C4.5决策树在处理大规模数据分类问题时所面临的挑战,提出了一种基于C4.5决策树的分布式化方法。本算法将Map-Reduce技术应用于决策树构造的每一个树节点中,构建了两个分布式算法:一个分布式算法用于树节点分裂属性和分裂点的选择,另一个用于数据的分割。其中在分裂属性和分裂...
【文章来源】：大连理工大学辽宁省 211工程院校 985工程院校 教育部直属院校
【文章页数】：134 页
【学位级别】：博士
【部分图文】：
图２．２文件在Ｈａｄｏｏｐ分布式文件系统上的存储模式??Ｆｉｇ．?２．２?Ｔｈｅ?ｄｉｓｔｒｉｂｕｔｉｏｎ?ｏｆ?ａ?ｆｉｌｅ?ｉｎ?Ｈａｄｏｏｐ?Ｄｉｓｔｒｉｂｕｔｅｄ?Ｆｉｌｅ?Ｓｙｓｔｅｍ??
生在多个计算机上，在该阶段存在一个被称为Ｍａｐ的函数，该函数主要用于处理输入数??据并产生一些中间的输出。然后，这些中间结果在Ｒｅｄｕｃｅ阶段通过一个Ｒｅｄｕｃｅ函数进行??聚合，该函数按照用户的实际实现输出最终的结果。图２．３详细描述了?Ｍａｐ－Ｒｅｄｕｃｅ框架??的处理步骤。??Ｍａｐ?Ｓｈｕｆｆｌｅ?Ｒｅｄｕｃｅ??＜?Ａ?、ｒ?Ａ??Ｋ?ｎ??＜ｋｅｙｉ，ｖａｌｕｅｉ＞?Ｉｉｓｔ＜ｋｃｙ２，ｖａｌｕｃ２＞?＜ｋｅｙ２，ｌｉｓｔ（ｖａｌｕＣ２）＞?＜ｋｅｙ３，ｖａｌｕｅ３＞??图２．３?Ｍａｐ－Ｒｅｄｕｃｅ框架的详细处理流程??Ｆｉｇ．?２．３?Ｔｈｅ?ｄｅｔａｉｌｅｄ?ｐｒｏｃｅｓｓｉｎｇ?ｐｒｏｃｅｄｕｒｅ?ｏｆ?ｔｈｅ?Ｍａｐ－Ｒｅｄｕｃｅ?ｆｒａｍｅｗｏｒｋ??如图２．３所示，Ｍａｐ阶段和Ｒｅｄｕｃｅ阶段都用＜?＞对作为相应函数的输入和输??出。在Ｍａｐ阶段，Ｍａｐ函数将每一个＜／：〇；，对作为输入，并且输出了一个中间结??－２５－??
图３．２所提算法在Ａｄｕｌｔ数据集上的执行时间??Ｆｉｇ．?３．２?Ｒｕｎｎｉｎｇ?ｔｉｍｅ?ｏｆ?ｔｈｅ?ｐｒｏｐｏｓｅｄ?ｍｅｔｈｏｄ?ｆｏｒ?Ａｄｕｌｔ?ｄａｔａ?ｓｅｔ??－４２－??
【参考文献】：
期刊论文
[1]基于MapReduce的决策树算法并行化[J]. 陆秋,程小辉. 计算机应用. 2012(09)
[2]Information entropy for ordinal classification[J]. HU QingHua , GUO MaoZu, YU DaRen & LIU JinFu Harbin Institute of Technology, Harbin 150001, China. Science China（Information Sciences）. 2010(06)
[3]粗糙集理论与应用研究综述[J]. 王国胤,姚一豫,于洪. 计算机学报. 2009(07)
[4]基于分层遗传算法的网格任务调度策略[J]. 刘海迪,杨裔,马生峰,李廉. 计算机研究与发展. 2008(S1)
[5]分支合并对决策树归纳学习的影响[J]. 王熙照,杨晨晓. 计算机学报. 2007(08)
[6]SVM-KNN组合改进算法在专利文本分类中的应用[J]. 李程雄,丁月华,文贵华. 计算机工程与应用. 2006(20)
[7]基于SVM的特征加权KNN算法[J]. 陈振洲,李磊,姚正安. 中山大学学报(自然科学版). 2005(01)
[8]决策树的优化算法[J]. 刘小虎,李生. 软件学报. 1998(10)
[9]基于粗糙集的多变量决策树构造方法[J]. 苗夺谦,王珏. 软件学报. 1997(06)
博士论文
[1]基于模糊规则的知识发现与表示研究[D]. 王显昌.大连理工大学 2015
[2]基于公理模糊集的模糊决策树算法研究[D]. 冯兴华.大连理工大学 2013
本文编号：3126006
【文章来源】：大连理工大学辽宁省 211工程院校 985工程院校 教育部直属院校
【文章页数】：134 页
【学位级别】：博士
【部分图文】：
图２．２文件在Ｈａｄｏｏｐ分布式文件系统上的存储模式??Ｆｉｇ．?２．２?Ｔｈｅ?ｄｉｓｔｒｉｂｕｔｉｏｎ?ｏｆ?ａ?ｆｉｌｅ?ｉｎ?Ｈａｄｏｏｐ?Ｄｉｓｔｒｉｂｕｔｅｄ?Ｆｉｌｅ?Ｓｙｓｔｅｍ??
生在多个计算机上，在该阶段存在一个被称为Ｍａｐ的函数，该函数主要用于处理输入数??据并产生一些中间的输出。然后，这些中间结果在Ｒｅｄｕｃｅ阶段通过一个Ｒｅｄｕｃｅ函数进行??聚合，该函数按照用户的实际实现输出最终的结果。图２．３详细描述了?Ｍａｐ－Ｒｅｄｕｃｅ框架??的处理步骤。??Ｍａｐ?Ｓｈｕｆｆｌｅ?Ｒｅｄｕｃｅ??＜?Ａ?、ｒ?Ａ??Ｋ?ｎ??＜ｋｅｙｉ，ｖａｌｕｅｉ＞?Ｉｉｓｔ＜ｋｃｙ２，ｖａｌｕｃ２＞?＜ｋｅｙ２，ｌｉｓｔ（ｖａｌｕＣ２）＞?＜ｋｅｙ３，ｖａｌｕｅ３＞??图２．３?Ｍａｐ－Ｒｅｄｕｃｅ框架的详细处理流程??Ｆｉｇ．?２．３?Ｔｈｅ?ｄｅｔａｉｌｅｄ?ｐｒｏｃｅｓｓｉｎｇ?ｐｒｏｃｅｄｕｒｅ?ｏｆ?ｔｈｅ?Ｍａｐ－Ｒｅｄｕｃｅ?ｆｒａｍｅｗｏｒｋ??如图２．３所示，Ｍａｐ阶段和Ｒｅｄｕｃｅ阶段都用＜?＞对作为相应函数的输入和输??出。在Ｍａｐ阶段，Ｍａｐ函数将每一个＜／：〇；，对作为输入，并且输出了一个中间结??－２５－??
图３．２所提算法在Ａｄｕｌｔ数据集上的执行时间??Ｆｉｇ．?３．２?Ｒｕｎｎｉｎｇ?ｔｉｍｅ?ｏｆ?ｔｈｅ?ｐｒｏｐｏｓｅｄ?ｍｅｔｈｏｄ?ｆｏｒ?Ａｄｕｌｔ?ｄａｔａ?ｓｅｔ??－４２－??
【参考文献】：
期刊论文
[1]基于MapReduce的决策树算法并行化[J]. 陆秋,程小辉. 计算机应用. 2012(09)
[2]Information entropy for ordinal classification[J]. HU QingHua , GUO MaoZu, YU DaRen & LIU JinFu Harbin Institute of Technology, Harbin 150001, China. Science China（Information Sciences）. 2010(06)
[3]粗糙集理论与应用研究综述[J]. 王国胤,姚一豫,于洪. 计算机学报. 2009(07)
[4]基于分层遗传算法的网格任务调度策略[J]. 刘海迪,杨裔,马生峰,李廉. 计算机研究与发展. 2008(S1)
[5]分支合并对决策树归纳学习的影响[J]. 王熙照,杨晨晓. 计算机学报. 2007(08)
[6]SVM-KNN组合改进算法在专利文本分类中的应用[J]. 李程雄,丁月华,文贵华. 计算机工程与应用. 2006(20)
[7]基于SVM的特征加权KNN算法[J]. 陈振洲,李磊,姚正安. 中山大学学报(自然科学版). 2005(01)
[8]决策树的优化算法[J]. 刘小虎,李生. 软件学报. 1998(10)
[9]基于粗糙集的多变量决策树构造方法[J]. 苗夺谦,王珏. 软件学报. 1997(06)
博士论文
[1]基于模糊规则的知识发现与表示研究[D]. 王显昌.大连理工大学 2015
[2]基于公理模糊集的模糊决策树算法研究[D]. 冯兴华.大连理工大学 2013
本文编号：3126006
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/3126006.html
