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

В ******, если несколько классов набрали равное количество ******* необходимо ************ взвешенное голосование.

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

 

где – квадрат расстояния от *звестной записи до новой , – количество **вестных записей класса, для которого рассчитываются *****а, – наименование класса.

Класс, набравший наибольшее количество голосов, присуждается новой записи. Совершенно очевидно, что при новой записи присваивается класс самого ближайшего соседа.

Положительными особенностями метода являются:

1. Алгоритм устойчив к аномальным выбросам, так как вероятность попадания такой записи в число -*лижайших соседей мала. Если же это произошло, то влияние на голосование (особенно взвешенное) (при ) также, скорее всего, будет незначительным, и, следовательно, малым будет и влияние на итог классификации.
2. Программная реализация алгоритма относительно проста.
3. Результат работы алгоритма легко поддаётся интерпретации. Экспертам в различных областях вполне понятна логика работы алгоритма, основанная на нахождении схожих объектов.
4. Возможность модификации алгоритма, путём использования наиболее подходящих функций сочетания и метрик позволяет подстроить алгоритм под конкретную задачу [4].

Сравнительный анализ ошибок метода ближайших соседей и метода Байеса.

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

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

 

Первый член выражения дает условную вероятность ошибки для  
, второй для и т.д. Воспользовавшись тем, что 
, перепишем (1) в виде

 

С другой стороны, условная вероятность ошибки байесовского решающего правила равна:

 

где , . Воспользовавшись неравенством Шварца, получим:

 

Прибавляя к левой и правой частям (4) получим:

 

Комбинируя (2) и (5), имеем:

 

Взяв математическое ожидание от левой и правой частей (6) получаем:

 

Из (7) следует, что вероятность ошибки ε метода ближайших соседей в случае нескольких классов меньше, чем удвоенная вероятность ошибки байесовского решающего правила [3].

 

 

Глава3.Практическая реализация алгоритма ближайшего соседа.

Среда разработки.

Для реализации дипломного проекта используется язык программирования Java. Средством разработки является Java Development Kit (сокращенно JDK) версии 7 – бесплатно распространяемый компанией Oracle Corporation комплект разработчика приложений на языке Java, включающий в себя компилятор Java (javac), стандартные библиотеки классов Java, примеры, документацию, различные утилиты и исполнительную систему Java (JRE). Средой разработки является программная платформа  Eclipce Kepler  с открытым исходным кодом, написанная на языке Java [5]. 

Приложения на языке Java исполняются в специальной, универсальной среде, которая называется Java Virtual Machine. JVM - это программа, которая пишется специально для каждой реальной платформы, чтобы, с одной стороны, скрыть все ее особенности, а с другой – предоставить единую среду исполнения для Java - приложений. За счет использования виртуальной машины обеспечивается кроссплатформенность языка Java. 

Java -платформа обладает следующими преимуществами:

• переносимость, или кроссплатформенность;
• объектная ориентированность, создана эффективная объектная модель;
• привычный синтаксис С/С++;
• динамичность, легкость развития и добавления новых возможностей;
• простота освоения;
• бесплатное распространение комплекта разработчика приложений JDK.

Также большим плюсом является бесплатное распространение программной платформы (среды разработки) Eclipce Kepler [6].

 

Задача 1.

В качестве обучающей выборки будем использовать набор данных состоящий из двух таблиц. В первой таблице представлены характеристики людей, совершивших преступления против личности (Приложение 1), во второй – характеристики людей, совершивших преступления против порядка управления (Приложение 2).

Посягательства на жизнь и здоровье человека являются одним из наиболее тяжких и опасных преступлений, поскольку они наносят непоправимый (необратимый) вред важнейшим социальным ценностям – жизни человека. Особую остроту уголовно-правовым средствам борьбы с преступлениями против жизни придают современные неблагоприятные процессы в динамике и структуре данных посягательств: увеличение количества умышленных убийств, применение для их совершения общеопасных и жестоких способов, увеличение убийств, обусловленных корыстными мотивами и т.п.

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

Наша задача, по набору признаков преступника определить, какое преступление совершил исследуемый объект.

Преступления против личности и преступления против порядка управления будем использовать в качестве классов. Рассмотрим следующие признаки (n): пол, семейное положение, образование, возраст, наличие ранее судимости, социальное положение и занятость (данные указаны в таблицах 3 и 4).

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

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

Семейное положение: женат/ замужем – 1, холост/ не замужем – 0;

Образование: высшее – 3, ср.-специальное – 2, среднее – 1,

 неполное среднее – 0;

Судимость: ранее не судим – 1, ранее судим – 0;

Социальное положение: высокое – 2, среднее – 1, низкое – 0;

Занятость: имеет работу – 1, не имеет работу – 0.

Пусть значит наша задача сводится к отысканию одного ближайшего соседа, который будет ********ть принадлежность исследуемого объекта к классу ( – преступления против личности или – преступления против порядка управления).

Предположим, что исследуемый объект (преступник) , имеет следующие признаки: мужского пола, женат, высшее образование, 25 лет, ранее не судим, среднее социальное положение, работает. 

Таким образом ,  т.е. пол, семейное положение, образование, возраст, наличие ранее судимости, социальное положение и ****тость соответственно.

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

Расстояние до объектов из таблицы 1 вычисляем по следующим формулам:

 

 

 

…

Расстояние до объектов из таблицы 2 вычисляем по следующим формулам:

 

 

 

