<jupyter_start><jupyter_text>Table of Contents1&nbsp;&nbsp;Task 12&nbsp;&nbsp;Task 22.1&nbsp;&nbsp;Task 2 a)2.2&nbsp;&nbsp;Task 2 b)2.3&nbsp;&nbsp;Task 2 c)3&nbsp;&nbsp;Task 33.1&nbsp;&nbsp;Task 3 a)3.2&nbsp;&nbsp;Task 3 b)3.3&nbsp;&nbsp;Task 3 c)3.4&nbsp;&nbsp;Task 3 d)4&nbsp;&nbsp;Task 44.1&nbsp;&nbsp;Task 4 a)4.2&nbsp;&nbsp;Task 4 b)5&nbsp;&nbsp;Task 55.1&nbsp;&nbsp;Task 5 a)5.2&nbsp;&nbsp;Task 5 b)<jupyter_code># setup autoload for imported python modules
%load_ext autoreload
%autoreload 2

# import modules form utils.py
from utils import *

# import libraries
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns

from sklearn.preprocessing import StandardScaler
from sklearn.preprocessing import MinMaxScaler

from sklearn.cluster import KMeans
from sklearn.cluster import SpectralClustering

from sklearn.neighbors import kneighbors_graph

from sklearn.metrics import silhouette_score
from sklearn.metrics import calinski_harabasz_score
from sklearn.metrics import davies_bouldin_score
from sklearn.metrics import normalized_mutual_info_score<jupyter_output>The autoreload extension is already loaded. To reload it, use:
  %reload_ext autoreload<jupyter_text>Task 1<jupyter_code># import spiral.txt dataset
# x1, x2: data features
# y: ground-truth labels

df = pd.read_csv('spiral.txt', sep="\t", header=None, names=["x1", "x2", "y"])
print("data shape: ", df.shape)
df.head()
# convert the dataframe to numpy array for calculations with libraries like scikit-learn
data = df[["x1","x2"]].values
print("data shape: ", data.shape)

data_array = df.to_numpy()

ground_truth_labels = df["y"].values
print("label shape: ", ground_truth_labels.shape)
# plot the dataset
scatter_x1 = df["x1"].values
scatter_x2 = df["x2"].values
group = df["y"].values
cdict = {1: 'red', 2: 'blue', 3: 'green'}

fig, ax = plt.subplots()
for g in np.unique(group):
    ix = np.where(group == g)
    ax.scatter(scatter_x1[ix], scatter_x2[ix], c = cdict[g], label = g, s = 10)
ax.legend()
plt.show()
# pre-processing
# - no imputation or pruning needed since no missing data

# standardization
scaler = StandardScaler() # standardization
data_scaled = scaler.fit_transform(data)
# k-means clustering

k = 3 # number of clusters

kmeans = KMeans(init="random", n_clusters=k, n_init=10, random_state=42)
kmeans.fit(data_scaled)
labels_kmeans = kmeans.labels_

# calculate evaluation indices
score_silhouette = silhouette_score(data_scaled, kmeans.labels_)
score_davies = davies_bouldin_score(data_scaled, kmeans.labels_)
score_nmi = normalized_mutual_info_score(ground_truth_labels, kmeans.labels_)

print("score_silhouette: ", score_silhouette)
print("score_davies: ", score_davies)
print("score_nmi: ", score_nmi)
# plot the dataset
print("k-means clustering")

scatter_x1 = data[:,0]
scatter_x2 = data[:,1]
group = labels_kmeans
cdict = {0: 'red', 1: 'blue', 2: 'green'}

fig, ax = plt.subplots()
for g in np.unique(group):
    ix = np.where(group == g)
    ax.scatter(scatter_x1[ix], scatter_x2[ix], c = cdict[g], label = g, s = 10)
ax.legend()
plt.show()
# spectral clustering
# - Gaussian RBF kernel
spectral_clustering = SpectralClustering(n_clusters=k, affinity='rbf', gamma=2, assign_labels="discretize", random_state=0)
spectral_clustering.fit(data)
labels_spectral = spectral_clustering.labels_

# calculate evaluation indices
score_silhouette = silhouette_score(data_scaled, labels_spectral)
score_davies = davies_bouldin_score(data_scaled, labels_spectral)
score_nmi = normalized_mutual_info_score(ground_truth_labels, labels_spectral)

print("score_silhouette: ", score_silhouette)
print("score_davies: ", score_davies)
print("score_nmi: ", score_nmi)
# plot the dataset
print("k-means clustering")

