Jérôme Euzenat
email: jerome.euzenat@imag.fr

Brief overview of T-TREE: the TROPES Taxonomy building Tool

TROPES is an object-based knowledge representation system. It allows the representation of multiple taxonomies over the same set of objects through viewpoints and provides tools for classification (identification) of objects and categorisation (classification) of classes from their descriptions. T-TREE is an extension of TROPES for the construction of taxonomies from objects. Data analysis algorithms consider TROPES objects for producing TROPES taxonomies. Thus, data analysis is integrated into the knowledge representation system. Moreover, the original bridge notion permits the comparison and connection of adjacent taxonomies. KEYS: Automated techniques to assist in creating classification scheme -Knowledge representation schemes -Classification algorithms -Software for management of classification schemes -Comparison and compatibility between classification schemes.

TROPES is an object-based knowledge representation system. It is thus a general-purpose knowledge repository whose basic entities are objects (i.e. entities structured into fields and belonging to a class). Such a system is provided for integration into a wider application system which uses it for containing both the objects (data) and the inference mechanisms tied to the object semantics. The application system consists in a set of programs which access the knowledge base for consulting and modifying the objects that which, in turn, can trigger some of the inference methods (knowledge).

TROPES heavily relies on the classification mechanism (i.e. the mechanism which recognises the class to which an object can belong). The classes are hierarchically organised into taxonomies and, as knowledge about an object is acquired, it can be further classified under more specific classes. Classification is very important since the more specific the class, the more adapted to the object is the knowledge attached to that class.

The TROPES Taxonomy building Tool (T-TREE for short) is an extension of the TROPES object-based knowledge representation system enabling the integration of data analysis and automatic classification methods for the construction of object taxonomies. As a matter of fact, an important part of data analysis research is devoted to automatic classification.

Here, we show how this integration can be achieved and what are the benefits which can be expected from the integration. In particular, it is shown how T-TREE takes advantage of exclusive features of TROPES such as viewpoints and bridges. Further on, the integration can be seen as an important outlet for automatic classification algorithms in directly fetching the data and storing the result of classification in the place where it is used: the knowledge base.

The first section presents the TROPES system as representative of available object repositories but also as proposing some special features. Section 2 is devoted to the classification and categorisation mechanisms in TROPES. It emphasises the importance of the taxonomies in the TROPES system. Section 3 presents the principles of T-TREE: how the TROPES notions can be accounted for by data analysis algorithms, how these algorithms can produce TROPES expressions and how the control of the algorithms can be passed on to the user. Section 4 describes the use of a special feature of TROPES (bridges) for correcting and comparing the results of the data analysis phase.

1.TROPES

TROPES is an object-based representation system which favours classification. It is here presented through its basic notions. As TROPES is still under development, references to previous experiences [START_REF] Chevenet | A development shell for cooperative problem solving environments[END_REF][START_REF] Gautier | Object-centered representation and fish identification in Antartica[END_REF][START_REF] Willamowski | Modelling methodological knowledge in data analysis[END_REF] are made on the basis of its ancestor SHIRKA.

1.1.Objects and concepts

TROPES [START_REF] Mariño | Multiple perspectives and classification mechanism in object-oriented representation[END_REF] is an object-based knowledge representation model (see [START_REF] Masini | Les langages à objets[END_REF] for a comprehensive introduction and review of such systems). This means that individuals are represented as objects.

The objects are partitioned into concepts (an object is an instance of one and only one concept). As an example, the employee concept concerns all the individual employees. Ontological prerogatives are attached to the concept. They are those which warrant the integrity of an object (i.e. that it cannot be modified in a way which would lead it to cease being an instance of the concept). Thus the concept defines the structure and the identity of its instances.

The structure of an object is uniquely determined by a set of fields and their basic domains independently of the classes to which the object can be attached. The fields relevant to objects are described in the concept. The instances of the employee concept have a name, a salary and a publications field. The basic domain of a field is either a primitive type (real, integer, string, boolean), a concept or a type constructed from these ones (and only them) with the help of set and list constructors.

Moreover, the field values are part of the objects and do not depend upon the classes to which they are attached. Thus, inference methods which represent implicit knowledge (valid deduction or value computation which must return the true value of a field) are attached to the concept itself.

The concept prerogatives also include the management of object identity. In TROPES, objects are identified with the help of a key: a list of field values which uniquely corresponds to one object. The usual consequences with keys are related to integrity: an object without a key cannot exist and there cannot exist two objects with the same key (thus accidental co-reference is avoided). Concepts also have in charge the management of existential dependencies from objects to components they cannot exist without (for example, it is not possible to change the hiring-date of some employee).

These prerogatives play an important role at instantiation when the object is created and registered. During its lifetime, an individual, created under some concept, is ensured that none of the above postulates is violated.

1.2.Viewpoints

Objects can be seen under several viewpoints. Some employee instances can be though of as employees from the Accounting viewpoint, as researchers from the Functional viewpoint, as customers from the Restaurant… The viewpoints allow to restrict the view on instances (as noted in [START_REF] Stephens | The classification of semantic relations based on primitive properties[END_REF], there are 970 fields (slots in CYC) in the person concept (class), thus users are often discouraged in their search for the adequate one) and organise the concept into a particular taxonomy. A viewpoint determines:

• The set of fields which are relevant under the viewpoint (the publications are not relevant from the Restaurant viewpoint as well as the diet under the Functional one, and thus the corresponding fields are hidden under the respective viewpoints). • A hierarchy of classes under which the instances of the concept can be classified.

Classes introduce constraints on the field values of their members. They are related through the specialisation relation and determine progressive subsets of the set of instances of the concept. This progression is parallel to the strengthening of the constraints added to sub-classes. Each of them determines a hierarchy of classes whose root class is named employee. For example, under the Functional viewpoint there is a decomposition of the set of employees following their functions. The CR Director object is attached to the vegetarian class under the Restaurant viewpoint, to the profit-sharing holder under the Accounting viewpoint and to the director class under the Functional viewpoint.

The advantages of multiple taxonomies are manifold: • Under a particular viewpoint, an object is attached to only one class (this was motivated by the argument that an object belonging to two unrelated classes is so under different viewpoints [START_REF] Mariño | Multiple perspectives and classification mechanism in object-oriented representation[END_REF]). This organisation is very useful since, from a particular viewpoint, one can classify an object with regard only to the relevant fields. As a consequence, the set of classes to be considered is small, while considering the whole lattice of possible structures (e.g. Vegetarian-Profit-sharing-Clerk) would confuse the user. • It allows to access taxon of a particular taxonomy from a specialised access device such as dichotomous diagnostic key [START_REF] Pankhurst | Practical taxonomic computing[END_REF] or decision trees. In [START_REF] Gautier | Object-centered representation and fish identification in Antartica[END_REF], two decision methods have been used in connection to zoological classification. It is also suggested that the viewpoints can be specific geographic areas which drastically restrict the set of available species and allow to build faster and simpler restriction key systems. • It is sometime useful to use different related taxonomies. This is the case in genetics when considering functional, chemical and evolutionary viewpoints on genes: there is a taxonomy for each viewpoint. This also allows the representation of alternative taxonomies in the same system. The need for representing "diverse overlapping classifications" has already be accounted for in [START_REF] Beach | Hierarchic taxonomic databases[END_REF]. • It enables the building of a new taxonomy without discarding the current one(s) (when testing a new hypothesis about the knowledge manipulated by the taxonomist). For instance, from an already existing knowledge base containing an important set of objects, it is possible to run clustering algorithms in order to build another taxonomy on a new viewpoint and to compare it with other taxonomies.

1.3.Classes and taxonomy

A class determines the relevant fields of its members and defines constraints that objects must satisfy in order to belong to the class. It is a projection of the structure of the concept retaining only relevant fields and a restriction of the possible values of these fields. This is achieved with the help of:

• Primitive domain restriction provided by domain enumeration, exclusion or bounding (diet has a string value enumerated by "regular", "vegetarian" and "low-fat"; the salary of a clerk can be between £750 and 1400). • Attachment restrictions for concepts: the field values must not only be instances of a particular concept but can be constrained to belong to particular classes of that concept (the value of the field project-director of a researcher must be member of the director class). • Constraints on field values. These constraints are membership constraints or constraints between fields (the share of an employee cannot exceed 20% of (her)his basic salary).

• Cardinality restriction on sets (resp. lists) by bounding the cardinality. It is noteworthy that constructed field values are true sets (resp. lists) and not multiple values. It means that the value of a field is given by the corresponding set (resp. list) and not by a subset (resp. sub-list) of it which could be completed later. The interpretation of the specialisation relation is twofold: first, the members of a class are members of its super-classes (extension inclusion property); second, the constraints defined in a class apply to all the members of that class (and thus to the objects attached to all of the less general classes). In the above example, it means that:

• all PhD students are researchers, and • all PhD students, as researchers, are subject to the confidentiality clause. But this does not imply the converse assertions. As a matter of fact, the interpretation of classes is descriptive, i.e. the satisfaction of the constraints associated to a class expresses a necessary but not sufficient condition for being a member of that class. The sufficient condition is the voluntary act of attachment produced by the user (or an application program).

