Type of Document Dissertation Author Torvik, Vetle Ingvald Author's Email Address vtorvik@uic.edu URN etd-1204101-184456 Title Data Mining and Knowledge Discovery: A Guided Approach Based on Monotone Boolean Functions Degree Doctor of Philosophy (Ph.D.) Department Engineering Science (Interdepartmental Program) Advisory Committee

Advisor Name Title Evangelos Triantaphyllou Committee Chair Jerry L. Trahan Committee Member Jianhua Chen Committee Member Lynn R. LaMotte Committee Member T. Warren Liao Committee Member Manoj K. Chari Dean's Representative Keywords

- partially ordered sets (posets)
- membership queries
- knowledge discovery
- average query complexity
- guided inference
- record linkage
- data mining
- Hansel chains
- sequential experiment design
- maximum likelihood
- breast cancer diagnosis
- isomorphism
- unequal probability sampling
- branch and bound
- monotone Boolean functions
- incremental maximum flow algorithm
- dynamic programming
Date of Defense 2001-10-30 Availability unrestricted AbstractThis dissertation deals with an important problem in Data Mining and Knowledge Discovery (DM & KD), and Information Technology (IT) in general. It addresses the problem of efficiently learning monotone Boolean functions via membership queries to oracles. The monotone Boolean function can be thought of as a phenomenon, such as breast cancer or a computer crash, together with a set of predictor variables. The oracle can be thought of as an entity that knows the underlying monotone Boolean function, and provides a Boolean response to each query. In practice, it may take the shape of a human expert, or it may be the outcome of performing tasks such as running experiments or searching large databases.Monotone Boolean functions have a general knowledge representation power and are inherently frequent in applications. A key goal of this dissertation is to demonstrate the wide spectrum of important real-life applications that can be analyzed by using the new proposed computational approaches. The applications of breast cancer diagnosis, computer crashing, college acceptance policies, and record linkage in databases are here used to demonstrate this point and illustrate the algorithmic details. Monotone Boolean functions have the added benefit of being intuitive. This property is perhaps the most important in learning environments, especially when human interaction is involved, since people tend to make better use of knowledge they can easily interpret, understand, validate, and remember.

The main goal of this dissertation is to design new algorithms that can minimize the average number of queries used to completely reconstruct monotone Boolean functions defined on a finite set of vectors V = {0,1}^n. The optimal query selections are found via a recursive algorithm in exponential time (in the size of V). The optimality conditions are then summarized in the simple form of evaluative criteria, which are near optimal and only take polynomial time to compute. Extensive unbiased empirical results show that the evaluative criterion approach is far superior to any of the existing methods. In fact, the reduction in average number of queries increases exponentially with the number of variables n, and faster than exponentially with the oracle's error rate.

Files

Filename Size Approximate Download Time (Hours:Minutes:Seconds)

28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access Torvik_dis.pdf1.83 Mb 00:08:27 00:04:20 00:03:48 00:01:54 00:00:09

Browse All Available ETDs by
( Author |
Department )

If you have questions or technical problems, please Contact LSU-ETD Support.