<jupyter_start><jupyter_text>***1/ Initialisation data reduced*** ***We will use for our clustering the Shi & Malik method with multiple eigenvectors. Recurrent bi-partitioning being inefficient insofar as it is difficult to obtain a very separated graph between the two smallest eigenvectors. This is due to the fact that we have noisy datas.***To avoid problems launch with colab   ***Create a 2D small dataset***<jupyter_code># data analysis and wrangling
import pandas as pd
import numpy as np
import random as rnd
import networkx as nx
import scipy as sy
import sklearn as sk
# visualization
import seaborn as sns
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
%matplotlib inline
 
# machine learning
from sklearn.linear_model import LogisticRegression
from sklearn.svm import SVC, LinearSVC
from sklearn.ensemble import RandomForestClassifier
from sklearn.neighbors import KNeighborsClassifier
from sklearn.naive_bayes import GaussianNB
from sklearn.linear_model import Perceptron
from sklearn.linear_model import SGDClassifier
from sklearn.tree import DecisionTreeClassifier
from scipy.sparse.linalg import eigsh
from sklearn.neighbors import NearestNeighbors
#K-means
from sklearn.cluster import KMeans
from mpl_toolkits.mplot3d import Axes3D
!wget -O dataset.csv https://www.openml.org/data/get_csv/49817/wine_quality.arff<jupyter_output>--2020-11-30 11:58:46--  https://www.openml.org/data/get_csv/49817/wine_quality.arff
Resolving www.openml.org (www.openml.org)... 192.168.127.12
Connecting to www.openml.org (www.openml.org)|192.168.127.12|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: unspecified [text/plain]
Saving to: ‘dataset.csv’

dataset.csv             [  <=>               ] 340.28K   894KB/s    in 0.4s    

2020-11-30 11:58:48 (894 KB/s) - ‘dataset.csv’ saved [348451]<jupyter_text>***1) This example is there, to make clustering more visual. We have therefore chosen two features for a 2D representation.We made a clustering with all features on an other notebook.***<jupyter_code>datas = pd.read_csv('dataset.csv')
datas_reduced = datas[0:200]
datas_reduced<jupyter_output><empty_output><jupyter_text>***2) We chose the first two colomnes***<jupyter_code>np_datas = datas_reduced.to_numpy()
np_datas_2D = np_datas[:,0:2]
plt.scatter(np_datas_2D[:,0],np_datas_2D[:,1])<jupyter_output><empty_output><jupyter_text>***Doing the first matrice with euclidian distances***  ***function for euclidian*** ***1) We do the adjacency matrix with the euclidian norm***<jupyter_code>def euclidian_distance(line1,line2):
  #here we do the squared of the difference between two lines
  line = (line1-line2)*np.transpose((line1-line2))
  #We do the sum on the line to obtain the euclidian norm
  nombre = sum(line)
  return np.sqrt(nombre);
#  print(np_datas_2D)<jupyter_output><empty_output><jupyter_text>***adjacency matrix*** ***The following code is there to create the adjacency matrix.We start by making a full square matrix of 0 with the dimension of the dataset.*** ***After that we browse along the matrix to calculate the euclidian norm. we use a double "for" loop. We calculate the distance for the upper part of the matrix because it is symmetrical. And we just copy past the transpose to have the all matrix.***<jupyter_code>A = np.zeros((len(np_datas_2D),len(np_datas_2D)))
for i in range(len(np_datas_2D)):
  for j in range(len(np_datas_2D)):
    if j > i :
      A[i][j]=euclidian_distance(np_datas_2D[i],np_datas_2D[j])
