بخشی از مقاله
چکیده
خوشه بندی در زمینه بازیابی اطلاعات به صورت گسترده ای در ساﳍای اخیر با هدف بالا بردن سرعت و کارایی سیستم مورد استفاده قرار گرفته است. ارتقاﺀ کارایی سیستم بر پایه این فرضیه استوار است که اسناد مرتبط با یک پرسش خود شبیه یکدیگر هستند و انتظـار می رود که در عمل خوشه بندی در یک خوشه قرار گیرند. جهت عمل خوشه بندی یک معیار شباهت مورد نیاز است که با آن بتوان شباهت دو سند را اندازه گرفت. معیارهای شباهت ایستا مانند کوسینوس، شباهت دو سند را بدون توجه به پرسش کاربر ﳏاسبه می کنند و در نتیجه شباهت دو سند ﲢت پرشس های ﳐتلف کاربر یکسان خواهد بود. معیارهای شباهت حساس به پرسـش Query-) (Sensitive Similarity Measures سعی در آشکار کردن شباهت دو سند ﲢت یک پرسش خاص را دارند. در این مقاله یک معیـار شباهت حساس به پرسش ارایه شده است که با استفاده از چندین ﳎموعه اسناد استاندارد در زمینه ی بازیابی اطلاعات مورد ارزیابی قرار گرفته است و کارایی آن با معیار شباهت ایستا که به پرسش توجهی ندارند و ﳘچنین با معیارهای شباهت حساس به پرسش ارایه شـده توسط سایر ﳏققان، مقایسه شده است. نتایج آزمایش ها، نشان دهنده ی پیشرفت قابل ملاحظه ی معیار ارایه شده است. بر اساس این نتایج انتظار می رود که استفاده از این معیار پیشنهادی، باعث افزایش کارایی سیستم های بازیابی اطلاعات مبتنی بر خوشه بندی شود.
کلمات کلیدی
خوشه بندی مﱳ، معیارهای شباهت ، سیستم های بازیابی اطلاعات متنی
۱_ مقدمه
خوشه بندی روشی است که اجازه ی شناخت و ایجاد گروه هایی از اشیاﺀ مشابه در فضای چند بعدی را می دهد. خوشه بندی ارتباط بین اسناد ﳎموعه را مورد توجه قرار می دهد. این روش می تواند اسناد مرتبطی که به علت میزان شباهت پایین با پرسش در انتهای لیست قرار گرفته اند را با اسناد مرتبط دیگر گروه کرده و باعث بازیابی آهنا شده و در نتیجه باعث افزایش کارایی شود .[1,2]
فرضیه خوشه بندی اساس هببود کارایی است، فرضیه بیان می کند که اسناد مرتبط با پرسش در مقایسه با اسناد غیرمرتبط، ﲤایل بیشتری برای شبیه به هم بودن دارند، بنابراین در یک خوشه قرار می گیرند .[3] اگر این فرضیه برای یک ﳎموعه اسناد ثابت به کار رود، اسناد مرتبط و غیرمرتبط را به خوبی از هم جدا می کند (به صورت گروهی). بنابراین، یک معیار جستجوی مبتنی بر خوشه بندی کارامد خواهد بود.
هر دو سند دارای یک شباهت ایستا می باشند که به پرسش وابسته نیست. مضافا، هر دو سند دارای شباهتی هستند که حساس به پرسش است. معیارهای شباهت حساس به پرسش سعی در آشکار کردن شباهت دو سند ﲢت یک پرسش خاص را دارند. در این نوع معیار شباهت، میزان شباهت دو سند ﲢت پرسش های ﳐتلف، یکسان ﳔواهد بود. معیارشباهت ایستا مانند کوسینوس، توانایی آشکار کردن این شباهت را ندارد، زیرا به پرسش که شباهت دو سند ﲢت آن بررسی می شود توجهی ندارد.
معیار شباهت حساس به پرسش روش بدیعی است و بر این پایه استوار است که، شباهت یک مفهوم پویا است و به پرسش وابستگی زیادی دارد. تلاش ما بر به دست آوردن معیاری (فرمولی) برای آشکار کردن این شباهت است. پیشنهاد این ﲢقیق استفاده از معیار شباهت حساس به پرسش در خوشه بندی است زیرا این معیار ﲤایل به آشکار کردن ارتباط بین هر دو سندی را دارد که دارای صفات مشترکی با پرسش باشند.
ادامه مقاله به صورت زیر سازماندهی شده است. در ﲞش دوم پیش زمینه های لازم بیان شده اند. معیار شباهت حساس به پرسش برای ﳏاسبه ارتباط بین اسناد در ﲞش سوم ارایه شده است. در ﲞش چهارم، کارهای اﳒام شده و نتایج آزمایش ها بیان شده اند و ﲞش پنجم به نتیجه گیری اختصاص یافته است. در پایان منابعی که به آهنا ارجاﺀ شده است بیان شده اند.
۲_ پیش زمینه
در هر روش خوشه بندی، به یک معیار شباهت برای ﳏاسبه شباهت اشیاﺀ نسبت به هم مورد نیاز است. در خوشه بندی اسناد معمولا قبل از ارایه پرسش کاربر به سیستم، میزان شباهت ﳘه اسناد، با هم ( بصورت دو به دو) ﳏاسبه شده و در یک ماتریس بزرگ ذخیره می شوند. این نوع از خوشه بندی به خوشه بندی ایستا شهرت یافته است زیرا شباهت هر دو سند، غیر وابسته به پرسش است و با تغییر پرسش ارایه شده به سیستم، ثابت باقی می ماند. در گذشته معیارهای شباهت ایستای گوناگونی در این زمینه پیشنهاد شده اند. یک معیار متعارف از این نوع، معیار شباهت کوسینوسی است که می توان آن را به صورت رابطه زیر بیان کرد.
n∑dk .xk :۱M
(۱) COS(D, X ) k 1
n∑xk n∑dk
k 1 k 1
در معادله بالا D و X معرف بردارهای دو سند در فضای برداری هستند. dk و xk وزن ترم kام به ترتیب در سندهای D و X می باشند، n نشان دهنده تعداد ترم هایی است که برای ﳕایه گذاری اسناد مورد استفاده قرارگرفته اند.
ایده یک معیار شباهت برای ﳏاسبه شباهت دو سند بر اساس ﳏتوای یک پرسش، اولین بار توسط ﳏققان در [4] ارایه شد. آهنا یک معیار ضمنی (implicit) برای ﳏاسبه این شباهت پیشنهاد کردند. به این ترتیب که آهنا از خوشه بندی برای زیر ﳎموعه ای از اسناد که در پاسخ به پرسش کاربر بازیابی شده، استفاده کردند. تفاوت به کار بردن خوشه بندی برای یک زیر ﳎموعه از اسناد (تعداد n سند بازیابی شده در ابتدای لیست خروجی سیستم بازیابی اطلاعات) و نه ﲤام ﳎموعه در این است که وزن ترم های اسناد با توجه به توزیع ترم ها در این زیر ﳎموعه، تغییر کرده و در حقیقت ترم ها با توجه به این زیر ﳎموعه دوباره وزن دهی می شوند. فرض کنید که اسناد D و X، هر دو در جواب پرسش های ۱Q و ۲Q بازیابی شوند. شباهت دو سند D) و (X ﲢت پرسش های ۱Q و ۲Q متفاوت خواهد بود، زیرا ﳕایش هر دو سند درهر حالت وابسته به اسناد دیگر در زیر ﳎموعه است (بازیابی شده در پاسخ به پرسش).
