Fundamenta Informaticae - Volume 47, issue 1-2

Authors: El-Kwae, E. | Raś, Z.

Article Type: Other

Keywords:

Citation: Fundamenta Informaticae, vol. 47, no. 1-2, pp. v-vii, 2001

Authors: Kramer, Stefan | Widmer, Gerhard | Pfahringer, Bernhard | De Groeve, Michael

Article Type: Research Article

Abstract: This paper is devoted to the problem of learning to predict ordinal (i.e., ordered discrete) classes using classification and regression trees. We start with S-CART, a tree induction algorithm, and study various ways of transforming it into a learner for ordinal classification tasks. These algorithm variants are compared on a number of benchmark data sets to verify the relative strengths and weaknesses of the strategies and to study the trade-off between optimal categorical classification accuracy (hit …rate) and minimum distance-based error. Preliminary results indicate that this is a promising avenue towards algorithms that combine aspects of classification and regression. Show more

Keywords: Machine Learning, Ordinal Classes, Regression Trees, Decision Trees, Classification, Regression, Inductive Logic Programming

Citation: Fundamenta Informaticae, vol. 47, no. 1-2, pp. 1-13, 2001

Authors: Esposito, Floriana | Fanizzi, Nicola | Ferilli, Stefano | Semeraro, Giovanni

Article Type: Research Article

Abstract: A framework for theory refinement is presented pursuing the efficiency and effectiveness of learning regarded as a search process. A refinement operator satisfying these requirements is formally defined as ideal. Past results have demonstrated the impossibility of specifying ideal operators in search spaces where standard generalization models, like logical implication or �-subsumption, are adopted. By assuming the object identity bias over a space defined by a clausal language ordered by logical implication, a novel generalization model, …named OI-implication, is derived and we prove that ideal operators can be defined for the resulting search space. Show more

Keywords: Incremental Learning, Theory Refinement, Refinement Operators, Generalization Models, �-subsumption, Implication

Citation: Fundamenta Informaticae, vol. 47, no. 1-2, pp. 15-33, 2001

Authors: Elomaa, Tapio | Rousu, Juho

Article Type: Research Article

Abstract: The need to partition or discretize numeric value ranges arises in machine learning and data mining algorithms. This subtask is a potential time-consumption bottleneck, since the number of candidate partitions is exponential in the number of possible cut points in the range. Thus, many heuristic algorithms have been proposed for this task. Recently, the efficiency of optimal multisplitting has improved dramatically, due to the introduction of linear-time algorithms for training error minimization and quadratic-time …generic algorithms. Whether these efficient algorithms are the best obtainable, is not yet known. In this paper, we probe the inherent complexity of the multisplitting problem. We reflect results obtained for similar problems in computational geometry and string matching to the multisplitting task. Subquadratic optimization algorithms in computational geometry rely on the monotonicity of the optimized function. We show by counterexamples that the widely used evaluation functions Training Set Error and Average Class Entropy do not satisfy the kind of monotonicity that facilitates subquadratic-time optimization. However, we also show that the Training Set Error function can be decomposed into monotonic subproblems, one per class, which explains its linear time optimization. Finally, we review recently developed techniques for speeding up optimal multisplitting. Show more

Keywords: Machine learning, splitting criteria, optimal multisplits, computational complexity

Citation: Fundamenta Informaticae, vol. 47, no. 1-2, pp. 35-52, 2001

Authors: Hacid, Mohand-Saïd | Toumani, Farouk | Elmagarmid, Ahmed K.

Article Type: Research Article

Abstract: In this paper we consider how constraint-based technology can be used to query semistruc-tured data. As many concerns in semistructured data (e.g., representing and retrieving) are also found in computational linguistics, this last area could provide an interesting angle to attack some of the problems regarding semistructured data. We present a formalism based on feature logics for query-ing semistructured data. The formalism is a hybrid one in the sense that it combines clauses with path constraints. The resulting language has a clear declarative and operational semantics based on the notion of extended active domain.

Keywords: Semistructured Data, Feature Logics, Path Expressions, Rule-Based Languages, Constraints

Citation: Fundamenta Informaticae, vol. 47, no. 1-2, pp. 53-73, 2001

Authors: Sang Hyun, Park | Wesley W., Chu

Article Type: Research Article

Abstract: This paper presents techniques for discovering and matching rules with {\em elastic patterns}. Elastic patterns are ordered lists of elements that can be stretched along the time axis. Elastic patterns are useful for discovering rules from data sequences with different sampling rates. For fast discovery of rules whose heads (left-hand sides) and bodies (right-hand sides) are elastic patterns, we construct a trimmed suffix tree from succinct forms of data sequences and keep the tree as a …compact representation of rules. The trimmed suffix tree is also used as an index structure for finding rules matched to a target head sequence. When matched rules cannot be found, the concept of {\em rule relaxation} is introduced. Using a cluster hierarchy and relaxation error as a new distance function, we find the least relaxed rules that provide the most specific information on a target head sequence. Experiments on synthetic data sequences reveal the effectiveness of our proposed approach. Show more

