The objects for this week's lab are to provide a sampling of common tasks that fall under traditional machine learning. Specifically, you will obtain experience and an understanding for:

• parsing large biological data sets
• implementing a clustering algorithm (k-means)
• implementing a classification algorithm (k-nearest neighbors)
• experimental methodology/evaluation metrics for unsupervised learning
• experimental methodology/evaluation metrics for supervised learning
• analyzing gene expression data

Your lab will be broken down into two programs: clustering yeast genes based on their expression values over several experiments and classifying leukemia patients based on their expression values for a set of genes.

For this portion of the lab, you will implement k-means clustering and test it on expression data set of the yeast genome. To be reusable in the future, you should create a library file clusterAlgos.py which should contain a general k-means formulation as well as functions to evaluate clusters based on various criteria. You should design a distance function. Your main program should be in a file named yeastCluster.py

Input

A user will enter three arguments on the command-line:

1. k, the number of clusters to use (integer)
2. the name of the file containing the instances
3. (optional)the name of a file containing annotations about each instance. If this is not provided, instances should indexed by their line number in the original file.

The data file will contain one instance per line and will be in comma separated format. There is a sample taken from class in class.csv.

For your main test, refer to the following paper:

Michael B. Eisen, Paul T. Spellman, Patrick O. Brown, and David Botstein. Cluster analysis and display of genome-wide expression patterns. PNAS 1998 95 (25) 14863-14868

In particular, take a look at the publicly available data set and associated key for column headers. I have provided a pre-processed sample of the data in your update directories. small-yeast.csv contains the expression values for 52 genes, one gene per line while full-yeast.csv contains the expression values for all 2467 genes in the original data set. Each file contains a companion gene identification file that contains the gene name and also the annotated functional assignment of that gene to help validate clusters. These two files (full-yeast-names.txt, sample-yeast-names.txt) contain the names of each gene which will help you identify the genes in a cluster. The list of gene names is an example of the optional command-line argument. It is not used in the actual algorithm, but is used when printing out cluster members to better understand the results.

Algorithm

You should implement the standard k-means clustering algorithm discussed in lecture. Additional requirements/design choices:

• You should utilize Manhattan distance to measure the distance between instances
• You should run k-means until convergence, or 50 iterations, whichever comes first.
• You should initialize each cluster by picking a random point from the data set. Also, if a cluster ever has 0 members, you should randomly assign the centroid to an instance in the data set.

Output

Your program should output the following:

