پایان نامه تقسيم بندي صفحات وب
مقدمه:
در اين فصل ما به بررسي ساختار مطلقاً پيچيدهاي كه در صفحات وب جاسازي شده است مي پردازيم و چگونگي استفاده از اطلاعات را در خلاصه سازي صفحات وب نشان مي دهيم . در اينجا هدف ما استخراج كردن مفاهيم مربوطهي بيشتر از صفحات وب و گذراندن آنها از يك الگوريتم تقسيم بندي متني استاندارد مي باشد .
بويژه ما به چهار شيوهي متفاوت اجراي خلاصه سازي صفحات وب رسيدگي مي نماييم روش اول مشابه تكنيك خلاصه سازي [1]Luhn مي باشد،که در بخش 2-1-1-1- توضیح داده شده است . روش دوم مشابه استفاده از تحليل معنايي نهفته روي صفحات وب براي خلاصه سازي مي باشد . روش سوم پيدا كردن مفاهيم مهم بدنه ي اصلي متن و تركيب اجزاي آن به منظور خلاصه سازي مي باشد و در آخر ، روش چهارم نگريستن به خلاصه سازي همانند يك امر يادگيري نظارت شده مي باشد .
ما نتايج هر چهار روش خلاصه سازي شده را با هم تركيب كرده و در خلاصه سازي صفحات وب مورد استفاده قرار مي دهيم .
2-1-1-1- روش خلاصه سازي تعديل شده Luhn
ما روش Luhn كه به منظور خلاصه سازي متون طراحي شده است را براي خلاصه سازي صفحات وب تغيير مي دهيم . روش Luhn يك شيوهي اصولي خلاصه سازي است كه در آن هر جمله با يك عامل با معني ارجاع داده شده است و جملات با بزرگ ترين عاملهاي با معني شان به منظور شكل دادن خلاصه انتخاب شده اند به منظور محاسبه ي عامل با معني يك جمله نيازمند ساختن يك ” منبع لغات با معني ” هستيم كه كلماتي را كه فرآواني آنها بين بيشترين حد فرآواني و كمترين حد فرآواني مي باشد را معين مي كند . پس از انجام دادن اين كار عامل با معني يك جمله مي تواند توسط روش Luhn همانند زير محاسبه شود :
(1) قرار دادن يك حد L براي فاصله بين هر دو كلمه با معني كه از نظر معني بهم مربوط مطرح شدهاند.
(2) پيدا كردن يك بخش از جمله كه مساوي با كلمات با معني نه بيشتر از L می باشد و از كلمات غير معني دار است.
(3) شمارش تعداد كلمات معني دار آن بخش و تقسيم عادلانهي اين تعداد توسط كل كلمات اين بخش .
نتيجه عامل با معني مربوط به S مي باشد .
به منظور تغيير دادن اين روال براي صفحات وب ما يك سري دستورات را براي الگوريتم Luhn مي سازيم . در امر تقسيم بندي صفحات وب ، دسته اطلاعات هر صفحه قبلاً در دادههاي آموزشي معلوم شده است ، بنابراين كلمات با معني انتخاب شده مي تواند بين هر دسته از قبل توليد شده باشد .
در اين روش ما براي هر دسته با انتخاب كردن كلمات با فرآواني زياد و پس از پاك كردن كلمات غير قابل استفاده در آن بخش يك منبع لغات بامعني ساختيم و سپس روش Luhn را به منظور محاسبه عامل با معني به كار گرفتيم.
اين تغيير دو مزيت دارد اول اينكه دانسته هاي قبلي بخش ها در خلاصه سازي مورد استفاده قرار مي گيرد و دوم اينكه برخي از لغاتي نسبتاً بطور مكرر دريك صفحهي مجزا تكرار مي شوند از ميان آمار پوشههاي متعدد پاك خواهند شد .
در طول خلاصه سازي صفحات وب در دورهي آموزشي شان با معني در جمله با توجه به معني لغات با معني مطابق بر چسب آن بخش محاسبه خواهد شد .
براي تست صفحات وب اطلاعات آن بخش را در دست نداريم در اينجا ما عاملهاي با معني را براي هر جمله با توجه به منابع لغات با معني متفاوت در سرتا سر بخشهاي مختلف محاسبه مي نماييم .
نشان با معني جملهي نهايي ميانگين همهي بخش ها خواهد بود و به Luhn S منسوب است . خلاصهي اين صفحه با جملاتي كه بالاترين نشان را دارند شكل خواهد گرفت .
2-1-1-2 – روش تحليل معنايي نهفته (LSA[2])
تحليل معنايي نهفته با موفقيت در بازيابي اطلاعات و بسياري از قلمروهاي مربوطه بكار رفته است و توانايي اين روش در ارائه كردن واحدها و اجزاي مربوط است كه به يك “فضاي خالي معنايي ” با ابعاد خيلي بزرگ اشاره مي كند . در حوزهي خلاصه سازي متني،روش گنگ[3] يكي از كارهايي است كه در متن هاي محض به روش LSA جواب داده است . در اين بخش ما چگونگي به كار بردن LSA را براي خلاصه سازي مرور خواهيم كرد .
روش تحليل معنايي نهفته مبني بر تجزيهي ارزش منفرد (SVD)[4] مي باشد .
SVD تكنيك تجزيهي ماتريس رياضي است كه قابل اجرا بر روي متون توسط انسان هاي كار آزموده و با تجربه است . به عنوان مثال ماتريس داده شده است كه هر بردار ستون نمايندهي بردار واحد فرآواني داراي وزن جملهي i در پوشهي تحت ملاحظه ميباشد ، روش SVD همانند زير تعريف ميشود :
- در اينجا كه يك ماتريس نرمال ستوني است كه ستونهاي آن بردارهاي منفرد طرف چپ ناميده مي شوند.
- ، يك ماتريس قطري n n است كه عناصر قطری غیر منفی آن با ارزش منفرد ، با ترتيب نزولي ذخيره شدهاند .
- يك ماتريس نرمال n n است كه ستونهاي آن بردارهاي منفرد طرف راست ناميده ميشوند ، روش LSA در خلاصه سازي به دو علت كاربرد پذير است:
ابتدا اينكه ، LSA قابل تعريف و مدلسازي در رابطهي متقابل بين واحدهاي طبقه بندي شده از نظر معنا وجملات مي باشد . دوم اينكه ، LSA مي تواند الگوي تركيبي كلمات برجسته و تكرار شوندهي متن را در پوشهاي كه يك موضوع خاص را توصيف مي كند بدست آورد. در روش LSA ، مفاهيم توسط يكي از بردارهاي منفردي كه مقدار متناظرشان نمايانگر اهميت درجهي آن الگو در يك پوشه مي باشد ، نشان داده ميشود. هر جمله اي شامل اين الگوي تركيبي لغات در اين بردار منفرد ارائه خواهد شد . هر جملهاي كه اين الگو را بهتر نمايش دهد ،بيشترين مقدار شاخص اين بردار را خواهد داشت اين شاخص را با نمايش مي دهيم . و جملات با بالاترين شاخص را براي خلاصه سازي انتخاب مي كنيم .
2-1-1-3- شناسايي مضمون بدنه اصلي توسط تجزيه و تحليل لايهاي
كاراكترهاي ساخت يافتهي صفحات وب ، خلاصه سازي صفحات وب را از خلاصه سازي متني محض متفاوت مي سازد . انجام اين كار روي اجزاء بسيار زياد يك صفحه وب مشكل است . همانند بلاك واسط كاربر، آگهي تبليغاتي و اطلاعات حق چاپ.
به منظور استفاده از اطلاعات ساخت يافتهي صفحات وب ما يك نسخه ساده شده از تابع مدل شيء[5] را بكار ميگيريم.
تابع مدل شيء تلاش مي كند تا منظور يك برنامه نويس كامپيوتر را با مشخص كردن تابع شيء و دستهي مربوط برساند . در تابع مدل شي ء اشياء به دستههاي شيء اصلي (BO) كه شامل كوچكترين اطلاعاتي است كه قابل تقسيم شدن نيستند يا شيء مركب ( CO) كه يك مجموعه از اشيايي هستند كه چندين تابع را با يكديگر اجرا مينمايد .
فايل ( pegj) يك مثال از شيء اصلي ميباشد . هيچ گونه برچسب ديگري درون محتواي شيء اصلي نمي باشد با توجه به این معيار پيدا كردن تمامي شيء هاي اصلي درون يك صفحه وب آسان است .
همچنان اشياء مركب مي توانند توسط تحليل لايهاي صفحات وب نمايان شوند . پس از يافتن تمامي اشياء اصلي و اشياء مركب در يك صفحه وب ما مي توانيم طبقهي هر شيء را با توجه به برخي قوانين اكتشافي تعيين كنيم . در اينجا ما يك نظر اجمالي بر مضامين طبقات اشياء مي اندازيم .
1- شيء اطلاعاتي : اين شيء اطلاعات مضامين را نمايش مي دهد .
2- شيء واسط كاربر: اين شيء راهنماييهاي واسط كاربر را در اختيار قرار مي دهد .
3- شيء عكس العمل : اين شيء عكس العمل جانب كاربر را مهيا مي نمايد .
4- شيء تزئيني : اين شيء براي اهداف تزئيني بكار مي رود .
5- شيء تابع خاص : اين شيء توابع خاص را اجرا مي كند .
به منظور استفاده از اين اشياء از انواع اشياء بالا ما بدنه اصلي مضمون[6] (CB) يك صفحهي وب را توضيح مي دهيم كه شامل اشياء اصلي مربوط به متن آن صفحه مي باشد. اين ها اشيايي هستند كه اطلاعات اصلي در مورد آن صفحه را حمل ميكنند. الگوريتم نمايش (CB) همانند زير است :
1- رسيدگي كردن به هر شيء انتخابي همانند يك پوشهي منفرد .
2- محاسبه شباهت بين هر دو شيء .
3- در يك گراف شيء هسته با بيشترين درجه مشخص شده است.
4- استخراج كردن (CB) با تركيب تمام اشيايي كه یالی به شيء هسته دارد .
در آخر ما يك امتياز را به هر جمله اختصاص مي دهيم . اگر 1= جمله شامل بدنهي اصلي مضمون مي باشد و در غير اين صورت 0= ، در انتها همهي جملات با 1= در خلاصه سازي صفحهي وب به كار گرفته ميشود .
2-1-1-4- خلاصه سازي نظارت شده
در اين بخش ما يك رويكرد نظارت شده را براي خلاصه سازي بكار مي گيريم كه بطور كامل از دادههاي آموزشي بر چسب دار استفاده مي كند و سپس يك الگوريتم يادگيري به منظور آموزش تلخيص كننده بكار گرفته ميشود تا تلخيص كننده بتواند شناسايي كند كه آيا يك جمله بايد براي خلاصهاش انتخاب شود يا خير . در مجموع هشت خصوصيت مورد استفاده در اين الگوريتم موجود مي باشد كه پنج تاي آنها خصوصيات متداول براي پوشه هاي متني و صفحات وب ميباشند و سه تاي باقيمانده مختص طراحي صفحات ميباشند .
برخي از علامت گذاريهادر زير توضيح داده شده اند :
PN: تعداد پاراگراف هاي يك پوشه
SN: تعداد جملات يك پوشه
: تعداد جملات يك پاراگراف خاص K
Para(i): پاراگراف مربوط به جمله ي i
: تعداد وقوع كلمهي w در يك صفحهي وب مشخص
: تعداد جملات شامل كلمهي W در b صفحه
به عنوان مثال اگر مجموعه جملات در يك صفحه داده شده باشداين هشت خصوصيت مانندزير است :
(1) = موقعيت يك جمله در يك پاراگراف خاص
(2)= طول يك جمله كه تعداد كلمات آن جمله را نشان مي دهد .
(3) اين خصوصيت به منظور استفاده و حذف كلمات محلي تكرار شونده بكار مي رود .
(4)= شباهت بين جملهي و عنوان ميباشد .
(5)= شباهت بين جمله و تمامي متن آن صفحه مي باشد.
(6)= شباهت بين جمله و دادههاي يك صفحه وب مي باشد .
(7)= تعداد وقوع كلمهاي از جملهي در مجموعه لغات خاص .
با جمع آوري لغات مايل ، پررنگ و زير خط دار واقع در صفحهي وب مجموعه لغات خاص ساخته ميشود.
(8)= ميانگين سايز فونت لغات در جمله است . بطور كل سايز فونت بزرگتر در يك صفحهي وب نشاندهندهي اهميت بيشتر مي باشد .
پس از اقتباس اين 8 خصوصيت از يك صفحهي وب ما از يك روش طبقه بندي براي آموزش دادن به يك تلخيص كننده استفاده مي نماييم :
در اينجا P(s/S) بر نرخ فشرده سازي و اختصار تلخيص كننده دلالت مي كند كه مي تواند براي كاربردهاي خاص از پيش تعيين شده باشد و احتمال هر خصوصيت I مي باشد و احتمال شرطي هر خصوصيت i است به هر جملهاي يك امتيازي مي تواند تعلق گيرد كه با نمايش داده ميشود.
2-1-1-5- يك دسته بندي كلي از خلاصه سازي
با تركيب كردن چهار روش ارائه شده در بخش هاي قبل ما يك صفحهي وب پيوندي به دست مي آوريم . بدين ترتيب با در اختيار داشتن يك صفحه وب مقدار امتيازات هر جمله را با چهار الگوریتم خلاصه سازي به طور جداگانه محاسبه مي نماييم . امتياز نهايي يك جمله مجموع اين چهار امتياز مي باشد :
جملات با بالاترين S براي خلاصه ي صفحات وب انتخاب خواهند شد .
2-1-2- آزمايشات
به منظور تست خلاصه سازي براي طبقه بندي صفحات وب چندين آزمايش انجام شده است . ابتدا ما طبقه بندي صفحات وب را بر روي خلاصهي توليد شده توسط انسان تست مي كنيم تا متوجه شويم كه آيا خلاصه سازي مي تواند به طبقه بندي صفحات وب كمك كند يا خير ما ” تلخيص كننده ي شناسايي بدنهي مضمون ” پيشنهاد شدهي خود را با دو الگوريتم سنتي مقايسه ميكنيم:
الگوريتم تعديل شدهي Luhn وروش هاي مبتني بر LSA . در انتها، يك دسته بندي كلي از خلاصه سازي ارزيابي شده است . ما در آزمايشاتمان همچنين تغييرات تنظيمات پارامترهاي متفاوت را براي حروف چيني بهترين خلاصه مطالعه مي نماييم .
2-1-2-1- مجموعه ی داده
در آزمايشاتمان ما تقريبا از دو ميليون صفحهي وب كه از شاخهي مراجعه به وب عبور ميكنند استفاده مي كنيم ( http://search.looksmart.com) به علت محدوديت پهناي باند شبكه ، ما تنها مي توانيم در حدود پانصد هزار صفحه وب را دانلود نماييم كه اين صفحات توسط ويرايشگران بشري توليد شدهاند . از آنجائيكه اجراي آزمايشات بر روي اين مجموعه عظيم اطلاعات يك امر زمان بر است ، ما به طور اتفاق از %30 صفحات براي اهداف آزمايشي مان نمونه برداري مي كنيم. مطلب استخراج شده شامل 153019 صفحه مي باشد كه به 64 بخش تقسيم شده است كه بزرگترين بخش شامل 17473 صفحه است ، در حاليكه كوچكترين بخش تنها شامل 52 صفحه مي باشد . جداول 2-1 و 2-2 تعداد صفحات بزرگترين سه بخش و كوچكترين 3 بخش را نشان مي دهند.
به منظور كاهش خطاي تخميني از هم جدا شدن داده ها از يك روال تصديقي براي اين آزمايش كمك گرفته ميشود.
جدول 2-1 سه بخش بزرگتر
نام بخش | مجموع | تمرین | آزمایش |
کتابخانه / اجتماع | ١٧٤٧٣ | ١٥٧٢٦ | ١٧٤٧ |
مسیر / مقصد | ١٣٣٢٤ | ١١٩٩٢ | ١٣٣٢ |
سرگرمی / شهرت | ١٠١١٢ | ٩١٠١ | ١٠١١ |
جدول 2-2 سه بخش كوچكتر
نام بخش | مجموع | تمرین | آزمایش |
ورزش ها / اخبار و امتیازات | ١٠٦ | ٩٦ | ١٠ |
مردم و چت / شخصی | ٧٤ | ٦٧ | ٧ |
مردم و چت / یافتن افراد | ٥٢ | ٤٧ | ٥ |
2-1-2-2- دسته كننده ها
از آنجائيكه مركز توجه اين بخش ميزان تاثير خلاصه سازي صفحات وب براي طبقه بندي مي باشد ما در آزمايشاتمان دو دسته كنندهي معروف را انتخاب ميكنيم يكي از آنها دسته كننده بيس ساده[7] است و ديگري ماشين بردار پشتيبان می باشد.
الف – دسته كنندهي بيس ساده ( NB):
دسته كنندهي بيس ساده يك الگوريتم طبقه بندي متني ساده ولي مؤثر مي باشد كه نيت و قصد آن استفاده از تركيب احتمالات كلمات و بخش ها به منظور برآورد احتمالات بخش هاي مربوط به يك پوشه مي باشد . اغلب پژوهشگران روش NB را با استفاده از قانون بيس بكار مي برند:
در اين جا ميتواند با شمارش تكرار هر بخش تعداد بخش ها ميباشد ، بر احتمال وقوع كلمهي در بخش دلالت مي كند و تعداد رخدادهاي كلمه در است و n تعداد كلمات در دادههاي آموزشي مي باشد .
ب – ماشين بردار پشتيبان (SVM)
ماشين بردار پشتيبان يك روش يادگيري بسيار قدرتمند مي باشد كه در شرايط تئوري يادگيري محاسباتي بنا نهاده شده و براي طبقه بندي متني باموفقيت به كار گرفته شده است . (SVM) با پيدا كردن يك سطح فوق العاده در فضاي وروديهاي ممكن عمل مي كند. سطح فوق العاده تلاش ميكند تا نمونههاي مثبت را از نمونههاي منفي با استفاده از ماكزيمم كردن فضاي بين نزديك ترين نمونه هاي مثبت و منفي با سطح فوق العاده جدا كند.
اين امر ، طبقه بندي را براي تست كردن دادههايي كه نزديك اما مشابه دادههاي آموزشي نمي باشند تصحيح مي كند .
بنابراين الگوريتم SMO بطور كارا و مؤثر براي مجموعههاي آموزشي عمل مي كند .
2-1-2-3- مقياس ارزيابي
ما مقياس هاي استانداردي را براي ارزيابي اجراي تقسيم بندي وب بكار مي بريم مثل فراخواني مقياس F1 . پارامتر اندازه گيري دقيق (P) مقدار واقعي اجزاي مثبت بخش مي باشد كه توسط سيستم برگردانده شده است و فراخواني (R) مقدار اجزاء مثبت پيش بيني شده از ميان تمام اجزاي حقيقي مثبت بخش ميباشد . بنابراين تابع F1 ميانگين دقت ميباشد و مطابق زير فراخواني ميشود.
[1].روشی که برای خلاصه سازی متون طراحی شده است.
[2] . LSA Latent semantic Analysis
[3] . Gong
[4] . SVD singular Value De composition
[5] . FOM : funcation object Model
[6] . CB: Content Body
[7] . naїve bayes text classi fication
نقد و بررسیها
هنوز بررسیای ثبت نشده است.