BIRCH

BIRCH (באנגלית: Balanced Iterative Reducing and Clustering using Hierarchies, בראשי תיבות: BIRCH) הוא אלגוריתם לא מנוהל (unsupervised) המשמש ליישומי כריית מידע לביצוע ניתוח אשכולות היררכיים על מערכי נתונים גדולים במיוחד, כגון אלו הקיימים ביישומי ביג-דאטה לסוגיהם. שמו של האלגוריתם נגזר מראשי התיבות באנגלית, שמשמעותן "אלגוריתם ניתוח אשכולות היררכי, מאוזן ומופחת איטרציות".

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

רקע

אלגוריתם BIRCH פותח בשנת 1996 על ידי קבוצת חוקרים מאוניברסיטת ווינסקונסין. האלגוריתם קיבל את פרס עשר השנים של SIGMOD לשנת 2006.

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

ישויות ומבני נתונים

מאפיין אשכול

מאפיין אשכול (באנגלית Clustering Feature, בראשי תיבות: CF) היא הגדרה לרשומה בסיסית לתיאור ולכימות מבנה נתונים המכיל אוסף נקודות מידע. באופן פורמלי מאפיין האשכול מוגדר על ידי סט של שלוש ישויות: $CF=(N,{\overrightarrow {LS}},SS)$, כאשר $N$ הוא מספר הנקודות במבנה הנתונים ואילו ${\overrightarrow {LS}}$ ו-$SS$ מוגדרים כך:

${\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}$, $SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$.

במרחב רב-ממדי, הביטוי של $SS$ יבוטא באמצעות ריבוע הנורמה המתאימה.

הגדרת סט מאפיין האשכול מאפשרת פורמולציה עבור שתי ישויות חשובות בעולם ניתוח האשכולות:

• מרכז האשכול (Centroid): ${\overrightarrow {C}}={\frac {\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}{N}}={\frac {\overrightarrow {LS}}{N}}$
• רדיוס: $R={\sqrt {\frac {\sum _{i=1}^{N}({\overrightarrow {X_{i}}}-{\overrightarrow {C}})^{2}}{N}}}={\sqrt {\frac {N\cdot {\overrightarrow {C}}^{2}+SS-2\cdot {\overrightarrow {C}}\cdot {\overrightarrow {LS}}}{N}}}={\sqrt {{\frac {SS}{N}}-({\frac {\overrightarrow {LS}}{N}})^{2}}}$

עץ מאפייני אשכולות

עץ מאפייני אשכולות (באנגלית: CF-Tree) הוא מבנה נתונים מסוג עץ מאוזן, אשר נבנה מתוך סריקה טורית של הנקודות בסט הנתונים. העץ מבוסס על שני פרמטרים:

• פקטור הסתעפות (באנגלית: Branching Factor), המסומן B ומייצג את מספר הבנים לכל צמת בעץ, אשר אינה עלה.
• פרמטר סף (באנגלית: Threshold), המסומן T ומייצג את הרדיוס המקסימלי המתאר את גודלו של כל אשכול המיוצג על ידי מבנה העץ. גודלו של העץ, אם כך, נקבע על ידי T.

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

• צמת שאינה עלה - מכיל B רשומות לכל היותר, מהצורה $[CF_{i},child_{i}]$, כאשר $CF_{i}$ הוא מאפיין האשקול עבור עבור הבן ה-$i$. ואילו $child_{i}$ הוא המצביע אל הבן ה-$i$.

• 

  תרשים של עץ מאפייני אשכולות

  עלה - מכיל לכל היותר L רשומות מהצורה $[CF_{i}]$, כפי שהוגדר עבור צמת שאינה עלה. כמו כן כל עלה מכיל שני מצביעים, המכונים Prev ו-Next, אשר מקושרים לעלים אחרים ונועדו לאפשר סריקה טורית של העלים.

האלגוריתם

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

שלב ראשון: הכנסת הנתונים לעץ

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

שלב שני: דחיסת העץ

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

שלב שלישי: ניתוח מחדש לעלים

כשלב שלישי, מופעל אלגוריתם ניתוח אשקולות כלשהו על העלים בלבד (תוך שימוש במצביעים Next ו-Prev), על מנת ליצור אשקולות מעודכנים ללא סריקה מחדש של המידע.

יישומים רבים של BIRCH רואים בשלב זה אופציונלי ולא מחייב, שכן לאחר השלב הראשון ניתן להתייחס למבנה הנתונים כמבנה אשכולות לפי סידור העלים.

שלב רביעי: עדכון האשכולות

זהו שלב אופציונלי, בו ניתנת האפשרות לסידור מחדש של האשקולות לפי הניתוח שנעשה בשלב השלישי. לצורך כך מחושב מחדש המרכז ${\overrightarrow {C}}$ עבור כל אשקול וסידור הנקודות יהיה לפי מרחק הסף T מהמרכזים המעודכנים.

יתרונות וחסרונות

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

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

דוגמאות לשימושים

• מחקר בנושא אלקטרוניקת הספק, מציע שימוש באלגוריתם BIRCH עבור ניתור עומסי אנרגיה ביתית (NILM).