13141933
Read-Twice DNF Formulas are Properly Learnable
We show that read-twice DNF formulas-Boolean formulas in disjunctive normal form in which each variable appears at most twice-are exactly and properly learnable in polynomial time. Our algorithm uses membership queries and proper equivalence queries and is based on a simple, new characterization of minimal read-twice DNF formulas. The algorithm improves on earlier results of Hancock and Aizenstein and Pitt which showed that read-twice DNF formulas are learnable using more powerful equivalence queries, i.e., where the hypotheses could be arbitrary DNF formulas. We also improve on the time-complexity of these earlier algorithms. Other results which may be of independent interest outside of learning follow directly from this paper. Specifically, we show that read-twice DNF formulas can be tested for equivalence in polynomial time and that the smallest read-twice formula equivalent to a given one can be found in polynomial time.
1363140
Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number
Partially ordered sets of small width and graphs of small Dilworth number have many interesting properties and have been well studied. Here we show that recognition of such orders and graphs can be done more efficiently than by using the well-known algorithms based on bipartite matching and matrix multiplication. In particular, we show that deciding deciding if an order has width k can be done in O(kn2) time and whether a graph has Dilworth number k can be done in O(k2n2) time.For very small k we have even better results. We show that orders of width at most 3 can be recognized in O(n) time and of width at most 4 in O(nlog n).
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.
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.
353294
Dynamic Data Mining
Business information received from advanced data analysis and data mining is a critical success factor for companies wishing to maximize competitive advantage. The use of traditional tools and techniques to discover knowledge is ruthless and does not give the right information at the right time. Data mining should provide tactical insights to support the strategic directions. In this paper, we introduce a dynamic approach that uses knowledge discovered in previous episodes. The proposed approach is shown to be effective for solving problems related to the efficiency of handling database updates, accuracy of data mining results, gaining more knowledge and interpretation of the results, and performance. Our results do not depend on the approach used to generate itemsets. In our analysis, we have used an Apriori-like approach as a local procedure to generate large itemsets. We prove that the Dynamic Data Mining algorithm is correct and complete.
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.