CS434 — Implementation Assignment 4 — Due 11:59PM -, 2020

General instructions.

1. Please add onto the Python starter code (version 3.6+). Note: you may need to install several packages

(pip install –user), but try not to require anything else. I’ll run it with the packages already there,

and you should have everything you need. (Things like ’os’ are fine though if they’re packaged with

Python 3.6).

2. You can work in a team of up to 3 people. Each team will only need to submit one copy of the source

code and report. You need to explicitly state each member’s contribution in percentages (a rough

estimate).

3. Your source code and report will be submitted through Canvas

4. You need to submit a readme file that contains the commands to run your code for requested experi-

ments (e.g. python main.py args).

5. Please make sure that you can run code remotely on the class server ( vm-cs434-1 ).

6. Be sure to answer all the questions in your report. You will be graded based on your code as well as

the report. In particular, the clarity and quality of the report will be worth 10 pts. So please

write your report in clear and concise manner. Clearly label your figures, legends, and tables.

7. In your report, the results should always be accompanied by discussions of the results. Do

the results follow your expectation? Any surprises? What kind of explanation can you provide?

1

Unsupervised Learning for Human Activity Recognition

(total points: 80 pts + 10 report pts + 10 result pts)

In this assignment we will work with the Samsung Human Activity Recognition dataset to practice un-

supervised and also dimensional reduction methods. More specifically we are interested in applying k-means

clustering and Principal Component Analysis (PCA) methods.

The data for this assignment comes from accelerometers and gyros of Samsung Galaxy S3 mobile phones.

Each instance in the dataset is a set of feature values extracted from sensor signals and pre-processed to

classify the type of activities a person has with his/her phone in his pockets. There are six activities WALK-

ING, WALKING UPSTAIRS, WALKING DOWNSTAIRS, SITTING, STANDING, LAYING.

The label of each instance (type of activities) are given, however we assume that they are unknown and thus we

try to apply an unsupervised k-means clustering to cluster the people based on the available features. We only use

the labels to evaluate the clusters with purity measure.

Data. The specifications of the datasets is as follows:

1. (x train.txt): Contains 7352 rows (samples) each with 561 features.

2. (y train.txt): Contains 7352 rows of labels corresponding to the rows in the (x train.txt).

Important Guidelines. Please note that a skeleton code (starter) is provided and the students should only fill

the code where is specified.

2

Part 1 (50 pts) : k-means clustering. For this part please implement the following steps in the starter

skeleton:

1. Please fill the places marked in the “clustering” module to complete the k-means class. In method “init-center”

the center of clusters will be initialized. You don’t need to implement a sophisticated method to initialize the

clusters. A random selection from the input instances will be sufficient. If you implement method “predict”

efficiently (using vector based operations) the running time will reduce significantly.

2. The k-means class will be used in module main. In this assignment we only consider value 10 as the maximum

number of classes. The maximum number of iterations is set to 20 by default, however we might need more

iterations until the k-means converges. Please update function ”apply-kmeans“ of main as follows:

• To reduce the sensitivity of the k-means to the initialization, update this function to produce the average

of SSE and purity vs k and iterations for 5 different runs of k-means. Note that each run should generate

different initial centers in method “init-center”.

• Plot the average (over 5 runs) of SSE versus iterations for k = 6. You could use the plot functions

provided in the main or change them if needed to show the observation more properly.

• Plot the average (over 5 runs) of the SSE versus k for k ∈ 1 . . . 10. Apply elbow on the curve of SSE

versus k for k ∈ 1 . . . 10, to select the best k. Please report the best k you found.

• Plot the average of purity versus k for k ∈ 1 . . . 10 for the train set and make observation on this.

Part 2 (40 pts) : dimension reduction (PCA). In this part we are interested in reducing the dimension

of the data (which is currently 561) to a smaller number. Please implement the following steps:

1. Implement the marked area in module ”decompose“ to implement the PCA class. In your implementation

please use the mean, cov and eig functions provided in the class.

2. In the main module, complete the ”visualize“ function to visualize the data points in the first two principle

component directions, and color each class with a distinct color.

3. The retain ratio r is the percentage of variance we are interested to maintain and is defined as follows:

d∑

i=1

λi ≥ r ×

m∑

i=1

λi (1)

where d and m are the reduced and original dimensions respectively and d ≤ m . By default this value is set

to 0.9. Please report the d you will find for this ratio.

4. Apply the k-means for k ∈ 1 . . . 10 described in part 1 (average over 5 runs) on the data with reduce dimension

for retain ratio r = 0.9. Plot the purity of the train for this experiment. Do you observe harmful effect due to

dimension reduction. If it hurts the purity, please increase r to a higher values (with a 2 or 3 trials) and report

the best r which still reduces the dimension but does not hurt the performance.

Submission. Your submission should include the following:

1. The modified source code with a short instruction on how to run the code for your experiments in a readme.txt.

2. Your report (only in PDF format), which begins with a general introduction section, followed by one section

for each part of the assignment.

3. Please note that all the files should be in one folder and compressed only by .zip.

3