Christos Dimitrakopoulos

Andreas Dimitris Vlantis
email: vlantis@ceid.upatras.gr

Konstantinos Theofilatos

Spiros Likothanassis

Seferina Mavroudi
email: mavroudi@ceid.upatras.gr

A New Framework For Bridging The Gap From Protein-Protein Interactions To Biological Process Interactions

Keywords: Protein-Protein Interactions, protein-protein interaction networks, Biological Process Interactions, EvoKalma Model, protein function, statistical enrichment

Proteins and their interactions have been proven to play a central role in many cellular processes and have been extensively studied so far. However of great importance, little work has been conducted for the identification of biological process interactions in the higher cellular level which could provide knowledge about the high level cellular functionalities and maybe enable researchers to explain mechanisms that lead to diseases. Existing computational approaches for predicting Biological Process interactions used PPI graphs of low quality and coverage but failed to utilize weighted PPI graphs to quantify the quality of the interactions. In the present paper, we propose a unified twostep framework to reach the goal of predicting biological process interactions. After conducting a comparative study we selected as a first step the EVOKALMA model as a very promising algorithm for robust PPI prediction and scoring. Then, in order to be able to handle weights, we combined it with a novel variation of an existing algorithm for predicting biological processes interactions. The overall methodology was applied for predicting biological processes interactions for Saccharomyces Cerevisiae and Homo Sapiens organisms, uncovering thousands of interactions for both organisms. Most of the linked processes come in agreement with the existing knowledge but many of them should be further studied.

Introduction

Among the numerous participants in molecular interactions, proteins are considered most important ones. In specific, proteins transmit regulatory signals throughout the cell, catalyze a huge number of chemical reactions, and are critical for the stability of numerous cellular structures. The total number of possible interactions within the cell is extremely large and the full identification of all true PPIs is a very challenging task. However, the identification of all true PPIs may contribute in understanding cellular functionality, designing more efficient medicines and uncovering the mechanisms that lead to diseases. For these reasons, this problem has been extensively studied in the last decades and many experimental and computational techniques have been combined to solve it [START_REF] Theofilatos | Computational Approaches for the Prediction of Protein-Protein Interactions: A Survey[END_REF].

A Biological Process Network is a model designed to offer an insight at the interactions occurring among biological processes. The traditional approach for studying complex biological networks is based on the identification of interactions between genes and proteins. As a result, little is known about interactions of the higher order biological systems, such as biological processes. The knowledge derived by process interactions can be effectively used in protein function prediction, increasing both coverage and accuracy of predictions. Moreover, uncovering the interactions of biological processes can be a step towards understanding the cellular functions in a high level.

Existing methods for predicting interactions between biological processes take as inputs the PPI networks and functional annotations. In [START_REF] Dotan-Cohen | Biological Process LinkageNetworks[END_REF], processes are considered as interacting when more proteins annotated by them interact than expected by chance. Other methods also require gene expression information [START_REF] Lasher | Discovering networks of perturbed biological processes in hepatocyte cultures[END_REF] to examine how interactions may change in different experimental conditions. In addition, this method incorporates weights at the protein interactions. In [START_REF] Lasher | Summarizing cellular responses as biological process networks[END_REF], the aim is to include as few inter-process links that successfully present as many gene interactions, to reduce complexity and allow further exploration in a greater detail. Despite the promising results of these approaches, their basic limitation is the utilization of PPI graphs of low quality and coverage as inputs. Moreover, most of them do not utilize confidence scores -weights for each PPI and others use confidence scores which only refer to the reference rate in the bibliography of a certain interaction.

In the present paper, we propose a computational framework for the prediction of PPIs, the prediction of a confidence score for each interaction which will reflect function, structural and sequential information and the prediction of interactions between biological processes. For the prediction and scoring of PPIs the method EVOKALMA was utilized [START_REF] Theofilatos | The Human Interactome Knowledge Base (HINT-KB): An integrative Human protein interaction database enriched with predicted protein protein interaction scores using a novel hybrid technique (Evolutionary Kalman Mathematical Modelling -EvoKalMaModel)[END_REF]. The selection was only performed after the conduction of extended experiments in order to ensure the superior performance of the EVOKALMA model when compared with existing state of the art classification techniques. The experimental results confirmed that EVOKALMA method outperformed the other methodologies in all the examined metrics. For the prediction of biological process interactions we enhanced the methodology proposed in [START_REF] Dotan-Cohen | Biological Process LinkageNetworks[END_REF] in order to be able to handle weighted PPIs. In this way, the method accounted for the high false positive and false negative rates encountered in PPI datasets ensuring that only high-confidence interactions contribute significantly to the method's output while low-confidence interactions have only a low effect.

The proposed algorithmic framework was applied for Saccharomyces Cerevisiae and Homo Sapiens organisms and useful conclusions were made about the interactions of biological processes in these organisms.

The rest of the paper is organized as follows: In section 2 the datasets and the proposed algorithmic framework are described in detail. In section 3 the experimental results are presented and analyzed while in section 3 conclusions and proposals for future work are presented.

2

Datasets and Methods

Datasets

For the training and testing process of the methods for predicting PPIs 1000 positive interactions referred in HPRD [START_REF] Prasad | Human Protein Reference Database-2009 update[END_REF] and 1000 negative protein interactions were selected. HPRD database is assumed to be highly reliable as it contains protein interactions that are supported by low and high throughput experimental evidence. The negative samples were created randomly from the unique identities of the whole set of proteins leaving out protein pairs which have been reported in iRefindex [START_REF] Razick | iRefIndex: A consolidated protein interaction database with provenance[END_REF] as protein-protein interactions. For every protein pair in the deployed dataset 22 informative features were calculated including several co-expression features, function similarity features, sequence similarity, a homology based feature, domain-domain interaction feature and co-localization features. More details about the utilized features is available at [START_REF] Theofilatos | The Human Interactome Knowledge Base (HINT-KB): An integrative Human protein interaction database enriched with predicted protein protein interaction scores using a novel hybrid technique (Evolutionary Kalman Mathematical Modelling -EvoKalMaModel)[END_REF].

All feature values are normalized in the range [0, 1] and missing are estimated using the kNN-impute methodology [START_REF] Troyanskaya | Missing value estimation methods for DNA microarrays[END_REF]. The trained EVOKALMA model (see section 2.2.1) was applied on an extended set of over 600000 protein pairs to predict most human PPIs and predicted 211367 PPIs. Moreover for every interaction a confidence score has been calculated. This confidence score indicates the strength of the interaction, its frequency and possibility to exist. These interactions alongside their weights (confidence scores) are stored in the HINT-KB.

The input graph datasets for predicting interactions among biological processes were: a) the protein interaction network for Saccharomyces Cerevisiae, obtained from Uniprot Database [START_REF]The UniProt Consortium: Reorganizing the protein space at the Universal Protein Resource (UniProt)[END_REF] (22969 interactions), b) the protein interaction network for Homo Sapiens, created from the interactions reported from iRefIndex database (115404 interactions) and, c) the weighted protein interaction network for H. Sapiens obtained from HINT-KB database (211367 interactions).

The input genetic interaction networks for S. Cerevisiae and H. Sapiens were created from BioGRID 3.2.98 database [START_REF] Stark | BioGRID: a general repository for interaction datasets[END_REF] and comprised 1606 genetic interactions for H. Sapiens and 145265 genetic interactions for S. Cerevisiae.

Methods

The overall methodology is consisted of a two step procedure. First, for each specific organism PPIs are predicted with computational prediction methods or retrieved through public available databases. Then, functional, structural and sequential information about the proteins are combined to predict a confidence score for these interactions. Finally, the constructed weighted PPI graphs are used as input for the biological process network prediction method to predict interactions between biological processes. All these methodologies are described in sections 2.2.1 -2.2.2.

EVOKALMA Model

