5.8.1. Неориентированные и ориентированные графы

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

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

Дендрит – один из типов неориентированного графа. Он может быть двух типов: минимальное древо (матрица включает оценки различий между объектами) или максимальное древо (использу­ются меры сходства).

Дендрит – это ломаная линия, которая может ветвиться, но не содержит циклов. Построение дендрита заключается в нахож­дении для каждого объекта наиболее сходного с ним объекта и со­единении их линией. В результате получается ряд отрезков, в том числе и разветвленных.

Построить дендрит (рис. 5.8.1) можно с помощью матрицы сход­ства выборочных совокупностей, например (A–Е), вычисленной на основе индекса сходства Жаккара (табл. 5.8.1). Для этого после­довательно соединяем две наиболее сходные выборки Г и Д (0,90) отрезком. Следующая по силе величина сходства 0,85 обнаружена между выборками Г и В. Поэтому выборку В можно присое­динить отрезком к уже построенной ветке Д – Г и т. д.

Таблица 5.8.1

Матрица сходства выборочных совокупностей

	А	Б	В	Г	Д	Е
А	–	0,80	0,20	0,40	0,50	0,60
Б	0,80	–	0,30	0,55	0,45	0,65
В	0,20	0,30	–	0,85	0,15	0,10
Г	0,40	0,55	0,85	–	0,90	0,75
Д	0,50	0,45	0,15	0,90	–	0,25
Е	0,60	0,65	0,10	0,75	0,25	–

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

Рис. 5.8.1. Последовательные этапы построения дендрита на ос­нове матрицы сходства выборок

5.8.2. Плеяды Терентьева

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

Плеяды Терентьева (рис. 5.8.2) также можно построить с помощью матрицы фаунистического сходства, вычисленной на основе индекса сходства Жаккара (табл. 5.8.1).

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

	1,0		Д	Г	В	Е	А	Б
	0,8
	0,6
	0,4
	0,2
	0

Рис. 5.8.2. Один из типов неориентированного графа – плеяд Терентьева, построенный на основе матрицы сходства выборок, где величины индекса сходства: 1 – [0,7: 0.9]; 2 – [0,4; 0,7]; 3 – [0,2: 0,4]

Другой графический вариант плеяд Терентьева показывает вза­имосвязи между выборками на разных уровнях сходства: 0,8, 0,5 и 0,2 (рис. 5.8.3).

	1,0		Д	Г	В	Е	А	Б
	0,8
	0,6
	0,4
	0,2
	0

Рис. 5.8.3. Один из типов плеяд Терентьева. Взаимосвязи между объектами показаны на уровнях сходства 0,8. 0,5 и 0,2

На уровне сходства 0,8 есть взаимосвязь между объектами Г и В, Г и Д, а также А и Б. На уровне сходства 0,5 прибавляются взаи­мосвязи между объектами Д и А, Г и Е, Г и Б, А и Е, Б и Е и т. д.