## Application to Pattern Recognition

### Using the Kohonen Feature Map

In this chapter, you will use the Kohonen program developed in Chapter  The Kohonen Self-Organizing Map to recognize patterns. You will modify the Kohonen program for the display of patterns.

#### An Example Problem: Character Recognition

The problem that is presented in this chapter is to recognize or categorize alphabetic characters. You will input various alphabetic characters to a Kohonen map and train the network to recognize these as separate categories. This program can be used to try other experiments that will be discussed at the end of this chapter.

Representing Characters

The letter A is represented by the values:

`0 0 1 0 0`
`0 1 0 1 0`
`1 0 0 0 1`
`1 0 0 0 1`
`1 1 1 1 1`
`1 0 0 0 1`
`1 0 0 0 1`

For use in the Kohonen program, we need to serialize the rows, so that all entries appear on one line.

For the characters A and X you would end up with the following entries in the input file, input.dat:

` `
`0 0 1 0 0  0 1 0 1 0  1 0 0 0 1  1 0 0 0 1  1 1 1 1 1  1 0 0 0 1  1 0 0 0 1`
` << the letter A`
`1 0 0 0 1  0 1 0 1 0  0 0 1 0 0  0 0 1 0 0  0 0 1 0 0  0 1 0 1 0  1 0 0 0 1`
` << the letter X`

Monitoring the Weights

We will present the Kohonen map with many such characters and find the response in output. You will be able to watch the Kohonen map as it goes through its cycles and learns the input patterns. At the same time, you should be able to watch the weight vectors for the winner neurons to see the pattern that is developing in the weights. Remember that for a Kohonen map the weight vectors tend to become aligned with the input vectors. So after a while, you will notice that the weight vector for the input will resemble the input pattern that you are categorizing.

Representing the Weight Vector

Although on and off values are fine for the input vectors mentioned, you need to see grayscale values for the weight vector. This can be accomplished by quantizing the weight vector into four bins, each represented by a different ASCII graphic character, as shown in table:

 Quantizing the Weight Vector <= 0 White rectangle (space) 0 < weight <= 0.25 Light-dotted rectangle 0.25 < weight <= 0.50 Medium-dotted rectangle 0.50 < weight <= 0.75 Dark-dotted rectangle weight > 0.75 Black rectangle

The ASCII values for the graphics characters to be used are listed in table:

 ASCII Values for Rectangle Graphic Characters White rectangle 255 Light-dotted rectangle 176 Medium-dotted rectangle 177 Dark-dotted rectangle 178 Black rectangle 219

### C++ Code Development

The changes to the Kohonen program are relatively minor. The following listing indicates these changes.

#### Changes to the Kohonen Program

The first change to make is to the Kohonen_network class definition. This is in the file, layerk.h, shown in listing:

Updated layerk.h file

`class Kohonen_network{`
`private:`
` `
`       layer *layer_ptr[2];`
`       int layer_size[2];`
`       int neighborhood_size;`
` `
`public:`
`       Kohonen_network();`
`       ~Kohonen_network();`
`       void get_layer_info();`
`       void set_up_network(int);`
`       void randomize_weights();`
`       void update_neigh_size(int);`
`       void update_weights(const float);`
`       void list_weights();`
`       void list_outputs();`
`       void get_next_vector(FILE *);`
`       void process_next_pattern();`
`       float get_win_dist();`
`       int get_win_index();`
`       void display_input_char();`
`       void display_winner_weights();`
` `
`};`

The new member functions are shown in italic. The functions display_input_char() and display_winner_weights() are used to display the input and weight maps on the screen to watch weight character map converge to the input map.

The implementation of these functions is in the file, layerk.cpp. The portion of this file containing these functions is shown in listing:

Additions to the layerk.cpp implementation file

