Context Navigation

besttree.c @ 101

Last change on this file since 101 was 101, checked in by (none), 14 years ago

File size: 10.0 KB

Rev	Line
[26]	1	/*************************************************************************/
	2	/* */
	3	/* Routines to manage tree growth, pruning and evaluation */
	4	/* ------------------------------------------------------ */
	5	/* */
	6	/*************************************************************************/
	7
	8	#include "defns.i"
	9	#include "types.i"
	10	#include "extern.i"
	11
[63]	12	ItemNo *TargetClassFreq;
	13	Tree *Raw;
	14	extern Tree *Pruned;
[26]	15
	16	/*************************************************************************/
	17	/* */
	18	/* Grow and prune a single tree from all data */
	19	/* */
	20	/*************************************************************************/
	21
[63]	22	OneTree()
[26]	23	/* --------- */
	24	{
[63]	25	Tree FormTree(), CopyTree();
	26	Boolean Prune();
[26]	27
[63]	28	InitialiseTreeData();
	29	InitialiseWeights();
[26]	30
[63]	31	Raw = (Tree *) calloc(1, sizeof(Tree));
	32	Pruned = (Tree *) calloc(1, sizeof(Tree));
[26]	33
[63]	34	AllKnown = true;
	35	Raw[0] = FormTree(0, MaxItem);
	36	//printf("\n");
	37	//PrintTree(Raw[0]);
[26]	38
[63]	39	SaveTree(Raw[0], ".unpruned");
[26]	40
[63]	41	Pruned[0] = CopyTree(Raw[0]);
	42	if (Prune(Pruned[0])) {
	43	printf("\nSimplified ");
	44	PrintTree(Pruned[0]);
	45	}
[26]	46	}
	47
[63]	48	OneTree_Discr()
	49	/* --------- */
	50	{
	51	Tree FormTree_Discr(), CopyTree();
	52	Boolean Prune();
[26]	53
	54
[63]	55	InitialiseTreeData();
	56	InitialiseWeights();
	57
	58	Raw = (Tree *) calloc(1, sizeof(Tree));
	59	Pruned = (Tree *) calloc(1, sizeof(Tree));
	60
[101]	61	AllKnown = true;
[63]	62
	63	Raw[0] = FormTree_Discr(0, MaxItem);
[101]	64
[63]	65	//printf("\n");
	66	//PrintTree(Raw[0]);
	67
	68	SaveTree(Raw[0], ".unpruned");
	69
	70	Pruned[0] = CopyTree(Raw[0]);
	71	if (Prune(Pruned[0])) {
	72	printf("\nSimplified ");
[101]	73	//PrintTree(Pruned[0]);
[63]	74	}
	75	}
[26]	76	/*************************************************************************/
	77	/* */
	78	/* Grow and prune TRIALS trees and select the best of them */
	79	/* */
	80	/*************************************************************************/
	81
	82	short BestTree()
	83	/* -------- */
	84	{
[63]	85	Tree CopyTree(), Iterate();
	86	Boolean Prune();
	87	short t, Best = 0;
[26]	88
[63]	89	InitialiseTreeData();
[26]	90
[63]	91	TargetClassFreq = (ItemNo *) calloc(MaxClass + 1, sizeof(ItemNo));
[26]	92
[63]	93	Raw = (Tree *) calloc(TRIALS, sizeof(Tree));
	94	Pruned = (Tree *) calloc(TRIALS, sizeof(Tree));
[26]	95
[63]	96	/* If necessary, set initial size of window to 20% (or twice
	97	the sqrt, if this is larger) of the number of data items,
	98	and the maximum number of items that can be added to the
	99	window at each iteration to 20% of the initial window size */
[26]	100
[63]	101	if (!WINDOW) {
	102	WINDOW = Max(2 * sqrt(MaxItem+1.0), (MaxItem+1) / 5);
	103	}
[26]	104
[63]	105	if (!INCREMENT) {
	106	INCREMENT = Max(WINDOW / 5, 1);
	107	}
[26]	108
[63]	109	FormTarget(WINDOW);
[26]	110
[63]	111	/* Form set of trees by iteration and prune */
[26]	112
[63]	113	ForEach(t, 0, TRIALS-1 ) {
	114	FormInitialWindow();
[26]	115
[63]	116	printf("\n--------\nTrial %d\n--------\n\n", t);
[26]	117
[63]	118	Raw[t] = Iterate(WINDOW, INCREMENT);
	119	printf("\n");
	120	PrintTree(Raw[t]);
[26]	121
[63]	122	SaveTree(Raw[t], ".unpruned");
[26]	123
[63]	124	Pruned[t] = CopyTree(Raw[t]);
	125	if (Prune(Pruned[t])) {
	126	printf("\nSimplified ");
	127	PrintTree(Pruned[t]);
	128	}
[26]	129
[63]	130	if (Pruned[t]->Errors < Pruned[Best]->Errors) {
	131	Best = t;
	132	}
[26]	133	}
[63]	134	printf("\n--------\n");
[26]	135
[63]	136	return Best;
[26]	137	}
	138
	139	/*************************************************************************/
	140	/* */
	141	/* The windowing approach seems to work best when the class */
	142	/* distribution of the initial window is as close to uniform as */
	143	/* possible. FormTarget generates this initial target distribution, */
	144	/* setting up a TargetClassFreq value for each class. */
	145	/* */
	146	/*************************************************************************/
	147
