Emily's Hints for KMeans:
I found the assignment page fairly confusing, so I wrote up this to help you guys out.
- A lot of this assignment is already filled in. Read what is there carefully: the code and the comments.
- It would behoove you to create a toString() method for Gene and Cluster. This helps a ton with debugging.
- Also, you should write a test client and THOROUGHLY test each method in each class before moving on to the next. Think about edge cases. How would someone try to break your code?
1. Gene class
- .equals() and .hashcode() are one-liners.
- euclideanDistance() is simple; just follow the formula. How do we compute sums with code?
- spearmanDistance(); since we are in the Gene class, you can access other.exprRanks directly even though it is private. Alternatively, add a getter method to return exprRanks from an object of type Gene.
- You also need some type of transform for spearmanDistance(). The Spearman metric is always been (-1, 1), with 1 being perfectly correlated and -1 being anti-correlated. But you need to transform (-1, 1) into (2, 0) so that a larger value indicates more distance between two Genes, while 0 is perfectly correlated.
2. Cluster class
- What is a HashSet? What does <Gene> mean? Google Java HashSet and Java generic for some insight.
- There are some other instance variables that you can add to this class to make life easier. What might they be? Where do you need to increment/calculate them?
- The constructor is easy. Just initialize your HashSet and any extra instance vars you might add.
- centroid(): you need to pull out the expression values for each gene in this cluster, then average the expression for each experiment. This gives you a new array of values that are the mean expression for the whole cluster. Use this array to initialize a "dummy" Gene called "centroid" and then return it.
- addGene() is already filled out, but if you created new instance variables, this might be a good place to update them!
- createJPG(): don't touch this! It works just fine. All you need to understand is what arguments it takes and what it does.
3. KMeans class
- What is contained in the given instance variables? Hint: you don't need to create any more unless you really want to.
- Constructor: don't touch! It's good to go.
- main: How do you initialize a KMeans object? How do you run a clustering? How do you get information on the cluster out? Finally, how do you make a .jpg of each cluster? Hint: look at the commented out code at the bottom.
Step 1. initialize centroids randomly.
- Pick K random numbers between 0 and genes.length-1.
- Store these K genes in an array; these are your starting centroids.
- You only do this step ONCE!
Step 2. initialize/reset clusters.
Step 3. assign genes to the closest centroid.
- Just loop over each cluster, and set each one equal to a fresh, empty cluster.
- In the first iteration you are initializing the cluster, after that you are resetting them.
Step 4. recompute centroids.
- You need to take each gene, and look at all the clusters' centroids to determine which one is closest. How do we find a minimum in code? The distance metric will be either spearman or euclidean; this is passed as an argument to the performClustering() method.
- have some psuedo code:
for each gene i;
- mindist = Inf;
- for each cluster j;
- compute distance(gene, centroid of cluster j);
- if (distance < mindist)
- set j as new cluster for gene i;
- set mindist to distance;
- add gene i to cluster j;
- You have now filled each cluster with some number of genes. so you have to recompute the centroid. Luckily you have a method that does this!
- Why do you have to recompute the centroid?
CHECK LOOP CONDITION: newly recomputed clusters != old clusters (tip: don't compare the centroids; doubles don't have perfect precision!)
RETURN to step 2 if clusters have changed. (Why?)
If clusters have not changed, exit loop.