Support measures for graph data* |
| |
Authors: | N Vanetik S E Shimony E Gudes |
| |
Affiliation: | (1) Department of Computer Science, Ben-Gurion University of the Negev, 84105 Beer-Sheva, Israel |
| |
Abstract: | The concept of support is central to data mining. While the definition of support in transaction databases is intuitive and
simple, that is not the case in graph datasets and databases. Most mining algorithms require the support of a pattern to be
no greater than that of its subpatterns, a property called anti-monotonicity, or admissibility. This paper examines the requirements for admissibility of a support measure. Support measures for mining
graphs are usually based on the notion of an instance graph---a graph representing all the instances of the pattern in a database
and their intersection properties. Necessary and sufficient conditions for support measure admissibility, based on operations
on instance graphs, are developed and proved. The sufficient conditions are used to prove admissibility of one support measure—the
size of the independent set in the instance graph. Conversely, the necessary conditions are used to quickly show that some
other support measures, such as weighted count of instances, are not admissible.
*Partially supported by the KITE consortium under contract to the Israeli Ministry of Trade and Industry, and by the Paul Ivanier
Center for Robotics and Production Management. |
| |
Keywords: | Data mining Graph mining Support measures |
本文献已被 SpringerLink 等数据库收录! |
|