scatter_x1 = data[:,0]
scatter_x2 = data[:,1]
group = labels_spectral
cdict = {0: 'red', 1: 'blue', 2: 'green'}

fig, ax = plt.subplots()
for g in np.unique(group):
    ix = np.where(group == g)
    ax.scatter(scatter_x1[ix], scatter_x2[ix], c = cdict[g], label = g, s = 10)
ax.legend()
plt.show()<jupyter_output>k-means clustering<jupyter_text>Questions Try to figure out which Laplacian matrix is used:* The spectral clustering algorithm of the scikitlearn library uses projection of the normalized Laplacian matrix.Rank the algorithms in terms of their performance with respect to each of the indices and discuss the results:* Silhouette: The silhouette value is a measure of how similar an object is to its own cluster (cohesion) compared to other clusters (separation). The silhouette ranges from −1 to +1, where a high value indicates that the object is well matched to its own cluster and poorly matched to neighboring clusters. * <NAME>: Davies-Bouldin index is the ratio between the within cluster distances and the between cluster distances and computing the average overall the clusters. Ranging from 0 to 1, lower score is better.* Normalized Mutual Information (NMI) is a normalization of the Mutual Information (MI) score to scale the results between 0 (no mutual information) and 1 (perfect correlation).* Based on the printed scores we can see. That k-means has a better Silhouette and Davis-Boulding index score. However, Spectral clustering has a much better NMI score.Which one captures the performance of the algorithm more accurately?* Only by looking at the plots after the clustering it is obviously that Spectral clustering performs way better than k-means for the given data set. K-means works with a euclidean distance matrix and is therefore not able to cluster into that spiral shape. In the plot for the kmeans algorithm you can see that the data is divided into sectors. However, spectral clustering perfectly clusters the dataset which is also reflected in the NMI score of 1.* NMI captures the performance the given dataset much better. Since Spectral Clustering is able to perfectly cluster the dataset. But the scores for Silhouette and Davis are better for k-means. Therefore NMI is in this context better to measure the performance.  Task 2  Task 2 a)<jupyter_code># Calculate RBF kernel matrix
kernel_matrix = rbf_kernel(data)
kernel_matrix
# calculate the scores of tau
score_kmeans = validation_method(kernel_matrix, labels_kmeans)
print("Tau score_kmeans", score_kmeans)

score_spectral = validation_method(kernel_matrix, labels_spectral)
print("Tau score_spectral", score_spectral)<jupyter_output>Tau score_kmeans 0.930070628436259
Tau score_spectral 0.9994790295553357<jupyter_text>Questions compare the results with the ones indicated by Silhouette and <NAME>:* How I see it, it is more in alignment with the NMI score.* For kmeans it is approximately the half of spectral. The same case as with NMI.Discuss the results. Is this index a better choice in this case?* Yes it is a better choice than Silhouette and Davies. For the given datasets with the spirals Silhouette and Davies are not suitable scores which was shown in task 1. * If we only look at the order of the calculated tau scores we can see that spectral clustering has a better score than kmeans. This already shows that tau-score is better than Silhouette and Davies. So the order is more like in the case of NMI.* However, the scores are very close to each other. So we don't really know how much better spectral clustering is in comparison to kmeans for the given dataset. That's definitely one drawback.  Task 2 b) Questions Do you see any clear disadvantage in using τ? Hint: consider the definition of the Gaussian kernel.* One major disadvantage or constraint to the used performance measures from exercise 1 is that we need to set sigma manually. So we have one more tuning parameter.* Since we are using a kernel we lose some information. The kernel maps the data to a higher-dimensional space to be better separable. However, by this transformation we lose information by working with approximations. But this is also the case for other measurements that are working with approximations.  Task 2 c)<jupyter_code># nearest neighbor matrix
knn_matrix = kneighbors_graph(data, 2, mode='connectivity', include_self=True) # number of nearest neighbors 
knn_matrix = knn_matrix.toarray()
knn_matrix
tau_kmeans_knn = validation_method(knn_matrix, labels_kmeans)
print("tau_kmeans_knn", tau_kmeans_knn)

