topfr

ALGORITHM l-KRAB     FOREL family algorithms are operating with distances between points. However, it was found, that under «manual» taxonomy the man usually pays attention not to the absolute distances, but to the relation between few neighbouring points [1].
     Imagine, that all points of the multitude A are connected in couples between them by the verges of the full graph. Let us denote the length of the verge between points a and b by an index b. Among all verges, adjacent to this verge, we will find the shortest one and denote its length by an index bmin. Relation l = a/bmin will be called the l-length of the verge (a,b). Large values of l correspond to the verges, connecting the points distant from each other and surrounded by closer neighbours. Such local jumps of points density are very well caught by the human eye under manual taxonomy.
    l-KRAB algorithm finds the compact clots of the points, using, as well as a man, the l-distances. In other words, it is based on the hypothesis of l-compactness.
     The work of the algorithm is started from the search for the couple of points with minimum value of l-distance between them. These points are connected with the verge of the new graph. Then the most l-closed points from the list of non-attached ones to the already constructed part of the new graph are connected. Such procedure is repeated until the moment, when all points will be connected by the verges of the new graph. This graph will have no loops and the summary length of all its verges will be minimum. The graph with such properties is called The Shortest Unclosed Way (SUW) [2]. In our case we will denote it as l-SUW.
     Now to separate the multitude A into two taxons it is necessary to tear up one verge of l-SUW graph. The remaining verges of l-SUW will connect two submultitudes with mi points in each i-th submultitude (taxon). Let us define the average length r of internal taxon verges and the length of the disconnected (boundary) verge d. Let us assume, that for taxon, containing one object, r= 0, two objects - r= 1, and for the combination of all points into one taxon d = 0.
     Let us assign every graph verge the «tension»
c=l*(2mi / m)*(2mj / m). The most tense are the verges, connecting the most distant and approximately equally powerful submultitudes of points.
      It is clear, that if we will tear up the most tense verge, then we will provide the fulfilling of the following natural requirements:
-- the border between taxons will lay on the most tense verges of lr-SUW;
-- the average tension of inner verges in taxons will be minimum;
-- the taxons will include equal (or almost equal) number of points.
     The criterion of the quality of such taxonomy will be F = ñd/(ñr +m ). Here cd is the average tension of the border verges, ñr - average tension of the inner verges of taxons. Smoothing coefficient m must higher than zero to avoid the speeding of F value to infinity under increase of single taxons number. m may be made equal, for example, to the average value of verges tension (c’) of the full l-SUW and then F = ñd /(ñr + ñ').
If all points are united into one taxon, then F=0. If the number of taxons is equal to the number of points, then F=1. In the interval between these limits the value of F may be either lower or than 1, but it is always higher than zero.
    F characteristic is invariant in relation to the absolute lengths of verges of the l-SUW graph, thus providing the possibility to compare the quality of taxonomy for different multitudes with various number of objects m, different number of taxons k and different average l-distance between objects.
     If the desired number of taxons is given by the range from kmin to kmax, then, observing the function F=f(k), one can find in the given range the number of taxons, providing maximum value of F, corresponding to the most appropriate taxonomy.

Fig.1

     Fig.1a shows the example of the multitude A, which taxonomy into different number of taxons is characterised by the function, given in the Fig.1b. The most appropriate number of taxons is equal to 2. If it is necessary to increase k, then it will be reasonable to select 5 or 7 taxons.
     Experiments with other two-dimension cases demonstrated good coincidence of the taxonomy results, «manually» obtained by experts and produced by l-KRAB software, including the cases, which cannot be solved from the positions of compactness hypothesis.
   Now there are the efficient algorithms for construction of l-SUW. However, if the number of initial points exceeds few hundreds, the l-SUW construction process becomes complicated. To speed up the procedure the l-KRAB-2 algorithm applies at the first stage the taxonomy of m objects into k’ taxons (k’<k) of simple spherical form by means of FOREL-2 algorithm. Afterwards the centres of these taxons are used as initial points of l-KRAB algorithm. The only difference is that the calculation of verges loading the centre of each small taxon is accounted with the weight, proportional to the number of initial points, included into this taxon.

REFERENCES

. Elkina V.N., Zagoruiko N.G. Quantitative criteria of taxonomy quality and their application in decision making process. In Works of the Institute of Mathematics SB AS USSR, Novosibirsk, «Computing systems» series, v.36, 1969, pp.29-47, in Russian
2. O.Boruvka. On a minimal problem. Prace Moravske Pridovedecke Spolechnosti, v.3, 1926.