Classification for asymmetric error costs
A behavior detection module constructs a random forest classifier (RFC) that takes into account asymmetric misclassification costs between a set of classification labels. The classification label estimate is determined based on classification estimates from the plurality of decision trees. Each parent node of a decision tree is associated with a condition of an attribute that splits a parent node into two child nodes by maximizing an improvement function based on a training database. The improvement function is based on an asymmetric impurity function that biases the decision tree to decrease the error for a label with high misclassification cost over the other, at the cost of increasing the error of the other label with a lower misclassification cost.
1. A method comprising:
accessing an external data entry comprising a set of attributes relating to fraudulent behavior in a web application;
accessing a trained model that is a random forest classifier (RFC) comprising a plurality of decision trees;
applying the trained model to the external data entry to perform an assignment to a classification label estimate for the external data entry by:
generating a plurality of label estimates for the external data entry from each of the plurality of decision trees; and
assigning the classification label estimate based on a function of the plurality of label estimates, wherein the classification label estimate relates to whether a user of the web application is engaging in fraudulent behavior, wherein at least one node of each of the decision trees of the trained model represents a condition determined using an impurity function that comprises an asymmetry biased toward determining that the condition is not related to fraudulent behavior in the web application; and
storing the classification label estimate in association with the external data entry in a data store.
2. The method of claim 1 , wherein the asymmetry of the impurity function biases the assignment of the classification label estimate to the external data entry, such that the classification label estimate is more likely to be assigned to the external data entry compared to when at least one decision tree is constructed using a symmetric impurity function relative to the other classification labels from a set of two or more classification labels.
3. The method of claim 1 , wherein the condition is determined based on:
partitioning a training database based on a plurality of test conditions, wherein each entry in the training database is associated with a classification label, and wherein each test condition is associated with a split of the training database into a plurality of partitions;
generating an improvement function output for each of the plurality of test conditions; and
determining the condition that maximizes the improvement function output.
4. The method of claim 3 ,
wherein the improvement function is given by
Δ i ( s,t )= i ( t )−π( l )· i ( l )·π( r )· i ( r )
where:
i(t) is an output of the impurity function of the training database before partitioning the training database based on a test condition;
π(l) is a proportion of training database entries in a first partition associated with the test condition;
i(l) is an output of the impurity function of the training database entries in the first partition;
π(r) is a proportion of training database entries in a second partition associated with the same test condition; and
i(r) is an output of the impurity function of the training database entries in the second partition.
5. The method of claim 3 ,
wherein the improvement function is based on the asymmetric impurity function:
i
A
(
t
)
=
0.25
·
p
(
0
|
t
)
a
·
p
(
1
|
t
)
b
max
[
0
,
1
]
{
p
(
0
|
t
)
a
·
p
(
1
|
t
)
b
}
+
0.25
·
p
(
1
|
t
)
c
·
p
(
0
|
t
)
d
max
[
0
,
1
]
{
p
(
1
|
t
)
c
·
p
(
0
|
t
)
d
}
in which a, b, c, d are constants with a≠1, b≠1, c≠1, d≠1, p(0|t) is a proportion of entries in a partition with a first classification label, and p(1|t) is a proportion of entries in the partition with a second classification label.
6. The method of claim 1 , wherein the classification label estimate is a label with a highest proportion in the plurality of label estimates.
7. A non-transitory computer readable storage medium comprising instructions configured to be executed by a processor, the instructions when executed by the processor causing the processor to:
access an external data entry comprising a set of attributes relating to fraudulent behavior in a web application;
access a trained model that is a random forest classifier (RFC) comprising a plurality of decision trees;
apply the trained model to the external data entry to perform an assignment to a classification label estimate for the external data entry by:
generating a plurality of label estimates for the external data entry from each of the plurality of decision trees; and
assigning the classification label estimate based on a function of the plurality of label estimates, wherein the classification label estimate relates to whether a user of the web application is engaging in fraudulent behavior, wherein at least one node of each of the decision trees of the trained model represents a condition determined using an impurity function that comprises an asymmetry biased toward determining that the condition is not related to fraudulent behavior in the web application; and
store the classification label estimate in association with the external data entry in a data store.
8. The non-transitory computer readable storage medium of claim 7 , wherein the asymmetry of the impurity function biases the assignment of the classification label estimate to the external data entry, such that the classification label estimate is more likely to be assigned to the external data entry compared to when at least one decision tree is constructed using a symmetric impurity function relative to the other classification labels from a set of two or more classification labels.
9. The non-transitory computer readable storage medium of claim 7 , wherein the condition is determined based on:
partitioning a training database based on a plurality of test conditions, wherein each entry in the training database is associated with a classification label, and wherein each test condition is associated with a split of the training database into a plurality of partitions;
generating an improvement function output for each of the plurality of test conditions; and
determining the condition that maximizes the improvement function output.
10. The non-transitory computer readable storage medium of claim 9 , wherein the improvement function is given by
Δ i ( s,t )= i ( t )−π( l )· i ( l )·π( r )· i ( r )
where:
i(t) is an output of the impurity function of the training database before partitioning the training database based on a test condition;
π(l) is a proportion of training database entries in a first partition associated with the test condition;
i(l) is an output of the impurity function of the training database entries in the first partition;
π(r) is a proportion of training database entries in a second partition associated with the same test condition; and
i(r) is an output of the impurity function of the training database entries in the second partition.
11. The non-transitory computer readable storage medium of claim 9 , wherein the improvement function is based on the asymmetric impurity function:
i
A
(
t
)
=
0.25
·
p
(
0
|
t
)
a
·
p
(
1
|
t
)
b
max
[
0
,
1
]
{
p
(
0
|
t
)
a
·
p
(
1
|
t
)
b
}
+
0.25
·
p
(
1
|
t
)
c
·
p
(
0
|
t
)
d
max
[
0
,
1
]
{
p
(
1
|
t
)
c
·
p
(
0
|
t
)
d
}
in which a, b, c, d are constants with a≠1, b≠1, c≠1, d≠1, p(0|t) is a proportion of entries in a partition with a first classification label, and p(1|t) is a proportion of entries in the partition with a second classification label.
12. The non-transitory computer readable storage medium of claim 7 , wherein the classification label estimate is a label with a highest proportion in the plurality of label estimates.
13. A system comprising:
a processor configured to execute instructions;
a computer-readable medium containing instructions for execution on the processor, the instructions causing the processor to perform steps of:
accessing an external data entry comprising a set of attributes relating to fraudulent behavior in a web application;
accessing a trained model that is a random forest classifier (RFC) comprising a plurality of decision trees;
applying the trained model to the external data entry to perform an assignment to a classification label estimate for the external data entry by:
generating a plurality of label estimates for the external data entry from each of the plurality of decision trees; and
assigning the classification label estimate based on a function of the plurality of label estimates, wherein the classification label estimate relates to whether a user of the web application is engaging in fraudulent behavior, wherein at least one node of each of the decision trees of the trained model represents a condition determined using an impurity function that comprises an asymmetry biased toward determining that the condition is not related to fraudulent behavior in the web application; and
storing the classification label estimate in association with the external data entry in a data store.
14. The system of claim 13 , wherein the asymmetry of the impurity function biases the assignment of the classification label estimate to the external data entry, such that the classification label estimate is more likely to be assigned to the external data entry compared to when at least one decision tree is constructed using a symmetric impurity function relative to the other classification labels from a set of two or more classification labels.
15. The system of claim 13 , wherein the condition is determined based on:
partitioning a training database based on a plurality of test conditions, wherein each entry in the training database is associated with a classification label, and wherein each test condition is associated with a split of the training database into a plurality of partitions;
generating an improvement function output for each of the plurality of test conditions; and
determining the condition that maximizes the improvement function output.
16. The system of claim 15 ,
wherein the improvement function is based on the asymmetric impurity function:
i
A
(
t
)
=
0.25
·
p
(
0
|
t
)
a
·
p
(
1
|
t
)
b
max
[
0
,
1
]
{
p
(
0
|
t
)
a
·
p
(
1
|
t
)
b
}
+
0.25
·
p
(
1
|
t
)
c
·
p
(
0
|
t
)
d
max
[
0
,
1
]
{
p
(
1
|
t
)
c
·
p
(
0
|
t
)
d
}
in which a, b, c, d are constants with a≠1, b≠1, c≠1, d≠1, p(0|t) is a proportion of entries in a partition with a first classification label, and p(1|t) is a proportion of entries in the partition with a second classification label.
17. The system of claim 13 , wherein the classification label estimate is a label with a highest proportion in the plurality of label estimates.