Метод ближайших соседей в задаче классификации

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

Возьмем пять объектов из таблицы № 1:

{1, 0, 1, 36, 1, 0, 0},

{0, 0, 1, 45, 0, 0, 0},

{0, 0, 1, 24, 0, 0, 1},

{0, 0, 1, 51, 1, 1, 1},

{0, 0, 1, 45, 0, 0, 0}.

 

И пять объектов из таблицы № 2:

{0, 1, 1, 54, 1, 1, 1},

{0, 1, 0, 26, 0, 1, 1},

{0, 0, 1, 32, 1, 0, 0},

{0, 1, 1, 49, 1, 1, 1},

{0, 1, 3, 51, 0, 0, 0}.

После проведения 10 экспериментов получили ошибочные значения в двух случаях, это означает, что вероятность ошибки равна 20% (Рисунок 1).

Рисунок 1.

Если внимательно изучить обучающую выборку в данном примере, не сложно заметить, что практически все характеристики (атрибуты) являются дискретными. Признак « социальное положение» принимает значения от 0 до 2, а признак «образование» – от 0 до 3. И только значения признака «возраст» являются непрерывными. Это, конечно, не означает, что значения данного атрибута являются решающими, но играют большую роль в вычислении конечного результата.

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

.

Для проверки вероятности ошибки возьмем по пять объектов из каждого класса, как было описано выше, и проведем 10 экспериментов.

В данном случае вероятность ошибки составила 10 % (Рисунок 2).

Рисунок 2. 
Задача 2.

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

Задача в данном примере, по набору признаков определить в какой части России (в Центральной или в Восточной части) работает данный гражданин.

В качестве классов будем использовать Центральную часть (Приложение 5) и Восточную часть (Приложение 6) России будем использовать в качестве классов.

Для более удобного вычисления Евклидова расстояния обозначим атрибуты следующим образом (Приложение 7 и Приложение 8):

Пол: женский – 0, мужской – 1;

Образование: высшее – 1, средне-специальное/среднее – 0;

Профессия: юрист – 1, бухгалтер – 2, менеджер – 3, водитель – 4, официант – 5, няня – 6, воспитатель – 7, программист – 8.

Пусть , из этого следует, что наша задача сводится к отысканию одного ближайшего соседа.

Пусть произвольным рабочим, относительно которого мы будем выявлять ближайшего соседа, будет объект со следующими признаками: трудовой стаж – 1 год, женский пол, 16 лет, образование среднее, профессия – официант, заработная плата 10000 – т.е. стаж, пол, возраст, образование, профессия, заработная плата соответственно. Расстояние до объектов вычисляется по тем же формула, что и в Задаче 1.

 

 

 

…

Объекты из таблицы № 5 (Приложение 5) (люди, работающие в Центральной части России) и объекты из таблицы № 6 (Приложение 6) (люди, работающие в Восточной части России), представим в виде двухмерного массива и   соответственно, размерностью 25*6, т.е. 25 элементом, каждый из которых имеет по 6 признаков.

 double m3[][] = {

{5, 0, 35, 1, 1, 60000},

{10, 0, 40, 1, 2, 100000},

{2, 1, 28, 0, 3, 50000},

{3, 1, 33, 0, 4, 35000},

{1, 0, 20, 0, 5, 50000},

{3, 1, 29, 1, 3, 100000},

{5, 0, 45, 1, 6, 35000},

{1, 0, 23, 1, 7, 20000},

{3, 1, 31, 1, 1, 30000},

{2, 0, 25, 1, 1, 35000},

{0, 0, 22, 1, 8, 21000},

{15, 0, 50, 0, 6, 5000},

{5, 1, 35, 1, 1, 60000},

{10, 1, 40, 1, 2, 23000},

{2, 0, 28, 0, 3, 50000},

{3, 1, 33, 0, 4, 35000},

{1, 0, 20, 0, 5, 50000},

{3, 0, 29, 1, 3, 100000},

{5, 1, 45, 1, 6, 35000},

{1, 0, 23, 1, 7, 20000},

{3, 0, 31, 1, 1, 30000},

{2, 0, 25, 1, 1, 35000},

{0, 1, 22, 1, 8, 21000},

{15, 1, 50, 0, 6, 5000},

{5, 0, 35, 1, 1, 60000}

   };

