כריית מידע - Data Mining

תקציר העבודה

תקציר סמינר בנושאים מיוחדים : DATA MINING:
הנושא הנדון נבחר בעקבות התפתחויות ותמורות רבות  ברשת האינטרנט בשנים האחרונות, דבר שגרם לשטף מידע של נתונים המאיים להטביע ארגונים העובדים בסביבות הרשת. בסמינר נבדק מקומו של DM (Data Mining)בתוך תהליך הנקרא KDD (Knowledge Discovery).           ה- DM מערב הרבה מאוד אלגוריתמים לצורך השגת משימות שונות. על אותם אלגוריתמים מנסים להתאים מודל מסויים למידע. האלגוריתמים בודקים את המידע ויוצרים לו מודל שמתאים למאפיינים של המידע. ישנם
2 מודלים עיקריים: האחד ניבוי (Predictive) והשני זיהוי תבניות (Descriptive), לכל מודל קיימים מספר שיטות לביצוע. אחת מהשיטות העיקריות לזיהוי תבניות הינה אשכול נתונים (Clustering). אשכול הינו תהליך בו מנתחים אוסף גדול של אובייקטים, על מנת לקבצם לאשכולות, כך שהתצפיות בתוך כל אשכול תהיינה דומות זו לזו, אבל שונות מתצפיות באשכולות אחרים. יש לציין כי זהו צעד חשוב בארגון המידע. בעבודה הנוכחית בוצעה הבחנה והשוואה בין שני אלגוריתמים לשם ביצוע אישכול האחד נקרא CLOPE והשני DNUMBER. נמצא כי אלגוריתם DNUMBER הפיק תוצאות פחות טובות בהשוואה ל- CLOPE אך למרות זאת נמצא יעיל יותר מאשר בהשוואה ל- Clope מכיוון ש- Dnumber זקוק רק בסריקה חד פעמית של בסיס הנתונים עבור אשכול נתונים.
תוכן עניינים
1.   מבוא –5

2 .   שלבי גילוי מידע בבסיס נתונים -.6
.2.1
כללי -…6

2 .2. טיוב נתונים (Data Cleaning) ..7

2 .2.1. ערכים חסרים ((Missing values –7

2 .2.2. שגיאות המידע (……………………….……..(Noisy Data8

2 .3. אינטגרציית נתונים ((Data Integration -9

2 .3.1. הפחתה ((Redundancy -…9

2 .4. המרת מידע ((Data Transformation -10
2 .4.1. נורמליזציה ((Normalization –…10
2 .4.2. הפחתת שדות ((Data Reduction -…12

2 .5. כריית מידע ((Data Mining .13

2 .5.1. מודלים ומשימות …14
2 .5.2.  ניבוי (Predictive) –…15
2 .5.2.1.  מיון (Classification) -15
2 .5.2.2.  רגרסיה (Regression) -15
2 .5.2.3.  ניתוח סדרה עתית (Time Series Analysis) -16
2 .5.2.4.  ניבוי (Prediction) –17
2 .5.3.  זיהוי תבניות (Descriptive) .17
2 .5.3.1.
אשכול (Clustering) -…17
2 .5.3.2.  סיכום (Summarization) .18
2 .5.3.3.  חוקים אסוציאטיביים (Association Rules) -..18
2 .5.3.4.  גילוי רציפות (Sequence Discovery) 19
2 .6.
תוצאות וניתוח תוצאות (Interpretation/ evaluation) 19

3 .   שיטות כרייה 20
3 .1. עצי החלטה (Decision trees) …20              3.1.1.
אלגוריתמים –20
3 .2. רשתות נוירונים (Neural Networks) -…22
3.2.1. מבנה רשת נוירונים 22
3.2.1.1. תהליך למידה (Learning Process) -23
3.2.1.2. רשתות Feed-Forward -23
3.2.1.3. רשתות Feed-Back –24
3.2.1.4. פונקציית פעולה (Activation Function) –.
5              3.2.1.5. אלגוריתמי אימון .26
3.3. אלגוריתמים גנטיים (Genetic Algorithms) 27
3.3.1. הגדרות בסיסיות -27
3.3.2. מבנה האלגוריתם -30
4 .   אלגוריתמי אשכול (Clustering Algorithms) 32

4 .1.        יחסים בין רשומות ..32
4 .1.1.
דימיון ומדידת מרחק (Similarity and Distance Measures)…33
4 .1.2.
מחוץ לאשכול (Outliers) -…34
4 .2.        אלגוריתמי אשכול …35
4.2.1. שיטות היררכיים (Hierarchical Methods) –…35
4.2.2. שיטות הפרדה למחיצות (Partitional Methods) -..37
4.3. חסרונות באלגוריתמי אשכול –39
5.   אלגוריתמי אשכול נבחרים 40 5.1.   אלגוריתם CLOPE ..40      5.1.1. הרעיון מאחורי CLOPE -…40 5.1.2.
האלגוריתם –..42
5.1.3.
סיבוכיות האלגוריתם 44
5.2.   אלגוריתם DNUMBER –44
5.2.1.
הרעיון מאחורי DNUMBER ..45
5.2.2.
האלגוריתם –…47
5.2.3.
סיבוכיות האלגוריתם 48
5.3.   תוצאות יישום האלגוריתמים -..49
5.3.1.           בסיס נתונים –.49
5.3.2.  אלגוריתם CLOPE .50 5.3.3.  אלגוריתם Dnumber  –.51
5.3.4  השוואת תוצאות -.51
5.4.
מסקנות -…52

6 .
ביבליוגרפיה -53

6 .1.
ספרים –53
6 .2.
מאמרים -..53