אלגוריתם רשויות ורכזים

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש
רשויות ורכזים
Hubs and Authorities /
Hyperlink-Induced Topic Search
Hubs & Atuhoritys.gif
מבנה נתונים גרף מכוון
ממציא ג'ון קליינברג

אלגוריתם רשויות ורכזים (Hubs and Authorities; בשמו הרשמי Hyperlink-Induced Topic Search, בראשי תיבות: HITS) הוא אלגוריתם לניתוח קישורים אשר נועד לדרג דפי אינטרנט, ופותח על ידי ג'ון קליינברג (Jon Kleinberg). הרעיון מאחורי HITS נבע מתוך הצורך בהבנה מעמיקה של יצירת דפי האינטרנט וחיפושם בזמן המצאת האינטרנט. דף אינטרנט נקרא "רכז" אם הוא מצביע על הרבה דפי אינטרנט אחרים. דף "רשות" טוב הוא דף אשר הרבה רכזים מצביעים עליו.

האלגוריתם, אם כן, פולט שני פרמטרים לכל דף, "רשות" אשר מעריך את הקישורים אל העמוד, ו"רכז" אשר מעריך את הקישורים מהעמוד לעמודים אחרים.

רקע[עריכת קוד מקור | עריכה]

האלגוריתם נוצר על ידי ג'ון קלינברג בשנת 1997 בעת שעבד ב-IBM ונועד לדרג אתרים, מבחינת דיוק נחשב למדויק ביותר מבין האלגוריתם אבל מבחינת יעילות נחשב למוצלח פחות. בשל היותו פחות יעיל מאלגוריתם אחרים אין כמעט מנועי חיפוש שמשתמשים בו.

חברות החיפוש מעדיפות להשתמש ב-PageRank של גוגל אשר מבחינת יעילות נחשב לטוב ביותר, אחד ממנועי החיפוש הגדולים אשר עדיין משתמשים באלגוריתם HITS הוא ask.com אשר מטרתו לתת למשתמש את התשובה הטובה ביותר לכל שאלה.

בעוד ש-PageRank שולף ממאגר נתונים את תוצאות החיפוש בתוך זמן אפסי (ננושניות בודדות), כל חיפוש בעזרת אלגוריתם HITS מצריך להפעיל את האלגוריתם מחדש מה שגורם לתוצאות החיפוש להיות אטיות באופן משמעותי.

שימוש בכתבי עת[עריכת קוד מקור | עריכה]

ישנם כתבי עת אשר נחשבים למשפיעים יותר מאשר כתבי עת אחרים, למשל Science ו-Nature. כאשר משווים שני כתבים עת מודדים אותם על פי מספר הציטוטים בהם, בעזרת האלגוריתם ניתן לתת ערך רב יותר לציטוטים מאתרים כמו Science ו-Nature מאשר מציטוטים מאתרים פחות נחשבים. במילים אחרות עדיף לקבל אזכורים בכתבי עת נחשבים מאשר מכתבי עת פחות נחשבים ואת זה האלגוריתם עושה בהצלחה.

שימוש באינטרנט[עריכת קוד מקור | עריכה]

תופעה זו קיימת גם באינטרנט, ספירת הלינקים שמובילים לדף מסוים יכולה לתת הערכה על האיכות שלו, או לפחות על ההתבלטות שלו ברשת, אך לעיתים דף עם פחות לינקים יכול להיות משמעותי יותר אם הלינקים מופנים ממנועים חיפוש גדולים כגון יאהו, גוגל, MSN.

האלגוריתם[עריכת קוד מקור | עריכה]

Expanding the root set into a base set

באלגוריתם HITS השלב הראשון הוא למצוא מספר עמודים מצומצם הכי רלוונטיים בעזרת אלגוריתם חיפוש מבוסס טקסט, לקבוצת דפים זו נקרא "קבוצת השורש".

לאחר מכן ניצור "קבוצת בסיס" אשר תכלול בתוכה את "קבוצת השורש" והקשרים אשר יוצאים ממנה, בנוסף לכך נכלול מספר עמודים אשר מקושרים לדפים בקבוצת השורש.

בזכות יצירת כל הקשרים למעלה נוצר תת-גרף, בשביל לחסוך בזמן ריצה, אלגוריתם HITS רץ רק על תת-הגרף שנוצר ולא על האינטרנט כולו.

לדברי קלינברג, רוב הרשויות הרלוונטיות יהוו חלק נכבד "מקבוצת הבסיס" ובכך האלגוריתם יחזיר תשובה נכונה ככל הניתן.

ערכי הרשות והרכז נקבעים זה מתוך זה. ערך הרשות של דף יעלה אם רכז טוב מצביע עליו, ובאופן דומה ערכו של רכז יעלה אם הוא מצביע על רשות טובה.