The main idea of the proposed classification methodology, called (Evolutionary Kalman Mathematical Modelling -EvoKalMaModel) is to find a simple mathematical equation that governs the best classifier and enables the extraction of biological knowledge. This method was based on previous methodologies proposed by our authoring group [START_REF] Theofilatos | A new hybrid method for predicting protein interactions using Genetic Algorithms and Extended Kalman Filters[END_REF][START_REF] Dimitrakopoulos | Efficient Computational Construction of Weighted Protein-Protein Interaction Networks Using Adaptive Filtering Techniques Combined with Natural-Selection Based Heuristic Algorithms[END_REF] and it was initially published in [START_REF] Theofilatos | The Human Interactome Knowledge Base (HINT-KB): An integrative Human protein interaction database enriched with predicted protein protein interaction scores using a novel hybrid technique (Evolutionary Kalman Mathematical Modelling -EvoKalMaModel)[END_REF]. It combines a state-ofthe-art adaptive filtering technique named Kalman Filtering [START_REF] Welch | An Introduction to the Kalman Filter[END_REF] with an adaptive genetic algorithm. The adaptive genetic algorithm is used to detect the optimal subset of terms in order to build the mathematical model for our predictor and then Extended Kalman Filters to compute its optimal parameters. The final model is in the form of a mathematical equation including a subset of the available mathematical terms and inputs. The evolutionary process is guided with a problem specific fitness function and utilizes an adaptive mutation rate to improve its convergence behavior.

Proposed Biological Process Network Method

Protein-protein interaction (PPI) networks are defined as graphs whose nodes represent proteins and the edges interactions between nodes/proteins. The weights of the edges (if they exist) represent the confidence scores of these interactions. Genetic interaction (GI) network is a graph whose nodes represent genes and the edges represent interactions between nodes/genes. The definition of linked biological processes is based on an input undirected graph whose nodes represent proteins and edges represent an interaction. Two types of networks were used: physical level PPI networks and functional level GI networks. Only proteins annotated by at least one function (Gene Ontology function [START_REF] Ashburner | Gene ontology: tool for the unification of biology. The Gene Ontology Consortium[END_REF]) were considered. A link between process i and process j suggests that the proteins annotated by i tend to interact with proteins annotated by j more than expected by chance. The statistical enrichment of process j is calculated based on the set of proteins connected with proteins annotated by i, except those annotated by both i and j.

The formal definition is as follows: Suppose N i be the set of nodes annotated with process i (and possibly with other processes as well) and NB i be the set of nodes not annotated with process i and connected with at least one node annotated with process i then:

(1) Based on the above definitions, a process i is connected with a process j, if j is statistically enriched in NB i set, when where:

∑ (2)
For the aforementioned threshold a very strict value (0.001) was assigned (as proposed in [START_REF] Dotan-Cohen | Biological Process LinkageNetworks[END_REF]) in order to filter false positive results. N is defined as the sum of all proteins annotated with processes i and j, so P is the probability a link to connect a protein annotated with process i and a protein annotated with process j, among all possible links between proteins annotated with i or j.

The methodology so far, is similar to the methodology initially proposed in by [START_REF] Dotan-Cohen | Biological Process LinkageNetworks[END_REF]. The drawback of this approach is the assumption that interactions have a dual nature. However, recent approaches for constructing PPI graphs achieved to predict a confidence score for each interaction. Thus, in our approach for the quantity |NB i | in equation 2, we utilized the sum of the weights (confidence scores) that connects the nodes not annotated with process i and the nodes annotated with processes i. Thus, connections of low confidence score will not be significant for the algorithm's output, while connections of high confidence score would be extremely significant.

To calculate semantic similarity of two biological processes the following formula was used:

( )

( ) (3)
where P(t i ) is the probability of a gene to be annotated with t i , that is the number of genes annotated with t i divided by the total number of genes and t ancestor is the most specific common ancestor of t i and t j in Gene Ontology.

The pseudocode of the method is provided in Table 1:

FOR processes i, j Find proteins annotated by these processes Exclude common proteins Find interactions among the remaining proteins Calculate P(i,j) IFP(i,j)<0.001 create link between i and j REPEAT FOR EVERY i, j Table 1. Pseudocode of BPN methodology 3

Results and discussion

For the problem of predicting and scoring PPIs many methods were applied and comparative results are provided in Table 2. The methodologies used for comparative reasons with the proposed EVOKALMA model, include the Naive Bayesian Classifier which is the algorithm utilized by most PPI databases that include computationally predicted PPIs [START_REF] Scott | Probabilistic prediction and ranking of human proteinprotein interactions[END_REF][START_REF] Zhang | PrePPI: a structure-informed database of protein-protein interactions[END_REF]. Moreover, two methodologies which have already provided encouraging results in predicting PPIs were used (Random Forests [START_REF] Liu | Protein interaction predictions from diverse sources[END_REF] and jGEPModel2.0 [START_REF] Theofilatos | Efficient Computational Prediction and Scoring of Human Protein-Protein Interactions Using a Novel Gene Expression Programming Methodology[END_REF]) alongside with the hybrid combinations of Genetic Algorithms [START_REF] Holland | Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[END_REF], Particle Swarm Optimization [START_REF] Kennedy | Particle swarm optimization[END_REF] and Differential Evolution [START_REF] Storn | Differential evolution -a simple and efficient heuristic for global optimization over continuous spaces[END_REF] with Support Vector Machines (SVM) which have several applications in many fields.

Classifiers' performance is theoretically supposed to be more confident when more testing datasets are pooled. Therefore, our experimental setup was extended from one testing dataset to multiple testing datasets and performed double loop cross validation [START_REF] Veenman | LESS: a model-based classifier for sparse subspaces[END_REF]. During the training 10-fold external and 9-fold internal cross validation were used. In particular, the external folds alter the subset of data used for testing the trained models (10 non-overlapping different subsets) after internal algorithms iterations (either heuristic iterations either parameter optimization steps), whereas the internal folds vary the subset of data used for validating the under training models (9 non-overlapping different subsets) during the algorithms internal iterations. The optimal model of each implementation of the 9 internal folds was finally kept for every algorithm. Then, the average of the metrics in the external fold was calculated for the 10 optimal models for every algorithm and Table 2 2 it is clearly observed that EVOKALMA model outperformed significantly all the other deployed methodologies in all the utilized metrics. This strengthens our belief that EVOKALMA algorithm is the most appropriate solution for predicting and scoring PPIs.

The main concepts of the methodology are Interacting Processes and the method's output, the Biological Processes Network (BPN) which nodes are biological processes terms, as described by Gene Ontology database. This method, combined with experimental or computational data of genetic or protein interactions, led to the discovery of a variety of process interactions. Two types of networks were created: a) networks based on protein interactions and, b) networks based on genetic interactions. Some of the discovered connections are consistent with our biological knowledge, while others require further research. For example, the process "protein ubiquitination" (GO:0016567) was found to be PPI-linked with protein catabolism-related proteins and GI-linked with processes related with cell cycle.

A process a was defined as PPI-linked with a process b if the number of proteins which are annotated with b and interact with those annotated with a is greater than expected by chance. Based on the process interactions the BPNs were created. The network is directed, its nodes represent processes and a directed edge from process a to b dictates interaction from a to b. The network created for S. Cerevisiae contains 5285 edges and the network created for H. Sapiens contains 24758 edges.

Gene Ontology database uses various metrics for the semantic similarity of processes which are calculated by the distance of the processes on the hierarchical tree of Gene Ontology. These metrics provide values mostly between 0 and 1, where 0 means that the only common ancestor of two processes is the term GO:0008150 ("biological process"). Many of the PPI-linked processes share a high semantic similarity. While some others have low semantic similarity, it could be useful to be further studied.

As an example, the method discovered a link between "response to DNA damage stimulus" (GO:0006974) and "chromatin modification" (GO:0016568). Despite the fact that they have semantic similarity 0, chromatin and histone modification are utilized in the DNA damage response pathway [START_REF] Unal | DNA damage response pathway uses histone modification to assemble a double-strand break-specific cohesin domain[END_REF].

Using the genetic interaction datasets, two more networks were created. Two genes are considered as interacting when their mutations show a combined effect which does not appear by either mutation alone. The network created for S. Cerevisiae contains 32967 edges and the network created for H. Sapiens contains 245 edges.

The resulting linked processes for the two organisms show great overlap, which is consistent with the fact that they share a large number of protein and genetic interactions. Unique linked processes also appear, such as the link between "hyperosmotic response" (GO:0006972) and "regulation of MAP kinase activity" (GO:0043405), which exists only in the S. Cerevisiae's network. The use of MAP kinase activity for the regulation of the hyperosmotic shock response, is a known mechanism of S. Cerevisiae. Many of the proteins that genetically interact, also participated in PPI-linked processes. For S. Cerevisiae, the probability two proteins to participate in PPI-linked processes is 11% (only those processes with at least 50 genes participating were considered). If it is considered as known that these proteins interact genetically, the probability reaches 36%. Therefore, PPI-linked processes could be used by genetic interaction prediction algorithms to increase their performance. Also, two proteins are more likely to interact if they both belong to PPI-linked processes.

Conclusions and Future Work

In the present paper, we proposed a new holistic algorithmic framework to construct accurate biological process network. This framework is consisted of a PPI prediction and scoring algorithm which outperforms other existing methodologies and a variation of an existing algorithms for prediction biological process interactions which enables it to handle weighted PPI networks.

Utilizing the proposed methodology, various interactions between biological processes were predicted for both examined organisms, S. Cerevisiae and H. Sapiens. Some were consistent with previous knowledge, while others require further research. The method presented, focuses on the computational detection of links between processes, rather than their confirmation or biological interpretation. A challenge derived by this work is the need to review the structure of biological information, since many of the computed interactions show little semantic similarity based on the current structure of Gene Ontology database.

It was proven that PPI-linked processes could be used to enhance the performance of genetic interaction prediction algorithms. Identifying GI-linked processes cal lead to a new direction in generic interaction research. As a next step, the method could incorporate gene expression information, to study processes interactions at a treatment-control basis, as proposed in [START_REF] Lasher | Discovering networks of perturbed biological processes in hepatocyte cultures[END_REF][START_REF] Lasher | Summarizing cellular responses as biological process networks[END_REF].

Another interesting idea for future work, is to investigate which processes show different behavior in various conditions and how the interactions between them may change. A way to achieve that, is by incorporating gene expression information from different experimental conditions, such as infected and healthy tissue samples. Using microarray experiments, genes whose expression changes greatly (often determined by using simple statistical tests) can be defined as perturbed. A process is considered as perturbed when the genes annotated with this process are perturbed. A link between processes is perturbed when both incident processes are perturbed. A major drawback of this analysis is the report of all possible links between processes, which includes unperturbed links and possibly identical links. To overcome this constraint the utilized process links could be minimized by rewarding the inclusion of links representing many gene interactions.

Table 2 .

 2 Comparative Results of PPI classification methodsFrom Table

	presents


Oksana Kalita

Georgios Pavlidis

Adjusting the Tests According to the Perception of Greek Students Who are Taught Russian Motion Verbs via Distance Learning

Keywords: intelligent tutoring system, trained agents, intelligent test agent, Russian motion verbs, Greek students' preferences

Nowadays, the quantity of digital data is so large that its analysis and evaluation can only be performed through (semi-) automatic methods. In a distance learning context, such problems arise for the teacher who needs to personalize the educational material for specific students. The present study focuses on the personalization of the educational material for Greek students learning the Russian language in a distance learning environment. We discovered that it is important for the Intelligent Tutoring System and more specifically for the Intelligent Agents (IA) to have a set of key-characteristics for a proper representation of the states. By having more features an agent has more accurate results whereas useless features are ignored.

Introduction

Distance learning platforms and more specifically, the Intelligent Tutoring Systems (ITS) play an increasing and important role in society. Towards an efficient and effective implementation of such systems, the technology of Intelligent Agents (IA) is gradually integrated. Processes are assigned to IA that must be complete under specific limitation [START_REF] Jennings | Agent Technology[END_REF]. In this way, acting on behalf of the users, they implement an additional type of interaction which is often referred as indirect administration [START_REF] Kay | User Interface: A Personal View[END_REF]. At the same time, IA can be reeducated and formed in such a way that they will perform an optimal gathering and processing of information. In other words, they will gradually become more efficient by learning the interests, the habits and the preferences of the users and their community [START_REF] Bentley | Managing information: Avoiding Overload[END_REF]. Moreover, they help the members of the educational community to effectively cooperate, to schedule their workload and to take part in common events.

The fact that the IA act without human intervention or intervention from other systems, gives them the desirable autonomy meaning that they have their own control practice and can take their own decisions which are presented to the users [START_REF] Leng | A Role-Based Cognitive Architecture for Multi-Agent Teaming[END_REF][START_REF] Franklin | Is it an Agent, or Just a Program? A Taxonomy for Autonomous[END_REF]. For this reason, they must be reliable. By taking decisions on behalf of the users, they should guarantee the quality of the services that are provided. Finally, for the efficient communication among the IA, it is essential that they act simultaneously and without interruption so that every process is handled directly [START_REF] Jennings | Agent Technology[END_REF].

Competence and Confidence

The purpose of IA is to help the educational community; however this presupposes the resolving of two basic problems. The first one is the competence, i.e. how an IA receives the desired information (knowledge) so as to decide when and how it can help the educational community. Under this scope, the efficiency and the effectiveness will depend on the number of key characteristics as well as on the quality of the information that are accessible from the IA. The second problem concerns confidence, i.e. how the educational community can feel secure when assign tasks to an IA. An implementation, which is in accordance with the necessary requirements and provides solutions to the above-mentioned problems, is the trained IA, presented by Pattie Maes [START_REF] Maes | Agents that Reduce Work and Information Overload[END_REF]. One trained IA can develop its competence through four different ways. First, it is trained by monitoring the activities of the user; it records the user's actions and seeks possible repetitions of behavioral patterns which can be automated. Secondly, it is adjusted based on direct or indirect user feedback. Indirect feedback is received when the user ignores the suggestion made by the IA or when negative feedback is given to an automatic IA action. Third, it is trained through explicit examples by the user, who is the one to show what action should be taken at various hypothetical situations. Fourth, it seeks advice coming from others either more experienced or supplementary IA, which support users in similar processes (situations).

This approach boosts confidence by allowing the IA to provide explanations both for the reasoning and for the behavior in a familiar to the user form. For example, it should explain to the students that, we propose you to proceed to this action:  due to the fact that there is similarity among past preferences for something  or there is similarity among past actions  or it was applied by another student with similar preferences.

Filtering the information

Filtering the information that enters and circulates in a ITS was and still remains an open issue theoretically and practically. Its goal is to introduce to users only the information that is relevant to them. Generally, the existing Information Filtering Systems represent a type of an information retrieval system designed for the management of large volume unstructured or semi structured data [START_REF] Hanani | Information Filtering: Overview of Issues, Research and Systems[END_REF].

There are three basic methods of information filtering: simple, based on the content and collaborative [START_REF] Palme | Information Filtering[END_REF][START_REF] Juszczyszyn | Personalized Ontology-Based Recommender Systems for Multimedia Objects[END_REF]. Simple Filtering is based on the categorization of the users in groups according to their personal features and their profiles. Thus, an IA will be in the position to send the appropriate information to the members of each category.

In Content-Based Filtering, the content of the existing information is analyzed and a representation of the interests (views) of the educational community members is formed. For this purpose, the teacher has to establish a set of key characteristics for every learning item and then the student has to assign the appropriate values to each characteristic. Content-based filtering uses the Euclidean distance in order to analyze the evaluations of key-characteristics and thus to establish the closer value that could be proposed to the "new" user.

In Collaborative Filtering, the viewpoints of the users about the educational objects are collected, either directly or indirectly, in order to develop clusters of likeminded persons. This system, in contrast with the content-based filtering, proposes information that has been evaluated by students of similar abilities and preferences with the user that receives the new educational material. In this case, the Euclidean distance is also used for the analysis of the values and the designation of information that will be proposed to the user.

Intelligent Tutoring Systems

The Intelligent Tutoring Systems (ITS) represent applications with major knowledge on a specific subject and aim to transfer this knowledge to the students through an interactive individualized process. They are trying to simulate the educational process so that a virtual teacher will guide the student to the learning process. The purpose of each ITS is to effectively convey its incorporated knowledge.

The main problem of ITS lies on their adaptation to the students' needs. In addition, students continuously interact with the system. The adaptation of the user is provided through pedagogical strategies which determine the sequence, the type of given assistance during the teaching and learning procedure, the time frame and the way of presenting the teaching material (problems, definitions, examples etc).

Generally, the architecture of an ITS consists of four basic components: the Student Model, the Field Model, the Pedagogical Unit and the Educational Unit [START_REF] Gascueña | An Agent-based Intelligent Tutoring System for Enhancing E-Learning/E-Teaching[END_REF]. Moreover, its function is supported by the following intelligent agents: the Preference agent, the Accounting agent, the Activity agent and the Test agent [START_REF] Håkansson | Agent and Multi-Agent Technology for Internet and Enterprise Systems[END_REF]. These IA must cooperate, help and complement each other in a dynamic way.

Application Example of a Test Agent

By extending the functionality of an ITS, we will analyze a way of calculating the suggestions produced by the Test agent, on the basis of the preferences of Greek students who learn Russian motion verbs with prefixes. These verbs cannot be understood by the students since the application of a prefix entails multiple meanings and multiple ways of use. In addition, the same prefixes have similar meanings indicating either proximity or withdrawal at different degree of achievement. There are no equivalent verbs in Greek language, which makes the situation more complex and enforces the development of many exercises on behalf of the teachers.

Having successfully finished with the exercises in the test phase, our research indicates confusion among students when all prefixes are used in combination with all pairs of motion verbs. More specifically, some prefixes in Greek language do not exist or have a similar meaning. The testbed of 10 classes of 10 students per class faced a particular difficultly as far as the following three groups of prefixes are concerned: IA suggests some tests to the students from the same category according to collaborative filtering technique the tests are evaluated later. Then, these grades are compared with those of other users, their similarity is estimated and the current user is provided with highly-evaluated activities by users of the same preferences as him/her.

(i) |При-| До-| Под-|, (ii) |Пере-| Про-|, and (iii) |Вы-| У-| (Table 1
As mentioned above, collaborative filtering technique makes use of the Euclidean distance in order to calculate the degree of evaluation similarity among users. It is assumed that each student can evaluate the activities with the use of a scale ranging from 1 (he/she does not like the activity at all) to 5 (he/she likes it very much), while 3 denotes a neutral opinion.

Let's assume the students A, B and C have evaluated three tests each as Table 2 shows.

Table 2. Ratings of the tests by the students plus a possible execution route.

We assume that the current user is C. At first, the Test agent will calculate the Euclidean distance of C from the other students. For example, the distance between C and B for i activities is calculated as follows:

It is noted that only common ratings, in our case that are those of tests 1 and 2, are taken into account. The corresponded Euclidean distance of student C from student A is 3,61. It is observed that the student who has the nearest distance from C is A. Finally, the Test agent will suggest to student C the most highly-rated activities of student A which haven't been already executed and rated by him/her. In a similar way we implement the proposals from the Activity agent.

Conclusions

Traditionally, when a teacher and his/her team, prepares the educational material and determines the outlines of the teaching process, he does not take into account the personality and the special characteristics of the students in the audience. The teacher assumes that the audience is a team which is logical because he/she has never a permanent, face to face, contact with all the students. However, this is not the case when the educational process takes place in a virtual, digital world. In such a world, personal contact is restricted or non-existent; nevertheless there is an increasing amount of old and new, primary or secondary external information regarding each of the students. The ITS analyze and collect all necessary data from the interaction of students with the system, thus the rate of presenting the contents of the educational material, the learning ability are adjusted to the preferences and the learning styles of each student. They offer invaluable assistance to the teachers, because the student is in a controlled but at the same time in a friendly environment. Moreover, individual proposals allow the avoidance of the student's information overload and improve the interaction with the system.

Evaluations

Our research will be continued with the study of more complex situations of interconnection. Specifically, our goal is the smooth and effective transition from the exercises to the tests, through the collaboration between the Test and the Exercise agent.

Table 1 .

 1 ). Prefixes with similar meaning and usage

	Directional prefixes	Meaning in Greek (English)
		При-	Άφιξη: μπαίνω μέσα (Arrival: to come to see a person / to come to a place)
	with oppo-	У-	Αναχώρηση (Departure: to leave a person / to leave a place)
	sites	Вы-	Έξοδος (Exit: to go out of a place)
		Под-	Προσέγγιση (Approaching: to go up to / to approach)
		Про-	Κίνηση διαμέσου, διέλευση δίπλα από κάποιο αντικείμενο (Motion through or pass: to go through / to pass)
	without opposites	До-	Φτάνω μέχρι (Reach a destination: to go as far as)
		Пере-	Κίνηση από τη μία άκρη στην άλλη, από ένα σημείο σε άλλο (Motion across: to cross / to go across)


Giannakouris -Salalidis Victor

Plerou Antonia

Sioutas Spyros
email: sioutas@ionio.gr

CSMR: A Scalable Algorithm for Text Clustering with Cosine Similarity and MapReduce

Keywords: MapReduce, Hadoop, TF-IDF, Text Mining, Cosine Similarity

As Internet develops rapidly huge amounts of texts need to be processed in a short time. This entails the necessity of fast, scalable methods for text processing. In this paper a method for pairwise text similarity on massive data-sets, using the Cosine Similarity metric and the tf-idf (Term Frequency-Inverse Document Frequency) normalization method is proposed. The research approach is mainly focused on the MapReduce paradigm, a model for processing large data-sets in parallel manner, with a distributed algorithm on computer clusters. Through MapReduce model application on each step of the proposed method, text processing speed and scalability is enhanced in reference to other traditional methods. The CSMR (Cosine Similarity with MapReduce) method's implementation is currently at the implementation stage. Precise and analytical conclusions concerning the efficiency of the proposed method are to be reached upon completion and review of the overall project phases.

Introduction

Nowadays, as the data amount grows rapidly, challenge of big data need to be faced [START_REF] Wu | Data Mining with Big Data[END_REF] in various domains such as Business Intelligence [START_REF] Chen | B USINESS I NTELLIGENCE AND A NALYTICS : F ROM B IG D ATA TO B IG I[END_REF] or Bioinformatics [START_REF] Taylor | An overview of the Hadoop/MapReduce/HBase framework and its current applications in bioinformatics[END_REF][START_REF] Matsunaga | CloudBLAST: Combining MapReduce and Virtualization on Distributed Resources for Bioinformatics Applications[END_REF]. With ever increasing volume of text documents, the abundant texts flowing over the Internet, huge collections of documents in digital libraries and digitized personal information are collected quickly every day [5]. In this paper, an innovative method for text similarity measuring with the use of common techniques and metrics is proposed.

In particular, a prospective of applying tf-idf [START_REF] Ramos | Using TF-IDF to Determine Word Relevance in Document Queries[END_REF] and Cosine Similarity [START_REF] Tata | Estimating the Selectivity of tf-idf based Cosine Similarity Predicates[END_REF] measurements on distributed text processing is further analyzed. The CSMR (Cosine Similarity with MapReduce) method includes the component of document pairwise similarity calculation. Especially, CSMR method performs pairwise text similarity with the use of a parallel and distributed algorithm which scales up, regardless the massive input size. This is utilized with the use of MapReduce component of the Hadoop Framework. The authors' proposed method consists by two main components: tf-idf and Cosine Similarity. In this study, these components are designed by following the concept of the MapReduce programming model. Initially, the terms of each document are counted. Secondly, texts are normalized with the use of tf-idf. Finally, Cosine Similarity of each document pair is calculated and results are given as an output. The CSMR method is proposed as a faster and more efficient method comparing to the traditional methods. This is due to MapReduce model implementation in each algorithmic step tends to enhance method's efficiency as well as to the aforementioned techniques innovative blend.

Related Work

There are quite many cases where several methods have been used for measuring similarity among texts. Tamer Elsayed et.al [START_REF] Elsayed | Pairwise Document Similarity in Large Collections with MapReduce[END_REF] method focuses on a MapReduce algorithm for computing pairwise document similarity in large document collections. The algorithm proposed exhibits linear growth in running time and space, in terms of the number of documents. This algorithm is suggested as an example of a programming paradigm that could be useful for a broad range of text analysis problem. Another approach has been proposed by Bin Li et.al [START_REF] Bin | Improvement of TF-IDF Algorithm Based on Hadoop Framework[END_REF], i.e. a tf-idf algorithm based on the Hadoop framework. This method is using the MapReduce model provided by Hadoop in order to improve the efficiency of traditional tf-idf algorithm. This case study showed that in the case of massive data computing, Hadoop framework implementation is more efficient comparing to the traditional method. Jacob Bank et.al [START_REF] Bank | Calculating the Jaccard Similarity Coefficient with Map Reduce for Entity Pairs in Wikipedia[END_REF] use a different approach in order to analyze the vast amounts of data associated with large-scale social networks on the web with the use of the MapReduce program. The Jaccard similarity coefficient between users of Wikipedia based on co-occurrence of page edits is proposed. After several separate linear time computations it was con-firmed that this approach was superior to quadratic computations on long lists of data. Calculating the Jaccard Similarity Coefficient with Map Reduce for Entity Pairs in Wikipedia. Furthermore, Jian Wan et.al [START_REF] Wan | Design and Implement of Distributed Document Clustering Based on MapReduce[END_REF] proposed an approach about how document clustering for large collection could be efficiently implemented with MapReduce. Additionally tf-idf and K-Means algorithm on MapReduce design and implementation is described in order to improve algorithm efficiency and effectiveness. Experimentation confirmed the scalability of processing mass data proposed method. Ping Zhou et.al [START_REF] Zhou | Large-Scale Data Sets Clustering Based on MapReduce and Hadoop[END_REF] supplementary research in reference to large-scale data sets clustering amplification a parallel K-Means algorithm based on MapReduce framework is proposed. Model's implementation results illustrated that the proposed clustering algorithm running on Hadoop cluster preserve a higher performance while handling large-scale document automatic classification. In the above mentioned methods dealing with text clustering, there is none or only a slight and indirect approach via Cosine Similarity in order to improve processing speed and scalability. Finally, according to Rada Mihalcea et.al [START_REF] Mihalcea | Corpus-based and Knowledge-based Measures of Text Semantic Similarity[END_REF] approach a method for measuring the semantic similarity of short texts, using corpus-based and knowledge-based measures of similarity is presented. Through experiments per-formed on a paraphrase data set, semantic similarity method outer-forms methods based on simple lexical matching, resulting in up to 13% error rate reduction with respect to the traditional vector-based similarity metric. On the contrary, they focus to the aspect that Cosine Similarity, tfidf as well as other methods can be used for text similarity measuring. There are also some approaches using MapReduce but, according to authors' knowledge, none of them proposes a model with tf-idf and Cosine function.

Authors' proposed method combines overall of these 3 powerful techniques, i.e. tfidf, Cosine Similarity and MapReduce and provides a powerful and scalable algorithm suitable for various purposes on Data Mining, especially on Text Processing on big, massive data-sets.

Basic Background

According to the project needs, three techniques had been chosen: The Vector Space Model, tf-idf and Cosine Similarity. Each of these techniques is being described in detail below.

Vector Space Model

Vector Space Model is an algebraic model for representing text documents as vectors. [START_REF] Turney | From Frequency to Meaning : Vector Space Models of Semantics[END_REF] With the use of this model, each term of a document and each number of occurrences in the document could be represented [START_REF] Raghavan | A critical analysis of vector space model for information retrieval[END_REF]. For instance, the document d1 = "This is a vector, this is algebra" based on a vocabulary 𝑉(𝑡) could be represented as follows:

1, " " 2, " " ( ) 3, " " 4, " " 5, " lg "

t this t is V t t a t vector t a ebra                        𝑑1 = (𝑡𝑓(1, 𝑑1), 𝑡𝑓(2, 𝑑1), 𝑡𝑓(3, 𝑑1), 𝑡𝑓(4, 𝑑1), 𝑡𝑓(5, 𝑑1)) = (2,2,1,1,1)
Where d1 is the document and ( , ) i tf t d is the term frequency of the t-term in the i th document.

Tf-Idf

In Text Mining, tf-idf (Term Frequency-Inverse Document Frequency) [START_REF] Ramos | Using TF-IDF to Determine Word Relevance in Document Queries[END_REF] is a numerical statistic that reflects the significance of a term in a document in a corpus. The importance increases proportionally to the number of times a word appears in the document but is offset by the frequency of the word in the corpus. Tf-idf algorithm is usually used in search engine, web data mining, text similarity computation and other applications [16]. These applications are often faced with massive data processing. According to Bin Li [START_REF] Bin | Improvement of TF-IDF Algorithm Based on Hadoop Framework[END_REF]approach the tf-idf of a term is calculated with the use of the following formula:

, || log | | | : | ij j n D TF IDF t d d D t d      

Cosine Similarity

Cosine Similarity is a measure of similarity between two vectors of an inner product space that measures the cosine of the angle between them [START_REF] Kalaivendhan | An Efficient Clustering Method To Find Similarity Between The Documents[END_REF]. For document clustering, there are different similarity measures available. The Cosine function is proposed as the most commonly used. For two documents A and B, the similarity between them is calculated with the use of the following formula:

1 1 2 2 1 1 cos(A, B) || A |||| B || ( ) ( ) n i i n i i i i i AB AB A B           
When the cosine value is computed to be 1, that indicates that the two documents are identical and while it is computed to be 0 if there is nothing in common between them (i.e., their document vectors are orthogonal to each other). The attribute vectors A and B are usually the term frequency vectors of the documents.

Hadoop & MapReduce

Hadoop software library [START_REF] Shvachko | The Hadoop Distributed File System[END_REF], is a framework developed by Apache, suitable for scalable, distributed computing. It allows storage and large-scale data processing across clusters of commodity servers [START_REF] Lin | A Practical Performance Model for Hadoop MapReduce[END_REF]. The innovative aspect of Hadoop is that there is no absolute necessity of expensive, high-end hardware. Instead, it enables distributed parallel processing of massive amounts of data [START_REF] Ekanayake | MapReduce for Data Intensive Scientific Analyses[END_REF] on industry-standard servers with high scalability for both data storing and processing. Therefore it is considered to be one of the most popular frameworks for Big Data Analytics. Especially, Hadoop has two main subprojects: HDFS (Hadoop Distributes File System) & MapReduce.

MapReduce [START_REF] Dean | Simplified Data Processing on Large Clusters[END_REF] is the main component of Hadoop. It's a programming model that allows massive data processing across thousands of servers in a Hadoop cluster. The MapReduce paradigm is derived from the Map and Reduce functions of the Functional Programming model [START_REF] Lämmel | Google's MapReduce programming model -Revisited[END_REF]. A MapReduce program constitutes from the Mappers and the Reducers. In the Map phase, the master node the master node divides the input into smaller partitions and distributes them to the worker nodes. Then a worker node may repeat the same step recursively. As soon as this procedure is completed, the master node collects the key-value pairs resulted from the Mappers and distributes them to the Combiners to combine the pairs with the same key. This phase is known as the Shuffle & Sort phase. Finally, the key-value pairs are distributed to the Reducers that produce the final output. This step is called the Reduce phase. MapReduce program procedure is visualized as follows:

Description

Authors' proposed method for measuring text similarity applying MapReduce consists of 4 stages. At the first stage, occurrences of each term in our documents are counted. Then, the term frequency of every one term in each document is measured.

Thereafter the tf-idf of each term is measured and finally the cosines of the pairs are calculated in order to estimate the similarity among them. MapReduce model was used in order to design each one of the above mentioned steps. The algorithm paradigm in pseudocode and further analysis of each step is disposed in details in the next section.

MapReduce Stages

In the 1 st implementation stage the occurrences of each term in every document are counted. The algorithm applied is as follows:

13: /* { o ∈ N : the number of occurrences } */

Initially, each document is divided into key-value pairs. The term is selected as the key as well as the number one as the value. That is denoted as (term, 1) where key corresponds to the term and the value to the number one respectively. This phase is known as the Map Phase. In the Reduce Phase each pair is taken and the sum of the list of ones for the term is computed. Finalizing, the key is set as the tuple (document, term) and the value as the number of occurrences respectively.

In the 2 nd implementation phase the overall number of terms of each document is computed.

return ( (docId, N), (term, o) )

By this algorithm implementation, concerning the Map Phase, the input is divided into key-value pairs while the docId is set as the key in addition to the tuple (term, o) as the value. In the reduce phase the total of terms in each document is counted and the key-value pairs are returned with the (DocId, N) as the key as well as the tuples (term, o) as the value (N is the total of terms in the document). The key-value pairs are returned with the tuples (docId, N) as the key and the tuples (term, o) as the value, where N is the total of terms in the document.

In the 3 rd implementation stage the tf-idf of each term in a document is computed with the use of the following formula: Applying the aforementioned algorithm, during the Map Phase the term is set as the key as well as the tuple (docId, o, N) as the value. In that case, the number of documents is calculated by the reducer, where the term appears and the result to the n variable is set. The term frequency is subsequently calculated plus the inverse document frequency of each term as well. Finally, key-value pairs with the docId as the key and the tuple (term, tf×idf) as the value are taken as a result.

In the 4 th and final implementation phase all the possible combinations of two documents pairs are provided and cosine for each of them is computed. Assuming that there are n documents in the corpus, a similarity matrix of size is generated as follows: In the Map phase, implementing the abovementioned algorithm, every potential combination of the input documents is generated and the document IDs for the key as well as the tf-idf vectors for the value is set. Within the Reduce phase, cosine for each document pair is calculated and the similarity matrix is also provided. Algorithm 4 is visualized as follows:

! 2 2!( 2)! n n n    
Input Output

Discussion

In this case study, popular methods for measure the similarity of texts had been used. In particular, tf-idf and Cosine Similarity were adjusted with the MapReduce model in order to propose an innovative and scalable method. Authors' approach enhances the innovative aspect of the MapReduce programming paradigm in the field of text processing. The key contribution is that the proposed method enhances the procedure of measuring the text similarity with the Cosine metric and increase algorithm scalability. The implementation of the aforementioned techniques on computer clusters run-ning the Hadoop Distributed File System (HDFS) blended with MapReduce also ensure algorithms effectiveness. The proposed method is currently at the design and implementation stage. Therefore, more clear and specific conclusions for its efficiency, as well as proposals for revisions and improvement, are to be provided after the projects' overall implementation. Authors' future work concerns the finalized proposed method version as well as statistically analyzed results of the data collected during piloting implementation procedure presentation. In addition the software's design and development for the CSMR algorithm implementation on real text files is ongoing. An additional research approach is the implementation of the abovementioned algorithm with the use of tools like Apache Spark and Scala [START_REF] Zaharia | Spark : Cluster Computing with Working Sets[END_REF] as well as an Open Source project implemented in Java.

Fig. 1 .

 1 Fig. 1. MapReduce Procedure Visualization

Fig. 2 .

 2 Fig. 2. Algorithm 4 Visualization

* Where |D| is the number of documents in the corpus */

			tfidf		|| : D N d D t d |{ n  	|
	Where |D| is the number of the documents in corpus and	|{ d D t d :  	}|	number of
	documents where t-term appears.
	Algorithm 3: Tf-Idf
	1: class Mapper
	2:	method Map( ( docId , N ), ( term , o ) )
	3:	for each element ∈ ( term , o )
	4:	write ( term, ( docId, o, N ) )
	5:
	6: class Reducer
	7:	method Reduce( term, ( docId , o , N ) )
	8:	n = 0
	9:	for each element ∈ ( docId , o , N ) do
	10:	n = n + 1
	11:	tf = o / N
	12:	idf =	 log | D | /(1 n) 	
	13:	return ( docId, ( term , tf×idf ) )
	14:
	15: /

  

	20: for i = 0 to docs.length
	21:	for j = i+1 to docs.length
	22:	write ( ( docs[i].id, docs[j].id ),( docs[i].tfidf, docs[j].tfidf ) )
	23:
	24: class Reducer
	25: method Reduce( ( docId_A, docId_B ),( docA.tfidf, docB.tfidf ) )
	26:	A = docA.tfidf
	27:	B = docB.tfidf
	28:	cosine = sum( A×B )/ (sqrt( sum(A 2 ) )× sqrt( sum(B 2 ) ))
	29: return ( (docId_A, docId_B), cosine )
	Algorithm 4: Cosine Similarity
	16: class Mapper
	17: method Map( docs )
	18:	n = docs.length
	19:

Doc1,Doc2 [Doc1 TF -IDF], [Doc2 TF -IDF] Doc1,Doc3 [Doc1 TF -IDF], [Doc3 TF -IDF] Doc1,Doc4 [Doc1 TF -IDF], [Doc4 TF -IDF] Doc4,Doc10 [Doc4 TF -IDF], [Doc10 TF -IDF] DocM,DocN [DocM TF-IDF], [DocN TF-IDF] Map Doc1,Doc2 Cosine(Doc1, Doc2) Doc1,Doc3 Cosine(Doc1, Doc3) Doc1,Doc4 Cosine(Doc1 ,Doc4) Doc4,Doc10 Cosine(Doc4, Doc10) DocM,DocN Cosine(DocM, DocN) Reduce

Acknowledgements. This research has been co-financed by the European Union (European Social Fund -ESF) and Greek national funds through the Operational Program "Education and Lifelong Learning" of the National Strategic Reference Framework (NSRF) -Research Funding Program: Thales. Investing in knowledge society through the European Social Fund.


Kalle Tomingas

Tanel Tammet

Margus Kliimask

Rule-based Impact Analysis for Enterprise Business Intelligence

Keywords: impact analysis, data lineage, data warehouse, rule-based reasoning, probabilistic reasoning, semantics

We address several common problems in the field of Business Intelligence, Data Warehousing and Decision Support Systems: the complexity to manage, track and understand data lineage and system component dependencies in long series of data transformation chains. The paper presents practical methods to calculate meaningful data transformation and component dependency paths, based on program parsing, heuristic impact analysis, probabilistic rules and semantic technologies. Case studies are employed to explain further data aggregation and visualization of the results to address different planning and decision support problems for various user profiles like business users, managers, data stewards, system analysts, designers and developers.

Introduction

Developers and managers are facing similar Data Lineage (DL) and Impact Analysis (IA) problems in complex data integration (DI), business intelligence (BI) and Data Warehouse (DW) environments where the chains of data transformations are long and the complexity of structural changes is high. The management of data integration processes becomes unpredictable and the costs of changes can be very high due to the lack of information about data flows and internal relations of system components. The amount of different data flows and system component dependencies in a traditional data warehouse environment is large. Important contextual relations are coded into data transformation queries and programs (e.g. SQL queries, data loading scripts, open or closed DI system components etc.). Data lineage dependencies are spread between different systems and frequently exist only in program code or SQL queries. This leads to unmanageable complexity, lack of knowledge and a large amount of technical work with uncomfortable consequences like unpredictable results, wrong estimations, rigid administrative and development processes, high cost, lack of flexibility and lack of trust. We point out some of the most important and common questions for large DW environments (see Fig. 1) which usually become a topic of research for system analysts and administrators:  Where does the data come or go to in a specific column, table, view or report?  Which components (reports, queries, loadings and structures) are impacted when other components are changed?  Which data, structure or report is used by whom and when?  What is the cost of making changes?  What will break when we change something? The ability to find ad-hoc answers to many day-to-day questions determines not only the management capabilities and the cost of the system, but also the price and flexibility of making changes. The dynamics in business, environment and requirements ensure that regular changes are a necessity for every living organization. Due to its reflective nature, the business intelligence is often the most fluid and unsteady part of enterprise information systems.

Obviously, the most promising way to tackle the challenges in such a rapidly growing, changing and labor-intensive field is automation. We claim that efficient automatization in this particular field requires the use of semantic and probabilistic technologies. Our goal is to aid the analysts with tools which can reduce several hard tasks from weeks to minutes, with better precision and smaller costs.

Related Work

Impact analysis, traceability and data lineage issues are not new. A good overview of the research activities of the last decade is presented in an article by Priebe et al. [START_REF] Priebe | Reinventing the Wheel?! Why Harmonization and Reuse Fail in Complex Data Warehouse Environments and a Proposed Solution to the Problem[END_REF]. We can find various research approaches and published papers from the early 1990s with methodologies for software traceability [START_REF] Ramesh | Toward reference models for requirements traceability[END_REF]. The problem of data lineage tracing in data warehousing environments has been formally founded by Cui and Widom [START_REF] Cui | Tracing the lineage of view data in a warehousing environment[END_REF] and [START_REF] Cui | Lineage tracing for general data warehouse transformations[END_REF]. Our recent paper builds upon this theory by introducing the Abstract Mapping representation of data transformations [START_REF] Tomingas | Data Integration Patterns for Data Warehouse Automation[END_REF].

Other theoretical works for data lineage tracing can be found in [START_REF] Fan | Using AutoMed metadata in data warehousing environments[END_REF] and [START_REF] Giorgini | GRAnD: A goal-oriented approach to requirement analysis in data warehouses[END_REF]. Fan and Poulovassilis developed algorithms for deriving affected data items along the transformation pathway [START_REF] Fan | Using AutoMed metadata in data warehousing environments[END_REF]. These approaches formalize a way to trace tuples (resp. attribute values) through rather complex transformations, given that the transformations are known on a schema level. This assumption does not often hold in practice. Transformations may be documented in source-to-target matrices (specification lineage) and implemented in ETL tools (implementation lineage).

Other practical works that based on conceptual models, ontologies and graphs for data quality and data lineage tracking can be found in [START_REF] Vassiliadis | Conceptual modeling for ETL processes[END_REF] and [START_REF] Skoutas | Ontology-based conceptual design of ETL processes for both structured and semi-structured data[END_REF]. De Santana proposes the integrated metadatada and the CWM metamodel based data lineage documentation approach [START_REF] De Santana | Metadata to support transformations and data & metadata lineage in a warehousing environment[END_REF]. The workflows and the manual annotations based solution proposed by Missier et al. [START_REF] Missier | Data lineage model for Taverna workflows with lightweight annotation requirements[END_REF].

Priebe et al. [START_REF] Priebe | Reinventing the Wheel?! Why Harmonization and Reuse Fail in Complex Data Warehouse Environments and a Proposed Solution to the Problem[END_REF] concentrates on proper handling of specification lineage, a huge problem in large-scale DWH projects, especially in case different sources have to be consistently mapped to the same target. They propose a business information model (or conceptual business glossary) as the solution and a central mapping point to overcome those issues.

Our approach to Impact Analysis and Data Lineage differs from previous work in several aspects. Our aim is to merge technical data lineage [START_REF] Cui | Lineage tracing for general data warehouse transformations[END_REF] with semantic integration approaches [START_REF] Priebe | Reinventing the Wheel?! Why Harmonization and Reuse Fail in Complex Data Warehouse Environments and a Proposed Solution to the Problem[END_REF], [START_REF] Reisser | Utilizing Semantic Web Technologies for Efficient Data Lineage and Impact Analyses in Data Warehouse Environments[END_REF], using grammar based methods for metadata extraction from program texts and a probabilistic rule-based inference engine for weight calculations and reasoning approaches [START_REF] Luberg | Smart City: A Rule-based Tourist Recommendation System[END_REF]. We also use the novel and powerful web based data flow and the graph visualization techniques with the multiple view approach [START_REF] Baldonado | Guidelines for using multiple views in information visualization[END_REF] to deliver the extraction and the calculation of the result to the end-users.

System Architecture

We present a working Impact Analysis solution which can be adopted and implemented in an enterprise environment or provided as a service (SaaS) to manage organization information assets, analyze data flows and system component dependencies. The solution is modular, scalable and extendable. The core functions of our system architecture are built upon the following components presented in the Fig. 2.

1. Scanners collect metadata from different systems that are part of DW data flows (DI/ETL processes, data structures, queries, reports etc.). We build scanners using our xml-based data transformation language and runtime engine XDTL [START_REF]XDTL Data Transformation Language[END_REF]. 2. The SQL parser is based on customized grammars, GoldParser parsing engine [START_REF] Cook | Gold parsing system[END_REF] and the Java-based XDTL engine.

3. The rule-based parse tree mapper extracts and collects meaningful expressions from the parsed text, using declared combinations of grammar rules and parsed text tokens. 4. The query resolver applies additional rules to expand and resolve all the variables, aliases, sub-query expressions and other SQL syntax structures which encode crucial information for data flow construction. 5. The expression weight calculator applies rules to calculate the meaning of data transformation, join and filter expressions for impact analysis and data flow construction. 6. The probabilistic rule-based reasoning engine propagates and aggregates weighted dependencies. 7. The directed and weighted sub-graph calculations, visualization and web based UI for data lineage and impact analysis applications. 8. The MMX open-schema relational database using PostgreSQL or Oracle for storing and sharing scanned, calculated and derived metadata [START_REF]MMX Metadata Framework[END_REF].

Query Parsing and Metadata Extraction

Scanners (No1 in Fig. 2) collect metadata from external systems: database data dictionary structures, ETL system scripts and queries, reporting system query models and reports. All the structural information extracted is stored to the metadata database.

The scanned objects and their properties are extracted and stored according to the meta-models we have designed: relational database, data integration, reporting and business terminology models. Meta-models contain ontological knowledge about the metadata and relations collected across different domains and models. The scanner technology (XDTL) and the open-schema metadata database (MMX) design have been described at a more detailed level in our previous work [START_REF] Tomingas | Mappings, Rules and Patterns in Template Based ETL Construction[END_REF], [START_REF] Tomingas | Data Integration Patterns for Data Warehouse Automation[END_REF].

In order to construct the data flows from the very beginning of the data sources (e.g. the accounting system) to the end points (e.g. the reporting system) we have to be able to find and connect both the identical and the related objects in different systems. In order to connect the objects we have to understand and extract the relations from the SQL queries (e.g. ETL tasks, database views, database procedures), scripts (e.g. loader utility scripts) and expressions (e.g. report structure) collected and stored by scanners. In order to understand the data transformation semantics encoded in the query language statements (e.g. insert, update, select and delete queries) and expressions, we have to involve external knowledge about the syntax and grammatical structure of the query language. Grammar-based parsing functionality is built into the scanner technology. A configurable "parse" command brings semi-structured text parsing and information extraction into the XDTL data integration environment. As the result of SQL parsing step (No2 in Fig. 2) we get a large parse tree with every SQL query token assigned a special disambiguated meaning by the grammar.

In order to convert different texts into the tree structure, to reduce tokens and to convert the tree back to the meaningful expressions (depending on search goals), we use a declarative rule set presented in the Json format, combining token and grammar rules. A configurable grammar and a synchronized reduction rule set makes the XDTL parse command suitable for general purpose information extraction and captures the resource hungry computation steps into one single parse-and-map step with the flat table outcome. The Parse Tree Mapper (No3 in Fig. 2) uses three different rule sets with more than eighty rules to map the parse tree to data transformation expressions.

After extraction and mapping of each SQL query statement into a series of expressions we execute the SQL Query Resolver (No4 in Fig. 2) which contains a series of functions to resolve the SQL query structure:  Solve source and target object aliases to full qualified object names;  Solve sub-query aliases to context specific source and target object names;  Solve sub-query expressions and identifiers to expand all the query level expressions and identifiers with fully qualified and functional ones;  Solve syntactic dissymmetry in different data transformation expressions (e.g. insert statement column lists, select statement column lists and update statement assign list etc.);  Extract quantitative metrics from data transformation, filter and join expressions to calculate expression weights (e.g. number of columns in expression, functions, predicates, string constants, number constants etc.).

Data Transformation Weight Calculation

Data structure transformations are parsed, extracted from queries and stored as formalized, declarative mappings in the system. To add additional quantitative measures to each column transformation or column usage in the join and filter conditions we evaluate each expression and calculate transformation and filter weights for those. Expression Weight Calculation (No5 in Fig. 2) is based on the idea that we can evaluate column data "transformation rate" and column data "filtering rate" using data structure and structure transformation information captured from SQL queries. Such a heuristic evaluation enables us to distinguish columns and structures used in the transformation expressions or in filtering conditions or both, and gives probabilistic weights to expressions without the need to understand the full semantics of each expression. We have defined two measures that we further use in our probabilistic rule system for deriving new facts: Definition 1. A primitive data transformation operation O(X,Y,M1,F1,W t ) is a data transformation between a source column X and a target column Y in a transformation set M (mapping or query) having expression similarity weight W t and having conditions set F1. Definition 2. Column transformation weight W t is based on the similarity of each source column and column transformation expression: the calculated weight expresses the source column transfer rate or strength. The weight is calculated on scale [0,1] where 0 means that the source data are not transformed to target (e.g. constant assignment in a query) and 1 means that the source is directly copied to the target (no additional column transformations). Definition 3. Column filter weight W f is based on the similarity of each filter column in the filter expression and the calculated weight expresses the column filtering rate or strength. The weight is calculated on scale [0,1] where 0 means that the column is not used in the filter and 1 means that the column is directly used in the filter predicate (no additional expressions).

The general column weight W algorithm in each expression for W t and W f components is calculated as a column count ratio over all the expression component counts (e.g. column count, constant count, function count, predicate count):

W=IdCount/IdCount+FncCount+StrCount+NbrCount+PrdCount.

Rule System

The defined figures, operations and weights are used in combination with the declarative probabilistic inference rules to calculate the possible relations and dependencies between data structures and software components. Applying the rule system to the extracted query graphs we calculate and produce a full dependency graph that is used for data lineage and impact analysis.

The basic operations used in the rules for the dependency graph calculations are the following:  The primitive data transformation is the elementary operation between the source column X and the target column Y in the query mapping id set M1 with the filter condition set F1 and the transformation weight W t (see Definition 1). This is represented by the predicate O(X,Y,M1,F1,Wt);  The predicate member(X,F1,Wt) is used in the filter impact calculation rule to detect that the column X is a member of the filter id set F1 with the filter weight Wt;  The predicate disjoint(M1,M2)is used in the impact aggregation rule to detect that two query mapping id sets M1 and M2 are disjoint. The disjointness condition is necessary for aggregating the data transformation relations and weights in case more than one path from different queries connects the same column pairs;  The predicate parent(X0,X1) is used in the parent aggregation rule to detect that the table X0 is the owner or parent object of the column X1. This condition is necessary for aggregating all the column level relations and the weights between two tables for the table level impact relation;  The function union(M1,M2) is used to calculate the impact relations over two disjoint query id sets M1 and M2: it returns the distinct id lists of two sets M1 and M2;  The function sum(W1,W2) is used to calculate the aggregated impact relation weight in case the basic operations are disjoint, i.e. stem from independent queries. The weight calculation is based on non-mutually-exclusive event probabilities (two independent queries means there could be an overlap between two events) and is calculated as the sum of probabilities of W1 and W2: sum(W1,W2)=(W1+W2)-(W1*W2);  The function avg(W1,W2) is used to calculate the parent impact weight when the basic operations have the same parent structures. The weight is calculated as the arithmetic mean of W1 and W2: avg(W1,W2)=(W1+W2)/2;

The inference rules with the basic operations and the weighs for the dependency graph calculations are the following:  The parent aggregation rule is used when multiple different impact relations connect the column pairs of the same tables: calculate the table level impact relations with aggregated query id-s and aggregated weights:

I(X1,

Dependency Score Calculation

We can use the derived dependency graph to solve different business tasks by calculating the selected component(s) lineage or impact over available layers and details chosen details. Business questions like: "What reports are using my data?", "Which components should be changed or tested?" or "What is the time and cost of change?" are converted to directed sub-graph navigation and calculation tasks. The following definitions add new quantitative measures to each component or node (e.g. table, view, column, etl task, report etc.) in the calculation. We use those measures in the UI to sort and select the right components for specific tasks. Definition 4. Local Lineage Dependency % (LLD) is calculated as the ratio over the sum of the local source and target Lineage weights W t : LLD = SUM(source(W t )/source(W t )+target(W t )).

Local Lineage Dependency 0 % means that there are no data sources detected for the object. Local Lineage Dependency 100 % means that there are no data consumers (targets) detected for the object. Local Lineage Dependency about 50 % means that there are equal numbers of weighted sources and consumers (targets) detected for the object.

Definition 5. Local Impact Dependency % (LID) is calculated as the ratio over the sum of local source and target impact weights W(W t, ,W f ):

LID=SUM(source(W) /source(W)+target(W)).

Local Impact Dependency 0 % means that there are no dependent data sources detected for the object. Local Dependency 100 % means that there are no dependent data consumers (targets) detected for the object. Local Impact Dependency about 50 % means that there are equal numbers of weighted dependent sources and consumers (targets) detected for the object. Definition 6. Global Dependency Count (GDC) is the sum of all source and target Lineage and Impact relations counts: GDC=GSC+GTC.

The Global Dependency Count is a good differential metric that allows us to see clear distinctions in the dependencies of each object. We can take the GDC metric as a sort of "gravity" of the object that can be used to develop new rules, to infer the time and cost of changes of object(s) (e.g. database table, view, data loading programs or report).

6

Conclusions and Future Work

The previously described architecture and algorithms have been used to implement an integrated toolset dLineage (http://dlineage.com). Both the scanners and web-based tools of dLineage have been enhanced and tested in real-life projects and environments to support several popular DW database platforms (e.g. Oracle, Greenplum, Teradata, Vertica, PostgreSQL, MsSQL, Sybase), ETL tools (e.g. Pentaho, Oracle Data Integrator, SQL scripts and different data loading utilities) and BI tools (e.g. SAP Business Objects, Microstrategy). The dLineage dynamic visualization and graph navigation tools are implemented in Javascript using the d3.js graphics libraries.

We have tested our solution during two main case studies involving a thorough analysis of large international companies in the financial and the energy sectors. Both case studies analyzed thousands of database tables and views, tens of thousands of data loading scripts and BI reports. Those figures are far over the capacity limits of human analysts not assisted by the special tools and technologies.

We have presented several algorithms and techniques for quantitative impact analysis, data lineage and change management. The focus of these methods is on automated analysis of the semantics of data conversion systems followed by employing probabilistic rules for calculating chains and sums of impact estimations. The algorithms and techniques have been successfully employed in two large case studies, leading to practical data lineage and component dependency visualizations.

We are planning to continue this research by considering a more abstract, conceptual/business level in addition to the current physical/technical level of data representation.

Fig. 1 .

 1 Fig. 1. General scheme of DW/BI data flows.

Fig. 2 .

 2 Fig. 2. Impact Analysis system architecture components.



  The basic impact calculation rule for the operation O with no additional filters produces the impact predicate I: O(X,Y,M1,F1,Wt) => I(X,Y,M1,F1,Wt);  The basic impact calculation rule for the operation O with a related filter condition produces the impact predicate I with multiplied weights: O(X,Y,M1,F1,Wt)& member(X,F1,Wf) => I(X,Y,M1,F1,Wt*Wf);  The transitivity rule is used to calculate the sequences of the consecutive impact relations: I(X,Y,M1,F1,W1) & I(Y,Z,M2,F2,W2) & disjoint(M1,M2) => I(X,Z,union(M1,M2),union(F1,F2),W1*W2); The column aggregation rule is used when multiple different paths from the different queries connect the same columns: calculate the impact relations with aggregated query id-s and the aggregated weights: I(X,Z,M1,F1,W1) & I(X,Z,M2,F2,W2) & disjoint(M1,M2) => I(X,Z,union(M1,M2),union(F1,F2),sum(W1,W2));

  Y1,M1,F1,W1) & I(X2,Y2,M2,F2,W2) & parent(X0,X1)& parent(X0,X2) & parent(Y0,Y1) & parent(Y0,Y2) => I(X0,Y0,union(M1,M2),union(F1,F2),avg(W1,W2)).

Acknowledgments

This research has been supported by European Union through European Regional Development Fund.