Алгоритмы семейства FOREL оперируют расстояниями между точками. Однако было замечено, что при ╚ручной╩ таксономии человек обращает внимание не  на абсолютные  расстояния, а на отношения расстояний между несколькими соседними точками [1]
   Представим себе, что все точки множества А попарно соединены между собой ребрами полного графа. Обозначим длину ребра между точками a и b индексом a.  Среди  всех  ребер,  смежных  этому ребру,  найдем самое короткое и его длину обозначим индексом bmin.   Отношение l= a/bmin будем называть l-длиной ребра (a,b).  Большие  значения l имеют ребра, которые соединяют удаленные друг от друга точки, окруженные близкими соседями. Именно такие локальные скачки плотности точек хорошо улавливает глаз человека при ручной таксономии.
    Алгоритм l-KRAB находит компактные сгустки точек, используя, как и человек, l-расстояния. Другими словами, он базируется на гипотезе l-компактности.
    Работа алгоритма начинается с нахождения пары точек с минимальным значением l-расстояния между ними. Эти точки соединяются ребром нового графа. Затем соединяются следующие самые l-близкие  точки  из числа не присоединенных  к  уже  построенной  части нового графа. Такая процедура повторяется до тех пор, пока все точки не окажутся соединенными ребрами нового графа. Этот граф не будет иметь петель и суммарная длина всех его ребер будет минимальной. Граф, обладающий такими свойствами, называется  Кратчайшим Незамкнутым Путем (КНП) [2]. В нашем случае будем обозначать его через l-КНП. 
    Теперь для разбиения множества А на два таксона необходимо разорвать одно  ребро графа l-КНП. При этом оставшимися ребрами l-КНП  будут  соединены  два подмножества  точек  по  mi точек  в  каждом  i-том  подмножестве (таксоне). Определим среднее значение длины r внутренних ребер таксонов и длину разорванного (граничного)  ребра  d  .  Примем,  что  для таксона, содержащего один объект, r = 0, два  объекта - r = 1,  а при объединении всех m точек в один таксон  d  = 0. 
   Кроме  характеристики l припишем   каждому   ребру   графа характеристику "напряженности" (с), равную произведению длины ребра на доли точек, находящихся по разные стороны  от  данного  ребра:  с = l*(2mi/m)*(2mj/m) .  Самыми напряженными будут длинные ребра,  через  которые  проходят  связи  между точками двух подмножеств, в каждом из которых содержится половина всех точек множества A.
    Ясно, что если мы разорвем самое напряженное  ребро,  то  тем самым обеспечим  выполнение  следующих  естественных  требований, предъявляемых обычно к алгоритмам таксономии: 
- граница между таксонами будет проходить по самым напряженным ребрам l-КНП;
- средняя  напряженность  внутренних  ребер  в  таксонах  будет минимальной; 
- таксоны будут иметь одинаковое (или почти  одинаковое)  число точек. 
   Критерием качества таксономии будем считать величину 
F=сd / (сr +v). Здесь cd - средняя напряженность граничных ребер, сr - средняя напряженность внутренних ребер  таксонов.  Сглаживающий коэффициент v должен быть больше 0, чтобы  при  увеличении  числа единичных таксонов значение F не  устремлялось  к  бесконечности. Можно приравнять  v,  например,  среднему  значению  напряженности ребер (c' ) полного l-КНП и тогда F=сd/(сr+с').
    Если  все  точки объединены в один таксон, то F = 0.  Если  число  таксонов  равно числу точек, то F = 1. В  промежутке  между  этими  крайностями F может быть как меньше, так и больше 1, но всегда больше 0.
   Характеристика  F  инвариантна  по  отношению  к   абсолютным  значениям длин ребер графа l-КНП, что позволяет сравнивать  между собой  качество  таксономии   различных   множеств   при   разных количествах объектов m, разном числе таксонов k и разном  среднем l- расстоянии между объектами. 
    Если желательное число таксонов задано диапазоном от kmin до kmax,    то, наблюдая за функцией F = f(k), можно в заданных пределах найти число таксонов, при котором F  достигает  максимума,  что соответствует наиболее  предпочтительной  таксономии.  На  рис.1a показан пример множества A, таксономия которого на  разное  число таксонов  характеризуется  функцией,  изображенной   на   рис.1b. Наиболее  предпочтительное  число  таксонов  равно  2.   Если   k требуется увеличить, то целесообразно выбрать 5 или 7 таксонов. 

Рис. 1.

    Эксперименты на других  двумерных  случаях  показали  хорошее совпадение результатов таксономии, сделанных экспертами "вручную" и программой l-KRAB, в том числе и для ситуаций,  неразрешимых  с позиций гипотезы компактности. 
    Сейчас  имеются  эффективные  алгоритмы   построения l-КНП. Однако, если количество исходных точек превышает несколько сотен, этап  построения l-КНП  становится  уже   затруднительным.   Для ускорения процедуры на первом этапе алгоритма l -KRAB-2  делается таксономия множества  из  m  объектов  на  k'  таксонов  простой сферической формы  (k'>k)  с  помощью  алгоритма  FOREL-2.  Затем центры этих таксонов используются в качестве исходных  точек  для алгоритма l-KRAB. Отличие состоит лишь в том, что при  вычислении нагруженности ребер центр каждого мелкого таксона  учитывается  с весом, пропорциональным числу исходных точек, включенных  в  этот таксон. 

Литература:
1.Елкина В.Н., Загоруйко Н.Г. Количественные  критерии  качества таксономии и их использование в процессе принятия решений. Тр. ИМ СО РАН  серия   "Вычислительные   системы",   1969,   вып.   36, Новосибирск, с.29-47. 
2. O.Boruvka. On a minimal problem. Prace Moravske  Pridovedecke Spolechnosti, v.3, 1926.