topfr

Метод последовательного сокращения признаков (Del-метод) [1].

    Пусть задача состоит в том, что из g=50 признаков нужно выбрать наиболее информативную систему, состоящую из n=25 признаков. В качестве критерия информативности будем использовать количество ошибок распознавания w.
     Оценим ошибку распознавания при использовании всех 50 признаков (w0). Затем исключим из системы первый признак и найдем ошибку (w1), которую дают оставшиеся 49 признаков. Поменяем ролями первый и второй признаки и найдем ошибку (w2) в новом 49-мерном пространстве. Эту операцию поочередного исключения одного признака проведем 50 раз.
    Среди полученных величин w1,..., wj,..., w50 найдем самую малую. Она укажет нам на признак, исключение которого из системы было наименее ощутимым. Исключим этот признак из системы и приступим к испытанию оставшихся 49 признаков. Их поочередное исключение из системы позволит   найти   самый неинформативный и снизить размерность пространства до 48. Эти процедуры повторяются (g-n+1) раз, т.е. до тех пор, пока в системе не останется заданное число признаков n.
    Количество проверяемых систем признаков при этом методе равно

L = [g+(g-1)+(g-2)+...+(n+1)] , что значительно меньше полного перебора всех комбинаций из g по n. Так, в нашем примере L = 900, что на 12 порядков меньше объема полного перебора. В литературе [1] приводятся примеры достаточно хорошего решения задач этим методом.
Метод последовательного добавления признаков (Ad-метод) [2].

    Этот алгоритм отличается от предыдущего лишь тем, что порядок проверки подсистем признаков начинается не с g-мерного пространства, а с одномерных пространств. Вначале все g признаков проверяются на информативность. Для этого делается распознавание контрольной   последовательности   по   каждому из g признаков в отдельности и в информативную подсистему включается признак, давший наименьшее число ошибок.
    Затем к   нему   по   очереди   добавляются   все   (g-1) признаков по одному. Получающиеся двумерные подпространства оцениваются по количеству ошибок распознавания. Выбирается самая информативная пара признаков. К ней таким же путем подбирается наилучший третий признак из оставшихся (g-2) и так продолжается до получения системы из n признаков.     Трудоемкость этого алгоритма приблизительно такая же, как и алгоритма Del, однако, результаты, получаемые алгоритмом Ad, обычно лучше, чем у Del. Объясняется этот факт эффектом недостаточной представительности обучающей выборки: при одном и том же объеме   выборки,   чем    выше    размерность    признакового пространства,    тем    меньше    обоснованность    получаемых статистических   выводов   (в   нашем    случае    -    оценки информативности). Средняя размерность выборочного пространства в алгоритме Del равна (g+n)/2, а в алгоритме Ad - n/2, так что риск    ошибочного   признания   информативного     признака неинформативным в Del выше, чем в Ad.
   Оба описанных алгоритма дают оптимальное решение на каждом шаге, но это не обеспечивает глобального оптимума. Причину такого явления можно проиллюстрировать примером из психологии малых коллективов: известно, что два самых дружных между собой человека не всегда входят в тройку самых дружных людей.
   Для ослабления влияния ошибок на первых шагах алгоритма применяется релаксационный метод. Алгоритмом Ad набирается некоторое количество (n1) информативных признаков и затем часть из них (n2<n1) исключаются методом Del. После этого алгоритмом Ad размерность информативных признаков наращивается на величину n1 и становится равной (2n1-n2). В этот момент снова включается   алгоритм   Del,   который   исключает   из системы n2 "наименее ценных" признака. Такое чередование алгоритмов Ad и Del, которое получило название алгоритма AdDel, продолжается до достижения   заданного   количества признаков n.
    Возможна и обратная стратегия: вначале работает алгоритм Del, после сокращения исходной системы   на   n1 признаков включается алгоритм Ad, который возвращает в систему n2 ошибочно исключенных из нее признаков.   Повторение   этих процедур (алгоритм DelAd) продолжается до получения системы из n наиболее информативных признаков.
    Наши эксперименты с этими алгоритмами показали,   что алгоритм AdDel приводит к лучшим результатам, чем алгоритмы Ad, Del и DelAd. При этом n2 бралось равным n1/3.

