بخشی از مقاله
چکیده
با رشد روزافزون حجم اسناد اطلاعاتی، استفاده از روش مناسب طبقهبندی، امری ضروری جهت سازماندهی این اطلاعات، محسوب میشود. در این راستا، استفاده از الگوریتمهای تکاملی، دسترسی و بازیابی اطلاعات را بهبود بخشیده است. این روشها از سرعت همگرایی مطلوبی در تعیین جواب بهینه، برخوردار نیستند.
در این تحقیق قصد داریم، با استفاده از روش خوشهبندی، سرعت همگرایی و پیچیدگی روشهای تکاملی در طبقهبندی اسنادی که پیچیدگی و ابعاد بالایی دارند، بهبود بخشیم. خوشهبندی بهعنوان یکی از مراحل پیشپردازش دادههاست که پیش از طبقهبندی انجام میشود و باعث میشود که دادههای مشابه با یکدیگر در درون یک خوشه و دادههای متفاوت با یکدیگر در خوشههای مجزا قرار گیرند. نتایج نشان میدهند که الگوریتم پیشنهادی در مقایسه با الگوریتمهای موردبررسی، سرعت همگرایی و دقت را افزایش میدهد.
.1 مقدمه
با رشد روزافزون ارتباطات، حجم انبوهی از اطلاعات مختلف پیش روی کاربران قرار میگیرد. در چنین شرایطی، نیاز به ذخیرهسازی، سازماندهی و مدیریت حجم انبوه اطلاعات موردنیاز کاربران بیشازپیش ضرورت مییابد. وظیفه یک سیستم طبقهبندی، طراحی یک مدل استاندارد و مناسب جهت انسجام ساختاری و تسهیل بازیابی اطلاعات هست. طبقهبندی اسناد، تفکیک اسناد به گروههایمشابه است.
در هر گروه درجه نسبتاً بالایی از شباهت وجود دارد درحالیکه شباهت بین اسناد متعلق به طبقههای مختلف باید تا حد امکان کم باشد. بهطورکلی طبقهبندی را میتوان به دودسته تقسیم کرد: طبقهبندی نظارتشده - با مدل - و طبقهبندی نظارت نشده - بدون مدل یا خوشهبندی - .
در طبقهبندی نظارتشده، اسناد برچسب دار به دستههای از پیش تعیینشده گروهبندی میشوند. این روش طبقهبندی دارای مدل است. به این معنی که میتوان با توجه به نمونههای موجود، مدلی ساخت که بر اساس آن بتوان دادههای فاقد برچسب را در دستههای مربوط به خودشان قرارداد. در طبقهبندی نظارتنشده اسناد بدون برچسب بوده و بر اساس معیار فاصلهای که از هم دارند به درون خوشهها گروهبندی میشوند.
در این روش هیچ دستهای از قبل وجود ندارد و تمرکز بر رویدادههایی است که به هم شباهت دارند. با کشف این شباهتها میتوان رفتارها را شناسایی و بر مبنای شناخت بهتر، تصمیمگیری کرد. در طبقهبندی نظارتشده از معیار ارزیابی خارجی جهت بررسی نتایج بر اساس برچسب کلاس استفاده میشود. معیارهای خارجی بر پایه ساختارهای از قبل مشخصشده میباشند که اطلاعات پیشین از دادهها را منعکس میکنند. ازجمله این متغیرها F-measure است که بهصورت نسبت متغیرهای دقت و فراخوانی به دست میآید.
متغیر دقت بهصورت نسبت کلمات وابسته و بازیابی شده به کلمات بازیابی شده تعریف میشود. درواقع این متغیر درجه دقت نتایج تولیدشده توسط الگوریتم طبقهبندی را معین میکند. همچنین متغیر فراخوانی بهصورت نسبت کلمات وابسته و بازیابی شده به کلمات وابسته مشخص میشود که توانایی روش طبقهبندی برای تولید همه کلماتی که در یک گروه هستند را نشان میدهد. هرچقدر ناحیه مشترک بین دو متغیر دقت و فراخوانی بیشتر باشد مقدار متغیر F-measure بیشتر و درنتیجه دقت و سرعت روش طبقهبندی بیشتر خواهد بود.
طبقهبندی اسناد در طبقهبندی متون علمی، سازمانی و اداری مورداستفاده قرار میگیرد. همچنین مستندات حاصل از جمعآوری صفحات وب و نامههای الکترونیکی نیز میتوانند با استفاده از طبقهبندی، انسجام ساختاری بهتری داشته باشند. تاکنون تحقیقات بسیاری با استفاده از الگوریتمهای مختلف درزمینهی طبقهبندی اسناد انجامشده است.
در بخش اول این مقاله بهمرور کارهای انجامشده در این زمینه و بررسی نقاط ضعف و قوت آنها پرداخته خواهد شد. در بخش دوم، مروری بر الگوریتمهای تکاملی و مفاهیم آن، خواهیم داشت. در بخش سوم، روش پیشنهادی موردبررسی قرار خواهد گرفت. پیادهسازی آزمایشها، بحث و نتیجهگیری به ترتیب در بخش چهارم و پنجم، بیان خواهند شد.
.2 پیش زمینه علمی
این بخش به بررسی الگوریتمهای طبقهبندی نظارتشده میپردازد. خلاصهای از الگوریتمهای موردبررسی در جدول 1 نشان دادهشده است.
.3 الگوریتمهای تکاملی
الگوریتمهای تکاملی، الگوریتم هایی جهت جستجو هستند که در آنها عمل جستجو از چندین نقطه در فضای جواب، انجام میشود. مسائل زیادی وجود دارند که راهحلهای متعارف برای آنها چارهساز نیستند؛ زیرا یا تحلیلی برای آنها وجود ندارد، یا حل تحلیلی بسیار مشکلدارند و یا پیچیدگی متغیرها و پارامترهای بسیار، انبوهی از راهحلها و نه لزوماً جواب مسئله را پیش رو قرار میدهد که امکان ارزیابی تمام راهحلها وجود ندارد. الگوریتمهای تکاملی روشهای بر مبنای جستجوی تصادفیاند که از مدلسازی تکامل بیولوژیکی طبیعی الگوبرداری شدهاند.
آنها بر روی پاسخهای ممکنی کار میکنند که از ویژگی برتری برخوردار بوده و بقای نسل بیشتری دارند، لذا تخمین نزدیکتری از پاسخ بهینه به دست میدهند. الگوریتمهای تکاملی از مکانیزم-ها و عملیات ابتدایی برای حل مسئله استفاده میکنند و در طی یک سری از تکرارها به راهحل مناسب برای مسئله میرسند. این الگوریتمها غالباً از یک جمعیت حاوی راهحلهای تصادفی شروع میکنند و در طی هر مرحله تکرار سعی در بهتر کردن مجموعه راهحلها دارند. در آغاز کار، تعدادی از افراد جامعه بهصورت تصادفی حدس زدهشده، سپس تابع برازندگی برای هر یک از این افراد محاسبه و اولین نسل ایجاد خواهد شد. اگر هیچیک از معیارهای خاتمه بهینهسازی برقرار نباشد ایجاد نسل جدید آغاز خواهد شد.
افراد برحسب میزان شایستگیشان برای تولید فرزندان انتخاب میشوند. این افراد بهعنوان والدین محسوب میشوند و با پیوند فرزندان را تولید مینمایند. تمامی فرزندان با یک مقدار معینی از احتمال، یعنی همان جهش، تغییر ژنتیکی مییابند. سپس میزان شایستگی فرزندان توسط تابع برازندگی تعیین و در اجتماع، جایگزین والدین شده و نسل جدید را ایجاد مینمایند. این چرخه آنقدر تکرار میشود تا یکی از معیارهای پایان بهینهسازی کسب شود. در این مقاله از الگوریتم تکاملی BioHEL که جزئیات کامل آن در [7] آمده است،استفاده می شود.
در طول فرآیند یادگیری، مجموعه قوانین با تکرار یادگیری یک قانون در یکزمان و با استفاده از الگوریتم ژنتیک ایجاد میشود. پس از به دست آمدن هر قانون، مثالهای یادگیری که با این قانون پوشش دادهشدهاند از مجموعه یادگیری حذف میشوند.
درنتیجه الگوریتم ژنتیک در سایر نواحی به جستجو ادامه میدهد. فرآیند یادگیری زمانی متوقف خواهد شد که کلاس قانون بهدستآمده، کلاس اکثریت نمونههای یادگیری نباشد. در مجموعهی قوانین، یک قانون پیشفرض قرار دارد که اکثریت کلاسهای دامنه را پوشش میدهد. در صورت توقف جستجو، همه نمونههای باقیمانده به قانون پیشفرض نسبت داده میشوند. برای کاهش زمان اجرای سیستم، BioHEL از طرح پنجرهای یادگیری افزایشی با strata تناوبی استفاده میکند .[8] این روش، مجموعه یادگیری را به چند زیرمجموعه غیرهمپوشان تقسیم میکند و در هر تکرار، الگوریتم ژنتیک یک زیرمجموعه متفاوت برای محاسبه برازندگی افراد انتخاب میکند.
تابع برازندگی BioHEL مبتنی بر اصل [9] MDL است. اصل MDL ، معیاری جهت ارزیابی پیچیدگی و دقت است که از تراکم دادهها استفاده میکند. این تابع بهصورت زیر تعریف میشود:
Fitness=TL.W+EL
در این تابع، TL طول بیتهای تئوری - پیچیدگی راهحل - و EL طول بیتهای استثنا - دقت راهحل - را مشخص میکنند. استثناها شامل نمونههای اشتباه طبقهبندیشده یا طبقهبندی نشده هستند. همچنین متغیر W رابطه بین طول بیتهای تئوری و استثنا را مشخص میکند. اگر مقدار W بسیار زیاد باشد جمعیت به یک قانون گرایش پیداکرده و متلاشی خواهد شد. اگر W بسیار کوچک باشد تنوع جمعیت بسیار بالا خواهد شد. بنابراین انتخاب مقدار مناسب W، امری ضروری است.
