Теория. Использование теории адаптивного резонанса для решения задач прогнозирования
 Скачать 1.46 Mb.
|
|
Использование теории адаптивного резонанса для решения задач прогнозирования Эль Махмуд Ф. 1 , Григорьев А. А. 2 , Солодовников И.В. 1 1 МГТУ им. Н.Э. Баумана, 2 МИЭМ Введение Прогнозирование является одной из чрезвычайно важных задач в проектировании, при планировании бизнес-процессов и в других областях человеческой деятельности. Важным моментом для проблемы прогнозирования [1] является пересмотр оценок по мере поступления новой информации, с тем чтобы получать новые значения выходных переменных системы (прогнозируемые значения) и корректировать выбор варианта решения. Просмотр и уточнение оценок могут производиться через определенные интервалы времени. В основе подхода лежит разбиение множества обучающих примеров на кластеры и предположение, что попадание объекта в определенный кластер означает, что его прогнозируемые характеристики будут подобны характеристикам примеров, попавших в этот кластер. Объединяя новые понятия в кластеры с уже существующими знаниями, а также создавая новые кластеры для усвоения абсолютно новой информации решается проблема называемая дилеммой стабильности – гибкости. Вопрос состоит в том, как классифицировать новые данные и при этом не уничтожить уже изученные. Этим требованиям удовлетворяет алгоритм Гроссберга и Карпентера [2, 3] – алгоритм теории адаптивного резонанса (ART1), который взят за основу предлагаемого подхода. Теория адаптивного резонанса ART1 включает в себя необходимые элементы, позволяющие не только создавать новые кластеры при обнаружении новой информации, но и реорганизовывать ее с учетом уже существующих кластеров. 97 Алгоритм ART1 работает с объектами, которые называются векторами признаков. Вектор признаков является группой значений в двоичном коде, которые представляют определенный тип информации. Пример такого вектора – выбор покупок. Каждый объект вектора признаков в примере показывает, приобрел ли покупатель товар. Этот вектор признаков задает покупательную способность путем идентификации приобретенных покупателем предметов, о которых мы имеем информацию. Собираются вектора признаков покупателя, к которым затем применяется алгоритм ART1, чтобы разделить данные на кластеры. Группа схожих данных о покупателе (содержащихся в кластере) должна дать информацию о схожих параметрах для группы покупателей. 1 0 0 0 1 0 0 0 молоток ключ бумага Определим группу векторов признаков E E k , , 1 K и группу векторов прототипов P P N , , 1 K . Вектор – прототип является центром кластера. Количество векторов – прототипов N является максимальным количеством кластеров, которое может поддерживаться. Параметр d показывает длину вектора. Инициализируем параметр внимательности ρ , равный небольшому значению от 0 до 1, а также β - параметр, равный небольшому целому числу. Полный список параметров алгоритма следующий: - V ∩ W – побитовый И - вектор; - ⎪⎪ V ⎪⎪ - значимость V (количество значимых элементов вектора); - N – количество векторов прототипов; - ρ - параметр внимательности (0 < ρ ≤ 1); - P – вектор – прототип; - E – вектор признаков; - d - размер вектора; - β - бета – параметр. Побитовый И – вектор представляет собой результат побитового И для двух векторов и является новым вектором. Причем в результирующем векторе бит равен 1, только если в исходных векторах содержится 1 в том же разряде. 98 Изначально не существует ни одного вектора – прототипа. Поэтому в начальный момент времени создается первый вектор прототип из первого вектора признаков E P 1 1 = Затем проверяются на схожесть все последующие вектора признаков с вектором прототипом. Цель проверки выяснить, насколько схожи текущий вектор и вектор прототип. ) ( ) ( d E E P P i i + > + ∩ β β β , используемое в этом уравнении проверки на схожесть – это параметр разрушения связи. Он выбирает прототипы, в которых больше значений 1, при условии, что все значения 1 в векторе прототипе также присутствуют в тестируемом векторе. Если тест на схожесть прошел успешно, выполняется следующий тест, чтобы проверит вектор признаков и вектор – прототип на параметр внимательности: ρ < ∩ E E P i / Задачей данного теста является определение размера кластера. Если значение параметра велико, то образуются кластеры с большим количеством элементов. При уменьшении ρ создаются кластеры с меньшим количеством элементов. Если параметр ρ < 0.1, векторы признаков должны соответствовать вектору прототипу. Если пройден тест на внимательность, алгоритм добавляет текущий вектор признаков в текущий вектор – прототип: E P P i i ∩ = Это слияние вектора признаков с вектором – прототипов с помощью операции И. Если тест на внимательность или схожесть не пройден, проверяется следующий вектор – прототип. Если все векторы – прототипы были проверены, и при этом вектор признаков не был помещен в кластер, создается новый вектор – прототип из вектора признаков. Это приводит к образованию нового кластера, то есть рассматриваемый вектор признаков не соответствует ни одному существующему кластеру. Теперь алгоритм проходит через все векторы признаков и сравнивает их со всеми векторами – прототипами. Хотя все вектора размещены по кластерам, такая 99 проверка необходима. Она позволяет убедиться, что все векторы расположены в нужных кластерах. Дело в том, что последующие тесты векторов признаков могли создать новые кластеры. Поэтому необходимо выполнить дополнительную проверку и удостовериться, что векторы не надо перемещать в другие кластеры. После проверки векторов признаков, которая не потребовала дополнительных изменений, процесс формирования кластеров можно считать завершенным. Чтобы избежать перемещения вектора признаков между двумя векторами – прототипами, алгоритм выполняет несколько итераций, чтобы объединить кластеры. Количество итераций должно быть достаточно большим, чтобы избежать преждевременного слияния. Для параметров β и ρ рекомендуется использовать несколько комбинаций, чтобы найти параметры, при которых можно получить наилучшие результаты. В то время как векторы признаков сверяются с векторами – прототипами создаются новые кластеры или модифицируются старые. Это действие известно как резонанс и отображает процесс обучения в алгоритме. Когда алгоритм достигает равновесия (то есть векторы прототипы больше не подвергаются изменениям), обучение завершается, и в результате получаем кластеризованные исходные данные. Модификация алгоритма для задачи прогнозирования. Для решения задачи прогнозирования введем следующую дополнительную информацию: T – интервал времени, для которого производится прогнозирование E E E i i i 2 1 ∪ = . Здесь E i1 - вектор признаков, на основе которых предполагается проводить прогнозирование, E i2 - вектор признаков, для которых производится прогноз. Таким образом, общие вектора признаков будут образцами, на которых будет производиться обучение. При этом предполагается, что вторая его составляющая была получена в интервале T от момента получения первой составляющей. d d d 2 1 + = - размер вектора признаков Ν p - количество векторов прототипов для векторов признаков { } E i 100 N 0 - количество векторов прототипов для векторов признака { } E i1 Произвести кластеризацию с помощью алгоритма ART1 независимо для векторов признаков { } E i по прототипам и Ν p { } E i1 по прототипам N 0 . Для каждого кластера определить, какое количество векторов признаков попало в кластер . Отношение N j 0 n k j Ν P k m n f k k j jk = , где количество векторов, попавших в кластер , можно рассматривать как значимость или оценку вероятности попадания векторов признаков из кластера в указанный кластер. m k Ν P k N j 0 Пусть теперь на вход системы поступает новый вектор признаков 1 , 1 , 1 , ≥ + r E r k Определим кластер из множества кластеров N 0 , в который он попадает. По значениям f jk можно оценить возможность попадания вектора нового признаков в кластеры Ν . Это и будет предполагаемый прогноз. P Через интервал времени T окончательно сформируем вектор признаков с учетом реальных значений прогнозируемых признаков и выполним кластеризацию на множестве кластеров . При этом состав всех кластеров может измениться, а это означает, что необходимо пересчитать Ν P f jk При использовании алгоритма Гроссберга – Карпентера для решения задачи прогнозирования важное значение приобретает тщательный подбор параметров β, ρ, количества кластеров N 0 и особенно N 0 . Эта проблема подобна центральной проблеме факторного анализа, а именно, идентификации факторов. Здесь же желательно идентифицировать кластеры, на основе которых осуществляется прогноз, в терминах предметной области (например, для медицины в терминах течения или лечения заболеваний, для кадровых систем с точки зрения кадровой политики предприятия и т.д.). Литература 1. Рассел С., Норвиг П. Искусственный интеллект: современный подход. – М.: Издательский дом «Вильямс», 2006. 2. Джонс М.Т. Программирование искусственного интеллекта в приложениях. – М.: ДМК Пресс, 2004 3. Carpenter G., Grossberg S. A Massively Parallel Architecture for a Self-Organizing Neural Pattern Recognition Machine // Computer Vision, Graphics and Image Processing, 37: 54 – 115, 1987 101 |