IX Международная студенческая научная конференция Студенческий научный форум - 2017

В статье описана задача группировки объектов, опирающаяся на непараметрическое воссоздание плотности по заданной выборке, и вероятные способы её решения. Работа выполнена в рамках курсового проекта по дисциплине «Machine Learning. Обучающиеся технические системы».

Классификация Байеса – подход, основанный на утверждении, что при известной плотности распределения каждого из исследуемых классов, искомый алгоритм можно выписать в явном аналитическом виде. Алгоритм обладает минимальной вероятностью возникновения ошибок, легко реализуется программно [10].

Цель классификации состоит в том, чтобы понять, к какому классу принадлежит объект X [1].

Существуют три наиболее распространенные подхода к восстановлению плотностей: параметрический, метод расщепления смеси вероятностных распределений, непараметрический [9]. В данной статье рассматривается способ непараметрической классификации на примере метода окна Парзена.

Метод окна Парзена относится к способам классификации, которые не опираются на какие-либо параметры, а также является одним из существующих вариантов исполнения байесовского подхода для выполнения задач классификации [5]. Главной идеей исследуемого метода является утверждение, что концентрация больше в местах, неподалеку от которых располагается большое число элементов выборки. Объекты классифицируются по расположенным на каком-либо удалении от них элементов, веса которых зависят от удаления от исследуемого параметра [6].

В случае, когда значение большого числа простых решений гораздо меньше числа элементов выборки, то как плотность, которая восстановлена по выборке, можно использовать гистограмму составляющих выборки. В противоположном случае этот метод не используется, потому что плотность располагается по близости к используемым для обучения объектам, а функция распределения будет иметь скачкообразный вид [8]. В данном случае необходимо применение других методов классификации.

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

Допустим, – исследуемая выборка,

– множество объектов,

– множество решений для объектов.

х₀ – объект, который нужно классифицировать,

α(x, X^l, h) – алгоритм для классификации. При известной оценке плотности Парзена

Где V(h) – функция, которая зависит от ширины окна, l_y – вспомогательный параметр, который зависит от класса.

Необходимо определить h (величину, от которой зависит точность восстановления плотности, и, следовательно, классификации), а также ядерную функцию К (случайная четная функция, основной вид которой ), так чтобы при группировке этим методом функционал качества был бы максимальным при выполнении алгоритма, когда известны параметры [2]:

λ_y – цена верного ответа для отдельного класса в Y.

Способ нахождения наилучших параметров

Для поиска ширины окна h и соответствующего типа ядра, потребуется использование принципа максимального правдоподобия с последовательным отсеиванием объектов.

Величина группы для одного параметра из исследуемого множества будет восстанавливаться, а логарифм числа верных решений при исключении всех составляющих множества будет последовательно максимизироваться. h определяется подбором из интервала δН, который находится с помощью эмпирических функций [7]. K определяется с помощью функций, которые приведенных в таблице1:

K функции K(r)	Формула
Квартическая
Треугольная
Гауссовская функция
Прямоугольная

Таб. 1 - Функции ядра

Получается:

Примеры

Пример 1.

Задача:

Классификация объектов с использованием функции веса, зависящей от расстояния объекта до соседа.

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

Код программы:

%% генерация двух классов

V=[0 2 2 15; 4 2 2 15];

[X,Y]=normdistgen(V,2);

kL = 1000;

p=size(X,2)/2+2;

[k,q]=kgen(X,Y,kL,p,'gaussian');

hold off;

plot(0,0,'xk');

hold on;

plot(q(:,2),q(:,1),'xr');

%отображение

[YU,v]=crosval(X,Y,k,'gaussian'); %генерация классов

hold off;

classesplotting(X,YU,'o');

classesplotting(X,Y,'x'); %построение правильных классов для всех объектов

%% генерация трех классов

V=[0 2 2 15; 4 2 2 15; 10 4 2 20];

[X,Y]=normdistgen(V,3);

kL = 1000;

p=size(X,2)/2+2;

[k,q]=kgen(X,Y,kL,p,'gauss');

hold off;

plot(0,0,'xk');

hold on;

plot(q(:,2),q(:,1),'xr');

hold off;

% отображение

[YU,v]=crosval(X,Y,k,'gauss'); % генерация классов

hold off;

classesplotting(X,YU,'o');

classesplotting(X,Y,'x'); % построение правильных классов для всех объектов

Пример работы программы:

Рис.1. График с двумя разделенными классами

В эксперименте, изображенном на рисунке 1, видно, что классы настолько сближены, что в результате возникают многочисленные ошибки.

Рис.2. График с тремя разделенными классами

В эксперименте, изображенном на рисунке 2, видно, что сближение классов гораздо ниже, чем в случае с двумя классами. И ошибок в разделении классов возникает существенно меньше.

Согласно проведенным экспериментам можно сделать вывод, что у заметно разделимых классов, алгоритм работает корректно, если правильно выбрано значение k и при любом ядре.

Решение задачи было реализовано с помощью программы GNU Octave [3], также, можно воспользоваться его аналогом, программным пакетом – MATLAB [4].

Пример 2

Задача:

Классификация объектов с использованием реального набора данных

Для реальной задачи выбрана задача классификации аппаратного обеспечения компьютера по 3 критериям (3 класса): минимальный объем основной памяти в килобайтах (minimum main memory in kilobytes), максимальный объем основной памяти в килобайтах (maxmum main memory in kilobytes) и объем кэш-памяти в килобайтах (cache memory in kilobytes). Данные хорошо разделимы по этим признакам.

Код программы:

%getting valid data

load 'computer.txt';

X=computer(:,7:9);

Y=computer(:,1);

Y=Y-1;

%нормализация объектов матрицы

X=normaliz(X);

% генерация k – оптимальной ширины окна

kL=1000;

p=size(X,2)/2+2;

[k,q]=kgen(X,Y,kL,p,'epanechnikov');

% k = 0.3641

% построение результата

[YU,v]=crosval(X,Y,k,'epanechnikov'); %генерация классов

hold off;

classesplotting(X,YU,'o');

classesplotting(X,Y,'x');

Пример работы программы:

Рис.3. График с классами для реальных данных

Из проведенного эксперимента, изображение которого приведено на рисунке 3, можно увидеть, что алгоритм разделил объекты на классы с довольно низким числом ошибок.

СПИСОК ЛИТЕРАТУРЫ

1. Официальный сайт вычислительного центра Российской академии наук http://www.ccas.ru

2. Воронцов К.В., «Лекции по линейным алгоритмам классификации»

3. Официальный сайт Octave: https://www.gnu.org/software/octave

4. Официальный сайт MATLAB: http://matlab.ru

5. Официальный сайт Национального открытого университета http://www.intuit.ru

6. Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006.

7. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999.

8. Лепский А.Е., Броневич А.Г. Математические методы распознавания образов. – Таганрог: Изд-во ТТИ ЮФУ, 2009

9. Sivia D.S., Skilling J. Data Analysis: A Bayesian Tutorial, Oxford, Oxford University Press, 2006

10. Хей Дж. Введение в методы байесовского статистического вывода. — М.: Финансы и статистика, 1987. — 336 с.

Код для цитирования: Скопировать