Constantinos Stylianou
email: cstylianou@cs.ucy.ac.cy

Andreas S Andreou
email: andreas.andreou@cut.ac.cy

Intelligent Software Project Scheduling and Team Staffing with Genetic Algorithms

Keywords: Software project management, project scheduling, team staffing, genetic algorithms

Software development organisations are under heavy pressure to complete projects on time, within budget and with the appropriate level of quality, and many questions are asked when a project fails to meet any or all of these requirements. Over the years, much research effort has been spent to find ways to mitigate these failures, the reasons of which come from both within and outside the organisation's control. One possible risk of failure lies in human resource management and, since humans are the main asset of software organisations, getting the right team to do the job is critical. This paper proposes a procedure for software project managers to support their project scheduling and team staffing activities -two areas where human resources directly impact software development projects and management decisions -by adopting a genetic algorithm approach as an optimisation technique to help solve software project scheduling and team staffing problems.

Introduction

A major problem that still exists in the area of software engineering is the high rate of software project failures. According to the 2009 Standish Group CHAOS Report [START_REF] Group | Standish Group CHAOS Report[END_REF], only 32% of software projects are delivered on time, within budget and with the required functionality, whereas 44% are delivered late, over budget and/or with less than the required functionality. The remaining 24% of software projects are cancelled prior to completion or delivered and never used. These figures reveal that project success rates have fallen from the group's previous study and, more alarmingly, that project failures are at the highest they've been in the last decade. Consequently, as more projects continue to fail, questions need to be asked of project management.

Questions such as "Was the team technically skilled to undertake the project?" or "Was it the project manager's fault for under-costing and bad planning?" provide a strong incentive to address the shortcomings of software project management by focusing on two activities that project managers undertake. In particular, project scheduling and team staffing are examined because these activities are closely tied with human resources and since human resources are the only major resource of software development organisations, they are areas that warrant investigation. The paper approaches project scheduling and team staffing as an optimisation problem and employs a genetic algorithm to perform optimisation

The remainder of the paper is organised as follows: section 2 provides an overview of software project scheduling and team staffing activities. Subsequently, section 3 describes in brief how genetic algorithms work and presents how this optimisation technique was designed and adapted to solve the project scheduling and team staffing problem. Section 4 illustrates the experiments carried out on several test projects to evaluate the proposed approach followed by a discussion on the results obtained. Finally, section 5 concludes with a brief summary and notes on future work.

Literature Overview

Software Project Scheduling

One of the main responsibilities of a software project manager is to determine what work will be carried out, how and when it will be done. This responsibility consists of identifying the various products to be delivered, estimating the effort for each task to be undertaken, as well as constructing the project's schedule. Due to the importance of this activity, it should have priority over all others, and furthermore, a project's schedule needs to be updated regularly to coincide with the project's current status. One of the major issues of project scheduling is that of representation [START_REF] Chang | Time-Line Based Model for Software Project Scheduling with Genetic Algorithms[END_REF]. Specifically, the representations that most project scheduling tools provide "cannot model the evolutionary and concurrent nature of software development". One of the most practical challenges project managers face in constructing project schedules is the fact that project scheduling problems are NP-complete. There are no algorithms that can provide an optimal solution in polynomial time, which means that brute force methods are basically inadequate [START_REF] Chang | Genetic Algorithms for Project Management[END_REF][START_REF] Pan | A Study of Project Scheduling Optimization using Tabu Search Algorithm[END_REF]. This problem is heightened due to the fact that software projects are intangible in nature and labour-intensive, and thus involve an even higher level of complexity and uncertainty. As a consequence of the uniqueness of software, project managers cannot completely depend on using experiences from previous projects nor can they use past project information unless used as indicative guidelines. Furthermore, goals may be different with respect to what type of optimisation is required (e.g., minimal cost, maximum resource usage, etc.). Finally, another issue is attributed to the level of information available to construct a project schedule. Similarly to software cost estimation, information available at the start of a project is usually missing or incomplete [START_REF] Chang | Time-Line Based Model for Software Project Scheduling with Genetic Algorithms[END_REF]. Therefore, any mechanism adopted must be able to provide a means to continuously update the schedule [START_REF] Joslin | Agent-based Simulation for Software Project Planning[END_REF].

Software Team Staffing

People and their role in teams are highly important for project success, and they are even taken into account in many cost estimation models, as for instance in the COCOMO model [START_REF] Boehm | Software Engineering Economics[END_REF]. Therefore, employees in software development organisations should be characterised as "human capital", which is considered the most important asset of the company [START_REF] Acuña | A Software Process Model Handbook for Incorporating People's Capabilities[END_REF]. The more effectively this capital is managed, the higher the competitive benefit achieved over other organisations. Therefore, when a company undertakes the development of a new project, another of the main responsibilities of a project manager is to decide who will be working on the project. Team formation therefore is a task that, although seemingly easy at first, requires experience and careful execution. Not getting the right team to do the job could possibly lead to overrunning its schedule, exceeding its budget or compromising the necessary quality.

Recent changes in software development processes have also brought on changes into the way project managers view teamwork and this has lead to new approaches and methods being proposed for enhancing teamwork processes. An example of such attempt can be found in [START_REF] Humphrey | The Team Software Process SM (TSP SM )[END_REF] who provide a Team Software Process (TSP) as an extension of the Personal Software Process (PSP). Another approach is proposed by [START_REF] Tseng | Novel Approach to Multi-Functional Project Team Formation[END_REF] who employ a grey decision-making (fuzzy) approach that selects members based on their characteristics. The Analytical Hierarchy Process (AHP) is another method that can be used for team formation as a decision-making tool as shown in [START_REF] Lin | Modeling Team Member Characteristics for the Formation of a Multifunctional Team in Concurrent Engineering[END_REF], who use multifunctional knowledge ratings and teamwork capability ratings. Recently, [START_REF] Chi | Project Teaming: Knowledge-Intensive Design for Composing Team Members[END_REF] have presented the Web Ontology Language (OWL) -a model that represents semantic knowledge -as a useful technique for team composition.

As stated in [START_REF] Acuña | Emphasizing Human Capabilities in Software Development[END_REF], the most common staffing methods available to software project managers rely heavily on the project manager's personal experiences and knowledge. However, these are highly biased techniques and subjectivity does not always yield the correct or best results. Another issue is the fact that because every project is unique, the application of a specific recruiting and staffing method on a project may not yield the expected results as it was applied on another project because of the differences in project characteristics [START_REF] Wi | A Team Formation Model Based on Knowledge and Collaboration[END_REF]. And this links to the fact that skill-based and experience-based methods are not suitable enough for project managers to deal with interpersonal relationships and social aspects which strongly exist is software development organisations [START_REF] Amrit | Coordination in Software Development: The Problem of Task Allocation[END_REF].

Methodology

Genetic Algorithm Overview

Project scheduling and team staffing may be considered optimisation problems, and as such will require specialised techniques to be solved. Genetic algorithms are one such optimisation technique, with which it is possible to adequately model the mathematical nature of project scheduling and team staffing. Genetic algorithms, introduced by John Holland in 1975 [START_REF] Holland | Adaptation in Natural and Artificial Systems[END_REF], work iteratively with populations of candidate solutions competing as a generation, in order to achieve the individual (or the set of individuals) considered as an optimal solution to a problem. Based on the process of natural evolution, their aim is for fitter individual solutions to prevail over those that are less strong at each generation. To achieve this, the fitness of every individual solution is evaluated using some criteria relative to the problem, and subsequently those evaluated highly are more probable to form the population of the next generation. Promoting healthy, better-off individuals and discarding less suitable, weaker individuals in a given generation is aided by the use of variations of the selection, crossover, and mutation operators, which are responsible for choosing the individuals of the next population and altering them to increase fitness as generations progress -making thus the whole process resemble the concept of 'survival of the fittest'.

Representation and Encoding

For the problem of project scheduling and team staffing, the candidate solutions for optimisation need to represent two pieces of information. On the one hand, schedule constraint information, regarding when and in which order tasks are executed and, on the other hand, skill constraint information, concerning the assignment of employees to tasks based on skill sets and experience required for a task. Fig. 1 below gives an example of the representation of a software project schedule containing 4 tasks and 5 possible employees. As shown, the genetic algorithm uses a mixed-type encoding: schedule information is represented by a positive, non-zero integer symbolising the start day of the task, whereas employee assignment information is represented by a binary code, wherein each bit signifies whether an employee is (a value of 1) or is not (a value of 0) assigned to execute the task. In Fig. 1, the first task starts at day 1 and employee 1 and 3 will execute it, task 2 starts at day 11 with only employee 4 assigned to it, and so on.

Fitness Evaluation Process

The evaluation of the fitness of each individual solution consists of an assessment across the two constraint dimensions that are the focus of this research (i.e., schedule constraints and skill constraints), and for each constraint dimension a corresponding objective function was constructed.

