Context Navigation

FURIA.java

Last change on this file was 29, checked in by gnappo, 14 years ago
Taggata versione per la demo e aggiunto branch.
File size: 85.4 KB

Rev	Line
[29]	1	/*
	2	* This program is free software; you can redistribute it and/or modify
	3	* it under the terms of the GNU General Public License as published by
	4	* the Free Software Foundation; either version 2 of the License, or
	5	* (at your option) any later version.
	6	*
	7	* This program is distributed in the hope that it will be useful,
	8	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	9	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	10	* GNU General Public License for more details.
	11	*
	12	* You should have received a copy of the GNU General Public License
	13	* along with this program; if not, write to the Free Software
	14	* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
	15	*/
	16
	17	/*
	18	* FURIA.java
	19	* Copyright (C) 2008,2009 Jens Christian Huehn
	20	*
	21	* (based upon) JRip.java
	22	* Copyright (C) 2001 Xin Xu, Eibe Frank
	23	*/
	24
	25	package weka.classifiers.rules;
	26
	27	import java.io.Serializable;
	28	import java.util.Enumeration;
	29	import java.util.Random;
	30	import java.util.Vector;
	31
	32	import weka.classifiers.AbstractClassifier;
	33	import weka.core.AdditionalMeasureProducer;
	34	import weka.core.Attribute;
	35	import weka.core.Capabilities;
	36	import weka.core.Copyable;
	37	import weka.core.FastVector;
	38	import weka.core.Instance;
	39	import weka.core.Instances;
	40	import weka.core.Option;
	41	import weka.core.OptionHandler;
	42	import weka.core.SelectedTag;
	43	import weka.core.Tag;
	44	import weka.core.TechnicalInformation;
	45	import weka.core.TechnicalInformationHandler;
	46	import weka.core.Utils;
	47	import weka.core.WeightedInstancesHandler;
	48	import weka.core.Capabilities.Capability;
	49	import weka.core.TechnicalInformation.Field;
	50	import weka.core.TechnicalInformation.Type;
	51
	52	/**
	53	<!-- globalinfo-start -->
	54	* FURIA: Fuzzy Unordered Rule Induction Algorithm<br/>
	55	* <br/>
	56	* Details please see:<br/>
	57	* <br/>
	58	* Jens Christian Huehn, Eyke Huellermeier (2009). FURIA: An Algorithm for Unordered Fuzzy Rule Induction. Data Mining and Knowledge Discovery..<br/>
	59	* <br/>
	60	* <p/>
	61	<!-- globalinfo-end -->
	62	*
	63	<!-- technical-bibtex-start -->
	64	* BibTeX:
	65	* <pre>
	66	* @article{Huehn2009,
	67	* author = {Jens Christian Huehn and Eyke Huellermeier},
	68	* journal = {Data Mining and Knowledge Discovery},
	69	* title = {FURIA: An Algorithm for Unordered Fuzzy Rule Induction},
	70	* year = {2009}
	71	* }
	72	* </pre>
	73	* <p/>
	74	<!-- technical-bibtex-end -->
	75	*
	76	<!-- options-start -->
	77	* Valid options are: <p/>
	78	*
	79	* <pre> -F <number of folds>
	80	* Set number of folds for REP
	81	* One fold is used as pruning set.
	82	* (default 3)</pre>
	83	*
	84	* <pre> -N <min. weights>
	85	* Set the minimal weights of instances
	86	* within a split.
	87	* (default 2.0)</pre>
	88	*
	89	* <pre> -O <number of runs>
	90	* Set the number of runs of
	91	* optimizations. (Default: 2)</pre>
	92	*
	93	* <pre> -D
	94	* Set whether turn on the
	95	* debug mode (Default: false)</pre>
	96	*
	97	* <pre> -S <seed>
	98	* The seed of randomization
	99	* (Default: 1)</pre>
	100	*
	101	* <pre> -E
	102	* Whether NOT check the error rate>=0.5
	103	* in stopping criteria (default: check)</pre>
	104	*
	105	* <pre> -s
	106	* The action performed for uncovered instances.
	107	* (default: use stretching)</pre>
	108	*
	109	* <pre> -p
	110	* The T-norm used as fuzzy AND-operator.
	111	* (default: Product T-norm)</pre>
	112	*
	113	<!-- options-end -->
	114	*
	115	* @author Jens Christian Hühn (huehn@gmx.net)
	116	* @author Xin Xu (xx5@cs.waikato.ac.nz)
	117	* @author Eibe Frank (eibe@cs.waikato.ac.nz)
	118	* @version $Revision: 5964 $
	119	*/
	120	public class FURIA
	121	extends AbstractClassifier
	122	implements OptionHandler, AdditionalMeasureProducer, WeightedInstancesHandler,
	123	TechnicalInformationHandler {
	124
	125	/** for serialization */
	126	static final long serialVersionUID = -6589312996832147161L;
	127
	128	/** The limit of description length surplus in ruleset generation */
	129	private static double MAX_DL_SURPLUS = 64.0;
	130
	131	/** The class attribute of the data*/
	132	private Attribute m_Class;
	133
	134	/** The ruleset */
	135	private FastVector m_Ruleset;
	136
	137	/** The predicted class distribution */
	138	private FastVector m_Distributions;
	139
	140	/** Runs of optimizations */
	141	private int m_Optimizations = 2;
	142
	143	/** Random object used in this class */
	144	private Random m_Random = null;
	145
	146	/** # of all the possible conditions in a rule */
	147	private double m_Total = 0;
	148
	149	/** The seed to perform randomization */
	150	private long m_Seed = 1;
	151
	152	/** The number of folds to split data into Grow and Prune for IREP */
	153	private int m_Folds = 3;
	154
	155	/** The minimal number of instance weights within a split*/
	156	private double m_MinNo = 2.0;
	157
	158	/** Whether in a debug mode */
	159	private boolean m_Debug = false;
	160
	161	/** Whether check the error rate >= 0.5 in stopping criteria */
	162	private boolean m_CheckErr = true;
	163
	164	/** The class distribution of the training data*/
	165	private double[] aprioriDistribution;
	166
	167	/** The RuleStats for the ruleset of each class value */
	168	private FastVector m_RulesetStats;
	169
	170
	171	/** What to do if instance is uncovered */
	172	private int m_uncovAction = UNCOVACTION_STRETCH;
	173
	174	/** An uncovered instance is covered using rule stretching. */
	175	private static final int UNCOVACTION_STRETCH = 0;
	176
	177	/** An uncovered instance is classified according to the training data class distribution. */
	178	private static final int UNCOVACTION_APRIORI = 1;
	179
	180	/** An uncovered instance is not classified at all. */
	181	private static final int UNCOVACTION_REJECT = 2;
	182
	183	/** The tags explaining the uncovered action. */
	184	private static final Tag [] TAGS_UNCOVACTION = {
	185	new Tag(UNCOVACTION_STRETCH, "Apply rule stretching (standard)"),
	186	new Tag(UNCOVACTION_APRIORI, "Vote for the most frequent class"),
	187	new Tag(UNCOVACTION_REJECT, "Reject the decision and abstain")
	188	};
	189
	190
	191	/** Whether using product T-norm (or else min T-norm) */
	192	private int m_tNorm = TNORM_PROD;
	193
	194	/** The Product T-Norm flag. */
	195	private static final int TNORM_PROD = 0;
	196
	197	/** The Minimum T-Norm flag. */
	198	private static final int TNORM_MIN = 1;
	199
	200	/** The tags describing the T-norms */
	201	private static final Tag [] TAGS_TNORM = {
	202	new Tag(TNORM_PROD, "Product T-Norm (standard)"),
	203	new Tag(TNORM_MIN, "Minimum T-Norm")
	204	};
	205
	206
	207	/**
	208	* Returns a string describing classifier
	209	* @return a description suitable for
	210	* displaying in the explorer/experimenter gui
	211	*/
	212	public String globalInfo() {
	213
	214	return "FURIA: Fuzzy Unordered Rule Induction Algorithm\n\n"
	215	+ "Details please see:\n\n"
	216	+ getTechnicalInformation().toString() + "\n\n";
	217	}
	218
	219	/**
	220	* Returns an instance of a TechnicalInformation object, containing
	221	* detailed information about the technical background of this class,
	222	* e.g., paper reference or book this class is based on.
	223	*
	224	* @return the technical information about this class
	225	*/
	226	public TechnicalInformation getTechnicalInformation() {
	227	TechnicalInformation result;
	228
	229	result = new TechnicalInformation(Type.ARTICLE);
	230	result.setValue(Field.AUTHOR, "Jens Christian Huehn and Eyke Huellermeier");
	231	result.setValue(Field.TITLE, "FURIA: An Algorithm for Unordered Fuzzy Rule Induction");
	232	result.setValue(Field.YEAR, "2009");
	233	result.setValue(Field.JOURNAL, "Data Mining and Knowledge Discovery");
	234	return result;
	235	}
	236
	237	/**
	238	* Returns an enumeration describing the available options
	239	* Valid options are: <p>
	240	*
	241	* -F number <br>
	242	* The number of folds for reduced error pruning. One fold is
	243	* used as the pruning set. (Default: 3) <p>
	244	*
	245	* -N number <br>
	246	* The minimal weights of instances within a split.
	247	* (Default: 2) <p>
	248	*
	249	* -O number <br>
	250	* Set the number of runs of optimizations. (Default: 2)<p>
	251	*
	252	* -D <br>
	253	* Whether turn on the debug mode
	254	*
	255	* -S number <br>
	256	* The seed of randomization used in FURIA.(Default: 1)<p>
	257	*
	258	* -E <br>
	259	* Whether NOT check the error rate >= 0.5 in stopping criteria.
	260	* (default: check)<p>
	261	*
	262	* -s <br>
	263	* The action performed for uncovered instances.
	264	* (default: use rule stretching)<p>
	265	*
	266	* -p <br>
	267	* The T-Norm used as fuzzy AND-operator.
	268	* (default: Product T-Norm)<p>
	269	*
	270	* @return an enumeration of all the available options
	271	*/
	272	public Enumeration listOptions() {
	273	Vector newVector = new Vector(8);
	274	newVector.addElement(new Option("\tSet number of folds for REP\n" +
	275	"\tOne fold is used as pruning set.\n" +
	276	"\t(default 3)","F", 1, "-F <number of folds>"));
	277
	278	newVector.addElement(new Option("\tSet the minimal weights of instances\n" +
	279	"\twithin a split.\n" +
	280	"\t(default 2.0)","N", 1, "-N <min. weights>"));
	281
	282	newVector.addElement(new Option("\tSet the number of runs of\n"+
	283	"\toptimizations. (Default: 2)", "O",
	284	1,"-O <number of runs>"));
	285
	286	newVector.addElement(new Option("\tSet whether turn on the\n"+
	287	"\tdebug mode (Default: false)", "D",
	288	0,"-D"));
	289
	290	newVector.addElement(new Option("\tThe seed of randomization\n"+
	291	"\t(Default: 1)", "S",
	292	1,"-S <seed>"));
	293
	294	newVector.addElement(new Option("\tWhether NOT check the error rate>=0.5\n"
	295	+"\tin stopping criteria "
	296	+"\t(default: check)", "E",
	297	0, "-E"));
	298
	299	newVector.addElement(new Option("\tThe action performed for uncovered instances.\n"
	300	+"\t(default: use stretching)", "s",
	301	1, "-s"));
	302
	303	newVector.addElement(new Option("\tThe T-norm used as fuzzy AND-operator.\n"
	304	+"\t(default: Product T-norm)", "p",
	305	1, "-p"));
	306
	307	return newVector.elements();
	308	}
	309
	310	/**
	311	* Parses a given list of options. <p/>
	312	*
	313	<!-- options-start -->
	314	* Valid options are: <p/>
	315	*
	316	* <pre> -F <number of folds>
	317	* Set number of folds for REP
	318	* One fold is used as pruning set.
	319	* (default 3)</pre>
	320	*
	321	* <pre> -N <min. weights>
	322	* Set the minimal weights of instances
	323	* within a split.
	324	* (default 2.0)</pre>
	325	*
	326	* <pre> -O <number of runs>
	327	* Set the number of runs of
	328	* optimizations. (Default: 2)</pre>
	329	*
	330	* <pre> -D
	331	* Set whether turn on the
	332	* debug mode (Default: false)</pre>
	333	*
	334	* <pre> -S <seed>
	335	* The seed of randomization
	336	* (Default: 1)</pre>
	337	*
	338	* <pre> -E
	339	* Whether NOT check the error rate>=0.5
	340	* in stopping criteria (default: check)</pre>
	341	*
	342	* <pre> -s
	343	* The action performed for uncovered instances.
	344	* (default: use stretching)</pre>
	345	*
	346	* <pre> -p
	347	* The T-norm used as fuzzy AND-operator.
	348	* (default: Product T-norm)</pre>
	349	*
	350	<!-- options-end -->
	351	*
	352	* @param options the list of options as an array of strings
	353	* @throws Exception if an option is not supported
	354	*/
	355	public void setOptions(String[] options) throws Exception {
	356	String numFoldsString = Utils.getOption('F', options);
	357	if (numFoldsString.length() != 0)
	358	m_Folds = Integer.parseInt(numFoldsString);
	359	else
	360	m_Folds = 3;
	361
	362	String minNoString = Utils.getOption('N', options);
	363	if (minNoString.length() != 0)
	364	m_MinNo = Double.parseDouble(minNoString);
	365	else
	366	m_MinNo = 2.0;
	367
	368	String seedString = Utils.getOption('S', options);
	369	if (seedString.length() != 0)
	370	m_Seed = Long.parseLong(seedString);
	371	else
	372	m_Seed = 1;
	373
	374	String runString = Utils.getOption('O', options);
	375	if (runString.length() != 0)
	376	m_Optimizations = Integer.parseInt(runString);
	377	else
	378	m_Optimizations = 2;
	379
	380	String tNormString = Utils.getOption('p', options);
	381	if (tNormString.length() != 0)
	382	m_tNorm = Integer.parseInt(tNormString);
	383	else
	384	m_tNorm = TNORM_PROD;
	385
	386	String uncovActionString = Utils.getOption('s', options);
	387	if (uncovActionString.length() != 0)
	388	m_uncovAction = Integer.parseInt(uncovActionString);
	389	else
	390	m_uncovAction = UNCOVACTION_STRETCH;
	391
	392	m_Debug = Utils.getFlag('D', options);
	393
	394	m_CheckErr = !Utils.getFlag('E', options);
	395	}
	396
	397	/**
	398	* Gets the current settings of the Classifier.
	399	*
	400	* @return an array of strings suitable for passing to setOptions
	401	*/
	402	public String [] getOptions() {
	403
	404	String [] options = new String [14];
	405	int current = 0;
	406	options[current++] = "-F"; options[current++] = "" + m_Folds;
	407	options[current++] = "-N"; options[current++] = "" + m_MinNo;
	408	options[current++] = "-O"; options[current++] = "" + m_Optimizations;
	409	options[current++] = "-S"; options[current++] = "" + m_Seed;
	410	options[current++] = "-p"; options[current++] = "" + m_tNorm;
	411	options[current++] = "-s"; options[current++] = "" + m_uncovAction;
	412
	413	if(m_Debug)
	414	options[current++] = "-D";
	415
	416	if(!m_CheckErr)
	417	options[current++] = "-E";
	418
	419	while(current < options.length)
	420	options[current++] = "";
	421
	422	return options;
	423	}
	424
	425	/**
	426	* Returns an enumeration of the additional measure names
	427	* @return an enumeration of the measure names
	428	*/
	429	public Enumeration enumerateMeasures() {
	430	Vector newVector = new Vector(1);
	431	newVector.addElement("measureNumRules");
	432	return newVector.elements();
	433	}
	434
	435	/**
	436	* Returns the value of the named measure
	437	* @param additionalMeasureName the name of the measure to query for its value
	438	* @return the value of the named measure
	439	* @throws IllegalArgumentException if the named measure is not supported
	440	*/
	441	public double getMeasure(String additionalMeasureName) {
	442	if (additionalMeasureName.compareToIgnoreCase("measureNumRules") == 0)
	443	return m_Ruleset.size();
	444	else
	445	throw new IllegalArgumentException(additionalMeasureName+" not supported (FURIA)");
	446	}
	447
	448	/**
	449	* Returns the tip text for this property
	450	* @return tip text for this property suitable for
	451	* displaying in the explorer/experimenter gui
	452	*/
	453	public String foldsTipText() {
	454	return "Determines the amount of data used for pruning. One fold is used for "
	455	+ "pruning, the rest for growing the rules.";
	456	}
	457
	458	/**
	459	* Sets the number of folds to use
	460	*
	461	* @param fold the number of folds
	462	*/
	463	public void setFolds(int fold) {
	464	m_Folds = fold;
	465	}
	466
	467	/**
	468	* Gets the number of folds
	469	*
	470	* @return the number of folds
	471	*/
	472	public int getFolds(){
	473	return m_Folds;
	474	}
	475
	476	/**
	477	* Returns the tip text for this property
	478	* @return tip text for this property suitable for
	479	* displaying in the explorer/experimenter gui
	480	*/
	481	public String minNoTipText() {
	482	return "The minimum total weight of the instances in a rule.";
	483	}
	484
	485	/**
	486	* Sets the minimum total weight of the instances in a rule
	487	*
	488	* @param m the minimum total weight of the instances in a rule
	489	*/
	490	public void setMinNo(double m) {
	491	m_MinNo = m;
	492	}
	493
	494	/**
	495	* Gets the minimum total weight of the instances in a rule
	496	*
	497	* @return the minimum total weight of the instances in a rule
	498	*/
	499	public double getMinNo(){
	500	return m_MinNo;
	501	}
	502
	503	/**
	504	* Returns the tip text for this property
	505	* @return tip text for this property suitable for
	506	* displaying in the explorer/experimenter gui
	507	*/
	508	public String seedTipText() {
	509	return "The seed used for randomizing the data.";
	510	}
	511
	512	/**
	513	* Sets the seed value to use in randomizing the data
	514	*
	515	* @param s the new seed value
	516	*/
	517	public void setSeed(long s) {
	518	m_Seed = s;
	519	}
	520
	521	/**
	522	* Gets the current seed value to use in randomizing the data
	523	*
	524	* @return the seed value
	525	*/
	526	public long getSeed(){
	527	return m_Seed;
	528	}
	529
	530	/**
	531	* Returns the tip text for this property
	532	* @return tip text for this property suitable for
	533	* displaying in the explorer/experimenter gui
	534	*/
	535	public String optimizationsTipText() {
	536	return "The number of optimization runs.";
	537	}
	538
	539	/**
	540	* Sets the number of optimization runs
	541	*
	542	* @param run the number of optimization runs
	543	*/
	544	public void setOptimizations(int run) {
	545	m_Optimizations = run;
	546	}
	547
	548	/**
	549	* Gets the the number of optimization runs
	550	*
	551	* @return the number of optimization runs
	552	*/
	553	public int getOptimizations() {
	554	return m_Optimizations;
	555	}
	556
	557	/**
	558	* Returns the tip text for this property
	559	* @return tip text for this property suitable for
	560	* displaying in the explorer/experimenter gui
	561	*/
	562	public String debugTipText() {
	563	return "Whether debug information is output to the console.";
	564	}
	565
	566	/**
	567	* Sets whether debug information is output to the console
	568	*
	569	* @param d whether debug information is output to the console
	570	*/
	571	public void setDebug(boolean d) {
	572	m_Debug = d;
	573	}
	574
	575	/**
	576	* Gets whether debug information is output to the console
	577	*
	578	* @return whether debug information is output to the console
	579	*/
	580	public boolean getDebug(){
	581	return m_Debug;
	582	}
	583
	584	/**
	585	* Returns the tip text for this property
	586	* @return tip text for this property suitable for
	587	* displaying in the explorer/experimenter gui
	588	*/
	589	public String checkErrorRateTipText() {
	590	return "Whether check for error rate >= 1/2 is included" +
	591	" in stopping criterion.";
	592	}
	593
	594	/**
	595	* Sets whether to check for error rate is in stopping criterion
	596	*
	597	* @param d whether to check for error rate is in stopping criterion
	598	*/
	599	public void setCheckErrorRate(boolean d) {
	600	m_CheckErr = d;
	601	}
	602
	603	/**
	604	* Gets whether to check for error rate is in stopping criterion
	605	*
	606	* @return true if checking for error rate is in stopping criterion
	607	*/
	608	public boolean getCheckErrorRate(){
	609	return m_CheckErr;
	610	}
	611
	612	/**
	613	* Returns the tip text for this property
	614	* @return tip text for this property suitable for
	615	* displaying in the explorer/experimenter gui
	616	*/
	617	public String uncovActionTipText() {
	618	return "Selet the action that is performed for uncovered instances.";
	619	}
	620
	621	/**
	622	* Gets the action that is performed for uncovered instances.
	623	* It can be UNCOVACTION_STRETCH, UNCOVACTION_APRIORI or
	624	* UNCOVACTION_REJECT.
	625	* @return the current TNorm.
	626	*/
	627	public SelectedTag getUncovAction() {
	628	return new SelectedTag(m_uncovAction, TAGS_UNCOVACTION);
	629	}
	630
	631	/**
	632	* Sets the action that is performed for uncovered instances.
	633	* It can be UNCOVACTION_STRETCH, UNCOVACTION_APRIORI or
	634	* UNCOVACTION_REJECT.
	635	* @param newUncovAction the new action.
	636	*/
	637	public void setUncovAction(SelectedTag newUncovAction) {
	638	if (newUncovAction.getTags() == TAGS_UNCOVACTION) {
	639	m_uncovAction = newUncovAction.getSelectedTag().getID();
	640	}
	641	}
	642
	643	/**
	644	* Returns the tip text for this property
	645	* @return tip text for this property suitable for
	646	* displaying in the explorer/experimenter gui
	647	*/
	648	public String TNormTipText() {
	649	return "Choose the T-Norm that is used as fuzzy AND-operator.";
	650	}
	651
	652	/**
	653	* Gets the TNorm used. Will be either TNORM_PROD or TNORM_MIN.
	654	*
	655	* @return the current TNorm.
	656	*/
	657	public SelectedTag getTNorm() {
	658	return new SelectedTag(m_tNorm, TAGS_TNORM);
	659	}
	660
	661	/**
	662	* Sets the TNorm used. Will be either TNORM_PROD or TNORM_MIN.
	663	*
	664	* @param newTNorm the new TNorm.
	665	*/
	666	public void setTNorm(SelectedTag newTNorm) {
	667	if (newTNorm.getTags() == TAGS_TNORM) {
	668	m_tNorm = newTNorm.getSelectedTag().getID();
	669	}
	670	}
	671
	672
	673	/**
	674	* Get the ruleset generated by FURIA
	675	*
	676	* @return the ruleset
	677	*/
	678	public FastVector getRuleset(){ return m_Ruleset; }
	679
	680	/**
	681	* Get the statistics of the ruleset in the given position
	682	*
	683	* @param pos the position of the stats, assuming correct
	684	* @return the statistics of the ruleset in the given position
	685	*/
	686	public RuleStats getRuleStats(int pos) {
	687	return (RuleStats)m_RulesetStats.elementAt(pos);
	688	}
	689
	690	/**
	691	* The single antecedent in the rule, which is composed of an attribute and
	692	* the corresponding value. There are two inherited classes, namely NumericAntd
	693	* and NominalAntd in which the attributes are numeric and nominal respectively.
	694	*/
	695	protected abstract class Antd
	696	implements WeightedInstancesHandler, Copyable, Serializable {
	697
	698	/** The attribute of the antecedent */
	699	public Attribute att;
	700
	701	/** The attribute value of the antecedent.
	702	For numeric attribute, value is either 0(1st bag) or 1(2nd bag) */
	703	public double value;
	704
	705	/** The maximum infoGain achieved by this antecedent test
	706	* in the growing data */
	707	protected double maxInfoGain;
	708
	709	/** The accurate rate of this antecedent test on the growing data */
	710	protected double accuRate;
	711
	712	/** The coverage of this antecedent in the growing data */
	713	protected double cover;
	714
	715	/** The accurate data for this antecedent in the growing data */
	716	protected double accu;
	717
	718
	719	/** Confidence / weight of this rule for the rule stretching procedure that
	720	* is returned when this is the last antecedent of the rule. */
	721	double weightOfTheRuleWhenItIsPrunedAfterThisAntecedent = 0;
	722
	723	/** Confidence / weight of this antecedent. */
	724	public double m_confidence = 0.0;
	725
	726	/**
	727	* Constructor
	728	*/
	729	public Antd(Attribute a){
	730	att=a;
	731	value=Double.NaN;
	732	maxInfoGain = 0;
	733	accuRate = Double.NaN;
	734	cover = Double.NaN;
	735	accu = Double.NaN;
	736	}
	737
	738	/* The abstract members for inheritance */
	739	public abstract Instances[] splitData(Instances data, double defAcRt,
	740	double cla);
	741	public abstract double covers(Instance inst);
	742	public abstract String toString();
	743
	744	/**
	745	* Implements Copyable
	746	*
	747	* @return a copy of this object
	748	*/
	749	public abstract Object copy();
	750
	751	/* Get functions of this antecedent */
	752	public Attribute getAttr(){ return att; }
	753	public double getAttrValue(){ return value; }
	754	public double getMaxInfoGain(){ return maxInfoGain; }
	755	public double getAccuRate(){ return accuRate; }
	756	public double getAccu(){ return accu; }
	757	public double getCover(){ return cover; }
	758	}
	759
	760	/**
	761	* The antecedent with numeric attribute
	762	*/
	763	public class
	764	NumericAntd extends Antd {
	765
	766	/** for serialization */
	767	static final long serialVersionUID = 5699457269983735442L;
	768
	769	/** The split point for this numeric antecedent */
	770	public double splitPoint;
	771
	772	/** The edge point for the fuzzy set of this numeric antecedent */
	773	public double supportBound;
	774
	775	/** A flag determining whether this antecedent was successfully fuzzified yet*/
	776	public boolean fuzzyYet = false;
	777
	778
	779	/**
	780	* Constructor
	781	*/
	782	public NumericAntd(Attribute a){
	783	super(a);
	784	splitPoint = Double.NaN;
	785	supportBound = Double.NaN;
	786	}
	787
	788	/**
	789	* Get split point of this numeric antecedent
	790	*
	791	* @return the split point of this numeric antecedent
	792	*/
	793	public double getSplitPoint(){
	794	return splitPoint;
	795	}
	796
	797	/**
	798	* Implements Copyable
	799	*
	800	* @return a copy of this object
	801	*/
	802	public Object copy(){
	803	NumericAntd na = new NumericAntd(getAttr());
	804	na.m_confidence = m_confidence;
	805	na.value = this.value;
	806	na.splitPoint = this.splitPoint;
	807	na.supportBound = this.supportBound;
	808	na.fuzzyYet = this.fuzzyYet;
	809	return na;
	810	}
	811
	812
	813
	814	/**
	815	* Implements the splitData function.
	816	* This procedure is to split the data into two bags according
	817	* to the information gain of the numeric attribute value
	818	* The maximum infoGain is also calculated.
	819	*
	820	* @param insts the data to be split
	821	* @param defAcRt the default accuracy rate for data
	822	* @param cl the class label to be predicted
	823	* @return the array of data after split
	824	*/
	825	public Instances[] splitData(Instances insts, double defAcRt,
	826	double cl){
	827	Instances data = insts;
	828	int total=data.numInstances();// Total number of instances without
	829	// missing value for att
	830
	831	int split=1; // Current split position
	832	int prev=0; // Previous split position
	833	int finalSplit=split; // Final split position
	834	maxInfoGain = 0;
	835	value = 0;
	836
	837	double fstCover=0, sndCover=0, fstAccu=0, sndAccu=0;
	838
	839	data.sort(att);
	840	// Find the las instance without missing value
	841	for(int x=0; x<data.numInstances(); x++){
	842	Instance inst = data.instance(x);
	843	if(inst.isMissing(att)){
	844	total = x;
	845	break;
	846	}
	847
	848	sndCover += inst.weight();
	849	if(Utils.eq(inst.classValue(), cl))
	850	sndAccu += inst.weight();
	851	}
	852
	853	if(total == 0) return null; // Data all missing for the attribute
	854	splitPoint = data.instance(total-1).value(att);
	855
	856	for(; split <= total; split++){
	857	if((split == total) \|\|
	858	(data.instance(split).value(att) > // Can't split within
	859	data.instance(prev).value(att))){ // same value
	860
	861	for(int y=prev; y<split; y++){
	862	Instance inst = data.instance(y);
	863	fstCover += inst.weight();
	864	if(Utils.eq(data.instance(y).classValue(), cl)){
	865	fstAccu += inst.weight(); // First bag positive# ++
	866	}
	867	}
	868
	869	double fstAccuRate = (fstAccu+1.0)/(fstCover+1.0),
	870	sndAccuRate = (sndAccu+1.0)/(sndCover+1.0);
	871
	872	/* Which bag has higher information gain? */
	873	boolean isFirst;
	874	double fstInfoGain, sndInfoGain;
	875	double accRate, infoGain, coverage, accurate;
	876
	877	fstInfoGain =
	878	//Utils.eq(defAcRt, 1.0) ?
	879	//fstAccu/(double)numConds :
	880	fstAccu*(Utils.log2(fstAccuRate)-Utils.log2(defAcRt));
	881
	882	sndInfoGain =
	883	//Utils.eq(defAcRt, 1.0) ?
	884	//sndAccu/(double)numConds :
	885	sndAccu*(Utils.log2(sndAccuRate)-Utils.log2(defAcRt));
	886
	887	if(fstInfoGain > sndInfoGain){
	888	isFirst = true;
	889	infoGain = fstInfoGain;
	890	accRate = fstAccuRate;
	891	accurate = fstAccu;
	892	coverage = fstCover;
	893	}
	894	else{
	895	isFirst = false;
	896	infoGain = sndInfoGain;
	897	accRate = sndAccuRate;
	898	accurate = sndAccu;
	899	coverage = sndCover;
	900	}
	901
	902	/* Check whether so far the max infoGain */
	903	if(infoGain > maxInfoGain){
	904	splitPoint = data.instance(prev).value(att);
	905	value = (isFirst) ? 0 : 1;
	906	accuRate = accRate;
	907	accu = accurate;
	908	cover = coverage;
	909	maxInfoGain = infoGain;
	910	finalSplit = (isFirst) ? split : prev;
	911	}
	912
	913	for(int y=prev; y<split; y++){
	914	Instance inst = data.instance(y);
	915	sndCover -= inst.weight();
	916	if(Utils.eq(data.instance(y).classValue(), cl)){
	917	sndAccu -= inst.weight(); // Second bag positive# --
	918	}
	919	}
	920	prev=split;
	921	}
	922	}
	923
	924	/* Split the data */
	925	Instances[] splitData = new Instances[2];
	926	splitData[0] = new Instances(data, 0, finalSplit);
	927	splitData[1] = new Instances(data, finalSplit, total-finalSplit);
	928
	929	return splitData;
	930	}
	931
	932
	933	/**
	934	* The degree of coverage for the instance given that antecedent
	935	*
	936	* @param inst the instance in question
	937	* @return the numeric value indicating the membership of the instance
	938	* for this antecedent
	939	*/
	940	public double covers(Instance inst){
	941	double isCover=0;
	942	if(!inst.isMissing(att)){
	943	if((int)value == 0){ // First bag
	944	if(inst.value(att) <= splitPoint)
	945	isCover=1;
	946	else if(fuzzyYet && (inst.value(att) > splitPoint) && (inst.value(att) < supportBound ))
	947	isCover= 1-((inst.value(att) - splitPoint)/(supportBound-splitPoint));
	948	}else{
	949	if(inst.value(att) >= splitPoint) // Second bag
	950	isCover=1;
	951	else if(fuzzyYet && inst.value(att) < splitPoint && (inst.value(att) > supportBound ))
	952	isCover= 1-((splitPoint - inst.value(att)) /(splitPoint-supportBound));
	953	}
	954	}
	955
	956	return isCover;
	957	}
	958
	959	/**
	960	* Prints this antecedent
	961	*
	962	* @return a textual description of this antecedent
	963	*/
	964	public String toString() {
	965	if (value == 0){
	966	if (fuzzyYet){
	967	return (att.name() + " in [-inf, -inf, " + Utils.doubleToString(splitPoint, 6) + ", " + Utils.doubleToString(supportBound, 6) + "]");
	968	}
	969	return (att.name() + " in [-inf, " + Utils.doubleToString(splitPoint, 6) + "]");
	970	}else{
	971	if (fuzzyYet){
	972	return (att.name() + " in [" + Utils.doubleToString(supportBound, 6) + ", " + Utils.doubleToString(splitPoint, 6) + ", inf, inf]");
	973	}
	974	return (att.name() + " in [" + Utils.doubleToString(splitPoint, 6) + ", inf]");
	975	}
	976
	977	}
	978
	979	}
	980
	981
	982	/**
	983	* The antecedent with nominal attribute
	984	*/
	985	protected class NominalAntd
	986	extends Antd{
	987
	988	/** for serialization */
	989	static final long serialVersionUID = -9102297038837585135L;
	990
	991	/* The parameters of infoGain calculated for each attribute value
	992	* in the growing data */
	993	private double[] accurate;
	994	private double[] coverage;
	995
	996	/**
	997	* Constructor
	998	*/
	999	public NominalAntd(Attribute a){
	1000	super(a);
	1001	int bag = att.numValues();
	1002	accurate = new double[bag];
	1003	coverage = new double[bag];
	1004	}
	1005
	1006	/**
	1007	* Implements Copyable
	1008	*
	1009	* @return a copy of this object
	1010	*/
	1011	public Object copy(){
	1012	Antd antec = new NominalAntd(getAttr());
	1013	antec.m_confidence = m_confidence;
	1014	antec.value = this.value;
	1015	return antec;
	1016	}
	1017
	1018	/**
	1019	* Implements the splitData function.
	1020	* This procedure is to split the data into bags according
	1021	* to the nominal attribute value
	1022	* The infoGain for each bag is also calculated.
	1023	*
	1024	* @param data the data to be split
	1025	* @param defAcRt the default accuracy rate for data
	1026	* @param cl the class label to be predicted
	1027	* @return the array of data after split
	1028	*/
	1029	public Instances[] splitData(Instances data, double defAcRt,
	1030	double cl){
	1031	int bag = att.numValues();
	1032	Instances[] splitData = new Instances[bag];
	1033
	1034	for(int x=0; x<bag; x++){
	1035	splitData[x] = new Instances(data, data.numInstances());
	1036	accurate[x] = 0;
	1037	coverage[x] = 0;
	1038	}
	1039
	1040	for(int x=0; x<data.numInstances(); x++){
	1041	Instance inst=data.instance(x);
	1042	if(!inst.isMissing(att)){
	1043	int v = (int)inst.value(att);
	1044	splitData[v].add(inst);
	1045	coverage[v] += inst.weight();
	1046	if((int)inst.classValue() == (int)cl)
	1047	accurate[v] += inst.weight();
	1048	}
	1049	}
	1050
	1051	for(int x=0; x<bag; x++){
	1052	double t = coverage[x]+1.0;
	1053	double p = accurate[x] + 1.0;
	1054	double infoGain =
	1055	//Utils.eq(defAcRt, 1.0) ?
	1056	//accurate[x]/(double)numConds :
	1057	accurate[x]*(Utils.log2(p/t)-Utils.log2(defAcRt));
	1058
	1059	if(infoGain > maxInfoGain){
	1060	maxInfoGain = infoGain;
	1061	cover = coverage[x];
	1062	accu = accurate[x];
	1063	accuRate = p/t;
	1064	value = (double)x;
	1065	}
	1066	}
	1067
	1068	return splitData;
	1069	}
	1070
	1071	/**
	1072	* Whether the instance is covered by this antecedent
	1073	*
	1074	* @param inst the instance in question
	1075	* @return the boolean value indicating whether the instance is
	1076	* covered by this antecedent
	1077	*/
	1078	public double covers(Instance inst){
	1079	double isCover=0;
	1080	if(!inst.isMissing(att)){
	1081	if((int)inst.value(att) == (int)value)
	1082	isCover=1;
	1083	}
	1084	return isCover;
	1085	}
	1086
	1087	/**
	1088	* Prints this antecedent
	1089	*
	1090	* @return a textual description of this antecedent
	1091	*/
	1092	public String toString() {
	1093	return (att.name() + " = " +att.value((int)value));
	1094	}
	1095	}
	1096
	1097
	1098	/**
	1099	* This class implements a single rule that predicts specified class.
	1100	*
	1101	* A rule consists of antecedents "AND"ed together and the consequent
	1102	* (class value) for the classification.
	1103	* In this class, the Information Gain (p*[log(p/t) - log(P/T)]) is used to
	1104	* select an antecedent and Reduced Error Prunning (REP) with the metric
	1105	* of accuracy rate p/(p+n) or (TP+TN)/(P+N) is used to prune the rule.
	1106	*/
	1107	public class RipperRule
	1108	extends Rule{
	1109
	1110	/** for serialization */
	1111	static final long serialVersionUID = -2410020717305262952L;
	1112
	1113	/** The internal representation of the class label to be predicted */
	1114	double m_Consequent = -1;
	1115
	1116	/** The vector of antecedents of this rule*/
	1117	public FastVector m_Antds = null;
	1118
	1119	/** Constructor */
	1120	public RipperRule(){
	1121	m_Antds = new FastVector();
	1122	}
	1123
	1124	/**
	1125	* Sets the internal representation of the class label to be predicted
	1126	*
	1127	* @param cl the internal representation of the class label to be predicted
	1128	*/
	1129	public void setConsequent(double cl) {
	1130	m_Consequent = cl;
	1131	}
	1132
	1133	/**
	1134	* Gets the internal representation of the class label to be predicted
	1135	*
	1136	* @return the internal representation of the class label to be predicted
	1137	*/
	1138	public double getConsequent() {
	1139	return m_Consequent;
	1140	}
	1141
	1142	/**
	1143	* Get a shallow copy of this rule
	1144	*
	1145	* @return the copy
	1146	*/
	1147	public Object copy(){
	1148	RipperRule copy = new RipperRule();
	1149	copy.setConsequent(getConsequent());
	1150	copy.m_Antds = (FastVector)this.m_Antds.copyElements();
	1151	return copy;
	1152	}
	1153
	1154
	1155
	1156	/**
	1157	* The degree of coverage instance covered by this rule
	1158	*
	1159	* @param datum the instance in question
	1160	* @return the degree to which the instance
	1161	* is covered by this rule
	1162	*/
	1163	public double coverageDegree(Instance datum){
	1164	double coverage = 1;
	1165
	1166	for(int i=0; i<m_Antds.size(); i++){
	1167	Antd antd = (Antd)m_Antds.elementAt(i);
	1168	if(m_tNorm == TNORM_PROD){
	1169	// Product T-Norm
	1170	if (antd instanceof NumericAntd)
	1171	coverage *= ((NumericAntd)antd).covers(datum);
	1172	else
	1173	coverage *= antd.covers(datum);
	1174	}else{
	1175	// Min T-Norm
	1176	if (antd instanceof NumericAntd)
	1177	coverage = Math.min(coverage, ((NumericAntd)antd).covers(datum));
	1178	else
	1179	coverage = Math.min(coverage, antd.covers(datum));
	1180	}
	1181
	1182	}
	1183
	1184	return coverage;
	1185	}
	1186
	1187	/**
	1188	* Whether the instance covered by this rule
	1189	*
	1190	* @param datum the instance in question
	1191	* @return the boolean value indicating whether the instance
	1192	* is covered by this rule
	1193	*/
	1194	public boolean covers(Instance datum){
	1195	if (coverageDegree(datum) == 0){
	1196	return false;
	1197	}else{
	1198	return true;
	1199	}
	1200	}
	1201
	1202	/**
	1203	* Whether this rule has antecedents, i.e. whether it is a default rule
	1204	*
	1205	* @return the boolean value indicating whether the rule has antecedents
	1206	*/
	1207	public boolean hasAntds(){
	1208	if (m_Antds == null)
	1209	return false;
	1210	else
	1211	return (m_Antds.size() > 0);
	1212	}
	1213
	1214	/**
	1215	* the number of antecedents of the rule
	1216	*
	1217	* @return the size of this rule
	1218	*/
	1219	public double size(){ return (double)m_Antds.size(); }
	1220
	1221
	1222	/**
	1223	* Private function to compute default number of accurate instances
	1224	* in the specified data for the consequent of the rule
	1225	*
	1226	* @param data the data in question
	1227	* @return the default accuracy number
	1228	*/
	1229	private double computeDefAccu(Instances data){
	1230	double defAccu=0;
	1231	for(int i=0; i<data.numInstances(); i++){
	1232	Instance inst = data.instance(i);
	1233	if((int)inst.classValue() == (int)m_Consequent)
	1234	defAccu += inst.weight();
	1235	}
	1236	return defAccu;
	1237	}
	1238
	1239
	1240	/**
	1241	* Build one rule using the growing data
	1242	*
	1243	* @param data the growing data used to build the rule
	1244	* @throws Exception if the consequent is not set yet
	1245	*/
	1246	public void grow(Instances data) throws Exception {
	1247	if(m_Consequent == -1)
	1248	throw new Exception(" Consequent not set yet.");
	1249
	1250	Instances growData = data;
	1251	double sumOfWeights = growData.sumOfWeights();
	1252	if(!Utils.gr(sumOfWeights, 0.0))
	1253	return;
	1254
	1255	/* Compute the default accurate rate of the growing data */
	1256	double defAccu = computeDefAccu(growData);
	1257	double defAcRt = (defAccu+1.0)/(sumOfWeights+1.0);
	1258
	1259	/* Keep the record of which attributes have already been used*/
	1260	boolean[] used=new boolean [growData.numAttributes()];
	1261	for (int k=0; k<used.length; k++)
	1262	used[k]=false;
	1263	int numUnused=used.length;
	1264
	1265	// If there are already antecedents existing
	1266	for(int j=0; j < m_Antds.size(); j++){
	1267	Antd antdj = (Antd)m_Antds.elementAt(j);
	1268	if(!antdj.getAttr().isNumeric()){
	1269	used[antdj.getAttr().index()]=true;
	1270	numUnused--;
	1271	}
	1272	}
	1273
	1274	double maxInfoGain;
	1275	while (Utils.gr(growData.numInstances(), 0.0) &&
	1276	(numUnused > 0)
	1277	&& Utils.sm(defAcRt, 1.0)
	1278	){
	1279
	1280	// We require that infoGain be positive
	1281	/*if(numAntds == originalSize)
	1282	maxInfoGain = 0.0; // At least one condition allowed
	1283	else
	1284	maxInfoGain = Utils.eq(defAcRt, 1.0) ?
	1285	defAccu/(double)numAntds : 0.0; */
	1286	maxInfoGain = 0.0;
	1287
	1288	/* Build a list of antecedents */
	1289	Antd oneAntd=null;
	1290	Instances coverData = null;
	1291	Enumeration enumAttr=growData.enumerateAttributes();
	1292
	1293	/* Build one condition based on all attributes not used yet*/
	1294	while (enumAttr.hasMoreElements()){
	1295	Attribute att= (Attribute)(enumAttr.nextElement());
	1296
	1297	if(m_Debug)
	1298	System.err.println("\nOne condition: size = "
	1299	+ growData.sumOfWeights());
	1300
	1301	Antd antd =null;
	1302	if(att.isNumeric())
	1303	antd = new NumericAntd(att);
	1304	else
	1305	antd = new NominalAntd(att);
	1306
	1307	if(!used[att.index()]){
	1308	/* Compute the best information gain for each attribute,
	1309	it's stored in the antecedent formed by this attribute.
	1310	This procedure returns the data covered by the antecedent*/
	1311	Instances coveredData = computeInfoGain(growData, defAcRt,
	1312	antd);
	1313	if(coveredData != null){
	1314	double infoGain = antd.getMaxInfoGain();
	1315	if(m_Debug)
	1316	System.err.println("Test of \'"+antd.toString()+
	1317	"\': infoGain = "+
	1318	infoGain + " \| Accuracy = " +
	1319	antd.getAccuRate()+
	1320	"="+antd.getAccu()
	1321	+"/"+antd.getCover()+
	1322	" def. accuracy: "+defAcRt);
	1323
	1324	if(infoGain > maxInfoGain){
	1325	oneAntd=antd;
	1326	coverData = coveredData;
	1327	maxInfoGain = infoGain;
	1328	}
	1329	}
	1330	}
	1331	}
	1332
	1333	if(oneAntd == null) break; // Cannot find antds
	1334	if(Utils.sm(oneAntd.getAccu(), m_MinNo)) break;// Too low coverage
	1335
	1336	//Numeric attributes can be used more than once
	1337	if(!oneAntd.getAttr().isNumeric()){
	1338	used[oneAntd.getAttr().index()]=true;
	1339	numUnused--;
	1340	}
	1341
	1342	m_Antds.addElement(oneAntd);
	1343
	1344
	1345	growData = coverData;// Grow data size is shrinking
	1346	defAcRt = oneAntd.getAccuRate();
	1347	}
	1348	}
	1349
	1350
	1351	/**
	1352	* Compute the best information gain for the specified antecedent
	1353	*
	1354	* @param instances the data based on which the infoGain is computed
	1355	* @param defAcRt the default accuracy rate of data
	1356	* @param antd the specific antecedent
	1357	* @return the data covered by the antecedent
	1358	*/
	1359	private Instances computeInfoGain(Instances instances, double defAcRt,
	1360	Antd antd){
	1361	Instances data = instances;
	1362
	1363	/* Split the data into bags.
	1364	The information gain of each bag is also calculated in this procedure */
	1365	Instances[] splitData = antd.splitData(data, defAcRt,
	1366	m_Consequent);
	1367
	1368	/* Get the bag of data to be used for next antecedents */
	1369	if(splitData != null)
	1370	return splitData[(int)antd.getAttrValue()];
	1371	else return null;
	1372	}
	1373
	1374	/**
	1375	* Prune all the possible final sequences of the rule using the
	1376	* pruning data. The measure used to prune the rule is based on
	1377	* flag given.
	1378	*
	1379	* @param pruneData the pruning data used to prune the rule
	1380	* @param useWhole flag to indicate whether use the error rate of
	1381	* the whole pruning data instead of the data covered
	1382	*/
	1383	public void prune(Instances pruneData, boolean useWhole){
	1384	Instances data = pruneData;
	1385
	1386	double total = data.sumOfWeights();
	1387	if(!Utils.gr(total, 0.0))
	1388	return;
	1389
	1390	/* The default accurate # and rate on pruning data */
	1391	double defAccu=computeDefAccu(data);
	1392
	1393	if(m_Debug)
	1394	System.err.println("Pruning with " + defAccu +
	1395	" positive data out of " + total +
	1396	" instances");
	1397
	1398	int size=m_Antds.size();
	1399	if(size == 0) return; // Default rule before pruning
	1400
	1401	double[] worthRt = new double[size];
	1402	double[] coverage = new double[size];
	1403	double[] worthValue = new double[size];
	1404	for(int w=0; w<size; w++){
	1405	worthRt[w]=coverage[w]=worthValue[w]=0.0;
	1406	}
	1407
	1408	/* Calculate accuracy parameters for all the antecedents in this rule */
	1409	double tn = 0.0; // True negative if useWhole
	1410	for(int x=0; x<size; x++){
	1411	Antd antd=(Antd)m_Antds.elementAt(x);
	1412	Instances newData = data;
	1413	data = new Instances(newData, 0); // Make data empty
	1414
	1415	for(int y=0; y<newData.numInstances(); y++){
	1416	Instance ins=newData.instance(y);
	1417
	1418	if(antd.covers(ins)>0){ // Covered by this antecedent
	1419	coverage[x] += ins.weight();
	1420	data.add(ins); // Add to data for further pruning
	1421	if((int)ins.classValue() == (int)m_Consequent) // Accurate prediction
	1422	worthValue[x] += ins.weight();
	1423	}
	1424	else if(useWhole){ // Not covered
	1425	if((int)ins.classValue() != (int)m_Consequent)
	1426	tn += ins.weight();
	1427	}
	1428	}
	1429
	1430	if(useWhole){
	1431	worthValue[x] += tn;
	1432	worthRt[x] = worthValue[x] / total;
	1433	}
	1434	else // Note if coverage is 0, accuracy is 0.5
	1435	worthRt[x] = (worthValue[x]+1.0)/(coverage[x]+2.0);
	1436	}
	1437
	1438	double maxValue = (defAccu+1.0)/(total+2.0);
	1439	int maxIndex = -1;
	1440	for(int i=0; i<worthValue.length; i++){
	1441	if(m_Debug){
	1442	double denom = useWhole ? total : coverage[i];
	1443	System.err.println(i+"(useAccuray? "+!useWhole+"): "
	1444	+ worthRt[i] +
	1445	"="+worthValue[i]+
	1446	"/"+denom);
	1447	}
	1448	if(worthRt[i] > maxValue){ // Prefer to the
	1449	maxValue = worthRt[i]; // shorter rule
	1450	maxIndex = i;
	1451	}
	1452	}
	1453
	1454	if (maxIndex==-1) return;
	1455
	1456	/* Prune the antecedents according to the accuracy parameters */
	1457	for(int z=size-1;z>maxIndex;z--)
	1458	m_Antds.removeElementAt(z);
	1459	}
	1460
	1461	/**
	1462	* Prints this rule
	1463	*
	1464	* @param classAttr the class attribute in the data
	1465	* @return a textual description of this rule
	1466	*/
	1467	public String toString(Attribute classAttr) {
	1468	StringBuffer text = new StringBuffer();
	1469	if(m_Antds.size() > 0){
	1470	for(int j=0; j< (m_Antds.size()-1); j++)
	1471	text.append("(" + ((Antd)(m_Antds.elementAt(j))).toString()+ ") and ");
	1472	text.append("("+((Antd)(m_Antds.lastElement())).toString() + ")");
	1473	}
	1474	text.append(" => " + classAttr.name() +
	1475	"=" + classAttr.value((int)m_Consequent));
	1476
	1477	return text.toString();
	1478	}
	1479
	1480	/**
	1481	* The fuzzification procedure
	1482	* @param data training data
	1483	* @param allWeightsAreOne flag whether all instances have weight 1. If this is the case branch-and-bound is possible for speed-up.
	1484	*/
	1485	public void fuzzify(Instances data, boolean allWeightsAreOne){
	1486	// Determine whether there are numeric antecedents that can be fuzzified.
	1487	if (m_Antds == null) return;
	1488	int numNumericAntds = 0;
	1489	for (int i = 0; i < m_Antds.size(); i++){
	1490	if (m_Antds.elementAt(i) instanceof NumericAntd)
	1491	numNumericAntds++;
	1492	}
	1493	if (numNumericAntds == 0)
	1494	return;
	1495
	1496	double maxPurity = Double.NEGATIVE_INFINITY;
	1497	boolean[] finishedAntecedents = new boolean[m_Antds.size()];
	1498	int numFinishedAntecedents = 0;
	1499
	1500	// Loop until all antecdents have been fuzzified
	1501	while (numFinishedAntecedents<m_Antds.size()){
	1502	double maxPurityOfAllAntecedents = Double.NEGATIVE_INFINITY;
	1503	int bestAntecedentsIndex = -1;
	1504	double bestSupportBoundForAllAntecedents = Double.NaN;
	1505
	1506	Instances relevantData = new Instances(data,0);
	1507	for (int j = 0; j < m_Antds.size(); j++){
	1508	if(finishedAntecedents[j]) continue;
	1509
	1510	relevantData = new Instances (data);
	1511	/*
	1512	* Remove instances which are not relevant, because they are not covered
	1513	* by the _other_ antecedents.
	1514	*/
	1515	for (int k = 0; k < m_Antds.size(); k++){
	1516	if (k==j) continue;
	1517	Antd exclusionAntd = ((Antd)m_Antds.elementAt(k));
	1518	for (int y = 0; y < relevantData.numInstances(); y++){
	1519	if (exclusionAntd.covers(relevantData.instance(y)) == 0){
	1520	relevantData.delete(y--);
	1521	}
	1522	}
	1523	}
	1524
	1525	// test whether this antecedent is numeric and whether there is data for making it fuzzy
	1526	if (relevantData.attribute(((Antd)m_Antds.elementAt(j)).att.index()).isNumeric() && relevantData.numInstances()>0){
	1527	// Get a working copy of this antecedent
	1528	NumericAntd currentAntd = (NumericAntd) ((NumericAntd) m_Antds.elementAt(j)).copy();
	1529	currentAntd.fuzzyYet=true;
	1530
	1531	relevantData.deleteWithMissing(currentAntd.att.index());
	1532
	1533	double sumOfWeights = relevantData.sumOfWeights();
	1534	if(!Utils.gr(sumOfWeights, 0.0))
	1535	return;
	1536
	1537	relevantData.sort(currentAntd.att.index());
	1538
	1539	double maxPurityForThisAntecedent = 0;
	1540	double bestFoundSupportBound = Double.NaN;
	1541
	1542	double lastAccu = 0;
	1543	double lastCover = 0;
	1544	// Test all possible edge points
	1545	if (currentAntd.value == 0){
	1546	for (int k = 1; k < relevantData.numInstances(); k++){
	1547	// break the loop if there is no gain (only works when all instances have weight 1)
	1548	if ((lastAccu+(relevantData.numInstances()-k-1))/(lastCover+(relevantData.numInstances()-k-1)) < maxPurityForThisAntecedent && allWeightsAreOne){
	1549	break;
	1550	}
	1551
	1552	// Bag 1
	1553	if (currentAntd.splitPoint < relevantData.instance(k).value(currentAntd.att.index())
	1554	&& relevantData.instance(k).value(currentAntd.att.index()) != relevantData.instance(k-1).value(currentAntd.att.index())){
	1555	currentAntd.supportBound = relevantData.instance(k).value(currentAntd.att.index());
	1556
	1557	// Calculate the purity of this fuzzification
	1558	double[] accuArray = new double[relevantData.numInstances()];
	1559	double[] coverArray = new double[relevantData.numInstances()];
	1560	for (int i = 0; i < relevantData.numInstances(); i++){
	1561	coverArray[i] = relevantData.instance(i).weight();
	1562	double coverValue = currentAntd.covers(relevantData.instance(i));
	1563	if (coverArray[i] >= coverValue*relevantData.instance(i).weight()){
	1564	coverArray[i] = coverValue*relevantData.instance(i).weight();
	1565	if (relevantData.instance(i).classValue() == m_Consequent){
	1566	accuArray[i] = coverValue*relevantData.instance(i).weight();
	1567	}
	1568	}
	1569	}
	1570
	1571	// Test whether this fuzzification is the best one for this antecedent.
	1572	// Keep it if this is the case.
	1573	double purity = (Utils.sum(accuArray)) / (Utils.sum(coverArray));
	1574	if (purity >= maxPurityForThisAntecedent){
	1575	maxPurityForThisAntecedent =purity;
	1576	bestFoundSupportBound = currentAntd.supportBound;
	1577	}
	1578	lastAccu = Utils.sum(accuArray);
	1579	lastCover = Utils.sum(coverArray);
	1580	}
	1581	}
	1582	}else{
	1583	for (int k = relevantData.numInstances()-2; k >=0; k--){
	1584	// break the loop if there is no gain (only works when all instances have weight 1)
	1585	if ((lastAccu+(k))/(lastCover+(k)) < maxPurityForThisAntecedent && allWeightsAreOne){
	1586	break;
	1587	}
	1588
	1589	//Bag 2
	1590	if (currentAntd.splitPoint > relevantData.instance(k).value(currentAntd.att.index())
	1591	&& relevantData.instance(k).value(currentAntd.att.index()) != relevantData.instance(k+1).value(currentAntd.att.index())){
	1592	currentAntd.supportBound = relevantData.instance(k).value(currentAntd.att.index());
	1593
	1594	// Calculate the purity of this fuzzification
	1595	double[] accuArray = new double[relevantData.numInstances()];
	1596	double[] coverArray = new double[relevantData.numInstances()];
	1597	for (int i = 0; i < relevantData.numInstances(); i++){
	1598	coverArray[i] = relevantData.instance(i).weight();
	1599	double coverValue = currentAntd.covers(relevantData.instance(i));
	1600	if (coverArray[i] >= coverValue*relevantData.instance(i).weight()){
	1601	coverArray[i] = coverValue*relevantData.instance(i).weight();
	1602	if (relevantData.instance(i).classValue() == m_Consequent){
	1603	accuArray[i] = coverValue*relevantData.instance(i).weight();
	1604	}
	1605	}
	1606	}
	1607
	1608	// Test whether this fuzzification is the best one for this antecedent.
	1609	// Keep it if this is the case.
	1610	double purity = (Utils.sum(accuArray)) / (Utils.sum(coverArray));
	1611	if (purity >= maxPurityForThisAntecedent){
	1612	maxPurityForThisAntecedent =purity;
	1613	bestFoundSupportBound = currentAntd.supportBound;
	1614	}
	1615	lastAccu = Utils.sum(accuArray);
	1616	lastCover = Utils.sum(coverArray);
	1617	}
	1618	}
	1619
	1620	}
	1621
	1622	// Test whether the best fuzzification for this antecedent is the best one of all
	1623	// antecedents considered so far.
	1624	// Keep it if this is the case.
	1625	if (maxPurityForThisAntecedent>maxPurityOfAllAntecedents){
	1626	bestAntecedentsIndex = j;
	1627	bestSupportBoundForAllAntecedents = bestFoundSupportBound;
	1628	maxPurityOfAllAntecedents = maxPurityForThisAntecedent;
	1629	}
	1630	}else{
	1631	// Deal with a nominal antecedent.
	1632	// Since there is no fuzzification it is already finished.
	1633	finishedAntecedents[j] = true;
	1634	numFinishedAntecedents++;
	1635	continue;
	1636	}
	1637	}
	1638
	1639	// Make the fuzzification step for the current antecedent real.
	1640	if (maxPurity <= maxPurityOfAllAntecedents){
	1641	if (Double.isNaN(bestSupportBoundForAllAntecedents)){
	1642	((NumericAntd)m_Antds.elementAt(bestAntecedentsIndex)).supportBound = ((NumericAntd)m_Antds.elementAt(bestAntecedentsIndex)).splitPoint;
	1643	}else{
	1644	((NumericAntd)m_Antds.elementAt(bestAntecedentsIndex)).supportBound = bestSupportBoundForAllAntecedents;
	1645	((NumericAntd)m_Antds.elementAt(bestAntecedentsIndex)).fuzzyYet = true;
	1646	}
	1647	maxPurity = maxPurityOfAllAntecedents;
	1648	}
	1649	finishedAntecedents[bestAntecedentsIndex] = true;
	1650	numFinishedAntecedents++;
	1651	}
	1652
	1653	}
	1654
	1655	/**
	1656	* Calculation of the rule weights / confidences for all beginning rule stumps.
	1657	* @param data The training data
	1658	*/
	1659	public void calculateConfidences(Instances data) {
	1660	RipperRule tempRule = (RipperRule) this.copy();
	1661
	1662	while(tempRule.hasAntds()){
	1663	double acc = 0;
	1664	double cov = 0;
	1665	for (int i = 0; i < data.numInstances(); i++){
	1666	double membershipValue = tempRule.coverageDegree(data.instance(i)) * data.instance(i).weight();
	1667	cov += membershipValue;
	1668	if (m_Consequent == data.instance(i).classValue()){
	1669	acc += membershipValue;
	1670	}
	1671	}
	1672
	1673	// m-estimate
	1674	double m = 2.0;
	1675	((Antd)this.m_Antds.elementAt((int)tempRule.size()-1)).m_confidence =
	1676	(acc+m*(aprioriDistribution[(int)m_Consequent]/
	1677	Utils.sum(aprioriDistribution))) / (cov+m);
	1678	tempRule.m_Antds.removeElementAt(tempRule.m_Antds.size()-1);
	1679	}
	1680	}
	1681
	1682
	1683	/**
	1684	* Get the rule confidence.
	1685	* @return rule confidence / weight
	1686	*/
	1687	public double getConfidence(){
	1688	if (!hasAntds())
	1689	return Double.NaN;
	1690	return ((Antd)m_Antds.lastElement()).m_confidence;
	1691	}
	1692
	1693	/**
	1694	*
	1695	*/
	1696	public String getRevision() {
	1697	return "1.0";
	1698	}
	1699
	1700	}
	1701
	1702	/**
	1703	* Returns default capabilities of the classifier.
	1704	*
	1705	* @return the capabilities of this classifier
	1706	*/
	1707	public Capabilities getCapabilities() {
	1708	Capabilities result = super.getCapabilities();
	1709	result.disableAll();
	1710
	1711	// attributes
	1712	result.enable(Capability.NOMINAL_ATTRIBUTES);
	1713	result.enable(Capability.NUMERIC_ATTRIBUTES);
	1714	result.enable(Capability.DATE_ATTRIBUTES);
	1715	result.enable(Capability.MISSING_VALUES);
	1716
	1717	// class
	1718	result.enable(Capability.NOMINAL_CLASS);
	1719	result.enable(Capability.MISSING_CLASS_VALUES);
	1720
	1721	// instances
	1722	result.setMinimumNumberInstances(m_Folds);
	1723
	1724	return result;
	1725	}
	1726
	1727	/**
	1728	* Builds the FURIA rule-based model
	1729	*
	1730	* @param instances the training data
	1731	* @throws Exception if classifier can't be built successfully
	1732	*/
	1733	public void buildClassifier(Instances instances) throws Exception {
	1734	// can classifier handle the data?
	1735	getCapabilities().testWithFail(instances);
	1736
	1737	// remove instances with missing class
	1738	instances = new Instances(instances);
	1739	instances.deleteWithMissingClass();
	1740
	1741	// Learn the apriori distribution for later
	1742	aprioriDistribution = new double[instances.classAttribute().numValues()];
	1743	boolean allWeightsAreOne = true;
	1744	for (int i = 0 ; i < instances.numInstances(); i++){
	1745	aprioriDistribution[(int)instances.instance(i).classValue()]+=instances.instance(i).weight();
	1746	if (allWeightsAreOne && instances.instance(i).weight() != 1.0){
	1747	allWeightsAreOne = false;
	1748	break;
	1749	}
	1750	}
	1751
	1752
	1753	m_Random = instances.getRandomNumberGenerator(m_Seed);
	1754	m_Total = RuleStats.numAllConditions(instances);
	1755	if(m_Debug)
	1756	System.err.println("Number of all possible conditions = "+m_Total);
	1757
	1758	Instances data = new Instances(instances);
	1759
	1760	m_Class = data.classAttribute();
	1761	m_Ruleset = new FastVector();
	1762	m_RulesetStats = new FastVector();
	1763	m_Distributions = new FastVector();
	1764
	1765
	1766	// Learn a rule set for each single class
	1767	oneClass:
	1768	for(int y=0; y < data.numClasses(); y++){ // For each class
	1769
	1770	double classIndex = (double)y;
	1771	if(m_Debug){
	1772	int ci = (int)classIndex;
	1773	System.err.println("\n\nClass "+m_Class.value(ci)+"("+ci+"): "
	1774	+ aprioriDistribution[y] + "instances\n"+
	1775	"=====================================\n");
	1776	}
	1777
	1778	if(Utils.eq(aprioriDistribution[y],0.0)) // No data for this class
	1779	continue oneClass;
	1780
	1781	// The expected FP/err is the proportion of the class
	1782	double expFPRate = (aprioriDistribution[y] / Utils.sum(aprioriDistribution));
	1783
	1784
	1785	double classYWeights = 0, totalWeights = 0;
	1786	for(int j=0; j < data.numInstances(); j++){
	1787	Instance datum = data.instance(j);
	1788	totalWeights += datum.weight();
	1789	if((int)datum.classValue() == y){
	1790	classYWeights += datum.weight();
	1791	}
	1792	}
	1793
	1794	// DL of default rule, no theory DL, only data DL
	1795	double defDL;
	1796	if(classYWeights > 0)
	1797	defDL = RuleStats.dataDL(expFPRate,
	1798	0.0,
	1799	totalWeights,
	1800	0.0,
	1801	classYWeights);
	1802	else
	1803	continue oneClass; // Subsumed by previous rules
	1804
	1805
	1806
	1807	if(Double.isNaN(defDL) \|\| Double.isInfinite(defDL))
	1808	throw new Exception("Should never happen: "+
	1809	"defDL NaN or infinite!");
	1810	if(m_Debug)
	1811	System.err.println("The default DL = "+defDL);
	1812
	1813	rulesetForOneClass(expFPRate, data, classIndex, defDL);
	1814	}
	1815
	1816	// Remove redundant antecedents
	1817	for(int z=0; z < m_Ruleset.size(); z++){
	1818	RipperRule rule = (RipperRule)m_Ruleset.elementAt(z);
	1819	for(int j = 0; j < rule.m_Antds.size(); j++){
	1820	Antd outerAntd = (Antd)rule.m_Antds.elementAt(j);
	1821	for (int k = j+1; k < rule.m_Antds.size(); k++){
	1822	Antd innerAntd = (Antd)rule.m_Antds.elementAt(k);
	1823	if (outerAntd.att.index() == innerAntd.att.index() && outerAntd.value==innerAntd.value){
	1824	rule.m_Antds.setElementAt(rule.m_Antds.elementAt(k), j);
	1825	rule.m_Antds.removeElementAt(k--);
	1826	}
	1827	}
	1828	}
	1829	}
	1830
	1831
	1832	// Fuzzify all rules
	1833	for(int z=0; z < m_RulesetStats.size(); z++){
	1834	RuleStats oneClass = (RuleStats)m_RulesetStats.elementAt(z);
	1835	for(int xyz=0; xyz < oneClass.getRulesetSize(); xyz++){
	1836	RipperRule rule = (RipperRule)((FastVector)oneClass.getRuleset()).elementAt(xyz);
	1837
	1838	// do the fuzzification for all known antecedents
	1839	rule.fuzzify(data, allWeightsAreOne);
	1840
	1841	double[] classDist = oneClass.getDistributions(xyz);
	1842	// Check for sum=0, because otherwise it does not work
	1843	if (Utils.sum(classDist)>0) Utils.normalize(classDist);
	1844	if(classDist != null)
	1845	m_Distributions.addElement(classDist);
	1846	}
	1847	}
	1848
	1849
	1850	// if there was some problem during fuzzification, set the support bound
	1851	// to the trivial fuzzification position
	1852	for(int z=0; z < m_Ruleset.size(); z++){
	1853	RipperRule rule = (RipperRule)m_Ruleset.elementAt(z);
	1854	for(int j = 0; j < rule.m_Antds.size(); j++){
	1855	Antd antd = (Antd)rule.m_Antds.elementAt(j);
	1856	if (antd instanceof NumericAntd) {
	1857	NumericAntd numAntd = (NumericAntd) antd;
	1858
	1859
	1860	if (!numAntd.fuzzyYet){
	1861	for (int i = 0; i < data.numInstances(); i++){
	1862	if ((numAntd.value == 1 &&
	1863	numAntd.splitPoint > data.instance(i).value(numAntd.att.index()) &&
	1864	(numAntd.supportBound < data.instance(i).value(numAntd.att.index()) \|\|
	1865	!numAntd.fuzzyYet)
	1866	)
	1867	\|\|
	1868	(numAntd.value == 0 &&
	1869	numAntd.splitPoint < data.instance(i).value(numAntd.att.index()) &&
	1870	(numAntd.supportBound > data.instance(i).value(numAntd.att.index()) \|\|
	1871	!numAntd.fuzzyYet)
	1872	)
	1873	){
	1874	numAntd.supportBound = data.instance(i).value(numAntd.att.index());
	1875	numAntd.fuzzyYet = true;
	1876	}
	1877	}
	1878
	1879	}
	1880	}
	1881	}
	1882	}
	1883
	1884	//Determine confidences
	1885	for(int z=0; z < m_Ruleset.size(); z++){
	1886	RipperRule rule = (RipperRule)m_Ruleset.elementAt(z);
	1887	rule.calculateConfidences(data);
	1888	}
	1889	}
	1890
	1891	/**
	1892	* Classify the test instance with the rule learner and provide
	1893	* the class distributions
	1894	*
	1895	* @param datum the instance to be classified
	1896	* @return the distribution
	1897	* @throws Exception
	1898	*/
	1899
	1900	public double[] distributionForInstance(Instance datum) throws Exception{
	1901	//test for multiple overlap of rules
	1902	double[] rulesCoveringForEachClass = new double[datum.numClasses()];
	1903	for(int i=0; i < m_Ruleset.size(); i++){
	1904	RipperRule rule = (RipperRule)m_Ruleset.elementAt(i);
	1905
	1906	/* In case that one class does not contain any instances (e.g. in UCI-dataset glass),
	1907	* a default rule assigns all instances to the other class. Such a rule may be ignored here.
	1908	*/
	1909	if (!rule.hasAntds())
	1910	continue;
	1911
	1912
	1913	// Calculate the maximum degree of coverage
	1914	if(rule.covers(datum)){
	1915	rulesCoveringForEachClass[(int)rule.m_Consequent] += rule.coverageDegree(datum) * rule.getConfidence();
	1916	}
	1917
	1918	}
	1919
	1920
	1921	// If no rule covered the example, then maybe start the rule stretching
	1922	if (Utils.sum(rulesCoveringForEachClass)==0){
	1923
	1924	// If rule stretching is not allowed,
	1925	// return either the apriori prediction
	1926	if (m_uncovAction == UNCOVACTION_APRIORI){
	1927	rulesCoveringForEachClass = aprioriDistribution;
	1928	if (Utils.sum(rulesCoveringForEachClass)>0)
	1929	Utils.normalize(rulesCoveringForEachClass);
	1930	return rulesCoveringForEachClass;
	1931	}
	1932	// or abstain from that decision at all.
	1933	if (m_uncovAction == UNCOVACTION_REJECT)
	1934	return rulesCoveringForEachClass;
	1935
	1936	// Copy the ruleset as backup
	1937	FastVector origRuleset = (FastVector) m_Ruleset.copyElements();
	1938
	1939	// Find for every rule the first antecedent that does not
	1940	// cover the given instance.
	1941	rulesCoveringForEachClass = new double[rulesCoveringForEachClass.length];
	1942	for(int i=0; i < m_Ruleset.size(); i++){
	1943	RipperRule rule = (RipperRule)m_Ruleset.elementAt(i);
	1944	double numAntdsBefore = rule.m_Antds.size();
	1945
	1946	int firstAntdToDelete = Integer.MAX_VALUE;
	1947	for (int j = 0; j < rule.m_Antds.size(); j++){
	1948	if (((Antd)rule.m_Antds.elementAt(j)).covers(datum)==0){
	1949	firstAntdToDelete = j;
	1950	break;
	1951	}
	1952	}
	1953
	1954	// Prune antecedent such that it covers the instance
	1955	for (int j = firstAntdToDelete; j < rule.m_Antds.size(); j++){
	1956	rule.m_Antds.removeElementAt(j--);
	1957	}
	1958	double numAntdsAfter = rule.m_Antds.size();
	1959
	1960	// Empty rules shall not vote here
	1961	if (!rule.hasAntds())
	1962	continue;
	1963
	1964	// Calculate the maximum degree of coverage and weight the rule
	1965	// by its confidence and the fraction of antecedents left after
	1966	// rule stretching
	1967	double secondWeight = (numAntdsAfter+1)/(numAntdsBefore+2) ;
	1968	if (rule.getConfidence() secondWeightrule.coverageDegree(datum) >= rulesCoveringForEachClass[(int)rule.getConsequent()]){
	1969	rulesCoveringForEachClass[(int)rule.getConsequent()] = rule.getConfidence()secondWeightrule.coverageDegree(datum);
	1970	}
	1971	}
	1972
	1973	// Reestablish original ruleset
	1974	m_Ruleset = origRuleset;
	1975	}
	1976
	1977	//check for conflicts
	1978	double[] maxClasses = new double[rulesCoveringForEachClass.length];
	1979	for (int i = 0; i < rulesCoveringForEachClass.length; i++){
	1980	if (rulesCoveringForEachClass[Utils.maxIndex(rulesCoveringForEachClass)] ==
	1981	rulesCoveringForEachClass[i] && rulesCoveringForEachClass[i]>0)
	1982	maxClasses[i] = 1;
	1983	}
	1984
	1985	//If there is a conflict, resolve it using the apriori distribution
	1986	if (Utils.sum(maxClasses)>0){
	1987	for (int i = 0; i < maxClasses.length; i++){
	1988	if (maxClasses[i] > 0 && aprioriDistribution[i] != rulesCoveringForEachClass[Utils.maxIndex(rulesCoveringForEachClass)])
	1989	rulesCoveringForEachClass[i] -= 0.00001;
	1990	}
	1991	}
	1992
	1993	// If no stretched rule was able to cover the instance,
	1994	// then fall back to the apriori distribution
	1995	if (Utils.sum(rulesCoveringForEachClass)==0){
	1996	rulesCoveringForEachClass = aprioriDistribution;
	1997	}
	1998
	1999
	2000	if (Utils.sum(rulesCoveringForEachClass)>0)
	2001	Utils.normalize(rulesCoveringForEachClass);
	2002
	2003	return rulesCoveringForEachClass;
	2004
	2005	}
	2006
	2007
	2008	/** Build a ruleset for the given class according to the given data
	2009	*
	2010	* @param expFPRate the expected FP/(FP+FN) used in DL calculation
	2011	* @param data the given data
	2012	* @param classIndex the given class index
	2013	* @param defDL the default DL in the data
	2014	* @throws Exception if the ruleset can be built properly
	2015	*/
	2016	protected Instances rulesetForOneClass(double expFPRate,
	2017	Instances data,
	2018	double classIndex,
	2019	double defDL)
	2020	throws Exception {
	2021
	2022	Instances newData = data, growData, pruneData;
	2023	boolean stop = false;
	2024	FastVector ruleset = new FastVector();
	2025
	2026	double dl = defDL, minDL = defDL;
	2027	RuleStats rstats = null;
	2028	double[] rst;
	2029
	2030	// Check whether data have positive examples
	2031	boolean defHasPositive = true; // No longer used
	2032	boolean hasPositive = defHasPositive;
	2033
	2034	/******************** Building stage *********************/
	2035	if(m_Debug)
	2036	System.err.println("\n* Building stage *");
	2037
	2038
	2039	while((!stop) && hasPositive){ // Generate new rules until
	2040	// stopping criteria met
	2041	RipperRule oneRule;
	2042
	2043	oneRule = new RipperRule();
	2044	oneRule.setConsequent(classIndex); // Must set first
	2045	if(m_Debug)
	2046	System.err.println("\nNo pruning: growing a rule ...");
	2047	oneRule.grow(newData); // Build the rule
	2048	if(m_Debug)
	2049	System.err.println("No pruning: one rule found:\n"+
	2050	oneRule.toString(m_Class));
	2051
	2052
	2053	// Compute the DL of this ruleset
	2054	if(rstats == null){ // First rule
	2055	rstats = new RuleStats();
	2056	rstats.setNumAllConds(m_Total);
	2057	rstats.setData(newData);
	2058	}
	2059
	2060	rstats.addAndUpdate(oneRule);
	2061	int last = rstats.getRuleset().size()-1; // Index of last rule
	2062	dl += rstats.relativeDL(last, expFPRate, m_CheckErr);
	2063
	2064	if(Double.isNaN(dl) \|\| Double.isInfinite(dl))
	2065	throw new Exception("Should never happen: dl in "+
	2066	"building stage NaN or infinite!");
	2067	if(m_Debug)
	2068	System.err.println("Before optimization("+last+
	2069	"): the dl = "+dl+" \| best: "+minDL);
	2070
	2071	if(dl < minDL)
	2072	minDL = dl; // The best dl so far
	2073
	2074	rst = rstats.getSimpleStats(last);
	2075	if(m_Debug)
	2076	System.err.println("The rule covers: "+rst[0]+
	2077	" \| pos = " + rst[2] +
	2078	" \| neg = " + rst[4]+
	2079	"\nThe rule doesn't cover: "+rst[1]+
	2080	" \| pos = " + rst[5]);
	2081
	2082	stop = checkStop(rst, minDL, dl);
	2083
	2084	if(!stop){
	2085	ruleset.addElement(oneRule); // Accepted
	2086	newData = rstats.getFiltered(last)[1];// Data not covered
	2087	hasPositive = Utils.gr(rst[5], 0.0); // Positives remaining?
	2088	if(m_Debug)
	2089	System.err.println("One rule added: has positive? "
	2090	+hasPositive);
	2091	}
	2092	else{
	2093	if(m_Debug)
	2094	System.err.println("Quit rule");
	2095	rstats.removeLast(); // Remove last to be re-used
	2096	}
	2097	}// while !stop
	2098
	2099
	2100	/****************** Optimization stage *****************/
	2101
	2102	RuleStats finalRulesetStat = null;
	2103	for(int z=0; z < m_Optimizations; z++){
	2104	if(m_Debug)
	2105	System.err.println("\n*** Optimization: run #"
	2106	+z+" ***");
	2107
	2108	newData = data;
	2109	finalRulesetStat = new RuleStats();
	2110	finalRulesetStat.setData(newData);
	2111	finalRulesetStat.setNumAllConds(m_Total);
	2112	int position=0;
	2113	stop = false;
	2114	boolean isResidual = false;
	2115	hasPositive = defHasPositive;
	2116	dl = minDL = defDL;
	2117
	2118	oneRule:
	2119	while(!stop && hasPositive){
	2120
	2121	isResidual = (position>=ruleset.size()); // Cover residual positive examples
	2122	// Re-do shuffling and stratification
	2123	//newData.randomize(m_Random);
	2124	newData = RuleStats.stratify(newData, m_Folds, m_Random);
	2125	Instances[] part = RuleStats.partition(newData, m_Folds);
	2126	growData=part[0];
	2127	pruneData=part[1];
	2128	//growData=newData.trainCV(m_Folds, m_Folds-1);
	2129	//pruneData=newData.testCV(m_Folds, m_Folds-1);
	2130	RipperRule finalRule;
	2131
	2132	if(m_Debug)
	2133	System.err.println("\nRule #"+position +
	2134	"\| isResidual?" + isResidual+
	2135	"\| data size: "+newData.sumOfWeights());
	2136
	2137	if(isResidual){
	2138	RipperRule newRule = new RipperRule();
	2139	newRule.setConsequent(classIndex);
	2140	if(m_Debug)
	2141	System.err.println("\nGrowing and pruning"+
	2142	" a new rule ...");
	2143	newRule.grow(newData);
	2144	finalRule = newRule;
	2145	if(m_Debug)
	2146	System.err.println("\nNew rule found: "+
	2147	newRule.toString(m_Class));
	2148	}
	2149	else{
	2150	RipperRule oldRule = (RipperRule)ruleset.elementAt(position);
	2151	boolean covers = false;
	2152	// Test coverage of the next old rule
	2153	for(int i=0; i<newData.numInstances(); i++)
	2154	if(oldRule.covers(newData.instance(i))){
	2155	covers = true;
	2156	break;
	2157	}
	2158
	2159	if(!covers){// Null coverage, no variants can be generated
	2160	finalRulesetStat.addAndUpdate(oldRule);
	2161	position++;
	2162	continue oneRule;
	2163	}
	2164
	2165	// 2 variants
	2166	if(m_Debug)
	2167	System.err.println("\nGrowing and pruning"+
	2168	" Replace ...");
	2169	RipperRule replace = new RipperRule();
	2170	replace.setConsequent(classIndex);
	2171	replace.grow(growData);
	2172
	2173	// Remove the pruning data covered by the following
	2174	// rules, then simply compute the error rate of the
	2175	// current rule to prune it. According to Ripper,
	2176	// it's equivalent to computing the error of the
	2177	// whole ruleset -- is it true?
	2178	pruneData = RuleStats.rmCoveredBySuccessives(pruneData,ruleset, position);
	2179	replace.prune(pruneData, true);
	2180
	2181	if(m_Debug)
	2182	System.err.println("\nGrowing and pruning"+
	2183	" Revision ...");
	2184	RipperRule revision = (RipperRule)oldRule.copy();
	2185
	2186	// For revision, first rm the data covered by the old rule
	2187	Instances newGrowData = new Instances(growData, 0);
	2188	for(int b=0; b<growData.numInstances(); b++){
	2189	Instance inst = growData.instance(b);
	2190	if(revision.covers(inst))
	2191	newGrowData.add(inst);
	2192	}
	2193	revision.grow(newGrowData);
	2194	revision.prune(pruneData, true);
	2195
	2196	double[][] prevRuleStats = new double[position][6];
	2197	for(int c=0; c < position; c++)
	2198	prevRuleStats[c] = finalRulesetStat.getSimpleStats(c);
	2199
	2200	// Now compare the relative DL of variants
	2201	FastVector tempRules = (FastVector)ruleset.copyElements();
	2202	tempRules.setElementAt(replace, position);
	2203
	2204	RuleStats repStat = new RuleStats(data, tempRules);
	2205	repStat.setNumAllConds(m_Total);
	2206	repStat.countData(position, newData, prevRuleStats);
	2207	//repStat.countData();
	2208	rst = repStat.getSimpleStats(position);
	2209	if(m_Debug)
	2210	System.err.println("Replace rule covers: "+rst[0]+
	2211	" \| pos = " + rst[2] +
	2212	" \| neg = " + rst[4]+
	2213	"\nThe rule doesn't cover: "+rst[1]+
	2214	" \| pos = " + rst[5]);
	2215
	2216	double repDL = repStat.relativeDL(position, expFPRate,
	2217	m_CheckErr);
	2218
	2219	if(m_Debug)
	2220	System.err.println("\nReplace: "+
	2221	replace.toString(m_Class)
	2222	+" \|dl = "+repDL);
	2223
	2224	if(Double.isNaN(repDL) \|\| Double.isInfinite(repDL))
	2225	throw new Exception("Should never happen: repDL"+
	2226	"in optmz. stage NaN or "+
	2227	"infinite!");
	2228
	2229	tempRules.setElementAt(revision, position);
	2230	RuleStats revStat = new RuleStats(data, tempRules);
	2231	revStat.setNumAllConds(m_Total);
	2232	revStat.countData(position, newData, prevRuleStats);
	2233	//revStat.countData();
	2234	double revDL = revStat.relativeDL(position, expFPRate,
	2235	m_CheckErr);
	2236
	2237	if(m_Debug)
	2238	System.err.println("Revision: "
	2239	+ revision.toString(m_Class)
	2240	+" \|dl = "+revDL);
	2241
	2242	if(Double.isNaN(revDL) \|\| Double.isInfinite(revDL))
	2243	throw new Exception("Should never happen: revDL"+
	2244	"in optmz. stage NaN or "+
	2245	"infinite!");
	2246
	2247	rstats = new RuleStats(data, ruleset);
	2248	rstats.setNumAllConds(m_Total);
	2249	rstats.countData(position, newData, prevRuleStats);
	2250	//rstats.countData();
	2251	double oldDL = rstats.relativeDL(position, expFPRate,
	2252	m_CheckErr);
	2253
	2254	if(Double.isNaN(oldDL) \|\| Double.isInfinite(oldDL))
	2255	throw new Exception("Should never happen: oldDL"+
	2256	"in optmz. stage NaN or "+
	2257	"infinite!");
	2258	if(m_Debug)
	2259	System.err.println("Old rule: "+
	2260	oldRule.toString(m_Class)
	2261	+" \|dl = "+oldDL);
	2262
	2263	if(m_Debug)
	2264	System.err.println("\nrepDL: "+repDL+
	2265	"\nrevDL: "+revDL+
	2266	"\noldDL: "+oldDL);
	2267
	2268	if((oldDL <= revDL) && (oldDL <= repDL))
	2269	finalRule = oldRule; // Old the best
	2270	else if(revDL <= repDL)
	2271	finalRule = revision; // Revision the best
	2272	else
	2273	finalRule = replace; // Replace the best
	2274	}
	2275
	2276	finalRulesetStat.addAndUpdate(finalRule);
	2277	rst = finalRulesetStat.getSimpleStats(position);
	2278
	2279	if(isResidual){
	2280	dl += finalRulesetStat.relativeDL(position,
	2281	expFPRate,
	2282	m_CheckErr);
	2283
	2284	if(m_Debug)
	2285	System.err.println("After optimization: the dl"
	2286	+"="+dl+" \| best: "+minDL);
	2287
	2288	if(dl < minDL)
	2289	minDL = dl; // The best dl so far
	2290
	2291	stop = checkStop(rst, minDL, dl);
	2292	if(!stop)
	2293	ruleset.addElement(finalRule); // Accepted
	2294	else{
	2295	finalRulesetStat.removeLast(); // Remove last to be re-used
	2296	position--;
	2297	}
	2298	}
	2299	else
	2300	ruleset.setElementAt(finalRule, position); // Accepted
	2301
	2302	if(m_Debug){
	2303	System.err.println("The rule covers: "+rst[0]+
	2304	" \| pos = " + rst[2] +
	2305	" \| neg = " + rst[4]+
	2306	"\nThe rule doesn't cover: "+rst[1]+
	2307	" \| pos = " + rst[5]);
	2308	System.err.println("\nRuleset so far: ");
	2309	for(int x=0; x<ruleset.size(); x++)
	2310	System.err.println(x+": "+((RipperRule)ruleset.elementAt(x)).toString(m_Class));
	2311	System.err.println();
	2312	}
	2313
	2314	//Data not covered
	2315	if(finalRulesetStat.getRulesetSize() > 0)// If any rules
	2316	newData = finalRulesetStat.getFiltered(position)[1];
	2317	hasPositive = Utils.gr(rst[5], 0.0); //Positives remaining?
	2318	position++;
	2319	} // while !stop && hasPositive
	2320
	2321	if(ruleset.size() > (position+1)){ // Hasn't gone through yet
	2322	for(int k=position+1; k<ruleset.size(); k++)
	2323	finalRulesetStat.addAndUpdate((Rule)ruleset.elementAt(k));
	2324	}
	2325	if(m_Debug)
	2326	System.err.println("\nDeleting rules to decrease"+
	2327	" DL of the whole ruleset ...");
	2328	finalRulesetStat.reduceDL(expFPRate, m_CheckErr);
	2329
	2330	if(m_Debug){
	2331	int del = ruleset.size() -
	2332	finalRulesetStat.getRulesetSize();
	2333	System.err.println(del+" rules are deleted"+
	2334	" after DL reduction procedure");
	2335	}
	2336	ruleset = finalRulesetStat.getRuleset();
	2337	rstats = finalRulesetStat;
	2338
	2339	} // For each run of optimization
	2340
	2341	// Concatenate the ruleset for this class to the whole ruleset
	2342	if(m_Debug){
	2343	System.err.println("\nFinal ruleset: ");
	2344	for(int x=0; x<ruleset.size(); x++)
	2345	System.err.println(x+": "+((RipperRule)ruleset.elementAt(x)).toString(m_Class));
	2346	System.err.println();
	2347	}
	2348
	2349
	2350	m_Ruleset.appendElements(ruleset);
	2351	m_RulesetStats.addElement(rstats);
	2352
	2353	return null;
	2354	}
	2355
	2356	/**
	2357	* Check whether the stopping criterion meets
	2358	*
	2359	* @param rst the statistic of the ruleset
	2360	* @param minDL the min description length so far
	2361	* @param dl the current description length of the ruleset
	2362	* @return true if stop criterion meets, false otherwise
	2363	*/
	2364	private boolean checkStop(double[] rst, double minDL, double dl){
	2365
	2366
	2367	if(dl > minDL+MAX_DL_SURPLUS){
	2368	if(m_Debug)
	2369	System.err.println("DL too large: "+dl+" \| "+minDL);
	2370	return true;
	2371	}
	2372	else
	2373	if(!Utils.gr(rst[2], 0.0)){// Covered positives
	2374	if(m_Debug)
	2375	System.err.println("Too few positives.");
	2376	return true;
	2377	}
	2378	else if((rst[4]/rst[0]) >= 0.5){// Err rate
	2379	if(m_CheckErr){
	2380	if(m_Debug)
	2381	System.err.println("Error too large: "+
	2382	rst[4] + "/" + rst[0]);
	2383	return true;
	2384	}
	2385	else
	2386	return false;
	2387	}
	2388	else{// Not stops
	2389	if(m_Debug)
	2390	System.err.println("Continue.");
	2391	return false;
	2392	}
	2393	}
	2394
	2395	/**
	2396	* Prints the all the rules of the rule learner.
	2397	*
	2398	* @return a textual description of the classifier
	2399	*/
	2400	public String toString() {
	2401	if (m_Ruleset == null)
	2402	return "FURIA: No model built yet.";
	2403
	2404	StringBuffer sb = new StringBuffer("FURIA rules:\n"+
	2405	"===========\n\n");
	2406	for(int j=0; j<m_RulesetStats.size(); j++){
	2407	RuleStats rs = (RuleStats)m_RulesetStats.elementAt(j);
	2408	FastVector rules = rs.getRuleset();
	2409	for(int k=0; k<rules.size(); k++){
	2410	sb.append(((RipperRule)rules.elementAt(k)).toString(m_Class)
	2411	+ " (CF = " + Math.round(100.0*((RipperRule)rules.elementAt(k)).getConfidence())/100.0 +")\n");
	2412	}
	2413	}
	2414	if(m_Debug){
	2415	System.err.println("Inside m_Ruleset");
	2416	for(int i=0; i<m_Ruleset.size(); i++)
	2417	System.err.println(((RipperRule)m_Ruleset.elementAt(i)).toString(m_Class));
	2418	}
	2419	sb.append("\nNumber of Rules : "
	2420	+ m_Ruleset.size() + "\n");
	2421
	2422
	2423
	2424
	2425	return sb.toString();
	2426	}
	2427
	2428	/**
	2429	* Main method.
	2430	*
	2431	* @param args the options for the classifier
	2432	* @throws Exception
	2433	*/
	2434	public static void main(String[] args) throws Exception {
	2435	runClassifier(new FURIA(), args);
	2436	}
	2437
	2438	/**
	2439	*
	2440	*/
	2441	public String getRevision() {
	2442	return "$Revision: 5964 $";
	2443	}
	2444	}

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

Context Navigation

source: branches/MetisMQI/src/main/java/weka/classifiers/rules/FURIA.java

Download in other formats: