<jupyter_start><jupyter_text>Data Science Ex 10 - Clustering (k-Means & k-Medoids) 26.04.2020, <NAME> (<EMAIL>)  Let's have some Fun with k-Means and k-Medoids Clustering! In this exercise, we are going to have a look at the k-Means and k-Medoids clustering approaches and clustering in general.Since this topic is complex and it is important that you understand the concept of a cluster, we focus on simple examples in this exercise.<jupyter_code>import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns

%matplotlib inline
sns.set()<jupyter_output><empty_output><jupyter_text>Introduction  Updates & Installation Before we can start with the exercises, we need to install a new package.I'm aware that this is a bit risky since we are not at the same location, but we'll try it.If you cannot update and install your Anaconda enviornment, you are not able to use the k-Medoids examples and exercises. Open the *Anaconda Prompt* with advanced privileges (administrator rights) (Mac users just open a terminal) and enter the following command: ```bashconda update --all``` This is the same command that we also used in the first exercise session.It will update your environment with the latests versions of all the packages you have already installed.We need this, since otherwise the next command wants to downgrade the majority your packages (what we don't want).Now, we can install a new package that contains the *k-Medoids* algorithm.Execute the command below in the same command prompt/terminal. ```bashconda install -c conda-forge scikit-learn-extra``` I recommend a restart of Anaconda, just to be sure.So close the notebook and Anaconda, and open it again.  Peparing the Data First we need some data to use with our clustering algorithms.<jupyter_code>data = pd.read_csv("./Demo_5Clusters.csv")
data.head(5)<jupyter_output><empty_output><jupyter_text>As you can see, we have 3 columns in our dataset.`l` contains a number from 0 to 4 representing the cluster a point belongs to.`x` and `y` are coordinates in a two dimensional space.Hence, we can visualize the given data.<jupyter_code>fig, ax = plt.subplots(figsize=(10,10))
ax.scatter(data["x"], data["y"], c=data["l"], s=50, cmap="rainbow")<jupyter_output><empty_output><jupyter_text>As we can see, the clusters are quite easily distinguishable.Well, the two on the right are a bit close.  Building Clusters Now, we know that there are two simple clustering algorithms that we can use:- k-Means- k-MedoidsBoth offer the same interface that we are already familiar with.There is a `fit()` method to let the algorithm find the clusters.And there is a `predict()` method to predict the clusters of points.There is also a `fit_predict()` method that combines both calls.This method comes in handy when we want to predict the clusters of the data used for finding them.  k-Means Reference: https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html<jupyter_code>from sklearn.cluster import KMeans<jupyter_output><empty_output><jupyter_text>Let's build the model, find the clusters and predict the clusters for the given points.For now, we need to know the number of clusters we want to find.Based on the provided data, we know that there are 5.<jupyter_code>model = KMeans(n_clusters=5, random_state=42) # Setting up the algorithm for 5 clusters
l_pred = model.fit_predict(data[["x", "y"]]) # Defining that we only want to use columns x and y<jupyter_output><empty_output><jupyter_text>We can also get the center of each cluster.<jupyter_code>centers = model.cluster_centers_
centers<jupyter_output><empty_output><jupyter_text>Have the results of the clustering algorithm, we can visualize again.<jupyter_code>fig, ax = plt.subplots(figsize=(10,10))
ax.scatter(data["x"], data["y"], c=l_pred, s=50, cmap="rainbow") # Using the predict clusters for coloring (c=l_pred)
ax.scatter(centers[:,0], centers[:,1], c="k", s=200, alpha=.5)<jupyter_output><empty_output><jupyter_text>As you can see, the centers do not overlap with given points.k-Means calculates its own points.  k-Medoid Reference: https://scikit-learn-extra.readthedocs.io/en/latest/generated/sklearn_extra.cluster.KMedoids.html*Note: k-Medoids is not an algorithm of scikit-learn, but an addition from another package.It supports the same interface, though.*<jupyter_code>from sklearn_extra.cluster import KMedoids<jupyter_output><empty_output><jupyter_text>Now, let's have a look how the k-Medoids algorithm solves the problem.<jupyter_code>model = KMedoids(n_clusters=5, random_state=42)
l_pred = model.fit_predict(data[["x", "y"]])
fig, ax = plt.subplots(figsize=(10,10))
ax.scatter(data["x"], data["y"], c=l_pred, s=50, cmap="rainbow")
centers = model.cluster_centers_
ax.scatter(centers[:,0], centers[:,1], c="k", s=200, alpha=.5)<jupyter_output><empty_output><jupyter_text>As you can see, now the center of each cluster is a given point within the cluster.  Sometimes, it doesn't work that well Let's have a look at another example.The main difference between this and the previous one, now we only have 4 clusters that we want to find.<jupyter_code>data = pd.read_csv("./Demo_4Clusters.csv")
data.head(5)<jupyter_output><empty_output><jupyter_text>As you can see, the data structure is the same.You just find values in column `l` ranging from 0 to 3.<jupyter_code>model_means = KMeans(n_clusters=4, random_state=42)
l_pred_means = model_means.fit_predict(data[["x", "y"]])

model_medoids = KMedoids(n_clusters=4, random_state=42)
l_pred_medoids = model_medoids.fit_predict(data[["x", "y"]])

fig, ax = plt.subplots(1, 2, figsize=(20,10))
ax[0].set(title="k-Means")
ax[0].scatter(data["x"], data["y"], c=l_pred_means, s=50, cmap="rainbow")
centers_means = model_means.cluster_centers_
ax[0].scatter(centers_means[:,0], centers_means[:,1], c="k", s=200, alpha=.5)

ax[1].set(title="k-Medoids")
ax[1].scatter(data["x"], data["y"], c=l_pred_medoids, s=50, cmap="rainbow")
centers_medoids = model_medoids.cluster_centers_
ax[1].scatter(centers_medoids[:,0], centers_medoids[:,1], c="k", s=200, alpha=.5)<jupyter_output><empty_output><jupyter_text>So, what happend here?It seems that the k-Means algorithm was able to predict the clusters well.But k-Medoids has its problems.This has something to do how the initial cluster centers are defined.While k-Means uses an optimized selection approach, k-Medoids selects them randomly.And this may lead (as in this case) to strange results. The optimized approach used by k-Means is called *k-means++* and is provied by the *init* hyperparameter.<jupyter_code>KMeans()<jupyter_output><empty_output><jupyter_text>And there is also an optimized selection approach implemented for k-Medoids - called *k-medoids++*, it's just not the default.<jupyter_code>KMedoids()<jupyter_output><empty_output><jupyter_text>So, if we run the same example again, but now with the optimized selection method, the results are as expected.<jupyter_code>model_medoids = KMedoids(n_clusters=4, init="k-medoids++", random_state=42)
l_pred_medoids = model_medoids.fit_predict(data[["x", "y"]])

fig, ax = plt.subplots(figsize=(10,10))

ax.set(title="k-Medoids")
ax.scatter(data["x"], data["y"], c=l_pred_medoids, s=50, cmap="rainbow")
centers_medoids = model_medoids.cluster_centers_
ax.scatter(centers_medoids[:,0], centers_medoids[:,1], c="k", s=200, alpha=.5)<jupyter_output><empty_output><jupyter_text>3D Depending on the use case or what we want to visualize, it is also possible to expand into the 3rd dimension.<jupyter_code>data3d = pd.read_csv("./Demo_5Clusters_3D.csv")
data3d.head(5)<jupyter_output><empty_output><jupyter_text>We have again a dataset with 5 clusters but now 3 values per point.Running the clustering algorithms stays the same (and is the same for any higher dimension - having more features - datasets).<jupyter_code>model3d = KMeans(n_clusters=5, random_state=42)
l_pred_3d = model3d.fit_predict(data3d[["x", "y", "z"]])
centers3d = model3d.cluster_centers_<jupyter_output><empty_output><jupyter_text>To use 3D visualization, we need a new package that extends matplotlib to support 3-dimensional data.<jupyter_code>from mpl_toolkits.mplot3d import Axes3D<jupyter_output><empty_output><jupyter_text>To enable 3D within matplotlib, we have to provide an additional parameter (`subplot_kw`) that has a key-value pair of `"projection": "3d"`.<jupyter_code>fig, ax = plt.subplots(figsize=(10,10), subplot_kw={"projection": "3d"})
ax.scatter(data3d["x"], data3d["y"], data3d["z"], c=l_pred_3d, s=50, cmap="rainbow", alpha=.25)
ax.scatter(centers3d[:,0], centers3d[:,1], centers3d[:,2], c="k", s=200)
ax.set(xlabel="x", ylabel="y", zlabel="z")<jupyter_output><empty_output><jupyter_text>We can also take different perspectives to get a better idea where the clusters are located.<jupyter_code>fig, ax = plt.subplots(2,2,figsize=(20,20), subplot_kw={"projection":"3d"})

ax[0,0].scatter(data3d["x"], data3d["y"], data3d["z"], c=l_pred_3d, s=50, cmap="rainbow", alpha=.25)
ax[0,0].scatter(centers3d[:,0], centers3d[:,1], centers3d[:,2], c="k", s=200)
ax[0,0].set(xlabel="x", ylabel="y", zlabel="z", title="Overview")
ax[0,0].view_init(10, 45) # Defines the perspective (elevation, horizontal angle)

ax[0,1].scatter(data3d["x"], data3d["y"], data3d["z"], c=l_pred_3d, s=50, cmap="rainbow", alpha=.25)
ax[0,1].scatter(centers3d[:,0], centers3d[:,1], centers3d[:,2], c="k", s=200)
ax[0,1].set(xlabel="x", ylabel="y", zlabel="z", title="X vs Z")
ax[0,1].view_init(10, 90)

ax[1,0].scatter(data3d["x"], data3d["y"], data3d["z"], c=l_pred_3d, s=50, cmap="rainbow", alpha=.25)
ax[1,0].scatter(centers3d[:,0], centers3d[:,1], centers3d[:,2], c="k", s=200)
ax[1,0].set(xlabel="x", ylabel="y", zlabel="z", title="Y vs Z")
ax[1,0].view_init(10, 0)

ax[1,1].scatter(data3d["x"], data3d["y"], data3d["z"], c=l_pred_3d, s=50, cmap="rainbow", alpha=.25)
ax[1,1].scatter(centers3d[:,0], centers3d[:,1], centers3d[:,2], c="k", s=200)
ax[1,1].set(xlabel="x", ylabel="y", zlabel="z", title="X vs Y")
ax[1,1].view_init(90, 45)<jupyter_output><empty_output><jupyter_text>As you can see, it can be quite useful to show clusters in 3-dimensions.And it's not that hard to achive that.  Number of Clusters As you saw in the examples above, we always had to know the number of clusters we expect in the data.And if this number is unknown, there is no way around trail & error. The simplest method that we can use when we need to know the number of clusters, we can use the so called **elbow-method**.Here, we just check, when the sum of squares of distances between the points and their cluster centers does not decrease anymore significantly.<jupyter_code>data = pd.read_csv("./Demo_FindingClusters.csv")
data.head(5)<jupyter_output><empty_output><jupyter_text>Having the data, we just test a range of clusters.The distance (square from points to centers) is held in the model and can be access with the `intertia_` property.<jupyter_code>sqr_dist = [] # Empty list for distances
clust = range(1,10)
for i in clust: # Testing numbers of clusters 1 to 9
    model = KMeans(n_clusters=i, random_state=42).fit(data)
    sqr_dist.append(model.inertia_)<jupyter_output><empty_output><jupyter_text>Having stored the values, we can now simply plot a line.<jupyter_code>fig, ax = plt.subplots(figsize=(10,5))
ax.plot(clust, sqr_dist, "o-")
ax.set(xlabel="Number of Clusters", ylabel="Sum of Distances in Clusters")<jupyter_output><empty_output><jupyter_text>And as you can see, after 4 clusters there is not much improvement.So in this case, our data can likely be split into 4 different clusters.And if we have a look at the data, we see that this is the case.<jupyter_code>model = KMeans(n_clusters=4, random_state=42)
l_pred = model.fit_predict(data)

fig, ax = plt.subplots(figsize=(10,10))
ax.scatter(data["x"], data["y"], c=l_pred, s=50, cmap="rainbow")
centers = model.cluster_centers_
ax.scatter(centers[:,0], centers[:,1], c="k", s=200, alpha=.5)<jupyter_output><empty_output><jupyter_text>Thus, the elbow-method is one simple approach to determine the number of clusters in a dataset.As you can imagine, in reality it's a bit harder.  Showing the Cluster Boundaries It could be also interesting to show the boundaries of your clusters.The concept to show the boundaries is called a [Voronoi diagram](https://en.wikipedia.org/wiki/Voronoi_diagram).A Voronoi diagram contains of points and perpendicular lines between two points.If we take the centers of your clusters as our points, the lines of a Voronoi diagram are our cluster boundaries. The scipy package offers the abbility to calculate these Voronoi diagrams and plot the in 2D.<jupyter_code>from scipy.spatial import Voronoi, voronoi_plot_2d
fig, ax = plt.subplots(figsize=(10,10))
ax.scatter(data["x"], data["y"], c=l_pred, s=50, cmap="rainbow")
centers = model.cluster_centers_
ax.scatter(centers[:,0], centers[:,1], c="k", s=200, alpha=.5)

# Voronoi
voronoi = Voronoi(centers)
f = voronoi_plot_2d(voronoi, ax=ax, show_points=False, show_vertices=False) # show_points=False does not show centers (we do that already), show_vertices=False does not show points where lines are connected.
# The method returns the figure assigned to the axis ax. If we don't store it in a variable, Jupyter will plot the figure twice.<jupyter_output><empty_output><jupyter_text>What if the points are not in a Sphere? What we have seen until now, are simple examples of points that we can easily fit into clusters.And k-Means and k-Medoids algorithms work good on such datasets.But as soon as we have other constructs, that we as humans easily can cluster, these algorithms fail miserably.<jupyter_code>data = pd.read_csv("./Demo_NonSpherical.csv")
data.head(5)
fig, ax = plt.subplots(figsize=(10,10))
ax.scatter(data["x"], data["y"], c=data["l"], s=50, cmap="rainbow")<jupyter_output><empty_output><jupyter_text>If we use our algorithms on this dataset, the results aren't quite good.<jupyter_code>model_means = KMeans(n_clusters=2, random_state=42)
l_pred_means = model_means.fit_predict(data[["x", "y"]])
centers_means = model_means.cluster_centers_

model_medoids = KMedoids(n_clusters=2, init="k-medoids++", random_state=42)
l_pred_medoids = model_medoids.fit_predict(data[["x", "y"]])
centers_medoids = model_medoids.cluster_centers_

fig, ax = plt.subplots(1,2, figsize=(20,10))
ax[0].set(title="k-Means")
ax[0].scatter(data["x"], data["y"], c=l_pred_means, s=50, cmap="rainbow")
ax[0].scatter(centers_means[:,0], centers_means[:,1], c="k", s=200, alpha=.5)

ax[1].set(title="k-Medoids")
ax[1].scatter(data["x"], data["y"], c=l_pred_medoids, s=50, cmap="rainbow")
ax[1].scatter(centers_medoids[:,0], centers_medoids[:,1], c="k", s=200, alpha=.5)<jupyter_output><empty_output><jupyter_text>As you can see, the algorithms work as expected but with such a form they cannot be successful. Luckily, there is a special clustering algorithm that uses internally the k-Means algorithm, but can handle these structures.The algorithm is called `SpectralClustering` and leverages the *nearest neighbors* approach to choose points of the cluster.<jupyter_code>from sklearn.cluster import SpectralClustering
model = SpectralClustering(n_clusters=2, affinity="nearest_neighbors", random_state=42)
l_pred = model.fit_predict(data[["x", "y"]])

fig, ax = plt.subplots(figsize=(10,10))
ax.scatter(data["x"], data["y"], c=l_pred, s=50, cmap="rainbow")
# The generated warning can be ignored.<jupyter_output><empty_output><jupyter_text>As you can see, both clusters are found as expected.So, it's really important that you have an understanding of how the data might look like.Thus, clustering is a hard task and will take some time. With this basic introdction, you are now ready to head into the exercises.You will concentrate on what you have learned today.And in the next exercise, we will introduced some advanced methods and more complex use cases.  Exercises  Ex01 - Simple Clustering In this exercise, you are going to use the k-Means and k-Medoids algorithms on a given dataset.Thus, load **Ex10_01_Data.csv**. How many points and clusters are in the dataset?You don't have to run the algorithms for that. Correct, there are 8 clusters. Create a k-Means algorithm model and train it with the given data. Where are the centers? Predict the clusters for the same points you used for training. Visualize the data and cluster centers.**Bonus:** Try to plot the cluster boundaries. Now do the same with the k-Medoids algorithm.**Bonus:** Try to plot the cluster boundaries.  Solution<jupyter_code># %load ./Ex10_01_Sol.py<jupyter_output><empty_output><jupyter_text>Ex02 - Finding the Number of Clusters In this exercise, you are going to find the number of clusters for a given dataset.You find the dataset in **Ex10_02_Data.csv**. As you can see, the data is 3-dimensional.But that shouldn't bother you. Create a k-Means model and train it with the data.Assume there is just 1 cluster. What's the sum of all distances (*hint:* `inertia_`) to the center. Now, do the same but with the assumption of 3 clusters.What's now the sum of all distances? Now, how about 8 clusters?What's the sum of distances now? Now, let's make it easier.Use the elbow-method.Check all numbers of clusters from 1 to 12.And plot the line. How many clusters do you expect in the data?Predict the clusters for the given data.Where are the cluster centers? Let's plot the data.Although, we have 3-dimensional data, we just plot 2 sides at the same time (so no 3D plot for now).But plot all 3 perspectives into the same figure.**Challenge:** Try to plot the cluster boundaries per view.  Solution<jupyter_code># %load ./Ex10_02_Sol.py<jupyter_output><empty_output><jupyter_text>Ex03 - 3D Clustering This one is pretty easy.You just have to plot 3D clusters.The dataset to use is in **Ex10_03_Data.csv**. Use the elbow-method to get the number of expected clusters. Create the k-Means algorithm model for the expected number of clusters and predict the clusters. Where are the centers? Plot the cluster in 3D.  Solution<jupyter_code># %load ./Ex10_03_Sol.py<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11771213629826308, 'fraction_numerical': 0.022900763358778626, 'mean_word_length': 6.228708516593363, 'pattern_counts': {'":': 3, '<': 123, '<?xml version=': 0, '>': 123, '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': '30', 'dir': 'jupyter-structured-clean-dedup', 'id': '577159', 'license': 'MIT', 'n_tokens_mistral': 6212, 'n_tokens_neox': 5912, 'n_words': 2030, 'path': 'SpringSemester2020/10_Clustering_kMeans-kMedoids/Data Science Ex 10 - Clustering - k-Means and k-Medoids.ipynb', 'repo_name': 'KretschiGL/DataScienceLecture', 'size': '18104'}