Development Of Convex Hull Finding Algorithm In Undirected Graphs With Its Application In Graphical Models

With the development of science and technology,high-dimensional and complex data appear more and more frequently in bioinformatics,finance and statistics.In front of this kind of data,as a perfect combination of probability theory and graph theory,probabilistic graphical model theory came into being,it has become a new effective tool to deal with high-dimensional complex data.The efficiency of statistical analysis is greatly improved by using the modular characteristics of graphical models.In statistical inference,collapsibility is an important method for reducing the model complexity.It means that the solution of global problems in graphical models can be transformed into local problems by collapsing over some variables of uninterest.Therefore,by reducing dimension we can do research and statistical analysis on marginal models,which are called sub-models.This can greatly reduce the requirements of variables and data volume in a certain degree and also improve the efficiency of statistical analysis.Collapsibility of graphical models is closely related to convex hull in computational graphics,given a set of points on a two-dimensional plane,a convex hull is a convex polygon formed by connecting the outermost points,which can contain all the points in the set.In graphical models,given a variable set of A,how to find the minimum variable set of B so that A(?)B and satisfies that the original graphical models can be collapsed onto the sub-model induced by the variable set B.This variable set B is called the convex hull of variable set A.At present,the equivalence between minimum collapsibility subsets of a graphical model and convex hull containing the set of concerned points has been established.From this equivalence,we can find the minimum subset of collapsibility for graphical model.This thesis focuses on development of related algorithms and integrate them to solve the collapsibility problem of graphical models.Additionally,we also survey the theoretical basis of collapsibility in graphical models and some important known researches.On the basis of previous studies,the algorithms of MCS,MCS-M and finding Convex Hull are developed and integrated.During the development process,we adopt the popular Python language,and the development tool adopts Pycharm software,and Numpy,Maplotlib,Xlrd,Networkx and other built-in toolkits to read the data set of graphical models and visualization of model structures.Finally,the research and development results are applied to two practical problems in graphical models,and the results are verified valid and efficient by these two examples.The program is not only suitable for finding the minimum collapsible set in Markov network,but also suitable for finding the minimum collapsible set of the concerned variable set in Bayesian network.