multi_one.c

使用具有增量学习的监控式学习方法。包括几个不同的分类算法。

/* Copyright (C) 2001-2002  Mikael Ylikoski
 * See the accompanying file "README" for the full copyright notice */
/**
 * @file
 * Multi class classification for binary classifiers.
 *
 * Wrapper to combine several binary classifiers to use as multi class
 * classifier.
 *
 * This file implements ONE_MAX, REST_MAX, LIN_MAX and UC_MAX.
 *
 * @author  Mikael Ylikoski
 * @date    2001-2002
 */

#include <float.h>
#include <stdio.h>
#include <stdlib.h>
#include "multi.h"
#include "multi_one.h"
#include "parray.h"
#include "utility.h"
#include "vector.h"


/**
 *
 */
int
multi_one_learn (void *data, vector *v, int class) {
    void *cd;
    multi_db *db;
    vector *u;

    db = (multi_db *)data;
    if (class >= db->size) {
	parray_set_size (db->classes, class + 1);
	db->size = class + 1;
    }

    if (!v || vector_length (v) == 0)	// FIXME maybe allow zero vectors?
	return -1;

    if (db->funcs->option & OPTION_COPY_VECTOR)
	u = vector_copy (v);
    else
	u = v;

    cd = array_get_value (db->classes, class);
    if (!cd) {
	cd = db->funcs->new ();
	if (!cd)
	    return -1;
	array_set_value (db->classes, class, cd);
    }

    return db->funcs->learn (db->data, cd, u, 1);
}


/**
 *
 */
int
multi_one_unlearn (void *data, vector *v, int class) {
    void *cd;
    multi_db *db;

    db = (multi_db *)data;
    if (!db->funcs->unlearn)
	return -1;

    if (class >= db->size)
	return -1;

    cd = array_get_value (db->classes, class);
    if (!cd)
	return -1;

    return db->funcs->unlearn (db->data, cd, v, 1);
}


/**
 *
 */
int
multi_one_remove (void *data, vector *v) {
    int i;
    void *cd;
    multi_db *db;

    db = (multi_db *)data;
    if (!db->funcs->remove)
	return -1;

    for (i = 0; i < db->size; i++) {
	cd = array_get_value (db->classes, i);
	if (cd)
	    db->funcs->remove (db->data, cd, v);
    }

    db->funcs->remove_db (db->data, v);

    return 0;
}


/**
 *
 */
int
multi_one_learn_rest (void *data, vector *v, int class) {
    int i;
    void *cd;
    multi_db *db;
    vector *u;

    db = (multi_db *)data;
    if (class >= db->size) {
	if (parray_set_size (db->classes, class + 1))
	    return -1;
	db->size = class + 1;
    }

    if (!v || vector_length (v) == 0)
	return -1;

    if (db->funcs->option & OPTION_COPY_VECTOR)
	u = vector_copy (v);
    else
	u = v;

    for (i = 0; i < db->size; i++) {
	cd = array_get_value (db->classes, i);
	if (i == class) {
	    if (!cd) {
		cd = db->funcs->copy (db->method_data);
		if (!cd)
		    return -1;
		array_set_value (db->classes, class, cd);
	    }
	    db->funcs->learn (db->data, cd, u, 1);
	} else if (cd)
	    db->funcs->learn (db->data, cd, u, -1);
    }

    db->funcs->learn (db->data, db->method_data, u, -1);

    return 0;
}


/**
 *
 */
int
multi_one_unlearn_rest (void *data, vector *v, int class) {
    int i;
    void *cd;
    multi_db *db;

    db = (multi_db *)data;
    if (!db->funcs->unlearn)
	return -1;

    if (class >= db->size) {
	if (parray_set_size (db->classes, class + 1))
	    return -1;
	db->size = class + 1;
    }

    for (i = 0; i < db->size; i++) {
	cd = array_get_value (db->classes, i);
	if (i == class) {
	    if (!cd) {
		cd = db->funcs->copy (db->method_data);
		if (!cd)
		    return -1;
		array_set_value (db->classes, class, cd);
	    }
	    db->funcs->unlearn (db->data, cd, v, 1);
	} else if (cd)
	    db->funcs->unlearn (db->data, cd, v, -1);
    }

    db->funcs->unlearn (db->data, db->method_data, v, -1);

    return 0;
}


