Content deleted Content added
→Overview: Pseudocode: Alternative verbose union |
Citation bot (talk | contribs) Add: doi, pages. | Use this bot. Report bugs. | Suggested by Dominic3203 | Linked from User:LinguisticMystic/cs/outline | #UCB_webform_linked 93/2277 |
||
| (5 intermediate revisions by 5 users not shown) | |||
Line 4:
== Overview ==
The Apriori algorithm was proposed by Agrawal and Srikant in 1994. Apriori is designed to operate on [[database]]s containing transactions (for example, collections of items bought by customers, or details of a website frequentation or [[IP address]]es<ref>
Apriori uses a "bottom up" approach, where frequent subsets are extended one item at a time (a step known as ''candidate generation''), and groups of candidates are tested against the data. The algorithm terminates when no further successful extensions are found.
Line 43:
{| class="wikitable"
|-
|-
| α || β ||
|-
| α || β ||
|-
| &alpha
▲| alpha|| beta || theta
|}
The association rules that can be determined from this database are the following:
# 100% of sets with α also contain β
# 50% of sets with α, β also have ε
# 50% of sets with α, β also have θ
we can also illustrate this through a variety of examples.
Line 142 ⟶ 141:
Also, both the time and space complexity of this algorithm are very high: <math>O\left(2^{|D|}\right)</math>, thus exponential, where <math>|D|</math> is the horizontal width (the total number of items) present in the database.
Later algorithms such as [[Max-Miner]]<ref>{{cite journal|author=Bayardo Jr, Roberto J.|title=Efficiently mining long patterns from databases|journal=ACM SIGMOD Record |volume=27|issue=2|year=1998|pages=85–93 |doi=10.1145/276305.276313 |url=http://www.cs.sfu.ca/CourseCentral/741/jpei/readings/baya98.pdf}}</ref> try to identify the maximal frequent item sets without enumerating their subsets, and perform "jumps" in the search space rather than a purely bottom-up approach.
== References ==
| |||