Learning hierarchical clustering from examples — application to the adaptive construction of dissimilarity indices

A classical problem of Pattern Recognition consists in looking for an operator of classification (a ‘classifier’) induced from a learning set on which classes are known. A problem frequently encountered in practice is that of looking for an operator of clustering (a ‘clusterfier’, in opposition to ‘classifier’) from a learning set on which clusters are also known. In the first case, we have to find an operator which allocates each new object to one of the classes defined by the learning set. In the second case, we have to find an operator which detects classes in the complete population, taking in account as well as possible the information given by the classes on the learning set. We propose a new approach permitting to induce and aggregation index from knowledge acquiring on the learning set; the aggregation index thus obtained permits to induce a hierarchy which infers the desired classes on the whole population.

A nearest neighbours algorith with validity constraints has been realized to induce the final hierarchy. We obtain a CPU time clearly shorter than with the classical hierarchical ascending classification algorithm which does not use inference.

This program has permitted to find aggregation indices adapted to particular learning sets (elongated classes, spherical class with central kernel, half spherical class with central kernel, noising elongated classes…), and some of new indices permit to recognize more specific classes than the usual indices.     

View creation for queries in object oriented databases

A view in object oriented databases corresponds to virtual schema with restructured generalization and decomposition hierarchies,Numbers of view creation methodologies have been proposed.A major drawback of existing methodologies is that they do not maintain the closure property.That is,the result of a query does not have the same semantics as embodied in the object oriented data model.Teherefore,this paper presents a view creation methodology that derives a class in response to a user‘s query,integrates derived class in global schema (i.e., considers the problem of classes moving in class hierarchy)and selects the required classes from global schema to create the view for user‘s query.Novel idea of view creation includes:(a) an object algebra for class derivation and customization(where the derived classes in terms of object instances and procedure/methods are studied),(b)maintenance of closure property,and (c)classification algorithm which provides mechanism to deal with the problem of a class moving in a class hierarchy.     

An operational semantics for object-oriented concepts based on the class hierarchy

The formalisation of object-oriented languages is essential for describing the implementation details of specific programming languages or for developing program verification techniques. However there has been relatively little formalisation work aimed at abstractly describing the fundamental concepts of object-oriented programming, separate from specific language considerations or suitability for a particular verification style. In this paper we address this issue by formalising a language that includes the core object-oriented programming language concepts of field tests and updates, methods, constructors, subclassing, multithreading, and synchronisation, built on top of standard sequential programming constructs. The abstract syntax is relatively close to the core of typical object-oriented programming languages such as Java. A novel aspect of the syntax is that objects and classes are encapsulated within a single syntactic term, including their fields and methods. Furthermore, class terms are structured according to the class hierarchy, and objects appear as subterms of their class (and method instances as subterms of the relevant object). This helps to narrow the gap between how a programmer thinks about their code and the underlying mathematical objects in the semantics. The semantics is defined operationally, so that all actions a program may take, such as testing or setting local variables and fields, or invoking methods on other objects, appear on the labels of the transitions. A process-algebraic style of interprocess communication is used for object and class interactions. A benefit of this label-based approach to the semantics is that a separation of concerns can be made when defining the rules of the different constructs, and the rules tend to be more concise. The basic rules for individual commands may be composed into more powerful rules that operate at the level of classes and objects. The traces generated by the operational semantics are used as the basis for establishing equivalence between classes.     

Interpreting SWRL Rules in RDF Graphs

An unresolved issue in SWRL (the Semantic Web Rule Language) is whether the intended semantics of its RDF representation can be described as an extension of the W3C RDF semantics. In this paper we propose to make the model-theoretic semantics of SWRL compatible with RDF by interpreting SWRL rules in RDF graphs. For dealing with SWRL/RDF rules, we regard ‘Implies’ as an OWL class, and extract all ‘Implies’ rules from an RDF database that represents a SWRL knowledge base. Each ‘Implies’ rule is grounded through mappings built into the semantic conditions of the model theory. Based on the fixpoint semantics, a bottom-up strategy is employed to compute the least Herbrand models.     

The object standardization challenge