Schedule constraint objective. This objective concerns assessing the degree to which the dependencies of the tasks in the software project are upheld as well as the unnecessary delays existing between dependent tasks. The objective requires a maximisation function and requires information only from the start days of the tasks since it is not affected by which employees are assigned to carry out the task. For each in the project, the fitness is calculated based on Eq. 1. If a task's start day does not satisfy all its predecessor dependencies then it is given a value of zero. Otherwise, the number of idle days between the task and its predecessor task is calculated. The lower the number, the higher the value allocated. In the case where has more than one predecessor tasks, the predecessor task that ends the latest is used for the value .

_ _ 0 _ _ _ 1 1 _ _ _ _ _ _ _ _ 1 max _ avg _ (1)
where .

(

) 2
The values obtained for each task in the project are then averaged over the total number of tasks to give the final evaluation for this objective for the individual.

Skill constraint objective. Employees assigned to work on tasks are evaluated based on the degree of experience they possess in the skills required by the task. The objective function in Eq. 3 shows the formula used to make this evaluation.

Experience in a skill is not considered as cumulative in this maximisation function and therefore is not presented as simply the summation of the skill experience value of all employees assigned. Instead, for each required by a task, it makes use of the highest experience value (i.e., the level of the most experienced employee assigned with

) and adds to that the mean level of experience of all the employees assigned to work on the task requiring .

(

) 3
In this way, the objective function helps assign highly experienced employees to a task and simultaneously prevents the assignment of employees without the skills required (i.e., non-contributors) as the average experience of the team will be lowered. As with the previous objective function, the values obtained for each skill are then averaged over the total number of skills to produce an individual's final skill constraint evaluation.

Conflict objective. The two aforementioned objective functions individually target to realise the shortest project duration or to assign the most experienced employees respectively. However, when used together, there will be cases where conflicts will arise due to assigning one or more employees to work on tasks that have been scheduled to execute simultaneously. For this reason a third objective function was created to handle assignment conflicts by taking into account the number of days each

1 _ _ _
has been assigned to work and how many of these days they have been assigned to more than one permitted task.

(4) Subsequently, the overall fitness for conflicts is computed as the average of all employees. Finally, adding all three evaluations gives an individual's total fitness.

Parameters and Execution

The parameters selected for the genetic algorithm are summarised in Table 1 below. The genetic algorithm is initialised with random individuals and is set to execute for a maximum number of iterations. The population is evaluated using the objective functions described in subsection 3.3. However, it should be noted that each objective value is given a weight so as to allow guidance of the genetic algorithm based on the preference of project managers. For instance, a project manager may want to focus primarily on the construction of a project schedule with the shortest possible duration and secondarily on the experience of employees. In such a case, a higher weight will be assigned to the objective function evaluating the schedule constraint and a lower weight will be assigned to the objective function evaluating the skill constraint. If the most experienced employee is assigned to work on two parallel tasks (i.e., leading to a conflict), then preference will be given to keeping the duration of the project the same but assigning the next most experienced to either one of the tasks. Conversely, if a project manager prefers to have a team that is the most experienced and gives lower priority to project duration then, when a conflict occurs, the project schedule will grow in duration so that the most experienced employee remains assigned to the two tasks. Subsequent to the population evaluation, those individual solutions ranked the highest in terms of fitness will be passed on to the next generation after being transformed using crossover and mutation operators. This is repeated until a suitable solution (or number of suitable solutions) has been found.

Application and Experimental Results

Design of Experiments

Experiments were carried out to validate the approach on several aspects. Foremost, it is essential to examine whether the objective functions used in the optimisation algorithm were sufficient enough to produce the correct results individually but also in their competitive environment. For this purpose, a number of test projects of different sizes were designed and constructed that also allowed investigation of the behaviour of the optimisation algorithm. The two test projects are depicted in the task precedence graph (TPG) in Fig. 2 below, which was used in [START_REF] Chang | Genetic Algorithms for Project Management[END_REF]. The smaller test project comprises a subset of 10 tasks (T1-T10) of the TPG, whereas the larger test project contains all the tasks (T1-T15) in the TPG. All dependencies between tasks are finish-to-start, and the duration and the set of skills required for each task is given inside the respective tasks nodes. In addition, Table 2 provides the degree of experience that employees possess in the skills required by the project's tasks. The genetic algorithm was executed thirty times for each test project in each experiment. The results reported in the following subsections contain examples of some of the best executions that converged or that came very close to converging to the optimal solution in each experiment. For Experiment 1, roughly 60% of the executions resulted in finding the optimal solution (i.e., the project schedule with the shortest makespan), whereas for Experiment 2 all executions obtained the optimal solution (i.e., the project schedule with the most experienced employees assigned). Finally, for Experiment 3, only around 5% of executions converged to the correct solution. It should also be noted here that genetic algorithms are random in nature with respect to initialisation and application of genetic operations. Because this randomness affects convergence, that is,. the number of iterations required to find the optimal solution, the time taken to complete an execution varied. Hence, any figures regarding execution time can only give a very rough indication of the overall behaviour of the genetic algorithm in terms of performance. Execution time ranged between 17 sec and 5 min, depending also on the size of the project.

Results and Discussion

Experiment 1. The first experiment involved executing the genetic algorithm on the test projects to evaluate the objective function for the schedule constraint only. This was done to assess that dependencies between tasks were in fact satisfied and no unnecessary delays existed. An example of the behaviour of the genetic algorithm, one for each test project, can be seen in Fig. 3. For the smaller test project the optimal solution was found around 1000 iterations whereas, as expected, for the larger test project the optimal solution required a higher number of iterations (roughly 3000). Construction of the corresponding optimal project schedules correctly shows that the shortest possible duration for the first test project is 90 days and for the second test project the shortest makespan is 110 days (Fig. 4). Experiment 2. The second experiment examined whether the genetic algorithm was indeed able to find the optimal project team with regards to experience by only evaluating the objective function for the skill constraint. For both test projects, the genetic algorithm successfully managed to assign to each task the most experienced employee or group of employees so that all skills were satisfied and no "idle" or "surplus" employees were used. Table 3 shows an example of a resulting assignment matrix that displays which employees will staff the small software test project.

Table 3. Employee-task assignment matrix (small test project)

T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 E4 0 0 1 0 0 0 0 0 0 1 E6 0 0 0 0 0 0 1 0 0 0 E8 1 1 0 1 1 1 0 0 1 0 E10 1 0 0 1 0 0 0 1 0 0 Experiment 3.
The third and final experiment was carried out to investigate the behaviour of the genetic algorithm when all three objectives were included in the evaluation. Since the objective functions are considered to be competing with each other, each objective function was multiplied by its preference weight as explained in subsection 3.4. Firstly in this series of experiments, greater preference was given to the schedule constraint than to the skill constraint. The results obtained showed that with all three objective functions active, the genetic algorithm was successfully able to find the optimal schedule for both test projects and, in order to avoid conflicts, managed to assign the next best employees in terms of experience to parallel tasks. An example of the assigned employees of the smaller test project is given in Table 4.

1 0 0 1 0 0 0 0 0 0 E4 0 0 1 0 0 0 0 0 0 1 E6 0 0 0 0 1 0 1 0 0 0 E8 0 1 0 0 0 1 0 0 1 0 E10 1 0 0 1 0 0 0 1 0 0
Secondly, a higher preference was given to the skill constraint and a lower preference to the schedule constraint. This was done to examine whether the genetic algorithm was able to keep the most experienced employees assigned by lengthening the project duration. Results obtained here showed that the genetic algorithm found it difficult to reach an optimal solution. Specifically, runs carried out on the test projects show that, as expected, the genetic algorithm draws its attention to the skill constraint objective (as seen in the example in Fig. 5), and thus the project duration is prolonged (Fig. 6). However, a minor dependence violation in one task of the order of 1 day is caused due to the non-multiobjective nature of the algorithm.

Concluding Remarks

This paper presented an approach to solving the problem of software project scheduling and team staffing by adopting a genetic algorithm as an optimisation technique in order to construct a project's optimal schedule and to assign the most experienced employees to tasks. The genetic algorithm uses corresponding objective functions to handle constraints and the results obtained when using either one of the objective functions show that the genetic algorithm is capable of finding optimal solutions for projects of varying sizes. However, when the objective functions were combined, the genetic algorithm presents difficulties in reaching optimal solutions especially when having preference to assign the most experienced employees over the project's duration. Through observation of a number of executions, it was noticed that in this case the genetic algorithm couldn't reduce idle "gaps" or was not able to produce a conflict-free schedule. One possible reason for this observation is due to the competitive nature of the objective functions, and a definite improvement to the approach will be to use multi-objective optimisation rather than using the aggregation of individual objective functions, which is how the genetic algorithm presently works. This could possibly be a means to handle the competitiveness of the objective functions and also allow for a set of optimal solutions to be produced throughout both constraint dimensions simultaneously, thus removing the need for using weights to give preference to either one of the constraints. Also, refinements may be needed to help the algorithm escape from local optima and, thus, improve its convergence rate.