As opposed to instantiation, objects can be attached to a class and can be detached from it at anytime. Classes also allow the expression of hypothetical knowledge in terms of default values or default inference methods. The hypothetical knowledge is relevant here since default values, for example, are given with regard to the specificity of the object class. These values are not to be seen as the true value of the field but as some hypothesis which can be made under a particular viewpoint. As a matter of fact, default values returned from different viewpoints do not have to be identical. For instance, it could be the case that research directors are usually fat while vegetarian are usually thin: what about a vegetarian director?

1.4.Bridges

As it has been said above, the classification of objects is considered as contingent. Thus, there can be several different classifications of the instances of the same concept: in a particular firm, the individuals are not considered the same way by the project management staff, the account office and the restaurant. Therefore the same individual is seen differently under several viewpoint and each viewpoint can have its own classification of the same set of individuals. However, viewpoints are not totally disconnected. Bridges are knowledge components which link a set of classes under pairwise disjoint viewpoints (called source) to a class in yet another viewpoint (called destination). A bridge means that an object which is member of each of the source classes is also member of the destination class. This allows, for instance, to infer that if an object is attached to the director class under the Functional viewpoint, it is member of the profit-sharing holders under the Accounting viewpoint (see figure 1). Bridges can be though of as either integrity constraints or inference mechanisms.

2.CLASSIFICATION AND CATEGORISATION

The aim of TROPES is not to be a taxonomic database system [START_REF] Beach | Hierarchic taxonomic databases[END_REF][START_REF] Pankhurst | Practical taxonomic computing[END_REF] but an object representation system which provides tools for taxonomy management. However, TROPES has emphasised classification for long now [START_REF] Gautier | Object-centered representation and fish identification in Antartica[END_REF][START_REF] Mariño | Classification d'objets composites dans un système de représentation de connaissances multi-points de vue[END_REF][START_REF] Mariño | Multiple perspectives and classification mechanism in object-oriented representation[END_REF] so that its classification mechanisms are elaborate. It provides classification and categorisation. The semantics of these operations are given in [START_REF] Euzenat | Une définition abstraite de la classification et son application aux taxonomies d'objets[END_REF]. Here is an informal presentation of TROPES classification abilities.

2.1.Classification

The system is able, given a particular object i with several field values, to find Cl(i), the set of classes (specialisation of its initial class) under which it can be attached (this is called "classification" in knowledge representation and "identification" in data analysis).

This is determined by an adequacy test which checks whether the field values of the object are included in the domain associated to the fields in the class and if the object as a whole satisfies the constraints associated to the class. The classification operation is based on a type interpretation of classes and algorithms which transform the classification process in a type inference process have been designed recently for TROPES [START_REF] Capponi | Interactive class classification using types[END_REF]. However, some important particularities of the classification in object-based knowledge representation system must be noted:

• The value of a field can be another object. Since the field type can be a set of classes, this object must in turn be classified in order to determine if it can belong to the specified classes [START_REF] Mariño | Classification d'objets composites dans un système de représentation de connaissances multi-points de vue[END_REF]. • The value of a field can be unknown. In such a case, it is possible that the algorithm cannot decide if the object satisfies the constraints of the class. Then the algorithm divides the set of classes into three: those which are known to be possible classes for the object (possible), those which are known not to be possible classes for the object (impossible) and the others (undetermined). A correct classification algorithm could test any of the classes and check if the object satisfies the class description. However, the implemented algorithm usually takes advantage of the taxonomic structure and the respect of extension inclusion.

A classification algorithm checks, for a particular class the super-class of which is a possible or undetermined class for the object, if the type constraints are satisfied by the object. If some field values are missing (and need to be checked) the system can ask them to the user. For classic domains, this test is carried out the usual way (type checking). For an object value, if the object must belong to specified classes, the algorithm triggers a new classification process on that value in order to check if this is possible. If every constraint is satisfied for every field, then the class is declared a possible class for the object; if any of the constraints is not satisfied, then the class is declared impossible; if the super-class is undetermined or some fields still do not have a value (and the others satisfy the constraints) then the class is undetermined. Then, it can proceed on sub-classes if the class is possible or undetermined. The classification process also takes into account the bridges which allow to infer the membership to a class from the membership to other classes in other viewpoints.

For instance, if a company hires a new employee, the corresponding object is created in the information system. The system will find the object class under the Functional viewpoint with the help of its function but also its diploma and other constraints on research directors. Since the project of the director (another object) is classified as a computer science project, the employee is classified under those which must have a login account on scientific computers. Once the object is attached to the research director class, it can be inferred, with the help of the bridge, that the individual is a profit sharing holder (without knowing anything from the Accounting viewpoint). Since there is no value about the kind of diet, the classification is carried on under the Restaurant viewpoint by asking the value.

It must be noted that the simplification introduced by viewpoints allows to restrict the taxonomies under which an object is classified. Moreover, even if the classification takes into account all the viewpoints, the user can distinguish the viewpoints under which (s)he is able to answer queries from those under which (s)he is not (for example, if the new employee is not at hand, the user can tell that the questions about the Restaurant viewpoint cannot be answered).

2.2.Categorisation

Categorisation corresponds to what is called classification in data analysis or machine learning. However, it is still a bit different since automatic classification builds the class and its description from the set of objects attached to that class and categorisation starts from a class description and tries to find the place of the class in the taxonomy. This is related to incremental conceptual clustering [START_REF] Fisher | Knowledge acquisition via incremental clustering[END_REF].

The categorisation in TROPES consists in finding the set of more general and the set of more specific classes than the class to insert in the taxonomy. The only constraint that a taxonomy must always satisfy is the extension inclusion property. As a consequence, the class can be a sub-class of one (or more) of its more general classes and a super-class of some (or all) of the more specific classes of its super-class(es) which are also in its more specific classes. The number of classes to which the newly inserted class is connected depends on the characteristics of the representation system. In TROPES, it is always a sub-class of only one class.

Thus, the algorithm starts with the class description and a starting class (usually the top of the taxonomy). It goes down the taxonomy and compares the classes. Again, the potential extension of the classes are abstracted through types and sub-typing is regarded as the test that the extension of a class is included in the extension of another (and thus that the former is more specific than the latter). The search is proceeded until the considered class is no more general than the class to insert. When this has been done for all the branches of the tree, the last encountered classes in each branches are the most specific more general classes than the class to be inserted. From here the search can continue until the encountered classes are more specific than the class to insert. Once these two sets of classes have been found, the new class can be inserted in the taxonomy by making it a specialisation of its more general classes and making some of its more specific classes a specialisation of it. The algorithm then tries to find possible sub-classes by going downward from that class.

Researcher and engineer are selected this time since they share all the fields in computer employee and only add new fields and constraints to the existing fields.

All these algorithms are skeleton algorithms since they can be different depending on whether the graph search is breadth-first, depth-first or adaptive. They can also optimise the number of questions asked to the user.

Thus TROPES makes an extensive use of the classification mechanisms both for the building of the knowledge base and for its use in identifying the objects. However, there is nothing available for classifying from the data. This lack is filled by T-TREE.

3.DATA ANALYSIS-BASED CLASSIFICATION

TROPES has been designed for hand made taxonomies. It also provides help in order to insert hand-crafted classes into an existing taxonomy. However, when a lot of objects have been collected for a particular concept, dedicated algorithms can be used to build new taxonomies out of these individuals. This is the aim of T-TREE.

Our purpose here is not the presentation of new specialised hierarchical classification algorithms but rather the description of how such algorithms can be integrated into an objectbased representation system (note that from that point, the examples concern a real estate knowledge base). First it is shown how some object-based concepts can be easily translated into data analysis concepts and how some others cannot be simply modelled. Then, it is shown how the results of data analysis algorithms are taken into account by TROPES. Last, the possible interactions between the user and data analysis methods are presented.

3.1.TROPES notions as data analysis ones

Clustering algorithms usually work on a set Ω of individuals affected of weight w 1 ,…w m (whose sum is equal to 1), with characteristics (or variables) v 1 ,…v n which are functions from Ω to structured sets of values O 1 ,…O n (see [START_REF] Day | Efficient algorithms for agglomerative hierarchical clustering methods[END_REF] for example). In TROPES, Ω corresponds to the set of instances of a concept and the variables are the fields to which corresponds a domain. Since objects with the same characteristics are grouped into one individual, its weight corresponds to the importance of the set of objects it represents. As it can be found in data analysis, the domain of a field can be qualitative or quantitative, structured or not by a partial order. It is sometime useful to change the kind of a variable in order to use particular methods or to simplify the results. This can be achieved in TROPES by creating a new field and defining an inference method allowing to compute its value with regard to the values of other fields. This is the case when one wants to obtain intervals from real values for instance or to use the returnrate (of an investment) variable instead of the two variables price and annual-rent.

The unit in which characteristic values are expressed is of great significance. It is thus useful to change variable units (rather than changing distance definitions). For the sake of experiments, the values of variables are divided by their standard deviation thus being independent from units.