double m4[][] = {

{10, 1, 40, 1, 2, 100000},

{2, 0, 28, 0, 3, 50000},

{3, 0, 33, 0, 4, 35000},

{1, 1, 20, 0, 5, 50000},

{3, 0, 29, 1, 3, 40000},

{0, 0, 18, 1, 6, 12000},

{1, 0, 23, 1, 7, 20000},

{3, 1, 31, 1, 1, 30000},

{2, 1, 25, 1, 1, 35000},

{0, 0, 22, 1, 8, 21000},

{15, 1, 50, 0, 6, 5000},

{5, 0, 35, 1, 1, 21000},

{8, 0, 40, 1, 2, 15000},

{2, 1, 28, 0, 3, 50000},

{3, 0, 33, 0, 4, 35000},

{1, 0, 20, 0, 5, 50000},

{3, 0, 29, 1, 3, 100000},

{5, 1, 45, 1, 6, 35000},

{1, 1, 23, 1, 7, 20000},

{3, 0, 31, 1, 1, 30000},

{2, 1, 25, 1, 1, 35000},

{2, 0, 21, 1, 8, 21000},

{1, 0, 23, 0, 6, 5000},

{3, 0, 25, 1, 1, 18000},

{3, 0, 25, 1, 1, 18000}

   };

Тип элементов массива также определен как Double, для более точного определения «близости» элемента обучающей выборки.

Элементы массива выводим на экран с помощью метода show. С помощью метода calculate вычисляем расстояние от нашего изучаемого объекта до каждого элемента массива.

После вызова необходимых методов получаем следующие значения:

x[0] = 50000.003949999846

x[1] = 90000.00371111103

x[2] = 40000.00186249996

x[3] = 25000.00587999931

x[4] = 40000.0002125

x[5] = 90000.00098888889

x[6] = 25000.017199994083

x[7] = 10000.002749999621

x[8] = 20000.006149999055

x[9] = 25000.00199999992

x[10] = 11000.002181817965

x[11] = 5000.1353981667335

x[12] = 50000.00393999984

x[13] = 13000.025653820841

x[14] = 40000.00187499996

x[15] = 25000.00587999931

x[16] = 40000.0002125

x[17] = 90000.00099444443

x[18] = 25000.017179994098

x[19] = 10000.002749999621

x[20] = 20000.006174999045

x[21] = 25000.00199999992

x[22] = 11000.00213636343

x[23] = 5000.135298169441

x[24] = 50000.003949999846

x[0] = 90000.00370555549

x[1] = 40000.00187499996

x[2] = 25000.005899999305

x[3] = 40000.0002

x[4] = 30000.002983333186

x[5] = 2000.001999999

x[6] = 10000.002749999621

x[7] = 20000.006149999055

x[8] = 25000.00197999992

x[9] = 11000.002181817965

x[10] = 5000.135298169441

x[11] = 11000.017954530802

x[12] = 5000.063599595509

x[13] = 40000.00186249996

x[14] = 25000.005899999305

x[15] = 40000.0002125

x[16] = 90000.00099444443

x[17] = 25000.017179994098

x[18] = 10000.002699999635

x[19] = 20000.006174999045

x[20] = 25000.00197999992

x[21] = 11000.001681818054

x[22] = 5000.005099997399

x[23] = 8000.00643749741

x[24] = 8000.00643749741

Изучив полученные расстояния, очевидно, что минимальное расстояние от произвольного объекта до объекта из обучающей выборки под номером 5 из таблицы № 6, следовательно, объект трудоустроен в Восточной части России.

 

Вероятность ошибки.

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

Как и в первом примере, возьмем по пять объектов из обучающей выборки из каждой таблицы.

Объекты из таблицы № 5:

{3, 0, 31, 1, 1, 30000},

{2, 0, 25, 1, 1, 35000},

{0, 1, 22, 1, 8, 21000},

{15, 1, 50, 0, 6, 5000},

{5, 0, 35, 1, 1, 60000}.

Объекты из таблицы № 6:

{2, 1, 25, 1, 1, 35000},

{2, 0, 21, 1, 8, 21000},

{1, 0, 23, 0, 6, 5000},

{3, 0, 25, 1, 1, 18000},

