DATA MINING Desktop Survival Guide by Graham Williams
Desktop Survival Project Home List of Figures List of Tables Data Mining Data Mining Data Mining with Rattle Introduction Data Transform Explore A Model Building Framework Unsupervised Modelling Two Class Models Multi Class Models Regression Models Text Mining Evaluation and Deployment Moving into R Troubleshooting R for the Data Miner R Data Graphics in R Understanding Data Preparing Data Building Models Evaluating Models Algorithms Apriori Bagging Bayes Classifier Boosting Cluster Analysis Conditional Trees Hierarchical Clustering K-Means K-Nearest Neighbours Linear Models Logistic Regression Neural Networks Support Vector Machines Text Mining Open Products AlphaMiner Borgelt Data Mining Suite KNime R Rattle Weka Closed Products C4.5 Clementine Equbits Foresight GhostMiner InductionEngine ODM Enterprise Miner Statistica Data Miner TreeNet Virtual Predict Appendicies Glossary Bibliography Index

Algorithm

The Apriori algorithm is a breadth-first or generate-and-test type of search algorithm. Only after exploring all possibilities of associations containing $k$ items does it then consider those containing $k+1$ items. For each $k$, all candidates are tested to determine whether they have enough support.

The algorithm uses a simple two step generate and merge process: generate frequent itemsets of size $k$ then combine them to generate candidate frequent itemsets of size $k+1$.

The algorithm is generally simple to implement and is reasonably efficient even though the number of possible items is generally large and the baskets are generally small.

The input data to the algorithm consists of entities or transactions, each transaction representing a basket of items.

The two primary tuning parameters are minsup (minimum support expressed as a percentage of the total number of transactions in data) and mincon (minimum confidence also expressed as a percentage of the total number of transactions in data). Typically they have quite small values because of the size of the databases we are dealing with. Thus a support of 0.1% or smaller is not unusual.

Procedure $\proc{Apriori}$ returns a set of association rules, each consisting of a left hand side, right hand side and a support and confidence tuple.

[gray].97$\parbox{0.985\textwidth}{\begin{codebox} \Procname{$\proc{Apriori}(\... ...ndentless \li \Return $\proc{BuildAssociations}(f, \id{mincon})$ \end{codebox}}$

[gray].97$\parbox{0.985\textwidth}{\begin{codebox} \Procname{$\proc{GenerateCa... ...dentless \Indentless \Indentless \li \Return $\id{candidates}$ \end{codebox}}$

[gray].97$\parbox{0.985\textwidth}{\begin{codebox} \Procname{$\proc{BuildAssoc... ... \Indentless \Indentless \Indentless \li \Return $\id{rules}$ \end{codebox}}$

Support further development through the purchase of the PDF version of the book.
Brought to you by Togaware.