K-means Clustering Concepts

Unsupervised Learning

• Unsupervised learning analyzes data without predefined categories or labels.
• The goal is to discover inherent patterns, structures, or relationships within the data.
• It's used for tasks like clustering and dimensionality reduction.

Agenda of Unsupervised Learning

• Basic concepts of unsupervised learning
• K-means algorithm
• Representation of clusters
• Hierarchical clustering
• Distance functions
• Data standardization
• Handling mixed attributes
• Determining which clustering algorithm to use
• Cluster evaluation
• Discovering holes and data regions
• Summary

Supervised Learning vs. Unsupervised Learning

• Supervised learning involves labeled data, with attributes relating to a target attribute that can be used to predict future values.
• Unsupervised learning deals with data without a target attribute, seeking to find intrinsic data structures.

Clustering

• Clustering is a technique used to group similar data instances into clusters.
• It's a method for finding patterns in data by grouping similar instances together.
• Clustering methods are often unsupervised learning techniques since they don't rely on pre-existing categories.

An Illustration

• The provided data illustrates three distinct groups of data points, these groups are the natural clusters.

What Clustering is Used For

• Example 1: Grouping people into different shirt sizes
• Example 2: Marketing—segmenting customers based on similarities for targeted marketing campaigns
• Example 3: Text document clustering—organizing text documents according to their content similarities for a hierarchical topic view

Aspects of Clustering

• A clustering algorithm defines how the data will be grouped.
• Partitional clustering forms clusters in a single step.
• Hierarchical clustering forms clusters in multiple steps, often represented in a tree structure called a dendrogram.
• A distance function measures the similarity or dissimilarity between data points.
• The quality of a clustering result depends on the chosen algorithm, distance function, and the specific application.

K-means Clustering

• K-means is a partitional clustering algorithm
• The algorithm aims to partition data points into k distinct clusters.
• Each cluster is assigned a centroid (center).
• The algorithm first randomly places k centroids in the data and then iteratively assigns each data point to the closest centroid.
• It then re-computes the centroids, repeating the assignment process until a given criteria or stopping condition is met.

K-means Algorithm (steps)

• Step 1: Randomly select k data points as the initial centroids.
• Step 2: Repeat until a stopping criterion is met.
  • Assign each data point to the closest centroid.
  • Recompute the centroids using the latest cluster assignment.

Stopping/Convergence Criteria

• Reached minimum re-assignments of points to different clusters.
• No (or minimum) change of centroids occurs.
• A minimum decrease in the sum of squared error (SSE) occurs.
• SSE (sum of squared errors) is a measure of how well the data points fit.

Strengths of K-means Clustering

• Simple to understand and implement
• Efficient (time complexity is O(tkn), where n is number of data points, k is the number of clusters, and t is the number of iterations).

Weaknesses of K-means Clustering

• The algorithm is applicable only if the mean is defined. For category data, the centroid is represented as the most frequent value.
• The user needs to specify k, the number of clusters, which can be subjective.
• The clustering algorithm is sensitive to outliers. Outliers are data instances that are significantly distant from other data points.
• The method can struggle with clusters of arbitrary shapes and is susceptible to the randomly chosen initial cluster centroids.

Dealing with Outliers in K-means Clustering

• Remove data points significantly distant from centroids.
• Implementing Random Sampling.

Choosing the K-means Algorithm

• Selecting the right clustering algorithm is challenging because algorithms often have strengths and weaknesses in the presence of different data distributions and characteristics.
• Practitioners employ several algorithms and distance functions for comparison.

How to Choose A Clustering Algorithm

• Due to various algorithm complexities, practitioners commonly run several algorithms using different parameters and distance functions.
• They carefully evaluate and compare the outcomes.
• Interpretation of results depends on understanding the original data and the clustering algorithm.

Cluster Evaluation

• Cluster evaluation is challenging because the true cluster structure is seldom known.
• Cluster quality is evaluated using various methods, such as:
• User inspection: visual analysis, reading examples
• Study centroids/cluster spreads: visual and/or numerical observations
• Rules from a decision tree
• Text documents: direct inspection of cluster contents

Cluster Evaluation (Ground Truth)

• One evaluation approach assumes that labeled data is available.
• Use a confusion matrix to evaluate various metrics, including entropy, purity, precision, recall, and F-score.
• Data sets often contain clusters which are not precisely known.

Evaluation Measures (Entropy)

• The entropy of a cluster measures the extent the cluster contains data points from a single class.
• For each cluster, computing the entropy considers the proportion of each data class within the cluster.
• A higher entropy indicates a greater diversity of classes within the cluster.

Evaluation Measures (Purity)

• Purity of a cluster measures the extent a cluster contains data points from a single class.
• Higher purity shows that a cluster contains mostly data from a single class.

Measuring Distance Between Clusters

• Various methods exist to measure distances between clusters. They affect the clustering algorithm's result.
• Single link: smallest distance between two data points, one selected per cluster
• Complete link: largest distance between two data points, one selected per cluster
• Average link: average distance between all data points in two clusters
• Centroid: Distance between cluster centroids

Complexity of Hierarchical Clustering Algorithms

• Hierarchical clustering algorithms, such as single link, complete link and average link have a time complexity of O(n^2).
• The complexity makes these methods less appropriate for large datasets.

Data Standardization

• Standardizing attributes is often crucial to avoid skewed distance computations when attributes have different scales.
• Standardizing values ensures that different attributes don't disproportionately affect clustering based on their ranges

Nominal Attributes

• Nominal attributes are attributes without a logical ordering. For instance, "eye color."
• Transforming nominal attributes to numeric attributes often involves creating new binary attributes. Create one binary attribute for each nominal value.

Ordinal Attributes

• Ordinal attributes are nominal attributes with an intrinsic ordering, but there is not a numerical ordering. For instance, survey responses like "poor, fair, good, excellent". They have order but not distances.
• Usually treated numerically during standardization.

Handling Mixed Attributes in Clustering

• Decide which data type (e.g., interval-scaled) is dominant.
• Transform other data types to match the dominant type. Common transformations include changing to binary.
• Combine individual distances for multiple attributes.

Indirect Evaluation in Clustering

• Some applications use clustering as a helper step for a primary task. E.g. recommending products using clustering—measure how well clustering helps in the recommendation task.

Holes in Data Space

• Holes in a data space are regions in the data set with little or no points.
• Assessing the presence of holes enhances understanding of data distributions.

Data Regions and Empty Regions

• Separate data regions (clusters) and empty regions (holes).
• Use decision tree induction to distinguish clusters and holes.
• Separating data and empty regions through decision tree induction has an interesting connection between supervised and unsupervised learning.

Supervised Learning for Unsupervised Tasks

• A supervised approach can be used to solve the problem of partitioning data into data regions and empty regions.
• A supervised approach adds new "non-existing" points with assumed classes.
• Decision tree algorithms are used to partition data into data and empty regions.

Evaluating Computational Methods

• An increasing number of N points, to account for non-existing points in the data space, has implications on algorithm computational speed and resource usage.

Evaluating Clustering Algorithm Performance

• In practice, there's no definitive way to evaluate clustering algorithm performance.
• A useful approach is using several algorithms using various distance functions, and parameters.
• Algorithm performance is based on domain expertise, application understanding and individual subjective preferences.