Глава 8. Многомерные методы анализа: алгоритм "Кора"

Дальше

Назад

Начало

Конец

Список

8.6. Задача об ассоциативности видов: алгоритм формирования логических высказываний
Формулировка задачи

Пусть пространство признаков Х размерностью m > 1, соответствующее некоторому списку видов гидробионтов, предварительно преобразовано к бинарному виду, т.е. x_i = 1, если значение обилия i-го вида в пробе превышает некоторый заданный порог, и x_i = 0 в противном случае, i = 1,2,…,m. Пусть также обучающая последовательность, в которую включаются специально отобранные измерения х из Х, распадается на два подмножества векторов – векторы первого класса Х и векторы второго класса .

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

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

Рекомендуемая литература: [Бонгард, 1967; Вайнцвайг, 1973; Голендер, Розенблит, 1978].

Математический лист

Рассмотрим логический метод распознавания, известный под названием алгоритм “Кора”, который широко используется в геологоразведочных работах и скрининге лекарственных препаратов.

Задается множество характеристических логических функций Y (x,t ), которые называются логическими высказываниями и представляют собой некоторую комбинацию исходных переменных x_ij, связанных между собой операцией коньюнкции, т.е. знаком логического произведения “И” (AND, Ù ): x_i1 Ù x_j2 Ù … Ù x_kl, где i, j, k Î M – индексы исходного словаря признаков, l = 1¸ 5 – количество элементов в логическом высказывании или его ранг. Каждый из сомножителей может трактоваться при этом на языке булевой алгебры как “Истина” (TRUE при x_ij = 1) или ее отрицание, т.е. “Ложь” (NOT TRUE или FALSE при x_ij = 0).

Алгоритм “Кора” многократно просматривает обучающую выборку, предварительно разделенную на два класса (0 и 1), и, с использованием операций алгебры логики, выделяет из множества высказываний так называемые непротиворечивые логические высказывания Y (x,t ^*), покрывающие все множество примеров. Непротиворечивым высказыванием для каждого класса считается конъюнкция, которая встречается некоторое количество раз только в одном классе и ни разу не встречается в другом. При генерации логических высказываний алгоритм руководствуется рядом следующих правил:

1. Конъюнкции сортируются по продуктивности или мощности, оцениваемой числом наблюдений, для которых это высказывание справедливо. Чем больше продуктивность конъюнкции, тем выше прогностическая ценность выделенной комбинации признаков. В случае детерминистской задачи распознавания в конечное решающее правило включаются конъюнкции, продуктивность которых превышает некоторый порог D .

2. Из генерируемого списка исключаются подчиненные (или дочерние) конъюнкции, полностью содержащие более короткие претенденты. После такой операции поглощения ликвидируется избыточность решающего правила, в котором остаются конъюнкции минимального ранга, содержащие выделенные закономерности в концентрированной форме.

3. Исключаются высказывания, которые по определенным критериям считаются "предрассудками". К ним относятся конъюнкции, не связанные с объективным правилом классификации, но в силу ограниченности выборки получившие хорошие оценки на обучении. Для выделения признаков, склонных к предрассудкам, выполняют bootstrep-процедуру, в которой обучающая выборка многократно случайным образом разбивается на классы. Разбитая таким образом выборка является тестом, позволяющим присвоить каждому исходному признаку штрафные баллы за склонность к предрассудкам. Конъюнкции, набравшие свернормативное количество штрафных очков, из решающего правила исключаются.

Описанием каждого класса является логическая сумма (дизъюнкция) некоторого количества непротиворечивых и продуктивных конъюнкций, прошедших описанные выше этапы отбора. Комбинация этих логических высказываний представляет собой своеобразную мозаично-фраг-ментарную разделяющую поверхность специального типа (в отличии от линейной поверхности "обобщенного портрета"). Существует возможность использовать сгенерированные конъюнкции для экзамена тестируемых примеров по принципу голосования (конъюнкции как бы используются в качестве "электората"). Однако, мы полагаем, что специальная ценность использования алгоритма “Кора” состоит в извлечении из моря исходных данных нетрадиционных и непротиворечивых гипотез об экологии видов – феноменах их взаимной обусловленности или конкурентности.

Алгоритм “Кора”, как и другие логические методы распознавания образов, является достаточно трудоемким, поскольку при отборе конъюнкций необходим полный или частично направленный перебор. Поэтому при применении логических методов предъявляются высокие требования к эффективной организации вычислительного процесса, и эти методы хорошо работают при сравнительно небольших размерностях пространства признаков и емкости задаваемого класса характеристических функций.

Практический пример

Используем алгоритм “Кора” для логико-структурного анализа той же обучающей выборки, что и в алгоритме 2 раздела 8.5. Напомним, что алфавит признаков соответствовал 166 видам хирономид, класс Х включал 70 проб на станциях с относительно удовлетворительной экологической ситуацией (НОРМА), а класс – 90 измерений в зоне с чрезвычайной экологической ситуацией (ПАТОЛОГИЯ).

Небольшая часть полученных высказываний приведена в табл. 8.21. Например, вид Microtendipes pedellus встретился в 9 наблюдениях класса НОРМА и ни в одном наблюдении класса ПАТОЛОГИЯ. Сочетание видов Cladotanytarsus mancus и Cricotopus bicinctus при непременном отсутствии Cryptochironomus gr. defectus достигли того же 8 раз. Логические высказывания класса ПАТОЛОГИЯ несколько беднее и часто оказываются, хотя бы фрагментарно, зеркальным отражением коньюнкций класса НОРМА.

Таблица 8.21

Фрагменты логических решающих правил, полученных по алгоритму "Кора" и характеризующих категории качества вод по видовому составу хирономид

Дальше Назад Начало Конец Список