دانلود با لینک مستقیم و پر سرعت .
دسته‌بندی صفحات وب
دسته‌بندی صفحات وب در بسیاری از وظیفه‌های مدیریتی در وب نقش ضروری‌ای دارد. طبیعت غبرقابل کنترل محتوای وب چالش‌های جدیدی را برای این دسته بندی ایجاد می کند اما طبیعت متصل صفحات وب و همچنین حالت نیمه ساخت‌یافته آنها قابلیتهایی را فراهم می کند که به کمک این دسته‌بندی می‌آید. امروزه توسعه زیادی در زمینه دسته‌بندی هوشمند صفحات صورت گرفته است بطوریکه بسیاری از محققین تمرکز خود را بر روی این قصیه قرار داده اند. در این مقاله ما رویکردهای دسته‌بندی صفحات وب را بررسی می‌کنیم تا چشم انداز های جدیدی را برای تحقیات بیابیم. همچنین در ابتدا برخی از کاربردهای دسته‌بندی صفحات وب را بیان خواهیم نمود. همچنین خصوصیتها و الگوریتمهایی را که برای دسته‌بندی مفید هستند توضیح خواهیم داد.
کلمات کلیدی
دسته‌بندی صفحات وب، دسته‌کننده، درخت تصمیم‌گیری، دسته‌کننده بیزی، ماشین بردار پشتیبان، خصوصیات درون صفحه، خصوصیات مجاورین، انتخاب قابلیت
دسته‌بندی در بسیاری از وظایف مدیریت وبازیابی اطلاعات یک نقش حیاتی ایفا می کند. در وب دسته‌بندی محتوی صفحات وب برای تمرکز خزیدن[1]، کمک به توسعه راهنماهای وب[2]، تحلیل بر اساس موضوع[3] لینکهای وب و برای تحلیل ساختار موضوعی وب ضروری است. دسته‌بندی صفحات وب همچنین می تواند به بهبود شرایط جستجوی وب نیز کمک نماید[1].
دسته‌بندی صفحات وب که به گروه بندی صفحات وب نیز معروف است عبارتست از فرایند نسبت دادن یک صفحه وب به یک یا چند گروه از پیش تعیین شده. دسته‌بندی اغلب بعنوان یک مسئله یادگیری مطرح می شود که در آن از یکسری داده های برچسب گذاری شده برای آموزش و تمرین دسته‌کننده استفاده می شود تا بر اساس آن دسته‌کننده بتواند داده ها را برچسب گذاری کند.
2- کاربردهای دسته‌بندی صفحات وب
2-1- ایجاد ، پشتیبانی یا توسعه راهنماهای وب
برخی از سایتها مانند Yahoo! و dmoz ODP یکسری راهنمای وب دارند که بر اساس آن می توان یکسری جستجو در گروههای از پیش تعیین شده انجام داد که در حال حاضر این راهنماها توسط انسان ایجاد می شوند. در جولای 2006 در dmoz ODP، 73354 ادیتور راهنما وجود داشت. با گسترش روزافزون صفحات وب دیدگاه سنتی به این قضیه دیگر نمی تواند موثر باشد . اما با استفاده از دسته‌بندی صفحات وب می توان این راهنماها را براحتی ایجاد کرد و توسعه داد[1].
2-2- بهبود کیفیت نتایج جستجو
گنگ بودن پرس و جوها[1] یکی از مشکلات اساسی برای نتایج جستجو می باشد. بعنوان مثال کلمه bank هم به معنی ساحل و هم به معنی بانک است. رویکردهای مختلفی برای بازیابی اطلاعات در اینگونه موارد مطرح گردیده است. Chekuri و گروهش دسته‌بندی اتوماتیک صفحات وب به منظور افزایش دقت جستجو در وب را مورد مطالعه قرار دادند. به یک دسته‌کننده آماری با استفاده از یکسری صفحات موجود آموزش داده شد، سپس این دسته‌کننده بر روی یکسری صفحات جدید بکار گرفته شد که یک لیست مرتب از گروهها را ایجاد کرد که صفحات وب می توانند در آن قرار گیرند. در زمان پرس و جو[2] از کاربر خواسته می شود تا یک یا چند گروه را انتخاب نماید بطوریکه فقط اطلاعات مربوط به آن گروهها برگردانده می شوند یا اینکه موتور جستجو فقط یک لیست از گروه‌هایی را نشان می دهد که اطلاعات مورد نظر در آنها وجود دارد. اما این رویکرد فقط زمانی ثمربخش است که کاربر به دنبال یک چیز معلوم و مشخص بگردد
نتایج جستجو معمولاً بر اساس رتبه بندی نمایش داده می شوند. یک رویکرد ارائه شده توسط Chen and Damais نتایج جستجو را در یک ساختار سیسله مراتبی از پیش تعیین شده دسته‌بندی می کند و نتایج گروهبندی شده را نشان می دهد[4]. مطالعه کاربران آنها نشان میدهد که نمایش گروهی برای کاربران خوشایندتر از نتایج لیست شده است و برای کاربران جهت یافتن اطلاعاتشان موثرتر است. در مقایسه با روش قبل این روش در زمان پرس و جو اثر کمتری دارد زیرا گروه بندی صفحات در آن بصورت در جا[1] ایجاد می شود. در هر حال لازم نیست که کاربر گروههای مورد نظر خود برای جستجو را انتخاب نماید بنابراین این روش زمانی که کاربر مورد جستجو را دقیقاً نمی‌شناسد بسیار سودمند است.
متشابهاً Kaki نیز نمایش گروهی را برای نتایج جستجوی کاربران پیشنهاد داده است. آزمایشات وی نشان می دهد که نمایش گروهی برای کاربران بسیار مفید است مخصوصاً زمانی که رتبه بندی نتایج راضی کننده نیست[5].
Page and Brin الگوریتم رتبه بندی بر اساس لینک[2] را توسعه دادند که Pagerank نامیده شد. در این روش میزان معتبر بودن یک صفحه بر اساس یک گراف ایجاد شده از صفحات وب و لینکهایش و بدون در نظر گرفتن موضوع هر صفحه محاسبه می شود . Haveliwala رتبه‌بندی بر اساس موضوع را ارائه کرد که باعث محاسبه رتبه بندی چندگانه می شود بطوریکه رتبه بندی برای هر موضوع جداگانه خواهد بود . این روش نیاز به یکسری صفحات دارد که از قبل و با دقت دسته‌بندی شده باشند[1].
-3- کمک به سیستمهای پاسخ به سوال[1]
یک سیستم پاسخ به سوال ممکن است تکنیکهای دسته‌بندی را برای بهبود کیفیت پاسخهایش بکار ببرد.
یک سوال جالب که در نوشته های سابق پاسخ داده نشده این است که چطور دسته‌بندی موضوعی صفحات وب در سیستمهای پاسخ به سؤال مفید است. در قسمت قبلی یک تعداد رویکرد در مورد استفاده از اطلاعات موضوعی صفحات وب برا ی بهبود کارایی جستجوی وب را دیدیم. بطور مشابه توسط تعیین گروه مورد انتظار پاسخ یک سوال و دسته‌بندی صفحاتی وبی که ممکن است شامل یک پاسخ کاندید باشند، یک سیستم پاسخ یه سوال می تواند در هر دو زمینه دقت و کارایی مفید واقع شود[1].
2-4- کاربردهای دیگر
در کنار کاربردهای ذکر شده، دسته‌بندی صفحات وب در فیلترینگ محتوای وب، کمک به مرور وب و ساختمان بر پایه دانش نیز می‌تواند مفید واقع شود.
3- تکنیک های دسته‌بندی صفحات وب
همانطور که اشاره شد دسته‌بندی صفحات وب شامل نسبت دادن اسناد وب به یکی از چند گروه از پیش تعیین شده است. برای نایل شدن به این هدف اسناد ورودی توسط یک مجموعه از مشخصات[2] که معمولاً خصوصیات[3] نامیده می شود توصیف می شوند. برخلاف خوشه‌بندی[4] اسناد وب که شامل آموزش بدون نظارت است، در دسته‌بندی یک مجموعه آموزشی از داده‌ها با برچسب‌گذاری قبلی نیاز است (یادگیری ماشین نظارتی). هدف دسته‌بندی تحلیل داده های ورودی و ایجاد یک مدل دقیق برای هر دسته با استفاده از این خصوصیات است. اسناد جدید در داخل یکی از این دسته ها دسته‌بندی می شوند.
در مسأله دسته‌بندی متن، مشخصات کلماتی هستند که درون اسناد متنی قرار دارند. انتخاب خصوصیت[1] در بسیاری از موارد قبل از یادگیری ماشین صورت می گیرد تا فضای خصوصیات[2] را کاهش دهد.
عموماً ما بین دسته‌کننده های بر پایه قانون[3] (قوانین بصورت دستی ساخته می شوند، و مجموعه حاصل از قوانین مکمل است که اصلاح شوند) و دسته‌کننده های با یادگیری استقرایی[4] تمایز قائل می شویم. دسته‌کننده های بر پایه یادگیری استقرایی توسط داده های آموزشی برچسب گذاری شده ساخته می شوند که برای ایجاد و به روزرسانی سهل و آسان هستند و به مهارتهای نوشتن قوانین[5] نیاز ندارند[3].
-1- دسته‌کننده‌های درخت تصمیم گیری[1]
دسته‌کننده درخت تصمیم گیری یکی از پر استفاده ترین روشهای یادگیری با نظارت است که برای کاوش[2] داده‌ها مورد استفاده قرار می گیرد. این دسته‌کننده برای تفسیر آسان است و می‌تواند بصورت قوانین if-then-else بازنمایی گردد. در این دسته‌کننده تابعی توسط مناطق ثابت تکه های تقریب زده می شود و به هیچ دانش قبلی از توزیع داده‌ها نیاز ندارد. این دسته‌کننده بر روی داده‌های پارازیت دار به خوبی کار می کند. یک دسته‌کننده درخت تصمیم گیری در اکتشاف داده ها به روش زیر کمک می کند:
•کاهش حجم زیادی از داده‌ها توسط تبدیل آن به یک نوع فشرده تر که خصوصیات ذاتی و اساسی را حفظ می کند و یک خلاصه دقیق را فراهم می کند.
•کشف می کند که آیا داده‌ها شامل دسته های به خوبی جدا شده[3] از اشیا هستند، بطوری که دسته ها بتوانند در متن یک تئوری حقیقی[4] بطور با معنی تفسیر شوند.
•داده ها را به شکل یک درخت نگاشت می کند بطوریکه مقادیر پیش بینی بتوانند عقب گرد از برگها به ریشه تولید شوند. که ممکن است پیش بینی نتایج برای یک داده یا پرس و جوی جدید استفاده شود.
الگوریتمهای درخت تصمیم‌گیری اصلی در دو گروه زیر دسته‌بندی شده اند:
•دسته‌کننده‌ها از نوع یادگیری ماشین مانند ID3، C4.5وCART.
•دسته‌کننده‌ها برای پایگاه داده‌ای بزرگ مانند SLIQ، SPRINT، SONARوRainForest.
شکل (2) : درخت تصمیم گیری برای ریسک رانندگی
یک دسته‌کننده درخت تصمیم گیری با استفاده از یک آستانه معین بر روی مقادیر ویژگیها یک مجموعه داده را بر اساس تصمیمات گسسته جدا می کند. یک گره ریشه در بالای ساختار درخت وجود دارد که خصوصیت را مشخص می کند که در ابتدا بر اساس بیشترین تفاوت(تبعیض) شکسته می شود. گره های داخلی درخت قوانین تصمیم گیری ساده ای را روی یک یا چند ویژگی نشان می دهد، بطوریکه گره های برگ برچسب دسته های پیش بینی شده هستند. مثلا در شکل شماره (2) که ریسک در رانندگی را مشخص می کند ابتدا درخت توسط خصوصیت سن تقسیم بندی شده است و سپس در مرحله بعد بر اساس نوع ماشین. همانطور که در شکل می بینید برگها دسته‌های تعیین شده بر اساس خصوصیات هستند.
فرایند ساخت درخت با یک درخت خالی شروع می شود و سپس مجموعه آموزشی وارد می شود و فرایند طبق روال زیر پیش می رود تا هیچ تقسیم دیگری در درخت ممکن نباشد:
.1اگر تمام نمونه های آموزشی در گره فعلی t به گروه Ci متعلق باشند یک گره برگ با دسته Ci بساز.
.2در غیر این صورت با استفاده از یک معیار مناسب به هر یک از مجموعه های تقسیم شونده S یک نمره بده.
.3بهترین تقسیم S* را بعنوان آزمایش در گره فعلی انتخاب کن.
.4فرزندان ایجاد شده بر اساس تقسیم S* را ایجاد کن و داده‌های آزمایشی را بر اساس S* به گره‌های فرزند تقسیم کن(افراز کن).
.5به یک فرزند پالایش شده[1] می گویند اگر تمام نمونه‌های آموزشی در t متعلق به همان دسته باشند. مراحل قبل را برای هر یک از فرزندان پالایش نشده[2] تکرار کن.
ساخت درخت می‌تواند توسط ماکزیمم ساختن اطلاعات متقابل[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) -
بطوریکه |S| کاردینالیتی S و I(S) فاکتور شهودی مشخص شده بعنوان هر Entropy(S) یا Gini(S).
•ویژگیهایی که بیشترین بهره اطلاعاتی را فراهم می کنند برای تقسیم بندی گره استفاده می شوند. بهر حال اول لازم است که تمام نقاط جداسازی ممکن برای هر ویژگی محاسبه شود[2].
ID3
یک رویکرد نظری اطلاعاتی را بکار می برد. روند کار به این صورت است که در هر نقطه خصوصیتی را که بیشترین بهره اطلاعاتی یا بطور معادل بزرگترین کاهش در بی نظمی را دارد مورد آزمایش قرار می‌گیرد.
بطوریکه مجموع تعداد الگوهای برچسب دار است.
.1انتخاب خصوصیتی که منجربه حداکثر کاهش در بی نظمی یا بهره اطلاعاتی بر اساس معادله (3) می‌شود، برای استفاده بعنوان گره ریشه در درخت تصمیم گیری.
.2ایجاد سطح بعدی از درخت تصمیم‌گیری با فراهم کردن بیشترین کاهش در بی نظمی.
.3تکرار مرحله 1 تا 3. روند را ادامه دهید تا تمام زیر‌جمعیتهایی که از یک کلاس واحد هستند بهمراه بی‌نظمی سیستم صفر شود.
در این مرحله هر جایی که الگوها از یک دسته واحد باشند یک مجموعه از گره های برگ(زیر جمعیت) از درخت تصمیم‌گیری بدست می آید. توجه کنید که آنجا می تواند تعدادی گره باشد که نمی تواند بیشتر از این در مورد آنها تصمیم گیری گردد[2].
را فراهم کند برای شکستن گره انتخاب می شود.(2)
SPRINT 1
SPRINT یک دسته‌کننده درخت تصمیم گیری برای داده کاوی است که قادر است تا با مجموعه‌های آموزشی بزرگ بر روی دیسک کار کند بدون محدودیت بر روی اندازه مجموعه آموزشی، و به آسانی قابل موازی سازی است. برای هر ویژگی در مجموعه داده ها یک لیست نگهداری می شود. ورودیها در یک لیست ویژگی شامل مقادیر ویژگی، مقادیر دسته و شناسه رکورد(RID) است. الگوریتم این دسته‌کننده یک درخت درهم[2] مناسب با اندازه مجموعه آموزشی استفاده می‌کند تا RIDها را ذخیره کند.
روش کار: روش کار بصورت زیر خلاصه شده است:
•هر گره از دسته‌کننده درخت تصمیم‌گیری نیاز دارد تا بطور کارا تمام شکست‌های آن روی هر مقدار از هر ویژگی آن آزمایش گردد.
•بعد از انتخاب یک ویژگی برای تقسیم، نیاز است تا تمام داده‌ها درون زیرمجموعه بخش‌بندی شوند.
•مادامی که تقسیم روی ویژگی های عددی ارزیابی شود، داده ها بر اساس مقدار ویژگی مرتب شده و بصورت افزایشی شاخص گذاری جینی محاسبه می گردد.
•مادامی که تقسیم روی ویژگی های قطعی(بی شرط) صورت گیرد، شاخص گذاری جینی برای هر زیر مجموعه یافت می‌شود و بهترین انتخاب می گردد. برای مجموعه داده‌های بزرگ یک روش حریصانه به کار می رود[2]
جنگل بارانی[1]
مطالعات نشان می دهد الگوریتمی که بطور یکنواخت در سراسر مجموعه داده ها دارای دقت باشد وجود ندارد. از اینرو چارچوب عمومی متحد جنگل بارانی برای ایجاد درخت دسته‌بندی گسترش پیدا کرد که منجر به ایجاد نسخه مقیاس پذیری از یک بازه وسیعی از الگوریتمهای دسته‌کننده که با عرضه نمودن بهبود کارایی بالا، سریعترین الگوریتم دسته‌بندی مقیاس پذیر موجود گردید. بر خلاف SPRINT جنگل بارانی به یک حجم کمینه معین از حافظه اصلی متناسب با مجموعه مقادیر مجزا در یک ستون از رابطه های ورودی نیاز دارد. این الگوریتم عمومی می تواند به منظور فراهم کردن نسخه های مقیاس پذیر بیشتر دسته‌بندی‌ها و الگوریتمهای موجود ساخت درخت رگرسیون در نوشته‌ها خاص گردد[2].
استخراج[2] قوانین دسته‌بندی از روی درختها
دانش رمز شده[3] توسط درختهای تصمیم‌گیری می‌تواند بصورت قوانین if-then استخراج گردد. برای هر مسیر از ریشه به سمت برگ یک قانون ساخته می شود و با جفت شدن هر مقدار ویژگی در طول یک مسیر یک ترکیب عطفی ایجاد می شود. گره برگ دسته پیش‌بینی شده را نگهداری می‌کند. درک قوانین برای انسان آسانتر است و سودمندی این قوانین در بهبود قابلیت فهم و قوانین بعدی(متعاقب) به منظور بهتر شدن تعامل انسان و ماشین نمی تواند نادیده گرفته شود.
دسته‌کننده بیزی نامقید[1]
برخلاف دسته‌کننده بیز ساده در این مورد فرض مستقل بودن کلمات در نظر گرفته نمی شود. این نوع یک نوع مشتق شده بصورت دسته‌کننده بیزی نیمه ساده است که متناوباً یک جفت از ویژگیها را بهم متصل می کند تا فرضیات مستقل قوی را کاهش دهد. پیاده سازی آن ساده است و نتایج آن نیز براحتی قابل تفسیرند. از طرف دیگر بخاطر فرض استقلال شروط کلمات محاسبات آن پیچیدگی نمایی دارد[3].
یادگیرنده‌های برپایه نمونه
قوانین نزدیکترین مجاور بر پایه مفهوم کمترین فاصله دسته‌ها از نمونه‌هاست و می‌تواند هر یک از یک نمونه اولیه یا چندین نمونه اولیه را درگیر کند. وقتی الگوی یک کلاس به یک قالب محکم مربوط به یک الگوی معرف نوعی برای تمام دسته ها تمایل داشته باشد، ما یک نمونه اولیه تکی از آنها را استفاده می کنیم تا کمترین فاصله را محاسبه کنیم. اجازه دهید نمونه اولیه برای دسته‌های باشد، بطوریکه فاصله بین نمونه‌ی قراردادی بردار و امین نمونه اولیه داده شده توسط بیان می‌شود.
وقتی یک اندازه گیری غیر اقلیدسی شبیه فاصله Mahalanobis استفاده شود، مشابه دسته‌کننده کمترین فاصله دسته‌کننده Mahalanobis نامیده می شود. داریم:
INSTANCE-BASED LEARNERS typical representative
دسته‌کننده های فاصله کمینه
در این گروه از قوانین تصمیم‌گیری، فرضیه‌سازی از یک توزیع احتمال صورت نمی گیرد. دسته‌کننده فاصله کمینه، فاصله یک نمونه را از الگوی اولیه هر دسته محاسبه می کند و نمونه را به دسته ای که نزدیکتر از بقیه است نسبت می دهد. Minimum distance classifiers
شامل29 اسلایدPOWERPOINT
