Methods and apparatus for implementing an ensemble merchant prediction system

• US 8,738,486 B2
• Filed: 12/31/2007
• Issued: 05/27/2014
• Est. Priority Date: 12/31/2007
• Status: Active Grant

• Current Assignee: Mastercard International Incorporated (MasterCard Incorporated)
• Original Assignee: Mastercard International Incorporated (MasterCard Incorporated)
• Inventors: McGeehan, Thomas
• Primary Examiner(s): Colbert, Ella
• Application Number:
  US11/967,490
• Publication Number:
  US 20090171759A1
• Time in Patent Office: 2,339 Days
• Field of Search: 705/35, 705/38, 705/39, 707/600
• US Class Current: 705/35
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions
• CPC Class Codes: G06Q 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes

Abstract

A computer-based method for discovering patterns in financial transaction card transaction data for the purpose of determining group membership of a merchant within the transaction data is described. The data relates to merchants that accept the financial transaction card for payment. The method includes receiving transaction data from at least one database, predicting a membership of a merchant in a group using at least one prediction algorithm and the retrieved transaction data, the algorithm generating meta-data describing the predictions, inputting the at least one predicted group membership and the meta-data into a data mining application, and assigning a confidence value to each predicted group membership by the data mining application, utilizing the predicted group memberships and the meta-data.

Claims

1. A computer-based method for discovering patterns in financial transaction card transaction data for determining group memberships of a merchant within the transaction data, said method comprising:

storing transaction data within at least one database, wherein the transaction data includes data relating to merchants accepting transaction cards for payment;

retrieving the transaction data by a first computer coupled to the at least one database;

using at least one prediction algorithm and the retrieved transaction data to predict a plurality of group memberships of a merchant within one or more groupings of merchants wherein the algorithm is processed by the first computer;

generating meta-data describing each prediction outputted by the at least one prediction algorithm, wherein the meta-data is generated by the at least one algorithm;

inputting the plurality of predicted group memberships for the merchant and the meta-data describing each prediction into a data mining application executed on a second computer;

assigning, by the second computer, a confidence score to each predicted group membership by the data mining application based at least in part on the predicted group memberships and the meta-data, wherein the confidence score represents a likelihood the merchant is actually associated with the corresponding predicted group membership; and

outputting, by the second computer, the group membership prediction with the highest confidence score as a final membership prediction for the merchant.

2. A computer-based method according to claim 1 wherein using at least one prediction algorithm and the retrieved transaction data to predict a plurality of group memberships comprises identifying, from the at least one database, a set of database fields that are meaningful in the context of deriving group membership.

3. A computer-based method according to claim 2 further comprising:

searching merchant location data within the at least one database for a number of merchant locations that are within a given distance from a given location, wherein location and distance are based on a similarity as measured by a cross-attribute, weighted, term frequency/inverse document frequency (TF/IDF) calculation for field values and field tokenized values within the database;

searching the merchant location data for those merchant locations that are within a given distance from a given location for similarities to determine at least one of new merchant locations and changed merchant locations;

calculating mode values through classification of the merchant locations that occur within the given distance from the given location; and

returning the most frequently occurring mode value as the group membership prediction.

4. A computer-based method according to claim 1 wherein using at least one prediction algorithm and the retrieved transaction data to predict a plurality of group memberships comprises:

tokenizing at least one field in the database;

calculating an inverse document frequency for all tokenized field values within the database;

computing a sparse matrix of weight metrics for each database field value and each tokenized database field value; and

generating a prediction by joining a given database field location to every other database field location based on one or more of field type and field value utilizing the sparse matrix.

5. A computer-based method according to claim 4 wherein the sparse matrix includes a merchant category code, an Interbank card association (ICA) code, a business region, a merchant name, a merchant phone number, an acquiring merchant identifier, a tier merchant identifier, a merchant legal name, and a federal tax identifier.

6. A computer-based method according to claim 1 wherein using at least one prediction algorithm and the retrieved transaction data to predict a plurality of group memberships comprises computing a relevance for a single merchant location relative to a set of merchant locations, wherein location is based on a calculated similarity, the similarity based on field values and field tokenized values within the database.

7. A computer-based method according to claim 6 wherein computing a relevance for a single merchant location relative to a set of merchant locations comprises:

extracting relevant features from a plurality of merchant locations grouped into sets to generate a document for each set;

collecting the generated documents within a dictionary;

