arules.rnw

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

(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
which is especially useful if the original database does not fit into
main memory, but the sample does.  However, even if the database fits
into main memory, sampling can provide an enormous speed-up for mining
at the cost of only little degradation of accuracy.

\cite{arules:Mannila+Toivonen+Verkamo:1994}
proposed sampling with replacement for association rule mining
and quantify the estimation error due to sampling.
Using Chernov bounds on the binomial distribution (the number of
transactions which contains a given itemset in a sample),
the authors argue that in theory even relatively small samples 
should provide good estimates for support.

\cite{arules:Zaki+Parthasarathy+Li+Ogihara:1997} built upon the
theoretic work by \cite{arules:Mannila+Toivonen+Verkamo:1994} and show
that for an itemset $X$ with support $\tau = \mathrm{supp}(X)$ and for
an acceptable relative error of support $\epsilon$ (an accuracy of $1 -
\epsilon$) at a given confidence level $1-c$, the needed sample size~$n$
can be computed by

\begin{equation}
n = \frac{-2\mathrm{ln}(c)}{\tau\epsilon^2}.
\label{equ:samplesize}
\end{equation}

Depending on its support, for each itemset a different sample size is
appropriate.  As a heuristic, the authors suggest to use the user
specified minimum support threshold for $\tau$.  This means that for
itemsets close to minimum support, the given error and confidence level
hold while for more frequent itemsets the error rate will be less.
However, with this heuristic the error rate for itemsets below minimum
support can exceed $\epsilon$ at the given confidence level and thus
some infrequent itemsets might appear as frequent ones in the sample.

\cite{arules:Zaki+Parthasarathy+Li+Ogihara:1997} also evaluated sampling
in practice on several data sets and conclude that sampling not only
speeds mining up considerably, but also the errors are considerably
smaller than those given by the Chernov bounds and thus samples with
size smaller than obtained by Equation~\ref{equ:samplesize} are often
sufficient.

Another way to obtain the required sample size 
for association rule mining is progressive 
sampling~\citep{arules:Parthasarathy:2002}.
This approach starts with a small sample and uses progressively larger 
samples until model accuracy does not improve significantly anymore. 
\cite{arules:Parthasarathy:2002} defines a proxy for 
model accuracy improvement by using a similarity measure between two
sets of associations. The idea is that 
since larger samples will produce more accurate results, the
similarity between two sets of associations of two consecutive samples
is low if accuracy improvements are high and increases with
decreasing accuracy improvements.
Thus increasing sample size can be stopped if the similarity
between consecutive samples reaches a ``plateau.'' 

\cite{arules:Toivonen:1996} presents an application of sampling to reduce
the needed I/O overhead for very large databases which do not fit into 
main memory.
The idea is to use a random sample from the data base to mine
frequent itemsets at a support threshold below the set minimum support.
The support of these itemsets is then counted in the whole database 
and the infrequent itemsets are discarded. 
If the support threshold to mine the sample is picked low enough, 
almost all frequent itemsets and their support will be found
in one pass over the large database.

In \pkg{arules} sampling is implemented by \func{sample}
which provides all capabilities of the standard sampling function 
in \proglang{R}
(e.g., sampling with or without replacement and probability weights).


\subsection{Generating synthetic transaction data}
Synthetic data can be used to evaluate and compare different mining algorithms
and to study the behavior of measures of interestingness. 

In \pkg{arules} the function \func{random.transactions} can be used to create 
synthetic transaction data. Currently there are two methods available.  The
first method reimplements the well known generator for transaction data for
mining association rules developed by~\cite{arules:Agrawal+Srikant:1994}. The
second method implements a simple probabilistic model where each transaction is
the result of one independent Bernoulli trial for each item
(see~\citep{arules:Hahsler+Hornik+Reutterer:2005}).


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


\subsection{Sub-, super-, maximal and closed itemsets}
For some calculations it is necessary to find all sub- or supersets 
for a specific itemset
in a set of itemsets. This functionality is implemented as 
\func{is.subset} and \func{is.superset}. 
For example, \code{is.subset(x, y, proper = TRUE)}, finds all
proper subsets of the itemsets in \code{x} in the set~\code{y}. 
The result is a logical matrix with \code{length(x)} 
rows and \code{length(y)} columns.  Each logical row vector represents 
which elements in \code{y} are subsets of the corresponding element in 
\code{x}. If \code{y} is omitted, the sub- or superset structure within the
set \code{x} is returned.

Similar methods, \func{is.maximal} and \func{is.closed}, can be used to find all
\emph{maximal itemsets} or \emph{closed itemsets} in a set.  An itemset is
maximal in a set if no proper superset of the itemset is contained in the
set~\citep{arules:Zaki+Parthasarathy+Ogihara+Li:1997}.  An itemset is closed,
if it is its own closure (i.e., for an items no superset with the same support
exits)~\citep{arules:Pasquier+Bastide+Taouil+Lakhal:1999}.


Note that these methods can be extremely slow and have high memory 
usage if the set contains many itemsets. 

\subsection{Additional measures of interestingness}
\pkg{arules} provides 
\func{interestMeasure}
which can be used to calculate
a broad variety of interest measures for itemsets and rules. 
To speed up the calculation, we try to reuse the quality information available 
from the sets of itemsets or rules (i.e., support, confidence, lift) and, only
if necessary, missing information is obtained from the
transactions used to mine the associations.

For example, available measures for itemsets are:
\begin{itemize}
\item All-confidence~\citep{arules:Omiecinski:2003}
\item Cross-support ratio~\citep{arules:Xiong+Tan+Kumar:2003}
\item Support
\end{itemize}

For rules the following measures are implemented:
\begin{itemize}
\item Chi square measure~\citep{arules:Liu+Hsu+Ma:1999}
\item Conviction~\citep{arules:Brin+Motwani+Ullman+Tsur:1997} 
\item Confidence
\item Difference of Confidence (DOC)~\citep{arules:Hofmann+Wilhelm:2001}
\item Hyper-lift and hyper-confidence~\citep{arules:Hahsler+Hornik:2007} 
\item Leverage~\citep{arules:Piatetsky-Shapiro:1991} 
\item Lift
\item Improvement~\citep{arules:Bayardo+Agrawal+Gunopulos:2000} 
\item Support
\item Several measures from \cite{arules:Tan+Kumar+Srivastava2004} 
  (e.g., cosine, Gini index, $\phi$-coefficient, odds ratio)
\end{itemize}

\subsection{Distance based clustering transactions and associations}

To allow for distance based clustering~\citep{arules:Gupta+Strehl+Ghosh:1999},
\pkg{arules} provides \func{dissimilarity} which can be used to calculate
dissimilarities and cross-dissimilarities between transactions or associations
(i.e., itemsets and rules). Currently, the following standard measures for
binary data are available: Jaccard coefficient, simple matching coefficient and
dice coefficient. Additionally, dissimilarity between transactions can be
calculated based on affinities between
items~\citep{arules:Aggarwal+Procopiuc+Yu:2002}.

The result of \func{dissimilarity} is either a \code{dist} object, which can be
directly used by most clustering methods in R (e.g., \code{hclust} for
hierarchical clustering), or an object of class \code{ar\_cross\_dissimilarity}.

Since the number of transactions or associations in often too large to
efficiently calculate a dissimilarity matrix and apply a clustering algorithm,
\func{sample} can be used to cluster only a subset of transactions 
(associations). To assign the remaining transactions (associations)
to clusters, \func{predict} implements the nearest neighbor approach for
predicting memberships for new data.

A small example can be found in~\cite{arules:Hahsler+Hornik:2007b}.

\section{Examples\label{sec:examples}}

\subsection{Example 1: Analyzing and preparing a transaction 
data set \label{sec:example-screen}}

In this example, 
we show how a data set can be analyzed and manipulated
before associations are mined.
This is important for finding problems in the data set which 
could make the mined associations useless or at least inferior
to associations mined on a properly prepared data set.
For the example,
we look at the \code{Epub} transaction data contained in
package \pkg{arules}.  This data set contains downloads of documents
from the Electronic Publication platform of the Vienna University of
Economics and Business Administration available via
\url{http://epub.wu-wien.ac.at} from January 2003 to August 2005.

First, we load \pkg{arules} and the data set.

<<>>=
library("arules")
@

<<epub1>>=
data("Epub")
Epub
@

We see that the data set consists of \Sexpr{length(Epub)} transactions
and is represented as a sparse matrix with \Sexpr{length(Epub)} rows
and \Sexpr{dim(Epub)[2]} columns which represent the items. 
Next, we use the \func{summary} to get more information about the 
data set.

<<epub2>>=
summary(Epub)
@

\func{summary} displays the most frequent items in the data set,
information about the transaction length distribution and that the data
set contains some extended transaction information.  We see that the
data set contains transaction IDs and in addition time stamps (using
class \class{POSIXct}) for the transactions.  This additional
information can be used for analyzing the data set.

<<>>=
year <- strftime(as.POSIXlt(transactionInfo(Epub)[["TimeStamp"]]), "%Y")
table(year)
@

For 2003, the first year in the data set, we have \Sexpr{table(year)[1]}
transactions.  We can select the corresponding transactions and inspect
the structure using a level-plot (see Figure~\ref{fig:imageEpub}).

%%% lattice image returns an object of class "trellis"
<<fig=FALSE>>=
Epub2003 <- Epub[year == "2003"]
length(Epub2003)
image(Epub2003)
@ %
\begin{figure}
\centering
<<echo=FALSE, fig=TRUE, include=FALSE, label=epub>>=
print(image(Epub2003))
@ %
\includegraphics[width=10cm]{arules-epub}
\caption{The Epub data set (year 2003).}
\label{fig:imageEpub}
\end{figure}

The plot is a direct visualization of the binary incidence matrix where
the the dark dots represent the ones in the matrix.  From the plot we
see that the items in the data set are not evenly distributed.  In fact,
the white area to the top right side suggests, that in the beginning of
2003 only very few items were available (less than 50) and then during
the year more items were added until it reached a number of around 300
items. Also, we can see that there are some transactions in the data set
which contain a very high number of items (denser horizontal lines).
These transactions need further investigation since they could originate
from data collection problems (e.g., a web robot downloading many
documents from the publication site).  To find the very long