ТаблицаТаблица данных, соответствующая ветви x6 = 1
| Признаки | |||||||||||||||
Объекты | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15 | x16 |
1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
3 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
4 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
5 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
6 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
8 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
9 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
10 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
11 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
15 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
Класс 1/Класс 2 | 1/1 | 3/3 | 3/3 | 3/2 | 3/1 | 6/4 | 3/2 | 2/1 | 4/2 | 4/4 | 5/1 | 2/2 | 4/3 | 3/4 | 4/1 | 4/2 |
Ветвь x6 = 1 устроена более сложно. На этой ветви наибольшей дискриминирующей силой обладает признак x11 (табл. 9. 4). Он имеет значение 0 у объекта 5 из первого класса и объектов 9, 11, 15 из второго класса; и значение 1 у объектов 1, 3, 4, 6 из первого класса и объекта 10 из второго класса. Таким образом, требуется дополнительное ветвление, которое осуществляется с помощью признаков x15, x16 и x2. Полное дерево приведено на рис. 9. 7.
Рис.Дерево логического вывода
Как следует из рисунка, дерево логического вывода, выросшее из признака x6 (носогубная складка), имеет 6 исходов. Только два из этих исходов включают по четыре объекта (полнота 4/8). Один исход группирует три объекта своего класса (полнота 3/8), один исход —два объекта (полнота 2/8) и три исхода включают по одному объекту (полнота 1/8). Естественно, нельзя считать логической закономерностью путь по дереву, для которого исход захватывает столь малое относительное число объектов одного класса (обладает малой полнотой). Как видим, решение, даваемое алгоритмом CLS далеко от требуемого.
Если попытаться вырастить дерево решений из любого другого признака, например, x2, x3, x10, x11, x14 или x15, то результат будет также далек от оптимального.
Алгоритм CLS способен приводить к качественным решениям задачи поиска логических закономерностей только в случае независимых признаков. В противном случае он нередко направляет ход логического вывода по ложному пути и создает лишь иллюзию правильного рассуждения.
Случайный поиск с адаптацией
Алгоритм случайного поиска с адаптацией (СПА) был предложен Г. С. Лбовым в 1965 г. для работы в условиях зависимых признаков /Лбов Г. С., 1965/. Он заключается в следующем.
Имеется множество возможных событий 
. Из этого множества требуется отобрать цепочки конъюнкций 
заданной длины l, максимизирующие некоторый критерий J.
Прежде всего, проводится серия опытов по случайному определению состава цепочек конъюнкций. Затем для этих цепочек вычисляются значения критерия J. Цепочка с максимальным значением критерия поощряется увеличением вероятности выбора вошедших в нее событий в следующих опытах. Цепочка с наименьшей величиной критерия наказывается соответствующим образом. Вся процедура повторяется до тех пор, пока события отчетливо не поляризуются по вероятности их выбора для испытаний.
Алгоритм СПА избегает полного перебора событий, требующего просмотра 
их комбинаций в цепочке. Его трудоемкость, однако, зависит от задаваемых условий: количества испытаний, мер поощрения и наказания событий, которые существенно влияют на скорость сходимости алгоритма. Экспериментально на одних и тех же данных показано, что алгоритм СПА давал оптимальное либо близкое к оптимальному решение за число шагов, сравнимое с величиной /Загоруйко Н. Г., 1972/
.
Пример с обнаружением логических закономерностей в группах изображений лиц людей (рис. 8. 1) может быть решен с помощью алгоритма СПА, если задать l = 4. Вместе с тем, этот пример является достаточно простым — число объектов и признаков в таблице данных мало. В более сложных ситуациях алгоритм СПА остается все‑таки весьма трудоемким. Кроме того, необходимость задавать длину цепочек конъюнкций l, что также ограничивает его применение.
Литература
М. Проблема узнавания. — М.: Наука, 1967.
Гик Дж., ван. Прикладная общая теория систем. М.: Мир, 1981.
Загоруйко Н. Г. Методы распознавания и их применение. — М.: Сов. радио, 1972.
Лбов Г. С. Выбор эффективной системы зависимых признаков/Тр. Сиб. отд. АН СССР: Вычислительные системы. — Новосибирск, 1965, вып. 19.
Чесноков С. В. Детерминационный анализ. — Материалы Internet, 1997.
Экспертные системы. Принципы работы и примеры: Пер. с англ./Под ред. Р. Форсайта. — М.: Радио и связь, 1987.
Boulding K. E. General Systems Theory — The Skeleton of Science//Management Science, 2, 1956.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 |
