Федеральное агентство по образованию
Государственное образовательное учреждений
высшего профессионального образования
«Ивановский государственный энергетический
университет им. В.И. Ленина»
Кафедра высокопроизводительных
вычислительных систем
№ 2031
НЕЙРОННЫЕ СЕТИ АДАПТИВНОГО
РЕЗОНАНСА
Методические указания
Иваново 2009
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
«Ивановский государственный энергетический университет
имени В.И.Ленина»
Кафедра высокопроизводительных вычислительных систем
2031
НЕЙРОННЫЕ СЕТИ АДАПТИВНОГО РЕЗОНАНСА
Методические указания
Иваново 2009
Составитель С.Г.СИДОРОВ
Редактор А.А.СКОРОБОГАТОВ
Методические указания содержат теоретический материал,
п|>имс|и । ।ip.п<1 ическои реализации нейронных сетей и задания для
। .iMiii н> ।ii’iii.ною П1.1110ЛЦОИИЯ Рассматриваются вопросы
нр11м<чп1|1ин iiiiopniM.i AH I 1 дня решения задачи кластеризации
11|1пдп । in rii'iii.i дин м.1ги< |рчп и .к пир.нпов, изучающих курсы
11иИ(|<|| (1М11ы<11''р|1Ыг| < и< и'Мы" и "I l<-H|ii>iiiiiю I <чи и искусственный
ИI I I П111II11 I
1,<Ч|1->(.11Ч|Г
др ।	। ок1>1>| пи 111одикч11.ных вычислительных систем
I । )>Н1 И > Ик.111(>1н кии государственный энергетический университет
ИМП11И II И 11<Ч1ИПЛ»
НЕЙРОННЫЕ СЕТИ АДАПТИВНОГО РЕЗОНАНСА
Методические указания
Составитель СИДОРОВ Сергей Георгиевич
Редактор М.А.Иванова
Подписано в печать Л’У/'Уформат 60x84 1/16.
Печать плоская Усл печ.л 0 93 Тираж 30 экз Заказ NqZ/’Z",'
ГОУВПО «Ивановский государственный энергетический университет
имени В.И Ленина»
Отпечатано в УИУНЛ ИГЭУ
153003 г Иваново, ул Рабфаковская, 34
Содержание
Введение.... ............................................     4
Алгоритм ART 1................................................
Детали алгоритма..............................................5
Графическая интерпретация алгоритма...........................6
Функционирование алгоритма................................... ?
Разбор выполнения алгоритма ....................    -	......9
Пример практической реализации алгоритма...................   9
Задания для самостоятельного выполнения......................10
Библиографический список................................. -	 11
Приложения................................................   12
Приложение! Текст программы.......................-..........12
Приложение 2. Пример запуска программы	16
3
Введение
Нейронные сети адаптивного резонанса были предложены
С Гроссбергом (S.Grossberg) в 1976 г Они основываются на теории
адаптивного резонанса (Adaptive Resonance Theory). В
соответствии с ней такие нейронные сети называются ART-сетями.
Резонзнс в них происходит при идентификации какого-либо
(обьния или образа В процессе функционирования ART-сетей в
них происходит циркуляция информации до тех пор, пока не
н.Il tynm < оснп1нип резонанса Нейронные сети адаптивного
рнion.ни ।	о(>у*|.пок я прз учишпя и характеризуются
। .'iMoopi 1НИ11ЦИОИ и пр(1Ц|’<С1' раГхны Они применяются для
ini । ри । щии длиных (р । |днлени । и объединения данных в
in Ihhii пин ipyiiiu.i кп.к h*|>i । по принципу аналогии) и могут быть
и< iioiii 1(1|1.ц||.| дня p.i по||(<п1.1ния образов, обработки речевых
( Hill IIKIII И II «Д.1Ч (X yup. inn пия
Ап1при1мы к пас । приза ции (Clustering algorithm) имеют
г>ип|||11И'|е( koi происхождение, поскольку предоставляют
по.(можносtn обучения посредством классификации. Человеческий
мн.и изучает новые понятия, сравнивает их с уже существующими
знаниями Классификация нового происходит при попытке
объединить его в одном кластере с чем-то уже известным (это
является основой для понимания нового). Если новое понятие
нельзя связать с тем, что уже известно, приходится создавать
новую структуру, чтобы понять явление, которое выходит за рамки
существующей структуры. Впоследствии эта новая модель может
стать основой для усвоения другой информации.
При объединении новых понятий в кластеры с уже
существующими знаниями, а также при создании новых кластеров
для усвоения абсолютно новой информации решается проблема,
которую Гроссберг назвал "дилеммой стабильности-гибкости".
Вопрос состоит в том, как классифицировать новые данные и при
этом не уничтожать уже изученные. Алгоритм ART1 включает все
необходимые элементы, позволяющие не только создавать новые
кластеры при обнаружении новой информации, но и
реорганизовывать с ее учетом уже существующие кластеры
Было создано множество версий алгоритма ART1 как в целях
усовершенствования, так и для решения различных проблем
Алгоритм ART1 работает с дискретными данными, а алгоритм ART2
позволяет классифицировать непрерывный поток данных
(например, временные диаграммы). ARTMAP - это измененный
алгоритм ART, который может изучать изменяющиеся двоичные
схемы. Он представляет собой синтез ART и нечеткой логики.
Существуют и другие алгоритмы из семейства ART.
4
Алгоритм ART1
Алгоритм ART1 работает с объектами, которые называются
векторами признаков (Feature vector). Вектор признаков является
группой значений в двоичном коде, которые представляют
определенный тип информации. Примером вектора признаков
может служить выбор покупок (рис.1).
Рис. 1. Пример вектора признаков
Каждый объект вектора признаков показывает, приобрел ли
покупатель товар (если да, то значение равно 1, если нет — 0).
Покупатель в данном случае купил молоток и гаечный ключ
Этот вектор признаков описывает покупательную способность
путем идентификации приобретенных покупателем предметов.
Собираются векторы признаков покупателя, к которым затем
применяется алгоритм ART1, чтобы разделить данные на кластеры.
Идея состоит в том, что группа схожих данных о покупателе
(содержащаяся в кластере) будет сообщать интересную
информацию о схожих параметрах для группы покупателей.
Детали алгоритма
Обозначим векторы признаков Ej к и группы
инициализированных векторов-прототипов Pi...n- Вектор-прототип
является центром кластера. Количество векторов-прототипов,
равное N, является максимальным количеством кластеров, которое
может поддерживаться. Параметр d показывает длину вектора.
Инициализируются параметр внимательности р небольшим
значением между 0 и 1, а также бета-параметр р, равный
небольшому положительному целому числу. Список рабочих
параметров представлен в табл. 1.
5
Таблица 1. Рабочие параметры
Параметр	Описание
vCIoj	Побитовый И-вектор
||у||	Значимость v (количество значимых элементов вектора)
N	Количество векторов-прототипов
Р	Параметр внимательности (0 < р <= 1)
Р	Вектор-прототип
Е	Вектор признаков
d	Размер векторов (длина)
₽	Бета-параметр
Побитовый И-вектор представляет собой результат побитового
"И" для двух векторов. В итоге получается новый вектор.
Значимость вектора - это количество разрядов в векторе, которые
не равны нулю.
Графическая интерпретация алгоритма
Необходимо найти такие синаптические векторы Р,. Р21 Pn,
которые разбивают входное пространство паттернов на различные
кластеры. Каждый кластер имеет размер, который характеризуется
угловым расстоянием а (рис. 2) и соответствующей ему величиной
р = cos а, называемой параметром бдительности (внимательности).
Рис 2. Разбиение входного пространства образов на кластеры
Если р имеет маленькое значение, то входные векторы будут
отображаться на большие кластеры, в противном случае на
маленькие.
6
Функционирование алгоритма
Алгоритм ART1 работает в соответствии с блок-схемой,
показанной на рис. 3.
Рис. 3. Блок-схема алгоритма ART1
Изначально не существует ни одного вектора-прототипа,
поэтому при выполнении алгоритма создается первый вектор-
прототип из первого вектора-признаков:
Ро=Ео.
(1)
Затем проверяются на схожесть все последующие векторы
признаков с вектором-прототипом. Цель проверки - выяснить,
насколько схож вектор признаков и текущий вектор-прототип.
||Р(П Е|| / (Р + ||Р,||) > ||Е|| / (₽ + d).
(2)
Бета-параметр р, который используется в уравнении проверки
на схожесть (2), - это параметр "разрушения связи". Он выбирает
прототипы, в которых больше значений 1, при условии, что все
значения 1 в векторе-прототипе также присутствуют в тестируемом
векторе признаков.
7
Если тест на схожесть прошел успешно выполняется
следующий тест, чтобы проверить вектор признаков и вектор-
прототип против параметра внимательности:
||Р,ПЕ||/||Е||<р.	(3)
Задачей данного параметра является определение размера
класса. Если значение параметра велико, образуются более
крупные классы (кластеры с большим количеством данных). При
уменьшении значения создаются кластеры с меньшим количеством
данных. Если параметр внимательности задан достаточно низким
(<0,1), для допуска векторы признаков должны соответствовать
вектору-прототипу.
Наконец, если пройден тест на внимательность, алгоритм
добавляет текущий вектор признаков в текущий вектор-прототип
Pi = Р, П Е .	(4)
Этот процесс представляет собой простое слияние вектора
признаков и вектора-прототипа с помощью операции "И". Если тест
на внимательность (или тест на схожесть) не был пройден,
проверяется следующий вектор-прототип. Если все векторы-
прототипы были проверены и при этом вектор признаков не был
помещен в кластер, создается новый вектор-прототип из вектора
признаков. Это приводит к формированию нового кластера, так как
рассматриваемый вектор признаков не соответствует ни одному
существующему кластеру.
Теперь алгоритм проходит через все векторы признаков и
сравнивает их со всеми векторами-прототипами (в соответствии с
блок-схемой). Хотя все векторы уже размещены по кластерам,
проверка необходима. Она позволяет убедиться в том, что векторы
расположены в нужных кластерах. Дело в том, что последующие
тесты векторов признаков могли создать новые кластеры, поэтому
необходимо выполнить дополнительную проверку и удостовериться,
что векторы не нужно перемещать в другие кластеры.
После проверки всех векторов признаков, которая не
потребовала дополнительных изменений, процесс формирования
кластеров можно считать завершенным. Чтобы избежать
перемещения вектора признаков между двумя векторами-
прототипами, алгоритм выполняет несколько итераций, чтобы
объединить кластеры Количество итераций должно быть
достаточно большим, чтобы избежать преждевременного слияния.
8
Разбор выполнения алгоритма
Пример. Предположим, что мы имеем два кластера,
представленных векторами-прототипами Ро = {1,0,0,1,1,0,1} и
Р, = {1,1,0,0,0,1,0}. Вектор признаков имеет следующий вид:
Ео = {1,1,1,0,0,1,0}. Параметры алгоритма имеют следующие
значения: d=7, {3—1, р=0,9. Теперь выполним тесты алгоритма ART1,
чтобы орределить, в признаков.	какой	кластер	будет	помещен вектор
Тест на сходство	Ро/Ех	(2)	1/5>4/8	Нет
Тест на сходство	Р,/Ех	(2)	3/5>4/8	Да
Тест на внимательность	№	О)	3/4<0,9	Да
Pi и Ех	(4)
{1,1,0,0,0,1,0} И {1,1,1,0,0,1,0} = {1,1,0,0,0,1,0}
В первом тесте выполнена проверка на схожесть для вектора-
прототипа Ро. Применение уравнения (2) показало, что тест прошел
неудачно (0,2 не больше, чем 0 5). Затем вектор признаков был
проверен против вектора Ръ В этом случае тест прошел успешно,
поэтому алгоритм выполняет тест на внимательность. Данный тест
также прошел успешно, поэтому вектор признаков ассоциируется с
кластером, который представлен вектором Р,. Затем вектор-
прототип изменяется путем выполнения операции побитового "И"
между вектором-прототипом Pi и вектором признаков (4). После
обновления вектора-прототипа все векторы признаков проверяются
против всех доступных векторов-прототипов. Следует убедиться,
что они находятся в нужных кластерах. После завершения
изменений процесс заканчивается.
В то время как векторы признаков сверяются с векторами-
прототипами, создаются новые кластеры или модифицируются уже
существующие. Это действие известно как "резонанс" и отображает
процесс обучения в алгоритме. Когда алгоритм достигает
равновесия (то есть векторы-прототипы больше не подвергаются
изменениям), обучение завершается и в результате получаются
классифицированные исходные данные.
Пример практической реализации алгоритма
Задача. Проанализировать статистику покупок различных
покупателей и сформировать группы покупателей. На основании
принадлежности к группе выдать рекомендации о приобретении
сопутствующих товаров
9
Текст программы, реализующей данную задачу, приведен в
приложении 1. Результаты запуска программы приведены в
приложении 2.
Задания для самостоятельного выполнения
1	Наберите программу, приведенную в приложении 1. Отладьте ее,
проверьте работоспособность по результатам, выдаваемым
программой. Они должны соответствовать результатам,
представленным в приложении 2.
2.	Исследуйте работу программы при изменении параметра
внимательности (Rho). Составьте таблицы зависимости и
постройте графики, демонстрирующие изменения в работе
программы.
3.	Исследуйте работу программы при изменении параметра
разрушения связей (Beta). Составьте таблицы зависимости и
постройте графики, демонстрирующие изменения в работе
программы.
4.	Исследуйте работу программы при изменении максимального
числа кластеров (MaxClusters). Составьте таблицы зависимости и
постройте графики, демонстрирующие изменения в работе
программы.
5.	На основе приведенного примера составьте программу,
решающую задачу кластеризации для самостоятельно
выбранной группы объектов (буквы, цифры, образы и т.д.).
10
Библиографический список
1	Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика
пер. с англ. / Ф.Уоссермен. - М.: Мир, 1992. - 240 с.
2.	Головко В.А. Нейронные сети: обучение, организация и
применение: учеб, пособие для вузов / В.А.Головко; под общ. ред.
А И.Галушкина. - М ИПРЖР, 2001. - Кн.4. - 256 с. -
(Нейрокомпьютеры и их применение).
3.	Хайкин С. Нейронные сети: полный курс: пер. с англ. / С.Хайкин.
- 2-е изд. - М.: Издательский дом "Вильямс", 2006. - 1104 с.
4.	Сидоров С.Г. Нейрокомпьютеры. Устройство, работа,
моделирование на ПК: метод, указания / С.Г.Сидоров,
Л.П.Чернышева, Б.Л.Ершов, Ф.Н.Ясинский; Иван. гос. энерг. ун-т.
-Иваново 2002.-24с.
5.	Carpenter G., Grossberg S. 1986. Neural dynamics of category
learning and recognition: Attention; memory consolidation and
amnesia. In Brain Structure, Learning and Memory (AAAS
Symposium Series), eds. J. Davis., R Newburgh and E. Wegman.
6.	Carpenter G., Grossberg S. 1987. A massively parallel architecture
for a self-organizing neural pattern recognition machine. Computing
Vision. Graphics, and Image Processing 37:54-115.
7.	Carpenter G., Grossberg S. 1987 ART-2: Self-organization of stable
category recognition codes for analog input patterns. Applied Optics
26(23):4919-30
8.	Crossberg S. 1987. Competitive learning: From interactive activation
to adaptive resonanse. Cognitive Science 11:23-63.
9.	Lippman R.P. 1987. An introduction to computing with neurals nets.
IEEE Transactions on Acosufics, Speech and Signal Processing,
April, pp. 4-22.
11
Приложения
Приложение 1
Текст программы
(**************************************************)
(* Кластеризация покупателей и подбор товара *)
(*	Алгоритм ART1	*)
(*	(с) 2006, Сидоров С.Г.	*)
(**************************************************)
Program ART1;
const Maxitems	=11;	(*число элементов*)
MaxClients	= 10;	(*число покупателей*)
MaxClusters =5;	(*предельное число кластеров*)
Beta	=1.0;	(*параметр разрушения связей*)
Rho	= 0.9;	(*внимательность*)
type TVector — array[1. .Maxitems] of byte;
TClusters — array[1..MaxClusters] of TVector;
TMembers = array[1..MaxClusters] of word;
TGroup = array[1..MaxClients] of word;
const ItemName :array[1..Maxitems] of string[12] =
('Молоток','Бумага*, 'Шоколадка*,'Отвертка* t
'Ручка',* Кофе *, * Гвоздодер’ ,* Карандаш *,
* Конфеты'г ’Дрель’, 'Дырокол') ;
Data:array[1.-MaxClients] of TVector =
((0,0,0,0,0,1,0,0,1,0,0),
(0,1,0,0,0,0,0,1,0,0,1),
(0,0,0,1,0,0,1,0,0,1,0),
(0,0,0,0,1,0,0,1,0,0,1) ,
(1,0,0,1,0,0,0,0,0,1,0) ,
(0,0,0,0,1,0,0,0,0,0,1),
(1,0,0,1,0,0,0,0,0,0,0) ,
(0,0,1,0,0,0,0,0,1,0,0) ,
(0,0,0,0,1,0,0,1,0,0,0),
(0,0,1,0,0,1,0,0,1,0,0)) ;
var Clusters
Sum
Members
Group
N
P
:TClusters;
:TClusters;
:TMembers;
:TGroup;
:word;
:word;
(*прототипы кластеров*)
(*векторы суммирования*)
(*число членов в кластерах*)
(*принадлежность к кластеру*)
(*число кластеров*)
(*текущий покупатель *)
12
procedure Initialize; (*инициализация*)
var i,j .-word; (‘индексы*)
begin
Randomiz e; N:=0;
for i:=l to Maxclusters do begin
for j:=l to Maxitems do begin
Clusters[i][j]:=0; Sum[i][j]:=0;
end;
Members[i]:=0;
end;
for j:=l to MaxClients do Group[j]:=0;
end;
procedure AndVectors(var R:TVector;V,W:TVector);(*И векторов*)
var i :word; (*индекс элемента*)
begin
for i:=l to Maxitems do R[i]:=V[i] and W[i];
end;
procedure UpdateVectors(K:word); (‘обновление прототипа К*)
var i,j	:word;	(‘индексы*)
f	:boolean; (‘флаг первого вектора*)
begin
if (K<l)or(K>MaxClusters) then Exit; f:=true;
for i:=l to Maxitems do begin
ClustersfK][i]:=0; Sum[K][i]:=0;
end;
for j:=l to MaxClients do begin
if Group[j]=K then
if first then begin
Clusters[K]:=Data[j];
Sum[K]:=Data[j];
f:=false;
end else begin
AndVectors(Clusters[K],Clusters[K],Data[j]);
for i:=l to Maxitems do
Sum[K][i]:=Sum[K][i]+Data[j][i];
end;
end;
end;
function CreateVector(var V:TVector):word; (‘новый кластер*)
var i :word; (*индекс кластера*)
begin
i:=0;
Repeat
i:=i+l; if i>MaxClusters then Exit;
Until Members[i]=0,
N:=N+1; Clusters[i]:—V; Members[i]:=1; CreateVector:=i;
end;
function OnesVector(V:TVector) :word; (*число 1 в векторе*)
var j,k :word; (*индекс элемента, количество*)
begin
k:=0; for j:=1 to Maxitems do if V[j]=l then k:=k+l;
OnesVector:=k;
end;			
procedure ExecuteARTl;			(*применение алгоритма ART1*)
var	R	:TVector;	(*вектор ”И"-результата*)
	PE	:word;	(‘значимость нового вектора*)
	P	:word;	(♦значимость вектора-прототипа*)
	E	:word;	(‘значимость вектора покупателя*)
	Test	: boolean;	(*флаг прохождения тестов*)
	ir j	:word;	(‘индексы клиента,прототипа*)
	count	:word;	(‘счетчик предельных итераций*)
	exit	:boolean;	(*флаг выхода из цикла*)
	s	:word;	(*старый номер кластера*)
begin
exit:—false; count:=50;
Repeat
exit:=true;
for i:=l to MaxClients do begin
for j:=l to MaxClisters do begin
if Members[j]>0 then begin
AndVectors(R,Data[i),Clusters[j] ) ;
PE: OnesVector (R) ;
P :=OnesVector(Clusters[j]);
E : Ones Vector (Data [i]) ;
{тест на схожесть} Test:=РЕ/(Beta+P) > Е/(Beta+MaxIterns)
{тест внимательности} if Test then Test:=PE/E < Rho;
if Test then Test:=Group[i] <> j;
if Test then begin
s:=Group[i]; Group[i]:=j;
if s>0 then begin
Dec(Members[s]);
if Members[s]=0 then N:=N-1;
end;
Inc(Members[j ]) ;
UpdateVectors(s) ; UpdateVectors(j)
exit:=false; break;
end;
end ;
end;
if Group[i]=0 then begin
Group [1] :OreateVector (Data [i] ) ;
exit:=false;
end;
end;
count:-count-1;
Until (exit) or (count=0);
end;
14
procedure ShowClusters; (*покаэ кластеров*)
var i,j,k :word; (*индексы*)
begin
for i:=l to N do begin
write('Вектор-прототип ',i:2,': ’);
for j:=l to Maxitems do write(Clusters[i] [ j ], ’ ');
writeIn;
for k:=l to MaxClients do
if Group[k]=i then begin
write('Покупатель ’,k:2,’	: ’);
for j:=l to Maxiterns do write(Data[k][j],r ');
writeIn;
end;
end;
writeIn;
end;
procedure MakeAdvise(P:word); (*рекомендации*)
var i,max,best:word;
begin
best:=O; max:=O;
for i:=l to Maxitems do begin
if (Data[P][i]=0)and(Sum[Group[P]][i]>max) then begin
best:=i; max:=Sum[Group[P],i];
end;
end;
write('Для покупателя ',P,' ');
if best>0 then writeIn('рекоммендация - ',ItemName[best])
else writein('нет рекоммендаций');
write('Уже выбраны: ');
for i:=l to Maxitems do
if Data[P][i]<>0 then write(ItemName[i],' ');
WriteIn;
end;
begin
Initialize;
ExecuteARTl;
Showclusters;
Readln;
for P:=l to MaxClients do MakeAdvise(P);
Readln;
end.
Приложение 2
Пример запуска программы
Вектор-прототип 1: О
Покупатель	1	:	О
Покупатель	8	:	О
Покупатель	10	:	0
Вектор-прототип 2: 0
Покупатель	6	:	0
Покупатель	9	:	0
Вектор-прототип 3: 0
Покупатель	3	:	0
Покупатель	5	:	1
Покупатель	7	:	1
Вектор-прототип 4: 0
Покупатель	2	:	0
Покупатель	4	:	0
0000000100
0000100100
0100000100
0100100100
0001000000
0001000001
0001001000
0010000000
0010010010
0010000010
0010000000
0000001001
1000001001
0001001001
Для покупателя 1 рекоммендация - Шоколадка
Уже выбраны: Кофе Конфеты
Для покупателя 2 рекоммендация - Ручка
Уже выбраны: Бумага Карандаш Дырокол
Для покупателя 3 рекоммендация - Молоток
Уже выбраны: Отвертка Гвоздодер Дрель
Для покупателя 4 рекоммендация - Бумага
Уже выбраны: Ручка Карандаш Дырокол
Для покупателя 5 рекоммендация - Гвоздодер
Уже выбраны: Молоток Отвертка Др< ль
Для покупателя 6 рекоммендация - Карандаш
Уже выбраны: Ручка Дырокол
Для покупателя 7 рекоммендация - Дрель
Уже выбраны: Молоток Отвертка
Для покупателя 8 рекоммендация - Кофе
Уже выбраны: Шоколадка Конфеты
Для покупателя 9 рекоммендация - Дырокол
Уже выбраны: Ручка Карандаш
Для покупателя 10 нет рекоммендаций
Уже выбраны: Шоколадка Кофе Конфеты
16