13: Clustering

• Learning from unlabeled data

• Useful to contras with supervised learning

• Supervised learning
  • Given a set of labels, fit a hypothesis to it
• Unsupervised learning
  • Try and determining structure in the data
  • Clustering algorithm groups data together based on data features

• Market segmentation - group customers into different market segments
• Social network analysis - Facebook "smartlists"
• Organizing computer clusters and data centers for network layout and location
• Astronomical data analysis - Understanding galaxy formation

• 1) Randomly allocate two points as the cluster centroids
  • Have as many cluster centroids as clusters you want to do (K cluster centroids, in fact)
  • In our example we just have two clusters
• 2) Cluster assignment step
  • Go through each example and depending on if it's closer to the red or blue centroid assign each point to one of the two clusters
  • To demonstrate this, we've gone through the data and "colour" each point red or blue
    
• 3) Move centroid step
  • Take each centroid and move to the average of the correspondingly assigned data-points 
    
  • Repeat 2) and 3) until convergence

• Input: 
  • K (number of clusters in the data)
  • Training set {x¹, x², x³ ..., xⁿ) 
• Algorithm:
  • Randomly initialize K cluster centroids as {μ₁, μ₂, μ₃ ... μ_K}
    
    • • Loop 1
        • This inner loop repeatedly sets the c⁽ⁱ⁾ variable to be the index of the closes variable of cluster centroid closes to xⁱ 
        • i.e. take i^th example, measure squared distance to each cluster centroid, assign c⁽ⁱ⁾to the cluster closest
          
      • Loop 2
      • • Loops over each centroid calculate the average mean based on all the points associated with each centroid from c⁽ⁱ⁾
  • What if there's a centroid with no data
  • • Remove that centroid, so end up with K-1 classes
    • Or, randomly reinitialize it
    • • Not sure when though...

• e.g. T-shirt sizing
  

• One way would be to run K-means on this data
• May do the following
  
• So creates three clusters, even though they aren't really there
• Look at first population of people
  • Try and design a small T-shirt which fits the 1st population
  • And so on for the other two

• This is an example of market segmentation 
• • Build products which suit the needs of your subpopulations

• K-means does too

• Why is this good?

• Knowing this is useful because it helps for debugging
• Helps find better clusters

• cⁱ is the index of clusters {1,2, ..., K} to which xⁱ is currently assigned
  • i.e. there are m cⁱ values, as each example has a cⁱ value, and that value is one the the clusters (i.e. can only be one of K different values)
• μ_k, is the cluster associated with centroid k
  • Locations of cluster centroid k
  • So there are K 
  • So these the centroids which exist in the training data space
•  μ_cⁱ, is the cluster centroid of the cluster to which example xⁱ has been assigned to
  • This is more for convenience than anything else
    • You could look up that example i is indexed to cluster j (using the c vector), where j is between 1 and K
    • Then look up the value associated with cluster j in the μ vector (i.e. what are the features associated with μ_j)
    • But instead, for easy description, we have this variable which gets exactly the same value 
  • Lets say xⁱ as been assigned to cluster 5
    • Means that
      • cⁱ = 5
      • μ_cⁱ, = μ₅

• i.e. squared distances between training example xⁱ and the cluster centroid to which xⁱ has been assigned to
  • This is just what we've been doing, as the visual description below shows;
    
  • The red line here shows the distances between the example xⁱ and the cluster to which that example has been assigned
    • Means that when the example is very close to the cluster, this value is small
    • When the cluster is very far away from the example, the value is large
• This is sometimes called the distortion (or distortion cost function)
• So we are finding the values which minimizes this function;
  

• The cluster assigned step is minimizing J(...) with respect to c¹, c² ... cⁱ 
  • i.e. find the centroid closest to each example
  • Doesn't change the centroids themselves
• The move centroid step
  • We can show this step is choosing the values of μ which minimizes J(...) with respect to μ
• So, we're partitioning the algorithm into two parts
  • First part minimizes the c variables
  • Second part minimizes the J variables

• And how avoid local optimum

• Never spoke about how we initialize the centroids
  • A few ways - one method is most recommended

• Randomly pick K training examples
• Set μ₁ up to μ_K to these example's values

• Risk of local optimum
  
• The local optimum are valid convergence, but local optimum not global ones

• We can do multiple random initializations
  • See if we get the same result - many same results are likely to indicate a global optimum

• A typical number of times to initialize K-means is 50-1000
• Randomly initialize K-means
  • For each 100 random initialization run K-means
  • Then compute the distortion on the set of cluster assignments and centroids at convergent
  • End with 100 ways of cluster the data
  • Pick the clustering which gave the lowest distortion

• If K is larger than 10, then multiple random initializations are less likely to be necessary
• First solution is probably good enough (better granularity of clustering)

• Not a great way to do this automatically
• Normally use visualizations to do it manually

• Sometimes very ambiguous
  • e.g. two clusters or four clusters
  • Not necessarily a correct answer
• This is why doing it automatic this is hard

• Plot this (K vs J())

• Normally you don't get a a nice line -> no clear elbow on curve
• Not really that helpful

• See how well different number of clusters serve you later needs

• T-shirt size example
  • If you have three sizes (S,M,L)
  • Or five sizes (XS, S, M, L, XL)
  • Run K means where K = 3 and K = 5
    
• How does this look
  
• This gives a way to chose the number of clusters
  • Could consider the cost of making extra sizes vs. how well distributed the products are
  • How important are those sizes though? (e.g. more sizes might make the customers happier)
  • So applied problem may help guide the number of clusters