BIRCH (באנגלית: Balanced Iterative Reducing and Clustering using Hierarchies, בראשי תיבות: BIRCH) הוא אלגוריתם לא מנוהל (unsupervised) המשמש ליישומי כריית מידע לביצוע ניתוח אשכולות היררכיים על מערכי נתונים גדולים במיוחד, כגון אלו הקיימים ביישומי ביג-דאטה לסוגיהם. שמו של האלגוריתם נגזר מראשי התיבות באנגלית, שמשמעותן "אלגוריתם ניתוח אשכולות היררכי, מאוזן ומופחת איטרציות".
אחד הייתרונות הבולטים של שיטת BIRCH הוא יכולת איגוד נתונים נומריים רב-ממדיים באופן הדרגתי ודינאמי, תוך יצירת חלוקת אשכולות איכותית עבור סט מידע נתון ותוך שימוש בתקורות משאבים נמוכות (זיכרון וזמן). מאפיין חשוב נוסף של BIRCH הוא שנדרשת סריקה אחת בודדת של הנתונים לצורך הפעולה הבסיסית.
אלגוריתם BIRCH פותח בשנת 1996 על ידי קבוצת חוקרים מאוניברסיטת ווינסקונסין[1]. האלגוריתם קיבל את פרס עשר השנים של SIGMOD לשנת 2006[2].
המחקר עליו מבוסס BIRCH נולד מתוך הדרישה הגוברת לניתוח אוספי נתונים גדולים ביישומי ביג-דאטה. אלגוריתמים קודמים של ניתוח אשכולות היו פחות יעילים בפעולה על בסיסי נתונים גדולים מאוד ולא התחשבו במקרים בהם מערך הנתונים גדול מכדי להתאים לזיכרון הזמין.
מאפיין אשכול (באנגלית Clustering Feature, בראשי תיבות: CF) היא הגדרה לרשומה בסיסית לתיאור ולכימות מבנה נתונים המכיל אוסף נקודות מידע. באופן פורמלי מאפיין האשכול מוגדר על ידי סט של שלוש ישויות: , כאשר הוא מספר הנקודות במבנה הנתונים ואילו ו- מוגדרים כך:
, .
במרחב רב-ממדי, הביטוי של יבוטא באמצעות ריבוע הנורמה המתאימה.
הגדרת סט מאפיין האשכול מאפשרת פורמולציה עבור שתי ישויות חשובות בעולם ניתוח האשכולות:
עץ מאפייני אשכולות (באנגלית: CF-Tree) הוא מבנה נתונים מסוג עץ מאוזן, אשר נבנה מתוך סריקה טורית של הנקודות בסט הנתונים. העץ מבוסס על שני פרמטרים:
פקטור הסתעפות (באנגלית: Branching Factor), המסומן B ומייצג את מספר הבנים לכל צמת בעץ, אשר אינה עלה.
פרמטר סף (באנגלית: Threshold), המסומן T ומייצג את הרדיוס המקסימלי המתאר את גודלו של כל אשכול המיוצג על ידי מבנה העץ. גודלו של העץ, אם כך, נקבע על ידי T.
את עץ מאפייני האשכולות עצמו ניתן לתאר באמצעות שני סוגים של צמתים:
צמת שאינה עלה - מכיל B רשומות לכל היותר, מהצורה , כאשר הוא מאפיין האשקול עבור עבור הבן ה-. ואילו הוא המצביע אל הבן ה-.
תרשים של עץ מאפייני אשכולותעלה - מכיל לכל היותר L רשומות מהצורה , כפי שהוגדר עבור צמת שאינה עלה. כמו כן כל עלה מכיל שני מצביעים, המכונים Prev ו-Next, אשר מקושרים לעלים אחרים ונועדו לאפשר סריקה טורית של העלים.
קלט האלגוריתם כולל סט של N נקודות מידע, פקטור ההסתעפות B, פרמטר הסף T וכן ערך L המייצג את המספר המקסימלי לרשומות העלה. אלגוריתם BIRCH מחולק לארבעה שלבים כפי שמפורט להלן.
שלב זה כולל פעולה איטרטיבית של קריאת חלקי המידע והכנסתם אל מבנה העץ. עץ מאפייני האשכולות נבנה בשלב זה ורשומות מאפייני האשכולות מותנים במידה רבה בסדר הכנסת המידע. כל נקודה חדשה של קלט מפעפעת משרש העץ ועד לעלה המתאים לה על ידי בדיקה של הנקודה אל מול כל מאפיין אשכולות של הצמת, כך שבכל מעבר נבחר הבן הקרוב ביותר אל הנקודה הנקלטת. במידת הצורך תתווסף עוד רמה לעץ (למשל במקרה והעלה הנבחר כולל יותר מ-L רשומות).
זהו שלב אופציונלי, בו ניתנת האפשרות לכיווץ מבנה העץ לאחר שהוכנסו כלל הנקודות. הכיווץ נעשה על ידי הגדלת פרמטר הסף T ואיחוד של רשומות עלים וצמתים לאור הגדלה זו.
זהו שלב אופציונלי, בו ניתנת האפשרות לסידור מחדש של האשקולות לפי הניתוח שנעשה בשלב השלישי. לצורך כך מחושב מחדש המרכז עבור כל אשקול וסידור הנקודות יהיה לפי מרחק הסף T מהמרכזים המעודכנים.
היתרון הבולט ביותר של השיטה היא שדרושה רק סריקה בודדת של הנתונים. יתרון זה מבוטא פעמים רבות בסיבוכיות זמן הריצה (Computational Complexity). האלגוריתם פועל בסיבוכיות ליניארית, משמע שקיים סט סופי של פעולות בכל מחזור (איטרציה) ולכן זמן הפעולה של האלגוריתם תלוי ליניארית בגודל קלט הנתונים. כמו כן מדובר באלגוריתם יעיל מבחינת ניצול הזיכרון, פחות רגיש לסדר לעומת אלגוריתמים אחרים של ביג-דאטה ובעל רמת דיוק טובה יחסית, בשל יכולת התמודדות עם רעשי מידע בכמות סבירה.
החסרון הבולט של BIRCH (כמו רוב שיטות ניתוחי האשכולות ההיררכיים) הוא בבעיה בהתמודדות עם תרחישים של רעש חמור, כאשר שולי הרעש יכולים להשפיע מהותית על אופן חלוקת האשכולות במהלך שלב בניית עץ מאפייני האשכולות. חסרון נוסף הוא חוסר היכולת לבנות אשכולות שאינן בעלי צורה כדורית או ספרית, בשל מושג פרמטר הסף T, אשר מייצג רדיוס.
^Tian Zhang, Raghu Ramakrishnan, Miron Livny, BIRCH, Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96, ACM Press, 1996 doi: 10.1145/233269.233324