Method and system for clustering transactions in a fraud detection system

• US 8,195,664 B2
• Filed: 10/22/2009
• Issued: 06/05/2012
• 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): Mofiz, Apu
• Assistant Examiner(s): Nguyen, Cindy
• Application Number:
  US12/604,220
• Publication Number:
  US 20110099169A1
• Time in Patent Office: 957 Days
• Field of Search: 707/737, 707/741, 707/748
• 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;

(a) determining an intersection set consisting of transactions that are neighbors of both transaction i and transaction };

(b) determining a union set consisting of transactions that are neighbors of either transaction i or transaction j;

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

(d) incrementing index j and repeating steps (a)-(c);

(e) summing the common linkages between transaction i and the transactions of the second set of transactions;

(f) normalizing the sum of the common linkages by a number of the second set of transactions;

(g) incrementing index i and repeating steps (a)-(f);

(h) summing the normalized common linkages between the first set of transactions and the second set of transactions; and

(i) normalizing the sum of the normalized common linkages by a number of the first set of transactions to determine the clustering metric; 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 including the first cluster and the second cluster based on the similarity between clusters.

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 2 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 transactions that are neighbors of both transaction i and transaction/are defined in relation to a similarity between 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, each of the n transactions having a group of neighboring transactions;

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

for transaction j of the n transactions;

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

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

(c) 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;

(d) forming a sum including the common linkage between the new transaction and the j^th transaction of the cluster; and

(e) incrementing j and repeating steps (a)-(d);

dividing the sum of the common linkages by n to provide a clustering metric;

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 transactions.

11. The method of claim 9 wherein the neighbors of transaction j are not 2 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 transactions that are neighbors of both the new transaction and transaction/are defined in relation to a similarity between 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 (a) determine an intersection set consisting of transactions that are neighbors of both transaction i and transaction j;

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

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

instructions that cause the data processor to (d) increment index j and repeat steps (a)-(c);

instructions that cause the data processor to (e) sum the common linkages between transaction i and the transactions of the second set of transactions;

instructions that cause the data processor to (f) normalize the sum of the common linkages by a number of the second set of transactions;

instructions that cause the data processor to (g) increment index i and repeat steps (a)-(f);

instructions that cause the data processor to (h) sum the normalized common linkages between the first set of transactions and the second set of transactions; and

instructions that cause the data processor to (i) normalize the sum of the normalized common linkages by a number of the first set of transactions to determine the selection metric.

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 including the first cluster and the second cluster based on the similarity between clusters.

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.

21. The system of claim 16 wherein the first set of transactions and the second set of transactions comprise Internet log-ins.

22. The system of claim 16 wherein transactions that are neighbors of both transaction i and transaction/are defined in relation to a similarity between transactions.

23. The system of claim 16 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.

24. A system for adding a new transaction to a cluster of n transactions, 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 add the new transaction to the cluster, the plurality of instructions comprising;

instructions that cause the data processor to receive the cluster, each of the n transactions having a group of neighboring transactions;

instructions that cause the data processor to receive the new transaction, wherein the new transaction has one or more neighboring transactions;

instructions that cause the data processor to initialize a counter j for the n transactions;

instructions that cause the data processor to (a) determine an intersection set comprising transactions that are neighbors to both the new transaction and transaction j;

instructions that cause the data processor to (b) determine a union set comprising transactions that are neighbors of either the new transaction or transaction j;

instructions that cause the data processor to (c) compute 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;

instructions that cause the data processor to (d) form a sum including the common linkage between the new transaction and the jth transaction of the cluster; and

instructions that cause the data processor to (e) increment j and repeat steps (a)-(d);

instructions that cause the data processor to divide the sum of the common linkages by n to provide a metric;

instructions that cause the data processor to determine that the metric is greater than a clustering threshold; and

instructions that cause the data processor to add the new transaction to the cluster.

25. The system of claim 24 wherein neighbors of the new transaction and neighbors of transaction j are defined in terms of a similarity between transactions.

26. The system of claim 24 wherein the neighbors of transaction j are not included in the cluster.

27. The system of claim 24 wherein one or more of the neighbors of transaction j are included in the first cluster.

28. The system of claim 24 wherein the new transaction and the cluster of n transactions comprise Internet log-ins.

29. The system of claim 24 wherein transactions that are neighbors of both the new transaction and transaction/are defined in relation to a similarity between transactions.

30. The system of claim 24 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.