Министерство образования республики Беларусь
Учреждение образования
«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ»
Институт информационных технологий
Специальность «Программное обеспечение информационных технологий»
КОНТРОЛЬНАЯ РАБОТА
По курсу «Методы и алгоритмы решения принятия решений»
Вариант № 5
Студент-заочник 1 курса
Группы №181022
ФИО Дубровская Галина Николаевна
Адрес: г.Гомель, ул. Рабочая,4 к.301
Тел: +375447452881
Минск, 2012
Задание1. По обучающей выборке точек Zi(xi,yi), распределенных по классам Сj(С=1-1-й класс, С2=2-2-й класс), определите принадлежность точек А и В одному из заданных классов.
Используя для этого алгоритм К-ближайших представителей (К положите равным 3 и 5 ) и три типа метрик для определения минимального расстояния: евклидову, Чебышева, по Манхэттену. Полученное решение оформите в виде сводной таблицы для удобного сравнения результатов по каждому периметру. Сделайте чертеж. Обучающая выборка:
|
Объекты |
xi |
yi |
Cj |
|
Z1 |
6 |
1 |
1 |
|
Z2 |
6 |
2 |
1 |
|
Z3 |
6 |
3 |
1 |
|
Z4 |
7 |
3 |
1 |
|
Z5 |
8 |
4 |
1 |
|
Z6 |
10 |
4 |
2 |
|
Z7 |
10 |
3 |
2 |
|
Z8 |
11 |
3 |
2 |
|
Z9 |
11 |
2 |
2 |
|
Z10 |
12 |
1 |
2 |
Классифицируемые объекты А(9,4), В(9,1)
Решение:
Приведем формулы нахождения расстояния ρ между точками Z(x1,y1) и Zx2,y2:
-
Евклидов метод (x2-x1)2+(y2-y1)2
-
по Манхэттену x2-x1+y2-y1
-
метод Чебышева maxx2-x1,y2-y1
Классифицируемый объект А(9, 4)
Построим сводную таблицу. Расчеты в таблице получены по вышеуказанным формулам.
-
Zj
Xj
Yj
Сj
Эвкл
Манх
Чав
1
6
1
1
4,2
6
3
2
6
2
1
3,6
5
3
3
6
3
1
3,2
4
3
4
7
3
1
2,2
3
2
5
8
4
1
1,0
1
1
6
10
4
2
1,0
1
1
7
10
3
2
1,4
2
1
8
11
3
2
2,2
3
2
9
11
2
2
2,8
4
2
10
12
1
2
4,2
6
3
Используя алгоритм К-ближайших представителей, выберем точки, ближайшие к точке А.
При К=3 по всем метрикам ближайшими точками будут точки Z5, Z6, Z7. Две из них принадлежат 2 классу, значит и точка А будет принадлежать 2 классу.
При К=5 по всем метрикам ближайшими точками будут точки Z4,Z5, Z6, Z7,Z8. Три из них принадлежат 2 классу, значит и точка А будет принадлежать 2 классу.
Классифицируемый объект B(9, 1)
Построим сводную таблицу. Расчеты в таблице получены по вышеуказанным формулам.
|
Zj |
Xj |
Yj |
Сj |
Эвкл |
Манх |
Чав |
|
1 |
6 |
1 |
1 |
3,0 |
3 |
3 |
|
2 |
6 |
2 |
1 |
3,2 |
4 |
3 |
|
3 |
6 |
3 |
1 |
3,6 |
5 |
3 |
|
4 |
7 |
3 |
1 |
2,8 |
4 |
2 |
|
5 |
8 |
4 |
1 |
3,2 |
4 |
3 |
|
6 |
10 |
4 |
2 |
3,2 |
4 |
3 |
|
7 |
10 |
3 |
2 |
2,2 |
3 |
2 |
|
8 |
11 |
3 |
2 |
2,8 |
4 |
2 |
|
9 |
11 |
2 |
2 |
2,2 |
3 |
2 |
|
10 |
12 |
1 |
2 |
3,0 |
3 |
3 |
Используя алгоритм К-ближайших представителей, выберем точки, ближайшие к точке А.
Положим К=3, тогда по Эвклидовой метрике ближайшими точками будут точки Z4, Z7, Z9, две из них принадлежат 2 классу; по Манхеттену ближайшие точки Z1, Z7, Z9, две из которых также принадлежат 2 классу; по Чебышеву ближайшие точки Z4, Z7, Z8 две из которых также принадлежат 2 классу, значит и точка В будет принадлежать 2 классу.
Положим К=5, тогда по Эвклидовой метрике ближайшими точками будут точки Z1,Z4, Z7, Z8,Z9, три из них принадлежат 2 классу; по Манхеттену ближайшие точки Z1,Z2, Z7, Z9,Z10, три из которых также принадлежат 2 классу; по Чебышеву ближайшие точки Z2,Z4, Z7, Z8,Z9, три из которых также принадлежат 2 классу, значит и точка В будет принадлежать 2 классу.
Ответ: по алгоритму К-ближайших представителей при К=3 и К=5 по трем метрикам, точка В принадлежит 2 классу.
y
4 Z5 A Z6
3 Z3 Z4 Z7 Z8
2 Z2 Z9
1 Z1 B Z10
1 2 3 4 5
6 7 8 9 10 11 12 x
Задание 2. Используя алгоритм К-средних (k-means), разбейте массив точек на 4 класса (К=4) и определите их центры. Проиллюстрируйте свое решение.
Исходные данные:
-
Объекты
xi
yi
Z1
6
1
Z2
6
2
Z3
6
3
Z4
7
3
Z5
8
4
Z6
10
4
Z7
10
3
Z8
11
3
Z9
11
2
Z10
12
1
Z11
9
4
Z12
9
1
Решение:
Итерация 1:
В качестве начальных центров классов выберем точки c1(0)=Z1, c2(0)=Z2,c3(0)=Z3,c4(0)=Z4. Разобьем выборку по методу ближайшего соседа. По методу Эвклида найдем расстояние между центрами классов и остальными точками:
ρ(Z1,Z2)=(x2-x1)2+(y2-y1)2
Составим сводную таблицу
|
Объекты |
Xj |
Yj |
Расстояние до Z1 |
Расстояние до Z2 |
Расстояние до Z3 |
Расстояние до Z4 |
Класс |
|
● Z1 |
6 |
1 |
- |
- |
- |
- |
1 |
|
● Z2 |
6 |
2 |
- |
- |
- |
- |
2 |
|
● Z3 |
6 |
3 |
- |
- |
- |
- |
3 |
|
● Z4 |
7 |
3 |
- |
- |
- |
- |
4 |
|
Z5 |
8 |
4 |
5,83 |
5,39 |
5,10 |
4,12 |
4 |
|
Z6 |
10 |
4 |
5,00 |
4,47 |
4,12 |
3,16 |
4 |
|
Z7 |
10 |
3 |
4,47 |
4,12 |
4,00 |
3,00 |
4 |
|
Z8 |
11 |
3 |
5,39 |
5,10 |
5,00 |
4,00 |
4 |
|
Z9 |
11 |
2 |
5,10 |
5,00 |
5,10 |
4,12 |
4 |
|
Z10 |
12 |
1 |
6,00 |
6,08 |
6,32 |
5,39 |
4 |
|
Z11 |
9 |
4 |
4,24 |
3,61 |
3,16 |
2,24 |
4 |
|
Z12 |
9 |
1 |
3,00 |
3,16 |
3,61 |
2,83 |
4 |
Получим начальные классы Z1(1)=Z1, Z2(1)=Z2,Z3(1)=Z3,
Z4(1)=Z4,Z5,Z6,Z7,Z8,Z9,Z10,Z11,Z12.Вычислим новые центры – центры тяжести классов: с11=Z1=6 1 , с21=Z2=6 2 ,с31=Z3=6 3 ,
с41=
Сравниваем: с1(0)=с1(1), с2(0)=с2(1),с3(0)=с3(1), с4(0)≠с4(1).