…

Объекты из таблицы № 1 (преступники совершившие преступление против личности), представим в виде двухмерного массива размерностью 25*7, т.е. 25 элементом, каждый из которых имеет по 7 признаков.

double m1[][] = {

{0, 1, 2, 21, 0, 0, 1},

{0, 0, 1, 21, 1, 0, 0},

{0, 1, 2, 23, 0, 0, 1},

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

{0, 0, 1, 37, 0, 0, 1},

{0, 1, 1, 42, 1, 1, 1},

{0, 0, 0, 16, 1, 0, 0},

{0, 1, 1, 34, 1, 0, 1},

{0, 1, 2, 53, 1, 1, 1},

{0, 0, 1, 29, 0, 0, 1},

{0, 0, 1, 41, 0, 0, 0},

{1, 0, 2, 34, 1, 1, 1},

{1, 0, 0, 35, 1, 0, 0},

{1, 0, 2, 30, 1, 0, 0},

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

{0, 0, 0, 40, 0, 0, 0},

{0, 0, 2, 28, 0, 0, 0},

{0, 1, 1, 43, 1, 1, 1},

{0, 0, 2, 44, 0, 0, 0},

{0, 0, 1, 31, 0, 0, 0},

{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 (преступники совершившие преступление против общественного порядка) представим в виде двухмерного массива той же размерности.

double m2[][] = {

{0, 1, 1, 39, 1, 1, 1},

{0, 0, 3, 39, 1, 1, 1},

{0, 1, 1, 48, 1, 1, 1},

{1, 0, 1, 30, 1, 1, 1},

{0, 0, 1, 28, 0, 0, 0},

{0, 1, 3, 38, 1, 1, 1},

{0, 0, 1, 53, 1, 1, 1},

{1, 1, 1, 39, 0, 1, 1},

{0, 0, 1, 41, 1, 1, 1},

{0, 0, 3, 43, 1, 1, 1},

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

{1, 0, 1, 56, 0, 1, 1},

{0, 0, 1, 48, 1, 1, 1},

{0, 1, 3, 47, 1, 2, 1},

{0, 0, 1, 43, 1, 1, 1},

{0,  1,  1, 35, 0, 1, 1},

{0, 1, 1, 29, 1, 1, 1},

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

{0, 1, 1, 34, 0, 1, 1},

{0, 0, 1, 37, 0, 1, 1},

{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}

};

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

С помощью метода show выводим на экран элементы массива.

public static double[][] show (double[][] arr){

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

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

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

System.out.println();

}

return arr;

}

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

public static double[] calculate (double[][] matrix, double[] person){  

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

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

x[k] = 0;

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

x[k] += Math.pow((person[l] - matrix[k][l]), 2);

x[k] = Math.sqrt(x[k]);

System.out.println("x[" + k + "] = " + x[k]);

}

return x;

} 
Получили значения:

Данные таблицы №1:

x[0] = 4.358898943540674

x[1] = 4.795831523312719

x[2] = 2.6457513110645907

x[3] = 26.115129714401192

x[4] = 12.288205727444508

x[5] = 17.11724276862369

x[6] = 9.643650760992955

x[7] = 9.273618495495704

x[8] = 28.0178514522438

x[9] = 4.795831523312719

x[10] = 16.24807680927192

x[11] = 9.16515138991168

x[12] = 10.63014581273465

x[13] = 5.477225575051661

x[14] = 26.095976701399778

x[15] = 15.427248620541512

x[16] = 3.7416573867739413

x[17] = 18.110770276274835

x[18] = 19.131126469708992

x[19] = 6.6332495807108

x[20] = 11.357816691600547

x[21] = 20.199009876724155

x[22] = 2.8284271247461903

x[23] = 26.095976701399778

x[24] = 20.199009876724155

Данные таблицы №2:

x[0] = 14.142135623730951

x[1] = 14.035668847618199

x[2] = 23.08679276123039

x[3] = 5.5677643628300215

x[4] = 4.123105625617661

x[5] = 13.0

x[6] = 28.089143810376278

x[7] = 14.212670403551895

x[8] = 16.15549442140351

x[9] = 18.027756377319946

x[10] = 2.449489742783178

x[11] = 31.11269837220809

x[12] = 23.108440016582687

x[13] = 22.02271554554524

x[14] = 18.138357147217054

x[15] = 10.246950765959598

x[16] = 4.47213595499958

x[17] = 26.038433132583073

x[18] = 9.273618495495704

x[19] = 12.24744871391589

x[20] = 29.068883707497267

x[21] = 3.3166247903554

x[22] = 7.483314773547883

x[23] = 24.08318915758459

x[24]=26.057628441590765Изучив полученные расстояния, получили, что минимальное расстояние от произвольного объекта до объекта из обучающей выборки под номером 10 из таблицы № 2, следовательно, произвольный преступник вероятней всего совершил преступление против порядка управления.

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

Имеем два значения из первого класса: x[2] = 2.6457513110645907, x[22] = 2.8284271247461903, и два значения из второго класса: x[10] = 2.449489742783178, x[21] = 3.3166247903554. То есть равное количество голосов. Необходимо применить взвешенное голосование, используя формулу:

 

Получили следующие значения: class1 = 15/56,  class2 = 17/66.

сlass1 › class2 – следует, что изучаемый объект принадлежит классу 1, т.е. объект совершил преступление против порядка управления.

 

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