- Задачи классификации
Задачи классификации
Метрические алгоритмы классификации
Метрические методы обучения - методы, основанные на анализе сходства объектов. Для формализации понятия сходства вводится функция расстояния между объектами . Чем меньше расстояние между объектами, тем больше объекты похожи друг на друга. Метрические классификаторы опираются на гипотезу компактности, которая предполагает, что схожим объектам чаще соответствуют схожие ответы.
Опр 1.1. Метрические алгоритмы классификации с обучающей выборкой относят классифицируемый объект u к тому классу y, для которого суммарный вес ближайших обучающих объектов максимален.
Ниже представлена таблица, в которой сравниваются разные алгоритмы классификации:
| Метод | Параметры | Точность |
|---|---|---|
| knn | k=6 | 0.0333 |
| kwnn | k=6,q=0.5 | 0.0466 |
| PW.Pryamoyg | h=0.3 | 0.04 |
| PW.Treyg | h=0.3 | 0.04 |
| PW.Kvartch | h=0.3 | 0.04 |
| PW.Epanech | h=0.3 | 0.04 |
| PW.Gays | h=0.1 | 0.04 |
Алгоритм k ближайших соседей (kNN)
Данный алгоритм классификации относит классифицируемый объект z к тому классу y, к которому относится большинство из k его ближайших соседей.
Имеется некоторая выборка , состоящая из объектов x(i), i = 1, ..., l (например, выборка ирисов Фишера), и класифицируемый объект, который обозначим z. Чтобы посчитать расстояние от классифицируемого объекта до остальных точек, нужно использовать функцию расстояния(Евклидово расстояние).
Далее отсортируем объекты согласно посчитаного расстояния до объекта z:
sortObjectsByDist <- function(xl, z, metricFunction = euclideanDistance) ## задаем функцию расстояния
{
distances <- matrix(NA, l, 2)## задаем матрицу расстояния
for (i in 1:l)
{
distances[i, ] <- c(i, metricFunction(xl[i, 1:n], z)) ## считаем расстояние от классифицируемой точки до остальных точек выборки
}
orderedXl <- xl[order(distances[, 2]), ] ##сортируем согласно посчитаного расстояния
return (orderedXl);
}Применяем сам метод kNN, то есть создаем функцию, которая сортирует выборку согласно нашего классифицируемого объекта z и относит его к классу ближайших соседей:
kNN <- function(xl, z, k)
{
orderedXl <- sortObjectsByDist(xl, z) ## Сортируем выборку согласно классифицируемого объекта
n <- dim(orderedXl)[2] - 1
classes <- orderedXl[1:k, n + 1] ## Получаем классы первых k соседей
counts <- table(classes) ## Составляем таблицу встречаемости каждого класса
class <- names(which.max(counts)) ## Находим класс, который доминирует среди первых соседей
return (class) ## возвращаем класс
}
В конце задаем точку z, которую нужно классфицировать(ее координаты, выборку и тд).
Ниже представлен итог работы алгоритма при k=6.
kNN
Скользящий контроль(leave-one-out) для knn
LeaveOneOut (или LOO) - простая перекрестная проверка, которая необходима, чтобы оценить при каких значениях k алгоритм knn оптимален, и на сколько он ошибается.
Нужно проверить, как часто будет ошибаться алгоритм, если по одному выбирать элементы из обучающей выборки.
Алгоритм состоит в следующем: извлечь элемент, обучить оставшиеся элементы, классифицировать извлеченный, затем вернуть его обратно. Так нужно поступить со всеми элементами выборки.
Если классифицируемый объект xi не исключать из обучающей выборки, то ближайшим соседом xi всегда будет сам xi, и минимальное (нулевое) значение функционала LOO(k) будет достигаться при k = 1.
Реализация самого LOO в коде выглядит так:
for(k in Ox) {
R <- 0
for(i in 1:l) {
iris_new <- iris[-i, ]
z <- iris[i, 3:4]
if(knn(iris_new, z, k) != iris[i, 5]) {
R <- R + 1
}
}
#после того как мы перебрали все элементы, считаем loo
LOO <- R/l #где R накопитель ошибки, а l-количество элементов выборки
Oy <- c(Oy, LOO)
#Если найденное loo оказалось меньше изначального оптимального значения, то сделаем это новое значение оптимальным и соотвественно k тоже оптимально
if(LOO < LOO_opt) {
LOO_opt <- LOO
k_opt <- k
}
}
График зависимости LOO от k:
k оптимальное (k_opt) достигается при минимальном LOO (оптимальное k равно 6).
Алгоритм 1NN
Алгоритм ближайшего соседа(1NN) является самым простым алгоритмом клссификации.
Данный алгоритм классификации относит классифицируемый объект u к тому классу y, к которому относится его ближайший сосед.
Для начала нужно задать метрическую функцию, затем нужно отсортировать выборку по расстояниям от точек до классфицируемой точки, после чего классифицируемый элемент относим к классу, к которому принадлежит ближайший элемент(первый в отсортированной выборке).
Имеется некоторая выборка Xl, состоящая из объектов x(i), i = 1, ..., l (снова выборка ирисов Фишера). Как и в задаче kNN, задаем функцию расстояния, считаем расстояния от классифицируемой точки до остальных точек выборки, сортируем эти расстояния.
Далее применяем метод 1NN и классифицируем данный объект, то есть найти ближайший объект выборки и вернуть класс, к которому принадлежит наш объект:
# применяем метод 1NN
NN1 <- function(xl, point) {
orderedXl <- sortObjectsByDist(xl, point) # сортировка выборки согласно классифицируемого объекта
n <- dim(orderedXl)[2] - 1
class <- orderedXl[1, n + 1] # получение класса соседа
return (class) # возвращаем класс
}
for(i in OX){
for(j in OY){
point<-c(i,j)
class <- NN1(xl, point)
points(point[1], point[2], pch = 21, col = colors[class], asp = 1) } # классификация заданного объекта
}Ниже представлен итог работы данного алгоритма:
Алгоритм k взвешенных ближайших соседей (kwNN)
Имеется некоторая выборка Xl, состоящая из объектов x(i), i = 1, ..., l ( выборка ирисов Фишера). Данный алгоритм классификации относит объект u к тому классу y, у которого максимальна сумма весов w_i его ближайших k соседей x(u_i), то есть объект относится к тому классу, который набирает больший суммарный вес среди k ближайших соседей.
В алгоритме kwNN используется весовая функция, которая оценивает степень важности при классификации заданного элемента к какому-либо классу, что и отличает его от алгоритма kNN.
kwNN отличается от kNN, тем что учитывает порядок соседей классифицируемого объекта, улучшая качество классификации.
Весовая функция kwNN выглядит следующим образом:
for(i in 1:l) {
weights[i] <- q^i
}Сама функция выглядит так:
distances <- matrix(NA, l, 2)# расстояния от классифицируемого объекта u до каждого i-го соседа
for(p in 1:l) {
distances[p, ] <- c(p, euclideanDistance(xl[p, 1:n], z))
}
orderedxl <- xl[order(distances[ , 2]), ]# сортировка расстояний
weights <- c(NA)# подсчёт весов для каждого i-го объекта
for(i in 1:l) {
weights[i] <- q^i
}
orderedxl_weighted <- cbind(orderedxl, weights)
classes <- orderedxl_weighted[1:k, (n + 1):(n + 2)] # названия первых k ближайших соседей и их веса
sumSetosa <- sum(classes[classes$Species == "setosa", 2])
sumVersicolor <- sum(classes[classes$Species == "versicolor", 2])
sumVirginica <- sum(classes[classes$Species == "virginica", 2])
answer <- matrix(c(sumSetosa, sumVersicolor, sumVirginica),
nrow = 1, ncol = 3, byrow = TRUE, list(c(1), c('setosa', 'versicolor', 'virginica')))#матрица имен классов и их сумм весов, которая заполняется по строкам
points(z[1], z[2], pch = 21, col = colors[which.max(answer)], asp=1) #закрашиваем точки в тот цвет класса, чей вес максимальныйРезультат работы алгоритма:
Ниже представлен график зависимости LOO от q:
Метод Парзеновского окна
Имеется некоторая выборка Xl, состоящая из объектов x(i), i = 1, ..., l (в нашем случае выборка ирисов Фишера).
В данном алгоритме используется такая весовая функция, которая зависит от расстояния между классфицируемым объектом и его соседями, тогда как в алгоритме взвешенных kNN весовая функция зависела от ранга соседа.
Весовая функция для данного алгоритма выглядит так:
, где K(z)-функция ядра, а h-ширина окна.
Используют 5 ядер:
1. прямоугольное:
.
2. треугольное:
.
3. квартическое:
.
4. Епанечникова:
.
5. Гауссовское:
.
Программная реализация данных функций:
RectangularКernel = function(z){
return ((0.5 * (abs(z) <= 1) )) #функция прямоугольного ядра
}
TriangularKernel = function(z){
return ((1 - abs(z)) * (abs(z) <= 1)) #функция для треугольного ядра
}
QuarticKernel = function(z){
return ((15 / 16) * (1 - z ^ 2) ^ 2 * (abs(z) <= 1)) #функция для квартического ядра
}
EpanechnikovKernel = function(z){
return ((3/4*(1-z^2)*(abs(z)<=1))) #функция для ядра Епанечникова
}
GaussianKernel = function(z){
(((2*pi)^(-1/2)) * exp(-1/2*z^2)) #функция для Гауссовского ядра
}Программная реализация самой функции PW:
PW <- function(xl,point, h)
{
weight <- matrix(NA, l, 2) #матрица расстояний и весов
for (p in 1:l) {
weight[p, 1] <- euclideanDistance(xl[p, 1:n], point) # расстояния от классифицируемого объекта u до каждого i-го соседа
z <- weight[p, 1] / h # аргумент функции ядра
cores <- c(RectangularКernel(z), TriangularKernel(z), QuarticKernel(z), EpanechnikovKernel(z), GaussianKernel(z)) #функции ядер
weight[p, 2] <- cores[2] # подсчёт веса для треугольного ядра
}
colnames(classes) <- c("Distances", "Weights", "Species")
sumSetosa <- sum(classes[classes$Species == "setosa", 2])
sumVersicolor <- sum(classes[classes$Species == "versicolor", 2])
sumVirginica <- sum(classes[classes$Species == "virginica", 2])
answer <- matrix(c(sumSetosa, sumVersicolor, sumVirginica),
nrow = 1, ncol = 3, byrow = T, list(c(1), c('setosa', 'versicolor', 'virginica')))
if(answer[1,1]==0&&answer[1,2]==0&&answer[1,3]==0){
class='white'
}
else{
class = colors[which.max(answer)]
}
return(class)
} Ниже представлены результаты работы алгоритма с разными ядрами, также посчитано LOO:
1.
2.
3.
4.
5.
Байесовские классификаторы.
=====================================
Байесовский подход основан на следующей теореме: если плотности распределения классов известны, то алгоритм классификации, имеющий минимальную вероятность ошибок, можно выписать в явном виде.
Чтобы классифицировать точку, для начала, нужно вычислить функции правдоподобия каждого из классов, затем вычислить апостериорные вероятности классов. Классифицируемый объект относится к тому классу, у которого апостериорная вероятность максимальна.
Байесовское решающее правило:
Нормальный дискриминантный анализ
Это случай байесовской классификации, когда предполагается, что плотности распределения всех классов являются многомерными нормальными.
Многомерное нормальное(гауссовское) распределение выглядит следующим образом:
, где
-математическое ожидание;
-ковариационная матрица(положительно определенная, симметричная, невырожденная).
Геометрия нормальной плотности:
В случае, когда признаки некореллированы, то есть , то плотности распределения имеют форму эллипсоидов, параллельных осям координат:
В случае, когда признаки имеют одинаковые дисперсии , линии уровня имеют форму сфер:
В случае, когда признаки коррелированы, а матрица не диагональна, то линии уровня – эллипсоиды, повернутые относительно исходной системы координат:
Наивный байесовский классификатор
Предполагается, что оценивать n одномерных плотностей легче, чем одну n-мерную, поэтому алгоритм называется "наивным". Все объекты выборки X описываются n числовыми признаками fj, где j=1,..,n. Эти признаки являются независимыми случайными величинами.
Функции правдоподобия классов выглядят так:
py(x) = py1(ξ1)⋅⋅⋅pyn(ξn), где pyj(ξj) плотность распределения значений j-го признака для класса y.
Оценка априорной вероятности:
Эмпирическая оценка n-мерной плотности:
Подставив в байесовское решающее правило эмпирические оценки одномерных плотностей признаков получим алгоритм:
Суть работы алгоритма:
Для начала определяем априорные вероятности каждого класса класса. Затем восстанавливаем матрицы математического ожидания и ковариационной матрицы.
Далее определяем саму функцию алгоритма:
naiveBayes = function(x, Py, mu, sigma, m, n) {
prasp <- 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)/sigma[i,j]*exp(-1/2*(x[j]-mu[i,j])^2/sigma[i,j]^2)##считаем эмпирическую оценку n-мерной плотности распределения
scores[i] = scores[i] * N
}
prasp[i,2]=scores[i]
}
class <- prasp[,1][which.max(prasp[,2])] ##относим объект к тому классу, у котрого наибольшая эмпирическая оценка
}
Реализация алгоритма довольна проста, это является преимуществом, также алгоритм оптимален для независимых признаков. Однако алгоритм имеет низкое качество классфикации.
Результат работы алгоритма:
Подстановочный(Plug-in) алгоритм
Нормальный дискриминантный анализ - это специальный случай байесовской классификации, предполагающий, что плотности всех классов являются многомерными нормальными.
Случайная величина x имеет многомерное нормальное распределение, если ее плотность задается выражением:
где 𝜇 ∈ ℝ - математическое ожидание (центр), а 𝛴 ∈ ℝ - ковариационная матрица (симметричная, невырожденная, положительно определённая).
Алгоритм заключается в том, чтобы найти неизвестные параметры 𝜇 и 𝛴 для каждого класса y и подставить их в формулу оптимального байесовского классификатора. В отличие от линейного дискриминанта Фишера(ЛДФ), в данном алгоритме мы предполагаем, что ковариационные матрицы не равны.
Оценка параметров нормального распределения производится на основе параметров функций правдоподобия:
Программная реализация восстановления данных параметров:
Для математического ожидания 𝜇, то есть находим центр нормального распределения элементов класса:
for (col in 1:cols){
mu[1, col] = mean(objects[,col])
}
Для восстановления ковариационной матрицы 𝛴:
for (i in 1:rows){
sigma <- sigma + (t(objects[i,] - mu) %*% (objects[i,] - mu)) / (rows - 1)
}
Результаты работы подстановочного алгоритма:
- Здесь по 250 элементов в каждом классе и ковариационные матрицы равны, поэтому разделяющая линия, как видим, вырождается в прямую(данный случай рассматривается в алгоритме ЛДФ(Линейный дискриминант Фишера), который мы рассмотрим позже):
- Здесь 300 элементов в каждом классе. Видим, что эллипсоиды параллельны осям координат:
Ковариационные матрицы:Sigma1 <- matrix(c(10, 0, 0, 1), 2, 2) Sigma2 <- matrix(c(3, 0, 0, 3), 2, 2)
3. Здесь по 70 эелементов каждом классе. Ковариационные матрицы не равны, разделяющая плотность является квадратичной и прогибается таким образом, что менее плотный класс охватывает более плотный.
Ковариационные матрицы:
```diff
Sigma1 <- matrix(c(3, 0, 0, 1), 2, 2)
Sigma2 <- matrix(c(10, 0, 0, 15), 2, 2)
Линейный дискриминант Фишера
Алгоритм ЛДФ отличается от подстановочного алгоритма тем, что ковариационые матрицы классов равны, поэтому для их восстановления необходимо использовать все объекты выборки. В этом случае разделяющая кривая вырождается в прямую.
Если оценить неизвестную 𝛴(ковариационная матрица, то есть их равенство), с учетом смещенности, то получим следующую формулу:
Восстановление ковариационных матриц в коде алгоритма:
for (i in 1:rows1){
sigma = sigma + (t(points1[i,] - mu1) %*% (points1[i,] - mu1))
}
for (i in 1:rows2){
sigma = sigma + (t(points2[i,] - mu2) %*% (points2[i,] - mu2))
}
Разделяющая плоскость здается формулой:
,
коэффициенты которой находятся следующим образом:
Программная реализация данной функции нахождения коэффициентов ЛДФ выглядит следующим образом:
inverseSigma <- solve(Sigma)
alpha <- inverseSigma %*% t(mu1 - mu2)
beta <- (mu1 %*% inverseSigma %*% t(mu1) - mu2 %*% inverseSigma %*% t(mu2)) / 2Результат работы алгоритма выглядит следующим образом:
Можно сравнить результаты работы алгоритмов с одинаковыми параметрами:
Здесь параметры следующие:
Sigma1 <- matrix(c(2, 0, 0, 2), 2, 2)
Sigma2 <- matrix(c(2, 0, 0, 2), 2, 2) Количество элементов в каждом классе: 50.
1.Подстановочный алгоритм.
2.ЛДФ алгоритм.
Видим, что превосходство ЛДФ очевидно. При чем, я заметила, что при малом количестве элементов в каждом классе ЛДФ превосходит подстановочный алгоритм. Чем меньше элементов, тем хуже работает подстановочный алгоритм.
Линейные алгоритмы классификации
Пусть , тогда алгоритм
называется линейным алгоритмом.
В данном пространстве классы разделяет гиперплоскость, которая задается уравнением:.
Если x находится по одну сторону гиперплоскости с её направляющим вектором w, то объект x относится к классу +1, в противном случае - к классу -1.
Эмпирический риск представлен следующей формулой: .
Для того, чтобы минимизировать его и подобрать оптимальный вектор весов w, рекомендуется пользоваться методом стохастического градиента.
Существует величина , которая называется отступом объекта относительно алгоритма клссификации. Если данный отступ отрицательный, тогда алгоритм совершает ошибку.
L(M) - функция потерь.
Метод стохастического градиента для линейных алгоритмов.
Пусть дана обучающая выборка: множество входных значений X и множество выходящих значений Y, такие что каждому входу xj соответствует yj - выход, j = 1..m.
Нужно найти вектор параметром w, при котором достигается минимум эмпирического риска.
Для этого применим метод градиентного спуска:
1.выберем приближенное значение для вектора параметров w;
2.запускаем итерационный процесс, на каждом шаге которого сдвигаемся в сторону, противоположную вектору
градиента 𝑄′(𝑤, 𝑋ℓ)) до тех пор, пока вектор весов 𝑤 не перестанет изменяться, причем вычисления градиента производится не на всех
объектах обучения, а выбирается случайный объект (отсюда и название метода «стохастический»), на основе которого и происходят
вычисления.
В зависимости от функции потерь, которая используется в функционале эмпирического риска, будем получать различные
линейные алгоритмы классификации.
Рассмотрим только сам итерационный процесс стохастического градиента.
Для начала нужно инициализировть веса w_j; j = 0,..., n и начальную оценку функционала Q, запускаем итерационный процесс:
# стандартная инициализация весов w
w <- c(1/2, 1/2, 1/2)
iterCount <- 0
# определяем Q
Q <- 0
for (i in 1:l) {
wx <- sum(w * xl[i, 1:n])
margin <- wx * xl[i, n + 1]
Q <- Q + lossQuad(margin)
}
repeat {
margins <- array(dim = l)
for (i in 1:l)
{
xi <- xl[i, 1:n]
yi <- xl[i, n + 1]
margins[i] <- crossprod(w, xi) * yi ##находим отступ
}
errorIndexes <- which(margins <= 0) ##инициализируем объекты, на которых выполняется ошибка
if (length(errorIndexes) > 0)
{
# случайным образом выбираем ошибочный объект
i <- sample(1:l, 1)
iterCount <- iterCount + 1
xi <- xl[i, 1:n]
yi <- xl[i, n + 1]
wx <- crossprod(w, xi)
margin <- wx * yi
ex <- lossQuad(margin)
w <- w - eta * (wx - yi) * xi ##расчитываем градиентный шаг для итерации (здесь правило обновления весов представлено для ADALINE)
Qprev <- Q
Q <- (1 - lambda) * Q + lambda * ex ##обновляем Q
} else
{
break
}
}
return(w)
}
Значение функционала Q:
- критеий останова
Qprev <- Q
Q <- (1 - lambda) * Q + lambda * ex
}Повторять все, что вычисляется после инициализации веса и начального значения Q пока значение Q не стабилизируется и/или веса w не перестанут изменяться.
Ниже я рассмотрела примеры работы метода стохастического градиента для линейных алгоритмов(ADALINE, Персептрон Розенблатта и Логистическая регрессия), изменяя лишь функции потерь и правила обновления весов.
Адаптивный линейный элемент(ADALINE)
- это квадратичная функция потерь.
- правило обновления весов на каждом шаге итерации метода стохастического градиента. Данное правило получено путем дифференцирования квадратичной функции.
Программная реализация квадратичной функции потерь:
lossQuad <- function(x)
{
return ((x-1)^2)
} Правило обновления весов:
w <- w - eta * (wx - yi) * xiРабота алгоритма:
Персептрон Розенблатта
- данную функцию потерь называют кусочно-линейной.
- правило обновления весов, которое называют правилом Хебба.
Программная реализация функции потерь:
lossPerceptron <- function(x)
{
return (max(-x, 0))
}Правило обновления весов:
w <- w + eta * yi * xiРабота алгоритма:
Логистическая регрессия
- логистическая функция потерь.
- правило обновления весов, которое называют логистическим, где сигмоидная функция:
.
Программная реализация функции потерь и сигмоидной функции:
##Функция потерь
lossLog <- function(x)
{
return (log2(1 + exp(-x)))
}
## Сигмоидная функция
sigmoidFunction <- function(z)
{
return (1 / (1 + exp(-z)))
}Правило обновления весов:
w <- w + eta * xi * yi * sigmoidFunction(-wx * yi)Работа алгоритма:
Теперь рассмотрим работу алгоритмов одновременно:
