Booklist_Holdings_Comparison.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Booklist/Holdings Comparison.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "98lEVHSykCRZ",
        "N6yX1DxOkl4t"
      ],
      "toc_visible": true,
      "mount_file_id": "1uS_A6omWKkpflMaPIbVqOGUJ8rsCkyJF",
      "authorship_tag": "ABX9TyO7Qrx0m6su59TuzUHmckee",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/jmgold/DEI-Collections/blob/main/Booklist_Holdings_Comparison.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9kmPeKV2cG3a"
      },
      "source": [
        "Jeremy Goldstein\n",
        "Minuteman Library Network\n",
        "\n",
        "This Python script will compare an excel or csv file of local holdings to a curated booklist to find how much of that list you own and which titles are missing based on fuzzy matching titles and authors.\n",
        "\n",
        "The script may appear daunting at first glance but it will do all the work for you.  Simply hit play, upload a couple spreadsheets where needed and enter a match value in step 4 when prompted.\n",
        "\n",
        "Minuteman staff may view [a video demoing the script here.](https://drive.google.com/file/d/1KP-7dD0OAgjdFaK14myptWCRrhmwuXPS/view?usp=sharing)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xurg45yXwklo"
      },
      "source": [
        "# Instructions"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bxm2GfRgwo2T"
      },
      "source": [
        "**Prerequisite**\n",
        "\n",
        "You will need two files containing at least title and author information.  The file can be a csv or excel (either .xls or .xlsx is fine).  Titles and authors need to each be in their own column with a header of 'title' and 'author' (capitalization does not matter).  The files can contain as many additional columns as you wish, so long as each one does include its own column header.\n",
        "The first file will be a list of titles you wish to check against your current holdings.  The second should be a list of your current holdings."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HGA7yTylxrXr"
      },
      "source": [
        "**Running the script**\n",
        "\n",
        "Each code block can be run one at a time by clicking the play icon that appears when you hover over the [] marker.  Once that block finishes running a green check will appear to the left of the block and any output from that portion of the script will appear beneath it, along with any errors that may be encountered.\n",
        "\n",
        "You may also use the \"Run All\" function, found within the Runtime drop down menu to Run the entire script, though there are points where user input is required before the script will continue past a particular code block to be on the lookout for.  These are indicated by the text **Action Required**.  There are also a few **Optional** code blocks where you can download the output of the script to excel.\n",
        "\n",
        "You may reset the output by going to the Edit menu and selecting clear all outputs.  You can also review files that have been uploaded or created as part of this script using the folder icon i the left hand navigation menu. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "98lEVHSykCRZ"
      },
      "source": [
        "# Step 1: Configure Python/Colab Environment\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "unDmpF37Q8KB",
        "cellView": "form"
      },
      "source": [
        "#@title\n",
        "#nmslib is not included by default with Colab and must be installed.\n",
        "!pip install nmslib\n",
        "!pip install xlrd==1.2.0\n",
        "\n",
        "#import Python libraries that will be used within the script\n",
        "import pandas as pd\n",
        "import io\n",
        "import numpy as np\n",
        "import os\n",
        "import re\n",
        "import nmslib\n",
        "import altair as alt\n",
        "from sklearn.feature_extraction.text import TfidfVectorizer\n",
        "%load_ext google.colab.data_table\n",
        "from google.colab import files"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Qo5yi8lhkURC"
      },
      "source": [
        "# Step 2: Import data\n",
        "Script will load tabular data into two dataframes using the Pandas library for Python.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "OJUETZ4Oqx6s"
      },
      "source": [
        "**Action Required** Upload either a csv or excel file with the list of suggested titles you wish to match your holdings against.  \n",
        "\n",
        "Must contain at least 2 columns with the headers author and title (capitalization does not matter)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "soz6bIdCiktr",
        "cellView": "form"
      },
      "source": [
        "#@title\n",
        "uploaded_list = files.upload()\n",
        "\n",
        "for fn in uploaded_list.keys():\n",
        "  file_name=fn\n",
        "  print('User uploaded file \"{name}\" with length {length} bytes'.format(\n",
        "      name=fn, length=len(uploaded_list[fn])))\n",
        "\n",
        "#Loads the uploaded file into a datafrome or returns an error if the file is an incorrect format  \n",
        "if file_name.endswith('.csv'):\n",
        "  booklist_df = pd.read_csv(io.BytesIO(uploaded_list[file_name]))\n",
        "elif file_name.endswith('.xls'):\n",
        "  booklist_df = pd.read_excel(io.BytesIO(uploaded_list[file_name]))\n",
        "elif file_name.endswith('.xlsx'):\n",
        "  booklist_df = pd.read_excel(io.BytesIO(uploaded_list[file_name]))\n",
        "else:\n",
        "  print(\"error file is not .csv or excel\")\n",
        "\n",
        "#clean up data in the table and add BooklistMatch Column for use later\n",
        "#change null to blank\n",
        "booklist_df=booklist_df.fillna('')\n",
        "#change headers to lower case\n",
        "booklist_df.columns = [x.lower() for x in booklist_df.columns]\n",
        "#save list of column headers for use at the end\n",
        "booklist_headers = booklist_df.columns.tolist()\n",
        "#create match point column\n",
        "booklist_df['BooklistMatch']=booklist_df['author']+booklist_df['title']"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "A02u1KhMULiE"
      },
      "source": [
        "**Optional** Preview the contents of this dataframe.  \n",
        "You can use the Filter button to further explore the data."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MculiptYhvhu",
        "cellView": "form"
      },
      "source": [
        "#@title\n",
        "#Preview booklist dataframe\n",
        "booklist_df"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "I1F7LhqDUWo6"
      },
      "source": [
        "**Action Required** Upload an excel or csv file containing the titles within your holdings\n",
        "\n",
        "Must contain at least 2 columns with the headers author and title (capitalization does not matter)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tiPpkhcINbKu",
        "cellView": "form"
      },
      "source": [
        "#@title\n",
        "uploaded_holdings = files.upload()\n",
        "\n",
        "for fn in uploaded_holdings.keys():\n",
        "  file_name=fn\n",
        "  print('User uploaded file \"{name}\" with length {length} bytes'.format(\n",
        "      name=fn, length=len(uploaded_holdings[fn])))\n",
        "\n",
        "#Loads the uploaded file into a datafrome or returns an error if the file is an incorrect format\n",
        "if file_name.endswith('.csv'):\n",
        "  holdings_df = pd.read_csv(io.BytesIO(uploaded_holdings[file_name]))\n",
        "elif file_name.endswith('.xls'):\n",
        "  holdings_df = pd.read_excel(io.BytesIO(uploaded_holdings[file_name]))\n",
        "elif file_name.endswith('.xlsx'):\n",
        "  holdings_df = pd.read_excel(io.BytesIO(uploaded_holdings[file_name]))\n",
        "else:\n",
        "  print(\"error file is not .csv or excel\")\n",
        "\n",
        "#clean up data in the table and add BooklistMatch Column for use later\n",
        "#remove null values\n",
        "holdings_df=holdings_df.fillna('')\n",
        "#change headers to lower case\n",
        "holdings_df.columns = [x.lower() for x in holdings_df.columns]\n",
        "#save list of column headers for use at the end\n",
        "holdings_headers = holdings_df.columns.tolist()\n",
        "#Create MatchPoint field\n",
        "holdings_df['HoldingsMatch']=holdings_df['author']+holdings_df['title']\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "V7I_D68mU0rP"
      },
      "source": [
        "**Optional** Preview holdings data.\n",
        "\n",
        "**Note:** If the file is contains more than 20,000 rows the preview will be displayed different than the prior preview and will not include the browse features."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_8w4Xdmbg8eC",
        "cellView": "form"
      },
      "source": [
        "#@title\n",
        "#Preview data\n",
        "holdings_df"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "N6yX1DxOkl4t"
      },
      "source": [
        "\n",
        "# Step 3: Calculate Matches Dataframe\n",
        "Compare two data frames and calculate match confidence value for each pair of rows.\n",
        "\n",
        "Matching algorithm is taken from [Fuzzy Matching at Scale by Josh Taylor](https://towardsdatascience.com/fuzzy-matching-at-scale-84f2bfd0c536) (viewed 11/24/2021)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6OT4VoNWO9db",
        "cellView": "form"
      },
      "source": [
        "#@title\n",
        "def ngrams(string, n=3):\n",
        "    \"\"\"Takes an input string, cleans it and converts to ngrams. \"\"\"\n",
        "    string = str(string)\n",
        "    string = string.lower() # lower case\n",
        "    string = string.encode(\"ascii\", errors=\"ignore\").decode() #remove non ascii chars\n",
        "    chars_to_remove = [\")\",\"(\",\".\",\"|\",\"[\",\"]\",\"{\",\"}\",\"'\",\"-\"]\n",
        "    rx = '[' + re.escape(''.join(chars_to_remove)) + ']' #remove punc, brackets etc...\n",
        "    string = re.sub(rx, '', string)\n",
        "    string = re.sub(' +',' ',string).strip() # get rid of multiple spaces and replace with a single\n",
        "    string = ' '+ string +' ' # pad names for ngrams...\n",
        "    ngrams = zip(*[string[i:] for i in range(n)])\n",
        "    return [''.join(ngram) for ngram in ngrams]\n",
        "\n",
        "\n",
        "###used to build the matching table\n",
        "##### Create a list of items to match here:\n",
        "booklist_match = list(booklist_df[\"BooklistMatch\"].unique())\n",
        "#Building the TFIDF off the clean dataset\n",
        "vectorizer = TfidfVectorizer(min_df=1, analyzer=ngrams)\n",
        "tf_idf_matrix = vectorizer.fit_transform(booklist_match)\n",
        "\n",
        "##### Create a list of messy items to match here:\n",
        "holdings_match = list(holdings_df[\"HoldingsMatch\"].unique()) #unique list of names\n",
        "\n",
        "\n",
        "messy_tf_idf_matrix = vectorizer.transform(holdings_match)\n",
        "\n",
        "# create a random matrix to index\n",
        "data_matrix = tf_idf_matrix#[0:1000000]\n",
        "\n",
        "# Set index parameters\n",
        "# These are the most important ones\n",
        "M = 80\n",
        "efC = 1000\n",
        "\n",
        "num_threads = 4 # adjust for the number of threads\n",
        "# Intitialize the library, specify the space, the type of the vector and add data points \n",
        "index = nmslib.init(method='simple_invindx', space='negdotprod_sparse_fast', data_type=nmslib.DataType.SPARSE_VECTOR) \n",
        "\n",
        "index.addDataPointBatch(data_matrix)\n",
        "# Create an index\n",
        "index.createIndex() \n",
        "\n",
        "\n",
        "# Number of neighbors \n",
        "num_threads = 4\n",
        "K=1\n",
        "query_matrix = messy_tf_idf_matrix\n",
        "query_qty = query_matrix.shape[0]\n",
        "nbrs = index.knnQueryBatch(query_matrix, k = K, num_threads = num_threads)\n",
        "\n",
        "mts =[]\n",
        "for i in range(len(nbrs)):\n",
        "  original_nm = holdings_match[i]\n",
        "  try:\n",
        "    matched_nm   = booklist_match[nbrs[i][0][0]]\n",
        "    conf         = nbrs[i][1][0]\n",
        "  except:\n",
        "    matched_nm   = \"no match found\"\n",
        "    conf         = None\n",
        "  mts.append([original_nm,matched_nm,conf])\n",
        "\n",
        "mts = pd.DataFrame(mts,columns=['holdings_match','booklist_match','conf'])\n",
        "#change negative values to positive for ease of reading\n",
        "mts['conf'] = mts['conf'].abs()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "p_vDnmdlMZ73"
      },
      "source": [
        "#Step 4: Determine matches"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oifkj3bWvP0P"
      },
      "source": [
        "**Action Required** In the table below you can browse the results to see the match confidence scores assigned to each pair.\n",
        "\n",
        "Look at values of the 'conf' column to find the point at which you feel the entries are matched correctly.  Generally we recommend looking at the values between .5 and .7 as a starting point.  To help here you can see a preview of the matched data that has been limited to the relevant range of values."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WTEHBXVvRk59",
        "cellView": "form"
      },
      "source": [
        "#@title\n",
        "#.66 used as default match confidence value based on initial testing, will be overwritten in step below\n",
        "\n",
        "mts = mts.sort_values(by=['conf'])\n",
        "mts[mts['conf'].between(.5,.7)]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yZX3O-6fbfN_"
      },
      "source": [
        "**Optional** Download matching table to an Excel file"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PsP1GtU4bNaR",
        "cellView": "form"
      },
      "source": [
        "#@title\n",
        "mts.to_excel(\"match_confidence.xlsx\")\n",
        "files.download('/content/match_confidence.xlsx')"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "b73rEq_bXQsJ"
      },
      "source": [
        "**Action Required** Enter the confidence value you wish to use for determining correct matches, based on the output from the prior code block.  \n",
        "\n",
        "Any value greater than or equal the number you enter will be considered a match.\n",
        "\n",
        "Once this code block has been run once, you may adjust the slider without having to run it again."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ITNACPmPtGwL"
      },
      "source": [
        "#@title Set Confidence Value { run: \"auto\", vertical-output: true, display-mode: \"form\" }\n",
        "match_confidence = 0.66 #@param {type:\"slider\", min:0, max:1, step:0.001}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6vZHzDWUNYik"
      },
      "source": [
        "**Percentage of Titles from list that are in your collection**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "X_WR0Yt4RqHr",
        "cellView": "form"
      },
      "source": [
        "#@title\n",
        "pct_held = (len(mts.loc[mts['conf'] >= match_confidence]) / len(booklist_df)) * 100\n",
        "source = pd.DataFrame({\"titles\": [\"all\",\"all\"],\"category\": [\"held\",\"not held\"], \"value\":[pct_held,100-pct_held]})\n",
        "\n",
        "print('You own '+str(round(pct_held, 2))+'% of the titles in the booklist')\n",
        "alt.Chart(source).mark_bar().encode(\n",
        "    x='sum(value)',\n",
        "    y='titles',\n",
        "    color='category',\n",
        "    order = alt.Order('category',sort='ascending')\n",
        ")"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LTwQKHXENNJh"
      },
      "source": [
        "**Titles Found in Your Collection**\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5Q98o0kOjlIl",
        "cellView": "form"
      },
      "source": [
        "#@title\n",
        "#Merge the holdings dataframe with the instances where a match has been found\n",
        "found_results = holdings_df.reset_index().merge(mts.loc[mts['conf'] >= match_confidence], left_on='HoldingsMatch', right_on='holdings_match').set_index('index')\n",
        "#found_results = found_results.rename(columns=str.capitalize)\n",
        "found_results[holdings_headers]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-h-VhKIKaOeZ"
      },
      "source": [
        "**Optional** Download results to an Excel file"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wLTAiD5GTzNI",
        "cellView": "form"
      },
      "source": [
        "#@title\n",
        "found_results[holdings_headers].to_excel(\"found_results.xlsx\")\n",
        "files.download('/content/found_results.xlsx')"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_uZJOGumNDKr"
      },
      "source": [
        "**Titles Not in your collection**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "e5vezPTxFPNg",
        "cellView": "form"
      },
      "source": [
        "#@title\n",
        "#Create missing dataframe containing the titles from the booklist that were not matched to your holdings\n",
        "booklist_found = booklist_df.reset_index().merge(mts.loc[mts['conf'] >= match_confidence], left_on='BooklistMatch', right_on='booklist_match').set_index('index')\n",
        "common = booklist_df.merge(booklist_found, how='outer', left_index=True, right_index=True)\n",
        "common = common[common[['conf']].notna().all(axis=1)]\n",
        "missing = booklist_df.merge(common, how='outer', left_index=True, right_index=True)\n",
        "\n",
        "missing = missing[missing['conf'].isnull()][booklist_headers]\n",
        "missing"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "G7ZvUCMOa-zB"
      },
      "source": [
        "**Optional** Download missing titles to an Excel file"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4VIoXFPIa_fY",
        "cellView": "form"
      },
      "source": [
        "#@title\n",
        "missing.to_excel(\"missing_results.xlsx\")\n",
        "files.download('/content/missing_results.xlsx')"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}