Apriori algorithm¶

frequent sequences in 'market basket'

https://rasbt.github.io/mlxtend/user_guide/frequent_patterns/association_rules/

Movielense dataset¶

https://nhsjs.com/2025/apriori-algorithm-in-the-context-of-movie-recommendation-systems/#google_vignette

https://github.com/NeoMCHS/AprioriMovieResearch

https://www.kaggle.com/datasets/grouplens/movielens-20m-dataset

Rule generation is a common task in the mining of frequent patterns.¶

--  (Mystery, Drama) →	(Crime)

suggesting that people who watch (Mystery, Drama) are also likely watch (Crime). To evaluate the "interest" of such an association rule, different metrics have been developed.

-- The key metric is support.

-- The current implementation `mlxtend.frequent_patterns` make use of the confidence and lift metrics.
In [75]:
from mlxtend.frequent_patterns import apriori, association_rules

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import warnings
warnings.simplefilter("ignore")

Simple data¶

In [76]:
data = {'Milk': [1, 1, 0, 1], 'Bread': [1, 0, 1, 1], 'Butter': [0, 1, 1, 1]}
df = pd.DataFrame(data)
df.head()
Out[76]:
Milk Bread Butter
0 1 1 0
1 1 0 1
2 0 1 1
3 1 1 1

Itemsets (sets of products) with support >= min_support¶

