{"id":492,"date":"2012-11-29T20:46:00","date_gmt":"2012-11-29T12:46:00","guid":{"rendered":"http:\/\/note.systw.net\/note\/?p=492"},"modified":"2023-11-02T20:47:50","modified_gmt":"2023-11-02T12:47:50","slug":"decision-tree","status":"publish","type":"post","link":"https:\/\/systw.net\/note\/archives\/492","title":{"rendered":"Decision Tree"},"content":{"rendered":"\n

\u6c7a\u7b56\u6a39<\/strong>
\u61c9\u7528:
\u3000\u5e38\u7528\u5728\u5206\u985e,\u4e5f\u5c31\u662f\u5148\u5f9e\u8cc7\u6599\u4e2d\u627e\u51fa\u898f\u5247,\u5728\u5229\u7528\u8a72\u898f\u5247\u5f9e\u5176\u4ed6\u8cc7\u6599\u4e2d\u627e\u51fa\u7d50\u679c 
\u5e38\u898b\u65b9\u6cd5: 
\u30001.C3 and C4.5
\u30002.gini index:\u53ea\u53ef\u8655\u7406\u5c6c\u6027\u50c52\u7a2e\u985e\u5225\u7684\u8cc7\u6599,\u8d85\u904e\u8981\u9032\u884c\u985e\u5225\u7684\u5408\u4f75
\u30003.\u5176\u4ed6\u65b9\u6cd5\u6709CHAID,C-SEP,G-statistics,MDL<\/p>\n\n\n\n

\u6982\u5ff5<\/strong>
\u7531\u4e0a\u800c\u4e0b\u905e\u8ff4\u7684\u5206\u88c2\u548c\u514b\u670d\u7684\u65b9\u6cd5
\u505c\u6b62\u689d\u4ef6<\/strong>
1\u6240\u6709\u7d50\u679c\u90fd\u5c6c\u65bc\u540c\u4e00\u985e\u6642,ex:\u5168\u90e8\u7684\u7d50\u679c\u90fd\u662fyes,\u800c\u6c92\u6709no\u6642,\u6216\u76f8\u53cd
2\u5df1\u6c92\u6709\u5c6c\u6027\u53ef\u4ee5\u505a\u5206\u88c2\u6642,\u5176\u9918\u7d50\u679c\u4ee5\u591a\u6578\u7d50\u679c\u4ee3\u8868\u9019\u90e8\u4efd\u7684\u5168\u9ad4
3\u5df1\u6c92\u6709\u8cc7\u6599,\u4ee5\u591a\u6578\u7d50\u679c\u4ee3\u8868\u9019\u90e8\u4efd\u7684\u5168\u9ad4
\u9650\u5236<\/strong>
\u82e5\u7522\u751f\u7684\u5206\u652f\u592a\u591a\u5247\u4e4b\u5f8c\u9032\u884c\u5206\u985e\u9810\u6e2c\u6642\u6548\u679c\u6703\u8b8a\u5dee
\u53ef\u4f7f\u7528\u4ee5\u4e0b\u5169\u65b9\u6cd5\u89e3\u6c7a
\u3000prepruning:\u6a39\u5728\u6210\u9577\u6642\uff0c\u82e5\u8d85\u904e\u9580\u6abb\u503c\u5247\u7acb\u5373\u526a\u6389
\u3000postpruning:\u6a39\u6210\u9577\u5b8c\u5f8c\uff0c\u5728\u628a\u4e0d\u5fc5\u8981\u7684\u5206\u652f\u526a\u6389
continuous value\u8655\u7406\u65b9\u5f0f<\/strong>
\u4e3b\u8981\u6709\u5169\u7a2e\u505a\u6cd5
1,\u81ea\u884c\u5b9a\u7fa9continuous value\u5404\u7bc4\u570d\u5c6c\u65bc\u4e00\u500b\u503c
ex:1-20year\u5b9a\u7fa9\u70bayoung,60-90year\u5b9a\u7fa9\u70baolder
2,\u8a08\u7b97\u5404\u7d50\u679c\u7684gain,\u7b49\u540c\u5404\u7d50\u679c\u90fd\u6383\u63cf\u4e00\u6b21,\u5f88\u82b1\u6642\u9593
ex:value\u670923,25,28,31
\u5247\u5148\u8a08\u7b97\u5c0f\u65bc\u53ca\u5927\u65bc(23+25)\/2\u7684\u589e\u76ca,\u4e00\u76f4\u7b97\u5230\u5c0f\u65bc\u53ca\u5927\u65bc(28+31)\/2\u7684\u589e\u76ca,
\u770b\u90a3\u4e00\u7a2e\u589e\u76ca\u7d50\u679c\u8f03\u597d,\u5247\u9078\u90a3\u500b\u7d44\u5408<\/p>\n\n\n\n

C3\u7684\u8a08\u7b97\u65b9\u5f0f<\/strong>
1
info(D)= -segma( i , Pi*log2(Pi) )
i=class\u5c6c\u6027\u4e2d\u7684\u4e0d\u540c\u503c,ex:{yes,no},{high,medium,low}
Pi=class\u5c6c\u6027\u4e2d\u5404\u503c\u5728\u8a72class\u767c\u751f\u7684\u6a5f\u7387
2
info_a(D)=segma( j , Dj\/D*info(Dj) )
gain(a)=info(D)-info_a(D)
3
new node = max(gain_all)
\u6839\u64da\u8a72\u5c6c\u6027\u7684\u503c\u7522\u751f\u5206\u652f
4
\u5404\u5206\u652f\u56de\u5230\u6b65\u9a5f1\u9032\u884c\u8a08\u7b97
ps
\u5728c4.5\u6642,\u4ee5gainratio\u4ee3\u66ffgain,\u9019\u53ef\u63d0\u6607attribute selection\u7684\u7d50\u679c
gainratio(a)=gain(a)\/splitinfo(a)
splitinfo(a)=segma_j( j , Dj\/D*log2(Dj\/D) )<\/p>\n\n\n\n


gini index\u7684\u8a08\u7b97\u65b9\u5f0f<\/strong>
1
gini(D)=1-sigma( i ,Pi^2)
2
gini_a(D)=D1\/D*gini(D1)+D2\/D*gini(D2)
ps:\u56e0\u70bagini index\u53ea\u63a5\u53d7\u5169\u500b\u985e\u5225,\u82e5\u51fa\u73feD3\u6642,\u9700\u548cD1\u6216D2\u5408\u4f75
gini(a)=gini(D)-gini_a(D)
3
new node = min(gini_all)
\u6839\u64da\u8a72\u5c6c\u6027\u7684\u503c\u7522\u751f\u5206\u652f
4
\u5404\u5206\u652f\u56de\u5230\u6b65\u9a5f1\u9032\u884c\u8a08\u7b97<\/p>\n\n\n\n

################################################################<\/p>\n\n\n\n

\u7bc4\u4f8b <\/strong> <\/p>\n\n\n\n

ex:<\/p>\n\n\n\n

rid <\/td>flow <\/td>packet <\/td>student <\/td>over1gb <\/td>class:is infected? <\/td><\/tr>
 1<\/td> low<\/td>high<\/td>no<\/td>no <\/td>no <\/td><\/tr>
 2<\/td> low<\/td>high<\/td>no <\/td>yes <\/td>no <\/td><\/tr>
 3<\/td> medium<\/td>high <\/td>no <\/td>no <\/td>yes <\/td><\/tr>
 4<\/td> high<\/td>medium <\/td>no <\/td>no <\/td>yes <\/td><\/tr>
 5<\/td> high<\/td>low <\/td>yes <\/td>no <\/td>yes <\/td><\/tr>
 6<\/td> high<\/td>low <\/td>yes <\/td>yes <\/td>no <\/td><\/tr>
 7<\/td> medium<\/td>low <\/td>yes <\/td>yes <\/td>yes <\/td><\/tr>
 8<\/td> low<\/td>medium <\/td>no <\/td>no <\/td>no <\/td><\/tr>
 9<\/td> low<\/td>low <\/td>yes <\/td>no <\/td>yes <\/td><\/tr>
 10<\/td> high<\/td>medium <\/td>yes <\/td>no <\/td>yes <\/td><\/tr>
 11<\/td> low<\/td>medium <\/td>yes <\/td>yes <\/td>yes <\/td><\/tr>
 12<\/td> medium<\/td>medium <\/td>no <\/td>yes <\/td>yes <\/td><\/tr>
 13<\/td> medium<\/td>high <\/td>yes <\/td>no <\/td>yes <\/td><\/tr>
 14<\/td> high<\/td>medium <\/td>no <\/td>yes <\/td>no <\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

\u4f7f\u7528C3<\/p>\n\n\n\n

1
P1=yes\u6a5f\u7387=9\/14
P2=no\u6a5f\u7387=5\/14
info(D)= ( -P1*log2(P1)) + ( – P2*log2(P2))
= ( -9\/14*log2(9\/14)) + ( -5\/14*log2(5\/14) )
=0.94<\/p>\n\n\n\n

2
info_flow(D)=D1\/D*( info(D1)) + D2\/D*( info(D2)) + D3\/D*( info(D3))
=D1\/D*( -P1*log2(P1) – P2*log2(P2) )
+ D2\/D*( -P1*log2(P1) – P2*log2(P2) )
+ D3\/D*( -P1*log2(P1) – P2*log2(P2) )
=5\/14*( -2\/5*log2(2\/5) -3\/5*log2(3\/5) )
+ 4\/14*( -4\/4*log2(4\/4) -0\/4*log2(0\/4) )
+ 5\/14*( -3\/5*log2(3\/5) -2\/5*log2(2\/5) )
=0.694
gain(flow)=0.246=0.940-0.694=info(D)-info_flow(D)
similarly
gain(packet)=0.029
gain(student)=0.151
gain(over1gb)=0.048
3
max(gain_all)=gain(flow)
attribute flow become root node
\u5171\u6839\u64daflow\u7684\u503c\u5206\u62103\u500b\u5206\u652f,\u5206\u5225\u662fflow_low,flow_medium,flow_high<\/strong><\/p>\n\n\n\n

ps:
\u82e5\u4f7f\u7528C4.5
splitpacket(packet)=0.926= -4\/14*log2(4\/14) -6\/14*log2(6\/14) -4\/14*log2(4\/14)
gainratio(packet)=0.029\/0.926=0.031
splitpacket(flow)=1.577= -5\/14*log2(5\/14) -4\/14*log2(4\/14) -5\/14*log2(5\/14)
gainratio(flow)=0.246\/1.577=0.156
similarly
gainratio(student)=
gainratio(over1gb)=
\u8a72\u7bc4\u4f8b\u7d50\u679c\u76f8\u540c
max(gain_all)=gain(flow)
attribute flow become root node<\/p>\n\n\n\n

ps:
\u82e5\u4f7f\u7528gini index
1
gini(D)=1-(9\/14)^2-(5\/14)^2=0.459
2
gini_student(D)=0.367
=7\/14*gini(D1) + 7\/14*gini(D2)
=7\/14*(1-(6\/7)^2 -(1\/7)^2 ) + 7\/14*(1-(3\/7)^2-(4\/7)^2)
gini_packet(D)=0.45
= gini_packet{low,medium} + gini_packet{high} \/\/\u6709\u4e09\u7a2e\u503c\u6642\u9700\u5408\u4f75\u90e8\u4efd\u7684\u503c,\u8b8a\u62102\u7a2e\u503c
=10\/14*gini(D1) + 4\/14*gini(D2)
=10\/14*( 1-(6\/10)^2-(4\/10)^2 ) + 4\/14*( 1-(1\/4)^2-(3\/4)^2 )
similarly
gini_over1gb(D)=0.429
gini_flow(D)=0.375
3
min(gini_all)=gini(packet)=gini(D)-gini_packet(D)=0.459-0.45
attribute packet become root node
\u4e26\u6839\u64dapacket\u7684\u503c\u5206\u62103\u500b\u5206\u652f,\u5206\u5225\u662fpacket_low,packet_medium,packet_high
\u6b64\u7d50\u679c\u8207C3\u548cC4.5\u4e0d\u540c<\/p>\n\n\n\n

……………………….. <\/p>\n\n\n\n


\u5206\u652fflow_low<\/strong>,\u8a72\u5206\u652f\u7684class\u4e0d\u540c,\u56e0\u6b64\u5728\u9032\u884c\u540c\u6a23\u7684\u8a08\u7b97<\/p>\n\n\n\n

 flow<\/strong><\/td>packet <\/td>student <\/td>over1gb <\/td>class: is infected? <\/td><\/tr>
 low<\/strong><\/td>high <\/td>no <\/td>no <\/td>no <\/td><\/tr>
 low<\/strong><\/td>high <\/td>no <\/td>yes <\/td>no <\/td><\/tr>
 low<\/strong><\/td>medium <\/td>no <\/td>no <\/td>no <\/td><\/tr>
 low<\/strong><\/td>low <\/td>yes <\/td>no <\/td>yes <\/td><\/tr>
 low<\/strong><\/td>medium <\/td>yes <\/td>yes <\/td>yes <\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

1
info(D1)=\u540c\u4e0a=5\/14*( -2\/5*log2(2\/5) -3\/5*log2(3\/5) ) =0.972
2
info_packet(D1)=D1\/D*( info(D1 )) + D2\/D*( info(D2 )) + D3\/D*( info(D3 ))
=D1\/D*( P1*log2(P1) – P2*log2(P2) )
+ D2\/D*( P1*log2(P1) – P2*log2(P2) )
+ D3\/D*( P1*log2(P1) – P2*log2(P2) )
=1\/5*( -1\/1*log2(1\/1) -0\/1*log2(0\/1) )
+ 2\/5*( -1\/2*log2(1\/2) -1\/2*log2(1\/2) )
+ 2\/5*( -0\/2*log2(0\/2) -2\/2*log2(2\/2) )
=0+2\/5+0
=0.4
gain_D1(packet)=0.972-0.4=0.572
similarly
gain_D1(student)=0.972
gain_D1(over1gb)=
3
max(gain_all)=gain_D1(student)=0.972
attribute student become node
\u5171\u6839\u64dastudent\u7684\u503c\u5206\u62102\u500b\u5206\u652f,\u5206\u5225\u662fstudent_yes,student_no<\/p>\n\n\n\n

\u5206\u652fflow_low\u7684\u5206\u652fstudent_yes,\u8a72\u5206\u652f\u7684class\u5168\u76f8\u540c,\u56e0\u6b64\u8a72\u5206\u652f\u5230\u6b64\u7d50\u675f<\/p>\n\n\n\n

 flow<\/strong><\/td> packet<\/td> student<\/strong><\/td> over1gb<\/td> class:is infected?<\/td><\/tr>
 low<\/strong><\/td>low <\/td>yes<\/strong> <\/td>no <\/td>yes <\/td><\/tr>
 low<\/strong><\/td>medium <\/td>yes <\/strong><\/td>yes <\/td>yes <\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

\u5206\u652fflow_low\u7684\u5206\u652fstudent_no,\u8a72\u5206\u652f\u7684class\u5168\u76f8\u540c,\u56e0\u6b64\u8a72\u5206\u652f\u5230\u6b64\u7d50\u675f<\/p>\n\n\n\n

flow<\/strong> <\/td>packet <\/td>student<\/strong> <\/td>over1gb <\/td>class:is infected <\/td><\/tr>
 low<\/strong><\/td>high <\/td>no <\/strong><\/td>no <\/td>no <\/td><\/tr>
 low<\/strong><\/td>high <\/td>no <\/strong><\/td>yes <\/td>no <\/td><\/tr>
 low<\/strong><\/td>medium <\/td>no<\/strong> <\/td>no <\/td>no  <\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

…………………………….. <\/p>\n\n\n\n

\u5206\u652fflow_medium<\/strong>,\u8a72\u5206\u652f\u7684class\u5168\u76f8\u540c,\u56e0\u6b64\u8a72\u5206\u652f\u5230\u6b64\u7d50\u675f<\/p>\n\n\n\n

 flow<\/strong><\/td>packet <\/td>student <\/td>over1gb <\/td>class:is infected <\/td><\/tr>
 medium<\/strong><\/td>high <\/td>no <\/td>no <\/td>yes <\/td><\/tr>
 medium<\/strong><\/td>low <\/td>yes <\/td>yes <\/td>yes <\/td><\/tr>
 medium<\/strong><\/td>medium <\/td>no <\/td>yes <\/td>yes <\/td><\/tr>
 medium<\/strong><\/td>high <\/td>yes <\/td>no <\/td>yes <\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

………………………………. <\/p>\n\n\n\n

\u5206\u652fflow_high<\/strong>,\u8a72\u5206\u652f\u7684class\u4e0d\u540c,\u56e0\u6b64\u5728\u9032\u884c\u540c\u6a23\u7684\u8a08\u7b97<\/p>\n\n\n\n

flow<\/strong> <\/td>packet <\/td>student <\/td>over1gb <\/td>class:is infected <\/td><\/tr>
 high<\/strong><\/td>medium <\/td>no <\/td>no <\/td>yes <\/td><\/tr>
 high<\/strong><\/td>low <\/td>yes <\/td>no <\/td>yes <\/td><\/tr>
 high<\/strong><\/td>low <\/td>yes <\/td>yes <\/td>no <\/td><\/tr>
 high<\/strong><\/td>medium <\/td>yes <\/td>no <\/td>yes <\/td><\/tr>
 high<\/strong><\/td>medium <\/td>no <\/td>yes <\/td>no <\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

1
info(D3)=\u540c\u4e0a=5\/14*( -2\/5*log2(2\/5) -3\/5*log2(3\/5) ) =0.972
2
gain_D3(packet)=
gain_D3(student)=
gain_D3(over1gb)=0.972
3
max(gain_all)=gain_D3(over1gb)=0.972
attribute over1gb become node
\u4e26\u6839\u64daover1gb\u7684\u503c\u5206\u62102\u500b\u5206\u652f,\u5206\u5225\u662fover1gb_yes,over1gb_no<\/p>\n\n\n\n

\u5206\u652fflow_high\u7684\u5206\u652fover1gb_no,\u8a72\u5206\u652f\u7684class\u5168\u76f8\u540c,\u56e0\u6b64\u8a72\u5206\u652f\u5230\u6b64\u7d50\u675f<\/p>\n\n\n\n

flow <\/strong><\/td>packet <\/td>student <\/td>over1gb<\/strong> <\/td>class:is infected <\/td><\/tr>
 high<\/strong><\/td>medium <\/td>no <\/td>no <\/strong><\/td>yes <\/td><\/tr>
 high<\/strong><\/td>low <\/td>yes <\/td>no <\/strong><\/td>yes <\/td><\/tr>
 high<\/strong><\/td>medium <\/td>yes <\/td>no<\/strong> <\/td>yes <\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

\u5206\u652fflow_high\u7684\u5206\u652fover1gb_yes,\u8a72\u5206\u652f\u7684class\u5168\u76f8\u540c,\u56e0\u6b64\u8a72\u5206\u652f\u5230\u6b64\u7d50\u675f<\/p>\n\n\n\n

flow<\/strong> <\/td>packet <\/td>student <\/td>over1gb<\/strong> <\/td>class:is infected <\/td><\/tr>
 high<\/strong><\/td>low <\/td>yes <\/td>yes <\/strong><\/td>no <\/td><\/tr>
 high<\/strong><\/td>medium <\/td>no <\/td>yes <\/strong><\/td>no  <\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

……………………………<\/p>\n\n\n\n


\u7d50\u679c:
infected signature\u5982\u4e0b
1.flow:low , student:yes
2.flow:medium
3.flow:high , over1gb:yes<\/p>\n","protected":false},"excerpt":{"rendered":"

\u6c7a\u7b56\u6a39\u61c9\u7528:\u3000\u5e38\u7528\u5728\u5206\u985e,\u4e5f\u5c31\u662f\u5148\u5f9e\u8cc7\u6599\u4e2d\u627e\u51fa\u898f\u5247,\u5728\u5229\u7528\u8a72 …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"","fifu_image_alt":"","_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[13],"tags":[],"class_list":["post-492","post","type-post","status-publish","format-standard","hentry","category-dataanalysis"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/492","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/comments?post=492"}],"version-history":[{"count":0,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/492\/revisions"}],"wp:attachment":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/media?parent=492"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/categories?post=492"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/tags?post=492"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}