[63]	148	FormTarget(Size)
	149	/* ----------- */
	150	ItemNo Size; {
	151	ItemNo i, *ClassFreq;
	152	ClassNo c, Smallest, ClassesLeft = 0;
[26]	153
[63]	154	ClassFreq = (ItemNo *) calloc(MaxClass + 1, sizeof(ItemNo));
[26]	155
[63]	156	/* Generate the class frequency distribution */
[26]	157
[63]	158	ForEach(i, 0, MaxItem) {
	159	ClassFreq[Class(Item[i])]++;
	160	}
[26]	161
[63]	162	/* Calculate the no. of classes of which there are items */
[26]	163
[63]	164	ForEach(c, 0, MaxClass) {
	165	if (ClassFreq[c]) {
	166	ClassesLeft++;
	167	} else {
	168	TargetClassFreq[c] = 0;
	169	}
[26]	170	}
	171
[63]	172	while (ClassesLeft) {
	173	/* Find least common class of which there are some items */
[26]	174
[63]	175	Smallest = -1;
	176	ForEach(c, 0, MaxClass) {
	177	if (ClassFreq[c] && (Smallest < 0 \|\| ClassFreq[c]
	178	< ClassFreq[Smallest])) {
	179	Smallest = c;
	180	}
	181	}
[26]	182
[63]	183	/* Allocate the no. of items of this class to use in the window */
[26]	184
[63]	185	TargetClassFreq[Smallest]
	186	= Min(ClassFreq[Smallest], Round(Size/ClassesLeft));
[26]	187
[63]	188	ClassFreq[Smallest] = 0;
[26]	189
[63]	190	Size -= TargetClassFreq[Smallest];
	191	ClassesLeft--;
	192	}
[26]	193
[63]	194	cfree(ClassFreq);
[26]	195	}
	196
	197	/*************************************************************************/
	198	/* */
	199	/* Form initial window, attempting to obtain the target class profile */
	200	/* in TargetClassFreq. This is done by placing the targeted number */
	201	/* of items of each class at the beginning of the set of data items. */
	202	/* */
	203	/*************************************************************************/
	204
[63]	205	FormInitialWindow()
[26]	206	/* ------------------- */
	207	{
[63]	208	ItemNo i, Start = 0, More;
	209	ClassNo c;
	210	void Swap();
[26]	211
[63]	212	Shuffle();
[26]	213
[63]	214	ForEach(c, 0, MaxClass) {
	215	More = TargetClassFreq[c];
[26]	216
[63]	217	for (i = Start; More; i++) {
	218	if (Class(Item[i]) == c) {
	219	Swap(Start, i);
	220	Start++;
	221	More--;
	222	}
	223	}
[26]	224	}
	225	}
	226
	227	/*************************************************************************/
	228	/* */
	229	/* Shuffle the data items randomly */
	230	/* */
	231	/*************************************************************************/
	232
[63]	233	Shuffle()
[26]	234	/* ------- */
	235	{
[63]	236	ItemNo This, Alt, Left;
	237	Description Hold;
[26]	238
[63]	239	This = 0;
	240	for (Left = MaxItem + 1; Left;) {
	241	Alt = This + (Left--) * Random;
	242	Hold = Item[This];
	243	Item[This++] = Item[Alt];
	244	Item[Alt] = Hold;
	245	}
[26]	246	}
	247
	248	/*************************************************************************/
	249	/* */
	250	/* Grow a tree iteratively with initial window size Window and */
	251	/* initial window increment IncExceptions. */
	252	/* */
	253	/* Construct a classifier tree using the data items in the */
	254	/* window, then test for the successful classification of other */
	255	/* data items by this tree. If there are misclassified items, */
	256	/* put them immediately after the items in the window, increase */
	257	/* the size of the window and build another classifier tree, and */
	258	/* so on until we have a tree which successfully classifies all */
	259	/* of the test items or no improvement is apparent. */
	260	/* */
	261	/* On completion, return the tree which produced the least errors. */
	262	/* */
	263	/*************************************************************************/
	264
	265	Tree Iterate(Window, IncExceptions)
