<jupyter_start><jupyter_text>Homework: Clustering Objectives- Understand the concept of unsupervised learning- Learn the _k-means clustering_ algorithm  through implementation- Practice numerical array computations without `for` or `while` loops BackgroundPizzaPy (see Homework 7) has a new competition in town. The NumPie franchise uses aggresive marketing and state of the art machine learning techniques to maximize its growth and revenue. Fresh out of university you are being hired by the new chain to plan the best locations for the new stores. Your benefit package includes a generous all you can eat option (after five years of employment).The preliminary dataset contains the geographical (2D) locations of habitual pizza eaters. Based on this information you will identify the clusters of potential customers and their location centers by implementing the [k-means clustering](https://en.wikipedia.org/wiki/K-means_clustering) algorithm.**Try to understand each step, and make sure you provide code solutions and/or text inputs for each `TODO` item (replacing `TODO` with your input).**  Step 1: Setup (5 pts)Please, provide your VUnetID. Also, if you need to import any additional Python modules (you can come back here later), add those import statements in the following code cell. To make the experiment repeatable, add a `np.random.seed()` function call with an arbitrary integer parameter.**VUnetID** : TODO<jupyter_code>import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
np.random.seed(1976)<jupyter_output><empty_output><jupyter_text>Step 2: Load and visualize the dataset (10 pts)Use the `np.loadtxt()` function to read the `customters.txt` file into a NumPy array (use `customers` as the variable name for the array). This array contains the 2D coordinates of 250 (`n`) potential customers. Make sure, you understand the shape and meaning of this array. Use the `plt.scatter()` function to create a 2D plot of the locations of the customers. Note: the plot functions expect the `x` and `y` coordinates as separate arrays. E.g. you can select the `x` coordinates from all customers by using `customers[:, 0]`.<jupyter_code>customers = np.loadtxt("customers.txt")
plt.scatter(customers[:, 0], customers[:, 1])<jupyter_output><empty_output><jupyter_text>Step 3: Determine the number of optimal clusters (5 pts)Use your human intuition based on the scatter plot above to decide how many clusters of customers you want to identify. This is the only step which relies on human brainpower (in practice, this can be automated as well, but that is beyond the scope of the assignment). Set variable `k` to the number of desired clusters.<jupyter_code>k = 5<jupyter_output><empty_output><jupyter_text>Step 4: Initialize the cluster centers (15 pts)The algorithm will keep track (and update) the centers of each cluster and will assign each customer to exactly one cluster based on the distances of the customer and centers. For the initial locations of the cluster centers pick `k` number of random of customer locations and store this array in a new variable, called `centroids`. Verify, that the shape os this array is `(k, 2)`.<jupyter_code>centroids = customers.copy()
np.random.shuffle(centroids)
centroids = centroids[:k]
centroids.shape<jupyter_output><empty_output><jupyter_text>Step 5: Initialize the cluster assignment (25 pts)Compute a new 1-dimensional integer array of `n` elements, called `assigment`, which describes the customer to cluster assignment. The assignment is decided on the geographical distances. For each customer store the integer index of the cluster, whose current location center (see `centroids`) is the closest to the customer. Do not use explicit for loops.Hint: first, compute all the pairwise distances between the customers and all cluster centers using a 3D array and automatic broadcasting. Try to understand the shape and meaning of the following expression: `customers - centroids[:, np.newaxis, :]`. Use this expression with squaring and the NumPy `sum` function (on the proper axis) to compute the pairwise distances. Finally, use `argmin` (on the proper axis) to find the indexes of the closest cluster centers.<jupyter_code>distances = np.sqrt(((customers - centroids[:, np.newaxis])**2).sum(axis=2))
assignment = np.argmin(distances, axis=0)<jupyter_output><empty_output><jupyter_text>Step 5v: Verify the cluster assignmentExecute the code below to verify that the `customers`, `centroids` and `assignment` arrays are properly initialized. You should see the `k` cluster centers in red and the assignments in different colors. Note: this is (obviously) not the final/optimal clustering, yet.<jupyter_code>plt.scatter(customers[:, 0], customers[:, 1], c=assignment)
plt.scatter(centroids[:, 0], centroids[:, 1], c="red")
plt.title("Initial cluster assignment");<jupyter_output><empty_output><jupyter_text>Step 6: Update the cluster centers (20 pts)Compute the updated location of the cluster centers. Based on the cluster assignment, compute the mean location of the customers in each cluster. This is going to be the new/updated location of the cluster center (`centroids`).Hint: This time you may use a (short) loop on the number of clusters. Try to use boolean indexing (masking) with the assignment to select all the customers belonging to the current cluster. You can also use the NumPy `mean()` function (with the proper axis) to compute the mean location of the cluster.<jupyter_code>centroids = np.array([customers[assignment==k].mean(axis=0) for k in range(centroids.shape[0])])<jupyter_output><empty_output><jupyter_text>Step 6v: Verify the updated cluster centersExecute the code below to verify that `centroids` is properly updated. While this is still not the final clustering, each center should be at the center of its assigned customers.<jupyter_code>plt.scatter(customers[:, 0], customers[:, 1], c=assignment)
plt.scatter(centroids[:, 0], centroids[:, 1], c="red")
plt.title("Initial cluster centers");<jupyter_output><empty_output><jupyter_text>Step 7: Iterative optimization (20 pts)Based on steps 5 & 6 (you can use copy & paste), implement a loop which iteratively updates the cluster assignment and the cluster centers as long as there is some change in the cluster assignment.<jupyter_code>prev_assignment = np.full_like(assignment, -1)
while np.all(prev_assignment != assignment):
    prev_assignment = assignment
    distances = np.sqrt(((customers - centroids[:, np.newaxis])**2).sum(axis=2))
    assignment = np.argmin(distances, axis=0)
    centroids = np.array([customers[assignment==k].mean(axis=0) for k in range(centroids.shape[0])])<jupyter_output><empty_output><jupyter_text>Step 7v: Verify the final clustersExecute the code below to see the final clusters. Note: while the results should look reasonable, it is not guaranteed that the algorithm finds the most optimal clusters and centers (becuase of the initial random picks of the centers). Try to run the notebook multiple times (you may want to use  `np.random.seed()` with different parameters at the start) to see if you can get the desired/optimal result.<jupyter_code>plt.scatter(customers[:, 0], customers[:, 1], c=assignment)
plt.scatter(centroids[:, 0], centroids[:, 1], c="red")
plt.title("Final clusters");<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08207934336525308, 'fraction_numerical': 0.008891928864569083, 'mean_word_length': 5.800930232558139, 'pattern_counts': {'":': 0, '<': 41, '<?xml version=': 0, '>': 41, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '584239', 'license': 'MIT', 'n_tokens_mistral': 1999, 'n_tokens_neox': 1936, 'n_words': 925, 'path': 'Lecture8/clustering.ipynb', 'repo_name': 'quao627/AGRI9999-Seminar-in-Python', 'size': '7310'}