אלגוריתם לויד-מקס

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

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

את האלגוריתם ניתן להפעיל במרחב אוקלידי, אך אלגוריתמים דומים יכולים להיות מופעלים על מרחבים ממד גבוה יותר או למרחבים לא אוקלידים.

בקוונטיזציה, האלגוריתם מאפשר למזער את השגיאה הריבועית הממוצעת.

הדגמה של אלגוריתם לויד-מקס. דיאגרמת וורונוי מוצגת עבור הנקודות בכל שלב. סימני הפלוס מסמנים את המרכזים של תאי וורונוי.
איטרציה 1
איטרציה 2
איטרציה 3
איטרציה 15
בתרשים האחרון, הנקודות סמוכות למרכזים של תאי וורונוי.

קוונטיזציה אחידה ושגיאת קוונטיזציה[עריכת קוד מקור | עריכה]

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

נחשב את ו- האופטימליים:

עבור , נגזור ונשווה ל-0:

(שכן, )

ואזי, נקבל האופטימלי:

עבור , נגזור ונשווה ל-0:

ואזי, נקבל האופטימלי:

כאשר:

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

- קבע בצורה שרירותית ואחידה את עבור .

- בצע בצורה איטרטיבית עד התכנסות:

  • לא בהכרח מתכנס למינימום מוחלט (יכולים להיתקע במינימום מקומי)
  • כאמור, אלגוריתם זה נותן קוונטיזציה
  • ישנן טבלאות עבור התפלגות גאוסית עבור ערכי N שונים.
    • במקרים שהתוחלת היא , אזי:
    • ובמקרים שהשונות היא , אזי:
    • ובמקרה הכללי:

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

הפונקציה הראשונה

דוגמה להתכנסות אלגוריתם לויד- מקס למינימום לוקלי:

נניח N=2. בתמונה משמאל ניתן לראות את .

, וכן מתקיימים התנאים לLloyd Max.

הפונקציה השנייה

למרות שקיימנו את תנאי Lloyd Max, קיבלנו מינימום לוקלי.

פתרון טוב יותר היה הפונקציה התחתונה:

לפי תנאי 1 באלגוריתם, מקבלים את הערך של והוא יהיה יותר קרוב למלבן הרחב בציור הראשון.

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

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

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