Title page for ETD etd-1204101-184456

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
  • 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
This 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.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Torvik_dis.pdf 1.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.