Automatic classification algorithms produce clusters which are sets of objects. They correspond to the classes of a particular viewpoint in TROPES and the set inclusion relation between clusters produced by a hierarchical clustering algorithm corresponds to the specialisation relation. Thus, TROPES is able to describe a problem for clustering algorithms and to store the result of such an algorithm. If already implemented programs make use of particular formats such as matrices, section 3.3 shows how the conversion can be worked out. However, TROPES has limited capabilities for expressing global constraints (i.e. constraints taking into account a set of objects). More exactly, such constraints cannot concern a set of objects defined intentionally (if the set of object evolves, everything must be computed from scratch). This is important in a number of data analysis operations:

• the definition of a class (with regard to data analysis algorithm output) can express both metric and topologic conditions for class membership, but these conditions cannot refer to the set of members of a class or the classes themselves. For instance, the definition of a class can be that of a precise n-dimensional sphere (for n fields) but not that it must be a sphere of limited diameter (that which depends on all the members of the class). • the definition of intervals which are balanced (grouping the same number of objects) or centred (grouping a set of homogeneous objects). • the weighting of characteristic values with regard to their variance is not possible through inference methods since it requires the computation of variance over the complete set of objects. It is here carried out during the translation step. This is related to the problem of interpreting the results and methods of data analysis algorithms and its capability to produce conceptual descriptions. The result cannot be translated as such into a knowledge representation formalism. Thus TROPES only plays the role of a repository of the class hierarchy and the associated members.

3.2.Integrating algorithms

In order to build a new taxonomy, the user creates a new viewpoint. (S)he then chooses the fields relevant under that viewpoint and a method for constructing the taxonomy. Here, several methodological problems arise which are related to choice and guidance of the user (choice of a method, choice of a metrics, choice of the other parameters of the method…). These problems are out of the scope here since they are independent from data analysis; §3.3 addresses them.

Two methods have been implemented so far: the divisive k-means method and the agglomerative method of closest neighbours [START_REF] Day | Efficient algorithms for agglomerative hierarchical clustering methods[END_REF]. In both methods, the Minkowski metrics is used and reduced to Euclidean distance function of the standard deviation of each dimension.

Figure 4 shows the result on a sample real estate base with two viewpoints modelling the buyer-for-rental and the buyer-for-inhabiting behaviour. The following table gives the object field values. Under the first double bar are the first viewpoint fields (floor, price, area-1is it close to work and facilities -, surface and number of rooms) and under the second double bar, those of the second viewpoint (price, return-rate, and another partition into area considering if the inhabitants are usually wealthy…). Note that the area values are ordered numbers. Once supplied with the relevant parameters, the method is able to build the new taxonomy. The resulting taxonomy is made of a set of new classes (with dummy names) plus the set of objects attached to their most specific class (usually a singleton class). This taxonomy can be used in many ways:

• As usual output of data analysis methods, it can be seen as an abstract representation of the set of objects. • As a usual knowledge representation taxonomy, it can be seen as a set of abstract classes ordered by progressive specialisation. • But, it can be seen as only one step of the more elaborate process for achieving a more precise classification by: -Examining the relations of the resulting classes with other classes on other taxonomies (this is detailed in §4). -Revealing the lack of particular individuals in the panel for achieving a meaningful classification. -Revealing the inadequacy of the parameters provided to the method.

3.3.Integrating external libraries and controlling algorithms

So far, it has just been said that data analysis algorithms are able to produce new taxonomies when run adequately thanks to the correspondence given at §3.1. One important point in using data analysis algorithms is the use of numerous parameters (e.g. distance definition, number of classes per level, initial classes…). When the knowledge base is used by a taxonomist, it is useful for (her)him to have at hand the choice of the method to use for classifying. Moreover, the taxonomist would certainly appreciate having some help for controlling the available methods and the opportunity to interrupt the system and lead (her)himself the classification process.

For instance, our implementation of the k-means method allows the user to provide the initial centre of gravity of the classes, the number of classes and the distance. Moreover, the k-means method is a partition method and not a hierarchical clustering method. Thus the user is allowed to change the parameters of the methods at each call (i.e. at each class which require more partitioning) such that the number of class sub-divisions is not always the same.

SCARP [START_REF] Chevenet | A development shell for cooperative problem solving environments[END_REF][START_REF] Willamowski | Modelling methodological knowledge in data analysis[END_REF] is a problem solving environment developed in our research team and which must be ported on top of TROPES. It has already been used for integrating a set of data analysis algorithms in the domain of simple linear ordination (principal component analysis, factorial correspondence analysis and multiple correspondence analysis). The idea beside SCARP is the representation of the tasks to be carried out as objects and the interpretation of these particular objects through a specific process (called engine). Each task is the composition of more not. Hence the user has to decide the validation of inferred bridges. This has to be contrasted with a stronger kind of bridge inference based on the structural constraints on classes. expensive and low return-rate cheaper and higher return-rate Figure 6: The example of figure 4 does not introduce relevant bridges. As suggested there, the classification is constructed here with the help of price and return-rate only: it is a more natural representation of the buyerfor-rental view of the examples. Bridges can be though of as rules and the inferred bridges here can be interpreted as: big, attractive and expensive flats have a poor return-rate; small and cheap flats have a high return-rate (another bridge which is inferred the other way tells that flats with the highest return-rate are either small or medium sized). All these rules are quite correct. However, this is not ensured by the algorithm.

The bridge inference method is designed for a large number of objects and a relatively small number of classes. It is exponential in the number of classes (the exponent being the number of viewpoints) and linear in the number of objects. The worst case complexity is O(n C * n CV n V * n I ) in which:

n I is the maximum number of objects in a class; n C is the number of subclasses of the initial class; n V is the number of viewpoints, and n CV is the maximum number of classes per viewpoint. Bridge inference is nothing else than the search for correlation between two sets of variables. This correlation is particular from a data analysis point of view since it does not need to be valid on the whole set of individuals (the algorithm looks for subsets under which the correlation is valid) and it is based on strict set equality (not similarity). However, even if the bridge inference algorithm has been described with set inclusion, it can be helped by other measurements which will narrow or broaden the search. A solution for search narrowing consists in adding a threshold on the bridge cardinal (the number of instances concerned by the bridge) in order to obtain more likely bridges. A solution, in order to broaden the search, consists in adding a threshold on the cardinal of the difference (some elements can miss the bridge without invalidating it). More sophisticated tools can take the typicality of the excluded members as a mean to decide if the bridge can be retained: such a result can help tuning the data analysis method which has been used for classifying. More generally, the inclusion and emptiness tests can be replaced out by tests based on the similarity of two sets of objects (as it is usual in data analysis). In fact, many parameters can be taken into account when inferring bridges; for that purpose, the algorithm is function of the meaning of the operators ⊆, ∩ and =∅.

5.CONCLUSION

Taxonomies are produced in a systematic way by data analysis algorithms from a set of formatted data. T-TREE aims at reducing the distance between data analysis algorithms and the taxonomic repository. It is an extension of the TROPES knowledge representation system which allows to use data analysis classification algorithms whose input is a set of objects of the representation and output is a new taxonomy into the representation. The following advantages are brought by T-TREE:

• Numeric and symbolic properties are merged into the same base and manipulated the same way; • Objects and classes are ready to be used like in any knowledge-based system: T-TREE enables in the same framework to build, compare and use taxonomies; • The result of the classification process can be compared under several viewpoints. These viewpoints can differ in the method used for establishing their taxonomies, the parameters of the methods or the fields of individuals which are selected in order to build the taxonomy. • The integration of tasks into object-based knowledge models should allow to easily integrate important data analysis libraries and combine them. At that point of development, we are looking for data analysis libraries and significant workbench in order to evaluate the advantages of T-TREE.

An important problem is due to the difficulty to interpret the clusters provided by data analysis. there is no systematic way to provide a class description from the cluster: this has to be carried out by hand. Anyway, this remains a cornerstone problem to build symbolic description out of numeric characterisation of classes. Using machine learning conceptual clustering algorithms [START_REF] Michalski | Learning from observation: conceptual clustering[END_REF] for this task could provide the answer.

Further work remains to be carried out on T-TREE:

• adding graphic user interface (with the building of TROPES interface);

• implementing the methods as tasks (after the port of SCARP);

• integrating more important data analysis or conceptual clustering algorithms. A relevant result would be the interfacing with a complete classification library (e.g. SICLA [START_REF] Celeux | Classification automatique de données[END_REF]); • testing various distances taking into account non valued characteristics and studying their relationships with incompleteness handling; • testing methods for automatically building consensus trees from several taxonomies can also be applied as a way of evaluating the classification results.

Figure 1 :

 1 Figure1: The employee concept is visible under the Restaurant, Accounting and Functional viewpoints. Each of them determines a hierarchy of classes whose root class is named employee. For example, under the Functional viewpoint there is a decomposition of the set of employees following their functions. The CR Director object is attached to the vegetarian class under the Restaurant viewpoint, to the profit-sharing holder under the Accounting viewpoint and to the director class under the Functional viewpoint.

