31:T6e5,> In the initial state, there are **5** orange dots and **5** blue dots:
> ${tex.block` \text { Original-Entropy } = - \frac{5}{10} log_2 \frac{5}{10} - \frac{5}{10} log_2 \frac{5}{10} = 1 \\~\\ `} > When the data is separated at point ${sep}:
> * Class ${sep}- has ${seperator.totalMinus} dots in total, **${seperator.minus1}** orange and **${seperator.minus0}** blue. > * Class ${sep}+ has ${seperator.totalPlus} dots in total, **${seperator.plus1}** orange and **${seperator.plus0}** blue. >

> ${tex.block` \text { Entropy }(${sep}-) = - \frac{${seperator.minus1}}{${seperator.totalMinus}} log_2 \frac{${seperator.minus1}}{${seperator.totalMinus}} - \frac{${seperator.minus0}}{${seperator.totalMinus}} log_2 \frac{${seperator.minus0}}{${seperator.totalMinus}} = ${resultMinus.toFixed(3)}\\~\\ \text { Entropy }(${sep}+) = - \frac{${seperator.plus1}}{${seperator.totalPlus}} log_2 \frac{${seperator.plus1}}{${seperator.totalPlus}} - \frac{${seperator.plus0}}{${seperator.totalPlus}} log_2 \frac{${seperator.plus0}}{${seperator.totalPlus}} = ${resultPlus.toFixed(3)}\\~\\~\\ \text {IG}(${sep}) = \text {Original-Entropy} - \sum_i \frac{|${sep}_i|}{${sep}} \text {Entropy}(${sep}_i) \\~\\ = 1 - \left(\frac{${seperator.totalMinus}}{10} \text { Entropy }(${sep}-) + \frac{${seperator.totalPlus}}{10} \text { Entropy }(${sep}+) \right) \\~\\ = 1 - \left(\frac{${seperator.totalMinus}}{10} \times ${resultMinus.toFixed(3)} + \frac{${seperator.totalPlus}}{10} \times ${resultPlus.toFixed(3)} \right) = ${resultIG.toFixed(3)}\\~\\ `}32:T47d,

## Classification and Regression Tree (CART) > Given training data > ${tex.block` D = \left\{(X^{(1)}, y^{(1)}), \ (X^{(2)}, y^{(2)}) \ \cdots \ (X^{(N)}, y^{(N)}) \right\} \\~\\ `} > We hope to learn a CART model that minimize the following cost function: > ${tex.block` Loss = \min_{j,s} \left[ \min_{C_1} L(y^{(i)}, C_1) + \min_{C_2} L(y^{(i)}, C_2) \right] \\~\\ where \quad C_m = average(y_i \ | \ x_i \in R_m) \\~\\ `} > In the CART model, we need to find the best variable ${tex`X_j`} and cut point ${tex`S`} in order to minimize the loss function. We can rewrite the loss by: > ${tex.block` Loss = \min_{j,s} \left[ \min_{C_1} \sum_{X \in R_1(j,s)} (y^{(i)}-C_1)^2 + \min_{C_2} \sum_{X \in R_2(j,s)} (y^{(i)}- C_2)^2 \right] \\~\\~\\ R_1(j,S) = \left\{ x \ | \ x_j \le S \right\} \\ R_2(j,S) = \left\{ x \ | \ x_j > S \right\} \\~\\ C_m = \frac{1}{N_m} \sum_{X \in R_m(j,s)} y^{(i)}, \quad m = 1 \text{ and } 0 \text { (binary) } \\~\\ `} > We need to calculate Loss(S) for each cut point (S) to find the best one. If we have more than one variable, we need to search (${tex`j = 1,2, \cdots n`}) with best cut point ${tex`S_j`}.33:[] 2f:{"title":"ML | 6 Decision Tree","cells":[{"id":0,"value":"# ML | 6 Decision Tree\n

