Clustering vs Classification

Overview

• Clustering is an unsupervised learning technique that groups unlabeled data based on similarity.
• k-means is an example of a clustering algorithm
• Classification is a supervised learning technique that assigns labels to new instances based on already labeled data.
• k-Nearest Neighbor (k-NN) is an example of a classification algorithm

k-means and k-NN

• Both k-means and k-NN are core approaches in machine learning, with k-means being unsupervised and k-NN being supervised.
• Both algorithms use a parameter called "k," but with different meanings specific to each algorithm.
• Both algorithms rely on the concept of distance, often using Euclidean distance to measure similarity between data points.

Distance Metrics

• Euclidean Distance, Manhattan Distance, and Minkowski Distance are common ways to measure the distance between data points

What is Clustering?

• Clustering involves grouping data points together based on their similarity, so they are closely related to each other within the same cluster.
• Clustering is typically performed without labels or prior knowledge of categories.

When to use k-means

• k-means used when presented with unlabeled data and discover inherent groupings.
• k-means useful when there is an expectation that the data can be divided into distinct clusters.
• k-means capable of handling approximate solutions due to its heuristic nature.

Usage Examples for k-means

• Customer clustering involves grouping customers into segments based on their purchasing behavior.
• Image compression involves reducing the color palette by clustering pixel colors.
• Document clustering involves grouping similar documents, which is useful in text mining.
• Anomaly detection identifies unusual points that don't fit well into any cluster.

k-means for image compression

• Similar colors in an image get clustered into k groups, then each pixel color gets replaced with the the average color of its cluster.
• This process reduces the palette to only k colors, which compresses the image.

k-means

• k-means is an unsupervised clustering algorithm used to partition data into k clusters, minimizing within-cluster variance.
• Clusters in k-means are based around centroids, which act as the mean point each is assigned closest to.

k-means Objective Function

• k-means partitions a set of observations X into k sets P to minimize the function: arg min Φ(P) = Σ Σ ||x - µᵢ||², where µᵢ is the centroid of cluster Pᵢ P P i=1 x∈Pᵢ

k-means: NP-hardness

• Finding the global minimum solution in k-means is NP-hard in general, even for k = 2 in high-dimensional Euclidean space, and for arbitrary k in 2D.

k-means: Lloyd's Algorithm

• Step 1 is Initialization, it involves selecting the initial centroids μ₁,..., μκ.
• Step 2 is repeating the next steps until convergence, when assignments no longer change, or the cost becomes small enough.
• The Assignment step assigns each data point xᵢ to its nearest centroid.
• The Update step recalculates each centroid as the mean of all points assigned to its cluster.

Random Initialization

• Can cause the initialization to be out of bounds of the data set

Random Initialization from Dataset

• A fast method for selecting the data, but leads to a poor local minima

Running Multiple Times with Different WCSS

Very slow way to run clustering

k-means++:

• The initialization method attempts to spreads out the initial centroids to reduce poorly selected initial seeds.

k-means++ Initialization Details:

• Motivation: Randomly choosing initial centroids tends to cause poor clustering, and can cause slow convergence
• Algorithm:
• Select one initial centroid uniformly at rondom from the data points
• For each subsequent centroid:
  • Compute the distance d(x) from each data point x to the nearest previously chosen centroid
  • Choose a new centroid from the data points with probability p(x) = D(x)^2 / Σ all x' D(x')^2
• Repeat until k centroids have been chosen

k-means++ Benefits

• k-means++ helps to reduce the chance of a bad starting configurations spreading out the initial centroids
• This approach helps to produce a lower final within-cluster sum of squares (WCSS).
• k-means++ converges faster in practice compared to purely random initialization

Feature Scaling

• Standardize or normalize features before clustering, as Euclidean distance calculations are highly affected by scale

k-means: Choosing k

• Take what happens if k is too large, or too small into account.
• Use the "Elbow method" as a heuristic when choosing, which involves plotting the sum of squared distances/Inertia vs the values of K - it being the number of clusters to form.

Pros of k-means:

• Simple and easy to implement.
• Effective if the clusters are roughly spherical and well-separated.

Cons of k-means:

