Abstract
This research involves implementation of genetic network programming (GNP) and standard dynamic programming to solve the knapsack problem (KP) as a decision support system for record clustering in distributed databases. Fragment allocation with storage capacity limitation problem is a background of the proposed method. The problem of storage capacity is to distribute sets of fragments into several sites (clusters). Total amount of fragments in each site must not exceed the capacity of site, while the distribution process must keep the relation (similarity) between fragments within each site. The objective is to distribute big data to certain sites with the limited amount of capacities by considering the similarity of distributed data in each site. To solve this problem, GNP is used to extract rules from big data by considering characteristics (value ranges) of each attribute in a dataset. The proposed method also provides partial random rule extraction method in GNP to discover frequent patterns in a database for improving the clustering algorithm, especially for large data problems. The concept of KP is applied to the storage capacity problem and standard dynamic programming is used to distribute rules to each site by considering similarity (value) and data amount (weight) related to each rule to match the site capacities. From the simulation results, it is clarified that the proposed method shows some advantages over the conventional clustering algorithms, therefore, the proposed method provides a new clustering method with an additional storage capacity problem
چکیده
این پژوهش شامل اجرای برنامه‌نویسی شبکه ژنتیک (GNP) و برنامه‌نویسی پویای استاندارد برای حل مسئله کوله پشتی (KP) به عنوان سیستم پشتیبان تصمیم برای خوشه‌بندی رکوردها در پایگاه داده توزیع شده است. مسئله تخصیص قطعه1 با توجه به محدودیت ظرفیت ذخیره‌سازی پیش‌زمینه برای روش پیشنهادی است. مسئله ظرفیت ذخیره سازی برای توزیع مجموعه قطعه‌ها در چند سایت (خوشه‌ها) است. مجموع قطعه‌ها در هر سایت نباید از ظرفیت سایت تجاوز کند، در حالی که فرآیند توزیع باید ارتباط (تشابه) بین قطعه‌ها را در هر سایت حفظ کند. هدف توزیع داده بزرگ برای سایت‌های اصلی با مقدار محدود شده ظرفیت با بررسی تشابه داده توزیع شده در هر سایت است. برای حل این مسئله، GNP برای استخراج قوانین از داده بزرگ با بررسی ویژگی‌های (دامنه مقادیر) هر صفت در پایگاه داده استفاده می‌شود. روش پیشنهادی، روش تصادفی جزئی استخراج قوانین را در GNP برای کشف الگوی تکراری فراوان‌ترین الگوها در پایگاه داده برای بهبود الگوریتم خوشه‌بندی، به خصوص در مسائل با داده بزرگ، ارائه داده است. مفهوم KP برای مسئله ظرفیت ذخیره سازی بکار می‌رود و برنامه نویسی پویای استاندارد برای توزیع قوانین برای هر سایت با بررسی تشابه (ارزش) و حجم داده (وزن) مربوط به هر قانون برای تطبیق ظرفیت سایت استفاده می‌شود. از نتایج شبیه‌سازی، بدیهی است که روش پیشنهادی مزایایی را برروی الگوریتم خوشه‌بندی معمولی نشان می‌دهد، بنابراین، روش پیشنهادی روش خوشه‌بندی جدیدی را یا مسئله ظرفیت ذخیره سازی اضافی ارائه می‌دهد.
1-مقدمه
سیستم مدیریت پایگاه داده توزیع شده (DDBMS) می‌تواند راه‌حلی برای سیستم‌های اطلاعاتی مقیاس بزرگ با مقدار زیاد رشد داده و دسترسی به داده باشد. یک پایگاه داده توزیع شده (DDB) مجموعه‌ای از داده است که از لحاظ منطقی به یک سیستم تعلق دارند اما برروی سایت‌های شبکه کامپیوتری توسعه یافته‌اند (شکل1). یک DDBM سپس به عنوان یک سیستم نرم‌افزاری تعریف می‌شود که اجازه مدیریت DDB و توزیع داده بین پایگاه‌داده‌ها و شفافیت نرم‌افزار برای کاربران دیگر را صادر می‌کند(Bhuyar، Gawande، و Deshmuk، 2012؛ Zilio و همکاران، 2004)....