Imaging and Visualisation Systems

P.Tino@cs.bham.ac.uk

Taught jointly with Bob Hendley

Lecture Timetable and Handouts

Here is a preliminary outline of the structure and lecture timetable for my part of the module. I will develop most of the ideas on the blackboard. You are encouraged to take notes during the lectures. Any handouts used will be made available here as pdf files shortly after the paper versions have been distributed.

Week	Session 1 Tuesdays 10:00-11:00	Session 2 Thursdays 12:00-13:00
1	B. Hendley	B. Hendley
2	Dimensionality reduction of vectorial data. Basic concepts of vector and matrix algebras.	B. Hendley
3	Linear models. Principal Component Analysis I.	B. Hendley
3	Principal Component Analysis II.	B. Hendley
4	Nonlinear methods. Self-organizing topographic maps I.	B. Hendley
5	Self-organizing topographic maps II.	B. Hendley
6	Probabilistic approaches. Basic probability and statistics.	B. Hendley
7	Latent-space reformulations of topographic maps. Generative topographic mapping.	B. Hendley
9	Enhancing the information content of visualisation plots.	B. Hendley
10	Hierarchical visualisation	Fractal Images. Iterative function systems.
11	Mandelbrot and Julia sets.	Fractal modelling of real world objects.

Useful Links

• XGobi - a system for multivariate data visualization
• HiSee - a software package for visualizing high-dimensional datasets
• Laboratory for Information Visualization and Evaluation at Virginia Tech
• Information Visualization Resources on the Web
• Latent Semantic Indexing
• Matrices, Vector Spaces and Information Retrieval by Michael W. Berry, Zlatko Drmac, Elizabeth R. Jessup.
• WEBSOM - Self-Organizing Maps for Internet Exploration
• Class Visualization of High-Dimensional Data with Applications. by Inderjit Dhillon, Dharmendra Modha, Scott Spangler, 1999. Free Software is available here.
• University of Maryland VANGOGH Laboratory
• Artificial life
• ANIMALAND

Suggested reading + software

• Principal Component Analysis
- Bishop: Section 8.6, Appendix E
- tutorial by Lindsay Smith: soft introduction to PCA with elementary vector and matrix algebras


• Self-Organizing Maps and Vector Quantization
- Haykin: Sections 9.1 - 9.11
- Web page devoted to SOM
- Data exploration using self-organizing maps by S. Kaski [ps.gz]
- Data Mining Techniques Based on the Self-Organizing Map by J. Vesanto [zip]
- Interactive SOM demos in Java by J. Hynninen
- SOM Toolbox for MATLAB
- software implementations of SOM
- SOM-based World Poverty Map
- Self-Organizing Map Training Visualization



• Fractals
- Flake: Sections 7 and 8
- Fractal Image Compression and the Inverse Problem of Recurrent Iterated Function Systems by John C. Hart
- Interactive IFS Fractals
- Julia and Mandelbrot Set Explorer
- Mandelbrot Set at University of Utah
- Introduction to the Mandelbrot Set
- Mandelbrot Explorer
- fractal terrain generator by Stephen Booth
- Spanky Fractal Database
- brazil_fractal_builder
- Fractal Frequently Asked Questions
- Art and Fractals

Assignment - hand in during revision lectures on May 3 and May 5

Make yourself familiar with my implementation (in C) of SOM. You are very welcome to use your own implementation, or download a working code from the web.
Un-tar the file som.tar.gz and go to the folder "SOM".
The subfolder "SOURCE" contains the c-implementation of som, "som.c".
There is an example in the folder "GAUSS.2D". Please consult the "read.me" file there.

You can chose any data set(s) from the list bellow.
Un-tar the relevant file and go to the corresponding folder.
The folder contains the data set, as well as additional information about the data. Read the available information, especially description of the features (data dimensions).
You will need to clean the data, so that it contains only numerical features (dimensions) and the features are space-separated (not comma-separated.

To make the plots informative, you should come up with a labelling scheme for data points.
If the data can be classified into several classes (find out in the data and feature description!), use that information as the basis for your labelling scheme. In that case exclude the class information from the data dimensions.
Alternatively, you can make labels out of any dimension, e.g. by quantising it into several intervals. For example, if the data dimension represents age of a person, you can quantise it into 5 labels (classes) [child, teenager, young adult, middle age, old].
Associate the data labels with different markers and use the markers to show what kind of data points get projected to different regions of the visualization plot (computer screen).

• Learn as much as you can about an assigned data set(s) using visualization methods developed in the module, namely PCA and/or SOM.
• Use various data labelling schemes.
• Compare more complex visualization schemes with straightforward co-ordinate projection methods.

• Data sets:
- abalone
- boston
- comp.activ
- image
- iris
- letter
- wine

Data Visualisation using PCA and SOM

Try a Java applet for an interactive PCA/SOM created by Daoxiao Jin.

Source code (tar+gzip)

Preparing for the exam - Sample Questions

• Principal Component Analysis (PCA)
- Why is it good to concentrate on variance/covariance structure of the multidimansional data?
- How can the variance/covariance structure be quantified? Define variance of a random variable and covariance of two random variables.
- How can the variance of a random variable X be estimated from a finite sample of realizations of X?
- Consider two random variables X,Y that form a two-dimensional vector random variable Z=(X,Y). How can the covariance between X and Y be estimated given a finite sample of realizations of Z?
- What is covariance matrix of a vector random variable?
- Define eigenvectors and eigenvalues of a square matrix A.
- Why are the eigenvectors/eigenvalues of covariance matrix important?
- Write down the PCA algorithm.
- How can you quantify the amount of lost information when projecting points onto a low-dimensional plane via PCA?
- What are the advantages/drawbacks of PCA?

• Self-Organizing Maps (SOM)
- What is the principal advantage of SOM over PCA?
- What is vector quantization (VQ)?
- What is the relation between SOM and VQ?
- What types of neighborhoods in the neural field can you think of?
- Why do we need to reduce both the neighborhood size and the learning rate?
- Write down the SOM algorithm.
- How would you quantify the amount of lost information when projecting points onto a low-dimensional surface via SOM?
- What are the advantages/drawbacks of SOM?

• Fractal images
- How would you describe self-similar objects?
- What is an Iterative Function System (IFS)?
- What is an affine mapping?
- Why can IFS pruduce realistic images of e.g. plants?
- How is an image produced from a given IFS?
- What are complex numbers and how do we add and multipy them?
- Define Mandelbrot set.
- In what ways can the Mandlebrot set be made visually appealing?
- Define Julia set associated with a complex number c.
- In what ways can Julia sets be made visually appealing?
- What is the relation between the Madelbrot set and Julia sets?

Problems to solve for those really interested

• Principal Component Analysis
- Show how the need for eigen-decomposition of the data covariance matrix arises from minimizing the distance between the data points and their corresponding projections in a low-dimensional linear subspace
- What happens if there are two (or more) equal eigenvalues of the covariance matrix?
- In general, the eigenvaules can be complex numbers. Why are the eigenvalues of the covariance matrix always real numbers?

Try the models out! - Benchmark data sets

As you get familiar with different types of models, try them out on benchmark data sets people in the machine learning community have been using to support their claims about yet another excellent learning system :-)

Here are two of the widely used data repisitories that contain data description, data itself and other useful things, like previously obtained results.