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.

Adding Characters

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.