`void Kohonen_network::display_input_char()`
`{`
`int i, num_inputs;`
`unsigned char ch;`
`float temp;`
`int col=0;`
`float * inputptr;`
`num_inputs=layer_ptr[1]->num_inputs;`
`inputptr = layer_ptr[1]->inputs;`
`// we’ve got a 5x7 character to display`
` `
`for (i=0; i<num_inputs; i++)`
`       {`
`       temp = *(inputptr);`
`       if (temp <= 0)`
`              ch=255;// blank`
`       else if ((temp > 0) && (temp <= 0.25))`
`              ch=176; // dotted rectangle -light`
`       else if ((temp > 0.25) && (temp <= 0.50))`
`              ch=177; // dotted rectangle -medium`
`       else if ((temp >0.50) && (temp <= 0.75))`
`              ch=178; // dotted rectangle -dark`
`       else if (temp > 0.75)`
`              ch=219; // filled rectangle`
`       printf(“%c”,ch); //fill a row`
`       col++;`
`       if ((col % 5)==0)`
`              printf(“\n”); // new row`
`       inputptr++;`
`       }`
`printf(“\n\n\n”);`
`}`
` `
`void Kohonen_network::display_winner_weights()`
`{`
`int i, k;`
`unsigned char ch;`
`float temp;`
`float * wmat;`
`int col=0;`
`int win_index;`
`int num_inputs, num_outputs;`
` `
`num_inputs= layer_ptr[1]->num_inputs;`
`wmat = ((Kohonen_layer*)layer_ptr[1])`
`              ->weights;`
`win_index=((Kohonen_layer*)layer_ptr[1])`
`              ->winner_index;`
` `
`num_outputs=layer_ptr[1]->num_outputs;`
` `
`// we’ve got a 5x7 character to display`
` `
`for (i=0; i<num_inputs; i++)`
`       {`
`       k= i*num_outputs;`
`       temp = wmat[k+win_index];`
`       if (temp <= 0)`
`              ch=255;// blank`
`       else if ((temp > 0) && (temp <= 0.25))`
`              ch=176; // dotted rectangle -light`
`       else if ((temp > 0.25) && (temp <= 0.50))`
`              ch=177; // dotted rectangle -medium`
`       else if ((temp > 0.50) && (temp <= 0.75))`
`              ch=178; // dotted rectangle -dark`
`       else if (temp > 0.75)`
`              ch=219; // filled rectangle`
`       printf(“%c”,ch); //fill a row`
`       col++;`
`       if ((col % 5)==0)`
`              printf(“\n”); // new row`
`       }`
`printf(“\n\n”);`
`printf(“—————————-\n”);`
` `
`}`

The final change to make is to the kohonen.cpp file. The new file is called pattern.cpp and is shown in listing:

The implementation file pattern.cpp

