A major topic of ETL is string matching and data matching. While string matching returns a simularity score between two strings, data matching returning a simularity between two two tuples (rows) in a database. For example, we would like to determine whether the tuples (David Smith, 608-245-4367, Madison WI) and (D. M. Smith, 245-4367, Madison WI) refer to the same person.

The problem of data matching arises in many integration situations. In the simplest case, we may be merging multiple databases with identical schemas, but without a unique global ID, and want to decide which rows are duplicates. The problem is complicated when we need to join rows from sources that have different schemas. Data matching may also arise at query time. For example, a query may often imprecisely refer to a particular data item, e.g., a query asking for the phone number of a David Smith who lives in Madison. We need to employ data matching techniques to decide which tuples in the database match the query.

In this project, we will complete a cross-dataset join across two terrorism databases w/ differnent schemas: GTD and GDELT.

Techniques

We cover several classes of solutions to the data matching problem. The first kind employs handcrafted rules, or Rule-based Matching to match tuples. These techniques typically make heavy use of domain-specific knowledge in domains where the complexity of the rules is manageable. The next kind of solution, Learning-based Matching learns the appropriate rules from labeled examples, using supervised learning. The third kind, clustering does not use training data. Instead, it iteratively assigns tuples to clusters, such that all tuples within a single cluster match and those across clusters do not.

import pandas as pd
import time
%pylab inline

Populating the interactive namespace from numpy and matplotlib

Data

Load the two datasets

gtd=pd.read_excel("data/gtd_12to15_0616dist.xlsx")

headers = pd.read_excel("data/GDELT Metadata.xlsx").columns.values
gdelt = pd.read_csv("data/20150108.export.txt", delimiter="\t", names=headers, parse_dates=["Day"])

/usr/local/lib/python2.7/site-packages/IPython/core/interactiveshell.py:2902: DtypeWarning: Columns (8,9,10,11,14,19) have mixed types. Specify dtype option on import or set low_memory=False.
  interactivity=interactivity, compiler=compiler, result=result)

Cleaning

Remove tuples where lat/lng or date is na

gtd = gtd.dropna(subset=['latitude', 'longitude', 'iday'])
gdelt = gdelt.dropna(subset=["ActionGeo_Lat", "ActionGeo_Long", "Day"])

Common Years

The two datasets intersect for years 2014-2015

gtd.iyear.value_counts()

2014    16737
2015    14712
2013    11892
2012     8448
Name: iyear, dtype: int64

The years in GDLET are distributed strangly:

gdelt.Year.value_counts()

2015    155997
2014      2744
2005        44
Name: Year, dtype: int64

set(gtd.iyear).intersection(set(gdelt.Year))

{2014, 2015}

Filter for 2015

#limit query to year 2015 b/c both datasest have full 2015 data
gtdf = gtd[(gtd.iyear==2015) | (gtd.iyear==2014)]
gdeltf=gdelt[(gdelt.Year==2015) | (gdelt.Year==2014)].sample(10000) #sampling a subset of the data for fast testing

Rule-Based Matching

Common Columns

We need to define the mapping between the columns that are in common between the two datasets.

I could only identify 2 columns that map GTD to GDELT. Key is GTD column Value is GDELT column

• iyear/imonth/iday : Day - convert to int seconds and measure euclidian distance
• latitude/longitude : ActionGeo_Lat/ActionGeo_Long - convert to 2D vector and measure euclidian distance

Simularity Metric

We begin by covering approaches that employ handcrafted matching rules. A simple yet popular type of rule computes the similarity score between a pair of tuples $x$ and $y$ as a linearly weighted combination of the individual similarity scores:

