• Метрические алгоритмы классификации
  • Метод ближайших соседей
  • kNN
  • kwNN
  • Метод парзеновского окна
• Байесовские алгоритмы классификации
  • Линии уровня нормального распределения
  • Наивный байесовский классификатор
  • Нормальный дискриминантный анализ
  • Подстановочный алгоритм (Plug-in)
  • Линейный дискриминант Фишера – ЛДФ
• Линейные алгоритмы классифиикации

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

Алгоритм ближайшего соседа (nearest neighbor, NN) является самым простым алгоритмом классификации. Он относит классифицируемый объект u ∈ Xℓ к тому классу, которому принадлежит ближайший обучающий объект:

Обучение NN сводится к запоминанию выборки Xℓ.

Для примера использования методов классификация была взята выборка ирисов фишера по длине и ширине лепестка.

Алгоритм k ближайших соседей (k nearest neighbors, kNN). Метрический алгоритм для автоматической классификации объектов. Объект присваивается к тому классу, который является наиболее распространённым среди k соседей данного элемента, классы которых уже известны.

## Применяем метод kNN
kNN <- function(xl, z, k)
{
  ## Сортируем выборку согласно классифицируемого объекта
	orderedXl <- sortObjectsByDist(xl, z)
	n <- dim(orderedXl)[2] - 1

  ## Получаем классы первых k соседей
	classes <- orderedXl[1:k, n + 1]

  ##Составляем таблицу встречаемости каждого класса
	counts <- table(classes)

  ## Находим класс, который доминирует среди первых k соседей
	class <- names(which.max(counts))
	return (class)
} 

1. Простота реализации.

1. Нужно хранить всю выборку.
2. При k = 1 неустойчивость к погрешностям (выбросам -- объектам, которые окружены объектами чужого класса), вследствие чего этот выброс классифицировался неверно и окружающие его объекты, для которого он окажется ближайшим, тоже.
3. При k = l алгоритм наоборот чрезмерно устойчив и вырождается в константу.
4. Крайне бедный набор параметров.
5. Точки, расстояние между которыми одинаково, не все будут учитываться.

При k=1 алгоритм ближайшего соседа неустойчив к шумовым выбросам: он даёт ошибочные классификации не только на самих объектах-выбросах, но и на ближайших к ним объектах других классов. При k=m, наоборот, алгоритм чрезмерно устойчив и вырождается в константу. Таким образом, крайние значения k нежелательны. На практике оптимальное значение параметра k определяют по критерию скользящего контроля, чаще всего — методом исключения объектов по одному (leave-one-out cross-validation).

Loo <- function(k,xl)
{
	sum <- 0
	for(i in 1:dim(xl)[1]){
		if(i==1){
				tmpXL <- xl[2:dim(xl)[1],]
			}
			else if (i==dim(xl)[1]) {
				tmpXL <- xl[1:dim(xl)[1]-1,]
			}
			else {
					
				tmpXL <- rbind(xl[1:i-1, ], xl[i+1:dim(xl)[1],])
			}

		xi <- c(xl[i,1], xl[i,2])
		class <-kNN(tmpXL,xi,k)
		if(class != xl[i,3])
		sum <- sum+1
	}
	return(sum)
}

Для нашей задачи оптимально k=6, при этом значении алгоритм LOO показывает минимальное количество ошибок, по сравнению с другими значениями k.

Метод взвешенных ближайших соседей. В задачах с числом классов 3 и более нечётность уже не помогает, и ситуации неоднозначности всё равно могут возникать. Тогда i-му соседу приписывается вес w, как правило, убывающий с ростом ранга соседа i. Объект относится к тому классу, который набирает больший суммарный вес среди k ближайших соседей.

kwNN <- function(xl, z, k, q) 
{ 
  orderedXl <- sortObjectsByDist(xl, z) 
  n <- dim(orderedXl)[2] - 1 
  v1 <- c('setosa', 'versicolor', 'virginica')
  v2 <- c(0,0,0)
  
  for(i in 1:k){ 
    orderedXl[i, 4] = q^i 
  } 
  
  a=n+1 
  b=n+2 
  classes <- orderedXl[1:k, a:b]
  
  v2[1]=sum(classes[classes$Species=='setosa', 2])
  v2[2]=sum(classes[classes$Species=='versicolor', 2])
  v2[3]=sum(classes[classes$Species=='virginica', 2])
  
  amo <- cbind(v1,v2)
  
  class <- v1[which.max(v2)]
  return (class) 
}

Loo <- function(k,q,xl)
{
  sum <- 0
  for(i in 1:dim(xl)[1]){
    if(i==1){
      tmpXL <- xl[2:dim(xl)[1],]
    }
    else if (i==dim(xl)[1]) {
      tmpXL <- xl[1:dim(xl)[1]-1,]
    }
    else {
      
      tmpXL <- rbind(xl[1:i-1, ], xl[i+1:dim(xl)[1],])
    }
    
    xi <- c(xl[i,1], xl[i,2])
    class <-kwNN(tmpXL,xi,k,q)
    if(class != xl[i,3])
      sum <- sum+1
  }
  return(sum)
}

Для нашей задачи оптимальными k являются от 3 до 150. При таких значениях k процент ошибок минимальный.

Сравнение качества алгоритмов kNN и kwNN

kNN — один из простейших алгоритмов классификации, поэтому на реальных задачах он зачастую оказывается неэффективным. Помимо точности классификации, проблемой этого классификатора является скорость классификации: если в обучающей выборке N объектов, в тестовой выборе M объектов, и размерность пространства K, то количество операций для классификации тестовой выборки может быть оценено как O(KMN).

