Combination of genetic network programming and knapsack problem to support record clustering on distributed databases

作     者：Wedashwara, Wirarama Mabu, Shingo Obayashi, Masanao Kuremoto, Takashi 

作者机构：Yamaguchi Univ Grad Sch Sci & Engn Ube Yamaguchi 7558611 Japan 

出 版 物：《EXPERT SYSTEMS WITH APPLICATIONS》 (专家系统及其应用)

年 卷 期：2016年第46卷

页      面：15-23页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Grants-in-Aid for Scientific Research [25330287  26330254] Funding Source: KAKEN 

主　　题：Genetic network programming Database clustering Knapsack problem Record clustering 

摘      要：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. (C) 2015 Elsevier Ltd. All rights reserved.