Apriori algorithm: Difference between revisions

Revision as of 05:18, 13 March 2023

Latest revision as of 14:04, 16 April 2025

(20 intermediate revisions by 15 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>{{usurped|1=[https://web.archive.org/web/20210822191810/https://deductive.com/blogs/data-science-ip-matching/ The data science behind IP address matching]}} Published by deductive.com, September 6, 2018, retrieved September 7, 2018</ref>). Other algorithms are designed for finding association rules in data having no transactions ([[Winepi]] and Minepi), or having no timestamps ([[DNA sequencing]]). Each transaction is seen as a set of items (an ''itemset''). Given a threshold <math>C</math>, the Apriori algorithm identifies the item sets which are subsets of at least <math>C</math> transactions in the database.

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 13:

'''Apriori'''(T, ε)

L₁ ← {large 1 -singleton itemsets}

k ← 2

'''while''' L_k−1 '''is not''' empty

C_k ← Apriori_genGenerate_candidates(L_k−1, k)

'''for''' transactions t '''in''' T

D_t ← {c in C_k : c ⊆ t}

Line 25:

k ← k + 1

'''return''' Union(L_k) '''over all''' k

'''Apriori_genGenerate_candidates'''(L, k)

result ← listempty_set()

'''for all''' p ∈ L, q ∈ L '''where''' p₁ =and q₁, p₂differ =in q₂,exactly ...,one p_k-2 = q_k-2 and p_k-1 < q_k-1element

c =← p ∪ {q_k-1}

'''if''' u ∈ L '''for all''' u ⊆ c '''where''' |u| = k-1

result.add(c)

'''return''' result

== Examples ==

Line 41:

Consider the following database, where each row is a transaction and each cell is an individual item of the transaction:

{| class="ddddwikitable"

|-

| &alpha; || &beta; || &epsilon;

|-

| &alpha; || &beta; || epsilon&theta;

|-

| &alpha ; || &beta; || &epsilon;

|-

| &alpha; || &beta; || &theta;

|}

The association rules that can be determined from this database are the following:

# 100% of sets with &alpha; also contain &beta;

# 50% of sets with &alpha;, &beta; also have &epsilon;

# 50% of sets with &alpha;, &beta; also have &theta;

we can also illustrate this through a variety of examples.

Line 70 ⟶ 72:

|-

| {1,2}

|-

|-We will use Apriori to determine the frequent item sets of this database. To do this, we will say that an item set is frequent if it appears in at least 3 transactions of the database: the value 3 is the ''support threshold''.

| {2,3,4}

|-

| {2,3}

|-

| {3,4}

|-

| {2,4}

|}

|-We will use Apriori to determine the frequent item sets of this database. To do this, we will say that an item set is frequent if it appears in at least 3 transactions of the database: the value 3 is the ''support threshold''.

The first step of Apriori is to count up the number of occurrences, called the support, of each member item separately. By scanning the database for the first time, we obtain the following result

Line 109 ⟶ 120:

| {3,4}||3

|}

sit@123

The pairs {1,2}, {2,3}, {2,4}, and {3,4} all meet or exceed the minimum support of 3, so they are frequent. The pairs {1,3} and {1,4} are not. Now, because {1,3} and {1,4} are not frequent, any larger set which contains {1,3} or {1,4} cannot be frequent. In this way, we can ''prune'' sets: we will now look for frequent triples in the database, but we can already exclude all the triples that contain one of these two pairs:

Line 123 ⟶ 133:

We have thus determined the frequent sets of items in the database, and illustrated how some items were not counted because one of their subsets was already known to be below the threshold.

== Limitations ==

Line 132 ⟶ 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 ==