1 Figure 3 :

 13 Figure3: Part of the Flat concept with the flat#4 instance as it is provided by the user and as it is seen from viewpoints Income and Comfort. The constraints allow to express relations between field values: the first one concerns a change of unit; the second one the elaboration of a new field, expressing the ratio annual-rent on acquisition price of a flat; the last one attributes an area-1 number to a flat regarding to the district it is built in. It must be noted that the Income viewpoint only displays data which are not provided by the user but computed by the system.

  field\flat

  Under the Functional viewpoint, employees are divided into engineers, researchers, clerks, and other classes; researchers can be divided into directors, assistants and PhD students. An object is attached to (to be opposed to "is member of") only one more specific sub-class under a viewpoint, but is member of all the classes of which this class is a specialisation. Each viewpoint offers to the user a new taxonomy under which the classification operation depends on different criteria. They allow to focus on particular aspects of objects without being disturbed by others.

	Viewpoint	Restaurant	Accounting	Functional
			Employee
	Concept	Employee			Employee
	Employee
				Clerk
		Low-fat Regular Vegetarian	Profit-	Researcher PhD student	Engineer
			sharing		Assistant
					Director
			Object	Bridge
					Class
			CR Director

  The categorisation aims at introducing, in the already existing taxonomy, the computer employee class characterised as a class of employees working with computers whose work is technical. It first tests if this class can be a sub-class of the employee class, that which is trivially true. It then tests for clerk class but this is not possible since the nature of the work is not technical: clerk is thus eliminated. It then tests for technician which is selected as a possible super-class. The algorithm tries to continue downward but must eliminate researcher, engineer and chemist assistant since they have fields (publications for instance) that the computer employee class does not have. The most specific more general classes is thus reduced to technician.

			more
		employee	general
	clerk	technician
			computer employee
	researcher engineer	chemist assistant
			more
			specific
	Figure 2:

  The lines represent specialisation; the arrows represent bridges which can be inferred, see §4): Both hierarchies have been computed with the same (closest neighbours) algorithm. The results are quite good for the second viewpoint in which three classes are obtained (the interpretation is given under the classes). The first viewpoint provides two relevant classes one of which is quite wide and would require more tuning of the algorithm (for example by giving less importance to the area and using it only for distinguishing two close individuals).

	2 slight progression of return 3 1	4	6 difficult to rent 5 expensive,	1 intermediate floor 2 cheap'n small	4 medium size 3 low floor level 5	6 big, high attractive, expensive
							medium price
	Figure 4 (
		1	2		3	4	5	6
	floor	3	3		0	6	0	3
	price	31	20	35	80	75	100
	area-1	3	2		2	3	1	1
	surface	35	20	60	74	80	90
	nb-rooms 1	1		2	3	3	4
	area-2	1	3		2	1	2	2
	return-rate 0,8	0,9	0,9	0,5	0,5	0,4

elementary tasks or the representation of an implemented algorithm. There is a set of generic tasks such as sequence, iteration, alternative, parallel… which are executed by the sequential, iterative, alternative or parallel execution of their sub-tasks. This stops at the leaves of the task decomposition tree which are implemented by programmed methods. A problem to solve is supplied to SCARP as a high-level task. The engine dynamically monitors the task decomposition, classification and execution until the problem is solved. SCARP is co-operative in that it is able to carry out the task on its own but can be interrupted and directed by the user. eliminated by classification, dashed lines represent task decomposition and arrows represent the classification of a task into a more specific task): A classic analysis is first specialised according to the problem context (especially the characteristics of the matrix to analyse) into a principal component analysis. This task is then decomposed into its sub-tasks. After the execution of opening analysis the next sub-task, making PCA triplet, has to be executed. It has no sub-class and is therefore directly decomposed into its sub-tasks; in fact, the solving strategy indicates a choice between implicit and explicit weighting. Implicit weighting is chosen and in turn classified.

SCARP deals with several problems arising in T-TREE:

First, it allows external library integration. As a matter of fact, one of the advantages of describing the tasks into sub-tasks is the ability to add pre-and post-treatments to the task itself. Indeed, the standard format for data analysis algorithms is not the set of objects but the matrix. A formatting task can produce the matrix required by the chosen method.

Second, SCARP provides the help which the user needs for choosing (for example) among the available methods and to build (her)himself a resolution tree (a step-by-step mode is available). Moreover, SCARP is designed as a co-operative problem solving environment. It allows the user to stop the current resolution, change parameters or backtrack to a previous choice before starting the resolution again. For instance, it allows to implement the k-means method as a task and the classification algorithm as another task using the k-means method through iteration. Thus the configuration of the k-means method is done before each call to the task.

Third, the pre-tasks of SCARP allow to ask the user for the configuration of the method to be used or to acknowledge the choice made by a specialised task. For instance, the choice for a metric should be taken into account by a specialised task.

Up to now, the algorithms are run by hand with the user supplying the parameters directly to the algorithm. But, in the future, each method must be supplied with its own configuration interface. Also, only the classification mechanisms have been considered. Of course, any data analysis method such as correspondence analysis or principal component analysis can be integrated as well. Such methods do not produce any new classification but they can output data in the form of matrix file or graphic display. However, the output can be the filling of new fields corresponding to the dimensions of the result. These fields can be the input of an automatic clustering method in order to integrate the result in a taxonomy, achieving automatically what is usually left to the user's eyes.

4.BRIDGE INFERENCE

So far, the emphasis has been put on the building of a new taxonomy under a new viewpoint. However, one of the strength of TROPES is the ability to consider objects under several viewpoints. The comparison between viewpoints can be really useful for a taxonomist. Not only, T-TREE allows to build and use the taxonomies but it also allows to compare different taxonomies. An algorithm has been developed which is able to infer bridges. The bridge inference algorithm, given a set of source viewpoints and a destination viewpoint (built by T-TREE or by any other mean), returns all the bridges (in a minimal fashion) which are satisfied by the available data. That is the set of bridges for which the objects in every source class are indeed in the destination class. Establishing bridges helps the taxonomist in:

• considering if bridges are legitimate and so retaining them,

• checking if some particular kind of data, which invalidates bridges, is missing, or • demonstrating the differences between methods (or their sensitivity to particular data).

The algorithm compares the extension (set of members) of the presumed destination to the intersection of these of the presumed source classes. If there is no inclusion of the latter in the former, the algorithm is re-iterated on all the sets of source classes which contain at least one class which is a sub-class of the tested source classes. If the intersection of the extension of the presumed source classes is included in that of the presumed destination class, then a bridge can be established from the latter (and also from any set of sub-classes of the source classes) to the former (and also any super-class of the destination class). But other bridges can exists on the sub-classes of the destination. The algorithm is thus re-iterated on them. It stops when the bridge is trivial, i.e. when the source is empty. The algorithm is as follows: The algorithm is extension-correct (only valid bridges are inferred), extension-complete (all valid bridges are inferred) and extension-minimal (only more general bridges are inferred). The proof is carried out in the classification scheme framework [START_REF] Euzenat | Une définition abstraite de la classification et son application aux taxonomies d'objets[END_REF] and the "extension-" prefix just tells that what is considered is only the extension of the classes (the algorithm tests set inclusion on classes). Thus the result is not considered as valid in the logical sense of the term (two classes can share the same set of members, but are not necessarily equivalent). For instance, is that a coincidence that all directors have formerly been at the same university? Maybe, maybe


Jérôme Euzenat
email: jerome.euzenat@imag.fr

On a purely taxonomic and descriptive meaning for classes

Keywords:

Three different aspects of classes in object-based systems are studied: the distinction between classes and instances, the separation of ontological from taxonomic function of classes and their descriptive or definitional meaning. The advantages of using a descriptive and taxonomic meaning for classes are advocated. One of the important reasons for separating ontology from taxonomy is the multiplicity of taxonomies over a same set of objects and the independence of objects from these taxonomies. These distinctions ground the semantics of the object-based representation system Tropes. The specialisation relation in Tropes is examined under this light and the classification mechanism is interpreted under the descriptive setting. It is shown that the use of a descriptive semantics of classes can support a semantics for the classification mechanism. In fact, there is no intrinsic superiority of definition over description: the precision of the former is balanced by the generality of the later.

Classes versus individuals

William Woods distinguished between structural and assertional links in semantic nets [START_REF] Woods | What's in a link: foundations for semantic networks[END_REF]. This distinction is the composition of the distinction between classes and individuals on one hand [3] and the fact that these links assert information about an entity or are used for defining the entity on the other hand. For example, the distinction between assertional and structural interpretation of the class described by "a cup is a container with ears" is given by the phrasing "a cup is a container which can have ears" (structural), "a cup is a container which must have ears" (assertional-universal) and "this container is called a cup and has ears" (assertionalindividual).