kwNN отличается от kNN, тем что учитывает порядок соседей классифицируемого объекта, улчшая качество классификации.

Для демонстрации преимущества kwNN перед kNN, возьмём часть выборки Ирисов Фишера, и применим два метода:

Один из методов классификации объектов - Метод парзеновского окна. В отличие от предыдущих методов, где для классификации объекта мы смотрели на ранг соседей, в методе парзеновского окна мы смотрим на расстоение до блищайших соседей, и после, с помощью функций ядер, задаем им вес. Для того что бы определить сколько соседей нужно взять, используется значение ширина окна (h). Все соседи попавшие в наше окно, будут иметь вес.

PW <- function(xl, z, h) 
{ 
  orderedXl <- sortObjectsByDist(xl, z) 
  
  for(i in 1:150){
    orderedXl[i,3] <- func_ep(orderedXl[i,2],h) 
  }
  
  b1 <- c('setosa', 'versicolor', 'virginica')
  b2 <- c(0,0,0)
  
  b2[1]=sum(orderedXl[orderedXl$Species=='setosa', 3])
  b2[2]=sum(orderedXl[orderedXl$Species=='versicolor', 3])
  b2[3]=sum(orderedXl[orderedXl$Species=='virginica', 3])
  
  amo <- cbind(b1,b2)
  
  if(amo[1,2]==0&&amo[2,2]==0&&amo[3,2]==0){
    class <- 'white'
  }
  else{
    class <- b1[which.max(b2)]
  }
  return (class) 
}

Для примера будут взяты 3 ядра и построены карты классификации.

Для выбора оптимального значения ширины окна, мы будем использовать метод Loo. Мы получим, что для наших ядер и нашей выборки оптимальным значением h является 0.4, при котором минимальное значение процента ошибки - 0.04. Выбор ядра слабо влияет на качество классификации.

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

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

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

Случайная величина x ∈ R имеет нормальное (гауссовское) распределение с параметрами µ и σ^2, если ее плотность задается выражением:

,

Параметры µ и σ^2 определяют, соответственно, мат.ожидание и дисперсию нормальной случайной величины.

Наи́вный ба́йесовский классифика́тор — простой вероятностный классификатор, основанный на применении теоремы Байеса со строгими (наивными) предположениями о независимости. Достоинством наивного байесовского классификатора является малое количество данных необходимых для обучения, оценки параметров и классификации.

naive = function(x, Py, mu, sigm, m, n) {
  amo <- matrix(c('setosa','versicolor', 'virginica', 0, 0, 0), nrow = 3, ncol = 2)
  scores = rep(0, m)
  for (i in 1:m) {
    scores[i] = Py[i]
    for (j in 1:n){
      N=1/sqrt(2*pi)/sigm[i,j]*exp(-1/2*(x[j]-mu[i,j])^2/sigm[i,j]^2)
      scores[i] = scores[i] * N
    }
    amo[i,2]=scores[i]
  }
  class <- amo[,1][which.max(amo[,2])]
}

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

, в которой

– объект, состоящий из n признаков,

– математическое ожидание,

– ковариационная матрица (положительно определенная, симметричная, невырожденная).

Подстановочный алгоритм относится к нормальному дискриминантному анализу.

Mu = function(points) {
    rows = dim(points)[1]
    cols = dim(points)[2]
    mu = matrix(NA, 1, cols)
    for (col in 1:cols) {
        mu[1, col] = mean(points[, col])
    }
    return(mu)
}

.

CovarianceMatrix = function(points, mu) {
    rows = dim(points)[1]
    cols = dim(points)[2]
    covar = matrix(0, cols, cols)
    for (i in 1:rows) {
        covar = covar + (t(points[i,] - mu) %*% (points[i,] - mu)) / (rows - 1)
    }
    return(covar)
}

Недостатки:

• Если длина выборки меньше размерности пространства, то матрица становится вырожденно. В этом случае обратная матрица не существует и метод вообще не применим.

ЛДФ основан на подстановочном алгоритме с предположением, что ковариационные матрицы классов равны. Отсюда следует, что разделяющая поверхность вырождается в прямую. Это условие в plug-in не выполнялось, так как разделяющая поверхность все равно была квадратичной (хоть и приближенной к прямой). Отсюда следует, что ЛДФ должен иметь более высокое качество классификации при одинаковых ковариационных матрицах.

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

При малом количеством объектов выборки, ЛДФ имеет преимущество над Подстановочным алгоритмом.

Пусть , тогда алгоритм называется линейным алгоритмом. В данном пространстве классы разделяет гиперплоскость, которая задается уравнением:. Если x находится по одну сторону гиперплоскости с её направляющим вектором w, то объект x относится к классу +1, в противном случае - к классу -1.

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

Метод стохастического градиента - это итерационный процесс, на каждом шаге которого сдвигаемся в сторону, противоположную вектору градиента 𝑄′(𝑤, 𝑋ℓ)) до тех пор, пока вектор весов 𝑤 не перестанет изменяться, причем вычисления градиента производится не на всех объектах обучения, а выбирается случайный объект (отсюда и название метода «стохастический»), на основе которого и происходят вычисления. В зависимости от функции потерь, которая используется в функционале эмпирического риска, будем получать различные линейные алгоритмы классификации.

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

L(M) - функция потерь.