`// pattern.cpp      V. Rao, H. Rao`
`// Kohonen map for pattern recognition`
`#include “layerk.cpp”`
` `
`#define INPUT_FILE “input.dat”`
`#define OUTPUT_FILE “kohonen.dat”`
`#define dist_tol      0.001`
`#define wait_cycles   10000 // creates a pause to`
`                      // view the character maps`
` `
`void main()`
`{`
` `
`int neighborhood_size, period;`
`float avg_dist_per_cycle=0.0;`
`float dist_last_cycle=0.0;`
`float avg_dist_per_pattern=100.0; // for the latest cycle`
`float dist_last_pattern=0.0;`
`float total_dist;`
`float alpha;`
`unsigned startup;`
`int max_cycles;`
`int patterns_per_cycle=0;`
` `
`int total_cycles, total_patterns;`
`int i;`
` `
`// create a network object`
`Kohonen_network knet;`
` `
`FILE * input_file_ptr, * output_file_ptr;`
` `
`// open input file for reading`
`if ((input_file_ptr=fopen(INPUT_FILE,”r”))==NULL)`
`              {`
`              cout << “problem opening input file\n”;`
`              exit(1);`
`              }`
` `
`// open writing file for writing`
`if ((output_file_ptr=fopen(OUTPUT_FILE,”w”))==NULL)`
`              {`
`              cout << “problem opening output file\n”;`
`              exit(1);`
`              }`
` `
`// ————————————————————-`
`//     Read in an initial values for alpha, and the`
`//  neighborhood size.`
`//  Both of these parameters are decreased with`
`//  time. The number of cycles to execute before`
`//  decreasing the value of these parameters is`
`//            called the period. Read in a value for the`
`//            period.`
`// ————————————————————-`
`              cout << “ Please enter initial values for:\n”;`
`              cout << “alpha (0.01-1.0),\n”;`
`              cout << “and the neighborhood size (integer between 0\`
`                     and 50)\n”;`
`              cout << “separated by spaces, e.g. 0.3 5 \n “;`
` `
`              cin >> alpha >> neighborhood_size ;`
` `
`              cout << “\nNow enter the period, which is the\n”;`
`              cout << “number of cycles after which the values\n”;`
`              cout << “for alpha the neighborhood size are \`
`                     decremented\n”;`
`              cout << “choose an integer between 1 and 500 , e.g. \ 50 \n”;`
` `
`              cin >> period;`
`       //     Read in the maximum number of cycles`
`       //     each pass through the input data file is a cycle`
`              cout << “\nPlease enter the maximum cycles for the`
`              simulation\n”;`
`              cout << “A cycle is one pass through the data set.\n”;`
`              cout << “Try a value of 500 to start with\n\n”;`
` `
`              cin >> max_cycles;`
` `
`// the main loop`
`//`
`//     continue looping until the average distance is less than`
`//            the tolerance specified at the top of this file`
`//            , or the maximum number of`
`//            cycles is exceeded;`
` `
`// initialize counters`
`total_cycles=0; // a cycle is once through all the input data`
`total_patterns=0; // a pattern is one entry in the input data`
` `
`// get layer information`
`knet.get_layer_info();`
` `
`// set up the network connections`
`knet.set_up_network(neighborhood_size);`
` `
`// initialize the weights`
` `
`// randomize weights for the Kohonen layer`
`// note that the randomize function for the`
`// Kohonen simulator generates`
`// weights that are normalized to length = 1`
`knet.randomize_weights();`
`// write header to output file`
`fprintf(output_file_ptr,`
`       “cycle\tpattern\twin index\tneigh_size\\`
`              tavg_dist_per_pattern\n”);`
` `
`fprintf(output_file_ptr,`
`       “————————————————————————\n”);`
` `
`startup=1;`
`total_dist=0;`
` `
`while (`
`                     (avg_dist_per_pattern > dist_tol)`
`                     && (total_cycles < max_cycles)`
` `
`                     || (startup==1)`
`                     )`
`{`
`startup=0;`
`dist_last_cycle=0; // reset for each cycle`
`patterns_per_cycle=0;`
`// process all the vectors in the datafile`
` `
`while (!feof(input_file_ptr))`
`       {`
`       knet.get_next_vector(input_file_ptr);`
` `
`       // now apply it to the Kohonen network`
`       knet.process_next_pattern();`
` `
`  dist_last_pattern=knet.get_win_dist();`
` `
`  // print result to output file`
`  fprintf(output_file_ptr,”%i\t%i\t%i\t\t%i\t\t%f\n”,`
`       total_cycles,total_patterns,knet.get_win_index(),`
`       neighborhood_size,avg_dist_per_pattern);`
` `
`       // display the input character and the`
`       // weights for the winner to see match`
` `
`       knet.display_input_char();`
`       knet.display_winner_weights();`
`       // pause for a while to view the`
`       // character maps`
`       for (i=0; i<wait_cycles; i++)`
`              {;}`
` `
`       total_patterns++;`
` `
`       // gradually reduce the neighborhood size`
`       // and the gain, alpha`
`       if (((total_cycles+1) % period) == 0)`
`              {`
`              if (neighborhood_size > 0)`
`                     neighborhood_size —;`
`              knet.update_neigh_size(neighborhood_size);`
`              if (alpha>0.1)`
`                     alpha -= (float)0.1;`
`              }`
` `
`       patterns_per_cycle++;`
`       dist_last_cycle += dist_last_pattern;`
`       knet.update_weights(alpha);`
`       dist_last_pattern = 0;`
`    }`
` `
`avg_dist_per_pattern= dist_last_cycle/patterns_per_cycle;`
`total_dist += dist_last_cycle;`
`total_cycles++;`
` `
`fseek(input_file_ptr, 0L, SEEK_SET); // reset the file`
`       pointer`
`                            // to the beginning of`
`                            // the file`
` `
`} // end main loop`
` `
`cout << “\n\n\n\n\n\n\n\n\n\n\n”;`
`cout << “———————————————————————\n”;`
`cout << “    done \n”;`
` `
`avg_dist_per_cycle= total_dist/total_cycles;`
` `
`cout << “\n”;`
`cout << “——>average dist per cycle = “ << avg_dist_per_cycle << “ <—-\n”;`
`cout << “>dist last cycle = “ << dist_last_cycle << “ <   \n”;`
`cout << “->dist last cycle per pattern= “ <<`
`       avg_dist_per_pattern << “ <—-\n”;`
`cout << “——->total cycles = “ << total_cycles << “ <—-\n”;`
`cout << “——————>total patterns = “ <<`
`       total_patterns << “ <—-\n”;`
`cout << “————————————————————————\n”;`
`// close the input file`
`fclose(input_file_ptr);`
`}`