","pinned":false,"hidden":false,"mode":"md"},{"id":6,"value":"## Information Theory\n\n> 1. The relationship between information ${tex`H(x)`} and probability ${tex`P(x)`}: ${tex`H(x) \\Leftrightarrow \\frac{1}{P(x)}`}\n>> * Low Probability Event: High Information (surprising).\n>> * High Probability Event: Low Information (unsurprising).\n>
\n> 2. ${tex`H(x_1, x_2) \\Leftrightarrow H(x_1) + H(x_2) \\\\~\\\\`}\n>
\n\n> **Information Function**\n> ${tex.block`\nH(x) = log_2 \\frac{1}{P(x)} = -log_2 P(x)\n`}\n> This function has attributes:
\n>> (1) Lower probability event has higher information, vice versa.
\n>> (2) ${tex.block`\nH(x_1, x_2) = log_2 \\frac{1}{P(x_1) P(x_2)} \\\\~\\\\\n= -log_2(P(x_1) P(x_2)) \\\\~\\\\\n= -(log_2 P(x_1) + log_2 P(x_2)) \\\\~\\\\\nwhere \\quad x_1 \\perp x_2 \\\\~\\\\\n`} \n\n> **Entropy** is the expected value of the information function\n> ${tex.block`\nEntropy = E_x[H(x)] = - \\sum_{x} P(x) log_2 P(x) \\\\~\\\\\n`}","pinned":false,"hidden":false,"mode":"md"},{"id":465,"value":"plot_6_1 = {\n\n const xmin = 0\n const xmax = 1\n const ymin = 0\n const ymax = 1\n const margin = 0.04\n \n const p = plotter({\n xDomain: [xmin-margin, xmax],\n yDomain: [ymax, ymin],\n xLabel: 'P(x)', \n yLabel:'Entropy(S)',\n grid: false,\n height: 350,\n width: 350\n });\n \n p.func(x => -1 * x * Math.log2(x) + (-1) * (1-x) * Math.log2(1-x), {\n stroke: 'steelblue',\n width: 2,\n defined: x => x >= 0 && x <= 1\n });\n\n p.segment(0.5, 0, 0.5, 1, { \n stroke: 'grey', \n width: 2, \n dash: '2,2'\n });\n\n return p.node;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":47,"value":"

\n## Information Gain (IG)","pinned":false,"hidden":false,"mode":"md"},{"id":229,"value":"> ${tex.block`\n\\text {IG } = \\text { Original-Entropy}(S) - \\sum W_i \\text { Entropy } (S_i) \\\\~\\\\\n= \\text { Original-Entropy}(S) - \\sum \\frac{|S_i|}{|S|} \\text { Entropy } (S_i) \\\\~\\\\\n`}","pinned":false,"hidden":false,"mode":"md"},{"id":193,"value":"viewof sep = Inputs.radio([\"A\", \"B\", \"C\"], {label: \"Seperate at Point: \", value: 'A'})","pinned":false,"hidden":false,"mode":"ojs"},{"id":131,"value":"plot_6_2 = {\n let w = 700;\n let p = plotter({ \n xDomain: [0, 10.5],\n yDomain: [3,1],\n width: w, \n height: w / 4, \n grid: false,\n axises: false \n });\n\n for (const d of demoData) {\n p.circle(d.x, d.y, 0.2, \n { stroke: d.cat == 0 ? 'steelblue' : 'orange', \n fill: d.cat == 0 ? 'steelblue' : 'orange', \n opacity: 0.9 }\n );\n }\n\n p.line_segment(cutoff, 1.5, cutoff, 3, { stroke: 'grey', width: 1.5});\n p.text(sep, cutoff, 1.2, { stroke: 'grey' });\n p.arrow(cutoff+0.2, 2.5, 10.5 , 2.5, { stroke: 'grey', width: 1, dash: '2,2'});\n p.arrow(cutoff-0.2, 2.5, 0.5 , 2.5, { stroke: 'grey', width: 1, dash: '2,2'});\n\n p.text(sep+'-', (cutoff)/2, 2.7, { stroke: 'grey' });\n p.text(sep+'+', (10-cutoff)/2+cutoff, 2.7, { stroke: 'grey' });\n\n return p.node;\n}\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":245,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":400,"value":"

\n## GINI Index\n\n> Gini Index for a given node t:\n> ${tex.block`\n\\text {GINI}(t) = 1 - \\sum_{j} \\left[p(j | t) \\right]^2\n`}\n> (Note: ${tex`p(j|t)`} is the relative frequency of class j at node t.)\n\n> When a node p is split into k partitions (children), the quality of split is computed as\n> ${tex.block`\n\\text {GINI}_{split} = \\sum_{i=1}^k \\frac{n_i}{n} \\text {GINI}(i) \\\\~\\\\\n\\quad n_i = \\text {number of records at child }i \\\\\n\\quad n = \\text {number of records at node }p \\\\\n`}\n","pinned":false,"hidden":false,"mode":"md"},{"id":392,"value":"

\n## Splitting a Decision Tree\n\n> Steps to split a decision tree using Information Gain:
\n> (Source: https://www.analyticsvidhya.com/blog/2020/06/4-ways-split-decision-tree)\n\n> 1. For each split, individually calculate the entropy of each child node\n> 2. Calculate the entropy of each split as the weighted average entropy of child nodes\n> 3. Select the split with the lowest entropy or highest information gain\n> 4. Until you achieve homogeneous nodes, repeat steps 1-3\n>\n> Decision tree is a model that divides the input space into a few regions","pinned":false,"hidden":false,"mode":"md"},{"id":418,"value":"$32","pinned":false,"hidden":false,"mode":"md"},{"id":71,"value":"

\n## Appendix","pinned":false,"hidden":false,"mode":"md"},{"id":380,"value":"resultIG = 1 - (seperator.totalMinus/10*resultMinus + seperator.totalPlus/10*resultPlus)","pinned":false,"hidden":false,"mode":"ojs"},{"id":282,"value":"resultMinus = (isNaN(seperator.minus1/seperator.totalMinus * Math.log2(seperator.minus1/seperator.totalMinus)) ? 0 : (-1)*(seperator.minus1/seperator.totalMinus * Math.log2(seperator.minus1/seperator.totalMinus))) + (isNaN(seperator.minus0/seperator.totalMinus * Math.log2(seperator.minus0/seperator.totalMinus)) ? 0 : (-1)*(seperator.minus0/seperator.totalMinus * Math.log2(seperator.minus0/seperator.totalMinus)))","pinned":false,"hidden":false,"mode":"ojs"},{"id":291,"value":"resultPlus = (isNaN(seperator.plus1/seperator.totalPlus * Math.log2(seperator.plus1/seperator.totalPlus)) ? 0 : (-1)*(seperator.plus1/seperator.totalPlus * Math.log2(seperator.plus1/seperator.totalPlus))) + (isNaN(seperator.plus0/seperator.totalPlus * Math.log2(seperator.plus0/seperator.totalPlus)) ? 0 : (-1)*(seperator.plus0/seperator.totalPlus * Math.log2(seperator.plus0/seperator.totalPlus)))","pinned":false,"hidden":false,"mode":"ojs"},{"id":269,"value":"seperator = {\n let classMinus = demoData.filter(d=>d.x < cutoff);\n let classPlus= demoData.filter(d=>d.x > cutoff);\n\n return {totalMinus:classMinus.length,\n totalPlus: classPlus.length, \n minus1:classMinus.filter(d=>d.cat == 1).length,\n minus0:classMinus.filter(d=>d.cat == 0).length,\n plus1:classPlus.filter(d=>d.cat == 1).length,\n plus0:classPlus.filter(d=>d.cat == 0).length,}\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":214,"value":"cutoff = linesData.filter(d=>d.text == sep)[0].x","pinned":false,"hidden":false,"mode":"ojs"},{"id":124,"value":"linesData = [{x:3.5, text:'A'}, {x:6.5, text:'B'}, {x:8.5, text:'C'}]","pinned":false,"hidden":false,"mode":"ojs"},{"id":88,"value":"demoData = [{x:1, y:2, cat:1},{x:2, y:2, cat:1},{x:3, y:2, cat:1},{x:4, y:2, cat:0},{x:5, y:2, cat:0},{x:6, y:2, cat:0},{x:7, y:2, cat:1},{x:8, y:2, cat:1},{x:9, y:2, cat:0},{x:10, y:2, cat:0}]","pinned":false,"hidden":false,"mode":"ojs"},{"id":77,"value":"import { plotter } from '50dadfdec01c15a8'","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}