بخشی از مقاله
چکیده
در این تحقیق برنامه نویسی ﮊنتیک بعنوان یک مکانیزم توسعه پرسش مورد استفاده قـرار گرفتـه اسـت. بـا اسـتفاده از یـک مجموعـه از پرسشها و سندهای مرتبط و غیرمرتبط بازیابی شده برای هر کدام, برنامه نویسی ﮊنتیک سعی در تکامل یک معیار (فرمول) جهت انتخاب ترمهایی دارد که با آن بتوان به نحو موثر پرسش کاربر را بسط داد. سه مجموعه استاندارد Lisa، Cranfield و Medline در طی دو مرحلـه جهت ارزیابی این روش مورد استفاده قرار گرفته است: ۱) برنامه نویسی ﮊنتیـک بـا اسـتفاده از یـک زیـر مجموعـه از پرسشـهای یکـی از مجموعه اسناد تکامل یافته و با پرسشهای جدید از همان مجموعه اسناد فوق مورد ارزیابی قرار مـی گیـرد. ۲) برنامـه نویسـی ﮊنتیـک بـا استفاده از پرسش های یکی از مجموعه اسناد فوق تکامل یافته و با مجموعه دوم مورد ارزیابی قرار می گیرد. روش RF١ احتمالی به عنوان یک روش پایه در این زمینه انتخاب و کارایی الگوریتم پیشنهادی با این روش مقایسه شده است. نتایج حاکی از برتر بـودن روش فـوق در تمامی آزمایشها می باشد.
کلمات کلیدی: سیستم های بازیابی اطلاعات, وزن دهی, توسعه پرسش, برنامه نویسی ﮊنتیک
۱- مقدمه
میزان اطلاعات الکترونیکی در طی دهه اخیر رشد چشمگیری داشته است. رشد سریع اطلاعات و حجـم زیـاد آن، پیـدا کـردن اطلاعـات مربوط را به مشکلی اساسی برای کاربران تبدیل کرده است. در سالهای اخیر, تحقیقات زیادی در مورد اسـتفاده از روشـهای هوشـمند بـه منظور بهبود کارایی سیستم های بازیابی اطلاعات انجام شده است. یک روش استفاده شده که کارایی سیستم های بازیابی اطلاعات را بـه میزان زیادی افزایش می دهد, روش RF یا استفاده از بازخوردکاربراست.
مکانیزمRF درسیستم های بازیابی اطلاعات از قضاوت کاربر بر روی سندهای بازیابی شده برای ایجاد یک پرسش جدید استفاده می کند.
الگوریتمهای RF توزیع ترمها بر روی سندهای مرتبط, نامرتبط و نیز کل مجموعه را برای تغییر پرسش موجود بکـار مـی برنـد. روشـهای مختلفی برای RF پیشنهاد شده است. این مقاله الگوریتم جدیدی براساس برنامه نویسی ﮊنتیک برای RF پیشنهاد می کند. نحوه کار بدین صورت است که ترمهایی از سندهای مرتبط براساس اطلاعات گرفته شده از کاربر و نیز اطلاعات آماری بدست آمده از توزیع این ترمها بـر روی سندهای مرتبط و نامرتبط بازیابی شده و نیز کل سندهای مجموعه انتخاب شده و به پرسش اولیه اضافه می شوند.
precision-recall
این مقاله از قسمتهای زیر تشکیل شده است: در قسمت بعد به معرفی سیستم های بازیابی اطلاعات مـی پـردازیم. سـپس مفهـوم RF و
روشهای مختلف آن در قسمت سوم بررسی می شود. در قسمت چهارم برنامه نویسی ﮊنتیک و کاربرد آن در بازیابی اطلاعات تشـریح مـی شود. در قسمت پنجم روش پیشنهادی برای توسعه پرسش براساس برنامه نویسی ﮊنتیک آورده می شـود. در قسـمت ششـم و هفـتم بـه ترتیب شرح آزمایشات و نتایج آنها آورده شده است.
۲- سیستم های بازیابی اطلاعات
یک سیستم بازیابی اطلاعات شامل مجموعه ای از اسناد می باشد که کاربران جهت دسترسی به اطلاعات مورد نیاز خود, پرسشهایی را به زبان طبیعی به سیستم وارد می کنند. بطور کلی یک زیر مجموعه از اسناد در پاسخ به پرسش کاربر توسط سیستم بازیابی و به او ارائه می شود. این مجموعه، معمولا شامل اسناد مرتبط با پرسش و هم شامل اسناد غیر مرتبط می باشد.
قبل از اعمال پرسش کاربر به سیستم, سندها مورد پردازش قرار گرفته و کلماتی که در بازیابی نقـش مـوثری ندارنـد و معمـولا در همـه سندها ظاهر می شوند، حذف می شوند(.(Stopwords در زبان انگلیسی لیستی از این کلمات تهیه شده اسـت و عمـل پـیش پـردازش بـا استفاده از این لیست انجام می شود.
در مرحله بعد, هر کلمه به ریشه آن تبدیل می شود(.(Stemming ایده کلی ریشه یابی این است که کلمات مختلف از یک خانواده (ریشه)
دارای مفهوم یکسان می باشند و بنابراین تبدیل هر کلمه به ریشه آن منجربه کاهش تعداد ترمهای شاخص هر سند می شود و چون عمل ریشه یابی به پرسش کاربر هم اعمال می شود، می تواند باعث افزایش کارایی بازیابی اطلاعات شود. عمل ریشه یابی اسـناد بصـورت غیـر بلادرنگ (قبل از اعمال پرسش کاربر به سیستم) و این عمل بر روی پرسشها بصورت بلادرنگ انجام می شود.
پس از اینکه ترمهای شاخص هر سند مشخص شد، عمل وزن دهی به هر ترم در هر سند انجام می شود. مکانیزمهـای زیـادی جهـت وزن دهی معرفی شده است .[1] یک روش مشهور جهت وزن دهی, روش Tf-Idf است و براین پایه می باشد کـه ترمهـایی کـه در یـک سـند خاص زیاد اتفاق افتاده و در بقیه اسناد مجموعه کمتر اتفاق افتاده اند, وزن بیشتری می گیرند.
در گذشته مدلهای مختلفی برای سیستم های بازیابی اطلاعات معرفی شده است. یک مدل متداول در این زمینه مدل فضای برداری مـی باشد. نظر به اینکه این مقاله از این مدل جهت نمایش و بازیابی استفاده می کند, خصوصیات این مدل بـه اختصـار در ادامـه آورده شـده است. در این مدل, سند و پرسش بصورت یک بردار در فضای n بعدی نمایش داده می شوند کـه n تعـداد ترمهـای شـاخص در مجموعـه اسناد می باشد. در این مدل , سند و پرسش به صورت زیر نمایش داده می شوند:
(۱) D [wd1 , wd 2 , wd 3 ,..., wdn ]T
(۲) Q [wq1 , wq 2 , wq3 ,..., wqn ]T
در فرمولهای فوق, wdi و wqi به ترتیب وزنهای ترم i ام سند D و پرسش Q و n تعداد ترمهای شاخص در مجموعه اسناد می باشند. برای محاسبه میزان شباهت سند و پرسش به یک معیار شباهت نیاز است. یک معیار متداول برای این منظور، تابع کسینوس می باشد که زاویه بین بردار سند و بردار پرسش را به عنوان میزان شباهت آنها در نظر می گیرد.
کارایی یک سیستم بازیابی اطلاعات با دو کمیت دقت (precision) و یادآوری (recall) اندازه گیری می شود که یادآوری نسبت تعداد سندهای بازیابی شده مرتبط با پرسش به تعداد کل سندهای مرتبط با پرسش در مجموعه است و دقت نیز نسبت تعداد سندهای بازیابی شده و مرتبط با پرسش به تعداد سندهای بازیابی شده تعریف می شود. نمایش میزان کارایی یک سیستم بازیابی اطلاعات برای یک
مجموعه پرسش که سندهای مرتبط با آنها از قبل قضاوت شده است, معمولا بصورت یک منحنی ارائه می شود.
اجزا یک سیستم بازیابی اطلاعات کلاسیک در شکل ۱ نشان داده شده است.
پرسش اسناد
نمایه گذاری
نمایش پرسش نمایش اسناد
R
معیارشباهت
F
لیست اسناد بازیابی شده برحسب شباهت با پرسش
شکل۱: یک سیستم بازیابی اطلاعات کلاسیک
۳- مکانیزمهای توسعه پرسش کاربر بر اساس RF
مکانیزم RF فرایندی است که به کاربر اجازه می دهد با قضاوت بر روی نتیجه جسـتجو, نیـاز اطلاعـاتی خـود را بصـورت مثالهـایی بـرای سیستم بیان کند. جهت مشخص نمودن این مثالها, کاربر از سندهای بازیابی شده تعدادی سند که به پرسش او مربوط می شود را انتخاب و به عنوان فیدبک به سیستم برمی گرداند.
هنگامی که یک سند بعنوان یک سند مرتبط توسط کاربر تعیین شد، واحد RF در سیستم بازیابی اطلاعات متن سـند را بررسـی کـرده و ترمهایی که از نظر آماری مهمتر از بقیه هستند را به پرسش اولیه اضافه می کند. سپس سیستم با پرسـش جدیـد اسـناد را بازیـابی و در اختیار کاربر قرار می دهد.
فرایند RF روش خوبی برای بیان کردن یک نیاز اطلاعاتی می باشد, بدلیل اینکه کاربر مجبور نیست هنگـام ترتیـب دادن پرسـش اولیـه زمان زیادی صرف کند. در عوض کاربر با مفاهیم موجود در سندها سروکار دارد و RF به خوبی با این مفهوم که "انسان تا چیزی را نبینـد,
نمی داند که چه می خواهد" تطبیق دارد. بمنظور شروع فرایند RF پرسش اولیه کاربر باید آنقدر مناسب باشد که بتواند حداقل تعدادی از سندهای مرتبط را بازیابی کند. اگر حداقل یکی از سندهای بازیابی شده تا اندازه ای به نیاز کاربر مـرتبط باشـد، مـی تـوان فراینـد RF را شروع کرد. در صورتیکه عملیات RF بخوبی پیش برود فهرست بعدی سندهای مرتبط بیشتری را در برخواهد داشت.
RF احتمالی٢ [2] یکی از روشهای پیشرفته RF می باشد که در عملی بازیابی اطلاعات از آن استفاده می شود. بطـور خلاصـه ایـن روش شامل اضافه کردن ترمها ی جدید به پرسش اصلی است. این روش تمام ترمهای موجود در سندهای مرتبط بازیابی شـده را طبـق فرمـول وزن دهی زیر مرتب می کند .[3] سپس تعداد m ترم که وزن بیشتری دارند را به پرسش کاربر اضافه می کند.
(۳) ri (N − ni − R ni ) wi log
− r ) i (R − r )(n
i i
درفرمول فوق, N تعداد کل سندهای مجموعه, ni تعداد سندهای شامل ترم R , i تعداد سندهای بازیابی شده و مرتبط کـه توسـط کـاربر علامت زده شده اند و ri تعداد سندهای بازیابی شده مرتبط و علامت زده شده توسط کاربر که حاوی ترم i هستند, می باشد. RF احتمالی فرکانس تکرار یک ترم در کل سندهای مرتبط را با فرکانس تکرار آن در کل مجموعه سندها مقایسه می کند. اگر یـک تـرم در سـندهای مرتبط بیشتر از کل مجموعه اتفاق بیفتد، وزن بیشتری توسط فرمول وزن دهی می گیرد. ایده بکار رفته در ایـن مقالـه ارائـه فرمـول وزن دهی مشابه فرمول فوق می باشد که توسط برنامه نویسی ﮊنتیک تکامل یافته است. اگر فرمول تکامل یافتـه از کـارایی بهتـری نسـبت بـه روش RF احتمالی برخوردار باشد، استفاده از آن در این زمینه قابل توجیه می باشد.
