Title An Approach For Incremental Learning Of Markov Network

Markov network is a kind of undirected graph and it is an important tool of learning and reasoning uncertain knowledge. It represents the dependency relationship among variables intuitively and simply by undirected edges. Some scholars have proposed many algorithms to get Markov network from data. But as the growth of the data, the original Markov network can not reflect the implied knowledge in the increased data.To learn knowledge and construct a Markov network from the increased data is straightforward. But we need mine the original data again while abandoning the original network and information we have got. In reality, this approach is not impractical. So we need an approach for incremental learning of Markov network based on the original network and new data. On the assumption that the volume of the new data is much smaller than the original data, this paper proposes an incremental Markov network updating algorithm (iMU).The approach makes full use of existing network and information and pays attention to the incremental data mining and then updates the original network structure partly. In this approach we updates the original network in two steps:nodes updating and edges updating. In the process of nodes updating, we use incremental Apriori algorithm to get the new frequent itemsets.And then we add and delete nodes from the original network corresponding to the new1-frequent itemset. In the process of edges updating, to control the scale of the edges to test, we give a concept of the substructure most need to update.We do conditional independency test between the nodes in th the substructure and add or delete relevant edges. If there are nodes to delete, we delete the edges related in the process of nodes updating. If there are nodes to add, we first find these maximum sets including added nodes and the maximum sets containing common nodes with these former sets.Then we do conditional independency tests between every added node and the relevant node in the sets we just found. And then we add some edges.After the nodes updating and edges updating, we get the Markov network which reflects the knowledge implied in the increased data. Finally, we make contrast experiment and prove that the algorithm is correct and practical.