Modeling - Clustering

Clustering

Clustering is a method which groups the "closest" values together. This page will analyze results and applications from different clustering methods. Namely, the following will be explored:

• KMeans Clustering
• Hierarchical Clustering
• DBSCAN (Density) Clustering

What Data Can Be Used?

The data for cluster modeling will be initialized with PCA. Therefore, the data preparation will be identical to the PCA section. This analysis focuses on the quantitative data of the main datasets used throughout this project:

• Ski Resorts Data - Cleaning and Aggregation Process Described Here
• Weather Data - Cleaning and Aggregation Process Described Here
• Google Places Data - Cleaning and Aggregation Process Described Here

Ski Resorts Data - Snippet

Weather Data - Snippet

Google Places Data - Snippet

Data Preparation

Each dataset required some alteration in preparation for PCA. Namely, this included subsetting the data to quantitative values and separating the labels. The labels would be saved for later to compare with the results. Some of the datasets had multiple categorical data features which could be used as labels depending on the purpose of the analysis. Other columns were simply dropped. Thus, a concise script with which could perform this cleaning, along with applying the PCA algorithm and analysis of the results was created. This script can be found here, and contains detailed documentation on these functions.

Ski Resort Data - Preparation

Weather Data - Preparation

Google Places Data - Preparation

Ski Resorts Data - PCA Projection Snippet

The three-dimensional PCA for the resorts data retains 85.63% of information from the orginal features.

Weather Data - PCA Projection Snippet

The three-dimensional PCA for the weather data retains 59.95% of information from the orginal features.

Google Places Data - PCA Projection Snippet

The three-dimensional PCA for the resorts data retains 83.12% of information from the orginal features.

KMeans Clustering

KMeans is one of the more common methods of clustering. The goal is to partition a dataset into a specified number of clusters, where each point belong to the cluster with the nearest mean. It is an unsupervised method which works to accomplish this goal by minimizing the sum of square distances between centroids. Distance and "closeness" will be evaluated via Euclidean Distance throughout this method and the other clustering methods. When choosing centroids, k randomly selected points are used as the initial centroids. Data points are assigned to the nearest centroid, forming k-clusters, with the mean updated for the points in each cluster. This is repeated until centroids no longer have signficant changes or a maximum number of iterations is reached.

There are several different methods to choose an optimal number of clusters to use. Using both the Silhouette Method and Elbow Method can help confirm this optimal amount. This script can be found here, and contains detailed documentation on these functions.

KMeans - Resorts

2, 3, and 10 clusters are decent choices for the optimal number of clusters for the Resorts data, with 3 showing strong potential to be the most optimal.

• k=2 Clusters
  • Silhouette Method: 2 has the highest average silhouette score, with each cluster having datapoints with silhouette coefficients surpassing the silhouette average.
  • Elbow Method: 2 isn't in a definitive elbow point, and likely wouldn't be recommended if only using this method.
• k=3 Clusters
  • Silhouette Method: 3 has a relatively high average silhouette score, excluding 2, with each cluster having datapoints with silhouette coefficients surpassing the silhouette average.
  • Elbow Method: 3 is a definitive elbow point, although it is a local elbow point with relatively high WCSS, it could be recommended using this method.
• k=10 Clusters
  • Silhouette Method: 10 has a relatively high average silhouette score, excluding 2, with each cluster having datapoints with silhouette coefficients surpassing the silhouette average.
  • Elbow Method: Although 10 is past the second elbow point, it does have the expectedly lowest WCSS. If there were more cluster groups considered, it could be possible that this is leading into another elbow point.
• Further Considerations
  • k=5 Clusters has a decent average silhouette score, excluding 2, however one of the cluster's data has silhouette coefficients which do not meet the silhouette average score.
  • k=5, 6, and 7 Clusters would likely be the strongest choices of clusters if strictly using the elbow method. However, as describe above, 5 clusters isn't a good choice due to the silhouette coefficients of one of its clusters, and 6 and 7 have the lowest silhouette averages of the tested clusters.
  • k=8 Clusters would also be a decent option. This reduces computational overhead compared to k=10 Clusters, but the average silhouette score is lower than 2, 3, and 10.

KMeans - Weather

2, 3, and 5 clusters are decent choices for the optimal number of clusters for the Weather data, with 3 and 5 showing strong potential to be the most optimal.

• k=2 Clusters
  • Silhouette Method: 2 has the highest average silhouette score, with each cluster having datapoints with silhouette coefficients surpassing the silhouette average.
  • Elbow Method: 2 isn't in a definitive elbow point, and likely wouldn't be recommended if only using this method.
• k=3 Clusters
  • Silhouette Method: 3 has a relatively high average silhouette score, excluding 2, with each cluster having datapoints with silhouette coefficients surpassing the silhouette average.
  • Elbow Method: 3 is a definitive elbow point, although it is a local elbow point with relatively high WCSS, it could be recommended using this method.
