本发明涉及树型分类领域，并特别涉及一种基于分布式并行决策树的高维特征数据分类方法及系统。
背景技术：
：决策树分类算法是一种基于实例的归纳学习方法，它能从给定的无序的训练样本中，提炼出树型的分类模型。树中的每个非叶子节点记录了使用哪个特征来进行类别的判断，每个叶子节点则代表了最后判断的类别。根节点到每个叶子节点均形成一条分类的路径规则。而对新的样本进行测试时，只需要从根节点开始，在每个分支节点进行测试，沿着相应的分支递归地进入子树再测试，一直到达叶子节点，该叶子节点所代表的类别即是当前测试样本的预测类别。1986年quinlan提出了著名的id3算法。在id3算法的基础上，1993年quinlan又提出了c4.5算法。构造决策树是采用自上而下的递归构造方法。决策树构造的结果是一棵二叉或多叉树，它的输入是一组带有类别标记的训练数据。二叉树的内部结点(非叶结点)一般表示为一个逻辑判断，如形式为a＝b的逻辑判断，其中a是属性，b是该属性的某个属性值；树的边是逻辑判断的分支结果。二叉决策树的内部结点是属性，边是按照属性取值的划分，每次分支仅分出左右两个子节点，可以有效减少过拟合。使用决策树进行分类，首先利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程。然后利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类。为了适应处理大规模数据集的需要，人们提出了若干决策树的并行方案，在一些工业场景中，针对数据特点出现了很多特殊设计的决策树算法，如根据时序并行建立多个决策树并聚合的算法，针对数据输入输出特点的可以处理实时流数据的并行决策树算法等。这些算法主要根据业务场景对决策树算法进行改进，而非提出通用的并行决策树算法。通用的并行决策树算法在传统决策树的建立过程中进行数据的并行处理，算法总体思想与串行决策树算法一致，并行思路为将大规模样本并行划分到节点并在节点上并行进行最优划分的选择。比如基于mapreduce的并行决策树算法和基于分层策略的并行决策树算法。由于这些算法在各个特征上的计算是串行的，因此在数据维度较高时效率较低。本发明主要设计实现基于spark的、能够有效处理高维特征的并行二叉决策树算法。构造决策树最大的运算代价在于计算选择最佳分裂属性，因为选择分裂的时候，每个节点对每个字段都需要考虑，以找到信息增益最大的划分方法，常见的衡量准则有信息熵和giniindex等方法。具体来说，首先需要对节点上所有样本进行统计，得到计算每个字段信息增益所需的信息，对于信息熵来说，是各个特征值对应各类别的样本数。然后对所有划分方法的信息增益进行排序，选择最佳分裂方法。为了处理大规模数据，出现了了很多分布式决策树的工作，一种基于mapreduce的并行决策树算法，该算法将样本划分到节点并同时进行样本数统计后在同一层节点间并行进行分裂属性的选择，但是该算法采用多叉树算法，将划分属性的每个属性值作为一个节点，因此无法处理高维特征的数据，会出现过拟合或内存使用过高的情况。类似地，并行计算决策树同一层节点的最佳分裂点，提高决策树的性能，但这个算法在最优属性决策时串行处理，因此在高维特征数据的处理上也存在着并行不足的问题。基于spark的并行决策树算法采用二叉决策树，并行对样本进行统计，直接计算出各个节点的统计信息，然后类似于一种基于mapreduce的并行决策树算法，在节点间并行进行最优划分的选择，虽然它处理维度较高的数据有较低的内存占用，但是对于所有特征的所有划分需要并行进行信息增益的计算，在节点内部的计算是串行的，在数据维度非常高的情况下带来巨大的时间消耗。基于以上分析，串行且基于内存的分类决策树不能处理海量数据，而已有的分布式处理方式，虽然数据处理规模都有了很大的提高，但基于mapreduce的算法大多并行效率低且无法得到全局分类模型。而基于节点并行的决策树算法虽然能得到全局分类模型，但是对数据特征的关注较少，存在无法处理高维特征，或对高维特征处理时间长的问题。技术实现要素：本发明的目的是克服上述现有并行决策树算法无法高效处理高维特征数据的问题，提出了一种同时在节点与特征层面并行处理的并行决策树算法，该算法在保持低维特征数据处理效率不变的情况下，能够有效提高高维特征数据处理效率。具体来说，本发明提供了一种基于分布式并行决策树的高维特征数据分类方法，其特征在于，包括：步骤1、获取包括多个样本高维特征数据的训练数据，且该样本高维特征数据具有对应的标签类别，将该训练数据存储在分布式文件系统中，通过对该训练数据的样本在分布式集群上进行并行采样统计，获取该训练数据上的特征分布信息，获得支撑决策树计算的元数据，并对连续型特征进行预处理；步骤2、通过对该元数据进行采样计算，为分布式集群中各计算节点分配特征组，建立树的根节点，分布式集群各工作节点联合统计样本的标签类别分布，以得到根节点初始信息熵；步骤3、对所有样本高维特征数据在分布式集群上各个工作节点上分别对各自储存的样本数据进行统计，根据各样本的特征的向量及决策树的划分规则获得各样本当前所属树节点，同时统计四元组(所属节点，特征，特征值，标签)的出现次数，各节点将各四元组按照(节点，特征组)进行分组聚合，各工作节点分布式存储<(节点，特征组),(特征，特征值，标签)>的键值对的统计信息，根据该统计信息得到各特征值的信息熵；步骤4、将特征值按照各自标签的信息熵排序，将所有标签的统计值归于右节点，然后顺序遍历特征值作为左节点特征值，每次遍历保留信息增益最大的特征值，得到<(节点，特征组)，最优划分>键值对，将相同节点各个特征组的最优划分聚合并取最优，得到<节点，最优划分>键值对，选择最优划分对节点进行划分；步骤5、循环步骤2到步骤4直到对决策树中全部节点完成划分，保存当前决策树作为分类模型，将待分类数据输入该分类模型，得到该待分类数据对应的类别。所述的基于分布式并行决策树的高维特征数据分类方法，其特征在于，该训练数据为文本数据或图像数据。所述的基于分布式并行决策树的高维特征数据分类方法，其特征在于，该步骤2包括：将特征按照特征值数量排序后可得序列二分特征值总数的最大值k，使用动态规划算法得到g组总数不超过k的特征，找到最小的k，此时的g组即为最优特征分组。所述的基于分布式并行决策树的高维特征数据分类方法，其特征在于，步骤1中该预处理包括：对连续特征进行采样，把采样样本的特征值汇集到主节点，统计各个特征值的样本数，将所有特征值按照值的大小排序后得到序列，根据预设的最大特征划分数，将样本分组，每组作为连续特征的一个桶，相邻两组特征值的最小差别的中位数作为候选划分。所述的基于分布式并行决策树的高维特征数据分类方法，其特征在于，该元数据由训练数据统计得到，包括特征数、样本数、标签数、最大特征划分、离散特征取值范围、无序离散特征、最大深度、节点最小样本数和分裂最小信息增益。本发明还提供了一种基于分布式并行决策树的高维特征数据分类系统，其特征在于，包括：模块1、获取包括多个样本高维特征数据的训练数据，且该样本高维特征数据具有对应的标签类别，将该训练数据存储在分布式文件系统中，通过对该训练数据的样本在分布式集群上进行并行采样统计，获取该训练数据上的特征分布信息，获得支撑决策树计算的元数据，并对连续型特征进行预处理；模块2、通过对该元数据进行采样计算，为分布式集群中各计算节点分配特征组，建立树的根节点，分布式集群各工作节点联合统计样本的标签类别分布，以得到根节点初始信息熵；模块3、对所有样本高维特征数据在分布式集群上各个工作节点上分别对各自储存的样本数据进行统计，根据各样本的特征的向量及决策树的划分规则获得各样本当前所属树节点，同时统计四元组(所属节点，特征，特征值，标签)的出现次数，各节点将各四元组按照(节点，特征组)进行分组聚合，各工作节点分布式存储<(节点，特征组),(特征，特征值，标签)>的键值对的统计信息，根据该统计信息得到各特征值的信息熵；模块4、将特征值按照各自标签的信息熵排序，将所有标签的统计值归于右节点，然后顺序遍历特征值作为左节点特征值，每次遍历保留信息增益最大的特征值，得到<(节点，特征组)，最优划分>键值对，将相同节点各个特征组的最优划分聚合并取最优，得到<节点，最优划分>键值对，选择最优划分对节点进行划分；模块5、循环模块2到模块4直到对决策树中全部节点完成划分，保存当前决策树作为分类模型，将待分类数据输入该分类模型，得到该待分类数据对应的类别。所述的基于分布式并行决策树的高维特征数据分类系统，其特征在于，该训练数据为文本数据或图像数据。所述的基于分布式并行决策树的高维特征数据分类系统，其特征在于，该模块2包括：将特征按照特征值数量排序后可得序列二分特征值总数的最大值k，使用动态规划算法得到g组总数不超过k的特征，找到最小的k，此时的g组即为最优特征分组。所述的基于分布式并行决策树的高维特征数据分类系统，其特征在于，模块1中该预处理包括：对连续特征进行采样，把采样样本的特征值汇集到主节点，统计各个特征值的样本数，将所有特征值按照值的大小排序后得到序列，根据预设的最大特征划分数，将样本分组，每组作为连续特征的一个桶，相邻两组特征值的最小差别的中位数作为候选划分。所述的基于分布式并行决策树的高维特征数据分类系统，其特征在于，该元数据由训练数据统计得到，包括特征数、样本数、标签数、最大特征划分、离散特征取值范围、无序离散特征、最大深度、节点最小样本数和分裂最小信息增益。针对现有技术的不足，本发明提出一种由以上方案可知，本发明的优点在于：本发明实现了基于spark的节点与特征全并行的二叉决策树算法，与现有技术相比，本发明提高了决策树模型的并行效率，在大规模高维数据的的处理上更加高效。可以有效减少最优划分选择时遍历所有划分方式的时间。在当前计算资源更丰富的条件下能更好地利用大规模集群，非常适合当前工业界对特征进行组合然后建立树分类模型的主流方法。发明人对10000维现实数据在较小规模集群上进行实验，相比最流行的spark并行决策树算法，本发明能将模型建立时间缩短30％以上，在集群规模更大、数据维度更高的情况下可以达到更好的效果。附图说明图1为本发明决策树构建流程图；图2为本发明决策树算法在spark中数据转换示意图。具体实施方式发明人在进行大规模数据挖掘研究时，发现会出现数据维度很大的情况，而现有决策树算法对这种数据不能很好地进行处理。原因是串行决策树无法处理大规模数据，而现有并行决策树算法并行程度较低，最快的算法也仅是在节点层面上并行，而没有在最优特征选择的部分进行并行。在特征维度较大且特征值较多的情况下，使用多叉决策树会导致决策树节点过多而造成内存使用过大和过拟合，使用二叉决策树则必须对所有可能的节点划分进行遍历，求每一种划分的信息增益并决策最优节点，也会带来较大时间消耗。现有并行决策树算法没有考虑到这种情况，原因是自然产生的数据很少会有特征维度特别大的情况。但是工业界经常会采用将多维特征进行组合产生新特征的做法，这样做使得最终特征维度呈现指数级增长，这种情况下，传统并行决策树无法高效地对高维特征进行筛选并建立最好的分类模型。发明人经过研究发现，该项缺陷可以通过在特征层面上并行来实现。如果希望在特征层面上进行并行，需要spark各节点分别计算各特征的最优划分，由于分布式系统的特点，这样做虽然从理论角度会大幅减少时间消耗，但是由于各节点之间shuffle所需要的数据传递时间、各节点数据分布不平衡导致节点等待的时间消耗等，并不能直接将各特征划分到spark的各节点中进行处理。在现有基于节点并行的并行决策树的基础上，发明人研究了特征划分部分的复杂度，并对最优特征选择部分进行优化，发现特征划分的复杂度由总特征值数量决定，为了增大并行程度并平衡spark其他时间消耗，发明人设计出一种将特征按照特征值数量进行平衡分组，从样本划分步骤开始就按照节点、特征同时并行处理以进行最优划分的并行决策树算法。在本发明中设计实现了基于spark的面向高维特征数据的并行决策树算法，该并行算法并行程度高，可以处理大规模数据集，不仅在决策树中同一层节点之间进行并行计算，而且能够在特征层面上进行并行计算，提高了高维数据的并行程度，能够有效减少高维特征的处理时间。本发明包括以下关键点：关键点1，设计实现了在特征维度并行的并行二叉决策树算法，提高了并行决策树算法在高维数据上的处理效率。关键点2，特征分组并行且组的大小可根据集群情况调节，平衡数据传输消耗和节点运算时间消耗，最大程度上对集群进行有效利用，提高并行效率。关键点3，通过对特征按照特征值平均分组，平衡了各个节点的运算量，能够进一步减少集群中节点的空闲时间，减少运算时间。为让本发明的上述特征和效果能阐述的更明确易懂，下文特举实施例，并配合说明书附图作详细说明如下。决策树算法如图1所示，并行决策树算法在spark中的实现，基本过程是首先对数据进行统计，获取特征分布等信息，然后将所有样本放入决策树根节点，并行计算样本特征、标签等统计信息，并据此计算出各个特征划分的信息增益，选择最优的划分方式并对节点进行划分。在本发明的并行决策树构件中，进一步提高决策树的并行程度，对于决策树上每一层的所有节点并行进行最优划分的选择，同时通过对特征进行分组，进一步在特征层面上进行信息增益的并行计算。算法在spark中数据转换如图2所示，算法具体步骤为：建立元数据(元数据中保存计算过程中需要使用的统计信息，以及用户设置的超参数等)。元数据由输入样本(输入样本包含所有训练数据，每条样本含有样本编号，样本所有特征，样本类别标签)统计得到，包括特征数，样本数，标签label数，最大特征划分，离散特征取值范围(各特征可取值的数量)，无序离散特征，最大深度，节点最小样本数，分裂最小信息增益等。连续特征预处理。由于本发明主要思路为将特征按照可能的划分数量(关系到计算量，下一段详细介绍)分组以实现高维特征下的并行处理，而连续特征可选的划分方式过多，无法提前确定计算量，因此本发明对连续特征进行预处理，在决策树建立之前确定可能的候选方案，具体来说对于连续特征，首先预先为每个连续特征(取值为连续数值的特征，比如椅子的高度特征取值可能为1米,1.2米，...。与之对应的是离散特征，比如椅子的颜色(特征)取值可能是黄色，红色)选择候选划分方式。具体来说，首先对样本进行采样，把采样样本的特征值(特征向量上需要进行预处理的这维特征的在所有样本上的取值)汇集到主节点driver，统计各个特征值的样本数，将所有特征值按照值的大小排序后得到序列(a1，count1)，(a2，count2)，...，(an，countn)，根据最初选定的最大特征划分数，以每组样本数尽量相等的原则划分成若干组(将特征的值划分成若干个区间，比如需要划分特征值处理后可能划分为0-0.2,0.3-0.4,0.7-1三个区间，落在三个区间内的样本数尽量相当，取两个区间相邻边界等中位数作为划分，如上例划分后两种候选划分为0.25,0.55)，每组作为连续特征的一个桶bin，相邻两组特征值的最小差别的中位数作为候选划分。特征平衡分组。为了把计算特征的最优划分的任务分散到各个工作节点worker，需要把特征划分成若干组，每个worker进行一组特征最优划分的计算。此步的时间取决于工作时间最长的worker，而最优划分计算的复杂度是o(∑i∈fvi),其中f是该组特征的集合，vi表示该特征特征值或bin的数量。因此为了最小化工作时间，需要让各组特征的特征值总数的最大值最小。将特征按照特征值数量排序后可得序列其中v表示各特征对应的特征值数量，对于离散型特征，此值为所有可能的特征取值数，对于连续型特征，此值为候选划分数。根据预设的分组数g，二分查找一个最小的值k，使得能够找到一种划分，使得划分组数不超过g，且每组内特征的特征取值数总和(或可能的划分数总和)不超过k，二分查找时对于确定的k可使用贪心算法找到具体划分，最终那个最小的k对应的分组方案为最优特征分组。此时的g组即为最优特征分组。在这种分组下，集群上各个工作节点所承担的最大计算量最小，计算量分配最为均衡，因此可以最大程度减少并行处理过程中已完成自身任务的工作节点等待其他节点完成任务的时间。节点信息统计。所有样本根据各自特征向量，按照已建决策树划分规则确定所在树节点，在所有样本上同时计算各个节点的特征值及标签分布情况，具体来说是统计(所属节点，特征，特征值，标签)四元组的数量。为了减少传输的消耗，首先在并行任务各个分区上分别进行统计，然后将统计值按照(节点，特征组)进行分组聚合，在各工作节点上得到<(节点，特征组),(特征，特征值，标签)>的键值对。最优划分计算。在各个(节点，特征组)上，分别计算各个特征的最优划分。对于连续特征，按顺序遍历所有候选划分，首先将所有标签的统计值归于右节点，每次将该划分对应的各标签数放入左节点，获得两个节点的标签数进行信息增益的计算。对于离散特征，首先将特征值按照各自标签的信息熵排序，然后顺序遍历特征值作为左节点特征值。每次遍历保留信息增益最大的特征值，则得到<(节点，特征组)，最优划分>键值对。将相同节点各个特征组的最优划分聚合并取最优，得到<节点，最优划分>键值对。节点划分。按照各节点最优划分，将节点划分出左右子节点，将划分信息写入节点信息，结束当前层节点划分。以西瓜数据集为例：编号色泽根蒂敲声纹理脐部触感好瓜1青绿蜷缩浊响清晰凹陷硬滑是2青绿硬挺清脆清晰平坦软粘否3乌黑蜷缩浊响清晰凹陷硬滑是4浅白蜷缩浊响模糊平坦软粘否5浅白蜷缩浊响清晰凹陷硬滑是6浅白稍蜷沉闷稍糊凹陷硬滑否7乌黑稍蜷浊响稍糊稍凹软粘是8浅白蜷缩浊响模糊平坦硬滑否9乌黑稍蜷沉闷稍糊稍凹硬滑否10乌黑蜷缩沉闷清晰凹陷硬滑是11浅白硬挺清脆模糊平坦硬滑否12青绿蜷缩沉闷清晰凹陷硬滑是13青绿稍蜷浊响稍糊凹陷硬滑否14青绿稍蜷浊响清晰稍凹软粘是15乌黑稍蜷浊响清晰稍凹软粘否16乌黑稍蜷浊响清晰稍凹硬滑是17青绿蜷缩沉闷稍糊稍凹硬滑否特征分组设分为三组统计后各特征特征值数为:色泽:3根蒂:3敲声:3纹理:3脐部:3触感:2按照特征值量平衡的原则，平均分组为(1:{色泽,根蒂},2:{敲声,纹理},3:{脐部，触感})样本划分统计：按决策树现有规则确定样本所属node编号色泽根蒂敲声纹理脐部触感好瓜node1青绿蜷缩浊响清晰凹陷硬滑是02青绿硬挺清脆清晰平坦软粘否03乌黑蜷缩浊响清晰凹陷硬滑是04浅白蜷缩浊响模糊平坦软粘否05浅白蜷缩浊响清晰凹陷硬滑是06浅白稍蜷沉闷稍糊凹陷硬滑否07乌黑稍蜷浊响稍糊稍凹软粘是08浅白蜷缩浊响模糊平坦硬滑否09乌黑稍蜷沉闷稍糊稍凹硬滑否010乌黑蜷缩沉闷清晰凹陷硬滑是011浅白硬挺清脆模糊平坦硬滑否012青绿蜷缩沉闷清晰凹陷硬滑是013青绿稍蜷浊响稍糊凹陷硬滑否014青绿稍蜷浊响清晰稍凹软粘是015乌黑稍蜷浊响清晰稍凹软粘否016乌黑稍蜷浊响清晰稍凹硬滑是017青绿蜷缩沉闷稍糊稍凹硬滑否0各partition统计样本信息partition合并第一组色泽是否乌黑42青绿33浅白14根蒂是否蜷缩53稍蜷34硬挺02最优划分:根蒂是否硬挺，熵0.89第二组敲声是否沉闷23浊响64清脆02纹理是否清晰72稍糊14模糊03最优：纹理是否模糊，熵0.83第三组脐部是否凹陷52稍凹33平坦04触感是否硬滑66软粘23最优：脐部是否平坦，熵0.76节点划分，将0节点划分为左右两个节点，分别是脐部平坦和非平坦。重复上述过程直到全部划分结束。以下为与上述方法实施例对应的系统实施例，本实施方式可与上述实施方式互相配合实施。上述实施方式中提到的相关技术细节在本实施方式中依然有效，为了减少重复，这里不再赘述。相应地，本实施方式中提到的相关技术细节也可应用在上述实施方式中。本发明还提供了一种基于分布式并行决策树的高维特征数据分类系统，其特征在于，包括：模块1、获取包括多个样本高维特征数据的训练数据，且该样本高维特征数据具有对应的标签类别，将该训练数据存储在分布式文件系统中，通过对该训练数据的样本在分布式集群上进行并行采样统计，获取该训练数据上的特征分布信息，获得支撑决策树计算的元数据，并对连续型特征进行预处理；模块2、通过对该元数据进行采样计算，为分布式集群中各计算节点分配特征组，建立树的根节点，分布式集群各工作节点联合统计样本的标签类别分布，以得到根节点初始信息熵；模块3、对所有样本高维特征数据在分布式集群上各个工作节点上分别对各自储存的样本数据进行统计，根据各样本的特征的向量及决策树的划分规则获得各样本当前所属树节点，同时统计四元组(所属节点，特征，特征值，标签)的出现次数，各节点将各四元组按照(节点，特征组)进行分组聚合，各工作节点分布式存储<(节点，特征组),(特征，特征值，标签)>的键值对的统计信息，根据该统计信息得到各特征值的信息熵；模块4、将特征值按照各自标签的信息熵排序，将所有标签的统计值归于右节点，然后顺序遍历特征值作为左节点特征值，每次遍历保留信息增益最大的特征值，得到<(节点，特征组)，最优划分>键值对，将相同节点各个特征组的最优划分聚合并取最优，得到<节点，最优划分>键值对，选择最优划分对节点进行划分；模块5、循环模块2到模块4直到对决策树中全部节点完成划分，保存当前决策树作为分类模型，将待分类数据输入该分类模型，得到该待分类数据对应的类别。所述的基于分布式并行决策树的高维特征数据分类系统，其特征在于，该训练数据为文本数据或图像数据。所述的基于分布式并行决策树的高维特征数据分类系统，其特征在于，该模块2包括：将特征按照特征值数量排序后可得序列二分特征值总数的最大值k，使用动态规划算法得到g组总数不超过k的特征，找到最小的k，此时的g组即为最优特征分组。所述的基于分布式并行决策树的高维特征数据分类系统，其特征在于，模块1中该预处理包括：对连续特征进行采样，把采样样本的特征值汇集到主节点，统计各个特征值的样本数，将所有特征值按照值的大小排序后得到序列，根据预设的最大特征划分数，将样本分组，每组作为连续特征的一个桶，相邻两组特征值的最小差别的中位数作为候选划分。所述的基于分布式并行决策树的高维特征数据分类系统，其特征在于，该元数据由训练数据统计得到，包括特征数、样本数、标签数、最大特征划分、离散特征取值范围、无序离散特征、最大深度、节点最小样本数和分裂最小信息增益。当前第1页1 2 3
技术特征：1.一种基于分布式并行决策树的高维特征数据分类方法，其特征在于，包括：
步骤1、获取包括多个样本高维特征数据的训练数据，且该样本高维特征数据具有对应的标签类别，将该训练数据存储在分布式文件系统中，通过对该训练数据的样本在分布式集群上进行并行采样统计，获取该训练数据上的特征分布信息，获得支撑决策树计算的元数据，并对连续型特征进行预处理；
步骤2、通过对该元数据进行采样计算，为分布式集群中各计算节点分配特征组，建立树的根节点，分布式集群各工作节点联合统计样本的标签类别分布，以得到根节点初始信息熵；
步骤3、对所有样本高维特征数据在分布式集群上各个工作节点上分别对各自储存的样本数据进行统计，根据各样本的特征的向量及决策树的划分规则获得各样本当前所属树节点，同时统计四元组(所属节点，特征，特征值，标签)的出现次数，各节点将各四元组按照(节点，特征组)进行分组聚合，各工作节点分布式存储<(节点，特征组),(特征，特征值，标签)>的键值对的统计信息，根据该统计信息得到各特征值的信息熵；
步骤4、将特征值按照各自标签的信息熵排序，将所有标签的统计值归于右节点，然后顺序遍历特征值作为左节点特征值，每次遍历保留信息增益最大的特征值，得到<(节点，特征组)，最优划分>键值对，将相同节点各个特征组的最优划分聚合并取最优，得到<节点，最优划分>键值对，选择最优划分对节点进行划分；
步骤5、循环步骤2到步骤4直到对决策树中全部节点完成划分，保存当前决策树作为分类模型，将待分类数据输入该分类模型，得到该待分类数据对应的类别。
2.如权利要求1所述的基于分布式并行决策树的高维特征数据分类方法，其特征在于，该训练数据为文本数据或图像数据。
3.如权利要求1所述的基于分布式并行决策树的高维特征数据分类方法，其特征在于，该步骤2包括：
将特征按照特征值数量排序后可得序列二分特征值总数的最大值k，使用动态规划算法得到g组总数不超过k的特征，找到最小的k，此时的g组即为最优特征分组。
4.如权利要求1所述的基于分布式并行决策树的高维特征数据分类方法，其特征在于，步骤1中该预处理包括：对连续特征进行采样，把采样样本的特征值汇集到主节点，统计各个特征值的样本数，将所有特征值按照值的大小排序后得到序列，根据预设的最大特征划分数，将样本分组，每组作为连续特征的一个桶，相邻两组特征值的最小差别的中位数作为候选划分。
5.如权利要求1所述的基于分布式并行决策树的高维特征数据分类方法，其特征在于，该元数据由训练数据统计得到，包括特征数、样本数、标签数、最大特征划分、离散特征取值范围、无序离散特征、最大深度、节点最小样本数和分裂最小信息增益。
6.一种基于分布式并行决策树的高维特征数据分类系统，其特征在于，包括：
模块1、获取包括多个样本高维特征数据的训练数据，且该样本高维特征数据具有对应的标签类别，将该训练数据存储在分布式文件系统中，通过对该训练数据的样本在分布式集群上进行并行采样统计，获取该训练数据上的特征分布信息，获得支撑决策树计算的元数据，并对连续型特征进行预处理；
模块2、通过对该元数据进行采样计算，为分布式集群中各计算节点分配特征组，建立树的根节点，分布式集群各工作节点联合统计样本的标签类别分布，以得到根节点初始信息熵；
模块3、对所有样本高维特征数据在分布式集群上各个工作节点上分别对各自储存的样本数据进行统计，根据各样本的特征的向量及决策树的划分规则获得各样本当前所属树节点，同时统计四元组(所属节点，特征，特征值，标签)的出现次数，各节点将各四元组按照(节点，特征组)进行分组聚合，各工作节点分布式存储<(节点，特征组),(特征，特征值，标签)>的键值对的统计信息，根据该统计信息得到各特征值的信息熵；
模块4、将特征值按照各自标签的信息熵排序，将所有标签的统计值归于右节点，然后顺序遍历特征值作为左节点特征值，每次遍历保留信息增益最大的特征值，得到<(节点，特征组)，最优划分>键值对，将相同节点各个特征组的最优划分聚合并取最优，得到<节点，最优划分>键值对，选择最优划分对节点进行划分；
模块5、循环模块2到模块4直到对决策树中全部节点完成划分，保存当前决策树作为分类模型，将待分类数据输入该分类模型，得到该待分类数据对应的类别。
7.如权利要求6所述的基于分布式并行决策树的高维特征数据分类系统，其特征在于，该训练数据为文本数据或图像数据。
8.如权利要求6所述的基于分布式并行决策树的高维特征数据分类系统，其特征在于，该模块2包括：
将特征按照特征值数量排序后可得序列二分特征值总数的最大值k，使用动态规划算法得到g组总数不超过k的特征，找到最小的k，此时的g组即为最优特征分组。
9.如权利要求6所述的基于分布式并行决策树的高维特征数据分类系统，其特征在于，模块1中该预处理包括：对连续特征进行采样，把采样样本的特征值汇集到主节点，统计各个特征值的样本数，将所有特征值按照值的大小排序后得到序列，根据预设的最大特征划分数，将样本分组，每组作为连续特征的一个桶，相邻两组特征值的最小差别的中位数作为候选划分。
10.如权利要求6所述的基于分布式并行决策树的高维特征数据分类系统，其特征在于，该元数据由训练数据统计得到，包括特征数、样本数、标签数、最大特征划分、离散特征取值范围、无序离散特征、最大深度、节点最小样本数和分裂最小信息增益。
技术总结本发明提出一种基于分布式并行决策树的高维特征数据分类方法及系统。实现了基于Spark的面向高维特征数据的并行决策树算法，该并行算法并行程度高，可以处理大规模数据集，不仅在决策树中同一层节点之间进行并行计算，而且能够在特征层面上进行并行计算，提高了高维数据的并行程度，能够有效减少高维特征的处理时间。
技术研发人员：孙莹;庄福振;敖翔;何清
受保护的技术使用者：中国科学院计算技术研究所
技术研发日：2020.01.09
技术公布日：2020.06.09
