الگوریتم 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 (اختیاری).

فیلم آموزش وب کاوی یا Web Mining در فرادرس

کلیک کنید

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

در صورت اجرای الگوریتم 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}

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

• مجموعه آموزش‌های برنامه‌نویسی پایتون
• آموزش تکمیلی برنامه‌نویسی پایتون
• مجموعه آموزش‌های داده‌کاوی و یادگیری ماشین
• زبان برنامه‌نویسی پایتون (Python) — از صفر تا صد
• یادگیری علم داده (Data Science) با پایتون — از صفر تا صد
• آموزش پایتون (Python) — مجموعه مقالات جامع وبلاگ فرادرس

^^