forming a sparse matrix utilizing the dictionary whereby the relevance of each field value and tokenized field value in the generated documents is computed, utilizing the extracted relevant features based on at least one of a term frequency and an inverse document frequency; and

joining a matrix of merchant location level weights to a matrix of merchant group weights based on field types and field values within the sparse matrix.

8. A computer-based method according to claim 7 further comprising:

utilizing a sum of the merchant location level weights and the merchant group weights within a relevance engine to determine the relevance of each merchant location to each set of merchant locations; and

outputting the set of merchant locations with the highest relevance as a prediction.

9. A computer-based method according to claim 7 wherein forming the sparse matrix includes a merchant category code, an Interbank card association (ICA) code, a business region, a merchant name, a merchant phone number, an acquiring merchant identifier, a tier merchant identifier, a merchant legal name, and a federal tax identifier.

10. A computer-based method according to claim 1 wherein using at least one prediction algorithm and the retrieved transaction data to predict a plurality of group memberships comprises utilizing third party provided data that has been matched to a database of financial transaction card transactions by merchant location, where location is based on a calculated similarity, the similarity based on field values and field tokenized values within the database.

11. A computer-based method according to claim 1 wherein using at least one prediction algorithm and the retrieved transaction data to predict a plurality of group memberships comprises:

using third party location data that has been matched to a database of financial transaction card brand merchant location data, wherein location is based on a calculated similarity, the similarity based on field values and field tokenized values within the database, the third party location data including an assigned chain identifier; and

linking the chain identifiers to the merchant locations associated with the financial transaction card brand.

12. A computer-based method according to claim 1 wherein:

using at least one prediction algorithm and the retrieved transaction data to predict a plurality of group memberships comprises;

using an approximate merchant location matching engine to join a set of third party merchant records to a set of merchant records in the at least one database; and

computing a predicted group for a given location as the merchant group that corresponds to the joined set for the given location; and

assigning a confidence score to each predicted group membership comprises assigning a match confidence score that is assigned by the approximate merchant location matching engine.

13. A computer-based method according to claim 1 wherein using at least one prediction algorithm and the retrieved transaction data to predict a plurality of group memberships comprises predicting, utilizing a numerical signature algorithm and an observed tendency for merchants belonging to the same group to diverge from a distribution in a relatively consistent manner, a group of locations that have a similar numeric distribution as compared to each merchant location, wherein location is based on a calculated similarity, the similarity based on field values and field tokenized values within the database.

14. A computer-based method according to claim 1 wherein using at least one prediction algorithm and the retrieved transaction data to predict a plurality of group memberships comprises:

randomly sampling merchant data from a grouping of merchant data in the at least one database;

computing a distribution of the numerals 1, 2, 3, 4, 5, 6, 7, 8, and 9 occurring in the first position of the transaction amount; and

summarizing a transaction volume by merchant grouping.

15. A computer-based method according to claim 14 further comprising:

computing an angle distance between the computed distribution of numerals and a distribution of numerals identified by Benford'"'"'s Law; and

outputting a merchant grouping with an angle distance closest to the computed angle distance as the predicted merchant group for the sampled merchant.

16. A computer-based method according to claim 1 wherein using at least one prediction algorithm and the retrieved transaction data to predict a plurality of group memberships using at least one prediction algorithm and the retrieved transaction data comprises utilizing multiple prediction algorithms to provide multiple membership predictions for a merchant.

17. A computer-based method according to claim 16 wherein assigning a confidence score to each predicted group membership comprises:

assigning a confidence score to each of the multiple membership predictions for a merchant; and

providing the membership prediction with the highest confidence score as a final membership prediction for the merchant.

18. A computer-based method according to claim 1 wherein the group memberships include memberships based on one or more of legal ownership, brand, and chain.

19. A computer system for discovering patterns in financial transaction card transaction data for the purpose of determining, for individual merchants, a membership of the merchant within one or more merchant groupings utilizing the transaction data, said computer comprising:

a processing device; and

a memory, said processing device operable to execute instructions stored in said memory causing said computer to;

store transaction data within said memory, wherein the transaction data includes data relating to merchants accepting transaction cards for payment;

run a plurality of prediction algorithms stored within said memory with the transaction data, each prediction algorithm predicting a membership for a merchant within the one or more merchant groupings based on the transaction data, at least one of the prediction algorithms generating meta-data describing the predictions;

