Классификационные построения в экологии и систематике - Андреев В.Л.
Скачать (прямая ссылка):
Отметим, что имеются системы, ранжирование элементов которых не имеет практического смысла. Это прежде всего такие структуры, которые порождаются тр анзптивнымп отношениями порядка. Например, в иерархических системах степень значимо-. ети элемента и так очевидна: она определяется уровнем иерархии. Таким образом, определение ранга, или функциональной нагрузки элемента, целесообразно проводить только для нетранзитивных отношений и структур типа сетей.
5.4. Информационный критерий сложности структурной схемы
Структурные свойства графа можно характеризовать разнообразием связей каждой вершины. При «однообразной» структуре все вершины имеют одинаковое число инцидентных ребер, и, наоборот, наибольшее разнообразие наблюдается в случае, когда каждая вершина имеет своп особенности. Структурное (топологическое) разнообразие удобно оценивать с помощью количественных показателей, заимствованных из теории информации.
Пусть Г — конечный граф со множеством вершин Н и множеством ребер А. Подмножество всех вершин, имеющих одинаковое число инцидентных ребер, образует класс эквивалентности.
В более общем случае (у орграфа) эквивалентные вершины не различаются по двум показателям: числу исходящих и числу заходящих дуг. Эквивалентность порождает разбиение множества Н на классы Ht, прпчем
т (#! (J Нч U • • • U Н») = т {Щ = п, т (Я{) = щ,
(5.13)
где п — число вершин графа; s — число классов.
Отдельный класс можно рассматривать как событие, а совокупность классов — как полную группу событий. Тогда пх частоты определяются отношенпем njn. Энтропия такой схемы событий дает меру разнообразия данного разбиения множества Н [40]:
/(Г) = -
п
(5.14)
Рассмотрим граф отношений «50%-ного сходства» на рис. 3.4, матрица смежностей которого имеет вид
А =
1 1 1 3
1 1 1 3
1 1 1 1 1 . 5
1 1 1 . 3
1 1 1 . . 1 Q = 4
у
1 1 . 0
1 1 1 3
1 . 1 1 3
(5.15)
В матрице Q указаны суммы элементов А по строкам: г-й элемент ?2 соответствует числу ребер, инцидентных г-й вершине графа (в данном случае — степени г-й вершины). Отношение сходства симметрично, поэтому сумма элементов г-й строки равна сумме элементов г-ro столбца.
Одинаковые элементы Q указывают эквивалентные вершины. Разобьем множество всех вершин на классы
Hi = {6}, Н2 = {1, 2,4,8}, Н3={5}, Н4 = {3}. (5.16)
В класс Н1 входят все вершины, степень которых равна 2, число таких вершин т (Ях) = 1 (вершина 6). В класс Н2 входят все вершины, имеющие степень 3, число таких вершин т (Н2) = 4 и т. д. Общее число вершин тп (Н) = 8, следовательно,
1(Г)=-
m (Ht) , m (Hj)
= - 3
m (H) 1
-lg.
m (H)
+
lg-
-rig-
m(H4) m (H)
0,49.
lg
m(H4) m (H)
Рассмотрим теперь схему вычислений для орграфов на примере рис. 3.5. Матрица смежностей орграфа
1
1..... 2 1
1..... 2 1
1 . . . . . 1 5
11.... 2 2
1 1 1 . . 1 Q = 3 1
...1.1 2 1
....11 2 1
.....1 1 4
(5.17)
В матрице Q числа первого столбца совпадают с полустепенью исхода (суммы элементов А по строкам), второго — с полустепенью захода (суммы элементов А по столбцам) каждой вершины.
Соответственно одинаковым строкам Q разобьем множество вершин Н на классы
Hi = {1, 2, 6, 7}, Н2= {3}, Н3-{4}, Н4 = {5}, Н5={8}.
(5.18)
Поступая, как и ранее, получим
/ (Г) = - [-L Ig 4 + 4 (4- Ig 4-) ] = 0,60,
откуда впдпо, что количество структурной информации у второго графа существенно больше, чем у первого.
Минимального разнообразия степеней вершин следует ожидать, когда все вершины эквивалентны и образуют единственный класс, максимального — когда число классов равно числу вершин. В первом случае
1
7(Г)т1„-----
во втором
I (Г)тах ~ — n (— lg —) = Ign.
Последняя величина дает возможность сравнивать графы с разным числом вершин, используя относительный показатель, изменяющийся в пределах от нуля до единицы:
2Х!* Пг
ЦТ)
1 -
nlgn
(5.19)
5.5. Таксономля структур
Назовем таксономией (от- греческого «таксис» — расположение по порядку, «номос» — закон) любое транзитивное и антирефлек-еивное отношение. Напомним, что антирефлексивное отношение —
это такое отношение, когда из факта выполнения хАу следует, что уфх для любой пары х, у М, A cz М. Приведенные выше примеры отношений иерархии и доминирования отвечают требованиям транзитивности и антирефлексивности, следовательно, являются частным случаем таксономии.
Рассмотрим более сложные примеры практического использования отношений подобного рода.
При изучении отношений иерархии можно было заметить, что матрица сходства содержит всю информацию о дендрограмме, однако восстановить по последней матрицу сходства в общем случае не удается. Другими словами, при построении дендрограммы происходит потеря информации. Поэтому в тех случаях, когда возникает необходимость сравнения нескольких .матриц мер сходства, сопоставление дендрограмм оказывается неэффективным.