Fig. 1 .

 1 Fig. 1. Example of project schedule representation

Fig. 2 .

 2 Fig. 2. Task precedence graph for test projects

Fig. 3 .

 3 Fig. 3. Evolution of the best individual for the two test projects

Fig. 4 .

 4 Fig. 4. Optimal project schedule for large test project (15 tasks)

Fig. 5 .Fig. 6 .

 56 Fig. 5. Evolution of best individual for small test project (10 tasks)

Table 1 .

 1 Genetic algorithm parameters

	Population size: 100 individuals	Selection method: Roulette wheel
	Maximum number of iterations: 10000	Crossover rate: 0.2 5
		⁄ Mutation rate: 2	_

Table 2 .

 2 Employees' level of experience for the test projects

		S1	S2	S3	S4	S5
	E1	0	0	0.4 0.8	0
	E2 0.2	0	0.4	0	0
	E3	0	0.8	0	0	0
	E4	0	0	0.4 0.8 0.6
	E5	0	0.6	0	0	0
	E6	0	0.6 0.4 0.8	0
	E7	0	0.4 0.4	0	0
	E8	0	0.6 0.6 0.8	0
	E9	0	0.2 0.4	0	0
	E10 0.6 0.4	0	0	0.6

Table 4 .

 4 Employee-task assignment matrix keeping shortest possible project schedule

	T1	T2	T3	T4	T5	T6	T7	T8	T9	T10
	E2


Shahina Ferdous
email: shahina.ferdous@mavs.uta.edu

Sarantos Kapidakis
email: sarantos@ionio.gr

Leonidas Fegaras
email: fegaras@cse.uta.edu

Fillia Makedon
email: makedon@uta.edu

An Adaptable Framework for Integrating and Querying Sensor Data

Keywords: Metadata, Schema Mappings, Query Interface, Digital Libraries, Pervasive Applications, Healthcare

Sensor data generated by pervasive applications are very diverse and are rarely described in standard or established formats. Consequently, one of the greatest challenges in pervasive systems is to integrate heterogeneous repositories of sensor data into a single view. The traditional approach to data integration, where a global schema is designed to incorporate the local schemas, may not be suitable to sensor data due to their highly transient schemas and formats. Furthermore, researchers and professionals in healthcare need to combine relevant data from various data streams and other data sources, and to be able to perform searches over all of these collectively using a single interface or query. Often, users express their search in terms of a small set of predefined fields from a single schema that is the most familiar to them, but they want their search results to include data from other compatible schemas as well. We have designed and implemented a framework for a sensor data repository that gives access to heterogeneous sensor metadata schemas in a uniform way. In our framework, the user specifies a query in an arbitrary schema and specifies the mappings from this schema to all the collections he wants to access. To ease the task of mapping specification, our system remembers metadata mappings previously used and uses them to propose other relevant mapping choices for the unmapped metadata elements. That way, users may build their own metadata mappings based on earlier mappings, each time specifying (or improving) only those components that are different. We have created a repository using data collected from various pervasive applications in a healthcare environment, such as activity monitoring, fall detection, sleeppattern identification, and medication reminder systems, which are currently undergoing at the Heracleia Lab. We have also developed a flexible query interface to retrieve relevant records from the repository that allows users to specify their own choices of mappings and to express conditions to effectively access fine-grained data.

Introduction

Data generated from pervasive applications can be of many different types, such as sensor readings, text, audio, video, medical records, etc. One example of a common pervasive application is the "remote activity monitoring" in an assistive environment. Continuous monitoring of activities is very important in healthcare since it helps caregivers and doctors to monitor a patient remotely and take actions in case of emergency. Such a system may also be very useful for monitoring an elderly person who lives alone in an apartment and needs occasional assistance. A pervasive application deploys various non-invasive sensors as an integral part of a persons' assistive daily living to automatically monitor his activities. It may also deploy a lessintrusive audio and video recording system, based on the needs and privacy requirements of the patient. To be effective, an assistive environment needs to store the data generated from pervasive applications into a common repository and to provide the healthcare providers a flexible and easier access to this repository.

Current advances in sensor technology allow many different sensors that use different technology to be used interchangeably to generate and record similar information about an environment. For example, a person may wear a wireless wrist watch [START_REF]Temperature, Wireless, USB Data Logger or Watch Development Tool[END_REF] as a heart rate monitor, which may also include a 3-axis accelerometer, a pressure and a temperature monitor. On the other hand, a Sunspot sensor [START_REF]Sun SPOT World[END_REF] can be used as an accelerometer and a temperature sensor as well. Although, both devices can be used to generate the same acceleration and temperature data, the format of their representation can be very different. In fact, a sensor can be programmed in many different ways to deliver data in different formats. For example, a sunspot can be programmed to transmit either 3-axis accelerometer data or the angle of acceleration. Therefore, even for a simple sensor device, such as a sunspot, the data storage may contain data in various schemas and configurations. As a result, it is very hard for a caregiver or a doctor to understand and remember each such different schema to query the data repository.

A pervasive application may sometimes refine a sensor reading specific to its settings. For example, sensor devices, such as a smoke/heat detector, only detect and transmit results when the environment reaches a predefined threshold. On the other hand, a stand-alone temperature sensor, such as a sunspot, can be configured to indirectly generate a heat alarm when the temperature exceeds some prespecified heat threshold. Moreover, such thresholds and conditions can change dynamically depending on a user's query requirements, thus making it highly infeasible for a system to cache all possible answers related to a user's query beforehand.

This paper describes a Digital Library that consists of a repository of sensor data collected from various pervasive applications and a flexible query interface for the user that requires minimum knowledge about the real metadata schemas from a user's point of view.

Framework

In this paper, we describe our framework for the sensor data repository, which contains datasets, such as C 11 , C 12 , …, C nm , derived from many different sensors, collected over a long period of time, possibly after years of experiments. We call each such dataset C ij, collected from various applications and contexts, a collection. Each collection is also associated with a metadata schema, which describes the format of that collection. For example, in Fig. 1, the collection C 11 is described by the schema S 1 . A user can query over these different collections by simply using one of his preferred schemas, which we call a virtual schema, S v in our framework. In our framework, given a user-query Q v over the collections of different schemas, the user first provides the needed parts of "Map(S i -> S v )", the mapping for each individual schema S i of a selected collection to the specified virtual schema, S v . Given that the user specifies all such required mappings, the system next applies these mappings to return the final query answers, denoted by Q 1 , Q 2 …Q n . Thus, based on our framework, a user may query on any kind and of any number of collections and obtain fine-grained results without knowing details about the real schemas. In the future, we are planning to use this framework as the building block to obtain the background knowledge for automatic metadata mappings.

Challenges

Sensor records may not of the same format, since they could be generated from different types of sensors installed in various setups, or different versions of similar sensors, with small variations on the record formats. Besides, the values recorded from similar sensors can have different semantics too. The following example shows that even for a simple scenario, such as monitoring "whether a door of an assistive apartment is open or not", the system may require many different mappings to answer a user query.

A pervasive application can use variety of door sensors, which eventually produce door-"open/close" datasets in different formats. For example, the system may use a sensor based on door-mounted magnetic contacts, which denotes that the door is open (1) or closed (0) as an OPEN_STATUS (1/0) attribute, combined with the time of this event as an attribute named TIME_DETECTED. Any accelerometer sensor, such as a sunspot, can also be mounted on the door to obtain similar information. Since, a sunspot can be preprogrammed in different configurations, one configuration may transmit and store Cartesian (x, y, z) coordinates of the door, while the other may compute and transmit the angle of the current position of the door. Such a programmable sunspot may provide both TIME_RECEIVED and TIME_BROADCAST attributes as well.

Fig. 2. Metadata Mapping between similar attributes with different names

A user may not know anything about the schema for the sensor being used to collect such door-data, but he still may ask a query such as "Give me the time when the door was open" over the collection of door datasets. Although answering such a simple query seems trivial, the mappings can be very different and complex. Fig. 2 describes the simplest mapping scenarios, where differently named attributes convey similar information, such as Open and OPEN_STATUS or Time and TIME_RECEIVED from the "Virtual" and the "Magnetic" schemas respectively. However, a metadata field from one schema can be mapped to multiple metadata fields from the other by applying appropriate mapping function. Hence, if a user wants to select such an one-to-many mapping, he needs to specify the correct mapping function as well as to obtain meaningful results. Fig. 3 shows one example scenario, where the field "Open" in the virtual schema is mapped as a function of X_COORD, Y_COORD and Z_COORD fields of the Accelerometer-xyz schema. Fig. 4 shows another scenario, where a user may need to specify a condition even for a one-to-one metadata mapping. As shown in the example, a user may map the field "Open" to the field "Angle". But, since the attribute "Angle" does not directly specify the open status of the door, the user also needs to specify a condition, such as "the door is open, if the angle is greater than at least 4 degrees" and so on.

However, even if the metadata field describing an attribute is the same for two schemas, the associated units of their values can be completely different. For example, the temperature can be described in either Celsius or Fahrenheit, distances can be written either in feet or in meters, time can be a represented in milliseconds or as a general date/time expression. Therefore, in addition to field mappings, the system needs to be able to apply value mappings as well.

Contribution

In this paper, we describe a flexible query interface for searching relevant records from a Digital Library of sensor data. Our interface requires minimum background knowledge and returns results in a format chosen by the user himself. The Library also stores the history of mappings as part of a user profile. Thus, a user can re-use existing mappings to query over the same collections multiple times, thus providing minimal information. However, our system is flexible enough to allow the user to rewrite some existing mappings or to add new conditions to the previously specified mappings. Our system may also suggest existing mappings from other user's profiles, which helps a new user to get some idea about the mapping between schemas. The flexibility of reusing and revising metadata mappings make the framework adaptive to different data management needs and different sensor metadata and formats.

Related Work

There is an increasing need for digital libraries to manage and share the vast variety of scientific data generated from different applications [START_REF] Wallis | Digital libraries for scientific data discovery and reuse: from vision to practical reality[END_REF]. Even when sensor data are stored in clouds or used in grids, they need a mapping handling mechanism, like ours, to interoperate. DSpace@MIT [START_REF]DSpace@MIT[END_REF] is an example repository that supports metadata creation and is built to store, share and search digital materials such as conference papers, images, scholarly articles and technical reports etc. Stanford Digital Library Project (SDLP) [START_REF] Baldonado | The Stanford digital library metadata architecture[END_REF] proposes a metadata infrastructure to achieve interoperability among heterogeneous digital data, thus providing a uniform access to such datasets or collections. SDSC (San Diego Supercomputer Center) Storage Resource Broker (SRB) [START_REF]Storage Resource Broker[END_REF] along with a metadata catalog component, MCAT provides a uniform interface to search over heterogeneous data sources distributed over the network. Although SRB is successful enough to store and query over a federated information system, it is not sufficient to manage and share real time data collected from wireless sensor networks [START_REF] Shankar | Scientific data archiving: the state of the art in information, data, and metadata management[END_REF]. In general, very little work can been found in literature on building digital libraries to store and search the data collected from pervasive applications.

Description of the System

Design

Based on our design, a user may have one of two different roles: He can either contribute or retrieve data to/from the repository. Whenever a user adds a new collection to the repository, he must also specify the metadata schema to describe that collection. Our system stores all such metadata schemas in the repository and stores the link between each collection and its corresponding metadata schema.

Our system provides a suitable query interface for the users who want to search over the repository for relevant data. The query interface consists of a suitable window to browse for different collections and metadata schemas. The user can either select a metadata schema from the list of collections or may use a "virtual" schema, which is not used in any collection. The user may either query over the entire library by selecting all collections or select some specific collections. As soon as the user asks to execute a query, the system first checks the stored metadata mappings to see whether some mappings already exist in the system from the schemas of the selected collections to the preferred virtual schema. Our interface collects and displays all such mappings and asks the user to select any of the following mapping choices:

1. Re-use an existing mapping. 2. Select the mapping used last time, which is the default choice for the preexisting mappings. 3. Specify a new mapping. This is the default option for the mappings that have not been specified yet. Since, initially, the system will not have any stored mappings; our interface will ask the user to enter the mappings first. A user may only provide mappings for the fields that he wants to query at that moment. However, he may enter a new mapping based on similar attribute names or RDF descriptions. He may also define a function to map one schema attribute to the others. 4. Select the recommended mapping from the system. Since our system stores mapping preferences into a user profile, it can identify the most commonly used mappings by different users for a pair of schemas and can recommend such mappings to the user.

Next, as soon as the user specifies his preferred mappings, the system retrieves the resulting records or data from the collections and returns those to the user. The user may either view all such records in a separate output window or browse individual collection manually and only view the results for that particular collection. We have implemented a prototype interface in Java to store and view mappings and collection data from the Library. A screenshot of our interface is shown in Fig. 5. From the interface, the user may express a query using the attributes listed under a particular metadata schema. Executing such a query is straightforward, as it does not require any mapping. However, the user does not need to use any such schema to search over the collections. Instead, the user can select any type and number of collections and can query using a virtual schema. In this case, he may be asked to provide the right pair-wise mapping for each selected dataset of new metadata schema to his preferred virtual schema, before the query could be executed. The user may also specify a mapping condition using the interface and as soon as he saves it, the mappings become part of the user profile. However, whenever he is done with all the mappings, the system executes the query and returns the results to the user.

Implementation

Management of Mappings

In our framework, a mapping, M ij , from schema S i to the schema S j is associated with a set of bindings A jk :f jk (A i1 ,...A in ) that derive the attribute value of A jk in S j from the attributes A i1 ,...A in in S i . The expression f jk may consist of simple arithmetic operations, such as the comparison of an attribute value with a constant threshold, and string manipulation operations, such as string concatenation. These expressions are represented as abstract syntax trees and are stored in a mapping repository along with the rest of the mapping information. When a query is expressed in the schema S i and the mapping M ij is selected to query the data collections that conform to the schema S j , then the query attributes are mapped to the S j attributes using the expression f jk and the derived query is used for querying the data collections that match S j .

Conclusions and Future Work

In this paper, we develop a framework for the repository of heterogeneous sensor data. We also design and implement a prototype for a flexible query interface, which allows the user to search over the collections of different metadata schemas using minimal background knowledge. Our system collects and stores possible mappings from various users incrementally, which could work as a building block to derive commonly accepted mappings. As a future work, we are planning to use our mapping repository as a knowledge base to facilitate automatic metadata mappings.

Fig. 1 .

 1 Fig. 1. Framework to query over the Digital Library

Fig. 3 .

 3 Fig. 3. Metadata Mapping from One-to-Many

Fig. 4 .

 4 Fig. 4. Indirect Metadata Mapping

Fig. 5 .

 5 Fig. 5. A Screenshot of the Query Interface


Vladimír Olej
email: vladimir.olej@upce.cz

Jana Filipová
email: jana.filipova@upce.cz

Modelling of Web Domain Visits by Radial Basis Function Neural Networks and Support Vector Machine Regression

Keywords: Web mining, radial basis function neural networks, -insensitive support vector machine regression, time series, prediction

The paper presents basic notions of web mining, radial basis function (RBF) neural networks and -insensitive support vector machine regression ( -SVR) for the prediction of a time series for the website of the University of Pardubice. The model includes pre-processing time series, design RBF neural networks and -SVR structures, comparison of the results and time series prediction. The predictions concerning short, intermediate and long time series for various ratios of training and testing data. Prediction of web data can be benefit for a web server traffic as a complicated complex system.

Introduction

Data modelling (prediction, classification, optimization) obtained by web mining [START_REF] Cooley | Web Mining: Information and Pattern Discovery on the World Wide Web[END_REF] from the log files and data on a virtual server, as a complicated complex system that affects these data, there are a few problems worked out. The web server represents a complicated complex system; virtual system usually works with several virtual machines that operate over multiple databases. The quality of the activities of the system also affects the data obtained using web mining. Given virtual system is characterized by its operational parameters, which are changing over time, so it is a dynamic system. The data show a nonlinear characteristics, are heterogeneous, inconsistent, missing and uncertain. Currently there are a number of methods for modelling of the data obtained by web mining. These methods can generally be divided into methods of modelling with unsupervised learning [START_REF] Krishnapuram | A Fuzzy Relative of the K-medoids Algorithm with Application to Document and Snippet Clustering[END_REF][START_REF] Pedrycz | Conditional Fuzzy C-means[END_REF] and supervised learning [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF]. The present work builds on the modelling of web domains visit with uncertainty [START_REF] Olej | Modelling of Web Domain Visits by IF-Inference System[END_REF][START_REF] Olej | Time Series Prediction of Web Domain Visits by IF-Inference System[END_REF].

In the paper is presented a problem formulation with the aim of describing the time series web upce.cz (web presentation visits), including possibilities of pre-processing which is realized by means of simple mathematic-statistic methods. Next, there are introduced basic notions of RBFs [START_REF] Broomhead | Multivariate Functional Interpolation and Adaptive Networks[END_REF] neural networks and -SVRs [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF][START_REF] Cristianini | An Introduction to Support Vector Machines and other Kernel-based Learning Methods[END_REF] for time series prediction. Further, the paper includes a comparison of the prediction results of the model designed. The model represents a time series prediction for web upce.cz with the pre-processing done by simple mathematical statistical methods. The prediction is carried out through RBF neural networks and -SVRs for different durations of time series and various ratios O train :O test training O train and testing O test dates (O= O train O test ). There is expected, that for shorter time series prediction it would be better to use RBF neural networks and for longer -SVRs.

Problem Formulation

