دانلود رایگان ترجمه مقاله به سمت خوشه بندی XML معنایی (Siam سال 2006)

مبتدی (مناسب برای درک مفهوم کلی مطلب) 

اخیراً، اهمیت خلاصه سازی داده XML افزایش می‌یابد، اساسا با هدف تعریف ترکیب‌های برای خوشه‌ها با ساختار مشابه است. رویکردها از مدل‌های نمایش مبتنی بر گراف و تطبیق درخت پیشنهادی استفاده می‌کنند. XSketch یک مدل خلاصه اصلاح شده است که مسئله تخمین انتخاب مسیر موجود را در محیط کلی داده XML با گراف ساختاریافته با مقادیر عناصر بررسی می‌کند. ساخت یک خلاصه دقیق بر اساس فرضیات آماری است که فقدان مسیر دقیق و ارزش اطلاعات را در خلاصه جبران می‌کند. به هر حال، ایجاد یک XSketch یک مسئله NP سخت تشریح شده است، بنابراین یک استراتژی پالایش اکتشافی باید استفاده شود.
نیاز برای سازمان دهی داده XML بر طبق ویژگی‌های ساختاری و محتوایی؛ با توجه به افزایش ناهمگونی منابع XML چالش برانگیز شده است. به هر حال، کاووش داده XML از نقطه نظر ترکیب محتوا/ساختار هنوز در مرحله اولیه است، و هیچ رویکردی برای ارائه قابلیت‌های موثر برای خوشه بندی XML معنایی وجود ندارد. اولین تلاش در [6] داده شده است، که اعمال تکنیک خوشه بندی تفکیکی را به اسناد XML نشان داده شده در یک مدل فضای برداری با ویژگی‌های مبتنی بر ‌تگ و متن اعمال می‌کند.
یک نمایش جایگزین، به نام BitCube، در [18] به عنوان شاخص بیت مپ 3 بعدی سه تایی < سند، مسیر عناصر-XML، کلمه> ارائه داده است. شاخص‌های BitCube می‌توانند برای تقسیم اسناد به خوشه ها، با استفاده از فاصله بیتی و سنجش شهرت دستکاری شوند. به منظور افزایش سرعت پاسخ به پرس و جو، عملیات برش/تاس/پیش بینی برای زیر بخش‌های نتیجه شده از فاز خوشه بندی اجرا می‌شود. به هر حال، هیچ تصمیم مهمی توسط مولفین در مورد بهبود ممکن خوشه بندی سند ارائه نشده است. به طور کل، رویکرد از معایب معمولی مدل‌های پیش نمایش بولین، مانند فقدان معیار تطبیق جزیی و سنجش طبیعی رتبه بندی اسناد رنج می‌برد.
تولید ویژگی‌ها برای داده XML در [16] عمیق تر بررسی شده است، جایی که تفسیرها، ساختارها و اطلاعات هستی شناسی با هم ترکیب می‌شوند. به هر حال، در اینجا تمرکز بر ایجاد ویژگی‌های مناسب در راستای اهداف دسته بندی نظارت شده داده XML است.
طرح مقاله. باقی مقاله به شرح زیر سازمان یافته است. بخش 2 اصطلاح شناسی و نمادهای سودمندی، و پیش زمینه ضروری بر مفاهیم تاپل درختی، آیتم، و تراکننش برای دامنه داده XML ارائه می‌دهد. بخش 3 تشریح می‌کند که چگونه ویژگی‌های XML به صورت معنایی به اطلاعات نحوی در آیتم‌های تاپل درختی XML با دانش هستی شناسی واژگان دست می‌یابد. تاکید ویژه این بخش بر روش‌های جدید ابهام زدایی از حس ‌تگ است. بخش 4 فریم ورکی را برای خوشه بندی تراکنش‌های XML ارائه می‌دهد. بخش 5 ارزیابی ‌آزمایش‌های را گزارش می‌دهد که اثربخشی فریم ورک خوشه بندی را گزارش می‌دهد. بخش 6 نتایج برجسته و نکات امیدوار کننده برای پژوهش‌های آینده بیان می‌کند.