The real challenge in object standardization is to reconcile diverse views of what an object inherently ‘is’. This is harder than agreeing on definitions of secondary characteristics such as type and inheritance. User interfaces visualize objects as things in two-dimensional space. Programming thinks of objects as active things that communicate with each other, such as editors and print programs. Database leans more toward objects as participants in operations, such as documents and printers. Unifying these, in a kind of wave/particle dualism, is intellectually tempting, but leads to its own anomalies. Such fundamental questions need sorting out before we can converge on object standards spanning these disciplines.     

Views as first-class citizens in object-oriented databases

Extensibility and dynamic schema evolution are among the attractive features that lead to the wide acceptance of the object-oriented paradigm. Not knowing all class hierarchy details should not prevent a user from introducing new classes when necessary. Naive or professional users may define new classes either by using class definition constructs or as views. However, improper placement of such classes leads to a flat hierarchy with many things duplicated. To overcome this problem, we automated the process in order to help the user find the most appropriate position with respect to her class in the hierarchy regardless of her knowledge of the hierarchy. The system must be responsible for the proper placement of new classes because only the system has complete knowledge of the details of the class hierarchy, especially in a dynamic environment where changes are very frequent. In other published work, we proved that to define a view it is enough to have the set of objects that qualify to be in a view in addition to having message expressions (possible paths) that lead to desired values within those objects. Here, we go further to map a view that is intended to be persistent into a class. Then we investigate the proper position of that class in the hierarchy. To achieve this, we consider current characteristics of a new class in order to derive its relationship with other existing classes in the hierarchy. Another advantage of the presented model is that views that generate new objects are still updatable simply because we based the creation of new objects on existing identities. In other words, an object participates inside view objects by its identity regardless of which particular values from that object are of interest to the view. Values are reachable via message expressions, not violating encapsulation. This way, actual values are present in only one place and can be updated.Received: 19 March 1999, Accepted: 26 December 2003, Published online: 8 April 2004Edited by: R. Topor.     

Rule Induction with Grouping Target Concepts based on Rough Sets

One of the most important problems with rule induction methods is that they cannot extract rules, which plausibly represent experts’ decision processes. In this paper, the characteristics of experts’ rules are closely examined and a new approach to extract plausible rules is introduced, which consists of the following three procedures. First, the characterization of decision attributes (given classes) is extracted from databases and the concept hierarchy for given classes is calculated. Second, based on the hierarchy, rules for each hierarchical level are induced from data. Then, for each given class, rules for all the hierarchical levels are integrated into one rule. The proposed method was evaluated on a medical database, the experimental results of which show that induced rules correctly represent experts’ decision processes.     

Topological models for boundary representation: a comparison with n-dimensional generalized maps

In boundary representation, a geometric object is represented by the union of a ‘topological’ model, which describes the topology of the modelled object, and an ‘embedding’ model, which describes the embedding of the object, for instance in three-dimensional Euclidean space. In recent years, numerous topological models have been developed for boundary representation, and there have been important developments with respect to dimension and orientability. In the main, two types of topological models can be distinguished. ‘Incidence graphs’ are graphs or hypergraphs, where the nodes generally represent the cells of the modelled subdivision (vertex, edge, face, etc.), and the edges represent the adjacency and incidence relations between these cells. ‘Ordered’ models use a single type of basic element (more or less explicitly defined), on which ‘element functions’ act; the cells of the modelled subdivision are implicitly defined in this type of model. In this paper some of the most representative ordered topological models are compared using the concepts of the n-dimensional generalized map and the n-dimensional map. The main result is that ordered topological models are (roughly speaking) equivalent with respect to the class of objects which can be modelled (i.e. with respect to dimension and orientability).     

Foundations for object-oriented query processing

A minimal framework for an object-oriented query language standard should (1) include a formal definition of a high-level data model and the syntax and semantics of associated query languages, (2) provide the functionality of relational query languages, and (3) support proofs of correctness of transformations for logical query optimization. In this paper, a high-level conceptual model for object-oriented query processing is discussed; the model includes widely-used structural abstractions such as the isa relationship, associations (properties) between complex objects and complex objects/values, and inheritance of properties. A formal, algebraic query language for the model, inspired by relational algebra, is presented. Operators of the algebra allow queries based on values, queries that manipulate entire objects, and queries that construct new objects from existing objects/values. All queries retain connections to existing database objects, providing logical access paths to data. Each query result is a class, so the algebra has the closure property. The intensional and extensional results of query operators are summarized. Two forms of logical query optimization supported by the query algebra are outlined: algebraic transformations and classifier-based optimizations (optimizations which employ inclusion and exclusion dependencies between classes).     

