عنوان پایان‌نامه
داده کاوی درxml بااستفاده ازالگوهای مبتنی برزیر در
- رشته تحصیلی
- مهندسی کامپیوتر -نرم افزار
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 35612
- تاریخ دفاع
- ۱۶ مهر ۱۳۸۶
- دانشجو
- مصطفی حقیرچهرقانی
- استاد راهنما
- مسعود رهگذر
- چکیده
- بسیاری از داده ها در ساختار رابطه ای مشخصی نمی گنجند چون این نوع داده ها ساختار کاملا یکسانی ندارند. به بانکهای اطلاعاتی این نوع داده ها، بانکهای اطلاعاتی نیم ساخت یافته (semi-structure) می-گویند. در این نوع بانکها شمای ثابتی برای بانک وجود ندارد و داده ها در یک ساختار گراف مانند که هم شامل اطلاعاتی در مورد داده ها و هم خود داده هاست، ذخیره می شوند. از جمله این نوع بانکهای اطلاعاتی می توان به XML اشاره کرد. در حال حاضر XML حجم زیادی از داده¬های موجود در وب را به خود اختصاص داده است و در همه زمینه¬های برنامه¬نویسی و ذخیره سازی اطلاعات تحت وب جای خود را باز کرده است. همراه با رشد مداوم داده های XML توانایی استخراج دانش از آنها اهمیت روز افزونی یافته است. در بانکهای اطلاعاتی XML ساختار یک داده بخش مهمی از مفهوم آن را بیان می کند. در نتیجه علاوه بر کاوش در خود داده، یافتن مدلها و الگوهایی در ساختار داده، نیز نقش مهمی در استخراج مفاهیم ایفا می کند. این روش استخراج مفاهیم را می توان حالت تعمیم یافته روشهای استخراج روابط وابستگی درنظرگرفت. از جنبه کاربردی، درختهایی که به تناوب تکرار می شوند، دیدی کلی از اطلاعات موجود در بانک اطلاعاتی را می رسانند و راهی برای خلاصه کردن داده های موجود در بانک اطلاعاتی می باشند. از این مفاهیم می توان در بیان پرس و جوها، ساختن ایندکسها، خوشه بندی ، دسته بندی و .... استفاده نمود. کشف ساختارهای پرتکرار به خاطر ساختار آزادی که XML دارد، چندان آسان نیست. برای مثال فایلهای XML ممکن است داده های یکسان ولی ساختارهای متفاوتی داشته باشند. حتی در حالتی که از DTD یکسان استفاده شده باشد، ساختار درختی آنها ممکن است یکسان نباشد. بسیاری از الگوریتمهای موجود برای یافتن الگوهای درختی پرتکرار، در فازهای تولید کاندیدا و شمارش تعداد دفعات تکرار هر یک از آنها، از روشهای مبتنی بر خاصیت anti-monotone استفاده می کنند. در این روشها فضای حالت به صورت نمایی افزایش می یابد و تعداد زیادی کاندیدای غیر-واقعی تولید می شود، به خصوص هنگامی که داده ها چگال باشند و تعداد زیادی الگوهای بزرگ در آنها وجود داشته باشند. برای غلبه بر این مشکلات ما سعی خواهیم کرد تا "مشبکه تولید کاندیدا" را از بالا به پایین بسازیم. یک روش بالا به پایین به الگوهای بزرگتر سریعتر می رسد، مضافاٌ اینکه کاندیداهای غیرواقعی کمتری تولید می کند. بعلاوه در این الگوریتم یک روش جدید برای شمارش تعداد دفعات تکرار کاندیداهای درختی ارائه می کنیم. این روش از لحاظ پیچیدگی زمانی کارا بوده و نیاز به حافظه زیادی ندارد. سپس سعی خواهیم کرد تا با استفاده از الگوهای درختی پرتکرار، یک الگوریتم خوشه بندی کارا برای داده های با ساختار درختی ارائه کنیم. این الگوریتم برای هر خوشه یک درخت نماینده در نظر می گیرد و هر درخت ورودی را تنها با درختهای نماینده خوشه ها مقایسه می کند، در نتیجه زمان اجرا را به شدت کاهش می دهد. ما پایین بودن پیچیدگی زمانی الگوریتم را اثبات می کنیم و به صورت عملی بالا بودن صحت الگوریتم را در مقایسه با الگوریتمهای مشابه نشان می دهیم. آزمایشهای ما نشان می دهند که الگوریتم پیشنهادی معیارهای مهم خوشه بندی از قبیل شباهت درون خوشه ای، شباهت بین خوشه ای، DUNN و DB را بهبود می¬بخشد. در ادامه الگوریتمهای C-Classifier و M-Classifier را برای دسته بندی مبتنی بر قانون داده های درختی ارائه می کنیم. این الگوریتمها بر پایه استخراج الگوهای خاصی از داده های درختی قرار دارند. این الگوها، یعنی الگوهای بسته و الگوهای بیشینه، قادر به استخراج کامل و در عین حال ناافزونه مشخصات داده های آموزشی هستند. آزمایشهای ما نشان می دهند که درستی C-Classifier تقریبا برابر با درستی کاراترین الگوریتمهای قبلی است ولی زمان اجرا آن کمتر است. آزمایشات ما همچنین نشان می دهند که M-Classifier درستی را افزایش می دهد و زمان اجرا و پیچیدگی دسته بندی را کاهش می-دهد.
- Abstract
- Nowadays, since all parts of a dataset do not share the same structure, they can not be stored in a unique pre-defined format. These databases which are usually called semi-structured databases do not have a fixed schema and their data are kept in a graph-based or tree-based structure containing both data and the relationships between them. XML is the well-known language for definition and manipulation of such data. Currently, XML is used for storing huge amount of web data. With the continuous growth of XML data, knowledge discovery and XML mining has found an increasing interest. XML document structure tells many about the concepts it contains; therefore, more than mining the data, finding models and patterns in the structure can play an important role in knowledge discovery. This type of data mining can be considered as generalized association rule mining. From applicability point of view, subtrees which are repeated frequently in a tree database describe its global view and provide a way for summarizing the information embedded in the database. These patterns can be used in query expression, index definition, clustering, classification and so on. Due to the relatively free structure of XML data, finding frequent tree patterns entails several difficulties. For example, XML documents may contain similar data in different structures that is possible even if we use a unique DTD. Most of existing algorithms for finding frequent tree patterns use apriori or anti-monotone property for candidate generation and frequency counting. In these algorithms, the state space grows exponentially and lots of unreal candidates are generated, especially when the input data are dense and they include many common frequent tree patterns. To solve afore mentioned problems, we will try to construct “candidate generation lattice” from top to down. A top-down approach can generate large patterns faster and furthermore produce less unreal candidates. We also present a new approach for frequency counting which leads to memory conservation and time complexity reduction. In the next part of our work, we propose an efficient algorithm for clustering tree-structured data. This algorithm considers a representative tree for each cluster and compares each input tree only with the representatives; as a result it reduces the running time intensively. We prove its efficiency in terms of time complexity and then empirically evaluate its high accuracy compared to other algorithms. Our experiments show that the proposed algorithm improves several important cluster quality measures such as intra-cluster similarity, inter-cluster similarity, DUNN and DB. Subsequently, we develop C-Classifier and M-Classifier algorithms for rule-based classification of tree-structured data. These algorithms are based on extracting special types of patterns from training data. These patterns, e.g. closed patterns and maximal patterns, are capable of complete and non-redundant discovery of specifications of training dataset. Our experimental results show that the accuracy of C-Classifier is nearly equal to the most accurate previously proposed algorithms meanwhile it reduces the running time and complexity. Our empirical studies also show that M-Classifier improves the accuracy of classification and reduces its running time and complexity.
