An ability to extract hidden and implicit knowledge, their integration into a knowledge base, and then retrieval of required knowledge items are important features of knowledge processing for many modern knowledge-based systems. However, the complexity of these tasks depends on the size of knowledge sources, which were used for extraction, the size of a knowledge base, which is used for the integration of extracted knowledge, as well as the size of a search space, which is used for the retrieval of required knowledge items. Therefore, in this paper, we adapted the algorithm for the decomposition of homogeneous classes of objects, within such knowledge representation model as object-oriented dynamic networks, to perform dynamic knowledge extraction and retrieval, adding additional filtration parameters. As the result, the algorithm extracts knowledge via constructing only semantically consistent subclasses of homogeneous classes of objects and then filters them according to the attribute and dependency queries, retrieving knowledge. To demonstrate some possible application scenarios for the improved algorithm, we provided an appropriate example of knowledge extraction and retrieval via decomposition of a particular homogeneous class of objects. In addition, we developed algorithms for objects' decomposition for their run-time usage and database storage, which allow the generation of instances for subclasses created during the class decomposition, and to perform knowledge extraction on the object level.
The extraction and retrieval of knowledge are important features of many modern knowledgebased systems. Such systems are capable to extract new knowledge by analyzing relevant knowledge sources, integrating it with previously obtained knowledge, and allowing users to search for necessary knowledge items in the knowledge base. Depending on the chosen knowledge representation model, the extraction of new implicit and hidden knowledge can be implemented in different ways. For object-oriented knowledge representation models, knowledge extraction can be performed via universal exploiters of classes, such as union, intersection, difference, and decomposition, which allow the construction of new classes of objects based on the existed ones.
In this paper, we study the decomposition of homogeneous classes of objects, within such knowl edge representation model as object-oriented dynamic networks, to demonstrate that the algorithm for decomposition of classes can be used as a tool for knowledge extraction and retrieval. For this pur pose, we improved the algorithm for decomposition of homogeneous classes of objects, which was proposed in [28], by adding more additional parameters, that allow adaptation of the algorithm, devel oped for knowledge extraction, to dynamic knowledge retrieval. We also discovered that classical methods of formal concept analysis do not cover internal semantic dependencies among properties and methods of homogeneous classes of objects. In addition, we show how the improved algorithm can reduce the search space during the retrieval of implicit or hidden knowledge, which cannot be obtained using standard methods of formal concept analysis.
Among the variety of formal systems for the analysis and processing of conceptual knowledge, formal concept analysis is one of the most developed frameworks, which is based on the mathematical theory of lattices. It provides tools for the construction, analysis, and processing of conceptual hierarchies, represented in terms of two isomorphic complete lattices of objects and attributes. Since lattices consist of chains, which are posets, it allows inference and retrieval of new concepts within the corresponding formal context. Let us consider the main concept of the formal concept analysis described in [20, 21]. The first step is the definition of the formal context.
Definition 1. A formal context is a tuple , where is a set of its attributes, and is a relation between has an attribute , i.e. or . is a set of objects of the context, while and , which express that an object Using this definition, any formal context can be represented by a corresponding cross table, where columns mean attributes, while row mean objects. It allows considering a set of common attributes for a set of objects, and a set of objects that have attributes from a set of common attributes.
from the set
. 3.
A A set of common attributes for selected set of objects is a set , i.e. all attributes from the set are common for all objects set of objects with the common
attributes , i.e. all objects from the set have all attributes from the set is
set a .
Using these notions, we can define a formal concept based on a particular formal context Definition 4. A formal concept of the formal context is a pair
Such definition of the formal concepts, i.e. using the notions of an extent and an intent, is similar to combination of two ways of set definition, described in [22]. In the first case, a set can be defined by particular elements (tabular form), while in the second one, it can be determined using the attributes, which must have all elements of the set (set builder from). In addition, according to [16], the notion of a formal concept is also similar to a combination of two theoretical forms of class consideration – an extensional and an intensional. From the first perspective, a class can be defined by the list of its ob jects, while from the second one it can be defined by the set of attributes. The definition of the formal concept proposed in [20] combines these two perspectives into a single notion and provides an opportunity simultaneously to consider a particular formal concept using both of them.
Since a formal context can define a certain number of formal concepts, there is a sense to define a set of all formal concepts.
Definition 5. A set of all formal concepts of the formal context is a set .
Formal concept analysis has different applications within an area of knowledge processing. Ac
cording to [31], conceptual knowledge retrieval is one of the main categories among the variety of
methods of formal knowledge processing. On another side, these methods allow the implementation
of corresponding functionality within knowledge-based systems developed based on formal concept
analysis. In general, the knowledge retrieval task can be simply described as querying a knowledge
base to find the required knowledge items. According to [
Nowadays, there are a few approaches, which propose the application of the formal concept analy sis to studying dependencies within the procedural program constructions. One of such was proposed in [30], the main idea of which is to construct the concept lattice of decomposition slices of the pro gram. It provides an opportunity to analyze groups of the ordered program statements, called decomposition slices, related to a particular context, for example to a variable. In other words, each particular variable, which is a part of the program, depends on the corresponding ordered sequence of operators, which somehow use or change its state. However, the proposed approach was designed for pro cedural programs, but not for object-oriented ones. Consequently, it is more suitable for the structure analysis of procedural knowledge than for the analysis of declarative knowledge represented in terms of classes. A similar approach, but for the analysis of class methods cohesion, was proposed in [29]. The main idea is to consider dependencies between different program statements within a particular method of a class and define the corresponding formal context using them, and then construct the con cept lattice called a cohesion lattice. However, the approach does not pay the attention to the external dependencies of class attributes used in the method with other properties and methods of the class, which are important for the decomposition of homogeneous classes of objects.
Usually, a formal context is defined using a set of attributes and a set of objects, where attributes have corresponding values encapsulated in a particular object. However, a formal context can also be determined using a set of classes and a set of attributes. This idea was used in [13, 14] to analyze the structure of classes in the Java programming language, in particular, to consider the interrelation be tween methods call of a class and then optimize its structure. The embedded call graph provides addi tional information about the interaction between methods of the class, which is absent in the corre sponding concept lattice. However, such an approach covers only dependencies between methods of the class and does not pay the attention to other kinds of dependencies, for example, between properties, properties, and methods of the class. Another application of the class formal context was pro posed in [23], which was used to analyze the class cohesion via the construction of the corresponding concept lattice called cohesion lattice. They capture the cohesiveness of a class and its members, which provides an opportunity to reorganize the class structure more efficiently, increasing cohesion. However, cohesion metrics are rather quantitative measures of dependencies among class members, than qualitative. Many approaches to class cohesion measurements pay the attention to dependencies’ existence but not to their semantics and consistency within a modeled domain, which is crucial for the decomposition of homogeneous classes.
One of the known approaches, that considers dependencies between the attributes of an object, is
the detection of functional dependencies in relational databases. As it was noted in [
An alternative approach to the analysis of dependencies between attributes of objects was pro posed in [25], according to which an attribute depends on another attribute , i.e. , whenever the presence of is not significant without the presence of and also may be atomic, as well as conjunctive or disjunctive attributes. However, such an explanation of the dependency between attributes is quite fuzzy because it is unclear how to verify that presence of one attribute is not significant without the presence of another one, as well as what the term significance should be meant here.
To consider what internal semantic dependencies of a class are, their kinds, and how they affect the decomposition of the homogeneous classes of objects, let us consider the definitions of a homoge neous class of objects and its subclass within such knowledge representation model as object-oriented dynamic networks (OODNs), which was proposed in [26, 27].
Definition 6. The homogeneous class of objects is a tuple is a collection of properties which define the structure of the class , while
is a collection of its methods, that define its behavior.
Definition 7. A homogeneous class of objects is a subclass of homogeneous class of objects , and , are specifications and signatures of the class and , respectively.
Let us consider an example of a homogeneous class of objects and analyze its specification and signature to understand how the properties and methods can depend on each other, creating internal semantic dependencies. For this purpose, let us define a homogeneous class of objects , which describes a concept of a point on a plane, and has the following structure: where and and are quantitative properties, which mean coordinates of a point ; and are methods, which return and coordinates of a point , respectively; are methods, which provide an opportunity to set a value of and coordinates of a point , respectively.
Now let us define another homogeneous class of objects gle on a plane, and has the following structure: , which describes a concept of a trianwhere , , and are quantitative properties, which mean vertices of a triangle, defined as objects of the class ; is a qualitative property, which means satisfiability of the triangle inequality and is defined by the following verification function: where , , and
are defined as follows: is a method, which returns the coordinates objects of the class and is defined as follows coordinates for a vertex of a triangle for a vertex of a triangle in a form of
; is a method, that set and is defined as follows is a method, which returns a distance between fined as follows: and of a triangle , and deis a method, which returns the perimeter of a triangle and is defined as follows , where , , and are defined in the same way as in for the .
Let us consider the class as a collection of properties and methods, i.e.
We denote an -th property of the class by , and a -th method – by for a more compact representation of all statements noted below.
As it was noted in [32], for the class we can construct subclasses, which create the power set lattice , which is a complete lattice and where is a set of all possible unique subsets of the set . From the decomposition perspective, we need to consider only subclass, which are nonempty ones and create the join-semilattice , which describes the search space for the knowledge retrieval. This semilattice is not a concept lattice, however as it was demonstrated in [28], it can crucially reduce the space search for the solving decomposition constraint satisfaction problem.
To compare the opportunities provided by the join-semilattice of nonempty subclasses of the ho mogeneous class of objects and the concept lattice of all its subclasses, let us define the formal context of all possible subclasses of the class and then construct the corresponding concept lattice. For this purpose, let us consider the formal context and define the corresponding cross table for it.
We do not provide a full cross table here because of its size, however, Table 1 illustrates the basic in tuition for the definition of formal context . We use the symbol plus to specify the pair of the relation where . An object is defined as follows , , , is a -th subclass of the class , which has a cardinality of and is a binomial coefficient, which is equal to a number of all possible unique subsets of the set cardinality ; and where an attribute (property or method) is defined as . , which have a
Now, let us construct the concept lattice for the formal context using the Table 1. Analyzing the results, depicted in Figure 1, we can see, that the constructed concept lattice has a big size and contains all formally possible subclasses of the class and all possible formal concepts of the context
. Considering the constructed concept lattice, we can ask a question about the semantic consistency of all constructed subclasses of the class , as it was done in [28]. To clarify the problem and then answer this question, let us consider in more detail the internal structure of the class and how it is related to the semantic consistency of its subclasses. According to the definition of the homogeneous class of objects, the class consists of a collection of properties methods called a specification, and a collection of called a signature. Analyzing definitions of properties and methods of the class , we can find some internal dependencies among them. It is a common practice for many object-oriented programming languages as well as knowledge representation mod els to define some properties and methods of a class using for this purpose other properties and (or) methods of the class. Such practice allows us to avoid code duplication and provides instead of it code reusability. However, it creates internal dependencies, which help to describe the modeled instance more precisely to the corresponding entity from a particular domain. In addition, such dependencies are important for the decomposition of classes because they define appropriate constraints for the properties and methods of a class. Furthermore, since not all formally possible subclasses of a class are semantically consistent, i.e., only some of them do not conflict with constraints imposed by the dependencies, the decomposition of a class as the construction of all its subclasses is based on such dependencies.
Let us consider examples of semantically consistent and inconsistent subclasses of the class , to understand the problem more specifically. One of the semantically consistent subclasses of the class is the subclass because the property is defined independently from other properties and methods, and it is required for the execution of methods and , which are determined based on this property. In other words, subclass defines a point on a plane with the ability to get and set its coordinates. One of the semantically inconsistent subclass of the class is a subclass because as in the previous case, the property
is defined independently from other properties and methods, and it is required for the invocation of the method
, however, the correct invocation of the method demands one more property similar to . In other words, subclass defines a point on a plane with the ability to get its coordinates, but the invocation of the method , which computes the distance between two points on a plane, will cause an error because the subclass determines only one point on a plane. Therefore, it is inconsistent one. Using this fact, we can conclude that the constructed concept lattice of the formal context contains semantically consistent concepts, as well as inconsistent ones. This fact is important for knowledge retrieval since it is avoiding the consideration of semantically inconsistent subclasses and reduce the search space.
To formalize the internal dependencies of a class, concepts of structural and functional atoms, as well as structural and functional molecules of the homogeneous class of objects, were introduced in [28]. Since properties and methods of a class can be defined independently of other properties and (or) methods of the class, as well as using them, they are similar to chemical atoms and molecules. Indeed, independent properties and methods are similar to atoms, which are the smallest indivisible particles, while dependent ones are similar to molecules, which are groups of atoms or smaller molecules somehow connected with each other. As the properties of a class define its structure, while the methods define its behavior, the corresponding atoms and molecules of the class can be classified as structural and functional ones. Let us consider the definitions of both kinds of atoms and molecules of a class, as well as some of their examples, using the class .
Definition 8. Structural atom of a homogeneous class of objects is a singleton collection , where
is a property defined without using any other properties and (or) methods of the class
is its specification.
To analyze the specification of the class
, we can observe, that quantitative properties , and
, which mean the vertices of a triangle, are defined without usage of any other prop erty or method of the class
. Therefore, these three properties define structural atoms , and
, respectively, i.e.
Definition 9. Functional atom of a homogeneous class of objects is singleton collection , where
is a method defined without using any other properties and (or) methods of the class
does not contain any methods defined independently from other properties Definition 10. A functional molecule of a homogeneous class of objects is a collection where on the other methods and (or) properties (or) functional atoms, and are parts of smaller molecules of the class , and is a specification of the class of objects is a method defined based which form structural and , , , , Definition 11. A structural molecule of a homogeneous class of objects is a collection on the other properties and (or) methods is a property defined based , which form structural
Thus, they define functional molecules , and , i.e.
, which calculates the perimeter of a triangle, uses methods and to compute the length of each figure’s side. As the result, it defines a complex structural molecule , which includes the elements of smaller molecules and complex structural molecule and and (or) functional atoms, and are parts of smaller molecules of the class , and is a specification of the class of objects has qualitative property
, which means the satisfiability of the triangle inequality, and uses methods and to compute the length of each figure’s side. Hence, it determines a
, which includes the elements of smaller molecules Since all molecules contain a property or method which is dependent on all other properties and (or) methods of the molecule, we can define a concept of dependency root, which describes such elements. Definition 12. The dependency root of the molecule of a homogeneous class of objects (or) methods of the class is a property or method which is defined based on other properties and
, which are atoms or parts of smaller molecules.
All detected internal dependencies within the class describe some semantic connections among the different properties and methods of the class, which express the internal nature of the modeled en tity from a particular domain if such a model is correct.
Definition 13. Internal semantic dependencies of a homogeneous class of objects type of objects , is a set of structural and functional atoms and molecules of the class , which defines , i.e. where while spectively.
, , and and , , are structural and functional atoms of the class
, are its structural and functional molecules re
can be represented in the following way: define its internal semantic dependencies, which Let us construct the concept lattice of all internal semantic dependencies of the class pose, let us define the formal context . For this purusing the corresponding cross table. Since, each of the functional molecules has three different contexts within the class , we let us split them onto separate conditions. We colored cells of Table 2, which means dependency roots of molecules of the class , using the gray color. Now let us construct the concept lattice for the formal context , using Table 2. Analyzing the results, depicted in Figure 2, we can see that constructed concept lattice contains nodes, which means formal concepts, however not all of them are semantically consistent ones. We used the green border to highlight the consistent concepts, which do not contradict any internal semantic de pendency of the class . Indeed, if we consider, for example, the concept , which defined as follows we can see that the intent
of the concept is semantically inconsistent because it contradicts the internal semantic dependencies defined by functional molecules , and . In other words, the concept defines a point on a plane, however, it has a method
, which computes the distance between two points on a plane, but the concept de fines only one point, that means if we invoke this method, it will raise an error.
Summarizing all noted above, we can conclude that classical methods of formal concept analysis have some gaps related to the semantic consistency of formal concepts, which are constructed within a formal context of decomposition of homogeneous classes of objects. Since, the definition of a for mal context does not consider the internal semantic dependencies of a class, defined by its atoms and molecules, the knowledge retrieval or reasoning within a corresponding concept lattice, constructed using such formal context, becomes inconsistent too because its result can contain inconsistent con cepts. 4. Decomposition of Classes and Objects
is a set of domains, and ables from the set are defined on domains from the set , i.e. main defines a range of values for the respective variable, i.e. constraint from the set is defined as a pair
Since a homogeneous class of objects consist of structural and functional molecules, which define
the restrictions over the class specification and signature, the decomposition of the class can be con
sidered as the constraint satisfaction problem (CSP) [28]. According to [
where is a relation deis a scope of the constraint and fined over the
, and only if is a solution of the CSP.
, and is the arity of the constraint . The tuple satisfies the constraint . If the tuple on the variables satisfies
if , then it
of a homogeneous class of objects can satisfy or not satisfy a constraint defined by a molecule
. Therefore, in contrast to the classical definition of the CSP, the constraint defined by the molecule is applicable only to some subclasses of the class . For example, the constraint defined by functional molecule is not applicable to any subclass of the class , which have a cardinality lower than the molecule itself. In such cases, we can conclude that the subclass does not contradict the constraint defined by the molecule, since the constraint is not applicable to it. To summarize these facts, let us introduce the following definition. Definition 14. A subclass of a homogeneous class of objects does not contradict molecular internal semantic dependency ing conditions is true: where it contains all elements of the molecule, i.e. , it does not contain any element of the molecule, i.e. it does not contain the dependency root of the molecule, but it contains some of its other ele ments, i.e.
, and ; ;
; , if and only if one of the followis a property or method defined based on the other properties and (or) methods of the class , and and , are specifications and signatures of the class and
respectively.
Using this notion, we can define the decomposition of the homogeneous classes of objects. Definition 15. A decomposition of a homogeneous class of objects , is a set of semantically consistent subclasses , which defines a type of objects , where subclasses do not contradict any molecular internal semantic dependency of the class
Now, let us compute the full decomposition of the homogeneous class of objects , using the corresponding algorithm, which was proposed in [28], and the set of internal semantic dependencies , which defines a collection of decomposition constraints. As the result of decomposition we obtained the collection of 49 semantically consistent subclasses of the class , where three subclasses of the cardinality of 1, i.e. nine subclasses of the cardinality of 2, i.e. thirteen subclasses of the cardinality of 3, i.e. twelve subclasses of the cardinality of 4, i.e. six subclasses of the cardinality of 5, i.e. three subclasses of the cardinality of 6, i.e. and three subclasses of the cardinality of 7, i.e.
Now let us construct the concept lattice for all semantically consistent subclasses of the class . For this purpose, let us consider the formal context using the structure of semantically consistent subclasses of the class noted above. As we can see, the concept lattice for the formal context
, depicted in Figure 3, contains 70 formal concepts, while the amount of all semantically consistent subclasses constructed by the decomposition algorithm is equal to 49. It means that some formal concepts in the lattice are semantically consistent, while other ones are inconsistent. For example, the formal concept 44 is semantically inconsistent because its intent contradicts internal semantic dependencies , , and , similarly to the case of concept 15 in formal context
. It happens because the algorithms for constructing of concept lattices compute the part of extents as the intersection of those extents which can be extracted from the formal context cross table [21]. They do not consider internal semantic dependencies within the classes and objects, consequently, they escape a question about the existence of such concepts within a modeled domain, rather compute only intersection among objects or classes to obtain sets of common attributes as new concepts.
We think that it is an important restriction for the usage of formal concept analysis, in particular, for knowledge retrieval and reasoning, since there is an ability to retrieve or infer concepts, which are in consistent, and therefore unreal within a modeled domain.
Let us compare the amount of semantically consistent subclasses of the class with the amount of all possible subclasses, splitting them according to antichains of join-semilattice created by all sub classes. Analyzing Table 1, we can see that among all 254 formally possible nonempty proper subclasses of the homogeneous class of objects , only 49, i.e. 19%, are semantically consistent ones, i.e. they do not contradict any of the internal semantic dependencies of the class. This coefficient allows us to estimate how the search space can be reduced by avoiding the consideration of all semantically incon sistent subclasses of the class . Therefore, let us introduce the corresponding definition for it. Definition 16. Decomposition consistency of a homogeneous class of objects computed in the following way is a coefficient where is a set of all semantically consistent subclasses of the class power set of its all possible subclasses. Since , it means that we can reduce the knowledge search space for the class approximately by times, i.e. .
All data given in Table 1 can be represented graphically, that provides an opportunity to estimate the search space for the knowledge extraction from another perspective. Figure 4 illustrates elements of the power set lattice, where each element is a subclass of the homogeneous class of objects .
Circles depicted by lime color mean semantically consistent subclasses, while yellow circles with numbers mean a particular antichain of the lattice, or in other words, a set of subclasses of the corre sponding cardinality. We also can see, that each element of this lattice, which has a cardinality bigger than 2, and lower than the class itself, can be also decomposed into subclasses, where some of them are semantically consistent, while others are not so. We also depicted in Figure 4 towers of subclass lattice for particular semantically consistent subclasses of cardinality from 2 to 7, which illustrates that the subclass lattice tower of the class contains towers of subclass lattices. The graphical representation of the complete lattice, illustrated in Figure 4, is not a typical or common way to the de piction of lattices, such as the Hasse diagram, for example. However, as you can see the power set lat tice of the class contains 256 elements and, as was noted in [32], connections, which makes the corresponding Hasse diagram complicated. Instead of this, for the quantitative analysis of semantically consistent subclasses of a particular homogeneous class of objects, we can depict only elements of the lattice’s antichains. Since the geometrical form of such representation re minds a tower, we called it a tower of the power set lattice or a tower of subclass lattice.
However, not only classes of objects can be decomposed to extract new knowledge. Since the main purpose of the definition of classes is creating objects, which also can be decomposed based on semantically consistent subclasses constructed by Algorithm 1. Therefore, let us define the notion of object decomposition.
Definition 17. A decomposition of an object of a homogeneous class of objects , which defines a type of objects , is a set of objects semantically consistent subclass properties of objects. , where the object
, and and are Considering the fact, that objects can exist during the program run-time and can be stored in the data base or knowledge base, their structure in each of these states can be different. Based on this idea and using the notion of object decomposition, we developed Algorithm 1 and Algorithm 2 for the decomposition of objects oriented on their run-time representation, and their storage in a database, respec tively.
Algorithm 1. Run-time decomposition of objects.
, Analyzing Algorithm 1, we can see that it generates the set of objects for the subclass constructed during the decomposition of the homogeneous class of objects based on the set of its objects . The algorithm creates a particular object for the subclass initializes each its property by corresponding value, which is got from the corresponding object of the class .
Algorithm 2. Database-oriented decomposition of objects.
then and do then 2: for
do 7: return , if if for all 8: 9: 10: return
Algorithm 2 also generates the set of objects decomposition of the homogeneous class of objects based on the set of its objects . However, in contrast to Algorithm 1, it generates an extended representation of objects by storing the results of the invocation of methods, which are available for them in the class . Since methods of the class can return different values as the result, their correct storage in the database can require additional processing, depending on the type of returned result.
Now let us consider some examples of objects’ decomposition, using Algorithm 2. Let us define and decompose a number of objects of the class , which represent particular triangles on a plane. For this purpose, let us define the collection of points on a plane via creating objects of the class (see Table 4).
Now let us determine triangles on a plane, creating objects of the class and using the above-defined points as vertices of figures (see Table 5). Since objects are containers, which encapsulate property values of particular instances of a class, all objects of the class are defined by the following four properties: , , , and , where . Such structure for objects of the class is commonly-used for their representation in the program run-time. For the storage in a database, we can use results computed by methods and , where the first one computes the length of the triangle’s sides while the second one computes the perimeter of the figure. Consequently, we can consider at least two scenarios of objects’ lifetime and their usage, therefore Table 5 contains both representations. 10 0 5 9 3 0 2 5.0 6.71 10.3 5.39 1 1 As the result of the full decomposition of the class , Algorithm 1 constructed 49 semantically consistent subclasses. It means that if we need to perform a decomposition of all objects of the class , we should do it for each constructed subclass. Due to the big number of subclasses, let us consider the decomposition of all objects of the class , but only for some of its subclasses, e.g. for , , , and . According to the definition of the class , its subclass has the following representation To decompose objects of the class , represented in the Table 5, for its subclass to set for the Algorithm 2 the following configuration set of all objects of the class
. As the result, the algorithm constructed objects of the subclass (see Table 6). Each of them defines a point on a plane with the ability to get its coordinates as objects of the class
has the following representation To decompose objects of the class , represented in the Table 5, for its subclass to set for the Algorithm 2 the following configuration the algorithm constructed objects of the subclass (see Table 7). Each of them defines three points on a plane, where each point is an object of the class
To decompose objects of the class , represented in the Table 5, for its subclass we need to set for the Algorithm 2 the following configuration . As the result, the algorithm constructed objects of the subclass (see Table 8). Each of them defines two points on a plane with the ability to get their coordinates as objects of the class , as well as to compute the distance between them. has the following representation 5.0 6.71 10.3 5.39 5.0 10.2 6.08 1.41 to set for the Algorithm 2 the following configuration the algorithm constructed objects of the subclass (see Table 9). Each of them defines three points on a plane with the ability to get their coordinates as objects of the class pute the distance between any two of them. , as well as to comAs we can see, the decomposition of objects of the class is based on the decomposition of the class itself. It guarantees that all generated objects of any semantically consistent subclass of the class will be also semantically consistent ones. Object decomposition allows us to generate instances for the subclasses created during the class decomposition, and to perform knowledge extraction on another representation level.
One of the approaches to knowledge retrieval was proposed in [24], according to which a formal context can be matched by its formal sub-context constructed using three main kinds of incidence relations that allows the cauterization of the formal context. However, such an approach requires constructing additional concept lattices, to perform their matching with the main concept lattice creating clusters, that can affect the performance of knowledge extraction. Therefore, let us consider another approach.
As we can see, the algorithm for decomposition of homogeneous classes of objects, proposed in [28], can be used for knowledge extraction of semantically consistent subclasses of a class. However, it also can be adapted for knowledge retrieval, by adding additional filtration parameters, which will provide new functional opportunities for conceptual knowledge retrieval and speed up the retrieval process itself. For this purpose, let us add the parameter which means the list of subclass cardinalities and allows the algorithm to construct only those seman tically consistent subclasses of a class , whose cardinality is matched with one of the list . It allows us to further reduce the search space for the algorithm if we know the exact cardinality of the se mantically consistent subclasses of the class , that we want to retrieve. In addition, we can add parameter which means the attribute query and allows the algorithm to construct only those semantically consis tent subclasses of the class , whose contain and do not contain properties and (or) methods from the include and exclude list respectively. It also helps the algorithm to reduce the number of constructed subclasses, if we know useful information about them, i.e. which properties and (or) methods they should and should not contain. Finally, we can add parameter which means the dependency query and allows the algorithm to construct only those semantically consistent subclasses of the class , whose contain and do not contain properties and (or) methods that are parts of internal semantic dependencies, from include and exclude lists respectively. Similar to the attributes, it also helps the algorithm to reduce the number of constructed subclasses, if we know other useful information about them, i.e. elements of which structural and (or) functional molecules they should and should not contain. Parameters and are filters, which allow us to retrieve semantically consistent subclasses of the class according to particular structural and behavior features. Using all these filtration parameters, we can improve the algorithm for the decomposition of homogeneous classes of objects in the following way.
Algorithm 3. Decomposition of homogeneous classes of objects.
then and then , , ,
, for if
do for
if 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: return then
do then satisfy for all if not satisfy break; if satisfy then true;
do if
false;
As we can see, Algorithm 3 performs the decomposition of the homogeneous class of objects , resolving the corresponding constraint satisfaction problem (CSP), using the set of its internal semantic dependencies , as well as the list of subclass cardinalities , attribute query , and dependency query . Using the list of subclass cardinalities , the algorithm resolves the CSP only for those subclasses, whose cardinality is matched with one of the list . The set of constraints used by the procedure to verify the satisfiability of the constraint is for the subclass , if the constraint is applicable to the subclass. In other words, the procedure resolves the CSP for particular subclass of the class and if the CSP is satisfiable, then the subclass is semantically consistent. It allows the algorithm constructs only semantically consistent subclasses of the class . For each such subclass of the class , the algorithm performs the additional filtration according to attribute query and dependency query , using for this purpose the procedure . As the result, the algorithm constructs all semantically consistent subclasses of the homogeneous class of objects , which have a certain cardinality and satisfy the attribute and dependency restrictions, if such subclasses exist. In general, Algorithm 3 performs two tasks, firstly, it extracts the conceptual knowledge via decomposition of homogeneous classes of objects onto the set of semantically consistent subclasses, and secondly, it retrieves the par ticular subclasses, which satisfy the corresponding restrictions.
{true, false}
Output: satisfy 1: satisfy 2: if 3: 4: for
for 5: if 6: satisfy 7: else 8: satisfy 9: break; 10: if satisfy then 11: return satisfy 12: return satisfy.
{true, false, none} none; then do
do
then
true;
Consequently, there are two different scenarios for the organization of conceptual knowledge
retrieval. In the first case, we can construct all possible semantically consistent subclasses of the class
and then store them in a database, using for this object-relational mapping. Indeed, according to
[
To filter semantically consistent subclasses during the retrieval stage, we propose to use attribute query and dependency query
, which describe the inclusion of desired attributes and dependencies, as well as the exclusion of undesired ones. Let us consider a few examples of dynamic knowledge retrieval using the homogeneous class of objects defined above. Suppose we want to retrieve all semantically consistent subclasses of the class , which have a cardinality from 4 to 6, and contain attributes and , for this purpose we need to set for Algorithm 3 the following configuration: As the result, we received the following subclasses:
, , , , , , , and . Suppose we want to retrieve all semantically consistent subclasses of the class , which have the same cardinality as previously, and do not contain attributes and , for this purpose we need to set for Algorithm 3 the following configuration: As the result, we received the following subclasses: , ,and . Let us join configurations and
, , , , , , , , , As the result we received the following subclasses: , , , , and class . Now let us assume that we need to retrieve all semantically consistent subclasses of the , which have a cardinality from 4 to 6, and contain functional molecules , , for this purpose we need to set for Algorithm 3 the following configuration: In this case, the algorithm returned the following subclasses:
, , , , , trieve all semantically consistent subclasses of the class do not contain functional molecules , rithm 3 the following configuration: In this case, the algorithm returned the following subclasses: . Let us join configurations and . Finally, let us join configurations and
In this case, the algorithm returned the following subclasses:
. Let us consider the interpretation of the obtained results in more detail. As we can see, each of subclass and
defines two points on a plane with the ability to get and set their coordinates, as well as compute the distance between them. According to the definition of the homogeneous class of objects , they have a following representation:
defines a triangle on a plane with the ability to get and set coordinates of its vertices, as well as compute the length of all its sides. According to the definition of the class it has a following representation: Therefore, we can conclude that decomposition of the homogeneous class of objects using Algorithm 3 generates semantically consistent subclasses, which represent the implicit or hidden knowl edge within the domain of the class . In addition, the algorithm performs the filtration of all constructed semantically consistent subclasses according to attribute query .
For some cases, Algorithm 3 can be improved by changing the filtration strategy, since a resolving of the decompositional SCP is also a kind of subclass filtration, depending on an attribute query, as well as a dependency query, the order of verification of their satisfiability can be changed. The main criterion for such modification of the algorithm is the estimation of search space reducing chain performed by a particular sequence of subclass filtration.
In this paper, we considered in detail the internal semantic dependencies of homogeneous classes of objects (structural and functional atoms and molecules) and how they affect the decomposition of the class. We defined the decomposition of the class as splitting the class into such subclasses, which do not contradict any internal semantic dependency. Since all possible subclasses of a homogeneous class of objects form a power set lattice, which is a complete lattice, using methods of formal concept analysis we constructed the corresponding concept lattices for all subclasses of the class, for all internal semantic dependencies of the class, and for all its semantically consistent subclasses. As the result, we found that in all three cases, constructed concept lattices contain a certain number of formal con cepts with semantically inconsistent intents because the algorithms for the construction of concept lat tices compute the part of extents via the intersection of extents which can be extracted from the formal context. At the same time, they do not consider the internal semantic dependencies of a class, which define corresponding restrictions to the creation of its semantically consistent subclasses. That re stricts the usage of formal concept analysis for knowledge extraction and retrieval since it allows retrieval, inference, or usage of inconsistent concepts, which are unreal within a modeled domain.
To propose an alternative approach to knowledge extraction and retrieval via decomposition of ho mogeneous classes of objects, we improved the decomposition algorithm, which was proposed in [28], adding the additional filtering parameters, which help to reduce the search space and improve the performance. As the result, in the first stage, the algorithm extracts knowledge by constructing only semantically consistent subclasses of a homogeneous class of objects, which have a certain cardinality, via solving the corresponding constraint satisfaction problem defined based on the internal semantic dependencies of the class. In the second stage, the algorithm retrieves knowledge by filtration of constructed semantically consistent subclasses according to the attribute and dependency queries, which allow selecting only those subclasses, which include all desired attributes and dependencies and do not include undesired ones. We introduced the decomposition consistency coefficient, which allows us to estimate how much the algorithm can reduce the search space for knowledge extraction and retrieval, avoiding the consideration of all semantically inconsistent subclasses of the class. To demonstrate the possible application of the algorithm, we considered seven different scenarios of how the homogeneous class of objects, which define a triangle on a plane, can be decomposed for knowl edge extraction and retrieval. In all cases, the algorithm extracted and retrieved subclasses of the class, which are semantically consistent within a modeled domain and satisfy all restrictions and fil ters.
In addition, we developed two algorithms for the decomposition of objects, which adapt generated objects for their usage in the run-time or storing them in a database. Both algorithms are based on the decomposition of a homogeneous class of objects and guarantee that all objects of any semantically consistent subclass of the class, generated during the decomposition, will be also semantically consis tent ones as their class. The proposed approach provides an opportunity to perform knowledge extrac tion via the decomposition of the homogeneous classes of objects, as well as the decomposition of their objects. To demonstrate the possible application of these algorithms, we provided corresponding examples of decomposition for objects of subclasses of different cardinality. However, despite all mentioned advantages of the developed algorithms, they require future analysis, improvement, and optimization.
This research has been supported by the National Academy of Science of Ukraine (project 0121U111944 Development of Methods and Tools for Construction of Domain-Oriented Intelligent Software Systems Based on Object-Oriented Dynamic Networks). [13] U. Dekel, Applications of Concept Lattices to Code Inspection and Review, in: Proceedings of the Israeli Workshop on Programming Languages and Development Environments. IBM Haifa Research Lab, 2002. [14] U. Dekel, Y. Gil, Revealing Class Structure with Concept Lattices, in: Proceedings of the 10th Working Conference on Reverse Engineering (WCRE’03). Victoria, BC, Canada, 2003, pp. 353-363. doi: 10.1109/WCRE.2003.1287267. [15] S. Dominich, The Modern Algebra of Information Retrieval, Springer, Berlin, Heidelberg, 2008. doi: 10.1007/987-3-540-77659-8. [16] D. Dubois, H. Prade, J.-P. Rossazza, Vagueness, typicality, and uncertainty in class hierar chies, International Journal of Intelligent Systems, 6 (1991) 167-183. doi: 10.1002/ int.4550060205. [17] F. Fkih, M. N. Omri, IRAFCA: an O(n) information retrieval algorithm based on formal concept analysis, Knowledge and Information Systems, 48 (2016) 465-491. doi: 10.1007/S10115015-0876-X. [18] F. Fkih, M. N. Omri, FCA_Retrieval: A Multi-operator Algorithm for Information Retrieval from Binary Concept Lattice, in: Proceedings of the 32nd Pacific Asia Conference on Language, Information and Computation, PACLIC 2018, Hong Kong, 2018, pp. 164-171. [19] E. C. Freuder, A. K. Mackworth, Constraint satisfaction: an emerging paradigm, in: F. Rossi, P. van Beek, and T. Walsh (Eds.), Handbook of Constraint Programming, Elsevier, Amsterdam, 2006. [20] B. Ganter, R. Wille, Formal Concept Analysis: Mathematical Foundations, Springer, Berlin,
Heidelberg, 1999. doi: 10.1007/978-3-642-59830-2. [21] B. Ganter, S. Rudolph, G. Stumme, Explaining Data with Formal Concept Analysis, in: M. Krotzsch, and D. Stepanova (Eds.), Reasoning Web. Explainable Artificial Intelligence, volume 11810 of LNCS, Springer Cham., 2019, pp. 153-195. doi: 10.1007/978-3-030-314231_5. [22] R. Goldblatt, Topoi. The Categorial Analysis of Logic. Revised edition, volume 98 of Studies in Logic and the Foundations of Mathematics, Elsevier Science Publishers B.V., Amsterdam, 1984. [23] P. Joshi, R. J. Joshi, Concept Analysis for Class Cohesion, in: 13th European Conference on Software Maintenance and Reengineering, Kaiserslautern, Germany, 2009, pp. 237-240. doi: 10.1109/CSMR.2009.54. [24] L. Kwuida, R. Missaoui, A. Balamane, J. Vaillancourt, Generalized pattern extraction from concept lattices, Annals of Mathematics and Artificial Intelligence. 72 (2014) 151-168. doi: 10.1007/S10472-014-9411-0. [25] N. Messai, M.-D. Devignes, A. Napoli, M. Smail-Tabbone, Extending Attribute Dependencies for Lattice-Based Querying and Navigation, in P. Eklund, and O. Haemmerle (Eds.), Conceptual Structures: Knowledge Visualization and Reasoning. ICCS 2008, volume 5113 of LNCS, Springer, Berlin, Heidelberg, 2008, pp. 189-202. doi: 10.1007/978-3-540-70569-3_13. [26] D. O. Terletskyi, O. I. Provotar, Object-oriented dynamic networks, in: G. Setlak, and, K. Markov (Eds.), Computational Models for Business and Engineering Domains, volume 30 of International Book Series Information Science and Computing, ITHEA, Rzeszow-Sofia, 2014. [27] D. O. Terletskyi, O. I. Provotar, Mathematical foundations for designing and development of intelligent systems of information analysis, in: Proceedings of 9th International and Practical Conference on Programming, UrkPROG’2014, Kyiv, Ukraine, 2014, pp. 233-241. [28] D. O. Terletskyi, Run-Time Class Generation: Algorithm for Decomposition of Homogeneous Classes. in: A. Lopata, R. Butkiene, D. Gudoniene, and V. Sukacke (Eds.), Information and Software Technologies. ICIST 2020, volume 1238 of CCIS, Springer Cham., Switzerland AZ, 2020, pp. 234-254. doi: 10.1007/978-3-030-59506-7_20. [29] M. Tiwari, P. Joshi, Method Cohesion Analysis through Concept Lattices, ACM SIGSOFT
Software Engineering Notes, 37 (2012) 1-4. doi: 10.1145/180921.2180924. [30] P. Tonella, Using a Concept Lattice of Decomposition Slices for Program Understanding and Impact Analysis, IEEE Transactions on Software Engineering. 29 (2003) 495-509. doi: 10.1109/TSE.2003.1205178. [31] R. Wille, Methods of Conceptual Knowledge Processing, in: R. Missaoui, J. Schmid (Eds.), Formal Concept Analysis. ICFCA 2006, volume 3874 of LNCS, Springer, Berlin, Heidelberg, 2006, pp. 1-29. doi: 10.1007/11671404_1. [32] H. Yao, H. J. Hamilton, Mining functional dependencies from data, Data Mining and Knowl edge Discovery, 16 (2008) 197-219. doi: 10.1007/S10618-007-0083-9.