The data for prediction of the time series web upce.cz over a given time period was obtained from Google Analytics. This web mining tool, which makes use of Java-Script code implemented for web presentation, offers a wide spectrum of operation characteristics (web metrics). Metrics provided by Google Analytics can be divided into following sections: visits, sources of access, contents and conversion. In the section 'visits' it can be monitored for example the number of visitors, the number of visits and number of pages viewed as well as the ratio of new and returning visitors. Indicator geolocation, i.e. from which country are visitors most often, is needed to be known because of language mutations, for example. In order to predict the visit rate to the University of Pardubice, Czech Republic website (web upce.cz) it is important monitoring the indicator of the number of visits within a given time period. One 'visit' here is defined as an unrepeated combination of IP address and cookies. A submetrics is absolutely unique visit defined by an unrepeatable IP address and cookies within given time period. The basic information obtained from Google Analytics about web upce.cz during May 2009 considered of the following: The total visit rate during given monthly cycles. A clear trend is obvious there, with Monday having the highest visit rate, which in turn decreases as the week progresses; Saturday has the lowest visit rate; The average number of pages visited is more than three; A visitor stays on certain page five and half a minutes on average; The bounce rate is approximately 60%; Visitors generally come directly to the website, which is positive; The favourite pages is the main page, followed by the pages of the Faculty of Economic and Administration and the Faculty of Philosophy.

The measurement of the visit rate of the University of Pardubice web page, (web upce.cz) took place time periods of regular, controlled intervals. The result represents a time series. The pre-processing of data was realized by means of simple mathematic-statistic methods: a simple moving average (SMA), a central moving average (CMA), a moving median (MM) along with simple exponential smoothing (SES) and double exponential smoothing (DES) at time t. Pre-processing was used with aim of smoothing the outliers, while maintaining the physical interpretation of data.

The general formulation of the model of prediction of the visit rate for upce.cz can be stated in thusly: y´=f(x t 1 ,x t 2 , … ,x t m ), m=5, where y´ is the number of daily web visits in time t+1, y is the number of daily web visits in time t, x t 1 is SMA, x t 2 is CMA, x t 3 is MM, x t 4 is SES, and x t 5 is DES at time t. An example of the preprocessing of the time series of web upce.cz is represented in Fig. 1.

where TS -time series, S -short TS (264 days), I -intermediate TS (480 days), Llong TS (752 days) at time t.

Basic Notions of RBF Neural Networks and -SVR

The term RBF neural network [START_REF] Broomhead | Multivariate Functional Interpolation and Adaptive Networks[END_REF] refers to any kind of feed-forward neural networks that uses RBF as an activation function. RBF neural networks are based on supervised learning. The output f(x,H,w) RBF of a neural network can be defined this way

