بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
دسته‌بندي صفحات وب
گروه کامپيوتر
چكيده
دسته‌بندي صفحات وب در بسياري از وظيفه‌هاي مديريتي در وب نقش ضروري‌اي دارد. طبيعت غبرقابل کنترل محتواي وب چالش‌هاي جديدي را براي اين دسته بندي ايجاد مي کند اما طبيعت متصل صفحات وب و همچنين حالت نيمه ساخت‌يافته آنها قابليتهايي را فراهم مي کند که به کمک اين دسته‌بندي مي‌آيد. امروزه توسعه زيادي در زمينه دسته‌بندي هوشمند صفحات صورت گرفته است بطوريکه بسياري از محققين تمرکز خود را بر روي اين قصيه قرار داده اند. در اين مقاله ما رويکردهاي دسته‌بندي صفحات وب را بررسي مي‌کنيم تا چشم انداز هاي جديدي را براي تحقيات بيابيم. همچنين در ابتدا برخي از کاربردهاي دسته‌بندي صفحات وب را بيان خواهيم نمود. همچنين خصوصيتها و الگوريتمهايي را که براي دسته‌بندي مفيد هستند توضيح خواهيم داد.
اسلاید 2 :
كلمات كليدي
دسته‌بندي صفحات وب، دسته‌کننده، درخت تصميم‌گيري، دسته‌کننده بيزي، ماشين بردار پشتيبان، خصوصيات درون صفحه، خصوصيات مجاورين، انتخاب قابليت
1- مقدمه
دسته‌بندي در بسياري از وظايف مديريت وبازيابي اطلاعات يک نقش حياتي ايفا مي کند. در وب دسته‌بندي محتوي صفحات وب براي تمرکز خزيدن[1]، کمک به توسعه راهنماهاي وب[2]، تحليل بر اساس موضوع[3] لينکهاي وب و براي تحليل ساختار موضوعي وب ضروري است. دسته‌بندي صفحات وب همچنين مي تواند به بهبود شرايط جستجوي وب نيز کمک نمايد[1].
دسته‌بندي صفحات وب که به گروه بندي صفحات وب نيز معروف است عبارتست از فرايند نسبت دادن يک صفحه وب به يک يا چند گروه از پيش تعيين شده. دسته‌بندي اغلب بعنوان يک مسئله يادگيري مطرح مي شود که در آن از يکسري داده هاي برچسب گذاري شده براي آموزش و تمرين دسته‌کننده استفاده مي شود تا بر اساس آن دسته‌کننده بتواند داده ها را برچسب گذاري کند.
اسلاید 3 :
2- کاربردهاي دسته‌بندي صفحات وب
2-1- ايجاد ، پشتيباني يا توسعه راهنماهاي وب
برخي از سايتها مانند Yahoo! و dmoz ODP يکسري راهنماي وب دارند که بر اساس آن مي توان يکسري جستجو در گروههاي از پيش تعيين شده انجام داد که در حال حاضر اين راهنماها توسط انسان ايجاد مي شوند. در جولاي 2006 در dmoz ODP، 73354 اديتور راهنما وجود داشت. با گسترش روزافزون صفحات وب ديدگاه سنتي به اين قضيه ديگر نمي تواند موثر باشد . اما با استفاده از دسته‌بندي صفحات وب مي توان اين راهنماها را براحتي ايجاد کرد و توسعه داد[1].
2-2- بهبود کيفيت نتايج جستجو
گنگ بودن پرس و جوها[1] يکي از مشکلات اساسي براي نتايج جستجو مي باشد. بعنوان مثال کلمه bank هم به معني ساحل و هم به معني بانک است. رويکردهاي مختلفي براي بازيابي اطلاعات در اينگونه موارد مطرح گرديده است. Chekuri و گروهش دسته‌بندي اتوماتيک صفحات وب به منظور افزايش دقت جستجو در وب را مورد مطالعه قرار دادند. به يک دسته‌کننده آماري با استفاده از يکسري صفحات موجود آموزش داده شد، سپس اين دسته‌کننده بر روي يکسري صفحات جديد بکار گرفته شد که يک ليست مرتب از گروهها را ايجاد کرد که صفحات وب مي توانند در آن قرار گيرند. در زمان پرس و جو[2] از کاربر خواسته مي شود تا يک يا چند گروه را انتخاب نمايد بطوريکه فقط اطلاعات مربوط به آن گروهها برگردانده مي شوند يا اينکه موتور جستجو فقط يک ليست از گروه‌هايي را نشان مي دهد که اطلاعات مورد نظر در آنها وجود دارد. اما اين رويکرد فقط زماني ثمربخش است که کاربر به دنبال يک چيز معلوم و مشخص بگردد.
اسلاید 4 :
نتايج جستجو معمولاً بر اساس رتبه بندي نمايش داده مي شوند. يک رويکرد ارائه شده توسط Chen and Damais نتايج جستجو را در يک ساختار سيسله مراتبي از پيش تعيين شده دسته‌بندي مي کند و نتايج گروهبندي شده را نشان مي دهد[4]. مطالعه کاربران آنها نشان مي‌دهد که نمايش گروهي براي کاربران خوشايندتر از نتايج ليست شده است و براي کاربران جهت يافتن اطلاعاتشان موثرتر است. در مقايسه با روش قبل اين روش در زمان پرس و جو اثر کمتري دارد زيرا گروه بندي صفحات در آن بصورت در جا[1] ايجاد مي شود. در هر حال لازم نيست که کاربر گروههاي مورد نظر خود براي جستجو را انتخاب نمايد بنابراين اين روش زماني که کاربر مورد جستجو را دقيقاً نمي‌شناسد بسيار سودمند است.
متشابهاً Kaki نيز نمايش گروهي را براي نتايج جستجوي کاربران پيشنهاد داده است. آزمايشات وي نشان مي دهد که نمايش گروهي براي کاربران بسيار مفيد است مخصوصاً زماني که رتبه بندي نتايج راضي کننده نيست[5].
Page and Brin الگوريتم رتبه بندي بر اساس لينک[2] را توسعه دادند که Pagerank ناميده شد. در اين روش ميزان معتبر بودن يک صفحه بر اساس يک گراف ايجاد شده از صفحات وب و لينکهايش و بدون در نظر گرفتن موضوع هر صفحه محاسبه مي شود . Haveliwala رتبه‌بندي بر اساس موضوع را ارائه کرد که باعث محاسبه رتبه بندي چندگانه مي شود بطوريکه رتبه بندي براي هر موضوع جداگانه خواهد بود . اين روش نياز به يکسري صفحات دارد که از قبل و با دقت دسته‌بندي شده باشند[1].
اسلاید 5 :
-3- کمک به سيستمهاي پاسخ به سوال[1]
يک سيستم پاسخ به سوال ممکن است تکنيکهاي دسته‌بندي را براي بهبود کيفيت پاسخهايش بکار ببرد.
يک سوال جالب که در نوشته هاي سابق پاسخ داده نشده اين است که چطور دسته‌بندي موضوعي صفحات وب در سيستمهاي پاسخ به سؤال مفيد است. در قسمت قبلي يک تعداد رويکرد در مورد استفاده از اطلاعات موضوعي صفحات وب برا ي بهبود کارايي جستجوي وب را ديديم. بطور مشابه توسط تعيين گروه مورد انتظار پاسخ يک سوال و دسته‌بندي صفحاتي وبي که ممکن است شامل يک پاسخ کانديد باشند، يک سيستم پاسخ يه سوال مي تواند در هر دو زمينه دقت و کارايي مفيد واقع شود[1].
2-4- کاربردهاي ديگر
در کنار کاربردهاي ذکر شده، دسته‌بندي صفحات وب در فيلترينگ محتواي وب، کمک به مرور وب و ساختمان بر پايه دانش نيز مي‌تواند مفيد واقع شود.
3- تکنيک هاي دسته‌بندي صفحات وب
همانطور که اشاره شد دسته‌بندي صفحات وب شامل نسبت دادن اسناد وب به يکي از چند گروه از پيش تعيين شده است. براي نايل شدن به اين هدف اسناد ورودي توسط يک مجموعه از مشخصات[2] که معمولاً خصوصيات[3] ناميده مي شود توصيف مي شوند. برخلاف خوشه‌بندي[4] اسناد وب که شامل آموزش بدون نظارت است، در دسته‌بندي يک مجموعه آموزشي از داده‌ها با برچسب‌گذاري قبلي نياز است (يادگيري ماشين نظارتي). هدف دسته‌بندي تحليل داده هاي ورودي و ايجاد يک مدل دقيق براي هر دسته با استفاده از اين خصوصيات است. اسناد جديد در داخل يکي از اين دسته ها دسته‌بندي مي شوند.
اسلاید 6 :
در مسأله دسته‌بندي متن، مشخصات کلماتي هستند که درون اسناد متني قرار دارند. انتخاب خصوصيت[1] در بسياري از موارد قبل از يادگيري ماشين صورت مي گيرد تا فضاي خصوصيات[2] را کاهش دهد.
عموماً ما بين دسته‌کننده هاي بر پايه قانون[3] (قوانين بصورت دستي ساخته مي شوند، و مجموعه حاصل از قوانين مکمل است که اصلاح شوند) و دسته‌کننده هاي با يادگيري استقرايي[4] تمايز قائل مي شويم. دسته‌کننده هاي بر پايه يادگيري استقرايي توسط داده هاي آموزشي برچسب گذاري شده ساخته مي شوند که براي ايجاد و به روزرساني سهل و آسان هستند و به مهارتهاي نوشتن قوانين[5] نياز ندارند[3].
اسلاید 7 :
-1- دسته‌کننده‌هاي درخت تصميم گيري[1]
دسته‌کننده درخت تصميم گيري يکي از پر استفاده ترين روشهاي يادگيري با نظارت است که براي کاوش[2] داده‌ها مورد استفاده قرار مي گيرد. اين دسته‌کننده براي تفسير آسان است و مي‌تواند بصورت قوانين if-then-else بازنمايي گردد. در اين دسته‌کننده تابعي توسط مناطق ثابت تکه هاي تقريب زده مي شود و به هيچ دانش قبلي از توزيع داده‌ها نياز ندارد. اين دسته‌کننده بر روي داده‌هاي پارازيت دار به خوبي کار مي کند. يک دسته‌کننده درخت تصميم گيري در اکتشاف داده ها به روش زير کمک مي کند:
- کاهش حجم زيادي از داده‌ها توسط تبديل آن به يک نوع فشرده تر که خصوصيات ذاتي و اساسي را حفظ مي کند و يک خلاصه دقيق را فراهم مي کند.
- کشف مي کند که آيا داده‌ها شامل دسته هاي به خوبي جدا شده[3] از اشيا هستند، بطوري که دسته ها بتوانند در متن يک تئوري حقيقي[4] بطور با معني تفسير شوند.
- داده ها را به شکل يک درخت نگاشت مي کند بطوريکه مقادير پيش بيني بتوانند عقب گرد از برگها به ريشه توليد شوند. که ممکن است پيش بيني نتايج براي يک داده يا پرس و جوي جديد استفاده شود.
اسلاید 8 :
الگوريتم‌هاي درخت تصميم‌گيري اصلي در دو گروه زير دسته‌بندي شده اند:
- دسته‌کننده‌ها از نوع يادگيري ماشين مانند ID3، C4.5وCART.
- دسته‌کننده‌ها براي پايگاه داده‌اي بزرگ مانند SLIQ، SPRINT، SONARوRainForest.
شکل (2) : درخت تصميم گيري براي ريسک رانندگي
يک دسته‌کننده درخت تصميم گيري با استفاده از يک آستانه معين بر روي مقادير ويژگيها يک مجموعه داده را بر اساس تصميمات گسسته جدا مي کند. يک گره ريشه در بالاي ساختار درخت وجود دارد که خصوصيت را مشخص مي کند که در ابتدا بر اساس بيشترين تفاوت(تبعيض) شکسته مي شود. گره هاي داخلي درخت قوانين تصميم گيري ساده اي را روي يک يا چند ويژگي نشان مي دهد، بطوريکه گره هاي برگ برچسب دسته هاي پيش بيني شده هستند. مثلا در شکل شماره (2) که ريسک در رانندگي را مشخص مي کند ابتدا درخت توسط خصوصيت سن تقسيم بندي شده است و سپس در مرحله بعد بر اساس نوع ماشين. همانطور که در شکل مي بينيد برگها دسته‌هاي تعيين شده بر اساس خصوصيات هستند.
اسلاید 9 :
فرايند ساخت درخت با يک درخت خالي شروع مي شود و سپس مجموعه آموزشي وارد مي شود و فرايند طبق روال زير پيش مي رود تا هيچ تقسيم ديگري در درخت ممکن نباشد:
.1اگر تمام نمونه هاي آموزشي در گره فعلي t به گروه Ci متعلق باشند يک گره برگ با دسته Ci بساز.
.2در غير اين صورت با استفاده از يک معيار مناسب به هر يک از مجموعه هاي تقسيم شونده S يک نمره بده.
.3بهترين تقسيم S* را بعنوان آزمايش در گره فعلي انتخاب کن.
.4فرزندان ايجاد شده بر اساس تقسيم S* را ايجاد کن و داده‌هاي آزمايشي را بر اساس S* به گره‌هاي فرزند تقسيم کن(افراز کن).
.5به يک فرزند پالايش شده[1] مي گويند اگر تمام نمونه‌هاي آموزشي در t متعلق به همان دسته باشند. مراحل قبل را براي هر يک از فرزندان پالايش نشده[2] تکرار کن.
اسلاید 10 :
ساخت درخت مي‌تواند توسط ماکزيمم ساختن اطلاعات متقابل[1] عمومي از کل درخت، يا توسط بهينه سازي محلي بهره اطلاعات[2] انجام گيرد. گاهي اوقات معيارهاي فاصله اي مثل شاخص جيني[3] تنوع نيز استفاده مي شود. هم بهينه‌سازي محلي بهره اطلاعات و هم معيار تقسيم بندي بر اساس فاصله درختهاي کوچک، کم عمق و دقيق توليد مي کنند.
به منظور جداسازي در يک گره الگوريتم بصورت زير پيش مي رود:
- يک ويژگي را که بهترين نمونه جداسازي از کلاسهاي مختلف است را بر مي دارد.
کمي کردن فاکتور شهودي براي اندازه گيري جداپذيري. يک I(S) پالايش نشده از يک مجموعه قراردادي S شامل دسته را مشخص مي کند، که مي تواند بصورت زير باشد:
اطلاعات بي نظمي بصورت زير سنجيده مي‌شود:Entropy(S)=
Entropy(S)= (1)
بطوريکه Pi فراواني نسبي دسته i در S است(يک احتمال قياسي) که مقدار آن وقتي همه الگوها فقط متعلق به يک دسته باشند صفر است و مقدرا آن زماني که همه دسته‌ها به تعداد برابري هستند يک است.
نشانه گذاري جيني که بصورت زير بيان مي‌شود:
Gini(S) = 1 - (2)
محاسبه بهره اطلاعات در تقسيم S به r زير مجموعه. اين بعنوان ناخالصي S کمترين مجموع ناخالصي وزن دار هر زير مجموعه شمرده مي شود. براي مثال:
Gain(S,S1,…,Sr) = I(S) -
