The knowledge base partitioning problem: Mathematical formulation and heuristic clustering

摘要

Allocation of production rules among several partitions in a knowledge base can shorten the compilation and execution of expert systems applications and facilitate their verification, validation and maintenance. The problem of allocation of rules or groups of rules among partitions of limited size while minimizing the sum of inter-partition connections is formulated as a 0–1 integer programming problem with a quadratic objective function. Since this type of problems is NP-complete, a clustering algorithm based on the nearest neighbor heuristic is proposed.