Ontology oriented programming in go!

In this paper we introduce the knowledge representation features of a new multi-paradigm programming language called go! that cleanly integrates logic, functional, object oriented and imperative programming styles. Borrowing from L&O [1] go! allows knowledge to be represented as a set of labeled theories incrementally constructed using multiple-inheritance. The theory label is a constructor for instances of the class. The instances are go!’s objects. A go! theory structure can be used to characterize any knowledge domain. In particular, it can be used to describe classes of things, such as people, students, etc., their subclass relationships and characteristics of their key properties. That is, it can be used to represent an ontology. For each ontology class we give a type definition—we declare what properties, with what value type, instances of the class have—and we give a labeled theory that defines these properties. Subclass relationships are reflected using both type and theory inheritance rules. Following [2], we shall call this ontology oriented programming. This paper describes the go! language and its use for ontology oriented programming, comparing its expressiveness with Owl, particularly Owl Lite[3]. The paper assumes some familiarity with ontology specification using Owl like languages and with logic and object oriented programming.     

A Formal Definition of the Chimera Object-Oriented Data Model

In this paper we formalize the object-oriented data model of the Chimera language. This language supports all the common features of object-oriented data models such as object identity, complex objects and user-defined operations, classes, inheritance. Constraints may be defined by means of deductive rules, used also to specify derived attributes. In addition, class attributes, operations, and constraints that collectively apply to classes are supported.The main contribution of our work is to define a complete formal model for an object-oriented data model, and to address on a formal basis several issues deriving from the introduction of rules into an object-oriented data model.     

Knowledge object modeling

Knowledge objects are an integration of the object-oriented paradigm with logic rules. The proper integration provides a flexible and powerful environment, as rule-based components provide facilities for deductive retrieval and pattern matching, and object-oriented components provide a clear intuitive structure for programs in the form of class hierarchies. Based on the knowledge object concept, this paper presents a factor-centered representation language, Factor++, which models logic rules into the object-oriented paradigm, and a scheduling system, Schedular, using the Factor++ framework The construction of Schedular demonstrates that by using an object-oriented representation of knowledge objects, users can be given explicit control of the object hierarchy to customize the system to their particular needs, which includes letting users select among scheduling and other methods. In Schedular, rules are designed as derivation rules and constraint rules. The purpose of rules is either to restrict object structure and behavior, or to infer new data from the existing data. Rules are arranged in positions so that object methods are automatically firing up if environment changes are detected by these rules     

An object deputy model for realization of flexible and powerful objectbases

In object-oriented databases, data and methods are combined by objects and their classes. Information redundancies are removed by the notions of class hierarchy and inheritance. This contributes the realization of high-performance systems. However, the flexibility of object structures still remains a problem due to its encapsulation feature. In this paper, we introduce an object deputy model which extends conventional object-oriented models with the concepts of deputy objects and deputy classes. A deputy object has its own identifier and may possess its own attributes and methods. It can also have attributes that are computed from values stored within its source object, and can be associated with methods generated from these of the source object. The inheritances are realized by switching operations, which make it possible to realize controllable, selective and dynamic inheritance structures. Schemata of deputy objects are defined by deputy classes which can be derived by an object deputy algebra. An object can have many deputy objects, and several objects can share a single deputy object. Thus, objects can be indirectly divided and combined through their deputy objects. We show that several difficult database problems, such as flexible views, objects with more than one role, object migration, and multiple inheritance become much easier in this model. The data-knowledge coordination model developed for the integration of distributed databases and knowledge-bases can also be realized easily by the object deputy model. Finally, we discuss several advanced database applications of this model, such as geographic databases, virtual office systems, and distant education systems.     

Familial model of data

