Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-08-06
2001-09-18
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06292797
ABSTRACT:
BACKGROUND INFORMATION
This invention relates to a method for organizing, updating and helping determine which “patterns” or associations amongst data in a database are of interest to a user of the database.
One of the central and most basic problems in the field of “knowledge discovery” is that of determining which patterns or associations amongst data in a database are of interest to a user of the database. As the literature has stated (see, e.g., G. Piatetsky-Shapiro and C. J. Matheus, “The Interestingness of Deviations,”
Proceedings of the AAAI
-94
Workshop on Knowledge Discovery in Databases
, 25-36, 1994) one way of gauging a user's interest in a pattern, particularly in a business context, is to determine whether and how a user wishes to act on a pattern. Patterns that satisfy this criterion are called “actionable” patterns. G. Piatetsky-Shapiro and C. J. Matheus, “
The Interestingness of Deviations,” Proceedings of the AAAI
-94
Workshop on Knowledge Discovery in Databases
, 25-36, 1994; A. Silberschatz and A. Tuzhilin, “On subjective measures of Interestingness in knowledge discovery,”
Proceedings of the First International Conference on Knowledge Discovery and Data Mining
, Montreal, Canada, August, 1995.
For example, consider a retail outlet or supermarket which wants to maximize its profit. In order to do so, it may want to take certain promotional, advertising or inventory stocking measures in response to certain facts (i.e., reflected as patterns or associations in the supermarket's database). For example, if a supermarket's database reflects that more of its customers now have children age six or under, and the database also reflects the fact that such customers in the past have bought more sweets, the supermarket will likely wish to stock up on sweets. But in order for the supermarket to be able to act on such information, it must be able to: (1) specify such associations between facts of import to it (i.e, specify which patterns are of interest); (2) associate such patterns with actions the supermarket would like to take in the event such patterns (associations of facts) arise; (3) periodically check, in for example a database, to determine whether such interesting patterns have in fact arose, and if so, act upon them; and (4) periodically update and change the supermarket's database to reflect the emergence of new facts and the disappearance of old ones.
These are difficult tasks. In particular, listing all possible actions for a given application and associating these actions with various patterns may be a huge endeavor. There may be many different actions for a given application, and it can be difficult (or even impossible) to list all of them in advance. In addition, even if all possible actions are listed, the actions still have to be assigned to various groups of patterns, and this can also be an overwhelming task.
In addition, periodically checking a database to determine whether user-specified patterns of interest have in fact arose can involve large computational resources.
Thus, what is needed is a method for allowing a database user to specify a potentially large number of (1) interesting patterns in the database, (2) actions to take in response, (3) and associations between the actions and patterns in an easy, efficient and intuitive manner. The method should also provide a way to determine whether new user-specified patterns of interest have arose so that on the one hand the system (and therefore the user) knows whenever new patterns satisfying the user-specified criterion have emerged, but on the other hand, time and computational resources are spared to the greatest degree possible.
OBJECTS AND ADVANTAGES
The present invention satisfies these needs. First, it allows a user to specify an “action hierarchy” which determines a set of possible actions in an application in an hierarchical way through an action/sub-action relationship. Thus, all possible actions for a given application need not be specified individually. Rather, actions may be specified in a structured, hierarchical manner in stages, with categories of action and individual actions represented by nodes in a tree. This allows the user to specify actions in an intuitive, top-down manner.
Second, the invention incorporates useful methods already known in the art for specifying interesting patterns.
Third, the invention provides a simple method to associate such patterns with respective nodes of the “action hierarchy” described above. The easy to use file organization of modern operating systems may, for example, be used for this purpose.
Finally, the invention provides a method of automatically determining whenever changes in the database are meaningful, and altering the pattern results accordingly. With this method, emerging patterns of interest are immediately discovered, but at the same time computational resources are optimized.
Thus, one object of the present invention is to help in determining which “patterns” or associations amongst data in a database are of interest to a user of the database in an efficient, intuitive manner.
Another object of the present invention is to provide an easy to maintain system which provides a user with actions to perform based on changes in patterns of underlying facts reflected in a database.
Still another object of the present invention is to allow easy, intuitive input of the actions by a user when the system is initially set up.
Still another object of the invention is to check for such changes in patterns only when necessary, so that computational and other resources are spared.
Further objects and advantages of the present invention will become apparent upon a review of the more detailed description set forth below.
REFERENCES:
patent: 5325466 (1994-06-01), Kornacker
patent: 5572604 (1996-11-01), Simard
patent: 5581634 (1996-12-01), Heide
patent: 5586240 (1996-12-01), Khan et al.
patent: 5659743 (1997-08-01), Adams et al.
patent: 5731986 (1998-03-01), Yang
patent: 5764974 (1998-06-01), Walster et al.
patent: 5774576 (1998-06-01), Cox et al.
patent: 5794239 (1998-08-01), Walster et al.
patent: 5809499 (1998-09-01), Wong et al.
patent: 5832182 (1998-11-01), Zhang et al.
patent: 5857169 (1999-01-01), Seide
Hambaba, Intelligent Hybrid System for Data Mining, IEEE Catalog No. 96TH8177, p. 111, Mar. 1996.*
Kamber et al. Generalization and Decision Tree Induction: Efficient Classification in Data Mining, IEEE, pp. 111-120, Apr. 1997.*
Yongjlan, Data Mining, IEEE, pp. 18-20, 1997.*
Tuzhilin et al., “A Belief-Driven Discovery Framework Based on Data Monitoring and Triggering,” Center for Research on Inform Dec., 1996, pp. 1-23.
T. Imielinski et al., “DataMine: Application Programming Interface and Query Language for Database Mining”, Systems for Mining Large Databases, KDD-96, pp. 256-261.
Han et al., “DMQL: A Data Mining Query Language for Relational Databases”, Database Syetems Research Laboratory, pp. 27-33.
Agrawal et al., “Fast Discovery of Association Rules”, pp. 307-328.
Klemettinen, “Finding Interesting Rules from Large Sets of Discovered Association Rules”, University of Helsinki, pp. 1-7.
Silberchatz et al., “What Makes Patterns Interesting in Knowledge Discovery Systems”, pp. 1-13.
Shen et al., “Metaqueries for Data Mining”, pp. 375-397.
Matheus et al., “Selecting and Reporting What is Interesting: The Kefir Application to Healthcare Data”, Advances in Knowledge Discovery and Data Mining, AAAI/MIT Press, 1995, pp. 401-419.
Agrawal et al., “Mining Association Rules between Sets of Items in Large Databases”, IBM Almaden Research Center, pp. 207-216.
Silberschatz et al., “On Subjective Measure of Interestingness in Knowledge Discovery”, pp. 275-281.
Piatesky-Shapiro et al., “The Interestingness of Deviations”, AAA1-94 Workshop on Knowledge Discovery in Databases, KDD-94, pp. 25-36.
Adomavicius Gediminas
Tuzhilin Alexander S.
Baker & Botts L.L.P.
Black Thomas
Coby Frantz
New York University
LandOfFree
Method for determining actionable patterns in a database does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for determining actionable patterns in a database, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for determining actionable patterns in a database will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2454521