الگوریتم HITS در پایتون — راهنمای کاربردی

۲۹۳ بازدید
آخرین به‌روزرسانی: ۱۹ تیر ۱۴۰۲
زمان مطالعه: ۳ دقیقه
الگوریتم HITS در پایتون — راهنمای کاربردی

در این مطلب، روش نوشتن الگوریتم HITS در پایتون مورد بررسی قرار گرفته است. «جستجوی موضوع القا شده با ابر پیوند» (Hyperlink Induced Topic Search | HITS) یک «الگوریتم تحلیل پیوند» (Link Analysis Algorithm) است که صفحات وب را امتیازدهی می‌کند. این الگوریتم توسط «جان کلینبرگ» (Jon Kleinberg) توسعه داده شده است. از الگوریتم HITS برای ساختارهای لینک وب به منظور کشف و رتبه‌دهی صفحات وب مرتبط برای جستجوهای خاص استفاده می‌شود. HITS از هاب‌ها و احراز هویت‌ها برای تعریف یک رابطه بازگشتی بین صفحات وب استفاده می‌کند. پیش از درک الگوریتم، ابتدا باید درباره مفهوم هاب‌ها (Hubs) و «احراز هویت‌ها» (Authorities) توضیح داده شود.

فهرست مطالب این نوشته
  • یک کوئری (Query) به موتور جستجو داده شده است که یک مجموعه از صفحات وب به شدت مرتبط هستند که Roots نامیده می‌شوند. این‌ها Authoritie‌های بالقوه هستند.
  • به صفحاتی که خیلی مرتبط نیستند، اما به صفحاتی در Roots اشاره دارند، هاب گفته می‌شود. بنابراین، یک Authority یک صفحه وب است که هاب‌های زیادی به آن اتصال (پیوند) دارند، در حالیکه یک هاب، صفحه‌ای است که به بسیاری از Authority‌ها متصل است.

الگوریتم HITS در پایتون

  • تعداد تکرارها را برابر با k قرار بده.
  • به هر گره، یک Hub score = 1 و یک Authority score = 1 تخصیص بده.
  • به اندازه K بار تکرار کن:
    • به روز رسانی Hub: امتیاز هاب هر گره = $$\sum$$ گره (امتیاز Authority هر گره‌ای که به آن اشاره دارد.)
    • به روز رسانی Authority: امتیاز Authority هر گره = $$\sum$$ (امتیاز Hub هر گره‌ای که به آن اشاره دارد.)
    • نرمال‌سازی امتیازها با تقسیم امتیاز هاب‌ها بر ریشه دوم مجموع مربعات همه امتیازها و تقسیم هر امتیاز Authority بر ریشه دوم مجموع مربعات همه امتیازهای Authority (اختیاری).

در ادامه، چگونگی پیاده‌سازی الگوریتم بیان شده با استفاده از ماژول Networxx مورد بررسی قرار می‌گیرد. گراف زیر مفروض است.

الگوریتم HITS در پایتون -- راهنمای کاربردی

در صورت اجرای الگوریتم HITS با k = 3 (بدون نرمال‌سازی) داریم:

Initially,
Hub Scores:        Authority Scores:
A -> 1             A -> 1
B -> 1             B -> 1
C -> 1             C -> 1
D -> 1             D -> 1
E -> 1             E -> 1
F -> 1             F -> 1
G -> 1             G -> 1
H -> 1             H -> 1

After 1st iteration,
Hub Scores:        Authority Scores:
A -> 1             A -> 3
B -> 2             B -> 2
C -> 1             C -> 4
D -> 2             D -> 2
E -> 4             E -> 1
F -> 1             F -> 1
G -> 2             G -> 0
H -> 1             H -> 1

After 2nd iteration,
Hub Scores:        Authority Scores:
A -> 2             A -> 4
B -> 5             B -> 6
C -> 3             C -> 7
D -> 6             D -> 5
E -> 9             E -> 2
F -> 1             F -> 4
G -> 7             G -> 0
H -> 3             H -> 1

After 3rd iteration,
Hub Scores:        Authority Scores:
A -> 5             A -> 13
B -> 9             B -> 15
C -> 4             C -> 27
D -> 13            D -> 11
E -> 22            E -> 5
F -> 1             F -> 9
G -> 11            G -> 0
H -> 4             H -> 3

بسته پایتون Networkx یک تابع توکار برای اجرای الگوریتم HITS است. این کار را می‌توان با ارجاع به گراف بالا بصری‌سازی کرد.

1# importing modules 
2import networkx as nx 
3import matplotlib.pyplot as plt 
4  
5G = nx.DiGarph() 
6  
7G.add_edges_from([('A', 'D'), ('B', 'C'), ('B', 'E'), ('C', 'A'), 
8                  ('D', 'C'), ('E', 'D'), ('E', 'B'), ('E', 'F'), 
9                  ('E', 'C'), ('F', 'C'), ('F', 'H'), ('G', 'A'),  
10                  ('G', 'C'), ('H', 'A')]) 
11  
12plt.figure(figsize =(10, 10)) 
13nx.draw_networkx(G, with_labels = True) 
14  
15hubs, authorities = nx.hits(G, max_iter = 50, normalized = True) 
16# The in-built hits function returns two dictionaries keyed by nodes 
17# containing hub scores and authority scores respectively. 
18  
19print("Hub Scores: ", hubs) 
20print("Authority Scores: ", authorities) 

خروجی قطعه کد بالا، به صورت زیر است.

Hub Scores:  {'A': 0.04642540386472174, 'D': 0.133660375232863,
              'B': 0.15763599440595596, 'C': 0.037389132480584515, 
              'E': 0.2588144594158868, 'F': 0.15763599440595596,
              'H': 0.037389132480584515, 'G': 0.17104950771344754}

Authority Scores:  {'A': 0.10864044085687284, 'D': 0.13489685393050574, 
                    'B': 0.11437974045401585, 'C': 0.3883728005172019,
                    'E': 0.06966521189369385, 'F': 0.11437974045401585,
                    'H': 0.06966521189369385, 'G': 0.0}

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۱ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *