بخشی از مقاله


خلاصه

امروزه موتورهای جستجو نقش مهمی برای دسترسی به اطلاعات در فضای وب دارند. حجم زیاد نتایج باعث سردرگمی کاربران میشود. بنابراین خوشهبندی نتایج جستجو و انتخاب یک برچسب مناسب مبتنی بر محتوای هر خوشه، ضروری است. در این مقاله سعی شده است نتایجی که در جستجوی اسناد XML بدست میآیند با استفاده از دادهکاوی به شکلی کارا خوشهبندی و سپس برچسبگذاری شوند. ازآنجا که عمل برچسبگذاری گام بلافصل پس از خوشهبندی میباشد اکثر روشهای برچسبگذاری، منتج از الگوریتمهای خوشهبندی میباشند. دراین مقاله نیز با ایجاد تغییراتی در یک الگوریتم خوشهبندی بهینه، قابلیت برچسبگذاری خوشهها را به آن اضافه کردهایم. الگوریتم پیشنهادی تحت عنوان CLXCLS قادر است اسناد XML را دریافت و حین انجام خوشهبندی، اطلاعات لازم برای برچسبگذاری را جمعآوری کند و در نهایت پس از برقراری ارتباط با یک پایگاه داده لغوی و تحلیل دادهها، به کمک بیشترین تکرار عناصر و مشابهت ساختاری، مناسبترین برچسب برای هر خوشه را پیشنهاد دهد. نتایج حاصل از ارزیابی الگوریتم روی مجموعه معتبری از دادهها با استفاده از معیار ”کلمات پرتکرار و پیشگویانه“ نشاندهنده برتری الگوریتم پیشنهادی در دقت و نزدیکی برچسبهای انتخاب‎شده نسبت به روشهای موجود میباشد.

کلمات کلیدی: اسناد XML، خوشهبندی، برچسبگذاری

.1 مقدمه

آنچه امروزه از اهمیت بسیار زیادی برخوردار گردیده، کمبود یا نبود اطلاعات نیست بلکه کمبود روشهایی در جهت یافت و بهرهبرداری از اطلاعات در دسترس، به نحوی بهینه است. متن کاوی، به عنوان روشی در استخراج دانش از متون، یکی از موضوعات مهم در این زمینه میباشد. نبود یک استاندارد همه جانبه و دقیق در تنظیم متون و قرارگیری این مجموعه عظیم به صورتی غیر ساختیافته و یا بعضاً نیمه ساختیافته، جامعه اطلاعاتی را دچار نوعی مشکل در دستیابی به اطلاعات مورد نیاز کرده به طوری که برای یافتن مطالب مورد نظر خود متحمل هزینه های زمانی بسیاری میگردند. محققان به ارائه راه کارهایی برای ساختیافته کردن اطلاعات نمودند و با ارائه زبانهای نشانه گذاری استاندارد نظیر XML تا حد زیادی جلوی این از هم پاشیدگی اطلاعاتی را گرفتند. در بخش 2 این مقاله به صورت کلی به مسئله خوشهبندی متون و بررسی کارهای مرتبط در زمینه برچسبگذاری بر روی خوشههای اسناد متنی پرداخته خواهد شد و یکی از الگوریتمهای خوشهبندی اسناد XML تحت عنوان XCLS تشریح میشود. در بخش 3 الگوریتم XCLS را تغییر داده و روشی تحت عنوان CLXCLS ارائه میکنیم که علاوه بر خوشهبندی اسناد XML قادر است برای خوشهها برچسب مناسبی نیز انتخاب کند. در بخش 4 الگوریتم پیشنهادی خود را بر روی یک مجموعه دادهای و تحت شرایط مختلف مورد ارزیابی قرار میدهیم و در بخش 5 به نتیجه گیری و ارائه پیشنهاد جهت کارهای آینده خواهیم پرداخت.

×

.2 کارهای انجامشده مرتبط با برچسب گذاری خوشههای اسناد متنی

روشهای مختلفی برای برچسبگذاری خوشههای حاوی اسناد متنی وجود دارد که اکثرا مبتنی بر محاسبه امتیازی برای عناصر موجود در خوشه و انتخاب عنصر با بیشترین امتیاز میباشند. بیشتر این روشها از تعداد تکرار هر عنصر به عنوان یک معیار اصلی برای امتیاز دهی استفاده میکنند و برخی نیز برای نرمالتر کردن نتیجه امتیازدهی و هرچه بهینه تر و واقعیتر کردن عملیات برچسبگذاری پارامترهای دیگری را نیز دخیل میکنند که معمولا از اطلاعات آماری حاصل از بررسی خوشه بدست میآیند.

