Stat 432 Homework 10

Instruction

Please remove this section when submitting your homework.

Students are encouraged to work together on homework and/or utilize advanced AI tools. However, there are two basic rules:

• sharing, copying, or providing any part of a homework solution or code to others is an infraction of the University’s rules on Academic Integrity. Any violation will be punished as severely as possible. This simply means: write your own solution.
• You must indicate clearly the level of involvement of AI tools (ChatGPT, Copilot, etc.) at the beginning of your homework. This includes whether you used it to generate code, debug code, or write explanations. If you did not use any AI tools, please state that explicitly. You are encouraged to briefly document your prompt(s) especially when AI is heavily involved. Please be aware that you are responsible any consequences of using AI tools, including incorrect or misleading information.

Final submissions must be uploaded to Gradescope. No email or hard copy will be accepted. Please refer to the course website for late submission policy and grading rubrics.

• You are required to submit the rendered file HWx_yourNetID.pdf. For example, HW01_rqzhu.pdf. Please note that this must be a .pdf file. .html format will not be accepted because they are often not readable on gradescope. Make all of your R code chunks visible for grading.
• Include your Name and NetID at the beginning of your homework.
• Make sure that you set seed properly so that the results can be replicated if needed. Make sure the version of your R is \(\geq 4.0.0\). This will ensure your random seed generation is the same as everyone else.
• For some questions, there will be restrictions on what packages/functions you can use. Please read the requirements carefully. As long as the question does not specify such restrictions, you can use anything.
• If you use this file or the example homework .Rmd file as a template, be sure to remove this instruction section.

Question 1: K-Means [25 pts]

In our lecture, we demonstrated an example of clustering pixels in an image. In this question, you will replicate that procedure using your favorite image. To complete this question, perform the following steps:

• [5 pts] Pick your favorite image for this question and plot the original image. For computational efficiency, avoid using an extremely large resolution image file.
• [5 pts] Report the following information about your data:
  • The dimension of the original image
    
  • The dimension of the transformed data (i.e., the version you use for applying K-means)
    
  • The total variation of your data
• [10 pts] Apply the \(k\)-means algorithm to your data. Choose three distinct values of \(k\) and report the following results for each:
  • The within-cluster variance
    
  • The cluster means
    
  • A plot of the image with each pixel replaced by its corresponding cluster mean

Question 2: Hierarchical Clustering [25 pts]

Load the mtcars dataset. We will perform hierarchical clustering on this dataset using a distance metric called the Manhattan distance (also known as the \(L_1\) norm). You should construct a distance matrix \(D_{n \times n}\), where the \((i, j)\)th element represents the distance between observations \(i\) and \(j\), defined as

\[ d(\mathbf{x}_i, \mathbf{x}_j) = \lVert \mathbf{x}_i - \mathbf{x}_j \rVert_1. \]

This can be done using the dist() function, but you need to read the documentation carefully [link]. Try the complete and ward.D2 linkage methods. Select one final clustering result. Since you know the meaning of these variables, you can make the judgment based on how you think these clusters represent the data. If you believe some variables are more/less important than others, you can consider rescale them and redo the analysis. This is an open-ended question, but you should provide a reasonable explanation for your choice. Provide both numerical and graphical results to support your conclusion.

Question 3: Spectral Clustering [25 pts]

Load our MNIST hand written digit data from previous homework. Take 200 observations each from the digits 0, 2, and 5 (total 600 observations). Perform spectral clustering on this dataset by following these steps:

• [10 pts] Construct the similarity graph using the \(k\)-nearest neighbor approach with \(k=2\).
• [5 pts] Compute the Normalized Graph Laplacian matrix \(L\).
  
• [5 pts] Select the proper eignenvectors of \(L\) to form a two-dimensional representation of the data points.
• [5 pts] Plot the data points in the two-dimensional space and color the points based on their true digit labels. Briefly comment on whether the clustering results are good. If not, can you tune the parameters to improve the results?

Question 4: UMAP [25 pts]

Use the umap package in R to perform UMAP on all the first 1000 observations of the MNIST handwritten digit dataset. Use the default settings of the umap function. Plot the two-dimensional representation of the data points and color them based on their true digit labels. Briefly comment on whether the clustering results are good. What is your criterion for “good” clustering here? Can you tune the parameters to improve the results? Ask ChatGPT for ideas of tuning if you do not know where to start.