Systems and methods for partitioning sets of features for a Bayesian classifier
First Claim
1. A method of building a partition list of feature subsets having probabilistic interdependence among features in the feature subsets for use with a classifier to detect fraudulent user registrations, the method including:
- accessing an input set including an input tuple comprising feature-values assigned to features, wherein the features are of user registration data records and wherein the feature-values of the input tuple are values from a user registration data record;
identifying, from the input tuple, input subtuples comprising unique feature subsets;
accessing a tuple instance count data structure stored in memory that provides counts of tuples in a data set;
computing class entropy scores for the identified input subtuples that have at least a threshold support count of instances in the tuple instance count data structure, wherein the class entropy scores are based on class labels of the input subtuples, and wherein a class label for an input subtuple has a class value that indicates either a fraudulent user registration or a non-fraudulent user registration;
building the partition list including;
ordering at least some of the scored input subtuples by non-decreasing class entropy score; and
traversing the ordered input subtuples, including;
adding a feature subset of a current ordered input subtuple to the partition list, andpruning, from subsequent ordered input subtuples, input subtuples including features that overlap with features of the feature subset corresponding to the current ordered input subtuple;
storing the partition list in a memory, whereby it becomes available to use with the classifier; and
using the partition list with the classifier to classify additional user registration data records as either fraudulent or non-fraudulent.
1 Assignment
0 Petitions
Accused Products
Abstract
The technology disclosed relates to methods for partitioning sets of features for a Bayesian classifier, finding a data partition that makes the classification process faster and more accurate, while discovering and taking into account feature dependence among sets of features in the data set. It relates to computing class entropy scores for a class label across all tuples that share the feature-subset and arranging the tuples in order of non-decreasing entropy scores for the class label, and constructing a data partition that offers the highest improvement in predictive accuracy for the data set. Also disclosed is a method for partitioning a complete set of records of features in a batch computation, computing increasing predictive power; and also relates to starting with singleton partitions, and using an iterative process to construct a data partition that offers the highest improvement in predictive accuracy for the data set.
164 Citations
15 Claims
-
1. A method of building a partition list of feature subsets having probabilistic interdependence among features in the feature subsets for use with a classifier to detect fraudulent user registrations, the method including:
-
accessing an input set including an input tuple comprising feature-values assigned to features, wherein the features are of user registration data records and wherein the feature-values of the input tuple are values from a user registration data record; identifying, from the input tuple, input subtuples comprising unique feature subsets; accessing a tuple instance count data structure stored in memory that provides counts of tuples in a data set; computing class entropy scores for the identified input subtuples that have at least a threshold support count of instances in the tuple instance count data structure, wherein the class entropy scores are based on class labels of the input subtuples, and wherein a class label for an input subtuple has a class value that indicates either a fraudulent user registration or a non-fraudulent user registration; building the partition list including; ordering at least some of the scored input subtuples by non-decreasing class entropy score; and traversing the ordered input subtuples, including; adding a feature subset of a current ordered input subtuple to the partition list, and pruning, from subsequent ordered input subtuples, input subtuples including features that overlap with features of the feature subset corresponding to the current ordered input subtuple; storing the partition list in a memory, whereby it becomes available to use with the classifier; and using the partition list with the classifier to classify additional user registration data records as either fraudulent or non-fraudulent. - View Dependent Claims (2, 3, 4)
-
-
5. A method of building a partition list of feature subsets having probabilistic interdependence among features in the feature subsets for use with a classifier to detect fraudulent user registrations, the method including:
-
accessing a tuple instance count data structure stored in memory, the tuple instance count data structure based on counts of feature-values in an input set of tuples wherein the feature-values of the tuples are values from user registration data records; accessing a class value, wherein the class value indicates either a fraudulent user registration or a non-fraudulent user registration; computing predictive power for the class value of tuple instances using counts in the tuple instance count data structure for supported tuples among tuple instances that have at least a threshold support of count instances; building the partition list including; ordering at least some of the tuple instances for which the predictive power for the class value has been computed by non-increasing predictive power; and traversing the ordered tuple instances, including; adding a feature subset of a current ordered input subtuple to the partition list, and pruning, from subsequent consideration, other input subtuples that include any features in the current ordered input subtuple; storing the partition list in a memory, whereby it becomes available to use with the classifier; and using the partition list with the classifier to classify additional user registration data records as either fraudulent or non-fraudulent. - View Dependent Claims (6, 7)
-
-
8. A method of building a partition list of feature subsets having probabilistic interdependence among features in the feature subsets for use with a classifier to detect fraudulent user registrations, the method including:
-
accessing a tuple instance count data structure stored in memory, the tuple instance count data structure based on counts of feature-values in an input set of tuples wherein the feature-values of the tuples are values from user registration data records; accessing an input set including an input tuple comprising feature-values assigned to features, wherein the features are of the user registration data records and wherein the feature-values of the input tuple are values from a user registration data record; building the partition list including; adding singleton input features present in the input set to the partition list as pending feature subsets; computing reduction in class entropy scores that would result from merging pairs of pending feature subsets using the tuple instance count data structure, limiting consideration of mergers resulting in merged feature subsets to the mergers that have at least a threshold support count of instances in the tuple instance count data structure, wherein the class entropy scores are based on class values that indicate either a fraudulent user registration or a non-fraudulent user registration; selecting a selected pair of pending feature subsets that yields a reduction in class entropy score resulting from the merger, wherein the reduction in class entropy score meets a predetermined class entropy reduction threshold; and merging the selected pair of feature subsets into a merged pending feature subset in the partition list; storing the partition list in the memory, whereby it becomes available to use with the classifier; and using the partition list with the classifier to classify additional user registration data records as either fraudulent or non-fraudulent. - View Dependent Claims (9, 10, 11)
-
-
12. A method of building a partition list of feature subsets having probabilistic interdependence among features in the feature subsets for use with a classifier to detect fraudulent user registrations, the method including:
-
accessing a tuple instance count data structure stored in memory, the tuple instance count data structure based on counts of feature-values in an input set of tuples wherein the feature-values of the tuples are values from user registration data records; accessing a class value, wherein the features are of the user registration data records and wherein the feature-values of the input tuple are values from a user registration data record, wherein the class value indicated either a fraudulent user registration or a non-fraudulent user registration; building the partition list including; adding singleton feature subsets to the partition list as pending feature subsets; computing an increase in class predictive power for the class value that would result from merging pairs of pending feature subsets using the tuple instance count data structure, limiting consideration of mergers to the mergers resulting in merged feature subsets that have at least a threshold support count of instances of the class value for the pairs of pending feature subsets; selecting a selected pair of feature subsets which yields an increase in predictive power for the class value that meets a predetermined predictive power increase threshold; merging the selected pair of feature subsets into a merged single feature subset in the partition list; storing the partition list in the memory, whereby it becomes available to use with the classifier; and using the partition list with the classifier to classify additional user registration data records as either fraudulent or non-fraudulent. - View Dependent Claims (13, 14, 15)
-
Specification