where $n$ is the number of common coloumns between tables $X$ and $Y$ (in this case 2), $s_i(x,y) ∈ [0,1]$ is a similarity score between the $i$th attributes of $x$ and $y$, and $\alpha_i ∈ [0, 1]$ is a prespecified weight that indicates the importance of the $i$th attribute to the overall similarity score, such that 􏰈$\Sigma_{i=1}^n \alpha_i = 1$. We declare $x$ and $y$ matched if $sim(x,y) ≥ β$ for a prespecified threshold $β$, and not matched otherwise.

Python Implementation

Lat/Lng

First we take each lat/lng and put them in a 2D vector format so we can take the euclidian disantace.

Date

We take the date data from each touple and put it in native python datetime format. Then we convert each datetime into an integer representing the seconds from the epoch. We can then take the euclidian distance between two datetimes.

Computational Complexity

This routine is a loop in a loop: O(n^2) growth complexity with 5,150,259,916 computations to run if we limit search to 2014-2015.

print (gtdf.shape, gdeltf.shape)
gtdf.shape[0] * gdeltf.shape[0]

((31449, 137), (10000, 58))





314490000

#python implemention of the sim function above w/ 2 matching rules for lat/lng and date
#arguments are pandas series (row) from each database
def sim(target, match):
    sim = 0

    latlng_sim = sim_latlng(target, match)
    sim += (W_LATLNG * latlng_sim)
    
    date_sim = sim_date(target, match)
    sim += (W_DATE * date_sim)
    
    return sim

#define lat/lng sim function
#expect 2 1x2 numpy arrays
def sim_latlng(target, match):
    target_latlng = np.array(target[["latitude", "longitude"]].values)
    
    match_latlng = np.array(match[["ActionGeo_Lat", "ActionGeo_Long"]].values)
    
    sim = euclid_sim(target_latlng, match_latlng)
    
    return sim

#try to match on date
#2  integers represeignn seconds from th epoch
def sim_date(target, match):
    target_date_parts = target[["iyear", "imonth", "iday"]].values
    target_date = datetime.datetime(target_date_parts[0], target_date_parts[1], target_date_parts[2])
    target_seconds = (target_date - EPOCH).total_seconds()
    
    match_date = match["Day"]
    match_seconds = (match_date - EPOCH).total_seconds()
    
    sim = euclid_sim(target_seconds, match_seconds)
    return sim

def euclid_sim(a,b):
    dist = numpy.linalg.norm(a-b)
    prob = 1 / (1 + dist)
    return prob

Results

Here we iterate thought our targets in GTD and then compare against each candidate match in GDELT and return the closest match. A match is defined as the highest score which is computed by nanargmax below. We can also configure our weights here too:

%%time

#weights should sum to 1
W_LATLNG=0.5
W_DATE=0.5
EPOCH = datetime.datetime.utcfromtimestamp(0)

# threshold (beta)
THRESHOLD = 0.4

#choose what tuples of GTD you want to match against
targets = gtdf.sample(500)
matches = {}

for _, target in targets.iterrows(): 
    scores = []
    for _, row in gdeltf.iterrows():
        score = sim(target, row)
        scores.append(score)

    i = np.nanargmax(scores)
    high_score = scores[i]
    #if above thershold, consider match
    if high_score >= THRESHOLD:
        match = gdeltf.iloc[i]
        matches[target.eventid] = (high_score, match.GlobalEventID)
    else:
        matches[target.eventid] = (None, None)
        pass

CPU times: user 1h 26min 10s, sys: 48.1 s, total: 1h 26min 58s
Wall time: 1h 26min 48s

Report

Print out top 200 matches by score

sorted_matches = sorted(matches.items(), key=lambda x: x[1][0], reverse=True)
top200 = sorted_matches[0:200]

gtdids= zip(*top200)[0]; scores = zip(*zip(*top200)[1])[0]; gdeltids=zip(*zip(*top200)[1])[1]
report = pd.DataFrame({"GTD": gtdids, "Score": scores, "GDELT": gdeltids})
report [["GTD", "Score", "GDELT"]].head(200)

Permalink: etl-data-matching

Tags: