CPSC51100 Programming Assignment  2– k-Means Clustering Solved

Description

Clustering has many applications, including inferring population structures from genetic data, recognizing communities within social networks, or segmenting of customers for market research.

 

One of the most popular algorithms for performing clustering is the k-means method. The algorithm depends on the notion of distance between two points. For points with only one dimension (just single values), we can define the distance between two points  and  as

 

The k-means algorithm will work by placing points into clusters and computing their centroids, which is defined as the average of the data points in the cluster. Specifically, the algorithm works as follows:

1. Pick k, the number of clusters.
2. Initialize clusters by picking one point (centroid) per cluster. For this assignment, you can pick the first k points as initial centroids for each corresponding cluster.
3. For each point, place it in the cluster whose current centroid it is nearest.
4. After all points are assigned, update the locations of centroids of the k clusters
5. Reassign all points to their closest centroid. This sometimes moves points between clusters.
6. Repeat 4,5 until convergence. Convergence occurs when points don’t move between clusters and centroids stabilize.

 

 

 

Requirements

You are to create a program using Python that does the following:

1. Asks the user for the number of clusters. This is the parameter k that will be used for k-means.
2. Reads the input file (prog2-input-data.txt) and stores the points into a list
3. Applies the k-means algorithm to find the cluster for each point.
4. Displays the points that each cluster contains after each iteration of the algorithm
5. Writes the final cluster assignments to the screen and the output file (prog2-output-data.txt).

 

YOU CANNOT USE ANY PYTHON PACKAGES FOR THIS PROGRAM (NUMPY, PANDAS, …) – NO IMPORT STATEMENTS.

 

Additional Requirements

1. The name of your source code file should be py. All your code should be within a single file.
2. Your code should follow good coding practices, including good use of whitespace and use of both inline and block comments.
3. You need to use meaningful identifier names that conform to standard naming conventions.
4. At the top of each file, you need to put in a block comment with the following information: your name, date, course name, semester, and assignment name.
5. The output of your program should exactly match the sample program output given at the end. That is, for same input, it should generate the same output. Note that I may use other test cases for grading your program and your code needs to work correctly in all cases.

 

 

 

Data File Format

Let N be the number of points and Pi to be the value of point i. The input file should be of the following format:

P1

P2

…

PN

 

Example:

1.2

2.1

4.56

2.113

2.2

 

The name of the input file is always:

prog2-input-data.txt

 

What to Turn In

You will turn in the single kMeans.py file using BlackBoard.

 

HINTS

• Make use of list comprehensions for reading lines from a file and then converting the strings into a list of floats.
• Use pwd() to check the directory where you should place your input file.
• Use a dict data structures for storing centroids and clusters. The centroids dict will be a mapping from cluster number to centroids. The clusters dict will be a mapping from cluster number to a list of points in the cluster.

 

# Initialization

1. Print header info to screen
2. Get input/output file names and number of clusters
3. Read file:

-use open() and a list comprehension to strip all lines of ending char (using rstrip method) and convert to floats

4. Create variables to store centroids, clusters, and point assignments. Initially, pick one point (centroid) per cluster:

-create and initialize a variable to store centroids for each cluster: a mapping (dict) from range(k) to data[0:k]

-create and initialize another variable to store all points for each cluster: a mapping (dict) of range(k) to k empty lists

-use zip when creating the dict

-create and initialize a dict mapping points to clusters

-create a variable to store old point assignments (from previous iteration)

# Algorithm

5. Repeat the following:
6. a) Save current point assignment into old point assignment variable (create a new dict from current assignment

variable)

1. b) Place each point in the closest cluster (you should make a function that does this)
2. c) Update the locations of centroids of the k clusters (make a function for this also)
3. d) Reinitialize the clusters variable to empty lists

# Output

6. Print the point assignments

DETAILED HINTS

# Initialization

1. Print header info to screen

Use print function.

2. Get input/output file names and number of clusters

Use raw_input. For number of clusters (k), make sure to use int() to convert to an integer.

3. Read file:

-use open() and a list comprehension to strip all lines of ending char (using rstrip method) and

convert to floats

I basically showed this in the video:

data = [float(x.rstrip()) for x in open(input_file)]

4. Create variables to store centroids, clusters, and point assignments. Initially, pick one point

(centroid) per cluster:

-create and initialize a variable to store centroids for each cluster: a mapping (dict) from range(k)

to data[0:k]

centroids = dict(zip(range(k),data[0:k])

-create and initialize another variable to store all points for each cluster: a mapping (dict) of

range(k) to k empty lists -use zip when creating the dict

clusters = dict(zip(range(k),[[] for i in range(k)]))

-create and initialize a dict mapping points to clusters

First, think about how points are represented – as numbers in a list, with each number having an

index value. So you can do a mapping between each of the index values (0..k-1) and the cluster

to which the point having this index value belongs. Initially, the points won’t belong to any

cluster, so you can just map to dummy values. Later, you will update these with appropriate

values (after each iteration).

-create a variable to store old point assignments (from previous iteration)

Since there is no previous assignment on first iteration, just assign an empty dict to an

old_point_assignments variable

# Algorithm

5. Repeat the following:
6. a) Save current point assignment into old point assignment variable (create a new dict from

current assignment variable)

This should create a copy of the dict holding the point assignments into the

old_point_assignments variable

1. b) Place each point in the closest cluster (you should make a function that does this)

Make a function called assign_to_clusters that takes as input: data, clusters, centroids, and

point_assignments. The function should go through each point and index of that point in data

(use enumarate()) and find the closest centroid. Then add that point to the list of points for that

clusters in the clusters variable. Also, do:

point_assignments[j] = closest_index

1. c) Update the locations of centroids of the k clusters (make a function for this also)

Make a function that takes as input: data, clusters, and centroids. It should go through each list

contained in clusters variable and recompute the centroid by averaging over all the points in that

list (use sum() and len() functions). After computing, update the corresponding centroids value.

1. d) Reinitialize the clusters variable to empty lists

clusters = dict(zip(range(k),[[] for i in range(k)]))

# Output

6. Print the point assignments

Go through all values in point_assignments and print them.

 

 

Sample Program Output

CPSC-51100, [semester] [year]

NAME: [put your name here]

PROGRAMMING ASSIGNMENT #2

 

Enter the number of clusters: 5

 

Iteration 1

0 [1.8]

1 [4.5, 6.5]

2 [1.1, 0.5]

3 [2.1, 3.2]

4 [9.8, 7.6, 11.32]

 

Iteration 2

0 [1.8, 2.1]

1 [4.5, 6.5]

2 [1.1, 0.5]

3 [3.2]

4 [9.8, 7.6, 11.32]

 

Iteration 3

0 [1.8, 2.1]

1 [4.5, 6.5]

2 [1.1, 0.5]

3 [3.2]

4 [9.8, 7.6, 11.32]

 

Point 1.8 in cluster 0

Point 4.5 in cluster 1

Point 1.1 in cluster 2

Point 2.1 in cluster 0

Point 9.8 in cluster 4

Point 7.6 in cluster 4

Point 11.32 in cluster 4

Point 3.2 in cluster 3

Point 0.5 in cluster 2

Point 6.5 in cluster 1

 

 

Output File Contents

Point 1.8 in cluster 0

Point 4.5 in cluster 1

Point 1.1 in cluster 2

Point 2.1 in cluster 0

Point 9.8 in cluster 4

Point 7.6 in cluster 4

Point 11.32 in cluster 4

Point 3.2 in cluster 3

Point 0.5 in cluster 2

Point 6.5 in cluster 1