Method for automatic community model generation based on uni-parity data

• US 20050203838A1
• Filed: 03/15/2004
• Published: 09/15/2005
• Est. Priority Date: 03/15/2004
• Status: Active Grant

• Current Assignee: United States Air Force
• Original Assignee: United States Air Force
• Inventors: Salerno, John J., Zhang, Zhongfei
• Granted Patent: US 7,756,685 B2
• Time in Patent Office: Days
• US Class Current: 705/39
• CPC Class Codes: G06Q 20/10 specially adapted for electronic funds transfer [EFT] systems; specially adapted for home banking systems
• CPC Class Codes: G06Q 20/4016 involving fraud or risk level assessment in transaction processing
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 40/02 Banking, e.g. interest calculation or account maintenance credit or loans G06Q40/03
• CPC Class Codes: G06Q 40/10 Tax strategies

Abstract

Method for automatic community model generation based on uni-parity data. Correlation analysis is employed to identify links within the community. Method may be particularized for solving specific problems such as determining the activities between individuals within a money laundering ring.

Claims

1. Method for automatic community model generation based on uni-parity data, comprising the steps of:

hypothesizing a subset S of set U, wherein for any pair of items in said subset S there exists a mathematical function C applicable to said pair of items so as to generate a correlation value and correlation relationship between any said pair of items in subset S;

generating said correlation values by applying said function C to each of said pairs of items in said subset S;

graphing G(S,E), wherein E is the edge set of said graph G with computed correlation values as weights; and

mapping said graph g to one of its subgraphs M⊂

G so as to generate a community.

2. Method of claim 1, wherein said correlation relationship and said correlation value is defined by:

∀

p,qε

S⊂

U,C;

S×

S→

[0,1]

and wherein said correlation value is in the range of [0,1].

3. Method for solving a community generation problem, comprising the steps of:

converting documents to digital form and tagging said digitized documents;

parsing said digitized and tagged documents to extract the transaction history vector for each individual;

creating timelines of said transaction vectors so as to form a timeline map;

determining the relevancy of said vectors;

projecting said vectors along a time dimension so as to form a histogram;

translating said vectors into groups of activities by histogram clustering;

determining the local correlation between any pair of clusters in the timeline of two individuals;

computing the global correlations between pairs of individuals;

converting data to a graph as a function of all individuals extracted from said documents and the correlation values between said individuals;

generating models based on a search of all subgraphs with correlation values above a threshold; and

outputting a group model.

4. Method of claim 3, wherein said step of parsing further comprises the step of applying the “

one way nearest neighbor”

principle.

5. Method of claim 4, wherein said “

one way nearest neighbor”

principle further comprises the following steps as applied to a money laundering problem;

for every person'"'"'s name encountered, the first immediate time instance is the first time instance for a series of financial activities;

the second immediate time instance is the second time instance for another series of financial activities, etc.;

for every time instance encountered, all the subsequent financial activities are considered as the series of financial activities between this time instance and the next time instance;

financial activities are identified in terms of money amount;

money amount is neutral in terms of deposit or withdrawal;

each person'"'"'s time sequence of financial activities is updated if new financial activities of this person are encountered in other places of the same document or in other documents; and

the financial activities of each time instance of a person is updated if new financial activities of this time instance of the same person are encountered in other places of the same document or in other documents.

6. Method of claim 3, wherein said step of determining the relevancy of said vectors further comprises a step of focusing on “

clusters”

of vectors in said timeline map and ignoring scattered (i.e., non-clustered) vectors in said timeline map.

7. Method of claim 3, wherein said step of translating said vectors into groups of activities further comprises solving a standard histogram clustering problem;

and

simplifying said standard clustering problem by virtue of all individuals sharing the same said timeline.

8. Method of claim 3, wherein said step of computing correlations between pairs of individuals further comprises computing the global correlation of all local correlations between pairs of individuals.

9. Method of claim 8, further comprising the step of computing local correlations by computing the correlation between two clusters corresponding to a pair of individuals on said histograms.

10. Method of claim 9, wherein said step of computing correlations between two clusters further comprises the step of computing the fuzzified correlation between fx_i(t) and fy_j(t), the financial transaction histogram functions of individual x and y in cluster i and j, respectively.

11. Method of claim 10, wherein said step of computing the fuzzified correlation between fx_i(t) and fy_j(t) further comprises the step of computing the maximum correlation value

$g$

( x i ⁢

y j ) = max t = 0 W i ⁢

∑

t ′

= - W j W j ⁢

 

⁢

gx i ⁡

( t ′

) ⁢

gy j ⁡

( t - t ′

) $\mathrm{where}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{gx}}_i<br><br>\left(t\right)=\underset{t^{\mathrm{\prime <br><br>}}=1}{\overset{W_i}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{fx}}_i<br><br>\left(t^{\mathrm{\prime <br><br>}}\right)<br><br>G_i<br><br>\left(t,t^{\mathrm{\prime <br><br>}}\right)$ $\mathrm{where}<br><br>\text{\hspace{1em}<br><br>}<br><br>G_i<br><br>\left(a,b\right)=\frac{1}{\sqrt{2<br><br>\mathrm{\pi <br><br>}}<br><br>{\mathrm{\sigma <br><br>}}_i}<br><br>e^{-\frac{{\left(a-b\right)}^2}{2<br><br>{\mathrm{\sigma <br><br>}}_i^2}}$ $\mathrm{and}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{where}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\sigma <br><br>}}_i=\frac{2}{W_i<br><br>\left(W_i-1\right)}<br><br>\underset{a=1}{\overset{W_i}{\sum <br><br>}}<br><br>\underset{b=a+1}{\overset{W_i}{\sum <br><br>}}<br><br><br><br>a-b<br><br>$

12. Method of claim 8 wherein said step of computing the global correlation of all local correlations between pairs of individuals further comprises computing the dot product between two vectors as follows:

$C<br><br>\left(x,y\right)=\mathrm{Cy}<br><br>\left(x\right)·<br><br>\mathrm{Cx}<br><br>\left(y\right)=\underset{i=1}{\overset{K}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>C<br><br>\left(x_i,y\right)<br><br>C<br><br>\left(y_i,x\right)$

where the vectors Cy(x) and Cx(y) are defined as

Cy(x)=<

C(x_i,y), i=1, . . . , K>


Cx(y)=<

C(y_i,x), i=1, . . . , K>


where C(x_i,y)=max_j=1^K={g(x_i,y_j)S(i,j)}$S<br><br>\left(i,j\right)=e^{-\frac{{\left(c_i-c_j\right)}^2}{2<br><br>{\mathrm{\sigma <br><br>}}_i^2}}$

and where

{g(x_i,y_j)S(i,j), j=1, . . . , K}

13. Method of claim 3, wherein said step of converting data to a graph further comprises obtaining a complete graph G(V, E), where V is the set of all the individuals extracted from the given collection of the documents, and E is the set of all the correlation values between individuals such that for any correlation C(x, y), there is a corresponding edge in G with the weight C between the two nodes x and y.

14. Method of claim 3, wherein said step of generating models further comprises the step of identifying links as a graph segmentation based on a minimum correlation threshold value.

15. Method of claim 14, wherein said minimum threshold value is selected based upon a user'"'"'s expertise.