Анотация. 
Новый иммуноподобный алгоритм классификации типа "обучение с учителем" Valis

В статье предлагается новый алгоритм классификации, основанный на принципах функционирования иммунной системы. Работа алгоритма рассматривается на примере задач распознавания символов и классификации текстов.

Описание системы

Существует множество алгоритмов, основанных на различных метафорах естественной иммунной системы: алгоритмы отрицательного отбора, клональной селекции и другие. Предлагаемая система VALIS (Vote Allocating Immune System — иммунная система с распределением голосов) предназначена для классификации и относится к алгоритмам типа «обучение с учителем». Следуя иммунологической метафоре, каждый образец данных представляет собой антиген. Элементарной структурной единицей искусственной иммунной системы является антитело. Молекулы (антигены и антитела) характеризуются наборами параметров, называющихся их обобщёнными формами. В пространстве обобщённых форм задаётся функция расстояния Distance (Ag, Ab) или близости Affinity (Ag, Ab), количественно определяющая степень взаимодействия между антигеном Ag и антителом Ab. Конкретный вид представления молекул и функции расстояния определяется задачей. Вдобавок к обобщённым формам, антитела (как и антигены) имеют ярлыки классов. Аналогично тому, как естественная иммунная система вырабатывает иммунный ответ на присутствующие антигены, алгоритм должен возвращать ярлык класса в ответ на предъявляемые данные.

При предъявлении системе образца данных производится связывание (binding) некоторых антител с предъявленным антигеном. Связывание количественно определяется весом W=F (Distance (Ag, Ab)) или W=F (Affinity (Ag, Ab)). В этой работе используется пороговая функция: Если Distance (Ag, Ab)1 иначе W=0 (Если Affinity (Ag, Ab)>R, W=1 иначе W=0), где R — порог активации (affinity threshold), который может быть глобальным (одинаков для всех антител) или локальным (свой для каждого антитела). В таком случае области связывания антител в пространстве параметров выглядят как гипершары. В качестве F можно использовать и другие функции — например, плавно затухающие вроде W=Exp (-Distance (Ag, Ab)/R), тогда области связывания не будут иметь чётких границ. В антитело можно добавить параметры, определяющие его форму — в таком случае связывание будет происходить в определяемой этими параметрами области. Наконец, для определения веса связывания вместо использования функции F можно использовать правило k-ближайших, когда связанными с антигеном считаются лишь k ближайших к нему антител.

Табл. 1.

При выполнении классификации образца данных, каждое связанное с ним антитело голосует за свой класс (вносит пропорциональный весу связывания вклад в гистограмму). Результат классификации (иммунный ответ) определяется по большинству голосов (максимум гистограммы), в случае нескольких максимумов из них выбирается случайный. При отсутствии связанных антител результатом является «неизвестный класс» .