Subjects: Computer Science >> Integration Theory of Computer Science submitted time 2022-05-18 Cooperative journals: 《计算机应用研究》
Abstract： The warning propagation algorithm, as a basic information propagation algorithm, is very effective in solving the satisfiability problem when it converges. However, when the structure of factor graph is more complex, the algorithm often does not converge, resulting in solving failure. In order to give a theoretical explanation for this phenomenon, and to effectively analyze the convergence of warning propagation algorithm, which using tree decomposition method to constructed the tree width measurement model of factor graph corresponding to propositional formula, and calculated the tree width satisfying the random instance. The relationship between tree width and convergence of warning propagation algorithm is established, and the convergence judgment condition of warning propagation algorithm based on tree width is given. The experimental results show that this method is effective, and it is very important to analyze the convergence of other information transmission algorithms.
Subjects: Computer Science >> Integration Theory of Computer Science submitted time 2022-04-07 Cooperative journals: 《计算机应用研究》
Abstract： The Max-SAT problem is an optimized version of the SAT problem. The goal is to find a set of variable assignments in a given set of clauses so that the maximum number of clauses is satisfied. This problem is a typical NP-hard problem. With the in-depth development of big data and artificial intelligence, the original algorithms in the past are no longer applicable. Designing a new solution algorithm or optimizing the existing solution algorithm is the current research hotspot. Aiming at the limitations of the information dissemination algorithm for solving the random Max-3-SAT problem, this paper proposes a warning dissemination algorithm based on the calculation of variable weights. Combined with the random walk algorithm, a new algorithm WWP+WalkSAT is formed, which is solved by improvement The limitation of, it is better to get a set of effective initial solutions, thereby improving the local search ability of the algorithm. Using some benchmark examples of the Max-SAT International Competition in 2016, the WWP+WalkSAT algorithm and 8 local search algorithms are used for accuracy comparison experiments. The experimental results show that the WWP + walksat algorithm has good performance.
Subjects: Computer Science >> Integration Theory of Computer Science submitted time 2020-09-28 Cooperative journals: 《计算机应用研究》
Abstract： Convergence is an important index for evaluating the performance of information propagation algorithms. When the information propagation algorithm solves the satisfiability problem, the structural characteristics of the proposition formula affect the convergence of the algorithm, propositional formulas with complex structures do not always converge on information propagation algorithms. For this phenomenon, there are few systematic theoretical explanations. As the basic model of the information propagation algorithm, the warning propagation algorithm (WP) , analyzing the convergence of the WP algorithm is of great significance to study the convergence of other information propagation algorithms. With the help of structural entropy methods and techniques, people proposed a structural entropy model of propositional formula and its measurement method. This paper calculated the structural entropy of a random satisfiability instance, analyze the relationship between the convergence of the WP algorithm and the structural entropy, and give the judgment condition of convergence of WP algorithm. Through experimental analysis, this method is effective and feasible.
Subjects: Computer Science >> Integration Theory of Computer Science submitted time 2020-09-28 Cooperative journals: 《计算机应用研究》
Abstract： High utility pattern mining (HUPM) is an emerging topic in recent years. The concept of utility provides greater flexibility for analysts to mine related itemsets, taking the user's needs as a starting point, measuring weights, values, quantities, and other information. This article provides a comprehensive and structured survey of the most advanced methods of HUPM by analyzing them. First of all, by introducing the relevant concepts and formulas of HUPM and giving application examples, this paper has a deeper understanding of HUPM. Classify the most common and advanced key technologies used to mine different types of HUPM, including Apriori-based, tree-based, list-based, projection-based, vertical/horizontal data-based, index-based, and more. This paper provides a comprehensive survey of the uses, advantages and disadvantages of existing key technologies. Then, because the static data is difficult to meet the actual needs, this paper summarizes the HUPM methods applied on the data stream, mainly based on the incremental methods, based on the sliding window model methods, based on the time decay model methods, based on the landmark model methods. Finally, this paper gives the shortcomings of the current technologies and the direction of improvement, and proposes new research methods in a targeted manner.
Subjects: Computer Science >> Integration Theory of Computer Science submitted time 2019-04-01 Cooperative journals: 《计算机应用研究》
Abstract： It is very effective when the message passing algorithm solves the satisfiability problem, while the most basic message passing algorithm is the warning propagation (WP) algorithm. Through the analysis of the mathematical principle of WP algorithm, it could be found that the partial variables determined by high probability are closely related to the backbone set and backdoor set of the formula. For the study of the convergence of WP-solvable formula and WP algorithm, WP-solvable formula was defined based on backbone set and backdoor set, and by using the G(n, 3, m) model and the planted distribution model to prove the convergence of the WP algorithm, the necessary and sufficient conditions for the convergence of the algorithm are given. Finally, by carrying out the numerical experiments on the model of the planted distribution formula, The results show that if a satisfiability formula WP-solvable formula, if and only if the WP algorithm has a high probability of convergence.
Subjects: Computer Science >> Integration Theory of Computer Science submitted time 2018-11-29 Cooperative journals: 《计算机应用研究》
Abstract： Currently, the trend of data stream classification algorithms is to ensemble classification algorithms. Because the ensemble algorithm provides better performance and more outstanding performance than the single classification algorithm. At the same time, it is easy to deploy in practical applications in the real world, has rapid adaptability and recovery to concept drift, and has the best classification performance in the processing of class imbalance problems. Based on the outstanding features and performance of the above ensemble classification algorithm, it has won extensive research by scholars at home and abroad. This paper introduces the ensemble classification algorithm at home and abroad in detail. The two parts of the ensemble classification algorithm (base classifier combination and dynamic update ensemble model) are reviewed in detail, and the advantages and disadvantages of different integration algorithms, comparison algorithm and experimental data set are clearly distinguished. The paper proposed further research Directions and considerations.
Hits
Hits
Downloads
Comment