خوشه بندی اسناد متنی مبتنی بر مفاهیم همسایگی و شباهت معنایی

متن کاوی فناوری ایجاد شده جهت کنترل داده های متنی در حال رشد است که در جهت برچینی اطلاعات معنی دار از متون زبان طبیعی تلاش می کند. متن کاوی یعنی جستجوی الگوها در متن غیرساخت یافته و برای کشف خودکار دانش مورد علاقه یا مفید از متن نیمه ساخت یافته استفاده می-شود [Tan 2005].
متن کاوی تقریبا معادل با تجزیه و تحلیل متون است که وظیفه آن استخراج اطلاعات با کیفیت بالا از متن می باشد [Kan 2007]. در موارد معدودی نیز به عنوان فرآیند تحلیل متن جهت استخراج اطلاعاتی که برای اهداف خاصی مفید هستند، تعریف می شود. در زمینه کاوش متن معمولا با متونی مواجه هستیم که وظیفه آنها ارتباط اطلاعات حقیقی و یا عقاید می باشد و هدف آن استخراج خودکار اطلاعات از چنین متونی می باشد، هر چند موفقیت جزئی حاصل گردد [Kan 2007].
به طور کلی متن کاوی جهت مشخص کردن سیستمی که بتواند حجم زیادی از متون زبان طبیعی را تحلیل کند و الگوهای مفید زبانی و لغوی را شناسایی کرده و به دنبال آن اطلاعات احتمالا مفید را استخراج کند، استفاده می شود [Fan 2005]. شکل 1-1 یک مدل کلی از یک کاربرد متن کاوی را نشان می دهد. این مدل با مجموعه ای از اسناد شروع می شود، یک ابزار متن کاوی، یک سند خاص را بازیابی و پیش پردازش می کند. سپس یک مرحله تحلیل متن انجام شده و در مواقعی از شیوه-های مکرر تا استخراج اطلاعات استفاده می شود. سه روش تحلیل متن در این نمونه نشان داده شده اما بسیاری از ترکیبات دیگر نیز بر اساس اهداف سازماندهی می توانند استفاده شوند. اطلاعات حاصل می تواند در یک سیستم مدیریت اطلاعات قرار داده شود و در نهایت حجم وسیعی از دانش برای کاربر آن سیستم فراهم می شود [Fan 2005].
گاهي به جاي واژه متن کاوی از عبارت “کشف دانش از متن” (KDT )، استفاده مي شود [Sha 2005]. معمولا وظایف متن کاوی شامل طبقه بندی متن، خوشه بندی متن ، استخراج مفهوم، تحلیل معنایی، خلاصه سازی متن و مدل سازی روابط میان نهادها می باشد .

خوشه بندي، روش داده کاوي قدرتمندی است که جهت کشف موضوع از اسناد متني مورد استفاده قرار می گیرد. در اين زمينه الگوريتم هاي خانواده k-means به دلیل سادگی و سرعت بالا، در خوشه بندی داده هایی با ابعاد بالا، کاربرد فراواني دارند. در اين الگوريتم ها، معيار شباهت cosine، تنها شباهت میان زوج اسناد را اندازه گيري مي کند که در مواقعی که خوشه ها به خوبي تفکيک نشده باشند، عملکرد مناسبي ندارد. درمقابل، مفاهيم همسايگي و اتصال با در نظرگرفتن اطلاعات سراسری در محاسبه میزان نزدیکی دو سند، عملکرد بسیار بهتری دارند. چنانچه ميزان شباهت دو سند از حد آستانه اي بيشتر باشد آن دو سند همسايه اند و تعداد همسایه های مشترک میان آنها، مقدار تابع اتصال این دو سند را نشان می دهد. بنابراین با توجه به اینکه تنها دو حالت همسایگی و عدم همسایگی داریم که با صفر و یک نمایش داده می شوند، مقداری از اطلاعات را در مورد میزان شباهت میان اسناد از دست می دهیم که منجر به کاهش دقت خوشه بندی حاصل می شود. جهت رفع این مشکل، در گام اول لیستی از مقادیر گسسته را برای تعیین بازه ای از مقادیر آستانه به جای تنها یک مقدار، در نظر گرفتیم که به دنبال آن درجات متفاوتی از همسایگی، بر اساس میزان شباهت میان اسناد خواهیم داشت. همچنین جهت افزایش هر چه بیشتر دقت نتایج حاصل، از منطق فازی نیز بهره برده و مقدار شباهت میان اسناد را با استفاده از مقادیر عضویت فازی نمایش دادیم. به این ترتیب میزان همبستگی میان اسناد را با استفاده از منطق فازی بهبود داده و گام جدیدی در کاربردهای منطق فازی برداشتیم.
همچنین در اين مدل، روابط معنايي ميان کلمات ناديده گرفته شده و تنها اسنادی با واژگان مشابه با يکديگر مرتبط شده اند. در اين پروژه پایانی از آنتولوژي WordNet جهت ايجاد مدل جدید نمايش اسناد بهره برديم، بدین صورت که در آن از روابط معنايي به منظور وزن گذاري مجدد بسامد کلمات در مدل فضاي برداري اسناد استفاده شده است. سپس مفاهیم همسایگی و اتصال را بر روی مدل حاصل اعمال نمودیم. نتايج حاصل از اعمال روش های پيشنهادي و ترکیبات آنها بر روي مجموعه داده هاي متن واقعی، حاکي از عملکرد موثر و مناسب تر الگوریتم پیشنهادی ما نسبت به روش های پيشين مي-باشد و می تواند جایگزین خوبی برای الگوریتم های پیشین در امر خوشه بندی اسناد باشد.

