Учебники

Python — График данных

CSGraph расшифровывается как Compressed Sparse Graph , который фокусируется на алгоритмах Fast графа, основанных на разреженных матричных представлениях.

Графические представления

Для начала давайте разберемся, что такое разреженный граф и как он помогает в представлении графов.

Что такое разреженный граф?

Граф — это просто набор узлов, между которыми есть связи. Графики могут представлять почти все — соединения в социальных сетях, где каждый узел является личностью и связан со знакомыми; изображения, где каждый узел является пикселем и связан с соседними пикселями; точки в многомерном распределении, где каждый узел связан со своими ближайшими соседями и практически всем остальным, что вы можете себе представить.

Один очень эффективный способ представления данных графа — это разреженная матрица: назовем ее G. Матрица G имеет размер N x N, а G [i, j] дает значение связи между узлом «i» и узлом. ‘J’. Разреженный граф содержит в основном нули, то есть большинство узлов имеют только несколько соединений. Это свойство оказывается истинным в большинстве случаев, представляющих интерес.

Создание подмодуля разреженного графа было мотивировано несколькими алгоритмами, использованными в scikit-learn, которые включали следующее:

  • Isomap — алгоритм обучения многообразия, который требует нахождения кратчайших путей в графе.

  • Иерархическая кластеризация — алгоритм кластеризации, основанный на минимальном остовном дереве.

  • Спектральная декомпозиция — алгоритм проекции, основанный на лапласианах разреженных графов.

Isomap — алгоритм обучения многообразия, который требует нахождения кратчайших путей в графе.

Иерархическая кластеризация — алгоритм кластеризации, основанный на минимальном остовном дереве.

Спектральная декомпозиция — алгоритм проекции, основанный на лапласианах разреженных графов.

В качестве конкретного примера представьте, что мы хотели бы представить следующий неориентированный граф:

Ненаправленный граф

Этот граф имеет три узла, где узлы 0 и 1 соединены ребром веса 2, а узлы 0 и 2 соединены ребром веса 1. Мы можем построить плотные, замаскированные и разреженные представления, как показано в следующем примере. , имея в виду, что ненаправленный граф представлен симметричной матрицей.

G_dense = np.array([ [0, 2, 1],
                     [2, 0, 0],
                     [1, 0, 0] ])
                     
G_masked = np.ma.masked_values(G_dense, 0)
from scipy.sparse import csr_matrix

G_sparse = csr_matrix(G_dense)
print G_sparse.data

Вышеуказанная программа сгенерирует следующий вывод.

array([2, 1, 2, 1])

Ненаправленный граф с использованием симметричной матрицы

Это идентично предыдущему графику, за исключением того, что узлы 0 и 2 соединены ребром нулевого веса. В этом случае представленное выше плотное представление приводит к неоднозначности — как можно представить не-ребра, если ноль является значимым значением. В этом случае либо маскированное, либо разреженное представление должно использоваться для устранения неоднозначности.

Давайте рассмотрим следующий пример.

from scipy.sparse.csgraph import csgraph_from_dense
G2_data = np.array
([
   [np.inf, 2, 0 ],
   [2, np.inf, np.inf],
   [0, np.inf, np.inf]
])
G2_sparse = csgraph_from_dense(G2_data, null_value=np.inf)
print G2_sparse.data

Вышеуказанная программа сгенерирует следующий вывод.