arules.tex

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

%\multirow{9}{1.5ex}{ \begin{sideways} itemsets \end{sideways} }
%\multirow{8}{1.5ex}{ \begin{sideways} itemsets \end{sideways} }
\multirow{4}{*}{\begin{sideways} itemsets \end{sideways}}

%& $X_1$ 		& 0 & 1 & 0 & . . . & 1 \\
%& $X_2$ 	  	& 0 & 1 & 0 & . . . & 1 \\
%& $X_3$ 		& 0 & 1 & 0 & . . . & 0 \\
%& $X_4$ 		& 0 & 0 & 1 & . . . & 0 \\
%& \phantom{-}.&.&.&.&\hspace{-7mm}.&.\\
%& \phantom{-}.&.&.&.&.&.\\
%& \phantom{-}.&.&.&.&\hspace{7mm}.&.\\
%& $X_{m-1}$ 		& 1 & 0 & 0 & . . . & 1 \\
%& $X_m$ 		& 0 & 0 & 1 & . . . & 1 \\

& $X_1$ 		& 1 & 1 & 0 &  0 \\
& $X_2$ 	  	& 0 & 1 & 0 &  1 \\
& $X_3$ 		& 1 & 1 & 1 &  0 \\
& $X_4$ 		& 0 & 0 & 1 &  0 \\
%& \phantom{-}.&.&.&.&.\\
%& \phantom{-}.&.&.&.&.\\
%& \phantom{-}.&.&.&.&.\\
%& $X_{m-1}$ 		& 1 & 0 & 0 & 1 \\
%& $X_m$ 		& 0 & 1 & 1 & 0 \\
\end{tabular}
\caption{Example of a collection of itemsets represented as a 
    binary incidence matrix.\label{fig:itemsetMatrix}}
\end{figure}

Collections of itemsets used for transaction databases and sets of
associations can be represented as binary incidence matrices with
columns corresponding to the items and rows corresponding to the
itemsets.  The matrix entries represent the presence (1) or absence (0)
of an item in a particular itemset.  An example of a binary incidence
matrix containing itemsets for the example database in
Figure~\ref{table:supermarket} on Page~\pageref{table:supermarket} is
shown in Figure~\ref{fig:itemsetMatrix}.  Note that we need to store
collections of itemsets with possibly duplicated elements (identical
rows), i.e, itemsets containing exactly the same items. This is
necessary, since a transaction database can contain different
transactions with the same items. Such a database is still a set of
transactions since each transaction also contains a unique
transaction~ID.

Since a typical frequent itemset or a typical transaction (e.g., a
supermarket transaction) only contains a small number of items compared
to the total number of available items, the binary incidence matrix will
in general be very sparse with many items and a very large number of
rows.  A natural representation for such data is a sparse matrix format.
For our implementation we chose the \class{ngCMatrix} class defined in
package~\pkg{Matrix}.  The \class{ngCMatrix} is a compressed, sparse, logical,
column-oriented matrix which contains the indices of the \code{TRUE} rows and
the pointers to the initial indices of elements in each column of the matrix.
Despite the column orientation of the \class{ngCMatrix}, it is more convenient
to work with incidence matrices which are row-oriented.  This makes the most
important manipulation, selecting a subset of transactions from a data set for
mining, more comfortable and efficient.  Therefore, we implemented the class
\class{itemMatrix} providing a row-oriented facade to the \class{ngCMatrix}
which stores a transposed incidence matrix\footnote{Note that the developers of
package~\pkg{Matrix} contains some support for a sparse row-oriented format,
but the available functionality currently is rather minimal.  Once all required
functionality is implemented, \pkg{arules} will switch the internal
representation to sparse row-oriented logical matrices.}.  
In sparse representation the following
information needs to be stored for the collection of itemsets in
Figure~\ref{fig:itemsetMatrix}: A vector of indices of the non-zero
elements (row-wise starting with the first row) $1, 2, 2, 4, 1, 2, 3, 3$
and the pointers $1, 3, 5, 8$ where each row starts in the index vector.
The first two pointers indicate that the first row starts with element
one in the index vector and ends with element 2 (since with element 3
already the next row starts).  The first two elements of the index
vector represent the items in the first row which are $i_1$ and $i_2$ or
milk and bread, respectively.  The two vectors are stored in the
\class{ngCMatrix}. Note that indices for the \class{ngCMatrix} start
with zero rather than with one and thus actually the vectors $0, 1, 1,
3, 0, 3, 3$ and $0, 3, 4, 7$ are stored.  However, the data structure of
the \class{ngCMatrix} class is not intended to be directly accessed by
the end user of \pkg{arules}. The interfaces of \class{itemMatrix} can
be used without knowledge of how the internal representation of the data
works.  However, if necessary, the \class{ngCMatrix} can be directly
accessed by developers to add functionality to \pkg{arules} (e.g., to
develop new types of associations or interest measures or to efficiently
compute a distance matrix between itemsets for clustering).  In this
case, the \class{ngCMatrix} should be accessed using the coercion
mechanism from \class{itemMatrix} to \class{ngCMatrix} via \func{as}.

