- A preliminary discussion of concepts relevant to the algorithm
- A description of the hyperplane construction process
- A description of how hyperplanes can be used to define classification regions in space
- A general discussion of the algorithm

The basic procedure is to find a set of hyperplanes that 'cut' Tomek links, thus separating prototypes and points belonging to different classes. Figure 9 shows a hyperplane (in purple) cutting a Tomek link. It is shown later that a set of hyperplanes that cut all Tomek links divides the point space into distinct regions, which can be used to classify points in a piecewise linear fashion. The key concept is to cut as many Tomek links as possible with each hyperplane, given the constraint that they must be able to classify points with an error less that a predefined maximum acceptable classification error. This results in a smaller set of hyperplanes, reducing the complexity of the classification according to a classification error limit.

If the hyperplane is capable of locally classifying points within the maximum error threshold, it is then modified to cut other nearby Tomek links. Tomek links are considered 'nearby' based on the distance of their midpoints to the midpoints of Tomek links already cut by the hyperplane under inspection. The distance to the nearest Tomek link is shown in figure 10 by the grey line connecting the midpoints of two Tomek links.

For each prototype, there exits a subset of hyperplanes, which cut its associated Tomek links. Each hyperplane in this subset divides the point space into two distinct regions, one of which contains the prototype. The union of all these regions containing the prototype defines a region in point space, which isolates the prototype from all other prototypes to which it is connected via Tomek links. In figure 17, the region formed by this union is shown for the red prototype in the top left corner of the example.

U =

There are several subtle problems that reduce the algorithm's usefulness however. Achieving classification under the maximum acceptable error threshold is not guaranteed by the algorithm itself, since the first Tomek link cut by a hyperplane in an iteration of the algorithm is guaranteed to be accepted regardless of its classification error rate on associated data points. This may or may not be a significant problem though, because if a hyperplane cannot cut a single Tomek link with a classification error rate less than the maximum error threshold, the error threshold is not achievable at any rate.

Secondly, there is no guidance as to how many prototypes to use on a particular set of test data. This is an important question - in the limits, one could either use a single prototype for each class, or a prototype corresponding to each data point. Either approach would have a very different effect on the minimum error achievable and the generalizability of the class boundaries.