Changes to the program are indicated in italic. Compile this program by compiling and making the pattern.cpp file, after modifying the layerk.cpp and layerk.h files, as indicated previously.

#### Testing the Program

Let us run the example that we have created an input file for. We have an input.dat file with the characters A and X defined. A run of the program with these inputs is shown as follows:

`Please enter initial values for:`
`alpha (0.01-1.0),`
`and the neighborhood size (integer between 0 and 50)`
`separated by spaces, e.g., 0.3 5`
`0.3 5`
`Now enter the period, which is the`
`number of cycles after which the values`
`for alpha the neighborhood size are decremented`
`choose an integer between 1 and 500, e.g., 50`
`50`
`Please enter the maximum cycles for the simulation`
`A cycle is one pass through the data set.`
`Try a value of 500 to start with`
`500`
`Enter in the layer sizes separated by spaces.`
`A Kohonen network has an input layer`
`followed by a Kohonen (output) layer`
`35 100`

The output of the program is contained in file kohonen.dat as usual. This shows the following result.

`cycle   pattern    win index   neigh_size    avg_dist_per_pattern`
`———————————————————————————————————————————————————————————————————`
`0       0          42          5             100.000000`
`0       1          47          5             100.000000`
`1       2          42          5             0.508321`
`1       3          47          5             0.508321`
`2       4          40          5             0.742254`
`2       5          47          5             0.742254`
`3       6          40          5             0.560121`
`3       7          47          5             0.560121`
`4       8          40          5             0.392084`
`4       9          47          5             0.392084`
`5       10         40          5             0.274459`
`5       11         47          5             0.274459`
`6       12         40          5             0.192121`
`6       13         47          5             0.192121`
`7       14         40          5             0.134485`
`7       15         47          5             0.134485`
`8       16         40          5             0.094139`
`8       17         47          5             0.094139`
`9       18         40          5             0.065898`
`9       19         47          5             0.065898`
`10      20         40          5             0.046128`
`10      21         47          5             0.046128`
`11      22         40          5             0.032290`
`11      23         47          5             0.032290`
`12      24         40          5             0.022603`
`12      25         47          5             0.022603`
`13      26         40          5             0.015822`
`13      27         47          5             0.015822`
`14      28         40          5             0.011075`
`14      29         47          5             0.011075`
`15      30         40          5             0.007753`
`15      31         47          5             0.007753`
`16      32         40          5             0.005427`
`16      33         47          5             0.005427`
`17      34         40          5             0.003799`
`17      35         47          5             0.003799`
`18      36         40          5             0.002659`
`18      37         47          5             0.002659`
`19      38         40          5             0.001861`
`19      39         47          5             0.001861`
`20      40         40          5             0.001303`
`20      41         47          5             0.001303`

The tolerance for the distance was set to be 0.001 for this program, and the program was able to converge to this value. Both of the inputs were successfully classified into two different winning output neurons. In Figures you see two snapshots of the input and weight vectors that you will find with this program. The weight vector resembles the input as you can see, but it is not an exact replication.

Sample screen output of the letter A from the input and weight vectors.

Sample screen output of the letter X from the input and weight vectors.

#### Generalization versus Memorization

As mentioned in Chapter 11, you actually don’t desire the exact replication of the input pattern for the weight vector. This would amount to memorizing of the input patterns with no capacity for generalization.

For example, a typical use of this alphabet classifier system would be to use it to process noisy data, like handwritten characters. In such a case, you would need a great deal of latitude in scoping a class for a letter A.

The next step of the program is to add characters and see what categories they end up in. There are many alphabetic characters that look alike, such as H and B for example. You can expect the Kohonen classifier to group these like characters into the same class.

We now modify the input.dat file to add the characters H, B, and I. The new input.dat file is shown as follows.

