arules.tex

本程序是基于linux系统下c++代码

in these data structures, they are used as item labels or transaction
IDs, accordingly.  To import data from a file, the
\func{read.transactions} function is provided.  This function reads
files structured as shown in Figure~\ref{fig:transactionMatrix} and also
the very common format with one line per transaction and the items
separated by a predefined character.  Finally, \func{inspect} can be
used to inspect transactions (e.g., ``interesting'' transactions
obtained with subset selection).

Another important application of mining association rules has been
proposed by \cite{arules:Piatetsky-Shapiro:1991} and
\cite{arules:Srikant+Agrawal:1996} for discovering interesting
relationships between the values of categorical and quantitative
(metric) attributes.  For mining associations rules, non-binary
attributes have to be mapped to binary attributes. The straightforward
mapping method is to transform the metric attributes into $k$ ordinal
attributes by building categories (e.g., an attribute income might be
transformed into a ordinal attribute with the three categories: ``low'',
``medium'' and ``high'').  Then, in a second step, each categorical
attribute with $k$ categories is represented by $k$ binary dummy
attributes which correspond to the items used for mining.  An example
application using questionnaire data can be found in
\cite{arules:Hastie+Tibshirani+Friedman:2001} in the chapter
about association rule mining.

The typical representation for data with categorical and quantitative
attributes in \proglang{R} is a \class{data.frame}.  First, a domain
expert has to create useful categories for all metric attributes.  This
task is supported in \proglang{R} by functions such as \func{cut}.  The
second step, the generation of binary dummy items, is automated in
package \pkg{arules} by coercing from \class{data.frame} to
\class{transactions}.  In this process, the original attribute names and
categories are preserved as additional item information and can be used
to select itemsets or rules which contain items referring to a certain
original attributes.
By default it is assumed that missing values do not carry information and thus
all of the corresponding dummy items are set to zero.  
If the fact
that the value of a specific attribute is missing provides information 
(e.g., a respondent in an interview refuses to answer a specific question), 
the domain expert can create for the attribute a category for missing values 
which then will be included in the transactions as its own dummy item.

The resulting \class{transactions} object can be
mined and analyzed the same way as market basket data, see the example
in Section~\ref{sec:example-screen}.


%% ------------------------------------------------------------------
%% ------------------------------------------------------------------
\subsection{Associations: itemsets and sets of rules\label{sec:associations}}

The result of mining transaction data in \pkg{arules} are
\class{associations.}  Conceptually, associations are sets of objects
describing the relationship between some items (e.g., as an itemset or a
rule) which have assigned values for different measures of quality.
Such measures can be measures of significance (e.g., support), or
measures of interestingness (e.g., confidence, lift), or other measures (e.g.,
revenue covered by the association).