int
multi_one_classify_max (void *data, vector *v);

/**
 *
 */
int
multi_one_learn_lin (void *data, vector *v, int class) {
    int i;
    void *cd;
    multi_db *db;
    vector *u;

    db = (multi_db *)data;
    if (class >= db->size) {
	if (parray_set_size (db->classes, class + 1))
	    return -1;
	db->size = class + 1;
    }

    if (!v || vector_length (v) == 0)
	return -1;

    if (db->funcs->option & OPTION_COPY_VECTOR)
	u = vector_copy (v);
    else
	u = v;

    i = multi_one_classify_max (db, u);
    if (i == -1) {
	cd = array_get_value (db->classes, class);
	if (!cd) {
	    cd = db->funcs->new ();
	    array_set_value (db->classes, class, cd);
	}
	db->funcs->learn (db->data, cd, u, 1);
    } else if (i != class) {
	//printf ("*** class = %d   guess = %d\n", class, i);
	cd = array_get_value (db->classes, class);
	if (!cd) {
	    cd = db->funcs->new ();	/* FIXME inte r鋞t */
	    array_set_value (db->classes, class, cd);
	}
	db->funcs->learn (db->data, cd, u, 1);
	cd = array_get_value (db->classes, i);
	db->funcs->learn (db->data, cd, u, -1);
    } //else printf ("=== class = guess = %d\n", class);

    return 0;
}


/**
 *
int
multi_one_learn_uc_old (void *data, vector *v, int class) {
    int i, j;
    double d, *rank;
    void *cd;
    multi_db *db;

    if (vector_length(v) == 0)
	return -1;

    db = (multi_db *)data;
    if (class >= db->size) {
	if (parray_set_size(db->classes, class + 1))
	    return -1;
	db->size = class + 1;
    }

    cd = array_get_value(db->classes, class);
    if (!cd) {
	cd = db->funcs->new();
	if (!cd)
	    return -1;
	array_set_value(db->classes, class, cd);
	db->funcs->learn(db->data, cd, v, 1);
	return 0;
    }

    rank = multi_one_classify_max_rank(db, v);
    d = rank[class];
    for (i = j = 0; i < db->size; i++) {
	if (i != class && rank[i] != 0 && rank[i] >= d) {
	    cd = array_get_value(db->classes, i);
	    db->funcs->learn(db->data, cd, v, -1);
	    j++;
	}
    }
    free(rank);

    if (j) {
	cd = array_get_value(db->classes, class);
	db->funcs->learn(db->data, cd, v, 1);
    }

    return 0;
}
 */


double *
multi_one_classify_max_score (void *data, vector *v);

/**
 *
 */
int
multi_one_learn_uc (void *data, vector *v, int class) {
    int i, j;
    double d, *rank;
    void *cd;
    multi_db *db;
    vector *u;

    db = (multi_db *)data;
    if (class >= db->size) {
	parray_set_size (db->classes, class + 1);
	db->size = class + 1;
    }

    if (!v || vector_length (v) == 0)
	return -1;

    if (db->funcs->option & OPTION_COPY_VECTOR)
	u = vector_copy (v);
    else
	u = v;

    cd = array_get_value (db->classes, class);
    if (!cd) {
	cd = db->funcs->new ();
	if (!cd)
	    return -1;
	array_set_value (db->classes, class, cd);
	db->funcs->learn (db->data, cd, u, 1);
	return 0;
    }

    rank = multi_one_classify_max_score (db, u);
    d = rank[class];

    for (i = j = 0; i < db->size; i++)
	if (i != class && rank[i] != 0 && rank[i] >= d)
	    j++;

    for (i = 0; i < db->size; i++)
	if (i != class && rank[i] != 0 && rank[i] >= d) {
	    cd = array_get_value (db->classes, i);
	    db->funcs->learn (db->data, cd, u, -1 / (float)j);
	}
    free (rank);

    if (j) {
	cd = array_get_value (db->classes, class);
	db->funcs->learn (db->data, cd, u, 1);
    }

    return 0;
}