• Runtime complexity is O(tmnk), which can be slow for large datasets.
• Requires specifying k a priori.
• Sensitive to outliers and initial centroids.

k-means: How Many Iterations?

• Convergence is guranteed, since there are a finite number of ways to patition the set
• Each iteration of k-means lowers the cost function

What is Classification?

• Predictive modelling task where each instance is mapped to a label, based on patterns learned from labeled data.
• Example tasks include spam detection, image recognition, medical diagnosis etc.
• Key steps:
• Training Phase: The alogrithm learns decision boundaries or patterns from labeled data
• Prediction phase, the model assigns labels to new, unseen instances

When to use k-NN

• Use k-NN when you have labeled Data
• Use k-NN when you prefer a lazy algorithm, since it has no seperate trianing time
• Use k-NN if you have a smaller data set, or an ability to speed up neighbour searches

k-Nearest Neighbor (k-NN)

• k-NN is a supervised learning method for classification that involves labeled training data.
• For a new instance, the algorithm finds the k nearest neighbors in the training set and uses a majority vote to predict the class.

k-NN for image classification

• Labeled images get stored into sets (cats vs dogs)
• To calssifye e new image, it's k nearest neighbours get found
• The majoirty label aong neighboursis the predicted class

k-NN: How It Works

• Training Phase: All labeled training instances are stored
• Lazy learning means that there are no explicit model parameters that have been saved
• Prediction Phase
• The distance of the new instance is calculated to all training instances
• Then k closest neighbours get identidied
• Then the predicted label is the majoirty class of those neighbours

k-NN: Choosing k

• When k is small may overfit to local points/outliers - leads to high variance
• A large k may smooth over local structures - leads to low variance
• Cross validation of a dataset is used to find the "correct" k

k-NN: Complexity

• Training Time - O(1) since there is no trianing and it justs stores data
• Prediction time O(k + m(1 + n)), without using data structures
• Therefore the space complexity must store all the traingin data O(mn)

k-NN: Pros

• Simple, Intuitive and easy to implement
• Can Model complex, nonlinear decision boundaries
• Works for Multi-class classification

k-NN: Cons

• Very slow if a large set gets used
• Requires all data be storied causing a large Memory usage
• Sensitive to irreverent features and feature scaling

k-means vs k-NN

• k-means, "k" = number of clusters to form.
• k-means, k must be chosen before the algorithm is run, with the dataset split accordingly.
• k-NN, "k" = the number of neighbors to consider for classification to balance bias-variance.
• k-NN, each new point may have its own set of k neighbors.

Comparison Table: k-means vs. k-NN

• k-means uses unsupervised learning, k-NN uses supervised learning
• k-means to Cluster, K-NN to Classify
• k-means to use Unlabelled data, k-NN uses Labelled data
• k-means will output k Clusters, while K-NN with show the predicted label
• k-means the usage of K = #Clusters, k-NN the usage of K = #neighbours
• K-means takes Iterative updated steps, while K-NN has no training and simply stores data.
• k-means has O(1) prediction time, k-NN may be expensive if the dataset is large.
• k-means typically uses Euclidean distance, while k-NN can use more flexible options.

Real world challenges

• With Large datasets
  • k-means might need many iterations
  • k-NN predictions will be slow
• With Noise or outliers
• k-means is sensitive with outliers
• k-NN is sensitive is k is small
• Methods rely on a good data representation

Future Directions

• k-means variants are available for different use cases
• k-NN improvements, there can improvements with "k" via Voting and indexing structures
• Dimensions can be reduced to reduce high dimensionality
• Integration is possible with deep learning

k-means:

• Parts of its unsupervised data into k clusers
• Minimises within-cluster sum of squares
• fast to run but sensitive to initialization and outliers

k-NN

• Uses labelled data to classify new points -Lazy, no trianing, expensive @ prediction time
• Simple + Powerful, but struggles with large datasets

Explore clustering and classification, two fundamental machine learning techniques. Clustering, like k-means, groups unlabeled data by similarity. Classification, exemplified by k-NN, assigns labels using labeled data. Both use 'k' and distance metrics like Euclidean distance.