q 1 i i i h w H f ) ( ) ( x w x , , , (2)
where H={h 1 (x),h 2 (x), … ,h i (x), … ,h q (x)} is a set of activation functions RBF of neurons (of RBF functions) in the hidden layer and w i are synapse weights. Each of the m components of vector x=(x 1 ,x 2 , … ,x k , … ,x m ) is an input value for the q activation functions h i (x) of RBF neurons. The output f(x,H,w) of RBF neural network represents a linear combination of outputs from q RBF neurons and corresponding synapse weights w.

The activation function h i (x) of an RBF neural network in the hidden layer belongs to a special class of mathematical functions whose main characteristic is a monotonous rising or falling at an increasing distance from center c i of the activation function h i (x) of an RBF. Neurons in the hidden layer can use one of several activation functions h i (x) of an RBF neural network, for example a Gaussian activation function (a one-dimensional activation function of RBF), a rotary Gaussian activation function (a two-dimensional RBF activation function), multisquare and inverse multisquare activation functions or Cauchy's functions. Results may be presented in this manner

h(x,C,R)= ) ( 2 || || exp i i r c q 1 i x , (3)
where x=(x 1 ,x 2 , … ,x k , … ,x m ) represents the input vector, C={c 1 ,c 2 , … ,c i , … ,c q } are centres of activation functions h i (x) an RBF neural network and R={r 1 ,r 2 , … ,r i , … ,r q } are the radiuses of activation functions h i (x).

The neurons in the output layer represent only a weighted sum of all inputs coming from the hidden layer. An activation function of neurons in the output layer can be linear, with the unit of the output eventually being convert by jump instruction to binary form. The RBF neural network learning process requires a number of centres c i of activation function h i (x) of the RBF neural networks to be set as well as for the most suitable positions for RBF centres c i to be found. Other parameters are radiuses of centres c i , rate of activation functions h i (x) of RBFs and synapse weights W(q,n). These are setup between the hidden and output layers. The design of an appropriate number of RBF neurons in the hidden layer is presented in [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF]. Possibilities of centres recognition c i are mentioned in [START_REF] Broomhead | Multivariate Functional Interpolation and Adaptive Networks[END_REF] as a random choice. The position of the neurons is chosen randomly from a set of training data. This approach presumes that randomly picked centres c i will sufficiently represent data entering the RBF neural network. This method is suitable only for small sets of input data. Use on larger sets, often results in a quick and needless increase in the number of RBF neurons in the hidden layer, and therefore an unjustified complexity of the neural network. The second approach to locating centres c i of activation functions h i (x) of RBF neurons can be realized by a K-means algorithm.

In nonlinear regression -SVR [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF][START_REF] Cristianini | An Introduction to Support Vector Machines and other Kernel-based Learning Methods[END_REF][START_REF] Smola | A Tutorial on Support Vector Regression[END_REF][START_REF] Niyogi | On the Relationship between Generalization Error, Hypothesis Complexity, and Sample Complexity for Radial Basis Functions[END_REF][START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF] minimizes the loss function L(d,y) with insensitive [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF][START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF]. Loss function L(d,y)= d-y where d is the desired response and y is the output estimate. The construction of the -SVR for approximating the desired response d can be used for the extension of loss function L(d,y) as follows

y d y d L 0 ) , ( else
- for y d , (4)
where is a parameter. Loss function L (d,y) is called a loss function with insensitive .

Let the nonlinear regression model in which the dependence of the scalar d vector x expressed by d=f(x) + n. Additive noise n is statistically independent of the input vector x. The function f(.), and noise statistics are unknown. Next, let the sample training data (x i ,d i ), i=1,2, ... ,N, where x i and d i is the corresponding value of the output model d. The problem is to obtain an estimate of d, depending on x. For further progress is expected to estimate d, called y, which is widespread in the set of nonlinear basis functions j x), j=0,1, ... ,m 1 this way

) ( ) ( x w x w y T m 0 j j j 1 , (5)
where (x)=[ (x), (x), … , m

i i N 1 i emp y d L N R , (6)
under conditions of inequality w c 0 , where c 0 is a constant. The restricted optimization problem can be rephrased using two complementary sets of non-negative variables. Additional variables and ´ describe loss function L (d,y) with insensitivity . The restricted optimization problem can be written as an equivalent to minimizing the cost functional

w w C w T N 1 i ' i i 2 1 ) ( ) , , ( ) ( ' , (7)
under the constraints of two complementary sets of non-negative variables and ´.

The constant C is a user-specified parameter. Optimization problem ( 7) can be easily solved in the dual form. The basic idea behind the formulation of the dual-shaped structure is the Lagrangian function [START_REF] Smola | A Tutorial on Support Vector Regression[END_REF], the objective function and restrictions. Can then be defined Lagrange multipliers with their functions and parameters which ensure optimality of these multipliers. Optimization the Lagrangian function only describes the original regression problem. To formulate the corresponding dual problem a convex function can be obtained (for shorthand)

N 1 i N 1 i ' i i ' i i i ' i i d Q ) ( ) ( ) , ( N 1 i N 1 j j i ' j j ' i i x , x K ) ( ) )( ( 2 1 , (8)
where K(x i ,x j ) is kernel function defined in accordance with Mercer's theorem [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF][START_REF] Cristianini | An Introduction to Support Vector Machines and other Kernel-based Learning Methods[END_REF].

Solving optimization problem is obtained by maximizing Q( ´) with respect to Lagrange multipliers and ´ and provided a new set of constraints, which hereby incorporated constant C contained in the function definition (w, ´). Data points covered by the

´, define support vectors [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF][START_REF] Cristianini | An Introduction to Support Vector Machines and other Kernel-based Learning Methods[END_REF][START_REF] Smola | A Tutorial on Support Vector Regression[END_REF].

Modelling and Analysis of the Results

The designed model in Fig. 2 The dependencies RMSE on the parameter C are represented in Fig. 6, the dependencies RMSE on the parameter in Fig. 7, the dependencies RMSE on the parameter in Fig. 8 The confirmation of conclusions presented in [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF][START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF] is verified by the analysis of results. RMSE test for the -SVR with RBF kernel function lowers toward zero value with decreasing C (in the case the user experimentation) and higher ratio of O train :O test . In the use of 10-fold cross validation, RMSE test moves towards zero with an increase of parameter for O train_S . In the -SVR with polynomial kernel function RMSE test significantly decreases when the parameter decreases (Fig. 7). Minimum RMSE test moves rights with an increase of the parameter (the minimum is between 0.2 to 0.3), whereas an indirect correlation between the ratio O train :O test and RMSE test obtains.

In Table 4 and Table 5 The original value of TS S (O test ) y compared with predicted values of y´ (in which time is t+ t, t=1 day) using RBF neural network is displayed in Fig. 9. In Fig. 10 TS S (O test ) y is then compared to predicted values y´ using the -SVR (with RBF kernel function). In Table 6, there is a comparison of the RMSE train and RMSE test on the training and testing set to other designed and analyzed structures. For example, it was used a fuzzy inference system (FIS) Takagi-Sugeno [START_REF] Olej | Modelling of Web Domain Visits by IF-Inference System[END_REF][START_REF] Olej | Time Series Prediction of Web Domain Visits by IF-Inference System[END_REF], intuitionistic fuzzy inference system (IFIS) Takagi-Sugeno [START_REF] Olej | Modelling of Web Domain Visits by IF-Inference System[END_REF][START_REF] Olej | Time Series Prediction of Web Domain Visits by IF-Inference System[END_REF], feed-forward neural networks (FFNNs), RBF neural networks and -SVR 1 ( -SVR 2 ) with RBF (polynomial kernel function) with preprocessing input data by simple mathematical statistical methods. [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF][START_REF] Niyogi | On the Relationship between Generalization Error, Hypothesis Complexity, and Sample Complexity for Radial Basis Functions[END_REF][START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF] for TS I (TS S ). Further direction of research in the area of modelling web domain visits (excluding the use of uncertainty [START_REF] Olej | Modelling of Web Domain Visits by IF-Inference System[END_REF][START_REF] Olej | Time Series Prediction of Web Domain Visits by IF-Inference System[END_REF] and modelling using RBF neural networks and machine learning using -SVR) is focused on different structures of neural networks. The crux of modelling are different lengths of time series, various ratios of O train :O test and different techniques of their partitioning. Prediction using web mining gives better characterization of webspace. On the basis of that system engineers can better characterize the load of complex virtual system and its dynamics. The RBF neural networks ( -SVR) design was carried out in SPSS Clementine (STATISTICA).

Fig. 1 .

 1 Fig. 1. The pre-processing of web upce.cz visits by SMA On the basis of the different durational time series of web upce.cz, concrete prediction models for the visit rate to upce.cz web can be defined thusly y´=f(TS S SMA ,TS S CMA ,TS S MM ,TS S SES ,TS S DES ), y´=f(TS I SMA ,TS I CMA ,TS I MM ,TS I SES ,TS I DES ), y´=f(TS L SMA ,TS L CMA ,TS L MM ,TS L SES ,TS L DES ),

1 (

 1 x)] T and w=[w 0 ,w 1 , ... ,w m 1 ]. It is assumed that (x)=1 in order to the weight w 0 represents bias b. The solution to the problem is to minimize the empirical risk ) , ( 1

Fig. 2 .

 2 Prediction modelling of time series for web.upce.cz In Fig. 3 are shown the dependencies of Root Mean Squared Error (RMSE) on the number of neurons q in the hidden layer. The dependencies RMSE on the parameter are represented in Fig. 4. In Fig. 5 the dependencies RMSE are on the parameter for training O train and as well as the testing O test set, where:  -O train_S ,  -O train_I ,  -O train_L , × -O test_S, -O test_I,  -O test_L . The parameter allows for an overrun of the local extreme in the learning process and the following progress of learning. The parameter represent the selection of centers RBFs as well as guarantees the correct allocation of neurons in the hidden layer for the given data entering the RBF neural network.

Fig. 3 .Fig. 4 .

 34 Fig. 3. RMSE dependencies on the parameter q

  for training O train as well as testing O test set, where:  -O train_S ,  -O train_I ,  -O train_L , × -O test_S, -O test_I,  -O test_L . The parameters C, are functions of kernel functions k(x,x i ) [4,11] variations. In the learning process -SVR are set using 10-fold cross validation. Parameter C controls the trade off between errors of the -SVR of training data and margin maximization; [4] selects support vectors in the regression structures, and represents the rate of polynomial kernel function k(x,x i ). The coefficient characterizes polynomial and RBF kernel function.

Fig. 6 .Fig. 7 .

 67 Fig. 6. RMSE dependencies on the parameter C

  are shown the optimized results of the analysis of the experiments for different parameters of the -SVR (with RBF and a polynomial kernel function) with different durations of time series, various ratios O train :O tes training O train and testing O test of data sets and same amount of learning at p=600 cycles. The tables are not represented by the partial results for the various parameters, but only the resulting set of parameters for the TS and the ratio O train :O test .

Fig. 9 .

 9 Fig. 9. TS S with values predicated by RBF Fig. 10. TS S with values predicated by SVR

  demonstrates prediction modelling of the time series web upce.cz. Data pre-processing is carried out by means of data standardization. Thereby, the dependency on units is eliminated. Then the data are pre-processed through simple mathematical statistical methods (SMA,CMA,MM,SES, and DES).

	y
	y´=f(x t	1 ,x t	2 , … ,x t	m ), m=5
	Data pre-processing makes the suitable physical interpretation of results possible. The
	pre-processing is run for time series of different duration namely (TS S SMA , TS S CMA ,TS S MM ,TS S SES ,TS S DES ),(TS I SMA ,TS I CMA ,TS I MM ,TS I SES ,TS I DES ),(TS L SMA ,TS L CMA , TS L MM ,TS L SES ,TS L DES ). The prediction is made for the aforementioned pre-processed
	time series S, I, and L with the help of RBF neural networks, -SVR with a
	polynomial kernel function and -SVR with a RBF kernel function for various sets of
	training O train and testing O test data.

Table 1 .

 1 test decreases only when the number q RBF neurons increases at a significantly slower ratio than the ratio O train :O test . Minimum RMSE test moves right with the increasing ratio O train :O test . Next, determination of the optimal number of q neurons in the hidden layer is necessary. Respectively, a lower number q neurons represents the increasing RMSE test . In Table 1, Table 2, and Table 3 are shown optimized results of the analysis of the experiments for different parameters of the RBF neural networks (with RBF activation function) with different durations of time series, various ratios of O train :O test training O train and testing O test of data sets and same amount of learning at p=600 cycles. Table 2 builds on the best set of q in Table1 and Table 3 builds on the best set of q (Table1) and (Table2). Optimized results of RMSE analysis using the amount of neurons q in the hidden layer

		Data
		standardization
		Data pre-processing by
		SMA,CMA,MM,SES,DES
	Modelling by RBF neural	Modelling by -SVR with	Modelling by -SVR with
	networks	RBF kernel function	polynomial kernel function
		Comparison of the results
		and prediction

RMSE

Table 2 .

 2 Optimized results of RMSE analysis using parameter q and are constant for given TS)

	TS	O train :O test	Number q of neurons			RMSE train	RMSE test
	S	50:50	80	0.5	1	0.473	0.385
	S	66:34	80	0.5	1	0.341	0.445
	S	80:20	80	0.5	1	0.311	0.408
	I	50:50	125	0.3	1	0.313	0.344
	I	66:34	125	0.3	1	0.302	0.428
	I	80:20	125	0.3	1	0.343	0.365
	L	50:50	25	0.3	1	0.400	0.387
	L	66:34	25	0.3	1	0.398	0.409
	L	80:20	25	0.3	1	0.406	0.391

Table 3 .

 3 Optimized results of RMSE analysis using parameter q and are constant for given TS)

	TS	O train :O test	Number q of neurons			RMSE train	RMSE test
	S	50:50	80	0.5	1	0.385	0.473
	S	66:34	80	0.5	1	0.341	0.445
	S	80:20	80	0.5	1	0.311	0.408
	I	50:50	125	0.3	3	0.357	0.375
	I	66:34	125	0.3	3	0.327	0.405
	I	80:20	125	0.3	3	0.376	0.441
	L	50:50	25	0.3	1	0.400	0.387
	L	66:34	25	0.3	1	0.398	0.409
	L	80:20	25	0.3	1	0.406	0.391

Table 4 .

 4 Optimized results of RMSE analysis using parameter C

	TS	O train :O test	C			RMSE train	RMSE test
	S	50:50	8	0.2	0.4	0.343	0.414
	S	66:34	10	0.1	0.4	0.365	0.314
	S	80:20	10	0.1	0.4	0.355	0.306
	I	50:50	10	0.1	0.4	0.331	0.369
	I	66:34	10	0.1	0.4	0.342	0.361
	I	80:20	9	0.1	0.4	0.350	0.336
	L	50:50	6	0.1	0.2	0.382	0.409
	L	66:34	4	0.1	0.2	0.383	0.416
	L	80:20	4	0.1	0.2	0.384	0.445

