multi_pair.c

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

/* Copyright (C) 2001-2002  Mikael Ylikoski
 * See the accompanying file "README" for the full copyright notice */
/**
 * @file
 * Pairwise multi class classification.
 *
 * This file implements PAIR_MAX_WINS and PAIR_DAG.
 *
 * @author  Mikael Ylikoski
 * @date    2001-2002
 */

#include <stdlib.h>
#include "parray.h"
#include "multi.h"
#include "multi_pair.h"
#include "utility.h"
#include "vector.h"


/**
 * Learn classification of vector.
 *
 * @param data   multi classifier database (type multi_db)
 * @param v      vector to classify
 * @param class  classification
 */
int
multi_pair_learn (void *data, vector *v, int class) {
    int i, j, k;
    void *cd;
    multi_db *db;
    vector *u;

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

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

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


/**
 * Unlearn classification of vector.
 *
 * @param data   multi classifier database (type multi_db)
 * @param v      vector to learn
 * @param class  classification
 */
int
multi_pair_unlearn (void *data, vector *v, int class) {
    int i, j, k;
    void *cd;
    multi_db *db;

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

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


/**
 * Classify a vector using max wins evaluation.
 *
 * @param data  multi classifier database (type multi_db)
 * @param v     vector to classify
 */
int
multi_pair_classify_max_wins (void *data, vector *v) {
    int i, j, k;
    int *r;
    double d;
    void *cd;
    multi_db *db;

    db = (multi_db *)data;
    r = my_calloc (db->size, sizeof(int));

    for (k = i = 0; i < db->size - 1; i++)
	for (j = i + 1; j < db->size; j++, k++) {
	    cd = array_get_value (db->classes, k);
	    d = db->funcs->classify (db->data, cd, v);
	    if (d > 0)
		r[j]++;
	    else if (d < 0)
		r[i]++;
	}
    for (k = j = i = 0; i < db->size; i++)
	if (r[i] > k)
	    k = r[j = i];

    return j;
}


/**
 * Classify a vector using max wins evaluation.
 *
 * @param data  multi classifier database (type multi_db)
 * @param v     vector to classify
 */
double *
multi_pair_classify_max_wins_score (void *data, vector *v) {
    int i, j, k;
    double *r;
    double d;
    void *cd;
    multi_db *db;

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

    for (k = i = 0; i < db->size - 1; i++)
	for (j = i + 1; j < db->size; j++, k++) {
	    cd = array_get_value (db->classes, k);
	    d = db->funcs->classify (db->data, cd, v);
	    if (d > 0)
		r[j]++;
	    else if (d < 0)
		r[i]++;
	}

    return r;
}


/**
 * Classify a vector using directed acyclic graph evaluation.
 *
 * @param data  multi classifier database (type multi_db)
 * @param v     vector to classify
 */
int
multi_pair_classify_dag (void *data, vector *v) {
    int i, j, k;
    double d;
    void *cd;
    multi_db *db;

    db = (multi_db *)data;
    i = 0;
    j = db->size - 1;
    k = db->size - 2;
    while (i != j) {
	cd = array_get_value (db->classes, k);
	d = db->funcs->classify (db->data, cd, v);
	if (d > 0)
	    k += db->size - ++i - 1;
 	else {
	    j--;
	    k--;
	}
    }
    return i;
}


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

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


static classifier_functions multi_pair_max_wins_functions = {
    .learn = multi_pair_learn,
    .classify_top = multi_pair_classify_max_wins,
    .info = multi_pair_info
};


static classifier_functions multi_pair_dag_functions = {
    .learn = multi_pair_learn,
    .unlearn = NULL,
    .classify_top = multi_pair_classify_dag,
    .info = multi_pair_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_pair_maxwins_new (multi_functions *funcs, void *data, int size) {
    int i, j;
    void *cc;
    multi_db *db;

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

    j = db->size * (db->size - 1) / 2;
    db->classes = parray_new (j);
    for (i = 0; i < j; i++) {
	cc = db->funcs->new ();
	array_set_value (db->classes, i, cc);
    }
    parray_set_size (db->classes, j);

    return classifier_new (db, &multi_pair_max_wins_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_pair_dag_new (multi_functions *funcs, void *data, int size) {
    int i, j;
    void *cc;
    multi_db *db;

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

    j = db->size * (db->size - 1) / 2;
    db->classes = parray_new (j);
    for (i = 0; i < j; i++) {
	cc = db->funcs->new ();
	array_set_value (db->classes, i, cc);
    }
    parray_set_size (db->classes, j);

    return classifier_new(db, &multi_pair_dag_functions);
}