# US 2022/0036250 A1 · Method and device for training tree model

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0036250 A1
- Document ID: US20220036250A1
- Status: Published application
- Kind: A1
- Application number: 17/372,921
- Filed: 2021-07-12
- Published: 2022-02-03
- Earliest claimed: 2020-07-30
- Assignees: Huakong Tsingjiao Information Science (Beijing) Limited
- Applicants: Huakong Tsingjiao Information Science (Beijing) Limited
- Inventors: Guosai Wang; Xu He; Xiaoyu Fan; Kun Chen
- Web page: https://patentgrep.com/patent/US20220036250A1

## CPC

- G06N 20/00: Machine learning
- G06N 20/20: Ensemble learning
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 5/04: Inference or reasoning models
- Y02T 10/40: Engine management systems
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- Y02T: CLIMATE CHANGE MITIGATION TECHNOLOGIES RELATED TO TRANSPORTATION

## Abstract

A method and device for training a tree model based on a dataset are disclosed. The dataset comprises m pieces of sample data and m sample labels, each sample data comprises n features, the features and feature values in the dataset are ciphertexts, the method comprises: generating, for the dataset, candidate splits based on ciphertexts; partitioning, for each candidate split, the dataset into a left and right subset based on ciphertexts; calculating a partition coefficient of each candidate split based on the left and right subset obtained through partition for each candidate split; determining a feature in a target candidate split as an optimal feature, determining a threshold in the target candidate split as an optimal splitting value, the optimal feature and the optimal splitting value are ciphertexts; assigning the dataset to two child nodes of the current node based on the optimal feature and the optimal splitting value.

## Claims

### Claim 1

A method for training a tree model, wherein the method is used to train the tree model based on a dataset, and wherein the dataset comprises m pieces of sample data and m sample labels, each sample data comprising n features, and wherein the features and feature values in the dataset are ciphertexts, the method comprising the following steps:
generating, for the dataset, candidate splits based on the ciphertexts, wherein each candidate split is consisting of a feature and a threshold corresponding to the feature;
partitioning, for each candidate split, the dataset into a left subset and a right subset based on the ciphertexts;
calculating a partition coefficient of each candidate split based on the left subset and the right subset obtained through partition for each candidate split;
determining a feature in a target candidate split as an optimal feature, and determining a threshold in the target candidate split as an optimal splitting value, wherein the target candidate split is a candidate split whose partition coefficient satisfies a preset condition, and the optimal feature and the optimal splitting value are ciphertexts;
assigning the dataset to two child nodes of the current node based on the optimal feature and the optimal splitting value; and
performing the above steps on the two child nodes recursively until a stop condition is satisfied.

### Claim 2 (depends on 1)

The method of claim 1, wherein, the step of generating candidate splits based on the ciphertexts comprises the following steps:
sorting, in a preset sorting manner, m feature values corresponding to the j-th feature in the dataset based on the ciphertext to obtain a first array corresponding to the j-th feature, with j taking a value in a range from 0 to n−1; and
selecting in sequence, for the j-th feature, an element from the first array as a threshold corresponding to the j-th feature, and combining the threshold with the j-th feature to obtain a candidate split.

### Claim 3 (depends on 2)

The method of claim 2, wherein, the step of selecting in sequence an element from the first array as a threshold corresponding to the j-th feature comprises:
selecting in sequence an element from the non-maximum elements in the first array as the threshold corresponding to the j-th feature.

### Claim 4 (depends on 2)

The method of claim 2, wherein, after obtaining the first array corresponding to the j-th feature, the method further comprises:
determining a second array corresponding to the first array according to the same sorting manner as used in the m feature values corresponding to the j-th feature, wherein the second array comprises each sample label corresponding to each feature value in the first array;
and the step of partitioning, for each candidate split, the dataset into a left subset and a right subset based on the ciphertexts comprises: based on the feature and threshold in each candidate split, partitioning the m pieces of sample data into the left subset and the right subset and partitioning the second array to the left subset and the right subset.

### Claim 5 (depends on 1)

The method of claim 1, wherein, the step of determining a feature in a target candidate split as an optimal feature, and determining a threshold in the target candidate split as an optimal splitting value comprises the following steps:
constructing a first matrix with n rows and m−1 columns based on the partition coefficient of each candidate split;
constructing a second matrix with n rows and m−1 columns based on a sorting result of m feature values corresponding to each feature in the dataset;
transforming the first matrix into a first vector;
determining a ciphertext index corresponding to an element whose partition coefficient satisfies the preset condition in the first vector; and
determining the optimal feature based on the ciphertext index, and determining the optimal splitting value based on the ciphertext index and the second matrix.

