K-Means Clustering Concepts

Introduction to Machine Learning AI 305: Unsupervised Learning - Clustering

• Clustering is a technique used to group similar data points together into clusters.
• Dissimilar data points are grouped into different clusters.
• Clustering is often considered a type of unsupervised learning task.

Supervised vs. Unsupervised Learning

• Supervised learning involves learning from labeled data, where each data point is associated with a target class.
• Unsupervised learning, as in clustering, does not involve pre-labeled classes; instead, it aims to discover inherent patterns or structures within the data.

Clustering

• Clustering is used to find similarity groups in data.
• The goal of clustering is to group similar data instances together and separate dissimilar data instances.
• It is often used as an unsupervised learning method.

Illustration

• A data set can have multiple natural clusters or groups of data points.

What is Clustering For?

• Example 1: Grouping people by size for clothing. To create "small", "medium", "large" sizing for T-shirts.
• Example 2: Targeted marketing, identifying subgroups of people, advertising, and product purchasing. Example 3: Organizing text documents (content). This helps make a hierarchical structure for topics/hierarchy.
• Clustering has applications in various fields, including areas like medicine, psychology, botany, sociology, biology, archeology, marketing, insurance, and libraries.

Aspects of Clustering

• A clustering algorithm's quality depends on the
• algorithm used, the method of determining similarity, and the application.

K-means Clustering

• K-means is a partitional clustering algorithm that groups data points into k clusters.
• Each cluster has a center called a centroid.
• k is specified by the user.

K-means Algorithm

• Randomly select k data points to be initial centroids.
• Assign each data point to the nearest centroid.
• Recompute the centroids based on the current cluster members.
• Repeat until no or minimal data re-assignment occurs to ensure convergence.

Stopping/Convergence Criteria

• There are a few methods for recognizing convergence in K-means like:
• No (or minimum) change in data point assignments to different clusters
• No (or minimal) change in the centroid positions
• Minimal decrease in the sum of squared errors (SSE).

An Example Illustration

• The algorithm involves multiple iterations to converge on an answer. The result represents a cluster grouping.

Strengths of K-means

• Simple and easy to implement.
• Efficient with a time complexity of O(tkn), typically linear.
• k-means is the most common clustering algorithm.

Weaknesses of K-means

• The algorithm's success relies on properly identifying the ideal k value.
• The algorithm can be sensitive to outliers.
• The algorithm's result is sensitive to the initial choice of centroids.
• Not suitable for discovering clusters that are not hyperellipsoids/hyper-spheres.

Selecting the k-value

• Determining k is an important decision.
• Multiple plots can aid visualizations for understanding the different groupings and the relationships between the variables.

Weaknesses of K-means: Handling Outliers

• Removal or random selection methods to reduce outlier influence.

Weaknesses of K-means: Handling Initial Seeds

• Variation of random starting points may be necessary for different or improved results.

Common Ways to Represent Clusters

• Centroids (averages) for the cluster.
• Compute radius and standard deviation to determine extent and spread.

Using Classification

• Assign a label or classification to every point within a cluster using a supervised learning model.

Use Frequent Values to Represent Clusters

• Useful for clustering categorical data.

Clusters of Arbitrary Shapes

• Difficult to represent using centroids alone.
• Centroids may not be able to adequately represent irregular shapes.

Hierarchical Clustering

• An alternative to K-means.
• It does not require pre-specifying the number of clusters (k).
• Uses a hierarchical structure (tree, Dendrogram) to group data based on relationships.

Types of Hierarchical Clustering

• Agglomerative (bottom-up): Starts with individual data points as clusters, and merges the closest clusters iteratively until reaching a single cluster.
• Divisive (top-down): Starts with a single cluster, and recursively divides clusters into smaller ones until each data point forms its own cluster.

Agglomerative Clustering Algorithm

• Each data point starts as its own initial cluster.
• Progressively merge the clusters based on smallest distance between them.
• Continue until there is only one large cluster.

Measuring the Distance of Two Clusters (Agglomerative)

• The algorithm uses different methods (single link, complete link, average link, centroid) to measure distance between cluster sets.

Single Link Method

• Uses the closest distance points to determine cluster distance.

Complete Link Method

• Uses the furthest distance points to determine cluster distance.

Average Link and Centroid Methods

• A compromise/average of distance between points in different clusters rather than furthest or nearest.
• Centroid method uses distance between cluster centroids for evaluation.

Distance Functions

• "Similarity" and "dissimilarity" measurements are critical to clustering.
• Different types of distance functions are available for different types of data (numerical, nominal) and applications.

Distance Functions for Numerical Attributes

• Euclidean distance: Standard distance calculation.
• Manhattan distance: Absolute differences between data points.
• Minkowski distance: Generalization of Euclidean and Manhattan distances.
• Weighted Euclidean distance: Allows varying weights to different dimensions.
• Squared Euclidean distance: Places greater weight on points far apart.
• Chebychev distance: Considers the maximum difference in attributes to determine distance.

How to Choose a Clustering Algorithm

• No one-size-fits-all answer.
• Trial and error methods.
• Consideration of the data's structure/distribution, data standardization/preprocessing, and distance functions used.

PCA (Principal Components Analysis): Introduction

• PCA is a dimensionality reduction technique.
• Used for visualization or pre-processing prior to supervised methods.
• Creates new variables with maximal variation, uncorrelated with each other to capture most variance in data and reduce dimensionality.

PCA: Details

• First principal component corresponds to maximum variance of data.
• Loading vectors represent linear combinations.
• Normalized to ensure equal weighting.
• The components must be uncorrelated to reduce overlap and improve interpretability.

PCA: Example

• Illustrates data representation using principal components in two dimensions.

PCA: Further components

• Subsequent components explain less variance.
• Uncorrelated with previous components (and each other).

Computing Initial Principal Components

• Calculate using either singular value decomposition or an eigen-decomposition calculation.

Geometry of PCA

• Vectors produced by PCA show maximal variations.

Interpretation of Example

• The first principal component in the example dataset is primarily influenced by population size and ad spending.

Scaling of Variables in PCA

• Variables with different units/spread are standardized for equal weight in the principal component calculations.

Proportions of Variance Explained

• Useful for understanding the strength and relative importance of different dimensions/principal components.
• Total variance is the sum of variances of the principal components.

Summary of PCA

• Simplifies and organizes data using fewer, uncorrelated variables/dimensions.

How many Principal Components Should Be Used?

• No single answer; need careful consideration of the variance explained.
• "Scree plot" can help identify the "elbow point" suggesting a reasonable limit and the important components.

Test your knowledge of the k-means clustering algorithm through this quiz. Explore key concepts such as time complexity, handling outliers, and the strengths and weaknesses of this popular algorithm. Perfect for students and professionals alike looking to solidify their understanding of k-means.