Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
101 1 1
(2.1)
Эта матрица применяется на следующем этапе распознавания. Для примера 2.2
эти матрицы имеют вид. ф = 60 %):
1) сочетание Хп <8".?^
11 1 У 0 1
1 0 1 10 0 3 3
1 0 1 00 1 1 2
0 0 1 11 0 1 1
1 0 1 01 4 0 4
1 1 5 5 10
0 1 0
0 0
0 1 0
0 0 1 0 оо II у-S у-S ><->? *-Р о о бит;
41
2) сочетание Х{ 1 (r)Х2
11 2 Y • 0 1
1 1 1 11 0 3 3
1 1 1 01 1 1 2
0 1 1 10 0 1 1
1 0 1 00 4 0 4
1 1 1 5 5 10
0 0 0
0 0 0
0 0 0
0 0 0
0 .1 0 /0(У:(ХП(r)*2)) = 8 бит;
3) сочетание Х^ <8> Х2 <8> Х^
1 2 7 Y 0 1
0 1 1 1 011 0 2 2
0 1 1 010 1 1 2
0 1 0 1 001 0 1 1
0 0 1 1 111 0 1 1
1 1 1 1 100 3 0 3
1 0 0 0 101 1 0 1
1 0 1 0 5 5 10
1 0 0 0
1 0 0 0
0 1 0 0 = 8 бит;
4) сочетание Х{{ (r) Х^
11 7 Y 0 1
1 1 1 11 0 4 4
1 1 1 00 4 1 5
0 0 1 01 1 0 1
1 1 1 5 5 10
1 1 1
0 0 0
0 1 0
0 0 0 -
0 0 0
0 0 о /0(У:(Л-П(r)*7)) = 6.4 бит.
2.5. Переход в новое пространство признаков.
Метрика Хэмминга
Будем считать новым признаком сложный признак, отобранный на предыдущем
этапе. Переход в новое признаковое пространство осуществляется следующим
образом.
Введем третий параметр настройки у, принимающий целочисленные значения 1,
2, ... Действие этого параметра
42
поясним на примере. Пусть у некоторого объекта в старом пространстве
признаки' Х2, X^ Х& принимают значения 0,1,1
соответственно. Находим в соответствующей переходной матрице (2.1)
сочетание (011) и соответствующую строку (С0, Су С2) (в
данном случае CQ = 0, С{ = 2, С2 = 0). Находим максимальное
значение, скажем, Су Если окажется, например, что Cl - CQ>
> у, Cj - С2 > у , то соответствующий признак в новом
пространстве принимает значение, равное 1. Если же в строке (CQ, Су С2)
нет "лидера", то записываем пробел (отказ от
распознавания по данному признаку для данного объекта). В нашем примере
при у = 2 новый признак принимает значение
1, а при у = 3-пробел. Таким образом, параметр у определяет "степень
доверия" к данному сложному признаку.
Размер нового пространства признаков совпадает с числом отобранных
сложных признаков. В новом пространстве все объекты (образы)
кластеризуются вокруг стандартных векторов
(0, 0....0), (1,1,..., 1), (2, 2,..., 2) и т. д.
Метрика Хэмминга определяется для двух слов как количество координат, в
которых буквы этих слов отличаются друг от друга. Эта величина
удовлетворяет всем аксиомам метрики. Если в пространстве признаков
основной является информационная метрика р(Х., X.), то в новом
пространстве образы
(объекты) кластеризуются относительно метрики Хэмминга d(k, т): два
объекта кит, лежащие в одном и том же классе, оказываются близкими в
смысле d(k, т) в новом пространстве. При этом степень кластеризации
регулируется параметром /3, а параметр у определяет реальный размер
нового пространства признаков (с учетом отказов).
2.6. Распознавание
Перейдем к последнему этапу распознавания. Сущность предыдущих этапов
заключается в том, что выполняется некоторое нелинейное преобразование
исходного пространства, так что в новом пространстве сходные объекты
становятся близкими по метрике Хэмминга.
Переведем контрольный объект в новое пространство и вычисляем расстояния
d(i, 0), d(i, 1), ... от этого объекта до стандартных слов 0 = (0, 0,
...), 1 = (1, 1, ...), ... Если d(i, f)
минимально, то считаем, что г'-й объект принадлежит у-му классу. Для
примера 2.2 имеем при X = 1
Номер объекта 11 (r) 1 11 (r) 2 1 (r) 2(r) 7 И (r) 7 У
1 1 1 1 1 1
7 0 0 0 0 0
11 - 0 - 0 0
12 1 1 - - 1
Настройку программы осуществляют, меняя у, затем уЗ и, наконец, а.
Конкретные значения этих параметров зависят от общего размера обучающей
выборки, числа исходных признаков и их информативности. Всегда следует
стремиться к возможно большим значениям у, но при этом появляется много
отказов и, как следствие, уменьшается число признаков в новом
пространстве. Это уменьшение можно компенсировать уменьшением параметра
/3, но тогда ухудшается кластеризация по Хэммингу (образы
"расплываются"). Параметр а, отсекающий "шум", не следует выбирать
слишком малым, так как при этом происходит искажение результатов
распознавания.
Если, тем не менее, не удается настроить программу, то следует изменить
обучающую выборку: некоторые объекты,
использованные ранее для контроля, применить для обучения и наоборот.
3. РЕЛЯЦИОННЫЕ БАЗЫ ДАННЫХ
3.1. Отношения
В гл. 1 рассматривались отдельные слова и были введены некоторые
характеристики слов и пар слов. В гл. 2 основным объектом была
информационная матрица, строки которой назывались образами, а столбцы-
признаками (атрибутами). В информационной матрице присутствует обычно
некоторая избыточность, позволявшая предсказывать значение некоторого
признака, если известны значения других признаков.
В этой главе мы будем рассматривать совокупность информационных матриц
(будем называть их отношениями). Такой способ описания базы данных был
предложен Е. Коддом.
Пример 3.1
Табельный номер Ф.И.О. Должность Помер комнаты Телефон Дети