input the meta-data and predicted group memberships into a data mining application;

assign a confidence score to each predicted group membership for the merchant based on a result provided by the data mining application, wherein the confidence score represents a likelihood the merchant is actually associated with the corresponding predicted group membership; and

output the group membership prediction with the highest confidence score as a final membership prediction for the merchant.

20. A computer system according to claim 19 wherein at least one of the algorithms stored within said memory is operable to identify, within the transaction data, a set of database fields that are meaningful for deriving group membership.

21. A computer system according to claim 20 wherein at least one of the algorithms stored within said memory is operable to:

search merchant location data within the transaction data for a number of merchant locations within a given distance from a given location;

calculate mode values through classification of the merchant locations that occur within the given distance from the given location; and

return the most frequently occurring mode value as the group membership prediction, wherein location and distance are based on a calculated similarity, the similarity based on field values and field tokenized values within the database.

22. A computer system according to claim 19 wherein to run a plurality of prediction algorithms with the transaction data, at least one of the algorithms stored within said memory is operable to:

tokenize at least one field in the database;

calculate an inverse document frequency for all the tokenized database field values within the database;

generate a sparse matrix of weight metrics for each database field value and each tokenized database field value; and

compute a prediction by joining a given database field location to every other database field location based on one or more of field type and field value in the sparse matrix.

23. A computer system according to claim 19 wherein to run a plurality of prediction algorithms with the transaction data, said computer system is programmed to compute a relevance for a single merchant location relative to a set of merchant locations within the transaction data, wherein location is based on a calculated similarity, the similarity based on field values and field tokenized values within the database.

24. A computer system according to claim 23 wherein to compute a relevance for a single merchant location relative to a set of merchant locations within the transaction data, said computer system is programmed to:

extract relevant features from a plurality of merchant locations grouped into sets to generate a document for each set;

collect the generated documents within a dictionary;

form a sparse matrix utilizing the dictionary whereby the relevance of each field value and tokenized field value in the generated documents is computed, utilizing the extracted relevant features based on at least one of a term frequency and an inverse document frequency; and

join a matrix of merchant location level weights to a matrix of merchant group weights based on field types and field values within the sparse matrix.

25. A computer system according to claim 24 wherein to determine a value for each set of merchant location data, said computer system is programmed to utilize a sum of the weights within a relevance engine to determine the relevance of each location to a merchant group.

26. A computer system according to claim 24 wherein said computer system is programmed to

utilize a sum of the merchant location level weights and the merchant group weights within a relevance engine to determine the relevance of each merchant location to each set of merchant locations;

and

output the set of merchant locations with the highest relevance as a prediction.

27. A computer system according to claim 19 wherein to run a plurality of prediction algorithms with the transaction data, said computer system is programmed to utilize third party provided data that has been matched to a database of financial transaction card transactions by merchant location, where location is based on a calculated similarity, the similarity based on field values and field tokenized values within the database.

28. A computer system according to claim 19, where location is based on a calculated similarity, the similarity based on field values and field tokenized values within the database, wherein to run a plurality of prediction algorithms with the transaction data, said computer system is programmed to:

use third party location data that has been matched to a database of financial transaction card brand merchant location data, the third party location data including an assigned chain identifier; and

link the chain identifiers to the merchant location data associated with the financial transaction card brand.

29. A computer system according to claim 19, where location is based on a calculated similarity, the similarity based on field values and field tokenized values within the database, wherein to run a plurality of prediction algorithms with the transaction data, said computer system is programmed to:

use an approximate merchant location matching engine to join a set of third party merchant location records to a set of merchant location records; and

compute a predicted group for a given location as the merchant group that corresponds to the joined set for the given location.

30. A computer system according to claim 29 further programmed to assign a match confidence score as assigned by the approximate merchant location matching engine.

31. A computer system according to claim 19 wherein to run a plurality of prediction algorithms with the transaction data, said computer system is programmed to:

randomly sample merchant data from a grouping of merchant data;

compute a distribution of the numerals 1, 2, 3, 4, 5, 6, 7, 8, and 9 occurring in the first position of a transaction amount within the transaction data; and

summarize a transaction volume by merchant grouping.

32. A computer system according to claim 31 further programmed to:

compute an angle distance between the computed distribution of numerals and a distribution of numerals identified by Benford'"'"'s Law; and

output a merchant grouping with an angle distance closest to the computed angle distance as the predicted merchant group for the sampled merchant.