آموزش نمایش گراف در پایتون

0 دیدگاه

CSGraph مخفف عبارت Compressed Sparse Graph است و بر الگوریتم‌های سریع گراف که بر پایه نمایش ماتریس خلوت ساخته می‌شوند تمرکز دارد.

آموزش نمایش گراف در پایتون

برای شروع، ابتدا مفهوم گراف خلوت و کاربرد آن در نمایش گراف ها را بررسی می‌کنیم.

گراف خلوت چیست؟

گراف مجموعه‌ای از گره‌ها است که یال‌ها آن‌ها را به یکدیگر متصل می‌کنند و می‌تواند تقریباً هر نوع رابطه یا ساختاری را نمایش دهد؛ برای مثال:

در شبکه‌های اجتماعی، هر گره یک فرد است و با آشنایان خود ارتباط دارد.
در تصاویر، هر گره یک پیکسل است و به پیکسل‌های همسایه متصل می‌شود.
در یک فضای چندبعدی، هر گره به نزدیک‌ترین همسایه‌های خود وصل می‌شود.

یکی از روش‌های بسیار کارآمد برای نمایش داده‌های گراف، استفاده از ماتریس خلوت است. فرض کنید این ماتریس را G بنامیم. این ماتریس اندازه‌ای N × N دارد و مقدار G[i, j] وزن یال بین گره i و گره j را نشان می‌دهد. در یک گراف خلوت، بیشتر خانه‌های ماتریس صفر هستند؛ یعنی هر گره فقط با تعداد محدودی از گره‌های دیگر ارتباط دارد. این ویژگی در بسیاری از کاربردهای واقعی وجود دارد.

دلیل ایجاد زیرماژول Sparse Graph

توسعه‌دهندگان scikit-learn این زیرماژول را برای پشتیبانی از چند الگوریتم مهم پیاده‌سازی کردند، از جمله:

Isomap: الگوریتم یادگیری مانیفولد که کوتاه‌ترین مسیرها را در گراف محاسبه می‌کند.
خوشه‌بندی سلسله‌مراتبی (Hierarchical Clustering): روشی که بر پایه درخت پوشای کمینه عمل می‌کند.
تجزیه طیفی (Spectral Decomposition): روشی برای فرافکنی داده بر اساس لاپلاسین گراف خلوت.

فرض کنید یک گراف بدون جهت با سه گره داریم:

گره 0 و گره 1 با یالی به وزن 2 متصل‌اند.
گره 0 و گره 2 با یالی به وزن 1 متصل‌اند.

در یک گراف بدون جهت، ماتریس نمایش آن متقارن است. نمایش‌های Dense، Masked و Sparse آن به شکل زیر است:

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

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])

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

گراف بدون جهت با استفاده از ماتریس متقارن

این گراف با قبلی یکسان است، فقط بین گره‌های 0 و 2 یک یال با وزن صفر وجود دارد. در این حالت، نمایش متراکم (Dense) ابهام ایجاد می‌کند؛ اگر مقدار صفر معنا داشته باشد، چگونه یالِ ناموجود را نشان بدهیم؟ برای حذف این ابهام، باید از نمایش ماسک‌شده (Masked) یا نمایش خلوت (Sparse) استفاده کنیم.

اکنون مثال زیر را بررسی می‌کنیم:

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

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

برنامه بالا خروجی زیر را تولید خواهد کرد:

array([ 2., 0., 2., 0.])

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

در این مثال، مقدار np.inf به عنوان null_value عمل می‌کند تا مشخص شود بین دو گره یالی وجود ندارد. این روش باعث می‌شود ماتریس خلوت، داده‌ها را بدون ابهام نمایش دهد.