Просмотр

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

У вас нет прав на выполнение этой операции по следующим причинам:

• Запрошенное действие могут выполнять только участники из групп emailconfirmed, Администраторы.
• Вы должны подтвердить ваш адрес электронной почты перед правкой страниц. Пожалуйста, введите и подтвердите ваш адрес эл. почты на странице настроек.

Вы можете просмотреть и скопировать исходный текст этой страницы:

[[Функция радиального базиса]] — функция, значение которой зависит только от нормы аргумента. RBF используются в [[Метрический классификатор|метрических алгоритмах классификации]], в частности в методе потенциальных функций, который (в упрощенном виде) рассматривается в этой статье. ==Постановка задачи== Задана выборка <tex>X^l</tex>, в которой описание каждого объекта является вектором <tex>x_{i}\in R^n</tex>. Метки классов <tex>y_i</tex> принадлежат множеству <tex>Y=\{+1,-1\}</tex>. Считается, что каждый объект выборки <tex>x_i</tex> имеет некоторый «заряд» <tex>\gamma_i</tex> и создает в пределах окрестности <tex>h_i</tex> потенциал, вид которого определяется функцией радиального базиса <tex>K(x)</tex>. Таким образом, суммарный потенциал в точке <tex>x\in{R^n}</tex> определяется по формуле: <center><tex>\phi(x)=\sum_{y=1}^{l}{y_{i}\gamma_{i}K(\frac{x_i-x}{h_i})}.</tex></center> Знак этого потенциала определяет класс объекта <tex>x</tex>, т.е. классификатор <tex>a(x)={\rm sign}\nolimits \phi(x)</tex>. Требуется оптимизировать значения параметров <tex>\gamma_i</tex>, <tex>h_i</tex>. ==Ядерные функции== Одной из важных частей алгоритма является выбор функции радиального базиса <tex>K(x)</tex>. В качестве <tex>K</tex> могут применяться следующие функции (введено обозначение <tex>\|x\|=r</tex>): # Гауссиана <tex>G(x)=\exp(-\beta r^2)</tex>, где <tex>\beta>0</tex>. # Ядро логистической регрессии <tex>L(x)=\frac{1}{1+e^{r/\sigma}}</tex>, <tex>\sigma>0</tex>. # Ядро, соответсвующее ньютонову потенциалу <tex>N(x)=\frac{1}{A+r}</tex>, <tex>A>0</tex>. # Модифицированный ньютонов потенциал <tex>N_n(x)=\frac{1}{A+r^n}</tex>, <tex>A>0</tex>, <tex>n>0</tex>. # Треугольное ядро <tex>T(x)=(1-r)[r\leq 1]</tex>. # Модифицированное треугольное ядро <tex>T_n(x)=(1-r)^{n}[r\leq 1]</tex>, <tex>n>0</tex>. # Прямоугольное ядро <tex>P(x)=[r\leq 1]</tex>. # Ядро Епанечникова <tex>E(x)=(1-r^2)[r\leq 1]</tex>. # Квартическое ядро <tex>Q(x)=(1-r^2)^2[r\leq 1]</tex>. # Обобщенное квартическое ядро <tex>Q_n(x)=(1-r^2)^n[r\leq 1]</tex>, <tex>n>0</tex>. # Обратное мультиквадратичное ядро <tex>M(x)=\frac{1}{\sqrt{A+r^2}}</tex>, <tex>A>0</tex>. # Семейство ядер Вендланда <tex>W_{nl}</tex>, представляющее собой многочлены на отрезке <tex>[-1,+1]</tex> и равные нулю вне его. Они характеризуются двумя параметрами — размерностью пространства <tex>n</tex> и степенью гладкости <tex>l</tex>. В данной реализации используется первые девять ядер: {| class="wikitable" style="text-align: left;" |- bgcolor="#cccccc" ! width=20 % |<tex>n</tex> ! width=20 % |<tex>l</tex> ! width=60 % |<tex>W_{nl}</tex> |- | 1 || 0 || <tex>(1-r)_{+}</tex> |- | 1 || 2 || <tex>(1-r)^{3}_{+}(3r+1)</tex> |- | 1 || 4 || <tex>(1-r)^{5}_{+}(8r^2+5r+1)</tex> |- | 3 || 0 || <tex>(1-r)^{2}_{+}</tex> |- | 3 || 2 || <tex>(1-r)^{4}_{+}(4r+1)</tex> |- | 3 || 4 || <tex>(1-r)^{6}_{+}(7r^2+6r+1)</tex> |- | 5 || 0 || <tex>(1-r)^{3}_{+}</tex> |- | 5 || 2 || <tex>(1-r)^{5}_{+}(5r+1)</tex> |- | 5 || 4 || <tex>(1-r)^{7}_{+}(16r^2+7r+1)</tex> |- |} Используется обозначение <tex>F_{+}=\max(0, F)</tex>. ==Алгоритм отыскания оптимальных параметров== Считается, что радиусы всех потенциалов равны между собой (<tex>h_i=h</tex> <tex>\forall i=1,...,l</tex>). Переменная <tex>h</tex> , а также параметры RBF (если таковые имеются) — структурные параметры метода. Заряды <tex>\gamma_i</tex> настраиваются согласно алгоритму: # положить <tex>\gamma_i:=0</tex> <tex>\forall i=1,...,l</tex>. # повторять # &nbsp;&nbsp;&nbsp;выбрать случайный элемент из выборки # &nbsp;&nbsp;&nbsp;если <tex>a(x_i)\neq y_i</tex> то # &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<tex>\gamma_i:=\gamma_i+1</tex> # пока не выполнен критерий останова Используются следующие критерии останова алгоритма: * Ограничение на максимальное количество итераций. * Доля ошибок на обучающей выборке — если <tex>\sum_{i=1}^l{[y_i\neq a(x_i)]} < \varepsilon</tex>, то алгоритм останавливается. <tex>\varepsilon</tex> является структурным параметром метода. * В качестве развития предыдущего пункта — процент ошибок на тестовой выборке <tex>X^k</tex>, которая выделяется из обучающей заранее случайным образом. Доля объектов, которые войдут в тестовую выборку, задается извне. Поскольку подсчет доли ошибок — весьма трудоемкий процесс, то рационально выполнять его не в каждой итерации алгоритма. Частоту проверок можно изменять извне. ==Вычислительный эксперимент== Для проверки работоспособности алгоритма использовались наборы реальных и синтетических данных. 1) '''Реальные данные''' В качестве реальных данных использовались данные о сортах ирисов, собранные Фишером. Обучающая выборка состояла из 100 объектов (по 50 объектов каждого из двух классов), обладающих четырьмя вещественными признаками. При использовании всех четырех признаков алгоритм показал очень хороший результат, неправильно классифицировав три объекта. При использовании только первых двух признаков классы глубоко проникают друг в друга; алгоритм работает значительно хуже, неправильно классифицируя около 25 объектов. [[Изображение:iris_f_all.png|Классификация ирисов, использованы 4 признака.|300px]] [[Изображение:iris_f_12.png|Классификация ирисов, использованы 2 признака.|300px]] По осям графиков отложены значения признаков. Точки — объекты, цвет точек обозначает принадлежность к тому или иному классу; цвет кружков вокруг точек — результат работы алгоритма. Во втором случае возможно нарисовать трехмерный график, изображающий потенциал в различных точках пространства признаков: [[Изображение:iris_3d.png|Потенциал, полученный в результате обучения.|300px]] 2) '''Синтетические данные''' Синтетические данные представляли собой объекты с двумя признаками из нескольких кластеров. В пределах каждого из кластеров признаки имели нормальное распределение. В зависимости от числа кластеров и параметров распределения задача классификации представляла разную сложность. <source lang="matlab"> 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 </source> 2.1) Легкий случай [[Изображение:synthe_1.png|Синтетические данные, легкий случай.|300px]] [[Изображение:synthe_1_3d.png|Потеницал, полученный алгоритмом.|300px]] Объекты формируют два кластера со слабым взаимным проникновением. Качество классификации хорошее (меньше 5% неправильно определенных меток классов). 2.2) Промежуточный случай [[Изображение:synthm_1.png|Синтетические данные, промежуточный случай.|300px]] [[Изображение:synthm_1_3d.png|Потеницал, полученный алгоритмом.|300px]] Объекты составляют пять кластеров с существенным проникновением. Неправильно классифицировано около 8% объектов. 2.3) Сложный случай [[Изображение:synthd_3.png|Синтетические данные, сложный случай.|300px]] [[Изображение:synthd_3_3d.png|Потеницал, полученный алгоритмом.|300px]] Объекты составляют восемь кластеров с сильным проникновением друг в друга. Неправильно классифицировано около 13% объектов. ==Исходный код== [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group674/Ostrovskiy2009RBF/src/ kernel.m], [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group674/Ostrovskiy2009RBF/src/ rbflearn.m], [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group674/Ostrovskiy2009RBF/src/ rbfmdl.m ] - (реализация алгоритма); [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group674/Ostrovskiy2009RBF/src/ demo_kernel.m] - (демонстрация доступных ядер); [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group674/Ostrovskiy2009RBF/src/ demo_iris.m], [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group674/Ostrovskiy2009RBF/src/ demo_synth1.m], [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group674/Ostrovskiy2009RBF/src/ demo_synth2.m] - (вычислительный эксперимент). ==Смотри также== * [[Media:Ostrovski_Report.pdf|Эта статья в формате PDF]] * [[Метрический классификатор]] * [[Ядерное сглаживание]] * [[Ядерная оценка плотности Парзена-Розенблатта]] * [[Численные методы обучения по прецедентам (практика, В.В. Стрижов)]] ==Литература== * К. В. Воронцов. Лекции по метрическим алгоритмам классификации. * Хардле В. Прикладная непараметрическая регрессия. * Интерактивная помощь программы MATLAB. * Bishop C. Pattern Recognition and Machine Learning. {{ЗаданиеВыполнено|Алексей Островский|В.В. Стрижов|28 мая 2009}} [[Категория:Метрические алгоритмы классификации]] [[Категория:Практика и вычислительные эксперименты]]

• Шаблон:Mbox
• Шаблон:Well
• Шаблон:ЗаданиеВыполнено

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