FoCS:

Clustering

Niema Moshiri

UC San Diego SPIS 2022

Clustering

Clustering

Clustering

Clustering

Genes

Clustering

Genes

What genes have similar function?

Clustering

Patients

Clustering

Patients

What patients have similar prognoses?

Cancer Research at UCSD (at a glance)

Hannah Carter

Cancer Research at UCSD (at a glance)

Hannah Carter

Cancer Genomics Cross-Lab Meeting

What is clustering?

Clustering

• Given data points, we want to “maximally separate” them

Clustering

• Given data points, we want to “maximally separate” them
• Low intra-cluster (i.e., within cluster) pairwise distances

Clustering

• Given data points, we want to “maximally separate” them
• Low intra-cluster (i.e., within cluster) pairwise distances
• High inter-cluster (i.e., across clusters) pairwise distances

Clustering

• Given data points, we want to “maximally separate” them
• Low intra-cluster (i.e., within cluster) pairwise distances
• High inter-cluster (i.e., across clusters) pairwise distances
• Generally, we want to try to minimize the number of clusters

Supervised vs. Unsupervised Learning

• Previously, we looked at the classification problem

Supervised vs. Unsupervised Learning

• Previously, we looked at the classification problem
• Given labeled points, train a computer to classify new data

Supervised vs. Unsupervised Learning

• Previously, we looked at the classification problem
• Given labeled points, train a computer to classify new data
• That was an example of supervised learning (we know labels)

Supervised vs. Unsupervised Learning

• Previously, we looked at the classification problem
• Given labeled points, train a computer to classify new data
• That was an example of supervised learning (we know labels)
• Clustering is an example of unsupervised learning

Supervised vs. Unsupervised Learning

• Previously, we looked at the classification problem
• Given labeled points, train a computer to classify new data
• That was an example of supervised learning (we know labels)
• Clustering is an example of unsupervised learning
• We don’t know labels or anything like that in advance

Supervised vs. Unsupervised Learning

• Previously, we looked at the classification problem
• Given labeled points, train a computer to classify new data
• That was an example of supervised learning (we know labels)
• Clustering is an example of unsupervised learning
• We don’t know labels or anything like that in advance
• We want the computer to learn the underlying structure of the data

Cluster These Tolkien Characters

Cluster These Tolkien Characters

Male

Female

Cluster These Tolkien Characters

Part of the Fellowship of the Ring

Cluster These Tolkien Characters

Royalty

Not Royalty

Cluster These Tolkien Characters

Starred in a Fast & Furious Movie

Cluster These Tolkien Characters

Starred in a Fast & Furious Movie

Cluster These Tolkien Characters

Starred in a Fast & Furious Movie

Clustering is subjective!

Cluster These Tolkien Characters

Starred in a Fast & Furious Movie

Clustering is subjective!

We need to define a

pairwise distance function!

Defining a Pairwise Distance Function

• We need to define a pairwise distance function

Defining a Pairwise Distance Function

• We need to define a pairwise distance function
• Let u and v denote two objects from the universe of possibilities

Defining a Pairwise Distance Function

• We need to define a pairwise distance function
• Let u and v denote two objects from the universe of possibilities
• D(u,v) denotes the distance between u and v

Defining a Pairwise Distance Function

• We need to define a pairwise distance function
• Let u and v denote two objects from the universe of possibilities
• D(u,v) denotes the distance between u and v
• E.g. Euclidean distance

Defining a Pairwise Distance Function

• We need to define a pairwise distance function
• Let u and v denote two objects from the universe of possibilities
• D(u,v) denotes the distance between u and v
• E.g. Euclidean distance
• We can alternatively define a similarity function (and negate it)

Desirable Properties of a Clustering Algorithm

Desirable Properties of a Clustering Algorithm

• Scalability (in terms of both time and space)

Desirable Properties of a Clustering Algorithm

• Scalability (in terms of both time and space)
• Ability to deal with different data types

Desirable Properties of a Clustering Algorithm

• Scalability (in terms of both time and space)
• Ability to deal with different data types
• Minimal requirements for domain knowledge to determine inputs

Desirable Properties of a Clustering Algorithm

• Scalability (in terms of both time and space)
• Ability to deal with different data types
• Minimal requirements for domain knowledge to determine inputs
• Interpretability and usability