### Claim 6 (depends on 5)

The method of claim 5, wherein, the step of determining the optimal feature based on the ciphertext index comprises:
performing an exact division operation on n by utilizing the ciphertext index to obtain a target index of the optimal feature in the n features; and
determining the optimal feature in the n features according to the target index.

### Claim 7 (depends on 5)

The method of claim 5, wherein, the step of determining the optimal splitting value based on the ciphertext index and the second matrix comprises:
constructing a first sequence, wherein the first sequence is a sequence of integers starting from 0 to (m−1)×n;
comparing the ciphertext index with each element in the first sequence, respectively, to obtain an index vector consisting of the comparison results represented by ciphertexts;
transforming rows 0 to m−2 of the second matrix into a second vector; and
performing an inner product operation on the second vector and the index vector to obtain the optimal splitting value.

### Claim 8 (depends on 1)

The method of claim 1, wherein, the tree model is a CART model, and the step of assigning the dataset to two child nodes of the current node based on the optimal feature and the optimal splitting value comprises the following steps:
determining a column vector corresponding to the optimal feature in the dataset;
comparing the optimal splitting value with each element in the column vector, respectively, to obtain a result matrix consisting of the comparison results represented by ciphertexts;
restoring each element in the result matrix to plaintext to obtain a result matrix represented by plaintexts; and
assigning a sample data corresponding to an element of the first value in the result matrix represented by plaintexts and a sample label corresponding to the sample data to a left node of the current node, and assigning a sample data corresponding to an element of the second value in the result matrix represented by plaintexts and a sample label corresponding to the sample data to a right node of the current node.

### Claim 9 (depends on 8)

The method of claim 8, wherein, the step of determining a column vector corresponding to the optimal feature in the dataset comprises:
constructing a second sequence, wherein the second sequence is a sequence of integers starting from 0 to n−1;
comparing the ciphertext index with each element in the second sequence, respectively, to obtain a third vector consisting of the comparison results represented by ciphertexts;
extending the third vector by m−1 rows to obtain a comparison matrix;
multiplying the comparison matrix with a sample data matrix of m rows and n columns to obtain a third matrix; and
adding together the third matrix by columns to obtain the column vector corresponding to the optimal feature.

### Claim 10 (depends on 1)

The method of claim 1, wherein, the stop condition comprises any one of the following: the depth of a tree model being constructed currently reaches a preset maximum depth, the number of features in the child node is less than a preset minimum number, and all the sample data in the dataset are assigned.

### Claim 11 (depends on 1)

The method of claim 1, wherein, the partition coefficient is a Gini index, the Gini index is calculated based on an impurity function, and the impurity function comprises a Gini function or an Entropy function.

### Claim 12

A device for training a tree model, wherein the device is used to train the tree model based on a dataset, and wherein the dataset comprises m pieces of sample data and m sample labels, each sample data comprising n features, and wherein the features and feature values in the dataset are ciphertexts, wherein, the device comprises a memory and one or more programs, the one or more programs be stored in the memory and be configured as by one or more of processors execute, and the one or more programs include an instruction for performing the following steps:
generating, for the dataset, candidate splits based on the ciphertexts, wherein each candidate split is consisting of a feature and a threshold corresponding to the feature;
partitioning, for each candidate split, the dataset into a left subset and a right subset based on the ciphertexts;
calculating a partition coefficient of each candidate split based on the left subset and the right subset obtained through partition for each candidate split;
determining a feature in a target candidate split as an optimal feature, and determining a threshold in the target candidate split as an optimal splitting value, wherein the target candidate split is a candidate split whose partition coefficient satisfies a preset condition, and the optimal feature and the optimal splitting value are ciphertexts;
assigning the dataset to two child nodes of the current node based on the optimal feature and the optimal splitting value; and
performing the above steps on the two child nodes recursively until a stop condition is satisfied.

### Claim 13 (depends on 12)

The device of claim 12, wherein, the step of generating candidate splits based on the ciphertexts comprises the following steps:
sorting, in a preset sorting manner, m feature values corresponding to the j-th feature in the dataset based on the ciphertext to obtain a first array corresponding to the j-th feature, with j taking a value in a range from 0 to n−1; and
selecting in sequence, for the j-th feature, an element from the first array as a threshold corresponding to the j-th feature, and combining the threshold with the j-th feature to obtain a candidate split.

### Claim 14 (depends on 13)