-- support(itemset)=(# rows with itemset)/(# rows)

-- support(A→C)=support(A∪C)
In [77]:
frequent_itemsets = apriori(df, min_support=0.1, use_colnames=True)
print("Frequent Itemsets:\n", frequent_itemsets)

Frequent Itemsets:
    support               itemsets
0     0.75                 (Milk)
1     0.75                (Bread)
2     0.75               (Butter)
3     0.50          (Bread, Milk)
4     0.50         (Milk, Butter)
5     0.50        (Bread, Butter)
6     0.25  (Bread, Milk, Butter)

Rules from itemsets¶

split (partition) the itemset into the antecedent A and the succedent C

-- confidence(A→C)=support(A→C)/support(A)       # P(C|A) estimate

--lift(A→C)=confidence(A→C)/support(C)           # =1 if A and C are independent
In [78]:
rules = association_rules(frequent_itemsets, metric="confidence", min_threshold=0.6)
rules[['antecedents', 'consequents', 'support', 'confidence', 'lift']]
Out[78]:
antecedents consequents support confidence lift
0 (Bread) (Milk) 0.5 0.666667 0.888889
1 (Milk) (Bread) 0.5 0.666667 0.888889
2 (Milk) (Butter) 0.5 0.666667 0.888889
3 (Butter) (Milk) 0.5 0.666667 0.888889
4 (Bread) (Butter) 0.5 0.666667 0.888889
5 (Butter) (Bread) 0.5 0.666667 0.888889

nothing interesting; too few of data

In [79]:
# Step 2: Keep only maximal itemsets
def is_maximal(itemset, all_itemsets):
    return not any(
        (itemset < other)  # strict subset
        for other in all_itemsets
    )

all_sets = [set(x) for x in frequent_itemsets['itemsets']]
frequent_itemsets['is_maximal'] = [
    is_maximal(s, all_sets) for s in all_sets
]
maximal_itemsets = frequent_itemsets[frequent_itemsets['is_maximal']]

# Step 3: Generate rules only from maximal itemsets
#rules = association_rules(maximal_itemsets, metric="confidence", min_threshold=0.6)

print(maximal_itemsets)
#print(rules)

   support               itemsets  is_maximal
6     0.25  (Bread, Milk, Butter)        True
In [80]:
import efficient_apriori as effapi 

transactions = [('eggs', 'bacon', 'soup'),
                ('eggs', 'bacon', 'apple'),
                ('soup', 'bacon', 'banana')]
itemsets, rules = effapi.apriori(transactions, min_support=0.5, min_confidence=1)
print(rules)  # [{eggs} -> {bacon}, {soup} -> {bacon}]

# Print out every rule with 2 items on the left hand side,
# 1 item on the right hand side, sorted by lift
rules_rhs = filter(lambda rule: len(rule.lhs) == 2 and len(rule.rhs) == 1, rules)
for rule in sorted(rules_rhs, key=lambda rule: rule.lift):
  print(rule)  # Prints the rule and its confidence, support, lift, ...

  print(itemsets)
# {1: {('bacon',): ItemsetCount(itemset_count=3, members={0, 1, 2}), ...

[{eggs} -> {bacon}, {soup} -> {bacon}]

Movie dataset with PLOT¶

https://www.davidsbatista.net/blog/2017/04/01/document_classification/¶

(Predicts GENRE from the PLOT)

In [81]:
movies = pd.read_csv("data/movies_genres_en.csv", delimiter='\t')#;movies.info()
genre_columns=movies.columns[2:29]
frequent_itemsets = apriori(movies[genre_columns], min_support=0.005, use_colnames=True)
frequent_itemsets.head()
Out[81]:
support itemsets
0 0.105594 (Action)
1 0.087402 (Adventure)
2 0.097010 (Animation)
3 0.011818 (Biography)
4 0.289008 (Comedy)

Itemsets sorted by support¶

In [82]:
frequent_itemsets.sort_values(by='support', ascending=False).head(10)
Out[82]:
support itemsets
7 0.391581 (Drama)
4 0.289008 (Comedy)
18 0.163609 (Romance)
8 0.131440 (Family)
81 0.130775 (Drama, Romance)
5 0.129025 (Crime)
0 0.105594 (Action)
17 0.105261 (Reality-TV)
15 0.102616 (Mystery)
6 0.102565 (Documentary)
In [83]:
frequent_itemsets[frequent_itemsets['itemsets']==frozenset({'Drama'})]
Out[83]:
support itemsets
7 0.391581 (Drama)

Rules from itemsets¶

In [84]:
r_cols=['antecedents', 'consequents', 'support', 'confidence', 'lift']
rules = association_rules(frequent_itemsets, metric="confidence", min_threshold=0.6)
rules["antecedent_len"] = rules["antecedents"].apply(lambda x: len(x))
rules[r_cols].head()
Out[84]:
antecedents consequents support confidence lift
0 (Crime) (Drama) 0.099101 0.768071 1.961459
1 (Mystery) (Crime) 0.069091 0.673291 5.218285
2 (Mystery) (Drama) 0.082240 0.801430 2.046650
3 (Romance) (Drama) 0.130775 0.799312 2.041239
4 (Thriller) (Drama) 0.058629 0.776209 1.982241

Select and order rules according your criteria¶

In [85]:
rules[ (rules['support'] > 0.02) &
       (rules['confidence'] > 0.75) &
       (rules['lift'] > 1.2) ][r_cols].sort_values(by='support', ascending=False)
Out[85]:
antecedents consequents support confidence lift
3 (Romance) (Drama) 0.130775 0.799312 2.041239
0 (Crime) (Drama) 0.099101 0.768071 1.961459
2 (Mystery) (Drama) 0.082240 0.801430 2.046650
36 (Mystery, Drama) (Crime) 0.062085 0.754928 5.851007
37 (Mystery, Crime) (Drama) 0.062085 0.898604 2.294808
4 (Thriller) (Drama) 0.058629 0.776209 1.982241
54 (Mystery, Thriller) (Drama) 0.040975 0.892731 2.279809
42 (Thriller, Crime) (Drama) 0.038159 0.893150 2.280878
45 (Thriller, Crime) (Mystery) 0.032621 0.763531 7.440650
118 (Mystery, Crime, Thriller) (Drama) 0.030300 0.928852 2.372052
119 (Thriller, Drama, Crime) (Mystery) 0.030300 0.794052 7.738077
21 (Action, Crime) (Drama) 0.024011 0.761776 1.945383

Text Preprocessing¶

Preprocessing

tokenizing - split words by spaces (rozdělení na slova mezerami apod.)
counting - count word occurences (počty slov v dokumentu)
stop-word removal - words without meaning, too frequent or too rare (příliš časté, moc málo výskytů)
normalizing - divide by the number of words in the document (vydělení počtem slov v dokumentu)

all in sparce matrices

https://scikit-learn.org/stable/modules/feature_extraction.html#text-feature-extraction

In [86]:
from sklearn.feature_extraction.text import TfidfVectorizer, CountVectorizer
from sklearn.decomposition import NMF, LatentDirichletAllocation

Download the English stopwords¶

In [87]:
import nltk
from nltk.corpus import stopwords
nltk.download('stopwords')
stop_words = ["qv","de","eric",'luc',"film",'tom','nick','sam','jon','bob','bill','000','10']+stopwords.words('english')
stopwords.words('english')[:10]

[nltk_data] Downloading package stopwords to
[nltk_data]     C:\Users\Marta\AppData\Roaming\nltk_data...
[nltk_data]   Package stopwords is already up-to-date!
Out[87]:
['a', 'about', 'above', 'after', 'again', 'against', 'ain', 'all', 'am', 'an']

TF vectorization¶

In [88]:
n_features = 1000  #TF vectorization

## remove frequent and rare words, stop_words, select max_features
tf_vectorizer = CountVectorizer(max_df=0.95, min_df=2,
                                max_features=n_features,
                                stop_words=stop_words)

## apply the tf_vectorized
tf = tf_vectorizer.fit_transform(movies['plot'])
tf_feature_names = tf_vectorizer.get_feature_names_out()

tf_feature_names[:10]
Out[88]:
array(['able', 'accept', 'accepts', 'accident', 'accidentally', 'across',
       'act', 'action', 'actor', 'actually'], dtype=object)
In [89]:
## Convert the sparse matrix tf to a list of tuples of feature names for each document
## input for efficient_apriori, not part of the presentation since it does not support lift metric

def get_row(row, tf_feature_names):
    return (tuple([tf_feature_names[x] for x in range(len(tf_feature_names)) if row[x]>0 ]))
rows = [get_row(row.toarray().ravel(), tf_feature_names) for row in tf]
itemsets, rules = effapi.apriori(rows, min_support=0.01, min_confidence=0.4)
print(rules) 

[{ago} -> {years}, {york} -> {new}, {year} -> {old}]

The word 'love' in plots¶

In [90]:
print('(movies.title, find("love"))')
feature_idx=np.where(tf_feature_names=='love')[0][0]
[(movies['title'].iloc[i],tf[i,feature_idx]) for i in range(10) if tf[i,feature_idx]>0]

(movies.title, find("love"))
Out[90]:
[('"#BlackLove" (2015) {Crash the Party (#1.9)}', np.int64(1)),
 ('"#BlackLove" (2015) {Sealing the Deal (#1.10)}', np.int64(1)),
 ('"#Hashtag: The Series" (2013)', np.int64(1))]

Latent Dirichlet Allocation (LDA)¶

In [91]:
n_components = 15  #LDA

## apply the LDA with specific n_components
lda = LatentDirichletAllocation(n_components=n_components, max_iter=5,
                                learning_method='online',
                                learning_offset=50.,
                                random_state=0)
topic_frequencies=lda.fit_transform(tf)

lda.components_.shape
Out[91]:
(15, 1000)

Ploting the results¶

In [92]:
# Author: Olivier Grisel <olivier.grisel@ensta.org>
#         Lars Buitinck
#         Chyi-Kwei Yau <chyikwei.yau@gmail.com>
# License: BSD 3 clause

n_top_words = 20 #for plot
n_rows= int(np.ceil(n_components/5))
def plot_top_words(model, feature_names, n_top_words, title):
    fig, axes = plt.subplots(n_rows, 5, figsize=(40, 25), sharex=True)
    axes = axes.flatten()
    for topic_idx, topic in enumerate(model.components_):
        top_features_ind = topic.argsort()[:-n_top_words - 1:-1]
        top_features = [feature_names[i] for i in top_features_ind]
        weights = topic[top_features_ind]

        ax = axes[topic_idx]
        ax.barh(top_features, weights, height=0.7)
        ax.set_title(f'Topic {topic_idx +1}',
                     fontdict={'fontsize': 30})
        ax.invert_yaxis()
        ax.tick_params(axis='both', which='major', labelsize=20)
        for i in 'top right left'.split():
            ax.spines[i].set_visible(False)
        fig.suptitle(title, fontsize=40)

    plt.subplots_adjust(top=0.90, bottom=0.05, wspace=0.90, hspace=0.3)
#    plt.show()
In [93]:
plot_top_words(lda, tf_feature_names, n_top_words, 'Topics in LDA model')
No description has been provided for this image

For each component, select the top word¶

In [94]:
component_first_words=[tf_feature_names[lda.components_[i].argmax()] for i in range(n_components)]
print(component_first_words)

['hospital', 'news', 'one', 'mike', 'david', 'night', 'find', 'son', 'life', 'show', 'mr', 'tells', 'money', 'man', 'new']

Preprocessing tf-idf¶

term-frequency times inverse document-frequency¶

$idf(t)=log \frac{n}{1+df(t)}$
($idf(t)=log \frac{1+n}{1+df(t)}+1$) smooth=True
normalizace Euclidean (L2) norm /sqrt(\sum(x_i^2))

https://scikit-learn.org/stable/modules/feature_extraction.html#text-feature-extraction

In [95]:
from time import time
# Use tf-idf features for NMF.
print("Extracting tf-idf features for NMF...")
tfidf_vectorizer = TfidfVectorizer(max_df=0.95, min_df=2,
                                   max_features=n_features,
                                   stop_words='english')
t0 = time()
tfidf = tfidf_vectorizer.fit_transform(movies['plot'])
print("done in %0.3fs." % (time() - t0))
tfidf_feature_names = tfidf_vectorizer.get_feature_names_out()

Extracting tf-idf features for NMF...
done in 32.477s.

Non-Negative Matrix Factorization (NMF)¶

ind two non-negative matrices (W, H) whose product approximates the non- negative matrix X. https://scikit-learn.org/stable/modules/generated/sklearn.decomposition.NMF.html?highlight=nmf#sklearn.decomposition.NMF

In [96]:
# Fit the NMF-Frobenius model
print("Fitting the NMF model (Frobenius norm) with tf-idf features, "
      "n_samples=%d and n_features=%d..."
      % (len(movies['plot']), n_features))
t0 = time()
nmf = NMF(n_components=n_components, random_state=1,init='nndsvda',
          #alpha=.1, 
          l1_ratio=.5).fit(tfidf)
print("done in %0.3fs." % (time() - t0))

Fitting the NMF model (Frobenius norm) with tf-idf features, n_samples=117194 and n_features=1000...
done in 63.431s.
In [97]:
plot_top_words(nmf, tfidf_feature_names, n_top_words,
               'Topics in NMF model (Frobenius norm)')
No description has been provided for this image
In [98]:
# Fit the NMF-KL model
print('\n' * 2, "Fitting the NMF model (generalized Kullback-Leibler "
      "divergence) with tf-idf features, n_samples=%d and n_features=%d..."
      % (len(movies['plot']), n_features))
t0 = time()
nmf = NMF(n_components=n_components, random_state=1,init='nndsvda',
          beta_loss='kullback-leibler', solver='mu', max_iter=1000, #alpha=.1,
          l1_ratio=.5).fit(tfidf)
print("done in %0.3fs." % (time() - t0))

tfidf_feature_names = tfidf_vectorizer.get_feature_names_out()
plot_top_words(nmf, tfidf_feature_names, n_top_words,
               'Topics in NMF model (generalized Kullback-Leibler divergence)')


 Fitting the NMF model (generalized Kullback-Leibler divergence) with tf-idf features, n_samples=117194 and n_features=1000...
done in 277.222s.
No description has been provided for this image