tau_spectral_knn = validation_method(knn_matrix, labels_spectral)
print("tau_kmeans_knn", tau_kmeans_knn)<jupyter_output>tau_kmeans_knn 0.9775641025641025
tau_kmeans_knn 0.9775641025641025<jupyter_text>Questions Propose an alternative validation index. Discuss the motivation, and possible disadvantages. * Based on the hint I was thinking of taking the k-nearest-neighbor graph as similarity matrix. That's intutitive because it is probably one of the simplest ways to measure similarity. The matrix consists of binary values 0 or 1. One advantage is that it is computationally easy. By using Euclidean distance it is easy to measure/calculate. Try it and discuss the results. * However, the results are not good. Even after tuning the parameter 'number of neighbors' the results don't get better. Both kmeans as well as spectral clustering have the same score. Therefore this similarity measure is not suitable in that context. It doesn't contain enough information.Hint: try to combine the idea of τ with other similarity matrices, such as the k-nearest-neighbour graph adjacency matrix, etc.  Task 3<jupyter_code># create pandas dataframe
data = {'num_rule': np.arange(1,13), 
        'fr(x)': [300, 500, 500, 342, 2, 500, 260, 120, 240, 80, 200, 251],
        'fr(xc)': [125, 150, 400, 240, 2, 352, 100, 32, 100, 32, 100, 203]
       }
df = pd.DataFrame(data=data)

n = 1000

# fr((not)x)
fr_not_x = 1000 - df['fr(x)'].values
df.insert(2, 'fr((not)x)', fr_not_x, True)

# P(x)
prob_x = df['fr(x)'].values / 1000
df['P(x)'] = prob_x

# P((not)x)
prob_not_x = df['fr((not)x)'].values / 1000
df['P((not)x)'] = prob_not_x

# P(xc)
prob_xc = df['fr(xc)'].values / 1000
df['P(xc)'] = prob_xc

# P(c)
prob_conseq = [0.3, 0.3, 0.7, 0.7, 0.7, 0.7, 0.3, 0.3, 0.3, 0.3, 0.3, 0.7]
df['P(c)'] = prob_conseq

# P((not)c)
prob_not_c = 1 - df['P(c)'].values
df['P((not)c)'] = prob_not_c

# leverage
leverage = df['P(xc)'].values - df['P(x)'].values * df['P(c)'].values
df['leverage'] = leverage

# lift
gamma = df['P(xc)'].values / ( df['P(x)'].values * df['P(c)'].values )
df['gamma'] = gamma



# Task b) 

# P(x(not)c)
prob_x_not_c = (df['fr(x)'].values - df['fr(xc)'].values) / 1000
df['P(x(not)c)'] = prob_x_not_c

# fr((not)xc)
fr_not_x_c = df['fr((not)x)'].values * df['P(c)'].values - n * df['leverage'].values
df['fr((not)xc)'] = fr_not_x_c

# P((not)xc)
prob_not_x_c = ( df['fr((not)xc)'].values ) / 1000
df['P((not)xc)'] = prob_not_x_c
 
# fr((not)x(not)c)
fr_not_x_not_c = df['fr((not)x)'].values - df['fr((not)xc)'].values
df['fr((not)x(not)c)'] = fr_not_x_not_c

# P((not)x(not)c)
prob_not_x_not_c = ( df['fr((not)x(not)c)'].values ) / 1000
df['P((not)x(not)c)'] = prob_not_x_not_c

# Calculate MI
mi = ( df['P(xc)']**df['P(xc)'] * df['P(x(not)c)']**df['P(x(not)c)'] * df['P((not)xc)']**df['P((not)xc)'] * df['P((not)x(not)c)']**df['P((not)x(not)c)'] ) / ( df['P(x)']**df['P(x)'] * df['P((not)x)']**df['P((not)x)'] * df['P(c)']**df['P(c)'] * df['P((not)c)']**df['P((not)c)'] )  #
mi = np.log2(mi)
df['MI'] = mi

# Calculate n*MI
df['n*MI'] = df['MI'].values * n

df<jupyter_output><empty_output><jupyter_text>Task 3 a)<jupyter_code># Prune out rules that do not express positive statistical dependence.
df = df[df['leverage'] > 0]
df = df[df['gamma'] > 1]
df<jupyter_output><empty_output><jupyter_text>Questions * Rules 2 and 8 get pruned out  Task 3 b)<jupyter_code># prune out rules where n · MI < 1.5 (i.e., MI < 0.0015).

df = df[df['n*MI'] >= 1.5]
df<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12017715697129716, 'fraction_numerical': 0.026999403798654287, 'mean_word_length': 5.526959421901056, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 30, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '311809', 'license': 'MIT', 'n_tokens_mistral': 4302, 'n_tokens_neox': 3919, 'n_words': 1313, 'path': 'Assignment2/submission/mdm_assignment2.ipynb', 'repo_name': 'breno-aberle/data-mining-course', 'size': '11758'}