<jupyter_start><jupyter_text>Customer Segmentation using Clustering***This mini-project is based on [this blog post](http://blog.yhat.com/posts/customer-segmentation-using-python.html) by yhat. Please feel free to refer to the post for additional information, and solutions.<jupyter_code>%matplotlib inline
import pandas as pd
import sklearn
import matplotlib.pyplot as plt
import seaborn as sns

# Setup Seaborn
sns.set_style("whitegrid")
sns.set_context("poster")<jupyter_output><empty_output><jupyter_text>DataThe dataset contains information on marketing newsletters/e-mail campaigns (e-mail offers sent to customers) and transaction level data from customers. The transactional data shows which offer customers responded to, and what the customer ended up buying. The data is presented as an Excel workbook containing two worksheets. Each worksheet contains a different dataset.<jupyter_code>df_offers = pd.read_excel("./WineKMC.xlsx", sheetname=0)
df_offers.columns = ["offer_id", "campaign", "varietal", "min_qty", "discount", "origin", "past_peak"]
df_offers.head()<jupyter_output><empty_output><jupyter_text>We see that the first dataset contains information about each offer such as the month it is in effect and several attributes about the wine that the offer refers to: the variety, minimum quantity, discount, country of origin and whether or not it is past peak. The second dataset in the second worksheet contains transactional data -- which offer each customer responded to.<jupyter_code>df_transactions = pd.read_excel("./WineKMC.xlsx", sheetname=1)
df_transactions.columns = ["customer_name", "offer_id"]
df_transactions['n'] = 1
df_transactions.head()<jupyter_output><empty_output><jupyter_text>Data wrangling We're trying to learn more about how our customers behave, so we can use their behavior (whether or not they purchased something based on an offer) as a way to group similar minded customers together. We can then study those groups to look for patterns and trends which can help us formulate future offers.The first thing we need is a way to compare customers. To do this, we're going to create a matrix that contains each customer and a 0/1 indicator for whether or not they responded to a given offer.  Checkup Exercise Set IExercise: Create a data frame where each row has the following columns (Use the pandas [`merge`](http://pandas.pydata.org/pandas-docs/stable/generated/pandas.DataFrame.merge.html) and [`pivot_table`](http://pandas.pydata.org/pandas-docs/stable/generated/pandas.pivot_table.html) functions for this purpose): customer_name One column for each offer, with a 1 if the customer responded to the offerMake sure you also deal with any weird values such as `NaN`. Read the documentation to develop your solution.<jupyter_code>#your turn
df_merge = pd.merge(left = df_offers, right = df_transactions, on = 'offer_id', how = 'left')
df_pivot= df_merge.pivot_table(index = 'customer_name', columns = 'offer_id', values = 'n', aggfunc= 'sum', fill_value = 0)
df_pivot= df_pivot.reset_index('customer_name')
x_col = df_pivot.drop('customer_name', axis = 1)
df_pivot.head()
x_col.head()<jupyter_output><empty_output><jupyter_text>K-Means ClusteringRecall that in K-Means Clustering we want to *maximize* the distance between centroids and *minimize* the distance between data points and the respective centroid for the cluster they are in. True evaluation for unsupervised learning would require labeled data; however, we can use a variety of intuitive metrics to try to pick the number of clusters K. We will introduce two methods: the Elbow method, the Silhouette method and the gap statistic.  Choosing K: The Elbow Sum-of-Squares MethodThe first method looks at the sum-of-squares error in each cluster against $K$. We compute the distance from each data point to the center of the cluster (centroid) to which the data point was assigned. $$SS = \sum_k \sum_{x_i \in C_k} \sum_{x_j \in C_k} \left( x_i - x_j \right)^2 = \sum_k \sum_{x_i \in C_k} \left( x_i - \mu_k \right)^2$$where $x_i$ is a point, $C_k$ represents cluster $k$ and $\mu_k$ is the centroid for cluster $k$. We can plot SS vs. $K$ and choose the *elbow point* in the plot as the best value for $K$. The elbow point is the point at which the plot starts descending much more slowly.  Checkup Exercise Set IIExercise:  What values of $SS$ do you believe represent better clusterings? Why? Create a numpy matrix `x_cols` with only the columns representing the offers (i.e. the 0/1 colums)  Write code that applies the [`KMeans`](http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html) clustering method from scikit-learn to this matrix.  Construct a plot showing $SS$ for each $K$ and pick $K$ using this plot. For simplicity, test $2 \le K \le 10$. Make a bar chart showing the number of points in each cluster for k-means under the best $K$. What challenges did you experience using the Elbow method to pick $K$?<jupyter_code># your turn

#Import Package:
from sklearn.cluster import KMeans

#Calculate Sum of Sqaured Errors for various values of k: 
SOS = []
for k in range(2,11):
    km = KMeans(n_clusters = k, random_state = 12)     #Initiate kmeans
    model = km.fit(x_col)           #Fit model
    SOS.append(model.inertia_)      #Calculate error values and append to SOS

#Transfrom to Dataframe:
df_SOS=  pd.DataFrame({'SOS': SOS, 'K': range(2,11)}) 

#Plot SOS Vs k:
df_SOS.plot(x= 'K', y = 'SOS', figsize= (15,8), color = 'red', marker = 'o')
_ = plt.xlabel('k-values')
_ = plt.ylabel('Sum of Squared Errors')
_ = plt.title('Elbow Method')
_ = plt.annotate("k= 4", xy =(4,218))
# Bar garph using best k:
import numpy as np

km_best = KMeans(n_clusters = 4, random_state = 12)
km_best.fit_predict(x_col)

unique,count = np.unique(km_best.labels_, return_counts = True)
print(unique, count)

_ = plt.figure(figsize= (15,8))
_ = plt.bar(unique, count, align = 'center', alpha = 0.8 )
_ = plt.xlabel('k-clusters')
_ = plt.ylabel('Count of cluster labels')
_ = plt.title('Frequency of cluster labels in the dataset')<jupyter_output>[0 1 2 3] [27 15 23 35]<jupyter_text>Observation: 1. Optimal value of k = 4 because after this point sum of squared errors reduce marginally.  2. Difficulty with elbow method is that it becomes difficult to pin down optimal value of k from the graph.   Choosing K: The Silhouette MethodThere exists another method that measures how well each datapoint $x_i$ "fits" its assigned cluster *and also* how poorly it fits into other clusters. This is a different way of looking at the same objective. Denote $a_{x_i}$ as the *average* distance from $x_i$ to all other points within its own cluster $k$. The lower the value, the better. On the other hand $b_{x_i}$ is the minimum average distance from $x_i$ to points in a different cluster, minimized over clusters. That is, compute separately for each cluster the average distance from $x_i$ to the points within that cluster, and then take the minimum. The silhouette $s(x_i)$ is defined as$$s(x_i) = \frac{b_{x_i} - a_{x_i}}{\max{\left( a_{x_i}, b_{x_i}\right)}}$$The silhouette score is computed on *every datapoint in every cluster*. The silhouette score ranges from -1 (a poor clustering) to +1 (a very dense clustering) with 0 denoting the situation where clusters overlap. Some criteria for the silhouette coefficient is provided in the table below. | Range       | Interpretation                                ||-------------|-----------------------------------------------|| 0.71 - 1.0  | A strong structure has been found.            || 0.51 - 0.7  | A reasonable structure has been found.        || 0.26 - 0.5  | The structure is weak and could be artificial.|| < 0.25      | No substantial structure has been found.      |Source: http://www.stat.berkeley.edu/~spector/s133/Clus.html Fortunately, scikit-learn provides a function to compute this for us (phew!) called [`sklearn.metrics.silhouette_score`](http://scikit-learn.org/stable/modules/generated/sklearn.metrics.silhouette_score.html). Take a look at [this article](http://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_silhouette_analysis.html) on picking $K$ in scikit-learn, as it will help you in the next exercise set. Checkup Exercise Set IIIExercise: Using the documentation for the `silhouette_score` function above, construct a series of silhouette plots like the ones in the article linked above.Exercise: Compute the average silhouette score for each $K$ and plot it. What $K$ does the plot suggest we should choose? Does it differ from what we found using the Elbow method?<jupyter_code># Your turn.
from sklearn.metrics import silhouette_samples, silhouette_score

silhouette = []

for k in range (2,11):
    km_best_2 = KMeans(n_clusters= k, random_state = 12)
    labels=km_best_2.fit_predict(x_col)
    silhouette_score(x_col,labels)
    silhouette.append(silhouette_score(x_col,labels))
print(silhouette)
    
#Plot silhouette score:
plt.figure(figsize = (15,8))
_ = plt.plot(range(2,11),silhouette, color = 'black', linestyle = '--')
_ = plt.xlabel('k-values')
_ = plt.ylabel('Silhouette Score')<jupyter_output>[0.09007566678796264, 0.11983176694269196, 0.134214593236668, 0.12669880588460608, 0.14923833749716883, 0.14998961923527868, 0.09681014391899324, 0.1002309461682194, 0.1067213573938179]<jupyter_text>Observation:1. Since silhouette average score for each k-value is <0.25, there is no substantial cluster that has been found in our dataset. 2. However, as per elbow method as well as silhouette score k = 4, 6 and 7 will provide better clustering than other k-values.   Choosing $K$: The Gap StatisticThere is one last method worth covering for picking $K$, the so-called Gap statistic. The computation for the gap statistic builds on the sum-of-squares established in the Elbow method discussion, and compares it to the sum-of-squares of a "null distribution," that is, a random set of points with no clustering. The estimate for the optimal number of clusters $K$ is the value for which $\log{SS}$ falls the farthest below that of the reference distribution:$$G_k = E_n^*\{\log SS_k\} - \log SS_k$$In other words a good clustering yields a much larger difference between the reference distribution and the clustered data. The reference distribution is a Monte Carlo (randomization) procedure that constructs $B$ random distributions of points within the bounding box (limits) of the original data and then applies K-means to this synthetic distribution of data points.. $E_n^*\{\log SS_k\}$ is just the average $SS_k$ over all $B$ replicates. We then compute the standard deviation $\sigma_{SS}$ of the values of $SS_k$ computed from the $B$ replicates of the reference distribution and compute$$s_k = \sqrt{1+1/B}\sigma_{SS}$$Finally, we choose $K=k$ such that $G_k \geq G_{k+1} - s_{k+1}$.  Aside: Choosing $K$ when we Have LabelsUnsupervised learning expects that we do not have the labels. In some situations, we may wish to cluster data that is labeled. Computing the optimal number of clusters is much easier if we have access to labels. There are several methods available. We will not go into the math or details since it is rare to have access to the labels, but we provide the names and references of these measures.* Adjusted Rand Index* Mutual Information* V-Measure* Fowlkes–Mallows indexSee [this article](http://scikit-learn.org/stable/modules/clustering.html) for more information about these metrics.  Visualizing Clusters using PCAHow do we visualize clusters? If we only had two features, we could likely plot the data as is. But we have 100 data points each containing 32 features (dimensions). Principal Component Analysis (PCA) will help us reduce the dimensionality of our data from 32 to something lower. For a visualization on the coordinate plane, we will use 2 dimensions. In this exercise, we're going to use it to transform our multi-dimensional dataset into a 2 dimensional dataset.This is only one use of PCA for dimension reduction. We can also use PCA when we want to perform regression but we have a set of highly correlated variables. PCA untangles these correlations into a smaller number of features/predictors all of which are orthogonal (not correlated). PCA is also used to reduce a large set of variables into a much smaller one. Checkup Exercise Set IVExercise: Use PCA to plot your clusters: Use scikit-learn's [`PCA`](http://scikit-learn.org/stable/modules/generated/sklearn.decomposition.PCA.html) function to reduce the dimensionality of your clustering data to 2 components Create a data frame with the following fields:     customer name   cluster id the customer belongs to   the two PCA components (label them `x` and `y`)   Plot a scatterplot of the `x` vs `y` columns Color-code points differently based on cluster ID How do the clusters look?  Based on what you see, what seems to be the best value for $K$? Moreover, which method of choosing $K$ seems to have produced the optimal result visually?Exercise: Now look at both the original raw data about the offers and transactions and look at the fitted clusters. Tell a story about the clusters in context of the original data. For example, do the clusters correspond to wine variants or something else interesting?<jupyter_code>#your turn
from sklearn.decomposition import PCA

pca = PCA(n_components = 2, random_state = 2)

pca_predict=pca.fit_transform(x_col)

df_pca = pd.DataFrame(pca_predict, columns=['x', 'y'])

df_pca.head()
df_merge_2 = pd.merge(left = df_pca, right = df_pivot, left_index=True, right_index=True)
df_merge_2 = df_merge_2.drop(range(1,33), axis = 1)
df_merge_2 = df_merge_2.assign(label= km_best.labels_)
df_merge_2.head()
#Plot PCA components: 
_ = plt.figure(figsize = (15,8))
_ = plt.scatter(df_merge_2.x, df_merge_2.y, alpha= 0.6, cmap='Set1', marker = 'o', edgecolors='black', c = df_merge_2.label)
_ = plt.xlabel('1st pca feature')
_ = plt.ylabel('2nd pca feature')
_ = plt.title('Scatter plot of PCA Variables')<jupyter_output><empty_output><jupyter_text>Observation: 1. From scatter plot above, we observe 4 cluster labels, showing some overlap between pink and brown clusters.2. Let's apply k-means to find optimal k-value as see if we can reduce some of these clusters.<jupyter_code>#Calculate optimal k-value for PCA variables:

#Sum of squared errors:
error = []

#Apply k-means
for i in range (2,11):
    km_pca = KMeans(n_clusters= i)
    km_pca.fit_predict(pca_predict)
    error.append(km_pca.inertia_)
    
#Convert array to dataframe:
df_pca_k= pd.DataFrame({'SOS': error, 'k_values': range(2,11)})

#Plot summ of squared errors Vs k-values: 

df_pca_k.plot(y = 'SOS', x = 'k_values', linestyle= "--", color = 'green', figsize = (15,8), marker = 'o')
_ = plt.annotate('k=3', xy=(3, 21), fontsize = 15)
_ = plt.xlabel('k-values')
_ = plt.ylabel('Summ of Squared Errors for PCA variables')
_ = plt.title('Elbow Method')
#Apply k-means using optimal k-value: 
km_pca_best = KMeans(n_clusters = 3, random_state = 12)

##Predict labels:
pca_lables=km_pca_best.fit_predict(pca_predict)
#Plot PCA components with optimized cluster id's: 
_ = plt.figure(figsize = (15,8))
_ = plt.scatter(df_pca.x, df_pca.y, alpha= 0.6, cmap='Set1', marker = 'o', edgecolors='black', c = pca_lables)
_ = plt.xlabel('1st pca feature')
_ = plt.ylabel('2nd pca feature')
#Silhouette Score: 
score = silhouette_score(pca_predict, pca_lables)
print(f"Silhouette Score is {score}")<jupyter_output>Silhouette Score is 0.5303468047950125<jupyter_text>Observation: 1. From above scatter plot, we can clearly see that after applying pca, we were able to reduce k-value from 4 to 3.2. Silhouette Score has improved from 0.13 to 0.53, which means a reasonable cluster structure had been formed after applying PCA before K-Means.<jupyter_code>#Let's visualize clusters with best k-value: 
df_merge_2 = pd.merge(left = df_pca, right = df_pivot, left_index=True, right_index=True)
df_merge_2 = df_merge_2.drop(range(1,33), axis = 1)
df_merge_3 = df_merge_2.assign(pca_label= pca_lables)
df_merge_3.head()
df_final=pd.merge(left = df_merge, right = df_merge_3, on= 'customer_name', how = 'inner').drop(['n'], axis = 1) 
df_final.head()
#Cluster Summary Table:
df_clusters=df_final.groupby('pca_label').agg({'min_qty': ['mean'],
                              'discount': ['mean']}).round().stack()

df_clusters=df_clusters.rename(columns={'x': 'pca_x', 'y': 'pca_y'}).reset_index()
df_clusters.drop('level_1', axis= 1)
#Melt Table:
df_clusters_melt = pd.melt(df_clusters,id_vars='pca_label',
                           value_vars=['min_qty','discount'],
                           var_name='criteria', value_name='mean')
#Bar plot:
_ = plt.figure(figsize=(15,8))
sns.barplot(x= 'pca_label', y = 'mean', data = df_clusters_melt, hue = 'criteria', palette='Set1')

_ = plt.legend(title = 'Criteria', loc ='upper right', bbox_to_anchor=(1.5,1))<jupyter_output><empty_output><jupyter_text>Observation: 1. Cluster 0: Customers get a good discount even if they don't buy as much.  What we've done is we've taken those columns of 0/1 indicator variables, and we've transformed them into a 2-D dataset. We took one column and arbitrarily called it `x` and then called the other `y`. Now we can throw each point into a scatterplot. We color coded each point based on it's cluster so it's easier to see them. Exercise Set VAs we saw earlier, PCA has a lot of other uses. Since we wanted to visualize our data in 2 dimensions, restricted the number of dimensions to 2 in PCA. But what is the true optimal number of dimensions?Exercise: Using a new PCA object shown in the next cell, plot the `explained_variance_` field and look for the elbow point, the point where the curve's rate of descent seems to slow sharply. This value is one possible value for the optimal number of dimensions. What is it?<jupyter_code>#your turn
# Initialize a new PCA model with a default number of components.
import sklearn.decomposition 
pca = sklearn.decomposition.PCA()
pca.fit(x_col)
print(pca.explained_variance_.shape)
# Do the rest on your own :)

plt.figure(figsize = (15,8))
_ = plt.plot(range(1, 33), pca.explained_variance_, color='red', marker = 'o') 
_ = plt.xlabel('Optimal Dimensions for the dataset')
_ = plt.ylabel('Explained Variance')
_ = plt.title('PCA Components Explained Variance')<jupyter_output>(32,)<jupyter_text>Observation: 1. From Elbow Curve above, we can see that explained variance decreases sharply after point 3, hence should be the optimal dimension for this dataset.  Other Clustering Algorithmsk-means is only one of a ton of clustering algorithms. Below is a brief description of several clustering algorithms, and the table provides references to the other clustering algorithms in scikit-learn. * **Affinity Propagation** does not require the number of clusters $K$ to be known in advance! AP uses a "message passing" paradigm to cluster points based on their similarity. * **Spectral Clustering** uses the eigenvalues of a similarity matrix to reduce the dimensionality of the data before clustering in a lower dimensional space. This is tangentially similar to what we did to visualize k-means clusters using PCA. The number of clusters must be known a priori.* **Ward's Method** applies to hierarchical clustering. Hierarchical clustering algorithms take a set of data and successively divide the observations into more and more clusters at each layer of the hierarchy. Ward's method is used to determine when two clusters in the hierarchy should be combined into one. It is basically an extension of hierarchical clustering. Hierarchical clustering is *divisive*, that is, all observations are part of the same cluster at first, and at each successive iteration, the clusters are made smaller and smaller. With hierarchical clustering, a hierarchy is constructed, and there is not really the concept of "number of clusters." The number of clusters simply determines how low or how high in the hierarchy we reference and can be determined empirically or by looking at the [dendogram](https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.cluster.hierarchy.dendrogram.html).* **Agglomerative Clustering** is similar to hierarchical clustering but but is not divisive, it is *agglomerative*. That is, every observation is placed into its own cluster and at each iteration or level or the hierarchy, observations are merged into fewer and fewer clusters until convergence. Similar to hierarchical clustering, the constructed hierarchy contains all possible numbers of clusters and it is up to the analyst to pick the number by reviewing statistics or the dendogram.* **DBSCAN** is based on point density rather than distance. It groups together points with many nearby neighbors. DBSCAN is one of the most cited algorithms in the literature. It does not require knowing the number of clusters a priori, but does require specifying the neighborhood size.  Clustering Algorithms in Scikit-learnMethod nameParametersScalabilityUse CaseGeometry (metric used)K-Meansnumber of clustersVery largen_samples, medium n_clusters withMiniBatch codeGeneral-purpose, even cluster size, flat geometry, not too many clustersDistances between pointsAffinity propagationdamping, sample preferenceNot scalable with n_samplesMany clusters, uneven cluster size, non-flat geometryGraph distance (e.g. nearest-neighbor graph)Mean-shiftbandwidthNot scalable with n_samplesMany clusters, uneven cluster size, non-flat geometryDistances between pointsSpectral clusteringnumber of clustersMedium n_samples, small n_clustersFew clusters, even cluster size, non-flat geometryGraph distance (e.g. nearest-neighbor graph)Ward hierarchical clusteringnumber of clustersLarge n_samples and n_clustersMany clusters, possibly connectivity constraintsDistances between pointsAgglomerative clusteringnumber of clusters, linkage type, distanceLarge n_samples and n_clustersMany clusters, possibly connectivity constraints, non EuclideandistancesAny pairwise distanceDBSCANneighborhood sizeVery large n_samples, medium n_clustersNon-flat geometry, uneven cluster sizesDistances between nearest pointsGaussian mixturesmanyNot scalableFlat geometry, good for density estimationMahalanobis distances to  centersBirchbranching factor, threshold, optional global clusterer.Large n_clusters and n_samplesLarge dataset, outlier removal, data reduction.Euclidean distance between pointsSource: http://scikit-learn.org/stable/modules/clustering.html Exercise Set VIExercise: Try clustering using the following algorithms. Affinity propagationSpectral clusteringAgglomerative clusteringDBSCANHow do their results compare? Which performs the best? Tell a story why you think it performs the best.<jupyter_code># Your turn
from sklearn.cluster import AffinityPropagation, AgglomerativeClustering, SpectralClustering, DBSCAN, MeanShift
#from sklearn.pipeline import make_pipeline

#Initiate models:
ap = AffinityPropagation()
ac = AgglomerativeClustering(n_clusters=3)
sc = SpectralClustering(n_clusters=3)
db = DBSCAN(eps = 1)
ms = MeanShift()
#AffinityPropagation
aff_labels= ap.fit_predict(x_col)
print('Silhouette Score AffinityPropagation:', silhouette_score(x_col, aff_labels))

#AgglomerativeClustering
agg_lables=ac.fit_predict(x_col)
print('Silhouette Score AgglomerativeClustering:',silhouette_score(x_col, agg_lables))

# SpectralBiclustering
sc_labels = sc.fit_predict(x_col)
print('Silhouette Score SpectralClustering:',silhouette_score(x_col, sc_labels))

#DBSCAN
db_labels = db.fit_predict(x_col)
print('Silhouette Score DBSCAN:',silhouette_score(x_col, db_labels))

#Scatter Plot of clustering models on Principal Components:
_ =plt.figure(figsize = (20,10))
_ =plt.subplot(2,2,1)
_ =plt.scatter(df_merge_2.x, df_merge_2.y, c = aff_labels, cmap = 'Set1')
_ = plt.title("Affinity Propagation")

_ =plt.subplot(2,2,2)
_ =plt.scatter(df_merge_2.x, df_merge_2.y, c = agg_lables, cmap ='Set2')
_ = plt.title("Agglomerative Clustering")

_ =plt.subplot(2,2,3)
_ =plt.scatter(df_merge_2.x, df_merge_2.y, c = sc_labels, cmap ='viridis')
_ = plt.title("Spectral Clustering")

_ =plt.subplot(2,2,4)
_ =plt.scatter(df_merge_2.x, df_merge_2.y, c = db_labels, cmap= 'plasma')
_ = plt.title("DBSCAN")<jupyter_output><empty_output><jupyter_text>Observation: 1. From above, Affinity Propogation performed better as observed from its silhouette score. However, there are multiple clusters of small sizes, which makes it difficult to    2. Because Affinity Propogation can accept many clusters of uneven cluster size. 3. So, how does it compare with mean shift model, which can also accept many clusters of uneven sizes.<jupyter_code>#Mean Shift (optional) 
ms_labels = ms.fit_predict(x_col)
print('Silhouette Score Mean Sift:',silhouette_score(x_col, ms_labels))
plt.figure(figsize= (10,8))
_ = plt.scatter(df_merge_2.x, df_merge_2.y, c = sc_labels)
_ = plt.title("Mean Shift")<jupyter_output>Silhouette Score Mean Sift: 0.16468837239678863
StarcoderdataJupyterStructuredCleanDedup