MINIMAL DIAGNOSIS IN ALIGNMENT INCOHERENCE REPAIR WITH DYNAMIC WEIGHTING BASED HEURISTIC - Gartina Husein, Inne
The alignment incoherence has been discussed on the ontology matching process since 2008 and now has become one of the determinants of alignment quality. Alignment is a collection of correspondences or relationships between entities of two matched ontologies. The relationship between the two entities is also called mapping. Alignment incoherence repair is done to ensure that there is no conflicting mapping in the alignment that results from the ontology matching process. The repair aims to restore the alignment condition from incoherent to coherent by eliminating some mapping in alignment. Alignment is a knowledge resource that has been widely used by practitioners and scientists in building the semantic web. Given the importance of these resources, the repair process must have the least impact on alignment, which is called minimal repair. Determining unwanted mapping is important in the repair process. This mapping will be removed from the alignment so that it can restore coherent conditions in alignment. The purpose of the repair is to improve the quality of alignment in terms of coherence. Minimal diagnosis is the activity to select and remove unwanted mapping as little as possible. This study proposes a minimal diagnosis that focuses on two things, namely the minimum number of removed mapping and minimum total confidence values of removed mappings. This study implements global techniques and optimal pathfinding algorithms with dynamic weighting based heuristic strategies in diagnosis activities. It is known that conflict mappings are collected in conflict sets so that the same mapping can appear in several conflict sets. Each mapping will be given a weight according to the number of the conflict set intersections, the highest number will be given the lowest weight and vice versa. The system will re-weight every time there is a change in the number of intersections due to diagnosis activities. This is called dynamic weighting and is the main clue in finding unwanted mapping. We have developed two methods for repairing incoherence alignment with different algorithms, namely A* and Greedy Best-first Search. These algorithms are tested on eight alignments in Conference domains. The experimental results in eight experiments showed that one of the methods built, namely Greedy Best-first Search, made a minimal repair and produced an output alignment that was 100% coherent. The A* search method that is built is superior in minimizing the number of removed mappings and total confidence values, but weak in producing a truly coherent output alignment. This study also measures the accuracy of the mapping in the output alignment. Reference alignment is an alignment made manually by experts in semantic fields and certain domain knowledge. Reference alignment becomes an alignment of expectations for measuring this accuracy ratio. The measurement results indicate an increase in the accuracy ratio of the mapping in the output alignment (or alignment after repair) compared to the alignment before repair. This indicates that there is an improvement in alignment quality after alignment incoherence repair. Additional testing is carried out in checking the existence of an unsatisfiable concept in the output alignment. The test results concluded that the release of all conflict sets would eliminate the mapping of conflicts in alignment. It was also stated that an alignment that does not contain a mapping of conflict is declared not to contain an unsatisfiable concept. In other words, resolving all conflict sets will result in a coherent output alignment. This becomes proof of the hypothesis mentioned in chapter I, namely the release of conflict sets in the alignment can improve the alignment to be coherent. The heuristic strategies based on dynamic weighting on a diagnostic scope is a contribution of this research so that improvements in alignment incoherence can be made by paying attention to the impact of changes as small as possible and improving the quality of alignment based on the precision or value ratio of precision.