<jupyter_start><jupyter_text>Deep Clustering - Part 2: DEC with Simple AutoencoderRecap from part 1:Clustering refers to dividing data points into groups such that members of the same group are more similar to each other compared to those in other groups. Traditional methods of clustering typically use similarity measures to compare data points and assign them to clusters. Deep clustering refers to using deep neural networks to map a high dimentional data to a new lower-dimentinal *hidden space*. The aim is to improve the accuracy of clustering by increasing the inter-cluster dissimilarity as well as instra-cluster similarity in the hidden space. In addition, the neural network is used to generate abstract and useful features such that the effect of the curse of dimentionality on the similarity measure, which is used for clustering, is minimised. The final clustering is performed in the hidden space and the clustering loss in backpropagated through the network to tune the neural network weights and consequently the data representation in the hidden space.The quality of final clustering in deep clustering highly depends on the initialisation of the clusters in the hidden space. The typcal way of performing this step is to train an autoencoder and use the encoder part of it to initialise the data mapping to the hidden space. This is shown in Figure 1.Figure 1. General steps in deep clustering. (Step 1) Training an autoencoder to initialise the data embedding in the hidden space. (Step 2) Fine tuning the network weights and the data embedding using a clustering based loss function. The aim is to increase the inter-cluster dissimilarity and intra-cluster similarities.In part 1 of this series, the quality of the clusters initialisation was investigated using simple and convolutional autoencoder. In this part, a choice of loss function for fine-tuning the data representation created by the autoencoder is explained. [DEC algorithm](https://arxiv.org/pdf/1511.06335.pdf) defines a soft cluster membership and an auxiliary target distribution on the cluster memberships, and optimises the encoder network by matching the former to the latter.Assuming $H = \{h_i\}_{i = 1..n}$ as the data representation in the feature space initialised by an encoder, the soft cluster membership is defined as:$q_{ij} = \frac{(1 + \|h_i - c_j\|^2/\alpha)^{-\frac{\alpha+1}{2}}}{\sum_{j'}(1 + \|h_i - c_{j'}\|^2/\alpha)^{-\frac{\alpha+1}{2}}},$where $c_j$ denotes the $j$th cluster center in $C=\{c_1..c_k\}$, and $k$ is the number of clusters.The auxiliary target distribution on the cluster memberships is defined as:$p_{ij} =\frac{q_{ij}^2/f_j}{\sum_{j'}q_{ij'}^2/f_j'},$where $f_j=\sum_{i}q_{ij}$. Using these distributions, the clustering-based loss function that minimises the difference of the $P$ and $Q$ matrices can be defined using Kullback-liber divergence: $J = KL(P\|Q) = \sum_i\sum_j p_{ij}\log\frac{p_{ij}}{q_{ij}}.$Let's use the DEC algorithms with a simple autoencoder to see how it improves the quality of the clusters initialised in the new feature space learnt by the autoencoder. The Google Colaboratory environment and the [DEC implementation](https://github.com/XifengGuo/DEC-keras/tree/6790d9e9a1aef629393cb7998b6087737fc78966) are used for this demo. We first clone the related files into the Google Colab environment and navigate to this directory.<jupyter_code>!git clone https://github.com/XifengGuo/DEC-keras.git
%cd DEC-keras/
# Importing the required libraries and packages
import numpy as np
import os
import matplotlib.pyplot as plt
from keras.initializers import VarianceScaling<jupyter_output><empty_output><jupyter_text>Data PreprocessingThe MNIST dataset is used for this demo. Similar to part 1 of these series, the data is scaled in the range $[0,1]$, then deskewd and normalise in the same range.<jupyter_code># The data preprocessing step for the image data using deskewing technique
from scipy.ndimage import interpolation
def moments(image):
    c0,c1 = np.mgrid[:image.shape[0],:image.shape[1]] # A trick in numPy to create a mesh grid
    totalImage = np.sum(image) #sum of pixels
    m0 = np.sum(c0*image)/totalImage #mu_x
    m1 = np.sum(c1*image)/totalImage #mu_y
    m00 = np.sum((c0-m0)**2*image)/totalImage #var(x)
    m11 = np.sum((c1-m1)**2*image)/totalImage #var(y)
    m01 = np.sum((c0-m0)*(c1-m1)*image)/totalImage #covariance(x,y)
    mu_vector = np.array([m0,m1]) # Notice that these are \mu_x, \mu_y respectively
    covariance_matrix = np.array([[m00,m01],[m01,m11]]) # Do you see a similarity between the covariance matrix
    return mu_vector, covariance_matrix

def deskew(image):
    c,v = moments(image)
    alpha = v[0,1]/v[0,0]
    affine = np.array([[1,0],[alpha,1]])
    ocenter = np.array(image.shape)/2.0
    offset = c-np.dot(affine,ocenter)
    return interpolation.affine_transform(image,affine,offset=offset)<jupyter_output><empty_output><jupyter_text>Let's load and prepare the data for analysis. Here, the load_data utility from DEC is used to load the data. This utility scales data in the range $[0,1]$ by devision to 255. Thus, the data should be skewed and normalised.<jupyter_code>from datasets import load_data
dataset = 'mnist'
# load dataset
x, y = load_data(dataset)
# Deskewing MNIST data
for i in range(len(x)):
  x[i] = deskew(x[i].reshape(28,28)).reshape((1,-1))

# Normalising the data in the range [0,1] using the MinMax scaler method:
# per feature vector v: v = (v-min(v))/(max(v)-min(v))
from sklearn.preprocessing import MinMaxScaler
scaler = MinMaxScaler()
scaler.fit(x)
x = scaler.transform(x)<jupyter_output><empty_output><jupyter_text>DEC with Simple Autoencoder For the autoencoder, the same setting as part 1 is used. Adam optimiser is used to minimise the autoencoder loss in $200$ epochs. If a pre-trained autoencoder is used, it can be reloaded by providing its storage location using the variable ae_weights.<jupyter_code># Setting parameters
n_clusters = len(np.unique(y))
batch_size = 256
maxiter = 2e4
tol = 0.001
# Change the following to the file name if using a pre-trained model 
ae_weights = None # Set if exists, e.g., "results/ae_weights.h5"
save_dir = 'results'
update_interval = 140 # Interval to print the DEC loss
pretrain_epochs = 200
init = VarianceScaling(scale=1. / 3., mode='fan_in',
                       distribution='uniform') #kernel-initialiser
pretrain_optimizer = 'adam' # Optimiser for pretraining
if not os.path.exists(save_dir):
    os.makedirs(save_dir)<jupyter_output><empty_output><jupyter_text>The clusters are initialised by means of an encoder, which is trained in an unsupervised manner using an autoencoder. The structure of the encoder is defined based on the related literature.<jupyter_code># prepare the DEC model
from DEC import *
dec = DEC(dims=[x.shape[-1], 500, 500, 2000, 10], n_clusters=n_clusters, init=init)

if ae_weights is None:
    dec.pretrain(x=x, y=y, optimizer=pretrain_optimizer,
                  epochs=pretrain_epochs, batch_size=batch_size,
                  save_dir=save_dir)
else:
    dec.autoencoder.load_weights(ae_weights)

dec.model.summary()<jupyter_output>...Pretraining...
Epoch 1/200
70000/70000 [==============================] - 3s 39us/step - loss: 0.0330
        |==>  acc: 0.3913,  nmi: 0.3496  <==|
Epoch 2/200
 4352/70000 [>.............................] - ETA: 2s - loss: 0.0225<jupyter_text>The SGD optimiser with a learning rate of $0.1$ and momentum of $0.9$ is used to minimise the clustering-based loss function of DEC. The final model as well as some intermediary models are saved in the directory provided in the save_dir variable along with other results.<jupyter_code>from keras.optimizers import SGD
dec.compile(optimizer=SGD(lr=0.1,momentum=0.9), loss='kld')
y_pred = dec.fit(x, y=y, tol=tol, maxiter=maxiter, batch_size=batch_size,
                  update_interval=update_interval, save_dir=save_dir)<jupyter_output>WARNING:tensorflow:From /usr/local/lib/python3.6/dist-packages/keras/backend/tensorflow_backend.py:1702: The name tf.log is deprecated. Please use tf.math.log instead.

Update interval 140
Save interval 1365
Initializing cluster centers with k-means.
Iter 0: acc = 0.91387, nmi = 0.82485, ari = 0.81639  ; loss= 0
WARNING:tensorflow:From /usr/local/lib/python3.6/dist-packages/tensorflow_core/python/ops/math_grad.py:1424: where (from tensorflow.python.ops.array_ops) is deprecated and will be removed in a future version.
Instructions for updating:
Use tf.where in 2.0, which has the same broadcast rule as np.where<jupyter_text>To extract the features in the new feature space, the encoders for the DEC algorithm and the autoencoder should be defined.<jupyter_code># Extract the encoder part of the DEC model
dec_encoder = Model(dec.model.input, dec.model.get_layer(index=-2).output)

# Reload the Autoencoder
from keras.models import clone_model
ae = clone_model(dec.autoencoder)
ae.load_weights("results/ae_weights.h5")
# Extract the encoder part of the autoencoder model
ae_encoder = Model(ae.input, ae.get_layer(index=int(len(ae.layers)/2)).output)<jupyter_output><empty_output><jupyter_text>Now, let's map the data once using the encoder trained by the DEC algorithm as well as the autoencoder.<jupyter_code># Embed the data using the DEC encoder
dec_mapped_data = dec_encoder.predict(x)
# Embed the data using the encoder trained by the autoencoder
ae_mapped_data = ae_encoder.predict(x)<jupyter_output><empty_output><jupyter_text>The custer centers in the DEC model are the weights of the clustering layer, which is the last layer in the model. For the autoencoder, the cluster centers and memberships are computed using k-means. Then the clustering accuracy of the two methods are compared to evaluate the quality of the clusters.<jupyter_code>from sklearn.cluster import KMeans
# Extract the cluster centers in the DEC model
dec_cluster_centers = dec.model.get_layer(index=-1).get_weights()
dec_cluster_centers = np.array(dec_cluster_centers).reshape(10,10)
# dec_idx stores the cluster membership of the data using DEC
dec_idx = y_pred
# K-means with 10 clusters
ae_km = KMeans(n_clusters=10)
ae_km.fit(ae_mapped_data)
# ae_idx stores the cluster membership of the data using autoencoder
ae_idx = ae_km.predict(ae_mapped_data)
# Matching the labels of the identified clusters
from scipy.stats import mode
dec_labels = np.zeros_like(dec_idx)
ae_labels = np.zeros_like(ae_idx)
for i in range(10):
  mask = (dec_idx == i)
  dec_labels[mask] = mode(y[mask])[0]
  mask = (ae_idx == i)
  ae_labels[mask] = mode(y[mask])[0]<jupyter_output><empty_output><jupyter_text>The accuracy and purity of clustering, associated with the accuracy and NMI measures, are considerably increased after fine-tuning the encoder network using the DEC algorithm:<jupyter_code>from tabulate import tabulate
print(tabulate([['Autoencoder', np.round(metrics.acc(y, ae_labels),3),np.round(metrics.nmi(y, ae_labels),3)], 
              ['DEC', np.round(metrics.acc(y, dec_labels),3),np.round(metrics.acc(y, dec_labels),3)]], 
              headers=['Method', 'Accuracy', 'NMI']))<jupyter_output>Method         Accuracy    NMI
-----------  ----------  -----
Autoencoder       0.914  0.825
DEC               0.949  0.949<jupyter_text>Let's visualise the clusters in both methods and compare them with the ground truth labels. tSNE is used for this purpose and a random subset of $1000$ samples are selected to show the visualisation.<jupyter_code>from sklearn.manifold import TSNE
# Choosing a sample of the data at random
ix = np.random.permutation(range(len(y)))
ix = ix[:1000]

# Creating a dataset that includes the samples and the cluster centers 
data = np.append(dec_cluster_centers,dec_mapped_data[ix],axis=0)
# Applying tSNE to project the data to a 2D data representation
tsne = TSNE(n_components=2)
dec_z = tsne.fit_transform(data)

# Creating a dataset that includes the samples and the cluster centers 
data = np.append(ae_km.cluster_centers_,ae_mapped_data[ix],axis=0)
# Applying tSNE to project the data to a 2D data representation
tsne = TSNE(n_components=2)
ae_z = tsne.fit_transform(data)
# Plot the ground truth data vs the predicted labels
cn = n_clusters
f = plt.figure(figsize=(10,9))

ax = f.add_subplot(221)
ax.title.set_text("Autoencoder: Ground truth labels")
ax.scatter(ae_z[cn:,0],ae_z[cn:,1],c=y[ix])
ax.scatter(ae_z[:cn,0],ae_z[:cn,1],c='r',marker='+')
# Predictions
ax = f.add_subplot(222)
ax.title.set_text("Predicted labels")
ax.scatter(ae_z[cn:,0],ae_z[cn:,1],c=ae_labels[ix])
ax.scatter(ae_z[:cn,0],ae_z[:cn,1],c='r',marker='+')

ax = f.add_subplot(223)
ax.title.set_text("DEC: Ground truth labels")
ax.scatter(dec_z[cn:,0],dec_z[cn:,1],c=y[ix])
ax.scatter(dec_z[:cn,0],dec_z[:cn,1],c='r',marker='+')
# Predictions
ax = f.add_subplot(224)
ax.title.set_text("Predicted labels")
ax.scatter(dec_z[cn:,0],dec_z[cn:,1],c=dec_labels[ix])
ax.scatter(dec_z[:cn,0],dec_z[:cn,1],c='r',marker='+')<jupyter_output><empty_output><jupyter_text>It can be confirmed that DEC increases the intra-class similarity while decreasing the inter-class similarity which leads to a better quality for clustering.As a final remark for the second part of this series, let's evaluate the accuracy and NMI measures when the Kmeans algorithm is directly applied to the input data. It can be confirmed that this algorithm is negatively affected by the curse of data dimentionality if the input data is directly used.<jupyter_code># K-means with 10 clusters
km = KMeans(n_clusters=10)
km.fit(x)
# ae_idx stores the cluster membership of the data using autoencoder
idx = km.predict(x)
print(tabulate([['Kmeans', np.round(metrics.acc(y, idx),3),np.round(metrics.nmi(y, idx),3)]],  
              headers=['Method', 'Accuracy', 'NMI']))<jupyter_output>Method      Accuracy    NMI
--------  ----------  -----
Kmeans         0.675  0.633
{'fraction_non_alphanumeric': 0.1062292238762827, 'fraction_numerical': 0.025003613238907357, 'mean_word_length': 4.952258064516129, 'pattern_counts': {'":': 0, '<': 46, '<?xml version=': 0, '>': 47, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '101089', 'license': 'MIT', 'n_tokens_mistral': 4629, 'n_tokens_neox': 4299, 'n_words': 1501, 'path': 'Deep_clustering_part2.ipynb', 'repo_name': 'zghafoori/Deep-Clustering', 'size': '13838'}