.2.2 روش تکرار کلمات پرتکرار و پیشگویانه

در این روش که توسط Popescul در [2] برای برچسبگذاری خودکار خوشه در این روش که توسط Popescul در [2] برای برچسبگذاری خودکار خوشههای اسناد پیشنهاد شده است کلمات براساس ضرب میزان تکرار محلی و میزان پیشگویانه بودن به صورت رابطه (2) برای برچسب دهی انتخاب میشوند:

رابطه (1)

عبارت اول که همان میزان پیشگویانه بودن است وزن بیشتری به کلماتی میدهد که در خوشه مورد نظر به تعداد بسیار زیادی

رخ میدهند و وزن کمتری را به کلماتی میدهد که در همه خوشهها ظاهر شدهاند. تعداد تکرار کلمه در یک خوشه داده شده است
و تعداد تکرار کلمه در یک رده عمومیتر یا در کل مجموعه است. کلماتی که مقادیر بالایی برای معیار پیشگویانه بودن دریافت میکنند
متمایز کنندگان خوبی برای تمایز قایل شدن بین یک خوشه و بقیه خوشه ها هستند.
.2.2 الگوریتم XCLS برای خوشه بندی اسناد XML

الگوریتم XCLS یکی از روشهایی است که به صورت افزایشی عمل خوشهبندی را انجام میدهد و در ادامه به تشریح روش XCLS که در [2] آمده است خواهیم پرداخت.

.1.2.2 مشابهت سطحی: تابع معیار سراسری خوشهبندی

مشابهت سطحی رخداد عناصر مشترک در سطوح متناظر از دو شئ را اندازهگیری میکند. عناصر در موقعیتهای مختلف ساختار سطحی دارای وزنهای متفاوتی میباشند. به عنوان نمونه در سطوح بالاتر مثل ریشه عناصر دارای وزن بیشتری نسبت به عناصر در سطوح پایینتر مثل برگها هستند. معیار مشابهت سطحی در مقایسه با شئ اول (سند) و شئ دوم (خوشه) به صورتی است که در رابطه (2) آورده شده است.

r L j 1 1 L r L i 1 1 L
j CN 0.5 CN i 0.5
2 1
رابطه (2) × 0 j 0 i
r L k 1 1 L

Z N k
0 k

مقدار حاصل شده از مشابهت سطحی عددی بین صفر و یک خواهد بود که صفر بیانگر دو شئکاملاًمتفاوت و عدد یک نمایانگر دو شئ یکسان است. پس از گذراندن مراحل پیشین مرحله بعدی دستهبندی اسناد XML از میان منابع مختلف میباشد که این کار با در نظر گرفتن مشابهت سطحی انجام میشود. با توجه با مزیتهای روش های خوشه بندی افزایشی3] و [4 الگوریتم خوشهبندی XCLS به صورت جلورونده هر سند XML را که وارد میشود در یک خوشه جدید و یا در یکی از خوشههای موجود که بر اساس مشابهت سطحی دارای بیشترین شباهت با سند وارد شده میباشد جای میدهد.الگوریتم XCLS از یک حد آستانه تعریف شده توسط کاربر (LevelSim_Threshold) استفاده میکند که مشابهت سطحی بیشتر از این حد آستانه به معنای شبیه در نظر گرفتن دو شئ میباشد و اگر مشابهت سطحی از این مقدار کمتر باشد به این معنی است که دو شئ به اندازه کافی به هم شبیه نیستند. روش های خوشهبندی افزایشیمعمولاً به خاطر حساس بودن به ترتیب ورود دادهها مورد انتقاد قرار میگیرند، چرا که ترتیب ظاهر شدن اسناد منجر به راه حل های بهینه محلی می شود و در نهایت ترتیب های متفاوت نتایج مختلفی را به همراه خواهد داشت. در الگوریتم XCLS فاز تخصیص مجدد برای اسنادی در نظر گرفته شده است که به خاطر ترتیب اولیه ورودشان در خوشههای اشتباهی قرار گرفتهاند. در این فاز خوشه بندی ایجاد شده مورد بررسی مجدد قرار میگیرد تا تصحیح شود، این عمل با بهینهسازی مشابهت سطحی بین اسناد جدید (اسنادی که به صورت تصادفی از بین سند های خوشهبندی شده انتخاب میشوند) و خوشههای موجود انجام میپذیرد. تعداد تکرار این فاز زیاد نمی باشد.

در متن اصلی مقاله به هم ریختگی وجود ندارد. برای مطالعه بیشتر مقاله آن را خریداری کنید