A = A + np.transpose(A)
print(A)      
A.mean()<jupyter_output>[[0.         0.43863424 0.40447497 ... 4.11946598 2.00455107 0.63411355]
 [0.43863424 0.         0.12       ... 3.74518357 2.40042184 0.92417531]
 [0.40447497 0.12       0.         ... 3.72848495 2.40117159 0.95859272]
 ...
 [4.11946598 3.74518357 3.72848495 ... 0.         6.12341612 4.667344  ]
 [2.00455107 2.40042184 2.40117159 ... 6.12341612 0.         1.52152062]
 [0.63411355 0.92417531 0.95859272 ... 4.667344   1.52152062 0.        ]]<jupyter_text>***Epsilon graph***  ***function for the weights*** ***We transform the contiguity matrix to have an epsilon graph. We thus build here our matrix W (named A because we re-use the matrix of contiguity). For sigma, we chose 0.1 because we want to have a distinct demarcation between the points. A small sigma means that the values will be more spaced out on the epsilon graph. To find our epsilon we did several tests to see what gave a nice clustering. This is a delicate step because it greatly influences the number of clusters and the quality of the clustering. We chose it arbitrarily because we had no real method in the course to determine it. We have therefore taken the average of the values of the adjacency matrix divided by 3.***<jupyter_code>#sigma defines the gap between the points on the graph (scale)
sigma = 0.1
meanA = A.mean()
epsilon = meanA/3
for i in range(len(np_datas_2D)):
  for j in range(len(np_datas_2D)):
    if A[i][j] < (epsilon):
      n = A[i][j]
      A[i][j] = np.exp(-n**2/(2*sigma))
    else : 
      A[i][j] = 0 
print(A)<jupyter_output>[[1.        0.        0.        ... 0.        0.        0.       ]
 [0.        1.        0.9305309 ... 0.        0.        0.       ]
 [0.        0.9305309 1.        ... 0.        0.        0.       ]
 ...
 [0.        0.        0.        ... 1.        0.        0.       ]
 [0.        0.        0.        ... 0.        1.        0.       ]
 [0.        0.        0.        ... 0.        0.        1.       ]]<jupyter_text>***Graph*** ***We have drawn the epsilon graph. We can already see groups of points appear which can help us to select the number k of clusters. We can deduce that our epsilon is a little bit too small because our graph is already partially cut.Indeed the next step is to carry out an "egeingap" to know the number of cluster. We can check if what we find is consistent with respect to the epsilon graph.***<jupyter_code>G = nx.from_numpy_matrix(A)
nx.draw(G,with_labels=True,
        font_weight='bold',
       )
G.edges(data=True)<jupyter_output><empty_output><jupyter_text>***2/ Calculs on laplacian***  ***Calcul of the normalized laplacian method from networkx*** ***We compute here the normalized laplacian. We use networkx library. We have to work with networkx graph format and not numpy array. It is possible to code the normalized laplacian with numpy but this is not optimized.***> the code is :`Ls = np.dot(np.dot(np.sqrt(np.linalg.inv(D)),L),np.sqrt(np.linalg.inv(D)))`***Is it possible to use others normalisation for exemple the Random walk normalized Laplacian : Lnorm = D^-1.L***<jupyter_code>Ls_nx = nx.normalized_laplacian_matrix(G)
G2 = nx.Graph(Ls_nx)
Ls = nx.to_numpy_array(G2)<jupyter_output><empty_output><jupyter_text>**Calcul of eigenvalues and vectors** ***Here we want to determine the number of cluster k. The most stable clustering is generally given by the value k which represent the last "small" eigenvalue***<jupyter_code>l, V = np.linalg.eig(Ls)
ind = np.argsort(l)
l = l[ind]
V = V[:,ind]
plt.plot(l[0:20],'b.')<jupyter_output><empty_output><jupyter_text>***number of cluster selection*** ***Thanks to the graph we can see that k is 8. Now we select the first 8 eigenvectors. An eigenvector associated with an eigenvalue equal to 0 in fact represents a cluster. The 8 vectors are therefore linearly independent. If a point is not connected to the cluster, its value in the eigenvector will be 0.By selecting the first 8 eigenvectors we therefore have information on the content of each clusters.***<jupyter_code>nb_cluster = 8
V_nb_clusters = V[:,0:nb_cluster-1]
V_nb_clusters<jupyter_output><empty_output><jupyter_text>***3/ K-mean***  ***Training*** ***Now we will do K_mean clustering on our eigenvectors data set.***> ‘k-means++’ : selects initial cluster centers for k-mean clustering in a smart way to speed up convergence.<jupyter_code>kmeans = KMeans(init = "k-means++",n_clusters=nb_cluster)
knn_clusters = kmeans.fit_predict(np.real(V_nb_clusters))
labels = kmeans.labels_
labels<jupyter_output><empty_output><jupyter_text>***We link each label to its ID in the starting dataset.***<jupyter_code>datas_reduced["k_means"] = labels
datas_reduced.head()<jupyter_output>/usr/local/lib/python3.6/dist-packages/ipykernel_launcher.py:1: SettingWithCopyWarning: 
A value is trying to be set on a copy of a slice from a DataFrame.
Try using .loc[row_indexer,col_indexer] = value instead

