{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Analisi di documenti simili #\n", "\n", "Una delle applicazioni delle tecniche di analisi dei documenti simili è legata alle procedure volte a eliminare record che si riferiscono alla stessa entità quando si fondono due o più fonti di dati. A tali procedure ci si riferisce utilizzando tipicamente il nome *entity resolution* o *record linkage*, ma nel gergo tecnico esiste una vasta gamma di termini più o meno equivalenti, quali per esempio *entity disambiguation*, *entity linking*, *duplicate detection*, *deduplication*, *record matching*, *conflation*, *reconciliation* o, più genericamente *data integration*)\n", "\n", "Si parla dunque di entity resolution quando si vogliono rilevare record in una fonte dati che si riferiscono tutti a una stessa entità, tipicamente a seguito dell'integrazione di fonti dati diverse e a fronte di descrizioni non identiche di uno stesso oggetto.\n", "\n", "## Strumenti\n", "Questo tutorial è basato sull'uso di funzionalità base di Python 2.7, di Spark 1.4.1 associato alle API pySpark e della libreria grafica matplotlib. Verrà fatto uso delle librerie standard per le espressioni regolari: nel caso in cui sia necessario un ripasso, il sito [regex101](https://regex101.com/) permette di applicare espressioni regolari su stringhe in modo interattivo." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "import pyspark\n", "sc = pyspark.SparkContext('local[*]')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## File\n", "I dati utilizzati fanno parte del progetto [metric-learning](https://code.google.com/archive/p/metric-learning/source). I file corrispondenti, memorizzati nella directory `data`, sono i seguenti:\n", "\n", "* `Google.csv`, dataset di prodotti estratto da Google,\n", "* `Amazon.csv`, dataset di prodotti estratto da Amazon,\n", "* `Google_small.csv`, \\\\(200\\\\) record campionati da `Google.csv`,\n", "* `Amazon_small.csv` \\\\(200\\\\) record campionati da `Amazon.csv`,\n", "* `Amazon_Google_perfectMapping.csv`, mapping tra i record dei due dataset che si riferiscono a uno stesso prodotto,\n", "* `stopwords.txt`, un elenco di stop word per la lingua inglese.\n", "\n", "Useremo i file contenenti i record campionati nella prima parte del tutorial, così da poter sperimentare senza che l'elaborazione richieda di attendere troppo tempo. Il file che indica quali coppie di record si riferiscano allo stesso prodotto (informazione che prende il nome di *gold standard* o *ground truth*) verrà usato per valutare la performance dell'algoritmo proposto.\n", "\n", "Memorizziamo i nomi di questi file in altrettante costanti:" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "import sys\n", "import os\n", "\n", "DATA_DIR = 'data/'\n", "\n", "base_dir = os.path.join(DATA_DIR)\n", "\n", "GOOGLE_PATH = 'Google.csv'\n", "GOOGLE_SMALL_PATH = 'Google_small.csv'\n", "AMAZON_PATH = 'Amazon.csv'\n", "AMAZON_SMALL_PATH = 'Amazon_small.csv'\n", "GOLD_STANDARD_PATH = 'Amazon_Google_perfectMapping.csv'\n", "STOPWORDS_PATH = 'stopwords.txt'" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 0. Operazioni preliminari ##\n", "\n", "Iniziamo creando un RDD per ciascuno dei due dataset. In essi, ogni linea fa riferimento a un prodotto, utilizzando il formato\n", "\n", " `\"id\",\"nome\",\"descrizione\",\"produttore\",\"prezzo\"`\n", "\n", "descritto nella prima linea di ogni file (che non dovrà quindi essere considerata). Va anche notato che i doppi apici fanno parte delle varie stringhe e che gli identificativi hanno una forma differente nei due dataset: sono URL per i dati di Google e codici alfanumerici per i dati di Amazon.\n", "\n", "Iniziamo costruendo degli RDD in cui gli elementi siano delle coppie in cui la chiave indica l'identificativo e il valore il resto della linea. Il parsing dei doppi apici va considerato con attenzione, perché quando un dato è mancante (come capita per esempio con il produttore) i file contengono una stringa vuota non delimitata da doppi apici. Vale quindi la pena utilizzare le virgole come punti di riferimento per costruire un'espressione regolare che indichi il formato di una linea dei file (cinque campi separati da virgola, dei quali i primi due non possono essere mancanti):" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": [ "import re\n", "DATAFILE_PATTERN = '^(.+),(.+),(.*),(.*),(.*)'" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Una volta verificato che una linea corrisponde a questa espressione regolare potremo procedere, ove serve, a eliminare i doppi apici, utilizzando la funzione che segue." ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "def remove_quotes(s):\n", " \"\"\" Remove quotation marks from an input string\n", " \n", " Args:\n", " s (str): input string that might have the quote \"\" characters\n", " \n", " Returns:\n", " str: a string without the quote characters\n", " \"\"\"\n", " return ''.join(i for i in s if i!='\"')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Siamo ora pronti a scrivere la funzione che si occuperà del parsing di una linea, verificando innanzitutto che quest'ultima segua il formato richiesto (restituendo una coppia contenente la linea e il valore speciale `-1` altrimenti) e identificando la prima riga dei file che contiene le intestazioni (restituendo una coppia contenente la linea e il valore speciale `0`). Infine i valori per i campi andranno recuperati al fine di costruire una coppia avente come chiave l'identificativo del prodotto (dopo avere eliminato i doppi apici) e come valore i restanti campi giustapposti. Tale oggetto dovrà essere restituito inserendolo come primo elemento in una coppia, il cui secondo elemento sarà il valore speciale `1`. In questo modo sarà possibile verificare quante linee dei file sono state convertite correttamente." ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [], "source": [ "def parse_datafile_line(datafile_line):\n", " \"\"\" Parse a line of the data file using the specified regular expression\n", " pattern\n", " \n", " Args:\n", " datafileLine (str): input string that is a line from the data file\n", " \n", " Returns:\n", " str: a string parsed using the given regular expression and without\n", " the quote characters\n", " \"\"\"\n", " \n", " match = re.search(DATAFILE_PATTERN, datafile_line.decode('utf-8'))\n", " if match is None:\n", " print('Invalid datafile line: {}'.format(datafile_line))\n", " return (datafile_line, -1)\n", " elif match.group(1) == '\"id\"':\n", " print('Header datafile line: {}'.format(datafile_line))\n", " return (datafile_line, 0)\n", " else:\n", " product = '%s %s %s' % (match.group(2), match.group(3), match.group(4))\n", " return ((remove_quotes(match.group(1)), product), 1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Il passo successivo è quello di definire una funzione che crei un RDD contenente un elemento per ogni linea di un file, per poi mapparvi sopra la funzione `parse_dataline_file` appena definita, mettendo in *cache* il risultato." ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [], "source": [ "def parse_data(filename):\n", " \"\"\" Parse a data file\n", " \n", " Args:\n", " filename (str): input file name of the data file\n", " \n", " Returns:\n", " RDD: a RDD of parsed lines\n", " \"\"\"\n", " \n", " return (sc\n", " .textFile(filename, 4, 0)\n", " .map(parse_datafile_line)\n", " )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "È ora possibile costruire una funzione che dato il nome di un dataset si occupa di creare il corrispondente RDD, e verifica che non vi siano stati errori di conversione. Ciò viene fatto:\n", "* costruendo l'RDD che si ottiene filtrando il numero di coppie che contengono il valore speciale `-1` e selezionando il loro primo elemento (ottenendo le linee che non sono convertibili);\n", "* stampando il contenuto di (al più) dieci linee siffatte;\n", "* costruendo l'RDD che corrisponde alle coppie che contengono il valore `0` e selezionandone il primo elemento (ovvero una coppia `(id, prodotto)` ottenuta a seguito di una conversione valida)\n", "* inserendo l'RDD dei valori convertiti in *cache*;\n", "* verificando che non siano avvenuti errori di conversione e che tutte le righe del file siano state effettivamente convertite;\n", "* restituendo l'RDD dei valori convertiti." ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [], "source": [ "def load_data(path):\n", " \"\"\" Load a data file\n", " \n", " Args:\n", " path (str): input file name of the data file\n", " \n", " Returns:\n", " RDD: a RDD of parsed valid lines\n", " \"\"\"\n", " \n", " filename = os.path.join(base_dir, path)\n", " raw = parse_data(filename).cache()\n", " \n", " failed = (raw\n", " .filter(lambda s: s[1] == -1)\n", " .map(lambda s: s[0]))\n", " \n", " for line in failed.take(10):\n", " #print('{} - Invalid datafile line: {}'.format(path, line))\n", " print(line)\n", " \n", " valid = (raw\n", " .filter(lambda s: s[1] == 1)\n", " .map(lambda s: s[0])\n", " .cache())\n", " print('{} - Read {} lines, successfully parsed {} lines, '\n", " 'failed to parse {} lines'.format(path,\n", " raw.count(),\n", " valid.count(),\n", " failed.count()))\n", " assert failed.count() == 0\n", " assert raw.count() == (valid.count() + 1)\n", " return valid" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Utilizzando le funzioni scritte si possono effettuare le conversioni dei dataset che verranno utilizzati." ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Google_small.csv - Read 201 lines, successfully parsed 200 lines, failed to parse 0 lines\n", "Google.csv - Read 3227 lines, successfully parsed 3226 lines, failed to parse 0 lines\n", "Amazon_small.csv - Read 201 lines, successfully parsed 200 lines, failed to parse 0 lines\n", "Amazon.csv - Read 1364 lines, successfully parsed 1363 lines, failed to parse 0 lines\n" ] } ], "source": [ "google_small = load_data(GOOGLE_SMALL_PATH)\n", "google = load_data(GOOGLE_PATH)\n", "amazon_small = load_data(AMAZON_SMALL_PATH)\n", "amazon = load_data(AMAZON_PATH)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Verifichiamo il contenuto di alcuni record nei due dataset convertiti:" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "google: http://www.google.com/base/feeds/snippets/11448761432933644608: \"spanish vocabulary builder\" \"expand your vocabulary! contains fun lessons that both teach and entertain you'll quickly find yourself mastering new terms. includes games and more!\" \n", "\n", "google: http://www.google.com/base/feeds/snippets/8175198959985911471: \"topics presents: museums of world\" \"5 cd-rom set. step behind the velvet rope to examine some of the most treasured collections of antiquities art and inventions. includes the following the louvre - virtual visit 25 rooms in full screen interactive video detailed map of the louvre ...\" \n", "\n", "google: http://www.google.com/base/feeds/snippets/18445827127704822533: \"sierrahome hse hallmark card studio special edition win 98 me 2000 xp\" \"hallmark card studio special edition (win 98 me 2000 xp)\" \"sierrahome\"\n", "\n", "amazon: b000jz4hqo: \"clickart 950 000 - premier image pack (dvd-rom)\" \"broderbund\"\n", "\n", "amazon: b0006zf55o: \"ca international - arcserve lap/desktop oem 30pk\" \"oem arcserve backup v11.1 win 30u for laptops and desktops\" \"computer associates\"\n", "\n", "amazon: b00004tkvy: \"noah's ark activity center (jewel case ages 3-8)\" \"victory multimedia\"\n", "\n" ] } ], "source": [ "for line in google_small.take(3):\n", " print('google: {}: {}\\n'.format(line[0], line[1]))\n", "\n", "for line in amazon_small.take(3):\n", " print('amazon: {}: {}\\n'.format(line[0], line[1]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. Codificare documenti tramite *bag of words* ##\n", "\n", "Un modo naturale di effettuare entity resolution su documenti testuali è quello di considerare ogni record come una stringa e utilizzare una distanza tra stringhe per calcolare la similiarità tra due documenti. In particolare utilizzeremo il cosiddetto approccio *bag of words*, in cui un documento testuale è codificato in termini di un insieme di parole o, meglio ancora, *token* che occorrono in esso.\n", "\n", "> **Nota**: si preferisce parlare di *token* per enfatizzare che non si tratta necessariamente di una parola, bensì di un «atomo» indivisibile che potrebbe essere una parola ma anche una sottostringa di lunghezza fissata (\\\\(k\\\\)-gramma) che occorre nel testo.\n", "\n", "I token divengono gli elementi che ci permettono di effettuare un confronto tra documenti, la cui similarità può essere espressa in termini del numero di token in comune." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.1 Estrarre token da una stringa ###\n", "\n", "Implementiamo una funzione `simple_tokenize` che data una stringa restituisce la lista dei token in essa contenuti, intesi come parole delimitate da spzi bianchi. Questa funzione utilizza opportunamente le espressioni regolari e sarà *case insensitive*, prendendosi inoltre cura di non considerare eventuali token vuoti." ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [], "source": [ "quickbrownfox = 'A quick brown fox jumps over the lazy dog.'\n", "split_regex = r'\\W+'\n", "\n", "def simple_tokenize(string):\n", " \"\"\" A simple implementation of input string tokenization\n", " Args:\n", " string (str): input string\n", " Returns:\n", " list: a list of tokens\n", " \"\"\"\n", " return [s for s in re.split(split_regex, string.lower()) if s != '']" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Verifichiamo che la funzione si comporti correttamente su un semplice caso di test, che non consideri gli spazi vuoti e che non elimini eventuali token duplicati." ] }, { "cell_type": "code", "execution_count": 51, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "['a', 'quick', 'brown', 'fox', 'jumps', 'over', 'the', 'lazy', 'dog']\n" ] } ], "source": [ "print(simple_tokenize(quickbrownfox))\n", "\n", "assert(simple_tokenize(quickbrownfox) ==\n", " ['a','quick','brown','fox','jumps','over','the','lazy','dog'])\n", "assert(simple_tokenize(' ') == [])\n", "assert(simple_tokenize('!!!!123A/456_B/789C.123A') == ['123a','456_b','789c','123a'])\n", "assert(simple_tokenize('fox fox') == ['fox', 'fox'])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.2 Eliminare le stop word ###\n", "\n", "Si indicano con il termine *stop word* le parole che appaiono comunemente nei testi scritti in una fissata lingua, e che dunque non apportano particolare contenuto informativo. Per tale motivo è opportuno eliminare tali parole prima di estrarre token da un documento. Utilizzando il file `stopwords.txt` implementiamo la funzione `tokenize` che si comporta in modo analogo a `simple_tokenize` ma che ignora le *stop word*." ] }, { "cell_type": "code", "execution_count": 54, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "These are the stopwords: {'ours', 'his', 'above', 'being', 'ourselves', 'these', 'there', 'that', 'between', 'don', 'further', 'myself', 'were', 'by', 'more', 'those', 'while', 'until', 'about', 's', 'during', 'then', 'too', 'because', 'if', 'below', 'no', 'from', 'how', 'a', 'he', 'on', 'off', 'all', 'into', 'and', 'very', 'under', 'as', 'has', 'yourself', 'only', 'her', 'other', 'yourselves', 'an', 'they', 'what', 'some', 'hers', 'them', 'had', 'down', 'the', 'itself', 'which', 'do', 'your', 'have', 'been', 'up', 'through', 'than', 'but', 'theirs', 'not', 'once', 'having', 'when', 'nor', 'him', 'whom', 'their', 'was', 'for', 'own', 'to', 'where', 'before', 'here', 'this', 'with', 'at', 'both', 'you', 'out', 'of', 'just', 'i', 'now', 'each', 'few', 'any', 'against', 'does', 'my', 'himself', 'themselves', 'over', 'me', 'yours', 'we', 'most', 'so', 'doing', 'again', 'she', 'am', 'such', 'why', 'its', 'after', 'or', 'who', 'same', 'herself', 'can', 'in', 't', 'be', 'is', 'it', 'are', 'will', 'did', 'should', 'our'}\n" ] } ], "source": [ "stopfile = os.path.join(base_dir, STOPWORDS_PATH)\n", "stopwords = set(sc.textFile(stopfile).collect())\n", "\n", "print('These are the stopwords: {}'.format(stopwords))\n", "\n", "def tokenize(string):\n", " \"\"\" An implementation of input string tokenization that excludes stopwords\n", " \n", " Args:\n", " string (str): input string\n", " \n", " Returns:\n", " list: a list of tokens without stopwords\n", " \"\"\"\n", " return [s for s in re.split(split_regex, string.lower())\n", " if s != '' and not s in stopwords]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Anche in questo caso, verifichiamo alcuni semplici test: la funzione deve eliminare le *stop word* ma considerare tutti gli altri termini." ] }, { "cell_type": "code", "execution_count": 55, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "['quick', 'brown', 'fox', 'jumps', 'lazy', 'dog']\n" ] } ], "source": [ "print(tokenize(quickbrownfox))\n", "\n", "assert(tokenize(\"Why a the?\") == [])\n", "assert(tokenize(\"Being at the_?\") == ['the_'])\n", "assert(tokenize(quickbrownfox) == ['quick','brown','fox','jumps','lazy','dog'])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.3 Estrarre i token dai dataset campionati ###\n", "\n", "Iniziamo a estrarre i token dai due dataset campionati, applicando `tokenize` a ogni elemento dell'RDD corrispondente." ] }, { "cell_type": "code", "execution_count": 56, "metadata": {}, "outputs": [], "source": [ "amazon_rec_to_token = amazon_small.map(lambda s: (s[0], tokenize(s[1])))\n", "google_rec_to_token = google_small.map(lambda s: (s[0], tokenize(s[1])))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Come prima analisi, provvediamo a contare il numero totale di token contenuti nei due dataset." ] }, { "cell_type": "code", "execution_count": 57, "metadata": {}, "outputs": [], "source": [ "def count_tokens(vendorRDD):\n", " \"\"\" Count and return the number of tokens\n", " Args:\n", " vendorRDD (RDD of (recordId, tokenizedValue)): Pair tuple of record ID to tokenized output\n", " Returns:\n", " count: count of all tokens\n", " \"\"\"\n", " return vendorRDD.map(lambda s: len(s[1])).reduce(lambda a, b: a+b)" ] }, { "cell_type": "code", "execution_count": 58, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "There are 22520 tokens in the combined datasets\n" ] } ], "source": [ "total_tokens = count_tokens(amazon_rec_to_token) + count_tokens(google_rec_to_token)\n", "print('There are {} tokens in the combined datasets'.format(total_tokens))\n", "assert(total_tokens == 22520)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.d Determinare quale documento ha più token ###\n", "\n", "Quale documento del dataset di Amazon ha il maggior numero di token? Per saperlo basta ordinare opportunamente i record." ] }, { "cell_type": "code", "execution_count": 60, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The Amazon record with ID \"b000o24l3q\" has the most tokens (1547)\n" ] } ], "source": [ "def find_biggest_record(vendorRDD):\n", " \"\"\" Find and return the record with the largest number of tokens\n", " \n", " Args:\n", " vendorRDD (RDD of (recordId, tokens)): input Pair Tuple of record ID and tokens\n", " \n", " Returns:\n", " list: a list of 1 Pair Tuple of record ID and tokens\n", " \"\"\"\n", " return vendorRDD.takeOrdered(1, key = lambda s: -1*len(s[1]))\n", "\n", "biggest_record_amazon = find_biggest_record(amazon_rec_to_token)\n", "print('The Amazon record with ID \"{}\"'\n", " ' has the most tokens ({})'.format(biggest_record_amazon[0][0],\n", " len(biggest_record_amazon[0][1])))\n", "\n", "assert(biggest_record_amazon[0][0] == 'b000o24l3q')\n", "assert(len(biggest_record_amazon[0][1]) == 1547)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Uso della misura TF.IDF ##\n", "\n", "Per migliorare la tecnica basata su *bag of words* è importante dare pesi diversi ai token contenuti in un documento, in modo da riflettere quali siano i termini più rilevanti. Un'euristica che permette di capire quali siano questi termini è la *misura TF.IDF* (Term Frequency times Inverse Document Frequency), ottenuta moltiplicando tra loro due indicatori definiti qui di seguito.\n", "\n", "### Term Frequency ###\n", "\n", "La *Term Frequency* dà maggior peso a token che tendono a occorrere più volte in uno stesso documento. Viene calcolata come la frequenza relativa del token nel documento. In altre parole, se il documento \\\\(d\\\\) contiene \\\\(100\\\\) token e tra questi il token \\\\(t\\\\) occorre in \\\\(d\\\\) cinque volte, la Term Frequency di \\\\(t\\\\) in \\\\(d\\\\) vale \\\\(\\mathrm{TF}(t, d) = \\frac{5}{100} = \\frac{1}{20}\\\\).\n", "\n", "### Inverse Document Frequency ###\n", "\n", "La *Inverse Document Frequency* dà un peso alto a token che occorrono raramente su un dataset. Dato un token \\\\(t\\\\) e un insieme di documenti \\\\(U\\\\), la Inverse Document Frequency di \\\\(t\\\\) è uguale a \\\\(\\mathrm{IDF}(t) = \\frac{N}{n(t)}\\\\), dove \\\\(N\\\\) è il numero totale di documenti in \\\\(U\\\\) e \\\\(n(t)\\\\) indica il numero di documenti in \\\\(U\\\\) che contengono \\\\(t\\\\). \n", "\n", "### TF.IDF ###\n", "\n", "La misura TF.IDF di un token \\\\(t\\\\) in un documento \\\\(d\\\\) è pari al prodotto tra la Term Frequency e la Inverse Document Frequency: \\\\(\\mathrm{TF.IDF}(t, d)= \\mathrm{TF}(t, d) \\cdot \\mathrm{IDF(t)}\\\\). Informalmente, un'elevata TF.IDF indica un token che occorre spesso in un documento ma raramente negli altri, e quindi andrà dato più peso, nel calcolo della similarità tra due documenti, al fatto che entrambi contengano un termine avente un'alto valore della misura TF.IDF." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.1 Implementare una funzione per la Term Frequency ###\n", "\n", "Implementiamo una funzione `tf` che data una lista di token restituisce un dizionario che trasforma ogni token nella corrispondente misura TF. La funzione opera nel modo seguente:\n", "\n", "* crea un dizionario vuoto;\n", "* per ogni token nella lista passata come argomento, lo aggiunge come chiave associata a \\\\(1\\\\) se già non occorre nel dizionario, altrimenti incrementa di un'unità il valore associato;\n", "* per ogni token nel dizionario, divide il valore associato per il numero totale di token nella lista passata come argomento." ] }, { "cell_type": "code", "execution_count": 61, "metadata": {}, "outputs": [], "source": [ "def tf(tokens):\n", " \"\"\" Compute TF\n", " \n", " Args:\n", " tokens (list of str): input list of tokens from tokenize\n", " \n", " Returns:\n", " dictionary: a dictionary of tokens to its TF values\n", " \"\"\"\n", " val = {}\n", " for t in tokens:\n", " if t in val:\n", " val[t] += 1\n", " else:\n", " val[t] = 1.0\n", " for t in val:\n", " val[t] /= len(tokens)\n", " return val" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Anche in questo caso, verifichiamo che la funzione `tf` passi alcuni test di base." ] }, { "cell_type": "code", "execution_count": 62, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'quick': 0.16666666666666666, 'brown': 0.16666666666666666, 'fox': 0.16666666666666666, 'jumps': 0.16666666666666666, 'lazy': 0.16666666666666666, 'dog': 0.16666666666666666}\n" ] } ], "source": [ "print(tf(tokenize(quickbrownfox)))\n", "tf_test = tf(tokenize(quickbrownfox))\n", "assert(tf_test == {'brown': 0.16666666666666666, 'lazy': 0.16666666666666666,\n", " 'jumps': 0.16666666666666666, 'fox': 0.16666666666666666,\n", " 'dog': 0.16666666666666666, 'quick': 0.16666666666666666})\n", "tf_test2 = tf(tokenize('one_ one_ two!'))\n", "assert(tf_test2 == {'one_': 0.6666666666666666, 'two': 0.3333333333333333})" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.2 Creare un corpus di documenti ###\n", "\n", "Il passo successivo è quello di creare un RDD che funga da *corpus* contenente tutti i documenti che vogliamo analizzare, e quindi sia il risultato della fusione tra il dataset di Amazon e quello di Google. Ogni elemento di questo nuovo RDD sarà una coppia contenente come chiave l'identificatore di un prodotto e come valore la sua descrizione (a seguito delle operazioni di ripulitura)." ] }, { "cell_type": "code", "execution_count": 63, "metadata": {}, "outputs": [], "source": [ "corpusRDD = google_rec_to_token.union(amazon_rec_to_token)" ] }, { "cell_type": "code", "execution_count": 64, "metadata": {}, "outputs": [], "source": [ "assert(corpusRDD.count() == 400)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.3 Implementare una funzione per l'Inverse Document Frequency ###\n", "\n", "Implementiamo una funzione `idfs` che assegna il valore di Inverse Document Frequency a ogni token che occorre in un corpus di documenti, restituendo un RDD di coppie \\\\((t, i)\\\\) dove \\\\(t\\\\) e \\\\(i\\\\) sono rispettivamente un token e il relativo valore di IDF.\n", "\n", "La funzione eseguirà i seguenti passi:\n", "\n", "* calcolare \\\\(N\\\\), il numero di documenti del corpus;\n", "* creare un RDD che per ogni documento del corpus contenga tutti i token unici che vi occorrono; in altre parole, per ogni documento sarà necessario includere ogni token una volta sola, *anche nel caso in cui esso occorra più volte nel documento*;\n", "* per ognuno dei token unici \\\\(t\\\\), contare quante volte occorre nel corpus per calcolare \\\\(n(t)\\\\) e successivamente l'Inverse Document Frequency per \\\\(t\\\\)." ] }, { "cell_type": "code", "execution_count": 65, "metadata": {}, "outputs": [], "source": [ "def idfs(corpus):\n", " \"\"\" Compute IDF\n", "\n", " Args:\n", " corpus (RDD): input corpus\n", "\n", " Returns:\n", " RDD: a RDD of (record ID, IDF value)\n", " \"\"\"\n", " \n", " N = corpus.count() * 1.0\n", " unique_tokens = corpus.map(lambda s: list(set(s[1])))\n", " token_count_pair_tuple = unique_tokens.flatMap(lambda t: [(s, 1) for s in t])\n", " token_sum_pair_tuple = token_count_pair_tuple.reduceByKey(lambda a, b: a+b)\n", " return token_sum_pair_tuple.map(lambda s: (s[0], N/s[1]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Usando la funzione `idfs` è possibile calcolare i valori IDF per tutti i token in `corpusRDD`, l'unione dei due dataset campionati, e determinare il numero di token unici." ] }, { "cell_type": "code", "execution_count": 66, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "There are 4772 unique tokens in the small datasets.\n" ] } ], "source": [ "idfs_small = idfs(corpusRDD)\n", "unique_token_count = idfs_small.count()\n", "\n", "print('There are {} unique tokens'\n", " ' in the small datasets.'.format(unique_token_count))\n", "\n", "assert(unique_token_count == 4772)\n", "token_smallest_IDF = idfs_small.takeOrdered(1, lambda s: s[1])[0]\n", "assert(token_smallest_IDF[0] == 'software')\n", "assert(abs(token_smallest_IDF[1] - 4.25531914894) < 0.0000000001)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.4 Determinare i token con i più piccoli valori IDF ###\n", "\n", "Ordinando opportunamente l'RDD che contiene i valori IDF è possibile stampare gli \\\\(11\\\\) token con i valori IDF più bassi." ] }, { "cell_type": "code", "execution_count": 67, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[('software', 4.25531914893617), ('features', 6.896551724137931), ('new', 6.896551724137931), ('use', 7.017543859649122), ('complete', 7.2727272727272725), ('easy', 7.6923076923076925), ('cd', 8.333333333333334), ('create', 8.333333333333334), ('system', 8.333333333333334), ('windows', 8.51063829787234), ('1', 8.51063829787234)]\n" ] } ], "source": [ "small_IDF_tokens = idfs_small.takeOrdered(11, lambda s: s[1])\n", "print(small_IDF_tokens)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.5 Istogramma dei valori IDF ###\n", "\n", "Possiamo ora visualizzare un istogramma dei valori IDF nel corpus, utilizzando la libreria `matplotlib`." ] }, { "cell_type": "code", "execution_count": 69, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAeoAAADFCAYAAACb4LFtAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAADJFJREFUeJzt3W2MpWdZB/D/ZUuLEbIIrYb0xW3dBmmMwWZFIoYQRCzUpWgaLZKICWEDitEYo0swBj+YVBNfQiSSRWtBhYL4QktLkPASYoLQFgpsXQsrLGEpYSWEUb+AyOWH8yxMhpnp7M50nvvM/n7J5Jznfp45c117n9n/PC/nnOruAABj+o65CwAANiaoAWBgghoABiaoAWBgghoABiaoAWBgghoABiaoAWBgghoABnbh3AUkySWXXNL79++fuwwA2BX33Xffl7r70q1sO2tQV9WhJIcOHDiQe++9d85SAGDXVNVnt7rtrIe+u/vO7j68b9++OcsAgGE5Rw0AAxPUADAwQQ0AAxPUADCwIV6eBQBz2n/krk3Xn7zlhl2q5NvZowaAgQlqABiYoAaAgQlqABiYoAaAgQlqABjYrEFdVYeq6ujKysqcZQDAsHwoBwAMzKFvABiYoAaAgQlqABiYoAaAgQlqABiYoAaAgQlqABiYoAaAgQlqABiYoAaAgQlqABiYoAaAgQlqABiYoAaAgQlqABiYoAaAgQlqABiYoAaAge14UFfVk6vqdVX1tqp6+U4/PgCcT7YU1FV1a1Wdrqpja8avr6oHq+pEVR1Jku4+3t0vS/JzSQ7ufMkAcP7Y6h71bUmuXz1QVRckeW2S5ya5NskLq+raad3zk/xLkvfsWKUAcB7aUlB39weSfHnN8FOTnOjuT3f315LcnuTGafs7uvvHkrxoJ4sFgPPNhdv43suSfG7V8qkkP1pVz0zys0kuTnL3Rt9cVYeTHE6SK6+8chtlAMDetZ2grnXGurvfn+T9D/fN3X00ydEkOXjwYG+jDgDYs7Zz1fepJFesWr48yUPbKwcAWG07e9T3JLmmqq5K8vkkNyf5hbN5gKo6lOTQgQMHtlEGsJH9R+7adP3JW27YpUqAc7XVl2e9OckHkzypqk5V1Uu6++tJXpHkXUmOJ3lrdz9wNj+8u+/s7sP79u0727oB4LywpT3q7n7hBuN3Z5MLxgCA7fEWogAwsFmDuqoOVdXRlZWVOcsAgGHNGtTOUQPA5hz6BoCBCWoAGJigBoCBuZgMAAbmYjIAGJhD3wAwMEENAAMT1AAwMBeTAcDAXEwGAANz6BsABiaoAWBgghoABiaoAWBgrvoGgIG56hsABubQNwAMTFADwMAENQAMTFADwMAENQAM7MI5f3hVHUpy6MCBA3OWwR61/8hdm64/ecsNu1QJwLnz8iwAGJhD3wAwMEENAAMT1AAwMEENAAMT1AAwMEENAAMT1AAwMEENAAObNair6lBVHV1ZWZmzDAAYlncmA4CBOfQNAAMT1AAwMEENAAMT1AAwsFk/j5q9zedBA2yfPWoAGJigBoCBCWoAGJigBoCBCWoAGJigBoCBCWoAGJhPzwKAgfn0LAAYmEPfADAwQQ0AAxPUADAwQQ0AAxPUADAwQQ0AAxPUADCwC+cugHnsP3LXputP3nLDLlUCwGbsUQPAwAQ1AAxMUAPAwAQ1AAxMUAPAwAQ1AAxMUAPAwAQ1AAxMUAPAwAQ1AAxsx4O6ql5QVa+vqrdX1XN2+vEB4HyypaCuqlur6nRVHVszfn1VPVhVJ6rqSJJ09z9190uT/FKSn9/xigHgPLLVD+W4LcmfJXnjmYGquiDJa5P8ZJJTSe6pqju6+9+mTX5nWs86fCgGAFuxpaDu7g9U1f41w09NcqK7P50kVXV7khur6niSW5K8s7s/stFjVtXhJIeT5Morrzz7ys9zgh7g/LCdc9SXJfncquVT09ivJnl2kpuq6mUbfXN3H+3ug9198NJLL91GGQCwd23n86hrnbHu7tckec02HhcAmGxnj/pUkitWLV+e5KGzeYCqOlRVR1dWVrZRBgDsXdsJ6nuSXFNVV1XVRUluTnLH2TxAd9/Z3Yf37du3jTIAYO/a6suz3pzkg0meVFWnquol3f31JK9I8q4kx5O8tbsfeORKBYDzz1av+n7hBuN3J7l7RysCAL5p1rcQdY4aADY3a1A7Rw0Am9vOy7P2rId7M5HkkX9Dka3UAMDe59OzAGBg9qjPkbfwBGA3uJgMAAY26x51d9+Z5M6DBw++dDd/rvO/ACwL56gBYGCCGgAG5mKyR4jD6wDsBBeTAcDAvDMZAAzMOWoAGJigBoCBCWoAGJigBoCBueobAAbmqm8AGJhD3wAwMEENAAMT1AAwMEENAAMT1AAwMEENAAPzOmoAGJjXUQPAwBz6BoCBCWoAGJigBoCBCWoAGJigBoCBCWoAGJigBoCBXTjnD6+qQ0kOHThwYEcfd/+Ru3b08QBgLt7wBAAG5tA3AAxMUAPAwAQ1AAxMUAPAwAQ1AAxMUAPAwKq7564hVfWfST67jYe4JMmXdqicuellXHupH72May/1o5eNfV93X7qVDYcI6u2qqnu7++DcdewEvYxrL/Wjl3HtpX70sjMc+gaAgQlqABjYXgnqo3MXsIP0Mq691I9exrWX+tHLDtgT56gBYK/aK3vUALAnCWoAGNhSB3VVXV9VD1bViao6Mnc956KqTlbVJ6rq/qq6dxp7fFW9u6o+Nd1+99x1rqeqbq2q01V1bNXYurXXwmumufp4VV03X+XfboNeXl1Vn5/m5v6qet6qda+cenmwqn5qnqrXV1VXVNX7qup4VT1QVb82jS/d3GzSy7LOzaOr6sNV9bGpn9+bxq+qqg9Nc/OWqrpoGr94Wj4xrd8/Z/2rbdLLbVX1mVVz85RpfNjn2RlVdUFVfbSq3jEtjzEv3b2UX0kuSPIfSa5OclGSjyW5du66zqGPk0kuWTP2h0mOTPePJPmDuevcoPZnJLkuybGHqz3J85K8M0kleVqSD81d/xZ6eXWS31xn22un59vFSa6anocXzN3DqvqemOS66f5jk3xyqnnp5maTXpZ1birJY6b7j0ryoenf/K1Jbp7GX5fk5dP9X07yuun+zUneMncPW+jltiQ3rbP9sM+zVTX+RpI3JXnHtDzEvCzzHvVTk5zo7k9399eS3J7kxplr2ik3JnnDdP8NSV4wYy0b6u4PJPnymuGNar8xyRt74V+TPK6qnrg7lT68DXrZyI1Jbu/ur3b3Z5KcyOL5OITu/kJ3f2S6/99Jjie5LEs4N5v0spHR56a7+3+mxUdNX53kWUneNo2vnZszc/a2JD9RVbVL5W5qk142MuzzLEmq6vIkNyT5i2m5Msi8LHNQX5bkc6uWT2XzX+BRdZJ/rqr7qurwNPa93f2FZPEfVZLvma26s7dR7cs6X6+YDtPduuoUxNL0Mh2S++Es9naWem7W9JIs6dxMh1fvT3I6ybuz2Ov/Snd/fdpkdc3f7Gdav5LkCbtb8cbW9tLdZ+bm96e5+ZOqungaG31u/jTJbyX5xrT8hAwyL8sc1Ov99bKMrzV7endfl+S5SX6lqp4xd0GPkGWcrz9P8v1JnpLkC0n+aBpfil6q6jFJ/j7Jr3f3f2226TpjQ/WzTi9LOzfd/X/d/ZQkl2ext//k9TabbofuZ20vVfWDSV6Z5AeS/EiSxyf57WnzYXupqp9Ocrq771s9vM6ms8zLMgf1qSRXrFq+PMlDM9Vyzrr7oen2dJJ/zOIX94tnDglNt6fnq/CsbVT70s1Xd39x+o/oG0len28dQh2+l6p6VBbB9rfd/Q/T8FLOzXq9LPPcnNHdX0ny/izO1z6uqi6cVq2u+Zv9TOv3ZeunaHbNql6un05XdHd/NclfZTnm5ulJnl9VJ7M4jfqsLPawh5iXZQ7qe5JcM12Vd1EWJ/TvmLmms1JV31VVjz1zP8lzkhzLoo8XT5u9OMnb56nwnGxU+x1JfnG68vNpSVbOHIYd1ZrzZz+Txdwki15unq78vCrJNUk+vNv1bWQ6V/aXSY539x+vWrV0c7NRL0s8N5dW1eOm+9+Z5NlZnHd/X5Kbps3Wzs2ZObspyXt7uoJpbhv08u+r/hisLM7prp6bIZ9n3f3K7r68u/dnkSXv7e4XZZR5eSSvVHukv7K4ivCTWZzjedXc9ZxD/VdncYXqx5I8cKaHLM51vCfJp6bbx89d6wb1vzmLw47/m8VfmC/ZqPYsDhW9dpqrTyQ5OHf9W+jlr6daP57FL+YTV23/qqmXB5M8d+761/Ty41kchvt4kvunr+ct49xs0suyzs0PJfnoVPexJL87jV+dxR8UJ5L8XZKLp/FHT8snpvVXz93DFnp57zQ3x5L8Tb51Zfiwz7M1fT0z37rqe4h58RaiADCwZT70DQB7nqAGgIEJagAYmKAGgIEJagAYmKAGgIEJagAY2P8DQZ0T3LW837gAAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "%matplotlib inline\n", "import matplotlib.pyplot as plt\n", "\n", "small_idf_values = idfs_small.map(lambda s: s[1]).collect()\n", "fig = plt.figure(figsize=(8,3))\n", "plt.hist(small_idf_values, 50, log=True)\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2.6 Implementare una funzione per il calcolo di TF.IDF ###\n", "\n", "Utilizziamo la fuzione `tf` per implementare una nuova funzione `tfidf` che, dati in ingresso una lista di token in un documento e il dizionario restituito da `idfs`, restituisce un dizionario che associa ai token nella lista il corrispondente valore della misura TF.IDF.\n", "\n", "La funzione si occuperà di\n", "* calcolare il TF per tutti i token nella lista, e\n", "* creare un dizionare in cui ogni token viene associato al proprio valore TF moltiplicato per il corrispodente valore IDF." ] }, { "cell_type": "code", "execution_count": 70, "metadata": {}, "outputs": [], "source": [ "def tfidf(tokens, idfs):\n", " \"\"\" Compute TF-IDF\n", " \n", " Args:\n", " tokens (list of str): input list of tokens from tokenize\n", " idfs (dictionary): record to IDF value\n", " \n", " Returns:\n", " dictionary: a dictionary of records to TF-IDF values\n", " \"\"\"\n", " tfs = tf(tokens)\n", " tf_idf_dict = {t: tfs[t]*idfs[t] for t in tokens}\n", " return tf_idf_dict" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Applichiamo la funzione `tfidf` al calcolo della misura TF.IDF per il prodotto di Amazon il cui ID vale `b000hkgj8k`. Tale operazione richiederà di estrarre il record corrispondente dal dataset di Amazon, nonché di convertire l'RDD che contiene i valori IFS per il corpus in un dizionario. Il primo compito si effettua facilmente applicando un'operazione di filtraggio, mentre per il secondo è possibile sfruttare l'azione `collectAsMap`." ] }, { "cell_type": "code", "execution_count": 72, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Amazon record \"b000hkgj8k\" has tokens and weights:\n", "{'autocad': 33.33333333333333, '2007': 3.5087719298245617, 'courseware': 66.66666666666666, 'customizing': 16.666666666666664, 'interface': 3.0303030303030303, 'autodesk': 8.333333333333332, 'psg': 33.33333333333333}\n" ] } ], "source": [ "recb000hkgj8k = amazon_rec_to_token.filter(lambda x: x[0] == 'b000hkgj8k').collect()[0][1]\n", "idfs_small_weights = idfs_small.collectAsMap()\n", "rec_b000hkgj8k_weights = tfidf(recb000hkgj8k, idfs_small_weights)\n", "\n", "print('Amazon record \"b000hkgj8k\" '\n", " 'has tokens and weights:\\n{}'.format(rec_b000hkgj8k_weights))\n", "\n", "assert(rec_b000hkgj8k_weights ==\n", " {'autocad': 33.33333333333333, 'autodesk': 8.333333333333332,\n", " 'courseware': 66.66666666666666, 'psg': 33.33333333333333,\n", " '2007': 3.5087719298245617, 'customizing': 16.666666666666664,\n", " 'interface': 3.0303030303030303})" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. Uso della distanza del coseno ##\n", "\n", "Una possibile distanza tra documenti è la cosiddetta *distanza del coseno*, che interpreta due oggetti come direzioni in uno spazio e calcola il coseno dell'angolo che queste direzioni formano.\n", "\n", "La prima difficoltà consiste nel codificare i documenti come direzioni nello spazio, e quindi come vettori. In realtà avendo a disposizione la tokenizzazione dei nostri documenti, possiamo pensare a uno spazio che ha una dimensione per ogni possibile token del nostro corpus: un generico documento avrà come componente nella dimensione che corrisponde a un token il corrispndente valore della misura TF.IDF (con l'ovvia estensione che se un token non occorre in un documento, allora la componente nella dimensione di tale token sarà nulla).\n", "\n", "Il secondo problema da risolvere è quello di determinare l'angolo tra due vettori, ma ciò si può fare facilmente ricordando che \\\\( a \\cdot b = \\| a \\| \\| b \\| \\cos \\theta \\\\), dove \\\\( a \\cdot b \\\\) indica il prodotto scalare tra due vettori \\\\(a\\\\) e \\\\(b\\\\), \\\\(\\theta\\\\) l'angolo tra questi vettori e \\\\(\\| a \\|\\\\) denota la norma di \\\\(a\\\\). Pertanto\n", "\n", "$$ \\mathrm{sim}(a, b) = \\cos \\theta = \\frac{a \\cdot b}{\\|a\\| \\|b\\|} = \\frac{\\sum a_i b_i}{\\sqrt{\\sum a_i^2} \\sqrt{\\sum b_i^2}} .$$\n", "\n", "Va tenuto presente che, sebbene procedendo in questo modo vi sia da considerare un elevato numero di dimensioni, i vettori possono essere memorizzati in un dizionario che contenga solo le componenti non nulle, sfruttando la proprietà di sparsità. Più precisamente, per ogni token \\\\(t\\\\) avente misura TF.IDF \\\\(i \\neq 0\\\\), in tale dizionario la chiave \\\\(t\\\\) sarà associata al valore \\\\(i\\\\)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.1 Implementare prodotto scalare e norma per vettori sparsi ###\n", "\n", "Usando le funzioni `tokenize` e `tfidf` e sfruttando la rappresentazione sparsa in dizionari è possibile:\n", "\n", "* definire una funzione `dotprod` che riceve come argomenti i dizionari che descrivono due vettori sparsi e che restituisce il corrispondente prodotto scalare (che in questo caso sarà uguale alla somma dei prodotti dei valori corrispondenti a chiavi che occorrono in *entrambi* i dizionari);\n", "* definire una funzione `norm` che restituisce la norma di un vettore sparso passato tramite il corrispondente dizionario (calcolandola come la radice quadrata del prodotto scalare del vettore con se stesso);\n", "* definire una funzione `cossim` that restituisca la distanza del coseno tra i due vettori sparsi specificati come argomenti, sfruttando la formula sopra riportata e le funzioni definite ai punti precedenti." ] }, { "cell_type": "code", "execution_count": 73, "metadata": {}, "outputs": [], "source": [ "import math\n", "\n", "def dotprod(a, b):\n", " \"\"\" Compute dot product\n", " \n", " Args:\n", " a (dictionary): first dictionary of record to value\n", " b (dictionary): second dictionary of record to value\n", " \n", " Returns:\n", " dotProd: result of the dot product with the two input dictionaries\n", " \"\"\"\n", " \n", " return sum([a[t] * b[t] for t in a if t in b])\n", "\n", "def norm(a):\n", " \"\"\" Compute square root of the dot product\n", " \n", " Args:\n", " a (dictionary): a dictionary of record to value\n", " \n", " Returns:\n", " norm: a dictionary of tokens to its TF values\n", " \"\"\"\n", " return math.sqrt(dotprod(a, a))\n", "\n", "def cossim(a, b):\n", " \"\"\" Compute cosine similarity\n", " \n", " Args:\n", " a (dictionary): first dictionary of record to value\n", " b (dictionary): second dictionary of record to value\n", " \n", " Returns:\n", " cossim: dot product of two dictionaries divided by the norm of the first dictionary and\n", " then by the norm of the second dictionary\n", " \"\"\"\n", " return dotprod(a, b)/(norm(a) * norm(b))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Anche in questo caso, verifichiamo il comportamento di queste funzione tramite semplici test." ] }, { "cell_type": "code", "execution_count": 74, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "102 6.164414002968976\n" ] } ], "source": [ "testVec1 = {'foo': 2, 'bar': 3, 'baz': 5 }\n", "testVec2 = {'foo': 1, 'bar': 0, 'baz': 20 }\n", "dp = dotprod(testVec1, testVec2)\n", "nm = norm(testVec1)\n", "print(dp, nm)\n", "assert(dp == 102)\n", "assert(abs(nm - 6.16441400297) < 0.0000001)" ] }, { "cell_type": "code", "execution_count": 75, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.8262970212292282" ] }, "execution_count": 75, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cossim(testVec1, testVec2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.2 Implementare una funzione per il calcolo della similarità ###\n", "\n", "Possiamo ora implementare una funzione `cosine_similarity` che, date due stringhe che descrivono documenti e un dizionario per i valori IDF in un corpus, calcola e restituisce la distanza del coseno tra i corrispondenti vettori nello spazio dei token. I passi necessari sono:\n", "\n", "* tokenizzare le due stringhe e successivamente utilizzarle unitamente al dizionario per invocare la funzione `tfidf`, e\n", "* invocare la funzione `cossim` e restituirne il risultato." ] }, { "cell_type": "code", "execution_count": 76, "metadata": {}, "outputs": [], "source": [ "def cosine_similarity(string1, string2, idfs_dictionary):\n", " \"\"\" Compute cosine similarity between two strings\n", " \n", " Args:\n", " string1 (str): first string\n", " string2 (str): second string\n", " idfsDictionary (dictionary): a dictionary of IDF values\n", " \n", " Returns:\n", " cossim: cosine similarity value\n", " \"\"\"\n", " \n", " w1 = tfidf(tokenize(string1), idfs_dictionary)\n", " w2 = tfidf(tokenize(string2), idfs_dictionary)\n", " return cossim(w1, w2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "È quindi ora possibile verificare la similarità tra due prodottti, date le loro descrizioni:" ] }, { "cell_type": "code", "execution_count": 77, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.05772433821630337\n" ] } ], "source": [ "cossimAdobe = cosine_similarity('Adobe Photoshop',\n", " 'Adobe Illustrator',\n", " idfs_small_weights)\n", "\n", "print(cossimAdobe)\n", "assert(abs(cossimAdobe - 0.0577243382163) < 0.0000001)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.3 Esecuzione della procedura di entity resolution ###\n", "\n", "Gli strumenti realizzati ci consentono ora di effettuare la procedura di entity resolution: per ogni prodotto nel dataset di Google possiamo calcolare la distanza del coseno rispetto a tutti i prodotti nel dataset di Amazon. In particolare procederemo come segue:\n", "\n", "* creeremo un RDD che contenga tutte le coppie di prodotti nei due dataset, ottenendo come generico elemento la tupla `((Google URL, Google String), (Amazon ID, Amazon String))`;\n", "* definiremo poi una funzione che accetti una siffatta tupla come argomento e restituisca la distanza del coseno tra i due prodotti ivi contenuti;\n", "* applicheremo infine tale funzione a tutti gli elementi del RDD creato al primo punto." ] }, { "cell_type": "code", "execution_count": 78, "metadata": {}, "outputs": [], "source": [ "cross_small = (google_small\n", " .cartesian(amazon_small)\n", " .cache())\n", "\n", "def compute_similarity(record):\n", " \"\"\" Compute similarity on a combination record\n", " \n", " Args:\n", " record: a pair, (google record, amazon record)\n", " \n", " Returns:\n", " pair: a pair, (google URL, amazon ID, cosine similarity value)\n", " \"\"\"\n", " \n", " google_rec = record[0]\n", " amazon_rec = record[1]\n", " google_URL = google_rec[0]\n", " amazon_ID = amazon_rec[0]\n", " google_value = google_rec[1]\n", " amazon_value = amazon_rec[1]\n", " \n", " cs = cosine_similarity(google_value, amazon_value, idfs_small_weights)\n", " return (google_URL, amazon_ID, cs)\n", "\n", "similarities = (cross_small\n", " .map(lambda r: compute_similarity(r))\n", " .cache())\n", "\n", "def similar(amazon_ID, google_URL):\n", " \"\"\" Return similarity value\n", " \n", " Args:\n", " amazon_ID: amazon ID\n", " google_URL: google URL\n", " \n", " Returns:\n", " similar: cosine similarity value\n", " \"\"\"\n", " \n", " return (similarities\n", " .filter(lambda record: (record[0] == google_URL and record[1] == amazon_ID))\n", " .collect()[0][2])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Siamo ora in grado di visualizzare, per esempio, il grado di similarità tra il prodotto di Amazon avente ID `b000o24l3q` e il prodotto di Google avente URL `http://www.google.com/base/feeds/snippets/17242822440574356561`." ] }, { "cell_type": "code", "execution_count": 79, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Requested similarity is 0.00030317194045132.\n" ] } ], "source": [ "similarity_Amazon_Google = \\\n", " similar('b000o24l3q',\n", " 'http://www.google.com/base/feeds/snippets/17242822440574356561')\n", "print('Requested similarity is {}.'.format(similarity_Amazon_Google))\n", "assert(abs(similarity_Amazon_Google - 0.000303171940451) < 0.0000001)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Il grado di similarità è basso: verifichiamo che i documenti corrispondenti siano effettivamente diversi, visualizzando i primi \\\\(300\\\\) caratteri di entrambi:" ] }, { "cell_type": "code", "execution_count": 80, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'adobe premiere pro cs3 upgrade note upgrade version adobe premiere pro cs3 tell story maximum impact using adobe premiere pro cs3 upgrade software start finish solution efficient video production includes adobe encore cs3 adobe onlocation cs3 windows formerly award winning dv rack hd save time set c'" ] }, "execution_count": 80, "metadata": {}, "output_type": "execute_result" } ], "source": [ "' '.join(amazon_rec_to_token.filter(lambda p: p[0]=='b000o24l3q')\n", " .take(1)[0][1])[:300]" ] }, { "cell_type": "code", "execution_count": 81, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'diana ross supremes yamaha best diana ross supremes smart pianosoft innovative software series enables disklavier mark iii piano perform world popular cds using yamaha pianosmart technology companion diskette magically empower disklavier mark iii accompany'" ] }, "execution_count": 81, "metadata": {}, "output_type": "execute_result" } ], "source": [ "' '.join(google_rec_to_token.filter( \\\n", " lambda p: p[0]=='http://www.google.com/base/feeds/snippets/17242822440574356561').take(1)[0][1])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Effettivamete si trtta di due documenti differenti: probabilmente da un lato del software, dall'altro della musica. Le cose sono diverse per i documenti `b00004tkvy` e `http://www.google.com/base/feeds/snippets/18441110047404795849`:" ] }, { "cell_type": "code", "execution_count": 82, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Requested similarity is 0.7330499385794952.\n" ] } ], "source": [ "similarity_Amazon_Google = similar('b00004tkvy', 'http://www.google.com/base/feeds/snippets/18441110047404795849')\n", "print('Requested similarity is {}.'.format(similarity_Amazon_Google))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In questo caso la similarità è elevata, e infatti i documenti hanno in comune molti termini:" ] }, { "cell_type": "code", "execution_count": 83, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'noah ark activity center jewel case ages 3 8 victory multimedia'" ] }, "execution_count": 83, "metadata": {}, "output_type": "execute_result" } ], "source": [ "' '.join(amazon_rec_to_token.filter(lambda p: p[0]=='b00004tkvy')\n", " .take(1)[0][1])[:300]" ] }, { "cell_type": "code", "execution_count": 84, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'beginners bible noah ark activity center activity center'" ] }, "execution_count": 84, "metadata": {}, "output_type": "execute_result" } ], "source": [ "' '.join(google_rec_to_token.filter(lambda p: p[0]=='http://www.google.com/base/feeds/snippets/18441110047404795849')\n", " .take(1)[0][1])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.4 Utilizzo di variabili broadcast ###\n", "\n", "La soluzione del Paragrafo 3.3 funziona efficacemente quando si utilizzano dataset di piccole dimensioni. Vi è però un problema di efficienza nel momento in cui l'esecuzione della funzione `compute_similarity` viene distribuita tramite `map` su diversi nodi del cluster. In questo caso infatti il dizionario `idfs_small_weights` dovrebbe venire distribuito a tutti i nodi (più volte se si invoca `similar` ripetutamente).\n", "\n", "In casi come questi ha senso utilizzare una funzionalità specifica di Spark chiamata *variabile broadcast*, cioè una variabile definita nel programma driver a cui i worker possono fare riferimento: una siffatta variabile viene inviata una sola volta ai vari worker, che la salvano localmente.\n", "\n", "Iniziamo a definire una variabile broadcast per il dizionario `idfs_small_weights`, invocando la funzione `broadcast` sullo spark context." ] }, { "cell_type": "code", "execution_count": 85, "metadata": {}, "outputs": [], "source": [ "idfs_small_broadcast = sc.broadcast(idfs_small_weights)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ora è possibile definire una funzione `compute_similarity_broadcast`, analoga di `computeSimilarity` ma che utilizza la variabile broadcast." ] }, { "cell_type": "code", "execution_count": 86, "metadata": {}, "outputs": [], "source": [ "def compute_similarity_broadcast(record):\n", " \"\"\" Compute similarity on a combination record, using a\n", " Broadcast variable\n", " \n", " Args:\n", " record: a pair, (google record, amazon record)\n", " \n", " Returns:\n", " a tuple (google URL, amazon ID, cosine similarity value)\n", " \"\"\"\n", " \n", " googleRec = record[0]\n", " amazonRec = record[1]\n", " \n", " googleURL = googleRec[0]\n", " amazonID = amazonRec[0]\n", " \n", " googleValue = googleRec[1]\n", " amazonValue = amazonRec[1]\n", " \n", " cs = cosine_similarity(googleValue, amazonValue,\n", " idfs_small_broadcast.value)\n", " return (googleURL, amazonID, cs)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Procedendo come nella parte precedente possiamo applicare questa funzione a tutte le coppie di prodotti e successivamente definire una funzione che filtri i record ottenuti al fine di valutare la similarità tra due specifici documenti." ] }, { "cell_type": "code", "execution_count": 87, "metadata": {}, "outputs": [], "source": [ "similarities_broadcast = (cross_small\n", " .map(lambda r: compute_similarity_broadcast(r))\n", " .cache())\n", "\n", "def similar_broadcast(amazon_ID, google_URL):\n", " \"\"\" Return similarity value, computed using Broadcast variable\n", " \n", " Args:\n", " amazon_ID: amazon ID\n", " google_URL: google URL\n", " \n", " Returns:\n", " similar: cosine similarity value\n", " \"\"\"\n", " return (similarities_broadcast\n", " .filter(lambda record: (record[0] == google_URL and record[1] == amazon_ID))\n", " .collect()[0][2])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Per verificare che tutto sia andato a buon fine, ricalcoliamo la similarità tra il documento `b000o24l3q` e il documento `http://www.google.com/base/feeds/snippets/17242822440574356561`." ] }, { "cell_type": "code", "execution_count": 88, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Requested similarity is 0.00030317194045132.\n" ] } ], "source": [ "similarity_amazon_google_broadcast = similar_broadcast('b000o24l3q', 'http://www.google.com/base/feeds/snippets/17242822440574356561')\n", "print('Requested similarity is {}.'.format(similarity_amazon_google_broadcast))\n", "\n", "from pyspark import Broadcast\n", "assert(isinstance(idfs_small_broadcast, Broadcast))\n", "assert(len(idfs_small_broadcast.value) == 4772)\n", "assert(abs(similarity_amazon_google_broadcast - 0.000303171940451) < 0.0000001)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 3.5 Valutare le performance ###\n", "\n", "Il file `Amazon_Google_perfectMapping.csv` contiene un insieme di corrispondenze tra prodotti nei due dataset che si sanno essere simili. Questo tipo di informazione, cui si fa riferimento utilizzando i termini *ground truth* o *gold standard*, può essere utilizzata per valutare la bontà della procedura di entity resolution.\n", "\n", "Iniziamo leggendo il file contenente la ground truth e creiamo il corrispondente RDD, i cui elementi avranno come formato `(\"AmazonID GoogleURL\", 'gold')`. Utilizzeremo a tal scopo una funzione il cui comportamento è simile alla funzione `parse_datafile_line` utilizzata nel Paragrafo 0." ] }, { "cell_type": "code", "execution_count": 90, "metadata": {}, "outputs": [], "source": [ "GOLDFILE_PATTERN = '^(.+),(.+)'\n", "\n", "def parse_goldfile_line(goldfile_line):\n", " \"\"\" Parse a line from the 'golden standard' data file\n", " \n", " Args:\n", " goldfile_line: a line of data\n", " \n", " Returns:\n", " pair: ((key, 'gold'), 1) if successful or else\n", " (goldfile_line, 0) when fed with the heading\n", " line and (goldfile_line, -1) when a parsing error\n", " occurs\n", " \"\"\"\n", " \n", " match = re.search(GOLDFILE_PATTERN, goldfile_line)\n", " \n", " if match is None:\n", " print('Invalid goldfile line: {}'.format(goldfile_line))\n", " return (goldfile_line, -1)\n", " \n", " elif match.group(1) == '\"idAmazon\"':\n", " print('Header datafile line: {}'.format(goldfile_line))\n", " return (goldfile_line, 0)\n", " \n", " else:\n", " key = '%s %s' % (remove_quotes(match.group(1)),\n", " remove_quotes(match.group(2)))\n", " return ((key, 'gold'), 1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Usando lo stesso approccio utilizzato per leggere i dataset campionati è possibile mappare la fuzione `parse_goldfile_line` su tutte le linee del file contenente la ground truth e successivamente estrarre dai risultati il RDD relativo a eventuali errori di parsing e quello contenente i dati convertiti, verificando successivamente che non sia avvenuto alcun errore di parsing, e che tutti i dati siano stati considerati." ] }, { "cell_type": "code", "execution_count": 92, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Read 1301 lines, successfully parsed 1300 lines, failed to parse 0 lines\n" ] } ], "source": [ "goldfile = os.path.join(base_dir, GOLD_STANDARD_PATH)\n", "\n", "gs_raw = (sc\n", " .textFile(goldfile)\n", " .map(parse_goldfile_line)\n", " .cache())\n", "\n", "gs_failed = (gs_raw\n", " .filter(lambda s: s[1] == -1)\n", " .map(lambda s: s[0]))\n", "\n", "for line in gs_failed.take(10):\n", " print('Invalid goldfile line: {}'.format(line))\n", "\n", "gold_standard = (gs_raw\n", " .filter(lambda s: s[1] == 1)\n", " .map(lambda s: s[0])\n", " .cache())\n", "\n", "print('Read {} lines, successfully parsed {} lines, '\n", " 'failed to parse {} lines'.format(gs_raw.count(),\n", " gold_standard.count(),\n", " gs_failed.count()))\n", "\n", "assert (gs_failed.count() == 0)\n", "assert (gs_raw.count() == (gold_standard.count() + 1))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Utilizzando la *ground truth* possiamo capire quante coppie di oggetti nei dataset campionati siano effettivamente simili e calcolare il corrispondente valor medio per l'indice di similarità.\n", "\n", "Per fare questo, iniziamo creando un RDD `sims` ottenuto da `similarities_broadcast`, in cui ogni elemento ha come formato `(\"AmazonID GoogleURL\", cosineSimilarityScore)`" ] }, { "cell_type": "code", "execution_count": 93, "metadata": {}, "outputs": [], "source": [ "sims = similarities_broadcast.map(lambda r: (r[1] + ' ' + r[0], r[2]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Effettuando un'operazione di join tra gli RDD `sims` e `gold_standard` è possibile costruire un RDD `true_dups_RDD` che contiene i valori di similarità per le coppie di documenti che abbiamo analizzato e che fanno parte della *ground truth*. Da questo nuovo RDD è immediato ottenere il numero di tali coppie." ] }, { "cell_type": "code", "execution_count": 94, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "There are 146 true duplicates.\n" ] } ], "source": [ "true_dups_RDD = (sims\n", " .join(gold_standard))\n", "\n", "true_dups_count = true_dups_RDD.count()\n", "\n", "print('There are {} true duplicates.'.format(true_dups_count))\n", "assert(true_dups_count == 146)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Il passo successivo consiste nel calcolare il valore medio dell'indice di similarità per le coppie di documenti che sappiamo essere simili, estraendolo opportunamente da `true_dups_RDD`." ] }, { "cell_type": "code", "execution_count": 95, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The average similarity of true duplicates is 0.2643325734351914.\n" ] } ], "source": [ "avg_sim_dups = float(sum(true_dups_RDD.map(lambda s: s[1][0])\n", " .collect())) / true_dups_count\n", "\n", "print('The average similarity of true duplicates is {}.'.format(avg_sim_dups))\n", "assert(abs(avg_sim_dups - 0.264332573435) < 0.0000001)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Possiamo calcolare la media dell'indice di similarità anche per le coppie di documenti nei dataset campionati che invece sappiamo **non** essere simili (in quanto le coppie corrispondenti non sono elencate nel file contenente la *ground truth*). Il RDD che contiene gli identificativi di tali coppie e la corrispondente similarità si ottiene facilmente considerando la differenza simmetrica tra i RDD `sims` e `gold_standard`, utilizzando la funzione `subtractByKey`." ] }, { "cell_type": "code", "execution_count": 96, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "And for non duplicates, it is 0.0012347630465555188.\n" ] } ], "source": [ "non_dups_RDD = (sims\n", " .subtractByKey(gold_standard))\n", "\n", "avg_sim_non = float(sum(non_dups_RDD.map(lambda s: s[1])\n", " .collect())) / non_dups_RDD.count()\n", "\n", "print('And for non duplicates, it is {}.'.format(avg_sim_non))\n", "assert(abs(avg_sim_non - 0.00123476304656) < 0.0000001)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 4. Entity resolution scalabile ##\n", "\n", "Nei paragrafi precedenti abbiamo costruito una funzione per il calcolo della similarità tra testi e l'abbiamo utilizzata per effettuare della entity resolution su piccola scala. L'implementazione soffre di una complessità temporale quadratica, cosa che la rende inefficiente anche per dataset di dimensione modesta. In questo paragrafo implementeremo un algoritmo più efficiente, al fine di applicarlo all'intero dataset.\n", "\n", "Per aumentare l'efficienza dell'algoritmo usato finora è opportuno analizzarne la complessità temporale. In particolare, questo algoritmo è quadratico per due motivi. Innanzitutto abbiamo eseguito in modo ridondante molti calcoli quando ci siamo occupati di token e pesi, in quanto ogni record veniva ricalcolato ogni volta che effettuavamo un confonto. Inoltre, abbiamo effettuato un numero quadratico di confronti tra record.\n", "\n", "La prima fonte di complessità quadratica può essere eliminata precalcolando i valori e memorizzandoli, ma la seconda fonte è più difficile da trattare. Nel caso peggiore, ogni token in ogni record di un dataset esisterà in ogni record dell'altro dataset, e quindi ogni token avrà un contributo non nullo nel calcolo del coefficiente di similarità. In realtà la maggior parte dei record hanno molto poco (se non nulla) in comune. Inoltre è tipico che ogni record in un dataset abbia al massimo un duplicato nel rimanente dataset. In casi come questo l'output è lineare nella dimensione dell'input e si può sperare di avere anche un tempo di esecuzione che sia lineare.\n", "\n", "La struttura dati che ci pemetterà di effettuare un numero quadratico di confronti si chiama *indice inverso*, e mappa ogni token nel dataset nella lista dei documenti che lo contengono. Utilizzando questa struttura dati, invece di confrontare due record token per token, è possibile semplicemente *cercare* quali record contengano un token specifico." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4.1 Estrazione dei token ###\n", "\n", "Iniziamo estraendo i token dai dataset completi di Google e Amazon." ] }, { "cell_type": "code", "execution_count": 97, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Amazon full dataset is 1363 products, Google full dataset is 3226 products\n" ] } ], "source": [ "amazon_full_rec_to_token = amazon.map(lambda s: (s[0], tokenize(s[1])))\n", "google_full_rec_to_token = google.map(lambda s: (s[0], tokenize(s[1])))\n", "print('Amazon full dataset is {} products, '\n", " 'Google full dataset is {} '\n", " 'products'.format(amazon_full_rec_to_token.count(),\n", " google_full_rec_to_token.count()))\n", "\n", "assert(amazon_full_rec_to_token.count() == 1363)\n", "assert(google_full_rec_to_token.count() == 3226)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4.2 Calcolo della misura TF-IDF ###\n", "\n", "Possiamo riutilizzare il codice già scritto per calcolare i valori IDF per i dataset completi. Iniziamo creando un RDD `full_corpus_RDD` che unisca i due dataset, e applichiamo a questo RDD la funzione `idfs`" ] }, { "cell_type": "code", "execution_count": 99, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "There are 17078 unique tokens in the full datasets.\n" ] } ], "source": [ "full_corpus_RDD = amazon_full_rec_to_token.union(google_full_rec_to_token)\n", "idfs_full = idfs(full_corpus_RDD)\n", "idfs_full_count = idfs_full.count()\n", "print('There are {} unique tokens '\n", " 'in the full datasets.'.format(idfs_full_count))\n", "assert(idfs_full_count == 17078)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Si continua sempre in modo analogo, trasformando il RDD con i valori IDF in un dizionario e generando una variabile broadcast a partire da quest'ultimo." ] }, { "cell_type": "code", "execution_count": 100, "metadata": {}, "outputs": [], "source": [ "# Recompute IDFs for full dataset\n", "idfs_full_weights = idfs_full.collectAsMap()\n", "idfs_full_broadcast = sc.broadcast(idfs_full_weights)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Il passo successivo consiste nel riutilizzare la funzione `tfidfs` assieme alla variabile broadcast, al fine di ottenere dei RDD che associno gli identificativi dei prodotti alle relativo dizionario che mappa i token alla corrispondente misura TF.IDF." ] }, { "cell_type": "code", "execution_count": 102, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "There are 1363 Amazon weights and 3226 Google weights.\n" ] } ], "source": [ "# Pre-compute TF-IDF weights. Build mappings from record ID weight vector.\n", "amazon_weights_RDD = amazon_full_rec_to_token.map(\n", " lambda s: (s[0], tfidf(s[1], idfs_full_broadcast.value)))\n", "google_weights_RDD = google_full_rec_to_token.map(\n", " lambda s: (s[0], tfidf(s[1], idfs_full_broadcast.value)))\n", "\n", "print('There are {} Amazon weights '\n", " 'and {} Google weights.'.format(amazon_weights_RDD.count(),\n", " google_weights_RDD.count()))\n", " \n", "assert(amazon_weights_RDD.count() == 1363)\n", "assert(google_weights_RDD.count() == 3226) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4.3 Calcolo delle norme per i vettori delle misure TF.IDF ###\n", "\n", "Per implementare in modo efficiente la procedura di entity resolution nei dataset completi, creiamo due RDD i cui elementi sono coppie che contengono l'identificativo di un documento e la norma del corrispondente vettore di misure TF.IDF. Tali RDD vanno poi convertiti in dizionari e utilizzati per ottenere delle variabili broadcast." ] }, { "cell_type": "code", "execution_count": 103, "metadata": {}, "outputs": [], "source": [ "amazon_norms = amazon_weights_RDD.map(lambda s: (s[0], norm(s[1])))\n", "amazon_norms_broadcast = sc.broadcast(amazon_norms.collectAsMap())\n", "\n", "google_norms = google_weights_RDD.map(lambda s: (s[0], norm(s[1])))\n", "google_norms_broadcast = sc.broadcast(google_norms.collectAsMap())\n", "\n", "assert(isinstance(amazon_norms_broadcast, Broadcast))\n", "assert(len(amazon_norms_broadcast.value) == 1363)\n", "assert(isinstance(google_norms_broadcast, Broadcast))\n", "assert(len(google_norms_broadcast.value) == 3226)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4.4 Creazione di indici inversi per i dataset completi ###\n", "\n", "Per creare gli indici inversi è necessario innanzitutto scrivere una funzione `invert` che data una coppia `(id, vettore di valori TF.IDF)` restituisce una lista di coppie `(token, id)`, ricordando che il vettore dei valori TF.IDF è memorizzato in modo sparso come dizionario che mappa i token ai valori.\n", "\n", "La funzione `invert` può quindi essere utilizzata per convertire i dataset completi nei corrispondenti indici inversi." ] }, { "cell_type": "code", "execution_count": 104, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "There are 111386 Amazon inverted pairs and 77678 Google inverted pairs.\n" ] } ], "source": [ "def invert(record):\n", " \"\"\" Invert (ID, tokens) to a list of (token, ID)\n", " \n", " Args:\n", " record: a pair, (ID, token vector)\n", " \n", " Returns:\n", " pairs: a list of pairs of token to ID\n", " \"\"\"\n", " \n", " pairs = [(f, record[0]) for f in record[1]]\n", " return pairs\n", "\n", "amazon_inv_pairs_RDD = (amazon_weights_RDD\n", " .flatMap(lambda r: invert(r))\n", " .cache())\n", "\n", "google_inv_pairs_RDD = (google_weights_RDD\n", " .flatMap(lambda r: invert(r))\n", " .cache())\n", "\n", "print('There are {} Amazon inverted pairs '\n", " 'and {} Google inverted pairs.'.format(amazon_inv_pairs_RDD.count(),\n", " google_inv_pairs_RDD.count()))\n", "\n", "inverted_pair = invert((1, {'foo': 2}))\n", "assert(inverted_pair[0][1] == 1)\n", "assert(amazon_inv_pairs_RDD.count() == 111386)\n", "assert(google_inv_pairs_RDD.count() == 77678)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4.5 Identificare token in comune nei dataset completi ##\n", "\n", "È ora possibile eseguire in modo efficiente la procedura di entity resolution sui dataset completi. L'operazione iniziale consiste nel costruire un RDD che ha come chiave una coppia `(ID, URL)` e come corrispondente valore la lista di token comuni nelle descrizioni dei corrispondenti prodotti. Per fare questo è necessario:\n", "\n", "* utilizzare i due indici inversi (RDD i cui elementi sono coppie che come primo elemento hanno un token e come secondo elemento l'ID o l'URL di un documento che contiene tale token) per creare un nuovo RDD che si riferisce solo ai token contenuti in entrambi i dataset, e il cui generico elemento è una coppia avente in prima posiizone un token e in seconda un iteratore di coppie `(ID, URL)`;\n", "* creare un nuovo RDD ottenuto invertendo gli elementi delle coppie ottenute al punto precedente;\n", "* creare un RDD che permetta di mappare le coppie `(ID, URL)` nella lista dei token comuni corrispondenti." ] }, { "cell_type": "code", "execution_count": 105, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Found 2441100 common tokens\n" ] } ], "source": [ "def swap(record):\n", " \"\"\" Swap (token, (ID, URL)) to ((ID, URL), token)\n", " \n", " Args:\n", " record: a pair, (token, (ID, URL))\n", " \n", " Returns:\n", " pair: ((ID, URL), token)\n", " \"\"\"\n", " token = record[0]\n", " keys = record[1]\n", " return (keys, token)\n", "\n", "common_tokens = (amazon_inv_pairs_RDD\n", " .join(google_inv_pairs_RDD)\n", " .map(lambda r: swap(r))\n", " .groupByKey()\n", " .cache())\n", "\n", "print('Found {} common tokens'.format(common_tokens.count()))\n", "\n", "assert(common_tokens.count() == 2441100)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A questo punto è possibile utilizzare le strutture dati create per costruire un dizionario che trasformi le coppie `(ID, URL)` nella corrispondenza misura di similarità basata sulla distanza del coseno, eseguendo i passi che seguono.\n", "\n", "* Creazione di due dizionari broadcast a partire dai RDD `amazon_weights_RDD` e `google_weights_RDD`;\n", "* Implementazione di un afunzione `fast_cosine_similarity` che accetta come argomento un record ((Amazon ID, Google URL), tokens list) e calcola il prodotto scalare corrispondente per poi dividerlo per la norma dei vettori che descrivono i due documenti coinvolti; la funzione dovrà restituire una coppia che ha il risultato ottenuto come valore e la coppia `(Amazon ID, Google URL)` come chiave;\n", "* Applicazione di `fast_cosines_similarity` ai token comuni ai due dataset completi." ] }, { "cell_type": "code", "execution_count": 115, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2441100\n" ] } ], "source": [ "amazon_weights_broadcast = sc.broadcast( \\\n", " amazon_weights_RDD.collectAsMap())\n", "google_weights_broadcast = sc.broadcast( \\\n", " google_weights_RDD.collectAsMap())\n", "\n", "def fast_cosine_similarity(record):\n", " \"\"\" Compute Cosine Similarity using Broadcast variables\n", " \n", " Args:\n", " record: ((ID, URL), token)\n", " \n", " Returns:\n", " pair: ((ID, URL), cosine similarity value)\n", " \"\"\"\n", " \n", " amazon_rec = record[0][0]\n", " google_rec = record[0][1]\n", " tokens = record[1]\n", " s = sum([amazon_weights_broadcast.value[amazon_rec][t] * \\\n", " google_weights_broadcast.value[google_rec][t]\n", " for t in tokens])\n", " value = s / (amazon_norms_broadcast.value[amazon_rec] * \\\n", " google_norms_broadcast.value[google_rec])\n", " key = (amazon_rec, google_rec)\n", " return (key, value)\n", "\n", "similarities_full_RDD = (common_tokens\n", " .map(lambda r: fast_cosine_similarity(r))\n", " .cache())\n", "\n", "print(similarities_full_RDD.count())\n", "\n", "g_URL = 'http://www.google.com/base/feeds/snippets/13823221823254120257'\n", "\n", "item_filter = lambda id_url_cs: id_url_cs[0][0] == 'b00005lzly' \\\n", " and id_url_cs[0][1] == g_URL\n", "\n", "similarity_test = similarities_full_RDD.filter(item_filter).collect()\n", "assert(len(similarity_test) == 1)\n", "assert(abs(similarity_test[0][1] - 4.286548414e-06) < 0.000000000001)\n", "assert(similarities_full_RDD.count() == 2441100)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 5. Analisi ##\n", "\n", "Ora che abbiamo un modo di associare a una coppia di documenti la similarità corrispondente, dobbiamo stabilire come utilizzare questa informazione per decidere quando una coppia di prodotti individua un duplicato. Il modo più semplice di procedere è quello di utilizzare una soglia: le coppie di record con un valore di similarità superiore verranno segnalate come duplicati, mentre i prodotti in quelle rimanenti saranno dichiarati come distinti.\n", "\n", "Per decidere a quale valore impostare questa soglia è necessario realizzare come essa influenzi tipi di errori differenti. Se la soglia è troppo bassa si otterranno infatti dei cosiddetti *falsi positivi*, che corrispondono a record dichiarati duplicati ma che nella realtà sono distinti. Dualmente, se la soglia è troppo alta aumenterà il numero di *falsi negativi*, intesi come record duplicati che non vengono rilevati.\n", "\n", "Valuteremo la procedura di entity resolution utilizzando due metriche tipiche del campo dell'information retrieval, chiamate *precision* e *recall*:\n", "\n", "* il valore di *precision* indica qual è la frazione dei record dichiarati come duplicati che lo sono effettivamente, mentre\n", "\n", "* il valore di *recall* indica qual è la frazione di record duplicati che vengono effettivamente rilevati.\n", "\n", "Siccome queste due metriche tendono ad assumere valori opposti, per misurare la bontà si utilizza una terza metrica detta *F-measure*, ottenuta calcolando la media armonica di *precision* e *recall*. Indicando rispettivamente con \\\\(p\\\\), \\\\(r\\\\) e \\\\(F\\\\) i valori di *precision*, *recall* e di questa nuova metrica si ha cioè\n", "\n", "$$ F = 2 \\frac{p \\cdot r}{p + r} $$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 5.1 Conteggio di veri positivi, falsi positivi e falsi negativi ##\n", "\n", "Per calcolare il numero di coppie duplicate dobbiamo:\n", "\n", "* creare `sims_full_RDD` a partire da `similarities_full_RDD`, in modo da considerare solo le coppie (ID, URL) e i valori di similarità;\n", "* estrarre da questo RDD i soli valori di similarità.\n", "\n", "Per ottenere i valori di similarità per i le coppie duplicate basterà effettuare una left outer join tra `gold_standard` e `sims_full_RDD` per poi estrarre la seconda componente." ] }, { "cell_type": "code", "execution_count": 117, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "There are 1300 true duplicates.\n" ] } ], "source": [ "# Create an RDD of ((Amazon ID, Google URL), similarity score)\n", "sims_full_RDD = similarities_full_RDD.map( \\\n", " lambda x: ('{} {}'.format(x[0][0], x[0][1]), x[1]))\n", "assert (sims_full_RDD.count() == 2441100)\n", "\n", "# Create an RDD of just the similarity scores\n", "sims_full_values_RDD = (sims_full_RDD\n", " .map(lambda x: x[1])\n", " .cache())\n", "\n", "assert(sims_full_values_RDD.count() == 2441100)\n", "\n", "# Look up all similarity scores for true duplicates\n", "\n", "# This helper function will return the similarity score\n", "# for records that are in the gold standard and the simsFullRDD\n", "# (True positives), and will return 0 for records that are\n", "#in the gold standard but not in simsFullRDD (False Negatives).\n", "\n", "def gs_value(record):\n", " if (record[1][1] is None):\n", " return 0\n", " else:\n", " return record[1][1]\n", "\n", "# Join the gold standard and simsFullRDD, and then extract\n", "# the similarities scores using the helper function\n", "\n", "true_dup_sims_RDD = (gold_standard\n", " .leftOuterJoin(sims_full_RDD)\n", " .map(gs_value)\n", " .cache())\n", "print('There are {} true duplicates.'.format(true_dup_sims_RDD.count()))\n", "assert(true_dup_sims_RDD.count() == 1300)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Il passo successivo consiste nel fissare una soglia tra \\\\(0\\\\) e \\\\(1\\\\) per il conteggio dei veri positivi (coppie duplicate il cui valore di similarità è superiore alla soglia). Vogliamo però sperimentare con differenti valori per la soglia, e per fare questo dividiamo lo spazio \\\\([0, 1]\\\\) in cui può variare la soglia in \\\\(100\\\\) intervalli e procediamo come segue:\n", "\n", "* utilizziamo gli *accumulatori* di Spark per implementare una funizone di conteggio; in particolare definiamo il tipo `VectorAccumulatorParam`, che comprende funzioni per inizializzare a zero il valore di un vettore di accumulatori e per addizionare due vettori; va notato come potremo utilizzare solo l'operatore `+=` in quanto è solo possibile aggiungere valori a un accumulatore;\n", "* scriviamo una funzione che crei una lista con un unico valore non nullo;\n", "* creiamo \\\\(101\\\\) contenitori per i possibili valori della soglia tra \\\\(0\\\\) e \\\\(1\\\\);\n", "* per ogni punteggio di similarità possiamo calcolare il numero di falsi positivi, sommando i valori di similarità al contenitore appropriato, per poi eliminare i veri positivi utilizzando i dati nel gold standard;\n", "* definiamo in questo modo funzioni per calcolare il numero di falsi positivi, falsi negativi e veri positivi per un dato valore della soglia." ] }, { "cell_type": "code", "execution_count": 120, "metadata": { "scrolled": false }, "outputs": [], "source": [ "from pyspark.accumulators import AccumulatorParam\n", "\n", "class VectorAccumulatorParam(AccumulatorParam):\n", " # Initialize the VectorAccumulator to 0\n", " def zero(self, value):\n", " return [0] * len(value)\n", "\n", " # Add two VectorAccumulator variables\n", " def addInPlace(self, val1, val2):\n", " for i in range(len(val1)):\n", " val1[i] += val2[i]\n", " return val1\n", "\n", "# Return a list with entry x set to value\n", "# and all other entries set to 0\n", "def set_bit(x, value, length):\n", " bits = []\n", " for y in range(length):\n", " if (x == y):\n", " bits.append(value)\n", " else:\n", " bits.append(0)\n", " return bits\n", "\n", "# Pre-bin counts of false positives\n", "# for different threshold ranges\n", "\n", "BINS = 101\n", "nthresholds = 100\n", "\n", "def bin(similarity):\n", " return int(similarity * nthresholds)\n", "\n", "# fpCounts[i] = number of entries (possible false positives)\n", "# where bin(similarity) == i\n", "\n", "zeros = [0] * BINS\n", "fpCounts = sc.accumulator(zeros, VectorAccumulatorParam())\n", "\n", "def add_element(score):\n", " global fpCounts\n", " b = bin(score)\n", " fpCounts += set_bit(b, 1, BINS)\n", "\n", "sims_full_values_RDD.foreach(add_element)\n", "\n", "# Remove true positives from FP counts\n", "def sub_element(score):\n", " global fpCounts\n", " b = bin(score)\n", " fpCounts += set_bit(b, -1, BINS)\n", "\n", "true_dup_sims_RDD.foreach(sub_element)\n", "\n", "def falsepos(threshold):\n", " fpList = fpCounts.value\n", " return sum([fpList[b] for b in range(0, BINS)\n", " if float(b) / nthresholds >= threshold])\n", "\n", "def falseneg(threshold):\n", " return true_dup_sims_RDD.filter( \\\n", " lambda x: x < threshold).count()\n", "\n", "def truepos(threshold):\n", " return true_dup_sims_RDD.count() - falsenegDict[threshold]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 5.2 Precision, Recall, e F-measure ###\n", "\n", "Possiamo ora definire delle funzioni che ci permettono di calcolare i valori di precision, recall e F-measure in funzione del valore di soglia." ] }, { "cell_type": "code", "execution_count": 121, "metadata": {}, "outputs": [], "source": [ "# Precision = true-positives / (true-positives + false-positives)\n", "# Recall = true-positives / (true-positives + false-negatives)\n", "# F-measure = 2 x Recall x Precision / (Recall + Precision)\n", "\n", "def precision(threshold):\n", " tp = trueposDict[threshold]\n", " return float(tp) / (tp + falseposDict[threshold])\n", "\n", "def recall(threshold):\n", " tp = trueposDict[threshold]\n", " return float(tp) / (tp + falsenegDict[threshold])\n", "\n", "def fmeasure(threshold):\n", " r = recall(threshold)\n", " p = precision(threshold)\n", " return 2 * r * p / (r + p)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 5.3 Grafici di precision, recall e F-measure ###\n", "\n", "Utilizzando le funzioni definite nel paragrafo precedente è possibile visualizzare l'andamento di precision, recall e F-measure in funzione del valore della soglia." ] }, { "cell_type": "code", "execution_count": 122, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.0005325468026709271 0.0010645266950540452\n" ] }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvIxREBQAAIABJREFUeJzs3Xd4VFX+x/H3Te+9ENIJgZCQBgmEIqCAFGkigqIoioJdcS3ouiu/XV17Q3FdREUEBUQBUTrSawg9hBRKeu89k5nz++NCBA0khCSTcl7PkyfMzJ17v0H85M65536PIoRAkiRJ6lgM9F2AJEmS1PxkuEuSJHVAMtwlSZI6IBnukiRJHZAMd0mSpA5IhrskSVIHJMNdkiSpA5LhLkmS1AHJcJckSeqAjPR1YCcnJ+Hj46Ovw0uSJLVLMTExeUII54a201u4+/j4cOTIEX0dXpIkqV1SFCW5MdvJYRlJkqQOSIa7JElSByTDXZIkqQPS25i7JEntm0ajIS0tjaqqKn2X0iGZmZnh4eGBsbFxk94vw12SpCZJS0vD2toaHx8fFEXRdzkdihCC/Px80tLS8PX1bdI+GhyWURTla0VRchRFOX2N1xVFURYoipKkKMpJRVH6NKkSSZLalaqqKhwdHWWwtwBFUXB0dLypT0WNGXNfAoy+zutjAP9LX7OB/za5GkmS2hUZ7C3nZv9uGwx3IcRuoOA6m0wElgrVQcBOURS3m6rqelIOwrb5IJcHlCRJuqbmmC3jDqRe8Tjt0nN/oSjKbEVRjiiKciQ3N7dpR8s4Dns/gor8pr1fkqQOw9DQkLCwMHr37s3dd99NRUXFTe/zyJEjPPPMM9d8PSMjgylTptz0cVpac4R7fZ8d6j2tFkIsEkJECCEinJ0bvHu2fvbe6vfCRt2kJUlSB2Zubs7x48c5ffo0JiYmfPHFF1e9LoRAp9Pd0D4jIiJYsGDBNV/v2rUrq1evblK9rak5wj0N8LzisQeQ0Qz7rZ+9j/q98EKLHUKSpPbnlltuISkpiYsXL9KrVy+eeOIJ+vTpQ2pqKlu2bGHAgAH06dOHu+++m7KyMgCio6MZOHAgoaGh9OvXj9LSUnbu3Mm4ceMA2LVrF2FhYYSFhREeHk5paSkXL16kd+/egHpR+aGHHiI4OJjw8HB27NgBwJIlS5g8eTKjR4/G39+fl156qdX/PppjKuQvwFOKoqwA+gPFQojMZthv/ey81O9F8sxdktqK/1sfy5mMkmbdZ2BXG14fH9SobWtra9m4cSOjR6tzP+Lj4/nmm2/4/PPPycvL44033mDbtm1YWlryzjvv8OGHHzJv3jymTZvGypUriYyMpKSkBHNz86v2+/7777Nw4UIGDRpEWVkZZmZmV72+cOFCAE6dOsXZs2e5/fbbSUhIAOD48eMcO3YMU1NTevbsydNPP42npyetpcFwVxTlB2AY4KQoShrwOmAMIIT4AtgAjAWSgArgoZYqFgATS7B0gcKLLXoYSZLavsrKSsLCwgD1zH3WrFlkZGTg7e1NVFQUAAcPHuTMmTMMGjQIgJqaGgYMGEB8fDxubm5ERkYCYGNj85f9Dxo0iOeff5777ruPyZMn4+HhcdXre/fu5emnnwYgICAAb2/vunAfPnw4tra2AAQGBpKcnNy2wl0IcW8DrwvgyWarqDHsfWS4S1Ib0tgz7OZ2ecz9zywtLev+LIRg5MiR/PDDD1dtc/LkyQanG86bN4877riDDRs2EBUVxbZt2646exfXmbVnampa92dDQ0Nqa2sb/HmaU/vsLWPvLS+oSpLUKFFRUezbt4+kpCQAKioqSEhIICAggIyMDKKjowEoLS39SwCfO3eO4OBgXn75ZSIiIjh79uxVrw8ZMoTly5cDkJCQQEpKCj179myFn6ph7TTcfaA4DbSt+5tQkqT2x9nZmSVLlnDvvfcSEhJCVFQUZ8+excTEhJUrV/L0008TGhrKyJEj/3JH6Mcff0zv3r0JDQ3F3NycMWPGXPX6E088gVarJTg4mGnTprFkyZKrztj1Sbnex4qWFBERIZq8WMfR7+CXp+DZE3/MnpEkqVXFxcXRq1cvfZfRodX3d6woSowQIqKh97bfM3eQ4+6SJEnXIMNdkiSpA2qf4W7TFQyM5UVVSZKka2if4W5gCHae8sxdkiTpGtpnuAPYecu7VCVJkq6h/Ya7vJFJkiTpmtp3uFfkQ3WpviuRJElPrmz5O378eIqKipp1/0uWLOGpp54CYP78+bz//vvNuv+W1I7DXbb+laTO7sqWvw4ODnWNvKR2He4+6nc5NCNJEjBgwADS09PrHr/33ntERkYSEhLC66+/Xvf80qVLCQkJITQ0lBkzZgCwfv16+vfvT3h4OCNGjCA7O7vV629uzdHyVz/sLp25y4uqkqR/G+dB1qnm3WeXYBjzdqM21Wq1bN++nVmzZgGwZcsWEhMTOXz4MEIIJkyYwO7du3F0dOTNN99k3759ODk5UVCgriA6ePBgDh48iKIoLF68mHfffZcPPvigeX+eVtZ+w93cHkxt5Zm7JHVil1v+Xrx4kb59+zJy5EhADfctW7YQHh4OQFlZGYmJiZw4cYIpU6bg5OQEgIODAwBpaWlMmzaNzMxMampq8PX11c8P1Izab7grCth7yXCXpLagkWfYze3ymHtxcTHjxo1j4cKFPPPMMwgheOWVV5gzZ85V2y9YsKDeNr9PP/00zz//PBMmTGDnzp3Mnz+/lX6CltN+x9zh0nRIOSwjSZ2dra0tCxYs4P3330ej0TBq1Ci+/vrruuX00tPTycnJYfjw4axatYr8/HyAumGZ4uJi3N3dAfj222/180M0s/Z75g5quCduBSHUM3lJkjqt8PBwQkNDWbFiBTNmzCAuLo4BAwYAYGVlxbJlywgKCuLvf/87Q4cOxdDQkPDwcJYsWcL8+fO5++67cXd3JyoqigsX2v8aze2z5e9l0Yvht7/B3Fiw9Wh4e0mSmo1s+dvyOl/L38vc1LUTSY/Rbx2SJEltTPsO9y4hYGQGKYf0XYkkSVKb0r7D3cgEuvaB1IP6rkSSJKlNad/hDuDVHzJPQE2FviuRJElqM9p/uHtGga4WMo7quxJJkqQ2owOEez/1e6ocd5ckSbqsfc9zB7BwAKee8qKqJHVChoaGBAcH1z1eu3YtPj4++iuoDWn/4Q7q2XvcetDpwKD9fxiRJKlxLrcfaE+0Wi2GhoYtfpyOkYReUVBVBHkJ+q5EkqQ2ZtiwYcydO5chQ4bQq1cvoqOjmTx5Mv7+/rz22mt12y1btox+/foRFhbGnDlz0Gq1ADz++ONEREQQFBR0VevgefPmERgYSEhICC+88AIAM2fOZPXq1XXbWFlZAbBz505uvfVWpk+fXvdJ41rHay4d5Mw9Sv2eeghcAvRbiyR1Qu8cfoezBWebdZ8BDgG83O/l625zuSskgK+vL2vWrKl3OxMTE3bv3s0nn3zCxIkTiYmJwcHBAT8/P+bOnUtOTg4rV65k3759GBsb88QTT7B8+XIeeOAB3nzzTRwcHNBqtQwfPpyTJ0/i4eHBmjVrOHv2LIqiNGoFqMOHD3P69Gl8fX2Ji4u75vGaS8cId0c/sHBUw73vg/quRpKkVtLYYZkJEyYAEBwcTFBQEG5ubgB069aN1NRU9u7dS0xMDJGRkYD6S8PFxQWAVatWsWjRImpra8nMzOTMmTMEBgZiZmbGI488wh133MG4ceMarKFfv351rYS3b99+zeM1l44R7ooCnv0hRd7MJEn60NAZdmt66KGHOHbsGF27dmXDhg0AmJqaAmBgYFD358uPa2trEULw4IMP8tZbb121rwsXLvD+++8THR2Nvb09M2fOpKqqCiMjIw4fPsz27dtZsWIFn332Gb///jtGRkbodDoAhBDU1NTU7cvS0rLuz9c6XnNq1Ji7oiijFUWJVxQlSVGUefW87qUoyg5FUY4pinJSUZSxzV9qAzz7Q8E5KMtt9UNLktR2fPPNNxw/frwu2Btj+PDhrF69mpycHEBtBZycnExJSQmWlpbY2tqSnZ3Nxo0bAXXxj+LiYsaOHcvHH39c9+nBx8eHmBi119W6devQaDQ3dLzm1OCZu6IohsBCYCSQBkQrivKLEOLMFZu9BqwSQvxXUZRAYAPg06yVNsR3iPo9cQuE39eqh5YkqX0LDAzkjTfe4Pbbb0en02FsbMzChQuJiooiPDycoKAgunXrxqBBgwAoLS1l4sSJVFVVIYTgo48+AuDRRx9l4sSJ9OvXj+HDh191tt6Y43l7ezfbz9Rgy19FUQYA84UQoy49fgVACPHWFdv8DzgvhHjn0vYfCCEGXm+/zdLy90pCwCch4BwA9/3YfPuVJKlesuVvy2vplr/uQOoVj9MuPXel+cD9iqKkoZ61P92I/TYvRYHAiXBuB1Q2fOVakiSpI2tMuNe3xNGfT/fvBZYIITyAscB3iqL8Zd+KosxWFOWIoihHcnNbYGw88E7QaSC+8WNtkiRJHVFjwj0N8LzisQeQ8adtZgGrAIQQBwAzwOnPOxJCLBJCRAghIpydnZtW8fW49wFbTzizrvn3LUnSX+hrJbfO4Gb/bhsT7tGAv6IovoqimAD3AL/8aZsUYDiAoii9UMO99aet1A3N/A5Vxa1+eEnqTMzMzMjPz5cB3wKEEOTn52NmZtbkfTQ4W0YIUasoylPAZsAQ+FoIEasoyr+AI0KIX4C/AV8qijIXdchmptDXf/HASXDgM4jfCKH36KUESeoMPDw8SEtLo0WGWCXMzMzw8Gj62tDte4Hs+ggBH/WGLsEwfUXz71+SJEmPOscC2fWpG5rZLodmJEnqtDpeuIMa7toaSNyq70okSZL0omOGu0eE2kgsYbO+K5EkSdKLjhnuBobgPwqStoK2Vt/VSJIktbqOGe4APUZBZSGkReu7EkmSpFbXccPd7zYwMIKETfquRJIkqdV13HA3swHvQXLcXZKkTqnjhjtAj9GQGweFF/VdiSRJUqvq4OE+Sv0uz94lSepkOna4O/qBo78cd5ckqdPp2OEO6tn7xb1QXarvSiRJklpNJwj30fJuVUmSOp2OH+7eA8HGHY4t03clkiRJrabjh7uBIYTPUHu8Fzbv6uKSJEltVccPd4Dw+9Vukce+03clkiRJraJzhLudJ3QfoQ7NyF4zkiR1Ap0j3AH6PAilmZC4Rd+VSJIktbjOE+49RoFVF4hZou9KJEmSWlznCXdDYwi/T20DXJyu72okSZJaVOcJd4A+D6hrrEYv1nclkiRJLapzhbu9D/QaD9FfQVWJvquRJElqMZ0r3AEGz4XqYoj5Rt+VSJIktZjOF+7ufaDbMDiwEDRV+q5GkqQ2qry6lqKKGn2X0WRG+i5ALwbPhaUT4cQPEPGQvquRJKmNqKnVsSM+h19OZLA9LptarWByH3ceH9YdXydLfZd3QzpnuPsOha7hsO8T9SKrgaG+K5IkSc+0OsHMbw6z/1w+DpYmTOnrgYLCyiOprI5JY7C/M11tzbC3NKG7sxWTwt0xNFD0XfY1dc5wVxQY/DysmgFn1kHvyfquSJIkPfvf7nPsP5fPP8YF8sAAb4wN1VHrp4d356s9F9iVkMvZzBIKK2rQaAVrj6fz0bQwnKxM9Vx5/RQhhF4OHBERIY4cOaKXYwOg08Gn4WrHyIc26K8OSZJa3YW8ckyNDOhqZw7AqbRi7vx8H7cHubJweh8U5dpn5EIIVkan8vovsdiaG7Pg3nCiujm2VukoihIjhIhoaLvOd0H1MgMD6DsTkvdBbry+q5EkqRlUabR8uCWehOxrL86z6XQWoz/ezdD3dvDKz6dIyinl2ZXHcLIy5T93Bl832AEUReGefl6sfXIQVqZGzPjqEKkFFc39o9y0zhvuAGH3g4ExHJHTIiWpvdPqBM+tOM6C35OY9W00xRWav2yzZN8FHl8eQ2BXG6ZFevJTTBojPtzN+dxyPpgaip2FSaOP18vNhmWP9KdWJ/jxSGqj37fqSCqF5S0/C6dzh7uVs3pT04nvQVOp72okSWoiIQT/WHeaTbFZTO/vRWZRFS+sPsHlYecqjZb/Wx/L/PVnGNnLle8fieKNScHsfHEYDw3y4Z/jAhnU3emGj9vVzpwh/s6sjklDq2t4iPt4ahEvrT7Jz8davgVK5w53gIiHoaoYYtfouxJJkppACMHH2xL5/lAKjw314z93BjNvTABbz2SzeM8FYpILuGPBHr7Zd5GZA3347/19MTdRZ8h1tTPn9fFBPDzYt8nHnxbpSUZxFXuT8hrcdtHuc9iYGTEt0rPJx2usRoW7oiijFUWJVxQlSVGUedfYZqqiKGcURYlVFOX75i2zBfkMBkd/OTQjSe1QRlEljy6N4ZPtidzVx4OXR/cEYNZgX0YHdeHtTWeZ8sUBqjQ6lj7cj/kTgpp9+uLwXi7YWxizqoGhmeT8cjadzuK+KG+sTFt+omKDR1AUxRBYCIwE0oBoRVF+EUKcuWIbf+AVYJAQolBRFJeWKrjZKYp6I9PmVyHrNHTpre+KJElqgE4n+PbARd7fHI9OwKtjA3h4kG/dxVBFUXj37hAe/fYIvdxseHFUTyxbKFBNjQyZFO7O8oMpFJbXYG9Z/7j9V3svYGig8NBAnxap488ac+beD0gSQpwXQtQAK4CJf9rmUWChEKIQQAiR07xltrDQe8HQFA59oe9KJKnTyyurZtPpTLKK628Pkl1SxYyvD/F/688Q4ePAlrlDmD3EDyPDq+PMxsyYlXMGMH9CUIsF+2XTIj2p0epYe7z+sfSC8hpWHUllUpg7LjZmLVrLZY35id2BKz9vpAH9/7RNDwBFUfYBhsB8IcSmP+9IUZTZwGwALy+vptTbMiwcoO+DcORrGPKC2j1SkqQWIYRgZ0IuC39PIru0itm3dGNapBfGhgo/HU3n37+eobhSnenSw9WKgX5O9HC1xtfJksKKGv6+5hRVGh3v3BXM1AjPBqcutoaALjaEeNiyMjqVmQN9/lLTdweSqdLomD2kW6vV1Jhwr+9v7s+XhY0Af2AY4AHsURSltxCi6Ko3CbEIWATqTUw3XG1LGvw8xHwLu9+DiQv1XY0kdSgarY74rFKOpRaxKjqVU+nFdLU1o4utGf9YF8sXu87j6WDOwfMFRHjb88xwf85mlbAnMY8V0SlUaXR1+wp0s2HBveF0d7HS40/0V9MiPfn7mtP8eCSNqVdcMC2u1LD0wEVuC3DB39W61eppTLinAVde2vUAMurZ5qAQQgNcUBQlHjXso5ulytZg46bOnDm8SA16Rz99VyRJ7V5ZdS3zf4nl15MZdQHt7WjB25ODmdzHA2NDhd2JeXywJZ4zGSX8e2IQ9/X3xsBAYUgPZ2YP8UOnE2QUV3I+t5ziSg23B7liatT2+kHd3deTTaezmPfzSWwtjBkV1IWs4ioe/PowJVUanry1e6vW02D7AUVRjIAEYDiQjhrY04UQsVdsMxq4VwjxoKIoTsAxIEwIkX+t/eq9/UB9SrPhk1AIuhPu/K++q5Gkdi0hu5THl8VwIa+ce/p50d/XgXBPezwdzNvEUEpLKK+uZfriQ8RllvCvCUF8+nsSxZUa/jejb5Pm0den2doPCCFqgaeAzUAcsEoIEasoyr8URZlwabPNQL6iKGeAHcCL1wv2NsvaFSJnwckVkJek72okqd1adzydiZ/to7hSw7JH+vOfO4OZGOaOl6NFhw12AEtTI5bMjMTbwYJ5P5+iulbHitlRzRbsN6LzNg67lrIc+DgEeo6Gu5fouxpJapPyyqr54VAKPx9LJ9DNhtfG9cLN1hyNVsebv8WxZP9FIn3s+Wx6H1xbaXZIW5JVXMUXu87x8CBfvBwtmnXfjT1zl+Fen51vw8634MFfwfcWfVcjSW2GRqtj/i+x/HgkjRqtjn4+DpxIK8LIQOHJ27rze1wOR5ILeXiQL6+MDahrmys1n8aGe+fs596QQc/C8eWw8SWYsxsMjfVdkSTpnRCCf66L5YfDKUzv78XDg3zp7mJFakEF/1x3mnc3xWNubMgn94QxMcxd3+V2ejLc62NsDqPfhhXTIXoxRD2u74okSe++2nuBHw6n8MQwP14aHVD3vKeDBV/PjGRvUh5d7czxc25bUxQ7K/mZ6Vp6joXuI2DHf9RxeEnq4C7klfNTTBoF9bSj3R6XzZsb4hgd1IUXbu/5l9cVReEWf2cZ7G2IPHO/FkWB0e/A51Gw4UX14moHvsovdU4VNbUsP5jCLycyOJVeDICliSGzBvsya3A3YjOKWX00jd9OZtK7qy0fTgvFoA2vGyr9QYb79Th1h9v+Dtvmw+73YeiL+q5I6kSqNFpOpRdzKq2YuMwS4rNLsTYzIsrXkQF+joR62l11wVKrEyzafZ6Y5ELCPG2J8HEgzNMOM+P6b/iJzSjm6R+OcT63nBAPW167oxehnnYs2XeRBb8n8dmOJHQCrE2NuDPcnedv74GFiYyM9kLOlmmIELD2cTjxA0z5Ri6m3YEJIRqcg11apSG/rAbvFpqvXVRRw3cHktmTmMfxtCJqatW7Oh0tTQhwsya/rIazWeoScu525swd2YM7w90pqqjhuZXH2ZOYh7udOelF6uIzVqZq7/CZA33wdFCn5FVptKw4nMJ/NpzFzsKYj6eFMfBP87BjM4r5KSadUE9bRgV1ueYvCKn1yamQzam2Gr6dAJnHYeYG8Oir74qkZpZbWs3Mbw5joCj8c3wgkT4Oda8JIYhJLmRFdCq/ncykUqPFzsKYvl72hHjY4etsia+jJb7Olk3u011coeGrvef5et9FymtqCfGwo5+PPZGXzr6drU3rfpkUlNew/1we/9t1nlPpxfR0taa4UkNBRQ3/NyGIeyI9Ka7UEJNcyPoTGfx6MhOdEIR42JFbWk1GcSVCwG0BLrw3JQRHK9Nm+TuUWocM9+ZWngdf3gZaDTy+T+0kKXUIWcVVTF98kMyiKuwsjMksrmJSWFcGdXfiwPl8DpzLJ7O4CksTQyaEdaW3uy0nUouISS7kXG553X6MDRVG9HJlaqQnQ/ydG1wUorC8ht/P5rAtLptdCblU1GgZG9yFZ4f3oGeXhhtM6XSCDacz+WBLAkIIPpveh97utn/ZLrO4kiX7L3I0uRAPewu8HS3o5WbD7YGuHfpu0Y5KhntLyDgOi0dAj1EwbZm8wNoBpBVWcN/iQ+SVVvPNQ/3o7W7D5zvOsWj3eWq0OhwsTRjQzZGhPZ25I9jtL33BK2u0JBeUczGvguiLBaw5lk5BeQ3udub8e1IQtwW41nvcvYl5PLI0miqNDhdrU4b3cmVGlDeBXW1u+GcQQqATNPsKQ1LbJMO9pez/FLa8BuM+UrtISu2SRqtjxeEUPt6WSI1Wx7cP96OPl33d61nFVRRXavB3sbqh2SE1tTq2xWXzybZE4rNLuauPB/8cF4itxR83wh1NKeT+xYfwcrDgnbtCCHa3lTNQpEaT4d5SdDpYfhckH4DZO8EloKF3SG2IEILNsVm8symeC3nl9PN14F8TgwjocuNnzNdTXavl0+1J/HfXORwsTbgn0pMJoV3RCsHULw5gb2nCj48NwMW68/VdkW6ODPeWVJoN/x0Ils4wazOY/XWcU2p7skuqeG3tabaeyaaHqxUvjw7gtgCXFh13PpVWzLubz7IvKQ+dABNDA+wtjVn92MC62SuSdCNkuLe087tg2WTwHgT3rQaj+hfFlfRHCEFRhYYL+eUcTS7kk+2J1NTqeOH2njw0yOcva262pJzSKjaczOTg+QL+dnuPVl2RR+pYZLi3huM/wNrHIOQeuPMLeYG1jUgtqGD5oRR+OppGbml13fP9fR14564QfJws9VidJN0c2RWyNYTdC8VpsOMNsPWA4f/Qd0WdjhCCC3nlxGeVkphTxrGUQnYm5KIAI3q50s/XAZ9Lc9C7OVnKqX9SpyHD/WYNeQGKU2DP++DSC4Kn6LuiTqFKo2X9iQyWHkiu64kC4OVgwRPD/Jje3xt3O3M9VihJ+iXD/WYpCoz9APISYd1T4OQPbqH6rqrD0ukE3x9O4YMt8RRWaOjuYsXr4wOJ8HbAz8VS9j6RpEvk/wnNwcgEpi6FRcNgxX3w6A6wctZ3VR3O+dwy5v18isMXChjQzZGnh3dnQDdHOdQiSfWQ4d5crFzUu1a/GQOrHoD7fwITOdXtZuSUVrHpdBaJ2WUk5ZQRk1KImZEB704J4e6+HjLUJek6ZLg3J/c+MHEh/PSIOk1y+ko5B74JNFodS/Zd5JPtiZRV12JtakR3VyvuifTkqdu6yxt/JKkRZLg3t+ApoBjAz4/Ct+Ph/p/B0qnh90mUVmnYeiabhTuSOJdbzq09nXllbC/8XazkWbok3SAZ7i2h92QwsYJVM+CbsfDwpk7dRTK/rJoNpzJZfzKTkkoNHvYWeDqYY29hghCgFYL4rBJ2xOdSU6vD18mSrx6MYHiv+ptuSZLUMBnuLaXH7eq4+3eTYeX9MGNtp7qLNbe0mq1nstkUm8W+pDy0OkFPV2s8HSxIK6xg/7k8Kmq0ddu7WJsyvZ8X40PdCPe0l420JOkmyXBvST6D1TH4nx+B3+bChM86/F2sZzJKeGtjHHuT8hACfBwtmD2kGxPDul7VnEsIQa1OYKgoKApy2EWSmpkM95YWcjfkJcDud8GpBwx6Vt8VNZlOJ0gpqMDEyAAHS5Orll4rqqjhw60JLDuYjJ2FCc8O92d07y70dLWuN7gVRcHYUAa6JLUUGe6tYdgrkJ8IW18HU+t21Qc+taCCzbFZHDxfQPTFAoorNXWvmRoZoCig0Qq0OoGBAjOivHl+ZM+r+pdLktT6ZLi3BgMDmPRfqCmHX+dCVQkMfk7fVV1TcaWGtcfSWXc8naMpRQD4OlkyOqgL4V52CNR1PIsrNSiAsaEBJkYGjAx0pZdb8/ZFlySpaWS4txZjc5i2HNbMgW2vQ1Ux3PYaGLSdVeXP55axZP9FVsekUVGjJaCLNS+N7sn4kK6y97gktTMy3FuTkQnctVgdmtn7IcT+DFFPQNh9YGrVqqXodIJT6cXsO5dHbHoJpzOKSc6vwMTQgAlhXZk50KfexZYlSWofGtXPXVGU0cAngCGwWAjx9jW2mwIwwlLAAAAgAElEQVT8CEQKIa7brL1D9HNvKiEg7hc4sBBSD6l3sd71FfiPbNHD1mp1HDifz4ZTWWyPyybnUq9zLwcLervbEOphx+Q+Hjhbm7ZoHZIkNV2z9XNXFMUQWAiMBNKAaEVRfhFCnPnTdtbAM8ChppXciSgKBE5Uv1Kj4bfnYcV0tTdNj1HNfriE7FK+P5TCryczySurxtLEkGE9XRgR6MLQHi44WHae+feS1Fk0ZlimH5AkhDgPoCjKCmAicOZP2/0beBd4oVkr7Og8I+HBX2DpJLWj5LTvoOeYZtl1Uk4pH29L5LdTmRgbGjA8wIWJYV0Z1tPlqmmMkiR1PI0Jd3cg9YrHaUD/KzdQFCUc8BRC/Kooigz3G2VuDw+sg+/uhJUzYMw76nTJG7yx50RqEbsScrmYX87FvHKOpRZhbmzI40P9ePSWbtjLM3RJ6jQaE+71JUzdQL2iKAbAR8DMBnekKLOB2QBeXl6Nq7CzMLeDGWvgx5nqME3CJvWOVuuG+6totDoWbE9k4Y4kdALcbM3wdlRXJHp4kC+OVnIMXZI6mwYvqCqKMgCYL4QYdenxKwBCiLcuPbYFzgFll97SBSgAJlzvomqnvqB6PTodRH8JW/8JxhYw9j3ofdc1z+JT8it4ZsUxjqcWMaWvB/8cH4iNmbyBSJI6qsZeUDVoxL6iAX9FUXwVRTEB7gF+ufyiEKJYCOEkhPARQvgAB2kg2KXrMDCA/nNgzh6w94GfZsEP90Bx+l823RKbxR0L9nAut4xP7w3n/btDZbBLkgQ0ItyFELXAU8BmIA5YJYSIVRTlX4qiTGjpAjst5x7wyDYY9R+4sBsW9oezvwGg1Qne3XSW2d/F4ONkyYZnbmF8aFc9FyxJUlvSqHnuLUEOyzReVV486WsewTknkaq7fua5PQbsP5fPvf08eX18kJz5IkmdSLPNc5dajkanYUfKDrYkb0EIgbmROWZGZlTVVlFaU0qpppS00jQyyzPBBAzcnfDf9QgplQOZdlskA/y07EzPwNHMES9rL5wtnDFQGjPSJklSRyfDvZXohI7kkmTyKvPIr8wnsSiRtYlryanMwcXcBSsTKypqK6iqrcLMyAwrYytsTGzo69oXV3MPdpzWkp1/HHOr/WjsDrEh8xAbMq8+hpmhGaHOoUztOZVbvW7F2ECOv0tSZyXDvQWV1ZSxNXkrBzIOcDDzIIXVhVe9Psh9EP/s+U8Guw/G8BoNxC7klTPr22hSCyp4Zcx4Zjonolk5jeKu4VSPeZsqC3tyK3NJLUnlYslFfk/5nb/t+hvO5s4M8RiClbEVFsYWOJk70dupN/72/jL0JakTkGPuLaC0ppTlccv57sx3lNSU4GTuxMCuA4lwjcDNyg0nMyecLZyxNb1+Y679SXk8vvwoBgp8cX9f+ndzVF+IXQPrngIDI7WVcMDYuvdodVr2pu9lRfwKzuSfobK2ksrayrrXzQzNCHQMJNQ5lBDnEMJcwnAylwt4S1J70dgxdxnuzSi1NJUfE35kdcJqSmtKGeYxjFnBswh1Dr2hZeQqamr5cEsCX++7gJ+zFV89GImX459a7uafg9UPQeYJiHoSRv4fGNZ/Rq4TOjLLMzmVe4oTuSc4mXuSuII4NDoNBooBt7jfwtSeUxnUddA1P0FIktQ2yHBvRYcyD/FN7DfsT9+PgWLArZ638mjIowQ6Bt7wvnYn5PLqmlOkFVZyX38v5o0JwPpac9drq2HLa3B4EXgPhruXgJVzo45To60hviCeHak7WJO0hrzKPFwtXIlyiyKiSwSRXSJxt3K/4folSWpZMtxbQWxeLJ8c/YQDmQdwNndmSo8pTPafTBfLLje8r8ziSt74LY7fTmbSzdmStyeH0M/XoXFvPrEC1j8LFo4w9Tvw6HtDx9boNPye8jsbL2wkJjuGomp19aWR3iN5MuxJ/Oz8bvTHkSSphchwb0GZZZl8FPMRGy9uxN7UnkeCH2FawDRMDW+8h4tWJ/hyz3kWbE9EqxM8Maw7c4Z2u/G565knYOX9UJoFd3wAfR644VpAHcI5V3SOzRc3syxuGRWaCsZ2G8vs4Nl0s+vWpH1KktR8ZLi3gMraSpacXsLXp79GIJgZNJOZQTOxMmnaKko1tTrmrjrObyczGdHLldfHB97ccnYVBWq7gnO/Q9+H1O6SRk1vGlZYVcg3sd/wQ9wPVGmruNXzVh7u/TBhLmFNr1GSpJsiw72Z5VXmMWfrHBIKExjtM5rn+z6Pm5Vbk/dXXl3LY8ti2JOYx6tjA5g9pJmGPnRa+P3fsPcjcOoBkY9AyFS1rXATFVQV8MPZH/jh7A8UVxczzGMYL0S+gLeNd/PULElSo8lwb0ZZ5Vk8uuVRsiuy+WDoB9ziccvN7a+4iseXx3AitYi3J4cwNdKzmSq9wtkNsPtdyDgGRmYQPAWGzgO7ph+rQlPB92e/58uTX1Kjq+G+gPt4LPSxJn9ykSTpxslwbyYpJSk8uuVRSmpK+HzE54S7hDd5XzqdYPmhZN7ZFI9Gq+OTe8IY3bvpZ/+NknkCYpbAseXq4/6z4Za/3dSZfF5lHguOLmBt0lqczJ14IeIFxviOuaHpnpIkNY0M92aQVZ7FjI0zqKqt4n8j/9ekqY2XpRZU8OyKYxxNKWJwdyfevLM33o6WzVhtA4pSYcd/4MQPYGoDUY9D1GM3FfKn807zxsE3iM2PpX+X/tzR7Q5cLVxxtXTFy9oL42vMu5ckqelkuN+k4upiZm6aSWZ5JktGLyHAIaDJ+0rILmXGV4eorNEyf0IQd4a76+8sN+s07HwLzv56KeSfgMFzwdisSbvT6rSsTljNgmMLKKkpqXve1NCUIMcgwl3CCXYKpqdDT9yt9PhzS1IHIcP9JlRrq5mzdQ4nck/wxYgv6O/Wv+E3XUNMciEPL4nG1MiA72b1p2cX62as9CZknYJd70LcL+ASCJMXQZfgJu9Oo9OQU5FDdnk2meWZxObHcjznOHH5cdSKWgCsja2J6hrF9IDp9HXtK4NekppAhnsTaXVaXtj1AttStvHekPcY7Tu6yfvam5jHo0uP4GJjyrJZ/W9ummNLSdgCvzylTqO89VUY8BQYNd9C2lW1VSQWJnK28Cxx+XFsSd5CcXUxAQ4BzOo9i1E+o2TIS9INkOHeBEII5h+Yz8+JP/Ny5MvcH3h/k/e1LymPh5dE4+tkyXez+uNs3YYXqS7Ph9/mwpl1YO8Lw/8BQZOvuW7rzaisreS387+xPG45SUVJ3OJ+C/+I+sdNTSuVpM5EhvsNEkLwYcyHLIldwpyQOTwV/lST97U/KY+Hv43Gx9GS5Y/0x9GqDQf7ZUJA0jbY+jrkxELXPnDXYnBsmdYDWp2WH87+wIJjC1BQmBU8i2Gew/C385dn8pJ0HTLcb9DiU4v55Ogn3NPzHl7t/2qTA2ZvYh6PLI3G28GS7x9tJ8F+JZ0WTq6Eza+qj6ctA5/BLXa4tNI03jj4Bvsy9gHgaOZIf7f+9HXtSx+XPnSz6yZXl5KkK8hwvwErz67kjUNvMNZ3LG/d8laTw2Td8XRe+PEEfs5WLHukP07tLdivVHAevp8GBRdg3EfQZ0aLHi6rPIsDGQc4kHmA6Kxo8irzAHAyd+Iu/7uY2nMqLhYuLVqDJLUHMtwb6dfzv/LqnlcZ6jGUD2/9sMmrFC3ec543foujn68DXz4Qga15B5jjXVkEP86E8zsg7H4Y/RaY2bT4YYUQpJamcjTnKFuTt7InbQ+GiiED3QfibO6MpbEldqZ2dQuOmBk1bRqnJLVHMtwbYWfqTp7b8Rx9Xfvy+YjPm9TVUacTvL3pLIt2n2dscBc+nBp24x0d2zJtLez8j9qrxtYDJn0BPoNatYTUklRWxq9kV9ouyjRllGvK61aXMjEwIcwljMdDHyeiS4P/3iWp3ZPh3oCLxReZsn4K/nb+LB61GEvjG79bVKPVMe+nU/x0NI0HBnjz+vggDA066MXAlEOwZg4UXoRBz8Ctf7+pjpM3q7SmlGM5x4jOimbzxc1klmcyqfsknu/7PPZmTb/rVpLaOhnu16ETOh7a9BCJhYmsnbS2SWO5lTVanvz+KL+fzeH5kT14+rbuHX+WR3UZbPm72qvGtTfc+T/o0lvfVVFZW8kXJ75gaexSLIwtiHCNwM/Oj+523RnsMRgbk5YfSpKk1iLD/TouX0D918B/caf/nTf8/uJKDbOWRHM0pZB/T+rNff07WevbhM3qAt1VRTBivtrCoA38YkssTOTLk19ytvAsKSUpaIUWcyNzJvhNYHrAdLnYiNQhyHC/hsyyTCatm0SIcwiLRi664bPtnNIqHvw6mnM5ZXxyTxhjgjvpzTflefDL0xC/AXqMgUmfg0UjlwVsBRqthriCOFbFr2LDhQ1odBqGeQ7j8dDHb6oBnCTpmwz3eggheHL7kxzJPsLPE37Gw9rjht6fWlDB/V8dIre0mv/N6Mst/o1bjLrDEgIO/U9dpNvKBYa8AD1Gg01XfVd2lfzKfFbFr+K7uO8orSllmOcwpvWcRmSXyCZdRJckfZLhXo/tKdt5bsdzvBT5EjMCb2zedn5ZNZM+30dJZS3fPBRJHy950a5O+lFY+zjknlUfdwmBXhOg9+QWu8O1KUprSlket5ylZ5ZSWlOKuZE5A9wG0M+tH72dehPgECDDXmrzZLj/iUarYdK6SRgZGPHThJ8wMjBq9HurNFqmf3mQ2IwSVs4ZQJinXQtW2k4JoYZ7wiaI3wSpB9Xnu4ZD4ET1jN45oE2MzVfVVhGdFc2utF3sSttFVnkWAEaKEUM9h/Ji5Iu4W7nruUpJqp8M9z9ZGruU9468x+fDP7+hZfJ0OsEzK47x68lM/ntfn847xn6jitMgdg2cWg2Zx9Xn7Lwh6E7oNxts20Z4CiHIrsgmNi+WYznHWJWwCiEEs0Nm82DQg5gYNl+HTElqDjLcr1BUVcTYNWMJcQrhi5Ff3NB7P9gSz6e/JzFvTACPDW07QwztSnE6JG6B+I2QtBUUAzXkB88F1yB9V3eVzLJM3o1+l20p23Ayd2K0z2ju6HYHQY5BHX+qq9QuNGu4K4oyGvgEMAQWCyHe/tPrzwOPALVALvCwECL5evtszXB/69BbrIxfyerxq+lu373R79scm8Wc72KYGuHBO3eFyP+5m0NhsnoR9uhSqK2EYfNg0FwwbPwwWWvYn7GfVfGr2J22G41Og5e1F2O7jWWM7xi62coplZL+NFu4K4piCCQAI4E0IBq4Vwhx5optbgUOCSEqFEV5HBgmhJh2vf22VrinlqQyfu14pvSYwmtRrzX6fedzy5jw2T78nC1Z9dgATI06UEuBtqCiADa8CKdXg0ckTPovOPnru6q/KKkpYVvyNjZc2MDhzMMIBCHOITwV9hQDug7Qd3lSJ9TYcG9M+8N+QJIQ4rwQogZYAUy8cgMhxA4hRMWlhweBG5tj2IK+jv0aQ8WQx0Ifa/R7yqtrmfNdDCZGBnx+f18Z7C3BwgGmfAV3fQV5CfBZBHw1Cg5/CWW5+q6ujo2JDZP9J7P49sVsu3sbL0a8SG5FLrO3zubRLY8Smxer7xIlqV6NCXd3IPWKx2mXnruWWcDG+l5QFGW2oihHFEU5kpvb8v8D51TksC5pHZO6T8LJ3KlR79HpBC+tPsm53DI+vTccdzvzFq6ykwueAk8ehtteg6pi2PACfNADlk6CY8vUzpRthIuFCw8EPcD6O9fzYsSLnC04yz2/3cOcrXOIzopGX9evJKk+jQn3+gaa6/1XrCjK/UAE8F59rwshFgkhIoQQEc7OLX8D0LIzy9AKLTODZjb6Pe9ujue3U5nMGxPAoO6N+4Ug3STrLjDkRXjyIDy+X73QWngB1j0JHwTAr3MhL1HfVdYxNTTlgaAH2Dh5I8/2eZb4gnge3vwwMzbOICY7Rt/lSRLQuDH3AcB8IcSoS49fARBCvPWn7UYAnwJDhRA5DR24pcfci6uLuX317Qz1HMq7Q95t1Hu+O5jMP9ae5v4oL/49sbe8gKpPQkB6DBz9Fk6sBG01+A4Ft1Bw7K7OmXfvA4b675tfra1mXdI6Fp1cRHZFNsO9hjO371y8bTpZzyGpVTTnBVUj1Auqw4F01Auq04UQsVdsEw6sBkYLIRp1itXS4b7o5CI+PfYpq8evpqdDzwa333ommznfHeHWni78b0ZfjAzl0m5tRlkuHPlKnTdfcB60NerzprbQfTj0HAtBk/Qe9JW1lSyNXcpXp79Co9NwX8B9zAmdg7WJtV7rkjqW5p4KORb4GHUq5NdCiDcVRfkXcEQI8YuiKNuAYCDz0ltShBATrrfPlgz3ytpKRv80mkDHQP474r8Nbn/ofD4PfnOYHq7WrJgdhYVJ25qWJ11Bp4XiVMg8qc6dT9gM5Tng1BPGvgvdhum7QvIq81hwdAFrk9Zib2bPM+HPMM5vnGxtIDWLTn0T0/pz63l176t8PeprIrtEXnfbE6lF3Lf4EK42pqycM6B9r3vaGel0asuDza+oC4n0mqDeINU1DOx99druIDYvlrcPv83x3ONYm1hzu/ftjOs2jlCX0CYv5yhJnTrc52ydQ3JJMhsnb7zuuHl8VinTFh3A2syIH+cMpIutXIuz3dJUwf5PYe+HoLk0K9fMFnqNh74PgXtfvQS9EIIDGQdYf34921O2U1lbiamhKUGOQQQ7BeNj60NXq654WHngYe3R5MXZpc6j04Z7bkUuI1aP4JHgR3g6/OlrbpddUsW4T/dioMCPcwbi5WjR7LVIelBbDTlxaj+blENwZh1oysElCAY8ASHT9DY2X6GpYG/6Xo7nHudk7knO5J9Bo9PUvW5nakdkl0ii3KIY4DYATxtPvdQptW2dNtwvNwhbN2ndNW8Tr6nVce+XB4nLLGHNE4Po2UVe8OqwqkvV5mVHvoKsU2DvA7f8TQ15Pa4BC1CrqyW3Ipf0snRSSlOIyY7hUOYhsiuyAfC09mRg14H42flhY2KDjYkNXjZeeFl7yZlcnVinDfep66dioBiwYtyKa24z/5dYluy/yKf3hjM+tG0tLCG1ECHUi6+73oaMY2BsCX63qq2I/W5rU10qL5ZcZH/GfvZn7Cc6K5rK2sqrtnEwcyDMOYxhnsO4o9sdsnNlJ9Mpw/1c0TkmrZvEy5Evc3/g/fVus+54Os+uOM7Dg3z553i53FqnIwSc3wlx69WwL0lTn7f3Ae/B0Gsc+I8Cg7Yx9l2rq6WouojSmlKKq4tJLErkeM5xYrJjSC9Lx8ncift73c9d/ndhZybXGegMOmW4Lzi6gK9Of8X2u7fX224gMbuUCZ/to7e7Dd8/GoWxnMveuQkB2bFwYTck74OLe9VFvx38IOpxCJsOJpb6rrJeQggOZR3im9PfsD9jPwDuVu4EOgbSx6UPY7uNxcGs7axpKzWfThfuOqFjzE9j8LX1rbdne2WNlkkL95FXVs2GZ2/B1UbOjJH+RFsLcevgwEL17lgjM/Wu2B6j1C/bNtMP7ypnC86yN30vcflxnMk/Q1pZGkYGRtzqeSuTuk9iUNdBGBrI5ncdRWPDvcPcrXM85zgZ5Rk8Ff5Uva//69dY4rNL+fbhfjLYpfoZGkHvuyBoMqQeVu+ITdgIiZvhN8A1WA35gDvU5QPbyEXNAIcAAhwC6h4nFiayNmkt68+tZ2vyVlwtXLnT/04md5+Mm5VcSayz6DBn7h8c+YBlccvYM20PViZWV712eZz98WF+vDw64Bp7kKR6CKG2JE7YrH6lHAChBdfe0OdBCJkK5m1zrFuj1bAjdQc/Jf7EgYwDKIrCKO9RzOw9k0BHeb2pvep0wzLj14zHzdKNRbcvuur51IIKxnyyh4AuamsB2TNGuimVheoZfcwSyDwBhqbgP1JtXdxjNBi3zRbR6WXprDy7klUJqyjXlNPXtS/9u/Qn2DmYYKdgbE1t9V2i1EidKtyTS5IZt2Yc8/rN475e99U9r9MJ7v3yIGcyStg0d4jszS41r4xjcGKFGvZl2WBirYZ835lq+4M2qLSmlB8TfmT9ufWcKzqHuNS9u5ttN8Jdwgl3Cec2r9tks7M2rFOF++UblzZO3oiH9R8Xvb7ee4F//XqGd6eEMDVC3u0ntRCdVp1pc+IHNehrq9TWxH1nQu8pYGaj7wrrVVZTRmx+LCdzT3Is5xjHc49TWlOKuZE5Y33HMrXnVHo59JI3TLUxnSrcZ22eRUFVAWsmrql77nxuGWMX7GGQnxOLH4yQ/0Cl1lFZBKd+VIdtsk+DsYXayKz7cHUevbWrviu8Jp3QcTrvND8m/MimC5uo0lbhbO5cd0bf3b473tbeuFq6yh44etRpwr2kpoShK4byYNCDPNf3OQC0OsHdX+znXG45W+cOwUXOjpFamxCQfhSOLoHTa6CmVH3esbvaxMwtDNxCwM4LrFz13grhz4qri9mSvIWY7BiOZR8jozyj7jUTAxO8bLzwtfWlm203IrtEEuEaIadbtpJOE+4bL2zkpd0v8d2Y7whzUcc5L6+o9PG0MCaFt43byqVOTFsLWSfUoZvkA2pTs9LMq7cxdwCXXmrodw37Y8WpNhKYORU5XCy+SEppCiklKVwovsD54vOklaWhEzoczRwZ6T2S/m798bX1xcvaC+M2sEpWR9Rpwv3l3S9zIOMAO6buwNDAkOJKDcPe21G38IYcjpHapNJstZFZaQaUZkFJunq3bNYpdcwe1P43biFg0xVMrMDUWl1v1rG7+mXvq87N16MKTQV70vew+eJmdqftplpbDYChYoijuSP2pvbYmdrhaumKn50ffrZ+eFp7Ym9mj42JjTzbb4JOcRNTra6Wvel7GeY5rO4fyYLtiRRVavjn+EAZ7FLbZe1a//i7thby4tVplhnHL30/BjXlUF2mti++zMwWuo9Qe+H4DFZ/CbTyv3kLYwtG+YxilM8oKmsrOV98Xj2rLzpPbmUuRdVFFFUVcTDjIL+c++Wq9xooBjiZO+Fv54+/vfrlZ+uHr60vFsayBffNatfhfjznuDrm7jEUUC+ifrv/ItMiPAnqKuftSu2QoRG4BqlfYdP/+npFgbqObF6C2g8nYQuc/kl9zdgSHLupveu9B6qB79Ct1QLf3MicIMcgghyD6n29uLqYC8UXSC9Lp6i6iMKqQjLLM0ksTOT7uO+p0dXUbetq4YqTuROO5o44mzvTzbZb3S8ARzNHeeLWCO063I/lHAMgqmsUAG/+FoeZsSF/u73hBbElqV2ycFC/PCLU8NfpIPOYevE2/xzkJ8K57XDyUstrazfwHqQGve8QcPTTW+m2praEuYTVXRu7Uq2ultTSVM4VneNc0TlSSlPIr8ontyKX03mn+Snxp6v242frh5+dH87mztib2eNo7khvx96yvcIV2nW4xxXE4WXthY2JDfuS8th+Nod5YwJwtm5bMw8kqcUYGKizb9z7/vHc5ZYJF/de+toDp1errzn4qXfSdr8NnHvpZSinPkYGRvja+uJr68sI7xF/eT2/Mp+koiQSCxNJKkrifPF5tiZvpai66KrtPK096delHyO8RxDlFoWRQbuOuJvSri+ojv5pNL2devPekPeYtHAfuaXV7HhxGKZG8iKNJNURQj2rP/e72gTtwh64dOETYws18B391Iu0Tj3As5/a374NhH5DNDoNxdXFZFdkcyz7GIeyDnEk6whlmjIczRwZ4zuG27xuI9Q5tMMsatLhZ8sUVxczeMVgnuvzHJ4GdzD7uxjeuSuYaZFezVilJHVANeWQdgTyk/4YyslPgsJktSkagI27Om7vEvjH7BybrupF3DYe+jXaGvak7WH9+fXsSttFra4WM0Mz+rr2xc/ODwczBxzNHfG38yfAIaDdzdjp8LNlzhacBSDAvhf/Xp2Ar5Mld/Vpm/22JalNMbGEbkPVryvV1qhBn7z/j8VLTv149TZG5uosH6sul2b8uIGTP7iFqxeBjfV/w6CJoQnDvYcz3Hs4pTWlHMk6wsHMgxzOOkxMdgxV2qq6bW1NbYlyi8LX1hchBAKBqaEpjmaOOJo74mWt3qzVHi/gtttwP5N/BoDkLDvOZl1gwb3hsuOjJN0MI5M/Zur0e1R9rqoECs6pZ/ilmeqc/LJs9Xv2GUj6/Y+7bw2M1DN+6y7ql7mD+ovE1BrM7dU7ca3dwMIRTK3Uufsmli36ScDaxJpbvW7lVq9b656r0FSQX5nPybyT7M/Yz8GMg2y+uBkABaWumdplLhYuDOw6kH5d+tHLoRc+tj7tYiy/3Q7LvLTrJY7lHkdz4RXMjA3Z8MwtGBi0v9+uktSuCQHFqX/MyS9KVoO/NEtdsrC6DP60wPdVDIyu/hRg5ar+YrB0Vn8pmFipjdesXNUvU6tr76vJP4K46sy8WltNfmU++ZX5JBQmqL8AMg9SUlMCqO0XgpyCmB4wnRHeI1o96Dv8mPv4NeMxx43Dhyby5QMRjAxsuw2ZJKlT02nVPvilmeqduRX5UFOmflUWqs+VZv7xiaCy4Nr7MrFSw//yLwRTm0ufDmzUPj2O3dWLwxbNu36sVqflXPE54gviSShMYGfqTi6WXMTDyoOHej/EXf53tdrYfYcO97KaMgb8MACX2onUFgxn5wvD2uWYmCRJ9aithvK8P34BVBVDWc4fnwjKsv4YHqourf/TgY37peZsoeASoIa+Q7dmW0xFJ3TsSNnB16e/5mTeSYKdgvn3oH/jZ9fy9xF06Auq8YXxAFzMtOfZAR4y2CWpIzEyBdsbbPhXW6MOCeUnQV6i2qMn8zjEb/j/9u4/tqqzjuP4+3NpYLIO1pVfg9EfKNBhszAkrJg5keoGmKzGgNSFOA1xG0T/Mf5hssQsW0KcyTQzkCjBRWeiTjHD6mAm0y2bROoah6OUoF3XKcgAYTDGz7J+/eM5yF1puYf2nnN77/2+kpuce8/Te7/fnnu/PX3Oc58HsvvQx02MzvQrQzfQpZFA4zFTtp0AAAcJSURBVKsv9/1nKqK5fCrD41V1V8zamVGG5tpmltYs5fne59nQvoFVv1vFg7c9yH233jcqFjspyuK+79g+APrPTefzC3zWR+fKXsXYMGpn0myYu/zy4+ffi4Z8RsM+zx4Pj104BScPhqkbzp0Y+nkBlAldPlX1UZfQVKiqhZrFaHIDy+uXs2jaIja0b2Dj7o1s2bOF5tpmWj7cwvwp8/lQRWFWgCvK4t51rAu9P4GmmnpuqfIJhpxzQxhXGaZQvtqyh6ePfbDAv38hmqjtVOgOOv5G9D2A3vBfwXuHob8vtB1fDXWfoPqjn+OJjz9GZ+NX2Na9je0923mu5zkyylA7oZaGmxpourmJO2fcyZTxUxJN+ZJYxV3SMuBJYAywxcy+M2D/OOBp4GPAMWC1mfXmN9TL/vZ2J31nprNysY9rd86N0PXV4RZXfz+c6A3fB+jdGeby6doGYytpnHMPjTPv4JuLH2cXp+k62cO+4/voeLuDHW/uAGBu1VzWz1/P0pqlyeQTyVncJY0BNgGfAQ4Ar0pqM7OurGZrgXfM7COSWoHHgdVJBHz24lkOnukl09fMssZpSbyEc84NLZMJF2dvmgW3rwmjgd7aCXu2wv4d0PkbrgOWAEvGV0PlNKxyKv+8cTavVPTz5wtHqTh/OseLjFycM/dFQLeZ9QBI+iXQAmQX9xbgkWh7K7BRkiyBoTidR/YDxoJpjVw/rih7lZxzpSQzJsy4WX9XGPd/6lAY9394b7QYy2H07kHmHOxgzvl3WQsw47OJhxWnOs4A/p11/wBwx1BtzOyipJNANfDffASZ7dmudgBW37Y430/tnHMjI4U5eCZMh4YVH9xnFoZ4HusOF2QTFqe4DzbOcOAZeZw2SHoAeACgpmZ4E3zNrKxjKktZ3tAwrJ93zrmCkKBycrilIM5kLAeAmVn3bwH+M1QbSRXAROCKr5mZ2WYzW2hmCydPHl6C65ru4YX7n2SMzyPjnHNDilMhXwVmS6qXNBZoBdoGtGkD7o+2VwJ/SqK/3TnnXDw5u2WiPvSvAX8gDIV8ysz2SnoU6DCzNuDHwM8kdRPO2FuTDNo559zVxRpuYmbbge0DHvt21vY5YFV+Q3POOTdc3nHtnHMlyIu7c86VIC/uzjlXgry4O+dcCfLi7pxzJahgKzFJOgq8Ncwfn0QCUxsUgXLMuxxzhvLMuxxzhmvPu9bMcn4LtGDFfSQkdcRZZqrUlGPe5ZgzlGfe5ZgzJJe3d8s451wJ8uLunHMlqFiL++ZCB1Ag5Zh3OeYM5Zl3OeYMCeVdlH3uzjnnrq5Yz9ydc85dxagu7pKWSdovqVvStwbZP07SM9H+dkl16UeZXzFy/oakLkmvS/qjpOSXdElBrryz2q2UZJKKflRFnJwlfSE63nsl/TztGJMQ4z1eI+lFSa9F7/MVgz1PMZH0lKQjkjqH2C9JP4h+J69LWjDiFzWzUXkjTC/8BjALGAv8HZg3oM164IfRdivwTKHjTiHnTwHjo+11xZ5z3LyjdjcALwO7gIWFjjuFYz0beA2oiu5PKXTcKeW9GVgXbc8Degsddx7yvgtYAHQOsX8FsIOwql0T0D7S1xzNZ+7/X5jbzC4AlxbmztYC/DTa3go0Sxpsyb9ikTNnM3vRzM5Ed3cRVsYqdnGONcBjwHeBc2kGl5A4OX8V2GRm7wCY2ZGUY0xCnLwNmBBtT+TKld+Kjpm9zCCr02VpAZ62YBdwo6SbR/Kao7m4D7Yw94yh2pjZReDSwtzFKk7O2dYS/toXu5x5S7odmGlmv08zsATFOdZzgDmSdkraJWlZatElJ07ejwBrJB0grCPx9XRCK6hr/eznFGuxjgLJ28LcRSR2PpLWAAuBTyYaUTqumrekDPB94MtpBZSCOMe6gtA1s4TwH9orkhrN7ETCsSUpTt5fBH5iZk9IWkxY5a3RzPqTD69g8l7LRvOZe94W5i4icXJG0qeBh4F7zex8SrElKVfeNwCNwEuSegl9km1FflE17vv7t2bWZ2ZvAvsJxb6Yxcl7LfArADP7C3AdYf6VUhbrs38tRnNxL8eFuXPmHHVP/IhQ2EuhDxZy5G1mJ81skpnVmVkd4VrDvWbWUZhw8yLO+3sb4QI6kiYRuml6Uo0y/+Lk/S+gGUDSrYTifjTVKNPXBnwpGjXTBJw0s0MjesZCX0XOcYV5BfAPwtX1h6PHHiV8sCEc9F8D3cBfgVmFjjmFnF8ADgO7o1tboWNOI+8BbV+iyEfLxDzWAr4HdAF7gNZCx5xS3vOAnYSRNLuBuwsdcx5y/gVwCOgjnKWvBR4CHso61pui38mefLy//RuqzjlXgkZzt4xzzrlh8uLunHMlyIu7c86VIC/uzjlXgry4O+dcCfLi7pxzJciLu3POlSAv7s45V4L+B9VuOxcWrmp+AAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "thresholds = [float(n) / nthresholds for n in range(0, nthresholds)]\n", "falseposDict = dict([(t, falsepos(t)) for t in thresholds])\n", "falsenegDict = dict([(t, falseneg(t)) for t in thresholds])\n", "trueposDict = dict([(t, truepos(t)) for t in thresholds])\n", "\n", "precisions = [precision(t) for t in thresholds]\n", "recalls = [recall(t) for t in thresholds]\n", "fmeasures = [fmeasure(t) for t in thresholds]\n", "\n", "print(precisions[0], fmeasures[0])\n", "assert (abs(precisions[0] - 0.000532546802671) < 0.0000001)\n", "assert (abs(fmeasures[0] - 0.00106452669505) < 0.0000001)\n", "\n", "\n", "fig = plt.figure()\n", "plt.plot(thresholds, precisions)\n", "plt.plot(thresholds, recalls)\n", "plt.plot(thresholds, fmeasures)\n", "plt.legend(['Precision', 'Recall', 'F-measure'])\n", "plt.show()" ] }, { "cell_type": "code", "execution_count": 121, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "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.3" }, "name": "entity-resolution-tutorial", "notebookId": 463537072256233 }, "nbformat": 4, "nbformat_minor": 1 }