Метод случайного поиска с адаптацией   (Алгоритм СПА) [3,4]
    Разобьем отрезок (0-1) на g   одинаковых   участков   и сопоставим каждый участок своему признаку:   1-й   участок соответствует первому признаку, 2-й -   второму   и   т.д. Каждый участок имеет ширину 1/g.
    Запускается   датчик   случайных   чисел   с   равномерным распределением в диапазоне (0-1). Если число попадает в j-тый участок, то j-тый признак включается в испытуемый набор признаков. После n шагов работы датчика выбранными оказываются n признаков. Качество этой случайно выбранной подсистемы оценивается по одному их критериев, например, по   числу получаемых ошибок распознавания w.
    Описанная процедура случайного выбора n-мерных подсистем признаков и оценки их качества повторяется r раз. Рассмотрение полученного списка оценок   w1, w2,... wi,... wr позволяет выбрать наилучшую и наихудшую из испытанных подсистем. На этом основании делается процедура "поощрения"   и   "наказания": участки, соответствующие признакам, попавшим в   наилучшую подсистему, "поощряются" путем расширения их   границ   на величину h, а участки, соответствующие признакам из самой неинформативной подсистемы, "наказываются" тем, что их ширина уменьшается на величину h (h<1/g). Суммарная длина всех участков по-прежнему равна 1.
    После этого случайным образом выбираются и испытываются новые r подсистем. Но теперь вероятность попадания признаков в эти подсистемы будет не одинаковой: поощренные признаки, представленные более широкими отрезками, имеют больше шансов войти в очередную подсистему, чем наказанные. По результатам испытания этой партии подсистем процедура адаптации (наказания и поощрения) повторяется.      Если некоторый признак случайно попадает и в самую лучшую и самую худшую подсистемы, то длина его участка остается неизменной. Если же он регулярно оказывается в составе самой информативной подсистемы, то длина его участка растет с каждым шагом адаптации. Точно также, признак, систематически попадающий в самую неинформативную подсистему с каждым шагом сокращает длину своего участка и, тем самым, вероятность его включения в испытуемые подмножества признаков уменьшается.
    После некоторого количества (R) циклов поиска и адаптации процесс стабилизируется: участки удачливых признаков занимают практически весь отрезок (0-1) и в испытуемую подсистему выбираются одни и те же признаки. Этот факт служит сигналом к окончанию процесса выбора   n-мерной   подсистемы   наиболее информативных признаков.
    Скорость сходимости и качество получаемого решения зависит от величины h. При больших h процесс останавливается раньше, но качество полученного решения обычно хуже, чем при малых h. Малые значения h соответствуют   более   мягкой   стратегии поощрений и наказаний.   Направленный таксономический поиск признаков (Алгоритм НТПП) [4,5]
    Если   мы   располагаем   методом    измерения    близости (зависимости) между признаками, то можем сделать таксономию множества g признаков на n таксонов. И если при таксономии объектов в один таксон объединяются наиболее близкие, похожие друг на друга объекты, то в данном случае в таксоны будут объединяться признаки, одинаково или похожим образом проявляющие себя на объектах обучающей выборки.
    Так как в один таксон группируются признаки по принципу максимального сходства (зависимости), то между   таксонами обеспечивается максимальное несходство (независимость).
    Выбрав затем по одному "типичному" признаку из каждого таксона, мы получим n-мерную подсистему, которая включает в свой состав признаки, отличающиеся максимальной независимостью друг от друга. Такая подсистема наилучшим образом соответствует   решающему   правилу,    ориентированному    на использование независимых признаков.
    В реальных задачах может встретиться случай, когда в исходной системе имеются группы признаков, связанных между собой сильной зависимостью, но не несущих информации, полезной для распознавания заданных образов. Такие признаки объединятся в таксоны, их представители попадут в n-мерную подсистему и будут разрушать компактность образов и служить помехой при принятии решений.
    Чтобы избежать   такой   ловушки   в   алгоритме   НТТП предусмотрен следующий прием. Таксономия g признаков делается на n' таксонов (g>n'>n). Из каждого таксона выбирается по одному признаку и делается перебор всех   сочетаний из n' по n признаков. Эти сочетания сравниваются между собой   по критерию информативности, в результате чего удается выбрать наиболее информативную n-мерную подсистему признаков.

Литература:

1. Merill T., Green O.M. On the effectiveness of receptors in recognition systems.- JRE Trans. Inform. Theory, 1963, vol. JT-9, p.11-17.
2.Барабаш Ю.Л., Варский Б.В. и др. Автоматическое распознавание образов. Изд. КВАИУ, Киев, 1964.
3. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. Изд. "Наука" Сибирское отделение, Новосибирск, 1981.
4.Загоруйко Н.Г., Елкина В.Н., Лбов Г.С., Емельянов С.В. Пакет прикладных программ ОТЭКС. Изд. ╚Финансы и Статистика╩, М., 1986.
5.Елкина В.Н., Загоруйко Н.Г., Темиркаев В.С.   Алгоритмы направленного таксономического поиска информативных подсистем признаков (НТПП)// Вычислительные системы: Сб. тр. ИМ СО АН СССР Вып.59, Новосибирск, 1974.