In addition to the sparse matrix, \class{itemMatrix} stores item labels
(e.g., names of the items) and handles the necessary mapping between the
item label and the corresponding column number in the incidence matrix.
Optionally, \class{itemMatrix} can also store additional information on
items.  For example, the category hierarchy in a supermarket setting can
be stored which enables the analyst to select only transactions (or as
we later see also rules and itemsets) which contain items from a certain
category (e.g., all dairy products).

For \class{itemMatrix}, basic matrix operations including \func{dim} and
subset selection (\code{[}) are available.  The first element of
\func{dim} and \code{[} corresponds to itemsets or transactions (rows),
the second element to items (columns).  For example, on a transaction
data set in variable \code{x} the subset selection \samp{x[1:10, 16:20]}
selects a matrix containing the first 10 transactions and items 16 to
20.

Since \class{itemMatrix} is used to represent sets 
or collections of itemsets additional functionality is provided.
\func{length} can be used to get the number of itemsets in an
\class{itemMatrix}.
Technically, \func{length} returns the number of rows in the matrix
which is equal to the first element returned by \func{dim}.
%\pkg{arules} also provides set operations including \func{union},
%\func{intersect} and \func{setequal}.
Identical itemsets can be found with \func{duplicated}, and duplications
can be removed with \func{unique}.  \func{match} can be used to find
matching elements in two collections of itemsets.

With \func{c}, several \class{itemMatrix} objects can be combined by
successively appending the rows of the objects, i.e., creating a
collection of itemsets which contains the itemsets from all
\class{itemMatrix} objects.  This operation is only possible if the
\class{itemMatrix} objects employed are ``compatible,'' i.e., if the
matrices have the same number of columns and the items are in the same
order.  If two objects contain the same items (item labels), but the
order in the matrix is different or one object is missing some items,
\func{recode} can be used to make them compatible by reordering and
inserting columns.


To get the actual number of items in the itemsets stored in the
\class{itemMatrix}, \func{size} is used.  It returns a vector with the
number of items (ones) for each element in the set (row sum in the
matrix).  Obtaining the sizes from the sparse representations is a very
efficient operation, since it can be calculated directly from the vector
of column pointers in the \class{ngCMatrix}.  For a purchase incidence
matrix, \func{size} will produce a vector as long as the number of
transactions in the matrix with each element of the vector containing
the number of items in the corresponding transaction.  This information
can be used, e.g., to select or filter unusually long or short
transactions.

\func{itemFrequency} calculates the frequency for each item in an
\class{itemMatrix}. Conceptually, the item frequencies are the column sums of
the binary matrix. Technically, column sums can be implemented for sparse
representation efficiently by just tabulating the vector of row numbers of the
non-zero elements in the \class{ngCMatrix}.  Item frequencies can be used for
many purposes.  For example, they are needed to compute interest measures.
\func{itemFrequency} is also used by \func{itemFrequencyPlot} to produce a bar
plot of item count frequencies or support.  Such a plot gives a quick overview
of a set of itemsets and shows which are the most important items in terms of
occurrence frequency.


Coercion from and to \class{matrix} and \class{list} primitives is
provided where names and dimnames are used as item labels.  For the
coercion from \class{itemMatrix} to \class{list} there are two
possibilities.  The usual coercion via \func{as} results in a list of
vectors of character strings, each containing the item labels of the
items in the corresponding row of the \class{itemMatrix}.  The actual
conversion is done by \func{LIST} with its default behavior (argument
\code{decode} set to \code{TRUE}).  If in turn \func{LIST} is called
with the argument \code{decode} set to \code{FALSE}, the result is a
list of integer vectors with column numbers for items instead of the
item labels. For many computations it is useful to work with such a list
and later use the item column numbers to go back to the original
\class{itemMatrix} for, e.g., subsetting columns.  For subsequently
decoding column numbers to item labels, \func{decode} is also available.

Finally, \func{image} can be used to produce a level plot of an
\class{itemMatrix} which is useful for quick visual inspection.  For
transaction data sets (e.g., point-of-sale data) such a plot can be very
helpful for checking whether the data set contains structural changes (e.g.,
items were not offered or out-of-stock during part of the observation
period) or to find abnormal transactions (e.g., transactions which
contain almost all items may point to recording problems).  Spotting
such problems in the data can be very helpful for data preparation.



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

\subsection{Transaction data\label{sec:transactions}}

The main application of association rules is for market basket analysis
where large transaction data sets are mined.  In this setting each
transaction contains the items which were purchased at one visit to a
retail store \citep[see e.g.,][]{arules:Berry+Linoff:1997}.
Transaction data are normally recorded by point-of-sale
scanners and often consists of tuples of the form:

\begin{displaymath}
<\emph{transaction ID}, \emph{item ID}, \ldots >
\end{displaymath}

All tuples with the same transaction ID form a single transaction which
contains all the items given by the item IDs in the tuples.  Additional
information denoted by the ellipsis dots might be available.  For
example, a customer ID might be provided via a loyalty program in a
supermarket.  Further information on transactions (e.g., time,
location), on the items (e.g., category, price), or on the customers
(socio-demographic variables such as age, gender, etc.) might also be
available.

\begin{figure}[tp]
\centering
%\includegraphics[width=12cm]{transactionMatrix}

\begin{minipage}[b]{.4\linewidth}
\renewcommand{\arraystretch}{1.1}
\setlength{\tabcolsep}{2mm}
%
\begin{center}
\begin{tabular}{cl|cccc}
& & \multicolumn{4}{c}{items}\\

& & milk & bread & butter & beer \\
%\hline
\cline{2-6}
\multirow{5}{*}{\begin{sideways} transactions \end{sideways}}

& 1 		& 1 & 1 & 0 & 0 \\
& 2 	  	& 0 & 1 & 1 & 0 \\
& 3 		& 0 & 0 & 0 & 1 \\
& 4 		& 1 & 1 & 1 & 0 \\
& 5 		& 0 & 1 & 1 & 0 \\
\end{tabular}

\vspace{1cm}
(a)
\end{center}
\end{minipage}
%
\hspace{.1\linewidth}
%
\begin{minipage}[b]{.4\linewidth}
\renewcommand{\arraystretch}{1.1}
\setlength{\tabcolsep}{2mm}
%
\begin{center}
\begin{tabular}{cl|l}
& & \multicolumn{1}{c}{transaction ID lists}\\

%\hline
\cline{2-3}
\multirow{4}{*}{\begin{sideways} items \end{sideways}}

& milk  		& 1, 4 \\
& bread  		& 1, 2, 4, 5 \\
& butter 		& 2, 4 \\
& beer  		& 3 \\
\end{tabular}

\vspace{1.5cm}
(b)
\end{center}
\end{minipage}

\caption{Example of a set of transactions represented in 
    (a) horizontal layout and in 
    (b) vertical layout.\label{fig:transactionMatrix}}
\end{figure}

For mining, the transaction data is first transformed into a binary
purchase incidence matrix with columns corresponding to the different
items and rows corresponding to transactions.  The matrix entries
represent the presence (1) or absence (0) of an item in a particular
transaction.  This format is often called the \emph{horizontal} database
layout~\citep{arules:Zaki:2000}.  Alternatively, transaction data can be
represented in a \emph{vertical} database layout in the form of
\emph{transaction ID lists}~\citep{arules:Zaki:2000}.  In this format
for each item a list of IDs of the transactions the item is contained in
is stored.  In Figure~\ref{fig:transactionMatrix} the example database
in Figure~\ref{table:supermarket} on Page~\pageref{table:supermarket} is
depicted in horizontal and vertical layouts.  Depending on the
algorithm, one of the layouts is used for mining.  In \pkg{arules} both
layouts are implemented as the classes~\class{transactions} and
\class{tidLists}.  Similar to \class{transactions},
class~\class{tidLists} also uses a sparse representation to store its
lists efficiently.  Objects of classes~\class{transactions} and
\class{tidLists} can be directly converted into each other by coercion.

The class \class{transactions} directly extends \class{itemMatrix} and
inherits its basic functionality (e.g., subset selection, getting
itemset sizes, plotting item frequencies).  In addition,
\class{transactions} has a slot to store further information for each
transaction in form of a \class{data.frame}.  The slot can hold
arbitrary named vectors with length equal to the number of stored
transactions.  In \pkg{arules} the slot is currently used to store
transaction IDs, however, it can also be used to store user IDs, revenue
or profit, or other information on each transaction.  With this
information subsets of transactions (e.g., only transactions of a
certain user or exceeding a specified profit level) can be selected.

Objects of class \class{transactions} can be easily created by coercion
from \class{matrix} or \class{list}.  If names or dimnames are available