[63]	266	/* ------- */
	267	ItemNo Window, IncExceptions; {
	268	Tree Classifier, BestClassifier = Nil, FormTree();
	269	ItemNo i, Errors, TotalErrors, BestTotalErrors = MaxItem + 1, Exceptions,
	270	Additions;
	271	ClassNo Assigned, Category();
	272	short Cycle = 0;
	273	void Swap();
[26]	274
[63]	275	printf("Cycle Tree -----Cases----");
	276	printf(" -----------------Errors-----------------\n");
	277	printf(" size window other");
	278	printf(" window rate other rate total rate\n");
	279	printf("----- ---- ------ ------");
	280	printf(" ------ ---- ------ ---- ------ ----\n");
[26]	281
[63]	282	do {
	283	/* Build a classifier tree with the first Window items */
[26]	284
[63]	285	InitialiseWeights();
	286	AllKnown = true;
	287	Classifier = FormTree(0, Window - 1);
[26]	288
[63]	289	/* Error analysis */
[26]	290
[63]	291	Errors = Round(Classifier->Errors);
[26]	292
[63]	293	/* Move all items that are incorrectly classified by the
	294	classifier tree to immediately after the items in the
	295	current window. */
[26]	296
[63]	297	Exceptions = Window;
	298	ForEach(i, Window, MaxItem) {
	299	Assigned = Category(Item[i], Classifier);
	300	if (Assigned != Class(Item[i])) {
	301	Swap(Exceptions, i);
	302	Exceptions++;
	303	}
	304	}
	305	Exceptions -= Window;
	306	TotalErrors = Errors + Exceptions;
[26]	307
[63]	308	/* Print error analysis */
[26]	309
[63]	310	printf("%3d %7d %8d %6d %8d%5.1f%% %6d%5.1f%% %6d%5.1f%%\n",
	311	++Cycle, TreeSize(Classifier), Window, MaxItem - Window + 1,
	312	Errors, 100 * (float) Errors / Window, Exceptions, 100
	313	* Exceptions / (MaxItem - Window + 1.001), TotalErrors,
	314	100 * TotalErrors / (MaxItem + 1.0));
[26]	315
[63]	316	/* Keep track of the most successful classifier tree so far */
[26]	317
[63]	318	if (!BestClassifier \|\| TotalErrors < BestTotalErrors) {
	319	if (BestClassifier)
	320	ReleaseTree(BestClassifier);
	321	BestClassifier = Classifier;
	322	BestTotalErrors = TotalErrors;
	323	} else {
	324	ReleaseTree(Classifier);
	325	}
[26]	326
[63]	327	/* Increment window size */
[26]	328
[63]	329	Additions = Min(Exceptions, IncExceptions);
	330	Window = Min(Window + Max(Additions, Exceptions / 2), MaxItem + 1);
	331	} while (Exceptions);
[26]	332
[63]	333	return BestClassifier;
[26]	334	}
	335
	336	/*************************************************************************/
	337	/* */
	338	/* Print report of errors for each of the trials */
	339	/* */
	340	/*************************************************************************/
	341
[63]	342	Evaluate(CMInfo, Saved)
	343	/* -------- */
	344	Boolean CMInfo;short Saved; {
	345	ClassNo RealClass, PrunedClass, Category();
	346	short t;
	347	ItemNo *ConfusionMat, i, RawErrors, PrunedErrors;
[26]	348
[63]	349	if (CMInfo) {
	350	ConfusionMat = (ItemNo ) calloc((MaxClass + 1) (MaxClass + 1),
	351	sizeof(ItemNo));
	352	}
[26]	353
[63]	354	printf("\n");
[26]	355
[63]	356	if (TRIALS > 1) {
	357	printf("Trial\t Before Pruning After Pruning\n");
	358	printf("-----\t---------------- ---------------------------\n");
	359	} else {
	360	printf("\t Before Pruning After Pruning\n");
	361	printf("\t---------------- ---------------------------\n");
	362	}
	363	printf("\tSize Errors Size Errors Estimate\n\n");
[26]	364
[63]	365	ForEach(t, 0, TRIALS-1) {
	366	RawErrors = PrunedErrors = 0;
[26]	367
[63]	368	ForEach(i, 0, MaxItem) {
	369	RealClass = Class(Item[i]);
[26]	370
[63]	371	if (Category(Item[i], Raw[t]) != RealClass)
	372	RawErrors++;
[26]	373
[63]	374	PrunedClass = Category(Item[i], Pruned[t]);
[26]	375
[63]	376	if (PrunedClass != RealClass)
	377	PrunedErrors++;
[26]	378
[63]	379	if (CMInfo && t == Saved) {
	380	ConfusionMat[RealClass * (MaxClass + 1) + PrunedClass]++;
	381	}
	382	}
[26]	383
[63]	384	if (TRIALS > 1) {
	385	printf("%4d", t);
	386	}
	387
	388	printf("\t%4d %3d(%4.1f%%) %4d %3d(%4.1f%%) (%4.1f%%)%s\n",
	389	TreeSize(Raw[t]), RawErrors, 100.0 * RawErrors
	390	/ (MaxItem + 1.0), TreeSize(Pruned[t]), PrunedErrors,
	391	100.0 * PrunedErrors / (MaxItem + 1.0), 100 * Pruned[t]->Errors
	392	/ Pruned[t]->Items, (t == Saved ? " <<" : ""));
[26]	393	}
[63]	394
	395	if (CMInfo) {
	396	PrintConfusionMatrix(ConfusionMat);
	397	free(ConfusionMat);
[26]	398	}
	399	}

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: proiecte/Parallel-DT/R8/Src/besttree.c @ 101

Download in other formats: