Classification and Clustering Tutorial

Contents

1. Correspondence or Principal Component Analysis.
2. Determine what variations are attribute or noise based.
3. Create Factor Maps .
4. Controlled Clustering and Hierarchical Classification.
5. Re-create certain images from eigenvectors.
6. Create "virtual" images from eigenvectors.
7. View dendrogram averages & factor (correspondence) map averages.
8. References.

Automatic Classification/Clustering -- General Steps

1. Execute CORAN or PCA
   • Create Orthogonal Vectors

     Run: 'CA S'

     Reads images.

     Carries out either PCA or CORAN analysis.

     Creates data files that are input for following steps.

2. Determine What Factors Are Important
   • Map

     Run: 'CA SM'

     Reads output files from: 'CA S'.

     Shows vector map of data: images, pixels, or eigenvectors

   • Clustering & Classification

     Run: 'CL CLA'

     Reads output files from 'CA S'.

     Finds clusters of data using Diday's method, then applys hierarchical ascendant classification (HAC), creates cluster membership file, and dendrogram plot.

     Run: 'CL HC' -- Alternative to 'CL CLA'

     Reads output files from: 'CA S'.

     Finds clusters of data using either single linkage, complete linkage, average linkage, the centroid method, or Ward's method to make a dendrogram plot.

     Run: 'CL KM' -- Alternative to 'CL CLA'

     Reads output files from: 'CA S'.

     Finds clusters of data using K-means method, then applys hierarchical ascendant classification (HAC), creates cluster membership doc. file.

     Uses the K-means method of clustering, no classification' to make a dendrogram plot for clusters.
   • Study clustering.

     Run: 'CL HD'

     Reads output files from 'CL HC' or 'CL KM'.

     Counts number of classes and images in each class, for a given threshold.

     Run: 'CL HE'

     Reads output files from 'CL HC' or 'CL KM'.

     Creates doc files describing which images in each class, for a given threshold.

3. View Images

   • Run: 'CA SR'

     Reconstitute images from eigenvalues & create "virtual" image from arbitrary eigenvector values

   • Run: 'CA SD'

     Create difference eigenimages.

   • Run: 'CA SRI'

     Reconstitute importance images.

4. Web Use
   • View Dendrogram and average images, for a given threshold
   • View the factor map/create average images regardless of class

Source Data

SPIDER procedures: makefaces.spi (and the face.spi procedure which it calls) were used to create the eight original faces below. The faces differ in three ways: oval vs. round head, left vs. right eyes, and big vs. small mouth. Ten copies of each face with random noise created the sample data set. These procedure files create four kinds of files. The scr* files are the face templates, seen here. The sma* files are the noise-filled data set, example below. The sca* files carry the average of the ten noise images for each template, and scv* hold the variance for each template.

Correspondence Analysis (CA) or Principal Component Analysis (PCA)

CA is the preferred method of finding variations and we will principally be discussing inter-image variance. PCA computes the distance between data vectors with Euclidean distances, while CA uses Chi-squared distance. This is superior because it ignores differences in exposure between images, eliminating the need to rescale between images.
The procedure file: cas.spi invokes the 'CA S' operation. The procedure file assumes you prefer CA and creates a user-defined circular mask. The procedure cas.spi also produces eigendoc.dat document file which contains listing of eigenvectors for each image for factors 1 and 2.

Hints for: 'CA S'

• The "Number of factors" requested should be larger than the expected number of variations. This is to see the characteristic slope of noise after the "useful" eigenvalues. Typically 10 should be more than enough for our example, but see 'CA S' for more detail.
• "Output file prefix" names all output files. A "Control" entry will result in "Control_SEQ", "Control_IMC, etc.

Description of Output Files (links lead to output from faces example)

• *_IMC is a text file that stores the coordinates of each IMAGE in the new vector space. The contents on the first line are:

  NUMIM	# of images included in analysis
  NFAC	# of factors requested, entry to "number of factors" question
  NSAM, NROW	X and Y values of images, respectively
  NUMIM	# of images included in analysis
  PCA	1 if PCA analysis was used, 0 if CA used

  There is a line for each image included. The contents of this line are:

  IMAGE(#)...NFAC)	Coordinates for each image, in the vector space. The number of entries depend on how many factors were requested.
  WEIGHTP	Relative weight of each image, = # of pixels in this image/# of pixels in all images
  DOR	Distance from the image to the origin of the new vector space
  FIM	# of the image. The first, 32nd, etc.
  ACT	Active image flag.

• *_PIX is a text file that stores the coordinates of each PIXEL. Very similar to *_IMC. The contents on the first line are:

  NPIX	# of pixels included in each image, determined by the mask
  NFAC	# of factors requested
  NSAM,NROW	X and Y values of images, respectively
  NUMIM	# of images included in analysis
  PCA	1 if PCA analysis was used, 0 if CA used

  There is a line for each pixel included. The outputs for this are:

  PIXEL(#)...NFAC)	Coordinates for each pixel, in the vector space. The number of entries depend on how many factors were requested.
  WEIGHTP	Relative weight of each pixel
  CO	Distance from the pixel to the origin of the new vector space
  FPIX	# of the pixel. The first, 32nd, etc.
  DUMMY	Unused

• *_EIG is a text file that stores the eigenvector values. The contents on the first line are:

  NFAC	# of factors requested
  TOTAL WEIGHT	Sum of all the pixels used. Not the # of them.
  TRACE	Sum of the diagonal of the eigenvector array
  PCA	1 if PCA analysis was used, 0 if CA used
  N	Number

  There is a line for each factor requested. The outputs for this are: variance is accounted for by eigenvalues

  EIGENVALUE	Eigenvalue, listed largest first.
  %	% of the total inter-image variance this eigenvalue is responsible for.
  CUMULATIVE %	Running tally of how much interimage

  If PCA was used there are additional lines. The outputs for these are: Average for this image or pixel

  AVERAGE(#)...N )

  %

• *_MAS is a SPIDER image file.
• *_SEQ is a binary file that stores all image pixel values within the mask from all the images. This file is NOT viewable in Web and is only useful internally to other 'CA' operations.
• *_SET is a binary file with transposed data. This file is only useful internally to 'CA' operations.

Determining Which Eigenvalues Are Useful, And Which are from Noise

1. Run: python eigendoc.py name_EIG.* > gnuplot_file
   where
   • name_EIG.* is the eigenvector output from CA S,
   • gnuplot_file is a file of gnuplot commands for displaying the histogram.
2. View file of gnuplot commands: gnuplot -persist gnuplot_file
   Note: The gnuplot output can be converted to a gif image using: gnu2gif

Creating Factor Maps to View Groupings, If Any

Once we know which eigenvectors have some meaning and which are noise, we can see if there are any clear clustering. 'CA SM' is an operation used to view 2D factor maps (graphs) of selected eigenvalues. Note that to view these maps you must have already run: CA S first.

• Input for: "IMAGE OR PIXEL COORDINATES" should almost always be "I", unless you are interested in "the images changing around the pixels". This also determines if 'CA SM' will read *_PIX or *_IMC .
• "File prefix" is the name entered for the "Outputfile prefix" in 'CA S'.
• "NUMBER OF HORIZONTAL PATCHES" Usually zero, UNLESS this particular CORAN analysis was done on a set of correlation patch averages.
• "(S)YMBOL, (A)SSIGN SYMBOL, (C)LASS, (D)OC, (I)D", "I" is typically the best choice.
• "PREPARE POSTCRIPT FILE FOR MAP" should usually be yes, unless you prefer an ASCII map like ascii12.dat.
• "FLIP #1" exchanges the map left-right. "FLIP #2" exchanges up-down."
• Everything after "Postscript output file" can generally be left as default values.

The procedure file: factor.spi invokes the SPIDER procedure: factor_casm.spi three times, creating three different factor maps using 'CA SM' and selecting different pairs of factors. 'CA SM' is run under the assumptions that you want image space with "id's" to create PostScript plots.

The three factor maps below were created from image (IMC) factor maps using GNUplot. Postscript files are similar.

Factor 1 vs. Factor 2 --- Factor 1 vs. Factor 3 --- Factor 2 vs. Factor 3

'CA SM' also works for pixel factor maps (PIX)as well. A common problem when creating a pixel factor map is the "ERROR: *** MAP ABORTED, MORE THAN 264 POINTS ON FRAME" error message. This is because of the large number of points. This can be fixed by increasing the value of ".NUMBER OF SD OR ≤CR>=2.3:". This increases the scale of the factor map. The pixel factor maps below were created from a screen snapshot. The large number of pixels located in the center show that most pixels vary little if at all between eigenvectors.

Factor 1 vs. Factor 2 --- Factor 1 vs. Factor 3 --- Factor 2 vs. Factor 3

The operation 'CL CLA' is limited in that it only uses Diday's and Ward's methods. 'CL HC' is more robust because the user controls the clustering criterion and can alter the "weights" for each factor. To best represent the "truth" set all factor weights equal to each other.

• "CORAN/PCA FILE" is the name of the file from 'CA S'. 'CL HC' can accept _IMC, _SEQ, or _PIX files. So this entry must include one of these endings to distinguish the kind of file.
• "FACTOR WEIGHTS" influence the clustering and the dendrograms. The larger the weight, the more importance a factor has as compared to the other factors. Zero sets all the rest of the factors to 1.0
• "CLUSTERING CRITERION". Option 5 is the method 'CL CLA' uses.
• A The output "DENDROGRAM DOC FILE" is used with Web to produce dendrograms with cluster averages. It is also used with the 'CL HD' and 'CL HE' operations to create document files listing the images assigned to each cluster.

The procedure: clhc.spi invokes 'CL HC' which reads the CA/PCA files from 'CA S' and creates dendroram plot files and document files.

Screen snaphots of the PostScript dendrogram from 'CL HC' for our "faces" data using clustering option 2 (complete linkage) and option 5 (Ward's method):

Dendrogram doc files affiliated with the above dendrograms:

Screen snapshot of Web display of the complete linkage dendrogram truncated at 20% level. Note that all of the images are properly seperated by head shape and eye direction. Mouth size is not so clear because it's eigenvalue is close to the eigenvalue for noise:

The operation 'CL HD' uses the dendrogram doc. file from 'CL HC' or 'CL CLA' to create a document file listing how many classes there for a given threshold and how many images there are in each class. This operation is similar to viewing the dendrogram in Web, setting a threshold, and recording the number of images and the number above each image.

The operation 'CL HE' uses the dendrogram doc. file from 'CL HC' or 'CL CLA' to create a series of class doc. files (e.g. class : 1) , listing which images are assigned to each class.

The procedure: clhe.spi invokes 'CL HD', 'CL HE', and then 'AS R' to threshold the dendrogram produced by 'CL HC' at a theshold of 66%, then average together the 20 images in each of the resulting classes. The class averages are then placed in a montage. The images are classified perfectly according to head shape and eye direction.

• "CORAN/PCA FILE PREFIX" is the response previously given for the "Output file prefix" question in 'CA S'.
• "CLUSTER OUTPUT FILE FOR CA SM USE" is the file to use with 'CA SM' to name image points by cluster. Not otherwise used in Web or SPIDER.
• 'CL CLA' uses the "moving center" method. Iterations are how many times the center is moved, and the centers per partition is how many points are initially used, per partition.
• "NUMBER OF INITIAL CLUSTERS" signifies the number of clusters 'CL CLA' will initally expect.
• "OCCUPANCY LEVEL FOR CLASS CUTTOFF" is the level or elements/images at which a class is not included in dendogram.
• The "DENDROGRAM POSTSCRIPT OUTPUT FILE" plot is useful to show the relationship between clusters/classes.
• The "PLOT CUTTOFF" can be used to truncate the lower edge of the dendrogram to remove excess branches.
• The "DENDROGRAM DOC. FILE" is used by the Web dendrogram operation and by: 'CL HE' and 'CL HD'.

The procedure: clcla.spi invokes 'CL CLA' to create a dendrogram plot containing an image of a PostScript dendrogram output. A vertical and horizontal line meeting signify the joining of two classes below it. A representitive reconstruction can be formed for each class with a 'CA SR' comand. The larger vertical bars signify a greater difference between classes. The many small differences at the bottom can be eliminated with an increase of the "% cutoff" command. The jpg file was obtained by using screen snapshot.

Examination Of K-Means Clustering

K-Means is a method of clustering that devides the data into a user defined number of clusters. Two random images "seeds" are chosen, and their centers of gravity are computed. A partition is drawn down the middle between the centers, the new centers of gravity are computed, and the process is repeated for a given number of times. The final result is VERY dependent on which image seeds are the first chosen.

Because our faces data set is manufactured. We know exactly which images are identical, except the random noise, and the exact number of clusters. The output discussed was obtained with 8 classes, using factors 1-3, and an even factor weight of 1.0 between those three factors. (NOTE: The results were from a data set with somewhat different noise from other runs discussed in this tutorial)

The doc file: IMC453doc.dat was produced by a run of 'CL KM' with the above input values with a random seed number of 453. The third column describes the image number and the fourth column is the class that 'CL KM' placed the image in. Images 1-10 were all placed in cluster 6, which is what we expect because they are all noisy images of the same protoimage. 'CL KM' kept the images from the same protoimage clustered together somewhat, except for the last ten images. However, it prefered to place images 11-20 and 31-40 in the same cluster, instead of each giving them each their own cluster. The average image for images 11-20 and 31-40 are shown below. They differ by their mouth size.

The doc file: IMC789doc.dat is a file from a 'CL KM' run exactly same as the previous, except with a random number of 789. Once again, most images were placed into the correct protoimage cluster correctly, except for the last few images. But in addition to images 11-20 and 31-40 being clustered together, images 1-10 and 21-30 were placed in the same cluster as well. This clearly demonstrates that K-means is highly dependent on the first image chosen, and should be used with extreme caution. Below are the average images for 1-10 and 21-30.

The doc files: SEQ453doc.dat and PIX453doc.dat are outputs from 'CL KM' being run on the same data as above, but using the SEQ and PIX files, respectively. The PIX453doc.dat file is 95Kb in size. The results for the SEQ run should be the same result as the previous runs, because it is still comparing images. However, the PIX results are expected to be different because it is trying to place the PIXELS in eight different classes.

• "CORAN/PCA FILE" must be the FULL name of the file you want to use (without the data extension), this is because it can input SEQ, PIX, or IMC files.
• "NUMBER OF CLASSES" = different clusters.
• "RANDOM SEEDSTARTING NUMBER", this should be made a note of, you are supposedly able to re-create runs with the same data and random number.
• "TEMPLATE FILENAME", for each class/cluster requested, 'CL KM' outputs a file with this prefix.
• DOCUMENT FILE,'CL KM' also returns one large file that tells the cluster assigned for each image/pixel used.

The procedure file: clkm.spi invokes 'CL KM' and created class averages for specified number of classes.

Re-creation of sample images from eigenvectors can eliminate the noise in the reconstituted image, this also results in large data compression. Below, is an image from our sample data set and four seperate reconstructions using the first four eigenvectors. The "halo" of noise and dark corners is a result of the masking function in the procedure files (face.spi and makefaces.spi) used to create this data.

It is difficult to see what traits the original image has because of noise. With the first three single eigenvalue reconstructions we can see that it has an oval head, with eyes looking left, and a small mouth. The fourth eigenvector does not "add" anything to our knowledge of the image because there are only three attributes that carry information. Threfore the fourth carries only noise.

Below is the sample image again, and a reconstruction from the first three eigenvectors combined. The image is from the 69'th prototype image shown in the source data area.

• "FILE PREFIX" is the response given for the "output file prefix" question from 'CA S'.
• "FILE #'S TO BE USED" = file numbers of images.
• "FACTORS TO BE USED" stands for which factors to be utilized in the reconstitution.
• "OUTPUT FILE TEMPLATE" needs at least one * at the end or it aborts program.

The procedure file: casr.spi invokes 'CA SR' to re-constitute any image, or images, from the eigenvectors.

Below we have the same "protoimage" images used to create the source data, a sample image from each protoimage,and we also have re-created the noisy samples using each eigenvector. The first row is the protoimages used to create the 80 sample images, and the second row consists of a sample image created from the protoimage above it. The third row is each sample image re-created with only the first eigenvector used. The next row includes the second eigenvector, and the last includes all relevant eigenvectors.

The operation: 'CA SRA' can create images or pixels that were not actually captured, using eigenimages. To do this, the eigenvalues must be given. This can be useful to interpolate images in between classes.
To choose what values to use for eigenvalues, use the factor maps. If you try to use a value outside the range of values for an eigenvalue, the results will be difficult to predict and interpret.

The images for eigenvector 1 equal to -0.1 and 0.1 are shown in the first two images. They "make sense" in that this vector controls headshape only. These values were chosen because they are the most extreme values shown on the factor maps. But the images for eigenvector 1 equal to -1 and 1,the last two images, do not represent "extreme" roundness like one might think. This is because these values are outside the range that they actually exist, i.e. the factor maps.

• To determine coordinate values, consult a factor map.
• Do not assume that a zero will fill the rest of the factor values to zero.
• See hints for 'CA SR' above.

The procedure file: casra.spi invokes 'CA SR'. The procedure file: casramontage.spi was used to create the image below.
The virtual images are created by changing only one eigenvalue at a time from -0.2 to 0.2 at regular intervals. The top row is eigenvalue one, and the bottom row eigenvalue three. Along each row all other eigenvalues were held to zero. The center column is identical because it is at this point that the varrying eigenvalues are equal to zero. Reconstitution with all eigenvalues set to zero is equivalent to reconstiting the average of the series. If reconstitution of each indiviual eigenvalue had progressed to one, the result would be the first three images directly above. Reconstitution of the three eigenvalues together will result in the fourth image above.

Viewing Eigenimages

The operation: 'CA SRE' creates eigenimages from 'CA S' outputs. With eigenimages, the user can easily see what the computer has determined as the factors to classify images by.

• None, see the manual page.

The procedure file:casre.spi invokes 'CA SRE'. It assumes that if you want more than one factor, they are continuous. Also assumes that you are using CORAN output. Both of these assumptions are in the procedure file, not the operation. Edit the procedure file to change them. Example results.

Use 'CA SRD' to see the different eigenimages that are used to recreate images.

The first image is the average among all 80 sample images. The next three are the difference image for each useful eigenvector for one image. The dark slivers in the first eigenvector image show that in order to obtain the correct head shape for this image, we must add black to either side of the face. Similarily, for the eyes we would make the left side of each eye socket brighter, and the right side darker. From the fourth image this image has a wide mouth .

Below are the seperate difference eigenimages for another image, as well as the combination of all three. This image has the opposite of every trait of the image represented above. We can tell because of white slivers on a dark background, right-hand side of the eyes light, etc. The last image below is the composite of the first three eigenimages.

Below is the average of all the images as well as the composite difference eigenimage from above. When we add (superimpose) these together we get the third image, a re-creation of the original sample image. However, the re-creation has no noise. This is because we only used the first three eigenimages. If we included the other five, then we would have re-created the sample image, with noise.

Hints for: 'CA SRD'

• "PREFIX" is the base name before _SEQ, _IMC, _PIX, etc.
• An entry out of bounds has no useful purpose.
• See hints for 'CA SR' above.

The procedure file: casrd.spi invokes 'CA SRD'. Note that it is similar to casr.spi except for minor changes.

Subgrouping images

Use 'CA SMI' to separate a series of images into active/inactive clusters. It appears that this can actually perform operations on a series of images using the 'CA S' files from another series. This has not been tested. If the images used in 'CA SMI' will be used with their 'CA S' run, it is a good idea to create a Postscript map before running 'CA SMI' for comparison later.

Hints for: 'CA SMI'

• Only supports image input and _IMC output?
• If using images with their "native" 'CA S run', be sure to compare the Postcript maps of before and after 'CA SMI'. If they are not very similar, you must re-run 'CA S' with "CN" instead of "C" as the fifth input.
• After 'CA SMI', if an odd factor is chosen in 'CA SM', it's axis may be flipped.
• If using this to force certain images, from the same series, standout on a factor map (one class inactive, all others active), use 'CA SM' with (S)ymbol option (it's quicker).

The procedure file: casmi.spi invokes 'CA SMI'.
Below are the 'CA SM' maps with no 'CA SMI' input, and below those maps with 'CA SMI' input. Note the labeled images are the same in all three, but the axis switch with an odd numbered factor. This axis switch is caused by using non-transposed data set. In order to have 'CA SMI' run on this data, forced 'CA S' to not transpose the data, with the "CN entry". Because of this, 'CA SM' reads in the images different from the transposed data. Be sure to take note of axes if using 'CA SMI' -> 'CA SM'

Factor 1 vs. Factor 2 --- Factor 1 vs. Factor 3 --- Factor 2 vs. Factor 3

Factor 1 vs. Factor 2 --- Factor 1 vs. Factor 3 --- Factor 2 vs. Factor 3

View Dendrogram In Web

Web can be used to view a dendrogram of the data instead of using CL CLA. Should also work with the output of CL HC. Web will display not only a usual dendrogram, but also the average of all the images below a threshold, and the number of images in each average.

1. Run 'CL CLA' (or 'CL HC'), and request a dendrogram doc file.
2. Make sure that your image files and dendrogram doc file have the same extension and are in the same folder, it's easier.
3. Start Web with your extension (i.e."Web dat &") and select Command -> image from the menus to navigate to where the images and cluster files are. Press "OK".
4. Commands -> Dendrogram and select the cluster file.
5. When the Dendrogram window pops up, to see all of what you selected, choose lowest threshold option. All the variation that was carried over from the 'CL CLA' or 'CL HC' operation is scaled from what the lowest level selected to +1 above.
6. If the "Show average images" option is selected, Web will show the average of the lowest level shown. This is why having the images in the same folder as the dendrogram doc file is easier.

The procedure file: webdendro.spi invokes 'CL CLA' so that a new dendrogram document file is the only thing created, used to change the lower threshold.
The document file: webdendoc.dat is an example of a dendrogram document file.

The procedure file: rename.spi can be used to change the extensions of a whole series of images. Should not be a problem if follow hint number three above.

View Factor (Correspondence) Map In Web and Compute Averages

In Web you view a factor map and select which images are similar using a "lasso" interface. Then the average of that class is computed and can be viewed or stored as a new image. Also, a SPIDER document file can be printed to what class each image was placed in. I believe that only images can be used, not pixels.

1. Run the 'SD C' command in SPIDER.
2. Start Web with your data file extension (i.e."Web dat &") and use the command -> image and "accept" to navigate to where the cluster file is.
3. If you are going to make image averages, the data files and the 'SD C' doc. file should be in the same folder and have the same extension. It is easier.
4. In Web, Commands -> Corr-map. Explanation of window options.
5. When you "accept", a Web window will appear, with either numbers or circles representing the images, depending on the "show image numbers" toggle.
6. "Lasso" a group of images with the left mouse button, and after completely enclosing the intended images, press the center button. A new window will appear.
• "Save images in Doc file" will open another window. From this new window you can name the file, and specify which registers carries the X co-ordinate, Y co-ordinate, and the order of that particular group created during the run of Corr-map. The first register always is the image number. Please remember that the X and Y co-ordinates are actually the values of the eigenvectors that was specified during the begining of corr-map.
• "Display avg. image" will show an average of all included images on the screen. It will not save that image. The "overlap" toggle controls where the average is displayed.
• "Store avg. image" will save the average of the selected images, but it will not be displayed on the screen.
• "New masking" will return you to the image factor map.
• "Continue masking" will do the same as new masking, except all the selected image markers will be shadowed in green. Useful to see what image markers have already been catagorized.
• "stop mapping" ends the corr-map function
7. Continue selecting image markers with new/continue masking until satisfied. Note that one image can be in many different groups.

The doc. file: sdcout.dat is the result of running 'SD C' on a _IMC file. It lists the image number and factor co-ordinates of each image.

The image: corrmap.gif is a screen-shot of a corr-map run. Note the placement of the average images. The upper-right image is overlapped with it's respective mask. We can also see what two traits were being compared in this factor map, head shape and eye direction.
docimg001.dat is the file created with the "save images in Doc. file" option. It lists the image number, X and Y co-ordinates and the order of class it was formed from. This particular class was the third formed, but the first image document list.

• SPIDER image processing for single-particle reconstruction of biological macromolecules from electron micrographs.
  Nature Protocols 3, 1941-1974 (2008)
• Three-Dimensional Electron Microscopy of Macromolecular Assemblies
  Oxford University Press, (February 2006)

Source: tutorial.html     Last update: 19 June 2009