7141965
Visualizing association mining results through hierarchical clusters
We propose a new methodology for visualizing association mining results. Inter-item distances are computed from combinations of itemset supports. The new distances retain a simple pairwise structure, and are consistent with important frequently occurring itemsets. Thus standard tools of visualization, e.g. hierarchical clustering dendrograms can still be applied, while the distance information upon which they are based is richer. Our approach is applicable to general association mining applications, as well as applications involving information spaces modeled by directed graphs, e.g. the Web. In the context of collections of hypertext documents, the inter-document distances capture the information inherent in a collection's link structure, a form of link mining. We demonstrate our methodology with document sets extracted from the Science Citation Index, applying a metric that measures consistency between clusters and frequent itemsets.
62608981
On the delusiveness of adopting a common space for modeling IR objects: are queries documents?
Many authors, who adopt the vector space model, take the view that documents, terms, queries, etc., are all elements within the same (conceptual) space. This view seems to be a natural one, given that documents and queries have the same vector notation. We show, however, that the structure of the query space can be very different from that of the document space. To this end, concepts like preference, similarity, term independence, and linearity, both in the document space and in the query space, are discussed. Our conclusion is that a more realistic and complete view of IR is obtained if we do not consider documents and queries to be elements of the same space. This conclusion implies that certain restrictions usually applied in the design of an IR system are obviated. For example, the retrieval function need not be restricted to the ones that have the possibility to be interpreted as a similarity measure. © 1993 John Wiley & Sons, Inc.
10429195
Monotone term decision lists
We introduce a new representation class of Boolean functions ? monotone term decision lists ? which combines compact representation size with tractability of essential operations. We present many properties of the class which make it an attractive alternative to traditional universal representation classes such as DNF formulas or decision trees. We study the learnability of monotone term decision lists in the exact model of equivalence and membership queries. We show that, for any constant k?0, k-term monotone decision lists are exactly and properly learnable with nO(k) membership queries in nO(k3) time. We also show that n?(k) membership queries are necessary for exact learning. In contrast, both k-term monotone decision lists (k?2) and general monotone term decision lists are not learnable with equivalence queries alone. We also show that a subclass of monotone term decision lists (disj-MDL) is learnable with equivalence and membership queries, while neither type of query alone suffices.
14710291
Learning Monotone Term Decision Lists
We study the learnability of monotone term decision lists in the exact model of equivalence and membership queries. We show that, for any constant k≥0, k-term monotone decision lists are exactly and properly learnable with nO(k) membership queries in O(nk3) time. We also show nΩ(k) membership queries are necessary for exact learning. In contrast, both k-term monotone decision lists (k≥2) and general monotone decision lists are not learnable with equivalence queries alone.
11434959
Exact Learning when Irrelevant Variables Abound
We prove the following results. Any Boolean function of O(log n) relevant variables can be exactly learned with a set of non-adaptive membership queries alone and a minimum sized decision tree representation of the function constructed, in polynomial time. In contrast, such a function cannot be exactly learned with equivalence queries alone using general decision trees and other representation classes as hypotheses. 
 
Our results imply others which may be of independent interest. We show that truth-table minimization of decision trees can be done in polynomial time, complementing the well-known result of Masek that truth-table minimization of DNF formulas is NP-hard. The proofs of our negative results show that general decision trees and related representations are not learnable in polynomial time using equivalence queries alone, confirming a folklore theorem.