TME2-2/TME2-2-melki-herbelot.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "# TME 2 - 2 : Inférence collective\n",
    "\n",
    "## Partie 1 - Classifieur local"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nombre de sites : 265\n",
      "Nombre d'attributs par site : 1703\n",
      "\n",
      "=== url dataframe ===\n",
      "0                            robios8.me.wisc.edu\n",
      "1    robios8.me.wisc.edu/~lumelsky/lumelsky.html\n",
      "2                           cae.wisc.edu/~ece552\n",
      "3                                    cs.wisc.edu\n",
      "4                             cs.wisc.edu/condor\n",
      "Name: 0, dtype: object\n",
      "\n",
      "=== labels dataframe ===\n",
      "0    project\n",
      "1    faculty\n",
      "2     course\n",
      "3     course\n",
      "4    project\n",
      "Name: 1704, dtype: object\n",
      "Distribution : (array(['course', 'faculty', 'project', 'staff', 'student'], dtype=object), array([ 76,  35,  22,  10, 122]))\n",
      "\n",
      "=== attributes dataframe ===\n",
      "   1     2     3     4     5     6     7     8     9     10    ...   1694  \\\n",
      "0     0     0     0     0     0     0     0     0     1     0  ...      0   \n",
      "1     0     0     0     0     0     0     0     0     1     0  ...      0   \n",
      "2     0     0     0     0     0     0     0     0     0     0  ...      0   \n",
      "3     0     0     0     0     0     0     0     0     0     0  ...      0   \n",
      "4     0     0     0     0     0     0     0     0     1     0  ...      0   \n",
      "\n",
      "   1695  1696  1697  1698  1699  1700  1701  1702  1703  \n",
      "0     0     0     0     0     0     0     0     1     0  \n",
      "1     0     0     0     0     0     0     0     0     0  \n",
      "2     0     0     0     0     0     0     1     0     0  \n",
      "3     0     0     0     0     0     1     0     0     0  \n",
      "4     0     0     0     0     0     0     0     1     0  \n",
      "\n",
      "[5 rows x 1703 columns]\n"
     ]
    }
   ],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "\n",
    "# Constantes : \n",
    "path = 'WebKB/'\n",
    "univ = 'wisconsin'\n",
    "percentage_unlabeled = 0.4\n",
    "\n",
    "# On parse les données\n",
    "#path = '/Users/ACHANGER/Desktop/UPMC/FDMS-2/WebKB/'\n",
    "# Fichier 'content' contient des lignes « [URL]\\t[Attributs:suite de nombres]\\t[Étiquette] »\n",
    "content = pd.read_csv(path + 'content/'+univ+'.content', sep ='\\t', header=None)\n",
    "# Fichier 'cites' contient des liens « [destination] [source] »\n",
    "cites   = pd.read_csv(path + 'cites/'+univ+'.cites',     sep =' ', header=None)\n",
    "\n",
    "# Les identifiants des sites web sont leur URL :\n",
    "M = len(content)\n",
    "print(\"Nombre de sites :\", M)\n",
    "N = content.shape[1] - 2\n",
    "print(\"Nombre d'attributs par site :\", N)\n",
    "n_labels = 5\n",
    "url = content.iloc[:,0] \n",
    "labels = content.iloc[:,-1] \n",
    "attributes = content.drop([0, N+1],axis=1)\n",
    "\n",
    "def clean_url(u):\n",
    "    return u.replace(\"http://\", \"\").replace(\"www.\", \"\")\n",
    "\n",
    "url = url.apply(clean_url)\n",
    "print(\"\\n=== url dataframe ===\")\n",
    "print(url.head())\n",
    "print(\"\\n=== labels dataframe ===\")\n",
    "print(labels.head())\n",
    "print(\"Distribution :\", np.unique(labels, return_counts=True))\n",
    "print(\"\\n=== attributes dataframe ===\")\n",
    "print(attributes.head())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=== unlabeled ===\n",
      "{'cs.wisc.edu',\n",
      " 'cs.wisc.edu/condor',\n",
      " 'cs.wisc.edu/condor/next.html',\n",
      " 'cs.wisc.edu/coral',\n",
      " 'cs.wisc.edu/exodus',\n",
      " 'cs.wisc.edu/paradise',\n",
      " 'cs.wisc.edu/shore',\n",
      " 'cs.wisc.edu/~agupta/agupta.html',\n",
      " 'cs.wisc.edu/~alain/alain.html',\n",
      " 'cs.wisc.edu/~amos/amos.html',\n",
      " 'cs.wisc.edu/~arch/uwarch/courses/cs354.html',\n",
      " 'cs.wisc.edu/~arch/uwarch/courses/cs552.html',\n",
      " 'cs.wisc.edu/~arch/uwarch/courses/cs752.html',\n",
      " 'cs.wisc.edu/~arch/uwarch/courses/cs757.html',\n",
      " 'cs.wisc.edu/~ashraf/ashraf.html',\n",
      " 'cs.wisc.edu/~bach/bach.html',\n",
      " 'cs.wisc.edu/~bart/cs736.html',\n",
      " 'cs.wisc.edu/~ben/ben.html',\n",
      " 'cs.wisc.edu/~bestor/bestor.html',\n",
      " 'cs.wisc.edu/~bestor/cs302/cs302.html',\n",
      " 'cs.wisc.edu/~bockrath/bockrath.html',\n",
      " 'cs.wisc.edu/~brad/brad.html',\n",
      " 'cs.wisc.edu/~breach/breach.html',\n",
      " 'cs.wisc.edu/~caol/caol.html',\n",
      " 'cs.wisc.edu/~carey/carey.html',\n",
      " 'cs.wisc.edu/~cs110/cs110.html',\n",
      " 'cs.wisc.edu/~cs132-1/cs132.html',\n",
      " 'cs.wisc.edu/~cs132-3/cs132.html',\n",
      " 'cs.wisc.edu/~cs302/course.html',\n",
      " 'cs.wisc.edu/~cs302/cs302.html',\n",
      " 'cs.wisc.edu/~cs564-1/cs564.html',\n",
      " 'cs.wisc.edu/~cs577-1/cs577.html',\n",
      " 'cs.wisc.edu/~cs640-1/cs640.html',\n",
      " 'cs.wisc.edu/~cs737-1/cs737.html',\n",
      " 'cs.wisc.edu/~cs838-2/cs838.html',\n",
      " 'cs.wisc.edu/~david/david.html',\n",
      " 'cs.wisc.edu/~dburger/dburger.html',\n",
      " 'cs.wisc.edu/~devise',\n",
      " 'cs.wisc.edu/~dyer/cs540.html',\n",
      " 'cs.wisc.edu/~dyer/cs766.html',\n",
      " 'cs.wisc.edu/~dyer/dyer.html',\n",
      " 'cs.wisc.edu/~falsafi/falsafi.html',\n",
      " 'cs.wisc.edu/~fischer/cs701.html',\n",
      " 'cs.wisc.edu/~galileo',\n",
      " 'cs.wisc.edu/~geery/geery.html',\n",
      " 'cs.wisc.edu/~goodman/goodman.html',\n",
      " 'cs.wisc.edu/~guangshu/guangshu.html',\n",
      " 'cs.wisc.edu/~hcl/cs302.html',\n",
      " 'cs.wisc.edu/~hcl/hcl.html',\n",
      " 'cs.wisc.edu/~hummert/cs110/cs110.html',\n",
      " 'cs.wisc.edu/~hummert/hummert.html',\n",
      " 'cs.wisc.edu/~iigor/iigor.html',\n",
      " 'cs.wisc.edu/~iss/userid.html',\n",
      " 'cs.wisc.edu/~jherro/jherro.html',\n",
      " 'cs.wisc.edu/~joev/joev.html',\n",
      " 'cs.wisc.edu/~jonb/cs132/index.html',\n",
      " 'cs.wisc.edu/~jonb/jonb.html',\n",
      " 'cs.wisc.edu/~jussi/jussi.html',\n",
      " 'cs.wisc.edu/~jyothi/jyothi.html',\n",
      " 'cs.wisc.edu/~kaxiras/kaxiras.html',\n",
      " 'cs.wisc.edu/~larus/larus.html',\n",
      " 'cs.wisc.edu/~leavy/leavy.html',\n",
      " 'cs.wisc.edu/~lederman/lederman.html',\n",
      " 'cs.wisc.edu/~lhl/lhl.html',\n",
      " 'cs.wisc.edu/~lloyd/lloyd.html',\n",
      " 'cs.wisc.edu/~markhill/cs752.html',\n",
      " 'cs.wisc.edu/~markhill/cs752/fall94-95/cs752.html',\n",
      " 'cs.wisc.edu/~markhill/markhill.html',\n",
      " 'cs.wisc.edu/~morgan/morgan.html',\n",
      " 'cs.wisc.edu/~moshovos/moshovos.html',\n",
      " 'cs.wisc.edu/~mscalar',\n",
      " 'cs.wisc.edu/~myuin/myuin.html',\n",
      " 'cs.wisc.edu/~natassa/natassa.html',\n",
      " 'cs.wisc.edu/~paradyn',\n",
      " 'cs.wisc.edu/~praveen/projects/seq.html',\n",
      " 'cs.wisc.edu/~pubs/faculty-info/miron.html',\n",
      " 'cs.wisc.edu/~raghu/raghu.html',\n",
      " 'cs.wisc.edu/~rahul/rahul.html',\n",
      " 'cs.wisc.edu/~raji/raji.html',\n",
      " 'cs.wisc.edu/~ratliff/132.html',\n",
      " 'cs.wisc.edu/~ratliff/ratliff.html',\n",
      " 'cs.wisc.edu/~sally/cs132.html',\n",
      " 'cs.wisc.edu/~sally/sally.html',\n",
      " 'cs.wisc.edu/~schoinas/schoinas.html',\n",
      " 'cs.wisc.edu/~seitz/interp/interp.html',\n",
      " 'cs.wisc.edu/~seitz/interp/vmorph.html',\n",
      " 'cs.wisc.edu/~seitz/pmotion.html',\n",
      " 'cs.wisc.edu/~seitz/seitz.html',\n",
      " 'cs.wisc.edu/~shavlik/cs540-all.html',\n",
      " 'cs.wisc.edu/~so/so.html',\n",
      " 'cs.wisc.edu/~sohi/sohi.html',\n",
      " 'cs.wisc.edu/~stever/stever.html',\n",
      " 'cs.wisc.edu/~suhui/cs132.html',\n",
      " 'cs.wisc.edu/~suhui/suhui.html',\n",
      " 'cs.wisc.edu/~swanderb/swanderb.html',\n",
      " 'cs.wisc.edu/~toonen/toonen.html',\n",
      " 'cs.wisc.edu/~tsiolis/tsiolis.html',\n",
      " 'cs.wisc.edu/~vijay/vijay.html',\n",
      " 'cs.wisc.edu/~watrous/watrous.html',\n",
      " 'cs.wisc.edu/~wenger/wenger.html',\n",
      " 'cs.wisc.edu/~wwt',\n",
      " 'cs.wisc.edu/~yannis/yannis.html',\n",
      " 'ece.wisc.edu/~jes/ece752.html',\n",
      " 'engr.wisc.edu/me/faculty/duffie_neil.html',\n",
      " 'robios8.me.wisc.edu',\n",
      " 'robios8.me.wisc.edu/~lumelsky/lumelsky.html'}\n",
      "Voisins de cs.wisc.edu/~schnarr/schnarr.html :\n",
      "(url, label, unlabeled)\n",
      "[('cs.wisc.edu/~schnarr/schnarr.html', 4, False), ('cs.wisc.edu/~wwt', 2, True), ('cs.wisc.edu/~larus/larus.html', 1, True)]\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "from pprint import pprint\n",
    "\n",
    "# Conversion des labels depuis string vers int\n",
    "classes_number = len(np.unique(labels))\n",
    "url_to_labels = dict(zip(url, labels))\n",
    "unique_labels = sorted(np.unique(labels))\n",
    "labels_to_id = dict(zip(unique_labels, range(len(unique_labels))))\n",
    "url_pos = dict(zip(url, range(M)))\n",
    "\n",
    "# Parsing du réseau depuis fichier 'cites'\n",
    "network = {}\n",
    "for line in cites.iterrows():\n",
    "    src = clean_url(line[1][1])\n",
    "    dest = clean_url(line[1][0])\n",
    "    if src in network:\n",
    "        network[src].add(dest)\n",
    "    else:\n",
    "        network[src] = set([dest])\n",
    "        \n",
    "# Suppression de labels\n",
    "remove_cluster = True\n",
    "if remove_cluster:\n",
    "    rand_noeud = np.random.choice(list(network.keys()))\n",
    "    voisins = deque(network[rand_noeud]) # voisins est de type \"queue\" : FIFO\n",
    "    unlabeled = set([rand_noeud])\n",
    "    while len(unlabeled) < M*percentage_unlabeled and voisins: # tq 'voisin' non vide\n",
    "        #print(\"voisins : \", voisins)\n",
    "        voisin = voisins.popleft()\n",
    "        unlabeled.add(voisin)\n",
    "        if voisin in network:\n",
    "             voisins.extend(set(network[voisin]) - unlabeled)\n",
    "        if not voisins: # si 'voisin' vide\n",
    "            voisins = deque([np.random.choice(list(network.keys()))])        \n",
    "else:\n",
    "    unlabeled = np.random.choice(url, size=int(M*percentage_unlabeled))\n",
    "    print(\"\\nUnlabeled items:\")\n",
    "    print(unlabeled)\n",
    "    example_page = np.random.choice(url)\n",
    "    print(\"Page d'exemple:\", example_page, \"dans unlabeled :\", example_page in unlabeled)\n",
    "\n",
    "print(\"=== unlabeled ===\")\n",
    "pprint(unlabeled)\n",
    "\n",
    "example_page = np.random.choice(url)\n",
    "print(\"Voisins de \"+example_page+\" :\")\n",
    "if example_page in network:\n",
    "    print(\"(url, label, unlabeled)\")\n",
    "    print([(v, labels_to_id[url_to_labels[v]], v in unlabeled) for v in network[example_page]])\n",
    "else:\n",
    "    print(\"Pas de citations depuis cette page\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'img/graph.pdf'"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from graphviz import Digraph\n",
    "\n",
    "graph = Digraph()\n",
    "labeled = set(url) - unlabeled\n",
    "\n",
    "for n in labeled:\n",
    "    graph.node(n,n)\n",
    "for n in unlabeled:\n",
    "    graph.node(n, n, {'color':'blue'})\n",
    "for noeud, voisins in network.items():\n",
    "    graph.edges([(noeud, voisin) for voisin in voisins])\n",
    "\n",
    "graph.render(\"img/graph\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Voisinage de la page d'exemple : [ 0.  0.  0.  0.  1.]\n"
     ]
    }
   ],
   "source": [
    "# Comptage des classes des voisins\n",
    "# Dans 'count' : 1 ligne = 1 url, 1 colonne = 1 classe (classes triées par ordre alphabétique) \n",
    "count = np.zeros((M, len(unique_labels)))\n",
    "\n",
    "# On itère sur tous les noeuds qui ont des liens sortants\n",
    "for noeud, voisins in network.items():\n",
    "    position = url_pos[noeud]\n",
    "    for voisin in network[noeud]:\n",
    "        voisin_label = labels_to_id[url_to_labels[voisin]]\n",
    "        if voisin not in unlabeled:\n",
    "            count[position, voisin_label] += 1\n",
    "            \n",
    "print(\"Voisinage de la page d'exemple :\", count[url_pos[example_page]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X.shape : (265, 1718)\n",
      "Searching best adaboost estimator\n",
      "CPU times: user 244 ms, sys: 28 ms, total: 272 ms\n",
      "Wall time: 4.16 s\n",
      "Score : 0.8427672955974843\n",
      "====================\n",
      "Searching best knn estimator\n",
      "CPU times: user 300 ms, sys: 20 ms, total: 320 ms\n",
      "Wall time: 1.87 s\n",
      "Score : 0.6037735849056604\n",
      "====================\n",
      "Searching best rf estimator\n",
      "CPU times: user 1.28 s, sys: 20 ms, total: 1.3 s\n",
      "Wall time: 17.5 s\n",
      "Score : 0.8553459119496856\n",
      "====================\n",
      "Searching best svc estimator\n",
      "CPU times: user 436 ms, sys: 16 ms, total: 452 ms\n",
      "Wall time: 2.81 s\n",
      "Score : 0.7861635220125787\n",
      "====================\n",
      "Aggrégation avec VotingClassifier\n",
      "Score vote : 0.660377358491\n",
      "Estimateur choisi : <class 'sklearn.ensemble.forest.RandomForestClassifier'>\n",
      "Score sur le test set : 0.669811320755\n"
     ]
    },
    {
     "ename": "ValueError",
     "evalue": "dictionary update sequence element #0 has length 5; 2 is required",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mValueError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-53-dcf373c5ca16>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m    112\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    113\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Score sur le test set :\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbest_clf\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mscore\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mX_test\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtrue_labels\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 114\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Proportion des labels :\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdict\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0munique\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mY\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mreturn_counts\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mTrue\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    115\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Prédiction sur le test set :\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbest_clf\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpredict\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mX_test\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    116\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Vrais labels :\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtrue_labels\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mValueError\u001b[0m: dictionary update sequence element #0 has length 5; 2 is required"
     ]
    }
   ],
   "source": [
    "# Classification\n",
    "\n",
    "from sklearn import preprocessing\n",
    "from sklearn.svm import SVC\n",
    "from sklearn.ensemble import RandomForestClassifier, AdaBoostClassifier, VotingClassifier \n",
    "from sklearn.grid_search import GridSearchCV\n",
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "\n",
    "\n",
    "def aggreg_neighbors(X, mode=\"count\"):\n",
    "    \"\"\" Transforms the matrix of neighborhood given a mode\n",
    "    :param X: The matrix of neighbors\n",
    "    :param mode: string, optional (default=\"count\")\n",
    "        Specificies the mode of the aggregator (Available: \"mode, proportion, count, exist\")\n",
    "    :return: A matrix of the same shape as X\n",
    "    \"\"\"    \n",
    "    if mode == \"mode\": # garde seulement le plus fréquent\n",
    "        mat = np.zeros_like(X)\n",
    "        if len(X.shape) > 1:\n",
    "            for line, idx in zip(mat, X.argmax(axis=1)):\n",
    "                line[idx] = 1\n",
    "        else:\n",
    "            mat[X.argmax()] = 1\n",
    "        return mat\n",
    "    elif mode == \"proportion\":\n",
    "        mat = X.copy()\n",
    "        for line in mat:\n",
    "            line /= np.linalg.norm(line, ord=1)\n",
    "        return mat\n",
    "    elif mode == \"count\":\n",
    "        return X.copy()\n",
    "    elif mode == \"exist\":\n",
    "        mat = X.copy()\n",
    "        mat[mat != 0] = 1\n",
    "        return mat\n",
    "    else:\n",
    "        print(\"Erreur, mode inconnu :\" + mode)\n",
    "        return None\n",
    "\n",
    "    \n",
    "def count_transform(count):\n",
    "    if len(count.shape) > 1:\n",
    "        return np.concatenate((aggreg_neighbors(count),\n",
    "                          aggreg_neighbors(count, mode=\"mode\"),\n",
    "                          aggreg_neighbors(count, mode=\"exist\")),\n",
    "                          axis=1)\n",
    "    else:\n",
    "        return np.concatenate((aggreg_neighbors(count),\n",
    "                          aggreg_neighbors(count, mode=\"mode\"),\n",
    "                          aggreg_neighbors(count, mode=\"exist\")))\n",
    "        \n",
    "X = np.concatenate((np.array(attributes), count_transform(count)),\n",
    "                   axis=1)\n",
    "print(\"X.shape :\", X.shape)\n",
    "X_scale = preprocessing.scale(X)\n",
    "Y = np.array([labels_to_id[lab] for lab in labels])\n",
    "\n",
    "idx = set(range(M))\n",
    "test_idx = set([url_pos[u] for u in unlabeled])\n",
    "train_idx = list(idx - test_idx)\n",
    "test_idx = list(test_idx)\n",
    "\n",
    "X_train, X_test = X_scale[train_idx], X_scale[test_idx]\n",
    "Y_train, Y_test = Y[train_idx], Y[test_idx]\n",
    "true_labels = np.array([labels_to_id[lab] for lab in labels])[test_idx]\n",
    "\n",
    "\n",
    "estimators = {\"rf\":{\"clf\":RandomForestClassifier(),\n",
    "                    \"params\":{\"n_estimators\":np.arange(2, 100, 10),\n",
    "                              \"max_features\":(\"auto\", \"sqrt\", \"log2\", None),\n",
    "                              \"max_depth\":np.arange(2, 20, 5)}},\n",
    "              \"svc\":{\"clf\":SVC(),\n",
    "                     \"params\":{\"C\":np.logspace(-2, 2, 7),\n",
    "                              \"kernel\":(\"linear\", \"poly\", \"rbf\"),\n",
    "                              \"class_weight\":(None, \"balanced\")}},\n",
    "              \"knn\":{\"clf\":KNeighborsClassifier(),\n",
    "                     \"params\":{\"n_neighbors\":np.arange(2, 100, 10), \n",
    "                               \"weights\":(\"uniform\", \"distance\"), \n",
    "                               \"algorithm\":(\"auto\", \"ball_tree\", \"kd_tree\", \"brute\")}},\n",
    "              \"adaboost\":{\"clf\":AdaBoostClassifier(),\n",
    "                          \"params\":{\"base_estimator\":(None, RandomForestClassifier()), \n",
    "                                    \"n_estimators\":np.linspace(5, 50, 5, dtype=int), \n",
    "                                    \"learning_rate\":np.logspace(-1,1,3)}}\n",
    "             }\n",
    "\n",
    "choice = \"adaboost\"\n",
    "\n",
    "best_clf = None\n",
    "best_score = 0\n",
    "estimators_aggreg = []\n",
    "for choice in estimators.keys():\n",
    "    print(\"Searching best \"+choice+\" estimator\")\n",
    "    gridsearch = GridSearchCV(estimators[choice][\"clf\"], estimators[choice][\"params\"], n_jobs=-1, verbose=0)\n",
    "    %time gridsearch.fit(X_train, Y_train)\n",
    "    estimators_aggreg.append((choice, gridsearch.best_estimator_))\n",
    "    print(\"Score :\", gridsearch.best_score_)\n",
    "    if gridsearch.best_score_ > best_score:\n",
    "        best_clf = gridsearch.best_estimator_\n",
    "        best_score = gridsearch.best_score_\n",
    "    print(20*\"=\")\n",
    "\n",
    "print(\"Aggrégation avec VotingClassifier\")\n",
    "vote_clf = VotingClassifier(estimators_aggreg)\n",
    "vote_clf.fit(X_train, Y_train)\n",
    "vote_score = vote_clf.score(X_test, true_labels) \n",
    "print(\"Score vote :\", vote_score)\n",
    "\n",
    "if vote_score > best_score:\n",
    "    best_clf = vote_clf\n",
    "\n",
    "print(\"Estimateur choisi :\", type(best_clf))\n",
    "\n",
    "print(\"Score sur le test set :\", best_clf.score(X_test, true_labels))\n",
    "print(\"Proportion des labels :\", dict(np.unique(Y, return_counts=True)))\n",
    "print(\"Prédiction sur le test set :\", best_clf.predict(X_test))\n",
    "print(\"Vrais labels :\", true_labels)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Partie 2 : ICA\n",
    "\n",
    "On va réutiliser les données de la partie précédente pour la 1ère phase, _bootstraping_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unlabeled indexes :  [0, 1, 3, 4, 5, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 20, 23, 24, 26, 27, 28, 30, 33, 35, 36, 42, 43, 46, 47, 49, 52, 53, 63, 65, 66, 69, 71, 75, 76, 81, 84, 85, 86, 92, 98, 101, 102, 104, 107, 111, 112, 117, 118, 119, 120, 123, 126, 128, 129, 131, 132, 134, 139, 140, 141, 142, 143, 145, 146, 147, 160, 161, 164, 167, 168, 177, 184, 188, 190, 191, 192, 195, 196, 201, 202, 209, 211, 212, 213, 214, 215, 221, 224, 229, 233, 234, 236, 242, 243, 248, 249, 254, 255, 256, 261, 263]\n",
      "Y[test_idx] : [4 4 4 4 4 4 4 4 2 4 4 1 4 4 4 4 0 1 0 4 4 0 0 4 4 4 1 4 0 0 4 0 0 4 0 4 4\n",
      " 1 4 4 0 0 1 4 0 4 0 4 0 0 4 0 4 4 4 4 4 0 4 4 0 4 1 4 4 4 4 0 0 1 4 4 4 4\n",
      " 4 4 2 4 1 4 4 0 4 0 4 4 2 4 2 4 0 4 1 4 0 4 4 4 4 4 4 4 4 1 0 4]\n",
      "true_labels : [2 1 0 2 2 2 2 2 2 4 4 1 0 0 0 0 4 1 0 4 4 0 4 4 4 4 1 0 0 0 0 0 0 0 0 0 0\n",
      " 1 4 2 0 0 1 4 0 2 4 1 4 0 4 0 4 4 4 4 4 0 4 4 4 4 1 4 3 1 4 0 0 1 4 4 2 4\n",
      " 4 2 2 1 1 4 4 0 4 0 1 4 2 2 2 4 0 4 1 4 0 4 4 4 4 4 4 3 2 1 0 1]\n",
      "======= Itération 0 =======\n",
      "Y[test_idx] : [4 4 4 4 4 4 4 4 4 4 4 1 4 4 4 4 0 1 0 4 4 0 0 4 4 4 1 4 0 0 4 4 0 4 0 4 4\n",
      " 1 4 4 0 0 1 4 0 4 0 4 0 0 4 0 4 4 4 4 4 0 4 4 0 4 1 4 4 4 4 0 4 1 4 4 4 4\n",
      " 4 4 4 4 1 4 4 0 4 0 4 4 4 4 4 4 4 4 1 4 0 4 4 4 4 4 4 4 4 4 4 4]\n",
      "true_labels : [2 1 0 2 2 2 2 2 2 4 4 1 0 0 0 0 4 1 0 4 4 0 4 4 4 4 1 0 0 0 0 0 0 0 0 0 0\n",
      " 1 4 2 0 0 1 4 0 2 4 1 4 0 4 0 4 4 4 4 4 0 4 4 4 4 1 4 3 1 4 0 0 1 4 4 2 4\n",
      " 4 2 2 1 1 4 4 0 4 0 1 4 2 2 2 4 0 4 1 4 0 4 4 4 4 4 4 3 2 1 0 1]\n",
      "======= Itération 1 =======\n",
      "Y[test_idx] : [4 4 4 4 4 4 4 4 4 4 4 1 4 4 4 4 0 1 0 4 4 0 0 4 4 4 1 4 0 0 4 4 0 4 0 4 4\n",
      " 1 4 4 0 0 1 4 0 4 0 4 0 0 4 0 4 4 4 4 4 0 4 4 0 4 1 4 4 4 4 0 4 1 4 4 4 4\n",
      " 4 4 4 4 1 4 4 0 4 0 4 4 4 4 4 4 4 4 1 4 0 4 4 4 4 4 4 4 4 4 4 4]\n",
      "true_labels : [2 1 0 2 2 2 2 2 2 4 4 1 0 0 0 0 4 1 0 4 4 0 4 4 4 4 1 0 0 0 0 0 0 0 0 0 0\n",
      " 1 4 2 0 0 1 4 0 2 4 1 4 0 4 0 4 4 4 4 4 0 4 4 4 4 1 4 3 1 4 0 0 1 4 4 2 4\n",
      " 4 2 2 1 1 4 4 0 4 0 1 4 2 2 2 4 0 4 1 4 0 4 4 4 4 4 4 3 2 1 0 1]\n",
      "Fini.\n",
      "Score :  0.584905660377\n"
     ]
    }
   ],
   "source": [
    "from sklearn.metrics import accuracy_score\n",
    "\n",
    "\n",
    "test_idx = sorted(test_idx)\n",
    "ordering = np.copy(test_idx)\n",
    "\n",
    "print(\"Unlabeled indexes : \", test_idx)\n",
    "#print(\"Y before :\", Y)\n",
    "Y[test_idx] = best_clf.predict(X_test)\n",
    "#print(\"Y after  :\", Y)\n",
    "old_labels = np.zeros_like(Y[test_idx]) - 1\n",
    "print(\"Y[test_idx] :\", Y[test_idx])\n",
    "print(\"true_labels :\", true_labels)\n",
    "\n",
    "max_iter = 5\n",
    "i = 0\n",
    "while not np.allclose(old_labels, Y[test_idx]) and i<max_iter:\n",
    "    print(\"======= Itération %d =======\" % i)\n",
    "    # On itère sur tous les noeuds qui ont des liens sortants\n",
    "    np.random.shuffle(ordering)\n",
    "    for position in ordering:\n",
    "        noeud = url[position]\n",
    "        count_noeud = np.zeros((classes_number,))\n",
    "        if noeud in network:\n",
    "            for voisin in network[noeud]:\n",
    "                vlabel = Y[url_pos[voisin]]\n",
    "                count_noeud[vlabel] += 1\n",
    "                transform = count_transform(count_noeud)\n",
    "                X[position, N:] = transform\n",
    "    old_labels = Y[test_idx]\n",
    "    Y[test_idx] = best_clf.predict(X[test_idx])\n",
    "    print(\"Y[test_idx] :\", Y[test_idx])\n",
    "    print(\"true_labels :\", true_labels)\n",
    "    \n",
    "    i += 1\n",
    "    \n",
    "print(\"Fini.\")\n",
    "print(\"Score : \", accuracy_score(Y[test_idx], true_labels))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Partie 3 : Propagation de labels\n",
    "\n",
    "* $f_\\theta(x_i)$ est le score du site n°$i$, de représentation $x_i$ pour le label représenté par $\\theta$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Recherche de theta_0...\n",
      "Optimization terminated successfully.\n",
      "         Current function value: 113.000000\n",
      "         Iterations: 2\n",
      "         Function evaluations: 23870\n",
      "         Gradient evaluations: 14\n",
      "→  [  8.46634978e-09  -8.46634978e-10   1.45137425e-09 ...,   9.67962347e-08\n",
      "   2.66984171e-06  -2.91000537e-07]\n",
      "Recherche de theta_1...\n",
      "Optimization terminated successfully.\n",
      "         Current function value: 140.000000\n",
      "         Iterations: 3\n",
      "         Function evaluations: 28985\n",
      "         Gradient evaluations: 17\n",
      "→  [  4.95615237e-07  -6.43552270e-08   2.60285976e-07 ...,  -7.71345326e-08\n",
      "   3.16690703e-06  -6.39729702e-07]\n",
      "Recherche de theta_2...\n",
      "Optimization terminated successfully.\n",
      "         Current function value: 153.000000\n",
      "         Iterations: 2\n",
      "         Function evaluations: 23870\n",
      "         Gradient evaluations: 14\n",
      "→  [ -2.09081845e-08  -1.57258140e-08  -3.57404864e-10 ...,  -1.37958277e-07\n",
      "   2.99105512e-06  -3.06832076e-07]\n",
      "Recherche de theta_3...\n",
      "Optimization terminated successfully.\n",
      "         Current function value: 151.000000\n",
      "         Iterations: 2\n",
      "         Function evaluations: 23870\n",
      "         Gradient evaluations: 14\n",
      "→  [ -6.92276648e-09  -7.10494455e-09   1.63960259e-09 ...,   2.88842262e-07\n",
      "   1.73014084e-06  -2.32459211e-07]\n",
      "Recherche de theta_4...\n",
      "Optimization terminated successfully.\n",
      "         Current function value: 79.000000\n",
      "         Iterations: 2\n",
      "         Function evaluations: 25575\n",
      "         Gradient evaluations: 15\n",
      "→  [ -2.49227034e-09  -1.45085737e-08   2.75929930e-09 ...,  -4.86162855e-09\n",
      "   3.73119103e-06  -1.83682025e-07]\n",
      "0.5\n"
     ]
    }
   ],
   "source": [
    "from scipy.optimize import minimize\n",
    "\n",
    "class LabelPropag():\n",
    "    \n",
    "    def __init__(self, graph_reg=1, l2_reg=1):\n",
    "        self.graph_reg = graph_reg\n",
    "        self.l2_reg = l2_reg\n",
    "        \n",
    "    def f(self, theta, x):\n",
    "        \"\"\" Return the score for x and label theta\"\"\"\n",
    "        return theta.dot(x)\n",
    "\n",
    "    def objective(self, theta, X, train_idx, Y, graph):\n",
    "       # print(\"Appel d'objective avec theta=\", theta)\n",
    "        s = 0\n",
    "        for i in train_idx:\n",
    "            s += self.hinge_loss(self.f(theta, X[i]), Y[i])\n",
    "            \n",
    "        #print(\"X.shape :\",X.shape)\n",
    "        for i, neighbors in graph.items():\n",
    "            for j in neighbors:\n",
    "                #print(\"i,j :\", i,j)\n",
    "                s += self.graph_reg * (self.f(theta, X[i]) - self.f(theta, X[j]))**2\n",
    "        s += self.l2_reg * np.linalg.norm(theta)**2\n",
    "        #print(\"Valeur : \",s)\n",
    "        return s\n",
    "        \n",
    "    def fit(self, X, train_idx, labels, graph, n_labels):\n",
    "        \"\"\"\n",
    "        :params graph: a dictionary of neighborhood\n",
    "        :params n_labels: number of labels \"\"\"\n",
    "        self.thetas = np.zeros((n_labels, X.shape[1]))\n",
    "        # Init Y\n",
    "        Y = np.zeros((X.shape[0], n_labels))\n",
    "        Y[:] = -1\n",
    "        for i,label in enumerate(labels):\n",
    "            Y[i, label] = 1\n",
    "        \n",
    "        # Trouver meilleurs theta_l\n",
    "        for label in range(n_labels):\n",
    "            print(\"Recherche de theta_%d...\" % label)\n",
    "            self.thetas[label] = minimize(lambda t:self.objective(t, X, train_idx, Y[:,label], graph), \n",
    "                                          self.thetas[label],\n",
    "                                          method=\"BFGS\",\n",
    "                                          tol=1e-2,\n",
    "                                          options={\"maxiter\":1000, \"disp\":True}).x\n",
    "            print(\"→ \", self.thetas[label])\n",
    "    \n",
    "        \n",
    "    def hinge_loss(self, score1, score2):\n",
    "        if score1*score2 > 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1\n",
    "        \n",
    "    def predict(self, X):\n",
    "        return np.array([np.argmax([self.f(theta, x) \n",
    "                        for theta in self.thetas]) for x in X])\n",
    "    \n",
    "    def score(self, X, Y):\n",
    "        return accuracy_score(self.predict(X), Y)\n",
    "    \n",
    "    def set_params(self, **parameters):\n",
    "        for parameter, value in parameters.items():\n",
    "            self.parameter = value\n",
    "        return self\n",
    "\n",
    "X = np.array(attributes)\n",
    "Y = np.array([labels_to_id[label] for label in labels])\n",
    "\n",
    "#X_train, X_test = X[train_idx], X[test_idx]\n",
    "#Y_train, Y_test = Y[train_idx], Y[test_idx]\n",
    "\n",
    "label_propag = LabelPropag(graph_reg=1, l2_reg=1)\n",
    "graph = {url_pos[noeud]:[url_pos[voisin] for voisin in network[noeud]] for noeud in network.keys()}\n",
    "label_propag.fit(X, train_idx, Y, graph, n_labels=n_labels)\n",
    "print(label_propag.score(X_test, Y_test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}