With the popularity of uncertain data, queries over uncertain graphs have become a hot topic in the database community. As one of the important queries, the shortest path query over an uncertain graph has attracted mu...With the popularity of uncertain data, queries over uncertain graphs have become a hot topic in the database community. As one of the important queries, the shortest path query over an uncertain graph has attracted much attention of researchers due to its wide applications. Although there are some e？cient solutions addressing this problem, all existing models ignore an important property existing in uncertain graphs： the correlation among the edges sharing the same vertex. In this paper, we apply Markov network to model the hidden correlation in uncertain graphs and compute the shortest path. Unfortunately, calculating the shortest path and corresponding probability over uncertain graphs modeled by Markov networks is a #P-hard problem. Thus, we propose a filtering-and-verification framework to accelerate the queries. In the filtering phase, we design a probabilistic shortest path index based on vertex cuts and blocks of a graph. We find a series of upper bounds and prune the vertices and edges whose upper bounds of the shortest path probability are lower than the threshold. By carefully picking up the blocks and vertex cuts, the index is optimized to have the maximum pruning capability, so that we can filter a large number of vertices which make no contribution to the final shortest path query results. In the verification phase, we develop an e？cient sampling algorithm to determine the final query answers. Finally, we verify the e？ciency and effectiveness of our solutions with extensive experiments.展开更多
Jaundice is a common and complex clinical symptom potentially occurring in hepatology, general surgery, pediatrics, infectious diseases, gynecology, and obstetrics, and it is faidy difficult to distinguish the cause o...Jaundice is a common and complex clinical symptom potentially occurring in hepatology, general surgery, pediatrics, infectious diseases, gynecology, and obstetrics, and it is faidy difficult to distinguish the cause of jaundice in clinical practice, especially for general practitioners in less developed regions. With collaboration between physicians and artificial intelligence engineers, a comprehensive knowledge base relevant to jaundice was created based on demographic information, symptoms, physical signs, laboratory tests, imaging diagnosis, medical histories, and risk factors. Then a diagnostic modeling and reasoning system using the dynamic uncertain causality graph was proposed. A modularized modeling scheme was presented to reduce the complexity of model construction, providing multiple perspectives and arbitrary granularity for disease causality representations. A ＂chaining＂ inference algorithm and weighted logic operation mechanism were employed to guarantee the exactness and efficiency of diagnostic rea- soning under situations of incomplete and uncertain information. Moreover, the causal interactions among diseases and symptoms intuitively demonstrated the reasoning process in a graphical manner. Verification was performed using 203 randomly pooled clinical cases, and the accuracy was 99.01% and 84.73%, respectively, with or without laboratory tests in the model. The solutions were more explicable and convincing than common methods such as Bayesian Networks, further increasing the objectivity of clinical decision-making. The promising results indicated that our model could be potentially used in intelligent diagnosis and help decrease public health expenditure.展开更多
Fault diagnostics is important for safe operation of nuclear power plants(NPPs). In recent years, data-driven approaches have been proposed and implemented to tackle the problem, e.g., neural networks, fuzzy and neuro...Fault diagnostics is important for safe operation of nuclear power plants(NPPs). In recent years, data-driven approaches have been proposed and implemented to tackle the problem, e.g., neural networks, fuzzy and neurofuzzy approaches, support vector machine, K-nearest neighbor classifiers and inference methodologies. Among these methods, dynamic uncertain causality graph(DUCG)has been proved effective in many practical cases. However, the causal graph construction behind the DUCG is complicate and, in many cases, results redundant on the symptoms needed to correctly classify the fault. In this paper, we propose a method to simplify causal graph construction in an automatic way. The method consists in transforming the expert knowledge-based DCUG into a fuzzy decision tree(FDT) by extracting from the DUCG a fuzzy rule base that resumes the used symptoms at the basis of the FDT. Genetic algorithm(GA) is, then, used for the optimization of the FDT, by performing a wrapper search around the FDT: the set of symptoms selected during the iterative search are taken as the best set of symptoms for the diagnosis of the faults that can occur in the system. The effectiveness of the approach is shown with respect to a DUCG model initially built to diagnose 23 faults originally using 262 symptoms of Unit-1 in the Ningde NPP of the China Guangdong Nuclear Power Corporation. The results show that the FDT, with GA-optimized symptoms and diagnosis strategy, can drive the construction of DUCG and lower the computational burden without loss of accuracy in diagnosis.展开更多
基金This work is supported in part by the National Natural Science Foundation of China under Grant Nos. 61332006, U1401256, 61328202, 61173029, the Fundamental Research Funds for the Central Universities of China under Grant No. N130504006, the Hong Kong RGC Project under Grant No. N_HKUST637/13, the National Basic Research 973 Program of China under Grant No. 2014CB340300, Microsoft Research Asia Gift Grant and Google Faculty Award 2013.
文摘With the popularity of uncertain data, queries over uncertain graphs have become a hot topic in the database community. As one of the important queries, the shortest path query over an uncertain graph has attracted much attention of researchers due to its wide applications. Although there are some e？cient solutions addressing this problem, all existing models ignore an important property existing in uncertain graphs： the correlation among the edges sharing the same vertex. In this paper, we apply Markov network to model the hidden correlation in uncertain graphs and compute the shortest path. Unfortunately, calculating the shortest path and corresponding probability over uncertain graphs modeled by Markov networks is a #P-hard problem. Thus, we propose a filtering-and-verification framework to accelerate the queries. In the filtering phase, we design a probabilistic shortest path index based on vertex cuts and blocks of a graph. We find a series of upper bounds and prune the vertices and edges whose upper bounds of the shortest path probability are lower than the threshold. By carefully picking up the blocks and vertex cuts, the index is optimized to have the maximum pruning capability, so that we can filter a large number of vertices which make no contribution to the final shortest path query results. In the verification phase, we develop an e？cient sampling algorithm to determine the final query answers. Finally, we verify the e？ciency and effectiveness of our solutions with extensive experiments.
基金supported by the Medical and Health Research Program of Zhejiang Province(No.2015KYB128)the Zhejiang Provincial Natural Science Foundation(No.LQ15H030004),China
文摘Jaundice is a common and complex clinical symptom potentially occurring in hepatology, general surgery, pediatrics, infectious diseases, gynecology, and obstetrics, and it is faidy difficult to distinguish the cause of jaundice in clinical practice, especially for general practitioners in less developed regions. With collaboration between physicians and artificial intelligence engineers, a comprehensive knowledge base relevant to jaundice was created based on demographic information, symptoms, physical signs, laboratory tests, imaging diagnosis, medical histories, and risk factors. Then a diagnostic modeling and reasoning system using the dynamic uncertain causality graph was proposed. A modularized modeling scheme was presented to reduce the complexity of model construction, providing multiple perspectives and arbitrary granularity for disease causality representations. A ＂chaining＂ inference algorithm and weighted logic operation mechanism were employed to guarantee the exactness and efficiency of diagnostic rea- soning under situations of incomplete and uncertain information. Moreover, the causal interactions among diseases and symptoms intuitively demonstrated the reasoning process in a graphical manner. Verification was performed using 203 randomly pooled clinical cases, and the accuracy was 99.01% and 84.73%, respectively, with or without laboratory tests in the model. The solutions were more explicable and convincing than common methods such as Bayesian Networks, further increasing the objectivity of clinical decision-making. The promising results indicated that our model could be potentially used in intelligent diagnosis and help decrease public health expenditure.
文摘Fault diagnostics is important for safe operation of nuclear power plants(NPPs). In recent years, data-driven approaches have been proposed and implemented to tackle the problem, e.g., neural networks, fuzzy and neurofuzzy approaches, support vector machine, K-nearest neighbor classifiers and inference methodologies. Among these methods, dynamic uncertain causality graph(DUCG)has been proved effective in many practical cases. However, the causal graph construction behind the DUCG is complicate and, in many cases, results redundant on the symptoms needed to correctly classify the fault. In this paper, we propose a method to simplify causal graph construction in an automatic way. The method consists in transforming the expert knowledge-based DCUG into a fuzzy decision tree(FDT) by extracting from the DUCG a fuzzy rule base that resumes the used symptoms at the basis of the FDT. Genetic algorithm(GA) is, then, used for the optimization of the FDT, by performing a wrapper search around the FDT: the set of symptoms selected during the iterative search are taken as the best set of symptoms for the diagnosis of the faults that can occur in the system. The effectiveness of the approach is shown with respect to a DUCG model initially built to diagnose 23 faults originally using 262 symptoms of Unit-1 in the Ningde NPP of the China Guangdong Nuclear Power Corporation. The results show that the FDT, with GA-optimized symptoms and diagnosis strategy, can drive the construction of DUCG and lower the computational burden without loss of accuracy in diagnosis.
