一种分类树构建方法及基于该分类树的数据处理方法与流程

1.本发明属于计算机技术领域，涉及数据处理技术，尤其涉及分类算法，具体为一种改进的分类树构建方法及基于该分类树的数据处理方法。


背景技术：

2.决策树是分类算法的典型代表，其基于带标记样本，采用一定的分裂准则，通过自顶向下的方式构造树状结构，形成直观的分类规则，是一种简单而实用的非线性分类器。
3.quinlan于1979年提出id3算法，其算法流程借鉴了hunt等提出的cls，即自顶向下的归纳学习方式。id3引入了信息驱动评价函数，替代了cls的成本驱动方式，以信息熵代表结点纯度，采用信息增益作为分裂属性的择优准则，递归构造决策树。基于信息增益的分裂准则会偏向于选择取值可能性较多(v值较大)的特征属性，易造成无意义的分类。为克服这一缺点，quinlan在id3的基础上，以增益率替代信息增益作为特征属性选择度量，提出c4.5算法。决策树的另一个典型代表是breiman等统计学家提出的cart算法。cart在处理分类问题时，以基尼指数作为样本集合不纯度的度量，对结点进行二元划分。
4.综上，常规的分类树算法只能考虑离散型和连续型特征属性。


技术实现要素：

5.本发明的目的之一在于提出一种改进的分类树构建方法，使之能够考虑向量型特征属性，区别于以往的方法，支持具有离散型、连续型和向量型三种类型特征的带标记样本，更加适应样本多样化的需求，提升分类算法的性能。
6.本发明的目的之二在于采用改进后的分类树进行数据处理，在样本集合中添加向量型特征能够更好地对样本进行刻画，从而进行更为准确的分类预测。
7.本发明的目的是通过以下技术方案实现的：
8.一种分类树的构建方法，包括以下步骤：
9.1)初始化分类树：采集样本数据，生成根结点，将所有样本均归于根结点，取样本集合类标记的众数作为根结点的类标记，初始化的根结点同时为当前唯一的叶子结点；
10.2)遍历结点，判断是否可分，包括以下步骤：
11.2-1遍历所有结点，寻找当前分类树最深的一层中的叶子结点；
12.2-2计算结点基尼指数，设该结点包含的样本子集为d，则其基尼指数计算方法为：
[0013][0014]
式中，k为d中包含的样本分类个数，pk为第k类样本所占比例；
[0015]
2-3设置阈值th
min
，th
min
为结点分裂所需的最小样本数量，小于该值结点终止分裂；
[0016]
2-4判断叶子结点是否可分，叶子结点可分的条件为结点基尼指数大于0且结点包含样本数量大于阈值th
min
；
[0017]
3)寻找分裂属性：遍历样本特征属性集合a中的各个特征属性，计算每个属性不同划分方式的不纯度降低值δgini，以δgini最大为原则选择分裂属性；针对离散型、连续型和向量型特征属性，其划分方式以及不纯度降低值的计算方式分别为：
[0018]
3-1对于特征属性a，若其为离散型变量，设其包含v个不同特征，则依次将每一个特征作为一类，其余特征作为一类，共v种划分方式；
[0019]
3-2对于特征属性a，若其为连续型变量，则排序去重后，依次取相邻特征值的平均数，根据样本的特征属性为大于此值还是小于此值，将样本划分为两组，共v'-1种划分方式，v'为去重后的特征值个数；
[0020]
3-3对于特征属性a，若其为向量型变量，选择相似性度量标准，计算结点内此特征属性各特征向量的相似性矩阵；根据二分类树的特性，依次选择某一特征向量作为聚类中心，基于相似性矩阵选择距其最远的特征向量作为另一聚类中心；采用最邻近规则，对其余特征向量进行划分，依次划分至两个聚类中心所在的簇中；
[0021]
3-4计算不纯度降低值：设特征属性a将叶子结点的样本子集d划分为d
l
和dr，则划分后d的基尼指数为：
[0022][0023]
对d进行划分后的不纯度降低值为：
[0024]
δgini＝gini(d)-ginia(d)
ꢀꢀꢀ
(5)
[0025]
3-5选择分裂属性：遍历样本特征属性集合a中的各个特征属性，计算每个属性不同划分方式的不纯度降低值δgini，以δgini最大为原则选择分裂属性；
[0026]
4)进行结点分裂，记录分裂信息：基于步骤3)中计算的特征属性划分方式对叶子结点的样本进行划分，完成叶子结点的分裂，将原结点标记为非叶子结点，记录新生成的左叶子结点和右叶子结点所包含的样本及其基尼指数，同时记录树的生长深度；
[0027]
5)标记叶子结点：遍历新生成的左右叶子结点的样本，以样本标记众数作为此叶子结点的标记；
[0028]
6)分类树的生长：设置阈值thd限制树的最大生长深度，当树的生长深度超过该值时停止生长；设置阈值ths限制结点分裂所需的最小样本数量，小于该值结点终止分裂；设置阈值thg限制分裂所需的最小增益，小于该值结点终止分裂；重复步骤2)、3)、4)、5)，当超过三个阈值的限制或者所有叶子节点均不可再分时，则完成分类树的生长。
[0029]
进一步的优选，步骤3-3中的选择相似性度量标准包括欧氏距离、dtw距离及其他适合的相似性度量标准中任意一种。
[0030]
进一步的，步骤3-3中，当特征向量为等长向量时，采用以欧氏距离为代表的距离度量方法，设其中两个特征向量为x＝{x1,x2,...,xi,...,xn}和y＝{y1,y2,...,yi,...,yn}，其欧氏距离的计算方式为：
[0031][0032]
进一步的，步骤3-3中，特征属性a的特征向量为非等长向量时，采用以dtw距离为代表的距离度量方法，具体方式为：
[0033]
对于特征向量x＝{x1,x2,...,xi,...,xm}和y＝{y1,y2,...,yj,...,yn}，其中m≠n，首先构建一个m
×
n阶矩阵，矩阵元素(i,j)为两个特征向量点xi和点yj之间的距离d(xi,yj)＝(x
i-yj)2，定义点(i,j)的累积距离计算公式：
[0034]
γ(i,j)＝d(xi,yj)+min{γ(i-1,j-1),γ(i-1,j),γ(i,j-1)}
ꢀꢀꢀ
(3)
[0035]
给定初始条件γ(1,1)＝d(x1,y1)，迭代计算得到累积距离矩阵，即为特征向量x与y的dtw距离。
[0036]
采用所述分类树进行数据处理的方法，通过所构建的分类树对目标结果进行预测或判定。
[0037]
所述数据处理的样本为具有离散型、连续型和向量型三种类型特征的带标记样本。
[0038]
本发明的优点和有益效果是：
[0039]
本发明提出一种改进的分类树构建方法在样本集合中添加向量型特征能够更好地对样本进行刻画，从而进行更为准确的分类预测，如在心脏病样本中添加心电图(ecg)序列，在动物识别样本中添加基因序列，均为向量型特征，本发明中公开的方法能够将此类特征作为分类树的结点分裂属性，从而提升分类算法的性能。
附图说明
[0040]
下面结合附图和实施例对本发明作进一步说明。
[0041]
图1是本发明分类树构建方法示意流程图。
具体实施方式
[0042]
实施例一：
[0043]
一种分类树构建方法，包括以下步骤：
[0044]
1)初始化分类树，具体内容为：采集样本数据，生成根结点，将所有样本均归于根结点，取样本集合类标记的众数作为根结点的类标记，初始化的根结点同时为当前唯一的叶子结点。
[0045]
2)遍历结点，判断是否可分；
[0046]
2-1遍历所有结点，寻找当前分类树最深的一层中的叶子结点；
[0047]
2-2计算结点基尼指数，设该结点包含的样本子集为d，则其基尼指数计算方法为：
[0048][0049]
式中，k为d中包含的样本分类个数，pk为第k类样本所占比例。
[0050]
2-3设置阈值th
min
，th
min
为结点分裂所需的最小样本数量，小于该值结点终止分裂；
[0051]
2-4判断叶子结点是否可分，叶子结点可分的条件为结点基尼指数大于0且结点包含样本数量大于阈值th
min
。
[0052]
3)寻找分裂属性；遍历样本特征属性集合a中的各个特征属性，计算每个属性不同划分方式的不纯度降低值δgini，以δgini最大为原则选择分裂属性。针对离散型、连续型
和向量型特征属性，其划分方式以及不纯度降低值的计算方式分别为：
[0053]
3-1对于特征属性a，若其为离散型变量，设其包含v个不同特征，则依次将每一个特征作为一类，其余特征作为一类，共v种划分方式；
[0054]
3-2对于特征属性a，若其为连续型变量，则排序去重后，依次取相邻特征值的平均数将样本划分为两组，共v'-1种划分方式，v'为去重后的特征值个数；
[0055]
3-3对于特征属性a，若其为向量型变量，首先选择欧氏距离、dtw距离或者其他适合的相似性度量标准，计算结点内此特征属性各特征向量的相似性矩阵。
[0056]
3-3-1当特征向量为等长向量时，可以采用以欧氏距离为代表的距离度量方法，设其中两个特征向量为x＝{x1,x2,...,xi,...,xn}和y＝{y1,y2,...,yi,...,yn}，其欧氏距离的计算方式为：
[0057][0058]
3-3-2特征属性a的特征向量可以为非等长向量。此时可以采用以dtw距离为代表的距离度量方法，具体方式为：
[0059]
对于特征向量x＝{x1,x2,...,xi,...,xm}和y＝{y1,y2,...,yj,...,yn}，其中m≠n，首先构建一个m
×
n阶矩阵，矩阵元素(i,j)为两个特征向量点xi和点yj之间的距离d(xi,yj)＝(x
i-yj)2。定义点(i,j)的累积距离计算公式：
[0060]
γ(i,j)＝d(xi,yj)+min{γ(i-1,j-1),γ(i-1,j),γ(i,j-1)}
ꢀꢀꢀ
(3)
[0061]
给定初始条件γ(1,1)＝d(x1,y1)，可以迭代计算得到累积距离矩阵。即为特征向量x与y的dtw距离。
[0062]
根据二分类树的特性，依次选择某一特征向量作为聚类中心，基于相似性矩阵选择距其最远的特征向量作为另一聚类中心；采用最邻近规则，对其余特征向量进行划分，依次划分至两个聚类中心所在的簇中；
[0063]
3-4计算不纯度降低值。设特征属性a将叶子结点的样本子集d划分为d
l
和dr，则划分后d的基尼指数为：
[0064][0065]
对d进行划分后的不纯度降低值为：
[0066]
δgini＝gini(d)-ginia(d)
ꢀꢀꢀ
(5)
[0067]
3-5选择分裂属性。遍历样本特征属性集合a中的各个特征属性，计算每个属性不同划分方式的不纯度降低值δgini，以δgini最大为原则选择分裂属性。
[0068]
4)进行结点分裂，记录分裂信息；基于步骤3)中计算的特征属性划分方式对叶子结点的样本进行划分，完成叶子结点的分裂，将原结点标记为非叶子结点，记录新生成的左叶子结点和右叶子结点所包含的样本及其基尼指数，同时记录树的生长深度。
[0069]
5)标记叶子结点；遍历新生成的左右叶子结点的样本，以样本标记众数作为此叶子结点的标记。
[0070]
6)分类树的生长；设置阈值thd限制树的最大生长深度，当树的生长深度超过该值
时停止生长；设置阈值ths限制结点分裂所需的最小样本数量，小于该值结点终止分裂；设置阈值thg限制分裂所需的最小增益，小于该值结点终止分裂；重复过程2)、3)、4)、5)，当超过三个阈值的限制或者所有叶子节点均不可再分时，则完成分类树的生长。
[0071]
实施例二：
[0072]
利用人体相关的体测指标，基于实施例一方法构建的分类树来预测对象的心脏病风险。
[0073]
构建心脏病数据集，数据集的特征包括：年龄、性别、心绞痛类型、静息血压、胆固醇、空腹血糖、心电图；数据标签为是否为心脏病。
[0074]
数据集内的年龄、静息血压、胆固醇、空腹血糖为连续型特征属性，性别、心绞痛类型为离散型特征属性，心电图属于向量型特征属性。
[0075]
以所构建的数据集训练分类树，即可对新的病例是否有心脏病风险进行预测。
[0076]
实施例三：
[0077]
基于实施例一方法构建的分类树利用脊椎动物的特征属性判断动物类型。
[0078]
构建脊椎动物数据集，数据集的特征包括：体温、表皮覆盖、是否胎生、是否水生、是否飞行、是否有腿、是否冬眠、体长、基因序列；数据标签为动物类，包括哺乳类、爬行类、鱼类、两栖类、鸟类。
[0079]
数据集内的体温、体长为连续型特征属性，表皮覆盖、是否胎生、是否水生、是否飞行、是否有腿、是否冬眠为离散型特征属性，基因序列属于向量型特征属性。
[0080]
以所构建的数据集训练分类树，即可对新发现动物物种的类型进行判断。
[0081]
实施例四：
[0082]
基于实施例一方法构建的分类树利用河流水系物理特征属性判断其洪水响应特征。
[0083]
构建河流水系物理特征集，数据集的特征包括：所属流域、流域面积、河长、平均土壤深度、流域轮廓形状特征、年平均降水量，其中所属流域为离散型特征，流域面积、河长、平均土壤深度、年平均降水量为连续型特征，形状特征为向量型特征，数据集的标记为流域洪水响应特征，其中快速标记为0，中等标记为1，慢速标记为2，各流域特征属性值及洪水响应标记如表1所示。
[0084]
表1流域特征属性及洪水响应标记表
[0085]
[0086]
[0087][0088]
依照本发明公开的方法训练分类树，设置阈值thd＝20，设置阈值ths＝2，设置阈值thg＝0，充分生长后分类树的结点信息如表2所示：
[0089]
表2分类树结点属性表
[0090]
[0091]
[0092]
[0093]
[0094]
[0095]
[0096]
[0097]
[0098]
[0099]
[0100]
[0101]
[0102]
[0103]
[0104]
[0105]
[0106]
[0107][0108]
对于未知洪水响应类型的流域，收集其基本特征如表3所示：
[0109]
表3流域特征属性表
[0110][0111]
采用上述训练的分类树对其洪水响应类型进行预测，得到标记为1，即响应速度为中等。
[0112]
最后应说明的是，以上仅用以说明本发明的技术方案而非限制，尽管参照较佳布置方案对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明技术方案的精神和范围。

