José L. Balcázar, Facultad De Ciencias
Abstract. Most often, association rules are parameterized by lower bounds on their support and confidence, even though many other measures exist that evaluate the intensity of implication of a single...
Minimum-Size Bases of Association Rules (2009)
José L. Balcázar, Departament Llenguatges, Sistemes Informàtics
Abstract. We focus on confidence-bounded association rules; we model a rather practical situation in which the confidence threshold is fixed by the user, as usually happens in applications. Within...
An Association Rule Miner with Semi-Autonomic Threshold Setting ∗ (2009)
Association rule mining is well-known to depend heavily on a support threshold parameter, and on one or more thresholds for intensity of implication; among these measures, confidence is most often...
Deduction Schemes for Association Rules (2009)
José L. Balcázar, Departament Llenguatges, Sistemes Informàtics
Abstract. Several notions of redundancy exist for Association Rules. Often, these notions take the form “any dataset in which this first rule holds must obey also that second rule, therefore the...
José L. Balcázar, Albert Bifet, Antoni Lozano
Abstract Many knowledge representation mechanisms are based on treelike structures, thus symbolizing the fact that certain pieces of information are related in one sense or another. There exists a...
Redundancy, Deduction Schemes, and Minimum-Size Bases for Association Rules (2009)
José L. Balcázar, Departament Llenguatges, Sistemes Informàtics
Association rules are among the most widely employed data analysis methods in the field of Data Mining. An association rule is a form of partial implication between two sets of binary variables. In...
Query Learning and Certificates in Lattices (2008)
Arias, Marta, Balcázar, José L.
We provide an abstract version, in terms of lattices, of the Horn query learning algorithm of Angluin, Frazier, and Pitt. To validate it, we develop a proof that is independent of the propositional...
J. Siekmann, José L. Balcázar, Philip M. Long, Frank Stephan (eds, José L. Balcázar, ...
concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks....
Characterizing Implications of Injective Partial Orders ⋆ (2008)
José L. Balcázar, Gemma C. Garriga
Abstract. It is known that implications in powerset-based closure systems correspond to Horn approximations in propositional logic frameworks. Here we focus on the problem of implications between...
Closed and Maximal Tree Mining Using Natural Representations (2008)
José L. Balcázar, Albert Bifet, Antoni Lozano
Mining frequent trees is becoming an important task, with broad applications including chemical informatics, computer vision, text retrieval, bioinformatics, and Web analysis. Many link-based...
Mining Implications from Lattices of Closed Trees (2008)
José L. Balcázar, Albert Bifet, Antoni Lozano
Abstract. We propose a way of extracting high-confidence association rules from datasets consisting of unlabeled trees. The antecedents are obtained through a computation akin to a hypergraph...
Characterizing Implications of Injective Partial Orders ⋆ (2008)
José L. Balcázar, Gemma C. Garriga
Abstract. Previous work of the authors has studied a notion of implication between sets of sequences based on the conceptual structure of a Galois lattice, and also a way of representing sets of...
Computational Power of Neural Networks: A Kolmogorov Complexity Characterization (2007)
José L. Balcázar, Ricard Gavaldà, Hava T. Siegelmann
The computational power of neural networks depends on properties of the real numbers used as weights. We focus on networks restricted to compute in polynomial time, operating on boolean inputs....
Compressibility of Infinite Binary Sequences (2007)
José L. Balcázar, Ricard Gavaldà, Montserrat Hermo
It is known that infinite binary sequences of constant Kolmogorov complexity are exactly the recursive ones. Such a kind of statement no longer holds in the presence of resource bounds. Contrary to...
Yet Another Transformation Scheme for Double Recursion (2007)
A tail recursive program (with a single recursive call per case) is derived from a generic recursive program with two independent recursive calls, under no algebraic hypothesis whatsoever. The...
Mining frequent closed unordered trees through natural representations (2007)
José L. Balcázar, Albert Bifet, Antoni Lozano
Abstract. Many knowledge representation mechanisms consist of linkbased structures; they may be studied formally by means of unordered trees. Here we consider the case where labels on the nodes are...
José L. Balcázar, Albert Bifet, Antoni Lozano
Abstract Many knowledge representation mechanisms are based on treelike structures, thus symbolizing the fact that certain pieces of information are related in one sense or another. Closure-based...
Subtree testing and closed tree mining through natural representations (2007)
José L. Balcázar, Albert Bifet, Antoni Lozano
Several classical schemes exist to represent trees as strings over a fixed alphabet; these are useful in many algorithmic and conceptual studies. Our previous work has proposed a representation of...
Intersection algorithms and a closure operator on unordered trees (2006)
José L. Balcázar, Albert Bifet, Antoni Lozano
Abstract. Link-based data may be studied formally by means of unordered trees. On a dataset formed by such link-based data, a natural notion of support-based closure can be immediately defined....
Intersection algorithms and a closure operator on unordered trees (2006)
José L. Balcázar, Albert Bifet, Antoni Lozano
Abstract. Link-based data may be studied formally by means of unordered trees. On a dataset formed by such link-based data, a natural notion of support-based closure can be immediately defined....
On Horn Axiomatizations for Sequential Data (2004)
Balcázar, José L., Casas-Garriga, Gemma
We propose a notion of deterministic association rules for ordered data. We prove that our proposed rules can be formally justified by a purely logical characterization, namely, a natural notion of...
Provably fast support vector regression using random sampling, to appear (2002)
José L. Balcázar, Yang Dai, Osamu Watanabe
Support Vector Machines are a family of data analysis algorithms, based on convex Quadratic Programming. Their use has been demonstrated in classification, regression, and clustering problems. In...
Provably fast training algorithms for support vector machines (2001)
José L. Balcázar, Yang Dai, Osamu Watanabe
Support Vector Machines are a family of data analysis algorithms, based on convex Quadratic Programming. We focus on their use for classification: in that case the SVM algorithms work by maximizing...
Refining Logical Characterizations of Advice Complexity Classes (1997)
Albert Atserias, José L. Balcázar, Jordi Girona Salgado
: Numerical relations in logics are known to characterize, via the finite models of their sentences, polynomial advice nonuniform complexity classes. These are known to coincide with reduction...
Coding Complexity: The Computational Complexity of Succinct Descriptions (1996)
José L. Balcázar, Ricard Gavaldà, Osamu Watanabe
For a given set of strings, the problem of obtaining a succinct description becomes an important subject of research, related to several areas of theoretical computer science. In structural...
Coding Complexity: The Computational Complexity of Succinct Descriptions (1996)
José L. Balcázar, Ricard Gavaldà, Osamu Watanabe
. For a given set of strings, the problem of obtaining a succinct description becomes an important subject of research, related to several areas of theoretical computer science. In structural...
The Complexity of Searching Implicit Graphs (1996)
The standard complexity classes of Complexity Theory do not allow for direct classification of most of the problems solved by heuristic search algorithms. The reason is that, almost always, these are...
Algorithms for Learning Finite Automata from Queries: A Unified View (1996)
José L. Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe
. In this survey we compare several known variants of the algorithm for learning deterministic finite automata via membership and equivalence queries. We believe that our presentation makes it easier...
Coding Complexity: The Computational Complexity of Succinct Descriptions (1996)
José L. Balcázar, Ricard Gavaldà, Osamu Watanabe
For a given set of strings, the problem of obtaining a succinct description becomes an important subject of research, related to several areas of theoretical computer science. In structural...
Learnability of Kolmogorov-Easy Circuit Expressions Via Queries (1995)
José L. Balcázar, Harry Buhrman, Montserrat Hermo
. Circuit expressions were introduced to provide a natural link between Computational Learning and certain aspects of Structural Complexity. Upper and lower bounds on the learnability of circuit...
Simple PAC learning of simple decision lists (1995)
Jorge Castro, José L. Balcázar
We prove that log n-decision lists -- the class of decision lists such that all their terms have low Kolmogorov complexity -- are learnable in the simple PAC learning model. The proof is based on a...
On Infinite Sequences (almost) as Easy as (1994)
José L. Balcázar, Ricard Gavaldà, Montserrat Hermo
. It is known that infinite binary sequences of constant Kolmogorov complexity are exactly the recursive ones. Such a kind of statement no longer holds in the presence of resource bounds. Contrary to...