The family of sets is proposed as the basic structure for modeling data. A family is created by indexing one set of objects by another to represent a directed binary association between two sets. Familial models are shown to have a number of distinct advantages in supporting diverse user views through a hierarchy of abstractions and a variety of derived data, and in describing themselves and other data models through metamodels. An algebra of families is introduced to provide a data definition, maintenance and processing language that is minimal, intuitive, algebraic and theoretically sound. The language is extended to a specification language for database application systems, largely eliminating the need for embedding database constructs into procedural programming languages.     

An Overview of the Rule-Based Object Language

This paper presents an overview of a novel strongly typed deductive object database language, called Rule-based Object Language, which is being developed at the University of Regina. Rule-based Object Language is a uniform language for defining, querying, and manipulating a database, which integrates important features of deductive databases and object databases. It supports object identity, complex objects, classes, class hierarchies, multiple inheritance with overriding and blocking, and schema definition. It also supports structured values such as functor objects and sets, treating them as first class citizens and providing powerful mechanisms for representing both partial and complete information about sets. Important integrity constraints such as domain, referential, functional dependency, multi-valued dependency, and cardinality are built-in in a uniform framework. Rule-based Object Language directly supports non-first normal form relations and is an extension of the pure valued-oriented deductive languages such as Datalog and LDL (without grouping) and subsumes them as special cases. It supports schema, object, fact and rule queries in a uniform framework. It also supports schema, fact and rule updates.     

Object-oriented data modeling in rule-based software development environments

Object-oriented databases (OODBs) were developed to support advanced applications for which traditional databases are not sufficient. The data management requirements of these new applications are significantly different from more traditional data processing applications. More light needs to be shed on these requirements in order to identify the aspects of OODBs that can lead to standards. We have studied the data management requirements of one class of advanced database applications: rule-based software development environments (RBDEs). RBDEs store project components in an object database and control access to these objects through a rule-based process model, which defines each development activity as a rule. The components are abstracted as instances of classes which are defined by the project's data model. In this paper we discuss the constructs that a data modeling language for RBDEs should provide, and then explore some of the data management requirements of RBDEs. We use the Marvel system we developed at Columbia as an example.     

The verification and synthesis of data structures

Summary The concept of machine extension is a commonly used technique for implementing complex software: sets of object classes and operations on these objects are defined and used, often in a layered fashion, to construct the system. This paper addresses the adaptation of this technique to automatic programming. It discusses how such sets of data structures may be precisely specified, presents an axiomatization of a programming language suitable for machine verification, and shows how programs which realize these data structures may be proved correct. A range of data type classes is treated—including arrays, records, and pointers. Some new verification rules are presented to handle programs which use assignments and structured objects.     

Class Based Contextual Logic for DOOD

Cntextual logic provides a mechanism to reason about modules.In this paper,this theory of modules if modules is extended to a context theory of classes where class is in the true spirit of object-oriented databases.The logic,referred to as CLOG,is class-based.CLOG supports class,object identity,multiple role of object, monotonic and non-monotonic inheritance of data and method,method factoring,views,derived and query classes.Views and derived classes are queries in themselves.Objects are pure data terms representing the ground instances of facts in the class.Object identity is a first class term in the logic.Inheritance is handled through delegation.     

Querying sequence databases with transducers

This paper develops a database query language called Transducer Datalog motivated by the needs of a new and emerging class of database applications. In these applications, such as text databases and genome databases, the storage and manipulation of long character sequences is a crucial feature. The issues involved in managing this kind of data are not addressed by traditional database systems, either in theory or in practice. To address these issues, we recently introduced a new machine model called a generalized sequence transducer. These generalized transducers extend ordinary transducers by allowing them to invoke other transducers as “subroutines.” This paper establishes the computational properties of Transducer Datalog, a query language based on this new machine model. In the process, we develop a hierarchy of time-complexity classes based on the Ackermann function. The lower levels of this hierarchy correspond to well-known complexity classes, such as polynomial time and hyper-exponential time. We establish a tight relationship between levels in this hierarchy and the depth of subroutine calls within Transducer Datalog programs. Finally, we show that Transducer Datalog programs of arbitrary depth express exactly the sequence functions computable in primitive-recursive time. Received: 12 March 1998 / 30 August 1999