תקציר- כריית מידע מטקסט ואלגוריתמי סיווג לטקסט גילוי ידע במאגרי נתונים Knowledge Discovery in Databases (KDD) , הינו תחום העוסק בפיתוח תיאוריות וכלים לסיוע בחילוץ ידע שימושי מכמויות אדירות של המידע הדיגיטלי הנאגרות בקצב מסחרר בעולם המידע כיום. כריית מידע הינה שלב הכרחי בתהליך גילוי הידע, במסגרת שלב זה מפעילים אלגוריתמים ושיטות לזיהוי מידע שימושי וידע הקיים באוסף הנתונים.
האלגוריתמים שיופעלו תלויים בסוג המידע שרוצים לכרות ובתחום בו עוסקים. חלקי מידע וידע אילו נקראים תבניות, קיימות תבניות מסוגים שונים.
במסגרת העבודה המסכמת אתמקד בתחום כריית טקסט – במקרה זה הקלט הינו טקסט חופשי כגון ספרים אלקטרונים, מאמרי מחקר, מידע חדשותי, הודעות אימייל, דפי אינטרנט ועוד. הוא כתוב באופן חופשי בשפה טבעית והוא אינו מידע בעל מבנה קשיח וידוע מראש.
העבודה תציג את תהליך כריית הטקסט הכולל מספר שלבים: הגדרת הבעיה, איסוף הנתונים, הכנת הטקסט לכרייה באמצעות טיוב הטקסט, הקטנת גודל הקלט ובחירת אופן הייצוג של הטקסט, כריית תבניות הטקסט, ניתוח התוצאות והסקת המסקנות.
עיקרה של העבודה תעסוק בכריית תבניות סיווג – בכריית תבנית מסוג זה נדרש לשייך כל קלט לאחת מקבוצת קטגוריות ידועה מראש, למשל סיווג מסמך לאחד מקבוצת נושאים או סיווג מסמכים ע"פ כותבם. העבודה תכיל סקירה של אלגוריתמים לסיווג טקסט: K-Nearest Neighbor Algorithm ,Decision Trees ,Decision Rule ,N-Gram .
בהמשך העבודה נתאר את תהליך יישום אלגוריתם לסיווג טקסט N-Gram לפיתרון בעיית זיהוי השפה. בעיית זיהוי השפה – בהינתן טקסט ,יש לקבוע באיזה שפה הטקסט כתוב מתוך מספר שפות אפשריות. זיהוי שפה הוא חלק אינטגרלי מתהליכים רבים בעולם המידע כיום, במיוחד בתחום האינטרנט בו כמויות המידע ומספר השפות השונות הולכים וגדלים מידי יום – במנועי חיפוש ניתן להגביל את תוצאות החיפוש לשפה מסוימת או למספר שפות, הצגת דפי html באינטרנט בצורה תקינה דורשת זיהוי של השפה בה נכתב הטקסט בדף, תהליכים שונים המופעלים עבור טקסט בשפה מסוימת כגון בדיקת איות, תרגום, הסרת הטיות של מילה, כינוי גוף, מילות יחס וחיבור דורשים כעיבוד מקדים זיהוי של שפת הטקסט.
החלק האחרון של העבודה יכלול כתיבת אב טיפוס לאפליקציה (המבוססת על אלגוריתם ה N-Gram) המסוגלת להבחין בין מסמכים בשתי שפות. במסגרת חלק זה יבוצע ניסוי המשתמש באב טיפוס להבחנה בין מסמכים בשתי שפות שונות , תוצאות הניסוי ינותחו ע"פ מדדי הצלחה לסיווג טקסט.

1 . מבוא. 8
2 . כריית מידע. 11
2 .1.
תהליך גילוי הידע. 11
2 .2.
כריית מידע. מנהל עסקים
2 .2.1.
מהי כריית מידע?   מנהל עסקים
2 .2.2.
המוטיבציה והחשיבות של כריית מידע –… מנהל עסקים
2 .2.3.
סוגי הקלט לכריית מידע -..  משפטים
2 .3.
תבניות. 17
2 .3.1.
מהי תבנית -..  17
2 .3.2.
מידת העניין של תבניות —  19
2 .4.
מערכות כריית מידע. 21
2 .4.1.
מבנה מערכת כריית מידע טיפוסית — 21
2 .4.2.
סיווג מערכות לכריית מידע ..  21
3 .
כריית טקסט. 26
3 .1.
מהי כריית טקסט?. 26
3 .2.
תהליך גילוי הידע במאגרי טקסט. 26
3 .2.1.
הגדרת הבעיה   26
3 .2.2.
איסוף הנתונים -…  28
3 .2.3.
הכנת הטקסט לכרייה —  29
3 .2.4. כריית תבניות הטקסט —  39
3 .2.5. הערכת תוצאות הכרייה 44
4 . סיווג טקסט Text Categorization.. 48
4 .1.
סיווג טקסט – הגדרת הבעיה. 48
4 .2.
הצורך. 48
4 .3.
סוגי סיווג 49
4 .4.
אפליקציות סיווג 51
4 .5.
גישות לפתרון 54
4 .6.
אלגוריתמים לסיווג טקסט. 60
4 .6.1.
K-Nearest  Neigbhor Algorithm   60
4 .6.2  Decision Tree —  62
4 .6.3.  Decision Rule –.  67
4 .6.4.  N-Gram —   72
5.
זיהוי שפה Language Identification.. 77
5.1. בעיית זיהוי השפה. 77
5.2.
זיהוי שפה ע"י אלגוריתם N-Gram.. 78
5.2.1. תהליך יישום האלגוריתם לבעיית זיהוי השפה 78
5.2.2. המערכת של Canvar ו Trenkle -.  78
6 . ישום. 84
6 .1.
מבוא. 84
6 .2. הגדרת הבעיה. 84
6 .3.
אסטרטגיית הפיתרון 84
6 .4.
נתוני הקלט. 85
6 .5. אפיון האב טיפוס. 86
6 .5.1. קלט –…  86
6 .5.2. פלט –…  86
6 .5.3. רכיבי מערכת האב טיפוס –..  86
6 .6. ביצוע ניסוי סיווג וניתוח התוצאות. 88
6 .6.1. כללי 88
6 .6.2. ניסוי 1 –…  88
6 .6.3. ניסוי 2 –…  90
6 .6.4. ניסוי 3 –…  91
6 .6.5. ניתוח תוצאות הניסוים ומסקנות –…  92
7. סיכום. 93
8 . נספח א' – קוד אב טיפוס. 94
9. רשימת מקורות. 99
רשימת מקורות [BD02] Ismaןl Biskri, Sylvain Delisle, Text Classification and Multilinguism:Getting at Words via N-grams of Characters, University of Qubec,Canada, Proceedings of SCI-2002,
6 th World Multiconference, 2002
[CT94] William B. Cavnar and John M. Trenkle, N-Gram-Based Text Categorization, Environmental Research Institute of Michigan , Proceedings of SDAIR-94, 3rd Annual Symposium on Document Analysis and Information Retrieval,1994
[C02] Peter G. Constable, Toward a Model for Language Identification, Defining an ontology of language-related categories, SIL International 2002
[D94] Ted Dunning, Statistical Indentification of Language, Computing Research Laboratory, New Mexico State University, Techical Report MCCS-94-273
,1994
[FPSS97] Usama Fayyad ,Gregory Piatetsky-Shapiro, and Padhraic Smyth , From Data Mining to Knowledge Discovery in Databases, AAAI97 Conference, Providence, Rhode Island, 1997
[G95] Gregory Grefenstette, Comparing two language identification schemes,Xerox Centre Europe, Meylan, France, Proceedings of the 3rd International Conference on the Statistical Analysis of Textual Data ,1995
[HK06] Jiawei Han and Micheline Kamber, Data Mining: Concepts and Techniques, 2nd ed. Morgan Kaufmann Publishers, March 2006
[HNG05] A. Hotho,A. N¨urnberger, G.PaaB, A Brief Survey of Text Mining ,University of Kassel, Otto-von-Guericke-University Magdeburg, LDV Forum 20(1):
19-62, 2005
[HBBNM05] Baden Hughes, Timothy Baldwin, Steven Bird, Jeremy Nicholson and Andrew MacKinlay, Reconsidering Language Identification for Written Language Resources, Department of Computer Science and Software Engineering, The University of Melbourne, Australia, Proceedings 5th International Conference on Language Resources and Evaluation , pages pp. 485-488 ,2005
[KL99] Aas, Kjersti and Eikvil, Line: Text categorization – A survey. Technical Report Nr. 941, Norwegian Computing Center, June, 1999
[KT04] Haralampos Karanikas and Babis Theodoulidis, Knowledge Discovery in Text and Text Mining Software, Centre for Research in Information Management, Manchester,UK ,Technical report, UMIST – CRIM, 2004
[KZY03]  Bryan Kisiel , Jian Zhang , Yiming Yang, A Scalability Analysis of Classifiers in Text Categorization , School of Computer Science, Carnegie Mellon University ,Pittsburgh, USA, Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2003
[LAC05] D. L´opez de Ipina, J. Adeva,R. Calvo ,Multilingual Approaches to Text Categorisation, School of Electrical and Information Engineering University of Sydney, Australia, Facultad de Ingenier´ıa, Universidad de Deusto, Bilbao,Spain, The European for the informatics Professional Journal Vol. VI, issue No. 3, June 2005
[LV04] ְgata Lapedriza , Jordi Vitria, Open N-Grams and Discriminant Features in Text World: An Empirical Study, Centre de Visiper Computador- Dept. Informtica, Barcelona, Catalonia, Spain, Catalan Conference on Artificial Intelligence, 2004
[M01] Inderjeet Mani, Automatic Summarization , John Benjamins Publishing Company, 2001
[MS05] Bruno Martins and Mario J.
Silva, Language Identification in Web Pages, Faculdade de Ciencias Universidade de Lisboa ,Lisboa, Portugal, Proceedings of the 2005 ACM symposium on Applied computing p. 764-768, 2005
[P01] Arjen Poutsma, Applying Monte Carlo techniques to language identification.
SmartHaven, Amsterdam, Presented at CLIN 2001,
2 001
[PSW03] Fuchun Peng, Dale Schuurmans, Shaojun Wang , Language and Task Independent Text Categorization with Simple Language Models, School of Computer Science, University of Waterloo, Canada, Proceedings of HLT-NAACL Main Papers , pp. 110-117 ,2003
[RL05] Graham Russell and Guy Lapalme. Automatic Identification of Language and Encoding, jan 2005
[RHM02] Dragomir R. Radev, Eduard Hovy, Kathleen McKeown , Introduction to the special issue on summarization , Computational Linguistics    Volume 28 ,  Issue 4 Summarization Pages: 399 – 408, 2002
[S00] Fabrizio Sebastiani, Text Categorization , Dipartimento di Matematica Purae Applicata, Universit`a di Padova, Italy, Encyclopedia of Database Technologies and Applications p.683-687 ,2000 [S02] Fabrizio Sebastiani ,Machine Learning in Automated Text Categorization, Consiglio Nazionale delle Ricerche, Italy, ACM Computing Surveys, Vol. 34, No. 1, March
2 002, pp. 1–47.
[WSS97] M.Wechsler, P.Sheridan, P.Schauble, Multi Language Text Indexing for internet Retrevial, Swiss Federal Institute of Technology, Zurich, Switzerland, Proceedings of the 5th RIAQ Conference, Computer-Assisted Information Searching on the Internet ,1997
[1]   http://www.columbia.edu/cu/lweb/indiv/ets/offsite.language.html#slavic Major Online Text Collections by Language, Electronic Text Service, Columbia university libraries [2]       news://freetext.usenetserver.com/ [3]      news://textnews.news.cambrium.nl/ רשימת איורים איור מספר 1 – Knowledge Engeneering תרשים זרימה –..57
איור מספר 2 – Machine Learning תרשים זרימה -…58
איור מספר 3 – Decision Tree דוגמה שלב א' 63
איור מספר 4 – Decision Tree דוגמה שלב ב' –… 63
איור מספר 5 – Decision Tree דוגמה שלב ג' 64
איור מספר 6 – Postpruning –
66
איור מספר 7 – סכמת בלוקים לאלגוריתם מבוסס N-Gram לסיווג טקסט -… 73
איור מספר 8- חישוב מדד Out-Of-Order באלגוריתם  N-Gram  .74
איור מספר 9 – צירופי אותיות אופניות לשפה
77
איור מספר 10 – קלטי הניסוי של Canvar ו Trenkle .. 80 איור מספר 11- תוצאות הניסוי של Canvar ו Trenkle 81
רשימת טבלאות טבלה מספר 1 – מספר הופעות המילים לקלט –. 37
טבלה מספר 2 – מדדים להערכת איכות הסיווג –45
טבלה מספר 3 – מדדים להערכת איכות הסיווג – דוגמה –… 46
טבלה מספר 4 – סוגי סיווג -..51
טבלה מספר 5 – חישוב פרופיל קלט באלגוריתם N-Gram –74
טבלה מספר 6 – קביעת קטגוריה באלגוריתם N-Gram  –..75
טבלה מספר 7 – תוצאות ניסוי 1
89
טבלה מספר 8 – תוצאות ניסוי 2   –…90 טבלה מספר 9 – תוצאות ניסוי 3
–… 91
טבלה מספר 10 – סיכום תוצאות ניסוים …
92

1 Abstract . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .8

2 Data Mining. . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . .  11
2 .1 Knowlodge. Discovery Procces. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . 11
2 .2 Data Mining. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . מנהל עסקים
2 .2.1 What is data mining? . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . מנהל עסקים
2 .2.2 The motivation and importance of data mining.
. . . . . . . . . . . . .. . מנהל עסקים
2 .2.3 Input types for data mining . . . . . . . . .
. . . . . . . . . . . . . . . . . . .. . . משפטים
2 .3 Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .. . . … . . 17
2 .3.1 What is a pattern? . . . . . . . . . . . . .
. . . . . . . . . . . . . . .. . . . . . .. . . . 17
2 .3.2 Measure of intrest of patterns . . . . . . .
. . . . . . . . . . . . .. . . . . .. . . . 19
2 .4 Data mining systems . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .  . . .. . . . 21
2 .4.1 Structure of typcal data mining system . . . .
. . . . . . . . . . . . . .. . . . 21
2 .4.2 Classification of data mining systems  . . . . . . . . . . .  . . . . . . .. . . . 21

3 Text Mining. . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . 26
3 .1 What is text mining?. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .  . . . . .. . . 26
3 .2 The process of discovering knowledge in text databases. . . . . . .
. . . . . .. . . .26
3 .2.1 Defining the problem . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .. . . 26
3 .2.2 Collecting the data . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .. . . 28
3 .2.3 Preparing text for mining. . . . . . . . . .
. . . . . . . . . ….. . . . . . . . .. . . 29
3 .2.4 Mining text pattern. . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .. . . . 39
3 .2.5 Evaluating mining. results. . . . . . . . . . . . . . .
. . . .. . . . . . . .. . . . . . 44

4 Text Categorization .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . .48
4 .1 Defining the problem. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . – . 48
4 .2 The need for text categorization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .48
4 .3 Categorization types. . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4 .4 Categorization applications.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .51
4 .5 Solution approaches. .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 54
4 .6 Text categorization algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..
. 60
4 .6.1
K-Nearest  neighbor algorithm. . . . . .
. . . . . . . . . . . . . . . . . . . .  .   60
4 .6.2  Decision tree. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .. . .62.
4 .6.3  Decision rule. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .  .  . . 67
4 .6.4  N-Gram. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . ..
.  72
5 Language Identification  . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .77
5.1 Language identification problem. . . . . . . . . . . . . . .
. . . . . . . . . .  . . . . . .. . . 77
5.2 Language identification by n-gram algorithm. . . . . . . . . . . . . . . . . . . . . . .
. 78
5.2.1 The process of implementation algorithm to language identification            problem  . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .. 78
5.2.2 The system of canvar and trenkle. . . . . . . .
. . . . . . . . . . . . . . . . . . 78

6 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . 84
6 .1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .84
6 .2 Defining the problem. . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . 84
6 .3 Solution strategy. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .84
6 .4 Test inputs. . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . .85
6 .5 Prototype design. . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..86
6 .5.1 Input . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . …. . . . . . . . . . .  86
6 .5.2 Output . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .  . . . . .
. . . . . . .  86
6 .5.3 Prototype components. . . . . . . . . . . . .
. . . . . . . . . .  . . . . . . . . . .
.  86
6 .6 Categorization tests . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6 .6.1 General . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . .. . . . . . . . . . . . . . . 88
6 .6.2 Test 1 . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .. . . . . . . . . . .. . . 88
6 .6.3 Test 2. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .  . . .
. . . . . . . . 90
6 .6.4 Test 3. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .  .
. . . . . . . . 91
6 .6.5 Evaluating tests results. . . . . . . . . . . . . . . .
. . . . . . .. . . . . . . . . . . . .92
7 Summary . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . .  . . . . . . . . . .  . . 93

8 Appendix. A – prototype code . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .
. . . . . . . . . . . . 94
9 Bibliography . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .. . . .  99