# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

import pandas as pd
print(f"Pandas Version: {pd.__version__}")
import numpy as np
print(f"NumPy Version: {np.__version__}")
from multiprocessing import Pool
import sys
print(f"System Version: {sys.version}")

df = pd.read_csv("County_Mortgage_Funding.csv")
df.drop("Unnamed: 0", axis=1, inplace=True)


def assign_to_centroid(centroid_dictionary, classification_dictionary, data):
    """
    Given a dictionary containing the positions of current centroids and a dictionary that will host the classifications of points to a centroid,
    this function will assign points to a particular centroid using euclidean distance.
    
    This is the function that is executed in parallel.
    """
    for point in data:
        # list of length k
        norms = [np.linalg.norm(point-centroid_dictionary[centroid]) for centroid in centroid_dictionary]
        # index corresponds to cluster #
        centroid_assignment = norms.index(min(norms))
        classification_dictionary[centroid_assignment].append(point)
    return classification_dictionary


def parallel_kmeans(k, data, processors,iterations):
    """
    This function will run the k-Means algorithm in parallel.
    
    Inputs:
        k = Number of Clusters
        data = numpy array
        processors = number of cores to use
        iterations = total iterations to run if algo does not converge.
    Outputs:
        merged_classification_dict = A dictionary containing the classification for each point in n-dimensional space.
        centroid_dict = A dictionary contains the location of the k-centroids in n-dimensional space. 
    """
    seed = np.random.RandomState(21) #random seed
    
    # splitting the data according to number of processors requested.
    data_split = np.array_split(data, processors)
    
    # this dictionary will store our centroids and their locations in n-dimensional space.
    centroid_dict = {}
    
    all_indicies = np.arange(len(data)) #all possible indicies of the data matrix
    
    #pick k random starting indicies for centroids - no replacement, want unique indicies
    intitial_centroids_indicies = seed.choice(all_indicies, size=k, replace=False)
    
    #setting k-random rows as initial centroids.
    for i in range(k):
        row = data[intitial_centroids_indicies[i]]
        centroid_dict[i] = row

    # this outer loop will ensure we stop after a certain number of iterations if we do not converge.
    for iter_ in range(iterations):
        classification_dict = {} # will store classifications of each n-dimensional point to a centroid

        for i in range(k):
            classification_dict[i] = [] #points to be stored in lists according to centroid.
        
        # multi-processing stage
        with Pool(processes=processors) as pool: #context manager
            process_objects = [pool.apply_async(assign_to_centroid, args=(centroid_dict, classification_dict, data_chunk)) for data_chunk in data_split]
            process_results = [proc.get() for proc in process_objects]
        
        # take the first dictionary that contains centroid assignments for points
        merged_classification_dict = process_results.pop(0)
        
        # Merging all the other dictionaries with the above dictionary.
        for dictionary in process_results:
            for key in dictionary:
                merged_classification_dict[key].extend(dictionary[key])
        
        old_centroids = dict(centroid_dict) # deep copy and to keep track of old_centroid locations
        
        # Here we are updating the centroid positions
        for class_ in merged_classification_dict:
            centroid_dict[class_] = np.mean(merged_classification_dict[class_], axis=0)

        convergence = True #Assume we have converged!

        for centroid in centroid_dict:
            previous_position = old_centroids[centroid]
            new_position = centroid_dict[centroid]
            # Calculated the distortion
            distortion = np.linalg.norm(new_position-previous_position)
            # if distortion is not 0,then we have not converged to a minimum. We need to keep iterating.
            if distortion != 0:
                convergence = False
        if convergence: # if we converge, break out of the iteration loop
#             print(f"Convergence on iteration {iter_}")
            break
    
    return merged_classification_dict, centroid_dict
                    


# ## Benchmarks
#
# Note: In terms of performance, using `.apply_async` significantly outperformed `.apply`.

# ### K = 2

# %%timeit
# k=2, 1 processor, max of 1000 iterations
classifications, centroids = parallel_kmeans(2, df.values, 1, 1000)

# %%timeit
# k=2, 2 processors, max of 1000 iterations
classifications, centroids = parallel_kmeans(2, df.values, 2, 1000)

# %%timeit
# k=2, 3 processors, max of 1000 iterations
classifications, centroids = parallel_kmeans(2, df.values, 3, 1000)

# %%timeit
# k=2, 8 processors, max of 1000 iterations
classifications, centroids = parallel_kmeans(2, df.values, 8, 1000)

# ### K = 3

# %%timeit
# k=3, 1 processor, max of 1000 iterations
classifications, centroids = parallel_kmeans(3, df.values, 1, 1000)

# %%timeit
# k=3, 2 processors, max of 1000 iterations
classifications, centroids = parallel_kmeans(3, df.values, 2, 1000)

# %%timeit
# k=3, 3 processors, max of 1000 iterations
classifications, centroids = parallel_kmeans(3, df.values, 3, 1000)

# %%timeit
# k=3, 8 processors, max of 1000 iterations
classifications, centroids = parallel_kmeans(3, df.values, 8, 1000)

# ## Outputs

# k=2, 8 processors, max of 1000 iterations
classifications, centroids = parallel_kmeans(2, df.values, 8, 1000)

classifications.keys() # we have 2 centroids

(len(classifications[0]) + len(classifications[1])) == df.shape[0] # all rows classified to a centroid

centroids # The final centroid positions



StarcoderdataJupyterScriptsDedupFiltered