Creating a list of nearest centre items

Question

I am currently doing a project using k-means on a large dataset. I have wanted to stretch my brain a bit and do it without using any external libraries, solely by creating my own functions. I have gone fairly far but have encountered a problem of not being about to create a list based on where cluster centres lie.

For convenience sake, I have created a small subset data below to use, rather than using the whole dataset I have

dataset1 = [(6.08804, 3.457729), (4.147974, 5.275341), (6.538759, 3.670323), 
            (4.579573, 4.03559), (4.756026, 4.184762), (5.221742, 2.872705)]

cluster_1 = (0, 1)
cluster_2 = (1, 2)
clusters = [cluster_1, cluster_2] # although clusters not near data, it is to practise my model

Below i have 3 functions pertaining to the process of creating centre points for clusters

Calculating the distance between the data and cluster centres, where each point in the dataset is compared to each point in cluster_list

def calculate_distance(point1, point2):
    distance = 0
    for i in range(len(point1)):
        # Euclidian distance formula
        distance += (point1[i] - point2[i])**2
    # result then square rooted for distance
    return distance**0.5
    # end of function

Determining which cluster center a certain point is closest to

def find_nearest_centre(dataset1, clusters):
    nearest_point = []
    min_distance = 100000
    # obtaining sample from cluster list
    for c in clusters:
        # using distance formula above to calculate distance between points
        distance = calculate_distance(c, dataset)
        if distance < min_distance:
            min_distance = distance
        nearest_point.append(min_distance)
        
    return nearest_point

Creating two lists, one for each cluster, containing coordinates of data that are part of that cluster.

def create_list(dataset1, clusters):
    # new lists created for 2 clusters
    list_1 = []
    list_2 = []
    for d in dataset1:
        # using nearest_centre formula to determine which points are closest to centres
        nearest_centre = find_nearest_centre(d, clusters)
        # adding closest coordinates to list_1 for cluster 1 and list_2 for cluster 2
        if nearest_centre == clusters[0]:
            list_1.append(d)
        elif nearest_centre == clusters[1]:
            list_2.append(d)
        
    return list_1, list_2

Now to my problem. When I run the function create_list it only creates two empty lists, not appending each coordinate, as is intended. Although not realistic, if the first 3 values were in first cluster, and final 3 were closest to second cluster, the output desired would be:

create_list(dataset1, clusters) # this is only function needed to operate ideally

list_1 = [(6.08804, 3.457729), (4.147974, 5.275341), (6.538759, 3.670323)] # list of tuples output
list_2 = [(4.579573, 4.03559), (4.756026, 4.184762), (5.221742, 2.872705)] # list of tuples output

I would appreciate any help I can get, obviously sticking to the theme of using no external packages. Thanks!

user_14536215 · Answer

You are getting empty lists because you are comparing clusters to points so there are no possible matches.

Return the nearest cluster instead of the point from

def find_nearest_centre(dataset, clusters):
    min_distance = float("inf")
    # obtaining sample from cluster list
    for c in clusters:
        # using distance formula above to calculate distance between points
        distance = calculate_distance(c, dataset)
        if distance < min_distance:
            min_distance = distance
            nearest_cluster = c

    return nearest_cluster

and then compare clusters to clusters

def create_list(dataset1, clusters):
    # new lists created for 2 clusters
    list_1 = []
    list_2 = []
    for d in dataset1:
        # using nearest_centre formula to determine which points are closest to centres
        nearest_cluster = find_nearest_centre(d, clusters)
        # adding closest coordinates to list_1 for cluster 1 and list_2 for cluster 2
        if nearest_cluster == clusters[0]:
            list_1.append(d)
        elif nearest_cluster == clusters[1]:
            list_2.append(d)
        else:
            print("No match")

    return list_1, list_2

The output is not as you expected, but just from looking at it I think cluster_1 is supposed to be always closer in this case.

list_1 = []
list_2 = [(6.08804, 3.457729), (4.147974, 5.275341), (6.538759, 3.670323), (4.579573, 4.03559), (4.756026, 4.184762), (5.221742, 2.872705)]

Creating a list of nearest centre items

1 Answers