Keywords: Knowledge Discovery , Data Mining,, Elastic Patterns, Sequence Databases

Citation: Fundamenta Informaticae, vol. 47, no. 1-2, pp. 75-90, 2001

Authors: Puuronen, Seppo | Tsymbal, Alexey

Article Type: Research Article

Abstract: Multidimensional data is often feature space heterogeneous so that individual features have unequal importance in different sub areas of the feature space. This motivates to search for a technique that provides a strategic splitting of the instance space being able to identify the best subset of features for each instance to be classified. Our technique applies the wrapper approach where a classification algorithm is used as an evaluation function to differentiate between different feature subsets. …In order to make the feature selection local, we apply the recent technique for dynamic integration of classifiers. This allows to determine which classifier and which feature subset should be used for each new instance. Decision trees are used to help to restrict the number of feature combinations analyzed. For each new instance we consider only those feature combinations that include the features present in the path taken by the new instance in the decision tree built on the whole feature set. We evaluate our technique on data sets from the UCI machine learning repository. In our experiments, we use the C4.5 algorithm as the learning algorithm for base classifiers and for the decision trees that guide the local feature selection. The experiments show some advantages of the local feature selection with dynamic integration of classifiers in comparison with the selection of one feature subset for the whole space. Show more

Keywords: Feature selection, ensemble of classifiers, dynamic integration, data mining, machine learning

Citation: Fundamenta Informaticae, vol. 47, no. 1-2, pp. 91-117, 2001

Authors: Kim, Minkoo | Deogun, Jitender S. | Raghavan, Vijay V.

Article Type: Research Article

Abstract: One of the essential goals in information retrieval is to bridge the gap between the way users would prefer to specify their information needs and the way queries are required to be expressed. Rule Based Information Retrieval by Computer (RUBRIC) is one of the approaches proposed to achieve this goal. This approach involves the use of production rules to capture user-query concepts (or topics). In RUBRIC, a set of related production rules is represented as an …AND/OR tree, or alternatively by a disjunction of Minimal Term Sets (MTSs). The retrieval output is determined by the evaluation of the weighted Boolean expressions of the AND/OR tree, and processing efficiency can be enhanced by employing MTSs. However, since the weighted Boolean expression ignores the term-term association unless it is explicitly represented in the tree, the terminological gap between users' queries and their information needs may still remain. To solve this problem, we adopt the generalized vector space model (GVSM) and the p-norm based extended Boolean model. Experiments are performed for two variations of the RUBRIC model, extended with GVSM, as well as for the integrated use of RUBRIC with the p-norm based extended Boolean model. The results are compared to the original RUBRIC model based on recall-precision. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 47, no. 1-2, pp. 119-135, 2001

Authors: Fernandes, Chris | Henschen, Lawrence

Article Type: Research Article

Abstract: We propose a system whereby subtle semantic ambiguity found in queries of distributed heterogeneous database systems can be resolved by considering the user's intentions. Through the use of domain-specific knowledge embedded within a mediator-based architecture, subtleties in meaning can be explicitly modeled. Through the use of dynamic profiles and active dialogue, the system can discover user intent, providing more satisfying query answers.

Keywords: heterogeneous databases, mediation, intent

Citation: Fundamenta Informaticae, vol. 47, no. 1-2, pp. 137-154, 2001

Authors: Bertino, Elisa | Catania, Barbara | Zarri, Gian Piero

Article Type: Research Article

Abstract: Metadata represent the vehicle by which digital documents can be efficiently indexed and retrieved. The need for such kind of information is particularly evident in multimedia digital libraries, which store documents dealing with different types of media (text, images, sound, video). In this context, a relevant metadata function consists in superimposing some sort of conceptual organization over the unstructured information space proper to these digital repositories, in order to facilitate the intelligent retrieval of the …original documents. To this purpose, the usage of conceptual annotations seems quite promising. In this paper, we propose a two-steps annotation approach by which conceptual annotations, represented in NKRL (Narrative Knowledge Representation Language) [7,8], are associated with multimedia documents and used during retrieval operations. We then present how documents and metadata can be stored and managed on persistent storage. Show more

Keywords: multimedia document, digital library, metadata, conceptual annotation, XML

Citation: Fundamenta Informaticae, vol. 47, no. 1-2, pp. 155-173, 2001