دانلود رایگان مقاله خوشه بندی XML معنایی

چکیده 

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

1. مقدمه 

        XML به عنوان نیروی محرکی برای نمایش و تبادل داده در وب معرفی شد. براستی، سیمای خود توصیف و نیمه ساختاریافته XML مدل کردن طیف گسترده‌ای از داده‌ها را به عنوان اسناد XML، به منظور تحقق وعده‌های وب نسل بعد، امکان پذیر ساخت. 

         منابع داده XML ساختارها و محتوای متفاوتی را نشان می‌دهند. تگ نشانه گذاری، که نقش پایه را برای تحمیل ساختار به سند بازی می‌کنند، عوامل ذهنی را که نام نویسنده را در اطلاعات برنامه نویسی هک می‌کند را منعکس می‌کند. در نتیجه، داده XML به صورت متفاوت اعلام شده ممکن است " از لحاظ معنایی" به درجه خاصی مربوط باشد. 

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

        مانند یک وظیفه داده کاوی اکتشافی اساسی، خوشه بندی راه حل‌های طبیعی را برای کشف ویژگی‌های مشترک و جنبه‌های خاص نشان داده شده توسط اسناد XML نشان می‌دهد. به هر حال، پیچیدگی ذاتی داده نیمه ساختاریافته نیازمند تلاش ناچیزی برای تعیین فریم ورک خوشه بندی موثر است. استخراج ویزگی‌های مهم، مدل سازی محتوا و ساختار اسناد، تعریف مفاهیم مناسب همگن بین اسناد تنها برخی از مسائل بررسی شده هستند. 

        سهم. در این مقاله از طریق تحلیل عمیق محتوا و ویژگی‌های ساختاری در داده چگونگی ربط معنایی داده‌های XML بررسی می‌شود. آنچه اخیراً برای کاووش داده XML پیشنهاد شده است معرفی نمادی از تاپل‌های درختی در تعریف مدل نمایش XML است که نگاشت درخت اسناد XML را در داده تراکنشی اجازه می‌دهد. مفهوم تاپل درخت به خوبی از شناخت معنایی زیرساختارهای منسجم اسناد XML گرفته شده است، علاوه بر این، یک نمایش XML منطقی، مسطح، را ممکن می‌سازد که برای برآورده سازی نیازمندی‌هایی برای خوشه بندی داده XML برطبق اطلاعات محتوا و ساختار بسیار مناسب است. سهم ما می‌تواند به شکل زیر خلاصه شود: 

1. با تدبیر ویژگی‌های مناسب برای داده XML، بر اطلاعات محتوای استخراج شده از عناصر متنی و اطلاعات ساختاری خاص از مسیرهای ‌تگ تمرکز می‌کنیم. هر دو نوع اطلاعات نحوی با دانش ارائه شده توسط هستی شناسی واژه بدست می‌آیند. به ویژه، برای مورد ساختاری، روش ابهام زدایی حس کلمه  جدیدی را برای انتخاب مناسب ترین حس برای هر نام ‌تگ در زمینه مسیر درخت XML انتخاب می‌کند. ویژگی‌های XML به آیتم‌های تاپل درخت XML ابلاغ می‌شود. 

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

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

         کارهای مرتبط. اخیراً رویکردهای متعددی برای کاووش داده XML توصیه شده است، که اغلب با توجه به ساختار بر خوشه بندی اسناد XML تمرکز می‌کند. این رویکردها اساسا با چندین برنامه کاربردی در مدیریت داده ساختار یافته، به خصوص در محیط وب، که تقاضا برای راه حل‌های موثر و کارآمد شناسایی شباهت‌های ساختاری در میان داده نیمه ساخت یافته افزایش می‌یابد، انگیزش می‌یابند. در این زمینه، یک ویرایش از راه دور آگاه از XML برای سنجش شباهت‌های ساختاری در میان اسناد XML پیشنهاد شده است؛ و الگوریتم خوشه بندی سلسله مراتب استانداردی برای ارزیابی اینکه چقدر اسنادهای خوشه به DTD مربوطه خود نزدیک هستند، اعمال شد. به هر حال، به طور کل، محاسبه فاصله ویرایش درخت به نوبه خود غیر عملی است، که نیازمند تعداد درجه دومی از مقایسه‌های بین عناصر اسناد است. 

         یک بینش مهم در وظایف دسته بندی نظارت شده داده XML از نقطه نظر ساختاری در [19] ارائه شده است. نویسنده یک تکنیک یادگیری ماشین را پیشنهاد داده است که از استخراج ساختارهای فرعی که مکرر در اسناد XML به منظور تعریف نقش‌های دسته بندی رخ می‌دهد استفاده می‌کند. 

