Функции радиального базиса (пример)

Материал из MachineLearning.

Версия от 19:37, 26 мая 2009; Ostralex (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Содержание

Постановка задачи

Задана выборка X^l, в которой описание каждого объекта является вектором x_{i}\in R^n. Метки классов y_i принадлежат множеству Y=\{+1,-1\}. Считается, что каждый объект выборки x_i имеет некоторый «заряд» \gamma_i и создает в пределах окрестности h_i потенциал, вид которого определяется функцией радиального базиса K(x). Таким образом, суммарный потенциал в точке x\in{R^n} определяется по формуле:

\phi(x)=\sum_{y=1}^{l}{y_{i}\gamma_{i}K(\frac{x_i-x}{h_i})}.

Знак этого потенциала определяет класс объекта x, т.е. классификатор a(x)={\rm sign}\nolimits \phi(x). Требуется оптимизировать значения параметров \gamma_i, h_i.

Алгоритм отыскания оптимальных параметров

Считается, что радиусы всех потенциалов равны между собой (h_i=h \forall i=1,...,l), функция радиального базиса — гауссиана K(x)=\exp(-\beta \|x\|^2). Переменные h и \beta являются структурными параметрами метода. Заряды \gamma_i настраиваются согласно алгоритму:

  1. положить \gamma_i:=0 \forall i=1,...,l.
  2. повторять
  3.    выбрать случайный элемент из выборки
  4.    если a(x_i)\neq y_i то
  5.       \gamma_i:=\gamma_i+1
  6. пока не выполнен критерий останова

Используются следующие критерии останова алгоритма:

  • Ограничение на максимальное количество итераций.
  • Доля ошибок на обучающей выборке — если \sum_{i=1}^l{[y_i\neq a(x_i)]} < \varepsilon, то алгоритм останавливается. \varepsilon является структурным параметром метода.
  • В качестве развития предыдущего пункта — процент ошибок на тестовой выборке X^k, которая

выделяется из обучающей заранее случайным образом. Доля объектов, которые войдут в тестовую выборку, задается извне.

Поскольку подсчет доли ошибок — весьма трудоемкий процесс, то рационально выполнять его не в каждой итерации алгоритма. Частоту проверок можно изменять извне.

Вычислительный эксперимент

Для проверки работоспособности алгоритма использовались наборы реальных и синтетических данных.

1) Реальные данные

В качестве реальных данных использовались данные о сортах ирисов, собранные Фишером. Обучающая выборка состояла из 100 объектов (по 50 объектов каждого из двух классов), обладающих четырьмя вещественными признаками. При использовании всех четырех признаков алгоритм показал очень хороший результат, неправильно классифицировав три объекта. При использовании только первых двух признаков классы глубоко проникают друг в друга; алгоритм работает значительно хуже, неправильно классифицируя около 25 объектов.

Классификация ирисов, использованы 4 признака. Классификация ирисов, использованы 2 признака.

По осям графиков отложены значения признаков. Точки — объекты, цвет точек обозначает принадлежность к тому или иному классу; цвет кружков вокруг точек — результат работы алгоритма.

Во втором случае возможно нарисовать трехмерный график, изображающий потенциал в различных точках пространства признаков:

Потенциал, полученный в результате обучения.

2) Синтетические данные

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

baseL = 200;   %average number of objects in clusters
X = [];
y = [];
L = 0;
CLUSTERS = 5;  %number of clusters
for cl=1:CLUSTERS
    alpha = 0.5 + rand; 
    L2 = floor(baseL*alpha); %number of objects in the cluster
    sigma = 1 + 1.5*rand;  %variance of feature values
    dist = 3 + 5*rand;   %distance to the (0, 0) point
    v = repmat(...
        dist * [sin(2*pi*rand) cos(2*pi*rand)], ...
        [L2, 1]);   %random vector between (0, 0) and the center of the cluster
    X2 = sigma * randn(L2, 2) + v; %objects in cluster
    label = sign(rand-0.5);  %choosing class of objects
    if (label == 0)
        label = 1;
    end
    X = [X; X2];
    y = [y; repmat(label, [L2, 1])];
    L = L + L2; %L is total number of objects
end

2.1) Легкий случай

Синтетические данные, легкий случай. Потеницал, полученный алгоритмом.

Объекты формируют два кластера со слабым взаимным проникновением. Качество классификации хорошее (меньше 5% неправильно определенных меток классов).

2.2) Промежуточный случай

Синтетические данные, промежуточный случай. Потеницал, полученный алгоритмом.

Объекты составляют пять кластеров с существенным проникновением. Неправильно классифицировано около 8% объектов.

2.3) Сложный случай

Синтетические данные, сложный случай. Потеницал, полученный алгоритмом.

Объекты составляют восемь кластеров с сильным проникновением друг в друга. Неправильно классифицировано около 13% объектов.

Исходный код

[1] rbflearn.m, rbfmdl.m (реализация алгоритма); demo_iris.m, demo_synth1.m, demo_synth2.m (вычислительный эксперимент)

Смотри также

Литература

  • К. В. Воронцов. Лекции по метрическим алгоритмам классификации.


Данная статья является непроверенным учебным заданием.
Студент: Участник:Алексей Островский
Преподаватель: Участник:В.В. Стрижов
Срок: 28 мая 2009

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Личные инструменты