• k=5 Clusters
  • Silhouette Method: 5 has a relatively high average silhouette score, excluding 2, with each cluster having datapoints with silhouette coefficients surpassing the silhouette average.
  • Elbow Method: 5 is a definitive elbow point, and would likely be the suggested number of clusters if strictly using this method.
• Further Considerations
  • k=2, 3, and 5 have the highest average silhouette scores.
  • All clusters tested have datapoints in which every cluster has datapoints with silhouette coefficents surpassing the average silhouette score.
  • All clusters tested have a relatively uniform distribution of datapoints across clusters, indicated by the size of the silhouette coefficients.
  • Although the silhouette averages and coefficients indicate decent choices for number of clusters, the scores for k=6, 8, 9, and 10 have relatively low average silhouette scores, which taper down even moreso after 7.
  • k=7 Clusters could be another choice, even being an elbow point in the Elbow Chart. However, the chosen 3 cluster numbers have better relative average silhouette scores.

KMeans - Google

4, 5 and 6 clusters are decent choices for the optimal number of clusters for the Google data, with 5 and 6 showing strong potential to be the most optimal.

• k=4 Clusters
  • Silhouette Method: Although 3 clusters has a higher average silhouette score, 4 is still among the highest average silhouette scores. Each cluster has datapoints with silhouette coefficients surpassing the silhouette average.
  • Elbow Method: Cluster choices of 4, 5, and 6 are optimal choices according to this method.
• k=5 Clusters
  • Silhouette Method: 5 clusters has the second highest average silhouette scores. One of the clusters with a small proportion of datapoints doesn't have silhouette coefficients which surpass the silhouette average, but that could be due to the proportion of data clustered into that group on an otherwise clustering with a high average.
  • Elbow Method: Cluster choices of 4, 5, and 6 are optimal choices according to this method.
• k=6 Clusters
  • Silhouette Method: 6 clusters has the highest average silhouette scores. One of the clusters with a small proportion of datapoints doesn't have silhouette coefficients which surpass the silhouette average, but that could be due to the proportion of data clustered into that group on an otherwise clustering with a high average.
  • Elbow Method: Cluster choices of 4, 5, and 6 are optimal choices according to this method.
• Further Considerations
  • Although k=3 Clusters has the third highest average silhouette score, using k=4 Clusters (fourth highest average silhouette score) was further validated via the elbow method.
  • All clusters tested have datapoints in which every cluster has datapoints with silhouette coefficents surpassing the average silhouette score.
  • All clusters tested have a relatively uniform distribution of datapoints across clusters, indicated by the size of the silhouette coefficients.
  • Although the silhouette averages and coefficients indicate decent choices for number of clusters, the scores for k=8, 9, and 10 have significantly lower average silhouette scores than the rest of the cluster choices. Additionally, they aren't quite supported by the elbow method.

KMeans Visualization - Resorts

For the Resorts data, clustering was performed for the following combinations of clusters and labels:

• Clusters
  • 2 Clusters
  • 3 Clusters
  • 10 Clusters
• Labels
  • Country: United States and Canada
  • Pass: type of ski pass associated with the businesses near a given ski resort
  • Region: 10 different spatial boundaries across North America

For each combination, the legend features are toggleable.

KMeans Visualization - Weather

For the Weather data, clustering was performed for the following combinations of clusters and labels:

• Clusters
  • 2 Clusters
  • 3 Clusters
  • 5 Clusters
• Labels
  • Icon: weather type for a given time period returned by the weather API
  • Month: illustrate how the clusters evolve over months via average monthly aggregation

Note that a subset of the Weather data was used for illustrative purposes.
For each combination, the legend features are toggleable.

KMeans Visualization - Google

For the Google data, clustering was performed for the following combinations of clusters and labels:

• Clusters
  • 4 Clusters
  • 5 Clusters
  • 6 Clusters
• Labels
  • Call Category: the business type that was passed to the Google Places API
  • Country: United States and Canada
  • Pass: type of ski pass associated with the businesses near a given ski resort
  • Region: 10 different spatial boundaries across North America

Note that a subset of the Google data was used for illustrative purposes.
For each combination, the legend features are toggleable.

KMeans Clustering Results and Discussion

Hierarchical Clustering

Hierarchical Clustering determines cluster assignments by building a hierarchy, either bottom-up (agglomerative) or top-down (divisive), and produces a tree-based hierarchy of points called a dendrogram. There are two main types of hierarchical clustering:

• Agglomerative (agnes)
  • bottom-up
  • starts with the points as individual clusters (i.e. each observation is initially considered as single-element cluster)
  • at each step, merge the closest pair of clusters until only one cluster (or specified k clusters) left
• Divisive (diana)
  • top-down
  • starts with one, all-inclusive clsuter (i.e. every observation in a single cluster)
  • at each step, split a cluster until each clsuter contains a point (or specified k clusters) left

Although some methods can take in a specified number of clusters, the strength of Hierarchical Clustering is in its ability to produce a visual tree known as a dendrogram, which is somewhat agnostic of this criteria, in an effort to visually compare similarities via distances.

The common machine learning libraries which allow for hierarchical clustering mostly use agglomerative clustering (bottom-up). Scikit-Learn has a module for this, sklearn.cluster.AgglomerativeClustering, however, this mainly relies on a specified number of clusters input. A more common approach in analysis of this sort is to use scip.cluster.hierarchy with dendrogram and linkage. This particular analysis will feature SciPy's libraries and modules.

Functions were created and then applied to create and analyze agglomerative dendrograms.

The functions script can be found here, and contains detailed documentation.

The applications of the functions can be found here.

Note that the same three-dimensional PCA space projected data on the three main datasets were used again for hierarchical clustering, however the Resorts data provided the best results.

Hierarchical Clustering - Resorts

The following process of analysis was applied to the Resorts data:

1. Run three-dimensional PCA on the data.
2. Create Linkage Matrix using the reduced dataset using the Ward's method.
3. Create dendrogram with parameters which essentially shows a complete bottom-up approach.
4. Tune parameters to investigate different tree clusters.
5. Expand leaves.

Complete Hierarchical Tree

The complete bottom-up visualization for the Resorts data:

There are a few things to note about this image:

• The parameters show 2 clear clusters (green and orange) under the final child cluster (blue) which contains all observations.
• The tree has increasing splits at the beginning, stemming from initial observations as their own clusters.
• The initial observation nodes are difficult to interpret. In fact, the dendrogram doesn't give much interpretation value in its current state.

One key takeway is that with the current parameters, there is little diagnostic value from this dendrogram. By tuning the parameters and expanding the nodes, actionable results can be achieved.

Truncated to Level 3 - Default Threshold

Truncating the dendrogram to level 3 will yield something more reasonable:

There are a few things to note about this image:

• The parameters show 2 clear clusters (green and orange) under the final child cluster (blue) which contains all observations.
• There is a similar result to the full dendrogram, however this version is more interpretable. At the very least, the leaves (final nodes) are readable.
• Leaves with (number) indicate number of original observations under that leaf.
• Leaves with number indicate the index of a single original observation ending in that branch. If labels are provided, leaves with this format would produce a label.
• Truncating at level 3 results in 3 tree layers underneath the final child cluster.

With these parameters, there are two clear clusters, but what's actually underneath the leaves (i.e. original observations)? If labels are applied, is there a clear split between labels? How can statistical tests help to ensure a clear differentiation between labels?

By examining different labels and applying a chi-squared statistic hypothesis test, whether or not a significant association between clusters and column labels can be concluded.

Although there isn't a distinct label separation between the clusters, different distributions of the labels are present in each cluster.

Truncated to Level 3 - Color Threshold set to Distance 30

With a truncation to level 3 revealing a more interpretable dendrogram, further patterns were revealed. By lowering the distance threshold for identifying clusters, different clusters within the data and different distributions can be revealed as well.

With these parameters, there are three clear clusters. What is underneath the leaves?

Truncated to Level 4 - Color Threshold set to Distance 20

Truncating to Level 3 was vetted well, but further clusters and patterns can be revealed given different parameters. How does a deeper truncation level with a closer distance fair for this data?

With these parameters, there are five clear clusters. What is underneath the leaves?

Hierarchical Clustering Results and Discussion

Density Clustering (DBSCAN)

Density Clustering is particularly useful when performing clustering on datasets with irregular (arbitrary) shapes and varying densities. Similar to hierarchical clustering, and different to KMeans clustering, this method doesn't require a specified number of clusters.

The main properties of DBSCAN clustering, comparitively are:

• Arbitrary Cluster Shapes
• Unspecified Number of Clusters

Using Scikit-Learn's module sklearn.cluster.DBSCAN, DBSCAN can be implemented on the datasets associated within this scope. The inputs necessary to utilize this module are namely:

• Epsilon: maximum distance between two observations
• Minimum Samples: number of observations required within parameters to be considered a cluster

Tuning the correct input parameters can be implemented via industry knowledge or dataset specific. This analysis will use a set of heuristics for choosing the correct input parameters. The process is detailed in this script.

Note that the same three-dimensional PCA space projected data on the three main datasets were used again for density based clustering.

Parameter Heuristics

If not utilizing domain knowledge for parameter selection, the following heuristics are generally accepted for density clustering:

• Epsilon: k-distance graph with elbow points
• Minimum Sample: number of dataset dimensions + 1