Table 5 .

 5 Optimized results of RMSE analysis using parameters and

	TS	O train :O test	C				RMSE train	RMSE test
	S	50:50	10	0.1	0.2	1	0.411	0.319
	S	66:34	10	0.2	0.2	2	0.474	0.379
	S	80:20	10	0.1	0.2	3	0.587	0.509
	I	50:50	6	0.1	0.3	1	0.385	0.416
	I	66:34	10	0.1	0.3	2	0.436	0.486
	I	80:20	6	0.1	0.3	3	0.526	0.567
	L	50:50	10	0.1	0.2	2	0.455	0.468
	L	66:34	6	0.1	0.2	1	0.385	0.416
	L	80:20	8	0.1	0.2	1	0.385	0.443

Table 6 .

 6 Comparison of the RMSE train and RMSE test on the training and testing data to other designed and analyzed structures of fuzzy inference systems and neural networksThe proposed model consists of data pre-processing and actual prediction using RBF neural networks as well as -SVR with polynomial and RBF kernel functions. Furthermore, the modelling was done for time series of different lengths and different parameters of neural networks. The analysis results for various ratios of O train :O test show trends for RMSE train and RMSE test . From the analysis of all obtained results of modelling time series by RBF neural network ( -SVR) shows that RMSE test takes minimum values

		FIS	IFIS	FFNN	RBF	-SVR 1	-SVR 2
	RMSE train	0.221	0.224	0.593	0.311	0.331	0.385
	RMSE test	0.237	0.239	0.687	0.408	0.369	0.416

Acknowledgments.

This work was supported by the scientific research project of Ministry of Environment, the Czech Republic under Grant No: SP/4i2/60/07.


Dubravko Ćulibrk
email: dculibrk@uns.ac.rs

Predrag Lugonja
email: lugonja@uns.ac.rs

Vladan Minić
email: minic@uns.ac.rs

Vladimir Crnojević
email: crnojevic@uns.ac.rs

Neural Network Approach to Water-Stressed Crops Detection Using Multispectral WorldView-2 Satellite Imagery

Keywords: Water stress, Agriculture, Satellite imagery, Neural networks, Waterlogged farmland, Remote sensing

The paper presents a method for automatic detection and monitoring of small waterlogged areas in farmland, using multispectral satellite images and neural network classifiers. In the waterlogged areas, excess water significantly damages or completely destroys the plants, thus reducing the average crop yield. Automatic detection of (waterlogged) crops damaged by rising underground water is an important tool for government agencies dealing with yield assessment and disaster control. The paper describes the application of two different neural network algorithms to the problem of identifying crops that have been affected by rising underground water levels in WorldView-2 satellite imagery. A satellite image of central European region (North Serbia), taken in May 2010, with spatial resolution of 0.5m and 8 spectral bands was used to train the classifiers and test their performance when it comes to identifying the water-stressed crops. WorldView-2 provides 4 new bands potentially useful in agricultural applications: coastal-blue, red-edge, yellow and near-infrared 2. The results presented show that a Multilayer Perceptron is able to identify the damaged crops with 99.4% accuracy. Surpassing previously published methods.

Introduction

The advances in the satellite imaging technology provide researchers and practitioners with ever more data that needs to be processed to extract meaningful and useful information.

In agriculture, the applications of satellite imagery typically deal with crop monitoring [START_REF] Yang | Evaluating high resolution SPOT 5 satellite imagery for crop identification[END_REF][5] [START_REF] Ryerson | Timely crop area estimates from Landsat[END_REF][15] [START_REF] Castillejo-González | Object-and pixelbased analysis for mapping crops and their agro-environmental associated measures using QuickBird imagery[END_REF]. A general goal is to be able to predict the yield of specific crops and monitor their health. Such information can be used directly by government agencies to ensure that the subsidies given to farmers are allocated correctly and that they are compensated for damage occurring in their fields.

While satellite imagery for crop monitoring is a practice with more than 30 years of tradition [START_REF] Hanuschak | Obtaining timely crop area estimates using ground-gathered and LANDSAT data[END_REF] [START_REF] Ryerson | Timely crop area estimates from Landsat[END_REF], the sensors have only recently gained resolution that allows for precision monitoring in the case of agriculture practices based on small land parcels [START_REF] Pan | Using QuickBird imagery and a production efficiency model to improve crop yield estimation in the semi-arid hilly Loess Plateau, China[END_REF][2] [START_REF] Helmholz | Automatic qualtiy control of cropland and grasland GIS objects using IKONOS Satellite Imagery[END_REF] [START_REF] Yang | Evaluating high resolution SPOT 5 satellite imagery for crop identification[END_REF].

In the work presented here we address the problem of detecting small wetland areas in the farmland. Particularly, we are interested to detect these areas in the plains of Northern Serbia (Central Europe), where the small areas of wetland appear in the arable land as the consequence of the rise of a groundwater. This phenomenon emerges usually after the period of heavy rains, affects small mutually isolated areas, and disappears in a couple of weeks. Although temporary, it influences crop yields significantly and therefore it is necessary to discover it in order to perform damage assessment. In addition, farmers in Serbia are entitled to compensation if more than 30% of their crop is affected. Since crops are still present in the wetland areas, their stress due to excess water can be used to detect the stretches of waterlogged area within arable land. In addition, the presence of the crops in the water occludes the water surface, rendering the methods which wold rely on reflection from water inapplicable.

High-resolution 8-band images, provided by the remote sensing equipment mounted on the recently launched WorldView-2 satellite are used to detect crops damaged by excess water. Besides the standard red, green, blue and near-infra red band, WorldView-2 it offers new bands: costal blue, yellow, red-edge and an additional near-infra red band [START_REF] Marchisio | On the relative predictive value of the new spectral bands in the WorldWiew-2 sensor[END_REF]. The new channels carry significant information one one is concerned with watelogged areas detection [START_REF] Petrovic | Detection of Wet Areas in Multispectral Images of Farmland[END_REF]. In addition, multispectral images are available in high spatial resolution of 50 cm, making them suitable for applications in areas with small-land-parcel-based agriculture.

Human-annotated ground truth was used to train 2 types of neural network classifiers to distinguish between pixels pertinent to waterlogged land and other pixels: Multi Layer Perceptron (MLP) and Radial Basis Function (RBF) neural nets. The experimental results presented show that the MLP approach achieves superior performance both in terms of accuracy and detection speed, when compared to previously published results [START_REF] Petrovic | Detection of Wet Areas in Multispectral Images of Farmland[END_REF]. RBF however, proved unsuitable for the task at hand, since it achieves accuracy below the simplest (logistic regression) classifier.

The rest of the paper is organized as follows: Section 2 provides an overview of the relevant published work. Section 3 provides the details of our approach. Section 4 describes the experiments conducted and the results achieved. Finally, Section 5 provides our conclusions.

Related work

The problem of waterlogged areas detection falls into the scope of land-cover classification. Lu and Weng [START_REF] Lu | A survey of image classification methods and techniques for improving classification performance[END_REF] provide a comprehensive and fairly recent survey of the different approaches used to distinguish between different types of cover. Within their taxonomy the proposed approach is supervised, non-parametric, per-pixel, spectral and makes hard decisions. This means that we use ground truth data created by human experts to train the classifier, make no assumptions about the data itself, consider single pixels with no notion of spatial dependencies and derive unambiguous classification decisions.

As far as precision agriculture applications are concerned, using satellite imagery for crop identification and crop-covered area estimation is a practice with more than 30 years of tradition [START_REF] Hanuschak | Obtaining timely crop area estimates using ground-gathered and LANDSAT data[END_REF] [START_REF] Ryerson | Timely crop area estimates from Landsat[END_REF]. Initially low-resolution Landsat MSS and TM data was used [5][19][21] [START_REF] Oetter | Land cover mapping in an agricultural setting using multiseasonal Thematic Mapper data[END_REF]. As new satellites became available SPOT imagery [START_REF] Murakami | Crop discrimination with multitemporal SPOT/HRV data in the Saga Plains, Japan[END_REF][1], Indian Remote Sensing (IRS) satellite data [START_REF] Dutta | Accuracy assessment in cotton acreage estimation using Indian remote sensing satellite data[END_REF][16] and moderate-resolution Moderate Resolution Imaging Spectroradiometer (MODIS) [START_REF] Lobell | Cropland distributions from temporal unmixing of MODIS data[END_REF][20] data has been used. More recently several studies have looked at using high-resolution satellite imagery from QuickBird [START_REF] Pan | Using QuickBird imagery and a production efficiency model to improve crop yield estimation in the semi-arid hilly Loess Plateau, China[END_REF][2], IKONOS [START_REF] Helmholz | Automatic qualtiy control of cropland and grasland GIS objects using IKONOS Satellite Imagery[END_REF] and SPOT 5 [START_REF] Yang | Evaluating high resolution SPOT 5 satellite imagery for crop identification[END_REF].

