Catálogo de publicaciones - libros

We are concerned with clustering sequences that have been classified according to heterogeneous schema. We adopt a model-based approach that uses a Hidden Markov model (HMM) that has as states the stages of the underlying process that generates the sequences, thus allowing us to handle complex and heterogeneous data. Each cluster is described in terms of a HMM where we seek to find schema mappings between the states of the original sequences and the states of the HMM. The general solution that we propose involves several distinct tasks. Firstly, there is a clustering problem where we seek to group similar sequences; for this we use mutual entropy to identify associations between sequence states. Secondly, because we are concerned with clustering heterogeneous sequences, we must determine the mappings between the states of each sequence in a cluster and the states of an underlying hidden process; for this we compute the most probable mapping. Thirdly, on the basis of these mappings we use maximum likelihood techniques to learn the probabilistic description of the hidden Markov process for each cluster. Finally, we use these descriptions to characterise the clusters by using Dynamic Programming to determine the most probable pathway for each cluster. Such an approach provides an intuitive way of describing the underlying shape of the process by explicitly modelling the temporal aspects of the data; non time-homogeneous HMMs are also considered. The approach is illustrated using gene expression sequences.

A new view of majority voting as a Monte Carlo stochastic algorithm is presented in this paper. Relation between the two approaches allows Adaboost’s example weighting strategy to be compared with the greedy covering strategy used for a long time in Machine Learning. The greedy covering strategy does not clearly show overfitting, it runs in at least one order of magnitude less time, it reaches zero error on the training set in few trials, and the error on the test set is most of the time comparable to that exhibited by AdaBoost.

A text mining system uses two kinds of background knowledge: a concept relation dictionary and a key concept dictionary. The concept relation dictionary consists of a set of rules. We can automatically acquire it by using an inductive learning algorithm. The algorithm uses training examples including concepts that are generated by using both lexical analysis and the key concept dictionary. The algorithm cannot deal with a training example with more than one concept in the same attribute. Such a training example is apt to generate from a report, when the concept dictionary is not well defined. It is necessary to extend an inductive learning algorithm, because the dictionary is usually not completed. This paper proposes an inductive learning method that deals with the report. Also, the paper shows the efficiency of the method through some numerical experiments using business reports about retailing.

A well-known problem with Bayesian networks (BN) is the practical limitation for the number of variables for which a Bayesian network can be learned in reasonable time. Even the complexity of simplest tree-like BN learning algorithms is prohibitive for large sets of variables. The paper presents a novel algorithm overcoming this limitation for the tree-like class of Bayesian networks. The new algorithm space consumption grows linearly with the number of variables while the execution time is proportional to ln(), outperforming any known algorithm. This opens new perspectives in construction of Bayesian networks from data containing tens of thousands and more variables, e.g. in automatic text categorization.

We present a (nearly) domain-independent approach to mining trivia questions from a database. Generated questions are ranked and are more “interesting” if they have a modest number of solutions and may reasonably be solved (but are not too easy). Our functional model and genetic approach have several advantages: they are tractable and scalable, the hypothesis space size is limited, and the user may tune question difficulty. This makes our approach suitable for application to other data mining problems. We include a discussion of implementation on disparate data sets.

The general context of this work is the problem of merging data provided by several sources which can be contradictory. Focusing on the case when the information sources do not contain any disjunction, this paper first defines a propositional modal logic for reasoning with data obtained by merging several information sources according to a majority approach. Then it defines a theorem prover to automatically deduce these merged data. Finally, it shows how to use this prover to implement a query evaluator which answers queries addressed to several databases. This evaluator is such that the answer to a query is the one that could be computed by a classical evaluator if the query was addressed to the merged databases. The databases we consider are made of an extensional part, i.e. a set of positive or negative ground literals and an intensional part i.e. a set of first order function-free clauses. A restriction is imposed to these databases in order to avoid disjunctive data.

The adoption of the bias for weakening implication has lead to the definition of OI-implication, a generalization model for clausal spaces. In this paper, we investigate on the generalization hierarchy in the space ordered by OI-implication. The decidability of this relationship and the existence of minimal generalizations in the related search space is demonstrated. These results can be exploited for constructing refinement operators for incremental relational learning.

Current Web search engines find new documents basically crawling the hyperlinks with the aid of spider agents. Nevertheless, when indexing newly discovered documents they revert to conventional information retrieval models and single-document indexing, thus neglecting the inherently hypertextual structure of Web documents. Therefore, it can happen that a query string, partially present in a document, with the remaining part available in a linked document on the same site, does not correspond to a hit. This considerably reduces retrieval effectiveness. To overcome this and other limits we propose an approach based on temporal logic that, starting with the modeling of a web site as a finite state graph, allows one to define complex queries over hyperlinks with the aid of Computation Tree Logic (CTL) operators. Query formulation is composed by two steps: the first one is user-oriented and provides a user with a friendly interface to pose queries. The second step is the query translation in CTL formulas. The formulation of the query is not visible to the user that simply expresses his/her requirements in natural language. We implemented the proposed approach in a prototype system. Results of experiments show an improvement in retrieval effectiveness.

Structured documents are composed of objects with a content and a logical structure. The effective retrieval of structured documents requires models that provide for a content-based retrieval of objects that takes into account their logical structure, so that the relevance of an object is not solely based on its content, but also on the logical structure among objects. This paper proposes a formal model for representing structured documents where the content of an object is viewed as the knowledge contained in that object, and the logical structure among objects is captured by a process of knowledge augmentation: the knowledge contained in an object is augmented with that of its structurally related objects. The knowledge augmentation process takes into account the fact that knowledge can be incomplete and become inconsistent.

Internet shopping using some on-line catalogue of products is one of the fastest growing businesses now. An intelligent support for selecting a product in such a catalogue should work as an assistant (on request), not forcing the user to perform any unnecessary steps. As many Internet portals which support browsing and search, the proposed solution should support browsing (the catalogue) and recommending. Our paper describes some ongoing work on intelligent shopping assistant of an on-line catalogue of a hardware vendor who sells a relatively restricted scale of products (PC’s) manufactured by a single company. We propose a solution that will make browsing the catalogue easier, will recommend products, and will adapt its behavior to different types of users. Grouping the products into easily interpretable clusters can enhance browsing. To recommend a product and to adapt the system to different users, we propose to use a Bayesian network. We believe that our solution will be able to automatically follow the changes in the notions of computer characteristics (as the performance of new products increases), will be able to easy incorporate new products and will be able to understand requests from different types of users.