All types of association have a common functionality in \pkg{arules} comprising
the following methods:
\begin{itemize}
 \item \func{summary} to give a short overview of the set and
  \func{inspect} to display individual associations,
 \item \func{length} for getting the number of elements in the set,
 \item \func{items} for getting for each association a set of items
  involved in the association (e.g., the union of the items in the LHS
  and the RHS for each rule),
 \item sorting the set using the values of different quality measures
  (\func{SORT}),
 \item subset extraction (\code{[} and \func{subset}),
 \item set operations (\func{union}, \func{intersect} and
  \func{setequal}), and
 \item matching elements from two sets (\func{match}),
% \item handling of duplicated elements for a collection
%     of associations (\func{duplicated} and \func{unique}).
\item \func{WRITE} for writing associations to disk in human readable form.
  To save and load associations in compact form, 
  use \func{save} and \func{load} from the
  \pkg{base} package. Package \pkg{pmml}~\citep{arules:Williams:2008} 
  includes functionality to
  save associations in PMML (Predictive Model Markup Language).
\end{itemize}

The associations currently implemented in package~\pkg{arules} are sets
of itemsets (e.g., used for frequent itemsets of their closed or maximal
subset) and sets of rules (e.g., association rules).  Both classes,
\class{itemsets} and \class{rules}, directly extend the virtual class
\class{associations} and provide the functionality described above.

Class \class{itemsets} contains one \class{itemMatrix} object to store
the items as a binary matrix where each row in the matrix represents an
itemset. In addition, it may contain transaction ID lists as an object
of class \class{tidLists}.  Note that when representing transactions,
\class{tidLists} store for each item a transaction list, but here store
for each itemset a list of transaction IDs in which the itemset appears.
Such lists are currently only returned by \func{eclat}.

Class \class{rules} consists of two \class{itemMatrix} objects
representing the left-hand-side (LHS) and the right-hand-side (RHS) of
the rules, respectively.

The items in the associations and the quality measures can be accessed
and manipulated in a safe way using accessor and replace methods for
\code{items}, \code{lhs}, \code{rhs}, and \code{quality}.  In addition
the association classes have built-in validity checking which ensures
that all elements have compatible dimensions.

It is simple to add new quality measures to existing associations.
Since the \code{quality} slot holds a \class{data.frame}, additional
columns with new quality measures can be added. These new measures can
then be used to sort or select associations using \func{SORT} or
\func{subset}.  Adding a new type of associations to \pkg{arules} is
straightforward as well. To do so, a developer has to create a new class
extending the virtual \class{associations} class and implement the
common functionality described above.

%% ------------------------------------------------------------------
%% ------------------------------------------------------------------

\section{Mining algorithm interfaces\label{sec:interfaces}}

In package \pkg{arules} we interface free reference implementations of
Apriori and Eclat by Christian Borgelt
\citep{arules:Borgelt+Kruse:2002,arules:Borgelt:2003}\footnote{Christian
Borgelt provides the source code for Apriori and Eclat at
\url{http://www.borgelt.net/fpm.html}.}.  The code is
called directly from \proglang{R} by the functions \func{apriori} and
\func{eclat} and the data objects are directly passed from \proglang{R} to
the \proglang{C} code and back without writing to external files.
The implementations can mine frequent itemsets,
and closed and maximal frequent itemsets. 
In addition, \func{apriori} can also mine association rules.  

The data given to the \func{apriori} and \func{eclat} functions have to
be \class{transactions} or something which can be coerced to
\class{transactions} (e.g., \class{matrix} or \class{list}).  The
algorithm parameters are divided into two groups represented by the
arguments \code{parameter} and \code{control}.  The mining parameters
(\code{parameter}) change the characteristics of the mined itemsets or
rules (e.g., the minimum support) and the control parameters
(\code{control}) influence the performance of the algorithm (e.g.,
enable or disable initial sorting of the items with respect to their
frequency).  These arguments have to be instances of the classes
\class{APparameter} and \class{APcontrol} for the function
\func{apriori} or \class{ECparameter} and \class{ECcontrol} for the
function \func{eclat}, respectively.  Alternatively, data which can be
coerced to these classes (e.g., \code{NULL} which will give the default
values or a named list with names equal to slot names to change the
default values) can be passed.  In these classes, each slot specifies a
different parameter and the values.  The default values are equal to the
defaults of the stand-alone \proglang{C} programs
\citep{arules:Borgelt:1996} except that the standard definition of the
support of a rule \citep{arules:Agrawal+Imielinski+Swami:1993} is
employed for the specified minimum support required (Borgelt defines the
support of a rule as the support of its antecedent).

For \func{apriori} the appearance feature implemented by Christian
Borgelt can also be used.  With argument \code{appearance} of function
\func{apriori} one can specify which items have to or must not appear in
itemsets or rules.  For more information on this feature we refer to the
Apriori manual~\citep{arules:Borgelt:1996}.

The output of the functions \func{apriori} and \func{eclat} is an object
of a class extending \class{associations} which contains the sets of mined
associations and can be further analyzed using the functionality provided for
these classes.


There exist many different algorithms which 
which use an
incidence matrix or transaction ID list representation as input and
solve the frequent and
closed frequent itemset problems.  Each algorithm has specific strengths
which can be important for very large databases.  Such algorithms, e.g.
kDCI, LCM, FP-Growth or Patricia, are discussed
in~\cite{arules:Goethals+Zaki:2003}.  The source code of most algorithms
is available on the internet and, if a special algorithm is needed, 
interfacing the
algorithms for \pkg{arules} is straightforward.
The necessary steps are:

\begin{enumerate}
 \item Adding interface code to the algorithm, preferably by directly
  calling into the native implementation language (rather than using
  files for communication), and an \proglang{R} function calling this
  interface.
 \item Implementing extensions for \class{ASparameter} and
  \class{AScontrol}.
\end{enumerate}



\section{Auxiliary functions \label{sec:auxiliary}}

In \pkg{arules} several helpful functions are implemented for
support counting, rule induction, sampling, etc.
In the following we will discuss some of these functions.

\subsection{Counting support for itemsets\label{sec:counting}}

Normally, itemset support is counted during mining the database with a
given minimum support constraint.  During this process all frequent
itemsets plus some infrequent candidate itemsets are counted (or support
is determined by other means).  Especially for databases with many items
and for low minimum support values, this procedure can be extremely time
consuming since in the worst case, the number of frequent itemsets grows
exponentially in the number of items.

If only the support information for a single or a few itemsets is needed,
we might not want to mine the database for all frequent itemsets. 
We also do not know in advance how high (or low) to set the minimum support to
still get the support information for the itemsets in question.
For this problem, \pkg{arules} contains \func{support}
which determines the support for a set of given sets of items
(as an \class{itemMatrix}).

For counting, we use a prefix tree~\citep{arules:Knuth:1997} to organize the
counters. The used prefix tree is similar to the itemset tree described
by~\cite{arules:Borgelt+Kruse:2002}. However, we do not generate the tree
level-wise, but we first generate a prefix tree which only contains the nodes
necessary to hold the counters for all itemsets which need to be counted.
Using the nodes in this tree only, we count the itemsets for each
transaction recursively. After counting, the support for each itemset is
contained in the node with the prefix equal to the itemset. The exact
procedure is described in~\cite{arules:Hahsler+Buchta+Hornik:2007}.

In addition to determining the support of a few itemsets without mining all
frequent itemsets, \func{support} is also useful for finding 
the support of infrequent itemsets with a support so low that mining
is infeasible due to combinatorial explosion.


\subsection{Rule induction\label{sec:induction}}

For convenience we introduce $\set{X} = \{X_1, X_2, \ldots, X_l\}$ for
sets of itemsets with length $l$.  Analogously, we write $\set{R}$ for
sets of rules.  A part of the association rule mining problem is the
generation (or induction) of a set of rules~$\set{R}$ from a set of
frequent itemsets~$\set{X}$.  The implementation of the Apriori
algorithm used in \pkg{arules} already contains a rule induction engine
and by default returns the set of association rules of the form $X
\Rightarrow Y$ which satisfy given minimum support and minimum
confidence.  Following the definition of
\cite{arules:Agrawal+Imielinski+Swami:1993} $Y$ is restricted to single
items.

In some cases it is necessary to separate mining itemsets and generating
rules from itemsets. For example, only rules stemming from a subset of
all frequent itemsets might be of interest to the user.  The Apriori
implementation efficiently generates rules by reusing the data
structures built during mining the frequent itemsets.  However, if
Apriori is used to return only itemsets or Eclat or some other algorithm
is used to mine itemsets, the data structure needed for rule induction
is no longer available for computing rule confidence.

If rules need to be induced from an arbitrary set of itemsets, support
values required to calculate confidence are typically missing.  For
example, if all available information is an itemset containing five
items and we want to induce rules, we need the support of the itemset
(which we might know), but also the support of all subsets of length
four. The missing support information has to be counted from the
database. Finally, to induce rules efficiently for a given set of
itemsets, we also have to store support values in a suitable data
structure which allows fast look-ups for calculating rule confidence.

Function~\func{ruleInduction} provided in \pkg{arules} 
uses a prefix tree to induce rules for a given
confidence from an arbitrary set of itemsets $\set{X}$ in the following
way:

\begin{enumerate}
    \item Count  the support values for each itemset $X \in \set{X}$ and the
        subsets $\{X \setminus \{x\}: x \in X\}$ needed for rule generation
        in a single pass over the database
        and store them in a suitable data structure.
    \item Populate set $\set{R}$ by selectively generating only rules for the
        itemsets in $\set{X}$ using the support information
        from the data structure created in step 1.
\end{enumerate}


Efficient support counting is done as described in Section~\ref{sec:counting}
above. After counting, all necessary support counts are contained in the prefix
tree. We can retrieve the needed support values and generating the rules is
straight forward. The exact procedure is described
in~\cite{arules:Hahsler+Buchta+Hornik:2007}.


\subsection{Sampling from transactions\label{sec:sample}}

Taking samples from large databases for mining is a powerful technique