/**
 *
 */
int
multi_one_classify_max (void *data, vector *v) {
    int i, c = -1;
    double d, w = -DBL_MAX;
    void *cd;
    multi_db *db;

    db = (multi_db *)data;
    for (i = 0; i < db->size; i++) {
	cd = array_get_value (db->classes, i);
	if (cd) {
	    d = db->funcs->classify (db->data, cd, v);
	    if (d > w && d != 0) {
		c = i;
		w = d;
	    }
	    //printf(":%d:%.3f  ", i, d);
	}
    }
    //printf("\n");
    return c;
}


/**
 *
 */
double *
multi_one_classify_max_score (void *data, vector *v) {
    int i;
    double *r;
    void *cd;
    multi_db *db;

    db = (multi_db *)data;
    if (db->size == 0)
	return NULL;
    r = my_calloc (db->size, sizeof(double));

    for (i = 0; i < db->size; i++) {
	cd = array_get_value (db->classes, i);
	if (cd)
	    r[i] = db->funcs->classify (db->data, cd, v);
	/*
	if (r[i] == 0)
	    printf(":%d:0  ", i);
	else
	    printf(":%d:%.3f  ", i, r[i]);
	*/
    }
    //printf("\n");

    return r;
}


int
multi_one_info (void *data) {
    multi_db *db;

    db = (multi_db *)data;
    return db->size;
}


int
multi_one_save (FILE *f, void *data) {
    int i;
    multi_db *db;

    db = (multi_db *)data;

    fprintf (f, "noc %d\n", db->size);
    fprintf (f, "[global]\n");
    db->funcs->save_db (f, db->data);

    for (i = 0; i < db->size; i++) {
	fprintf (f, "[%d]\n", i);
	db->funcs->save_class (f, array_get_value (db->classes, i));
    }

    return 0;
}


int
multi_one_rest_save (FILE *f, void *data) {
    int i;
    multi_db *db;

    db = (multi_db *)data;

    fprintf (f, "noc %d\n", db->size);
    fprintf (f, "[rest]\n");
    db->funcs->save_class (f, db->method_data);
    fprintf (f, "[global]\n");
    db->funcs->save_db (f, db->data);
    for (i = 0; i < db->size; i++) {
	fprintf (f, "[%d]\n", i);
	db->funcs->save_class (f, array_get_value (db->classes, i));
    }

    return 0;
}


static classifier_functions multi_one_max_functions = {
    .save = multi_one_save,
    .learn = multi_one_learn,
    .unlearn = multi_one_unlearn,
    .remove = multi_one_remove,
    .classify_top = multi_one_classify_max,
    .classify_score = multi_one_classify_max_score,
    .info = multi_one_info
};


static classifier_functions multi_rest_max_functions = {
    .save = multi_one_rest_save,
    .learn = multi_one_learn_rest,
    .unlearn = multi_one_unlearn_rest,
    .classify_top = multi_one_classify_max,
    .classify_score = multi_one_classify_max_score,
    .info = multi_one_info
};


static classifier_functions multi_lin_max_functions = {
    .save = multi_one_save,
    .learn = multi_one_learn_lin,
    .classify_top = multi_one_classify_max,
    .classify_score = multi_one_classify_max_score,
    .info = multi_one_info
};


static classifier_functions multi_uc_max_functions = {
    .save = multi_one_save,
    .learn = multi_one_learn_uc,
    .classify_top = multi_one_classify_max,
    .classify_score = multi_one_classify_max_score,
    .info = multi_one_info
};


/**
 * Create a new classifier database.
 *
 * @param funcs  classifiers functions
 * @param data   classifiers global data
 * @param size   number of classes
 * @return  The new classifier database.
 */
