Интервальные формальные понятия и их использование в распознавании образов

1.

Тема:
ИНТЕРВАЛЬНЫЕ ФОРМАЛЬНЫЕ
ПОНЯТИЯ И ИХ ИСПОЛЬЗОВАНИЕ В
РАСПОЗНАВАНИИ ОБРАЗОВ

2. Цель:

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

3. Задачи:

1.
2.
3.
введение понятия слабых «положительных» и
слабых «отрицательных» гипотез;
рассмотрение и доказательство свойств
указанных гипотез;
формулировка алгоритма классификации в
терминах слабых гипотез.

4.

Формальный контекст
K U , G, P
U
-
ПП
G U
-
выборка
P p1 , p 2 , , p n : U { 0, 1}

5.

Задача распознавания
G G G ; G G ∅ .
K U , G G , P
Требуется:
Комбинируя предикаты множества P , построить
такие «обобщения» предикатных описаний «+» и
«-» примеров, которые позволяли бы
производить классификацию тех точек из
признакового пространства U , классификация
которых неизвестна.

6.

«Штрих» операторы
A G.
A { p P : p (a ) 1, a A}
B P.
B { g G : p ( b ) 1, b B }
B
B G
'
B
B P
'
" : 2P→2P − оператор замыкания

7.

Контекcтная равносильность
A, B P
K
A B A B
K
−
отношение эквивалентности
A K
( A K , )
−
K
B P| B A
упорядоченное множество
1.
!max[ A]K
2.
| min[ A]K | 1
A max[ A ] K

8.

Формальные понятия
Пусть
A G, B P
( A, B ) − ФП A B, B A
A − объём ФП
B − содержание (описание) ФП
B (K ) − формальные понятия контекста K

9.

Положительные и отрицательные гипотезы
формальных контекстов
Пусть G G G ; G G ∅
.
K (U , G , P) B( K )
K (U , G , P) B( K )
Пусть
( A, B) B( K ) B − «+» гипотеза
df.
G B ∅ B − ф-ая «+» гипотеза
df.
G B ∅ B − неф-ая «+» гипотеза
p.s.
( A, B) B( K ) − аналогично

10.

Алгоритм классификации
Пусть
u U
1.
| H (u ) | 0
и
| H (u) | 0 u «+»
2.
| H (u ) | 0
и
| H (u ) | 0 u «−»
3.
| H (u ) | 0
и
| H (u ) | 0 u − отказ (н.и.)
4.
| H (u ) | 0
и
| H (u ) | 0 u − отказ (п.)

11.

Обобщённые понятия и слабые гипотезы
( A,[ B] K ) − ОФП A B
B [ B]K
− СГ
B − гипотеза и слабая гипотеза
С1. Если
НСГ
С2. Если Г- ф-ая
Г - неф-ая
Каждая СГ - ф-ая
и
B A

12.

Алгоритм классификации слабыми
гипотезами
1.
| H (u ) | | H (u ) | u − «+»
2.
| H (u ) | | H (u ) | u − «−»
3.
| H (u ) | | H (u ) | u − отказ :
| H (u ) | 0
− по недостатку информации
| H (u ) | 0
− по противоречию информации

13.

Пример
Рис. 1: Признаковое пространство и выборка точек
из 2-х классов;

14.

Пример
Рис. 2: Сетка ; каждая «клетка» содержит точки не
более, чем одного класса;

15.

Пример
Рис. 3: «+» , «-» - гипотезы, порождаемые текущей
сеткой;

16.

Пример
Рис. 4: Дополнительные точки, классификация
которых неизвестна;

17.

Пример
Рис. 5: Классификация точек с помощью гипотез;
отказ в классификации точек с помощью «слабых»
гипотез;

18.

Пример
Рис. 6: Измельчение сетки и «слабые» гипотезы;

19.

Пример
Рис. 7: Классификация «слабыми» гипотезами;

20.

Пример
Рис. 8: Измельчение сетки; «слабые» гипотезы;

21.

Пример
Рис. 9: Классификация «слабыми» гипотезами;

22.

Пример
Рис. 10

23.

Основные результаты выпускной квалификационной
работы следующие:
1. Введены понятия слабых «положительных» и
«отрицательных» гипотез, порождаемых
формальным контекстом;
2. Приведено доказательство некоторых свойств
указанных гипотез;
3. Предложена формулировка одного из возможных
алгоритмов классификации в терминах слабых
гипотез