These distinctions have to be made. However, the confusion between individuals and classes was only effective in semantic nets and early frame languages [16]. The class/individual distinction is already accounted for by the class-instance distinction of object-oriented languages (OOL) and post-frame languages (or OBR: artificial intelligence languages, such as KRL, SRL, and their commercial counterpart such as the ART and KEE object languages, based on the frame model but strongly inspired by object-oriented languages [START_REF] Masini | Les langages à objets[END_REF]). Moreover, the distinction in most existing OOL is sharp since the language for expressing instances is weaker than the one for expressing classes: instances can have values but cannot support added constraints. For instance, usual terminological languages allow to talk of "a man with less than three daughters" at the assertional level while an OOL can represent a man but cannot constrain the number of his daughters but by providing the list of the daughters. This is an acknowledged limit of this sharp distinction, however, the OOL world is changing (see [START_REF] Puget | Solver: contraints + objects = descriptions[END_REF]).

Definition versus description

Once classes and individuals are distinguished, the meaning of classes remains loose: they could be definitional if they provide necessary and sufficient conditions for being a member of the class, or descriptive if they only provide necessary conditions. This distinction led to terminological languages (TL, [START_REF] Nebel | Reasoning and revision in hybrid representation systems[END_REF]5]) which distinguish terminological and assertional components of TL: primitive concepts are descriptive classes, constructed concepts are definitional classes and individuals are descriptive individuals.

In contrast, the definitional or descriptive character of OBR had hardly been clearly stated (see for example the discussion in [START_REF] Davis | Views: multiple perspectives and structured objects in a knowledge representation language[END_REF]): even if it is often considered that the interpretation of classes is descriptive, they are sometime used like if it were definitional (for example when using automatic instance classification mechanism). A descriptive semantics of classes is provided below for OBR classes and this enables a clear interpretation of classification results. However, it is noteworthy that this interpretation never suffers from exception [START_REF] Brachman | lied about the trees" or, defaults and definitions in knowledge representation[END_REF]: classes are necessary conditions.

The defence of descriptive classes has two justifications: First, there are many descriptive concepts in the world to be modelled and this should be accounted for by knowledge representation (for instance, a researcher is an employee with a PhD but the converse is not true). Second, the descriptive interpretation is weaker than the definitional interpretation. Thus, more can be represented in the descriptive interpretation but less can be inferred. This means that any result on descriptive interpretation is also valid for the definitional interpretation and that it is possible to explicitly and locally strengthen the definitions in order to use the definitional interpretation. As a matter of fact, if a cup is characterised as a container with one ear, then from a definitional interpretation, it is possible to infer that an individual container with ears is a cup. From a descriptive interpretation, it can only be inferred that the individual container can be a cup.

Being versus being categorised

In classical OBR, there are strong implications of belonging to a class. But some of them are necessary while others are contingent (exemplified by the fact that an object can change class).

Classes, in many languages, are loaded with too much meaning. They merge the ontological aspects of instances (i.e. the conditions of their being: structure, integrity, identity) and the taxonomic aspects (i.e. the conditions for seeing them as a member of a class: domain restriction, relevant fields). There are two important problems here:

1. Ontological and taxonomic aspects are merged. One cannot merge both views together because this raises problems of integrity: does some object change class (breaking the integrity of the object) or is it replaced by another object with similar characteristics but belonging to another class (giving up identity of objects)? [START_REF] Carré | On multiple classification, points of view and object evolution[END_REF] Classes cannot play their role of categories in an identification system without breaking the ontological link with the objects.

2. There exist several different ways to classify objects in concurrent taxonomies (for example, employees in your firm are not categorised the same way by yourself or by your account agent). It is thus important to define the function of classes as ontological or taxonomic.

So far, three important distinctions for object-based knowledge representation have been made. They form the basis of the definition of Tropes. The remainder shows how these distinctions can be used in a coherent manner.

Tropes

Here is a short description of the Tropes system which distinguishes classes from instances ( §2.2) and ontology from taxonomy ( §2.3). The consequences of the descriptive character of classes are presented in the following sections.

Overview

Tropes [START_REF] Mariño | Multiple perspectives and classification mechanism in object-oriented representation[END_REF] is an object-based knowledge representation model. This means that individuals are represented as objects. These objects are partitioned into concepts (an object is instance of one and only one concept). As an example, the employee concept concerns all the entities which are employees. The fields relevant to objects are described in the concepts. The structure of an object is uniquely determined by a set of fields and their basic domains independently of the classes to which the object can be attached. The instances of the employee concept have a name, a salary and a publications field. The basic domain of a field is either a primitive type (real, integer, string, boolean), a concept, or a type constructed from these one (and only them) with the help of set and list constructors.

Objects can be seen under several viewpoints. A viewpoint determines the set of fields which are visible from that viewpoint. The employee instances can be seen under several viewpoints: as employees from the accounting viewpoint, as researchers from the functional viewpoint, as customers from the restaurant. . . The publications are not relevant to the restaurant viewpoint as well as the diet to the functional one, and thus the corresponding fields are hidden in the respective viewpoints. Thus viewpoints do have more in common with database views than with KEE viewpoints [START_REF] Filman | Reasoning with worlds and truth maintenance in a knowledge-based programming environment[END_REF] for instance. Viewpoints also determine a hierarchy of classes under which the instances of the concept can be classified. Classes introduce constraints on their member field values. They are related through the specialisation relation (whose interpretation is given at §3) and determine progressive subsets of the set of the instances of the concept. This progression is parallel to the reinforcement of the constraints added to sub-classes. Under the functional viewpoint, employees are divided into engineers, researchers, clerks, and other classes; researchers can be divided into directors, assistants and juniors. An object is attached to only one more specific subclass under a viewpoint, but is member of all the classes of which this class is a specialisation. The system is able, given a particular object, to find the classes under which it can be attached (this is called "classification" in knowledge representation and "identification" in data analysis). Bridges are knowledge components which link a set of classes under pairwise different viewpoints to a class in yet another viewpoint. The meaning of the bridge is that an object, which is member of each of the former classes, must be member of the later one. This allows, for instance, to infer that if an object is attached to the director class under the functional viewpoint, it is member of the profit-sharing employees under the accounting viewpoint.

In Tropes, the class is thus split into two separate units: the concept has in charge the ontological aspects of instances (i.e. the conditions of their being: structure, integrity, identity) and the class supports the taxonomic aspects (i.e. the conditions for seeing them as a member of a class: domain restriction, relevant fields). This allows to freely change the class of an object while its fundamental characteristics remain and to use several taxonomies simultaneously.

The usefulness of multiple taxonomies is twofold. First, one wants to use different related taxonomies (this is the case in biometrics when considering functional, chemical and evolutionary viewpoints on genes: there is a taxonomy for each viewpoint). Second, one wants to build a new taxonomy without discarding the current one (when testing a new hypothesis about the knowledge manipulated by the biometrician). For instance, from an already existing knowledge base containing an important set of objects, it is possible to run clustering algorithms for building another taxonomy on a new viewpoint and to compare it with other taxonomies.

Note that, in Tropes, the taxonomy is not part of the implementation level but of the knowledge level: it is aimed at representing man-made taxonomies and not these taxonomies that are the consequence of entity definitions (such as sub-typing, set-inclusion or structure subsumption in TL). They are compatible with them but not complete ( §3).

Of course, the ontology is not unique and given once for all: it can be different with regards to the application. However, there already can be several taxonomies in the same application.

Ontological prerogatives

Ontological prerogatives are attached to the concept. They are those which warrant the integrity of an object (i.e. that it cannot be modified in a way which would lead it to cease being an instance of the concept). This also includes the management of objects identity. In Tropes, objects are identified with the help of a key: a list of field values that uniquely corresponds to one object. The usual consequences with keys are related to integrity: an object without a key cannot exist and there cannot exist two objects with the same key (thus accidental co-reference is avoided).

These prerogatives play an important role at instantiation when the object is created and registered. They have in charge the management of existential dependencies from objects to the components they cannot exist without. During its lifetime, an individual, coming under some concept, is ensured that none of the above postulates is violated.

Moreover, the field values are part of the objects and do not depend upon the classes to which they are attached. Thus inference methods which represent implicit knowledge (valid deduction or value computation which must return the true value of an object) are attached to the concept itself [START_REF] Rechenmann | Integrating procedural knowledge: procedural attachment revisited[END_REF].

Contingency and taxonomy

As it has been said above the classification of objects is considered as contingent. Thus there can be several different classifications of the instances of the same concept: in a particular firm, the individuals are not considered the same way by the project management staff, the account office and the restaurant. Therefore the same individual is seen differently under several viewpoints and each viewpoint can have its classification of the same set of individuals.

Under a particular viewpoint, an object is attached to only one class (this was motivated by the argument that an object belonging to two unrelated classes is so under different viewpoints [START_REF] Mariño | Multiple perspectives and classification mechanism in object-oriented representation[END_REF]). This organisation is very useful since, from a particular viewpoint, one can classify an object with regard only to the relevant fields of the object. As a consequence, the set of classes to be considered is small, while considering the whole lattice of possible structures (e.g. Vegetarian-Profit-sharing-Clerk) would confuse the user.

A class defines constraints that objects must satisfy in order to belong to the class. It is a projection of the structure of the concept retaining only relevant fields and it defines an elaborated domain for the field values by refining the basic domain of the fields. This is achieved with the help of:

• Primitive domain restriction provided by domain enumeration, exclusion or bounding.

