6: LOF_algorithm.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "kernelspec": {
      "display_name": "Python 2",
      "language": "python",
      "name": "python2"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 2
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython2",
      "version": "2.7.13"
    },
    "colab": {
      "name": "LOF_algorithm.ipynb",
      "provenance": []
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jQSShIpI1C5D"
      },
      "source": [
        "# Outlier detection with LOF(Local Outlier Factor)\n",
        "\n",
        "Brief description about anamolous point : https://www.youtube.com/watch?v=MhYotnZSdC8"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hLr3qrU01C5K"
      },
      "source": [
        "Based on the clickstream event frequency pattern in Q2Q3_input.csv, apply LOF algorithm to\n",
        "calculate LOF for each point with the following initial settings:\n",
        "1. Set k = 2 and use Manhattan distance. \n",
        "2. Set k = 3 and use Euclidean distance.\n",
        "3. Report top 5 outliers \n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OuaA1nsU1C5L",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "75aa4a4c-7768-4e48-e355-ca19f66ba60d"
      },
      "source": [
        "#python 2.7\n",
        "%matplotlib inline\n",
        "%pylab inline\n",
        "import pandas as pd\n",
        "import numpy as np\n",
        "import seaborn as sns\n",
        "from scipy.spatial.distance import pdist, squareform"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Populating the interactive namespace from numpy and matplotlib\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "collapsed": true,
        "id": "r3ziZK0i1C5N"
      },
      "source": [
        "data_input = pd.read_csv('https://raw.githubusercontent.com/gulabpatel/Statistics/master/Dataset/Q2Q3_input.csv')"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zJPI3w371C5N",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 202
        },
        "outputId": "8e246601-716e-483e-854d-5d4f9acd7873"
      },
      "source": [
        "data_input.head()"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "   user_id  load_video  pause_video  play_video  seek_video  \\\n",
              "0        0         2.0          1.0         4.0         1.0   \n",
              "1        1         6.0         14.0        14.0         0.0   \n",
              "2        2         1.0          0.0         0.0         0.0   \n",
              "3        3         2.0          2.0         2.0         0.0   \n",
              "4        4         1.0          3.0        22.0        18.0   \n",
              "\n",
              "   speed_change_video  stop_video  \n",
              "0                 0.0         1.0  \n",
              "1                 0.0         1.0  \n",
              "2                 0.0         0.0  \n",
              "3                 0.0         1.0  \n",
              "4                 0.0         0.0  "
            ],
            "text/html": [
              "<div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>user_id</th>\n",
              "      <th>load_video</th>\n",
              "      <th>pause_video</th>\n",
              "      <th>play_video</th>\n",
              "      <th>seek_video</th>\n",
              "      <th>speed_change_video</th>\n",
              "      <th>stop_video</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>0</td>\n",
              "      <td>2.0</td>\n",
              "      <td>1.0</td>\n",
              "      <td>4.0</td>\n",
              "      <td>1.0</td>\n",
              "      <td>0.0</td>\n",
              "      <td>1.0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>1</td>\n",
              "      <td>6.0</td>\n",
              "      <td>14.0</td>\n",
              "      <td>14.0</td>\n",
              "      <td>0.0</td>\n",
              "      <td>0.0</td>\n",
              "      <td>1.0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>2</td>\n",
              "      <td>1.0</td>\n",
              "      <td>0.0</td>\n",
              "      <td>0.0</td>\n",
              "      <td>0.0</td>\n",
              "      <td>0.0</td>\n",
              "      <td>0.0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>3</td>\n",
              "      <td>2.0</td>\n",
              "      <td>2.0</td>\n",
              "      <td>2.0</td>\n",
              "      <td>0.0</td>\n",
              "      <td>0.0</td>\n",
              "      <td>1.0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>4</td>\n",
              "      <td>1.0</td>\n",
              "      <td>3.0</td>\n",
              "      <td>22.0</td>\n",
              "      <td>18.0</td>\n",
              "      <td>0.0</td>\n",
              "      <td>0.0</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hZZMJX-w4BpT",
        "outputId": "596bd7c8-c29f-4f23-aac6-174e2e09122e"
      },
      "source": [
        "data_input.iloc[1][1]"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "6.0"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "collapsed": true,
        "id": "-b8j6atr1C5O"
      },
      "source": [
        "#Reachdist function\n",
        "def reachdist(distance_df, observation, index):\n",
        "    return distance_df[observation][index]"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "collapsed": true,
        "id": "DGfehXTv1C5O"
      },
      "source": [
        "#LOF algorithm implementation from scratch\n",
        "def LOF_algorithm(data_input, distance_metric = \"cityblock\", p = 5):\n",
        "    distances = pdist(data_input.values, metric=distance_metric)\n",
        "    dist_matrix = squareform(distances)\n",
        "    distance_df = pd.DataFrame(dist_matrix)\n",
        "    \n",
        "    k = 2 if distance_metric == \"cityblock\" else 3 \n",
        "    observations = distance_df.columns\n",
        "    lrd_dict = {}\n",
        "    n_dist_index = {}\n",
        "    reach_array_dict = {}\n",
        "    \n",
        "    for observation in observations:\n",
        "        dist = distance_df[observation].nsmallest(k+1).iloc[k]\n",
        "        indexes = distance_df[distance_df[observation] <= dist].drop(observation).index\n",
        "        n_dist_index[observation] = indexes\n",
        "    \n",
        "        reach_dist_array = []\n",
        "        for index in indexes:\n",
        "            #make a function reachdist(observation, index)\n",
        "            dist_between_observation_and_index = reachdist(distance_df, observation, index)\n",
        "            dist_index =  distance_df[index].nsmallest(k+1).iloc[k]\n",
        "            reach_dist = max(dist_index, dist_between_observation_and_index)\n",
        "            reach_dist_array.append(reach_dist)\n",
        "        lrd_observation = len(indexes)/sum(reach_dist_array)\n",
        "        reach_array_dict[observation] = reach_dist_array\n",
        "        lrd_dict[observation] = lrd_observation\n",
        "        \n",
        "    #Calculate LOF\n",
        "    LOF_dict = {}\n",
        "    for observation in observations:\n",
        "        lrd_array = []\n",
        "        for index in n_dist_index[observation]:\n",
        "            lrd_array.append(lrd_dict[index])\n",
        "        LOF = sum(lrd_array)*sum(reach_array_dict[observation])/np.square(len(n_dist_index[observation]))\n",
        "        LOF_dict[observation] = LOF\n",
        "\n",
        "    return sorted(LOF_dict.items(), key=lambda x: x[1], reverse=True)[:p]"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "P6pE0TJO1C5P",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b1a21195-57a4-4e63-a8b8-5f5f050964fc"
      },
      "source": [
        "LOF_algorithm(data_input, p = 5)"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(19, 11.07),\n",
              " (525, 8.867228661749209),\n",
              " (66, 5.026785714285714),\n",
              " (638, 4.334727219682972),\n",
              " (177, 3.6292633292633294)]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-LM2I4zJ1C5P",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "89457421-f6e0-4722-f421-c446a8adf529"
      },
      "source": [
        "LOF_algorithm(data_input, p = 5, distance_metric = 'euclidean')"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(638, 3.0800716645705695),\n",
              " (525, 3.010316256261629),\n",
              " (19, 2.8402916620868903),\n",
              " (66, 2.801410266169121),\n",
              " (65, 2.6456528412196416)]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tfoTuq5R5zPh"
      },
      "source": [
        "----------------------"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Re3UUMeOtCUy"
      },
      "source": [
        "#Apply Sklearn "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AxbSymzkun1b"
      },
      "source": [
        "Documentation : https://scikit-learn.org/stable/modules/outlier_detection.html#isolation-forest\n",
        "\n",
        "https://scikit-learn.org/stable/auto_examples/miscellaneous/plot_anomaly_comparison.html"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HUSH-9Whtchm"
      },
      "source": [
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "from sklearn.model_selection import train_test_split\n",
        "from sklearn.neighbors import LocalOutlierFactor"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NDPZ5hDstBsk"
      },
      "source": [
        "df = data_input.copy()"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "o_6-Alm8tnsc"
      },
      "source": [
        "X_train, X_test = train_test_split(df, test_size=0.33, random_state=42)"
      ],
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "6dUCRQovtJ9S",
        "outputId": "a68d1640-925d-41ba-c3a4-50f76c52d46b"
      },
      "source": [
        "lof = LocalOutlierFactor(novelty=True)\n",
        "lof.fit(X_train)"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "/usr/local/lib/python2.7/dist-packages/sklearn/neighbors/lof.py:236: FutureWarning: default contamination parameter 0.1 will change in version 0.22 to \"auto\". This will change the predict method behavior.\n",
            "  FutureWarning)\n"
          ],
          "name": "stderr"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "LocalOutlierFactor(algorithm='auto', contamination='legacy', leaf_size=30,\n",
              "          metric='minkowski', metric_params=None, n_jobs=None,\n",
              "          n_neighbors=20, novelty=True, p=2)"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 12
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "eysV5AqyuTOe",
        "outputId": "edd29d90-91c3-4e05-a2b1-1042e2b795dd"
      },
      "source": [
        "lof.predict(X_test)  ##Inliers are labeled 1, while outliers are labeled -1."
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([-1,  1,  1,  1,  1, -1,  1,  1,  1,  1, -1,  1,  1,  1,  1, -1,  1,\n",
              "        1,  1,  1, -1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,\n",
              "        1,  1,  1,  1, -1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, -1,\n",
              "       -1,  1, -1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, -1,  1, -1,  1,\n",
              "        1,  1,  1,  1,  1,  1,  1,  1,  1,  1, -1,  1,  1,  1,  1,  1,  1,\n",
              "        1,  1, -1, -1,  1,  1,  1,  1, -1,  1,  1,  1,  1,  1,  1, -1,  1,\n",
              "        1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, -1,  1,  1,\n",
              "        1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1, -1,\n",
              "        1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,\n",
              "       -1, -1,  1,  1,  1,  1,  1,  1,  1,  1, -1,  1, -1,  1,  1,  1,  1,\n",
              "        1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,\n",
              "        1,  1, -1,  1,  1, -1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,\n",
              "        1, -1,  1,  1,  1,  1, -1,  1,  1, -1,  1, -1,  1, -1, -1,  1,  1,\n",
              "        1,  1,  1,  1,  1,  1,  1, -1,  1])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 13
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0uuD3SlduYFD",
        "outputId": "ee0eb0be-b125-4b44-a0f2-81e5e162a81e"
      },
      "source": [
        "lof.decision_function(X_test)"
      ],
      "execution_count": 14,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([-0.22286463,  0.40121049,  0.39382115,  0.37299218,  0.39349483,\n",
              "       -0.64078132,  0.39626584,  0.39433938,  0.38184346,  0.395146  ,\n",
              "       -0.20723262,  0.37445958,  0.38395417,  0.33009596,  0.38503253,\n",
              "       -0.15691907,  0.23951273,  0.39115323,  0.36645194,  0.34440098,\n",
              "       -0.61824998,  0.37799249,  0.39715424,  0.40278667,  0.37995124,\n",
              "        0.38409949,  0.37502625,  0.37463909,  0.37173208,  0.41110184,\n",
              "        0.32771888,  0.39461345,  0.3877664 ,  0.41798382,  0.17272477,\n",
              "        0.39190799,  0.39170294,  0.39037857, -0.12602858,  0.38612983,\n",
              "        0.37923225,  0.32274755,  0.35989714,  0.38964145,  0.39841785,\n",
              "        0.13624181,  0.40628758,  0.36318703,  0.33587816,  0.3746578 ,\n",
              "       -0.30842027, -0.30322515,  0.38127225, -0.11446579,  0.35012343,\n",
              "        0.39455884,  0.27578984,  0.29388924,  0.35252845,  0.38465442,\n",
              "        0.30475718,  0.39427387,  0.37814206,  0.3240583 , -0.20092219,\n",
              "        0.38624432, -0.0172637 ,  0.37628522,  0.39376907,  0.41031933,\n",
              "        0.39589931,  0.29256308,  0.36063242,  0.3219224 ,  0.39711289,\n",
              "        0.10134387,  0.36896381,  0.40670536, -0.48818739,  0.38770589,\n",
              "        0.37858314,  0.37635146,  0.29359471,  0.36085761,  0.38044163,\n",
              "        0.34986455,  0.35201135, -1.04305862, -0.00440518,  0.33727584,\n",
              "        0.17814946,  0.39031827,  0.34659039, -0.87420656,  0.32262036,\n",
              "        0.39076083,  0.15722489,  0.35214737,  0.37544902,  0.39037857,\n",
              "       -0.00462662,  0.39033723,  0.11845774,  0.26180562,  0.34543283,\n",
              "        0.13349725,  0.38946999,  0.41881053,  0.39272096,  0.42116922,\n",
              "        0.386362  ,  0.40308873,  0.34544456,  0.40813264,  0.40661543,\n",
              "        0.32818078, -0.82246427,  0.39036584,  0.33825181,  0.2909503 ,\n",
              "        0.35412036,  0.36315524,  0.38657062,  0.27259543,  0.38749924,\n",
              "        0.15767517,  0.36702149,  0.41351884,  0.37087968,  0.42116922,\n",
              "        0.42261798,  0.32877198,  0.36702622,  0.41524415,  0.38652916,\n",
              "       -0.51676567,  0.40761962,  0.36827027,  0.37006995,  0.42609279,\n",
              "        0.33953206,  0.38545726,  0.37266691,  0.17492096,  0.40541701,\n",
              "        0.36521066,  0.36358833,  0.29166613,  0.40314992,  0.40657789,\n",
              "        0.39055998,  0.36736264,  0.37673795, -0.62632171, -0.55457443,\n",
              "        0.35461431,  0.43789199,  0.40114039,  0.39052319,  0.35689371,\n",
              "        0.14922214,  0.4070404 ,  0.37401854, -0.94678439,  0.37032706,\n",
              "       -0.66648331,  0.40913218,  0.37814206,  0.2073955 ,  0.40358267,\n",
              "        0.36461409,  0.3886919 ,  0.40322004,  0.42599225,  0.41002523,\n",
              "        0.40496411,  0.37533354,  0.21654021,  0.39046753,  0.37636565,\n",
              "        0.39703526,  0.41769865,  0.42228703,  0.38662268,  0.37057402,\n",
              "        0.39223725,  0.38344552,  0.30167346,  0.31652915, -3.13779022,\n",
              "        0.33624914,  0.38309639, -0.16705496,  0.37100234,  0.38062343,\n",
              "        0.21149129,  0.43344867,  0.41148847,  0.42116922,  0.32649782,\n",
              "        0.41377636,  0.39828257,  0.40418704,  0.1097979 ,  0.36815372,\n",
              "       -0.11941937,  0.38777065,  0.39685578,  0.38784537,  0.06952873,\n",
              "       -0.84997715,  0.38971455,  0.40773103, -0.59749373,  0.39042582,\n",
              "       -0.00657381,  0.05407696, -0.10335924, -0.22844801,  0.35361847,\n",
              "        0.32206127,  0.41693028,  0.37375918,  0.19411965,  0.3901339 ,\n",
              "        0.36910565,  0.39029552,  0.3899639 , -0.087938  ,  0.3828688 ])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 14
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aVDoB6j_ur9C"
      },
      "source": [
        "------------------------------"
      ]
    }
  ]
}