classifier.c

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

/* Copyright (C) 2001-2002, 2003  Mikael Ylikoski
 * See the accompanying file "README" for the full copyright notice */
/**
 * @file
 * Vector classifier interface.
 *
 * @author  Mikael Ylikoski
 * @date    2001-2003
 */

#include <stdlib.h>
#include <string.h>
#include "classifier.h"
#include "doc_classifier.h"
#include "utility.h"
#include "vector.h"


/**
 * Create a new classifier.
 */
classifier *
classifier_new (void *data, classifier_functions *funcs) {
    classifier *cl;

    cl = my_malloc (sizeof(classifier));
    cl->data = data;
    cl->funcs = funcs;

    return cl;
}


/**
 * Get number of classes.
 */
int
classifier_get_noc (classifier *cl) {
    return cl->funcs->info (cl->data);
}


/**
 * Learn a vector.
 */
int
classifier_learn (classifier *cl, vector *v, int class) {
    return cl->funcs->learn (cl->data, v, class);
}


/**
 * Unlearn a vector.
 */
int
classifier_unlearn (classifier *cl, vector *v, int class) {
    if (cl->funcs->unlearn)
	return cl->funcs->unlearn (cl->data, v, class);
    return -1;
}


/**
 * Classify a vector.
 */
int
classifier_classify_top (classifier *cl, vector *v) {
    return cl->funcs->classify_top (cl->data, v);
}


/**
 * Make a ranked classification.
 */
double *
classifier_classify_score (classifier *cl, vector *v) {
    return cl->funcs->classify_score (cl->data, v);
}


/**
 * Find maximum class from classification list.
 */
int
classifier_max_class (double *list, int num) {
    int i, c = -1;
    double d = 0;

    for (i = 0; i < num; i++)
	if (list[i] != 0) {
	    d = list[i];
	    c = i;
	    break;
	}
    for (i++; i < num; i++)
	if (list[i] != 0 && list[i] > d) {
	    c = i;
	    d = list[i];
	}

    return c;
}


/**
 * Find maximum class from classification list.
 */
int
classifier_min_class (double *list, int num) {
    int i, c = -1;
    double d = 0;

    for (i = 0; i < num; i++)
	if (list[i] != 0) {
	    d = list[i];
	    c = i;
	    break;
	}
    for (i++; i < num; i++)
	if (list[i] != 0 && list[i] < d) {
	    c = i;
	    d = list[i];
	}

    return c;
}


/**
 * Train a classifier with a vector.
 */
static int
classifier_learn_vector (void *db, void *vec, int class) {
    classifier *cl;
    vector *v;

    cl = (classifier *)db;
    v = (vector *)vec;
    return cl->funcs->learn (cl->data, v, class);
}


/**
 * Untrain a classifier with a vector.
 */
static int
classifier_unlearn_vector (void *db, void *vec, int class) {
    classifier *cl;
    vector *v;

    cl = (classifier *)db;
    v = (vector *)vec;
    if (cl->funcs->unlearn)
	return cl->funcs->unlearn (cl->data, v, class);
    return -1;
}


/**
 * Untrain a classifier with a vector.
 */
static int
classifier_remove (void *db, void *vec) {
    classifier *cl;
    vector *v;

    cl = (classifier *)db;
    v = (vector *)vec;
    if (cl->funcs->remove)
	return cl->funcs->remove (cl->data, v);
    return -1;
}


/**
 * Classify a vector, with a score result.
 */
double *
classifier_classify_doc_score (void *db, void *vec) {
    double *dl;
    classifier *cl;
    vector *v;

    cl = (classifier *)db;
    v = (vector *)vec;

    if (cl->funcs->classify_score)
	dl = cl->funcs->classify_score (cl->data, v);
    else
	dl = NULL;

    return dl;
}


/**
 * Make a rank list from a score list.
 *
 * @param rank   rank list, the length of which must be at least len + 1
 * @param score  score list
 * @param len    length of score list
 */
/*
static void
rank_from_score_old (int *rank, double *score, int len) {
    int i, j, pos;
    double val;

    val = 0;
    pos = -1;
    for (j = 0; j < len; j++) {
	pos = -1;
	for (i = 0; i < len; i++)
	    if (score[i] != 0 && (pos == -1 || val < score[i])) {
		val = score[i];
		pos = i;
	    }
	if (pos == -1)
	    break;
	rank[j] = pos;
	score[pos] = 0;
    }
    rank[j] = -1;
}
*/


