<jupyter_start><jupyter_text>Clustering lab Using clustering to find best store locationsImagine the following problem:You own the pizza chain, and you collected data about pizza deliveries in a certain neighborhood. The data contains a coordinate of each delivery as a pair *(Latitude,Longitude)*. You do not have any stores in this neighborhood, and driving there takes a lot of resources from your business. So you decide to open $K$ new stores in this area. The goal is, based on the frequent delivery data, determine the best locations for the new stores.You need to perform the $K$-means clustering of delivery locations, and otput the best location for $K$ new stores. How would you choose the location of the store within each cluster that minimizes the overall distancebetween the store and the delivery address?The data is 2-dimensional and it is easy to plot it to see if the locations of new stores make sense.<jupyter_code>%matplotlib inline
import matplotlib.pyplot as plt
import seaborn as sns; sns.set()  # for plot styling
import pandas as pd
import numpy as np
import random
from math import sqrt<jupyter_output><empty_output><jupyter_text>The data is a real data collected by [this person](https://github.com/angelddaz) while working as a pizza delivery driver. The file [pizza_delivery_locations.csv](https://docs.google.com/spreadsheets/d/1guQN-_EykRqqlY2R3uYfopNX9pc8p-E8oHJr-RTXtQU/edit?usp=sharing) is a subset of the original data and contains only *(Latitude,Longitude)* of each delivery address. Download the file and update the path below.<jupyter_code>data_file = "../datasets/pizza_delivery_locations.csv"
data = pd.read_csv(data_file)
print(data.columns)
len(data)

# convert dataframe to a 2D numpy array - it is easier to work with it
data = data.to_numpy()<jupyter_output>Index(['Latitude', 'Longitude'], dtype='object')<jupyter_text>Task 1.Use $K$-means clustering algorithm to find the best locations for new pizza stores for $K$=2, $K$=3 and $K$=4. The answers should be represented as lists of *(Latitide,Longitude)* tuples for each value of $K$.You can use the custom code from the k-means demo, or you can use the `sklearn.KMeans` module to perform clustering.<jupyter_code># clustering code for 2,3 and 4 clusters

def euclidean(v1,v2):
    res=0
    dimensions=min(len(v1),len(v2))
    for i in range(dimensions):
        res+=pow(abs(v1[i]-v2[i]),2)

    return sqrt(float(res))

# k-means clustering
def kcluster(rows,distance=euclidean,k=2):
    # Determine the minimum and maximum values for each point
    ranges=[(min([row[i] for row in rows]),max([row[i] for row in rows]))
    for i in range(len(rows[0]))]

    # Create k randomly placed centroids
    clusters=[[random.random()*(ranges[i][1]-ranges[i][0])+ranges[i][0]
                            for i in range(len(rows[0]))] for j in range(k)]
  
    lastmatches=None
    bestmatches = None

    for t in range(100):
        print ('Iteration %d' % t)
        bestmatches=[[] for i in range(k)]
    
        # Find which centroid is the closest for each row
        for j in range(len(rows)):
            row=rows[j]
            bestmatch=0
            for i in range(k):
                d=distance(clusters[i],row)
                if d<distance(clusters[bestmatch],row): bestmatch=i
            bestmatches[bestmatch].append(j)

        # If the results are the same as last time, this is complete
        if bestmatches==lastmatches: break
        lastmatches=bestmatches
    
        # Move the centroids to the average of the cluster members
        for i in range(k):
            avgs=[0.0]*len(rows[0])
            if len(bestmatches[i])>0:
                for rowid in bestmatches[i]:
                    for m in range(len(rows[rowid])):
                        avgs[m]+=rows[rowid][m]
                for j in range(len(avgs)):
                    avgs[j]/=len(bestmatches[i])
                clusters[i]=avgs
      
    return bestmatches

# Extracting best store locations for each cluster of addresses
def get_store_locations(data, clusters):
    store_locations = []
    for cluster in clusters:
        sum_x = 0
        sum_y = 0
        count = 0
        for point in cluster:
            sum_x += data[point][0]
            sum_y += data[point][1]
            count += 1
        store_locations.append((sum_x/count, sum_y/count))
    
    return store_locations

# for k = 2
ls_2 = kcluster(data, k=2)
store_locations_two = get_store_locations(data, ls_2)

# for k = 3
ls_3 = kcluster(data, k=3)
store_locations_three = get_store_locations(data, ls_3)

# for k = 4
ls_4 = kcluster(data, k=4)
store_locations_four = get_store_locations(data, ls_4)
        

print(store_locations_two)
print(store_locations_three)
print(store_locations_four)<jupyter_output>Iteration 0
Iteration 1
Iteration 2
Iteration 3
Iteration 0
Iteration 1
Iteration 2
Iteration 3
Iteration 0
Iteration 1
Iteration 2
Iteration 3
[(43.63263042079218, -116.2097921683169), (43.65603271571911, -116.25422347714658)]
[(43.64181413317214, -116.24036592978175), (43.63263042079218, -116.2097921683169), (43.66816551446282, -116.26604820247981)]
[(43.72387899999997, -116.25504600000009), (43.63263042079218, -116.2097921683169), (43.64430153457963, -116.24478462616814), (43.66813457012219, -116.26953390243892)]<jupyter_text>Task 2Visualize clusters by plotting each data point and coloring it with the different color according to the cluster to which it belongs. Also plot the locations of new stores for each value of $K$. Some examples of the final visualizations are given below.<jupyter_code>def get_data_points(data, clusters):
    points = []
    for cluster in clusters:
        cluster_points = []
        for point in cluster:
            cluster_points.append(data[point])
        points.append(cluster_points)
    
    x_y = []
    for cluster in points:
        x = []
        y = []
        for point in cluster:
            x.append(point[0])
            y.append(point[1])
        x_y.append(x)
        x_y.append(y)
    return x_y

def get_store_location_x_y(clusters):
    x = []
    y = []
    x_y = []
    for point in clusters:
        x.append(point[0])
        y.append(point[1])
    x_y.append(x)
    x_y.append(y)
    return x_y
        
# for k = 2
points_2 = get_data_points(data, ls_2)
store_loc_2 = get_store_location_x_y(store_locations_two)

plt.scatter(points_2[0], points_2[1], c='b')
plt.scatter(points_2[2], points_2[3], c='r')
plt.scatter(store_loc_2[0], store_loc_2[1], marker='x', c='g')
plt.show()


# for k = 3
points_3 = get_data_points(data, ls_3)
store_loc_3 = get_store_location_x_y(store_locations_three)

plt.scatter(points_3[0], points_3[1], c='b')
plt.scatter(points_3[2], points_3[3], c='r')
plt.scatter(points_3[4], points_3[5], c='y')
plt.scatter(store_loc_3[0], store_loc_3[1], marker='x', c='g')
plt.show()


# for k = 4
points_4 = get_data_points(data, ls_4)
store_loc_4 = get_store_location_x_y(store_locations_four)

plt.scatter(points_4[0], points_4[1], c='b')
plt.scatter(points_4[2], points_4[3], c='r')
plt.scatter(points_4[4], points_4[5], c='y')
plt.scatter(points_4[6], points_4[7], c='c')
plt.scatter(store_loc_4[0], store_loc_4[1], marker='x', c='g')
plt.show()<jupyter_output><empty_output><jupyter_text>Examples of cluster visualization in 2D<jupyter_code># Plotting original data

# Plotting clusters with centers<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10798756588728206, 'fraction_numerical': 0.05771050141911069, 'mean_word_length': 3.6599496221662466, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 20, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '309142', 'license': 'MIT', 'n_tokens_mistral': 2748, 'n_tokens_neox': 2457, 'n_words': 715, 'path': 'pizza_store_locations_lab.ipynb', 'repo_name': 'jyun18/ml_clustering_lab', 'size': '7399'}