8.2. Метод «дробящихся эталонов» (алгоритм ДРЭТ)

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

Один из вариантов этого метода предусматривает использование в качестве покрывающих фигур набора гиперсфер. Для каждого из  образов строится сфера минимального радиуса, покрывающая все его обучающие реализации. Значения радиусов этих сфер и расстояний между их центрами позволяет определить образы, сферы которых не пересекаются со сферами других образов. Такие сферы считаются эталонными (см. образы 1 и 8 на рис. 19), а их центры и радиусы запоминаются в качестве эталонов первого поколения.

Рис. 19

Если два образа пересекаются, но в области пересечения не оказалось ни одной реализации обучающей выборки, такое пересечение считается фиктивным, центры и радиусы этих сфер также вносятся в список эталонов первого поколения. При этом область пересечения считается принадлежащей сфере с меньшим радиусом (сфере 2 на рис. 19). Если в зоне пересечения оказались точки только одного образа, то эта зона считается принадлежащей этому образу (сфере 3 на рис. 19). Точка считается относящейся к образу 4, если она попадает в сферу 4 и не попадает в сферу 3. Если же область пересечения содержит точки разных образов, то для этих точек строятся эталоны второго поколения (сферы 5, 6 и 7). Если и они пересекаются, то для точек их зоны пересечения строятся эталоны третьего поколения. Процедура дробления эталонов продолжается до получения заданной надежности распознавания обучающей последовательности.

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

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

Если постановка задачи распознавания предостерегает от ошибочного включения реализаций -го образа в состав любого из  заданных образов (т. е. если цена ошибки  достаточно велика), то нужно избегать излишней «пустоты» в эталонных сферах (это имеет место, например, в сфере 8). С этой целью вычисляется отношение  числа точек  к радиусу сферы . И если  меньше заданного порога , такая сфера подвергается дополнительному анализу: делается попытка заменить одну разреженную сферу несколькими более плотными сферами меньшего диаметра. Это можно сделать с помощью алгоритма таксономии типа FOREL. Если средняя плотность новых сфер окажется выше плотности начальной сферы, то эти сферы вносятся в список эталонов вместо начальной. Следует предостеречь от чрезмерного увлечения процедурой повышения плотности сфер: каждая новая сфера — это дополнительные затраты машинной памяти на эталоны и времени на принятие решений. Кроме того, увеличение числа поколений эталонов фактически приводит к построению «слишком вычурных» границ между образами, что при ограниченной выборке статистически мало оправдано.

Опыт показал, что даже в очень сложных случаях для хорошего распознавания обучающей выборки бывает достаточно в среднем не более трех поколений эталонов. Так, при распознавании 11 устных команд для безошибочного распознавания обучающей последовательности потребовалось от 2 до 5 сфер на образ (в среднем 2,8). При распознавании же по одному эталону на образ эти реализации распознавались с ошибкой 45%, что говорит о высокой сложности данной задачи.

Если бы мы могли сопоставлять в единых ценах расходы машинных ресурсов на эталоны  и стоимость потерь , то нам следует стремиться к минимизации общих потерь :

При распознавании новых реализаций процесс проверки попадания в ту или иную эталонную сферу начинается со сфер наименьшего диаметра.

Решающие правила отличаются друг от друга так называемой емкостной характеристикой [25,102]. Она оценивает отношение сложности правила к его разделяющей способности. Алгоритм ДРЭТ вырабатывает очень простые правила, которые вместе с тем могут отделить друг от друга образы со сложными границами, так что эти правила обладают очень хорошей емкостной характеристикой.

В заключение отметим, что здесь так же, как и в предыдущем алгоритме, имеется возможность по количеству эталонов судить об информативности признакового пространства. Если для безошибочного распознавания  обучающих объектов  образов  потребовалось  эталонов, то характеристика  позволяет определить меру информативности признаков. Она меняется в диапазоне значений от единицы (один эталон на образ) до нуля (число эталонов равно числу обучающих объектов). В последнем случае мы имеем дело с очень плохо подготовленной задачей распознавания. Такого рода ситуация образно выражается известной метафорой «вода в губке», для которой гипотеза компактности не выполняется. Ясно, что о надежном распознавании контрольных реализаций здесь говорить не приходится.