Context Navigation

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

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

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

Download in other formats: