{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "前面提到，要构建决策树，最关键的问题是如何找到最优的划分属性，常见的划分方法有三种：\n", "\n", "* **信息增益**（information gain），代表算法为 **ID3**\n", "* **增益率**（gain ratio），代表算法为 **C4.5**\n", "* **基尼指数**（Gini index），代表算法为 **CART**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 信息熵\n", "\n", "划分的原则是希望决策树的分支节点包含的样本尽可能属于同一类别，也就是节点的 **纯度**（purity）越高越好，而 **信息熵**（information entropy）是度量样本集合纯度最常用的一种指标之一：\n", "\n", "$$\n", "Ent(D) = - \\sum_{k=1}^{\\left| \\mathcal{Y} \\right|} p_k log_2p_k\n", "$$\n", "\n", "其中，$p_k$ 表示第 k 类样本所占的比例。熵越小，数据就越接近于同一个类别，纯度越高；熵越大，数据的纯度越低，也可以说不确定性越低。\n", "\n", "举一个例子，假设数据集 D 有 3 个类别，所占比例为 $\\{\\frac{1}{3}, \\frac{1}{3}, \\frac{1}{3}\\}$，根据公式计算出该数据集的信息熵为：\n", "\n", "$$\n", "Ent(D) = -\\frac 1 3 log(\\frac 1 3)-\\frac 1 3log(\\frac 1 3)-\\frac 1 3log(\\frac 1 3)=1.0986\n", "$$\n", "\n", "再假设 3 个类别所占比例为 $\\{\\frac 1 {10},\\frac 2 {10},\\frac 7 {10}\\}$，那么信息熵为：\n", "\n", "$$\n", "Ent(D) = -\\frac 1 {10} log(\\frac 1 {10})-\\frac 2 {10}log(\\frac 2 {10})-\\frac 7 {10}log(\\frac 7 {10})=0.8018\n", "$$\n", "\n", "再假设 3 个类别所占的比例为 $\\{1,0,0\\}$，得到的信息熵为：\n", "\n", "$$\n", "Ent(D) = 0\n", "$$\n", "\n", "可以看出，当数据属于同一个类别时，信息熵达到最小值 0，当数据均匀分布时，信息熵的值最大。\n", "\n", "### 信息熵曲线\n", "\n", "当数据集只有两个类别时，假设一个类别所占的比例为 x，则另一个类别所占的比例为 1-x，信息熵为：\n", "\n", "$$\n", "Ent(D) = -xlog(x)-(1-x)log(1-x)\n", "$$\n", "\n", "我们画出这个曲线如下：" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzt3Xd8lfXd//HX52QnZEEGIQkkgQQIICtsEdyoFdyCkzqoWmtr1621tb3t3XFrq71rsRZX1SponYgoOHCwCZswE2b2gOydfH9/JPaX0kAO5JxznfF5Ph48HjknX5P3ZfDtN9/rur6XGGNQSinlXWxWB1BKKeV4Wu5KKeWFtNyVUsoLabkrpZQX0nJXSikvpOWulFJeSMtdKaW8kJa7Ukp5IS13pZTyQv5WfeOYmBiTkpJi1bdXSimPtHnz5nJjTGxP4ywr95SUFLKzs6369kop5ZFE5Ig943RZRimlvJCWu1JKeSG7yl1EZonIPhHJFZGHuvn8UyKyrfPPfhGpdHxUpZRS9upxzV1E/ICFwMVAPrBJRJYaY3Z/M8YY82CX8d8Dxjohq1JKKTvZM3OfCOQaYw4aY5qBJcCc04yfByx2RDillFJnx55yTwSOdXmd3/nefxCRQUAq8HnvoymllDpb9pS7dPPeqR7fNBd4yxjT1u0XElkgItkikl1WVmZvRqWUUmfInuvc84HkLq+TgMJTjJ0LfPdUX8gYswhYBJCVlaXP91MuZ4yhsr6F0pomSmsaOVHfQmNzGw0tnX+a2xCBAD8bAX6Cv81GUICNvqGBRIcF0jcskOjQQPqFBWKzdTfvUco92FPum4B0EUkFCugo8JtOHiQiQ4FoYJ1DEyp1Fk7UNbO3uIa8slryymrJLa3lUHkdpdVNNLe19/rrB/rZSO4bwqB+YQzsG0pqTBiZAyLITIggLMiyewOV+pce/xYaY1pF5H5gBeAHvGiMyRGRx4BsY8zSzqHzgCVGn7itXKy1rZ3dRdVsPVrJ1qMn2HasksMV9f/6fGigH4Nj+zBuYDQJUcHEhwcTFxFEXHgwfcMCCAn0JyTAj5AAP4L8O1YqW9rbaW0ztLYZGlvbOF7XzIm6Zo7XN3O8rpmCygaOlNdz5Hg96w9WUN/csRIpAmkxYYxMjGRMchRTB8eQEd8HEZ3lK9cSq7o4KyvL6PYD6mwVVDbw1f4yvtpfxprccqobWwGICw9i7MAoxg6MJjMhgiFxfUiIDHZquRpjKKluIqewil0F1ewqrGJXQRVFVY0AxPQJZHJaP6YOjuH8YbEkRIY4LYvyfiKy2RiT1dM4/f1ReYzc0hqW7Shi+c4i9pfUApAQGcxlIxM4Nz2G8YOinV7k3RER+kcG0z8ymAuHx//r/fwT9azLq2BdXgVr8spZtqMIgNHJUVw6Ip5LR/RncGwfl2ZVvkNn7sqtHTtez3tbC/hwZxF7i2sQgYkpfbk4M54ZGbEMifOMJQ9jDHlltazIKWFlTjHb86sAyIjvw7Xjkrh6XCJx4cEWp1SewN6Zu5a7cjstbe18uruE1zceZXVuOcZA1qBovnVOApePSiAuwvNLsLCygZU5xSzdXsiWo5X42YSZGbFcn5XEBcPiCfTXbZ9U97TclccprmrklXWHeTM7n/LaJhIig7lxQjLXZyWTGOW969R5ZbW8tTmfd7bkU1LdRHxEELdNSWHexIH0DQu0Op5yM1ruymMcKKlh0VcHeW9bAW3thguGxXPTpGRmZMTh50PXkre1G77cX8pLaw7z9YFygvxtXDMuiTumpZAeH251POUmtNyV29t85AR//SKXT/eUEhxg48asZO6ankZy31Cro1luf0kNL605xDtbCmhqbefyUf154MJ0hvWPsDqaspiWu3JbOYVV/HHlfj7fW0p0aAC3T03htikpugTRjYraJl5ee5gX1xymtqmVK0Yl8MCF6QztrzN5X6XlrtzOwbJanvr0AB9sLyQi2J97Zg5m/tQUQgP1ityeVNY388LqQ7y05jB1za1cec4AfjprKEnR+luOr9FyV26jqr6Fpz7dz6vrjxDkb+OOaancfV4akSEBVkfzOCfqmnnu64O8sPoQBrjr3FTuO38IfXTLA5+h5a4s19ZueGPTMZ5YsZeqhhZunjSIBy5MJzY8yOpoHq+wsoHHP97Le9sKiekTxI8vyeD6rGSfOgHtq7TclaU2HznOL5fmsKugmompffnVlSPIHKAnAx1t27FKfr1sN5uPnGBMchS/u2YUwxP037M303JXlqhtauXxj/fyyrojJEQG87PLh/OtcxI84i5ST2WM4f1thfx62W6qGlq4a3oa378wnZBAP6ujKSfQvWWUy325v4yfvbOTwqoGvj0thR9fMlS3v3UBEeGqsYnMyIjldx/t4dkv81i+s4jfXD2S6emxVsdTFtF7nFWvVdW38KM3t3P7ixsJDrDx1j1T+OWVI7TYXSw6LJDHrxvN4rsn428Tbn1hI794bxcNzd0+GE15Of2vT/XK+oMVPPjGNkprmvju+YP53gXpBAfocoCVpgzux/LvT+cPK/bx/OpDrMkt58kbxzAmOcrqaMqFdOauzkpLWzt/XLmPec+tJ8jfxjv3TuUnlw7TYncTwQF+/Pxbmbx+1yQaWtq49q9r+b9PD9DqgKdQKc+g5a7O2NGKem742zqe/jyX68Yl8eED0xmts0K3NHVIDB//4DyuPCeBpz7dz9xF6ynufIiI8m5a7uqMrMgp5oo/f01uaS1PzxvLE9eP1rV1NxcZEsCf5o7lTzeOYXdRNVf8+WtWHyi3OpZyMi13ZZe2dsPjH+/lO69uJi02jI++P50rRw+wOpY6A1eNTWTp/dOIDgvk1hc38OfPDtDero889lZa7qpHx+uamf/SRp75Io95E5N54ztTdE8TDzUkLpz3vzuNOaMH8OQn+5n/901U1bdYHUs5gZa7Oq1dBVVc+fRqNhw6zv9eO4rfXXOOnjT1cGFB/jx14xh+c/VI1uWVc9Uza8grq7U6lnIwLXd1Sityirnu2bUYY3jrnincOGGg1ZGUg4gIN08axOt3T6aqoYWrF67h6wNlVsdSDmRXuYvILBHZJyK5IvLQKcbcICK7RSRHRF53bEzlSsYYFn2Vxz3/2Myw/hG8f/+5nJOkV8N4owkpfXn/u9NIiAxh/kubeGXdYasjKQfpsdxFxA9YCFwGZALzRCTzpDHpwMPANGPMCOAHTsiqXKClrZ1H3tvFb5fv5fKRCSxZMFl3cfRyyX1Defu+qZw/NJZH38/hl+/vok1PtHo8e2buE4FcY8xBY0wzsASYc9KYu4GFxpgTAMaYUsfGVK5Q09jCHX/fxOsbjnLfzME8PW+srq/7iD5B/vzt1izunp7Ky+uO8L3FW2hs0W0LPJk9FygnAse6vM4HJp00JgNARNYAfsCvjDEfOyShcomK2ibmv7SJPUXVPH7tOdwwIdnqSMrF/GzCI1dkEh8RzP98uIeK2o08d3sWEcH6UBVPZM/Mvbu9Wk/+nc0fSAdmAvOA50XkPxZpRWSBiGSLSHZZmZ68cReFlQ1c/7d17C+pYdFt47XYfdxd09P4v7lj2HL0BDc8u46Sar2j1RPZU+75QNf/2pOAwm7GvG+MaTHGHAL20VH2/8YYs8gYk2WMyYqN1a1I3UFeWS3X/XUtZdVNvHrnJC4YFm91JOUG5oxJ5IXbJ3D0eD3XPLOWw+V1VkdSZ8iect8EpItIqogEAnOBpSeNeQ84H0BEYuhYpjnoyKDK8XYVVHH9s+tobmtn8YLJTEzta3Uk5UbOy4hlyYLJNLS0ceOideSW6rXwnqTHcjfGtAL3AyuAPcCbxpgcEXlMRGZ3DlsBVIjIbmAV8BNjTIWzQqve23asknnPrSckwI9/3jOVkYmRVkdSbuicpCgW3z2ZtnbD3EXr2V9SY3UkZSd9zJ4P2naskltf2EB0aCCLF0wmMSrE6kjKzeWW1nLTc+tpbTf8485J+jxcC9n7mD29Q9XHaLGrszEkrg9vfGcKQf42bnp+PbsKqqyOpHqg5e5DtNhVb6TGhPHGgimEBfpz03Pr2VNUbXUkdRpa7j5iR74Wu+q9gf1CWbJgMqGB/tz6wgbdcMyNabn7gNzSGm5/cSORIQFa7KrXkvuG8trdHfcx3vL8Bo4dr7c4keqOlruXyz9Rzy3Pb8TPZuMfd07SYlcOMTi2D6/cMYm6plZueWGD3ujkhrTcvVh5bRO3vrCR+uZWXr1zIikxYVZHUl4kc0AEL98xkfKaJm55fgPH65qtjqS60HL3UtWNLdz2wkaKqhp46dsTGJ6gl64pxxs7MJoX5nfcyXrH3zfR0KybjbkLLXcv1NjSxl0vZ3OgtIZnbxnP+EF656lynslp/fjzvLHsyK/ke4u30trWbnUkhZa712lvN/z4n9vZeOg4f7xhDDOHxlkdSfmAS0f051ezR/DpnhJ+uTQHq26OVP+fPVv+Kg/yh5X7WLajiIcuG8bs0QOsjqN8yG1TUiisbOTZL/MYEBXCd88fYnUkn6bl7kWWbDzKM1/kMW/iQL5zXprVcZQP+umlQymuauCJFftIiAzmmnFJVkfyWVruXuKr/WU88t4uzsuI5ddzRiDS3Tb8SjmXzSY8ft1oSmua+OlbO0iMCmFSWj+rY/kkXXP3AnuLq7nvtS2kx/Vh4U1j8ffTH6uyTqC/jb/eMp6B/UK597UtepOTRbQFPNzxumbuejmb0EA/Xpw/gXB9JJpyA5EhATx/Wxatbe3c/Uo2tU2tVkfyOVruHqy1rZ37X99CaU0Tz92WxQC9+1S5kbTYPiy8eRwHSmt58I1ttLfrFTSupOXuwX67fC9r8yr4zVUjGZ38H4+sVcpy09Nj+fkVw/lkdwl//GSf1XF8ip5Q9VBvb87nxTWHmD81heuz9IHWyn3Nn5rCvuIaFq7KIyM+nDljEq2O5BN05u6Bth+r5OF3dzIlrR+PXDHc6jhKnZaI8NickUxIieaht3fqo/pcRMvdw5TVNPGdVzcT2yeIhTePI0CvjFEeINDfxsKbxhEW5M89/9isJ1hdQJvBg7S1Gx58Yxsn6ptZdNt4+oYFWh1JKbvFRQTz9LyxHC6v47/e2qFbFDiZlrsH+cvnuazOLee/Z49gxIBIq+ModcamDO7HTy4dxoc7i3hpzWGr43g1LXcPsTa3nD99tp+rxyZy4wQ9gao81z0z0rg4M57fLt/D5iPHrY7jtbTcPUBpTSMPLNlGWkwY/3PVSN1aQHk0EeEP148mMTqE+17bQkVtk9WRvJJd5S4is0Rkn4jkishD3Xx+voiUici2zj93OT6qb2prN3x/8TZqm1p45ubxhAXp1avK80WGBPDMzeM4Ud/CT3T93Sl6LHcR8QMWApcBmcA8EcnsZugbxpgxnX+ed3BOn/V/nx1g3cEKfj1nJEP7h1sdRymHGTEgkocvG8bne0t5Zd0Rq+N4HXtm7hOBXGPMQWNMM7AEmOPcWApg0+Hj/OXzA1w7LklvVFJeaf7UFM4fGstvlu9hT1G11XG8ij3lnggc6/I6v/O9k10rIjtE5C0R6baJRGSBiGSLSHZZWdlZxPUd1Y0tPPjGNpKiQ/nvOSOsjqOUU4gIT1w/mojgAB5YvFWfwepA9pR7d2fvTl4g+wBIMcacA3wKvNzdFzLGLDLGZBljsmJjY88sqY/51dIciqoaeerGMfTRdXblxWL6BPHkDaM5UFrLb5bvtjqO17Cn3POBrjPxJKCw6wBjTIUx5ptT3s8B4x0Tzzct21HIO1sKuP/8IYwfFG11HKWc7ryMWBacl8Y/1h9lRU6x1XG8gj3lvglIF5FUEQkE5gJLuw4QkYQuL2cDexwX0bcUVTXwyLu7GJMcxfcu0GdQKt/x40uGMjIxgofe3kFZjV4e2Vs9lrsxphW4H1hBR2m/aYzJEZHHRGR257AHRCRHRLYDDwDznRXYm7W3G3705nZa2tr5041j9IlKyqcE+tt46oYx1DW38fP3durlkb1k12KuMWY5sPyk9x7t8vHDwMOOjeZ7/r72MGvzKvjfa0eREhNmdRylXC49PpwfXZzB7z7ay/vbCrlqrG4PfLZ0augmDpfX8fiKvVwwLI4b9LJH5cPump7GuIFR/HJpDiXVjVbH8Vha7m6gvd3w07d3EOBn47dXj9LtBZRP87N1bE/Q1NrGw+/o8szZ0nJ3A//YcISNh47ziysy6R8ZbHUcpSyXFtuHn17acffqW5vzrY7jkbTcLXbseD2//2gv52XEcn1WktVxlHIb86emMDG1L499sJvCygar43gcLXcLGWN46J0d2ET43TW6HKNUVzab8IfrRtPabnj0/V26PHOGtNwttHjjMdbkVvDw5cNIjAqxOo5Sbmdgv1B+eHEGn+4p5eNdenPTmdByt0hJdSO/Xb6HqYP7cdPEgVbHUcptfXtaCiMGRPDLpTlUNbRYHcdjaLlb5LFlu2lua9erY5Tqgb+fjd9fcw7ltU08/vFeq+N4DC13C3yxr5QPdxTxvfOH6M1KStlhVFIk356WymsbjpJ9WB/NZw8tdxdrbGnj0fdzSIsNY8GMNKvjKOUxfnhxBolRITz8zk6aW9utjuP2tNxdbOGqXI4er+d/rhpJkL+f1XGU8hhhQf78+qoRHCit5W9f5lkdx+1pubtQbmktz36ZxzVjE5k6OMbqOEp5nAuGxXPFOQk8vSqXoxX1Vsdxa1ruLmKM4efv7SQkwI+fXTHc6jhKeaxfXJGJv014bJk+2ON0tNxd5N2tBaw/eJyHLhtOTJ8gq+Mo5bH6RwbzwIXpfLqnhFX7Sq2O47a03F2gtqmV3320lzHJUcydoDs+KtVbd0xLJS0mjMc+2E1Tqz53tTta7i6wcFUuZTVN/Gr2CGw2vaZdqd4K9Lfx6JWZHCqv48XVh62O45a03J3sSEUdL3x9iGvHJTEmOcrqOEp5jZlD47g4M56nPz9AcZXu+34yLXcn+82HewjwE/5r1lCroyjldX5xRSat7YbfLtfHNp9My92JVh8oZ+XuEr57wRDiInSfdqUcbWC/UO45L42l2wvZcLDC6jhuRcvdSVrb2nlsWQ4D+4Zyx7RUq+Mo5bXunTmExKgQHlu2m/Z23Rb4G1ruTvL6xqPsL6nlkSuGExygd6Iq5SwhgX785NKh5BRW8/72AqvjuA0tdyeorG/myU/2M21IPy7JjLc6jlJeb/boAYxMjOCJj/fR2KKXRoKd5S4is0Rkn4jkishDpxl3nYgYEclyXETP88wXeVQ1tPCLb2Xqdr5KuYDNJvzs8uEUVjXy0prDVsdxCz2Wu4j4AQuBy4BMYJ6IZHYzLhx4ANjg6JCepKCygb+vPcy145IY1j/C6jhK+Yypg2O4cFgcz6zKpaK2yeo4lrNn5j4RyDXGHDTGNANLgDndjPs18Djg0xecPvXJfgAevDjD4iRK+Z6HLhtGXXMrT3+ea3UUy9lT7onAsS6v8zvf+xcRGQskG2OWne4LicgCEckWkeyysrIzDuvu9hZX8/aWfOZPTdFnoiplgfT4cOZOHMg/1h/hUHmd1XEsZU+5d7do/K/rjUTEBjwF/KinL2SMWWSMyTLGZMXGxtqf0kM8/vE+woP8uW/mYKujKOWzfnBROoH+Nv73I99+JJ895Z4PdN3tKgko7PI6HBgJfCEih4HJwFJfO6m6/mAFn+8t5b7zhxAVGmh1HKV8Vlx4MPfMGMzHOcVsPnLC6jiWsafcNwHpIpIqIoHAXGDpN580xlQZY2KMMSnGmBRgPTDbGJPtlMRuyBjD7z/aS/+IYOZPTbE6jlI+785zU+kXFsiTn+yzOopleix3Y0wrcD+wAtgDvGmMyRGRx0RktrMDeoKPdxWz7VglP7w4Q29YUsoNhAX5c+/MwazJrWBtXrnVcSwhxlhzu25WVpbJzvb8yX1bu+GSp77EJsJH35+Ov5/eF6aUO2hsaWPGE6tIjg7ln/dM8Zp7TkRkszGmx2VvbaJe+mB7IXlldTx4cYYWu1JuJDjAj/svSCf7yAm+3O99V+f1RNuoF1rb2vnzZwcY1j+cWSP6Wx1HKXWSG7OSSYoO4Y8r92PVKoVVtNx7Yen2Qg6W1/GDi9L1CUtKuaFAfxvfvzCdnQVVrNxdYnUcl9JyP0vfzNqHJ0RwSabO2pVyV1ePTSQtJownV+73qS2BtdzP0nvbCjlcUa+zdqXcnL+fjR9cnMG+khqW7SyyOo7LaLmfhda2dp7+/AAjBkTolr5KeYBvjUpgaHw4f/p0P20+MnvXcj8L72wt4EhFPT+4KMNrLq9SypvZbML9FwzhYFkdH+8qtjqOS2i5n6GWzln7qMRILhoeZ3UcpZSdLh+VQFpMGH9ZlesTV85ouZ+hd7cWcOx4Aw9enK6zdqU8iJ9NuHfmYPYUVbNqX6nVcZxOy/0MtLcbnv0yj8yECM4fqrN2pTzNVWMTSYwK4S+fe//sXcv9DKzcXcLBsjrunTlYZ+1KeaAAPxv3zEhjy9FK1h2ssDqOU2m528kYw1+/zGNQv1AuG6nXtSvlqa7PSiY2PIiFq7z7aU1a7nZad7CC7ccqWXBemu4ho5QHCw7w4+7pqazJrWDrUe/d711byk5//SKPmD5BXDsuyeooSqleunnSIKJCA7x69q7lboed+VV8faCcO89N1f3alfICYUH+3DEtlU/3lLK7sNrqOE6h5W6HZ7/MIzzIn5snD7Q6ilLKQW6fkkJooB/Prz5odRSn0HLvwaHyOpbvKuLWKYOICA6wOo5SykEiQwO4ISuZD7YXUlLdaHUch9Ny78Gir/II8LPx7WmpVkdRSjnYHdNSaWs3vLz2sNVRHE7L/TTKapp4e3MB149PIjY8yOo4SikHG9gvlEtH9Oe1DUepb261Oo5DabmfxusbjtLc1s4d5+qsXSlvddf0VKoaWnhrc77VURxKy/0UmlrbeHX9EWYOjWVwbB+r4yilnGTcwGjGJEfx4upDXrUdsJb7KXy4o4jy2ibu0LV2pbyaiHDX9FQOV9Tz2R7veRSfXeUuIrNEZJ+I5IrIQ918/h4R2Ski20RktYhkOj6q6xhjeHHNIYbE9WF6eozVcZRSTjZrRH8So0J4/utDVkdxmB7LXUT8gIXAZUAmMK+b8n7dGDPKGDMGeBx40uFJXSj7yAl2FVTz7WkpukGYUj7A38/Gt6elsPHwcbYfq7Q6jkPYM3OfCOQaYw4aY5qBJcCcrgOMMV1v8QoDPHrh6sXVh4gMCeCasbrVgFK+4sYJyYQH+fP8au+YvdtT7onAsS6v8zvf+zci8l0RyaNj5v5Ad19IRBaISLaIZJeVlZ1NXqfLP1HPipxi5k0cSEigbjWglK8IDw7gxgnJLN9ZRHGV59/UZE+5d7cu8R8zc2PMQmPMYOC/gJ9394WMMYuMMVnGmKzY2NgzS+oir6w7gohw25RBVkdRSrnYrVMG0W4Mr288anWUXrOn3POB5C6vk4DC04xfAlzVm1BWqWtqZcnGo8wa2Z8BUSFWx1FKudigfmHMzIhl8cajNLe2Wx2nV+wp901AuoikikggMBdY2nWAiKR3eXkFcMBxEV3nna0FVDe2cse0FKujKKUsctuUFMpqmliRU2x1lF7psdyNMa3A/cAKYA/wpjEmR0QeE5HZncPuF5EcEdkG/BC43WmJncQYw2vrjzAyMYJxA6OtjqOUssiMjFgG9g3l1XVHrI7SK/72DDLGLAeWn/Teo10+/r6Dc7nc5iMn2Ftcw++vGaWXPyrlw2w24ZbJA/nt8r3sLa5mWP8IqyOdFb1DtdNrG44SHuTPlaMHWB1FKWWxG7KSCfK38YoHz9613IHjdc18uLOIq8clEhZk1y8zSikvFhUayJwxA3h3SwE1jS1WxzkrWu7A25vzaW5t56ZJ+qQlpVSHmyYNoqGljaXbT3dxoPvy+XJvb++4pjVrULTHrq0ppRxvdFIkwxMiWOyh17z7fLmvzavgUHkdt0zWm5aUUv+fiDBvYjK7CqrZmV9ldZwz5vPlvnjjUaJCA5g1sr/VUZRSbmbOmESCA2ws3uR5s3efLvfjdc2s3F3M1WMTCQ7QfWSUUv8uMiSAy0clsHRbIXVNnvUYPp8u9/e2FtDSZrhxQnLPg5VSPummiQOpbWpl2Q7POrHqs+VujOHN7GOckxSpJ1KVUqc0flA0Q+L6sHjjsZ4HuxGfLfedBVXsLa7hhiydtSulTk1EmDshmW3HKtlfUmN1HLv5bLm/sekYQf42Zo/RO1KVUqd31dhE/G3C25vzrY5iN58s94bmNpZuK+TyUQlEBAdYHUcp5eZi+gQxc2gc72wtoLXNM7YC9sly/ziniJqmVl2SUUrZ7brxSZTVNPH1gXKro9jFJ8v9rc35DOwbyqTUvlZHUUp5iAuGxREdGsBbWzxjacbnyr2oqoG1eRVcPTYRm0239lVK2SfQ38acMYl8klNCVb37bybmc+W+dFshxnScIFFKqTNx3fgkmtva+cADrnn3uXJ/d2sBYwdGkRoTZnUUpZSHGTEggmH9w3nLA66a8aly31NUzd7iGq7RWbtS6iyICNeOS2LbsUryymqtjnNaPlXu724twN8mXHGOXtuulDo7s8cMQKRjided+Uy5t7Ub3t9WwMyhcfQNC7Q6jlLKQ8VHBDM5tR8fbC/EGGN1nFPymXJfl1dBSXUT14zTJRmlVO/MGTOAg+V17CqotjrKKflMub+7tYDwYH8uGBZndRSllIe7bGQCAX7C+9sKrI5ySnaVu4jMEpF9IpIrIg918/kfishuEdkhIp+JiFs91qixpY2VOcXMGtFf921XSvVaZGgAMzLi+GBHIW3t7rk002O5i4gfsBC4DMgE5olI5knDtgJZxphzgLeAxx0dtDe+PlBOTVMr3xqtJ1KVUo4xZ8wASqqb2HjouNVRumXPzH0ikGuMOWiMaQaWAHO6DjDGrDLG1He+XA8kOTZm7yzbUUh0aABTB/ezOopSyktcNDye0EA/lm53z6UZe8o9Eei6S31+53uncifwUXefEJEFIpItItllZWX2p+yFxpY2Pt1dwqyR/Qnw85lTDEopJwsJ9OOSzHiW7yymudX9doq0p+2624Cl20UmEbkFyAKe6O7zxphFxpgsY0wQq5JBAAAKoUlEQVRWbGys/Sl7YdXeUuqa2/iWXtuulHKw2WMGUNXQwupc10xWz4Q95Z4PdN0bNwn4j6v3ReQi4BFgtjGmyTHxem/ZziJi+gTqDpBKKYebNiSG8CB/PtpZbHWU/2BPuW8C0kUkVUQCgbnA0q4DRGQs8Dc6ir3U8THPTn1zK5/vKWXWyP7465KMUsrBgvz9uCgznk/2lNDiZg/x6LHxjDGtwP3ACmAP8KYxJkdEHhOR2Z3DngD6AP8UkW0isvQUX86lPttTSkOLLskopZxn1sj+VNa3sP5ghdVR/o2/PYOMMcuB5Se992iXjy9ycC6H+HBHEbHhQUxI0SUZpZRzzMiIJTTQj492FTM93TXnEu3htWsVDc1tfLG/lFkj+uOnD+VQSjlJcIAfFwyLY2VOsVvd0OS15b46t5zGlnYuHdHf6ihKKS932cgEymub2XTYfW5o8tpyX5FTTHiwP5PSdElGKeVcM4fGEhxg4+Nd7nPVjFeWe2tbO5/tKeHCYXF645JSyunCgvyZkRHLR7uKaHeTpRmvbL7sIyc4Ud/CJboko5RykctGJlBS3cTWY5VWRwG8tNxX5pQQ6G9jRob7nLlWSnm384fF4WcTPttTYnUUwAvL3RjDyt3FTB8SQ1iQXVd6KqVUr0WGBDAhJZrP9rjHfZxeV+67i6rJP9HAJSPirY6ilPIxFw2PZ19JDceO1/c82Mm8rtxX5pQgAhcO13JXSrnWN73jDkszXlfun+wuYfzAaGL6BFkdRSnlY1JjwkiLDeOzvdYvzXhVuZdUN7K7qFpn7Uopy1w0PJ71ByuoaWyxNIdXlfuX+zr2VJ45VK+SUUpZ48JhcbS0Gb4+UG5pDq8q91X7SukfEcyw/uFWR1FK+ajxg6KJDAngU4vX3b2m3Fva2ll9oJyZQ2MR0Y3ClFLW8PezMXNoLF/sK7N0IzGvKffNR05Q09TKzKFxVkdRSvm4C4fHc7yuma1HT1iWwWvK/Yt9ZfjbhGlD+lkdRSnl42akx2IT+MrCdXcvKvdSslKiCQ8OsDqKUsrHRYYGMCopiq8PWPfgbK8o96KqBvYW13C+LskopdzEeekxbD9WSVWDNZdEekW5f/GvSyC13JVS7mF6eiztBtblWbM04yXlXsqAyGAy4vtYHUUppQAYOzCKsEA/y6539/hyb21rZ21uBTP0EkillBsJ8LMxZXA/LfeztauwmpqmVqYOjrE6ilJK/Zvp6bEcPV7PkYo6l39vu8pdRGaJyD4RyRWRh7r5/HkiskVEWkXkOsfHPLV1eRUATE7TSyCVUu7l3PSOSacVs/cey11E/ICFwGVAJjBPRDJPGnYUmA+87uiAPVmbV05GfB9iw3UXSKWUe0mLCSMxKsSSSyLtmblPBHKNMQeNMc3AEmBO1wHGmMPGmB1AuxMynlJzazvZh08wRWftSik3JCJMT49hbW4FrW0urUe7yj0RONbldX7ne2dMRBaISLaIZJeV9f7/ZNvzK2loaWOKrrcrpdzUuekx1DS1sj3ftQ/Otqfcu7sE5ax2wzHGLDLGZBljsmJje78t77q8CkRgclrfXn8tpZRyhm8u9vjm/KCr2FPu+UByl9dJQKFz4pyZtXnlZCZEEBUaaHUUpZTqVt+wQIb1D2fDoeMu/b72lPsmIF1EUkUkEJgLLHVurJ41trSx5Wilrrcrpdze5LR+ZB8+QYsL1917LHdjTCtwP7AC2AO8aYzJEZHHRGQ2gIhMEJF84HrgbyKS48zQAFuOnKC5tZ2pugukUsrNTUrtS0NLGzvyq1z2Pf3tGWSMWQ4sP+m9R7t8vImO5RqXWXewAj+bMCFF19uVUu5tYmpHT204VMH4QdEu+Z4ee4fq2rwKRiVG6ha/Sim3169PEBnxfVh/0HXr7h5Z7o0tbezIr9S7UpVSHmNSaj82Hz7uskfveWS5bz9WSUubIctFv94opVRvZaVEU9fcxt7iapd8P48s982dzyV01dqVUkr11riBHX215YhrnqvqmeV++ASDY8OIDtPr25VSniEpOoT4iCCytdy7Z4xh89ETOmtXSnkUEWH8oGg2a7l3L6+sjsr6FrIG6SWQSinPMn5QX/JPNFBS3ej07+Vx5f7NetU4nbkrpTzMNysOrpi9e1y5R4UGcHFmPINjw6yOopRSZ2TEgAguGBZHWJBd94/2ihjjmmsuT5aVlWWys7Mt+d5KKeWpRGSzMSarp3EeN3NXSinVMy13pZTyQlruSinlhbTclVLKC2m5K6WUF9JyV0opL6TlrpRSXkjLXSmlvJBlNzGJSBlw5Az+kRig3Elx3Jket+/x1WPX47bPIGNMbE+DLCv3MyUi2fbcleVt9Lh9j68eux63Y+myjFJKeSEtd6WU8kKeVO6LrA5gET1u3+Orx67H7UAes+aulFLKfp40c1dKKWUntyt3EZklIvtEJFdEHurm80Ei8kbn5zeISIrrUzqeHcf9QxHZLSI7ROQzERlkRU5H6+m4u4y7TkSMiHjF1RT2HLeI3ND5M88RkdddndEZ7Ph7PlBEVonI1s6/65dbkdPRRORFESkVkV2n+LyIyJ87/73sEJFxvf6mxhi3+QP4AXlAGhAIbAcyTxpzH/Bs58dzgTeszu2i4z4fCO38+F5fOe7OceHAV8B6IMvq3C76eacDW4HoztdxVud20XEvAu7t/DgTOGx1bgcd+3nAOGDXKT5/OfARIMBkYENvv6e7zdwnArnGmIPGmGZgCTDnpDFzgJc7P34LuFBExIUZnaHH4zbGrDLG1He+XA8kuTijM9jz8wb4NfA44PynCruGPcd9N7DQGHMCwBhT6uKMzmDPcRsgovPjSKDQhfmcxhjzFXD8NEPmAK+YDuuBKBFJ6M33dLdyTwSOdXmd3/let2OMMa1AFdDPJemcx57j7upOOv4v7+l6PG4RGQskG2OWuTKYk9nz884AMkRkjYisF5FZLkvnPPYc96+AW0QkH1gOfM810Sx3ph3QI+c/pfXMdDcDP/lyHnvGeBq7j0lEbgGygBlOTeQapz1uEbEBTwHzXRXIRez5efvTsTQzk47f0r4WkZHGmEonZ3Mme457HvB3Y8wfRWQK8Grncbc7P56lHN5r7jZzzweSu7xO4j9/LfvXGBHxp+NXt9P9uuMJ7DluROQi4BFgtjGmyUXZnKmn4w4HRgJfiMhhOtYil3rBSVV7/56/b4xpMcYcAvbRUfaezJ7jvhN4E8AYsw4IpmPvFW9nVwecCXcr901AuoikikggHSdMl540Zilwe+fH1wGfm84zEh6sx+PuXJ74Gx3F7g3rr9DDcRtjqowxMcaYFGNMCh3nGmYbY7Ktiesw9vw9f4+Ok+iISAwdyzQHXZrS8ew57qPAhQAiMpyOci9zaUprLAVu67xqZjJQZYwp6tVXtPos8inOGu+n46z6I53vPUbHf9TQ8cP+J5ALbATSrM7souP+FCgBtnX+WWp1Zlcc90ljv8ALrpax8+ctwJPAbmAnMNfqzC467kxgDR1X0mwDLrE6s4OOezFQBLTQMUu/E7gHuKfLz3th57+XnY74e653qCqllBdyt2UZpZRSDqDlrpRSXkjLXSmlvJCWu1JKeSEtd6WU8kJa7kop5YW03JVSygtpuSullBf6f2LSvo9kyHKxAAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "\n", "def entropy(p):\n", " return -p * np.log(p) - (1-p) * np.log(1-p)\n", "\n", "x = np.linspace(0.01, 0.99, 200)\n", "\n", "plt.plot(x, entropy(x))\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "从图中可以看出，当数据所占比例为 0.5 时，信息熵的值达到最大。\n", "\n", "### 信息增益\n", "\n", "有了信息熵了概念之后，我们再来看看 **信息增益**（information gain），信息增益表示根据某个属性对数据进行划分后，数据的信息熵得到了多大的提升。比如属性 a 有 V 个可能的取值，如果用属性 a 对数据集进行划分，则可以得到 V 个分支节点（注意，我们在这里只考虑该属性是离散值），也就是 V 个子集，我们记为 $D^v（v = 1,2,...,V）$，我们可以计算出每个子集的信息熵 $Ent(D^v)$，然后将所有子集的信息熵累加起来作为子集的信息熵，考虑到每个子集所含样本数不一样，我们再根据各自的比例乘上相应的系数：\n", "\n", "$$\n", "Ent(D_a) = \\sum_{v=1}^{V} \\frac{|D^v|}{|D|} Ent(D^v)\n", "$$\n", "\n", "其中，$|D^v|$ 表示第 v 个子集所含样本的数量，$|D|$ 表示数据集 $D$ 的样本总数。\n", "\n", "这样，我们就可以得到根据属性 a 对数据进行划分的信息增益：\n", "\n", "$$\n", "Gain(D, a) = Ent(D) - Ent(D_a) = Ent(D) - \\sum_{v=1}^{V} \\frac{|D^v|}{|D|} Ent(D^v)\n", "$$\n", "\n", "信息增益越大，表示使用属性 a 进行划分所得到的纯度提升越大，所以只要对每一个属性进行计算，找到信息增益最大的属性进行划分即可。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 增益率\n", "\n", "使用信息增益对样本进行划分存在一个问题：信息增益对取值较多的属性有所偏好。我们设想一个极端的情形，比如样本集共有 N 个类别，而其中某一个属性的取值也有 N 个，如果使用这个属性对样本进行划分，将得到 N 个分支节点，每个分支仅包含一个样本，很显然分支无法再继续划分了，但是这样的决策树绝大多情况下没有任何作用，其不具有泛化能力。\n", "\n", "通常使用 **增益率**（gain ratio）来解决这个问题：\n", "\n", "$$\n", "Gain\\_ratio(D, a) = \\frac{Gain(D, a)}{IV(a)}\n", "$$\n", "\n", "其中，IV 被称为属性 a 的 **固有值**（intrinsic value），$IV(a)$ 的定义如下：\n", "\n", "$$\n", "IV(a) = - \\sum_{v=1}^{V} \\frac{\\left| D^v \\right|}{\\left| D \\right|} log_2 \\frac{\\left| D^v \\right|}{\\left| D \\right|}\n", "$$\n", "\n", "属性 a 的可能取值越多，它的固有值 IV 通常越大。\n", "\n", "值得注意的是，增益率对取值较少的属性有所偏好，在实际使用中，通常使用启发式算法来综合使用增益率和信息增益。譬如在 C4.5 算法中，首先找出信息增益高于平均水平的属性，然后再从中选择增益率最高的。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 基尼指数\n", "\n", "信息熵是度量样本集合纯度最常用的一种指标之一，除此之外，还有其他指标来度量样本集合纯度，比如 **基尼值**：\n", "\n", "$$\n", "Gini(D) = \\sum_{k=1}^{\\left| \\mathcal{Y} \\right|} \\sum_{k' \\ne k} p_k p_{k'} \n", "= 1 - \\sum_{k=1}^{\\left| \\mathcal{Y} \\right|} p_k^2\n", "$$\n", "\n", "可以看出，基尼值反映了从数据集中随机抽取两个样本，其类别不一致的概率。因此基尼值越小，数据集的纯度越高。\n", "\n", "根据基尼值就可以定义出属性 a 的 **基尼指数**（Gini index）:\n", "\n", "$$\n", "Gini\\_index(D, a) = \\sum_{v=1}^{V} \\frac{\\left| D^v \\right|}{\\left| D \\right|} Gini(D^v)\n", "$$\n", "\n", "和信息增益的做法一样，使用基尼指数作为构建决策树的划分方法，首先计算出所有属性的基尼指数，然后选择基尼指数最小的属性即可。" ] } ], "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.1" } }, "nbformat": 4, "nbformat_minor": 2 }