INPUT FILE VALUES
1.8 4.5 1.1 2.1 9.8 7.6 11.32 3.2 0.5 6.5
Introduction Clustering is a process of identifying groupings (i.e. clusters) within the data. For example, the figure below shows three clusters of two-dimensional data points (X's): XX XX x x x X XX XX X XXX x x x X X x x X 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 p and q as d(p. 4) = 1p-91 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: Asks the user for the number of clusters. This is the parameter k that will be used for k-means. 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 kmeans.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 to use meaningful identifier names that conform to standard naming conventions. 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. 4. 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 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. Sample Program Output DATA-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.51 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 o Point 4.5 in cluster 1 Point 1.1 in cluster 2 Point 2.1 in cluster o 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 Point 4.5 in cluster 1 Point 1.1 in cluster 2 Point 2.1 in cluster o 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 Step by Step Directions # 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] -crcate and initialize another variable to store all points for cach cluster: a mapping (dict) of range(k) to k cmpty lists -usc 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: a) Save current point assignment into old point assignment variable (create a new dict from current assignment variable) b) Place cach point in the closest cluster (you should make a function that docs this) c) Update the locations of centroids of the k clusters (make a function for this also) 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(zipirange(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 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: 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 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_assignmentslj] = closess_index 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. d) Reinitialize the clusters variable to empty lists clusters = dict(zip (range (k), [[] for ; in range (k))) # Output 6. Print the point assignments Go through all values in point assignments and print them
