CLTD-LP: גישה מסווגת מלמעלה למטה מותאמת עם עצי קידומות ליניאריים לגילוי תבניות שכיחות בקנה מידה גדול במאגרי נתונים

מציאת תבניות החבויות בנתונים היומיומיים

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

מדוע צירופים חוזרים חשובים

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

מגבלות שיטות כרייה מוקדמות

דורות קודמים של אלגוריתמים, כמו Apriori ו-FP-growth, סורקים מאגרי נתונים כדי לבנות מבנים שעוקבים אחר הופעת פריטים משותפת. Apriori פועל מלמטה למעלה על ידי יצירה ובדיקה של מועמדים רבים, מה שעלול להתפוצץ במספרם. FP-growth משפר זאת על ידי בניית עץ מיוחד שמדחס חלקים חוזרים של עסקאות, אך הוא עדיין נשען על בנייה חוזרת של עצי תנאים ובסיסי תבניות עבור כל פריט. וריאנטים עדכניים יותר, כולל LP-growth, OFIM ו-SSFIM, מנסים לייעל שלבים אלה, אך הם ממשיכים להתקשות כאשר המאגר גדול וספאשי — הרבה פריטים נדירים ועסקאות ארוכות ומגוונות.

קיבוץ תחילה, ואז עץ חכם יותר

גישה CLTD-LP מתחילה בעיצוב מחדש של מאגר הנתונים לפני בניית כל עץ. היא מתייחסת לכל עסקה, כגון עגלת קניות או מושב משתמש, כאל דפוס הדלקה/כיבוי של פריטים ומקבצת עסקאות דומות באמצעות אשכולות. המחברים משתמשים במדד דמיון נפוץ (מקדם ג'אקד) ומתאימים את מספר האשכולות כך שרשומות בתוך אשכול יהיו דומות ואילו אשכולות שונים ישמרו על שונות. בכל אשכול מסננים פריטים שמופיעים לעיתים רחוקות מדי, ועסקאות ריקות או כמעט ריקות מוסרות. מה שנשאר הוא מאגר נתונים קטן ונקי יותר ששומר על ההתנהגות הליבה. נתוני האשכול המטופחים האלה משרתים לאחר מכן בניית עץ קידומות ליניארי — מבנה קומפקטי בדומה למערך שמאחסן מסלולי פריטים בסדר עקבי, ומפחית את העומס של מצביעים בעיצובים עץ קלאסיים.

ממבט מלמעלה למטה במקום מלמטה למעלה

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

הוכחת רווחי זמן וזיכרון

כדי לבחון את השיטה החדשה, המחברים מיישמים את CLTD-LP על שלוש קבוצות נתונים תקניות: מאגר משחקי שחמט, מאגר דמוגרפי ציבורי (Pumsb) ומאגר רכישות אונליין אמיתי שבנו. עבור כל מאגר הם משנים את סף התדירות הדרוש לתבנית ומשווים את האלגוריתם שלהם ל-LP-growth, OFIM ו-SSFIM. בכל שלוש הקבוצות CLTD-LP מסיימת בקביעות בזמן קצר יותר ומשתמשת פחות זיכרון, במיוחד כאשר סף התדירות נמוך ויש לחקור הרבה קבוצות פריטים. המחברים מגבים תצפיות אלה עם הרצות חוזרות, בחירה זהירה של הגדרות האשכולות ובדיקות סטטיסטיות המראות שהשיפורים אינם נובעים במקרה.

מה זה אומר לכריית נתונים בעולם האמיתי

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

ציטוט: Sinthuja, M., Diviya, M. & Saranya, P. CLTD-LP: an optimized top-down clustering approach with linear prefix trees for scalable frequent pattern discovery in large datasets. Sci Rep 16, 9918 (2026). https://doi.org/10.1038/s41598-026-37338-9

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