labpgm3.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "decision tree for thge dataset using id3 algorithm\n",
      " Wind\n",
      "  strong\n",
      "   Outlook\n",
      "    overcast\n",
      "     yes\n",
      "    rain\n",
      "     Temp\n",
      "      mild\n",
      "       Humidity\n",
      "        high\n",
      "         no\n",
      "        normal\n",
      "         yes\n",
      "      cool\n",
      "       yes\n",
      "    sunny\n",
      "     Temp\n",
      "      mild\n",
      "       yes\n",
      "      hot\n",
      "       no\n",
      "  weak\n",
      "   Outlook\n",
      "    overcast\n",
      "     yes\n",
      "    rain\n",
      "     Temp\n",
      "      mild\n",
      "       yes\n",
      "      cool\n",
      "       no\n",
      "    sunny\n",
      "     Temp\n",
      "      mild\n",
      "       no\n",
      "      hot\n",
      "       no\n",
      "      cool\n",
      "       yes\n",
      "the test instance: ['rain', 'cool', 'normal', 'strong']\n",
      "the predicted label:yes\n",
      "the test instance: ['sunny', 'mild', 'normal', 'strong']\n",
      "the predicted label:yes\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "import csv\n",
    "\n",
    "def load_csv(filename):\n",
    "    lines=csv.reader(open(filename,\"r\"))\n",
    "    dataset=list(lines)\n",
    "    headers=dataset.pop(0)\n",
    "    return dataset,headers\n",
    "\n",
    "class Node:\n",
    "    def __init__(self,attribute):\n",
    "        self.attribute=attribute\n",
    "        self.children=[]\n",
    "        self.answer=\" \"\n",
    "        \n",
    "def subtables(data,col,delete):\n",
    "    dic={}\n",
    "    coldata=[row[col] for row in data]\n",
    "    attr=list(set(coldata))\n",
    "    for k in attr:\n",
    "        dic[k]=[]\n",
    "    for y in range(len(data)):\n",
    "        key=data[y][col]\n",
    "        if delete:\n",
    "            del data[y][col]\n",
    "        dic[key].append(data[y])\n",
    "    return attr,dic\n",
    "    \n",
    "def entropy(s):\n",
    "    attr =list(set(s))\n",
    "    if len(attr)==1:\n",
    "        return 0\n",
    "    counts=[0,0]\n",
    "    for i in range(2):\n",
    "        counts[i]=sum([1 for x in s if attr[i]==x])/(len(s)*1.0)\n",
    "    sums=0\n",
    "    for cnt in counts:\n",
    "        sums+=-1*cnt*math.log(cnt,2)\n",
    "    return sums\n",
    "    \n",
    "def compute_gain(data,col):\n",
    "    attrvalues,dic=subtables(data,col,delete=False)\n",
    "    total_entropy=entropy([row[-1] for row in data])\n",
    "    for x in range (len(attrvalues)):\n",
    "        ratio=len(dic[attrvalues[x]])/(len(data)*1.0)\n",
    "        entro=entropy([row[-1] for row in dic[attrvalues[x]]])\n",
    "        total_entropy =ratio*entro\n",
    "    return total_entropy\n",
    "                            \n",
    "                            \n",
    "def build_tree(data,features):\n",
    "    lastcol=[row[-1] for row in data]\n",
    "    if(len(set(lastcol)))==1:\n",
    "        node=Node(\"\")\n",
    "        node.answer=lastcol[0]\n",
    "        return node\n",
    "    n=len(data[0])-1\n",
    "    gains=[compute_gain(data,col) for col in range(n)]\n",
    "    split=gains.index(max(gains))\n",
    "    node=Node(features[split])\n",
    "    fea=features[:split]+features[split+1 :]\n",
    "    attr,dic=subtables(data,split,delete=True)\n",
    "                                \n",
    "    for x in range(len(attr)):\n",
    "        child=build_tree(dic[attr[x]],fea)\n",
    "        node.children.append((attr[x],child))\n",
    "    return node\n",
    "    \n",
    "def print_tree(node,level):\n",
    "    if node.answer !=\" \":\n",
    "        print(\" \" *level,node.answer)\n",
    "        return\n",
    "    print(\" \" * level,node.attribute)          \n",
    "    for value,n in node.children:\n",
    "        print(\" \"*(level+1),value)\n",
    "        print_tree(n,level+2)\n",
    "                                        \n",
    "def classify(node,x_test,features):\n",
    "    if node.answer!=\" \":\n",
    "        print(node.answer)\n",
    "        return\n",
    "    pos=features.index(node.attribute)\n",
    "    for value,n in node.children:\n",
    "        if x_test[pos]==value:\n",
    "            classify(n,x_test,features)\n",
    "                                                    \n",
    "dataset,features=load_csv(\"data3.csv\")\n",
    "node = build_tree(dataset,features)\n",
    "print(\"decision tree for thge dataset using id3 algorithm\")\n",
    "print_tree(node,0)\n",
    "testdata,features=load_csv(\"data3_test.csv\")\n",
    "for xtest in testdata:\n",
    "    print(\"the test instance:\",xtest)\n",
    "    print(\"the predicted label:\",end=\"\")\n",
    "    classify(node,xtest,features)"
   ]
  },
  {
   "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}