8.2. Метод «дробящихся эталонов» (алгоритм ДРЭТ)Так же, как и в предыдущих случаях, будем стремиться к безошибочному распознаванию обучающей выборки, но с использованием покрытий обучающей выборки каждого образа простыми фигурами, усложняющимися по мере необходимости [69]. Один из вариантов этого метода предусматривает использование в качестве покрывающих фигур набора гиперсфер. Для каждого из Рис. 19 Если два образа пересекаются, но в области пересечения не оказалось ни одной реализации обучающей выборки, такое пересечение считается фиктивным, центры и радиусы этих сфер также вносятся в список эталонов первого поколения. При этом область пересечения считается принадлежащей сфере с меньшим радиусом (сфере 2 на рис. 19). Если в зоне пересечения оказались точки только одного образа, то эта зона считается принадлежащей этому образу (сфере 3 на рис. 19). Точка считается относящейся к образу 4, если она попадает в сферу 4 и не попадает в сферу 3. Если же область пересечения содержит точки разных образов, то для этих точек строятся эталоны второго поколения (сферы 5, 6 и 7). Если и они пересекаются, то для точек их зоны пересечения строятся эталоны третьего поколения. Процедура дробления эталонов продолжается до получения заданной надежности распознавания обучающей последовательности. Дальнейшим упрощением алгоритма ДРЭТ служит его разновидность, отличающаяся только тем, что в качестве покрывающих фигур используются гиперпараллелепипеды. Если их стороны параллельны координатным осям, то задание их положения, проверка условия попадания точек внутрь параллелепипедов или в область их пересечения осуществляется с помощью очень простых процедур, что позволяет экономить приблизительно 30% машинного времени по сравнению с предыдущим вариантом. Напомним, что в соответствии с гипотезой Если постановка задачи распознавания предостерегает от ошибочного включения реализаций Опыт показал, что даже в очень сложных случаях для хорошего распознавания обучающей выборки бывает достаточно в среднем не более трех поколений эталонов. Так, при распознавании 11 устных команд для безошибочного распознавания обучающей последовательности потребовалось от 2 до 5 сфер на образ (в среднем 2,8). При распознавании же по одному эталону на образ эти реализации распознавались с ошибкой 45%, что говорит о высокой сложности данной задачи. Если бы мы могли сопоставлять в единых ценах расходы машинных ресурсов на эталоны При распознавании новых реализаций процесс проверки попадания в ту или иную эталонную сферу начинается со сфер наименьшего диаметра. Решающие правила отличаются друг от друга так называемой емкостной характеристикой [25,102]. Она оценивает отношение сложности правила к его разделяющей способности. Алгоритм ДРЭТ вырабатывает очень простые правила, которые вместе с тем могут отделить друг от друга образы со сложными границами, так что эти правила обладают очень хорошей емкостной характеристикой. В заключение отметим, что здесь так же, как и в предыдущем алгоритме, имеется возможность по количеству эталонов судить об информативности признакового пространства. Если для безошибочного распознавания
|