open-city/dedupe — pull request #147 by nikitsaraf (2013-08-02 14:39:41+00:00)
Title: Data matching

The William W. Cohen does wonderful task to present the problem and solution for the task of Constraint Data Matching. The aim of this report is to discuss the implementation details for the constraint Data Matching problem.

Cohen’s paper outlines the following changes to the existing canopy clustering algorithm :-

For the two Datasets A and B

A]. Let PossibleCenters = A;
B] Let Canopy(a) = {(a,b) : b B and approxDist(a,b) < Tloose};
C]. let Ttight = 0 (i.e only remove a from the set of Possible Centers).

Implementing the following changes, will accommodate the above mentioned changes:-

## Read in data from multiple sources

First of all, the data_d structure which is passed to the blockingFunction needs to be modified so as to identify each of the records present in data_d, from which dataset it belongs.

```python
def readData(filenames):
"""
Read in our data from a CSV file and create a dictionary of records,
where the key is a unique record ID and each value is a
[frozendict](http://code.activestate.com/recipes/414283-frozen-dictionaries/)
(hashable dictionary) of the row fields.
"""
data_d = {}
row_id = 0
for filename in filenames:
with open(filename) as f:
reader = csv.DictReader(f)
for file_no,row in enumerate(reader):
clean_row = [(k, preProcess(v)) for (k, v) in row.items()]
clean_row.append(('dataSet',file_no))
data_d[row_id] = dedupe.core.frozendict(clean_row)
row_id += 1
return data_d
```

# Step A
To implement Step A. Since in the implementation of dedupe, the Center for the canopy is always selected from corpus_ids, we would need to modify the invertIndex() function, to add only the records Ids which belong to dataset A.

```python
def invertIndex(data, tfidf_fields, df_index=None):

inverted_index = defaultdict(lambda : defaultdict(list))
token_vector = defaultdict(dict)
corpus_ids = set([])

for (record_id, record) in data:
if record[‘dataset’] == 0:
corpus_ids.add(record_id) # candidate for removal
```

# Step B

To implement Step B, Since, each record of the candidate set is compared with the center, the candidate_set, should only include the elements from database B.

```python
def createCanopies(field, threshold, corpus_ids, token_vector, inverted_index,data):

candidate_set = set((doc_id for token in center_tokens for doc_id in field_inverted_index[token]['occurrences'] if data[doc_id][‘dataset’] == 1))
```

Note - We would need to pass the data

# Step C
The Step C, will work by itself due to the changes made in the second step.

# Step D
From each and every Block, Blocked Pairs are generated are for each of permutation and combination while choosing a threshold for clustering. The blocked pairs can be generated correctly, by making the following changes -

```python
def blockedPairs(blocks) :
for block in blocks :

block_pairs = itertools.combinations(block, 2)

for pair in block_pairs :
if (pair[0]['dataset'] != pair[1]['dataset'])
yield pair
```

The major focus of this report was to implement the constrained Data Matching by making changes to the Blocking section of the code base.

# Step D

The suggested modification to implement the Constraint Data Matching, would not affect the Active Learning of dedupe and hence, dedupe will generate still generate the pairs for the labeling which may belong to the same dataset. One possible solution -

```python
def dataSample(data, sample_size):
'''Randomly sample pairs of records from a data dictionary'''

data_list = data.values()
data_list_A = []
data_list_B = []
for data in data_list:
if data['dataset'] == 0:
data_list_A.append(data)
else:
data_list_B.append(data)

n_records = len(data_list_A) if len(data_list_A) < len(data_list_B) else len(data_list_B)

random_pairs = dedupe.core.randomPairs(n_records, sample_size)

return tuple((data_list_A[int(k1)], data_list_B[int(k2)]) for k1, k2 in random_pairs)
```