<jupyter_start><jupyter_text>Introduction to Data Science Unsupervised Methods - Clustering This notebook is based on [this](https://towardsdatascience.com/unsupervised-learning-with-python-173c51dc7f03), [this](https://joernhees.de/blog/2015/08/26/scipy-hierarchical-clustering-and-dendrogram-tutorial/) and [this](https://www.analyticsvidhya.com/blog/2016/11/an-introduction-to-clustering-and-different-methods-of-clustering/) posts.<jupyter_code>import re
import os
import codecs
import string
import numpy as np
import pandas as pd
from collections import Counter

import matplotlib.pyplot as plt
import matplotlib as mpl

from sklearn import feature_extraction
from sklearn import datasets
from sklearn.cluster import KMeans

from scipy.cluster.hierarchy import linkage
# https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.cluster.hierarchy.linkage.html
from scipy.cluster.hierarchy import dendrogram
# https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.cluster.hierarchy.dendrogram.html
from scipy.cluster.hierarchy import cophenet
#https://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.cophenet.html
from scipy.spatial.distance import pdist

from IPython.display import display, Image
from IPython.core.interactiveshell import InteractiveShell

%matplotlib inline
#%matplotlib notebook<jupyter_output><empty_output><jupyter_text>Datasets  In this notebook we'll these datasets:  + [Iris dataset](https://gist.github.com/curran/a08a1080b88344b0c8a7file-iris-csv) - contains a set of 150 records under 5 attributes — Petal Length , Petal Width , Sepal Length , Sepal width and Class. Iris Setosa, Iris Virginica and Iris Versicolor are the three classes. For our Unsupervised Algorithm we give these four features of the Iris flower and predict which class it belongs to.+ Stocks - 3000 observations with 100 predictors of stock data to predicting whether the stock will go up or down. This dataset contains 100 independent variables from X1 to X100 representing profile of a stock and one outcome variable Y with two levels : 1 for rise in stock price and -1 for drop in stock price.+ A third dataset, used by a financial institution in an enployment test. It contains anonymized data from clients+ [Seeds datasets](https://raw.githubusercontent.com/vihar/unsupervised-learning-with-python/master/seeds-less-rows.csv) - information about wheat seeds+ And the fifth dataset present information about cities, population and highways, and was used in a call for applications for a data scientist position.<jupyter_code># Loading datasets
#df_iris = datasets.load_iris()  # this dataset is present in the scikit-learn distribution
df_iris = pd.read_csv('../datasets/CSVs/Iris.csv')
df_stock = pd.read_csv('../datasets/CSVs/stock_data.csv')
df_bank = pd.read_csv('../datasets/CSVs/ds_test/dados_Q3.csv')
df_seeds = pd.read_csv('../datasets/CSVs/seeds-less-rows.csv')
df_cities = pd.read_csv('../datasets/CSVs/city_dataset.csv', sep=';', decimal=',')<jupyter_output><empty_output><jupyter_text>Supervised vs Unsupervised Learning.Unsupervised Learning is a class of Machine Learning techniques to find the patterns in data. The data given to unsupervised algorithm are not labelled, which means only the input variables(X) are given with no corresponding output variables. In unsupervised learning, the algorithms are left to themselves to discover interesting structures in the data.  In supervised learning, the system tries to learn from the previous examples that are given. (On the other hand, in unsupervised learning, the system attempts to find the patterns directly from the example given.) So if the dataset is labelled it comes under a supervised problem, it the dataset is unlabelled then it is an unsupervised problem.<jupyter_code>display(Image(os.path.join('../datasets/','Figs', 'sup-unsup.png'), width=600))<jupyter_output><empty_output><jupyter_text>Clustering as an Unsupervised Learning TechniqueClustering is the task of dividing the population or data points into a number of groups such that data points in the same groups are more similar to other data points in the same group than those in other groups. In simple words, the aim is to segregate groups with similar traits and assign them into clusters.Clustering has a large no. of applications spread across various domains. Some of the most popular applications of clustering are:  + Recommendation engines+ Market segmentation+ Social network analysis+ Search result grouping+ Medical imaging+ Image segmentation+ Anomaly detection  Types of ClusteringBroadly speaking, clustering can be divided into two subgroups :    + Hard Clustering: In hard clustering, each data point either belongs to a cluster completely or not.+ Soft Clustering: In soft clustering, instead of putting each data point into a separate cluster, a probability or likelihood of that data point to be in those clusters is assigned. Since the task of clustering is subjective, the means that can be used for achieving this goal are plenty. Every methodology follows a different set of rules for defining the ‘similarity’ among data points. In fact, there are more than 100 clustering algorithms known. But few of the algorithms are used popularly, let’s look at them in detail:  + Centroid models: These are iterative clustering algorithms in which the notion of similarity is derived by the closeness of a data point to the centroid of the clusters. __K-Means clustering__ algorithm is a popular algorithm that falls into this category. In these models, the no. of clusters required at the end have to be mentioned beforehand, which makes it important to have prior knowledge of the dataset. These models run iteratively to find the local optima.  + Connectivity models: As the name suggests, these models are based on the notion that the data points closer in data space exhibit more similarity to each other than the data points lying farther away. These models can follow two approaches. In the first approach, they start with classifying all data points into separate clusters & then aggregating them as the distance decreases. In the second approach, all data points are classified as a single cluster and then partitioned as the distance increases. Also, the choice of distance function is subjective. These models are very easy to interpret but lacks scalability for handling big datasets. Examples of these models are __Hierarchical clustering__ algorithm and its variants.  + Distribution models: These clustering models are based on the notion of how probable is it that all data points in the cluster belong to the same distribution (For example: Normal, Gaussian). These models often suffer from overfitting. A popular example of these models is __Expectation-maximization__ algorithm which uses multivariate normal distributions.  + Density Models: These models search the data space for areas of varied density of data points in the data space. It isolates various different density regions and assign the data points within these regions in the same cluster. Popular examples of density models are __DBSCAN__ and __OPTICS__.    K-means Clustering  K-means is an iterative clustering algorithm that aims to find local maxima in each iteration. This algorithm works in these 5 steps :1. Specify the desired number of clusters K and randomly assign them a position2. Assign each data point the closest cluster3. Re-compute cluster centroids : Now, re-computing the centroids for both the clusters.  4. Re-assign each point to the closest cluster centroid5. Repeat steps 3 and 4 until no improvements are possibleEach centroid of a cluster is a collection of feature values which define the resulting groups. Examining the centroid feature weights can be used to qualitatively interpret what kind of group each cluster represent.<jupyter_code>display(Image('../datasets/Figs/K-means.png'))<jupyter_output><empty_output><jupyter_text>Hierarchical ClusteringHierarchical clustering, as the name suggests is an algorithm that builds hierarchy of clusters. This algorithm starts with all the data points assigned to a cluster of their own. Then two nearest clusters are merged into the same cluster. In the end, this algorithm terminates when there is only a single cluster left.The results of hierarchical clustering can be shown using dendrogram as in the next figure:<jupyter_code>display(Image('../datasets/Figs/hclustering-1.png'))<jupyter_output><empty_output><jupyter_text>At the bottom, we start with 25 data points, each assigned to separate clusters. Two closest clusters are then merged till we have just one cluster at the top. The height in the dendrogram at which two clusters are merged represents the distance between two clusters in the data space.<jupyter_code>display(Image('../datasets/Figs/hclustering-2.png'))<jupyter_output><empty_output><jupyter_text>The decision of the no. of clusters that can best depict different groups can be chosen by observing the dendrogram. The best choice of the no. of clusters is the no. of vertical lines in the dendrogram cut by a horizontal line that can transverse the maximum distance vertically without intersecting a cluster.  In the above example, the best choice of no. of clusters will be 4 as the red horizontal line in the dendrogram below covers maximum vertical distance A-B.    Clustering the seeds dataset:<jupyter_code>df_seeds.head()
# Remove the grain species from the DataFrame, save for later
varieties = list(df_seeds.pop('grain_variety'))

# Extract the measurements as a NumPy array
samples = df_seeds.values<jupyter_output><empty_output><jupyter_text>Perform hierarchical clustering on samples using the linkage() function with the method='complete' keyword argument.  Assign the result to mergings.<jupyter_code>mergings = linkage(samples, method='complete')<jupyter_output><empty_output><jupyter_text>It never hurts to play around with some other common linkage methods like 'ward', 'single', 'complete', 'average', ... and the different distance metrics like 'euclidean' (default), 'cityblock' aka Manhattan, 'hamming', 'cosine'... if you have the feeling that your data should not just be clustered to minimize the overall intra cluster variance in euclidean space. For example, you should have such a weird feeling with long (binary) feature vectors (e.g., word-vectors in text clustering).   Plot a dendrogram using the dendrogram() function on mergings, specifying the keyword arguments labels=varieties, leaf_rotation=90, and leaf_font_size=6.<jupyter_code>plt.figure(figsize=(16,8))
dendrogram(mergings,
           labels=varieties,
           leaf_rotation=90,
           leaf_font_size=6,
           )

plt.show()<jupyter_output><empty_output><jupyter_text>Clustering the cities dataset:<jupyter_code>df_cities.head()
df_cities.columns
useful = ['veiculos', 'motos', 'pop1519', 'pop2024', 'pop2529', 'pop60p',  'jovem', 'pmotos', 'rodovia']
grouped = df_cities.groupby(['ibge'])[useful].mean()
grouped = grouped.round(2)
grouped.head()
grouped.info()
grouped[grouped.isnull().any(axis=1)]
grouped.dropna(inplace=True)
X = grouped.values
mergings = linkage(X, method='ward', metric='euclidean')
#mergings = linkage(X, metric='jaccard')
#mergings = linkage(X, method='complete')
#mergings = linkage(X, method='complete', metric='correlation')
plt.figure(figsize=(18,24))
plt.title('Hierarchical Clustering Dendrogram')
plt.xlabel('sample index')
plt.ylabel('distance')
dendrogram(mergings,
           labels=grouped.index,
           leaf_rotation=90,
           leaf_font_size=6,
           )

plt.show()
c, coph_dists = cophenet(mergings, pdist(X))
c
model = KMeans(algorithm='auto', 
               copy_x=True, 
               init='k-means++', 
               max_iter=300,
               n_clusters=6, 
               n_init=10, 
               n_jobs=-1, 
               precompute_distances='auto',
               random_state=0, 
               tol=0.0001, 
               verbose=0)
model.fit(X)
all_predictions = model.predict(X)
print(all_predictions)
print(Counter(all_predictions))
plt.hist(all_predictions)<jupyter_output><empty_output><jupyter_text>Clustering the Bank dataset:<jupyter_code>df_bank.head()
df_bank.columns
df_bank.target.unique()
len(df_bank)
# Remove the target from the DataFrame, save for later
targets = list(df_bank.pop('target'))

# Extract the measurements as a NumPy array
samples = df_bank.values
mergings = linkage(samples, method='complete')
fig, ax = plt.subplots(figsize=(16,8))

dendrogram(mergings,
           p=100, 
           truncate_mode=None, 
           color_threshold=None, 
           get_leaves=True, 
           orientation='top', 
           labels=targets,
           count_sort=False, 
           distance_sort=False, 
           show_leaf_counts=True, 
           no_plot=False, 
           no_labels=False, 
           #color_list=None, 
           leaf_font_size=5, 
           leaf_rotation=90, 
           leaf_label_func=None, 
           #no_leaves=False, 
           show_contracted=False, 
           link_color_func=None, 
           ax=ax
           )
plt.show()<jupyter_output><empty_output><jupyter_text>Two important things that you should know about hierarchical clustering are:+ This algorithm has been implemented above using bottom up approach. It is also possible to follow top-down approach starting with all data points assigned in the same cluster and recursively performing splits till each data point is assigned a separate cluster.+ The decision of merging two clusters is taken on the basis of closeness of these clusters. There are multiple metrics for deciding the closeness of two clusters :      + Euclidean distance: ||a-b||2 = √(Σ(ai-bi))    + Squared Euclidean distance: ||a-b||22 = Σ((ai-bi)2)    + Manhattan distance: ||a-b||1 = Σ|ai-bi|    + Maximum distance:||a-b||INFINITY = maxi|ai-bi|    + Mahalanobis distance: √((a-b)T S-1 (-b))   {where, s : covariance matrix} Difference between K Means and Hierarchical clustering+ Hierarchical clustering can’t handle big data well but K Means clustering can. This is because the time complexity of K Means is linear i.e. O(n) while that of hierarchical clustering is quadratic i.e. O(n2).+ In K Means clustering, since we start with random choice of clusters, the results produced by running the algorithm multiple times might differ. While results are reproducible in Hierarchical clustering.+ K Means is found to work well when the shape of the clusters is hyper spherical (like circle in 2D, sphere in 3D).+ K Means clustering requires prior knowledge of K i.e. no. of clusters you want to divide your data into. But, you can stop at whatever number of clusters you find appropriate in hierarchical clustering by interpreting the dendrogram  Exploring Iris Dataset<jupyter_code>df_iris.head()<jupyter_output><empty_output><jupyter_text>Difference between K Means and Hierarchical clustering    Hierarchical clustering can’t handle big data well but K Means clustering can. This is because the time complexity of K Means is linear i.e. O(n) while that of hierarchical clustering is quadratic i.e. O(n2).    In K Means clustering, as we start with an arbitrary choice of clusters, the results generated by running the algorithm multiple times might differ. While results are reproducible in Hierarchical clustering.    K Means is found to work well when the shape of the clusters is hyper spherical (like circle in 2D, sphere in 3D).    K-Means doesn't allow noisy data, while in Hierarchical we can directly use noisy dataset for clustering. t-SNE ClusteringIt is one of the unsupervised learning method for visualisation. t-SNE stands for t-distributed stochastic neighbor embedding. It maps high dimensional space into a 2 or 3 dimensional space which can be visualised. Specifically, it models each high-dimensional object by a two- or three-dimensional point in such a way that similar objects are modeled by nearby points and dissimilar objects are modeled by distant points with high probability.t-SNE Clustering Implementation in Python for Iris Dataset.<jupyter_code># Importing Modules
from sklearn import datasets
from sklearn.manifold import TSNE
import matplotlib.pyplot as plt

# Loading dataset
df_iris = datasets.load_iris()

# Defining Model
model = TSNE(learning_rate=100)

# Fitting Model
transformed = model.fit_transform(iris_df.data)

# Plotting 2d t-Sne
x_axis = transformed[:, 0]
y_axis = transformed[:, 1]

plt.scatter(x_axis, y_axis, c=iris_df.target)
plt.show()
# Plotting
plt.scatter(x_axis, y_axis, c=df_iris.target)
plt.show()<jupyter_output><empty_output><jupyter_text>Here as the Iris dataset has four features(4d) it is transformed and represented in two dimensional figure. Similarly t-SNE model can be applied to a dataset which has n-features.DBSCAN ClusteringDBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a popular clustering algorithm used as an replacement to K-means in predictive analytics. It doesn’t require that you input the number of clusters in order to run. But in exchange, you have to tune two other parameters.The scikit-learn implementation provides a default for the eps and min_samples parameters, but you’re generally expected to tune those. The eps parameter is the maximum distance between two data points to be considered in the same neighborhood. The min_samples parameter is the minimum amount of data points in a neighborhood to be considered a cluster.DBSCAN Clustering in Python<jupyter_code># Importing Modules
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
from sklearn.decomposition import PCA

# Load Dataset
df_iris = datasets.load_iris()

# Declaring Model
dbscan = DBSCAN()

# Fitting
dbscan.fit(df_iris.data)

# Transoring Using PCA
pca = PCA(n_components=2).fit(df_iris.data)
pca_2d = pca.transform(df_iris.data)

# Plot based on Class
for i in range(0, pca_2d.shape[0]):
    if dbscan.labels_[i] == 0:
        c1 = plt.scatter(pca_2d[i, 0], pca_2d[i, 1], c='r', marker='+')
    elif dbscan.labels_[i] == 1:
        c2 = plt.scatter(pca_2d[i, 0], pca_2d[i, 1], c='g', marker='o')
    elif dbscan.labels_[i] == -1:
        c3 = plt.scatter(pca_2d[i, 0], pca_2d[i, 1], c='b', marker='*')

plt.legend([c1, c2, c3], ['Cluster 1', 'Cluster 2', 'Noise'])
plt.title('DBSCAN finds 2 clusters and Noise')
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07160292921074043, 'fraction_numerical': 0.010252237591537835, 'mean_word_length': 4.68135593220339, 'pattern_counts': {'":': 0, '<': 57, '<?xml version=': 0, '>': 57, 'https://': 8, 'lorem ipsum': 0, 'www.': 1, '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': '14', 'dir': 'jupyter-structured-clean-dedup', 'id': '227908', 'license': 'MIT', 'n_tokens_mistral': 5380, 'n_tokens_neox': 4962, 'n_words': 2143, 'path': 'notebooks/ML_UNSUP_Clustering.ipynb', 'repo_name': 'hidroware/FGV_Intro_DS', 'size': '18435'}