Method and system for clustering transactions in a fraud detection system

• US 8,566,322 B1
• Filed: 04/25/2012
• Issued: 10/22/2013
• Est. Priority Date: 10/22/2009
• Status: Active Grant

• Current Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Lanxner, Eyal S., Raz, Shay, Gross, Oren
• Primary Examiner(s): Leroux, Etienne
• Assistant Examiner(s): Nguyen, Cindy
• Application Number:
  US13/455,334
• Time in Patent Office: 545 Days
• Field of Search: 707/737, 707/741, 707/749
• US Class Current: 707/737
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection

Abstract

A method of determining a clustering metric includes receiving a first set of transactions and a second set of transactions. For transaction i of the first set and transaction j of the second set, the method includes (a) determining an intersection set, (b) determining a union set; (c) computing a common linkage between transaction i and transaction j equal to the intersection set divided by the union set, and (d) incrementing index j and repeating steps (a)-(c). The method also includes (e) summing the common linkages between transaction i and the transactions of the second set, (f) normalizing the sum of the common linkages by a number of the second set, and (g) incrementing index i and repeating steps (a)-(f). The method further includes (h) summing the normalized common linkages and (i) normalizing the sum of the normalized common linkages by a number of the first set.

Claims

1. A computer-implemented method of determining a clustering metric, the method comprising:

receiving, by a processor, a first set of transactions;

receiving a second set of transactions; and

for transaction i of the first set of transactions and transaction j of the second set of transactions;

determining an intersection set comprising transactions that are neighbors of transaction i and transaction j;

determining a union set comprising transactions that are neighbors of either transaction i or transaction j;

computing a common linkage between transaction i and transaction j equal to the intersection set divided by the union set;

determining a clustering metric based on the common linkage; and

storing the clustering metric in memory.

2. The method of claim 1 wherein the first set of transactions are included in a first cluster and the second set of transactions are included in a second cluster.

3. The method of claim 2 further comprising forming a third cluster comprising the first cluster and the second cluster based on a similarity between the first cluster and the second cluster.

4. The method of claim 2 wherein the neighbors of transaction i and the neighbors of transaction j are not included in the first cluster or the second cluster.

5. The method of claim 2 wherein one or more of the neighbors of transaction i and one or more of the neighbors of transaction j are included in at least one of the first cluster or the second cluster.

6. The method of claim 1 wherein the first set of transactions and the second set of transactions comprise Internet log-ins.

7. The method of claim 1 wherein the transactions that are neighbors of transaction i and transaction j are defined in relation to a similarity between the transactions.

8. The method of claim 1 wherein a number of transactions in the union set is equal to neighbors of transaction i plus neighbors of transaction j less the intersection set.

9. A computer-implemented method of adding a new transaction to a cluster of n transactions, the method comprising:

receiving, by a processor, the cluster, wherein each of the n transactions comprises a group of neighboring transactions;

receiving the new transaction, wherein the new transaction comprises one or more neighboring transactions;

for transaction j of the n transactions;

determining an intersection set comprising transactions that are neighbors to the new transaction and transaction j;

determining a union set comprising transactions that are neighbors of either the new transaction or transaction j;

computing a common linkage between the new transaction and transaction j, wherein the common linkage is equal to the intersection set divided by the union set;

determining a clustering metric based on the common linkages;

determining that the clustering metric is greater than a clustering threshold;

adding the new transaction to the cluster; and

storing the cluster with the new transaction in memory.

10. The method of claim 9 wherein neighbors of the new transaction and neighbors of transaction j are defined in terms of a similarity between the new transaction and transaction j.

11. The method of claim 9 wherein the neighbors of transaction j are not included in the cluster.

12. The method of claim 9 wherein one or more of the neighbors of transaction j are included in the first cluster.

13. The method of claim 9 wherein the new transaction and the cluster of n transactions comprise Internet log-ins.

14. The method of claim 9 wherein the transactions that are neighbors of the new transaction and transaction j are defined in relation to a similarity between the transactions.

15. The method of claim 9 wherein a number of transactions in the union set is equal to neighbors of the new transaction plus neighbors of transaction j less the intersection set.

16. A system for determining a clustering metric, the system comprising:

a data processor;

a communications module coupled to the data processor;

an input/output interface coupled to the data processor; and

a non-transitory computer readable storage medium coupled to the data processor and storing a plurality of instructions for controlling the data processor to determine the clustering metric, the plurality of instructions comprising;

instructions that cause the data processor to receive a first set of transactions;

instructions that cause the data processor to receive a second set of transactions;

instructions that cause the data processor to initialize a counter i for the first set of transactions and a counter j for the second set of transactions;

instructions that cause the data processor to determine an intersection set comprising transactions that are neighbors of both transaction i and transaction j;

instructions that cause the data processor to determine a union set comprises transactions that are neighbors of either transaction i or transaction j;

instructions that cause the data processor to compute a common linkage between transaction i and transaction j equal to the intersection set divided by the union set; and

instructions that cause the data processor to determine a selection metric based on the common linkage.

17. The system of claim 16 wherein the first set of transactions are included in a first cluster and the second set of transactions are included in a second cluster.

18. The system of claim 17 further comprising forming a third cluster comprising the first cluster and the second cluster based on a similarity between the first cluster and the second cluster.

19. The system of claim 17 wherein the neighbors of transaction i and the neighbors of transaction j are not included in the first cluster or the second cluster.

20. The system of claim 17 wherein one or more of the neighbors of transaction i and one or more of the neighbors of transaction j are included in at least one of the first cluster or the second cluster.