`0 0 1 0 0   0 1 0 1 0  1 0 0 0 1  1 0 0 0 1  1 1 1 1 1  1 0 0 0 1`
` 1 0 0 0 1`
`1 0 0 0 1   0 1 0 1 0  0 0 1 0 0  0 0 1 0 0  0 0 1 0 0  0 1 0 1 0`
` 1 0 0 0 1`
`1 0 0 0 1   1 0 0 0 1  1 0 0 0 1  1 1 1 1 1  1 0 0 0 1  1 0 0 0 1`
` 1 0 0 0 1`
`1 1 1 1 1   1 0 0 0 1  1 0 0 0 1  1 1 1 1 1  1 0 0 0 1  1 0 0 0 1`
` 1 1 1 1 1`
`0 0 1 0 0   0 0 1 0 0  0 0 1 0 0  0 0 1 0 0  0 0 1 0 0  0 0 1 0 0`
` 0 0 1 0 0`

The output using this input file is shown as follows.

`—————————————————————————-`
`       done`
`——>average dist per cycle = 0.732607 <—-`
`——>dist last cycle = 0.00360096 <—-`
`->dist last cycle per pattern= 0.000720192 <—-`
`——————>total cycles = 37 <—-`
`——————>total patterns = 185 <—-`
`—————————————————————————-`

The file kohonen.dat with the output values is now shown as follows.

`cycle   pattern    win index   neigh_size    avg_dist_per_pattern`
`—————————————————————————————————————————————————————————————————`
`0       0          69          5             100.000000`
`0       1          93          5             100.000000`
`0       2          18          5             100.000000`
`0       3          18          5             100.000000`
`0       4          78          5             100.000000`
`1       5          69          5             0.806743`
`1       6          93          5             0.806743`
`1       7          18          5             0.806743`
`1       8          18          5             0.806743`
`1       9          78          5             0.806743`
`2       10         69          5             0.669678`
`2       11         93          5             0.669678`
`2       12         18          5             0.669678`
`2       13         18          5             0.669678`
`2       14         78          5             0.669678`
`3       15         69          5             0.469631`
`3       16         93          5             0.469631`
`3       17         18          5             0.469631`
`3       18         18          5             0.469631`
`3       19         78          5             0.469631`
`4       20         69          5             0.354791`
`4       21         93          5             0.354791`
`4       22         18          5             0.354791`
`4       23         18          5             0.354791`
`4       24         78          5             0.354791`
`5       25         69          5             0.282990`
`5       26         93          5             0.282990`
`5       27         18          5             0.282990`
`...`
`35      179        78          5             0.001470`
`36      180        69          5             0.001029`
`36      181        93          5             0.001029`
`36      182        13          5             0.001029`
`36      183        19          5             0.001029`
`36      184        78          5             0.001029`

Again, the network does not find a problem in classifying these vectors.

Until cycle 21, both the H and the B were classified as output neuron 18. The ability to distinguish these vectors is largely due to the small tolerance we have assigned as a termination criterion.

#### Other Experiments to Try

You can try other experiments with the program. For example, you can repeat the input file but with the order of the entries changed. In other words, you can present the same inputs a number of times in different order. This actually helps the Kohonen network train faster. You can try applying garbled versions of the characters to see if the network distinguishes them. Just as in the backpropagation program, you can save the weights in a weight file to freeze the state of training, and then apply new inputs. You can enter all of the characters from A to Z and see the classification that results. Do you need to train on all of the characters or a subset? You can change the size of the Kohonen layer. How many neurons do you need to recognize the complete alphabet?

There is no restriction on using digital inputs of 1 and 0 as we had used. You can apply grayscale analog values. The program will display the input pattern according to the quantization levels that were set. This set can be expanded, and you can use a graphics interface to display more levels. You can then try pattern recognition of arbitrary images, but remember that processing time will increase rapidly with the number of neurons used. The number of input neurons you choose is dictated by the image resolution, unless you filter and/or subsample the image before presenting it to the network. Filtering is the process of using a type of averaging function applied to groups of pixels. Subsampling is the process of choosing a lower-output image resolution by selecting fewer pixels than a source image. If you start with an image that is 100 × 100 pixels, you can subsample this image 2:1 in each direction to obtain an image that is one-fourth the size, or 50 × 50 pixels. Whether you throw away every other pixel to get this output resolution or apply a filter is up to you. You could average every two pixels to get one output pixel as an example of a very simple filter.

### Summary

The following list highlights the important Kohonen program features which you learned in this chapter.

This chapter presented a simple character recognition program using a Kohonen feature map.

The input vectors and the weight vectors were displayed to show convergence and note similarity between the two vectors.

As training progresses, the weight vector for the winner neuron resembles the input character map.

` `
` `
` `
` `
` `
` `
` `