Глава 10 Алгоритмы таксономии в λ-пространстве

§ 1. Алгоритм λ-KRAB

Алгоритмы таксономии семейства FOREL, описанные в главе 4, оперируют евклидовыми расстояниями между точками. Однако было замечено, что при «ручной» таксономии человек обращает внимание не только на абсолютные расстояния, но и на отношения расстояний между несколькими соседними точками [54]. На этом основании была сформулирована гипотеза -компактности, изложенная в главе 3. Согласно этой гипотезе глаз человека хорошо улавливает различия в локальной плотности точек на плоскости и при прочих равных условиях предпочитает проводить границу между таксонами по участкам, где наблюдаются заметные изменения («скачки») этой плотности. Напомним, что локальное изменение плотности дискретного множества точек на границе между точками  и  можно описать нормированной величиной , а расстояние между этими точками — нормированной величиной .

При «ручной» таксономии человек стремится к такому решению, при котором граница между таксонами проходила бы по участку с наибольшим значением характеристики , которую мы называем -расстоянием. Если имеется несколько возможных вариантов таксономии с примерно одинаковыми значениями , то предпочтение отдается тому варианту, при котором таксоны включают в свой состав по возможности одинаковое количество объектов. Этот критерий «равномощности» таксонов хорошо отражает величина

где  — количество таксонов,  — число объектов в -м таксоне, а  — общее число объектов.

Итоговый критерий, характеризующий качество таксономии, выражается величиной . На максимизации фактически этого критерия основан алгоритм KRAB [54,69], давно и успешно применяемый при решении разнообразных задач таксономии.

Более поздние исследования, связанные с аккуратной формулировкой гипотезы -компактности, привели к заключению, что человек в процессе таксономии действительно использует все эти составляющие , и , но придает им разный вес. Была сформулирована задача идентификации модели следующего вида:

Меняя параметры модели , можно на одном и том же множестве двумерных объектов получать разные варианты таксономии. Фиксируется тот вариант, который совпадает с вариантом, полученным экспертом при «ручной» таксономии. Запоминаются те сочетания параметров, при которых получался этот вариант. Затем программе и эксперту предъявляется другая выборка двумерных объектов (точек на плоскости) и эксперимент повторяется. После многочисленного повторения таких сравнительных экспериментов можно определить значения параметров, при которых машинная и экспертная таксономии совпадают.

Для проведения этих экспериментов была разработана программная система, с помощью которой на экране дисплея отображались сцены в виде точек, координаты которых задавались либо генератором случайных чисел, либо вручную, с помощью курсора и мыши. Эти сцены анализировались экспертами и программой таксономии, и экспериментатор, меняя значения параметров ,  и , добивался совпадения результатов таксономии. В итоге такого исследования было установлено, что наилучшие результаты получаются при максимизации функционала  качества таксономии, в котором наибольший вес придается нормированному расстоянию , затем характеристике скачка плотности  и лишь потом характеристике равномощности таксонов . Так как все эти величины меняются в пределах от нуля до единицы, то уменьшение значимости того или иного параметра можно делать путем возведения его в степень, большую единицы. С учетом этого значения параметров оказались такими:  и . В окончательном виде критерий качества таксономии, положенный в основу алгоритма -KRAB, выглядит следующим образом:

Работа алгоритма -KRAB начинается с нахождения пары точек с минимальным значением -расстояния между ними. Эти точки соединяются ребром графа. Затем соединяются следующие самые -близкие точки из числа не присоединенных к уже построенной части графа. Эта процедура повторяется до тех пор, пока все точки не окажутся соединенными ребрами этого графа. Такой граф не будет иметь петель, и суммарная длина всех его ребер будет минимальной. Граф, обладающий такими свойствами, называется кратчайшим незамкнутым путем (КНП) [135]. В нашем случае будем обозначать его через -КНП.

Теперь для разбиения множества  на два таксона необходимо разорвать одно ребро из ребер графа -КНП. Выберем ребро  с -длиной . Оставшимися ребрами -КНП соединяются два подмножества по  точек в каждом -м подмножестве (таксоне). Эта информация позволяет для данного варианта разбиения вычислить характеристику равномощности таксонов . Общая оценка качества  этого -го варианта таксономии равна . Вычисление величины  для всех  ребер графа позволяет найти такой вариант таксономии, при котором достигается максимум критерия .

Характеристика  инвариантна по отношению к количеству объектов , числу таксонов  и абсолютным значениям длин ребер графа -КНП. Это позволяет сравнивать между собой качество таксономии различных множеств при разных количествах объектов , разном числе таксонов  и разном среднем -расстоянии между объектами.

Алгоритмы семейства KRAB испытывались на многих модельных примерах и применялись для решения большого числа практических задач таксономии. В частности, успешно были решены все задачи, показанные на рис. 28, взятые из книги [12]. Там они были предназначены для доказательства теоремы несуществования: автор утверждал, что не может быть одного алгоритма, который смог бы решить все эти задачи. Однако если разные люди решают их одинаково, то, по-видимому, все они пользуются одним и тем же критерием. Следовательно, правильно было бы говорить не о том, что единого алгоритма нет и не может быть, а о том, что невозможно выявить интуитивные человеческие критерии качества таксономии. Описанный выше критерий является результатом попытки выявить именно эти человеческие критерии.

Рис. 28

Некоторое время казалось, что нам удалось решить поставленную задачу полностью. Однако затем были построены примеры, показанные на рис. 29, на которых таксономия  по критерию  не совпадала с человеческими решениями .

По-видимому, глаз человека обращает внимание не только на те характеристики, которые входят в состав критерия , но также и на форму описания получаемых таксонов — на привычность этих фигур, их простоту. В примере из рис. 29, а человек выделяет два таксона простой сферической формы. Таксоны, выделяемые человеком в примере, показанном на рис. 29, б, описываются прямыми линиями.

Рис. 29

Идея использования закономерностей, описывающих получаемые таксоны, в качестве дополнительного критерия качества таксономии принадлежит Р. Михальскому и Р. Степпу [127, 128]. Они ввели понятие концепта. Таксон — это не только набор похожих друг на друга объектов, но и некоторое новое понятие или концепт. В алгоритмах таксономии следует опираться на набор концептов в виде простых для восприятия понятий: сфера, эллипсоид, прямая линия, линейная разделяющая граница, логическое решающее правило и т. д.

В алгоритме -KRAB получаемые таксоны описываются наборами гиперсфер. Для этого применяется программа «Дробящиеся эталоны» (см. §8 главы 5). В начале выбирается несколько вариантов таксономии на одно и то же число таксонов с наибольшими значениями критерия . В процессе сравнения этих вариантов предпочтение отдается тому из них, при котором потребовалось меньшее число эталонных гиперсфер. Если в число «финалистов» попали бы те два варианта таксономии, которые показаны на рис. 29, а, то для описания «человеческого» варианта было бы достаточно использовать два эталона, а для варианта по критерию  потребовалось бы три эталона (см. рис. 30). Алгоритм выбрал бы то же решение, что и эксперты.

Рис. 30

Достичь такого же результата в примере из рис. 29, б с помощью сферических концептов не удастся. Здесь потребовался бы концепт «линейный объект». Из этого следует, что алгоритм, который мог бы получать человеческие решения во всех случаях, должен включать в свой состав такую же обширную библиотеку концептов, какую использует человек. Выявление состава этой библиотеки и формализация процедур использования разнородных концептов представляет собой интересную, но трудную и потому пока не решенную проблему.