Search

At present many algorithms for mining association rules have been proposed, but most of them are only suitable for discovering specific frequent itemsets from characteristic data sets on the appointed environments, namely, these algorithms are not general enough when mining association rules. In this paper, a general framework based on composite granules for mining association rules is proposed, which is a general data mining model without appointed restriction from frequent itemsets, data sets or mining environments and so on. An iterative method is efficiently applied to the general mining framework for discovering frequent itemsets, which adopts repartitioning frequent attributes to iteratively reconstruct the mixed radix information system for reducing a relational database. In order that the framework for discovering frequent itemsets has a generality, in discussing and establishing the general mining framework, this paper introduces a novel conception and data model, namely, a mixed radix information system is applied to describe a relational database, and a composite granules is used to build a specific relationship between an information system and a mixed radix information system, which can hold the same extension and simultaneously exist in two different information systems. The mixed radix information system can help the general framework to reduce information data and improve the performance of the framework for generating frequent itemsets. The composite granules model can create a relationship between an information granule and a digital information granule, and help the framework for computing the support to avoid reading the database repeatedly or using the complex data structure. Finally, a new taxonomy is presented to verify the generality and the high efficiency of the mining framework and all the experiments based on the taxonomy indicate that the general mining framework has the required generality, and the performance of the framework is better than these classical mining frameworks. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new cardinality constraint: Ordered Distribute. Given a set of variables, this constraint limits for each value v the number of times v or any value greater than v is taken. It extends the global cardinality constraint, that constrains only the number of times a value v is taken by a set of variables and does not consider at the same time the occurrences of all the values greater than v. We design an algorithm for achieving generalized arc-consistency on Ordered Distribute, with a time complexity linear in the sum of the number of variables and the number of values in the union of their domains. In addition, we give some experiments showing the advantage of this new constraint for problems where values represent levels whose overrunning has to be under control. Finally, we present three extensions of our constraint that can be particularly useful in practice. [ABSTRACT FROM AUTHOR]

Because of the inherent computational complexity, mining the complete frequent item-set in dense datasets remains to be a challenging task. Mining Maximal Frequent Item-set (MFI) is an alternative to address the problem. Set-Enumeration Tree (SET) is a common data structure used in several MFI mining algorithms. For this kind of algorithm, the process of mining MFI's can also be viewed as the process of searching in set-enumeration tree. To reduce the search space, in this paper, a new algorithm, Index-MaxMiner, for mining MFI is proposed by employing a hybrid search strategy blending breadth-first and depth-first. Firstly, the index array is proposed, and based on bitmap, an algorithm for computing index array is presented. By adding subsume index to frequent items, Index-MaxMiner discovers the candidate MFI's using breadth-first search at one time, which avoids first-level nodes that would not participate in the answer set and reduces drastically the number of candidate itemsets. Then, for candidate MFI's, depth-first search strategy is used to generate all MFI's. Thus, the jumping search in SET is implemented, and the search space is reduced greatly. The experimental results show that the proposed algorithm is efficient especially for dense datasets. [ABSTRACT FROM AUTHOR]

This paper addresses a novel sentence reduction algorithm based on a decision tree model in which semantic information is used to enhance the accuracy of sentence reduction. The proposed algorithm is able to deal with the changeable order problem in sentence reduction. Furthermore, the use of decision list to solve the fragment problem in sentence reduction based decision tree model is also discussed. Our experimental results show an improvement when compared with earlier methods. [ABSTRACT FROM AUTHOR]

Propositional satisfiability (SAT) problem is fundamental to the theory of NP-completeness. Indeed, using the concept of "polynomial-time reducibility" all NP-complete problems can be polynomially reduced to SAT. Thus, any new technique for satisfiability problems will lead to general approaches for thousands of hard combinatorial problems. In this paper, we introduce the incremental propositional satisfiability problem that consists of maintaining the satisfiability of a propositional formula anytime a conjunction of new clauses is added. More precisely, the goal here is to check whether a solution to a SAT problem continues to be a solution anytime a new set of clauses is added and if not, whether the solution can be modified efficiently to satisfy the old formula and the new clauses. We will study the applicability of systematic and approximation methods for solving incremental SAT problems. The systematic method is based on the branch and bound technique while the approximation methods rely on stochastic local search and genetic algorithms. Experimental tests, conducted on randomly generated SAT instances, demonstrate the efficiency in time of the approximation methods over the branch and bound algorithm. However these approximation methods do not always guarantee the completeness of the solution returned. We show that a method we propose that uses non systematic search in a limited form together with branch and bound has the best compromise, in practice, between time and quality of the solution returned (success ratio). [ABSTRACT FROM AUTHOR]