Abstract

       The increasing availability of heterogeneous XML informative sources has raised a number of issues concerning how to represent and manage semistructured data. Although XML sources can exhibit proper structures and contents, differently annotated XML documents may in principle encode related semantics due to subjective definitions of markup tags. Discovering knowledge to infer semantic organization of XML documents has become a major challenge in XML data management. In this context, we address the problem of clustering XML data according to structure as well as content features enriched with lexical ontology knowledge. We propose a framework for clustering semantically cohesive XML structures based on a transactional representation model. Experiments on large real datasets give evidence that the proposed approach is highly effective in detecting groups of XML data that exhibit structure and/or content affinities.

1 Introduction

        XML is touted as the driving-force for representing and exchanging data on the Web. Indeed, the semistructured and self-describing physiognomy of XML makes it feasible to model a broad variety of data as XML documents, in order to fulfill the promises of the nextgeneration Web.

        XML data sources exhibit different structures and contents. Markup tags, which play a basic role to impose the structure of a document, reflect subjective factors that brand the authorship in coding information. As a consequence, differently annotated XML data may be “semantically related” at a certain degree.

        In such a context, a challenge is inferring semantics from XML documents according to the available syntactic information, namely structure and content features. This has several interesting application domains, such as integration of data sources and query processing, that can be seamlessly generalized to any kind of semistructured data. For example, detecting structural and content affinities among XML data can aid to conceive techniques for indexing such data, thus narrow-ing the search space and improving the design of query plans.

       As a fundamental exploratory data mining task, clustering represents the natural solution to discover common characteristics and specific facets exhibited by XML documents. However, the complexity intrinsic to semistructured data requires nontrivial effort to define an effective clustering framework. Extracting significant features, modeling document structures and contents, defining an appropriate notion of homogeneity between documents are only some of the issues to be addressed.

       Contribution. In this paper we investigate how to cluster semantically related XML data through an indepth analysis of content and structural specifics in the data. A major novelty of our proposal for mining XML data is the introduction of the notion of tree tuple in the definition of an XML representation model that allows for mapping XML document trees into transactional data. The notion of tree tuple lends itself particularly well to identify semantically cohesive substructures from XML documents; moreover, it enables a flat, relationallike XML representation that is well-suited to meet the requirements for clustering XML data according to structure and content information. Our contributions can be summarized as follows:

1. We devise suitable features for XML data, focusing on content information extracted from textual elements and structure information derived from tag paths. Both kinds of syntactic information are enriched with knowledge provided by a lexical ontology. In particular, for the structure case, we propose a novel word sense disambiguation method to select the most appropriate sense for each tag name in the context of an XML tree path. XML features are conveyed by XML tree tuple items.

2. We conceive a transactional model for representing the XML tree tuples extracted from a collection of XML documents. Such a model is at the basis of a semantic XML clustering framework. We adopt an effective partitional approach based on an algorithm designed for the XML transactional domain, although the proposed framework is conceived to be parametric w.r.t. any method of clustering.

3. We conduct on large real datasets several experiments aimed at assessing the ability of the framework in performing structure- or content-driven clustering, as well as discovering clusters of “hybrid” type. Empirical evidence argues that the proposed framework is highly effective and shows a good scalability.

        Related work. Several approaches to mining XML data have been recently devised, mostly focusing on clustering XML documents by structure. This is mainly motivated by several applications in the management of semistructured data, especially in the Web environment [1, 17], which have raised the demand for effective and efficient solutions to the problem of identifying structural similarities among semistructured data. In this context, [12] proposes an XML-aware edit distance to measure structural similarity among XML documents, and applies a standard hierarchical clustering algorithm to evaluate how closely cluster documents correspond to their respective DTDs. However, in general, computing tree edit distances turns out to be unpractical, as it requires a quadratic number of comparisons between document elements.

        An important insight into the task of supervised classification of XML data from the structure viewpoint is provided in [19]. The authors propose a machine learning technique that exploits mining of substructures frequently occurring in XML documents in order to define classification rules.

چکیده 

1. مقدمه 

2. پیش زمینه 

2.1 مسیرها و درخت‌های XML

2.2 تاپل‌های درخت XML. 

2.3 یک مدل تراکنشی برای تاپل‌های درخت XML. 

3. استخراج ویژگی‌های XML 

3.1 ویژگی‌های ساختار 

3.2 ویژگی‌های محتوا 

4. خوشه بندی تراکنشی XML 

4.1 تشابه آیتم در تاپل درختی XML 

4.2 الگوریتم میانگین – XTrK

5. ارزیابی آزمایشی

6. نتیجه گیری و کارهای آینده 

منابع

Abstract

1 Introduction

2 Background

2.1 XML trees and paths

2.2 XML tree tuples

2.3 A transactional model for XML tree tuples

3 Extracting XML Features

3.1 Structure features

3.2 Content features

4 XML Transactional Clustering

4.1 XML tree tuple item similarity

4.2 The XTrK-means algorithm

5 Experimental Evaluation

6 Conclusion and Future Work

References