• In a file titled kmeans.out, write the number of clusters on the first line. After that, you should have k sections. The first line of each section should contain the value of the cluster centroid (the mean value learned). After that, print a list of the gene names for all genes that belong to that cluster, each on its own line. When you transition to a new cluster leave a blank line. If no gene name file is provided (for example, the
• On standard output, indicate the sum of squared errors across all clusters using the formula from class:
• On standard output, indicate the AIC measure of error of your clustering results
• On standard output, indicate the Silhouette Index of your cluster result. The Silhouette index for one data point is:
  
  
  
  where b(x_i) is the average distance to members of the closest cluster (simply calculate the distance from x_i to all cluster means mu_j except the one x_i belongs to and select the smallest) and a(x_i) is the average distance to the members of the same cluster (not including x_i). After calculating all s(i)s, the total Silhouette Index is:
  
  More details can be found here.

Experimental methodology

For both the small and full yeast data set, test your program on a reasonable range of possible values for k. Then, in a separate file (results.{doc, pdf}), provide the following:

• For the small yeast data set, provide a table of results for each k value you tested. Each row should represent one value of k and each column represents the 3 metrics above (SSE, AIC, Silhouette Index).
• In a paragraph, discuss what value(s) of k are would be best to choose and what measures lead you to that choice. Justify your choice using both the measures above as well as external validation (the names of each gene include a short description of their functional category). How useful are the validation metrics?
• Provide a paragraph description of how the Eisen et al. paper validated their results. That is, how did they justify their clustering algorithm as being informative?

Sample Results

For the example from class:

$ python yeastCluster.py 2 class.csv
Clustering using k-means with k=2

SSE: 7.33
AIC: 15.33
Silhouette: 0.85

The output file called kmeans.out should like this. For the yeast example:

$ python yeastCluster.py 2 sample-yeast.csv sample-yeast-names.txt
Clustering using k-means with k=2

SSE: 37115.38
AIC: 37431.38
Silhouette: 0.36

and the corresponding output file kmeans.out.

NOTE: since k-means is locally optimal and there is randomness in the starting point, your results may vary. You should get similar results if you run your method a few times.

For this portion of the lab, you will implement the supervised learning algorithm k-nearest neighbors, and employ appropriate experimental methodology to estimate the accuracy of your algorithm. As with the above problem, you should use good design skills by creating a library for classification algorithms in the file classifiers.py and put your main program in the file leukemiaClassifier.py.

Input

A user will input two arguments to run your program in the following order:

1. k, the number of neighbors to consider
2. The file name of the training set.

I originally designed this lab to have you utilize a tuning set to pick k, but cut that out for brevity. If you choose to implement that as an extension, you can omit the first command-line argument.

Your data set comes from the paper referenced in class for using expression analysis to differentiate cancer patients:

T.R. Golub, D.K. Slonim, P. Tamayo, C. Huard, M. Gaasenbeek, J.P. Mesirov, H. Coller, M. Loh, J.R. Downing, M.A. Caligiuri, C.D. Bloomfield, and E.S. Lander, D. Molecular Classification of Cancer: Class Discovery and Class Prediction by Gene Expression. Science, 286(5439):531-537. 1999.

The data has been made available in your labs directory in the file titled leukemia.csv. Each line describes the expression values of one patient. Each column (except the last) is the expression value for one gene. Details can be found here. The last column is the class for the sample: -1 for acute lymphoblastic leukemia (ALL) and 1 for acute myeloid leukemia (AML).

Algorithm

You are to implement the standard k-nearest neighbors algorithm discussed in lecture. To guide your algorithm design, follow these tips/requirements:

• Utilize Euclidean distance
• For a voting scheme, use weighted distance:
  
  .
  
  Where y'_i is prediction for test sample x_i; c is the possible class assignments (i.e., +1, -1); I(x) is 1 if x is true and 0 otherwise; and the last term provides the weight, or influence, of nearest neighbor j.

Experimental Methodology

To provide an accurate estimate of classifier error, we must validate the algorithm on a separate set of data than used for training. As discussed in class, a typical methodology to accomplish this while utilizing all of the data is to use n-fold cross validation as your strategy. You should use 5 folds for this lab. You do not need to worry about using a tuning set as we will assume k is set by some external piece of information.

To perform proper cross-validation, each example should appear in the test set in exactly one fold, no more no less. When not in the test set, it should be in the training set for the fold. In addition, the relative size of each training/test set split should be about the same for each fold (since 72 is not evenly divisible by 5, 3 of your test sets will have 14 data points and 2 will have 15). Some methodologies also balance the ratio of positive to negative examples in the test set, but we'll skip that for this lab.

In Python, you should utilize the shuffle command. The following pseudocode should provide guidance. I assume the entire data set is in a two-dimensional list title origData.

generateCVData(numFolds, origData):
  indexList = list of numbers from 0 to N-1
  random.shuffle(indexList) #list of integers all shuffled up

  shuffledData = empty list
  for each index in indexList
     append origData[index] to shuffledData

  foldSize = N/numFolds

  for each fold k:
    leftEnd = k*foldSize
    rightEnd = (k+1)*foldSize
    testFold[k] = shuffledData[leftEnd:rightEnd]
    trainFold[k] = rest of shuffledData #items before left end and after right end

  return [trainFolds, testFolds]

Note that you'll have to deal with floats and ints for fold size and index range formulas. Also, be careful of Python's negative indexing for lists. Note that you will only need to run this function once as it generates all of the folds for you. There are many ways to perform cross validation, this is just one.

Output

You should maintain the cumulative counts of true positives (TP), true negatives (TN), false positives (FP), and false negatives (FN) across the folds. That is, for five fold cross-validation, sum the number of true positives for each fold to obtain the final true positive count. The output of your program should include the following measures of error:

• Accuracy
  
  
• Sensitivity (number of correctly labeled positives divided by total number of positives in the original data set):
  
  
• Specificity (number of correctly labeled negatives divided by total number of negatives in the original data set):
  
  

Here, positive refers to AML (class 1) and negative refers to ALL (class -1). N is the total number of test examples which is simply the size of the input data set.

Sample Results

In your directory, you'll find a toy data set titled simple.csv. A sample run with k=2 and 5-fold cross-validation produces the following output:

$ python leukemiaClassifier.py 2 simple.csv
Classification using k-nearest neighbors with k=2 and 5 folds

Results:

Accuracy: 0.80
Sensitivity: 0.67
Specificity: 1.00

To help with debugging, take a look at the intermediate values produced by the algorithm. Note that randomization may produce a different ordering for your the folds. However, since 5-fold cross validation is the same as leave-one-out in this example, you should have the same exact results just in a shuffled ordered of folds.

A sample run with the leukemia data set would look similar to:

$ python leukemiaClassifier.py 5 leukemia.csv
Classification using k-nearest neighbors with k=5 and 5 folds

Results:

Accuracy: 0.93
Sensitivity: 0.86
Specificity: 0.98

Your results will differ as the folds are determined randomly.

When you are finished with your lab, submit your code using handin68.

Home Page