The device of claim 13, wherein, the one or more programs further include an instruction for performing the following steps:
determining a second array corresponding to the first array according to the same sorting manner as used in the m feature values corresponding to the j-th feature, wherein the second array comprises each sample label corresponding to each feature value in the first array;
and the step of partitioning, for each candidate split, the dataset into a left subset and a right subset based on the ciphertexts comprises: based on the feature and threshold in each candidate split, partitioning the m pieces of sample data into the left subset and the right subset and partitioning the second array to the left subset and the right subset.

### Claim 15 (depends on 12)

The device of claim 12, wherein, the step of determining a feature in a target candidate split as an optimal feature, and determining a threshold in the target candidate split as an optimal splitting value comprises the following steps:
constructing a first matrix with n rows and m−1 columns based on the partition coefficient of each candidate split;
constructing a second matrix with n rows and m−1 columns based on a sorting result of m feature values corresponding to each feature in the dataset;
transforming the first matrix into a first vector;
determining a ciphertext index corresponding to an element whose partition coefficient satisfies the preset condition in the first vector; and
determining the optimal feature based on the ciphertext index, and determining the optimal splitting value based on the ciphertext index and the second matrix.

### Claim 16 (depends on 15)

The device of claim 15, wherein, the step of determining the optimal feature based on the ciphertext index comprises:
performing an exact division operation on n by utilizing the ciphertext index to obtain a target index of the optimal feature in the n features; and
determining the optimal feature in the n features according to the target index.

### Claim 17 (depends on 15)

The device of claim 15, wherein, the step of determining the optimal splitting value based on the ciphertext index and the second matrix comprises:
constructing a first sequence, wherein the first sequence is a sequence of integers starting from 0 to (m−1)×n;
comparing the ciphertext index with each element in the first sequence, respectively, to obtain an index vector consisting of the comparison results represented by ciphertexts;
transforming rows 0 to m−2 of the second matrix into a second vector; and
performing an inner product operation on the second vector and the index vector to obtain the optimal splitting value.

### Claim 18 (depends on 12)

The device of claim 12, wherein, the tree model is a CART model, and the step of assigning the dataset to two child nodes of the current node based on the optimal feature and the optimal splitting value comprises the following steps:
determining a column vector corresponding to the optimal feature in the dataset;
comparing the optimal splitting value with each element in the column vector, respectively, to obtain a result matrix consisting of the comparison results represented by ciphertexts;
restoring each element in the result matrix to plaintext to obtain a result matrix represented by plaintexts; and
assigning a sample data corresponding to an element of the first value in the result matrix represented by plaintexts and a sample label corresponding to the sample data to a left node of the current node, and assigning a sample data corresponding to an element of the second value in the result matrix represented by plaintexts and a sample label corresponding to the sample data to a right node of the current node.

### Claim 19 (depends on 18)

The device of claim 18, wherein, the step of determining a column vector corresponding to the optimal feature in the dataset comprises:
constructing a second sequence, wherein the second sequence is a sequence of integers starting from 0 to n−1;
comparing the ciphertext index with each element in the second sequence, respectively, to obtain a third vector consisting of the comparison results represented by ciphertexts;
extending the third vector by m−1 rows to obtain a comparison matrix;
multiplying the comparison matrix with a sample data matrix of m rows and n columns to obtain a third matrix; and
adding together the third matrix by columns to obtain the column vector corresponding to the optimal feature.

### Claim 20

A computer readable storage medium, an instruction be stored in the storage medium and be configured as by one or more of processors execute for performing a method for training a tree model, wherein, the method is used to train the tree model based on a dataset, and wherein the dataset comprises m pieces of sample data and m sample labels, each sample data comprising n features, and wherein the features and feature values in the dataset are ciphertexts, the method comprising the following steps:
generating, for the dataset, candidate splits based on the ciphertexts, wherein each candidate split is consisting of a feature and a threshold corresponding to the feature;
partitioning, for each candidate split, the dataset into a left subset and a right subset based on the ciphertexts;
calculating a partition coefficient of each candidate split based on the left subset and the right subset obtained through partition for each candidate split;
determining a feature in a target candidate split as an optimal feature, and determining a threshold in the target candidate split as an optimal splitting value, wherein the target candidate split is a candidate split whose partition coefficient satisfies a preset condition, and the optimal feature and the optimal splitting value are ciphertexts;
assigning the dataset to two child nodes of the current node based on the optimal feature and the optimal splitting value; and
performing the above steps on the two child nodes recursively until a stop condition is satisfied.
