بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارائه روشي جهت خلاصه سازي خودکار چندسندي با کمک تکنيک فاکتورگيري ماتريس نامنفي (NMF)
چکيده: با گسترش روز افزون حجم دادهها و اطلاعات، خلاصه سازي خودکار متن نيز با استقبال چشم گير محققين روبرو شده است . در سالهاي اخير خلاصه سازي چندسندي با اقبال بيشتري مواجه بوده است . يک سيستم خلاصه سازي چندسندي استخراجي، خلاصه سازي است که چندين سند به عنوان ورودي دريافت کرده و گزيدهاي از جملات اسناد اوليه را توليد مينمايد. خلاصه خوب بايد بيانگر زمينه کلي بوده و ضمن بيان ديدگاههاي مختلف موجود در متن از خوانايي و پيوستگي بالايي برخوردار باشد. در اين مقاله با تمرکز به مشکلات اصلي خلاصه سازي چندسندي، يعني پوشش کامل مطالب اصلي وعدم وجود افزونگي، روشي براي خلاصه سازي ارائه شده است . در مدل پيشنهادي، ابتدا کلمات متن استخراج شده و ماتريس کلمه -سند ساخته ميشود. سپس آنها را خوشه بندي کرده و تکنيک NMF روي آن اعمال شده است . سپس جملات مهم استخراج شده و رتبه بندي ميشوند. در نهايت خلاصه نهايي توليد ميشود. ارزيابي سيستم پيشنهادي بر روي دادههاي کنفرانس DUC و با استفاده از معيار ارزيابي ROUGE صورت گرفته است . نتايج اين روش نسبت به ميانگين ٣٢ سيستم قدرتمند دنيا که کار خلاصه سازي را انجام دادهاند، بهبود داشته است .
کلمات کليدي: خلاصه سازي چندسندي، NMF،LSA ، خوشه بندي
١. مقدمه
با گسترش روزافزون حجم اطلاعات موجود در وب، رشد روزافزون سايت هاي خبري گوناگون، انتشار کتب الکترونيکي متعدد و افزايش چشم گير مقالات منتشر شده در زمينه هاي مختلف علمي، دسترسي درست و دقيق به اطلاعات مورد نياز، همواره يکي از مشکلات محققان و پژوهشگران قرن ٢١ بوده است . حجم انبوه منابع اطلاعات از يک سو و محدوديت زمان از سوي ديگر، منجر به گرايش محققان به موضوع جذاب خلاصه سازي خودکار متن شده است . خلاصه سازي خودکار متن به عنوان هسته ي مرکزي طيف گستردهاي از ابزارهاي پردازشگر متن مانند خلاصه سازهاي ماشيني، سيستم هاي تصميم يار، سيستم پاسخ گو، موتورهاي جستجو و ... از سالها پيش مطرح شده و همواره به عنوان يک موضوع مهم مورد بررسي و تحقيق قرار گرفته است .
در خلاصه سازي چندسندي با پيچيدگيهاي بيشتري نسبت به خلاصه سازي تک سندي روبرو هستيم .
مهمترين چالش هاي پيش رو در اين دسته از خلاصه -سازها عبارتند از [١٠]:
• چون اسناد با ديدگاههاي متفاوت به شرح يک موضوع ميپردازند که گاها متناقض با يکديگر هم بوده، بنابراين توليد خلاصه اي با خوانايي بالا امري دشوار خواهد بود.
• با توجه به اين که همه اسناد در ارتباط با يک موضوع کلي ميباشند، بحث همپوشاني جمله هاي انتخاب شده از اين اسناد يا همان افزونگي مشکل مهمي ميباشد.
• استخراج ديدگاههاي مختلف پنهان در اسناد مختلف و پوشش دادن تمامي آنها نياز به دقت و توجه فراوان دارد.
٢. مرور ادبيات
در اين بخش به صورت مختصر به روشهاي مبتني بر
LSA و همچنين NMF اشاره شده است . اولين بار Gong در سال ٢٠٠١ از LSA در خلاصه سازي استفاده نمود [٢].وي در ابتدا ماتريس کلمه -جمله را با استفاده از محاسبه معيار TFISF تشکيل داد. آقاي Steinberger [٩] با دخيل کردن روش ادغام ضماير در LSA، کارايي روش Gong را افزايش داد. وي در اين مقاله ثابت کرد که ادغام ضماير با استفاده از روش افزايشي، دقت خلاصه سازي روش Gong را افزايش ميدهد. در سال ٢٠٠٥،] Yeh12]، با استفاده توامان از LSA و T.R.M(نگاشت رابطه اي متن ) ساختار معنايي پنهان موجود در سند را استخراج کرده و خلاصه را بر اساس اين روابط پنهاني استخراج شده، توليد نمود.
در سال ٢٠٠٩، Yu [١٣] روشي براي خلاصه سازي اخبار مبتني بر LSA ارائه نمود. وي در ابتدا با استفاده از LSA شباهت معنايي بين جملات را محاسبه کرده و سپس با استفاده از خوشه بندي مبتني بر روش -k means جملات را دسته بندي کرده و سپس از هر کلاستر، جمله اي که بيشترين شباهت را به موضوع داشته باشد به عنوان نماينده آن خوشه برميگرداند.
در سال ٢٠١٢، He [٥]، از تجزيه ماتريس نامنفي غيرمتقارن براي خوشه بندي جملات داخل گروها استفاده کرده و از هر خوشه جملاتي را براي خلاصه انتخاب ميکند. وي همچنين DSDR که خلاصه سازي اسناد بر اساس بازسازي دادهها ميباشد، را به کار برده است .
در اين مقاله با استفاده از روش NMF روشي را ارائه شده است که بيشترين مقدار فراخواني ٢-ROUGE را نسبت به روشهاي قبلي دارا ميباشد.
٣. روش پيشنهادي
فازهاي کلي روش ارائه شده به شرح زير ميباشد:
الف ) پيش پردازش
در اين گام دادههاي اوليه بايد پردازش شده و آماده استفاده براي مراحل بعدي گردند. مرحله پيش پردازش شامل قسمت هاي زير ميباشد:
١) استخراج جملات و کلمات تشکيل دهنده آنها: در اين گام، ابتدا جملات از اسناد ورودي استخراج مي- شوند، سپس اين جملات به کلمات تشکيل دهنده - شان تجزيه ميگردند.
٢) حذف ايست واژهها: در گام بعدي بايد ايست واژهها حذف شوند. وجود اين کلمات باعث پايين آمدن دقت و همچنين بزرگ شدن اندازه ماتريس اوليه ميشود.
٣) ريشه يابي: عمليات ريشه يابي بر روي کلمات استخراج شده، انجام ميشود تا براي کلماتي که از لحاظ معنايي و نحوي شبيه به هم هستند، يک نماينده انتخاب شود.
٤) ساخت ماتريس کلمه -سند: پس از انجام مراحل بالا ماتريس کلمه -سند ساخته ميشود. بصورتيکه کلمات در سطر و اسناد در ستون قرار ميگيرد.
براي ساخت ماتريس از روشهاي وزندهي مختلفي ميتوان استفاده نمود. در اين جا از روش وزندهي -tf - idfکه ترکيبي از روشهاي وزندهي سراسري و روش - هاي وزندهي محلي ٢ مي باشد، استفاده شده است که بصورت رابطه (١) محاسبه ميشود:
Aيک ماتريس m×n است که mتعداد لغات و nتعداد جملات در تمامي اسناد ميباشد. Aij، وزن فرکانس لغت iدر جمله jاست . جائيکه Lij وزن محلي(فرکانس لغت ) براي لغت i در جمله j است و وزن سراسري(برعکس فرکانس سند) براي لغت iدر تمامي اسناد است که در رابطه (٢) نشان داده شده است :
که در آن Nتعداد کل جملات در همه اسناد و تعداد جملاتي است که شامل لغت iميباشد. البته از روشهاي وزندهي ديگري هم ميتوان استفاده نمود.
اطلاعات کلي در مورد روشهاي وزندهي به کلمات در مرجع [٢] آورده شده است .
ب) خوشه بندي و استفاده از روش NMF
در روش پيشنهادي از خوشه بندي K-means استفاده شده است [٤]. ورودي اين الگوريتم nنمونه داده و مقدار kکه تعداد خوشه هاي خروجي را مشخص ميکند، مي - باشد. در ابتدا تعداد kنمونه به صورت معادله (٣) انتخاب ميشود:
اين نمونه ها به عنوان نماينده ي k خوشه شناخته خواهند شد. گاهي به آنها مرکز ثقل ٤ يا مرکز خوشه نيز اطلاق ميشود. هر يک از نمونه هاي باقيمانده عضوي از خوشه اي خواهند بود که يکي از نمايندهها(k نمونه ) متعلق به آن است [١]. با کمک فاصله کسينوسي تشابه هر يک از نمونه هاي باقيمانده با kنماينده محاسبه مي شود و نمونه مورد نظر به هر يک نزديکتر بود، به عضويت آن خوشه در ميآيد. به عنوان مثال، فاصله کسينوسي با توجه به ماتريس Aدر معادله (٤) نشان داده شده است :
به ترتيب ، A*a و A*b، وزن جمله aام و جمله bام هستند.
اين مقادير نامنفي هستند زيرا بنابراين ميباشد.
همانطور که در معادله (٦) نشان داده شده است ، تکنيک NMF، ماتريس Aبا ابعاد m×n را به دو ماتريس Wو Hتجزيه ميکند. ماتريس W، ماتريس ويژگي معنايي نامنفي 5(NSFM) و H، ماتريس متغير معنايي نامنفي 6(NSVM) در معادله فوق ميباشد. از تابع هدف استفاده شده است تا فاصله اقليدسي بين هر ستون A و تقريبش که A=WH است را به حداقل برساند همانطور که Lee و Seung در مقالاتشان پيشنهاد کردند .[6][7]
ُنرم فروبنيوس ٧ که بعنوان يک تابع هدف استفاده شده است [١١]، عبارتند از:
در اين عبارت، rمعمولا کوچکتر از mيا nانتخاب مي - شود، در اينصورت اندازه کلي Wو Hکمتر از ماتريس Aاست . معمولا مقدار rبصورت معادله (٨) تعيين مي -شود [٥]:
کران پايين عبارت (٣-٧) به صفر ميل ميکند و تنها اگر A=WH شد، به صفر ميرسد. Wو Hمدام بروز ميشوند تا (ΘE)W,H به مقدار آستانه از پيش تعريف شده، همگرا شود و يا از تعداد تکراري تجاوز کند. قوانين بروز رساني بصورت رابطه (٩) است :
A*j، يک بردار ستوني مطابق با جمله jام است که مي - تواند بعنوان ترکيب خطي بردارهاي ويژگي معنايي W*j و متغير معنايي Hlj نشان داده شود:
ج) توليد خلاصه
مرحله توليد خلاصه ، جملات را استخراج کرده و سپس رتبه بندي ميکند.
• استخراج جملات با استفاده از ويژگيهاي معنايي
فرآيند استخراج جملات به شرح زير است . با بکار بردن الگوريتم NMF،Cc به دو ماتريس Wc و Hc تجزيه مي - شود، بطوريکه معادله (١) برقرار باشد. سپس براي هر خوشه Cc مراحل زير را انجام ميدهيم :
٣- سپس جملات مطابق با را مجموعه جملات کانديد قرار ميدهيم .
٤- مراحل ١تا ٣را براي همه خوشه ها تکرار ميکنيم .
در مرحله ١، بردار ويژگي معنايي که بيشترين شباهت را با پرسوجوي qدارد، انتخاب ميکنيم . در مرحله ٢، ستون qام که بيشترين مقدار را در ميان رديف pام دارد، انتخاب ميکنيم . مرحله ٣، جملات انتخاب شده را در مجموعه جملات کانديد قرار ميدهد تا بعدا در مرحله رتبه بندي جملات مرتب شوند. در ضمن ، اين ٣مرحله براي همه خوشه ها انجام ميشود.
در اين مثال مراحل گفته شدهي بالا را با ٥جمله انجام ميدهيم . جدول ١، پنج جمله و يک پرسوجو را نشان ميدهد. توسط مرحله پيش پردازش ماتريس Aرا براي اين جدول تشکيل داده و توسط روش NMF ماتريس Aرا به دو ماتريس Wو Hتجزيه ميکنيم . در شکل ١، شباهت کسينوسي بين دو ماتريس query و Wنشان داده شده است .
