Chapter03 决策树.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 0.简要介绍\n",
    "\n",
    "#### K-近邻算法的最大缺点在于无法给出数据的内在含义，而决策树的主要优势在于<font color=\"red\" size = 4>数据形式非常容易理解\n",
    "\n",
    "![title.png](./picture/03决策树示例.png)\n",
    "![title.png](./picture/03决策树流程.png)   \n",
    "![title.png](./picture/03决策树特点.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 决策树关键在于<font color=\"red\" size = 4>每次如何找到合适的划分特征。</font>  \n",
    " __而如何确定哪些特征起决定性作用就需要对特征进行评估__\n",
    "    \n",
    "这里涉及到信息论里面的信息增益相关概念"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 信息增益  \n",
    "\n",
    "划分数据集的大原则是：__将无序的数据转换成更加有序__  \n",
    "    \n",
    "这种评估数据的有序性指标中的一种方法就是使用信息论度量方法  \n",
    "    \n",
    "<font color=\"red\" size = 4>在划分数据集之前之后信息发生的变化称为信息增益</font>  \n",
    "    \n",
    "    \n",
    "某符号含有的信息表示为：\n",
    "    ![title.png](./picture/03信息.png)\n",
    "    其中p(xi)表示该分类的概率\n",
    "    \n",
    "熵定义为信息的期望值：\n",
    "    ![title.png](./picture/03熵.png)\n",
    "    \n",
    "<font face=\"微软雅黑\"> <font color=\"red\" size = 6>Talk is cheap， show me the code.</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#计算给定数据集的香农熵\n",
    "from  math import log\n",
    "\n",
    "def calcShannonEnt(dataSet):\n",
    "    numEntries = len(dataSet)\n",
    "    labelCounts = {}\n",
    "    for featVec in dataSet:\n",
    "        currentLabel = featVec[-1]\n",
    "        if currentLabel not in labelCounts.keys():   #统计出现次数，并创建字典\n",
    "            labelCounts[currentLabel] = 0  #出现新类别，扩展字典\n",
    "        labelCounts[currentLabel] += 1\n",
    "        \n",
    "    shannonEnt = 0.0\n",
    "    for key in labelCounts:\n",
    "        prob = float(labelCounts[key])/numEntries   #计算概率\n",
    "        shannonEnt -= prob * log(prob, 2)  #计算香农熵，以2为底\n",
    "        \n",
    "    return shannonEnt  \n",
    "\n",
    "\n",
    "#生成简单的数据测试一下\n",
    "def creatDataSet():\n",
    "    dataSet = [[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]\n",
    "    labels = ['no surfacing', 'flippers']\n",
    "    return dataSet, labels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "shannonEnt: 0.9709505944546686\n"
     ]
    }
   ],
   "source": [
    "dataSet, labels = creatDataSet()\n",
    "shannonEnt = calcShannonEnt(dataSet)\n",
    "print(\"shannonEnt:\",shannonEnt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### 熵越高，则混合的数据越多\n",
    "\n",
    "例如将第一个数据最后一位改成‘maybe’"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "shannonEnt: 1.3709505944546687\n"
     ]
    }
   ],
   "source": [
    "dataSet[0][-1] = 'maybe'\n",
    "shannonEnt = calcShannonEnt(dataSet)\n",
    "print(\"shannonEnt:\",shannonEnt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 基尼不纯度(Gini impurity)\n",
    "另一个度量数据无序程度的方法是基尼不纯度(Gini impurity):  \n",
    "简单来说是从一个数据中随机选取子项，度量其被错误分类的概率"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.计算信息增益  \n",
    "\n",
    "重新回到前面，决策树关键在于选择何种特征，选择特征的标准是计算采用不同特征产生的信息增益。  \n",
    "因此，我们需要计算利用不同特征划分时的信息增益"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.1划分数据集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 函数说明"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Extended List :  [123, 'xyz', 'zara', 'abc', 123, 2009, 'manni']\n"
     ]
    }
   ],
   "source": [
    "#A.extend()表示往已知list后面添加多项，类似拼接操作\n",
    "A = [123, 'xyz', 'zara', 'abc', 123];\n",
    "B = [2009, 'manni'];\n",
    "A.extend(B)\n",
    "\n",
    "print(\"Extended List : \", A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def splitDataSet(dataSet, axis, value):\n",
    "    retDataSet = []\n",
    "    for featVec in dataSet:\n",
    "        if(featVec[axis] == value):\n",
    "            reducedFeatVec = featVec[:axis]\n",
    "            reducedFeatVec.extend(featVec[axis+1:])\n",
    "            retDataSet.append(reducedFeatVec)\n",
    "    return retDataSet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "划分后数据集: [[1, 'yes'], [1, 'yes'], [0, 'no']]\n",
      "划分后数据集: [[1, 'no'], [1, 'no']]\n"
     ]
    }
   ],
   "source": [
    "myDat, labels = creatDataSet()\n",
    "s1_myDat = splitDataSet(myDat, 0, 1)\n",
    "print(\"划分后数据集:\", s1_myDat)\n",
    "s2_myDat = splitDataSet(myDat, 0, 0)\n",
    "print(\"划分后数据集:\", s2_myDat)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 1.2根据不同的划分计算信息增益"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def chooseBestFeatureToSplit(dataSet):\n",
    "    numFeatures = len(dataSet[0]) - 1 #统计特征数\n",
    "    baseEntropy = calcShannonEnt(dataSet)  #计算原来的香农熵\n",
    "    bestInfoGain = 0.0  #初始化\n",
    "    bestFeature = -1\n",
    "    for i in range(numFeatures):\n",
    "        featList = [example[i] for example in dataSet]  #统计每个特征下不同类别的数目\n",
    "        uniqueVals = set(featList) #集合，数据无序不重复\n",
    "        newEntropy = 0.0\n",
    "        for value in uniqueVals:  #计算不同特征切分的信息增益\n",
    "            subDataSet = splitDataSet(dataSet, i, value)\n",
    "            prob = len(subDataSet) / float(len(dataSet))\n",
    "            newEntropy += prob * calcShannonEnt(subDataSet)\n",
    "            \n",
    "        infoGain = baseEntropy - newEntropy\n",
    "        if(infoGain > bestInfoGain): #选择最佳信息增益的特征\n",
    "            bestInfoGain = infoGain\n",
    "            bestFeature = i\n",
    "            \n",
    "    return bestFeature        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最优划分特征： 0\n"
     ]
    }
   ],
   "source": [
    "myDat, labels = creatDataSet() #生成简单数据\n",
    "print(\"最优划分特征：\",chooseBestFeatureToSplit(myDat)) #选择分割特征"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.递归构建决策树  \n",
    "\n",
    "由于数据可能通过选择一个特征无法完全区分，因此，我们需要进一步划分，也即对划分后的数据再次划分  \n",
    "\n",
    "因此，我们可以采用递归的方式遍历所有划分的属性  \n",
    "\n",
    "![title.png](./picture/03海洋生物分类.png)\n",
    "\n",
    "![title.png](./picture/03划分数据集时的数据路径.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 当然，还有一些不需要消耗特征的算法，这里暂时不涉及"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 函数说明"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "字典值 : dict_items([('Google', 'www.google.com'), ('Runoob', 'www.runoob.com'), ('taobao', 'www.taobao.com')])\n"
     ]
    }
   ],
   "source": [
    "#items()返回可遍历的(键, 值) 元组数组\n",
    "\n",
    "dict = {'Google': 'www.google.com', 'Runoob': 'www.runoob.com', 'taobao': 'www.taobao.com'} \n",
    "print(\"字典值 : %s\" %  dict.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "#统计每种类型的数目，并进行排序，返回数目最多的类别\n",
    "def majorityCnt(classList): \n",
    "    classCount = {}\n",
    "    for vote in classList:\n",
    "        if vote not in classCount.keys(): \n",
    "            classCount[vote] = 0\n",
    "        classCount[vote] += 1\n",
    "    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)\n",
    "    return sortedClassCount[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "#创建决策树\n",
    "def creatTree(dataSet, labels):\n",
    "    classList = [example[-1] for example in dataSet] #统计不同类别的数目\n",
    "    \n",
    "    if classList.count(classList[0]) == len(classList): #类别完全相同，则停止划分\n",
    "        return classList[0]\n",
    "    \n",
    "    if len(dataSet[0]) == 1: #遍历完所有特征时，返回出现次数最多的\n",
    "        return majorityCnt(classList)\n",
    "    bestFeat = chooseBestFeatureToSplit(dataSet) #选择最佳分类特征\n",
    "    bestFeatLabel = labels[bestFeat]\n",
    "    \n",
    "    myTree = {bestFeatLabel:{}}\n",
    "    \n",
    "    del(labels[bestFeat]) #划分完成后去除该特征\n",
    "    \n",
    "    featValues = [example[bestFeat] for example in dataSet]  #得到列表包含的所有属性值\n",
    "    uniqueVals = set(featValues)\n",
    "    \n",
    "    for value in uniqueVals:\n",
    "        subLabels = labels[:] #对属于最优属性的样本进一步划分\n",
    "        myTree[bestFeatLabel][value] = creatTree(splitDataSet(dataSet, bestFeat, value), subLabels) #迭代继续划分\n",
    "    return myTree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "myTree: {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}\n"
     ]
    }
   ],
   "source": [
    "#测试\n",
    "myDat, labels = creatDataSet()\n",
    "# print(len(myDat[0]))\n",
    "myTree = creatTree(myDat, labels)\n",
    "print(\"myTree:\", myTree)"
   ]
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}