ID3.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\nID3 Algorithm\\nMuskan Pandey\\n'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''\n",
    "ID3 Algorithm\n",
    "Muskan Pandey\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import csv\n",
    "import math\n",
    "import os"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def load_csv_to_header_data(filename):\n",
    "    fpath = os.path.join(os.getcwd(), filename)\n",
    "    fs = csv.reader(open(fpath, newline='\\n'))\n",
    "\n",
    "    all_row = []\n",
    "    for r in fs:\n",
    "        all_row.append(r)\n",
    "\n",
    "    headers = all_row[0]\n",
    "    idx_to_name, name_to_idx = get_header_name_to_idx_maps(headers)\n",
    "\n",
    "    data = {\n",
    "        'header': headers,\n",
    "        'rows': all_row[1:],\n",
    "        'name_to_idx': name_to_idx,\n",
    "        'idx_to_name': idx_to_name\n",
    "    }\n",
    "    return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_header_name_to_idx_maps(headers):\n",
    "    name_to_idx = {}\n",
    "    idx_to_name = {}\n",
    "    for i in range(0, len(headers)):\n",
    "        name_to_idx[headers[i]] = i\n",
    "        idx_to_name[i] = headers[i]\n",
    "    return idx_to_name, name_to_idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def project_columns(data, columns_to_project):\n",
    "    data_h = list(data['header'])\n",
    "    data_r = list(data['rows'])\n",
    "\n",
    "    all_cols = list(range(0, len(data_h)))\n",
    "\n",
    "    columns_to_project_ix = [data['name_to_idx'][name] for name in columns_to_project]\n",
    "    columns_to_remove = [cidx for cidx in all_cols if cidx not in columns_to_project_ix]\n",
    "\n",
    "    for delc in sorted(columns_to_remove, reverse=True):\n",
    "        del data_h[delc]\n",
    "        for r in data_r:\n",
    "            del r[delc]\n",
    "\n",
    "    idx_to_name, name_to_idx = get_header_name_to_idx_maps(data_h)\n",
    "\n",
    "    return {'header': data_h, 'rows': data_r,\n",
    "            'name_to_idx': name_to_idx,\n",
    "            'idx_to_name': idx_to_name}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_uniq_values(data):\n",
    "    idx_to_name = data['idx_to_name']\n",
    "    idxs = idx_to_name.keys()\n",
    "\n",
    "    val_map = {}\n",
    "    for idx in iter(idxs):\n",
    "        val_map[idx_to_name[idx]] = set()\n",
    "\n",
    "    for data_row in data['rows']:\n",
    "        for idx in idx_to_name.keys():\n",
    "            att_name = idx_to_name[idx]\n",
    "            val = data_row[idx]\n",
    "            if val not in val_map.keys():\n",
    "                val_map[att_name].add(val)\n",
    "    return val_map"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_class_labels(data, target_attribute):\n",
    "    rows = data['rows']\n",
    "    col_idx = data['name_to_idx'][target_attribute]\n",
    "    labels = {}\n",
    "    for r in rows:\n",
    "        val = r[col_idx]\n",
    "        if val in labels:\n",
    "            labels[val] = labels[val] + 1\n",
    "        else:\n",
    "            labels[val] = 1\n",
    "    return labels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def entropy(n, labels):\n",
    "    ent = 0\n",
    "    for label in labels.keys():\n",
    "        p_x = labels[label] / n\n",
    "        ent += - p_x * math.log(p_x, 2)\n",
    "    return ent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition_data(data, group_att):\n",
    "    partitions = {}\n",
    "    data_rows = data['rows']\n",
    "    partition_att_idx = data['name_to_idx'][group_att]\n",
    "    for row in data_rows:\n",
    "        row_val = row[partition_att_idx]\n",
    "        if row_val not in partitions.keys():\n",
    "            partitions[row_val] = {\n",
    "                'name_to_idx': data['name_to_idx'],\n",
    "                'idx_to_name': data['idx_to_name'],\n",
    "                'rows': list()\n",
    "            }\n",
    "        partitions[row_val]['rows'].append(row)\n",
    "    return partitions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def avg_entropy_w_partitions(data, splitting_att, target_attribute):\n",
    "    # find uniq values of splitting att\n",
    "    data_rows = data['rows']\n",
    "    n = len(data_rows)\n",
    "    partitions = partition_data(data, splitting_att)\n",
    "\n",
    "    avg_ent = 0\n",
    "\n",
    "    for partition_key in partitions.keys():\n",
    "        partitioned_data = partitions[partition_key]\n",
    "        partition_n = len(partitioned_data['rows'])\n",
    "        partition_labels = get_class_labels(partitioned_data, target_attribute)\n",
    "        partition_entropy = entropy(partition_n, partition_labels)\n",
    "        avg_ent += partition_n / n * partition_entropy\n",
    "\n",
    "    return avg_ent, partitions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def most_common_label(labels):\n",
    "    mcl = max(labels, key=lambda k: labels[k])\n",
    "    return mcl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def id3(data, uniqs, remaining_atts, target_attribute):\n",
    "    labels = get_class_labels(data, target_attribute)\n",
    "\n",
    "    node = {}\n",
    "\n",
    "    if len(labels.keys()) == 1:\n",
    "        node['label'] = next(iter(labels.keys()))\n",
    "        return node\n",
    "\n",
    "    if len(remaining_atts) == 0:\n",
    "        node['label'] = most_common_label(labels)\n",
    "        return node\n",
    "\n",
    "    n = len(data['rows'])\n",
    "    ent = entropy(n, labels)\n",
    "\n",
    "    max_info_gain = None\n",
    "    max_info_gain_att = None\n",
    "    max_info_gain_partitions = None\n",
    "\n",
    "    for remaining_att in remaining_atts:\n",
    "        avg_ent, partitions = avg_entropy_w_partitions(data, remaining_att, target_attribute)\n",
    "        info_gain = ent - avg_ent\n",
    "        if max_info_gain is None or info_gain > max_info_gain:\n",
    "            max_info_gain = info_gain\n",
    "            max_info_gain_att = remaining_att\n",
    "            max_info_gain_partitions = partitions\n",
    "\n",
    "    if max_info_gain is None:\n",
    "        node['label'] = most_common_label(labels)\n",
    "        return node\n",
    "\n",
    "    node['attribute'] = max_info_gain_att\n",
    "    node['nodes'] = {}\n",
    "\n",
    "    remaining_atts_for_subtrees = set(remaining_atts)\n",
    "    remaining_atts_for_subtrees.discard(max_info_gain_att)\n",
    "\n",
    "    uniq_att_values = uniqs[max_info_gain_att]\n",
    "\n",
    "    for att_value in uniq_att_values:\n",
    "        if att_value not in max_info_gain_partitions.keys():\n",
    "            node['nodes'][att_value] = {'label': most_common_label(labels)}\n",
    "            continue\n",
    "        partition = max_info_gain_partitions[att_value]\n",
    "        node['nodes'][att_value] = id3(partition, uniqs, remaining_atts_for_subtrees, target_attribute)\n",
    "\n",
    "    return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pretty_print_tree(root):\n",
    "    stack = []\n",
    "    rules = set()\n",
    "\n",
    "    def traverse(node, stack, rules):\n",
    "        if 'label' in node:\n",
    "            stack.append(' THEN ' + node['label'])\n",
    "            rules.add(''.join(stack))\n",
    "            stack.pop()\n",
    "        elif 'attribute' in node:\n",
    "            ifnd = 'IF ' if not stack else ' AND '\n",
    "            stack.append(ifnd + node['attribute'] + ' EQUALS ')\n",
    "            for subnode_key in node['nodes']:\n",
    "                stack.append(subnode_key)\n",
    "                traverse(node['nodes'][subnode_key], stack, rules)\n",
    "                stack.pop()\n",
    "            stack.pop()\n",
    "\n",
    "    traverse(root, stack, rules)\n",
    "    print(os.linesep.join(rules))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "IF Outlook EQUALS Rainy AND Windy EQUALS False THEN Yes\n",
      "IF Outlook EQUALS Rainy AND Windy EQUALS True THEN No\n",
      "IF Outlook EQUALS Sunny AND Humidity EQUALS Normal THEN Yes\n",
      "IF Outlook EQUALS Sunny AND Humidity EQUALS High THEN No\n",
      "IF Outlook EQUALS Overcast THEN Yes\n"
     ]
    }
   ],
   "source": [
    "def main():\n",
    "    config = {'data_file': 'tennis.csv', 'data_mappers': [], 'data_project_columns': ['Outlook', 'Temperature', 'Humidity', 'Windy', 'PlayTennis'], 'target_attribute': 'PlayTennis'}\n",
    "\n",
    "    data = load_csv_to_header_data(config['data_file'])\n",
    "    data = project_columns(data, config['data_project_columns'])\n",
    "\n",
    "    target_attribute = config['target_attribute']\n",
    "    remaining_attributes = set(data['header'])\n",
    "    remaining_attributes.remove(target_attribute)\n",
    "\n",
    "    uniqs = get_uniq_values(data)\n",
    "\n",
    "    root = id3(data, uniqs, remaining_attributes, target_attribute)\n",
    "\n",
    "    pretty_print_tree(root)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\": main()"
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}