DSME6650: Data Mining for Managers Assignment 1 Due Date: 23:59 Jan.19, 2020 Submission Instruction: For this assignment, please submit electronic version only. For the programming questions, you need to submit BOTH your Python codes and your results. Submit codes as zipped tar file and the output of your program in plain-text file. For other questions, answer them in a word document. You should place the relevant files in their separate directory (preferable A and B for each part). After that, please compress all your files as one zip named using your student id, e.g., 11xxxxxxxx.zip, and submit to Blackboard. Part A. Clustering The following problem is based on lecture 5. 1. Practice the K-means algorithm using Manhattan distance. Suppose there are 15 data points: • A1(1.0, 1.0), A2(1.0, 2.0), A3(2.0, 0.0), A4(2.0, 3.0), A5(5.0, 10.0), • A6(5.0, 12.0), A7(6.0, 2.0), A8(6.0, 4.0), A9(6.0, 10.0), A10(7.0, 2.0), • A11(7.0, 5.0), A12(9.0, 9.0), A13(10.0, 7.0), A14(10.0, 9.0), A15(11.0, 8.0). Assume we cluster these 15 data points into 4 clusters. The initial seeds are A1, A5, A7, A12. (1) Please draw all data points and the initial seeds in a figure with grid line in the range of x: [0, 12] and y: [-2, 14]. (2) After running the K-means algorithm for 1 epoch only, answer the following questions one by one: a. The new clusters (i.e., the examples belonging to each cluster) b. The centers of the new clusters c. How many more iterations are needed to converge? Please write down the final centers and plot the results. (3) If we use A7, A8, A10, A11 as initial seeds, how many more iterations are needed to converge? Please write down the final centers and plot the results. (4) If we apply K-mean++ to the data and choose A1 as the first seed, which point will have the highest probability to be chosen as the second seed? For these problems, write down your answers for all questions in the word file. For question (2), (3) and (4), you need to write a program to simulate the process of K-means and put your codes in directory A which will be zipped into the final submitted file. Please note that you should write a README.txt file (in the directory A), which indicates how to run the program to get the results you provided (hyper-parameters of the model should be given if needed). Without an appropriate README.txt will be deducted certain scores. Part B. Graph Representation The following problem is based on lecture 6. Figure 1: Figure for Graph Analysis. Given a small graph shown in Fig. 1, please answer the following questions: 1. Compute the adjacency matrix, the degree matrix, the unnormalized Laplacian matrix, and the normalized Laplacian matrix. 2. You are required to implement a Spectral Clustering method to cluster the clusters of the given graph (k=2) on both unnormalized and normalized Laplacian matrix. For question 1, write down your answers in a word file. For question 2, you need to write a program to simulate the process of spectral clustering and put your codes in directory B which will be zipped into the final submitted file. Please note that you should write a README.txt file (in the directory B), which indicates how to run the program to get the results you provided (hyper-parameters of the model should be given if needed). Without an appropriate README.txt will be deducted certain scores.