האלגוריתם רץ מספר מחזורים, אשר מבצעים בכל מחזור שני שלבים בסיסים:

  1. עדכון ערך רשות: מבצעים סכימה של כל ערכי הרכזים אשר מצביעים על דף זה, מחלקים במספר הרכזים ומעדכנים את ערכה של הרשות. נובע מכאן שככל שהרכזים יהיו בעלי ערך רב יותר כך ערך הרשות יהיה גבוה יותר.
  2. עדכון ערך רכז: מבצעים סכימה של כל ערכי הרשויות אשר רכז זה מצביע עליהם, מחלקים במספר הרשויות ומעדכנים את ערכו בהתאם. ככל שערך הרשות גבוהה יותר כך ערך הרכז יעלה.

האלגוריתם לחישוב הרכז והרשות מחושב כך:

  1. בתחילה כל צומת (דף) מקבל ציון 1 לרשות ולרכז.
  2. עדכון:
    1. מעדכנים את ערכה של כל רשות.
    2. מעדכנים את ערכו של כל רכז.
    3. מנרמלים את הערכים על ידי חילוק כל ציון רכז בסכום כל ציוני הרכזים בריבוע, וכן חילוק כל ציון רשות בסכום כל ציוני הרשויות בריבוע.
  3. חזרה על שלב העדכון, אם נדרש.

הבדלים מאלגוריתמים אחרים[עריכת קוד מקור | עריכה]

HITS, כמו אלגוריתמי חיפוש אחרים, הוא אלגוריתם לולאתי שמבוסס על לינקים באינטרנט. למרות זאת ישנם כמה הבדלים מהותיים:

  • הוא מבוסס שאילתה, זאת אומרת, ציוני הרשות והרכז הנובעים מניתוח הקישור מושפעים ממונחי החיפוש.
  • מבוסס שאילתה ולא אינדקס, בשל כך זמן החיפוש הוא ארוך יותר.
  • לא נפוץ בקרב מנועי חיפוש (אחד ממנועי החיפוש היחידים אשר משתמשים באלגוריתם דומה לו הוא Ask.com).
  • לעומת אלגוריתמים אחרים שמחשבים תוצאה אחת, HITS מחשב שתי תוצאות (רכז ורשות).
  • הוא מנתח מספר קטן של דפים רלוונטיים("קבוצת הבסיס"), לא כמו PageRank שמנתח את הדפים.

פירוט האלגוריתם[עריכת קוד מקור | עריכה]

על מנת להתחיל את הדירוג, דרגת כל רשות ורכז ייקבעו ל-1.

אנו מתכוונים לבצע שני עדכונים: עדכון ערכי רשויות, ועדכון ערכי רכזים.

כלל עדכון הרשויות – לכל רשות p נבצע עדכון של ערכה –

כאשר n מייצגת את מספר הרכזים אשר מפנים אל רשות זו.

כלל עדכון הרכזים – לכל רכז p נבצע עדכון של ערכו –

כאשר m מייצגת את מספר הרשויות אשר רכז זה מצביע עליהן.

על מנת להגיע לתוצאה אופטימלית מבצעים על תהליך החישוב מספר חזרות, ואחרי כל חזרה מעדכנים את ערך הרשות/רכז.

פסאודו-קוד[עריכת קוד מקור | עריכה]

 1 G = set of pages
 2 for page in G do
 3     page.auth = 1 // page.auth is the authority score of the page p
 4     page.hub = 1  // page.hub is the hub score of 'page
 5    
 6 function HubsAndAuthorities(G)
 7     for step in (1 to k) do // run the algorithm for k steps
 8         norm = 0
 9         for page in G do      // update all authority values first
10         page.auth = 0
11             for inNeighbor in page.incomingNeighbors do // page.incomingNeighbors is the set of pages that link to 'page'
12                 page.auth += inNeighbor.hub
13         norm += square(page.auth) // calculate the sum of the squared auth values to normalise
14     norm = sqrt(norm)
15     for page in G do  // update the auth scores 
16         page.auth = page.auth / norm  // normalise the auth values
17     norm = 0
18     for page in G do  // then update all hub values
19         page.hub = 0
20         for outNeighbor in page.outgoingNeighbors do // page.outgoingNeighbors is the set of pages that 'page' links to
21             p.hub += outNeighbor.auth
22         norm += square(page.hub) // calculate the sum of the squared hub values to normalise
23     norm = sqrt(norm)
24     for page in G do  // then update all hub values
25         page.hub = page.hub / norm   // normalize the hub values

קישורים חיצוניים[עריכת קוד מקור | עריכה]