2. پیش زمینه
2.1 مسیرها و درخت‌های XML
یک درخت T یک چندتایی است، به مجموعه‌ای از گره‌ها اشاره دارد، ریشه متماییز T است، به مجموعه یال‌های (بدون دور) اشاره دارد، و تابعی از ارتباط یک گره با یک ‌تگ در الفبای است. فرض کنید Tag، Att، و Str الفبایی از نام ‌تگ ها، صفات، و رشته‌ها هستند. در یک درخت XML، XT یک جفت ، به طوریکه : 1) T یک درخت تعریف شده در الفبای است، که نماد برای اشاره به مدل محتوای استفاده می‌شود؛ 2) با توجه به ؛ 3) تابعی از رشته‌های مرتبط با گره برگ T است.
یک مسیر p XML یک توالی از نمادها در است. نماد با نام تگ عنصر ریشه سند متناظر است. یک مسیر XML می‌تواند دو نوع باشد: مسیر تگ ؛ اگر ، یا مسیر کامل باشد، اگر برقرار باشد. به به عنوان مجموعه‌ای از مسیرهای کامل در XT اشاره می‌کنیم.
فرض کنید یک درخت XML است، و یک مسیر XML است. کاربرد p برای XT شناسایی مجموعه گره‌های است به طوری که، برای هر ، دنباله‌ای از گره ها، یا مسیر گره، با ویژگی‌های زیر وجود دارد: 1) و ؛ 2) فرزند ، برای هر ؛ 3) برای هر . است.
علاوه بر این، می‌گوییم که یک مسیر به یک درخت XML یک پاسخ حاصل می‌کند، که بسته به نوع مسیر تعریف می‌شود. در مورد مسیر تگ p، پاسخ p بر XT دقیقاً مجموعه‌ای از شناسه گره است، بنابراین داریم . برای یک مسیر کامل p، پاسخ p بر XT به عنوان مجموعه‌ای از مقادیر رشته‌ای مرتبط با گره‌های برگ شناخته شده با p تعریف می‌شود، به همین ترتیب داریم . برای یک مسیر کامل p، پاسخ p بر XT به عنوان مجموعه‌ای از مقادیر رشته‌ای مرتبط به گره‌های برگ شناخته شده توسط pتعریف می‌شود، .

2.2 تاپل‌های درخت XML.
تاپل‌ها مفهوم تاپل را در یک پایگاه داده رابطه‌ای همانند سازی می‌کنند و بسطی از وابستگی‌های تابعی برای محیط XML پیشنهاد می‌کنند. در یک پایگاه داده رابطه‌ای، یک تاپل یک تابع از هر صفت با مقداری از دامنه متناظر است. برطبق [8]، تعریف‌های زیر را ارائه می‌دهیم:
تعریف 2.1 با توجه به XT از درخت XML، یک تاپل درخت یک زیر درخت ماکسیمال XT است، به طوری که بر هر ( ‌تگ یا کامل) مسیر p در XT، پاسخ حداقل یک عنصر است.
به به عنوان مجموعه‌ای از تاپل‌های درخت از XT اشاره می‌کنیم.
مستقیما، یک تاپل درخت یک نمایش درخت (یا زیر درختی) از مجموعه کاملی از مفاهیم متمایز است که بر طبق معنا شناسی ساختاری درخت اصلی با هم همبسته هستند. علاوه بر این، تاپل‌های درخت استخراج شده از همان درخت، ساختار یکسانی را حفظ می‌کنند، در حالی که روش‌های متفاوتی از محتوای مربوطه ساختاری را منعکس می‌کند که می‌تواند طبیعتآ از درخت اصلی استنباط شده باشد.
مثال 1. درخت XML نشان داده شده در شکل 1 را در نظر بگیرید، که دو مقاله علمی را از آرشیو DBLP نشان می‌دهد. هر گره داخلی دارای ‌تگ منحصربفردی است که به نام ‌تگ اشاره می‌کند،در حالی که هر گره برگ نیز با نام و مقدار یک صفت برچسب خورده است، یا نماد S و رشته مربوطه با مدل محتوای #PCDATA متناظر است. مسیر پاسخ‌ها می‌تواند به سادگی محاسبه شود: برای مثال، مسیر dblp.article.title مجموعه‌ای از شناسه‌های گره را حاصل می‌کند، در حال که مسیر dblp.article.author.S مجموعه رشته {‘Hartmut Liefke’, ‘Dan Suciu’} را کسب می‌کند.
سه تاپل درخت می‌تواند از مثال درخت (شکل 2) استنتاج شود. یک تاپل درختی با شروع از زیررخت راست با ریشه در عنصر dblp استخراج شود. دو تاپل درخت در عوض با شروع از زیردرخت چپ با ریشه در dblp استخراج می‌شود، از آنجایی که در این زیر دخت دو مسیر dblp.article.author وجود دارد، هریک مسیر پاسخ متماییزی را متناظر با نویسنده مقاله کسب می‌کنند.