C 4.5 Source code Pt.3 ISL / 강한솔
2019-04-10 Index Tree structure Build.h Tree.h St-thresh.h 2
Tree structure *Concpets : Node, Branch, Leaf, Subtree, Attribute, Attribute Value, Class Play, Don't Play. outlook: sunny, overcast, rain. temperature: continuous. humidity: continuous. windy: true, false. <File Format> short NodeType; // 0=leaf 1=branch 2=cut 3=subset ClassNo Leaf; // 현재노드에서평가하는클래스인덱스 ItemCount Items, // 현재노드에서의항목수 *ClassDist, // 현재노드에서평가하는클래스의수 Errors; // 현재노드에서의에러수 Attribute Tested; // 현재테스트하고있는속성의인덱스 short Forks; // 현재노드에서 branch 수 float Cut, //threshold 값 Lower, // 낮은 threshold Upper; // 높은 threshold Set *Subset; // 명목형속성의 subset Tree *Branch; //Branch[x] subtree집합 <Decision Tree> 3 <Tree Structure>
Build.h void InitialiseTreeData() 트리작성과관련된메모리를할당한다. void InitialiseWeight() 가중치를 1로초기화한다. Tree FormTree(ItemNo Fp, ItemNo Lp) Decision tree를만들어준다. ItemNo Group (DiscrValue V, ItemNo Fp, IemNo Lp, Tree TestNode) 서로연관성있는항목끼리그룹화시켜준다. 4
Build.h ItemCount CountItems(ItemNo Fp, ItemNo Lp) 가중치를둬서항목들의개수를구한다. void Swap (ItemNo a, ItemNo b) a 인덱스를가지는항목과 b 인덱스를가지는항목을바꾼다. 5
Build.h Tree FormTree(ItemNo Fp, ItemNo Lp) 현재노드에서항목수저장 Gain 값을크게가지는속성을찾음 (BestAtt) Subset 여부에따라 Subset 테스트 현재노드에서가장많은클래스인덱스저장 속성에따라 Subset 여부에따라 연속형속성평가 Subset 속성평가 명목형속성평가 속성에따라 해당노드에서의 Branch(Subtree) 구하는과정반복 Leaf 로처리 연속형속성테스트 F T 명목형속성테스트 unknown 속성의개수를구하고 unknown rate 계산 평가하고자하는속성을모으고개수파악 속성개수 >=unknown 6
Build.h ItemNo Group (DiscrValue V, ItemNo Fp, IemNo Lp, Tree TestNode) Att=tested V? ==0 NodeType 에따라 >=1 NodeType 에따라 1,3=branch, subset 해당속성값이 unknown? 2=cut 해당속성값이 unknown? 해당속성값이 V 와일치? 1=branch 2=cut 3=subset 해당속성값 <=thresh? subset 끼리? swap 을통해모음 swap 을통해모음 swap 을통해모음 swap 을통해모음 swap 을통해모음 모인개수반환 7
Tree.h void PrintTree(Tree T) Decision Tree를출력한다. void Show(Tree T, short Sh) PrtintTree에서호출되는함수로, 실질적인출력하는역할 (leaf) 을한다. void ShowBranch(short Sh, Tree T, DiscrValue v) Show에서호출되는함수로 Branch를출력하는함수다 short MaxLine(Tree St) leaf가없는하위 subtree의한줄의최대크기를알려주는함수다. 8
Tree.h void Indent(short Sh, char *Mark) 들여쓰기해주는함수로 branch를가시적으로나타내기위해사용된다. void SaveTree(Tree T, String Extension) OutTree를호출해 Decision Tree를저장하는함수다. void OutTree(Tree T) Tree를 char 형태의데이터로저장하는함수다.( 바이너리파일과흡사한형태 ) Tree GetTree(String Extension) SaveTree와반대로 InTree를호출해 Decision Tree를읽어오는함수다. 9
Tree.h Tree InTree() OutTree와반대로 char형태로저장된 Tree를읽어오는형태의함수다. void StreamOut(String s, int n) OutTree에서사용되는함수로 char형태로저장한다. void StreamIn(String s, int n) InTree에서사용되는함수로 char형태로저장된형태를다시 tree형태로복원한다. void ReleaseTree(Tree Node) 해당노드에의해잡힌메모리를해제하는함수다. 10
Tree.h Tree Leaf(ItemCount *ClassFreq, ClassNo NodeClass, ItemCount Cases, ItemCount Errors) 주어진노드의 leaf를구하는함수다. void Sprout(Tree Node, DiscrValue Branches) : 해당노드에 branch를추가하는함수다. int TreeSize(Tree Node) : 노드의개수를세는함수이다. Tree CopyTree(Tree T) Tree를복사하는함수다. 11
Tree.h void SaveDiscreteNames() 명목형속성들을 char형태로저장한다. void RecoverDiscreteNames() char형태로저장된명목형속성들을다시복원한다. 12
Tree.h void Show(Tree T, short Sh) NodeType 에따라 SubTree 의길이 >Width leaf 출력 치환하여출력 ShowBranch 13
Tree.h void ShowBranch(short Sh, Tree T, DiscrValue v) NodeType 에따라 Indent Indent Subset 으로묶일개수 (Value) 파악 속성이어떤속성값을가지는지출력 Thresh<= 일때 Thresh> 일때 Indent Value==1? F Subtree 로표현 T 속성이어떤속성값을가지는지출력 Offset 증가, 하위트리 (Branch) 에관한 show 함수호출 14
St-thresh.h void SoftenThresh(Tree T) 연속형속성에대한 Thresholds값을부드럽게하는함수다. void ScanTree(Tree T, ItemNo Fp, ItemNo Lp) 연속형속성에서나누는기준 (upper, lower) 을계산하는함수다. 15
St-thresh.h void ScanTree(Tree T, ItemNo Fp, ItemNo Lp) Probability 1 Quicksort 0.5 에러계산 ( 잘못분류된속성의수 ) TE(i) <=Limit< TE(i-1)? 0 Z Z Z + Value V 에러 + 표준편차를 Limit 값으로설정 현재속성을 Threshold 값으로썼을때의에러계산 Lower 선정 TE(i-1) <=Limit< TE(i)? Upper 선정 16
Q & A