Research On CP-nets Structure Learning Based On Constraints With Heuristics

CP-nets(Conditional Preference nets)are intuitive graph model used to describe preferences.It is one of the powerful tools for studying uncertain relations,and its learning problem has become a research hotspot.However,when the data scale become larger and the number of transaction attributes increases,the number of CP-nets structure obtained increases exponentially.Moreover,in the structure learning of CP-nets,the results obtained are easy to fall into local solutions,and it is difficult to reach the global optimum.Based on the above problems,this paper proposes a method of shortest path learning based on threshold constraints and a simulated annealing learning method based on MMPC to try to solve the complex structure problem caused by the large number of attributes,and the learning result is easy to fall into the local solution problem.The research content of this paper mainly includes the following two aspects.(1)Research on CP-nets structure of shortest path learning based on threshold constraint.In order to solve the complex structure problem caused by multiple attributes,this paper transforms the structure learning process of CP-nets into the shortest path solving problem.The idea is to express the structure learning problem as a search problem in a sequence diagram,the path between the start node and the target node in the graph is regarded as the path,and the shortest path is the path with the least cost among the paths.In the path search process,the threshold constraint method is used to narrow the search range.After obtaining the shortest path between each node,each path is combined into the corresponding CP-nets structure.The main tasks of the learning process include design constraint methods and search strategies.Restricting the search of the sequence diagram can narrow the search scope and effectively reduce the search time.Guide the search process through heuristic algorithms,obtain the shortest path between nodes,and learn the CP-nets structure.Through experimental verification,this method is suitable for large-scale data,reduces the time overhead of the learning process,and can obtain accurate CP-nets structure.(2)Research on CP-nets structure learning of simulated annealing based on MMPC.In order to solve the problem that the CP-nets hybrid learning algorithm may cause the results to fall into a local solution,this paper design a simulated annealing algorithm based on MMPC for structure learning of CP-nets.Firstly,using the MMPC algorithm to obtain CPC(candidate parent-child nodes),and then designing a search algorithm to perform a score search to obtain the optimal CP-nets structure.In the search stage,based on the idea of simulated annealing,a result that is worse than the current one is accepted with a certain probability to avoid falling into a local solution.Through experimental verification,it is demonstrated that the algorithm can avoid falling into the local solution with a certain probability,and can obtain accurate CP-nets structure.In summary,the shortest path CP-nets learning based on threshold constraints improves the search efficiency by constraining the search space,and is suitable for large-scale data with a large number of attributes.Simulated annealing based on MMPC learns CP-nets which can avoid the result from falling into a local solution with a certain probability.