Классификационные построения в экологии и систематике - Андреев В.Л.
Скачать (прямая ссылка):
В (6.22) каждая Ти имеет одинаковые значепия ®тах и число изоморфных таблиц, однако среднее на столбец число значений «*» для Тг и Т2 равно 0,5, а для Т3 и Г4 — 0,67. Следовательно, выбираем первую пару: Тгя Т2. Эти таблицы различаются только названием последней строки (S4 и S5). Поскольку значения определяются на реальных объектах труднее и менее надежно, чем значения <S4, то окончательно выбираем Тг.
Определитель есть своего рода хранилище информации, отобранной в соответствии с заданной целью. Ключ — это способ (алгоритм) отыскания некоторой, нужной в данный момент, ее части.
Компактные определители по сравнению с допустимыми предназначены для облегчения поиска нужной информации за счет устранения избыточности. К сожалению, на практике это устранение неизбежно приводит к потере надежности распознавания. Поэтому оптимальный определитель — это такой, который обеспечивает максимальную надежность поиска при минимальном объеме.
Составление ключа также является задачей с противоречивыми требованиями: обеспечить краткость и простоту использования, с одной стороны, и точность — с другой. В общем случае эта задача сводится к поиску экстремума некоторого достаточно сложного функционала.
Не останавливаясь подробно на методологии решения подобных проблем, приведем алгоритм построения ключа, использующего минимальное число шагов (вопросов) и обеспечивающего максимальную точность определения.
Из общих положений теории информации [15] следует, что если имеется q объектов, заданных бинарными описаниями, то минимальное число признаков, обеспечивающиее их безошибочное распознавание, находится по уравнению
Ршт = • (6.23)-
Например, для различения восьми объектов (q = 8) требуется не менее трех бинарных признаков, для 2000 объектов — не менее 15 и т. д. Процедура отбора переменных в этом случае сводится к тому, что на первом шаге выбирается признак, делящий совокупность объектов пополам (половина объектов имеет значение этого признака, равное единице, а другая половина — равное нулю), вторым отбирается такой, который делит одновременно обе полученные подсовокупности пополам и т. д. Однако на практике ред-
ко удается точно выполнить эти правила, поэтому решение ищется лишь по возможности близким к оптимальному.
Для примера проанализируем Тг из (6.22). При q = 4 согласно (6.23) Pmin=2. Тем не менее имеющаяся информация не позволяет найти решение при таком чпсле переменных. Признак S2 делит все четыре подсемейства на две равных совокупности: Ru R2 (жало имеется) и R-s, R4 (жало отсутствует). Признак St делит подсемейства и Д2, а признак <S4 — R3 и Я4. Таким образом, в данном примере минимальное число разделяющих признаков равно трем. Оптимальный ключ содержит всего два вопроса: 1) имеется ли в заданном наборе S2 или S-2; 2) если S2, то выясняется значение SL, а если S2, то значение Si.
Для повышения надежности определения можно использовать следующий прием. 7\ и Т.г имеют эквивалентные структуры из-за- того, что в допустимой таблице (6.21) четвертая и пятая строки одинаковы. Это дает возможность объединить Тх и Т.2 в одном определителе
* Si ^.5
Ri 1 1 *
2?o -1 0 *
Яг 0 0 1
Ri .0 0 0
где индекс Т означает операцию транспонирования.
Признаки в таблице (6.24) перечислены в том порядке (слева направо), которого требует ключ: на первом месте стоит S2¦ Запись Si.b означает, что в данном столбце помещаются значения
Si и S3, которые одинаково изменяются при переходе от объекта к объекту. Это означает также, что для распознавания объекта можно использовать либо S4, либо S5, либо Si и S5 одновременно. Прямоугольником обведены значения, знание которых при распознавании желательно, но необязательно.
Допустим, требуется распознать объект
•S' 1S3 Si S5 д = (? 0 0 ? 1).
Вопросительным знаком отмечены неизвестные значения соответствующих признаков: в распознаваемом- объекте неизвестны значения St и S4 (х1. = ?, Xi. = ?). Согласно (6.24) первым анализируем признак S2: поскольку х.2. = 0, то искомый образ находится в нижней половине определителя (R3 или Д4). В этой половине важно значение S4 пли S-0. Поскольку значение Si неизвестно, используем хъ. = 1 и устанавливаем, что объект R относится к Д3 (подсемейство Formicinae).
Данный пример иллюстрирует только идею составления ключей, но не трудности, которые встречаются на практике. Поэтому могут оказаться полезными некоторые упрощенные процедуры минимизации описаний. Существо одной из них сводится к следующему.
На первом шаге определяется признак, дающий максимальную энтропию на множестве описаний:
(6.25)
где п — объем совокупности; пх — число описаний, имеющих значение 1 у i-ro признака; п0 = п — пх.
В соответствии с этим исходная совокупность разбивается на две, имеющие п1 И па описаний. Затем точно таким же образом каждая подсовокупность разбивается на две и так до тех пор, пока в каждой группе останутся лишь неразличимые объекты.
