LINEAR DISCRIMINANT TREE.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  LINEAR DISCRIMINANT TREES"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/shitian/anaconda/lib/python3.5/site-packages/sklearn/cross_validation.py:41: DeprecationWarning: This module was deprecated in version 0.18 in favor of the model_selection module into which all the refactored classes and functions are moved. Also note that the interface of the new CV iterators are different from that of this module. This module will be removed in 0.20.\n",
      "  \"This module will be removed in 0.20.\", DeprecationWarning)\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from sklearn.discriminant_analysis import LinearDiscriminantAnalysis as LDA\n",
    "from sklearn.metrics import accuracy_score\n",
    "from sklearn.cross_validation import train_test_split\n",
    "from sklearn import tree\n",
    "import io\n",
    "import requests\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import datetime\n",
    "import time\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Class:\n",
    "    def __init__(self,means,class_name,num_instances,instances):\n",
    "        self.means = means\n",
    "        self.class_name = class_name\n",
    "        self.num_instances = num_instances\n",
    "        self.instances = instances\n",
    "    def __eq__(self, other):\n",
    "        if isinstance(other, self.__class__):\n",
    "            ret = (self.means == other.means and self.class_name == other.class_name)\n",
    "            return ret      \n",
    "        else:\n",
    "            return False\n",
    "    def __ne__(self, other):\n",
    "        ret = not self.__eq__(other)\n",
    "        return ret\n",
    "    def __str__(self):\n",
    "        str_ = \"Class details: \"\n",
    "        str_ += \" - means:\"+str(self.means) + \"\\n\"\n",
    "        str_ += \" - class_name:\"+self.class_name + \"\\n\"\n",
    "        str_ += \" - num_instances:\"+str(self.num_instances)\n",
    "        return str_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Decision_Node:\n",
    "    def __init__(self,\n",
    "                lda,\n",
    "                left_node,\n",
    "                right_node):\n",
    "        self.lda = lda\n",
    "        self.left_node = left_node\n",
    "        self.right_node = right_node\n",
    "\n",
    "class Leaf_Node:\n",
    "    def __init__(self,\n",
    "                class_name):\n",
    "        self.class_name = class_name\n",
    "\n",
    "def print_tree(node, spacing=\"\"):\n",
    "    if isinstance(node,Leaf_Node):\n",
    "        print(spacing,\"Predict\",node.class_name)\n",
    "        return\n",
    "#     print(spacing+\"LDA: coef_: \"+str(node.lda.coef_)+\" intercept_: \"+str(node.lda.intercept_))\n",
    "    print(spacing+\"--> LDA.predict == 0:\")\n",
    "    print_tree(node.left_node,spacing+\"     \")\n",
    "    print(spacing+\"--> LDA.predict == 1:\")\n",
    "    print_tree(node.right_node,spacing+\"     \")\n",
    "    \n",
    "def test_tree(node, data):\n",
    "    if isinstance(node,Leaf_Node):\n",
    "#         print(\"Predicted: \",node.class_name)\n",
    "        return node.class_name\n",
    "    if(node.lda.predict(data)==0):\n",
    "        return test_tree(node.left_node, data)\n",
    "    if(node.lda.predict(data)==1):\n",
    "        return test_tree(node.right_node, data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#utiities\n",
    "\n",
    "def data_frame_to_list(df):\n",
    "    return [row[value_col_names].values.tolist() for i,row in df.iterrows()]\n",
    "\n",
    "def unique_vals(rows,col):\n",
    "    return set([row[col] for row in rows])\n",
    "\n",
    "def find_tuple_in_array(tuple,array):\n",
    "    return [False if x[0] != tuple[0] and x[1] != tuple[1] else True for x in array]\n",
    "\n",
    "def remove_tuple_from_array(tuple,array):\n",
    "    return [x for x in array if x.all() != tuple.all()]\n",
    "\n",
    "def print_classes(class_):\n",
    "    for i in class_:\n",
    "        print (\" \",i.class_name, end=\" \")\n",
    "    print()\n",
    "\n",
    "def test_rows_len(data):\n",
    "    al=np.array([])\n",
    "    tot=0\n",
    "    for m in data:\n",
    "        ma=m.instances\n",
    "        r=np.array(ma[value_col_names].values)\n",
    "        if tot==0:\n",
    "            al = r\n",
    "        else:\n",
    "            al=np.concatenate([al,tuple(r)],axis=0)\n",
    "        tot+=m.num_instances\n",
    "    uni=np.vstack({tuple(row) for row in al})\n",
    "    return len(uni)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def init_mean(dataset,class_col):\n",
    "    class_keys = set(dataset[class_col])\n",
    "    cols = dataset.keys()\n",
    "    locs = []\n",
    "    for key in class_keys:\n",
    "        this_class = dataset.loc[dataset['class'] == key]\n",
    "        this_loc = []\n",
    "        for col in cols:\n",
    "            if col == \"class\":\n",
    "                continue\n",
    "            this_loc.append(np.average(np.array(this_class[col]).astype(float)))\n",
    "\n",
    "        values = this_class.reset_index(drop=True).drop(\"class\",1).astype(float).fillna(0.0)\n",
    "        locs.append(Class(this_loc,key,len(this_class),values))\n",
    "    return locs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def calculate_distance(data1,data2):\n",
    "    dis=0\n",
    "    for i in range(len(data1)):\n",
    "        dis+=(data1[i]-data2[i])**2\n",
    "    return dis**0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def initial_partition(data):\n",
    "    max_dis = 0\n",
    "    max_dis_pair = (data[0],data[0])\n",
    "    CL = []\n",
    "    CR = []\n",
    "    for i in range(len(data)):\n",
    "        for j in range(i,len(data)):\n",
    "            dis = calculate_distance(data[i].means,data[j].means)\n",
    "            if(dis>max_dis):\n",
    "                max_dis = dis\n",
    "                max_dis_pair = (data[i],data[j])\n",
    "    CL.append(max_dis_pair[0])\n",
    "    CR.append(max_dis_pair[1])\n",
    "    for i in data:\n",
    "        if i in max_dis_pair:\n",
    "            continue\n",
    "        if(calculate_distance(max_dis_pair[0].means,i.means)<calculate_distance(max_dis_pair[1].means,i.means)):\n",
    "            CL.append(i)\n",
    "        else:\n",
    "            CR.append(i)\n",
    "    return CL,CR"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def LDA_from_CL_CR(CL,CR):\n",
    "#     print(\"LDA_CL\",CL)\n",
    "#     print(\"LDA_CR\",CR)\n",
    "    X = np.array([])\n",
    "    Y=np.array([])\n",
    "    for i in CL:\n",
    "        if X.shape[0]==0:\n",
    "            X=np.array(data_frame_to_list(i.instances) )\n",
    "            Y=np.array(np.tile(0,(i.num_instances,1)))\n",
    "        else:\n",
    "            X=np.append(X,np.array(data_frame_to_list(i.instances) ), axis=0)\n",
    "            \n",
    "            tile = np.tile(0,(i.num_instances,1))\n",
    "            Y=np.append(Y,tile)\n",
    "        \n",
    "    for i in CR:\n",
    "        if X.shape[0]==0:\n",
    "            X=np.array(data_frame_to_list(i.instances) )\n",
    "            Y=np.array(np.tile(1,(i.num_instances,1)))\n",
    "        else:\n",
    "            X=np.append(X,np.array(data_frame_to_list(i.instances) ), axis=0)\n",
    "            \n",
    "            tile = np.tile(1,(i.num_instances,1))\n",
    "            Y=np.append(Y,tile)\n",
    "#     print(\"After: \",X.shape,Y.shape,X,Y)\n",
    "    ret_lda = LDA().fit(X,Y)\n",
    "    predict = ret_lda.predict(X)\n",
    "#     print(\"LDA Accuracy :\",accuracy_score(predict,Y))\n",
    "    return ret_lda"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# def calc_entropy(CL,CR):\n",
    "#     CL_data_count = 0\n",
    "#     CR_data_count = 0\n",
    "#     for i in CL:\n",
    "        \n",
    "#         for instance in i.instances:\n",
    "#             if lda.predict(instance)==0:\n",
    "#                 CL_data_count+=1\n",
    "#             else:\n",
    "#                 CR_data_count+=1\n",
    "                \n",
    "                \n",
    "#         CL_data_count += i.num_instances\n",
    "#     for i in CR:\n",
    "        \n",
    "#         for instance in i.instances:\n",
    "#             if lda.predict(instance)==0:\n",
    "#                 CL_data_count+=1\n",
    "#             else:\n",
    "#                 CR_data_count+=1\n",
    "        \n",
    "#         CR_data_count += i.num_instances\n",
    "#     pL = 1.0*CL_data_count/(CL_data_count+CR_data_count)\n",
    "#     return -pL*np.log2(pL)-(1-pL)*np.log2(1-pL)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def calc_info_gain(CL,CR):\n",
    "    if len(CL)==0 or len(CR)==0:\n",
    "        return -np.inf\n",
    "    lda=LDA_from_CL_CR(CL,CR)\n",
    "    N_L = 0\n",
    "    N_R = 0\n",
    "    N = 0\n",
    "    for i in CL:\n",
    "        N_L += i.num_instances\n",
    "    for i in CR:\n",
    "        N_R += i.num_instances \n",
    "    N = N_L + N_R\n",
    "    \n",
    "    #calc E0\n",
    "    E0 = 0   \n",
    "    for i in CL:\n",
    "        tem = i.num_instances*1.0/N\n",
    "        E0 -= tem * np.log2(tem)\n",
    "    for i in CR:\n",
    "        tem = i.num_instances*1.0/N\n",
    "        E0 -= tem * np.log2(tem)\n",
    "        \n",
    "    #calc second term\n",
    "    info_gain = E0\n",
    "    N_i_Ls = []\n",
    "    N_i_Rs = []\n",
    "    for i in CL:\n",
    "        N_i_L = 0\n",
    "        N_i_R = 0\n",
    "        for index, instance in i.instances.iterrows():\n",
    "            if lda.predict([instance]) == 0:\n",
    "                N_i_L += 1\n",
    "            else:\n",
    "                N_i_R += 1\n",
    "        N_i_Ls.append(N_i_L)\n",
    "        N_i_Rs.append(N_i_R)\n",
    "    for i in CR:\n",
    "        N_i_L = 0\n",
    "        N_i_R = 0\n",
    "        for index, instance in i.instances.iterrows():\n",
    "            if lda.predict([instance]) == 0:\n",
    "                N_i_L += 1\n",
    "            else:\n",
    "                N_i_R += 1\n",
    "        N_i_Ls.append(N_i_L)\n",
    "        N_i_Rs.append(N_i_R)\n",
    "    left = 0\n",
    "    for N_i_L in N_i_Ls:\n",
    "        if N_i_L == 0:\n",
    "            continue\n",
    "        left += N_i_L / N_L * np.log2(N_i_L / N_L)\n",
    "    info_gain += left * N_L / N\n",
    "    left = 0\n",
    "    for N_i_R in N_i_Rs:\n",
    "        if N_i_R == 0:\n",
    "            continue\n",
    "        left += N_i_R / N_R * np.log2(N_i_R / N_R)\n",
    "    info_gain += left * N_R / N\n",
    "        \n",
    "    return info_gain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def iter_substitute(CL,CR,data):\n",
    "#     if len(CL)==1 or len(CR) == 1:\n",
    "#         return (CL,CR)\n",
    "#     original_entropy = calc_entropy(CL,CR)\n",
    "    max_info_gain = calc_info_gain(CL,CR)\n",
    "#     print(\"initial info gain: \",max_info_gain)\n",
    "    best_partition = (CL,CR)\n",
    "\n",
    "    for d in data:\n",
    "        CL_ = CL.copy()\n",
    "        CR_ = CR.copy()\n",
    "        \n",
    "        if d in CL:\n",
    "            CL_=[x for x in CL if x != d]\n",
    "            CR_.append(d)\n",
    "        else:\n",
    "            CR_=[x for x in CR if x != d]\n",
    "            CL_.append(d)\n",
    "        \n",
    "        if(len(CL_)==0 or len(CR_) == 0):\n",
    "            continue\n",
    "        \n",
    "        gain = calc_info_gain(CL_,CR_)\n",
    "        \n",
    "#         print(\"classes in this iter:\")\n",
    "#         print(\"  CL: \",end=\" \")\n",
    "#         for i in CL_:\n",
    "#             print(i.class_name,end=\" \")\n",
    "#         print(\"\\n  CR: \",end=\" \")\n",
    "#         for i in CR_:\n",
    "#             print(i.class_name,end=\" \")\n",
    "        \n",
    "#         print(\",  info_gain: \",gain)\n",
    "#         print(\"\\n----------------------\\n\")\n",
    "#         if original_entropy - ent > max_delta_entropy:\n",
    "#             max_delta_entropy = original_entropy - ent\n",
    "#             best_partition = (CL_,CR_)\n",
    "        if gain > max_info_gain:\n",
    "            max_info_gain = gain\n",
    "            best_partition = (CL_,CR_)\n",
    "#     print(\"CL:\")\n",
    "#     print_classes(best_partition[0])\n",
    "#     print(\"CR:\")\n",
    "#     print_classes(best_partition[1])\n",
    "#     print(max_info_gain)\n",
    "#     print()\n",
    "#     print()\n",
    "    assert(len(best_partition[0])+len(best_partition[1])==len(CL)+len(CR))\n",
    "    return best_partition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def partition(centers):\n",
    "    if(len(centers)==1):\n",
    "        return Leaf_Node(centers[0].class_name)\n",
    "    CL,CR = initial_partition(centers)\n",
    "\n",
    "    CL,CR = iter_substitute(CL,CR,centers)\n",
    "\n",
    "#     print(\"**************\\nclasses in this node:\\nCL:\",end=\"  \")\n",
    "#     for i in CL:\n",
    "#         print(i.class_name,end=\" \")\n",
    "#     print(\"\\nCR:  \",end=\" \")\n",
    "#     for i in CR:\n",
    "#         print(i.class_name,end=\" \")\n",
    "#     print()\n",
    "#     print(\"vvv   partitioning   vvv\")\n",
    "#     for i in CL:\n",
    "#         print(i.instances)\n",
    "#     print(\"^^^   partitioning   ^^^\")\n",
    "\n",
    "    left_node = partition(CL)\n",
    "    right_node = partition(CR)\n",
    "    \n",
    "    lda = LDA_from_CL_CR(CL,CR)\n",
    "#     print(\"parting\")\n",
    "    return Decision_Node(lda,left_node,right_node)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Apply on data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "url = \"https://archive.ics.uci.edu/ml/machine-learning-databases/ecoli/ecoli.data\"\n",
    "\n",
    "s=requests.get(url).content\n",
    "c=pd.read_csv(io.StringIO(s.decode('utf-8')),delim_whitespace=True, error_bad_lines=False,names=[\"Sequence Name\",\"mcg\",\"gvh\",\"lip\",\"chg\",\"aac\",\"alm1\",\"alm2\",\"class\"])\n",
    "c=c.drop(labels=\"Sequence Name\", axis=1)\n",
    "\n",
    "value_col_names = list(c.columns.values)[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/shitian/anaconda/lib/python3.5/site-packages/sklearn/discriminant_analysis.py:388: UserWarning: Variables are collinear.\n",
      "  warnings.warn(\"Variables are collinear.\")\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Time used: 0:00:59\n",
      "Accuracy: 0.835119047619\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "scores = []\n",
    "\n",
    "for i in range(20):\n",
    "    training_data, validation_data = train_test_split(c,train_size=0.75,test_size=0.25)\n",
    "\n",
    "    means = init_mean(training_data,\"class\")\n",
    "    means=np.array(means)\n",
    "\n",
    "    root = partition(means)\n",
    "\n",
    "#     print_tree(root)\n",
    "\n",
    "    valid_data = validation_data.drop(\"class\",axis=1)\n",
    "    valid_label = validation_data[\"class\"]\n",
    "\n",
    "    results=[]\n",
    "    for index, row in valid_data.iterrows():\n",
    "        results.append(test_tree(root, [row]))\n",
    "    score = accuracy_score(results, valid_label)\n",
    "\n",
    "    scores.append(score)\n",
    "    \n",
    "end_time = time.time()\n",
    "uptime = end_time - start_time\n",
    "human_uptime = str(datetime.timedelta(seconds=int(uptime)))\n",
    "print(\"Time used:\",human_uptime)\n",
    "print(\"Accuracy:\",np.mean(scores))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Compare with sklearn Decision Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Time used: 0:00:00\n",
      "Accuracy: 0.786904761905\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "scores = []\n",
    "\n",
    "for i in range(20):\n",
    "    training_data, validation_data = train_test_split(c,train_size=0.75,test_size=0.25)\n",
    "    clf = tree.DecisionTreeClassifier()\n",
    "\n",
    "    train_data = training_data.drop(\"class\",axis=1)\n",
    "    train_label = training_data[\"class\"]\n",
    "    \n",
    "    valid_data = validation_data.drop(\"class\",axis=1)\n",
    "    valid_label = validation_data[\"class\"]\n",
    "    clf.fit(train_data,train_label)\n",
    "    results=clf.predict(valid_data)\n",
    "    score = accuracy_score(results, valid_label)\n",
    "\n",
    "    scores.append(score)\n",
    "    \n",
    "end_time = time.time()\n",
    "uptime = end_time - start_time\n",
    "human_uptime = str(datetime.timedelta(seconds=int(uptime)))\n",
    "print(\"Time used:\",human_uptime)\n",
    "print(\"Accuracy:\",np.mean(scores))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion: This linear discriminant tree is slower than standard sklearn Decision Tree but more accurate"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "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": 0
}