技术特征：
1.一种分类树构建方法，其特征在于，包括以下步骤：1)初始化分类树：采集样本数据，生成根结点，将所有样本均归于根结点，取样本集合类标记的众数作为根结点的类标记，初始化的根结点同时为当前唯一的叶子结点；2)遍历结点，判断是否可分，包括以下步骤：2-1遍历所有结点，寻找当前分类树最深的一层中的叶子结点；2-2计算结点基尼指数，设该结点包含的样本子集为d，则其基尼指数计算方法为：式中，k为d中包含的样本分类个数，p
k
为第k类样本所占比例；2-3设置阈值th
min
，th
min
为结点分裂所需的最小样本数量，小于该值结点终止分裂；2-4判断叶子结点是否可分，叶子结点可分的条件为结点基尼指数大于0且结点包含样本数量大于阈值th
min
；3)寻找分裂属性：遍历样本特征属性集合a中的各个特征属性，计算每个属性不同划分方式的不纯度降低值δgini，以δgini最大为原则选择分裂属性；针对离散型、连续型和向量型特征属性，其划分方式以及不纯度降低值的计算方式分别为：3-1对于特征属性a，若其为离散型变量，设其包含v个不同特征，则依次将每一个特征作为一类，其余特征作为一类，共v种划分方式；3-2对于特征属性a，若其为连续型变量，则排序去重后，依次取相邻特征值的平均数，根据样本的特征属性为大于此值还是小于此值，将样本划分为两组，共v'-1种划分方式，v'为去重后的特征值个数；3-3对于特征属性a，若其为向量型变量，选择相似性度量标准，计算结点内此特征属性各特征向量的相似性矩阵；根据二分类树的特性，依次选择某一特征向量作为聚类中心，基于相似性矩阵选择距其最远的特征向量作为另一聚类中心；采用最邻近规则，对其余特征向量进行划分，依次划分至两个聚类中心所在的簇中；3-4计算不纯度降低值：设特征属性a将叶子结点的样本子集d划分为左子叶节点集合d
l
和右子叶节点集合d
r
，则划分后d的基尼指数为：对d进行划分后的不纯度降低值为：δgini＝gini(d)-gini
a
(d)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(5)3-5选择分裂属性：遍历样本特征属性集合a中的各个特征属性，计算每个属性不同划分方式的不纯度降低值δgini，以δgini最大为原则选择分裂属性；4)进行结点分裂，记录分裂信息：基于步骤3)中计算的特征属性划分方式对叶子结点的样本进行划分，完成叶子结点的分裂，将原结点标记为非叶子结点，记录新生成的左叶子结点和右叶子结点所包含的样本及其基尼指数，同时记录树的生长深度；5)标记叶子结点：遍历新生成的左右叶子结点的样本，以样本标记众数作为此叶子结点的标记；6)分类树的生长：设置阈值th
d
限制树的最大生长深度，当树的生长深度超过该值时停
止生长；阈值th
min
限制结点分裂所需的最小样本数量，小于该值结点终止分裂；设置阈值th
g
限制分裂所需的最小增益，小于该值结点终止分裂；重复步骤2)、3)、4)、5)，当超过三个阈值的限制或者所有叶子节点均不可再分时，则完成分类树的生长。2.根据权利要求1所述的分类树构建方法，其特征在于，步骤3-3中的选择相似性度量标准包括欧氏距离、dtw距离中任意一种。3.根据权利要求2所述的分类树构建方法，其特征在于，步骤3-3中，当特征向量为等长向量时，采用以欧氏距离为代表的距离度量方法，设其中两个特征向量为x＝{x1,x2,
…
,x
i
,
…
,x
n
}和y＝{y1,y2,
…
,y
i
,
…
,y
n
}，其欧氏距离的计算方式为：4.根据权利要求2所述的分类树构建方法，其特征在于，步骤3-3中，特征属性a的特征向量为非等长向量时，采用以dtw距离为代表的距离度量方法，具体方式为：对于特征向量x＝{x1,x2,
…
,x
i
,...,x
m
}和y＝{y1,y2,...,y
j
,...,y
n
}，其中m≠n，首先构建一个m
×
n阶矩阵，矩阵元素(i,j)为两个特征向量点x
i
和点y
j
之间的距离d(x
i
,y
j
)＝(x
i-y
j
)2，定义点(i,j)的累积距离计算公式：γ(i,j)＝d(x
i
,y
j
)+min{γ(i-1,j-1),γ(i-1,j),γ(i,j-1)}
ꢀꢀꢀꢀꢀꢀꢀ
(3)给定初始条件γ(1,1)＝d(x1,y1)，迭代计算得到累积距离矩阵，即为特征向量x与y的dtw距离。5.采用权利要求1～4中任意一项的所述分类树构建方法构建的分类树进行数据处理的方法，其特征在于：通过所构建的分类树对目标结果进行预测或判定。6.根据权利要求5所述的数据处理方法，其特征在于：所述数据处理的样本为具有离散型、连续型和向量型三种类型特征的带标记样本。

技术总结
本发明公开了一种分类树构建方法及基于该分类树的数据处理方法，分类树构建包括以下步骤：1)初始化分类树；2)遍历结点，判断是否可分；3)计算分裂属性；4)进行结点分裂，记录分裂信息；5)标记叶子结点；6)分类树的生长。常规的分类树只支持离散型和连续型的特征属性，本发明提出分类树构建方法，使之能够支持向量型的特征属性，从而对样本数据进行更为准确的分类预测。预测。预测。


技术研发人员：王帆 向立云 张大伟 张丹 白钰 姜晓明
受保护的技术使用者：中国水利水电科学研究院
技术研发日：2021.12.06
技术公布日：2022/3/8