Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 54

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

Afij = (1 + dj (1)

где Afj аффинность между i и j объектами, а dj евклидово расстояние между их признаками.

Необходимо разработать алгоритм кластериза­ции объектов, функционирующий на основе мето­да k-means и иммунных принципов группировки, использующий в качестве основной меры близо­сти объектов критерий (1), позволяющий опреде­лять центры k кластеров и принадлежность к ним исходных объектов.

2. Алгоритм кластеризации

Работу алгоритма k-means можно условно раз­делить на четыре основных этапа [1, 4]:

1. Определение k центров кластеров.

2. Определение принадлежности объектов кла­стерам.

3. Определение центроидов k кластеров.

4. Сравнение центров и центроидов кластеров.

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

Использование ИИС—принципов в организа­ции работы k-means приводит к некоторому из­менению в организации вычислений. Иммунная система оперирует с двумя типами клеток (лимфо­цитов): Т-клетки, распознающие антигены и сти­мулирующие иммунный ответ, и В-клетки, нейтра­лизующие антигены. Антигенами AG(ag1;...;agn) являются все исходные объекты, В-клетки [3]формируют популяцию Bc(bcl;...;bck) и являют­ся кластерами, которые переопределяются в ходе работы алгоритма. В работе данного метода на на­чальном этапе используется популяция T-клеток. Их основная задача заключается в определении критерия пороговой аффинности Afthr и стимуля­ции B-клеток.

Основная идея модифицированного k-means алгоритма при использовании ИИС состоит в том, что предлагаемая модель иммунной сети предпо­лагает, что процесс поиска антигенов уже произ­веден и Т-клетки, вступившие во взаимодействие с антигенами, определили их признаки (априорная завершенность процесса распознавания). В ре­зультате распознавания популяция Т-клеток со­держит признаки всех исходных антигенов, после чего для каждой Т-клетки определяется уровень стимуляции. После отбора k Т-клеток с наиболь­шим уровнем стимуляции формируется популяция В-клеток путем клонирования отобранных объек­тов. После этого популяция В-клеток клонируется и мутирует до тех пор, пока не будут выделены все В-клетки, каждая из которых в ходе клонирования и мутации станет соответствующей некоторому количеству входных антигенов.

Формально предлагаемый иммунньгй алгоритм k-means может быть представлен в виде следующей последовательности операторов:

kmAIS (ag1agn) = stimTcell (t{,...tn), selBmem(blbk), clonBcell (b[;...;b'k), stimBcell (b';bk), matchBcell ((bl;bk ),(b';...; b'k)),

(2)

где stimTcell (t1 ;...tn) — оператор определения уровня стимуляции T-клеток; selBmem(bl;...;bk) — оператор выделения центров В-клеток (исходных центров кластеров); clonBcell (b[;...;bk) — операторы клони­рования, мутации и отбора В-клеток (формиро­вание центроидов); stimBcell (b[;...;bk) — оператор определения уровня стимуляции для получен­ных центроидов (определение принадлежности исходных объектов выделенным кластерам); match((bl;...;bk ),(b';...;bk)) — оператор сравнения клеток памяти Bmem(bl;...;bk) и сформированных клеток Bcell(b';...;b'k).

Следует отметить, что работа оператора clonBcell(b[;...;bk) может происходить на основе следующих подходов:

1. Клонирование граничных антител в В-клетке.

2. Клонирование центра (ядра) В-клетки. Граничные антитела В-клетки определяются с

помощью критерия пороговой аффинности Affthr. Это происходит из предположения, что все антите­ла выделенной В-клетки соответствуют антигенам в ее области, т.е. её антитела по своим признакам идентичны вступившим с ней во взаимодействие

антигенам. После этого граничные антитела под­вергаются клонированию и мутации. Принадлеж­ность объекта (антигена) кластеру (В-клетке) опре­деляется путем выбора максимального веса клонов объектов (антител), соответствующего одной из В-клеток (кластеров).

При клонировании всей В-клетки происходит мутация ее центра, представленного антителом с максимальным уровнем стимуляции ко всем анти­генам, взаимодействующим с В-клеткой, либо её ядром (центроидом). После клонирования и мута­ции центра новое ядро (центроид) отбирается среди полученных клонов на основании конкурентного отбора, при этом ядром (центроидом) становится клон с наибольшим уровнем стимуляции ко всем антигенам В-клетки.

Для определения уровня стимуляции Т-клеток stimTcell (t1 ;...tn) производится вычисление их сред­них аффинностей affiAG со всеми антигенами по­пуляции AG(ag1;...;agn):

affAG

І=1

(3)

где affj аффинность Т-клетки ti и антигена agj.

После этого на основании полученных уровней стимуляции производится определение значения пороговой аффинности Affhr:

Affthr

if

iAG

(4)

Пороговая аффинность используется при опре­делении центров В-клеток (центров кластеров) и определении граничных антител (граничных объ­ектов кластера) при кластеризации.

Перед формированием популяции В-клеток по значениям affiAG определяются k наиболее сти­мулированных Т-клеток, аффинность между ко­торыми не превышает значения Affthr. Эти клетки формируют популяцию В-клеток, каждая из ко­торых изначально характеризуется только одним антителом (центром). Данное антитело становит­ся клеткой памяти системы. После определения центра происходит рост В-клеток — антитела от­носятся к В-клеткам по максимальным значениям аффинности с её ядром (центральным объектом, центроидом).

Клонирование и мутация В-клеток clonBcell(b';...;bk) может происходить на основе указанных подходов. В первом случае (клониро­вание граничных антител) из антител, входящих в В-клетку для клонирования, выбираются анти­тела, аффинность которых к центру В-клетки удо­влетворяет выражению:

affj Af

thr

(5)

n

де affj аффинность i -го антитела с j -ым цен­тром B-клетки (центром кластера), а у коэффици­ент деформации (сжатия) клетки, устанавливаемый в процентах. Для каждого клонируемого антитела количество возможных клонов определяется сле­дующим образом:

clt = int\\(k affj )2||, (6)

где int\\ (j округляет значение до ближайшего большего целого, k количество кластеров, а affj аффинность i -го антитела с центром j -ой В-клетки.

При мутации клонированных антител исполь­зуется оператор гипермутации, в результате чего коэффициент мутации at определяется как:

C (1 - affy), (7)

где affj аффинность i -го антитела с j -ым цен­тром В-клетки, а у коэффициент деформации (сжатия) клетки, устанавливаемый в процентах.

После клонирования и мутации клоны антите­ла определяют аффинности со всеми k центрами В-клеток (центрами кластеров). Принадлежность антитела кластеру определяется по значению общей максимальной аффинности его клонов ядру (цен­тру, центроиду) В-клетки. После этого происходит переопределение ядер (центроидов) В-клеток по средним аффинностям входящих в него антител.

Во втором случае (клонирование центра В-клетки) клонируется только ядро (центральный антиген), при этом количество клонов определяет­ся как количество антител, содержащихся в данной В-клетке, а коэффициент мутации определяется как:

ai =у-affiAG , (8)

где affAG аффинность центра i -й В-клетки с анти­генами множества AG(ag1;...;agn).

После клонирования для каждого из клонов определяется средняя аффинность affAG с антиге­нами AG(ag1;...;agn). В результате конкурентного отбора [5] остается только клон с наибольшим зна­чением аффинности, который формирует новое ядро (центроид) мутировавшей В-клетки.

При определении уровня стимуляции получен­ных ядер (центроидов) В-клеток stimBcell(b{;...;b'k) для каждого нового ядра вычисляется аффинность affAG , которая определяет уровень стимуляции В-клетки.

В работе оператора сравнения match((b1;...;bk),(b[\..:,b'k)) происходит определе­ние аффинности между соответствующими пара­ми центров В-клеток. Клонирование и мутация В-клетки прекращается, если выполняются сле­дующие условия:

affj >Уу^;  C-aj , (9)

где у коэффициент деформации клетки, Affthr пороговая аффинность, affj аффинность между соответствующей парой центров, с{ и с j уровни стимуляции антител.

В случае, если данное условие не выполняет­ся, в памяти происходит замещение предыдуще­го центра В-клетки новым ядром (центроидом) и операции клонирования, стимуляции и сравнения повторяются.

Процесс кластеризации с помощью иммунного k-means алгоритма можно представить как следую­щую последовательность шагов:

1. Определение уровней стимуляции affAG (3) для популяции Т-клеток и значения пороговой аф­финности Afflhr (4) для формируемого популяции В-клеток.

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа