soft.c

Ripper 分类算法

/******************************************************************************
 soft.c - routines for soft ripper
******************************************************************************/

#include <stdio.h>
#include "ripper.h"
#include "soft.h"
#include "mdb.h"

ex_count_t *Class_counts=NULL;
order_t Class_ordering=INCFREQ;

static soft_rule_t *soft_rule(symbol_t *,vec_t *);
static void update_rule_weights(soft_concept_t *,example_t *,ex_count_t *);

/*****************************************************************************/

soft_concept_t *soft_model(data)
vec_t *data;
{

    soft_concept_t *hyp; 
    soft_rule_t *rj;
    int i,j,k;
    example_t *exk;
    ex_count_t tot_wt,tot_err,orig_tot_wt,err;
    ex_count_t *save_wt;
    double epsilon,beta;
    symbol_t *clj;


    /* initialize the hypothesis, and save example weights */

    hyp = newmem(1,soft_concept_t);
    hyp->rules = new_vec(rule_t);
    save_wt = newmem(vmax(data),ex_count_t);
    orig_tot_wt = 0;
    for (k=0; k<vmax(data); k++) {
	exk = vref(example_t,data,k);
	save_wt[k] = exk->wt;
	orig_tot_wt += exk->wt;
    }

    /* iteratively "boost" to find a set of plausible experts */

    for (i=0; i<N_boost; i++) {

	/* add a new rule for each class */
	for (j=0; j<vmax(Classes); j++) {
	    clj = vref(atom_t,Classes,j)->nom;
	    rj = soft_rule(clj,data);
	    ext_vec(soft_rule_t,hyp->rules,rj);
	}

	/* run the sleeping experts algorithm with the current rule set */
	reset_rule_weights(hyp);
	tot_err = tot_wt = 0;
	for (k=0; k<vmax(data); k++) {
	    exk = vref(example_t,data,k);
	    update_rule_weights(hyp,exk,&err);
	    tot_wt += exk->wt;
	    tot_err += err;
	}

	/* compute error of specialists on previous pass */
	epsilon = tot_err/tot_wt;
	beta = epsilon / (1.0 - epsilon);

	/* update distribution as in ADABOOST */
	tot_err = tot_wt = 0;
	for (k=0; k<vmax(data); k++) {
	    exk = vref(example_t,data,k);
	    if (soft_classify(hyp,exk->inst) == exk->lab.nom) {
		exk->wt *= beta;
	    } else {
		tot_err += exk->wt;
	    }
	    tot_wt += exk->wt;
	}
	/* re-normalize weights */
	for (k=0; k<vmax(data); k++) {
	    exk = vref(example_t,data,k); 
	    exk->wt *= orig_tot_wt/tot_wt;
	}
    }

    /* now that we have a list of sleeping expert rules, use them 
       on the examples (with original weighting restored)
     */ 

    reset_rule_weights(hyp);
    for (k=0; k<vmax(data); k++) {
	exk->wt = save_wt[k];
	update_rule_weights(hyp,exk,&err);
    }
    return hyp;
}