• Attachment restriction for concepts: the field values must not only be instances of a particular concept, but also be attached to particular classes of that concept.

• Cardinality restrictions on sets (resp. lists) by bounding the cardinality. It is noteworthy that constructed field values are true sets (resp. lists) and not multi-values, i.e. the value of the field are given by the corresponding set (resp. list) and not by a subset (resp. sub-list) of it which could be completed later.

As opposed to instantiation, objects can be attached to a class and can be detached from it at anytime. Classes also allow the expression of hypothetical knowledge in term of default values or default inference methods. The hypothetical knowledge is relevant here since default values (for example) are given with regard to the specificity of the object class. These values are not to be seen as the true value of a field but as hypothesis that can be made under a particular viewpoint. As a matter of fact, default values returned from different viewpoints do not have to be identical. For instance, it could be the case that research directors are usually fat while vegetarian are usually thin: what about a vegetarian director?

The former paragraphs exemplified the account of class/instance and ontology/taxonomy distinction by the Tropes system. The remainder is devoted to the descriptive meaning of classes. For instance, in French public laboratories, there exist research engineers and research assistant. The first ones belong to the engineers body while the second ones belong to the researcher body. However, the only objective difference between these people is the category under which they have been hired! And there is no classificatory relation between these categories. This classification is very important for its consequences: only researchers can become research directors, only engineers can earn particular subsidies. But, there is no ontological difference between the members of these categories (as a matter of fact, an engineer can later become a researcher; but this can only be achieved by passing the same procedures as other candidates). Hence there are two categories with the same characteristics and they belong to the same hierarchy. As a consequence, any man fulfilling the conditions can be suspected to be either a researcher or an engineer. This answers the critics made to TL that such classes must be primitive terms and are thus unclassifiable [START_REF] Doyle | Two theses on knowledge representation: language restriction, taxonomic classification, and the utility of representation services[END_REF]. It will be shown that the descriptive meaning for classes can support a specialisation relation and a classification mechanism.

The semantics of specialisation

The discussion above states the basic characteristics of a Tropes concept apart from the interpretation of the classification relation. The specialisation relation is given an interpretation according to a descriptive interpretation of classes. Next section shows that this descriptive interpretation does allow a correct and fruitful exploitation of the knowledge.

Set-based interpretation

The set-based view of Tropes only considers individuals, also called objects, and sets of objects (there are two kinds of sets: concepts and classes). The set of all objects is partitioned into concepts (one object belongs to one and only one concept). In a concept, several viewpoints over the same set of objects exist. A viewpoint on a concept corresponds to a structure (and not a partition) of the concept into hierarchically organised classes the most general of which, or root class, represents the whole concept.

As a consequence, classes are subsets of concepts. A class corresponds to a set E of objects which is called the extension of that class. The root class of each viewpoint represents the set of all the instances of the concept. Thus, an object is member of only one concept but of several classes: since Tropes can only attach an object to one more specific class by viewpoint, each class is divided into disjoint direct sub-classes. Classes are organised by the specialisation relation which is interpreted as inclusion (⊆) over their extensions. Consequently, there cannot be disconnection between classes of the same viewpoint (for each class but the root class, there is a class which includes it).

In order to allow cooperation between viewpoints (mainly during classification) bridges are introduced. Their set-based interpretation is that if a bridge goes from classes A 1 . . . A n to class B, then, each object belonging to each A i is also an object of B (thus A 1 ∩ . . . A n ⊆ B). For instance, a bridge exists from any root class of a concept to any other root class under another viewpoint of that concept.

The set-based interpretation is sound but not complete in the sense that not every inclusion based structure corresponds to a viewpoint.

Structure-based interpretation

Once again, in the structure-based interpretation, it must be distinguished between two kinds of entities: structures and values. An instance of a particular concept is characterised by a collection of fields. The structures corresponding to concepts or classes can be described by record types with typed fields [START_REF] Cardelli | Operations on records[END_REF] 1 .

The fields are defined for all the instances of a concept but viewpoints hide some fields and classes add constraints on others. Hidden fields are considered as existing but not relevant for specialisation. In other terms, there is no constraint on such a field in the classes in which it is hidden. The structure associated to a class thus denotes a potential extension P (the set of all expressible objects satisfying the record type corresponding to the class).

In the structure-based view, the specialisation relation is interpreted as sub-typing (<:) on record types (this also could have been the O-subsumption [START_REF] Napoli | Subsumption in object-based representations[END_REF]). It is noteworthy that the subtyping relation is not necessarily isomorphic to the specialisation relation. As a matter of fact, two classes can have the same definition (and thus the same type) without even being related by specialisation. This is the case of the above mentioned engineer/researcher example. However, the specialisation must respect the sub-typing relation: a class can be a specialisation of another class only if the type corresponding to the former is a sub-type of the class corresponding to the later.

The structure-based interpretation of a bridge which relies classes A 1 . . . A n to class B is that the record type associated with each of the A i is a sub-type of the one associated with B (thus for each i, A i <: B). This is a requirement of the Tropes model which is used in order to infer the necessary consequences on the record types.

Putting set and structure together

In fact the set-based and structure-based approaches reinforce each other and the relation made of set inclusion and record-type sub-typing is the specialisation relation. The next step after that dual explanation of the specialisation relation consists in determining if the interpretations are equivalent and, if not, which one prevails. In other terms: "Am I in such a set because of my structure" or "Do I have such a structure because I am in such a set?".

Here comes the idea of necessary and sufficient conditions to belong to some class. When an object is voluntarily and successfully attached to a class, first, the structural conditions are met by the object and, second, the user decided to make of the object a member of the class. In this action, the type-checking which is necessary for successful attachment constitutes a necessary condition only grounded on the class structure, and the intent which is necessary for voluntary attachment constitutes a sufficient condition. There is no equivalence between E and P , but the general result is that E ⊆ P : if you got a PhD and are a member of the laboratory, you can be a researcher but maybe you are not, you are the cook. However, without a PhD, you cannot be a researcher.

Thus, the class definitions in themselves are (independently of their set of objects E) to be interpreted according to the descriptive interpretation of classes: they provide conditions that all attached objects must respect.

Classification and description

In order to show the usefulness of classification in a system whose semantics is given in terms of descriptions, a clear definition of classification is first given independently of any class system ( §4.1). Then, the interpretation of classification and categorisation is given in the context of Tropes ( §4.2).

General view of classification

Classification takes place over sets of abstract entities L C and L I the members of which are respectively named categories and individuals. An individual i can be classified under a particular category c. Here, these categories are just labels to put on entities and do not carry any meaning. They are assigned an interpretation for a particular system. The classification aims at determining the set Cl(i) of categories in which an individual i is classified. The set of individuals i such that c ∈ Cl(i) is called the extension of c (and noted

In(c) = {i ∈ L I ; c ∈ Cl(i)}).
The set of categories is usually organised into a taxonomy (in the sense used in [START_REF] Woods | Understanding subsumption and taxonomy: a framework for progress[END_REF] for instance). A taxonomy is a structure made of a set C of categories and a relation ≤ on these categories which respects the extension inclusion property:

c ≤ c ⇒ In(c ) ⊆ In(c).
As it is convenient to represent a taxonomy with the help of its transitive reduction [START_REF] Aho | The transitive reduction of a directed graph[END_REF], it is also convenient to represent the result of a classification with its minimisation. The minimisation of a set S with regard to a partial order R over its elements is defined by: µ R S = {x ∈ S; ∀y ∈ S, yRx ⇒ xRy}.

It retains only minimal elements for R. Hence, the minimal categories of an instance i are µ ≤ Cl(i). Terminal categories of an instance i is the set

νCl(i) = Cl(i) ∩ µ ≤ C.
It is the set of solutions which do not have sub-categories (or the set of leaves in which i is classified; the set µ ≤ C is called the terminal categories of the taxonomy).

For the purpose of describing classification algorithms, the following terms are defined: the sub-classification is the operation which classifies an object i in the sub-categories of a particular category c (which is called the initial category):

Cl c (i) = Cl(i) ∩ {c ∈ C; c ≤ c }.
The categorisation (or class classification) supervises the construction of a taxonomy. It determines incrementally the relations between a new category and the already categorised ones. The categorisation helps constructing the ≤ relation according to a sub-categorisation criterion ( ) external to the relation to be constructed but taking into account the already constructed part of this last relation. Intuitively, this criterion represents the loosest constraints that ≤ must respect in order to be a taxonomy. Thus, the property of is that

∀c, c ∈ L C , c c ⇒ In(c) ⊆ In(c )
and any graph built with its help will respect the property

∀c, c ∈ L C , c ≤ c ⇒ c c .
To that extent, the categorisation of a category c determines its more general categories (M GC) and more specific categories (M SC) with regard to the criterion:

