بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارائه يک مدل جديد مبتني بر گراف جهت خلاصه سازي چندسندي متون
خلاصه
با توجه به رشد روزافزون مستندات و منابع اينترنتي، نياز به سيستم هاي خلاصه ساز بيشتر احساس ميشود.
سيستم هاي خلاصه ساز چندسندي سيستم هايي هستند که مفاهيم اصلي اسناد ورودي را در چندين جمله بيان ميکنند.
افزونگي، پوشش محتوا و پيوستگي بين جملات ، سه چالش اصلي اين سيستم ها محسوب ميشود. بررسي سيستم هاي امروزي نشان ميدهد که اين چالش ها هنوز رفع نشده اند. در اين مقاله يک معماري جديد سه لايه مبتني بر گراف معرفي ميشود. هر جمله نشان دهنده ي يک راس در گراف ميباشد و شباهت بين جملات ، يال هاي اين گراف را تشکيل ميدهد.
در مرحله ي اول با استفاده از استخراج ويژگيها، براي هر جمله ارزشي تعيين ميشود. در مرحله ي دوم يک الگوريتم خوشه بندي معرفي ميشود. با استفاده از اين الگوريتم ، جملاتي که باعث افزونگي ميشوند، حذف ميشود. در مرحله ي سوم با استفاده از الگوريتم رتبه بندي و تابع هدف ، پوشش و پيوستگي جملات خلاصه افزايش مييابد. مهم ترين مزيت اين مقاله اين است که هر سه چالش بيان شده را با هم بهبود ميدهد. براي ارزيابي سيستم ارائه شده از مجموعه داده اي
DUC٢٠٠٢ استفاده ميگردد. بر اساس معيار استانداردF، بهبود قابل توجه سيستم پيشنهادي در مقايسه با ساير سيستم ها مشهود ميباشد.
کلمات کليدي: خلاصه سازي چند سندي، مبتني بر گراف ، خوشه بندي، استخراج جملات ، رتبه بندي، پردازش زبان طبيعي
١. مقدمه
به دليل دسترسي آسان و کم هزينه به دنياي وب ، امروزه استفاده از اين تکنولوژي براي تبادل اطلاعات بين افراد بيشتر شده است . يکي از روش هاي تبادل اطلاعات ، اطلاعات متني است . اطلاعات متني در مقايسه با اطلاعات غير متني داراي حجم کمتر و سرعت دسترسي بيشتري دارند. از طرفي، روزانه حجم اطلاعات متني قابل دسترس براي نياز کاربران در حال افزايش است . به طوري که هر فردي براي جستجوي يک موضوع خاص با هزاران منبع اطلاعاتي روبرو ميشود.
بررسي تمام اين منابع متني براي هر فردي بسيار سخت و زمان گير ميباشد. يکي از روش هاي حل اين مسئله استفاده از خلاصه سازي † است . خلاصه سازي، يعني نمايش فشرده و دقيق متن ورودي به طوري که متن خروجي مفاهيم مهم متن ورودي را در بر داشته باشد.
١
توليد خلاصه به روش دستي دشوار، کند و پرهزينه است . خلاصه سازي خودکار متون باعث صرفه جويي در وقت و
توليد اطلاعات مفيدتر ميگردد. سه مزيت عمده توليد خودکار خلاصه عبارتند از[١]: ١. اندازه خلاصه قابل کنترل است . ٢.
محتواي آن قابل پيش بيني است . ٣. به راحتي قابل تشخيص است که هر بخش از خلاصه مربوط به کدام بخش از متن ميباشد.
هووي * و لين † [٢] در سال ١٩٩٨، خلاصه سازي را به سه جنبه ي اصلي(١) نوع منبع ورودي، (٢) مشخصات خلاصه
§ ‡
توليد شده (خروجي) و (٣) هدف خلاصه سازي طبقه بندي نموده اند. ١- نوع منبع ورودي: تک سندي ، چندسندي .
خلاصه سازي تک سندي، يک سند را فشرده ميکند و خلاصه را ايجاد ميکند. در حالي که خلاصه سازي چند سندي، مجموعه اي از اسناد را فشرده ميکند و به شکل کوتاه تر نمايش ميدهد. کار خلاصه سازي چندسندي بسيار پيچيده تر از خلاصه کردن يک سند است . اين مشکل از اينجا ناشي ميشود که در خلاصه سازي چندسندي با مسئله ي افزونگي اطلاعات مواجه هستيم . ٢- خلاصه ي توليد شده (خروجي): استخراجي **، چکيده اي ††. در خلاصه هاي استخراجي، عينا جملاتي از متن اصلي که مهم ترين جملات متن هستند به عنوان خلاصه ي متن انتخاب ميشوند. در حالي که خلاصه ي چکيده اي، تفسيري از متن اوليه است . جملاتي که مفهوم متن اصلي را ميرساند و عينا از خود جملات متن اصلي انتخاب نميشوند. خلاصه ي چکيده اي به مراتب پيچيده تر ميباشد، زيرا نياز به تکنيک هاي عميق پردازش زبان طبيعي دارد. به همين دليل اکثر کارهاي انجام شده در حوزه خلاصه سازي خودکار متون به صورت استخراجي ميباشد. ٣- هدف خلاصه - سازي: کلي ‡‡، مبتني بر پرس وجو§§. خلاصه ي کلي يک درک کلي از محتواي سند را ميدهد، در حالي که در يک خلاصه ي مبتني بر پرس وجو، جملات متناسب با خواسته ي مد نظر کاربر انتخاب ميشوند. سيستم پيشنهادي بر روي خلاصه سازي چندسندي استخراجي کلي متمرکز ميشود.
در اين مقاله يک سيستم جديد مبتني بر گراف براي متون چند سندي معرفي ميشود. در اين سيستم ابتدا ارزش هر جمله مشخص ميشود. سپس با استفاده از الگوريتم خوشه بندي جملاتي که باعث افزونگي ميشوند، حذف ميگردند. در مرحله آخر با استفاده از الگوريتم رتبه بندي و با استفاده از يک تابع هدف جملات خلاصه تشکيل ميشوند. اين الگوريتم باعث ميشود پيوستگي بين جملات خلاصه بيشتر شده و از طرفي دقت و پوشش محتواي اسناد بالاتر رود.
ادامه مقاله به صورت زير سازماندهي شده است : در بخش دوم کارهاي مرتبط بررسي ميشود. در بخش سوم روش پيشنهادي و ويژگيهاي بکار رفته توضيح داده ميشود. در بخش چهارم با استفاده از مجموعه داده اي DUC٢٠٠٢ روش پيشنهادي مورد ارزيابي قرار ميگيرد. در نهايت بخش پنجم نتيجه گيري اين مقاله را شامل ميشود.
٢. کارهاي مرتبط
روش هاي زيادي براي خلاصه سازي اسناد وجود دارد که ميتوانند به دو دسته طبقه بندي شوند. يک دسته مبتني بر مرکز*** است که به جملات اسناد امتياز ميدهد[٣,٤] . دسته بعدي مبتني بر گراف است که بر اساس رتبه بندي و
٢
رايگيري * ميباشد[٥,٦,٧,٨,٩]. در روش هاي مبتني بر مرکز اغلب جملاتي که شامل مهم ترين کلمات هستند، جهت تشکيل خلاصه انتخاب ميشوند، ولي در روش هاي مبتني بر گراف هر جمله به عنوان يک راس از گراف و شباهت بين جملات به عنوان يال اين گراف در نظر گرفته ميشود.
در [١٠] روشي پيشنهاد شده که در آن خوشه بندي بر مبناي يک تابع هدف صورت ميگيرد. اين تابع ، تابعي است که بر مبناي عدم شباهت بين جملات در خوشه تعريف شده است و بايد کمينه شود. براي کمينه کردن اين تابع ، خوشه ها با استفاده از روش K-Means خوشه بندي ميشوند. سپس تا جايي که امکان جابجايي جملات بين خوشه ها وجود داشته باشد به نحوي که اين جابجايي منجر به کاهش تابع هدف گردد، فرآيند جابجايي ادامه مييابد.
در[١١] يک سيستم خلاصه ساز چندسندي مبتني بر مرکز، تحت عنوان MEAD ارائه ميشود. در اين سيستم ، براي هر جمله در يک خوشه از اسناد مربوطه ، سه ويژگي امتياز مرکز، موقعيت و شباهت با عنوان را محاسبه ميکند و از ترکيب خطي اين ويژگيها براي شناسايي جملات مهم استفاده ميکند.
سيستم ارائه شده در [١٢] روش مبتني بر مرکز است که براي انتخاب جملات از مفاهيم ويکيپديا استفاده ميکند.
اين روش نگاشتي از جملات اسناد به مفاهيم ويکيپديا انجام ميدهد.
سيستم ارائه شده در [١٣] از متون ويکيپديا و عناوين متون براي شناسايي کلمات مهم اسناد و حذف نويز استفاده
ميکند.
در سال ٢٠١٢ روشي توسط گوتا† و همکارانش [١٤] ارائه شده است که خلاصه هاي تک سندي را با استفاده از تکنيک هاي خوشه بندي جملات ترکيب ميکند تا خلاصه هاي چند سندي ايجاد کند. نحوه کار به اين صورت است که ابتدا يک خلاصه تک سندي با استفاده از روش امتيازدهي جمله ايجاد ميشود. سپس جملات با استفاده از شباهت هاي نحوي و معنايي بين جملات خوشه بندي ميشوند تا قسمت هايي از متون که بايد در خلاصه بيايد مشخص گردد. نهايتا خلاصه با استخراج يک جمله از هر خوشه توليد ميشود.
در [١٥] براي خلاصه سازي متون ، از الگوريتم PageRank با استفاده از رايگيري و پيشنهادات ‡ بين جملات ارائه ارائه ميکند. اين مدل ابتدا گرافي ايجاد ميکند تا ارتباط بين جملات را نشان دهد. سپس الگوريتم PageRank را براي محاسبه امتياز جملات اعمال ميکند. جملات با امتياز بالا براي خلاصه انتخاب ميشوند. اين سيستم براي متون چندسندي معرفي شده است .
روش ارائه شده در [١٦] يک روش گرافي ميباشد که هر جمله به صورت يک راس در نظر گرفته ميشود . جملاتي که بيشترين ميزان ارتباط را با کلمات مهم دارند، مهم تر هستند. منظور از ارتباط اين است که همپوشاني محتوايي و لغوي بيشتري با ساير جملات داشته باشند. مهم تر بودن بوسيله الگوريتم بازگشتي PageRank مشخص ميشود.
روش ارائه شده در [١٧] يک مدل مبتني بر HITS§ براي خلاصه سازي چندسندي ميباشد. در اين روش اسناد به به عنوان هاب ها و جملات ارزش هاي اين هاب ها هستند. براي به دست آوردن امتياز نهايي جملات از امتياز هاب ها و ارزش ها استفاده ميشوند.
سيستم ارائه شده در [١٨] يک روش گرافي ميباشد. در اين روش جملات به منظور يافتن موضوعات نهفته داستان در گروه هاي مختلفي خوشه بندي ميشوند و جملات با امتياز بالا براي تشکيل خلاصه انتخاب ميشوند. اين سيستم براي متون داستاني معرفي شده است .
در [١٩] سيستمي تحت عنوان PSG که يک مدل گرافي دولايه است ، ارائه شده است . در لايه اول زيرگرافي تشکيل ميشود که ارتباط بين جملات را نشان ميدهد و در لايه دوم زير گراف ارتباط بين عبارات موجود در جملات ايجاد مي - شود. بررسي اين ارتباط با تجزيه و تحليل ويکيپديا انجام ميشود. بالاخره دو زير گراف باهم ادغام ميشوند و جملات خلاصه توليد ميشود.
در [٢٠] روشي ارائه شده است که با اضافه کردن يک گره براي هر جمله اسناد ورودي به يک گراف وزن دار تبديل ميشوند. هر دو جمله توسط اندازه گيري اعوجاج * که نشان گر ارتباط معنايي بين آنها است بررسي ميشوند. اگر اعوجاج کمتر از حد آستانه ي از پيش تعريف شده باشد، يک يال بين دو جمله اضافه ميشود. پس از تشکيل گراف ، به منظور يافتن مهمترين جملات جهت ايجاد خلاصه الگوريتم رتبه بندي تکرارشونده روي گراف اعمال ميشود و جملات خلاصه تشکيل ميشود.
در [٢١] يک سيستم خلاصه سازي چندسندي معرفي شده است . در اين روش جملات خلاصه توسط الگوريتم خوشه بندي مبتني بر گراف که از شباهت هاي آماري و زباني استفاده ميکند، تعيين ميشود. اين الگوريتم متن را به يک گراف تبديل کرده و با استفاده از TextRank جملات اصلي گراف شناسايي ميشود. سپس جملات بر اساس شباهت بين آنها گروه بندي ميشوند.
بررسي سيستم هاي معرفي شده پيشين نشان ميدهد که هنوز اين سيستم ها کامل نيستند و داراي مشکلاتي مي - باشند. مهم ترين مشکلات اين سيستم ها دقت پايين ، عدم پيوستگي بين جملات خلاصه و داشتن افزونگي بالا در جملات خلاصه ميباشد.
٣. روش پيشنهادي
يک خلاصه خوب ، خلاصه اي است که بخش هاي مهم يک متن (يا متون ) را انتخاب کرده و به صورت پيوسته و خوانـا در اختيار کاربر قرار ميدهد. در اين مقاله ، يک معماري جديد براي خلاصه سازي چندسندي استخراجي معرفـي مـيشـود.
اين معماري در شکل ١ ارائه ميشود.
شکل ١- معماري کلي سيستم ارائه شده
اين معماري ارائه شده ، چهار مرحله اي ميباشد.
١- در مرحله ي اول ، پيش پردازش بر روي متون که شامل حذف کلمات توقف و ريشه يابي ميباشد، صورت ميگيرد.
کلمات توقف ، کلماتي هستند که به دليل بار معنايي بسيار اندک مانند ضمائر، حروف اضافه و حرف تعريف ، حذف کردن آنها قبل از مرحله ي پردازش متن مفيد خواهد بود. ريشه يابي فرايندي است که کلماتي که هم ريشه هستند را به يک شکل تبديل ميکند. در اين مقاله براي ريشه يابي از الگوريتم پورتر† استفاده شده است .
٢- در مرحله دوم ، پس از پيش پردازش متون ورودي، ويژگيهاي اساسي سيستم هاي خلاصه ساز مانند: شباهت با عنوان ، کلمات پرارزش محاسبه ميشود و بر اساس اين ويژگيها، به هر جمله امتيازي تخصيص داده ميشود.
٣- در مرحله سوم ، بر اساس امتياز هر جمله بر اساس الگوريتم خوشه بندي که معرفي ميشود، گرافي تشکيل مي - دهيم . در اين گراف هر جمله يک راس از گراف ميباشد و يالهاي اين گراف بر اساس الگوريتم خوشه بندي تشکيل ميشود. هدف اين مرحله حذف جملاتي که باعث افزونگي ميشوند، ميباشد.
٤- در مرحله چهارم ، با استفاده از يک الگوريتم رتبه بندي، جملات خلاصه انتخاب شده و به کاربر ارسال ميشود.
اين مراحل در ادامه توضيح داده ميشوند.
١.٣ محاسبه ويژگيها
TFIDF 1.1.3
براي محاسبه ي اين ويژگي، متن ورودي به صورت يک ماتريس نمايش داده ميشود که تعداد سطرها نشان دهنده ي تعداد جملات و تعداد ستون ها نشان دهنده ي تعداد کلمات هر جمله ميباشد. به عنوان مثال ، [٣١٨]M، يعني جمله سوم متن داراي ١٨ کلمه ميباشد. بر اساس فرمول ١، TFIDF محاسبه ميشود.
در اين رابطه ، freqi,j تعداد رخدادهاي کلمه j ام در جمله i ام ميباشد. (Maxk)freqi,j نشان دهنده ي ماکزيمم رخداد تکرار کلمه در سند k ميباشد. Df نشان دهنده ي اين است که کلمه در چند سند استفاده شده است . N تعداد کل اسناد ميباشد و m تعداد کلمات هر جمله است . براي هر کلمه اين ويژگي محاسبه ميشود و تا زماني که به انتهاي جمله نرسيديم مقادير با هم جمع ميشود. اين عمل براي تمام جملات انجام ميشود.
٢.١.٣ شباهت کسينوسي
ويژگي ديگري که براي سيستم هاي خلاصه ساز بسيار مهم است ، محاسبه ي شباهت بين جملات ميباشد. براي محاسبه ي شباهت بين دو جمله ي متن از رابطه ي ٢ استفاده ميشود.
