Description
Assignment Goals
- Implement hierarchical clustering
- Process real-world data of particular contemporary relevance
Summary
There is a lot of analysis happening with the various datasets for COVID-19 right now. One of the goals of these analyses is to help figure out which countries are “beating” the pandemic.
Using the publicly available Johns Hopkins COVID-19 data, you’ll be performing clustering on time series data for different regions in the world. Each region is defined by a row in the data set, which can be a country, a province, etc. The time series data represents the number of (cumulative) confirmed cases on each day. Because different regions have different onset of the outbreak and differ in magnitude, it is often desirable to convert a raw time series into a shorter feature vector. For this assignment, you will represent a time series by two numbers: the “x” and “y” values in the above ten-hundred plot video. After each region becomes that two-dimensional feature vector, you will cluster all regions with HAC.
Program Specification
Download the data in CSV format: time_series_covid19_confirmed_global.csvDownload time_series_covid19_confirmed_global.csv
This is a snapshot of the data from the morning of April 2, 2020. If you wish to test your code on current data, the Johns Hopkins University git repoLinks to an external site. has constantly-updating data, but we will only be testing your code with the snapshot.
Write the following Python functions:
- load_data(filepath) — takes in a string with a path to a CSV file formatted as in the link above, and returns the data (without the lat/long columns but retaining all other columns) in a single structure.
- calculate_x_y(time_series) — takes in one row from the data loaded from the previous function, calculates the corresponding x, y values for that region as specified in the video, and returns them in a single structure.
- Notes:
- The “n/10 day” is the latest day with LESS THAN OR EQUAL TO n/10 cases, similarly for the “n/100 day”.
- If “n/10 day” is day i, and today is day j, then x=j–i, not j-1+1.
- Some x or y can be NaN if the time series doesn’t contain enough growth.
- There is a link to Matlab code in the video description on YouTube, please consult that for the precise definition of x and y.
- Notes:
- hac(dataset) — performs single linkage hierarchical agglomerative clustering on the regions with the (x,y) feature representation, and returns a data structure representing the clustering.
You may implement other helper functions as necessary, but these are the functions we will be testing.
Load Data
Read in the file specified in the argument (the DictReader from Python’s csv moduleLinks to an external site. will be of use) and return a list of dictionaries, where each row in the dataset is a dictionary with the column headers as keys and the row elements as values. These dictionaries should not include the lat/long columns, as we will not be using them in this program, but retain the province (possibly empty) and country columns so that data points can be uniquely identified.
You may assume the file exists and is a properly formatted CSV.
Calculate Feature Values
This function takes in the data from a single row of the raw dataset as read in the previous function (i.e. a single dictionary, without the lat/long values but retaining all other columns). As explained in the video above, this function should return the x, y values in a tuple, formatted as (x, y).
Perform HAC
For this function, we would like you to mimic the behavior of SciPy’s HAC functionLinks to an external site., linkage(). You may not use this function in your implementation, but we strongly recommend using it to verify your results!
Input: A collection of m observation vectors in n dimensions may be passed as an m by n array. All elements of the condensed distance matrix must be finite, i.e. no NaNs or infs. If you follow the Matlab code from the YouTube video description, you will occasionally have NaN values — such rows should be filtered out within this function and should not count toward your total number of regions.
In our case, m is the number of regions and n is 2: the x and y features for each region.
Using single linkage, perform the hierarchical agglomerative clustering algorithm as detailed on slide 19 of this presentationLinks to an external site.. Use a standard Euclidean distance function for calculating the distance between two points.
Output: An (m-1) by 4 matrix Z. At the i-th iteration, clusters with indices Z[i, 0] and Z[i, 1] are combined to form cluster m + i. A cluster with an index less than m corresponds to one of the m original observations. The distance between clusters Z[i, 0] and Z[i, 1] is given by Z[i, 2]. The fourth value Z[i, 3] represents the number of original observations in the newly formed cluster.
That is:
- Number each of your starting data points from 0 to m-1. These are their original cluster numbers.
- Create an (m-1)x4 array or list. Iterate through the list row by row.
- For each row, determine which two clusters you will merge and put their numbers into the first and second elements of the row. The first point listed should be the smaller of the two cluster indexes. The single-linkage distance between the two clusters goes into the third element of the row. The total number of points in the cluster goes into the fourth element.
- If you merge a cluster containing more than one data point, its number (for the first or second element of the row) is given by m+the row index in which the cluster was created.
- Before returning the data structure, convert it into a NumPy matrix.
If you follow these guidelines for input and output, your result should match the result of scipy.cluster.hierarchy.linkage() and you can use that function to verify your results. Be aware that this function does not contain code to filter NaN values, so this filtering should be performed before calling the function.
Tie Breaking
In the event that there are multiple pairs of points with equal distance for the next cluster:
Given a set of pairs with equal distance {(xi, xj)} where i < j, we prefer the pair with the smallest first cluster index i. If there are still ties (xi, xj), … (xi, xk) where i is that smallest first index, we prefer the pair with the smallest second cluster index.
Be aware that this tie breaking strategy may not produce identical results to scipy.cluster.hierarchy.linkage().
Challenge Options
If you wish to continue exploring the data, we challenge you to implement a complete linkage option and compare the results with single linkage. You may also wish to use the results of your HAC algorithm to choose an appropriate k for k-means, and implement that clustering as well. Do you get the same clusters every time? If not, how do they differ? Is there anything meaningful there, do you think?
Submission
Please submit your code in a file called ten_hundred.py. All code should be contained in functions or under a
if __name__=="__main__":
check so that it will not run if your code is imported to another program.