Minimum Sample choice is relatively straight forward, thus the question of epsilon remains. A k-distance graph approach is initialized with a choice of minimum samples made, and then the average distance between each point in the dataset and its minimum sample of neighbors is calculated. This can be aided with sklearn.neighbors.NearestNeighbors. A decent choice for epsilon is then the elbow of the sorted plotted ascending distances.

Finding the elbow, or maximum curvature, can be accomplished through "eyeballing", a manual implementation, or even through a module. This analysis take a manual approach which utilizes KMeans clustering to cluster the slopes between curves and uses an automated approach using kneed.KneeLocator.

For each dataset, the following parameters will be implemented:

• Manual (i.e. distance slope clustering)
• Automatic (i.e. KneeLocator)
• Custom (i.e. use previous parameters to attempt best clustering)

DBSCAN Clusering - Resorts

The epsilon value with the automatic detection technique gives a value of 1.22, while looking at the slope clusters give a value of around 0.1. Another manual value for epsilon could be right where the values start to change on the k-distance graph, which looks to be around 0.8.

By running the DBSCAN algorithm and visually evaluating how the parameters cluster the data can provide insight into the best choice.

DBSCAN Clusering - Weather

The epsilon value with the automatic detection technique gives a value of 0.86, while looking at the slope clusters give a value of around 0.1. Another manual value for epsilon could be right where the values start to change on the k-distance graph, which looks to be between these.

By running the DBSCAN algorithm and visually evaluating how the parameters cluster the data can provide insight into the best choice.

DBSCAN Clusering - Google

The epsilon value with the automatic detection technique gives a value of 0.99, while looking at the slope clusters give a value of around just above 0 to about 1. A custom version of the parameters was also used for this with epsilon value of 0.65 and minimum samples of 10.

By running the DBSCAN algorithm and visually evaluating how the parameters cluster the data can provide insight into the best choice.

Density Clustering (DBSCAN) Results and Discussion

Given the arbitrary shape detection used in density clustering, the clustering detection seemed to work best for Resorts Data and Google Data. A property of this clustering method is its outlier detection. Resorts and Google have rather obscure shapes, especially Google, and it was mentioned previously that outliers could be causing this. Although these aren't outliers in a typical sense, as they just don't belong any single cluster, its still a decent analysis technique.

This method wasn't great for the PCA projection of the Weather Data due to its spherical nature. Already being not an obscure shape, the algorithm seemed to cluster itself almost entirely. Although a small change of parameters did result in some of the datapoints on the outside of the data being grouped together, with more outliers (or not assigned to a single group) were recognized as well.

An Overview on Clustering Techniques (Strengths and Weaknesses)

• KMeans Clustering: iterate through centroids to minimize the sum of square distances between centroids and points.
• Strength: easy to implement and understand.
• Strength: works well with large dataset and relatively quick.
• Weakness: works with the assumption that clusters are spherical and evenly sized.
• Weakness: the number of clusters must be specified beforehand.
• Applications: seemed to work best for the Weather data due its spherical nature.
• Hierarchical Clustering: builds a hierarchy of clusters either bottom-up (agglomerative) or top-down (divisive), which produces a tree structure known as a dendrogram.
• Strength: the dendrogram can produce intuitive visual representations of the data.
• Strength: works with various distance or similarity measures.
• Strength: the shape of the data distribution doesn't affect the results.
• Strength: the number of clusters does not need to be specified beforehand.
• Weakness: computationally expensive.
• Weakness: can be difficult to use on larger datasets.
• Applications: only tested in-depth on the Resort data, which did seem to produce clusters with different properties.
• Density Clustering (DBSCAN): groups together closely packed points and identifies areas of high density as clusters based on parameters.
• Strength: the number of clusters does not need to be specified beforehand.
• Strength: works well with clusters of arbitrary shape.
• Weakness: the process is highly sensitive to parameter choice, which are given in place of a specified number of clusters.
• Weakness: computationally expensive
• Applications: seemed to work best for the Resort and Google data, which is logical due to their arbitrary and obsure shapes. This did not work well on the Weather data, likely due to the entirety of the data essentially being a highly dense sphere.

Conclusion

Distinct groupings can be identified for staple sources associated with the ski and snowbound community. Ski Resorts themselves, Weather Phenomena surrounding Ski Resorts, and Places of Business all contain characteristics which can be consolidated and patterns extracted. Ski Resorts can be processed into hierarchical structure which explains different distributions such as location (either county or region) or by Pass Type (Ikon, Epic, Other). Weather characteristics tend to form patterns around the type of weather (snow, rain, clear, etc.) and especially around time of year (i.e. months). Places of Business tend to form different groups based on their category, location (either county or region), and even by the Pass Type (Ikon, Epic, Other) of their associated ski resort!