Методы классификации. Методы прогнозирования (лекция 2)

1.

2 лекция
Методы классификации
Методы прогнозирования
Ростова Е.П.

2.

Методы классификации
Метод К-ближайших соседей (K-Nearest Neighbors);
Метод опорных векторов (Support Vector Machines);
Классификатор дерева решений (Decision Tree Classifier) /
Случайный лес (Random Forests);
Наивный байесовский метод (Naive Bayes);
Линейный дискриминантный анализ (Linear Discriminant
Analysis);
Логистическая регрессия (Logistic Regression).
Методы прогнозирования
Ростова Е.П.

3.

Алгоритм K-ближайших соседей (KNN)
1. Используется для классификации, регрессии, обнаружения
выбросов
2. Нет специализированной фазы обучения. Все данные
используются для обучения
Методы прогнозирования
Ростова Е.П.

4.

Алгоритм K-ближайших соседей (KNN)
Известные объекты:
n - количество объектов
i - номер объекта
xij - значение для i-го объекта j-го признака
Новый объект:
x*j - значение для нового объекта j-го признака
Методы прогнозирования
Ростова Е.П.

5.

Алгоритм K-ближайших соседей (KNN)
Вычисляем «расстояние» от известных объектов до нового объекта
di
x
m
j 1
ij
x * j
2
расстояние от нового объекта до известного i-го объекта
Методы прогнозирования
Ростова Е.П.

6.

Алгоритм K-ближайших соседей (KNN)
Определяем К «ближайших соседей».
К - натуральное число (2, 5 или 10)
К=2
Методы прогнозирования
Ростова Е.П.

7.

Алгоритм K-ближайших соседей (KNN)
Методы прогнозирования
Ростова Е.П.

8.

Алгоритм K-ближайших соседей (KNN)
К=5
К=1
Методы прогнозирования
Ростова Е.П.

9.

Алгоритм K-ближайших соседей (KNN)
Методы прогнозирования
Ростова Е.П.

10.

Алгоритм K-ближайших соседей (KNN)
Самара
Нижний Новгород
Омск
Новосибирск
Ростов - на – Дону Казань
Екатеринбург
Волгоград
Воронеж
Краснодар
Методы прогнозирования
Ростова Е.П.
Уфа
Пермь
Челябинск
Красноярск

11.

Алгоритм K-ближайших соседей (KNN)
Если это задача регрессии, KNN рассчитает средневзвешенную сумму
K-ближайших точек для прогноза.
Каждый объект имеет результирующий признак уi.
Задача: рассчитать значение результирующего признака у* для нового
объекта
Методы прогнозирования
Ростова Е.П.

12.

Алгоритм K-ближайших соседей (KNN)
Методы прогнозирования
Ростова Е.П.

13.

Алгоритм K-ближайших соседей (KNN)
К=3
если веса =1,
тогда
у*=(30*1+26*1+24*1)/3=
=26,7
Методы прогнозирования
Ростова Е.П.

14.

Алгоритм K-ближайших соседей (KNN)
К=3
если веса разные,
тогда
у*=(30*3+26*2+24*1)/6=
=27,65
Методы прогнозирования
Ростова Е.П.

15.

Алгоритм K-ближайших соседей (KNN)
К=6
если веса =1,
тогда
у*=(49*1+38*1+30*1+
+26*1+17*1+24*1)/6=
=30,7
Методы прогнозирования
Ростова Е.П.

16.

Алгоритм K-ближайших соседей (KNN)
площадь, кв.м.
63,1
61,8
75,7
65,3
74,3
75,0
67,2
72,3
50,1
59,9
54,3
58,2
60,0
57,4
79,6
51,4
48,4
41,3
район
Красноглинский
Красноглинский
Советский
Куйбышевский
Кировский
Промышленный
Советский
Кировский
Ленинский
Ленинский
Октябрьский
Самарский
Октябрьский
Куйбышевский
Самарский
Ленинский
Октябрьский
Красноглинский
этаж
3
3
4
2
2
3
4
4
3
2
4
3
2
2
3
2
2
Методы прогнозирования
2
год постройки
1992
1989
1988
1992
1992
1994
1986
1985
1999
1994
1985
1993
1984
1983
1997
1987
1984
Ростова Е.П.
1993
цена, млн руб.
4,135
4,468
4,729
2,950
4,101
3,542
3,968
3,904
3,481
2,658
2,796
1,482
1,690
1,238
1,013
3,134
1,942
3,432

17.

Алгоритм K-ближайших соседей (KNN)
площадь, кв.м.
74,3
72,3
63,1
61,8
41,3
65,3
57,4
50,1
59,9
51,4
54,3
60,0
48,4
75,0
58,2
79,6
75,7
67,2
район
Кировский
Кировский
Красноглинский
Красноглинский
Красноглинский
Куйбышевский
Куйбышевский
Ленинский
Ленинский
Ленинский
Октябрьский
Октябрьский
Октябрьский
Промышленный
Самарский
Самарский
Советский
Советский
этаж
год постройки
2
1992
4
1985
3
1992
3
1989
2
1993
2
1992
2
1983
3
1999
2
1994
2
1987
4
1985
2
1984
2
1984
3
1994
3
1993
3
1997
4
1988
Методы
Ростова Е.П.
4 прогнозирования 1986
цена, млн руб.
4,101
3,904
4,135
4,468
3,432
2,950
1,238
3,481
2,658
3,134
2,796
1,690
1,942
3,542
1,482
1,013
4,729
3,968
Достаточно ли
этих данных?
Какие еще
признаки надо
добавить?