{3, 0, 25, 1, 1, 18000}.

В данном случае после проведения 10 экспериментов получили ошибочные значения в трех случаях, это означает, что вероятность ошибки равна 30% (Рисунок 3).

Рисунок 3.

Рассмотрим подробнее признаки объектов обучающей выборки в данном примере. Признак «стаж», «возраст», «заработная плата» являются непрерывными, атрибут «профессия» принимает значения от 1 до 8.

Выполним аналогичную проверку, используя метрику

.

Процент частоты ошибки в данном случае 20% (Рисунок 4).

Рисунок 4.

 

Отбор признаков.

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

Для выявления оптимального набора признаков будем проводить эксперименты для выявления частоты ошибок на контрольной выборке. Контрольная выборка сформирована, как описано в предыдущих пунктах, по 5 объектов из каждого класса обучающей выборки. После первого эксперимента, с использованием всех признаков, фиксируем частоту ошибки. В следующих экспериментах проводим последовательное исключение одного из признаков. После проведения вычислений фиксируем частоту ошибки. Если частота ошибки увеличилась, то это значит, что данный признак положительно влияет на качество распознавания, а если уменьшилась либо не изменилась – данный признак исключается из выборки.

Рассмотрим задачу 1 на примере евклидовой метрики. После первого эксперимента частота ошибки составила 20% (Рисунок 5). Строчки на рисунке «На входе» и «На выходе» означают признаки, в данном случае все признаки условно обозначены как 1, что значит использование всех признаков.

Рисунок 5.

В следующем эксперименте исключаем последний признак, в данном примере это признак «Работа». На входе и выходе последнее значение равно 0 (Рисунок 6).

Рисунок 6.

В данном случае частота ошибки не изменилась. На следующем этапе исключаем два последних признака, т.к. последний признак не влияет на качество распознавания, его исключаем (Рисунок 7).

Рисунок 7.

Частота ошибки также остается неизменной. В следующем эксперименте исключаем уже три последних признака, это «Судимость», «Соц.положение», «Работа» (Рисунок 8).

Рисунок 8.

В этом случае частота ошибки также не изменилась. На следующем этапе исключаем четыре последних признака (Рисунок 9).

Рисунок 9.

На последнем этапе значение частоты ошибки уменьшилось и составило 10%. Для данного примера получили 3 признака (Пол, Семейное положение, Образование), наиболее оптимальных для рассматриваемой задачи, так как наша выборка состоит небольшого количества признаков.

 

Описание основных методов программного продукта.

Все входные данные хранятся в отдельном классе Data. Основные методы описаны в классе Mass, пользовательский интерфейс реализован в классе Diplom. Все данные из таблиц представлены в виде двухмерных массивов: m1, m2 – по примеру № 1 (классификация преступлений), m3, m4 – по примеру № 2 (определение географической части России по трудовой деятельности граждан).

Расстояние от изучаемого объекта до каждого объекта выборки вычисляется с помощью Евклидовой метрики, также реализована возможность вычисления расстояния с помощью формулы:

,

которая реализована в двух методах ro и metric:

public static double ro (double [] y, double [] x){

double maxValue = 0;

for ( int i = 0; i < x.length; i++){

 double curValue = Math.abs(x[i] - y[i]);

  if (curValue > maxValue)

   maxValue = curValue;

}

return maxValue;

}

public static double[] metric (double [][] matrix, double[] x){

double[] result = new double[matrix.length];

for ( int i = 0; i < matrix.length; i++){

result[i] = ro(matrix[i], x);

}

Arrays.sort(result);

return result;

}

Метод реализующий вычисление Евклидовой метрики, euclMetric, был описан выше. 

Два метода show осуществляют вывод на экран двумерного либо одномерного массива, в зависимости от входных данных.

public static void show (double[] matrix){

for ( int k = 0; k < matrix.length; k++) {

System.out.print(matrix[k] + " ");

System.out.println();

}

}

public static void show (double[][] matrix){

for ( int k = 0; k < matrix.length; k++) {

for (int l = 0; l < matrix[0].length; l++)

System.out.print(matrix[k][l] + " ");

System.out.println();

}

}

Сортировка массивов осуществляется при помощи метода sort() из класса Arrays:

Arrays.sort(arr1);