כיצד להתאים פיל בגיליון אלקטרוני

טבלת קישורים

תקציר ומבוא 1

2 עבודות מקדימות ונלוות

2.1 על אסטרטגיות דגימה

2.2 אסטרטגיות Coreset אחרות

2.3 Coresets עבור יישומי מסד נתונים

2.4 הטבעות Quadtree

3 מחילות מהירים

4 הפחתת השפעת ההתפשטות

4.1 חישוב גבול עליון גולמי

4.2 מפתרון משוער לפיזור מופחת

5 דחיסה מהירה בפועל

5.1 מטרה והיקף של הניתוח האמפירי

5.2 הגדרה נסיונית

5.3 הערכת אסטרטגיות דגימה

5.4 הגדרת סטרימינג ו-5.5 טייקים

6 מסקנה

7 תודות

8 הוכחות, פסאודו-קוד והרחבות ו-8.1 הוכחה לתוצאה 3.2

8.2 הפחתת ה-k-אמצעי ל-k-חציון

8.3 אומדן העלות האופטימלית בעץ

8.4 הרחבות לאלגוריתם 1

הפניות

תַקצִיר

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

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

1 הקדמה

למנתח הנתונים המודרני אין מחסור באלגוריתמים של אשכול לבחירה, אבל בהתחשב בגודל ההולך וגדל של מערכי נתונים רלוונטיים, רבים מהם הם לרוב איטיים מכדי להיות שימושיים בפועל. זה רלוונטי במיוחד עבור צינורות ביג דאטה, שבהם נעשה שימוש נפוץ באלגוריתמי אשכולות לדחיסה. המטרה היא להחליף מערך נתונים גדול מאוד במערך קטן יותר וניתן לניהול עבור משימות במורד הזרם, בתקווה שהוא מייצג היטב את הקלט המקורי. האלגוריתם של לויד [49] הוצג בדיוק מסיבה זו וממזער את שגיאת הקוונטיזציה - סכום המרחק הריבועי מכל נקודת קלט לנציג שלה במערך הנתונים הדחוס. ללא ספק אלגוריתם האשכולות הפופולרי ביותר, Lloyd's פועל עבור איטרציות מרובות עד להתכנסות עם כל איטרציה הדורשת זמן O(ndk), כאשר n הוא מספר הנקודות, d הוא מספר התכונות ו-k הוא מספר האשכולות - או גודל הדחיסה הממוקדת. עבור יישומים כאלה, מספר הנקודות יכול בקלות להיות מאות מיליונים, ומכיוון שאיכות הדחיסה עולה עם k, יעדים סטנדרטיים יכולים לקבל k באלפים [41, 4]. בהגדרות כאלה, כל אלגוריתם O(ndk) הוא איטי בצורה בלתי רגילה.

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

מכיוון שמערכי נתונים יכולים להיות גדולים במספר הנקודות n ו/או במספר התכונות d, שיטות ביג דאטה חייבות למתן את ההשפעות של שתיהן. ביחס למרחב התכונה, השאלה למעשה נסגרת מכיוון שתחזיות אקראיות הן מהירות (פועלות בזמן ליניארי ביעילות), פרקטיות ליישום [50], ומספקות ערבויות הדוקות לגבי גודל ואיכות ההטמעה. התחזית פחות ברורה כאשר מצמצמים את מספר הנקודות n, ויש שתי פרדיגמות נפרדות שכל אחת מהן מספקת יתרונות ברורים. מצד אחד, יש לנו דגימה אחידה, הפועלת בזמן תת-ליניארי אך עשויה להחמיץ תת-קבוצות חשובות של הנתונים ולכן יכולה להבטיח דיוק רק בהנחות חזקות מסוימות על הנתונים [45]. מצד שני, אסטרטגיות הדגימה המדויקות ביותר מספקות את הערבות החזקה של הליבה, שבה העלות של כל פתרון בנתונים הדחוסים היא ב-ε-פקטור של עלות הפתרון הזה במערך הנתונים המקורי [25].

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

קל להראות שכל אלגוריתם שמשיג הבטחת דחיסה חייב לקרוא את כל מערך הנתונים[1]. לפיכך שאלה פתוחה ברורה היא אילו ערבויות ניתן להשיג בזמן ליניארי או כמעט ליניארי. ואכן, אלגוריתמי דגימה מהירה הזמינים כיום לאשכולות [6, 5] אינם יכולים להשיג ערבויות חזקות של מערך ליבה. לאחרונה, [31] הציע שיטה עבור ערכות ליבה חזקות הפועלות בזמן O˜(nd + nk) והשערה שזו אופטימלית עבור k-mediaan ו-k-means.

הגבול הזה אמנם אופטימלי למעשה עבור ערכים קטנים של k, אך ישנם יישומים רבים כגון ראייה ממוחשבת [34] או הגינות אלגוריתמית [18] שבהם מספר האשכולות יכול להיות גדול ממספר התכונות במספר סדרי גודל. בהגדרות כאלה, השאלה של ערכות הליבה האופטימליות בזמן נשארת פתוחה. מאחר שסוגיית קביעת הליבה בגודל אופטימלי נסגרה לאחרונה [25, 28, 44], זו ללא ספק הבעיה הפתוחה העיקרית במחקר הליבה עבור מקבץ מבוסס-מרכז. אנו פותרים זאת על ידי מראה שקיים אלגוריתם קל ליישום שבונה ערכות הליבה בזמן O˜(nd) - רק גורמים לוגריתמיים רחוקים מהזמן שלוקח לקריאה במערך הנתונים.

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

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

לסיכום, התרומות שלנו הן כדלקמן:

• אנו מראים שניתן להשיג ערכות ליבה חזקות עבור k-אמצעי ו-k-חציוני בזמן O˜(nd). זה פותר השערה לגבי זמן הריצה הדרוש עבור ערכות הליבה של k-means [31] והוא אופטימלי תיאורטית עד לגורמי רישום.

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