Desirable Properties of a Clustering Algorithm

• Scalability (in terms of both time and space)
• Ability to deal with different data types
• Minimal requirements for domain knowledge to determine inputs
• Interpretability and usability
• Optional: Incorporation of user-specified constraints

Partitional vs. Hierarchical Clustering

Partitional vs. Hierarchical Clustering

• Partitional: Construct partitions and evaluate them by some criterion

Partitional vs. Hierarchical Clustering

• Partitional: Construct partitions and evaluate them by some criterion
• Hierarchical: Create a hierarchy using some criterion

Partitional vs. Hierarchical Clustering

• Partitional: Construct partitions and evaluate them by some criterion
• Hierarchical: Create a hierarchy using some criterion
• A hierarchical clustering can be “cut” into a partitional clustering

Partitional vs. Hierarchical Clustering

• Partitional: Construct partitions and evaluate them by some criterion
• Hierarchical: Create a hierarchy using some criterion
• A hierarchical clustering can be “cut” into a partitional clustering

Partitional vs. Hierarchical Clustering

• Partitional: Construct partitions and evaluate them by some criterion
• Hierarchical: Create a hierarchy using some criterion
• A hierarchical clustering can be “cut” into a partitional clustering

Bottom-Up Hierarchical Clustering

Bottom-Up Hierarchical Clustering

Bottom-Up Hierarchical Clustering

Bottom-Up Hierarchical Clustering

Bottom-Up Hierarchical Clustering

Bottom-Up Hierarchical Clustering

How do we know which clusters are closest??

Computing Distances Between Clusters

• Given our pairwise distance function D, we know how to compute the distance between two individual objects u and v

Computing Distances Between Clusters

• Given our pairwise distance function D, we know how to compute the distance between two individual objects u and v
• It’s just D(u,v)

Computing Distances Between Clusters

• Given our pairwise distance function D, we know how to compute the distance between two individual objects u and v
• It’s just D(u,v)
• How do we compute the distance between two clusters A and B?

Computing Distances Between Clusters

• Given our pairwise distance function D, we know how to compute the distance between two individual objects u and v
• It’s just D(u,v)
• How do we compute the distance between two clusters A and B?
• Minimum distance between any element u in A and v in B

Computing Distances Between Clusters

• Given our pairwise distance function D, we know how to compute the distance between two individual objects u and v
• It’s just D(u,v)
• How do we compute the distance between two clusters A and B?
• Maximum distance between any element u in A and v in B

Computing Distances Between Clusters

• Given our pairwise distance function D, we know how to compute the distance between two individual objects u and v
• It’s just D(u,v)
• How do we compute the distance between two clusters A and B?
• Average distance between any element u in A and v in B

Computing Distances Between Clusters

• Given our pairwise distance function D, we know how to compute the distance between two individual objects u and v
• It’s just D(u,v)
• How do we compute the distance between two clusters A and B?
• Average distance between any element u in A and v in B

Something else?

Soft vs. Hard Partitional Clustering

Soft vs. Hard Partitional Clustering

• In a hard clustering, each point is assigned to a single cluster

Soft vs. Hard Partitional Clustering

• In a hard clustering, each point is assigned to a single cluster
• What about if a point looks like a mix of clusters?

Soft vs. Hard Partitional Clustering

• In a hard clustering, each point is assigned to a single cluster
• What about if a point looks like a mix of clusters?
• In a soft clustering, each point is partially assigned to multiple clusters

Some Common Clustering Algorithms

Some Common Clustering Algorithms

• K-means Clustering: Cluster points into k clusters

Some Common Clustering Algorithms

• K-means Clustering: Cluster points into k clusters
• Need to specify k (or can try multiple different values)

Some Common Clustering Algorithms

• K-means Clustering: Cluster points into k clusters
• Need to specify k (or can try multiple different values)
• UPGMA: A common bottom-up hierarchical clustering algorithm

Some Common Clustering Algorithms

• K-means Clustering: Cluster points into k clusters
• Need to specify k (or can try multiple different values)
• UPGMA: A common bottom-up hierarchical clustering algorithm
• Gaussian Mixture Models: Fit a mixture of distributions, and assign each point to its closest distribution