See the caveats in the documentation: https://pandas.pydata.org/pandas-docs/stable/user_guide/indexing.html#returning-a-view-versus-a-copy
  """Entry point for launching an IPython kernel.<jupyter_text>***We can see clusters averages values. This doesn't really give us any information in a spectral clustering, because the clusters are in the shape of a circle.***<jupyter_code>a = datas_reduced.groupby("k_means").mean()
print(a)
fig, ax = plt.subplots()

scatter = ax.scatter(np_datas_2D[:,0], np_datas_2D[:,1], c = labels.astype(np.float),alpha = 0.5)

# produce a legend with the unique colors from the scatter
legend1 = ax.legend(*scatter.legend_elements(),
                    loc="best", title="Cluster")
ax.add_artist(legend1)
plt.show()<jupyter_output><empty_output><jupyter_text>***4/ Silhouette analisys*** ***We are now going to do a silhouette analysis on our k_mean. Silhouette coefficient is the difference between the average distance with the points of the same group as it and the average distance with the points of the other neighboring groups. It is not really relevant in our case because our clusters have ring shapes. Which means that the coefficient will be bad for the clusters outside the center.***<jupyter_code>score = sk.metrics.silhouette_score(np.real(V_nb_clusters), kmeans.labels_, metric='euclidean')
print('Silhouetter Score: %.3f' % score)
score = sk.metrics.silhouette_score(np_datas_2D, kmeans.labels_, metric='euclidean')
print('Silhouetter Score: %.3f' % score)
sample_silhouette_values = sk.metrics.silhouette_samples(np_datas_2D, kmeans.labels_, metric='euclidean')
print(sample_silhouette_values)
for i in range(len(sample_silhouette_values)):
  if sample_silhouette_values[i] < 0:
    labels[i] = 0
labels
fig, ax = plt.subplots()

scatter = ax.scatter(np_datas_2D[:,0], np_datas_2D[:,1], c = labels.astype(np.float),alpha = 0.5)

# produce a legend with the unique colors from the scatter
legend1 = ax.legend(*scatter.legend_elements(),
                    loc="best", title="Cluster")
ax.add_artist(legend1)
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10726150925486473, 'fraction_numerical': 0.045942097769340294, 'mean_word_length': 4.1096023278370515, 'pattern_counts': {'":': 0, '<': 56, '<?xml version=': 0, '>': 57, 'https://': 3, 'lorem ipsum': 0, 'www.': 6, 'xml': 0}, 'pii_count': 2, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '14', 'dir': 'jupyter-structured-clean-dedup', 'id': '269061', 'license': 'CC0-1.0', 'n_tokens_mistral': 3813, 'n_tokens_neox': 3393, 'n_words': 1144, 'path': 'V3_spectral_clustering2.ipynb', 'repo_name': 'MariiaS/moml', 'size': '10533'}