Научная литература
booksshare.net -> Добавить материал -> Биология -> Андреев В.Л. -> "Классификационные построения в экологии и систематике" -> 34

Классификационные построения в экологии и систематике - Андреев В.Л.

Андреев В.Л. Классификационные построения в экологии и систематике — М.: Наука, 1980. — 142 c.
Скачать (прямая ссылка): klassifikacionniepostroeniyavekologii1980.pdf
Предыдущая << 1 .. 28 29 30 31 32 33 < 34 > 35 36 37 38 39 40 .. 58 >> Следующая

1 © 1 = 0, 1 © 0 = 0 © 1 = 1, о © о = о,
*©i = i©* = oe* = *©o~*©*=o. (6‘9)
Признак Si называется различающим на множестве Я, если найдутся такие к и / (к =j= j), что xik © xi} — 1. Описания R} и Rk называются различимыми, если имеют хотя бы один различающий признак. Таблица Т называется допустимой, если все столбцы в ней попарно различимы.
Для многих практических целей интересно выяснпть: какие из переменных St можно удалить, не нарушив различимости описаний Rj?
Набор признаков
ти — {$тП1* • • • > *^mj} т ТПЪ . . ., Tflt I, И = 1, . . ., Г (6.10)
называется тестом таблицы Т, если после удаления всех признаков, не вошедших в Ти, все Rj ?Е Я остаются различимыми. Тест называется тупиковым, если при удалении хотя бы одного SгЕЕ 6= Ти условия различимости Rj нарушаются.
Алгоритмы выявления всех тупиковых тестов таблицы Т приводятся в статье [21]. Существо одного из этих алгоритмов можно пояснить с использованием операции А © В, позволяющей установить различающие признаки на каждой паре описаний Rj и Rk (к ф j).
Произведем попарное сравнение всех объектов из Г и составим вспомогательную таблицу со столбцами
Rjk — Rj © Rk — {xij © • • • Xpj © Zpk}- (6-11)
В каждом Rjk выделим номера х1;. . ., ие различающих признаков и сопоставим RJk дизъюнкцию
v ik — • • •> Xi, ...,xeS/, (6.12)
а разным Rjk — конъюнкцию
П П vik. (6.13)
3=1 k=j+1
Рассматривая SXi,. . ., Sy.e как логические переменные, приведем (6.12) к виду 2П и упростим выражения типа А - А = А-. А -г А = А, А + А'В = А. Тогда (6.12) будет иметь вид
(6.14)
Каждому слагаемому в (6.14) соответствует тупиковый тест Т. Кроме того, (6.14) указывает все тупиковые тесты таблицы Т. Пример. На множестве описаний Я, заданном в виде таблицы
Г = '
Ri R, Дз Я
Si 0 0 0 0
•S’s 1 0 1 0
?3 0 1 1 1
1 1 1 0
•у* 0 1 и 1
(6.15)
определить все тупиковые тесты.
Прежде чем решать эту задачу, убеждаемся в том, что таблица (6.15) допустима, т. е. не содержит одинаковых столбцов. Если Т не является допустимой, то один из неразличимых столбцов должен быть удален.
Проведем попарное сопоставление Rj и Rk (к Ф j), отмечая различающие признаки «1», а прочие «О»:
¦3*
Riz R и Ru Rz 3 i?,4 R
Si 0 0 0 0 0 0
s2 1 0 1 1 0 1
ss 1 1 1 0 0 0
Si 0 0 1 0 1 1
Sb 1 0 1 1 0 1
;k) I3 1 4 2 1 3
(6.16)
В нижней строке поместим значения тп (Rjk) — число единичек в каждом столбце.
В содержательном смысле значения столбцов Rjk = 1 означают: описания Rx и R2 различимы по признакам S2, S3 и Sy следовательно, один из них — либо S2, либо 53, либо S5 — может быть включен в тест; описания Rx и R3 различимы по признаку S3 и т. д. Для сопоставления теста необходимо учитывать все столбцы (6.16) одновременно, поэтому
Rn Ягз Ru
(S2 -(- S3 -j- S5)-S3'(S2 -j- 1S3+ ¦
R2 3 ?5) (^2 4
Rn
<S5)-S4-(S;
Ik,
Si -f- Sb). (6.17)
Раскрывая скобки, получим все тесты таблицы Т, а произведя упрощения: А-А — А, А + А = А, А + А-В = А, найдем все ее тупиковые тесты
S*'S3-Si -f- S3'S4-S5. (6.18)
число которых х — 2. Из них первый содержит признаки S2, S3, S4, второй — 53545'5. В самом деле, если учитывать каждый набор в отдельности, получим таблицы
Rl я. Дз Я4 Л1 R-Z «3 R
1 0 1 0 ¦*» 0 1 1 1
s 3 0 1 1 1 1 1 1 0
1 1 1 0 ¦у* 0 1 0 1
(6.19)
в каждой из которых все столбцы различимы, а удаление хотя бы одной строки нарушает условия различимости. Следовательно, 7\ и Т2 — тупиковые тесты.
Заметим, что признак Sx не является различающим и не вошел ни в один тупиковый тест. Признак S2 входит в Тг, S3 — в Тг п Т2 и т. д. Обозначим т; число тупиковых тестов, в которые входит ?-й признак, тогда
(й; = тц'т (6.20)
называется информационным весом i-го признака. Для таблицы
(6.15) <Dj =0, ю2 = 1/2, (о3 = 1, а>4 = 1, со8 = 1/о. Наибольший вес имеют признаки S3 и 54.
В данном примере громоздкими действиями оказываются раскрытие скобок и упрощение (6.17). Многих трудностей можно избежать, если провести предварительное упрощение таблицы
(6.16). В нижней строке m (Rjk) выделим минимальное значение. Таковым оказывается «1», которая встречается два раза: тп (R13) = = 1 и m (R2i) = 1. Рассмотрим столбцы, соответствующие минимальным значениям. В R13 значение «1» соответствует признаку S3: вычеркиваем из (6.16) все столбцы, у которых S3 имеет значение «1», т. е. R12 и В14. Во втором из отобранных столбцов — R2i — значение «1» соответствует St, поэтому вычеркиваем из (6.16) все столбцы, которые имеют «1» в четвертой строке (столбец R3i). Остаются: Rl3, R22, R2i, не имеющие «1» в одинаковых строках. Дальнейшее упрощение невозможно, поэтому анализируем содержание оставшихся столбцов:
Предыдущая << 1 .. 28 29 30 31 32 33 < 34 > 35 36 37 38 39 40 .. 58 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed