📄 id3算法.java
字号:
From: <由 Windows Internet Explorer 7 保存>
Subject: =?gb2312?B?vvay38r3SUQzy+O3qCAtIMTHw8C/y9DHyMu1xLzSsK6yqb/NIC0gSg==?=
=?gb2312?B?YXZhRXllvLzK9c341b4=?=
Date: Wed, 21 May 2008 22:59:29 +0800
MIME-Version: 1.0
Content-Type: multipart/related;
type="text/html";
boundary="----=_NextPart_000_0000_01C8BB96.5312AB00"
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2962
This is a multi-part message in MIME format.
------=_NextPart_000_0000_01C8BB96.5312AB00
Content-Type: text/html;
charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Location: http://leon-a.javaeye.com/blog/178585
=EF=BB=BF<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" =
"http://www.w3c.org/TR/1999/REC-html401-19991224/loose.dtd">
<HTML dir=3Dltr xml:lang=3D"zh-CN"=20
xmlns=3D"http://www.w3.org/1999/xhtml"><HEAD><TITLE>=E5=86=B3=E7=AD=96=E6=
=A0=91ID3=E7=AE=97=E6=B3=95 - =
=E9=82=A3=E7=BE=8E=E5=85=8B=E6=98=9F=E4=BA=BA=E7=9A=84=E5=AE=B6=E7=88=B1=E5=
=8D=9A=E5=AE=A2 - JavaEye=E6=8A=80=E6=9C=AF=E7=BD=91=E7=AB=99</TITLE>
<META http-equiv=3DContent-Type content=3D"text/html; charset=3DUTF-8">
<META=20
content=3D" package graph; import java.util.ArrayList; =
import java.util.List; import java.util.TreeSet; /** =
* =E5=86=B3=E7=AD=96=E6=A0=91=E7=9A=84ID3=E7=AE=97=E6=B3=95 * =
=E5=8F=82=E7=85=A7=E5=AE=9E=E7=8E=B0http://www.blog.edu.cn/user2/huangbo9=
2 ..."=20
name=3Ddescription>
<META content=3D" =E5=86=B3=E7=AD=96=E6=A0=91ID3=E7=AE=97=E6=B3=95" =
name=3Dkeywords><LINK href=3D"/images/favicon.ico"=20
type=3Dimage/x-icon rel=3D"shortcut icon"><LINK =
title=3D=E9=82=A3=E7=BE=8E=E5=85=8B=E6=98=9F=E4=BA=BA=E7=9A=84=E5=AE=B6=E7=
=88=B1=E5=8D=9A=E5=AE=A2 href=3D"/rss"=20
type=3Dapplication/rss+xml rel=3Dalternate><LINK media=3Dscreen=20
href=3D"http://www.javaeye.com/stylesheets/blog.css?1211351677" =
type=3Dtext/css=20
rel=3Dstylesheet><LINK media=3Dscreen=20
href=3D"http://www.javaeye.com/stylesheets/themes/blog/blue.css?120045187=
6"=20
type=3Dtext/css rel=3Dstylesheet>
<SCRIPT =
src=3D"http://www.javaeye.com/javascripts/application.js?1210060270"=20
type=3Dtext/javascript></SCRIPT>
<LINK media=3Dscreen=20
href=3D"http://www.javaeye.com/javascripts/syntaxhighlighter/SyntaxHighli=
ghter.css?1201588027"=20
type=3Dtext/css rel=3Dstylesheet>
<SCRIPT=20
src=3D"http://www.javaeye.com/javascripts/syntaxhighlighter/shCoreCommon.=
js?1203397332"=20
type=3Dtext/javascript></SCRIPT>
<SCRIPT =
src=3D"http://www.javaeye.com/javascripts/se_hilite.js?1203397332"=20
type=3Dtext/javascript></SCRIPT>
<STYLE>DIV#main {
BORDER-TOP-WIDTH: 0px; PADDING-RIGHT: 0px; PADDING-LEFT: 0px; =
BORDER-LEFT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; PADDING-BOTTOM: 0px; =
WIDTH: 740px; PADDING-TOP: 0px; BACKGROUND-COLOR: transparent; =
BORDER-RIGHT-WIDTH: 0px
}
</STYLE>
<LINK media=3Dscreen=20
href=3D"http://www.javaeye.com/javascripts/editor/css/ui.css?1205805545" =
type=3Dtext/css rel=3Dstylesheet>
<SCRIPT =
src=3D"http://www.javaeye.com/javascripts/editor/compress.js?1209370586" =
type=3Dtext/javascript></SCRIPT>
<META content=3D"MSHTML 6.00.5730.11" name=3DGENERATOR></HEAD>
<BODY>
<DIV id=3Dheader>
<DIV id=3Dsite_logo><A href=3D"http://www.javaeye.com/blogs"><IMG=20
title=3DJavaEye-=E6=9C=80=E6=A3=92=E7=9A=84=E8=BD=AF=E4=BB=B6=E5=BC=80=E5=
=8F=91=E4=BA=A4=E6=B5=81=E7=A4=BE=E5=8C=BA alt=3DJavaEye3.0=20
src=3D"http://www.javaeye.com/images/logo_small.gif?1192372128"></A></DIV=
>
<UL id=3Duser_nav>
<LI class=3Dlast><A =
href=3D"http://leon-a.javaeye.com/index/help">=E5=B8=AE=E5=8A=A9</A> =
</LI>
<LI><A =
href=3D"http://leon-a.javaeye.com/search">=E6=90=9C=E7=B4=A2</A> </LI>
<LI><A =
href=3D"http://leon-a.javaeye.com/signup">=E6=B3=A8=E5=86=8C</A> </LI>
<LI><A href=3D"http://leon-a.javaeye.com/login">=E7=99=BB=E5=BD=95</A> =
</LI>
<LI =
class=3Dhighlight><SPAN>=E6=82=A8=E8=BF=98=E6=B2=A1=E6=9C=89=E7=99=BB=E5=BD=
=95 !</SPAN> </LI></UL></DIV>
<DIV id=3Dpage>
<DIV class=3Dclearfix id=3Dbranding>
<DIV id=3Dblog_name>
<H1><A =
href=3D"http://leon-a.javaeye.com/">=E9=82=A3=E7=BE=8E=E5=85=8B=E6=98=9F=E4=
=BA=BA=E7=9A=84=E5=AE=B6=E7=88=B1=E5=8D=9A=E5=AE=A2</A></H1></DIV>
<DIV id=3Dblog_preview></DIV>
<DIV id=3Dblog_domain>=E6=B0=B8=E4=B9=85=E5=9F=9F=E5=90=8D <A=20
href=3D"http://leon-a.javaeye.com/">http://leon-a.javaeye.com/</A></DIV><=
/DIV>
<DIV class=3Dclearfix id=3Dcontent>
<DIV id=3Dmain>
<DIV class=3Dblog_main>
<DIV id=3Dblog_nav>
<DIV class=3Ddigg id=3Db178585>
<H3><A class=3Ddigg onclick=3D"digg_blog(178585);return false;"=20
href=3D"http://leon-a.javaeye.com/blog/178585#">0=E9=A1=B6</A><BR><A =
class=3Dbury=20
onclick=3D"bury_blog(178585);return false;"=20
href=3D"http://leon-a.javaeye.com/blog/178585#">0=E8=B8=A9</A></H3></DIV>=
<DIV id=3Dpre_next><A class=3Dnext =
href=3D"http://leon-a.javaeye.com/blog/181958">=E6=95=B0=E6=8D=AE=E6=8C=96=
=E6=8E=98=20
=E5=86=B3=E7=AD=96=E6=A0=91ID3=E7=AE=97=E6=B3=95=E5=8E=9F=E7=90=86</A> | =
<A class=3Dpre=20
href=3D"http://leon-a.javaeye.com/blog/163722">ext2.0 =
=E7=9A=84XMLWriter</A> </DIV></DIV>
<DIV class=3Dblog_title>
<DIV class=3Ddate><SPAN class=3Dyear>2008</SPAN><SPAN =
class=3Dsep_year>-</SPAN><SPAN=20
class=3Dmonth>04</SPAN><SPAN class=3Dsep_month>-</SPAN><SPAN=20
class=3Dday>01</SPAN></DIV>
<H3><A =
href=3D"http://leon-a.javaeye.com/blog/178585">=E5=86=B3=E7=AD=96=E6=A0=91=
ID3=E7=AE=97=E6=B3=95</A></H3></DIV>
<DIV class=3Dblog_content><PRE class=3Djava name=3D"code">package graph; =
=20
=20
import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet; =20
=20
/** =20
* =E5=86=B3=E7=AD=96=E6=A0=91=E7=9A=84ID3=E7=AE=97=E6=B3=95 =20
* =
=E5=8F=82=E7=85=A7=E5=AE=9E=E7=8E=B0http://www.blog.edu.cn/user2/huangbo9=
29/archives/2006/1533249.shtml =20
* @author Leon.Chen =20
*/ =20
public class DTree { =20
=20
/** =20
* root =20
*/ =20
TreeNode root; =20
=20
/** =20
* =E5=8F=AF=E8=A7=81=E6=80=A7=E6=95=B0=E7=BB=84 =20
*/ =20
private static boolean[] visable; =20
=20
private Object[] array; =20
=20
private int index;
=20
/** =20
* @param args =20
*/ =20
@SuppressWarnings("boxing") =20
public static void main(String[] args) { =20
//=E5=88=9D=E5=A7=8B=E6=95=B0=E6=8D=AE =20
Object[] array =3D new Object[] { =20
new String[]{ "Sunny" ,"Hot" ,"High" =
,"Weak" ,"No" }, =20
new String[]{ "Sunny" ,"Hot" ,"High" =
,"Strong" ,"No" }, =20
new String[]{ "Overcast" ,"Hot" ,"High" =
,"Weak" ,"Yes"}, =20
new String[]{ "Rain" ,"Mild" ,"High" =
,"Weak" ,"Yes"}, =20
new String[]{ "Rain" ,"Cool" ,"Normal" =
,"Weak" ,"Yes"}, =20
new String[]{ "Rain" ,"Cool" ,"Normal" =
,"Strong" ,"No" }, =20
new String[]{ "Overcast" ,"Cool" ,"Normal" =
,"Strong" ,"Yes"}, =20
new String[]{ "Sunny" ,"Mild" ,"High" =
,"Weak" ,"No" }, =20
new String[]{ "Sunny" ,"Cool" ,"Normal" =
,"Weak" ,"Yes"}, =20
new String[]{ "Rain" ,"Mild" ,"Normal" =
,"Weak" ,"Yes"}, =20
new String[]{ "Sunny" ,"Mild" ,"Normal" =
,"Strong" ,"Yes"}, =20
new String[]{ "Overcast" ,"Mild" ,"High" =
,"Strong" ,"Yes"}, =20
new String[]{ "Overcast" ,"Hot" ,"Normal" =
,"Weak" ,"Yes"}, =20
new String[]{ "Rain" ,"Mild" ,"High" =
,"Strong" ,"No" }, =20
}; =20
=20
DTree tree =3D new DTree(); =20
tree.create(array,4);
}=20
=20
public void create(Object[] array,int index){
this.array =3D array;
init(array,index);
createDTree(array);
printDTree(root);
}
=20
public Object[] getMaxGain(Object[] array){ =20
Object[] result =3D new Object[2]; =20
double gain =3D 0; =20
int index =3D 0;
=20
for(int i=3D0;i<visable.length;i++){ =20
if(!visable[i]){ =20
double value =3D gain(array,i); =20
if(gain < value){ =20
gain =3D value; =20
index =3D i; =20
} =20
} =20
} =20
result[0] =3D gain; =20
result[1] =3D index; =20
visable[index] =3D true; =20
return result; =20
} =20
=20
public void createDTree(Object[] array) { =20
Object[] maxgain =3D getMaxGain(array); =20
if (root =3D=3D null) { =20
root =3D new TreeNode(); =20
root.parent =3D null; =20
root.parentArrtibute =3D null; =20
root.arrtibutes =3D getArrtibutes(((Integer) =
maxgain[1]).intValue()); =20
root.nodeName =3D getNodeName(((Integer) =
maxgain[1]).intValue()); =20
root.childNodes =3D new TreeNode[root.arrtibutes.length];
insertTree(array,root);
}
} =20
=20
public void insertTree(Object[] array,TreeNode parentNode){
String[] arrtibutes =3D parentNode.arrtibutes;
for(int i=3D0;i<arrtibutes.length;i++){
Object[] pickArray =3D =
pickUpAndCreateArray(array,arrtibutes[i],getNodeIndex(parentNode.nodeName=
));
Object[] info =3D getMaxGain(pickArray);
double gain =3D ((Double)info[0]).doubleValue();
if(gain !=3D 0){
int index =3D ((Integer) info[1]).intValue();
System.out.println("gain =3D "+gain+" ,node name =3D =
"+getNodeName(index));
TreeNode currentNode =3D new TreeNode();
currentNode.parent =3D parentNode;
currentNode.parentArrtibute =3D arrtibutes[i];
currentNode.arrtibutes =3D getArrtibutes(index);
currentNode.nodeName =3D getNodeName(index);
currentNode.childNodes =3D new =
TreeNode[currentNode.arrtibutes.length];
parentNode.childNodes[i] =3D currentNode;
insertTree(pickArray,currentNode);
}else {
TreeNode leafNode =3D new TreeNode();
leafNode.parent =3D parentNode;
leafNode.parentArrtibute =3D arrtibutes[i];
leafNode.arrtibutes =3D new String[0];
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -