Relational Concept Analysis (RCA) extends standard Formal Concept Analysis (FCA) by taking relations between objects into account. The scalability of RCA learning on top of huge amounts of sensor data is a challenge for applications such as smart home system monitoring in ambient assisted living environments. One possible approach to improve scalability is to exploit the capabilities of modern parallel computing architectures such as multi-core CPUs. In this paper, we propose PRCA (Parallel Relational Concept Analysis), a novel framework for parallel relational concept learning. 1 In the next few years, the world population will be ageing dramatically: the percentage of people over 65 will grow to more than 25% and average life expectancy will increase to 75. This will have a particular impact on the health care systems since there will not be enough health care workers to adequately attend to all elderly people. Especially elderly people who su er from cognitive impairment are known to remain independent for longer when living in their own home. Despite their cognitive shortfalls these people are still able to perform everyday activities like washing, grooming and eating. These activities are called Activities of Daily Living (ADLs) and it has been demonstrated that they will be retained for a longer period if the elderly people remain in their familiar environment. [1] The application scenario of the research described in this paper is in the eld of smart home systems that support elderly cognitive impaired people to stay independently in their own houses as long as possible with just minimal support from health care services. A smart home system monitors inhabitants with unobtrusive sensors, identi es particular behaviors and noti es health workers if an abnormal behavior, such as taking medication in the middle of the night, occurs. Abnormal behaviour detection is a core feature of smart home systems.
Concepts of normal behaviour are learned from positive and negative training data. New behaviours are classi ed using the concepts of normal behaviours.
Formal concept analysis (FCA) is a simple yet powerful and elegant
representational concept learning mechanism introduced in [
Relational Concept Analysis (RCA) was rst proposed in [
Given the amount of data that has to be processed by modern applications,
the scalability of learning is of particular concern. One approach to tackle this
problem is to take advantage of parallel computing platforms (multicore CPUs,
GPUs, cloud computing), and to parallelise learning algorithms. In this paper,
we present PRCA (Parallel Relational Concept Analysis), a novel framework for
parallel concept learning. PRCA is based on RCA [
Our research is mainly based on the mathematical foundations of FCA as
described in [
Huchard et al. have proposed Relational Concept Analysis (RCA) [
The main approach of the Parallel Relational Concept Analysis (PRCA) framework is the parallelization of the scaling step of object-object relations to relational properties and the integration of basic and relational properties into one concept lattice. The aim is to learn positive and negative hypotheses. PRCA does not generate a complete lattice with all relational properties, but only nds suitable relational properties that are good for dividing the positive from the negative examples. Therefore, the PRCA framework iteratively generates new relational properties from the relational information given in the data set and combines them with the basic properties in one lattice until su cient hypotheses are found. 3.1
Figure 1 depicts the basic steps of the PRCA framework. The input of the framework are relational contexts. We de ne a relational context C as a pair (K; R) consisting of a set of formal contexts K = fKig, whereby each context Ki = (Oi; Pi; Ii) has objects Oi, properties Pi and a relationship Ii between these objects and properties; and object-object relations R = fRig, with Ri O1i O2i, associating objects from two contexts.
Each basic relation Rj has a source (relational) context Ci and a target (relational) context Ck, both source and target can be identical. The main (relational) context is a learning problem with multiple contexts. One context is the main context. This is the context that contains the positive, negative (and unknown) labelled objects of the learning problem.
The learning algorithm consists of several steps.
In the Generation of Relations step, relations are generated based on the basic relations and properties of the relational contexts. The generator yields basic relations as well as new composite relations. A composite relation is the result of composing two relations or one relation and an additional post condition. Di erent generation operators like joins, intersections and conditional joins exist. For instance, the relation join is de ned as Rj:k := Rj :Rk. Applying a postcondition creates a new relation by applying lters based on properties in the target context.
In the following Relational Scaling step, these relations are then scaled to relational properties. Di erent Scaling operators exist: existential, universal and cardinality restricted. There are also di erent scaling directions: left and right direction (has/is).
In the Integration into Lattice step, the relational properties are integrated with the basic properties into one lattice to check for new positive hypotheses, i.e. intentions of concepts that contain only positive examples)=, All new formal concept intentions being hypotheses are selected and stored.
In the Learning step, it is checked if all positive and negative examples are covered by at least one positive, or negative hypothesis, respectively. If all positive examples of the main context are covered by at least one hypothesis, the best hypotheses are selected and returned as result of the learning process. 3.2
Figure 2 shows the realization of the basic steps of the PRCA framework. Input data are one or more relational contexts. In addition to formal contexts and the set of basic relations, each relational context contains a set for storing relational properties that are scaled during relational scaling step. Uncovered positive examples is an agenda containing all positive examples. When a new positive hypothesis is found , the examples covered by this hypothesis will be removed from the agenda. Hypotheses is a container shared by all parallel running workers to collect the learned hypotheses. The global property pool contains all basic properties and relational properties which are relevant for building the lattice. The parallel running workers scale new relational properties and add them to the global property pool. The relation generator generates new relations using the operations described above.
The steps Relational Scaling and Integration into Lattice are realized by parallel running worker threads. In each working step, the worker requests a new relation from the relation generator, scales new relational properties and integrates them into one lattice with the basic properties and previously scaled properties.
Step by step the lattice is extended by new formal concepts. When a new formal concept covers only positive examples the worker updates the agenda of uncovered positive examples and stores the intention of the concept as new hypothesis in its local hypotheses pool. The worker adds the new relational properties to the global property pool and to the relational property pool of the respective relational context.
The Learning step is done by the learner. The learning is nished when all examples have been removed from the agenda, i.e., all examples are covered. Then, each worker adds its found hypotheses to the global hypotheses pool. Then, the learner selects the best hypotheses to create the result of the learning process. A set cover algorithm is used for this purpose. By default, we use a simple greedy algorithm that selects hypotheses covering the most (not yet covered) examples. The use of other algorithms is possible as well. 3.3
The purpose of the framework is to provide a tool for developing and evaluating di erent strategies of RCA learning. The framework o ers several variability points and con guration options that can be combined. In particular, this includes operators to compose relations, lters and set coverage algorithms to select hypotheses.
Scaling operators de ne the type of the relational scaling. Multiple scaling operators can be de ned at the same time. Each worker applies all the de ned scaling operators to the given relation.
Property lter : The workers add their newly scaled relational properties to the global property pool. However, not all relational properties are relevant. To reduce the number of irrelevant properties, the con gured property lter controls which properties are added to the global property pool.
A relation lter lters the generated relations. When the relation generator is requested for a next relation it will only return relations that pass the lter. 4 4.1
The evaluation is conducted with a ten 10 fold cross validation. The evaluation metrics are:
Learning Time: duration from context to selected hypotheses.
The hypotheses learned by the prototypes are used to classify unknown examples. To determine the quality of the learned hypotheses their correctness, completeness and accuracy are measured. Therefore a set of positive and negative labelled examples is used. Each example of the data set is classi ed by the learned hypotheses. The results of the classi cation are compared to the original labels of the examples. Correctness determines the ability of the learned hypotheses to classify negative examples as negative. Completeness determines the ability of the learned hypotheses to classify positive examples as positive. Accuracy combines correctness and completeness. It determines the ability of the learned hypotheses to classify undetermined examples correctly. correctness = jnegative examples classified as negativej
jall negative examplesj completeness = jpositive examples classified as positivej
jall positive examplesj accuracy = jnegative examples classified as negativej + jpositive examples classified as positivej jall examplesj
De nition length: A further quality property of the learned hypotheses is their length. A shorter hypothesis is regarded as better than a longer one describing the same objects.
{ property length: To compute the length of a property the containing relations, properties and scaling operators are counted, e.g., female = 1 exists has sibling (exists has child (female)) = 5 { hypotheses length: The hypothesis is the conjunction of all its properties. The hypothesis length is in uenced by the number of properties per hypothesis and the length of the properties. It is the sum of the length of all its properties plus n-1 \ANDs" between n properties. For example, the hypothesis ffemale, oldg consists of two hypotheses with length one. Its hypothesis length is three (female AND old). { de nition length:The de nition length is the sum of the length of all its hypotheses plus the n-1 ORs between n hypotheses. For example, in the learning problem Uncle of the Family data set the learned de nition consists of two hypotheses: fmale, exists has sibling.childg OR fmale, exists has married.sibling.childg.
It has a de nition length of twelve (4 + 1 (AND) + 1 (OR) + 5 + 1 (AND)) 4.2
Data sets used for evaluation are the family data set: machine learning data set from DL learner repository 4 and the straight data set: a (randomly) generated data set.
Data Sets Uncle (Family) 202 Cousin (Family) 202 Aunt (Family) 202 Grandson (Family) 202 Grand mother 202 (Family) Straight200 Straight800
Exam- Posit- Negat-Relatio- Basic Proper- Relations ples ive ive nal ties
Contexts 38 38 1 2 4 71 71 1 2 4 41 41 1 2 4 30 30 1 2 4 17 16 1 2 4 4 http://sourceforge.net/p/dl-learner/code/HEAD/tree/trunk/examples/ family/
{ The additional generator operators lead to the generation of more irrelevant relations, that need to be scaled and integrated into the lattice. Furthermore, the additional scaling operators and the less restrictive property lter lead to more properties that need to be integrated into the lattice as well. Hence bigger lattices are generated. The generation and scaling of more irrelevant relations and the generation of lattices with more concepts increases the learning time when PRCA is run with a more expressive con guration. { PRCA achieves high testing accuracy on all learning problems, but not 100% because the data sets are small and the learned de nitions are over tted to the training data set. { A general problem of FCA (for our purpose) is that it generates most speci c descriptions instead of most general ones. According to the de nition offormal concept a concept consists of all properties common to all objects in the concept extension (because FCA is based on closure operator). (this happens on small data sets, but may happen on noisy data sets as well) { PRCA with minimal con guration outperforms DL Learner regarding learning time while achieving the same testing accuracy values. { de nition length: the de nitions of the DL Learner tend to be a bit longer than those of PRCA because DL Learner combines partial de nitions and counter partial de nitions, e.g., one partial de nition for the uncle learning problem is not female and exists sibling.exists child.top. { DL Learner and PRCA nd the same number of partial de nitions/hypotheses (hypotheses in PRCA correspond to partial de nitions in DL Learner). Straight data set: { The DL-Learner has troubles with learning these problems. On Straight200 its testing accuracy is only 73.9% which is useless for practical application and on Straight800 it runs out of memory. The de nition length value and analysis of the result les reveal that ParCEL-Ex learns speci c partial definitions whereas PRCA learns one generic hypothesis and achieves high accuracy (99-100%) in all test runs. { The con gurations for the straight data sets are trade-o s between learning time. { With PRCA III the hypothesis with minimal length is learned and 100% testing accuracy is gained, e.g., exists has [[card+[card+[card.nextRank+card].nextRank].nextRank].nextRank+card] { However, learning times are large on both data sets: more than 2 seconds on
Straight200 and more than 9 seconds on Straight800. { With the weaker 80% uncovered positives lter learning time is reduced on both data sets: the learning duration of the Staight200 learning problem becomes two times faster and the learning duration of Straight800 becomes 3.6 times faster. The trade-o s are that the testing accuracy gets less (but is still more than 99%) and the de nition length becomes 2.6 times longer on Straight200 and 3.4 times longer on Straight800. { The de nition length values and result le analysis reveal that when the lter gets weaker the hypotheses consist of more properties. These properties are shorter than in the PRCA III hypothesis, but describe the straight only partially. For instance, the hypothesis describes a sequence of four cards of sequential rank and three cards with two of sequential rank and a third of the \next-next-next" rank. This leads to worse testing accuracy. The reason is the small training data set: the hypothesis covers all positive examples and not any negative example.
In summary, { the benchmark shows that PRCA outperforms DL Learner on the used data sets (when run with appropriate con guration). It is faster with always higher accuracy. { the experiments revealed the general problem of FCA. It generates most speci c descriptions instead of most general ones. We tried to reduce the irrelevant properties by property lters. However, hypotheses still contain irrelevant properties. Further work may investigate property reduction during the nal hypotheses selection in the learner. { PRCA nd short de nitions because DL Learner (ParCEL-Ex) combines counter partial de nitions. { for generalizing the results evaluations on bigger data sets (more examples, more relations, more properties, more complex de nition, noisy data) need to be conducted { the slowing down on more expressive con gurations and on learning problems with long hypotheses indicates that the relation generator needs to be improved, e.g., by atm breadth rst search ! heuristic based search, relation lter mechanism for ltering duplicate relations { for improving lattice creation (the more properties are in the pool the bigger the lattice the more time is needed to create the lattice) we apply distributed lattice creation. 5
Our application scenario is in learning positive concepts of normality for detecting abnormal (i.e. negative) behaviours in the context of smart monitoring environments in ambient assisted living. Our event data sets don't only contain object-property relations but also more complex information relating objects to other objects which have properties. We therefore extended standard FCAbased learning on the basis of RCA for parallel learning on top of data with object-object relations. Due to the amount of data, high scalability of the learning method is relevant and the proposed parallel learner addresses this problem. The proposed approach is con gurable and extensible which allows us to further study and evaluate relational concept analysis in di erent parallel con gurations. We conducted experiments that have shown that we can handle data sets with one or multiple relational contexts and that PRCA outperforms DL Learner on the used data sets: PRCA nds a solution on straight data sets, where DL Learner doesn't nd a correct solution. On data sets where both nd solutions PRCA learns the de nitions faster and achieves similar results for testing accuracy.