M GC(c) = {c ∈ C; c c } and M SC(c) = {c ∈ C; c c}.
If the newly introduced category is a sub-category of only one of its more general categories and all its sub-categories are sub-categories of its super-category, then the relation is a taxonomy. For summarising, a classification scheme is given by a set of categories (C), a sub-categorisation relation (≤) and a sub-categorisation criterion ( ). The first element allows classification, the second the expression of a taxonomy and the third the construction of that taxonomy. L C and C ≤ defines two partial orders, the later being a subset of the former. This ensures that the taxonomy under which individuals are classified respects the extension inclusion.

From the properties of a given ≤ relation, it can be defined two important properties of the classification process [START_REF] Euzenat | Une définition abstraite de la classification et son application aux taxonomies d'objets[END_REF]:

Univocity : a classification scheme is univocal iff ∀i, | µ ≤ Cl(i) |= 1.
This means that there is a unique minimal category for any individual. This property is important for representation languages in which an individual can only be attached under a unique category because it allows automatic classification (i.e. always attaching an individual under its minimal category).

Determination : a classification scheme is determinant iff ∀i, νCl(i) = µ ≤ Cl(i).
This means that any individual is fully characterised by minimal classes. This is very important for biological taxonomies in which an individual is necessarily in a terminal taxon (there is no raw mammals -i.e. mammals which are not members of a sub-category -they are either primates, rodents. . . ).

The two later properties can be affected with an objective or subjective character. This character is related with the incompleteness of a knowledge base. The subjective properties are in the subject (user)'s mind, the objective properties are in the object (category definitions). As a consequence, the system can check the objective properties but not the subjective ones (for example, OBR classically require that procedural attachments do not lead to side-effect but cannot check it: this is a subjective property). Knowing that a property must hold, even only subjectively, can be useful (for instance, when proving that the negation of that property objectively holds, the system can report the problem).

Moreover, the incompleteness of objects can lead to the incompleteness of the classification of that object (thus, even if the classification scheme is determinant, the classification process cannot reach the minimal class).

Consequences for classification in Tropes

Tropes taxonomies are hierarchies with no exhaustivity (the specialisations of a particular class are not required to cover the class) and subjective exclusivity (an object can only be classified in one direct specialisation of a class it is classified in; but the system cannot check it generally). Moreover, objects to be classified can be incomplete and, as a consequence of the descriptive character of classes, the fact that an object satisfies a class definition is not sufficient to attach it to the class. Hence, there is no determination and no univocity, so that automatic classification is impossible [START_REF] Euzenat | Une définition abstraite de la classification et son application aux taxonomies d'objets[END_REF]. Such a result would have been dramatic for a purely definitional system, this is not the case for a descriptive one: the interpretation is given below.

Classification

Instance classification in Tropes classifies an object into a taxonomy. Thus, only C and ≤ are relevant. C is the set of classes in a particular viewpoint of a concept and ≤ is the specialisation relation. The object to be classified is necessarily an instance of the initial class c: an instance is attached to a class in each viewpoint (this could be the root class). Its field values are necessarily compliant with the class constraints (even if the value is unknown: this is an advantage of instantiation and attachment) and thus respect all the necessary and sufficient conditions over this class.

The sub-classification process goes down along the taxonomic tree by taking advantage of the sub-type relation between record types associated to classes in specialisation relation and the result given at §2.3: E ⊆ P . Thus it is able to classify the object in the more specialised classes in which the object respects the necessary conditions provided by the structure (and thus, are in P ). So, the classification mechanism uses both sides of the specialisation relation: type checking for deciding if an object can belong to a class and set-based specialisation for deciding in which classes to sub-classify next.

The set µCl(i) is not necessarily a singleton, is not empty (since the initial class is in Cl(i)) and is not necessarily a set of classes with no further specialisation. This result is no more than formal and must be interpreted with regard to the semantics of Tropes. The interpretation of that result in a descriptive framework is that the object can belong to any class in which it has been classified. But, since the object only complies the structural constraints and that they are only necessary but not sufficient conditions, it is up to the user to decide in which class to put the object by an explicit statement. This is the only way to meet the set-based sufficient conditions.

Categorisation

For Tropes, the criterion relation ( ) is the sub-type relation (<:) over the record-types associated to classes (note that this is different from the sub-categorisation relation which is specialisation). As for classification, sub-typing only determines necessary and not sufficient conditions for being a specialisation since the structure-based interpretation is not complete.

Thus, again, the interpretation of categorisation, according to the descriptive interpretation of classes, is that the categorised class can be a specialisation of all of its M GC and all of the M SC can be a specialisation of it. So, the user must choose the class of which c is a specialisation among M GC(c), and the more specialised classes than c among those M SC(c) which specialise the former one; but (s)he does not have to choose them all.

Hence, the resulting taxonomy is not necessary complete (w.r.t. the sub-type relation) but the categorisation process is (w.r.t. existing specialisation relation).

Extensions allowed by the weakness of descriptive semantics

Nothing requires that all viewpoints have the same interpretation. In a future development of Tropes, it is foreseen to add latitude: under some viewpoint, classification can be strictly based on sub-type (i.e. P = E). Moreover, if one retains this interpretation, (s)he can use specific classification algorithms which take advantage of this. As a consequence, this would allow automatic classification just like in TL. Moreover, if there were multi-specialisation in Tropes (the specialisation relation would be a direct acyclic graph and not a tree but its semantics would remain the same) it could be possible to build a complete taxonomy. This can be achieved by automatically making a class a specialisation of all of its M GC and all of its M SC a specialisation of it [START_REF] Capponi | Construction incrémentale d'une base de classes correcte du point de vue des types[END_REF][START_REF] Euzenat | Une définition abstraite de la classification et son application aux taxonomies d'objets[END_REF]. As a consequence, the specialisation relation is immediately induced by the criterion (i.e. sub-typing) and the specialisation relation would be the sub-type relation. This would lead to the property of univocity.

As a conclusion, the use of classification and categorisation in Tropes is grounded on the semantics of the specialisation relation which, in turn, is grounded on the descriptive interpretation of classes. In fine, classification is still compatible with the descriptive interpretation of classes.

Related works

The three presented alternatives can be found in different representational systems: Class/instance : semantic nets and early frame languages do not discriminate between classes and individuals. But in all but some OBR systems and OOL, the distinction is made. It is noteworthy that this confusion has been also made by early logicians and corrected later on. In TL, this distinction can be found in the difference between assertional and terminological components. However, this is changing due to the critics emitted in [START_REF] Doyle | Two theses on knowledge representation: language restriction, taxonomic classification, and the utility of representation services[END_REF].

Ontology/taxonomy : there has not been a lot of works carried out on these aspects. OOL usually have purely ontological classes while TL have purely taxonomic ones. However, Rome [START_REF] Carré | On multiple classification, points of view and object evolution[END_REF] has been the first system to explicitly separate ontology from taxonomy. The system makes an object instance of an instantiation class borrowed from OOL and let it be classified under a representational class related to OBR. This system does not separate the base into different viewpoints and there is only one taxonomy. Not explicitly referring to the ontology/taxonomy distinction, Views [START_REF] Davis | Views: multiple perspectives and structured objects in a knowledge representation language[END_REF] already offers the possibility to organise knowledge into multiple taxonomies. However, the semantics of relations is not given in a taxonomic setting (thus the user has to ground and implement classification) and the ontological apparatus is presented as useless platonism.

Definition/description : OBR usually consider (even if not explicitly) descriptive classes while TL consider definition (see above).

It is noteworthy that Tropes characteristics are a combination of those of OOL and postframe languages. In fact, OOL classes have concept prerogatives (methods, instantiation, weak typing) with instances which cannot change class and OBR classes have class prerogatives (default inference, strong typing) with instances which can migrate. However, in the objectoriented view of Tropes the message-passing control mechanism and the specialisation of concepts are missing. It has been suggested that, in Tropes, concepts represent TL primitive descriptions and classes are constructed description. This is not adequate, since classes are interpreted descriptively.

Conclusion

A clear semantic account has been given of a system which separates the ontological aspects of classes from their taxonomic aspects. Moreover, the categorisation is grounded on the very general notion of description instead of definition. This generality prevents from using a classification system as straightforward as that of definitional systems but still allows a clear definition of classification which therefore can be used adequately. Tropes offers several other facilities, due to multi-viewpoints and the descriptive semantics, as for instance, the capability to build a new classification from objects with clustering or data analysis algorithms or that of using different classification algorithms on different viewpoints depending on particular reinforcement of the specialisation semantics.

The definition of Tropes semantics including inference mechanisms is not yet completed. The theoretical complexity of relevant algorithms promises to be very high but, from our experience, its practical impact is not critical, mainly because the complexity is on classes and not on objects (it remains high on recursive types but not practically). In fact, the problems are exactly the same as for definitional languages such as TL.

Figure 1 :

 1 Figure 1: The employee concept

Recursive types will have to be introduced in Tropes and this requires a more powerful type system[START_REF] Amadio | Subtyping recursive types[END_REF][START_REF] Nebel | Terminological cycles: semantics and computational properties[END_REF]. However, recursive types are not dealt with here and it can be considered that the structure of a class is the definition of a record type.


Ahmed Amine Loukili

Damien Saucez

Thierry Turletti

Mathieu Bouet

Content Distribution and OpenFlow: a Reality Check

