ripper.1

Ripper 分类算法

An attribute
is "suppressed" by inserting the keyword
.I suppressed
after the colon in the atrribute's definition.
.PP
The 
.I data file 
contains a set of classified examples.  Each example is a
comma-separated list of attribute values, followed by an atom
indicating the class of the example, followed by a period.  (It is
usually convenient to have one example per line, but this is not
required.) Attribute values are given in 
the same order that attributes are defined in the names file; most of 
the usual syntaxes for numbers are supported.  Set- and bag-valued 
attributes
are specified by simply enumerating the elements of the set,
separated with whitespace.
Unknown attributes 
are indicated with a question mark token.
.PP
Examples can also be given a weight, by inserting 
.I :w
between the class name and the terminating period
(where 
.I w
is a real number, the default value for which is one).
.PP 
The 
.I test file
is formatted in the same way as the data file.
.PP
Finally, the
.I grammar file
contains a description of a context-free grammar, roughly in BNF
notation.  
The grammar file is optional for ripper,
and most users will be probably not want to change the 
default grammar; however we will describe it here for completeness.
The terminal symbols of the grammar are tests on the values
of attributes defined in the names file; each sentence generated by
the grammar is thus a sequence of attribute-value tests.  Ripper
will read in this grammar and constrain its learning component so that
every rule generated by ripper will have as an antecedent a sequence
of attribute-value tests that is a sentence of the grammar.  The
grammar thus is a way for the user to guide ripper's choice of rules.
.PP
More specifically, the grammar file contains a series of
.I grammar rules.
Each grammar rule consists of an atomic 
.I left-hand side
followed by the token
"-->"
followed by a comma-separated list of 
.I grammar symbols
followed by a period.
A 
.I grammar symbol
is either a nonterminal symbol (which is simply an atom
that appears on the left-hand side of some grammar rule)
or a 
.I terminal symbol.
A terminal symbol is of the form
.I attribute op value
where 
.I attribute
is the name of an attribute (e.g. "height") and value is a valid
value for that attribute.  An operator 
.I op
must be one of the
tokens "=", "!=", ">=", "<=", "~" or "!~".
Terminal symbols of the form
.I attribute op *
are also allowed, in which case any possible value is allowed.
.PP 
The condition 
.I attribute ~ symbol
is used for set- and bag-valued
attributes.
The condition
.I attribute ~ symbol
is true of an example if 
.I attribute 
is set-valued and 
.I symbol 
is contained in the set.
The condition 
.I attribute !~ symbol
is true if
.I symbol
is not present in the set.
For bags, the condition
.I attribute ~ symbol__k
is true if 
.I attribute
contains at least 
.I
k
instances of 
.I symbol.
The condition 
.I attribute !~ symbol__k
is treated analogously.
.PP
Often one will have several grammar rules with the same left-hand
side, but different right-hand sides.  In this case one may use the
syntax
.in +6
.br
LHS --> RHS1 | RHS2 | ... | RHSk
.in -6
rather than the wordier
.in +6
.br
LHS --> RHS1
.br
 ...
.br
LHS --> RHSk
.in -6
Finally, prefixing a grammar rule with an exclamation point indicates
to ripper that sentences generated using that grammar rule have a lower
priority; if possible, ripper will build a hypothesis without using
low-priority sentences.  Even lower priorities can be assigned by
prefixing grammar rules with a string of two or more exclamation
points.
.SH THE DEFAULT GRAMMAR
.PP
When learning rules to predict the class "class", ripper will expect
to find some left-hand side of the form "body_class" to use as the
start symbol of the grammar; if this is not present, ripper will use
the atom "body" as the start symbol.  If this is not present, ripper
will construct the following default grammar:
.PP
.in +6
body --> body_conds.
.br
body_conds --> .
.br
body_conds --> cond,body_conds.
.br
cond --> attr1_cond.
.br
 ...
.br
cond --> attrk_cond.
.br
.in -6
.PP
where 
.I attr1, ..., attrk
are the names of the attributes defined in the names file.  
If discretization is used, then 
for each
continuous attribute
.I cattr,
the default grammar also contains the rules 
.PP
.in +6
 cattr_cond --> cattr>=t1.
.br
 cattr_cond --> cattr<=t1.
.br 
 ...
.br
 cattr_cond --> cattr>=tn.
.br
 cattr_cond --> cattr<=tn.
.br 
.in -6
.PP
where 
.I t1, ..., tn
are ripper's discretization of the training data.
Otherwise, the grammar will contain the rules
.PP
.in +6
 cattr_cond --> cattr>= '*'.
.br
 cattr_cond --> cattr<= '*'.
.br 
.in -6
.PP
For a nominal attribute 
.I nattr
the default grammar contains the rule 
.PP
.in +6
 nattr_cond --> nattr = '*'.
.in -6
.PP
For a set- or bag-valued attribute 
.I sattr
the default grammar contains the rules
.PP
.in +6
 sattr_cond --> sattr ~ '*'.
.br
 sattr_cond --> sattr !~ '*'.
.br
.in -6
.PP
If the grammar file is missing or empty, then the default grammar will
be used.  If the grammar contains definitions of some but not all of
the nonterminal symbols used in the default grammar, they will
override the default definitions. 
.SH FILES
.PP
.in +6
ripper
.br
filestem.data (data file)
.br
filestem.names (names file)
.br
filestem.gram (grammar file)
.br
filestem.test (unseen data)
.br
filestem.hyp (learned rules)
.in -6
.PP
Some sample input files are also available from wcohen@research.
.SH SEE ALSO
.PP
The man page for
.I ripperaux
contains brief descriptions of some additional useful programs for
working with ripper rulesets and/or datasets.
.PP
Ripper's input files are more-or-less compatible with Quinlan's 
.I C4.5 
tree-learning system.
.PP
The papers "Fast efficient rule learning" (Cohen, ML95) and
"Learning trees and rules with set-valued features" (Cohen, AAAI96)
describe the algorithms used in Ripper in more detail.
.SH USING RIPPER TO CLASSIFY TEXT
.PP
I am frequently asked about tools to preprocess text so that it can be
easily digested by Ripper.  I don't have any tools to distribute,
largely because I think it would be hard to have any tool that is
sufficiently general to handle all the necessary cases,
but still substantially simpler than a general-purpose text processing
language like Perl.
.PP
My current recommendation in feeding Ripper is to use something like
Perl (or whatever suits you) to convert punctuation to white space,
and coerce everything to lower case, and then feed the result into
Ripper as a single set (or perhaps bag).  If you use sets, it is not
necessary to remove duplicate tokens.  Be careful to remove the
punctuation symbols percent sign (%), comma (,), colon (:), 
single quote ('), and period
(.), all of which have special meaning to Ripper.
If you want a non-default tokenization, then you must surround each
token with single quotes. Stemming
doesn't seem to make a big difference on the benchmarks I've tried.
Coercion to lower case also means that you can safely use any
upper-case or mixed-case symbol as an attribute or class name. 
.SH BUGS
.PP 
Attribute names, attribute values, grammar symbols, and class names
are all put in the same name space, so you can't use the same symbol
for, say, a class name and a possible set value.  This is awkward
when you're using set- or bag-valued attributes to handle text.  
.PP 
Ripper doesn't actually check the range
of symbolic attributes for consistency with
declaration in the names file.
.PP
The response of ripper to the -S and -L options is sometimes
rather abrupt---i.e. small changes can sometimes 
have drastic consequences.