{"id":530,"date":"2022-07-22T06:41:05","date_gmt":"2022-07-21T22:41:05","guid":{"rendered":"https:\/\/www.wennroy.com\/?p=530"},"modified":"2022-07-23T12:46:29","modified_gmt":"2022-07-23T04:46:29","slug":"introduction-to-data-mining1","status":"publish","type":"post","link":"https:\/\/wennroy.com\/index.php\/2022\/07\/22\/introduction-to-data-mining1\/","title":{"rendered":"Introduction to Data Mining"},"content":{"rendered":"\n

2020\u5e74\u7684\u7b14\u8bb0\uff0c\u62ff\u51fa\u6765\u8bb0\u5f55\u4e00\u4e0b\u3002<\/p>\n\n\n\n

Introduction to Data Mining 1<\/h1>\n\n\n\n

\u76f8\u4f3c\u6027\u4e0e\u76f8\u5f02\u6027\u7684\u5ea6\u91cf<\/h2>\n\n\n\n

Metric \u5ea6\u91cf<\/h3>\n\n\n\n

  1. \u975e\u8d1f\u6027<\/strong>\u3002 $$ d(x,y)\\geq 0\\quad\\mbox{Only when } x = y,~d(x,y) = 0 $$<\/p> <\/li>

  2. \u5bf9\u79f0\u6027<\/strong>\u3002 $$ d(x,y) = d(y,x) $$<\/p> <\/li>

  3. \u4e09\u89d2\u4e0d\u7b49\u5f0f<\/strong>\u3002 $$ d(x,z)\\leq d(x,y) + d(y,z) $$<\/p> <\/li><\/ol>\n\n\n\n

    \u76f8\u4f3c\u5ea6(Similarity)\u4e0e\u76f8\u5f02\u5ea6(Dissimilarity)<\/h3>\n\n\n\n
    Term<\/th>Range<\/th>Synonym<\/th><\/tr><\/thead>
    Similarity<\/td>[0,1]<\/td><\/td><\/tr>
    Dissimilarity<\/td>Usually [0,$\\infty$]<\/td>Distance<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

    Distance<\/h4>\n\n\n\n

    1. Euclidean Distance:\n$$\nd(\\textbf{x},\\textbf{y}) = \\sqrt{\\sum_{k = 1}^{n}(x_k – y_k)^2}\n$$<\/p>\n<\/li>

    2. Minkowski Distance:\n$$\nd(\\textbf{x},\\textbf{y}) = \\left(\\sum_{k = 1}^{n}|x_k – y_k|^r\\right)^{1\/r}\n$$<\/p>\n<\/li>

    3. Mahalanobis Distance:\n$$\nd(\\textbf x,\\textbf y) = (\\textbf x-\\textbf y)\\boldsymbol{\\Sigma}^{-1}(\\textbf x-\\textbf y)^T\n$$<\/p>\n<\/li><\/ol>\n\n\n\n

      \u4e8c\u5143\u6570\u636e\u7684\u76f8\u4f3c\u6027\u5ea6\u91cf<\/h4>\n\n\n\n

      \u4e00\u822c\u503c\u4e3a1\u8868\u660e\u4e24\u4e2a\u5bf9\u8c61\u5b8c\u5168\u76f8\u4f3c\u3002\u503c\u4e3a0\u8868\u660e\u5bf9\u8c61\u4e00\u70b9\u4e5f\u4e0d\u76f8\u4f3c\u3002<\/p>\n\n\n\n

      \u7b80\u5355\u5339\u914d\u7cfb\u6570(Simple Matching Coefficient)<\/h5>\n\n\n\n

      $$\nSMC = \\frac{\\mbox{\u503c\u5339\u914d\u7684\u5c5e\u6027\u4e2a\u6570}}{\\mbox{\u5c5e\u6027\u4e2a\u6570}} = \\frac{f_{11} + f_{00}}{f_{01} + f_{10} + f_{11} + f_{00}}\n$$<\/p>\n\n\n\n

      Jaccard \u7cfb\u6570(Jaccard Coefficient)<\/h5>\n\n\n\n

      $$\nJ = \\frac{\\mbox{\u5339\u914d\u7684\u4e2a\u6570}}{\\mbox{\u4e0d\u6d89\u53ca0-0\u5339\u914d\u7684\u5c5e\u6027\u4e2a\u6570}} = \\frac{f_{11}}{f_{01}+f_{10} + f_{11}}\n$$<\/p>\n\n\n\n

      \u5f530-0\u4ea7\u54c1\u8fc7\u591a\u7684\u65f6\u5019\uff0c\u8fd9\u4f1a\u5bfc\u81f4SMC\u603b\u4f53\u503c\u53d8\u5316\u4e0d\u591f\u663e\u8457\uff0c\u56e0\u6b64\u5254\u9664$f_{00}$\u3002<\/p>\n\n\n\n

      \u4f59\u5f26\u76f8\u4f3c\u5ea6<\/h4>\n\n\n\n

      $$\n\\cos(\\textbf{x},\\textbf y) = \\frac{\\textbf x\\cdot\\textbf y}{\\|\\textbf x\\|\\|\\textbf y\\|}\n$$<\/p>\n\n\n\n

      Bregman Divergence<\/h4>\n\n\n\n

      Bregman\u6563\u5ea6\u662f\u635f\u5931\u6216\u5931\u771f\u51fd\u6570\u3002$\\textbf y$\u662f\u539f\u6765\u7684\u70b9\uff0c\u800c$\\textbf{x}$\u662f\u5b83\u7684\u67d0\u4e2a\u5931\u771f\u6216\u8fd1\u4f3c\u3002\u4f8b\u5982$\\textbf{x}$\u53ef\u80fd\u662f\u6dfb\u52a0\u4e86\u4e00\u4e9b\u968f\u673a\u566a\u58f0\u5230$\\textbf{y}$\u4e0a\u4ea7\u751f\u7684\u3002\u6b63\u5f0f\u5b9a\u4e49\u5982\u4e0b\uff1a<\/p>\n\n\n\n

      Bregman \u6563\u5ea6<\/strong> \u7ed9\u5b9a\u4e00\u4e2a\u4e25\u683c\u51f8\u51fd\u6570$\\phi$ \uff0c\u7531\u8be5\u51fd\u6570\u751f\u6210\u7684Bregman\u6563\u5ea6$D(\\textbf x,\\textbf y)$\u901a\u8fc7\u4ee5\u4e0b\u516c\u5f0f\u7ed9\u51fa\uff1a $$ D(\\textbf x,\\textbf y) = \\phi(\\textbf x)-\\phi(\\textbf y) – \\left<\\nabla\\phi(\\textbf y),(\\textbf x-\\textbf y)\\right> $$ \u5176\u4e2d\uff0c$\\nabla\\phi(\\textbf y)$ \u662f\u5728$\\textbf y$\u4e0a\u8ba1\u7b97\u7684$\\phi$ \u68af\u5ea6\uff0c$\\textbf x – \\textbf y$ \u4e0e$\\textbf x$\u4e0e$\\textbf y$ \u7684\u5411\u91cf\u5dee\uff0c$\\left<\\nabla\\phi(\\textbf y),(\\textbf x-\\textbf y)\\right>$ \u662f\u5185\u79ef\u3002 <\/p>\n\n\n\n

      Kullback-Leibler Divergence<\/h4>\n\n\n\n

      $$\nD_{KL}(p||q) = \\int_xp(x)\\ln\\frac{p(x)}{q(x)}\\text dx\n$$<\/p>\n\n\n\n

      F-divergence<\/h4>\n\n\n\n

      KL-divergence \u7684\u574f\u5904\u5728\u4e8e\u5b83\u662f\u65e0\u754c\u7684\u3002\u4e8b\u5b9e\u4e0aKL-divergence \u5c5e\u4e8e\u66f4\u5e7f\u6cdb\u7684f-divergence\u4e2d\u7684\u4e00\u79cd\u3002<\/p>\n\n\n\n

      \u5e38\u7528\u7684F-divergence\u6709 Hellinger distance<\/a>, Total Variation Distance<\/a>.\n$$\nD_f(p||q) = \\int_xq(x)f\\left(\\frac{p(x)}{q(x)}\\right)\\text d x\n$$\n\u5982\u679c\u53d6$f(t) = t\\log t$\u6216\u8005$f(t) = -\\log t$\u5c31\u80fd\u5f97\u5230KL\u6563\u5ea6\u3002<\/p>\n\n\n\n

      \u5206\u5e03\u7684\u76f8\u4f3c\u5ea6\u7528\u4ec0\u4e48\u6a21\u578b\u6bd4\u8f83\u597d<\/h3>\n\n\n\n

      \u5206\u5e03\u5f0f\u7684\u76f8\u901f\u5ea6\uff08\u8ddd\u79bb\uff09\u7528\u4ec0\u4e48\u6a21\u578b\u6bd4\u8f83\u597d<\/a><\/p>\n\n\n\n

      Wasserstein distance<\/h4>\n\n\n\n

      \u5165\u95e8\u4e3e\u4f8b\uff1a\u5047\u8bbe\u4f60\u662f\u4e00\u4e2a\u505a\u6728\u6750\u8fd0\u8f93\u7684\uff0c\u4f60\u8981\u8fd0\u9001\u6728\u6750\u4ece\u82e5\u5e72\u4e2a\u6728\u6750\u751f\u4ea7\u5730\u5230\u82e5\u5e72\u4e2a\u6728\u6750\u9700\u6c42\u5730\uff0c\u5047\u8bbe\u6bcf\u4e2a\u751f\u4ea7\u5730\u6709\u56fa\u5b9a\u6570\u91cf\u7684\u6728\u6750\uff0c\u6bcf\u4e2a\u9700\u6c42\u5730\u4e5f\u6709\u56fa\u5b9a\u6570\u91cf\u6728\u6750\u7684\u9700\u6c42\uff0c\u4ed6\u4eec\u7684\u603b\u548c\uff08\u6070\u597d\uff09\u5f7c\u6b64\u76f8\u7b49\uff0c\u4f60\u8981\u6307\u5b9a\u4e00\u4e2a\u8fd0\u8f93\u8ba1\u5212\uff0c\u628a\u6240\u6709\u6728\u6750\u4ece\u751f\u4ea7\u5730\u5206\u522b\u8fd0\u9001\u5230\u9700\u6c42\u5730\uff0c\u4f7f\u5f97\u4f9b\u9700\u521a\u597d\u5e73\u8861\uff0c\u4e5f\u5c31\u662f\u6bcf\u4e2a\u751f\u4ea7\u5730\u7684\u6728\u6750\u90fd\u521a\u597d\u8fd0\u9001\u8d70\u4e86\uff0c\u6bcf\u4e2a\u9700\u6c42\u5730\u90fd\u5f97\u5230\u4e86\u9884\u671f\u7684\u6728\u6750\u91cf\u3002\u4f60\u5c06\u78b0\u5230\u8fd9\u6837\u4e00\u4e2a\u95ee\u9898\uff1a\u5047\u8bbe\u4f60\u4e8b\u5148\u5df2\u7ecf\u8ba1\u7b97\u597d\u4ece\u6bcf\u4e2a\u751f\u4ea7\u5730\u8fd0\u9001\u6728\u6750\u5230\u6bcf\u4e2a\u9700\u6c42\u5730\u7684\u5355\u4f4d\u6728\u6750\u8fd0\u8d39\uff0c\u4f60\u8be5\u600e\u6837\u5408\u7406\u7684\u6307\u5b9a\u8fd0\u8f93\u8ba1\u5212\u4f7f\u5f97\u603b\u5f00\u652f\u6700\u5c0f\u5462\uff1f<\/p>\n\n\n\n

      wiki: Wasserstein metric<\/a><\/p>\n\n\n\n

      \u53ea\u8ba8\u8bba\u6700\u7b80\u5355\u7684\u60c5\u51b5\uff0c\u5b9a\u4e49\uff0c\n$$\nW_2(p,q) = \\sqrt{\\min_{P_{XY}} E_{P_{XY}}\\left[\\|x-y\\|^2_2\\right]}\\quad s.t. P_X\\sim p,P_Y\\sim q\n$$\n\u4e5f\u5c31\u662f\u8bf4\u5bf9\u4e8e\u4efb\u610f\u8fb9\u7f18\u5206\u5e03\u4e3a$p$\u548c$q$\u7684\u8054\u5408\u5206\u5e03$P_{XY}$\uff0c\u6211\u4eec\u53ef\u4ee5\u6c42\u51fa$E_{P_{XY}}\\left[\\|x-y\\|^2_2\\right]$\uff0c\u800c$p$\u548c$q$\u7684Wasserstein Distance\u5219\u5b9a\u4e49\u4e3a$P_{XY}$\u53d6\u904d\u53ef\u80fd\u7684\u5206\u5e03\u65f6\uff0c\u8fd9\u4e2a\u671f\u671b\u7684\u6700\u5c0f\u503c\u7684\u5e73\u65b9\u6839\u3002<\/p>\n\n\n\n

      \u53ef\u89c6\u5316<\/h2>\n\n\n\n

      \u5404\u79cd\u56fe<\/h3>\n\n\n\n

      \u6563\u5e03\u56fe<\/h4>\n\n\n\n

      Empirical CDF:<\/p>\n\n\n\n

      \u51b3\u7b56\u6811<\/h2>\n\n\n\n

      \u56de\u5f52\u6811<\/h3>\n\n\n\n

      Three elements:<\/p>\n\n\n\n

      1. Split process\n\u2022 Choose splitting variables and split points\n\u2022 Goodness of split criterion !(s, t) needed to evaluate any\nsplit s of any node t.<\/li>
      2. Partition process\n\u2022 Partition the data into two resulting regions and repeat the\nsplitting process on each region\n\u2022 Declare a node is terminal or to continue splitting it; need a\nstop-splitting rule<\/li>
      3. Pruning Process\n\u2022 Collapse some branches back together<\/li><\/ol>\n\n\n\n

        \u8003\u8651\u6211\u4eec\u6709$M$\u4e2a\u5206\u5272\u533a\u57df$R_1,R_2,\\ldots,R_M$\uff0c\u5bf9\u4e8e\u6bcf\u4e2a\u533a\u57df\u7684\u5e38\u6570$c_m$\uff0c\u6211\u4eec\u6709\uff1a $$ f(x) = \\sum_{m=1}^Mc_mI(x\\in R_m) $$ <\/p>\n\n\n\n

        \u5bf9\u4e8e\u4e00\u6b21\u526a\u679d\u6b65\u9aa4\uff0c\u4e0d\u59a8\u8bbe\u4e24\u8fb9\u5de6\u53f3\u5b69\u5b50\u5206\u522b\u4e3a $$ R_1(j,s) = \\lbrace\\textbf X |X_j\\leq s\\rbrace,\\quad\\text{and}\\quad R_2(j,s) = \\lbrace\\textbf X |X_j> s\\rbrace $$ <\/p>\n\n\n\n

        \u7136\u540e\u6700\u5c0f\u5316: $$ \\min_{j,s}[\\phi_{R_1}+\\phi_{R_2}] $$ \u5176\u4e2d$\\phi_{R_m}$\u662f\u67d0\u79cd\u5bf9\u4e8e\u7ed3\u70b9$R_m$\u7684\u7eaf\u5ea6\u6d4b\u91cf\u3002<\/p>\n\n\n\n

        \u9009\u62e9\u6700\u4f73\u5212\u5206\u7684\u5ea6\u91cf<\/h3>\n\n\n\n

        \u51b3\u5b9a\u6811\u7684Size\u2014\u2014Terminal points(Leaf points) \u7684\u4e2a\u6570\u3002Cardinality<\/p>\n\n\n\n

        \u5728\u4e8c\u53c9\u6811\u4e2d\uff0c\u53f6\u7ed3\u70b9\u7684\u6570\u91cf\u662f\u5206\u88c2(split)\u7ed3\u70b9+1.<\/p>\n\n\n\n

        \u5b9a\u4e49$p(i|t)$\u8868\u793a\u7ed9\u5b9a\u7ed3\u70b9$t$\u4e2d\u5c5e\u4e8e\u7c7b$i$\u7684\u8bb0\u5f55\u6240\u5360\u7684\u6bd4\u4f8b\u3002\u5728\u4e8c\u5143\u95ee\u9898\u4e2d\uff0c\u6211\u4eec\u4efb\u610f\u7ed3\u70b9\u7684\u7c7b\u5206\u5e03\u90fd\u53ef\u4ee5\u8bb0\u4f5c\u662f$(p_0,p_1)$\uff0c\u5176\u4e2d$p_0+p_1 = 1$\u3002<\/p>\n\n\n\n

        \u540c\u65f6\u6211\u4eec\u5b9a\u4e49\u4e0d\u7eaf\u6027(\u5927\u6982\u662fImpure)\u3002(0,1)\u5177\u6709\u96f6\u4e0d\u7eaf\u6027\uff0c(0.5,0.5)\u5177\u6709\u6700\u9ad8\u7684\u4e0d\u7eaf\u6027\u3002\u56de\u5f52\u4e2d\u6211\u4eec\u53ef\u4ee5\u7528RSS\u6765\u8861\u91cfimpurity\u3002RSS\u9ad8\u8bf4\u660e\u8d8a\u4e0d\u7eaf\uff0cRSS\u4f4e\u8bf4\u660e\u7eaf\u3002\u800c\u5176\u4ed6\u60c5\u51b5(\u79bb\u6563)\u7684\u4e0d\u7eaf\u6027\u7684\u5ea6\u91cf\u6211\u4eec\u5229\u7528\u4ee5\u4e0b\u65b9\u6cd5\uff1a\n$$\n\\begin{eqnarray}\n\\mbox{Entropy}(t) &=& -\\sum_{i=0}^{c-1}p(i|t)\\log_2p(i|t)\\\\\n\\mbox{Gini}(t) &=& 1-\\sum_{i = 0}^{c-1}[p(i|t)]^2\\\\\n\\mbox{Classification error}(t) &=& 1-\\max_\\limits{i}[p(i|t)]\n\\end{eqnarray}\n$$\n\u5176\u4e2d$c$\u662f\u7c7b\u7684\u4e2a\u6570\uff0c\u5e76\u4e14\u5728\u8ba1\u7b97\u71b5\u65f6\uff0c$O\\log_20 = 0$\u3002<\/p>\n\n\n\n

        \u4e3a\u4e86\u786e\u5b9a\u6d4b\u8bd5\u6761\u4ef6\u7684\u6548\u679c\uff0c\u6211\u4eec\u9700\u8981\u6bd4\u8f83\u7236\u7ed3\u70b9(\u5212\u5206\u524d)\u7684\u4e0d\u7eaf\u7a0b\u5ea6\u548c\u5b50\u5973\u7ed3\u70b9(\u5212\u5206\u540e)\u7684\u4e0d\u7eaf\u7a0b\u5ea6\uff0c\u5b83\u4eec\u7684\u5dee\u8d8a\u5927\uff0c\u6d4b\u8bd5\u6761\u4ef6\u7684\u6548\u679c\u5c31\u8d8a\u597d\u3002\u589e\u76ca$\\Delta$\u662f\u4e00\u79cd\u53ef\u4ee5\u7528\u6765\u786e\u5b9a\u5212\u5206\u6548\u679c\u7684\u6807\u51c6:\n$$\n\\Delta = I(\\mbox{parent}) = \\sum_{i = 1}^k\\frac{N(v_j)}{N}I(v_j)\n$$\n\u5176\u4e2d\uff0c$I(\\cdot)$\u662f\u7ed9\u5b9a\u7ed3\u70b9\u7684\u4e0d\u7eaf\u6027\u5ea6\u91cf\uff0c$N$\u662f\u7236\u7ed3\u70b9\u4e0a\u7684\u8bb0\u5f55\u603b\u6570\uff0c$k$\u662f\u5c5e\u6027\u503c\u7684\u4e2a\u6570\uff0c$N(v_j)$\u662f\u5b50\u5973\u7ed3\u70b9$v_j$\u76f8\u5173\u8054\u7684\u8bb0\u5f55\u4e2a\u6570\u3002\u6211\u4eec\u7684\u76ee\u7684\u5c31\u662f\u4e3a\u4e86\u6700\u5927\u5316$\\Delta$\u3002\u4e5f\u5c31\u662f\u6700\u5c0f\u5316\u5b50\u5973\u7ed3\u70b9\u7684\u4e0d\u7eaf\u6027\u5ea6\u91cf\u7684\u52a0\u6743\u503c\u3002<\/p>\n\n\n\n

        \u5982\u679c\u6211\u4eec\u9009\u62e9\u71b5(entropy)\u4f5c\u4e3a\u6211\u4eec\u7684\u4e0d\u7eaf\u6027\u5ea6\u91cf\uff0c\u5219\u71b5\u7684\u5dee\u5c31\u662f\u4fe1\u606f\u589e\u76ca(information gain)$\\Delta_{\\mbox{info}}$\u3002<\/p>\n\n\n\n

        \u4e00\u822c\u6211\u4eec\u90fd\u9009\u62e9\u71b5<\/strong>\u6216\u8005\u57fa\u5c3c<\/strong>\u6765\u4f5c\u4e3a\u6211\u4eec\u7684\u589e\u76ca\u51fd\u6570\u3002<\/p>\n\n\n\n

        \u8865\u5145\uff1a<\/p>\n\n\n\n

        \u5bf9\u4e8e\u6837\u672cD\uff0c\u4e2a\u6570\u4e3a|D|\uff0c\u6839\u636e\u7279\u5f81A\u7684\u67d0\u4e2a\u503ca\uff0c\u628aD\u5206\u6210|D1|\u548c|D2|\uff0c\u5219\u5728\u7279\u5f81A\u7684\u6761\u4ef6\u4e0b\uff0c\u6837\u672cD\u7684\u57fa\u5c3c\u7cfb\u6570\u8868\u8fbe\u5f0f\u4e3a\uff1a\u8fd9\u4e5f\u5c31\u662f\u591a\u8def\u5206\u652f\u7684\u57fa\u5c3c\u6307\u6570\u8ba1\u7b97\u65b9\u6cd5\n$$\nGini(D,A) = \\frac{|D_1|}{|D|}Gini(D_1) + \\frac{|D_2|}{|D|}Gini(D_2)\n$$<\/p>\n\n\n\n

        \u6211\u4eec\u8fd9\u91cc\u4e3e\u4e00\u4e2a\u5b9e\u4f8b\u6765\u89e3\u91ca\u8ba1\u7b97\u65b9\u6cd5\uff1a<\/p>\n\n\n\n

        \u5de5\u4f5c\u6027\u8d28\u7684\u71b5<\/strong><\/p>\n\n\n\n

        1. \u7a33\u5b9a\uff1a8 = 6\u9ad8+2\u4f4e<\/p>\n

          \u4e00\u822c\uff1a6 = 3\u9ad8+3\u4f4e<\/p>\n<\/li>

        2. $$\nEntropy(S_{wd}) = -\\left(\\frac 6 8\\right)\\log_2\\frac 6 8-\\left(\\frac2 8\\right)\\log_2\\frac 2 8 =0.811\n$$<\/p>\n

          $$\nEntropy(S_{yb}) = -\\left(\\frac 3 6\\right)\\log_2\\frac 3 6-\\left(\\frac3 6\\right)\\log_2\\frac 3 6 =1\n$$<\/p>\n<\/li>

        3. \u7531\u201c\u7a33\u5b9a\u201d\u548c\u201c\u4e00\u822c\u201d\u7684\u71b5\u53ef\u6c42\u5f97\u7684\u5c5e\u6027\u201c\u5de5\u4f5c\u6027\u8d28\u201d\u7684\u71b5\u4e3a\uff1a\n$$\nEntropy(S,\\mbox{\u5de5\u4f5c\u6027\u8d28}) = \\left(\\frac 8 {14}\\right)Entropy(S_{wd}) + \\left(\\frac 6{14}\\right)Entropy(S_{yb}) = 0.892\n$$\n\u9ad8\u548c\u4f4e\u4ee3\u8868\u7684\u662f\u989d\u5ea6\u3002<\/p>\n<\/li><\/ol>\n\n\n\n

          \u7b97\u6cd5\u5b9e\u73b0\u7684\u5173\u952e\u70b9<\/h3>\n\n\n\n

          Decision_tree.py<\/a> \u63d0\u4f9b\u4e86\u79bb\u6563\u60c5\u51b5\u7684\u7b97\u6cd5\u5b9e\u73b0<\/p>\n\n\n\n

          \u51b3\u7b56\u6811\u4e4bC4.5\u5b9e\u73b0\uff08\u79bb\u6563\u5c5e\u6027\u4e0e\u8fde\u7eed\uff0c\u5c5e\u6027\u5e76\u5b58\uff09<\/a>\u542b\u4ee3\u7801<\/p>\n\n\n\n

          \u4e09\u79cd\u5e38\u89c1\u7684\u7b97\u6cd5\u6709C4.5\u3001ID3\u3001CART\u5206\u7c7b\u6811\u3002<\/p>\n\n\n\n

          \u7b97\u6cd5<\/th>\u652f\u6301\u6a21\u578b<\/th>\u6811\u7ed3\u6784<\/th>\u7279\u5f81\u9009\u62e9<\/th>\u8fde\u7eed\u503c\u5904\u7406<\/th>\u7f3a\u5931\u503c\u5904\u7406<\/th>\u526a\u679d<\/th><\/tr><\/thead>
          ID3<\/td>\u5206\u7c7b<\/td>\u591a\u53c9\u6811<\/td>\u4fe1\u606f\u589e\u76ca<\/td>\u4e0d\u652f\u6301<\/td>\u4e0d\u652f\u6301<\/td>\u4e0d\u652f\u6301<\/td><\/tr>
          C4.5<\/td>\u5206\u7c7b<\/td>\u591a\u53c9\u6811<\/td>\u4fe1\u606f\u589e\u76ca\u6bd4<\/td>\u652f\u6301<\/td>\u652f\u6301<\/td>\u652f\u6301<\/td><\/tr>
          CART<\/td>\u5206\u7c7b\u56de\u5f52<\/td>\u4e8c\u53c9\u6811<\/td>\u57fa\u5c3c\u7cfb\u6570 \u5747\u65b9\u5dee<\/td>\u652f\u6301<\/td>\u652f\u6301<\/td>\u652f\u6301<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

          ID3\u5206\u7c7b\u6811\u7684\u5b9e\u8df5<\/h4>\n\n\n\n

          Iterative Dichotmizer 3(ID3)<\/p>\n\n\n\n

          ID3\u5206\u7c7b\u6811<\/a><\/p>\n\n\n\n

          \u603b\u6d41\u7a0b\uff1a<\/p>\n\n\n\n

          1. \u9009\u62e9\u51b3\u7b56\u6811\u7684\u6839\u8282\u70b9\uff0c\u9009\u62e9\u6807\u51c6\uff1a\u6839\u636e\u5c5e\u6027\u7684\u4fe1\u606f\u589e\u76ca\uff0c\u786e\u5b9a\u51b3\u7b56\u6811\u7684\u6839\u7ed3\u70b9\n$$\nGain(S,A) = Entropy(S) – Entropy(S,A)\n$$<\/p>\n<\/li>

          2. \u8282\u70b9\u5c5e\u6027\u5212\u5206<\/p>\n<\/li>

          3. \u5bf9\u5212\u5206\u7684\u5b50\u96c6\u6309\u7167\u4e0a\u8ff0\u8fc7\u7a0b\u8fdb\u884c\u53cd\u590d\u8fed\u4ee3\u6765\u83b7\u5f97\u6811\u7684\u6240\u6709\u5185\u90e8\u8282\u70b9<\/p>\n<\/li>

          4. \u6700\u540e\u6839\u636e\u8282\u70b9\u3001\u5185\u90e8\u8282\u70b9\u4ee5\u53ca\u53f6\u8282\u70b9\u95f4\u7684\u5173\u7cfb\u6784\u5efa\u51b3\u7b56\u6811<\/p>\n<\/li><\/ol>\n\n\n\n

            \u6ce8\u610f\uff1a\u8be5\u8fc7\u7a0b\u9700\u8981\u53cd\u590d\u8fed\u4ee3\uff0c\u4e5f\u5c31\u662f\u6700\u57fa\u7840\u7684\u51b3\u7b56\u6811\u7b97\u6cd5\u3002<\/p>\n\n\n\n

            C4.5\u5206\u7c7b\u6811\u7684\u5b9e\u8df5<\/h4>\n\n\n\n

            C4.5\u51b3\u7b56\u6811<\/a><\/p>\n\n\n\n

            C4.5\u5e76\u4e0d\u662f\u4e00\u201d\u4ef6\u201c\u7b97\u6cd5\u800c\u662f\u4e00\u201d\u5957\u201c\u7b97\u6cd5\u2014\u2014C4.5\uff0cC4.5-no-pruning\u548cC4.5-rules\u3002\u6211\u4eec\u9996\u5148\u4ecb\u7ecd\u57fa\u672c\u7684C4.5\u540e\u9762\u4ecb\u7ecd\u7279\u6b8a\u7684C4.5\u3002<\/p>\n\n\n\n

            C4.5\u4e00\u822c\u9009\u53d6Gain Ratio<\/strong> rather than Gain<\/strong>\uff0c\u7528\u6765\u7ea0\u6b63gain\u5ea6\u91cf\u503e\u5411\u4e8e\u591a\u8f93\u51fatest\u7684\u65b9\u6cd5\u3002<\/p>\n\n\n\n

            Gain Ratio<\/h5>\n\n\n\n

            From \u7ef4\u57fa\u767e\u79d1\uff1a\u5173\u4e8egain\u4e0egain ratio<\/a><\/p>\n\n\n\n

            \u200b \u53ef\u4ee5\u770b\u5230gain\u4e0egain ratio\u7684\u533a\u522b\u5728\u4e8egain ratio = gain \/ intrinsic value(\u5185\u5728\u4ef7\u503c)\u3002\u591a\u4e86\u4e00\u4e2aintrinsic value\u610f\u4e49\u5728\u4e8e\u7ea0\u6b63gain\u4f5c\u4e3atest\u7684\u5ea6\u91cf\u65f6\u4f1a\u51fa\u73b0\u7684\u4e00\u4e2a\u95ee\u9898\uff1a\u4e3e\u4e00\u4e2a\u5ba2\u6237\u7cfb\u7edf\u7684\u4f8b\u5b50\uff0c\u5982\u679c\u8981\u5bf9\u4e00\u4e2a\u5ba2\u6237\u4fe1\u606f\u6570\u636e\u5206\u7c7b\uff0c\u5176\u4e2d\u6709\u4e00\u9879\u5c5e\u6027\u662f\u6bcf\u4e2a\u5ba2\u6237\u7684\u4fe1\u7528\u5361\u53f7\uff0c\u7531\u4e8e\u8fd9\u548c\u6bcf\u4e2a\u5ba2\u6237\u662f\u4e00\u4e00\u5bf9\u5e94\u7684\uff0c\u53ef\u60f3\u800c\u77e5\uff0c\u4f7f\u7528\u8be5\u5c5e\u6027\u7684test\u5fc5\u7136\u83b7\u5f97\u6700\u5927\u7684gain\uff0c\u56e0\u4e3a\u5bf9\u6b64\u5c5e\u6027\u5206\u7c7b\u540e\uff0c\u6bcf\u4e2a\u5b50\u6811\u5bf9\u5e94\u7684\u662f\u552f\u4e00\u7684\u4e00\u4e2a\u6837\u672c\uff0c\u8fd9\u663e\u7136\u4e0d\u662f \u6211\u4eec\u5206\u7c7b\u60f3\u8981\u7684\u7ed3\u679c\uff0c\u4e5f\u4e0d\u5177\u6709\u666e\u9002\u6027\u3002\u800c\u5f53\u6309\u7167\u4fe1\u7528\u5361\u53f7\u505atest\u5206\u7c7b\u65f6\uff0cintrinsic value\u540c\u6837\u662f\u6781\u5927\u7684\uff0c\u8fd9\u53ef\u4ee5\u770b\u505a\u662f\u5404\u4e2a\u7c7b\u6570\u91cf\u5206\u5e03\u7684\u71b5\uff0c\u8fd9\u6837\u5c31\u6709\u6548\u5730\u6291\u5236\u4e86\u9009\u62e9\u4fe1\u7528\u5361\u53f7\u8fd9\u6837\u7684test\u4f5c\u4e3a\u6700\u4f73test\u3002<\/p>\n\n\n\n

            \u540c\u65f6\u6211\u4eec\u7ed9\u51faGain Ratio\u7684\u8ba1\u7b97\u65b9\u5f0f\uff1a\n$$\nGainRatio(a) = \\frac{Gain(a)}{Entropy(a)}=\\frac{\\Delta_{\\mbox{info}}}{Split~Info}\n$$<\/p>\n\n\n\n

            \u8fd9\u79cd\u60c5\u51b5\u4e0b\uff0c\u6709\u53ef\u80fd\u539f\u5148Gain\u4e2d\u662f\u6700\u4f73\u5206\u652f\u7684\u5c5e\u6027\uff0c\u6700\u7ec8\u5e76\u4e0d\u662f\u6700\u4f73\u5206\u652f\u4e86\u3002<\/p>\n\n\n\n

            \u8ba8\u8bba\u5230\u6b64\uff0c\u5e94\u5f53\u6307\u51fa\u51b3\u7b56\u6811\u5e76\u4e0d\u80fd\u4ee5\u8fd9\u79cd\u7b80\u5355\u7684\u65b9\u5f0f\u4e3a\u6240\u6709\u51b3\u7b56\u8fb9\u754c\u5efa\u6a21\u3002\u4f8b\u5982\uff0c\u5c3d\u7ba1\u5b83\u80fd\u6a21\u62df\u4efb\u4f55\u4e8c\u503c\u51fd\u6570\uff0c\u6700\u7ec8\u7684\u6811\u53ef\u80fd\u662f\u76f8\u5f53\u7684\u590d\u6742\u3002\u6bd4\u5982\u5728\u5927\u91cf\u4e8c\u503c\u5c5e\u6027\u4e0a\u5efa\u6a21XOR\u64cd\u4f5c\u3002\u5728\u8fd9\u79cd\u60c5\u51b5\u4e0b\u6bcf\u4e00\u6761\u8def\u5f84\u4e2d\u90fd\u9700\u8981\u5bf9\u6240\u6709\u5c5e\u6027\u505a\u6d4b\u8bd5\uff0c\u8fd9\u68f5\u6811\u7684\u5c3a\u5bf8\u5c06\u4f1a\u5448\u6307\u6570\u7ea7\u89c4\u6a21\u3002\u53e6\u4e00\u4e2a\u96be\u9898\u662f\u6240\u8c13\u7684\u201dm-of-n\u201c\u51fd\u6570\uff0cclass\u53ea\u4e0en\u4e2a\u5c5e\u6027\u4e2d\u7684m\u4e2a\u6709\u5173\uff0c\u4f46\u662f\u5e76\u4e0d\u6e05\u695a\u662f\u54eam\u4e2a\u5c5e\u6027\u3002\u503e\u659c\u51b3\u7b56\u6811\uff0c\u5c06\u5728\u540e\u9762\u4ecb\u7ecd\uff0c\u80fd\u591f\u514b\u670d\u8fd9\u4e9b\u7f3a\u9677\u3002\u9664\u4e86\u8fd9\u4e9b\u56f0\u96be\uff0cC4.5\u751f\u6210\u7684\u51b3\u7b56\u6811\u8fd8\u6709\u4e00\u4e2a\u95ee\u9898\u662f\u7531\u4e8e\u5728\u5c5e\u6027\u9009\u62e9\u65f6\u7684\u8d2a\u5fc3\u9009\u62e9\u5bfc\u81f4\u5b50\u6811\u7684\u91cd\u590d\u3002\u9664\u4e86\u7a77\u4e3e\u641c\u7d22\u6700\u4f73\u5c5e\u6027\u6765\u751f\u957f\u51fa\u4e00\u4e2a\u5b8c\u5168\u51b3\u7b56\u6811\uff0c\u8fd9\u4e2a\u95ee\u9898\u901a\u5e38\u522b\u65e0\u4ed6\u6cd5\u3002<\/p>\n\n\n\n

            C4.5\u5bf9ID3\u7b97\u6cd5\u7684\u6539\u8fdb:<\/h5>\n\n\n\n
            1. \u71b5\u7684\u6539\u8fdb,\u52a0\u4e0a\u4e86\u5b50\u6811\u7684\u4fe1\u606f.\n Split_Infox(X)= – SUM( (|T|\/|Ti| ) *LOG(|Ti|\/|T|))\n Gain ratio(X)= Gain(X)\/Split_Infox(X)<\/li>
            2. \u5728\u8f93\u5165\u6570\u636e\u4e0a\u7684\u6539\u8fdb.
                \n
              1. \u56e0\u7d20\u5c5e\u6027\u7684\u503c\u53ef\u4ee5\u662f\u8fde\u7eed\u91cf,C4.5\u5bf9\u5176\u6392\u5e8f\u5e76\u5206\u6210\u4e0d\u540c\u7684\u96c6\u5408\u540e\u6309\u7167ID3\u7b97\u6cd5\u5f53\u4f5c\u79bb\u6563\u91cf\u8fdb\u884c\u5904\u7406,\u4f46\u7ed3\u8bba\u5c5e\u6027\u7684\u503c\u5fc5\u987b\u662f\u79bb\u6563\u503c.<\/li>\n
              2. \u8bad\u7ec3\u4f8b\u7684\u56e0\u7d20\u5c5e\u6027\u503c\u53ef\u4ee5\u662f\u4e0d\u786e\u5b9a\u7684,\u4ee5 ? \u8868\u793a,\u4f46\u7ed3\u8bba\u5fc5\u987b\u662f\u786e\u5b9a\u7684<\/li>\n<\/ol>\n<\/li>
              3. \u5bf9\u5df2\u751f\u6210\u7684\u51b3\u7b56\u6811\u8fdb\u884c\u88c1\u526a,\u51cf\u5c0f\u751f\u6210\u6811\u7684\u89c4\u6a21<\/li><\/ol>\n\n\n\n
                \u526a\u679dTree Pruning<\/h5>\n\n\n\n

                \u6709\u591a\u91cd\u526a\u679d\u7684\u7b97\u6cd5\uff0c<\/p>\n\n\n\n

                1. cost-complexity pruning<\/li>
                2. Reduced error pruning<\/li>
                3. Pessimistic pruning<\/li><\/ol>\n\n\n\n

                  \u526a\u679d\u65b9\u6cd5\uff1a<\/p>\n\n\n\n

                  1. pre-pruning. Has some drawbacks: A seemingly worthless split might lead to a very\ngood split below it (short-sighted). <\/li>
                  2. post-pruning. Preferred approach.<\/li><\/ol>\n\n\n\n