Text Document Clustering Based on Neighbors and Semantic Similarity
خوشه بندی اسناد متنی مبتنی بر مفاهیم همسایگی و شباهت معنایی

.

فهرست مطالب
فصل 1- ورود به مطلب1
1-1- مقدمه 1
1-2- متن کاوی 2
1-2-1- تعاریف متن کاوی 3
1-3- مراحل اصلی فرآیند متن کاوی 4
1-4- کاربردهای متن کاوی 5
1-5- خوشه بندی 5
1-6- هدف از خوشه بندی 6
1-7- کاربردهای خوشه بندی 7
1-8- خوشه بندی در مقابل طبقه‌بندي 8
1-9- رویه خوشه بندی 9
1-9-1- نمایش الگو 9
1-9-2- شباهت الگو 9
1-9-3- خوشه بندی یا گروه بندی 10
1-9-4- انتزاع داده 10
1-9-5- معیارهای آزمودن خروجی الگوریتم 10
1-10- چالش های الگوریتم های خوشه بندی 11
1-11- خوشه بندی متن 12
1-12- تعریف مساله 12
فصل 2- مبانی اولیه تحقیق15
2-1- مقدمه 15
2-2- داده متنی 15
2-3- پیش پردازش متن 16
2-3-1- جمع آوری داده های متنی 17
2-3-2- Collection Reader 18
2-3-3- Detagger 18
2-3-4- Tokenization 18
2-3-4-1- حذف کلمات توقف 19
2-3-4-2- ریشه یابی 20
2-3-5- هرس کردن 22
2-3-6- وزن گذاری کلمات 22
2-4- روش های نمایش اسناد 22
2-4-1- مدل دودویی 23
2-4-2- مدل برداری 24
2-4-3- مدل احتمالاتی 25
2-4-4- مقایسه روش های مدلسازی اطلاعات 26
2-5- مدل فضای برداری در بازیابی اسناد 26
2-6- استفاده از دانش پس زمینه در خوشه بندی متون 31
2-6-1- خوشه بندی مبتنی بر آنتولوژی 31
2-6-1-1- آنتولوژی 33
2-6-1-2- آنتولوژی WordNet 34
2-7- الگوریتم های خوشه بندی سند 36
2-7-1- روشهای سلسله مراتبی 36
2-7-2- الگوریتم های افرازکننده 38
2-8- مفهوم نزدیکترین همسایه ها 39
فصل 3- مروري بر کارهاي گذشته43
3-1- مقدمه 43
3-2- استفاده از آنتولوژی در خوشه بندی اسناد 43
3-2-1- روش های وارد کردن آنتولوژی در نمایش متن 43
3-2-1-1- افزودن مفاهیم 43
3-2-1-2- جایگزین کردن کلمات با مفاهیم 44
3-2-1-3- استفاده از بردار مفاهیم به تنهایی 44
3-2-2- مقایسه روش های استفاده از آنتولوژی در خوشه بندی اسناد 44
3-3- معیارهای روابط معنایی 46
3-3-1- معیارهای مبتنی بر لبه 48
3-3-1-1- کوتاه ترین مسیر 48
3-3-1-2- اتصالات وزن گذاری شده 48
3-3-1-3- Wu and Palmer 49
3-3-1-4- Hirst-St.Onge 51
3-3-1-5- Li 52
3-3-1-6- LeacockوChadorow 52
3-3-2- معیارهای مبتنی بر گره 53
3-3-2-1- Resnik 54
3-3-2-2- Jiang-Conrath 54
3-3-2-3- Lin 55
3-3-3- معیارهای مبتنی بر ویژگی 55
3-3-3-1- Tversky 55
3-4- پیشینه استفاده از همسایگی و اتصال در خوشه بندی 56
3-4-1- تعریف همسایگی و اتصال در خوشه بندی اسناد متنی 61
3-4-2- انتخاب مراکز خوشه های اولیه بر اساس رتبه بندی 62
3-4-3- معیار شباهت بر مبنای توابع cosine و link 63
3-4-4- انتخاب یک خوشه جهت شکافتن بر اساس همسایه های مراکز 66
مراجع 73