Неориентированные и ориентированные графы
Для эффективного выделения скоплений объектов существуют методы сетевого анализа. Сетевой анализ матрицы оценок сходства между объектами заключается в построении некоторых типов графов, т.е. диаграмм, где объекты изображены в виде точек (кружков) – вершин графа, которые соединяются или не соединяются линиями, называемыми ребрами графа. Степень соответствия между объектами отражается в графах или характером взаимного расположения точек, или длиной и другими особенностями линии, соединяющих точки. При анализе матриц сходства обычно используются «неориентированные графы», в которых линии, соединяющие вершины графа, не имеют направления. Реже применяются «ориентированные графы», в которых вершины соединены стрелками. Дендрит – один из типов неориентированного графа. Он может быть двух типов: минимальное древо (матрица включает оценки различий между объектами) или максимальное древо (используются меры сходства). Дендрит – это ломаная линия, которая может ветвиться, но не содержит циклов. Построение дендрита заключается в нахождении для каждого объекта наиболее сходного с ним объекта и соединении их линией. В результате получается ряд отрезков, в том числе и разветвленных. Построить дендрит (рис. 5.8.1) можно с помощью матрицы сходства выборочных совокупностей, например (A–Е), вычисленной на основе индекса сходства Жаккара (табл. 5.8.1). Для этого последовательно соединяем две наиболее сходные выборки Г и Д (0,90) отрезком. Следующая по силе величина сходства 0,85 обнаружена между выборками Г и В. Поэтому выборку В можно присоединить отрезком к уже построенной ветке Д – Г и т. д. Таблица 5.8.1
|