18.

Методы прогнозирования
Ростова Е.П.

19.

Алгоритм K-ближайших соседей (KNN)
если добавить веса к признакам
признак
площадь
ремонт
количество комнат
год постройки
район
этаж
вес
0,28
0,2
0,1
0,05
0,33
0,04
Методы прогнозирования
Ростова Е.П.

20.

Метод опорных векторов (Support Vector
Machines)
Рассматривается задача
бинарной классификации
у={-1: +1}
Требуется определить
принадлежность нового
объекта к одному из
классов.
Методы прогнозирования
Ростова Е.П.

21.

Метод опорных векторов (Support Vector
Machines)
a1x1 a2x2 b 0
n(a1 , a2 )
Методы прогнозирования
Ростова Е.П.

22.

Метод опорных векторов (Support Vector
Machines)
Граница классов
a1x1+a2x2-b=0
a , x b 0
a R2, x R2
Методы прогнозирования
Ростова Е.П.

23.

Метод опорных векторов (Support Vector
Граница классов
Machines)
a1x1+a2x2 +a3x3 - b=0
a , x b 0
a R , x R
3
3
a1x1+a2x2 +...amxm - b=0
a , x b 0
Методы прогнозирования
Ростова Е.П.
a Rm , x Rm

24.

Метод опорных векторов (Support Vector
Machines)
Граница классов
a , x b 0
a, x b 0 x C1 ,
a, x b 0 x C2
или
a, x b 0 x C1 ,
a, x b 0 x C2
Методы прогнозирования
Ростова Е.П.

25.

Метод опорных векторов (Support Vector
Machines)
Выбор уравнения границы
a , x b 0
Максимальный отступ между
классами
типичный
объект
Методы прогнозирования
Ростова Е.П.
типичный
объект

26.

Метод опорных векторов (Support Vector
Machines)
Типичные объекты
Опорные объекты
«Всплески»
1) симметричность «пограничной» полосы
2) наибольшее расстояние от границы для объектов обучающей выборки
Методы прогнозирования
Ростова Е.П.

27.

Метод опорных векторов (Support Vector
Machines)
|| a || min
a , x b 1
Методы прогнозирования
Ростова Е.П.

28.

Классификатор дерева решений (Decision Tree
Classifier)
Это непараметрический
контролируемый метод
обучения, используемый
для классификации и
регрессии.
Методы прогнозирования
Ростова Е.П.

29.

Классификатор дерева решений (Decision Tree
Classifier)
Методы прогнозирования
Ростова Е.П.

30.

Классификатор дерева решений (Decision Tree
Classifier)
Методы прогнозирования
Ростова Е.П.

31.

Классификатор дерева решений (Decision Tree
Classifier)
Методы прогнозирования
Ростова Е.П.

32.

Классификатор дерева решений (Decision Tree
Classifier
Методы прогнозирования
Ростова Е.П.

33.

Классификатор дерева решений (Decision Tree
Classifier
Дерево — это связный ациклический
граф. Связность означает наличие
маршрута между любой парой вершин,
ацикличность — отсутствие циклов.
Число рёбер в дереве на единицу меньше
числа вершин, а между любыми парами
вершин имеется один и только один путь
Методы прогнозирования
Ростова Е.П.

34.

Классификатор дерева решений (Decision Tree
Classifier
В каждом узле разбиение на два
подмножества:
• первое состоит из тех элементов, которые
удовлетворяют установленному правилу;
• второе состоит из тех элементов, которые
не удовлетворяют установленному
правилу.
Далее процедура повторяется
Методы прогнозирования
Ростова Е.П.

35.

Классификатор дерева решений (Decision Tree
Classifier
Конечный пункт - «лист»
Лист определяет решение для каждого
объекта, попавшего в него.
Дойти до листа можно единственным
маршрутом.
Методы прогнозирования
Ростова Е.П.

36.

Классификатор дерева решений (Decision Tree Classifier
площадь, кв.м.
74,3
72,3
63,1
61,8
41,3
65,3
57,4
50,1
59,9
51,4
54,3
60,0
48,4
75,0
58,2
79,6
75,7
67,2
район
Кировский
Кировский
Красноглинский
Красноглинский
Красноглинский
Куйбышевский
Куйбышевский
Ленинский
Ленинский
Ленинский
Октябрьский
Октябрьский
Октябрьский
Промышленный
Самарский
Самарский
Советский
Советский
этаж
год постройки
2
1992
4
1985
3
1992
3
1989
2
1993
2
1992
2
1983
3
1999
2
1994
2
1987
4
1985
2
1984
2
1984
3
1994
3
1993
3
1997
4
1988
Методы
Ростова Е.П.
4 прогнозирования 1986
цена, млн руб.
4,101
3,904
4,135
4,468
3,432
2,950
1,238
3,481
2,658
3,134
2,796
1,690
1,942
3,542
1,482
1,013
4,729
3,968

37.

Классификатор дерева решений (Decision Tree
Classifier
Методы прогнозирования
Ростова Е.П.