Granted Patent B1

US 12,406,209 · App. 16/457,884 · Granted Sep 2, 2025

Inventors: Samir Shah (San Francisco, CA); Bei Zhang (San Jose, CA); Kenton Miller (Sunnyvale, CA)

Assignee: Shape Security, Inc.

G06N20/20G06N5/01G06N20/00

Abstract

Claims (70)

1. A computer-implemented method for training a decision tree using a database system, the decision tree comprising a plurality of decision nodes, the computer-implemented method implemented by a network traffic management system comprising one or more network traffic apparatuses, one or more computing devices, or server devices, the method comprising:

storing in a database input data for training the decision tree, the input data comprising a plurality of feature values corresponding to a plurality of features, wherein the input data is stored in a columnar format, wherein rows of columnar format correspond to input sets of the input data in the database and columns correspond to at least one of the plurality of features, wherein the decision tree is trained using a set of training data comprising the input data, and wherein the set of training data does not comprise output data; and

generating a particular node of the plurality of decision nodes by:

selecting a subset of the plurality of features and a subset of the input data;

using one or more queries to the database system, for each feature of the subset of the plurality of features, calculating a variance value associated with the feature based on the subset of the input data, wherein the calculated variance value is based on aggregate label output values of partitioned subsets of the input data that are generated based on identified patterns relating to legitimacy of requests to one of the server devices, wherein the partitioned subsets of the input data are based on one or more conditions, wherein the aggregate label output values provide status information on conformity of the partitioned subsets to the identified patterns relating to legitimacy of the requests;

identifying a particular feature of the subset of the plurality of features associated with a highest variance value; and

associating the particular node with the particular feature, wherein the particular node causes the decision tree to branch based on the particular feature associated with the highest variance value.

2. The method of claim 1 further comprising generating a random forest comprising a plurality of decision trees by generating, for each decision tree of the plurality of decision trees, a respective plurality of decision nodes.

3. The method of claim 2 further comprising generating a second query to the database system corresponding to the random forest, wherein the second query, when executed using the database system, applies each decision tree of the plurality of decision trees to a set of input data.

4. The method of claim 1 wherein the selecting the subset of the plurality of features comprises randomly selecting the subset of the plurality of features.

5. The method of claim 1 wherein calculating the variance value associated with the feature comprises:

identifying the one or more conditions for partitioning the subset of the input data;

partitioning the subset of the input data based on the one or more conditions;

applying an aggregate label to each partition of the subset of the input data;

calculating a respective variance value for each condition of the one or more conditions based on applying the aggregate label to each partition of the subset of the input data; and

selecting a highest respective variance value as the variance value associated with the feature.

6. A system for training a decision tree using a database system, the decision tree comprising a plurality of decision nodes, the system comprising:

one or more processors; and

non-transitory computer-readable media storing instructions which, when executed by the one or more processors, cause:

storing in a database input data for training the decision tree, the input data comprising a plurality of feature values corresponding to a plurality of features, wherein the input data is stored in a columnar format, wherein rows of columnar format correspond to input sets of the input data in the database and columns correspond to at least one of the plurality of features, wherein the decision tree is trained using a set of training data comprising the input data, and wherein the set of training data does not comprise output data; and

generating a particular node of the plurality of decision nodes by:

selecting a subset of the plurality of features and a subset of the input data;

using one or more queries to the database system, for each feature of the subset of the plurality of features, calculating a variance value associated with the feature based on the subset of the input data, wherein the calculated variance value is based on aggregate label output values of partitioned subsets of the input data that are generated based on identified patterns relating to legitimacy of requests to one of the server devices, wherein the partitioned subsets of the input data are based on one or more conditions, wherein the aggregate label output values provide status information on conformity of the partitioned subsets to the identified patterns relating to legitimacy of the requests;

identifying a particular feature of the subset of the plurality of features associated with a highest variance value; and

associating the particular node with the particular feature, wherein the particular node causes the decision tree to branch based on the particular feature associated with the highest variance value.

7. The system of claim 6 wherein the instructions, when executed by the one or more processors, further cause generating a random forest comprising a plurality of decision trees by generating, for each decision tree of the plurality of decision trees, a respective plurality of decision nodes.

8. The system of claim 7 wherein the instructions, when executed by the one or more processors, further cause generating a second query to the database system corresponding to the random forest, wherein the second query, when executed using the database system, applies each decision tree of the plurality of decision trees to a set of input data.

9. The system of claim 6 wherein the subset of the plurality of features comprises randomly selecting the subset of the plurality of features.

10. The system of claim 6 wherein calculating the variance value associated with the feature comprises:

identifying the one or more conditions for partitioning the subset of the input data;

partitioning the subset of the input data based on the one or more conditions;

applying an aggregate label to each partition of the subset of the input data;

calculating a respective variance value for each condition of the one or more conditions based on applying the aggregate label to each partition of the subset of the input data; and

selecting a highest respective variance value as the variance value associated with the feature.

