About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
ICDM 2001
Conference paper
Mining mutually dependent patterns
Abstract
In some domains, such as isolating problems in computer networks and discovering stock market irregularities, there is more interest in patterns consisting of infrequent, but highly correlated items rather than patterns that occur frequently (as denned by minsup, the minimum support level). Herein, we describe the m-pattern, a new pattern that is denned in terms of minp, the minimum probability of mutual dependence of items in the pattern. We show that all infrequent m-pattern can be discovered by an efficient algorithm that makes use of: (a) a linear algorithm to qualify an m-pattern; (b) an effective technique for candidate pruning based on a necessary condition for the presence of an m-pattern; and (c) a level-wise search for m-pattern discovery (which is possible because m-patterns are downward closed). Further, we consider frequent m-patterns, which are denned in terms of both minp and minsup. Using synthetic data, we study the scalability of our algorithm. Then, we apply our algorithm to data from a production computer network both to show the m-patterns present and to contrast with frequent patterns. We show that when minp= 0, our algorithm is equivalent to finding frequent patterns. However, with a larger minp, our algorithm yields a modest number of highly correlated items, which makes it possible to mine for infrequent but highly correlated itemsets. To date, many actionable m-patterns have been discovered in production systems. © 2001 IEEE.