Keywords: SDN, benchmark, content distribution

With the advent of virtualization and network function softwarization, the networking world shifts to Software Defined Networking (SDN). The OpenFlow protocol is one of the most suitable candidates to implement the SDN concept. In the meanwhile, the generalization of broadband Internet (mobile, cable, DSL, fiber etc.) has led to massive content consumption. However, while content is usually retrieved via layer 7 protocols, OpenFlow operations are performed at lower layers (layer 4 or lower) making the protocol completely ineffective to deal with content. To address this issue, we proposed and developed an API to manage content in OpenFlow networks. We implemented this API using open source software and study the impact of logical centralization suggested by SDN on network performances.

I. INTRODUCTION

Over the last decade we have seen the generalization of virtualization in networking. More specifically, the SDN approach aims at making networks programmable thus enabling network operators to automate their network management. OpenFlow is one of the most used SDN protocol. It relies on a separation between the control plane and the data plane [START_REF] Mckeown | Openflow: Enabling innovation in campus networks[END_REF] and matchaction rules on layers 1 to 4. In parallel to the advent of SDN, network communications have diverted to massive content distribution via the HTTP protocol that operates at the layer 7 of the networking stack (e.g., YouTube). As a result, OpenFlow cannot be directly used to manage content distribution.

To reconcile content distribution and OpenFlow, we developed a content distribution RESTful API and implemented it by extending the OpenFlow controller and using HTTP proxy middleboxes. The proxies determine the contents that are actually requested within TCP flows. This information is then propagated to the controller that can make the association between contents and TCP flows to finally optimize the network via OpenFlow rules.

With the demonstration, we show that the choice of the architecture implementing the API has a major effect on the control plane and therefore on the feasibility of the solution: by introducing the notion of control plane caches, a centralized approach can be used to manage content distribution with OpenFlow without impairing network performances.

In Sec. II we present the architecture that implements our content distribution API relying on OpenFlow. In Sec. III we provide first performance figures for the architecture. Finally, in Sec. IV we conclude this work.

II. ARCHITECTURE

Our architecture provides content distribution management with OpenFlow. To that aim, we developed a RESTful API1 modeling the content distribution network as an abstract graph. The data model defines three atomic types: compute nodes for functions related to processing (e.g., process, CPU), storage nodes for data related operations (e.g., file, hard-drive), and network nodes for all operations related to the network (e.g., routes, NIC) and the composition of complex entities is called a slice. For example, a router is composed of network ports (network nodes), processors (compute nodes), and memory (storage nodes). All these components are modeled independently and grouped by a slice to compose the router.

The API links contents and network but content distribution relies on HTTP while OpenFlow matching is limited to the lowest layers of the network stack (i.e., up to transport layer). Thus, implementing the API requires to use HTTP proxies. The interaction between OpenFlow, HTTP proxies, and the centralized controller is depicted in Fig. 1 where all components interact by the means of the API.

The API links contents and network but content distribution relies on HTTP while OpenFlow matching is limited to the lowest layers of the network stack (i.e., up to transport layer). Thus, implementing the API requires to use HTTP proxies. The interaction between OpenFlow, HTTP proxies, and the centralized controller is depicted in Fig. 1 where all components interact by the means of the API. We leverage the logically centralized approach of OpenFlow to simplify the management of the infrastructure. However, networks being inherently distributed systems, and concentrating all information and decisions would impair performances by causing high signaling load. Therefore, as illustrated by Fig. 1, decisions are performed centrally by the controller, but pushed in the network components that dispose of a control plane cache, thus avoiding to load the controller with data plane events.

The central entity controlling the network extends the OpenFlow controller to link content and network operations with the API. This API is used to retrieve content information from the HTTP proxies and to manage them, but also to program the storage or migration of contents on various storage servers of the network. Furthermore, combined with the OpenFlow controller, it permits to manage OpenFlow switches to optimize network operations as well. A naive way of implementing the centralized control would be to ensure that at any time the central controller disposes of all information of the network and that all the components of the network query the controller whenever they have to make a decision. This approach guarantees the decision consistency but at the expense of the scalability since the control plane load would be directly proportional to the data plane load.

To tackle this issue while keeping the advantage of centralization, we extend the concept of OpenFlow flow table. We propose control plane caches that store, locally on the network components, the result of computations of the controller. This way, instead of querying the controller to know what operation to perform, network components query their local control plane cache. In OpenFlow switches, the control plane cache corresponds to the flow table, while in the HTTP proxies it is an indirection table that determines how to tag packets so that they can be processed adequately by OpenFlow switches. With this approach, managing the control plane becomes a database synchronization problem where network components feed the database with data plane information and the controller process the information to decide data plane operations.

The controller bases its decision on knowledge of the network status and traffic flows. However, in most situations, the controller is out-of-band and must query the data plane components (i.e., switches and proxies) to obtain the information. Therefore, to avoid the data plane components to send such information to the controller at the data plane rate, the control plane cache is also used to temporary store data-plane statistics collected by the data plane components and the controller periodically retrieves this information. The frequency of updates is a tradeoff between the scalability and the reactivity of the system. 2III. DEMONSTRATION We prototyped our architecture with open source software. We use Open vSwitch [START_REF]Open vSwitch[END_REF] and Floodlight [START_REF]Floodlight OpenFlow Controller -Project Floodlight[END_REF] for OpenFlow parts, and CherryProxy for the HTTP parts [START_REF]CherryProxy -a filtering HTTP proxy extensible in Python | Decalage[END_REF]. The REST API and the control plane cache are implemented with Flask [START_REF]Flask (A Python Microframework)[END_REF] and PostgreSQL [START_REF]PostgreSQL: The world's most advanced open source database[END_REF].

For this lecture demonstration, we will show the impact of the control plane cache on the network load. To that aim, we consider three scenarios: (i) fully-centralized, (ii) semi-centralized, and (iii) fully-decenralized control plane caches. The first scenario is the case where all information and decisions are treated by the controller, i.e., no cache. The semi-centralized scenario is the situations where the control plane caches only store the data plane decision made by the controller. Finally, the fully-decentralized control plane scenario is the one where all information are cached in the data plane network components.

Fig. 2 is an example of results we will show during the demonstration. It shows the evolution of the data plane and control plane rates with the content demand rate. Each network function runs in a separate virtual machine deployed on the same host. As expected, the fully-decentralized approach guarantees a control plane load independent of the data plane rate. On the contrary, the fully-and semi-centralized scenarios show a rather linear correlation between control and data plane rates. Interestingly, when control plane caches are used, the proxy requires more CPU cycles to process flows, which reduces the data plane rate. With a fully decentralized control plane cache this phenomenon is compensated by the suppression of traffic with the controller but when the controller is involved, it results that a fully centralized approach offers slightly better, though not significant, data plane rates.

IV. TAKE AWAY MESSAGES

We present an architecture to implement a content distribution API in OpenFlow networks. Our architecture demonstrates that OpenFlow can be used to distribute content using a centralized approach without impairing network performances.

BIOGRAPHIES

Ahmed Amine Loukili received his master degree in Ubiquitous networking and computing (UBINET) from the Universit'e Nice Sophia Antipolis, France, and an engineering degree in Telecommunication and networking from the National School of Applied Sciences of Tangier (ENSAT), Morocco

Fig. 1 .Fig. 2 .

 12 Fig. 1. SDN-enabled content distribution architecture.

  in 2016. His master internship at Inria Sophia Antipolis is entitled Content Distribution over SDN. His current research interest is NFV/SDN. Damien Saucez received his master degree in Computer Science engineering from Université catholique de Louvain in 2007 and his Ph.D. thesis entitled Mechanisms for Interdomain Traffic Engineering with LISP in 2011. Since 2011, he has been working as a resercher at Inria Sophia Antipolis. His current research interests are information-centric networking (ICN) (e.g., routing and congestion control), Software Defined Networking (SDN) (e.g., resiliency and robustness), and largescale experimentations. He is actively contributing to the IETF and IRTF. Thierry Turletti is a senior research scientist in the DIANA team at Inria Sophia Antipolis. He received M.Sc. and Ph.D. degrees in computer science from the University of Nice-Sophia Antipolis, France. His current research interests include Software Defined Networking, network experimentation platforms, and wireless networking. He is serving on the editorial boards of the Wireless Networks and Advances in Multimedia journals. Mathieu Bouet received his PhD degree from the Computer Science laboratory (LIP6) of Pierre & Marie Curie University (UPMC), France, in 2009. Since 2009, he has been working as a research engineer at Thales Communications & Security, where he first conducted research on autonomic networks and cyber-security and then initiated and developed activities on software-defined networking and network functions virtualization. In 2014, he became the technical manager of the Network Softwarization research group. He coordinates several collaborative research projects on this topic. His current research interests are the softwarization of IP and mobile networks (routing and traffic engineering, mobility, new architectures and performance).

Available at https://github.com/Rzozi/Contentdistribution

Upon exceptional events, the control plane cache can be bypassed to directly inform the controller.

ACKNOWLEDGMENTS

This work was supported by the ANR DISCO Project (ANR-13-INFR-013).