11. A non-transitory computer readable medium having stored thereon instructions for training a decision tree using a database system, the decision tree comprising a plurality of decision nodes, the non-transitory computer readable medium comprising executable code which when executed by one or more processors, causes the one or more processors to:

store in a database input data for training the decision tree, the input data comprising a plurality of feature values corresponding to a plurality of features, wherein the input data is stored in a columnar format, wherein rows of columnar format correspond to input sets of the input data in the database and columns correspond to at least one of the plurality of features, wherein the decision tree is trained using a set of training data comprising the input data, and wherein the set of training data does not comprise output data; and

generate a particular node of the plurality of decision nodes by:

selecting a subset of the plurality of features and a subset of the input data;

using one or more queries to the database system, for each feature of the subset of the plurality of features, calculating a variance value associated with the feature based on the subset of the input data, wherein the calculated variance value is based on aggregate label output values of partitioned subsets of the input data that are generated based on identified patterns relating to legitimacy of requests to one of the server devices, wherein the partitioned subsets of the input data are based on one or more conditions, wherein the aggregate label output values provide status information on conformity of the partitioned subsets to the identified patterns relating to legitimacy of the requests;

identifying a particular feature of the subset of the plurality of features associated with a highest variance value; and

associating the particular node with the particular feature, wherein the particular node causes the decision tree to branch based on the particular feature associated with the highest variance value.

12. The medium as set forth in claim 11 , wherein the executable code which when executed by the one or more processors, further causes the processors to:

generate a random forest comprising a plurality of decision trees by generating, for each decision tree of the plurality of decision trees, a respective plurality of decision nodes.

13. The medium as set forth in claim 12 , wherein the executable code which when executed by the one or more processors, further causes the processors to:

generate a second query to the database system corresponding to the random forest, wherein the second query, when executed using the database system, applies each decision tree of the plurality of decision trees to a set of input data.

14. The medium as set forth in claim 11 , wherein the selecting the subset of the plurality of features comprises randomly selecting the subset of the plurality of features.

15. The medium as set forth in claim 11 , wherein calculating the variance value associated with the feature comprises:

identifying the one or more conditions for partitioning the subset of the input data;

partitioning the subset of the input data based on the one or more conditions;

applying an aggregate label to each partition of the subset of the input data;

calculating a respective variance value for each condition of the one or more conditions based on applying the aggregate label to each partition of the subset of the input data; and

selecting a highest respective variance value as the variance value associated with the feature.

16. A network traffic manager apparatus for training a decision tree using a database system, comprising memory comprising programmed instructions stored in the memory and one or more processors configured to be capable of executing the programmed instructions stored in the memory to:

store in a database input data for training a decision tree, the decision tree comprising a plurality of decision nodes, the input data comprising a plurality of feature values corresponding to a plurality of features, wherein the input data is stored in a columnar format, wherein rows of columnar format correspond to input sets of the input data in the database and columns correspond to at least one of the plurality of features, wherein the decision tree is trained using a set of training data comprising the input data, and wherein the set of training data does not comprise output data; and

generate a particular node of the plurality of decision nodes by:

selecting a subset of the plurality of features and a subset of the input data;

using one or more queries to the database system, for each feature of the subset of the plurality of features, calculating a variance value associated with the feature based on the subset of the input data, wherein the calculated variance value is based on aggregate label output values of partitioned subsets of the input data that are generated based on identified patterns relating to legitimacy of requests to one of the server devices, wherein the partitioned subsets of the input data are based on one or more conditions, wherein the aggregate label output values provide status information on conformity of the partitioned subsets to the identified patterns relating to legitimacy of the requests;

identifying a particular feature of the subset of the plurality of features associated with a highest variance value; and

associating the particular node with the particular feature, wherein the particular node causes the decision tree to branch based on the particular feature associated with the highest variance value.

17. The network traffic manager apparatus as set forth in claim 16 , wherein the one or more processors are further configured to be capable of executing the programmed instructions stored in the memory to:

generate a random forest comprising a plurality of decision trees by generating, for each decision tree of the plurality of decision trees, a respective plurality of decision nodes.

18. The network traffic manager apparatus as set forth in claim 17 , wherein the one or more processors are further configured to be capable of executing the programmed instructions stored in the memory to:

generate a second query to the database system corresponding to the random forest, wherein the second query, when executed using the database system, applies each decision tree of the plurality of decision trees to a set of input data.

19. The network traffic manager apparatus as set forth in claim 16 , wherein the selecting the subset of the plurality of features comprises randomly selecting the subset of the plurality of features.

20. The network traffic manager apparatus as set forth in claim 16 , wherein calculating the variance value associated with the feature comprises:

identifying the one or more conditions for partitioning the subset of the input data;

partitioning the subset of the input data based on the one or more conditions;

applying an aggregate label to each partition of the subset of the input data;

calculating a respective variance value for each condition of the one or more conditions based on applying the aggregate label to each partition of the subset of the input data; and

selecting a highest respective variance value as the variance value associated with the feature.

Assignments (1)

References Cited (52)

Cited By (1)

US 12,526,289