{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Real world example\n", "\n", "In this example, I'm going to show you how to use RLTK to solve a real problem.\n", "\n", "## Problem & Dataset analysis\n", "\n", "The data we used here is called Abt-Buy, which can be found [here](https://github.com/usc-isi-i2/rltk-experimentation/tree/master/datasets/Abt-Buy). Abt.com (Abt.csv) and Buy.com (Buy.csv) are two e-commerce retailers, the goal is to find all matches (abt_buy_perfectMapping.csv) of products between these two files.\n", "\n", "Let's take a look of these files first. `wc`, `less` and `grep` are great tools to start with, then `pandas` or other data analysis tools / libraries can tell you more detailed information. Here's what I will do:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# initialization\n", "import os\n", "import pandas as pd\n", "from IPython.display import display\n", "\n", "# find rltk-experimentation\n", "def find_file_path(from_dir, file_path, depth=5):\n", " if depth == 0:\n", " raise RecursionError('Maximum recursion depth exceeded')\n", " path = os.path.join(from_dir, file_path)\n", " if os.path.exists(path):\n", " return path\n", " return find_file_path(os.path.join(from_dir, '..'), file_path, depth-1)\n", "os.chdir(find_file_path(os.getcwd(), 'rltk-experimentation'))" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "datasets/Abt-Buy/abt.csv\n", "\n", "first 5 rows:\n" ] }, { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
idnamedescriptionprice
0552Sony Turntable - PSLX350HSony Turntable - PSLX350H/ Belt Drive System/ ...NaN
1580Bose Acoustimass 5 Series III Speaker System -...Bose Acoustimass 5 Series III Speaker System -...$399.00
24696Sony Switcher - SBV40SSony Switcher - SBV40S/ Eliminates Disconnecti...$49.00
35644Sony 5 Disc CD Player - CDPCE375Sony 5 Disc CD Player- CDPCE375/ 5 Disc Change...NaN
46284Bose 27028 161 Bookshelf Pair Speakers In Whit...Bose 161 Bookshelf Speakers In White - 161WH/ ...$158.00
\n", "
" ], "text/plain": [ " id name \\\n", "0 552 Sony Turntable - PSLX350H \n", "1 580 Bose Acoustimass 5 Series III Speaker System -... \n", "2 4696 Sony Switcher - SBV40S \n", "3 5644 Sony 5 Disc CD Player - CDPCE375 \n", "4 6284 Bose 27028 161 Bookshelf Pair Speakers In Whit... \n", "\n", " description price \n", "0 Sony Turntable - PSLX350H/ Belt Drive System/ ... NaN \n", "1 Bose Acoustimass 5 Series III Speaker System -... $399.00 \n", "2 Sony Switcher - SBV40S/ Eliminates Disconnecti... $49.00 \n", "3 Sony 5 Disc CD Player- CDPCE375/ 5 Disc Change... NaN \n", "4 Bose 161 Bookshelf Speakers In White - 161WH/ ... $158.00 " ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "\n", "total number of rows:\n" ] }, { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
idnamedescriptionprice
total108110811081418
\n", "
" ], "text/plain": [ " id name description price\n", "total 1081 1081 1081 418" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "\n", "\n", "datasets/Abt-Buy/buy.csv\n", "\n", "first 5 rows:\n" ] }, { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
idnamedescriptionmanufacturerprice
010011646Linksys EtherFast EZXS88W Ethernet Switch - EZ...Linksys EtherFast 8-Port 10/100 Switch (New/Wo...LINKSYSNaN
110140760Linksys EtherFast EZXS55W Ethernet Switch5 x 10/100Base-TX LANLINKSYSNaN
210221960Netgear ProSafe FS105 Ethernet Switch - FS105NANETGEAR FS105 Prosafe 5 Port 10/100 Desktop Sw...NetgearNaN
310246269Belkin Pro Series High Integrity VGA/SVGA Moni...1 x HD-15 - 1 x HD-15 - 10ft - BeigeBelkinNaN
410315184Netgear ProSafe JFS516 Ethernet SwitchNetgear ProSafe 16 Port 10/100 Rackmount Switc...NetgearNaN
\n", "
" ], "text/plain": [ " id name \\\n", "0 10011646 Linksys EtherFast EZXS88W Ethernet Switch - EZ... \n", "1 10140760 Linksys EtherFast EZXS55W Ethernet Switch \n", "2 10221960 Netgear ProSafe FS105 Ethernet Switch - FS105NA \n", "3 10246269 Belkin Pro Series High Integrity VGA/SVGA Moni... \n", "4 10315184 Netgear ProSafe JFS516 Ethernet Switch \n", "\n", " description manufacturer price \n", "0 Linksys EtherFast 8-Port 10/100 Switch (New/Wo... LINKSYS NaN \n", "1 5 x 10/100Base-TX LAN LINKSYS NaN \n", "2 NETGEAR FS105 Prosafe 5 Port 10/100 Desktop Sw... Netgear NaN \n", "3 1 x HD-15 - 1 x HD-15 - 10ft - Beige Belkin NaN \n", "4 Netgear ProSafe 16 Port 10/100 Rackmount Switc... Netgear NaN " ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "\n", "total number of rows:\n" ] }, { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
idnamedescriptionmanufacturerprice
total109210926511086590
\n", "
" ], "text/plain": [ " id name description manufacturer price\n", "total 1092 1092 651 1086 590" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "\n", "\n", "datasets/Abt-Buy/abt_buy_perfectMapping.csv\n", "\n", "first 5 rows:\n" ] }, { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
idAbtidBuy
03847710011646
13847510140760
23305310221960
32724810246269
42526210315184
\n", "
" ], "text/plain": [ " idAbt idBuy\n", "0 38477 10011646\n", "1 38475 10140760\n", "2 33053 10221960\n", "3 27248 10246269\n", "4 25262 10315184" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "\n", "total number of rows:\n" ] }, { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
idAbtidBuy
total10971097
\n", "
" ], "text/plain": [ " idAbt idBuy\n", "total 1097 1097" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "\n", "\n" ] } ], "source": [ "def print_stats(fp):\n", " print(fp)\n", " df_data = pd.read_csv(fp, encoding='latin-1')\n", " \n", " print('\\nfirst 5 rows:')\n", " display(df_data.head(5))\n", " \n", " stat = []\n", " for i in range(df_data.shape[1]):\n", " stat.append(df_data.shape[0] - df_data.iloc[:,i].isnull().sum())\n", " df_stat = pd.DataFrame([stat], columns=df_data.columns.values.tolist())\n", " df_stat.rename(index={0: 'total'}, inplace=True)\n", " print('\\ntotal number of rows:')\n", " display(df_stat.head(1))\n", " print('\\n')\n", " \n", "print_stats('datasets/Abt-Buy/abt.csv')\n", "print_stats('datasets/Abt-Buy/buy.csv')\n", "print_stats('datasets/Abt-Buy/abt_buy_perfectMapping.csv')" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "After a rough inspection, the summaries are:\n", "\n", "- Abt\n", " - It has 1081 items and all items have `id`, `name` and `description`, only 414 items have `price`.\n", " - It seems `name` is formed in the pattern `{product name} - {model}`\n", "- Buy\n", " - It has 1092 items and all items have `id` and `name`, 1086 items have `manufacturer`, some items have description and prices.\n", " - Some of the `name`s are formed in pattern `{product name} - {model}`, somes are `{product name} - {probably sku id}`\n", "- Most of the `name` have brand / manufacturer included.\n", "- There are 1097 matches in total." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Construct RLTK components\n", "\n", "> One thing you should notice here is that my Record is not built immediately. I usually do a very basic one first, then evaluate the linkage result to find what should be improved. It's like a feedback system, after serveral rounds improvement, you should get a better Record.\n", "\n", "My personal assumption is, brand (manufacturer) and model can be two strong indicators: if two records have same brand and same model, there's a very high possibility that they belong to same entity.\n", "\n", "So I write couple of functions to do tokenization, model & brand extraction, name alias parsing." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "import rltk\n", "\n", "tokenizer = rltk.CrfTokenizer()\n", "\n", "\n", "model_stop_words = set([])\n", "with open('Abt-Buy/rltk_exp/stop_words_model.txt') as f:\n", " for line in f:\n", " line = line.strip().lower()\n", " if line:\n", " model_stop_words.add(line)\n", "\n", "def extract_possible_model(s):\n", " possible_models = []\n", " tokens = s.split(' ')\n", "\n", " for t in tokens:\n", " t = t.replace('(', '').replace(')', '')\n", " if len(t) < 2 or t in model_stop_words:\n", " continue\n", "\n", " if t.isdigit():\n", " possible_models.append(t)\n", " continue\n", "\n", " has_digit = has_alpha = False\n", " for c in t:\n", " if c.isdigit():\n", " has_digit = True\n", " elif c.isalpha():\n", " has_alpha = True\n", " if has_digit and has_alpha:\n", " possible_models.append(t)\n", "\n", " possible_models.sort(key=len, reverse=True)\n", "\n", " return possible_models[0] if len(possible_models) > 0 else ''\n", "\n", "\n", "def tokenize(s):\n", " tokens = tokenizer.tokenize(s)\n", " return [w.lower() for w in tokens if w.isalpha()]\n", "\n", "\n", "def get_brand_name(tokens):\n", " for word_len in range(min(5, len(tokens)), 0, -1):\n", " i = 0; j = i + word_len\n", " while j <= len(tokens):\n", " name = ' '.join(tokens[i:j])\n", " if name in brand_list:\n", " return name\n", " i += 1; j += 1\n", " return ''\n", "\n", "\n", "def process_brand_alias(alias):\n", " return brand_mapping.get(alias, alias)\n", "\n", "\n", "brand_list = set([])\n", "with open('Abt-Buy/rltk_exp/brands.txt') as f:\n", " for line in f:\n", " line = line.strip().lower()\n", " if len(line) == 0:\n", " continue\n", " brand_list.add(' '.join(tokenize(line)))\n", "\n", "brand_mapping = {}\n", "with open('Abt-Buy/rltk_exp/brand_alias.txt') as f:\n", " for line in f:\n", " alias = [w.strip().lower() for w in line.split('|')]\n", " for name in alias:\n", " brand_mapping[name] = alias[0]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Then, I build Records and Datasets." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "@rltk.remove_raw_object\n", "class AbtRecord(rltk.Record):\n", " def __init__(self, raw_object):\n", " super().__init__(raw_object)\n", " self.brand = ''\n", "\n", " @rltk.cached_property\n", " def id(self):\n", " return self.raw_object['id']\n", "\n", " @rltk.cached_property\n", " def name(self):\n", " return self.raw_object['name'].split(' - ')[0]\n", "\n", " @rltk.cached_property\n", " def name_tokens(self):\n", " tokens = tokenize(self.name)\n", "\n", " self.brand = get_brand_name(tokens)\n", "\n", " return set(tokens)\n", "\n", " @rltk.cached_property\n", " def model(self):\n", " ss = self.raw_object['name'].split(' - ')\n", " return ss[-1].strip() if len(ss) > 1 else ''\n", "\n", " @rltk.cached_property\n", " def description(self):\n", " return self.raw_object.get('description', '')\n", "\n", " @rltk.cached_property\n", " def price(self):\n", " p = self.raw_object.get('price', '')\n", " if p.startswith('$'):\n", " p = p[1:].replace(',', '')\n", " return p\n", "\n", " @rltk.cached_property\n", " def brand_cleaned(self):\n", " _ = self.name_tokens\n", " return process_brand_alias(self.brand)\n", "\n", " @rltk.cached_property\n", " def model_cleaned(self):\n", " m = self.model\n", " return m.lower().replace('-', '').replace('/', '').replace('&', '')" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "@rltk.remove_raw_object\n", "class BuyRecord(rltk.Record):\n", " def __init__(self, raw_object):\n", " super().__init__(raw_object)\n", " self.brand = ''\n", "\n", " @rltk.cached_property\n", " def id(self):\n", " return self.raw_object['id']\n", "\n", " @rltk.cached_property\n", " def name(self):\n", " return self.raw_object['name'].split(' - ')[0]\n", "\n", " @rltk.cached_property\n", " def name_tokens(self):\n", " tokens = tokenize(self.name)\n", " self.brand = get_brand_name(tokens)\n", " return set(tokens)\n", "\n", " @rltk.cached_property\n", " def description(self):\n", " return self.raw_object.get('description', '')\n", "\n", " @rltk.cached_property\n", " def manufacturer(self):\n", " return self.raw_object.get('manufacturer', '').lower()\n", "\n", " @rltk.cached_property\n", " def price(self):\n", " p = self.raw_object.get('price', '')\n", " if p.startswith('$'):\n", " p = p[1:].replace(',', '')\n", " return p\n", "\n", " @rltk.cached_property\n", " def model(self):\n", " ss = self.raw_object['name'].split(' - ')\n", " ss = ss[0].strip()\n", "\n", " return extract_possible_model(ss)\n", "\n", " @rltk.cached_property\n", " def name_suffix(self): # could probably be the model\n", " ss = self.raw_object['name'].split(' - ')\n", " return BuyRecord._clean(ss[-1]) if len(ss) > 1 else ''\n", "\n", " @staticmethod\n", " def _clean(s):\n", " return s.lower().replace('-', '').replace('/', '').replace('&', '')\n", "\n", " @rltk.cached_property\n", " def brand_cleaned(self):\n", " _ = self.name_tokens\n", " manufacturer = self.manufacturer\n", " return process_brand_alias(manufacturer if manufacturer != '' else self.brand)\n", "\n", " @rltk.cached_property\n", " def model_cleaned(self):\n", " m = self.model\n", " return BuyRecord._clean(m)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "ds_abt = rltk.Dataset(reader=rltk.CSVReader(open('datasets/Abt-Buy/Abt.csv', encoding='latin-1')),\n", " record_class=AbtRecord, adapter=rltk.MemoryKeyValueAdapter())\n", "\n", "ds_buy = rltk.Dataset(reader=rltk.CSVReader(open('datasets/Abt-Buy/Buy.csv', encoding='latin-1')),\n", " record_class=BuyRecord, adapter=rltk.MemoryKeyValueAdapter())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> Notes:\n", ">\n", "> - `cached_property` is set for pre-computing. It's recommended to use if the property generating is time consuming.\n", "> - Because `cached_property` is set and no more property needs `raw_object`, `remove_raw_object` is set to release the space used by `raw_object`.\n", "> - If you are using persistent Adapter (Redis, HBase) in Dataset, you can reuse it by calling `rltk.Dataset(adapter=...)` without other parameters." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Blocking\n", "\n", "Blocking can reduce a lot of unnecessary computings (but it also imports false postives and false negatives, which can be evaluated by pair completness and reduction ratio). Here I use a simple trigram blocking key which is really practically and widely-used in real world." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "def simple_ngram(s, n=3):\n", " return [s[i:i + n] for i in range(len(s) - (n - 1))]\n", "\n", "bg = rltk.TokenBlockGenerator()\n", "block = bg.generate(\n", " bg.block(ds_abt, function_=lambda r: simple_ngram(r.name, 3)),\n", " bg.block(ds_buy, function_=lambda r: simple_ngram(r.name, 3))\n", ")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Rule based solution\n", "\n", "One traditional way of solving record linkage problem is using some rules.\n", "\n", "### Build ground truth\n", "\n", "Since abt_buy_perfectMapping.csv contains all positives, the combinations of two records should be negative. There are lot of ways to generate negatives and RLTK also provides many methods.\n", "\n", "My plan here is to use fall perfect matches as positive and generate all negatives based the cross product of all ids appear in these matches." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "gt = rltk.GroundTruth()\n", "with open('datasets/Abt-Buy/abt_buy_perfectMapping.csv', encoding='latin-1') as f:\n", " for d in rltk.CSVReader(f): # this can be replace to python csv reader\n", " gt.add_positive(d['idAbt'], d['idBuy'])\n", "gt.generate_all_negatives(ds_abt, ds_buy, range_in_gt=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Generate results\n", "\n", "Let's come up with some rules and generate results." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "def rule_based_method(r_abt, r_buy):\n", " brand_score = 0\n", " if r_abt.brand_cleaned and r_buy.brand_cleaned:\n", " if r_abt.brand_cleaned == r_buy.brand_cleaned:\n", " brand_score = 1\n", " model_score = 0\n", " if r_abt.model_cleaned and r_buy.model_cleaned:\n", " if r_abt.model_cleaned == r_buy.model_cleaned:\n", " model_score = 1\n", " jaccard_score = rltk.jaccard_index_similarity(r_abt.name_tokens, r_buy.name_tokens)\n", "\n", " if model_score == 1:\n", " return True, 1\n", "\n", " total = brand_score * 0.3 + model_score * 0.3 + jaccard_score * 0.4\n", " return total > 0.45, total" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Trial can be used to record and evaluate results." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "trial = rltk.Trial(gt)\n", "candidate_pairs = rltk.get_record_pairs(ds_abt, ds_buy, ground_truth=gt, block=block)\n", "for r_abt, r_buy in candidate_pairs:\n", " result, confidence = rule_based_method(r_abt, r_buy)\n", " trial.add_result(r_abt, r_buy, result, confidence)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "### Evaluation" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.7620190210278335 0.02891807612686452 0.9710819238731355 0.23798097897216647 0.26020826195122676 0.7620190210278335 0.387944341414119\n", "tp: 17467\n", "fp: 49660\n", "tn: 1667605\n", "fn: 5455\n" ] } ], "source": [ "trial.evaluate()\n", "print(trial.true_positives, trial.false_positives, trial.true_negatives, trial.false_negatives,\n", " trial.precision, trial.recall, trial.f_measure)\n", "print('tp:', len(trial.true_positives_list))\n", "print('fp:', len(trial.false_positives_list))\n", "print('tn:', len(trial.true_negatives_list))\n", "print('fn:', len(trial.false_negatives_list))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Instead of setting a pre-computed `is_positive` mark, theshold can be decided at evaluation time. What's more, if you have a collection of `Trial`s, you can use `rltk.Evaluation` to plot a chart." ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYUAAAEKCAYAAAD9xUlFAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4xLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvDW2N/gAAIABJREFUeJzt3XmYFOXV/vHvYRNBFlmMRhAwQWRfHBBEo6JsRiEiiLgrikYBlRiFqAGXRJElBl6MoiKaKC7omx8m+uIeNxCGiICAgMiOkRhFEBWQ8/vj6ZkM20wPM9XV3XN/rmsuurtquu9ycA5V9TznMXdHREQEoFzcAUREJH2oKIiISD4VBRERyaeiICIi+VQUREQkn4qCiIjkU1EQEZF8KgoiIpJPRUFERPJViDtAcdWpU8cbNmwYdwwRkYwyb968f7t73aL2y7ii0LBhQ3Jzc+OOISKSUcxsdTL76fKRiIjkU1EQEZF8KgoiIpIv4+4piEjJ7Nixg3Xr1vHdd9/FHUUiULlyZerVq0fFihUP6PtVFETKmHXr1lGtWjUaNmyImcUdR0qRu/PFF1+wbt06GjVqdEDvEdnlIzObYmafm9mi/Ww3M5tgZivMbIGZtYsqi4j813fffUft2rVVELKQmVG7du0SnQVGeU9hKtCjkO09gcaJr0HAnyLMIiIFqCBkr5L+bCMrCu7+FvCfQnbpDTzuwWygppkdEVUeEREpWpyjj44E1hZ4vi7xmohksfLly9OmTRtatGhBv3792LZtW4nfMzc3l6FDh+53+4YNG+jbt2+JP6coBY/trLPO4quvvirV9586dSqDBw8GYNSoUYwdO7ZU3x8yZEiqmQ0ys1wzy920aVPccUSkBA4++GDmz5/PokWLqFSpEg888MBu292dXbt2Fes9c3JymDBhwn63//jHP2b69OkHlLc4Ch5brVq1mDRpUuSfWdriLArrgfoFntdLvLYXd5/s7jnunlO3bpGtO0QkQ5x00kmsWLGCVatW0aRJEy6++GJatGjB2rVrefnll+nUqRPt2rWjX79+bN26FYC5c+dywgkn0Lp1azp06MCWLVt48803OfPMMwH4xz/+QZs2bWjTpg1t27Zly5YtrFq1ihYtWgDhRvtll11Gy5Ytadu2LW+88QYQ/hXep08fevToQePGjbnppptKdGydOnVi/fr//kobM2YM7du3p1WrVowcOTL/9ccff5xWrVrRunVrLrroIgBeeOEFjj/+eNq2bcvpp5/Ov/71rxJlKY44h6TOAAab2VPA8cBmd98YYx6RMuf662H+/NJ9zzZt4L77it5v586dvPTSS/ToEcajLF++nMcee4yOHTvy73//m7vuuotXX32VqlWrMnr0aMaPH8/w4cPp378/Tz/9NO3bt+frr7/m4IMP3u19x44dy6RJk+jcuTNbt26lcuXKu22fNGkSZsbChQtZunQp3bp1Y9myZQDMnz+fDz74gIMOOogmTZowZMgQ6tevT3H98MMPvPbaawwcOBCAl19+meXLlzNnzhzcnV69evHWW29Ru3Zt7rrrLt577z3q1KnDf/4TbsOeeOKJzJ49GzPj4Ycf5t5772XcuHHFznEgIisKZjYNOAWoY2brgJFARQB3fwB4ETgDWAFsAy6LKovEb9s2uOQSGDoUTjop7jQSp2+//ZY2bdoA4Uxh4MCBbNiwgQYNGtCxY0cAZs+ezeLFi+ncuTMA27dvp1OnTnz88cccccQRtG/fHoDq1avv9f6dO3dm2LBhXHDBBfTp04d69erttv2dd95hyJAhABx77LE0aNAgvyicdtpp1KhRA4BmzZqxevXqYhWFvGNbv349TZs2pWvXrkAoCi+//DJt27YFYOvWrSxfvpwPP/yQfv36UadOHQBq1aoFhLkk/fv3Z+PGjWzfvv2A5xwciMiKgrsPKGK7A9dG9fmSXj7+GN55B6ZPh65d4fbboVOnuFNJMv+iL2151933VLVq1fzH7k7Xrl2ZNm3abvssXLiwyPcfPnw4P//5z3nxxRfp3LkzM2fO3OtsYX8OOuig/Mfly5dn586du21///33ueqqqwC444476NWr127b845t27ZtdO/enUmTJjF06FDcnREjRuR/b56JEyfuM8eQIUMYNmwYvXr14s0332TUqFFJ5S8NGXGjWTJf27bwyScwbly4XHHCCXDGGaAu6LIvHTt25N1332XFihUAfPPNNyxbtowmTZqwceNG5s6dC8CWLVv2+sX9ySef0LJlS26++Wbat2/P0qVLd9t+0kkn8cQTTwCwbNky1qxZQ5MmTZLKdfzxxzN//nzmz5+/V0EoqEqVKkyYMIFx48axc+dOunfvzpQpU/Lvi6xfv57PP/+cLl268Oyzz/LFF18A5F8+2rx5M0ceGQZjPvbYY0llKy0qCpIyVarAsGGwciXccw+8/z60bw+9e5f+dW3JbHXr1mXq1KkMGDCAVq1a0alTJ5YuXUqlSpV4+umnGTJkCK1bt6Zr1657zd697777aNGiBa1ataJixYr07Nlzt+3XXHMNu3btomXLlvTv35+pU6fudoZQWtq2bUurVq2YNm0a3bp14/zzz6dTp060bNmSvn37smXLFpo3b84tt9zCySefTOvWrRk2bBgQhpv269eP4447Lv/SUqpYuIqTOXJyclyL7GSHr7+GCRPC2cNXX8E558CoUZAYJCIRWbJkCU2bNo07hkRoXz9jM5vn7jlFfa/OFCQ21avDrbfCp5/Cb38LL78MrVrBgAGwxxm/iKSIioLErmbNcON51SoYPhxeeAGaN4eLL4bEJWURSREVBUkbtWrB738fzhyGDQsjlY49Fi6/PLwmpSfTLhtL8kr6s1VRkLRTty6MGRNuSA8eDE8+CcccA1ddBWvWxJ0u81WuXJkvvvhChSEL5a2nkOwQ3H3RjWZJe+vXw913w+TJYAZXXgkjRsCRap94QLTyWnbb38pryd5oVlGQjLFmDfzudzBlCpQvD7/8Jdx8Mxx+eNzJRNKfRh9J1jnqKHjwwTA7+vzzYeJEOProUChEpHSoKEjGOfrocLawZAn07BmGtU6ZEncqkeygoiAZq3FjeOYZOP10uOYa+Oc/404kkvlUFCSjlS8fRicddliYEf2fwhaAFZEiqShIxqtbF559NoxSuugiKOaiXSJSgIqCZIXjjw9toF98UTeeRUpCRUGyxi9/CRdeCCNHwsyZcacRyUwqCpI1zMKQ1RYtwpDV1avjTiSSeVQUJKtUqQLPPQc7d0LfvvD993EnEsksKgqSdRo3hscfD6u6XXdd3GlEMouKgmSl3r1DC4wHH4QUr2YoktFUFCRr3XUXnHoqXH21lvsUSZaKgmStChXgqaegdu0wse3LL+NOJJL+VBQkqx12WJjYtmYNXHKJJraJFEVFQbJep04wfnxY5vOee+JOI5LeVBSkTBg8GAYMgNtug1dfjTuNSPpSUZAywQweegiaNg3FYe3auBOJpCcVBSkzqlYNE9u+/14T20T2R0VBypQmTeDRR2HOHBg2LO40IulHRUHKnHPOgRtvhPvvh7/8Je40IulFRUHKpLvvhpNPhkGDYMGCuNOIpA8VBSmT8ia21awZzhw2b447kUh6UFGQMuvww8Maz6tWwaWXgnvciUTiF2lRMLMeZvaxma0ws+H72H6Umb1hZh+Y2QIzOyPKPCJ7OvFEGDMG/vpXuPfeuNOIxC+yomBm5YFJQE+gGTDAzJrtsdutwDPu3hY4D7g/qjwi+3PdddC/P/zmN/D663GnEYlXlGcKHYAV7r7S3bcDTwG999jHgeqJxzWADRHmEdknM3j44TBc9bzzYN26uBOJxCfKonAkUHDe6LrEawWNAi40s3XAi8CQCPOI7Nchh8Dzz8O338K558L27XEnEolH3DeaBwBT3b0ecAbwZzPbK5OZDTKzXDPL3bRpU8pDStlw7LEwZQrMmhXmMYiURVEWhfVA/QLP6yVeK2gg8AyAu88CKgN19nwjd5/s7jnunlO3bt2I4opAv35www0wcSJMmxZ3GpHUi7IozAUam1kjM6tEuJE8Y4991gCnAZhZU0JR0KmAxGr06DAq6YorYNGiuNOIpFZkRcHddwKDgZnAEsIoo4/M7A4z65XY7VfAlWb2ITANuNRdo8UlXhUrhvkL1aqFiW1ffx13IpHUsUz7HZyTk+O5ublxx5Ay4K23oEsX6N0bpk8Po5REMpWZzXP3nKL2i/tGs0ja+tnPwqWk55+HcePiTiOSGioKIoUYNiysvTB8OPzjH3GnEYmeioJIIczgkUfgpz8Ns543aHqlZDkVBZEiVK8eVmzbsiVMbNuxI+5EItFRURBJQvPm4Yzh3XfhppviTiMSHRUFkSSddx4MHQr33ReGrIpkIxUFkWIYMwZOOAEuvxwWL447jUjpU1EQKYZKlcJZQtWqYWLbli1xJxIpXSoKIsV05JFhKc9ly2DgQK3YJtlFRUHkAJx6Ktx9Nzz7bLjHIJItVBREDtCvfw1nnx3+fPvtuNOIlA4VBZEDZAaPPgpHHx3mL3z2WdyJREpORUGkBGrUCBPbNm8OM541sU0ynYqCSAm1bAkPPRS6qo4YEXcakZJRURApBRdcANdeG7qpPv983GlEDpyKgkgpGT8e2rcPw1RXr447jciBUVEQKSWVKoX5C7t2wYABur8gmUlFQaQUHX00TJ4Ms2bBqFFxpxEpPhUFkVLWv3+4hHT33fDqq3GnESkeFQWRCPzxj3DssXDRRfCvf8WdRiR5KgoiEahaFZ5+Gr78Ei65JNxnEMkEKgoiEWnZMvRFmjkzjEwSyQQqCiIRuuqq0GJ7xAiYMyfuNCJFU1EQiZBZmO185JFh5bbNm+NOJFI4FQWRiB16KEybBmvWwKBBWn9B0puKgkgKdOoEd94ZVm175JG404jsn4qCSIrcfDOcfjoMHar1nSV9qSiIpEi5cvDnP0O1amGC27ffxp1IZG8qCiIpdPjh8PjjsGgRDBsWdxqRvakoiKRY9+5w003wwAMwfXrcaUR2p6IgEoO77oIOHeCKK2DVqrjTiPyXioJIDCpWDMNU3dVmW9KLioJITPLabM+eDb/9bdxpRIJIi4KZ9TCzj81shZkN388+55rZYjP7yMyejDKPSLrp3x+uvBJGj4ZXXok7jUiERcHMygOTgJ5AM2CAmTXbY5/GwAigs7s3B66PKo9IurrvPmjaVG22JT1EeabQAVjh7ivdfTvwFNB7j32uBCa5+5cA7v55hHlE0lKVKqHN9ubNcPHFarMt8YqyKBwJrC3wfF3itYKOAY4xs3fNbLaZ9Ygwj0jaatEinDG8/DKMHRt3GinL4r7RXAFoDJwCDAAeMrOae+5kZoPMLNfMcjdt2pTiiCKpMWgQ9O0Lt9wSbj6LxCHKorAeqF/geb3EawWtA2a4+w53/xRYRigSu3H3ye6e4+45devWjSywSJwKttkeMAC++iruRFIWRVkU5gKNzayRmVUCzgNm7LHPXwlnCZhZHcLlpJURZhJJazVrwlNPwdq1arMt8ahQ2EYzK7Q7i7vvd5FBd99pZoOBmUB5YIq7f2RmdwC57j4jsa2bmS0GfgB+7e5fFPcgRLJJx47wu9/B8OHQtWsYsiqSKuaF/FPEzEYW9s3ufnupJypCTk6O5+bmpvpjRVJq1y7o0QPefhtyc6F587gTSaYzs3nunlPUfoWeKcTxS19EQpvtxx+H1q3DBLc5c8LQVZGoFXX5aEJh2919aOnGEZE8hx8e1l/o3h1uuAEefDDuRFIWFFoUgHkpSSEi+9StW1ixbfRoOO00OPfcuBNJtiv0nkI60j0FKWt27ICTToIlS2D+fGjUKO5EkomSvaeQ1JBUM6trZmPN7EUzez3vq+QxRaQoeW22zdRmW6KX7DyFJ4AlQCPgdmAVYR6CiKRAo0ZhYtv778Ntt8WdRrJZskWhtrs/Auxw93+4++VAlwhzicge+vULE9pGjw49kkSikGxRyDth3WhmPzeztkCtiDKJyH784Q9hzsJFF8Fnn8WdRrJRskXhLjOrAfwKuBF4GLghslQisk95bba3bAmFQW22pbQlVRTc/W/uvtndF7n7qe5+XKJNhYikWPPm8Mc/wquvwr33xp1Gsk2yo48eK9jS2swONbMp0cUSkcJccUWYs3DrrTBrVtxpJJske/molbvnN/JNrJTWNppIIlIUM5g8GerXV5ttKV3JFoVyZnZo3hMzq0XRs6FFJEI1aoQ22+vXhzOHDJuHKmkq2aIwDphlZnea2Z3Ae4CuZorE7PjjQ5vt554LZw4iJZXsjebHgT7AvxJffdz9z1EGE5Hk3Hhj6JF0/fWwcGHcaSTTFWfltVrAN+7+P8AmM1MHFpE0kNdmu0aN0Gb7m2/iTiSZLNnRRyOBm4ERiZcqAn+JKpSIFM+PfgR/+QssXRrOGEQOVLJnCmcDvYBvANx9A1AtqlAiUnynnx6W8Hz44TDBTeRAJFsUtnvose0AZlY1ukgicqBuvz2s8TxoEKxcGXcayUTJFoVnzOxBoKaZXQm8Smh1ISJpZM8229u3x51IMk2yo4/GAtOB54AmwG/dvdClOkUkHg0bhktIc+aEGc8ixZH0BDR3fwV4BcDMypnZBe7+RGTJROSA9e0LV18NY8ZAly7Qo0fciSRTFHqmYGbVzWyEmf2PmXWzYDCwEtBqsSJpbPx4aNECLr4YNm6MO41kiqIuH/2ZcLloIXAF8AbQD/iFu/eOOJuIlMDBB4dRSFu3qs22JK+oonC0u1/q7g8CA4BmQHd3nx99NBEpqWbNYMIEeO21sGKbSFGKKgr5S4S7+w/AOnf/LtpIIlKaBg4MM51vuw3eey/uNJLuiioKrc3s68TXFqBV3mMz+zoVAUWkZMzgwQfhqKPCMNUvv4w7kaSzQouCu5d39+qJr2ruXqHA4+qpCikiJZPXZnvDBrXZlsIVpyGeiGSwDh3g7rvh+efhgQfiTiPpSkVBpAwZNizMWbjhBliwIO40ko5UFETKkHLl4LHH4NBD4bzz1GZb9qaiIFLGHHbYf9tsX3dd3Gkk3URaFMysh5l9bGYrzGx4IfudY2ZuZjlR5hGR4LTTYMQIeOSR0EBPJE9kRcHMygOTgJ6ESW8DzKzZPvarBlwHvB9VFhHZ26hRcMIJcNVV8MkncaeRdBHlmUIHYIW7r3T37cBTwL5aY9wJjAY0KU4khSpWhCefhPLlw/0FtdkWiLYoHAmsLfB8XeK1fGbWDqjv7n+PMIeI7EeDBuESUm4u/OY3caeRdBDbjWYzKweMB36VxL6DzCzXzHI3bdoUfTiRMqRPH7jmGhg3Dl56Ke40Ercoi8J6oH6B5/USr+WpBrQA3jSzVUBHYMa+bja7+2R3z3H3nLp160YYWaRsGjsWWrYMbbY3bIg7jcQpyqIwF2hsZo3MrBJwHjAjb6O7b3b3Ou7e0N0bArOBXu6eG2EmEdmHvDbb27aFNts//BB3IolLZEXB3XcCg4GZwBLgGXf/yMzuMLNeUX2uiByYpk1h4kR4/XW4556400hczDOsM1ZOTo7n5upkQiQK7nDBBfDMM/Dmm3DiiXEnktJiZvPcvci5YJrRLCL5zEKzvAYN4Pzz4T//iTuRpJqKgojspnr1cH/hs8/CAj0ZdjFBSkhFQUT2kpMT2mz/9a/wpz/FnUZSSUVBRPbphhugZ8/QbvvDD+NOI6mioiAi+1SuHEydCrVqhTWe1Wa7bFBREJH9ymuzvWwZDBkSdxpJBRUFESlUly5wyy3w6KPwxBNxp5GoqSiISJFGjoTOneHqq2HFirjTSJRUFESkSBUqhDbbFSuqzXa2U1EQkaQcdVRosz1vXli1TbKTioKIJO3ss+Haa2H8+DDBTbKPioKIFMvYsXD88eEy0nXXwXdaMzGrqCiISLFUrhya5Q0dChMmQMeOsGRJ3KmktKgoiEixVa4Mf/wjvPACrF8Pxx0HDz2kPknZQEVBRA7YmWfCggVhuOqgQdCvH3z5ZdyppCRUFESkRI44AmbOhNGj4f/9P2jdGt55J+5UcqBUFESkxMqVg5tugvfeg0qV4OSTYdQo2Lkz7mRSXCoKIlJq2reHDz6ACy+E22+HU06B1avjTiXFoaIgIqWqWjV47LHQSG/BgnA56dln404lyVJREJFIXHBBOGto0gTOPReuvFLttzOBioKIROYnPwk3nUeMCC0ycnJg/vy4U0lhVBREJFIVK8Lvfw+vvgqbN4fZ0PfdpzkN6UpFQURSokuXcI+he/ew1OeZZ8Lnn8edSvakoiAiKVOnTpjLMHEivPYatGoFr7wSdyopSEVBRFLKDAYPhjlzoHZt6NYtzHHQGg3pQUVBRGLRqhXMnRtWcxszJrTKWL487lSioiAisalSBf70J3j+efjkE2jbNsxx0E3o+KgoiEjszj4bPvwwdFu99NIwx2Hz5rhTlU0qCiKSFurXh9dfhzvvhGeeCWcNs2fHnarsUVEQkbRRvjzceiu89Rbs2gUnnhjmOPzwQ9zJyg4VBRFJOyecEGY+9+0Lt9wCXbuGxXwkeioKIpKWataEadNgypQwfLVVqzDHQaKloiAiacsMLrsM/vlPaNAAfvELuPZa+PbbuJNlr0iLgpn1MLOPzWyFmQ3fx/ZhZrbYzBaY2Wtm1iDKPCKSmY45BmbNgmHD4P77oUMH+OijuFNlp8iKgpmVByYBPYFmwAAza7bHbh8AOe7eCpgO3BtVHhHJbAcdBOPGwUsvhZ5JOTlhjoPmNJSuKM8UOgAr3H2lu28HngJ6F9zB3d9w922Jp7OBehHmEZEs0KNHaKx3yilwzTXQpw988UXcqbJHlEXhSGBtgefrEq/tz0DgpX1tMLNBZpZrZrmbNm0qxYgikol+9CP4+99h/PjwZ+vW8OabcafKDmlxo9nMLgRygDH72u7uk909x91z6tatm9pwIpKWypULLbhnz4aqVUNr7ltvhR074k6W2aIsCuuB+gWe10u8thszOx24Bejl7t9HmEdEslC7djBvXmiP8bvfwc9+Bp9+GneqzBVlUZgLNDazRmZWCTgPmFFwBzNrCzxIKAhabkNEDsghh4T5DE89BYsXQ5s2YY6DFF9kRcHddwKDgZnAEuAZd//IzO4ws16J3cYAhwDPmtl8M5uxn7cTESlS//6hsV7z5nD++WGOw9atcafKLOYZNp4rJyfHc3Nz444hImls5064445wOeknPwlnDccdF3eqeJnZPHfPKWq/tLjRLCJSmipUCEXh9dfD7OdOncIch1274k6W/lQURCRrnXxyuJx05plw443Qsyd89lncqdKbioKIZLVateC55+CBB0JL7tatw6xo2TcVBRHJemZw1VWQmxsmvp1xRpjj8L0Gwe9FRUFEyozmzUMb7sGD4b774KyzNNltTyoKIlKmVK4MEyfCww/DK6/A1VerqV5BFeIOICISh4EDYfXqsCb00UeHFd5ERUFEyrDbb4dVq0LPpIYN4YIL4k4UPxUFESmzzMJlpLVr4fLLoV69MIy1LNM9BREp0ypVguefD5eQzj4bli6NO1G8VBREpMw79FB48UWoWDEMV/28DLfnVFEQEQEaNYIXXggzns86C7ZtK/p7spGKgohIQocO8OSTMHcuXHgh/PBD3IlST0VBRKSAX/wC/vAH+N//hV//Ou40qafRRyIie7juOli5MhSHRo1gyJC4E6WOioKIyD6MHx/mMFx/PTRoAL16FfktWUGXj0RE9qF8+XB/oV07GDAgNNMrC1QURET2o2pV+Nvf4LDDwpoMq1fHnSh6KgoiIoX40Y/CHIbvvw9zGL76Ku5E0VJREBEpQtOmYdbz8uVwzjmwfXvciaKjoiAikoRTT4VHHgnrPg8alL3ttjX6SEQkSRddBJ9+CiNHhqGqI0fGnaj0qSiIiBTDbbeFOQyjRoV225dcEnei0qWiICJSDGYweXJot33FFVC/PnTpEneq0qOiICJSTJUqwXPPQefO0KcPTJkCBx8cbkBv3x5GKuU93tfzHTugShWoUQNq1gx/5n0VfF65cuqPTUVBROQA1KwZhqp27BhGJCWrUqXQonvbtqJvVh90UCgO7dqFzzIrWeZkqCiIiBygBg1g4UJYsiT8ss/7OuigfT+vUOG/v9h37YKtW8O8h82b//tV8PlXX8GsWfB//wdffx0KRNRUFERESqBOHTjppOJ/X7lyUL16+CrMk0/C22/Dxo2pKQqapyAiksaOOCL8+dlnqfk8FQURkTR2+OHhTxUFERHJLwobN6bm81QURETSWM2a4UZ1VpwpmFkPM/vYzFaY2fB9bD/IzJ5ObH/fzBpGmUdEJNOYhbOFjC8KZlYemAT0BJoBA8ys2R67DQS+dPefAn8ARkeVR0QkU+XkQK1aqfmsKIekdgBWuPtKADN7CugNLC6wT29gVOLxdOB/zMzcs7X/oIhI8U2fnrrPivLy0ZHA2gLP1yVe2+c+7r4T2AzUjjCTiIgUIiMmr5nZIGBQ4un3ZrYozjwxqwP8O+4QMSrLx1+Wjx10/CU9/gbJ7BRlUVgP1C/wvF7itX3ts87MKgA1gC/2fCN3nwxMBjCzXHfPiSRxBtDxl93jL8vHDjr+VB1/lJeP5gKNzayRmVUCzgNm7LHPDCCvG3lf4HXdTxARiU9kZwruvtPMBgMzgfLAFHf/yMzuAHLdfQbwCPBnM1sB/IdQOEREJCaR3lNw9xeBF/d47bcFHn8H9Cvm204uhWiZTMdfdpXlYwcdf0qO33S1RkRE8qjNhYiI5EvbolDWW2QkcfzDzGyxmS0ws9fMLKnhZpmgqGMvsN85ZuZmllUjUpI5fjM7N/Hz/8jMnkx1xigl8Xf/KDN7w8w+SPz9PyOOnFEwsylm9vn+ht1bMCHx32aBmbUr9RDunnZfhBvTnwBHA5WAD4Fme+xzDfBA4vF5wNNx507x8Z8KVEk8/mW2HH8yx57YrxrwFjAbyIk7d4p/9o2BD4BDE88Pizt3io9/MvDLxONmwKq4c5fi8f8MaAcs2s/2M4CXAAM6Au+XdoZ0PVPIb5Hh7tuBvBYZBfUGHks8ng6cZpaKFUxTosjjd/c33H1b4ulswjyQbJDMzx7gTkKvrO9SGS4Fkjlrn998AAAEGklEQVT+K4FJ7v4lgLt/nuKMUUrm+B3IW6+sBrAhhfki5e5vEUZi7k9v4HEPZgM1zeyI0syQrkWhrLfISOb4CxpI+NdDNijy2BOnzPXd/e+pDJYiyfzsjwGOMbN3zWy2mfVIWbroJXP8o4ALzWwdYXTjkNRESwvF/d1QbBnR5kL2z8wuBHKAk+POkgpmVg4YD1wac5Q4VSBcQjqFcIb4lpm1dPevYk2VOgOAqe4+zsw6EeY6tXD3XXEHywbpeqZQnBYZFNYiI0Mlc/yY2enALUAvd/8+RdmiVtSxVwNaAG+a2SrCddUZWXSzOZmf/TpghrvvcPdPgWWEIpENkjn+gcAzAO4+C6hM6AtUFiT1u6Ek0rUolPUWGUUev5m1BR4kFIRsuqZc6LG7+2Z3r+PuDd29IeF+Si93z40nbqlL5u/+XwlnCZhZHcLlpJWpDBmhZI5/DXAagJk1JRSFTSlNGZ8ZwMWJUUgdgc3uXqoLdabl5SMv4y0ykjz+McAhwLOJ++tr3L1XbKFLSZLHnrWSPP6ZQDczWwz8APza3bPiLDnJ4/8V8JCZ3UC46XxptvyD0MymEQp+ncQ9k5FARQB3f4BwD+UMYAWwDbis1DNkyX9LEREpBel6+UhERGKgoiAiIvlUFEREJJ+KgoiI5FNREBGRfCoKUiaZ2Q9mNt/MFpnZs2ZWpRTeM8fMJhSy/cdmNr2knyMSJQ1JlTLJzLa6+yGJx08A89x9fIHtRvj/Q60TpEzRmYIIvA381MwaJvr4Pw4sAuqbWTczm2Vm/0ycUeQVkvZm9p6ZfWhmc8ysmpmdYmZ/S2w/OXEmMj/R979a4v0XJbZXNrNHzWxhYvupidcvNbPnzez/zGy5md0b038TKaNUFKRMS/TN6gksTLzUGLjf3ZsD3wC3Aqe7ezsgFxiWaL/wNHCdu7cGTge+3eOtbwSudfc2wEn72H4t4O7ektDg7TEzq5zY1gboD7QE+ptZfURSREVByqqDzWw+4Rf9GkLbFIDViT71EJrtNQPeTex7CdAAaAJsdPe5AO7+daJ9e0HvAuPNbChQcx/bTwT+kvj+pcBqQg8jgNcSPZ6+AxYnPlMkJdKy95FICnyb+Fd8vkQPqW8KvgS84u4D9tivZVFv7u73mNnfCX1q3jWz7iS/IFDBjrc/oP9PJYV0piCyf7OBzmb2UwAzq2pmxwAfA0eYWfvE69USl6HymdlP3H2hu48mdP48do/3fhu4ILHvMcBRifcViZWKgsh+uPsmwmI+08xsATALODaxTGR/YKKZfQi8QmjfXND1ieGuC4Ad7L0y3v1AOTNbSLg/cWkWrYkhGUxDUkVEJJ/OFEREJJ+KgoiI5FNREBGRfCoKIiKST0VBRETyqSiIiEg+FQUREcmnoiAiIvn+P0M2Kjd/vggaAAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "eva = rltk.Evaluation()\n", "for threshold in range(0, 10):\n", " threshold = float(threshold) / 10\n", " t = trial.clone() # remember to clone it\n", " t.evaluate(threshold)\n", " eva.add_trial(t)\n", "eva.plot_precision_recall().show()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "## Machine learning solution\n", "\n", "Another approach is using machine learning techniques. [Scikit-learn](http://scikit-learn.org/stable/) is used here (Run `pip install -U scikit-learn` for installation).\n", "\n", "### Feature vector\n", "\n", "The basic idea to use machine learning is to construct the feature vector of each pair and use it to train a model, then this model can be used to predict whether the input feature vector indicates a pair or not." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "tfidf = rltk.TF_IDF()\n", "for r in ds_abt:\n", " tfidf.add_document(r.id, r.name_tokens)\n", "for r in ds_buy:\n", " tfidf.add_document(r.id, r.name_tokens)\n", "tfidf.pre_compute()\n", "\n", "def generate_feature_vector(r_abt, r_buy):\n", " # brand\n", " brand_score = 0.2\n", " brand_marker = 0\n", " if r_abt.brand_cleaned and r_buy.brand_cleaned:\n", " if r_abt.brand_cleaned == r_buy.brand_cleaned:\n", " brand_score = 1\n", " brand_marker = 1\n", "\n", "\n", " # model 1\n", " model_score = 0.2\n", " model_marker = 0\n", " if r_abt.model_cleaned and r_buy.model_cleaned:\n", " if r_abt.model_cleaned == r_buy.model_cleaned:\n", " model_score = 1\n", " model_marker = 1\n", " else:\n", " if len(r_abt.model_cleaned) > len(r_buy.model_cleaned):\n", " if r_abt.model_cleaned.startswith(r_buy.model_cleaned) \\\n", " or r_abt.model_cleaned.endswith(r_buy.model_cleaned):\n", " model_score = 1\n", " model_marker = 1\n", " else:\n", " model_score = rltk.levenshtein_similarity(r_abt.model_cleaned, r_buy.model_cleaned)\n", " elif len(r_abt.model_cleaned) < len(r_buy.model_cleaned):\n", " if r_buy.model_cleaned.startswith(r_abt.model_cleaned) \\\n", " or r_buy.model_cleaned.endswith(r_abt.model_cleaned):\n", " model_score = 1\n", " model_marker = 1\n", " else:\n", " model_score = rltk.levenshtein_similarity(r_abt.model_cleaned, r_buy.model_cleaned)\n", " else:\n", " model_score = 0\n", "\n", " # model 2\n", " model2_score = rltk.levenshtein_similarity(r_abt.model_cleaned, r_buy.name_suffix)\n", "\n", " # name tokens jaccard\n", " jaccard_score = rltk.jaccard_index_similarity(r_abt.name_tokens, r_buy.name_tokens)\n", "\n", " tfidf_score = tfidf.similarity(r_abt.id, r_buy.id)\n", "\n", " # price\n", " if r_abt.price and r_buy.price:\n", " price_marker = 1\n", " abt_price = float(r_abt.price)\n", " buy_price = float(r_buy.price)\n", " if abt_price == 0 and buy_price == 0:\n", " price_difference = 0\n", " else:\n", " price_difference = float(abs(abt_price - buy_price)) / max(abt_price, buy_price)\n", " else:\n", " price_marker = 0\n", " price_difference = 0\n", "\n", " return [brand_score, brand_marker, model_score, model_marker,\n", " model2_score, jaccard_score, tfidf_score, price_difference, price_marker]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Train test split" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": [ "gt.remove_negatives()\n", "gt_train, gt_test = gt.train_test_split(test_ratio=0.3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Generate stratified negatives for ground truth\n", "\n", "In order to train a machine learning model, same amount of negatives to positives needs to be given. But how to sample negatives is a problem: random sampling may only give training algorithm very easy-to-detect negatives.\n", "\n", "So I'm going to do a stratified sampling. RLTK has a built-in method called `generate_stratified_negatives`. You only need to provide a clustering function and tell RLTK the total number of clusters and the total number of negatives you want, then it generates negatives and picks them based on the positive and negatives ratio of each cluster.\n", "\n", "For testing, I want the model to be validated on all possible combination of pairs." ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "from sklearn.cluster import KMeans\n", "\n", "X_km = []\n", "for id_abt, id_buy, _ in gt_train:\n", " r_abt = ds_abt.get_record(id_abt)\n", " r_buy = ds_buy.get_record(id_buy)\n", " X_km.append(generate_feature_vector(r_abt, r_buy))\n", "kmeans_model = KMeans(n_clusters=10, random_state=0).fit(X_km)\n", "\n", "\n", "def classify(r_abt, r_buy):\n", " v = generate_feature_vector(r_abt, r_buy)\n", " cluster_id = kmeans_model.predict([v])[0]\n", " return cluster_id\n", "\n", "gt_train.generate_stratified_negatives(ds_abt, ds_buy, classify, 10, range_in_gt=True, exclude_from=gt_test)\n", "gt_test.generate_all_negatives(ds_abt, ds_buy, range_in_gt=True, exclude_from=gt_train)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Train and test\n", "\n", "After preparation, it's time to train and test model." ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [], "source": [ "from sklearn import svm\n", "from sklearn.model_selection import GridSearchCV\n", "\n", "# train\n", "X, y = [], []\n", "train_pairs = rltk.get_record_pairs(ds_abt, ds_buy, ground_truth=gt_train)\n", "for r_abt, r_buy in train_pairs:\n", " v = generate_feature_vector(r_abt, r_buy)\n", " X.append(v)\n", " y.append(gt_train.get_label(r_abt.id, r_buy.id))\n", "\n", "clf = svm.SVC(probability=True)\n", "res = 5\n", "clf = GridSearchCV(clf,\n", " {'C' : [i / res for i in range(1, res + 1)], \n", " 'gamma' : [i / (100 * res) for i in range(0, res + 1)]},\n", " cv=3)\n", "clf.fit(X, y)\n", "\n", "# test\n", "trial = rltk.Trial(ground_truth=gt_test)\n", "for r_abt, r_buy in rltk.get_record_pairs(ds_abt, ds_buy, ground_truth=gt_test):\n", " # ml\n", " v = generate_feature_vector(r_abt, r_buy)\n", " vv = clf.predict_proba([v])[0][1]\n", " trial.add_result(r_abt, r_buy, vv > 0.3,\n", " confidence=vv,\n", " feature_vector=v)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Though Abt-Buy contains few many-to-many pairs, if I restrict it only to have one-to-one pairs (by using Munkres), false positive drops and F-measure increases. " ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "threshold: 0.0 f-measure: 0.8462709284627092\n", "threshold: 0.1 f-measure: 0.8462709284627092\n", "threshold: 0.2 f-measure: 0.8416149068322981\n", "threshold: 0.3 f-measure: 0.8538587848932677\n", "threshold: 0.4 f-measure: 0.75\n", "threshold: 0.5 f-measure: 0.7252336448598131\n", "threshold: 0.6 f-measure: 0.6666666666666666\n", "threshold: 0.7 f-measure: 0.628099173553719\n", "threshold: 0.8 f-measure: 0.5482456140350878\n", "threshold: 0.9 f-measure: 0.14124293785310732\n" ] } ], "source": [ "for threshold in [round(x * 0.1, 1) for x in range(0, 10)]:\n", " trial.run_munkres(threshold=threshold)\n", " trial.evaluate()\n", " print('threshold:', threshold, 'f-measure:', trial.f_measure)" ] } ], "metadata": { "kernelspec": { "display_name": "rltk", "language": "python", "name": "rltk" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.2" } }, "nbformat": 4, "nbformat_minor": 1 }