09_knn_prediction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Predicting interactions with kNN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import Pkg; Pkg.activate(\".\")\n",
    "using Plots\n",
    "using StatsBase"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Getting the data\n",
    "\n",
    "We will get data from the *Ecological Interactions and the Netflix Problem* paper, which was assigned reading for this chapter. The data will go into a specific folder, which we create if it doesn't exist:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create a folder called data if it doesn't exist\n",
    "ispath(joinpath(\"data\", \"knn\")) || mkdir(joinpath(\"data\", \"knn\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All the data files are stored on *GitHub* - we can get them directly, using the `download` function. To save time, we only download them if they do not exist yet. The `joinpath` function will ensure that our code works on all operating systems:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "_project_root = \"https://raw.githubusercontent.com/PhDP/EcoInter/master/KNN/data/\"\n",
    "isfile(joinpath(\"data\", \"knn\", \"interactions.csv\")) || download(_project_root*\"mercure-interactions.csv\", joinpath(\"data\", \"knn\", \"interactions.csv\"))\n",
    "isfile(joinpath(\"data\", \"knn\", \"traits-codes.txt\")) || download(_project_root*\"mercure-trait-codes.txt\", joinpath(\"data\", \"knn\", \"traits-codes.txt\"))\n",
    "isfile(joinpath(\"data\", \"knn\", \"traits.csv\")) || download(_project_root*\"mercure-traits.csv\", joinpath(\"data\", \"knn\", \"traits.csv\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Predictions based only on interactions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the first part, we will make a prediction based only on interactions. Specifically, we will try to estimate the amount of information needed to make a prediction, by building a \"recommender\", *i.e.* an algorithm that will suggest a prey to a predator, based on what other predators with similar diets are eating. To do this, we will store the diet of every predator as a `Set`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data_interactions = joinpath(\"data\", \"knn\", \"interactions.csv\")\n",
    "preys = Set{Int64}[]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now fill the `preys` array, by reading all of the lines (have a look at the `interactions.csv` file to see how it is organized):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for (i,line) in enumerate(readlines(data_interactions))\n",
    "    if length(line) > 0\n",
    "        this_preys = parse.(Int64, split(line, \", \"))\n",
    "        push!(preys, Set(this_preys))\n",
    "    else\n",
    "        push!(preys, Set(Int64[]))\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at what the first 5 predators are eating:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "preys[1:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To get an idea of which preys have \"the same diet\", we will use the Tanimoto distance, which is the cardinality of the intersect of the diets divided by the cardinality of their union:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tanimoto(s1::T, s2::T) where {T <: Set} = length(s1 ∩ s2)/length(s1 ∪ s2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Tanimoto measure reflects similarity, and is bounded by 0 and 1, so we can simply substract it to unity to get a distance measure:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "D(s1,s2) = 1.0 - tanimoto(s1,s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "function success_rate_int_only(preys; k::Int64=3, top::Int64=5)\n",
    "    @assert 1 ≤ top ≤ 20\n",
    "    @assert 1 ≤ k ≤ (length(preys)-1)\n",
    "    attempts = zeros(Bool, length(preys))\n",
    "    successes = zeros(Bool, length(preys))\n",
    "    for prey_idx in 1:length(preys)\n",
    "        if length(preys[prey_idx]) > 2\n",
    "            sampled_preys = sample(collect(preys[prey_idx]), length(preys[prey_idx])-1, replace=false)\n",
    "            removed_prey = first(collect(filter(p -> !(p in sampled_preys), preys[prey_idx])))\n",
    "            test_preys = preys[filter(i -> i != prey_idx, 1:length(preys))]\n",
    "            neighbors = [D(Set(sampled_preys), p) for p in test_preys]\n",
    "            likely_preys = test_preys[partialsortperm(neighbors, 1:k)]\n",
    "            recos = countmap(vcat(collect.(likely_preys)...))\n",
    "            recommended = zeros(Bool, top)\n",
    "            for re in 1:top\n",
    "                if length(recos) > 0\n",
    "                    cmax = filter(f -> f.second == maximum(values(recos)), recos)\n",
    "                    recommended[re] = removed_prey in collect(keys(cmax))\n",
    "                    filter!(f -> f.second < maximum(values(recos)), recos)\n",
    "                end\n",
    "            end\n",
    "            successes[prey_idx] = sum(recommended)\n",
    "            attempts[prey_idx] = true\n",
    "        end\n",
    "    end\n",
    "    return sum(successes)/sum(attempts)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "k = 1:1:7\n",
    "r = [success_rate_int_only(preys; k=x, top=5) for x in k]\n",
    "scatter(k, r, lab=\"Top 5\")\n",
    "yaxis!((0.5,1), \"Success rate\")\n",
    "xaxis!(\"k\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adding traits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data_traits = joinpath(\"data\", \"knn\", \"traits.csv\")\n",
    "traits = Set{Int64}[]\n",
    "for (i,line) in enumerate(readlines(data_traits))\n",
    "    if length(line) > 0\n",
    "        this_traits = parse.(Int64, split(line, \", \"))\n",
    "        push!(traits, Set(this_traits))\n",
    "    else\n",
    "        push!(traits, Set(Int64[]))\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "function success_rate_with_traits(preys, traits; k::Int64=3, top::Int64=5, wt::Float64=0.5)\n",
    "    @assert 1 ≤ top ≤ 20\n",
    "    @assert 1 ≤ k ≤ (length(preys)-1)\n",
    "    @assert 0.0 <= wt <= 1.0\n",
    "    attempts = zeros(Bool, length(preys))\n",
    "    successes = zeros(Bool, length(preys))\n",
    "    for prey_idx in 1:length(preys)\n",
    "        if length(preys[prey_idx]) > 2\n",
    "            sampled_preys = sample(collect(preys[prey_idx]), length(preys[prey_idx])-1, replace=false)\n",
    "            removed_prey = first(collect(filter(p -> !(p in sampled_preys), preys[prey_idx])))\n",
    "            test_preys = preys[filter(i -> i != prey_idx, 1:length(preys))]\n",
    "            test_traits = traits[filter(i -> i != prey_idx, 1:length(traits))]\n",
    "            neighbors = [(1-wt)*D(Set(sampled_preys), test_preys[i])+wt*D(traits[prey_idx], test_traits[i]) for i in 1:length(test_preys)]\n",
    "            likely_preys = test_preys[partialsortperm(neighbors, 1:k)]\n",
    "            recos = countmap(vcat(collect.(likely_preys)...))\n",
    "            recommended = zeros(Bool, top)\n",
    "            for re in 1:top\n",
    "                if length(recos) > 0\n",
    "                    cmax = filter(f -> f.second == maximum(values(recos)), recos)\n",
    "                    recommended[re] = removed_prey in collect(keys(cmax))\n",
    "                    filter!(f -> f.second < maximum(values(recos)), recos)\n",
    "                end\n",
    "            end\n",
    "            successes[prey_idx] = sum(recommended)\n",
    "            attempts[prey_idx] = true\n",
    "        end\n",
    "    end\n",
    "    return sum(successes)/sum(attempts)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "success_rate_int_only(preys; k=4, top=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "success_rate_with_traits(preys, traits; k=4, top=3, wt=0.0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "wt = 0.0:0.1:1.0\n",
    "r = [success_rate_with_traits(preys, traits; k=4, top=3, wt=x) for x in wt]\n",
    "scatter(wt, r, leg=false)\n",
    "yaxis!((0.5,1), \"Success rate\")\n",
    "xaxis!(\"Relative importance of traits\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot(wt, r , leg=false)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.2.0",
   "language": "julia",
   "name": "julia-1.2"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.2.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}