Using neural networks for classification of multispectral image pixels was considered as early as 1992 [START_REF] Heermann | Classification of multispectral remote sensing data using a back-propagation neural network[END_REF]. At the time, the authors of the study were concerned with the feasibility of training the network classifying the pixels of a satellite image in reasonable time, using the hardware available. The considered a single hidden layer feed-forward neural network trained and proposed an adaptive back-propagation algorithm, which reduced the training time from 3 weeks to 3 days, for a network with 24, 24 and 5 nodes in the input, hidden and output layer. At the time, a single input neuron was used for each bit in the RGB pixel value of a Landsat image. The authors concluded that the neural network is able to generalize well across different images, both real and synthetic. Since this early work there have been numerous applications of neural networks to classification of remotely sensed data. Mas and Flores provide an overview [START_REF] Mas | The application of artificial neural networks to the analysis of remotely sensed data[END_REF].

A recent study by Marchisio et al. [START_REF] Marchisio | On the relative predictive value of the new spectral bands in the WorldWiew-2 sensor[END_REF] evaluated the capability of new WorldView-2 data, when it comes to general land-cover classification. They considered the relative predictive value of the new spectral bands in the WorldWiew-2 sensor. Four types of classifiers were employed: logistic regression, decision trees, random forest and neural network classifiers. The study showed that new bands lead to an improvement of 5-20% in classification accuracy on 6 different scenes. In addition, the authors proposed an approach to evaluate the relative contribution of each spectral band to the learned models and, thus, provide a list of bands important for the identification of each specific land cover class. Although the neural network classifiers used by Marchisio et al. [START_REF] Marchisio | On the relative predictive value of the new spectral bands in the WorldWiew-2 sensor[END_REF] have not been described in detail, they state that they used a topology with two hidden layers, containing 10 -20 neurons. The neural network used was most likely a Multilayer Perceptron trained by back propagation.

Our work builds up on the study of Petrovic et al. [START_REF] Petrovic | Detection of Wet Areas in Multispectral Images of Farmland[END_REF]. The authors used WorldView-2 data to address the problem of water-logged agricultural land detection. They evaluated logistic regression, Support Vector Machines (SVMs) and Genetic Programming (GP) classifiers. SVMs and GP achieved best classification results when cross validated (98,80% and 98,87% accurate respectively). The GP solution was deemed the best by the authors, since it was able to achieve best classification and do it significantly faster than the SVM classifier that contained 6000 support vectors. Neural network classifiers were not considered in that study, and to the best of our knowledge were never applied to the problem of waterlogged area detection nor the problem of plant water-stress detection.

Detecting Waterlogged Crops Using WorldView-2 Data

WorldView-2 Data

The data used in this work is provided by commercial satellite WorldView-2. The image was made during July 2010 and covers the area of arable land from in the northern part of Serbia. Figure 1 shows visible light components of a part of the scene. The discolored irregular shaped blotches within the arable land correspond to waterlogged parts.

WorldView-2 is the first commercial satellite which provides eight highresolution spectral bands. Its sensors are sensitive to visible and near-infrared spectral bands and producce images of 50 cm resolution. This satellite detects radiation in following spectral bands: red (630-690 nm), green (510-580 nm), blue (450-510 nm), near-infrared 1 (NIR1 -770-895 nm), coastal blue (400-450 nm), yellow (585-625 nm), red-edge (705-745 nm) and near-infrared 2 (NIR2 -860-1040 nm). The last four components provide additional value when compared to the data available from other commercial satellites and each of them has been designed with specific applications in mind. The costal blue is least absorbed by water, but it is absorbed by chlorophyll in healthy plants. NIR2 component to some extent resembles the characteristics of NIR1 component, initially aimed at vegetation detection and classification tasks, but is less influenced by atmospheric interference. Red-edge is especially designed for maximal reflection from vegetation and is intended for the measurement of plant health and classification of vegetation [START_REF] Digitalglobe | The Benefits of the 8 Spectral Bands of WorldView-2[END_REF].

The data set used for training and testing of classifiers was derived based on ground truth, manually annotated on a part of a single satellite image covering an area of 10km 2 . It contains environ 200,000 data samples, corresponding to the values of 8 bands for both waterlogged and non-waterlogged pixels, selected out some 25,000,000 pixels in the single scene. The values for each of the 8 bands are 16 bits wide. All values were normalized in our experiments.

Neural Network Classification

Two types of feed forward neural networks were considered for the classification of multispectral pixel values: Multilayer Perceptron (MLP) [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF] and Radial Basis Function (RBF) [START_REF] Park | Universal approximation using radial-basis-function networks[END_REF].

Both architectures represent feed-forward networks the signals are propagated from the input to output neurons, with no backward connections. The MLP contained a single hidden layer and was trained using a back-propagation algorithms as detailed in [START_REF] Witten | Data Mining: Practical machine learning tools and techniques, 2nd Edition[END_REF].

The parameters of the RBF network used were determined using k-means clustering. Both MLP and RBF implementation is available within the opensource data mining and artificial intelligence suite Wakaito Environment for Knowledge Discovery (WEKA) [START_REF] Witten | Data Mining: Practical machine learning tools and techniques, 2nd Edition[END_REF]. This is the suite that has been used to conduct experiments detailed in Section 4.

Once the neural networks are trained they are used to classify each pixel in the image separately.

Experiments and Results

To evaluate the performance of the two neural network models 10-fold cross validation was used. The process involves holding out 10 percent of data in the training data set and using the rest to train the classifier. The 10% is used to test the model. The process is repeated 10 times and average performance measures are reported for each type of classifier.

The MLP contained 100 neurons in a single hidden layer, learning rate was set to 0.3, momentum to 0.2 and 500 training epochs were used. The time taken to build the model on an Intel Core2Duo processor running at 2.93 GHz was 6251 seconds. Table 1 provides the performance statistics for the MLP model: true-positive (TP) rate, false-positive (FP) rate, precision, recall, f-measure and Response Operating Characteristic (ROC) Area. The accuracy achieved by the MLP is 99.4043%.

The RBF model was built much faster. It took only 43.69 seconds to train the network. Minimum standard deviation for the clusters was set to 0.1, while 1. The parts of the scene classified as waterlogged are indicated by white pixels. Since the waterlogged areas represent a relatively small part of the overall area, the classification result shown in two images differs significantly, although the difference in accuracy between two methods is just 5%.

When compared to the results of other classifiers as reported in [START_REF] Petrovic | Detection of Wet Areas in Multispectral Images of Farmland[END_REF], the MLP achieved results superior to any of the classifiers reported there. The best classifier reported in the previous study was achieved by Genetic Programming and its accuracy was 98.87% on the same data set. Unfortunately the RBF classifier performed worse even than the simple logistic regression, which achieved 97.58% accuracy, as reported previously. This can only be attributed to the errors in the k-means clustering used to position the kernels of the RBF.

Conclusion

The application of two different neural network classifiers to the problem of detecting waterlogged farmland using multispectral satellite imagery, has been evaluated in the study presented.

Using imagery acquired by the new WorldView-2 satellite, we showed that Multilayer Perceptron can achieve accuracy superior to that of other published approaches and classify 99.4% of the pixels in the scene accurately.

RBFs have not proved successful when applied to the problem at hand, since the k-means procedure used to position the kernel functions was unable to cope. Other ways of doing this, such as random sampling from the training data or orthogonal least square learning should be considered if RBFs are to be used in this scenario.

As a direction for further research, the methodology could be evaluated in terms of detecting less pronounced effects of water stress, where plants are not irreparably damaged. It could also be possible to design crop yield estimation models, akin to the methodology presented in [START_REF] Pan | Using QuickBird imagery and a production efficiency model to improve crop yield estimation in the semi-arid hilly Loess Plateau, China[END_REF].

Fig. 1 .

 1 Fig. 1. Part of the satellite image used to derive the training data set and test the classifiers. Only red, green and blue bands are shown.

Fig. 2 .

 2 Fig. 2. MLP classification result for the image shown in Fig. 1.

Fig. 3 .

 3 Fig. 3. MLP classification result for the image shown in Fig. 1.

Table 1 .

 1 Classification results for Multilayer Perceptronthe ridge parameter for the logistic regression was set to 10 -8. Table1provides the performance statistics for the RBF model. The accuracy achieved by the RBF is significantly lover than that of the MLP (94.3538%).

		TP Rate FP Rate Precision Recall F-Measure ROC Area
	Not waterlogged	0.998	0.037	0.995 0.998	0.997	0.995
	Waterlogged	0.963	0.002	0.987 0.963	0.975	0.995
	Weighted Avg.	0.994	0.033	0.994 0.994	0.994	0.995

Table 2 .

 2 Classification results for RBF

		TP Rate FP Rate Precision Recall F-Measure ROC Area
	Not waterlogged	0.992	0.410	0.947 0.992	0.969	0.925
	Waterlogged	0.590	0.008	0.904 0.590	0.714	0.925
	Weighted Avg.	0.944	0.362	0.942 0.944	0.938	0.925
	Figures 2 and 3 show the classification results for a part of the satellite image
	shown in Figure