classifier *
multi_one_max_new (multi_functions *funcs, void *data, int size) {
    multi_db *db;

    db = my_malloc (sizeof(multi_db));
    db->funcs = funcs;
    db->data = data;
    db->size = size;
    db->classes = parray_new (db->size);
    parray_set_size (db->classes, db->size);

    return classifier_new (db, &multi_one_max_functions);
}


/**
 * Create a new classifier database.
 *
 * @param funcs  classifiers functions
 * @param data   classifiers global data
 * @param size   number of classes
 * @return  The new classifier database.
 */
classifier *
multi_one_rest_new (multi_functions *funcs, void *data, int size) {
    multi_db *db;

    db = my_malloc (sizeof(multi_db));
    db->funcs = funcs;
    db->data = data;
    db->size = size;
    db->classes = parray_new (db->size);
    parray_set_size (db->classes, db->size);
    db->method_data = funcs->new ();

    return classifier_new (db, &multi_rest_max_functions);
}


/**
 * Create a new classifier database.
 *
 * @param funcs  classifiers functions
 * @param data   classifiers global data
 * @param size   number of classes
 * @return  The new classifier database.
 */
classifier *
multi_one_lin_new (multi_functions *funcs, void *data, int size) {
    multi_db *db;

    db = my_malloc (sizeof(multi_db));
    db->funcs = funcs;
    db->data = data;
    db->size = size;
    db->classes = parray_new (db->size);
    parray_set_size (db->classes, db->size);

    return classifier_new (db, &multi_lin_max_functions);
}


/**
 * Create a new classifier database.
 *
 * @param funcs  classifiers functions
 * @param data   classifiers global data
 * @param size   number of classes
 * @return  The new classifier database.
 */
classifier *
multi_one_uc_new (multi_functions *funcs, void *data, int size) {
    multi_db *db;

    db = my_malloc (sizeof(multi_db));
    db->funcs = funcs;
    db->data = data;
    db->size = size;
    db->classes = parray_new (db->size);
    parray_set_size (db->classes, db->size);

    return classifier_new (db, &multi_uc_max_functions);
}


static multi_db *
multi_one_load (FILE *f, multi_functions *funcs) {
    int i, j;
    void *d;
    multi_db *db;

    db = my_malloc (sizeof(multi_db));
    db->funcs = funcs;

    i = fscanf (f, "noc %d\n", &db->size);
    fscanf (f, "[global]\n");

    db->data = db->funcs->load_db (f);
    db->classes = parray_new (db->size);
    parray_set_size (db->classes, db->size);

    for (i = 0; i < db->size; i++) {
	fscanf (f, "[%d]\n", &j);
	d = db->funcs->load_class (f);
	array_set_value (db->classes, i, d);
    }

    return db;
}


classifier *
multi_one_max_load (FILE *f, multi_functions *funcs) {
    multi_db *db;

    db = multi_one_load (f, funcs);
    return classifier_new (db, &multi_one_max_functions);
}


classifier *
multi_one_lin_load (FILE *f, multi_functions *funcs) {
    multi_db *db;

    db = multi_one_load (f, funcs);
    return classifier_new (db, &multi_lin_max_functions);
}


classifier *
multi_one_uc_load (FILE *f, multi_functions *funcs) {
    multi_db *db;

    db = multi_one_load (f, funcs);
    return classifier_new (db, &multi_uc_max_functions);
}


classifier *
multi_one_rest_load (FILE *f, multi_functions *funcs) {
    int i, j;
    void *d;
    multi_db *db;

    db = my_malloc (sizeof(multi_db));
    db->funcs = funcs;

    i = fscanf (f, "noc %d\n", &db->size);

    fscanf (f, "[rest]\n");
    db->method_data = db->funcs->load_class (f);

    fscanf (f, "[global]\n");
    db->data = db->funcs->load_db (f);
    db->classes = parray_new (db->size);
    parray_set_size (db->classes, db->size);

    for (i = 0; i < db->size; i++) {
	fscanf (f, "[%d]\n", &j);
	d = db->funcs->load_class (f);
	array_set_value (db->classes, i, d);
    }

    return classifier_new (db, &multi_one_max_functions);
}