38. Information Entropy and Gina Coefficient.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "assigned-david",
   "metadata": {},
   "source": [
    "# Information Entropy and Gina Coefficient\n",
    "\n",
    "## Information Entropy\n",
    "Information Entropy implys the uncertain degree of a random variable\n",
    "\n",
    "$$H = -\\sum ^k_{i = 1}p_ilog(p_i)$$\n",
    "\n",
    "$$(p_i\\ is\\ the\\ ratio\\ of\\ i)$$\n",
    "\n",
    "+ x决策树算法利用了信息熵和决策树思维：\n",
    "    1. 信息熵越小的数据集，样本的确定性越高，当数据集的信息熵为 0 时，该数据集中只有一种类型的样本；\n",
    "    2. 训练数据集中有很多类型的样本，通过对数据集信息熵的判断，逐层划分数据集，最终将每一类样本单独划分出来；\n",
    "    3. 划分数据集的方式有很多种，只有当按样本类别划分数据集时（也就是两部分数据集中不会同时存在相同类型的样本），划分后的两部分数据集的整体的信息熵最小；反相推断，当两部分数据集的整体的信息熵最小时，则两部分数据集中不会同时存在相同类型的样本；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "removed-failing",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "broke-engine",
   "metadata": {},
   "outputs": [],
   "source": [
    "def entropy(p):\n",
    "    return -p * np.log(p) - (1-p) * np.log(1-p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "metropolitan-irish",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = np.linspace(0.01, 0.99, 200)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "regulated-guard",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD4CAYAAAD8Zh1EAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAqUUlEQVR4nO3deXhV5bn+8e+TeSDzQEhCSAJhSJgJYRIFR0ALjhXqcBw5tFLbHj1H29rhtKe1nva01Val1NrWEXGmiqKiIDKHeQyEBEjCkInMc/L+/kjsL8VAdmDvvfbwfK4r15W99yL7XgTurLzrXe8SYwxKKaXcn4/VAZRSStmHFrpSSnkILXSllPIQWuhKKeUhtNCVUspD+Fn1xrGxsSY1NdWqt1dKKbe0bdu2cmNMXE+vWVboqamp5ObmWvX2SinllkTk2Lle0yEXpZTyEFroSinlIbTQlVLKQ9hU6CIyS0TyRCRfRB7t4fX/FJGdXR97RaRdRKLtH1cppdS59FroIuILPA3MBjKBBSKS2X0bY8yvjTFjjTFjge8Da40xlQ7Iq5RS6hxsOULPAfKNMQXGmBZgGTDvPNsvAF61RzillFK2s6XQk4Cibo+Lu577ChEJAWYBb57j9YUikisiuWVlZX3NqpRS6jxsmYcuPTx3rjV3vwasP9dwizFmKbAUIDs7W9ftVU5njKGmqY2y2iZKa5qpqG+hsbWdptZ2GlvaaWxtB8Df1wc/H8HP14dAPx8iQ/yJDgkgKjSAmNAAokMD8PPVOQXKtdhS6MXAwG6Pk4ET59h2PjrcolxAbVMreadqOVJWx5GyevJL6ygoq+NkdRPNbR0X/fX9fISkqGAGxYQyKDqEQTEhZA4IJysxgogQfzvsgVJ9Z0uhbwUyRCQNKKGztL9x9kYiEgFcBtxu14RK9aKjw3CotJYdx6vYcfwMO4uqOFxax5f3bgnw8yE9NpSsxAiuyuxPfFgQ8eGBxIcFEdMvgJAAX4L9fQkO8CXIzxeAtg5DW0cHre2G5tZ2qhpbqaxvobK+hYr6Fk5VN3KsooFjFQ3sOH6G2qa2f+ZJiQ5hZFI4Y5IjmTI4hqzECHx9evpFVyn76rXQjTFtIrIYWAX4As8bY/aJyKKu15d0bXoD8JExpt5haZXqUl7XzLrDZXx+qJx1h8sor2sBICrEn7EDI7ludCIjk8IZEhdGUlRwnws1wEcI+PIUU7A/8eFB59zWGENlfQv7T9awp6SafSU17D1Rzco9pwAIC/JjcnoMUwfHMGNYPGmxoRe200r1Qqy6BV12drbRtVxUXxSfaWDlnpO8v/sku4qrAYgODWB6RizTM+LIHhTFoJgQRFzjaLi0tolNBZVsPFLOhiMVHKtoAGBo/37Mykrg6qwEshLDXSavcg8iss0Yk93ja1roypWV1jaxYucJ3tt9kp1FVQCMTo7g6sz+XDY0nqzEcHzcZDijqLKBTw6c5sO9p9h6tJIOAwOjg7lhXDK3TEhmYHSI1RGVG9BCV26lo8PwRX45r245zsf7T9PWYchKDOfa0QO4blQiKTHuX3wVdc18cuA07+0+yRf55RgDk9OjuWXCQGaPSiAkwLKFUJWL00JXbqGqoYWXNx9n2dbjFFU2EhXiz80Tkrl1YgpD4vtZHc9hTlQ18tb2Yt7YVszRigYigv1ZkJPCnVMGkRgZbHU85WK00JVLK6lq5C/rClm29TgNLe1MTo/mG5MGcU1WfwK7Zp14A2MMWworeWHjMT7YexIRYc6oAdwzLZVxKVFWx1Mu4nyFrr/XKcscOl3Ls2uOsGLXCQSYOyaR+y9NZ8SAcKujWUJEmJQew6T0GIrPNPD3DUdZtqWIf+w6wSVDYvnulRlkp+qad+rc9AhdOd2xinp+/8lh3tlZQrC/LwtyUrjnkjSSdHjhK+qa23h183H+9PkRyutamJ7RWewTBmmxeysdclEu4XRNE0+tPsxrW4vw8xX+bWoqiy4dTFRogNXRXF5jSzsvbTrGkrVHqKhv4bKhcfxgzgiGJYRZHU05mRa6slRTaztL1h5hydojtHcY5k9MYfHlQ+h/not1VM8aWtp4ceMxnv4sn7rmNubnpPAfVw0ltl+g1dGUk2ihK0sYY/hw7yn+5/0DlFQ1ct3oATwya7jOt7aDM/UtPLn6MC9uOkaIvy8PXD6Eu6eletVJZG+lha6c7tDpWn66Yh8bjlQwPCGM/56bxaT0GKtjeZz80joeX3mA1QdLSY8L5Zc3jGKy/j17NC105TQtbR08syafpz/LJyTAj4evHsqCnBRdatbB1uSV8qN391JU2cit2QP5/pzhRIbouQlPpIWunGJXURX/9cZu8k7XMm9sIj++LpMYHdt1msaWdn6/+hDPrSskKsSfH12XydwxibpWjIfRQlcO1dTazm8/PsRz6wqIDwviFzeM5IoR/a2O5bX2n6jh+2/vYVdRFXNGJfCL60fpTCIPohcWKYc5eKqGB1/dwaHTdSzIGcj354wgPEhv8GClzMRw3vrmVJZ+XsBvP84j9+gZ/vfm0cwYFm91NOVgOrCpLogxhr9vOMrcP66nsr6Vv9+Tw+M3jtYydxG+PsI3ZwzmnQemERniz11/3cqP3tlLY0u71dGUA+kRuuqzirpm/vON3Xx6sJSZw+L49S1jdB60i8pKjGDF4kv49ao8/vJFIZsKKnj29vEMidcLkjyRHqGrPsk9WsnsJ9fxRX45P/1aJs/fNVHL3MUF+fvyo+syefHeHCrrW5j7x/W8u7PE6ljKAbTQlU2MMfxtfSHzl24iJMCXd741jbumpekMCjcyPSOO9x+cTuaAcL6zbCePvbOH5jYdgvEkWuiqV40t7XzvtZ389B/7mTEsjncXX0JmoneuiOjuEiKCeHXhZBZems5Lm45zy5KNnKhqtDqWshMtdHVexysauOGZ9by76wQPXTWUpXdkExGsJz7dmb+vDz+YM4Kld0ygsKyeuX9cz/bjZ6yOpexAC12dU+7RSq5/Zj0nq5v4610T+fYVGW5z/07Vu6uzEnjrW1MJCfBl/tJNvLNDx9XdnRa66tG7O0v4xp83ExHsz7sPTNM5zB4qo38Y7z4wjXEDI/nuazv53w8P0tFhzcWG6uLZVOgiMktE8kQkX0QePcc2M0Rkp4jsE5G19o2pnMUYw1OrD/OdZTsZmxLJW9+cSmpsqNWxlANFhQbw4r2TWJAzkGfWHOFbL2+nqVVPlrqjXgtdRHyBp4HZQCawQEQyz9omEngGmGuMyQJusX9U5WgtbR089PoufvvxIW4cl8SL9+boJeNeIsDPh1/eMIrHrh3Bqv2nuPMvW6huaLU6luojW47Qc4B8Y0yBMaYFWAbMO2ubbwBvGWOOAxhjSu0bUzlaY0s797+Qy1vbS/jelUP5v6+P0bW1vYyIcN/0dJ6aP44dRWf4+p82cqq6yepYqg9sKfQkoKjb4+Ku57obCkSJyBoR2SYid/b0hURkoYjkikhuWVnZhSVWdlfd0Mrtf9nMusNl/OrGUXznygydX+7FvjYmkb/fnUNJVSM3PrOe/NJaqyMpG9lS6D39zz77rIkfMAG4FrgG+JGIDP3KHzJmqTEm2xiTHRcX1+ewyv5Ka5u4delGdhdX8cdvjGd+TorVkZQLmDoklmULJ9PSbrh5yUZ2FlVZHUnZwJZCLwYGdnucDJzoYZsPjTH1xphy4HNgjH0iKkcpqmzgliUbOV7ZwPN3TWTOqAFWR1IuZGRSBG99cyrhQf7c/txmco9WWh1J9cKWQt8KZIhImogEAPOBFWdt8y4wXUT8RCQEmAQcsG9UZU/HKur5+p82UtXQykv3TWJ6hv7GpL4qJSaE5f8+hfiwQO58fgubCiqsjqTOo9dCN8a0AYuBVXSW9HJjzD4RWSQii7q2OQB8COwGtgDPGWP2Oi62uhjHKuqZv3QTTa3tvHr/ZManRFkdSbmwhIggli2cTGJkMHf9dQvr88utjqTOQe9Y5GW6l/nL903WNVmUzcrrmrn9uc0Ultfzpzsm6MVmFjnfHYv0SlEvomWuLkZsv0BeuX8yg+P6sfCFbXxxWI/UXY0WupcoqmzQMlcXLTo0gFfun0R6XCj3v5CrJ0pdjBa6FyitaeK25zbT0KJlri5eZEjnUgEDIoK4+69b2VtSbXUk1UUL3cNVN7Ry5/NbKK9r5m93T9QyV3YRFxbIS/dNIjzYnzv+splDp/XiI1eghe7BGlrauOfvWykoq2fpHdmM09ksyo4SI4N5+b5J+Pv6cPtzmzlWUW91JK+nhe6hWto6WPTSdnYcP8NTC8ZySUas1ZGUB0qNDeXl+ybR2t7xz98ElXW00D1QR4fhodd38fmhMh6/cRSzRuoVoMpxMvqH8fxdEzld08S9f9tKQ0ub1ZG8lha6B3pi1UH+sesEj84ezq0TdW0W5XjjUqL4w4Lx7CmpZvErO2hr77A6klfSQvcwr2w+zp/WFnD75BT+/dJ0q+MoL3JVZn9+Nm8knx4s5Ufv7sWqixa9mZ/VAZT9rMnr/I80c1gcP/1ali6Bq5zu9smDOFHVyDNrjpAYEcy3r8iwOpJX0UL3EPtP1LD4lR0M6x/GH74xHj9f/eVLWeM/rxnGqeom/u/jQ6TEhDBv7Nm3T1COov/rPcCp6ibu+dtW+gX68fxdE+kXqD+nlXVEhF/dNJqc1Gj+643d7NK11J1GC93NNbW28+8v5lLb1Mrzd00kISLI6khKEeDnw7O3jye2XyALX8zldI3eys4ZtNDdmDGGH7y9h13F1fzu1rF6FahyKTH9Annu37KpbWpj4Qu5NLW2Wx3J42mhu7G/rj/KW9tL+O6VGVydlWB1HKW+YsSAcH5361h2FVfzyJu7deaLg2mhu6n1+eX8YuUBrs7sz4OX60wC5bquyUrg4auH8u7OEzy79ojVcTyaFrobKqpsYPEr20mPDeW3t47Fx0enJyrX9sDMIVw3egC/WZWndzxyIC10N9PY0s7CF7fR3mFYeme2zmhRbkFEeOKm0aTH9ePBV3dwqlpPkjqCFrqb+cmKvRw8VcOTC8aRFhtqdRylbBYa6MeS28fT2NrOA69sp1WXB7A7LXQ38ua2YpbnFvPAjCHM1Ps5Kjc0JD6MJ24azbZjZ3h85UGr43gcLXQ3cfh0LY+9s5dJadF890o9Carc19fGJHLX1FSeX1/I+7tPWh3Ho2ihu4GGlja+9fJ2QgN9+cOCcXpZv3J7P5gzgvEpkfzXG7s4UlZndRyPYVMziMgsEckTkXwRebSH12eISLWI7Oz6+LH9o3onYwyPvbOX/LI6npw/jvhwvRJUub8APx+evm08AX4+PPjqDprb9KIje+i10EXEF3gamA1kAgtEJLOHTdcZY8Z2ffzMzjm91uvbinlrewkPXp7BtCF61yHlOQZEBPPETaPZd6KG36zKszqOR7DlCD0HyDfGFBhjWoBlwDzHxlIAheX1/OTdfUxJj+FBXYZUeaCrsxK4Y/Ig/ryukLWHyqyO4/ZsKfQkoKjb4+Ku5842RUR2icgHIpLV0xcSkYUikisiuWVl+s07n9b2Dr772k4C/Hz47a1j8NWLh5SH+uG1Ixjavx8PLd+l9yS9SLYUek9NcvaCDNuBQcaYMcAfgHd6+kLGmKXGmGxjTHZcXFyfgnqbP3yaz66iKn55wygGRARbHUcphwny9+WpBeOoaWrl4dd36XovF8GWQi8GBnZ7nAyc6L6BMabGGFPX9flKwF9EdMD3Am07doY/fnqYm8Ync+1ovcGz8nzDE8J57NoRrMkr46/rj1odx23ZUuhbgQwRSRORAGA+sKL7BiKSIF33OxORnK6vW2HvsN6grrmN7722k6SoYH46t6dzz0p5pjsmD+LKEfH86oODHD5da3Uct9RroRtj2oDFwCrgALDcGLNPRBaJyKKuzW4G9orILuApYL7R35suyH+v2EfxmQZ+9/WxhAX5Wx1HKacRER6/cTShgb489Pou2nRpgD6zaR66MWalMWaoMWawMeYXXc8tMcYs6fr8j8aYLGPMGGPMZGPMBkeG9lSr9p3i9W3FPDBzCNmp0VbHUcrp4sIC+Z/rR7G7uJolutRun+klhy6iqqGFH769l8wB4TpFUXm1a0cP4LrRA3hy9WEOnKyxOo5b0UJ3ET/7x36qGlr49S2j8ddL+5WX+9m8kUQE+/PQ8l20tOnQi620OVzApwdP89aOEr41YzBZiRFWx1HKctGhAfzyhlHsP1nD05/lWx3HbWihW6y6sZXvv7WHYf3DWKy3klPqn67OSuCGcUk8/Vk+e0uqrY7jFrTQLfaL9/dTXtc51BLgp98Opbr76deyiA4N4L/e2K2zXmygDWKhtYfKWJ5bzMJL0xmdHGl1HKVcTkSIP/89N4v9J2v0giMbaKFbpKGljR+8tYch8f34js5qUeqcZo1M4MoR/fntx4coqmywOo5L00K3yJOrD1NS1cjjN44iyN/X6jhKuSwR4WfzsvAReOydvbrWy3looVvg4Kka/rKukFuzBzJRLyBSqleJkcE8fM0w1h4qY8WuE73/AS+lhe5kHR2Gx97eS1iQH4/OHm51HKXcxp1TUhmTHMHP3+u8ZkN9lRa6k72+rYjcY2f4wZwRRIUGWB1HKbfh69O51suZhlYeX3nQ6jguSQvdiSrqmnn8g4PkpEVz84Rkq+Mo5XYyE8O5b3oar+UWkXu00uo4LkcL3Yke/+AgdU1t/OL6kXStNqyU6qPvXJHBgIggfvzuPto79ARpd1roTrK5oII3tnXOOc/oH2Z1HKXcVkiAHz+8dgT7T9bwypbjVsdxKVroTtDeYfjJin0kRQbzbb28X6mLdu2oAUxJj+H/PsrjTL2eIP2SFroTLNt6nIOnavnhtSMIDtA550pdLBHhp3OzqG1q4zcf5Vkdx2VooTtYdUMrv1mVx6S0aGaPTLA6jlIeY1hCGHdOGcQrW47r4l1dtNAd7MnVh6lubOXHX8vUE6FK2dl3rxxKdEgAP1mxT68gRQvdofJLa3lh41Hm56ToOudKOUBEsD+PzBrOtmNneHtHidVxLKeF7iDGGH723gGCA3x56KqhVsdRymPdPCGZMQMjeeLDgzS0tFkdx1Ja6A7yWV4pnx8q47tXDiWmX6DVcZTyWD4+wmPXjuB0TTN/WVdodRxLaaE7QGt7Bz9/7wCD40K5c8ogq+Mo5fEmpkZzTVZ/lqw9Qllts9VxLGNToYvILBHJE5F8EXn0PNtNFJF2EbnZfhHdz6tbjlNYXs8Prx2hN3xWykkemTWc5rYOfv/JIaujWKbXthERX+BpYDaQCSwQkcxzbPcEsMreId1JXXMbT60+zOT0aGYOi7c6jlJeIz2uH7dNSmHZ1iLyS2utjmMJWw4fc4B8Y0yBMaYFWAbM62G7bwNvAqV2zOd2nltXQHldC4/OHqHTFJVysgevyCDE35dffeCdqzHaUuhJQFG3x8Vdz/2TiCQBNwBLzveFRGShiOSKSG5ZWVlfs7q8stpm/vx5AXNGJTB2YKTVcZTyOjH9AvnmzMF8cqCUjUcqrI7jdLYUek+HmWfP4P898Igxpv18X8gYs9QYk22MyY6Li7Mxovv4w6eHaWrr4OGrh1kdRSmvdc+0NBIjgvjlygN0eNlqjLYUejEwsNvjZODse0BlA8tE5ChwM/CMiFxvj4Du4mh5Pa9sPs6CnIGkx/WzOo5SXivI35eHrxnGnpJq3ttz0uo4TmVLoW8FMkQkTUQCgPnAiu4bGGPSjDGpxphU4A3gW8aYd+wd1pX95qM8/H19ePAKXU1RKatdPzaJYf3D+P3Hh2hr77A6jtP0WujGmDZgMZ2zVw4Ay40x+0RkkYgscnRAd7CrqIr3dp/k/ulpxIcFWR1HKa/n4yN876qhFJTXe9WSAH62bGSMWQmsPOu5Hk+AGmPuuvhY7uU3H+URHRrA/ZemWx1FKdXlmqz+jEwK58nVh5k3NokAP8+/JsTz99DBco9Wsu5wOYsuSycsyN/qOEqpLiLCQ1cPo/hMI8tzi3r/Ax5AC/0i/e6TQ8T2C+D2yXqJv1KuZsbQOCYMiuqcgdZ63kl4HkEL/SJsKaxkfX4Fiy4bTEiATaNXSiknEhEevnoYp2uaeXmz599/VAv9Ivzu40PE9gvktkl6dK6Uq5oyOIZpQ2J4dk0+9c2evbyuFvoF2lRQwcaCCr45Y7DeJ1QpF/cfVw2jvK6Fv288anUUh9JCv0C/+/gQ8WGB3DYpxeooSqleTBgUxcxhcfxpbQF1HnyUroV+ATYcKWdzYSXfnDGYIH89OlfKHTx4RQbVja28vOmY1VEcRgu9j4wx/P7jw/QPD2RBjh6dK+UuxqVEMW1IDH9eV+ixM1600PtoY0EFW45W8sDMIXp0rpSbWTwzg/K6Zo+dl66F3kfPrjlCbL9Avp49sPeNlVIuZXJ6NBMGRfGntQW0euAaL1rofbC3pJp1h8u595I0PTpXyg2JCItnDqGkqtEj13jRQu+DZ9ceISzQj9sm69i5Uu5qxrA4shLDeXbNEdo9bL10LXQbFZbX88Gek9w+ZRDhumaLUm5LRHhg5hAKy+tZ6WHrpWuh22jp50fw8/Xh7mmpVkdRSl2kWVkJDI4L5enP8jHGc47StdBtcLqmiTe3lXDLhGRd71wpD+Dj03mUfvBULasPeM597bXQbfD8F4W0dXSwUNc7V8pjzB2TSFJkMEvXFVgdxW600HtR3dDKS5uOcd3oRAbFhFodRyllJ18OoW4prGR3cZXVcexCC70XL20+Rn1LO4suG2x1FKWUnd06cSBhgX48t67Q6ih2oYV+Hs1t7fx1/VEuGxpHZmK41XGUUnYWFuTP/JyBvL/nJCeqGq2Oc9G00M/jvV0nKa9r5r7paVZHUUo5yL9NTQXgbxuOWprDHrTQz8EYw/PrC8mI78clQ2KtjqOUcpDkqBBmj0zg1c3H3X5pXS30c9h69Az7TtRw97Q0RMTqOEopB7pvejq1zW0s3+rei3bZVOgiMktE8kQkX0Qe7eH1eSKyW0R2ikiuiFxi/6jO9fwXhUSG+HPDuCSroyilHGzswEgmpkbx/PpC2tx40a5eC11EfIGngdlAJrBARDLP2mw1MMYYMxa4B3jOzjmdqqiygY/2n2JBToreXk4pL3HvJekUn2nko/2nrY5ywWw5Qs8B8o0xBcaYFmAZMK/7BsaYOvP/r58NBdz6WtoXNh5FRLhjst78WSlvcVVmfwbFhPBnN77QyJZCTwK6DywVdz33L0TkBhE5CLxP51H6V4jIwq4hmdyysrILyetw9c1tLNtaxOyRCSRGBlsdRynlJL4+wt1TU9lxvIqdRVVWx7kgthR6T2cEv3IEbox52xgzHLge+HlPX8gYs9QYk22MyY6Li+tTUGd5c3sxtU1t3D1Npyoq5W1umpBMaIAvL2w8anWUC2JLoRcD3W/PkwycONfGxpjPgcEi4nZz/To6DH9bf5QxAyMZnxJpdRyllJOFBflz4/hk3tt9ksr6Fqvj9Jkthb4VyBCRNBEJAOYDK7pvICJDpGtun4iMBwKACnuHdbS1h8soKK/nnmmpOlVRKS91x5RBtLR18JobTmHstdCNMW3AYmAVcABYbozZJyKLRGRR12Y3AXtFZCedM2JuNW64yPDLm44R2y+Q2SMHWB1FKWWRof3DmJwezUubjrndHY1smodujFlpjBlqjBlsjPlF13NLjDFLuj5/whiTZYwZa4yZYoz5wpGhHaGkqpFPD5Yyf+JAAvz0eiulvNmdU1IpqWrks4PutVa6NleXZVuOY4D5OQN73VYp5dmuyuxP//BAXth0zOoofaKFDrS2d7BsaxEzh8WTHBVidRyllMX8fX24bdIgPj9UxtHyeqvj2EwLHfhk/2nKapu5bVKK1VGUUi7i1okD8fURXst1n5OjWujAy5uPkxQZzIxh8VZHUUq5iP7hQVw+PJ7Xc4tpdZP1Xby+0AvL6/kiv5wFOZ0/jZVS6ksLcgZSXtfM6gPusb6L1xf6si3H8fURvp6tJ0OVUv/qsqHxDIgI4pUt7jHs4tWF3trewZvbi7l8eDzx4UFWx1FKuRhfH+GW7IGsO1xGUWWD1XF65dWF/tnBUsrrWrhVj86VUudw68TOfljuBidHvbrQl+cWERcWyIxhrrlQmFLKekmRwVw2NI7luUUuf/MLry300pomPssr46bxyfj5eu1fg1LKBvMnpnC6ppnPD7vmst9f8tome3N7Ce0dhq9nJ1sdRSnl4i4fHk90aABvbiuxOsp5eWWhG2N4PbeIialRpMf1szqOUsrFBfj5MHdMIh/vP01Vg+suq+uVhZ577AwF5fU6VVEpZbObJyTT0t7BP3ad83YQlvPKQn8jt5jQAF/mjNJlcpVStslKDGd4QhhvbHfdYRevK/Sm1nZW7jnJrJEDCA30szqOUspNiAg3T0hmV1EV+aW1VsfpkdcV+uoDpdQ2t3HDuK/c51oppc5r3tgkfH2EN1z05KjXFfrbO4rpHx7IlMExVkdRSrmZuLBAZg6L4+0dxS55NyOvKvTK+hbW5JVxfddPWaWU6qubxidzuqaZ9fnlVkf5Cq8q9Pd2n6Ctw3C9DrcopS7QzOHxhAX58e5O15vt4lWF/vaOEoYnhDFiQLjVUZRSbirI35dZWQms2neKptZ2q+P8C68p9MLyenYcr+LG8Xp0rpS6OPPGJlHX3OZyN5H2mkJ/Z0cJIjB3jBa6UuriTBkcQ2y/QJcbdrGp0EVklojkiUi+iDzaw+u3icjuro8NIjLG/lEvnDGGf+w+weS0GBIidN1zpdTF8fURrhs9gE/zSqlparU6zj/1Wugi4gs8DcwGMoEFIpJ51maFwGXGmNHAz4Gl9g56MQ6eqqWgrJ7rxuiVoUop+5g3NpGWtg5W7T1ldZR/suUIPQfIN8YUGGNagGXAvO4bGGM2GGPOdD3cBLjUEobv7T6Br48wKyvB6ihKKQ8xdmAkKdEhrHChtV1sKfQkoPutOoq7njuXe4EPenpBRBaKSK6I5JaVOWddYWMM7+0+ydTBMcT0C3TKeyqlPJ+IMHdMIuvzyymtbbI6DmBbofd0BU6Pl0iJyEw6C/2Rnl43xiw1xmQbY7Lj4pxzl6C9JTUcq2jgutE63KKUsq+5YxPpMPChiwy72FLoxUD3dWaTga/8jiEio4HngHnGmAr7xLt47+05gZ+PcI0Otyil7Gxo/zAGx4XywR73KfStQIaIpIlIADAfWNF9AxFJAd4C7jDGHLJ/zAtjjOH93Se5JCOWyJAAq+MopTzQnFED2FxYQUVds9VRei90Y0wbsBhYBRwAlhtj9onIIhFZ1LXZj4EY4BkR2SkiuQ5L3Ac7i6ooPtPIdaMTrY6ilPJQs0Ym0GHgo/2nrY6CTQuCG2NWAivPem5Jt8/vA+6zb7SL9/7ukwT4+nBVZn+royilPFTmgHAGxYTwwd5TLMhJsTSLx14paoxh1f5TTBsSQ0Swv9VxlFIeSkSYPXIAG/LLqW6w9iIjjy30g6dqKaps1JOhSimHmz0ygbYOw8cHrB128dhCX7XvFCJwxQgdblFKOdbo5AiSIoP5cO9JS3N4bKF/tO80E1KiiAvTi4mUUo4lIswamcDnh8qptXBtF48s9KLKBvafrOHqLD06V0o5x+yRCbS0d/CphUvqemShf9w1fejqTB0/V0o5x/iUKGJCA1h9QAvdrj7af4ph/cNIjQ21OopSykv4+Agzh8ezJq+U1vYOazJY8q4OVFnfwpbCSh1uUUo53ZUj4qlpaiP36JneN3YAjyv01QdO02F0uEUp5XzTM+II8PVhtUXTFz2u0D/ef5oBEUGMTNIbQSulnCs00I/Jg2NYbdGJUY8q9Ja2Dtbnl3P58HhEelr1VymlHOvKEfEUltdzpKzO6e/tUYWee7SS+pZ2ZgyLtzqKUspLXT68s3+sGHbxqEL/LK+UAF8fpg6OsTqKUspLJUeFMDwhjE8smL7oUYW+Jq+MnLRoQgNtWkRSKaUc4ooR8Ww7doaqhhanvq/HFHrxmQYOl9YxY5hzbm2nlFLncsWI/rR3GNbkOefeyV/ymEL/8i9Ox8+VUlYbmxxJVIg/nx/WQr8ga/JKSY4KZnCcXh2qlLKWj48wdUgsXxwuxxjjvPd12js5UHNbO+vzK5g5TKcrKqVcw6UZsZTWNnPotPOmL3pEoW8prKSxtV3Hz5VSLuOSjM4+WufEYRePKPQ1eWUE+PkwRacrKqVcRFJkMOlxoaw7XO609/SIQl93uIxJadGEBOh0RaWU67g0I47NhRU0tbY75f3cvtDLusaopg6OtTqKUkr9i+kZsTS1drDtmHNWX7Sp0EVklojkiUi+iDzaw+vDRWSjiDSLyMP2j3lumwoqAHS4RSnlcialx+DnI04bdum10EXEF3gamA1kAgtEJPOszSqBB4Hf2D1hLzYcqSAs0I+Ribq6olLKtfQL9GP8oCinnRi15Qg9B8g3xhQYY1qAZcC87hsYY0qNMVsBp98ddVNBBTlp0fj5uv3okVLKA12aEcu+EzWU1zU7/L1sacEkoKjb4+Ku5/pMRBaKSK6I5JaVXfxPrJPVjRSW1+twi1LKZX05fXF9vuOHXWwp9J6u1LmgS5+MMUuNMdnGmOy4uIufM77xiI6fK6Vc26ikCMKC/P7ZV45kS6EXAwO7PU4GTjgmTt9sOFJBZIg/IxJ0/Fwp5Zp8fYRJadFsLqx0+HvZUuhbgQwRSRORAGA+sMKxsXpnjGHjkQomp8Xg46OX+yulXNfk9BgKy+s5XdPk0PfptdCNMW3AYmAVcABYbozZJyKLRGQRgIgkiEgx8B/AYyJSLCIOPWwuqmykpKqRqUN0uEUp5dompXX21JfTrB3FpksrjTErgZVnPbek2+en6ByKcZqNBZ0nGPTuREopV5eZGE5YoB+bCyuZN/aC5pTYxG3n+m04UkFcWCCD4/pZHUUppc7L10eYmBbt8CN0ty30LYWVTEqL1uVylVJuYVJaNAVl9Q6dj+6WhV5S1cjJ6iayB0VZHUUppWySndrZV45c18UtC/3Lv5Ds1GiLkyillG2yEiMI8PVhuxb6v9p2tJKQAF+GJ4RZHUUppWwS5O/LqOQIcrXQ/9W242cYOzBS129RSrmVCYOi2FNcTXObY9ZHd7tGrG9u48DJWh0/V0q5nQmDomhp72BvSbVDvr7bFfquoiraOwzjtdCVUm5mfIpjT4y6XaH7+/kwc1gc41K00JVS7iUuLJB5YxOJDwtyyNcXYy5o4cSLlp2dbXJzcy15b6WUclciss0Yk93Ta253hK6UUqpnWuhKKeUhtNCVUspDaKErpZSH0EJXSikPoYWulFIeQgtdKaU8hBa6Ukp5CMsuLBKRMuBYH/5ILFDuoDiuzFv3G7x333W/vUtf93uQMSaupxcsK/S+EpHcc10d5cm8db/Be/dd99u72HO/dchFKaU8hBa6Ukp5CHcq9KVWB7CIt+43eO++6357F7vtt9uMoSullDo/dzpCV0opdR5a6Eop5SFcrtBFZJaI5IlIvog82sPrIiJPdb2+W0TGW5HT3mzY79u69ne3iGwQkTFW5LS33va723YTRaRdRG52Zj5HsWW/RWSGiOwUkX0istbZGR3Bhn/nESLyDxHZ1bXfd1uR095E5HkRKRWRved43T69ZoxxmQ/AFzgCpAMBwC4g86xt5gAfAAJMBjZbndtJ+z0ViOr6fLa37He37T4FVgI3W53bSd/vSGA/kNL1ON7q3E7a7x8AT3R9HgdUAgFWZ7fDvl8KjAf2nuN1u/Saqx2h5wD5xpgCY0wLsAyYd9Y284AXTKdNQKSIDHB2UDvrdb+NMRuMMV/eWXYTkOzkjI5gy/cb4NvAm0CpM8M5kC37/Q3gLWPMcQBjjCfsuy37bYAwERGgH52F3ubcmPZnjPmczn05F7v0mqsVehJQ1O1xcddzfd3G3fR1n+6l86e5u+t1v0UkCbgBWOLEXI5my/d7KBAlImtEZJuI3Om0dI5jy37/ERgBnAD2AN8xxnQ4J56l7NJrfnaLYx/Sw3Nnz6u0ZRt3Y/M+ichMOgv9Eocmcg5b9vv3wCPGmPbOgzaPYMt++wETgCuAYGCjiGwyxhxydDgHsmW/rwF2ApcDg4GPRWSdMabGwdmsZpdec7VCLwYGdnucTOdP6r5u425s2icRGQ08B8w2xlQ4KZsj2bLf2cCyrjKPBeaISJsx5h2nJHQMW/+dlxtj6oF6EfkcGAO4c6Hbst93A78ynQPL+SJSCAwHtjgnomXs0muuNuSyFcgQkTQRCQDmAyvO2mYFcGfXWeHJQLUx5qSzg9pZr/stIinAW8Adbn6U1l2v+22MSTPGpBpjUoE3gG+5eZmDbf/O3wWmi4ifiIQAk4ADTs5pb7bs93E6fytBRPoDw4ACp6a0hl16zaWO0I0xbSKyGFhF5xnx540x+0RkUdfrS+ic6TAHyAca6PyJ7tZs3O8fAzHAM11Hq23GzVems3G/PY4t+22MOSAiHwK7gQ7gOWNMj1Pe3IWN3++fA38TkT10DkM8Yoxx+yV1ReRVYAYQKyLFwE8Af7Bvr+ml/0op5SFcbchFKaXUBdJCV0opD6GFrpRSHkILXSmlPIQWulJKeQgtdKWU8hBa6Eop5SH+HxcAmsYo1u8RAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(x, entropy(x))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "concerned-athletics",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "![title](attachment/11.png)\n",
    "\n",
    "To decline the information entroy by dividing sample"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "electronic-story",
   "metadata": {},
   "source": [
    "### Use Information Entroy to Optimize Classifition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "economic-culture",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn import datasets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "intellectual-relevance",
   "metadata": {},
   "outputs": [],
   "source": [
    "iris = datasets.load_iris()\n",
    "X = iris.data[:, 2:]\n",
    "y = iris.target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "metallic-floor",
   "metadata": {},
   "outputs": [],
   "source": [
    "def split(X, y, d, value):\n",
    "    index_a = (X[:, d] <= value)\n",
    "    index_b = (X[:, d] > value)\n",
    "    return X[index_a], X[index_b], y[index_a], y[index_b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "hydraulic-execution",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "from math import log"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "attractive-thread",
   "metadata": {},
   "outputs": [],
   "source": [
    "def entropy(y):\n",
    "    counter = Counter(y)\n",
    "    res = 0.0\n",
    "    for num in counter.values():\n",
    "        p = num / len(y)\n",
    "        res += -p * log(p)\n",
    "    return res\n",
    "\n",
    "def try_split(X, y):\n",
    "\n",
    "    best_entropy = float('inf')\n",
    "    best_d, best_v = -1, -1\n",
    "\n",
    "    for d in range(X.shape[1]):\n",
    "        sorted_index = np.argsort(X[:,d])\n",
    "        for i in range(1, len(X)):\n",
    "            if X[sorted_index[i-1], d] != X[sorted_index[i], d]:\n",
    "                v = (X[sorted_index[i-1], d] + X[sorted_index[i], d]) / 2\n",
    "                x_l, x_r, y_l, y_r = split(X, y, d, v)\n",
    "                e = entropy(y_l) + entropy(y_r)\n",
    "                if e < best_entropy:\n",
    "                    best_entropy, best_d, best_v = e, d, v\n",
    "                    \n",
    "    return best_entropy, best_d, best_v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "finnish-burton",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "best_entropy = 0.6931471805599453\n",
      "best_d = 0\n",
      "best_v = 2.45\n"
     ]
    }
   ],
   "source": [
    "best_entropy, best_d, best_v = try_split(X, y)\n",
    "\n",
    "\n",
    "print('best_entropy =', best_entropy)\n",
    "print('best_d =', best_d)\n",
    "print('best_v =', best_v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "finnish-princeton",
   "metadata": {},
   "outputs": [],
   "source": [
    "x1_l, x1_r, y1_l, y1_r = split(X, y, best_d, best_v)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acceptable-macedonia",
   "metadata": {},
   "source": [
    "判断数据集的信息熵是否为 0，如果等于 0，说明该数据集中只有一种类型的样本，不需要再进行划分；反之则需要再次进行划分；\n",
    "划分方法与第一次划分的过程一样；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "minor-flight",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "entropy(y1_l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "thousand-radiation",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6931471805599453"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "entropy(y1_r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "rocky-frontier",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "best_entropy2 = 0.4132278899361904\n",
      "best_d2 = 1\n",
      "best_v2 = 1.75\n"
     ]
    }
   ],
   "source": [
    "best_entropy2, best_d2, best_v2 = try_split(x1_r, y1_r)\n",
    "\n",
    "\n",
    "print('best_entropy2 =', best_entropy2)\n",
    "print('best_d2 =', best_d2)\n",
    "print('best_v2 =', best_v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "opposite-bacon",
   "metadata": {},
   "outputs": [],
   "source": [
    "x2_l, x2_r, y2_l, y2_r = split(x1_r, y1_r, best_d2, best_v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "selective-delta",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.30849545083110386"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "entropy(y2_l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "monthly-milton",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.10473243910508653"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "entropy(y2_r)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "saved-guarantee",
   "metadata": {},
   "source": [
    "## Gina Coefficient\n",
    "$$G = 1-\\sum ^k_{i=1}p_i^2$$\n",
    "\n",
    "If and only a two-dimension classification:\n",
    "\n",
    "$$G = 1-x^2-(1-x)^2$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "celtic-lightweight",
   "metadata": {},
   "source": [
    "## Use Gini Coefficient in Sklearn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "necessary-ghost",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "DecisionTreeClassifier(max_depth=2)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from sklearn.tree import DecisionTreeClassifier\n",
    "\n",
    "dt_clf = DecisionTreeClassifier(max_depth=2, criterion='gini')\n",
    "dt_clf.fit(X, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "elegant-mentor",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_decision_boundary(model, axis):\n",
    "    \n",
    "    x0, x1 = np.meshgrid(\n",
    "        np.linspace(axis[0], axis[1], int((axis[1]-axis[0])*100)).reshape(-1,1),\n",
    "        np.linspace(axis[2], axis[3], int((axis[3]-axis[2])*100)).reshape(-1,1)\n",
    "    )\n",
    "    X_new = np.c_[x0.ravel(), x1.ravel()]\n",
    "    \n",
    "    y_predict = model.predict(X_new)\n",
    "    zz = y_predict.reshape(x0.shape)\n",
    "    \n",
    "    from matplotlib.colors import ListedColormap\n",
    "    custom_cmap = ListedColormap(['#EF9A9A','#FFF59D','#90CAF9'])\n",
    "    \n",
    "    plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "marine-portfolio",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/yasmine/anaconda3/lib/python3.7/site-packages/ipykernel_launcher.py:15: UserWarning: The following kwargs were not used by contour: 'linewidth'\n",
      "  from ipykernel import kernelapp as app\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD8CAYAAABn919SAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAb5UlEQVR4nO3dfXBd9Z3f8fdXD7axLCOobWywgWTiTSC04UE1JG4zzG6WYptZMmnoOJ0mk8zOqkmBgTYznRJ2eGrS7F9p3ZDG4wLdMMvChJhk6WI27E6zy0PWAduxN4DphJKlVi0swMiW/ASSvv3jHklXR+dK55577j0P9/Oa0UTnd3/n3C/K6Oujcz73d8zdERGR4uvIugAREUmHGrqISEmooYuIlIQauohISaihi4iUhBq6iEhJLNjQzWyJmb1oZgfM7BUzuzdijpnZfzWz183s78zsyuaUKyIitXTFmHMG+G13HzOzbuB5M3va3XdXzdkErA++rga+H/yviIi0yIJn6F4xFmx2B1/hTyPdCDwczN0N9JnZmnRLFRGR+cQ5Q8fMOoG9wEeA77n7L0JTLgAOVW0PBmNDoeMMAAMAi87queq8iz6asGwRkfZ06LV977j7yqjXYjV0d58ALjezPuDHZnaZu79cNcWidos4zg5gB8CFl1zlX3/4b+O8vYiIBG7fsPjNWq/VlXJx9xHgr4HrQy8NAuuqttcCh+s5toiINCZOymVlcGaOmZ0FfAZ4LTTtSeBLQdrlGuCYuw8hIiItE+eSyxrgB8F19A7gh+7+52b2VQB33w7sAjYDrwMnga80qV4REalhwYbu7n8HXBExvr3qewduTrc0ERGphz4pKiJSEmroIiIloYYuIlISaugiIiWhhi4iUhJq6CIiJaGGLiJSEmroIiIloYYuIlISaugiIiWhhi4iUhJq6CIiJaGGLiJSEmroIiIloYYuIlISaugiIiWhhi4iUhJq6CIiJaGGLiJSEmroIiIloYYuIlISaugiIiWhhi4iUhJq6CIiJaGGLiJSEmroIiIloYYuIlISCzZ0M1tnZj8zs4Nm9oqZ3RYx51ozO2Zm+4Ovu5pTroiI1NIVY8448HV332dmvcBeM/tLd381NO85d78h/RJFpEheH3maPcP3MzZ+hGVd59G/6hY+0rcp0X5AomO1qwUbursPAUPB96NmdhC4AAg3dBFpc6+PPM1zQ99kwk8DMDb+Fs8NfRNg3kYctd/fHL4HM2PSP6jrWO2srmvoZnYxcAXwi4iXP2lmB8zsaTP7eBrFiUix7Bm+f7opT5nw0+wZvr/u/Zzx6WZez7HaWZxLLgCY2TJgJ3C7ux8PvbwPuMjdx8xsM/ATYH3EMQaAAYBzVl+YtGYRyamx8SN1jcd9PencdhPrDN3Muqk080fc/Ynw6+5+3N3Hgu93Ad1mtiJi3g5373f3/mV9c14WkYJb1nVeXeNxX086t93ESbkY8CBw0N2/U2PO6mAeZrYhOO67aRYqIvnXv+oWOm3JrLFOWzJ9g7Oe/YwuOqy77mO1sziXXDYCXwR+ZWb7g7FvABcCuPt24PPA18xsHDgFbHV3T79cEcmzqZuV9SZTau2X5FjtzLLquxdecpV//eG/zeS9RdpF0ghhXC8c/javjTyBM4nRwcf6PsfG8+9I7fgy1+0bFu919/6o12LfFBWRYkkaIYzrhcPf5uDIj6a3ncnpbTX1bOij/yIllTRCGNdrI3PyEfOOS/OpoYuUVNIIYVzOZF3j0nxq6CIllTRCGJfVaB+1xqX59JMXKamkEcK4Ptb3ubrGpfl0U1SkpJJGCOOauvGplEt+qKGLtJm4qxpGjYX/Mdh4/h1zGnicqGTcOGWzY5dJ5bUu5dBFSiocW4TKpy+rVzAE6LBu3B1nfN55nbaEf7rmD+taNTFqvzhz6pnXalnXNV8OXdfQRUoq7gqGk/7BrGZea17SVRPD+8WNUzY7dplUXusCNXSR0mrGqoRJV02sHo8bp2x27DKpvNYFaugipdWMVQmTrppYPR43Ttns2GVSea0L1NBFSivuCoYd1o2F8hFJVzqME5WMG6dsduwyqbzWBUq5iJRWPSsYxh1Lumpi9X5x45TNjl0mlde6QCkXEWlA0eOHUfJeq1ZbFJHUxV3NsdmrPqapSLVG0TV0EUmk6PHDKEWqNYoauogkUvT4YZQi1RpFDV1EEil6/DBKkWqNooYuIokUPX4YpUi1RtFNURFJpOjxwyhFqjWKYosiIgWi2KKI1C2cx1637J9waOz5VD6QlJesd17qSIvO0EVkjqglYsPiLsWbdPncZstLHfXS8rkiUpeoPHZY3KV4ky6f22x5qSNNaugiMkfauesky+c2W17qSJMauojMkXbuOsnyuc2WlzrSpIYuInNE5bHD4i7Fm3T53GbLSx1pUspFROaIymOnlXLJS9Y7L3WkacGUi5mtAx4GVgOTwA533xaaY8A2YDNwEviyu++b77hKuYg0ppmxwqJrJI6Y9yjjfCmXOA19DbDG3feZWS+wF/isu79aNWczcCuVhn41sM3dr57vuGroIsnFiRVGRQijooZFiOrVo5E4YhGijA3FFt19aOps291HgYPABaFpNwIPe8VuoC/4h0BEmiBOrDAqQhgVNSx6VC+skThi0aOMdd0UNbOLgSuAX4ReugA4VLU9yNymj5kNmNkeM9szNvJOnaWKyJRmxgqLrpE4YtGjjLEbupktA3YCt7v78fDLEbvMuZbj7jvcvd/d+5f1raivUhGZ1sxYYdE1EkcsepQxVkM3s24qzfwRd38iYsogsK5qey1wuPHyRCRKnFhhVIQwKmpY9KheWCNxxKJHGReMLQYJlgeBg+7+nRrTngRuMbPHqNwUPebuQ+mVKSLVmhkrLLpG4ohFjzLGyaFvBL4I/MrM9gdj3wAuBHD37cAuKgmX16nEFr+SeqUiMstH+jbNeRjzobHnZ805cnI/J8aHAefE+DBHTu5n4/l35Hb1w7CkdYV/NvVoZN+sLdjQ3f15oq+RV89x4Oa0ihKR+kQ9rf5vDt+NMzE9x5nk4MiPANh4/h3z7puHJ93nta4800f/RUogKm5X3cyrvTYy+zZYXqN6ea0rz9TQRUqgnlidMxlr36yjenmtK8/U0EVKoJ5YnYV+7fMa1ctrXXmmhi5SAlFxO6Mzcu7H+j634L55iOrlta4802qLIiVQK2535OR+Xht5AmcSo4OP9X1u1g3R+fbN+sZjXuvKMzV0kQJ4+dd/wIvv72WSyp/VGxZdxbGeD89p1lt/66k5+05l03u6VnHe0ssjjx8nqvfC4W/Peb/zll4eq+HGiR/WmhOngec1dtlqaugiOffyr/+A3e/vBaukhyehsv3BzArVUZHENGN/Lxz+9vTxq9/v4MhOplb5qHX8OHU0UqvijTN0DV0k516saubTwtuB6khimrG/cNRxxuwlm6KOH6eOdl4hMU1q6CI5N7nwlGnVkcQ0Y3/hqON8wsePU0c7r5CYJjV0kZyr55e0OpKYZuwvHHWcT/j4cepo5xUS06SGLpJzGxZdBeEni9V40lh1JDHN2F846jhj9qWfqOPHqaOdV0hMk26KiuTcZev/O8RMuVRHEtOM/U0dN0nKJU4d7bxCYpoWfKZos+iZoiIi9ZvvmaKZnaGvOutdbvv4n2T19iKZeOrNg2x7+QXeOjnK6qW93HbZRrZcdEk6B391Dzy7C46/B8vPgU9vhksjf++lwG6f5zVdchFpkafePMg9e/+K0xOVBzcPnRzlnr1/BdB4U391D/zFD2E8eAD08fcq26Cm3kZ0U1SkRba9/MJ0M59yemKcbS+/0PjBn90108ynjH9QGZe2oYYu0iJvnRyta7wux9+rb1xKSQ1dpEVWL+2ta7wuy8+pb1xKSQ1dpEVuu2wjSzpn37Za0tnFbZdtbPzgn94MXd2zx7q6K+PSNnRTVKRFpm58NiXlMnXjUymXtqaGLtJCW06cYMuhwzNN90Mn5k5KGj+8tH/uvJxEGZsa15RpaugirRInWphm/DAnUcamxjVlFl1DF2mVONHCNOOHOYkyNjWuKbOooYu0SpxoYZrxw5xEGZsa15RZ1NBFWiVOtDDN+GFOooxNjWvKLGroIq0SJ1qYZvwwJ1HGpsY1ZRbdFBVplTjRwjTjhzmJMjY1rimzLNjQzewh4AZg2N0vi3j9WuDPgN8EQ0+4+30p1iiSL41EAX/2P+HE8cr3x9+DZ3bOPVZczzwOB3aDT4J18NQl/5BtNj6radLTw7Z15/PWyd7KWE8PW+r/L27YlosuUQNvgThn6H8M3A88PM+c59z9hlQqEsmzRqKA37t7pplPef905WvqWE89Ch0GExPzH/+Zx2H/z6c3n1q6hHtOvMvpjspV1KGTo/zhSz/FzPhgcnJ6THHBclvwGrq7PwscbUEtIvnXSBQw3Myj+ORMM5/v+Ad2z9rcdk7fdDOf3s19uplPUVyw3NK6KfpJMztgZk+b2cdrTTKzATPbY2Z73n5nLKW3FmmhrKKA4eP77Eb9Vldn7EMpLlheaTT0fcBF7v4J4LvAT2pNdPcd7t7v7v0rVyxL4a1FWiyrKGD4+Db7V3f1eOisfh6KC5ZXww3d3Y+7+1jw/S6g28xWNFyZSB41EgXsWb7wHOuAztDZdtTxP3HNrM3b3hthSejySpcZ3aHLMIoLllvDDd3MVpuZBd9vCI75bqPHFcmlS/vh+n8xc8a8/JzKdpyUy833zm3qi5bMPtaWL8CmrQsf/7qb4PJPTZ+pbzl5mnt6/gFrlvZiwJqlvXzzH/8z/mP/dbPG7rnqM7ohWmJxYouPAtcCK8xsELgb6AZw9+3A54Gvmdk4cArY6u7etIpF0pLmqoZRQrFCPnFNpalH1VBt8Dcweqzy/eixyjbMrfW6mypfgS3BV1gzG7hWUcwXy6r39l95se95/q5M3ltkTvwQKpc24p5tLyQUK5x2+admmnBUDdYx54Zn5HiatSYUXkURKpd09FdAc1nP7+9198j/4/XRf2lPzV6JMBQrjByPqiGqmUeN5+AB0FpFMX/U0KU9NTt+GKcxN/peGT8AWqso5o8aurSnZscPrcavVvV4o++V8QOgtYpi/qihS3tq9kqEoVhh5HhUDXH+IYBcPABaqyjmj1ZblPbU7JUIp258hlMuVamUmjUM/mbufms/lPmqiWFaRTF/lHIRESmQ+VIuOkOXYkv7qfaP/Tf4v7+e2e5ZDifHZp8tw9wz6KixqLNqmD324UvgjYO5OvOW4tIZuhRX2lnycDNvlBlU/351dsKk107AQC7y5ZJvyqFLOaWdJU+zmcPsZg6VZXHna+aQi3y5FJcauhRXTp5qn7qi1y+ZUUOX4srJU+1TV/T6JTNq6FJcaWfJL1zfeE3VKouQzujsrJ0zn5KDfLkUlxq6FFcjS9lG2fpv5jb1nuUzTdg6KotrVS1bO+/Yln85u7ZNWyvL41aPXf6p9OqXtqfYohRb3KVso0RFHv/RBhh5Z/4Y4at7ZqKGvWdX4omX9s/+0NDUvCT1ph3FlLahhi7tKRx5PP4ePPUodNjMQ5qPv1eZAzMNNWq/8Jx65sWpK85+IuiSi7SrWkvXToSezRmOEcaNSiaNVDZ7WV8pNTV0aU/1RAOr58aNSiaNVJY1iiktoYYu7ameaGD13LhRyaSRyrJGMaUl1NClPdVaurazc/ZYOEYYNyqZNFLZ7GV9pdR0U1TaU62la6PGqm9Gxl12N+nyvM1e1ldKTQ1d0pXXyF1UXVHixArjRiWTRiobiWJKW1NDl/TkNXIXVdfTj81e+TAvtYo0QNfQJT15jdxF1RW18mEeahVpgBq6pCevkbukEUWRglFDl/TkNXKXNKIoUjBq6JKevEbuouqKWvkwD7WKNEA3RSU9eY3cJY0oihTMgg3dzB4CbgCG3f2yiNcN2AZsBk4CX3b3fWkXKgWRNHL3zONzH7IcXr0w7rxa0cmouqJWUtRDnKWg4lxy+WPg+nle3wSsD74GgO83Xpa0lWceh/0/n0md+GRl+5nH6583FVGcurk5FUeMWso2LGrf/T9PdiyRDCzY0N39WeDoPFNuBB72it1An5mtSatAaQMHdscbjzOvkehk1L5hijZKjqVxU/QC4FDV9mAwNoeZDZjZHjPb8/Y7Yym8tZRCOA9eazzOvEaik3Eji4o2Sk6l0dAtYsyjJrr7Dnfvd/f+lSuWpfDWUgq1nrMZHo8zr5HoZNzIoqKNklNpNPRBYF3V9lrgcArHlXbxiWvijceZ10h0MmrfMEUbJcfSaOhPAl+yimuAY+4+lMJxpV1cd1P0Q5bD6ZU48xp5cHTUvnqIsxSIuUdeHZmZYPYocC2wAjgC3A10A7j79iC2eD+VJMxJ4CvuvmAMoP/Ki33P83c1VLyISLuxnt/f6+6RZxUL5tDd/QsLvO7AzQlrExGRlOij/yIiJaGGLiJSEmroIiIloYYuIlISaugiIiWhhi4iUhJq6CIiJaGGLiJSEmroIiIlkdkj6CaOwsgjE1m9vYhI6egMXUSkJNTQRURKQg1dRKQk1NBFREpCDV1EpCTU0EVESkINXUSkJNTQRURKQg1dRKQk1NBFREois4/+l8mu0bP47tFe3hrvZHXXBLeeO8rm3lNZlyUibUYNvUG7Rs/ivrfP5rRX/tgZGu/ivrfPBlBTF5GW0iWXBn33aO90M59y2jv47tHejCoSkXalht6gt8Y76xoXEWkWNfQGre6KXgK41riISLOooTfo1nNHWWKTs8aW2CS3njuaUUUi0q50U7RBUzc+lXIRkazFauhmdj2wDegEHnD3Pwq9fi3wZ8BvgqEn3P2+9MrMt829p9TARSRzCzZ0M+sEvgf8LjAIvGRmT7r7q6Gpz7n7DU2osZCUTReRVotzDX0D8Lq7v+Hu7wOPATc2t6xim8qmD4134dh0Nn3X6FlZlyYiJRanoV8AHKraHgzGwj5pZgfM7Gkz+3gq1RWUsukikoU419AtYsxD2/uAi9x9zMw2Az8B1s85kNkAMACw9txz66u0QJRNF5EsxDlDHwTWVW2vBQ5XT3D34+4+Fny/C+g2sxXhA7n7Dnfvd/f+Fb3lPVtVNl1EshCnob8ErDezD5nZImAr8GT1BDNbbWYWfL8hOO67aRdbFMqmi0gWFrzk4u7jZnYL8FMqscWH3P0VM/tq8Pp24PPA18xsHDgFbHX38GWZtqFsuohkIVYOPbiMsis0tr3q+/uB+9MtrbXixgwHBs/lxTOLp7c3LD7DZ88+NWffNN9TRCQOfVKU+EvgzjTzmfvEL55ZzEvDi/FgbGi8i7uH+3CccWofT8vuikjatJYL8WOG4WZeYdPNfMoH2HQzr3U8RRtFJG1q6LQuZlh9PEUbRSRtaui0LmZYfTxFG0UkbWroxI8Zblh8hrmfqXIsNNaN08X8x1O0UUTSpoZO5SbkXSuPsaZrHMNZ0zXOXSuPzbk5uWPt0aqmXvnasPgM31o1Mmvfe1eNcN+q+Y8X9z1FROJSyiXwy1PdHBnvxIEj45388lQ3Pzl2VmRE8dDRrumo4WfPPhW5fG6chbi07K6IpEkNHfjW8HIeH+1hKsEyCcE2LBRRjIoaKpIoIlnQJRdgZ1Uzn2GRY+GIYlTUUJFEEcmCGjqEbl/WLxw1VCRRRLKghk7jP4Rw1FCRRBHJgho68M97TxAVR4wTUYyKGiqSKCJZUEMH7lx1nJt6T9ARNPEOnJt6T8SKKEZFDRVJFJEslC7lEncFw28NL2fnaA+TVP5V62Fy+lr6JLD35CLenJj949l7ZhEHhhdxZjrl0sm9w2fzn9/u5W2fuT6+0ib4tysXPhvXaosikqZSNfS4ccGomOIoHVSnWt6Y6A6+mxmbCL6qx85A0Mxnxt72Tr4x3Dc9ptUWRaQVSnXJJW5csHZMMbyd3phWWxSRZitVQ48bF2w0ppiUVlsUkWYqVUOPGxfM6j9aqy2KSDOVqqHHjQvWjimGt9Mb02qLItJspWroceOCUTHFXiapjih+uPMDOqu2wenEWRwaW4yz0iZmja20Cf7TAvFGRRtFJG3mHj67bI0rLr7Yf3bnnZm8t4hIUZ0zMLDX3fujXitVbLGWpHnvcFa9cqmGOWN3rjrezPJFRGIpfUNPmveOs6Ru9ZiauohkrVTX0KMkzXvXs6TuzulGLyKSndI39KR573qy6lnl2kVEqpW+oSfNe9fzgyn9D1FECqH0vShp3rueJXWnbpaKiGSp9DdFp2581ptymbrJqZSLiBRFrIZuZtcD24BO4AF3/6PQ6xa8vhk4CXzZ3felXGtim3tPJfrAzp2rjkc2azVwEcmjBS+5mFkn8D1gE3Ap8AUzuzQ0bROwPvgaAL6fcp0iIrKAONfQNwCvu/sb7v4+8BhwY2jOjcDDXrEb6DOzNSnXKiIi84hzyeUC4FDV9iBwdYw5FwBD1ZPMbIDKGTzA2DkDA/+7rmrrswJ4p4nHbzbVn60i11/k2kH1L+SiWi/EaejhT9LA3KhHnDm4+w5gR4z3bJiZ7am13kERqP5sFbn+ItcOqr8RcS65DALrqrbXAocTzBERkSaK09BfAtab2YfMbBGwFXgyNOdJ4EtWcQ1wzN2HwgcSEZHmWfCSi7uPm9ktwE+pxBYfcvdXzOyrwevbgV1UIouvU4ktfqV5JcfWkks7TaT6s1Xk+otcO6j+xDJbD11ERNJV+o/+i4i0CzV0EZGSKF1DN7OHzGzYzF7OupYkzGydmf3MzA6a2StmdlvWNcVlZkvM7EUzOxDUfm/WNSVhZp1m9ksz+/Osa6mXmf29mf3KzPab2Z6s66mXmfWZ2Y/M7LXgd+CTWdcUl5l9NPi5T30dN7PbW1pD2a6hm9mngTEqn1y9LOt66hV8wnaNu+8zs15gL/BZd38149IWFKzp0+PuY2bWDTwP3BZ8ergwzOzfAf3Acne/Iet66mFmfw/0u3shP5hjZj8AnnP3B4JU3VJ3H8m4rLoFS6b8P+Bqd3+zVe9bujN0d38WOJp1HUm5+9DUwmbuPgocpPKp29wLln4YCza7g69CnTGY2VpgC/BA1rW0GzNbDnwaeBDA3d8vYjMP/A7wf1rZzKGEDb1MzOxi4ArgFxmXEltwuWI/MAz8pbsXpvbAfwH+PcV9EJUDz5jZ3mCpjSL5MPA28D+CS14PmFlRn++4FXi01W+qhp5TZrYM2Anc7u6FWa/X3Sfc/XIqnxbeYGaFuexlZjcAw+6+N+taGrDR3a+ksgLqzcElyKLoAq4Evu/uVwAngP+QbUn1Cy4V/R7weKvfWw09h4LrzzuBR9z9iazrSSL4U/mvgeuzraQuG4HfC65DPwb8tpn9SbYl1cfdDwf/Owz8mMpqqUUxCAxW/VX3IyoNvmg2Afvc/Uir31gNPWeCG4sPAgfd/TtZ11MPM1tpZn3B92cBnwFey7SoOrj7He6+1t0vpvIn8/9y93+VcVmxmVlPcCOd4FLFdUBh0l7u/hZwyMw+Ggz9DpD7MECEL5DB5RYo4SPozOxR4FpghZkNAne7+4PZVlWXjcAXgV8F16IBvuHuu7IrKbY1wA+CO/wdwA/dvXDRvwI7D/hx5ZyALuBP3f0vsi2pbrcCjwSXLd4gH8uIxGZmS4HfBf51Ju9fttiiiEi70iUXEZGSUEMXESkJNXQRkZJQQxcRKQk1dBGRklBDFxEpCTV0EZGS+P/1uS4DWpUuSQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3])\n",
    "plt.scatter(X[y==0, 0], X[y==0, 1])\n",
    "plt.scatter(X[y==1, 0], X[y==1, 1])\n",
    "plt.scatter(X[y==2, 0], X[y==2, 1])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "defensive-stations",
   "metadata": {},
   "source": [
    "### Use Gini Coefficient to Optimize Classifition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "structural-explorer",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "from math import log"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "cutting-hobby",
   "metadata": {},
   "outputs": [],
   "source": [
    "def split(X, y, d, value):\n",
    "    index_a = (X[:, d] <= value)\n",
    "    index_b = (X[:, d] > value)\n",
    "    return X[index_a], X[index_b], y[index_a], y[index_b]\n",
    "\n",
    "def gini(y):\n",
    "    counter = Counter(y)\n",
    "    res = 1.0\n",
    "    for num in counter.values():\n",
    "        p = num / len(y)\n",
    "        res += -p**2\n",
    "    return res\n",
    "\n",
    "def try_split(X, y):\n",
    "    \n",
    "    best_g = float('inf')\n",
    "    best_d, best_v = -1, -1\n",
    "    for d in range(X.shape[1]):\n",
    "        sorted_index = np.argsort(X[:,d])\n",
    "        for i in range(1, len(X)):\n",
    "            if X[sorted_index[i-1], d] != X[sorted_index[i], d]:\n",
    "                v = (X[sorted_index[i-1], d] + X[sorted_index[i], d]) / 2\n",
    "                x_l, x_r, y_l, y_r = split(X, y, d, v)\n",
    "                g = gini(y_l) + gini(y_r)\n",
    "                if g < best_g:\n",
    "                    best_g, best_d, best_v = g, d, v\n",
    "                    \n",
    "    return best_g, best_d, best_v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "adequate-heather",
   "metadata": {},
   "outputs": [],
   "source": [
    "best_g, best_d, best_v = try_split(X, y)\n",
    "X1_l, X1_r, y1_l, y1_r = split(X, y, best_d, best_v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "exceptional-bullet",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "best_g = 0.5\n",
      "best_d = 0\n",
      "best_v = 2.45\n"
     ]
    }
   ],
   "source": [
    "best_g, best_d, best_v = try_split(X, y)\n",
    "\n",
    "print('best_g =', best_g)\n",
    "print('best_d =', best_d)\n",
    "print('best_v =', best_v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "critical-burns",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gini(y1_l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "distant-review",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gini(y1_r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "german-catholic",
   "metadata": {},
   "outputs": [],
   "source": [
    "best_g2, best_d2, best_v2 = try_split(X1_r, y1_r)\n",
    "X2_l, X2_r, y2_l, y2_r = split(X1_r, y1_r, best_d2, best_v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "turned-marsh",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "best_g2 = 0.2105714900645938\n",
      "best_d2 = 1\n",
      "best_v2 = 1.75\n"
     ]
    }
   ],
   "source": [
    "print('best_g2 =', best_g2)\n",
    "print('best_d2 =', best_d2)\n",
    "print('best_v2 =', best_v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "incorporated-ratio",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.1680384087791495"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gini(y2_l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "bronze-coating",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.04253308128544431"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gini(y2_r)"
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}