typedef struct {
    int i;
    double d;
} intdouble;


static int
rcomp (const void *e1, const void *e2) {
    intdouble *a;
    intdouble *b;

    a = (intdouble *)e1;
    b = (intdouble *)e2;
    if (a->d < b->d)
	return 1;
    else if (a->d > b->d)
	return -1;
    return 0;
}


/**
 * Make a rank list from a score list.
 * This is only marginally faster than rank_from_score_old for len < 100.
 * Should be replaced with a custom made sorting function.
 *
 * @param rank   rank list, the length of which must be at least len + 1
 * @param score  score list
 * @param len    length of score list
 */
static void
rank_from_score (int *rank, double *score, int len) {
    int i, j;
    static int newlen = 0;
    static intdouble *new = NULL;

    if (len > newlen) {
	free (new);
	new = my_malloc (sizeof(intdouble) * len);
    }
    j = 0;
    for (i = 0; i < len; i++) {
	if (score[i] != 0) {
	    new[j].i = i;
	    new[j].d = score[i];
	    j++;
	}
    }

    if (j)
	qsort (new, j, sizeof(intdouble), rcomp);

    for (i = 0; i < j; i++)
	rank[i] = new[i].i;
    rank[i] = -1;
}


/**
 * Make a rank list from a score list.
 * This is a little faster than rank_from_score for len < 100.
 * This only outputs at most the top 5 rankings (which is usually enough).
 *
 * @param rank   rank list, the length of which must be at least len + 1
 * @param score  score list
 * @param len    length of score list
static void
rank_from_score_small (int *rank, double *score, int len) {
    int i, j;
    int rsize;

    if (0)
	rank_from_score (0, 0, 0);

    if (len > 5)
	rsize = 5;
    else
	rsize = len;
    rank[rsize] = -1;

    for (j = 0; j < len; j++) {
	if (j < rsize)
	    rank[j] = -1;
	if (score[j] == 0)
	    continue;
	for (i = 0; i < rsize; i++)
	    if (rank[i] == -1) {
		rank[i] = j;
		break;
	    } else if (score[j] > score[rank[i]]) {
		memmove (&rank[i + 1], &rank[i], (rsize - i - 1)
			 * sizeof(int));
		rank[i] = j;
		break;
	    }
    }
    rank[rsize] = -1;
}
*/


/**
 * Classify a vector, with a rank result.
 */
int *
classifier_classify_doc_rank (void *db, void *vec) {
    classifier *cl;
    vector *v;
    double *dl;
    int *il;
    int i;

    cl = (classifier *)db;
    v = (vector *)vec;

    if (!vec)
	return NULL;

    if (cl->funcs->classify_rank)
	il = cl->funcs->classify_rank (cl->data, v);
    else if (cl->funcs->classify_score) {
	dl = cl->funcs->classify_score (cl->data, v);
	i = cl->funcs->info (cl->data);
	il = my_malloc ((i + 1) * sizeof(int));
	rank_from_score (il, dl, i);
	free (dl);
    } else
	il = NULL;

    return il;
}


/**
 * Get number of classes in a classifier.
 */
int
classifier_get_noc_doc (void *db) {
    classifier *cl;

    cl = (classifier *)db;
    return cl->funcs->info (cl->data);
}


/**
 * Save a classifier.
 */
int
classifier_save (FILE *f, void *db) {
    classifier *cl;

    cl = (classifier *)db;
    if (cl->funcs->save)
	return cl->funcs->save (f, cl->data);
    return -1;
}


/**
 * Classifier functions.
 */
const doc_classifier_functions my_functions = {
    .save = classifier_save,
    .learn = classifier_learn_vector,
    .unlearn = classifier_unlearn_vector,
    .remove = classifier_remove,
    //.classify_top = classifier_classify_doc_top,
    .classify_rank = classifier_classify_doc_rank,
    .classify_score = classifier_classify_doc_score,
    .info = classifier_get_noc_doc
};


/**
 * Get classifier functions.
 */
const doc_classifier_functions *
classifier_get_doc_classifier_functions (void) {
    return &my_functions;
}