Guillaume Touya

A Road Network Selection Process Based on Data Enrichment and Structure Detection

In the context of geographical database generalisation, this paper deals with a generic process for road network selection. It is based on the geographical context that is made explicit and on the characteristic structure preservation. It relies on literature work that is adapted and gathered. The first step is to detect significant structures and patterns of the road network such as roundabouts or highway interchanges. It allows to enrich the initial dataset with explicit geographic structures that were implicit in initial data. It helps both to explicit the geographical context and to preserve characteristic structures. Then, this enrichment is used as knowledge input for the following step that is the selection of roads in rural areas using graph theory techniques. After that, urban roads are selected by means of a block aggregation complex algorithm. Continuity between urban and rural areas is guaranteed by modelling continuity using strokes. Finally, the previously detected characteristic structures are typified to maintain their properties in the selected network. This automated process has been fully implemented on Clarity™ and tested on large datasets.

Introduction

Generalisation is a process that seeks to summarise geographical information from a geographic database in order to produce a less detailed database or map. When the goal is to derive a new database and not a map, it is called model generalisation and it is not constrained by cartographic symbols [START_REF] Weibel | Generalising Spatial Data and Dealing with Multiple Representations[END_REF]. Selection, that can be considered as an operation concerning the abstraction of the database [START_REF] Mackaness | Understanding Geographic Space[END_REF], is a key step to model generalisation. It consists in choosing the relevant information in relation to the target map or database specifications. This paper presents a generic road network selection process based on data enrichment using spatial analysis.

Selection seeks to choose the essential and relevant elements of a geographic database but also to maintain the main characteristics of geographic information while reducing the level of detail. As roads are important features of maps and geographic databases, road network selection is a key topic of generalisation that has already been tackled in the past [START_REF] Richardson | Integrating Thematic, Geometric and Topologic Information in the Generalization of Road Networks[END_REF][START_REF] Thomson | The "Good Continuation" principle of Perceptual Organization applied to the Generalization of Road Networks[END_REF][START_REF] Ruas | Modèle de généralisation de données géographiques à base de contraintes et d'autonomie[END_REF][START_REF] Jiang | A Structural Approach to the Model Generalization of an Urban Street Network[END_REF]. Other papers deal with structure and pattern recognition in order to ease road selection (Marshall 2005[START_REF] Heinzle | Graph Based Approaches for Recognition of Patterns and Implicit Information in Road Networks[END_REF][START_REF] Heinzle | Characterising Space via Pattern Recognition Techniques: Identifying Patterns in Road Networks[END_REF].

Road network selection for model generalisation raises several problems. First, selecting roads requires to infer the usage of the roads that heavily depends on roads implicit geographical context: methods have to be found to make the context explicit for an automatic process. Then, a hierarchy of roads is necessary in order to select the most important ones but road saliency is hard to infer: it depends on geometry, attributes, topology and role in the network i.e. it depends on implicit geographical context. Moreover, road networks in urban or rural areas are clearly different in road density and network shape and such differences have to be maintained by selection; road networks contain typical complex implicit road structures that a good selection should maintain. Finally, it is hardly manageable to precisely quantify the selection reduction level (in objects number? In meters? In relation to specifications?). Because of the diversity of data and generalisation problems, all previous work on the topic dealt with a specific part of these problems of road network selection. There has not been any attempt yet to develop a generic method that would gather this material in order to tackle all the problems globally. Thus, the objective of this work is to design an automatic and generic (for different data and resolution changes) process that would deal with the global problem of road network selection in model generalisation as well as developing solutions for the missing bricks of the process. The proposed method enriches data with the proper road structures and selects differently rural and urban networks thanks to the enriched data.

The next part of the paper describes the design constraints and the overall methodology for road network selection. The third part deals with data enrichment by structure detection in road networks and with the structures typification. The fourth part deals with the selection steps of our proposed process. Section five illustrates the process with results obtained with a real database. Finally, last section draws some conclusions and discusses further work.

Methodology

Hypotheses

Some hypotheses are made on the input vector data in order to use the proposed methodology. But the properties required for the data are quite generic and are met by most of vector geographic databases that contain roads. The last two requirements are optional as they are not necessary for the process but they improve its results. In the parts of the paper that describe how the optional data are used, alternative solutions are proposed. Here are the seven data requirements:  linear road data is required rather than surfacic roads.  the road network needs to be correctly topologically connected.  only one attribute representing roughly road classes is required.  no traffic direction data is required.  urban areas are necessary to separate urban and rural roads, or buildings to create the urban areas with a method from [START_REF] Boffet | Creating urban information for cartographic generalisation[END_REF].  optionally, facility points (airports, train stations, schools, malls...) can improve the process quality.  optionally, buildings can help in some structure detection algorithms. The test data of this work are a large dataset (150 x 100 km) extracted from BD TOPO®, the 1m resolution topographic vector database produced at IGN France. The road data correspond to our requirements and the optional requirements like facility points and buildings are also extracted from this database. The test area is characterised by a large heterogeneity of landscapes, which allows to anticipate the work validity on other areas of the same database.

Experiments

The methodology used to design the presented road network selection method was based on experiments: in order to have a clear view of the problems raised by road network selection, several tests and literature algorithm implementations were carried out on the test data. Then the methodology consisted in gathering literature resources that appeared to be useful, in adapting them to make them work together: according to the experiments results, some algorithms were mixed, chained, some were modified and some were dropped when alternative ones proved to be more effective. When no resource was available, new algorithms were developed. The last ones, as well as the adaptations, are more focused on in this paper.

Overall Process

This methodology led to the design of a complete road selection process composed of five important steps (Figure 1). First, the amount of implicit information contained in road networks requires a huge enrichment of initial data to provide what Brassel and Weibel (1988) called structural knowledge. The enrichment also provides some particular structures of the network that rather need to be typified than being simply selected to maintain properly the structures during selection. Then, the problems raised by urban networks appeared to be very specific: road density is very high and network shape and patterns are here the major factor of selection (to be able to still differentiate old European cities and modern US ones after selection). In rural areas, the problem is more about removing the less significant roads. As a consequence, two different processes have to be applied on rural and urban areas immediately followed by a process that guarantees continuity between the two types of area. Each step of the process will be described in detail in the following sections of the paper.

road use estimation

Database enrichment

Rural selection

Urban selection

Continuity checking

Structure typification

Data Enrichment

Brassel and Weibel (1988) recommended data enrichment as a prerequisite for automatic generalisation to formalise the structural knowledge contained in geographic information. This structural knowledge includes structure and patterns detection whose importance in generalisation has been claimed by [START_REF] Mackaness | The Importance of Modelling Pattern and Structure in Automated Map Generalisation[END_REF]. [START_REF] Mackaness | The Importance of Modelling Pattern and Structure in Automated Map Generalisation[END_REF] define patterns as a property (shape, orientation...) within an object or between objects that is repeated with sufficient regularity. A structure can be defined as a particular distribution of objects representing an implicit geographic entity. It corresponds to what [START_REF] Ruas | Modèle de généralisation de données géographiques à base de contraintes et d'autonomie[END_REF] calls meso objects. We consider road meaningful patterns as structures and we will use only this concept from now on. Road networks perfectly illustrate the importance of structures as roads form complex man-made networks full of particular structures. This section presents the main developed enrichments and the typification of some detected structures.

Road Structures Detection

This section presents the road structures that we consider as important to detect for selection and the algorithms developed for their automatic detection in a vector database.

Crossroads Classification.

Road crossroads can be considered as an atomic element of road network and it is very useful to better characterise them for selection according to [START_REF] Heinzle | Graph Based Approaches for Recognition of Patterns and Implicit Information in Road Networks[END_REF]. For example, y-nodes correspond to slip roads and T-nodes represent crossroads between a minor and a major road. A simple taxonomy of crossroads has been designed based on [START_REF] Grosso | Etude des carrefours d'un réseau routier -Première approche : modélisation et implémentation d'outils de détection des carrefours[END_REF]Sester (1995) The spatial analysis algorithms developed rely on a mixed use geometry and graph measures. The road network is seen as a graph thanks to GIS topology tools. T-nodes are topologically characterised by a degree 3 node and geometrically characterised by two nearly right angle  and a flat angle  between the arcs entering the node. With abstraction, it is characterised by a minor road leading to a major road. The tolerance thresholds used for  and  in the test case are 20° and 15°. As another example, y-nodes are characterised by a flat angle  (5° threshold), a slipping angle  (15° threshold) and an arc shape for the slip road. The Fork, CRS and Star nodes are detected and characterised with similar methods that are not developed here for briefness reasons. The Undifferentiated nodes are the remaining nodes. Figure 2 shows the results of the automatic detection of T-nodes, y-nodes, fork-nodes and CRS nodes (no Star node in the picture and the Undifferentiated nodes are the unmarked ones) : all the nodes are iterated and if the degree and the angles correspond to one of the characteristic crossroads, the nodes are properly classified. This enrichment is particularly useful for the detection of more complex structures but also for the structure typification and rural selection processes.

Complex

Junctions. Some widespread road patterns like roundabouts or branching crossroads can be seen as complex junction in relation to simple crossroads. With abstraction, they have the function of a crossroad and can be generalised as simple crossroads. In order to detect roundabouts, the faces of the mathematical graph are used rather than arcs and nodes [START_REF] Sheeren | How to Integrate Heterogeneous Spatial Databases in a Constistent Way[END_REF]. To keep only the small round faces (that clearly correspond to roundabouts (Figure 2)), a measure of polygon compactness is used on all the small faces of the graph. Miller's measure of compactness (see definition in Figure 4b) is chosen with a threshold of 0.98 determined after experiments. The Miller's measure varies from 0 to 1 (for a circle).

Branching crossroads are a bit more complex to detect as [START_REF] Grosso | Etude des carrefours d'un réseau routier -Première approche : modélisation et implémentation d'outils de détection des carrefours[END_REF] distinguishes two types. The first type concerns the small triangular faces of the network; the second is related to the branching junctions attached to roundabouts (Figure 2, on the left). The detection algorithm consists in considering the faces with only three degree 3 nodes. Then, a surface distance is computed between the face and the triangle formed by the three nodes. If the distance is low, the face is considered as a branching crossroad. In the test data, the thresholds are 10000 m² for size and 0.45 for surface distance (that is between 0 et 1). Then when a potential face is branched to a roundabout, the surface distance threshold is bigger.

Road Strokes.

The notion of strokes is based on one of the perceptual grouping principles enunciated by the Gestalt Psychologists [START_REF] Wertheimer | Laws of organization in perceptual forms[END_REF], namely the "good continuation" principle. Strokes are groups of roads gathered by continuous curvature (Figure 3a). The stroke creation algorithm described in [START_REF] Thomson | The "Good Continuation" principle of Perceptual Organization applied to the Generalization of Road Networks[END_REF] is used taking into account road class continuity: for each road section, the following sections continuity is analysed in relation to curvature and road class continuity. The best continuing section is added to the stroke if at least one provides a good continuity and the process iterates until all the sections of the network are part of a stroke, possibly being the only component of their stroke. In addition, the algorithm is adapted to manage previously detected complex junctions such as roundabouts or branching crossroads: the characterisation of such junctions allows to know the road segments leading to the junction.

When a stroke arrives at such junctions, continuity is only computed with the "outside" segments (Figure 3b) whereas the stroke would be stopped without the adaptation. As stroke length is a factor used in selection and as such junctions are very common in networks, strokes stopping at roundabouts would bias the selection and would correctly represent important routes as it intends to.

Dual Carriageways.

Considering the hypotheses (section 2.1), no traffic direction information is available in our data so the dual carriageways detection can not rely only on traffic direction as in [START_REF] Thom | A Strategy for Collapsing OS Integrated Transport Network Dual Carriageways[END_REF]. Thus, like in the roundabout detection method, the algorithm iterates through the network faces but this time, it seeks for very long and thin or narrow faces or small faces interlocked in thin faces. Indeed, looking for the parallel roads in data appeared to be ineffective. Road faces are classified by three measures, convexity (definition in Figure 4c), elongation (Figure 4a) and compactness (Figure 4b) that help to determine whether the face is thin (it belongs to a dual carriageway) or not. When the polygon is convex, the elongation measure is a correct assessment of the thinness of the face and then is used. But when the face is concave, this elongation measure can no longer be used because turning dual carriageways would not be detected. Thus, a compactness measure is used coupled with an area threshold as long and thin faces are not compact because the perimeter is very big compared to area. After long experiments, thresholds are set so that a face might belongs to a dual carriageway if:

 convexity > 0.8 and elongation > 5  or convexity < 0.8 and compactness < 0.2 and size < 50000 m²  or size <10000 m² and has 2 part of dual carriageways for neighbours Miller's index [START_REF] Campbell | Map Use and Analysis[END_REF] compactness = 0.54 [START_REF] Regnauld | Généralisation du Bâti : structure spatiale de type graphe et représentation cartographique[END_REF] Convexity rate [START_REF] Regnauld | Généralisation du Bâti : structure spatiale de type graphe et représentation cartographique[END_REF] 3.1.5. Highway Interchange. Highway interchanges are a significant example of the road structures that need a typification process to be properly generalised. [START_REF] Grosso | Etude des carrefours d'un réseau routier -Première approche : modélisation et implémentation d'outils de détection des carrefours[END_REF] noticed that highway interchanges are characterised by a high density in nodes that correspond to fork and y-nodes in our classification. The detection algorithm consists in a clustering by spread search in the road graph on the fork and y-nodes. Then, all roads inside the buffered convex hull of the cluster belong to the highway interchange (Figure 5). Over-detection is managed excluding the clusters whose extent contains a significant amount of buildings. The cluster search threshold was determined considering the usual length of slip roads and set to 400 m. If there is no building data available, measures can be used only on roads like the amount of dead ends, the presence of dual carriageways and the belonging of nodes to roundabouts. 3.1.6. Rest Areas. Rest areas are also important to detect. The properties of the structure are the presence of an entrance and an exit with roads between located on both sides of dual carriageways or other major road. The detection algorithm is composed of two main steps: the detection and grouping of entrances and exits, and the addition of in-between roads.

Entrances and exits are detected with y-nodes and their orientation (Figure 6a). The y-nodes belonging to an interchange are excluded and couples (entrance, exit) are formed considering the highway direction. Then, we switch once again to faces and a buffer is used on the good side (considering the direction) of the major road in which the small neighbouring faces are aggregated (Figure 6b). According to our experiments, a buffer size of 500 m and an area threshold for the faces to be included in the rest area of 50000 m² are effective thresholds. 3.1.7. Dead Ends. Dead end roads are another road structure that play a key role in selection processes because they are either useless (leading to nowhere important) or very important (leading to a significant facility). Unlike simple dead ends, the detection of dead end groups is not obvious. It uses the notion of minimal graph cycles: the roads that do not belong to a minimal cycle or that belong to a cycle disconnected from the graph (case with a roundabout at the end of the dead end) are considered as dead ends and are then grouped by connectivity. In the test data, optional facility data is available so dead ends are enriched with access to the facility when exists (when the nearest access to the network of a facility point is a dead end).

Typification of particular structures

Pattern typification is considered as the final step of the selection process (Figure 1) but it is presented here as it is completely linked to the structures recognition. A typification operator has been defined by [START_REF] Mcmaster | Generalization in Digital Cartography[END_REF] like this : 'A selective number and pattern of the symbols are depicted. Generally, this is accomplished by leaving out the smallest features, or those which add little to the general impression of the distribution (...) or using a representative pattern of the symbols...'. This step concerns a large part of the road structures presented in section 3.1. The road segments belonging to a structure needing typification are ignored by the different selection steps (rural, urban and continuity checking) in order to be finally typified. As a consequence, a parameter of the overall process is the choice of the important road patterns that have to be typified rather than to be simply selected or eliminated by the appropriate process. Two implemented methods to typify structures are presented in this section. First, a simple typification of roundabouts and branching crossroads relies on their characterisation with an enriched data schema. The roles of the road segment in the complex junction are identified: the road segments leading to a roundabout or belonging to it are distinguished. Then the last ones are collapsed into one point where the first ones are extended. Branching crossroads are typified into a T-node thanks to the enriched schema that identifies the minor and major roads of the abstracted T-shaped junction. A size parameter is added to decide whether the junction has to be typified or not. In the test case presented in the results section 5, if the diameter of a roundabout is under 100m, it is typified. Dual carriageways can be typified with the collapse of the structure into its centreline. The centreline can be obtained with algorithm computing skeletons of surfaces. [START_REF] Thom | A Strategy for Collapsing OS Integrated Transport Network Dual Carriageways[END_REF] method using Delaunay triangulation was implemented.

The Road Network Selection Process

The previous section presents a prerequisite step for the selection process described in this section as all the structures and patterns recognised in the road network enable a correct and relevant selection. As exposed in Figure 1, two different selection processes were developed, one for rural areas, one for urban areas. Added to that, a continuity checking process at the interface of the areas is included to recombine the selections.

Road selection in rural areas

Rural selection is based on determining roads saliency by shortest paths between attraction points following the method of [START_REF] Richardson | Integrating Thematic, Geometric and Topologic Information in the Generalization of Road Networks[END_REF]. The aim of the method is to estimate road use by cars, so shortest paths are computed in the network between nodes where cars are supposed to start (residential areas or airports) and nodes where cars are supposed to arrive (commercial or work areas). The attraction points result from the optional facility data weighted by importance and attached to a node of the network (Figure 7). If facility points are not available, random points can be used [START_REF] Ruas | Simulation and Agent Modelling for road selection in generalisation[END_REF]. Shortest paths are computed in the complete road graph including roads in urban areas to be really meaningful. Moreover, road use estimation is considered as an enrichment of road segments and it will be useful for urban selection process as input described in section 4.2. Only the shortest paths between an attraction point and the ones in a radius of 50 km are computed, using the algorithm of [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF], because we consider that road trips over this distance will massively use highways that are already considered as important. Like in [START_REF] Richardson | Integrating Thematic, Geometric and Topologic Information in the Generalization of Road Networks[END_REF], after the computation of all the shortest paths, roads used by shortest paths have their road use estimation value incremented to assess their importance in relation to initial and final attraction point weights. In Figure 9a, there is a graph with 5 attraction points (AP) (a to e) weighted from 1 to 3 according to their importance. In Figure 9b the shortest path from AP "c" to AP "d" is computed and the 2 roads used by the shortest paths are assigned a value equal to final AP weight (here 3). In Figure 9c, all shortest paths from AP "c" to the others are computed and road values are incremented as soon as they are used by a shortest path. For example, the road between AP "c" and the centre simple node is used by several shortest paths and its value is incremented to 7 (3 from c to d, 2 from c to a and 2 from c to e). Figure 9d shows the values of all roads after all shortest paths have been computed. Finally, rural selection is processed using different parameters that correspond to thresholds. A road is selected if :  estimated road use is bigger than a given threshold (very used road segments are important).

 or stroke (it belongs) length is bigger than a given threshold (long strokes are important).

 or stroke (it belongs) crosses a number of T-nodes bigger than a given threshold (it is important because it is served by many minor roads).

 or it belongs to a dead end longer than a given threshold (long dead ends are significant landmarks in a map).

 or it belongs to a dead end with facility access longer than a given threshold lower than the threshold just above (the access to the facility has to be maintained).

The choice of the selection criteria is partly application-related. Other selection criteria could be chosen when it is necessary to meet particular specifications. For example, some specifications may require that roads with particular attribute values have to be always selected.

Street selection in urban areas

As street selection is a more complex problem than rural road selection, different approaches have been tried: [START_REF] Ruas | Modèle de généralisation de données géographiques à base de contraintes et d'autonomie[END_REF][START_REF] Edwardes | Intelligent Generalization of Urban Road Networks[END_REF][START_REF] Jiang | A Structural Approach to the Model Generalization of an Urban Street Network[END_REF]. The approach presented in this paper is a kind of synthesis of these three ones based on the road block aggregation principle of [START_REF] Ruas | Modèle de généralisation de données géographiques à base de contraintes et d'autonomie[END_REF]: as for roundabouts for instance, the faces of the graph are considered rather than the arcs. The face aggregation principle is quite similar to area aggregation methods [START_REF] Van Oosterom | The GAP-tree, an approach to 'on the fly' map generalization of an area partitioning[END_REF] : the smallest area is aggregated to the neighbour area that minimises a cost function. In the case of road faces, when two faces are aggregated, the road that separates them is eliminated and the remaining roads at the end of the process are selected. [START_REF] Ruas | Modèle de généralisation de données géographiques à base de contraintes et d'autonomie[END_REF] aimed at cartographic generalisation so buildings density was the key factor for aggregation. Hence, the principle was kept but factors for aggregation and dynamics were changed.

Urban network enriched model.

In our process, data has to be enriched in urban areas (here called "towns" for the sake of simplicity (Figure 10)). Towns are characterised by a size ("big" or "small") and attribute statistics: strokes mean length in town, road use estimation mean for the streets and streets density. Two parameters are also assigned to the town: the maximum cost of aggregation (see section 4.2.3) and the maximum area of the faces. The parameters assigned can be different if the town is either big or small if we want big towns to be more simplified than small ones. Indeed, we have noticed that such requirements are common in generalised database specifications. Then, three new classes are added and populated. First, the road graph faces cut up by town limits are called "urban blocks". The urban blocks are the features that will be aggregated during the urban selection process. Then main roads passing inside the town, determined with stroke length, road class and road use estimation (result of rural selection), are classified as urban axes. The thresholds used are more restrictive than the ones for rural selection, which selects only the very important streets. It is both a way to be sure that these streets will not be eliminated in the process and to structure the town with its main axes. Finally, towns are partitioned by the urban axes to create "urban partitions". Like towns, partitions are characterised by a measure about the density of streets. It allows to take into account and maintain in the process road density differences like in town centre (many small roads) compared to suburbs (few longer roads).

Dynamics of aggregation.

The aggregation algorithm is based on an aggregation cost. For each small block that needs to be aggregated, a cost is computed for each neighbour of the same partition (two blocks of different partitions can't be aggregated). The candidate neighbour with the lowest aggregation cost is chosen and aggregated if the cost is lower than a maximum cost. When there is no block small enough left or when all aggregation costs are above the maximum cost, the algorithm stops (Figure 11).

Get smallest block

Get good candidates

Compute costs and get smallest

Aggregate the 2 blocks

Size > t1 ?

Cost > t2 ? number > 0 ?

_ _ _ _ _ _ _ _ _ _ ) 1 ( cos 3       
The main factor is compactness (Figure 4b) as compact blocks are a good final result of the algorithm. The more appropriate the aggregation is, the lower the cost is. All factors used are normalised in order to be multiplied. If a factor is higher than 1 (for example the road use on the separating street is higher than the road use mean for town streets), the cost increases to make the aggregation more difficult. Apart from compactness, the factors used in the cost function are:

 the graph centralities of separating streets as proposed [START_REF] Jiang | A Structural Approach to the Model Generalization of an Urban Street Network[END_REF]: centrality measures the importance of nodes in a graph and to measure the centrality of streets, they proposed to build a dual graph of the network where streets are the nodes connected by arcs to the nodes that represent intersecting streets. Thus, central separating streets are harder to eliminate by aggregation.

 the traffic estimation of separating streets with the same value as the one computed for rural selection (but that was computed on all roads). Thus, streets with a traffic estimation higher than the town mean are harder to eliminate by aggregation.

 the length of the strokes that contain the separating streets. Thus, streets that belong to strokes longer than the town mean are harder to eliminate by aggregation.

 the partition block density as aggregation is made easier in town partitions that were not initially very dense in order to maintain the differences between town centre and suburbs.

 the aggregated block size as aggregation is made easier when it generates small aggregated blocks. Once the factors were defined, the formula was adapted after testing by weighting more or less some factors to give them more or less importance in the cost. For instance, we believe that compactness is the key factor and should have the main influence in the cost, that is why the factor is powered by three while the centrality factor is square rooted. Figure 12 shows an example of aggregation : (a) block 1 is candidate for aggregation and has four neighbours. (b) Blocks 4 et 5 are eliminated because separated from 1 by important roads that belong to long and central strokes and cost is higher than maximum. (c) shows that the compactness of the aggregate 1-3 is quite low which increases the cost of aggregation. (d) shows that the aggregate 1-2 is very compact and as a consequence has a lower aggregation cost. Finally, block 1 is aggregated to block 2. After the aggregation, dead end selection in urban areas is managed the same way as in rural areas as it cannot be managed by a block aggregation process. Moreover, the dead ends linked to the network by a street that was eliminated are also eliminated whatever its length is to maintain network continuity. The two parameters of the algorithm are the minimum size of a block and the maximum aggregation cost that is related to the cost function formula.

Continuity checking

The presented method for road network selection uses two different kind of processes for rural and urban areas. Using them independently would cause discontinuities and inconsistencies. In order to avoid such problems, a continuity checking step is necessary and is decomposed in two steps : first, continuity needs to be controlled at urban/rural interface zones; then, the connectivity within the complete selected network has to be checked and corrected if necessary.

The idea is that a road partly selected in one of the processes should have its other part selected. If it has not been selected by the other process, it is restored during the continuity checking step. Strokes seem to be the ideal way to allow this (Figure 13). In this example, the road is only selected in urban selection and continuity checking allows to restore the part of the stroke that was not selected during rural selection providing a more logical selected network. Furthermore, to avoid discontinuities that are internal to one of the areas (it is most likely to appear in rural areas), an additional continuity checking post-process is carried out: groups of connected road segments that are not connected to the rest of the network are detected and the roads used by the shortest way to connect them are added to selection. The algorithm used here is similar to the one developed by Chaudhry and Mackaness (2005) : if discontinuities are detected, the unselected strokes are tested by length ascending order until the addition of one of them re-connects the network. The re-connecting stroke is added to selection.

Results and discussion

As mentioned in section 2, the test data is BDTOPO® (1m resolution topographic database) from IGN France. The main test case is the generalisation of BDCARTO® (10m resolution database) from the test data. The process has been applied with selection parameters corresponding to BDCARTO® specifications. But the process has been tested with other parameters. The complete process has been implemented on Clarity™ GIS and the results presented here as well as the ones presented in the previous sections, are all obtained automatically. Figure 14 shows a result of the global process presented in the section 2 with the test case of BDCARTO® on the town of Salies-de-Béarn and its surrounding area. This result is good in relation to the specifications and is totally equivalent to actual BDCARTO®. Figure 15 focuses on street selections obtained on a larger city with two sets of parameters. The first case (b) consist in a light selection of the network while the second one is a stricter selection that approximately correspond to a 10m resolution database. In both, main streets still appear and the density difference between the city centre and the suburbs is visible.

Such results are shown before the pattern typification step so roundabouts and dual carriageways, visible in the pictures, would disappear in the final results. Figure 14. A result of the global process on the town of Salies-de-Béarn and its surrounding area.

The difficulty to evaluate such a process is that the quality of a selection is hardly quantifiable because of most selection specifications fuzziness. Even when the result is compared to a reference dataset, it is hard to say if the differences are due to an imperfect process, uncertainties in the specifications translation or errors in the reference dataset (upto-dateness for example). Nevertheless, the results were compared in our test case with BDCARTO®. Rural selection selects 95% of BDCARTO® roads (in terms of road length) and urban selection provides a road length up to 98% of BDCARTO® road length but not exactly the same road segments (75%, in length, of the roads selected are identical). Most differences are due to specification fuzziness and up-to-dateness differences. In terms of efficiency (how quickly the result is obtained), it is a quite heavy process with a lot of enrichment and process time consuming algorithms like shortest path and centrality computing, but database generalisation is not supposed to be 'on-the-fly'.

(a) (a) The aim of this work was to design a generic process able to give results with different target specifications but also with different initial data. Nevertheless, the presented process is slightly dependant on the test data used to develop it. So, to be used with different datasets, the process would require little adjustments especially for shortest path computation where additional data is used for node and link weighting (point facilities data, road attributes like width or elevation). A difficult part of the process design is the choice of the multiple parameters and thresholds. Indeed, the translation of the target database specification may not always be obvious and the process requires a significant number of parameters. We decided to develop sets of default parameters to make the choice easier. Tests were carried out on the sensibility of a major part of the parameters, particularly the thresholds for selection like 'selection if stroke length > 3000 km'. The tests showed that the process was not very sensible to the variation of such parameters. Then the parameters can be chosen by approximation without risking to change drastically the results.

Conclusion

To conclude, this paper presents a complete process to allow road network selection in model generalisation. It consists in (1) enriching the data by structures recognition, (2) rural selection based on assessing traffic by shortest paths, (3) street selection algorithm based on road block aggregation and (4) structures typification. The contribution is mainly the design of this generic process and the development of the urban selection method. There are also contributions in the structure detection algorithms. Tests carried out on large datasets show encouraging results for different kind of generalisation specifications.

To go further, pattern typification has to be improved by implementing some algorithms specific to each structure. Added to that, it would be interesting to integrate new particular road structures like circular roads or star-shaped structures [START_REF] Heinzle | Characterising Space via Pattern Recognition Techniques: Identifying Patterns in Road Networks[END_REF]. Their detection could be used to enhance the selection algorithms. The idea exposed in Marshall (2005) that road patterns are like an unfolding fractal shows that many more structures can be detected in a road network to add knowledge and improve the selection. As a further work, it would also be interesting to work on expressing the specifications of a selection to parameterise automatically the process, like in [START_REF] Hubert | A method based on samples to capture user needs for generalisation[END_REF] that used generalised data samples to converge to the user needs. Finally, it could be interesting to insert this process into a global cartographic generalisation process that would deal with selection before the cartographic operations.

Figure 1 .

 1 Figure1. the overall process of road network selection. In italics, the different inputs and outputs of the process steps.

  . It contains T-shaped nodes (T-nodes), Fork nodes, y-nodes (slip road end), Cross-shaped nodes (CRS-nodes), Star nodes and Undifferentiated nodes.

Figure 2 .

 2 Figure 2. Results of the automatic detection of some simple crossroads.

  Figure 3. (a) A stroke in a road network: a group a roads following the "good continuation" principle. (b) strokes pass through roundabouts and branching crossroads.

where

  L = length of MBR and W = width of MBR HullArea = area of convex hull (polygon B)

Figure 4 .

 4 Figure 4. The 3 measures used to assess the thinness of polygons: (a) elongation. (b) compactness by Miller's index. (c) convexity.

Figure 5 .

 5 Figure 5. Highway interchange detected by clustering the fork (triangles) and y-nodes (circles).

  Figure 6. (a) Detection of enters and exits of rest areas. (b) detection of the extent of the rest area.

Figure 7 .Figure 8 .

 78 Figure 7. How weighted attraction points are attached to the road network. Instead of using simply road length to compute shortest paths, a travel time estimation is used. The travel time is estimated with a weight function (Figure 8) taking into account attribute values or geometric characteristics : road length is multiplied by factors smaller than 1 for quickening characteristics and greater than 1 otherwise. Road class (main roads

Figure 9 .

 9 Figure 9. Valuing of roads in shortest path computation. See description of the process in the text.

Figure 10 .

 10 Figure 10. Enriched data model of an urban area for street selection, illustrated with data samples from the town of Salies-de-Béarn in the southwest of France.

Figure 11 .

 11 Figure 11. Diagram of the dynamics of the aggregation algorithm.We defined the cost function formula below to compute the aggregation cost.

Figure 12 .

 12 Figure 12. Which neighbour block can be aggregated to block 1?

Figure 13

 13 Figure 13. (a) An initial network at the limit (in bold) of a town. (b) A big stroke that crosses both urban and rural areas. (c) The use of only the two independent processes creates a problem of continuity highlighted by the circle. (d) The continuity problem is solved by the use of the stroke highlighted in (b).

Figure 15 .

 15 Figure 15. (a) The street network of the city of Pau (southwest of France) in BDTOPO®. (b) a light selection of this street network. (c) a stronger selection corresponding to 10 m resolution database.

Acknowledgement

I wish to acknowledge Pr. William Mackaness for his contribution to this paper and for helping me to organise my ideas.


Céline Fiot
email: fiot@lirmm.fr

G A Putri Saptawati

Anne Laurent
email: laurent@lirmm.fr

Maguelonne Teisseire
email: teisseire@lirmm.fr

Learning Bayesian Network Structure from Incomplete Data without any Assumption

Since most real-life data contain missing values, reasoning and learning with incomplete data has become crucial in data mining and machine learning. In particular, bayesian networks are one machine learning technique that allow for reasoning with incomplete data, but training such networks with incomplete data may be a difficult task. Many methods were thus proposed to learn bayesian network structure with incomplete data, based on multiple structure generation and scoring of their adequacy to the dataset. However this kind of approaches may be time-consuming. Therefore we propose an efficient dependency analysis approach that uses a redefinition of probability calculation to take incomplete records into account while learning BN structure, without generating multiple possibilities. Some experiments on well-known benchmarks are described to show the validity of our proposal.

Introduction

Graphical models [START_REF] Whittaker | Graphical models in applied multivariate statistics[END_REF] are tools combining two different areas: graph theory and probability theory. They are often used to illustrate and work with conditional independencies and probabilistic relationships among variables in a given problem. Among graphical models, bayesian networks are often involved in tasks requiring to reason under uncertainty. In particular, many approaches allow for reasoning with incomplete data. But the task of training bayesian networks with incomplete datasets is more complex.

In fact, there are two classes of methods for building the graphical structure of bayesian networks from complete datasets. Scoring-based algorithms consist in generating many likely structures and then scoring them using a fitness function measuring how well each possible graph fits the data. On the other hand, constraint-based algorithms -also called dependency analysis approaches -build the graph directly from the data thanks to probability calculations and conditional independency tests. Some approaches tackle the problem of missing values either by deleting observations with missing values or using ad-hoc techniques to impute missing information. Such procedures may however lead to biased results, and in case of imputing a single value for unassigned attributes, to an overconfidence in the results of the analysis. Some specific algorithms have also been shown to be successful for learning bayesian network structure from complete data, and learning parameters for a fixed network. Other scoring-based algorithm have finally been developed using an estimation of the missing observations on the basis of available information and data distribution. However this may be timeconsuming and resource-demanding.

Since very few methods are capable of using incomplete cases as a base to determine the structure of a bayesian network by a constraint-based approach, we propose in this paper an efficient dependency analysis approach to handle incomplete records while learning BN structure. Our proposal consists in a redefinition of probability calculation that allows for information incompleteness without missing value imputation. Then we adapted the efficient Three Phase Dependency Analysis algorithm proposed by [START_REF] Cheng | Learning belief networks from data: an information theory based approach[END_REF] to make it use our new probability definitions, while computing conditional independency tests. Some experiments on classical benchmarks are described to show the validity of our proposal for generating bayesian network structure underlying incomplete datasets.

This paper is organized as follows: in Section 2, we introduce the definition and principles used in the context of bayesian network learning; then in Section 3, we detail the basis of our approach and our new definitions for probability calculation. Finally, before concluding in Section 5, some results of experiments are developed by Section 4.

Bayesian Network and Incomplete Data

Regarding a data set, a bayesian network gives both a qualitative and quantitative description of the dependencies existing between data attributes. First, these dependencies are visually described by a directed acyclic graph (DAG). In this graph, each vertex, or node, corresponds to an attribute in the database and directed edges between nodes show the dependencies between related attributes. Then, each node is associated with a conditional probability table, which gives, for each value of the node attribute, its probability considering the value of the attribute parent nodes.

Directed Acyclic Graph (DAG)

A graph, or undirected graph, can be defined as a set of nodes, also called vertices, and a set of edges, also called arcs, each being a pair of nodes. If the two vertices within each edge are ordered, then the edges have a direction assigned to them; this is called a directed graph. A chain is a series of nodes where each successive node in the chain is connected to the previous node by an edge. A path is a chain with the further constraint for directed graphs that each connecting edge in the chain has a directionality going in the same direction as the chain. A cycle is a path that starts and ends at the same node. A directed acyclic graph, or DAG, is a directed graph that has no cycles. The terms parent and child define the relationship between two vertices connected by a directed edge from the parent to the child. Two vertices are said to be adjacent when they are connected by an undirected edge.

Bayesian Network

A bayesian network is a specific graphical model that is a concise representation of the joint probability distribution for a large set of attributes in a database. Each attribute can be considered as a random variable associated with several values. Then, for a set of variables V, a bayesian network consists of a directed acyclic graph that encodes a set of conditional dependence and independence assertions about variables in V, and a set of local probability distributions associated with each variable. Together, these components define the joint probability distribution for V.

In [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems[END_REF], Pearl defines a bayesian network as a triplet [V, G, P (V i |P a (V i ))], where:

-V = {V 1 , ..., V n } is the set of random discrete variables;
-G is a directed acyclic graph whose nodes represent variables V i , and whose arcs encode the conditional dependencies between the variables; -P (V i |p a (V i )) describes the conditional probability distribution of each variable V i considering its immediate parents pa(V i ) in the graph G.

The edges in the bayesian network encode a particular factorization of the joint distribution. In general, the joint probability function for any bayesian network representing the set of nodes V is given by

P (V) = n i=1 P (V i |pa(V i ))
This means that the joint probability of all of the variables is the product of the probabilities of each variable given its parents' values. Then, the graph describes these dependencies. For any given edge between variables V i and V j , if there is a causal relationship between variables, the edge will be directional, leading from the cause variable to the effect variable. If there is just a correlation between the two variables, the edge will be undirected [START_REF] Cowell | Probabilistic networks and expert systems[END_REF]. Two variables that are conditionaly independent have no direct impact on each other's values. However, any path through intermediary variables that separates two conditionally independent variables shows how these two conditionally independent variables affect each other.

Learning Bayesian Networks

As a bayesian network is constituted of one qualitative component, the DAG, and one quantitative component, the conditional probability distribution, learning bayesian network consists in two tasks. First the structure describing the dependencies is designed, then the conditional probabilities of each node are calculated. Two approaches are generally used to learn the structure. The first one is based on scoring an a priori designed structure. The second one uses constraints and conditional independence tests to build the graph.

Scoring-based approaches [START_REF] Cooper | A bayesian method for the induction of probabilistic networks from data[END_REF][START_REF] Spiegelhalter | Bayesian analysis in expert systems[END_REF][START_REF] Lam | Learning bayesian belief networks: An approach based on the mdl principle[END_REF][START_REF] Heckerman | Learning bayesian networks: The combination of knowledge and statistical data[END_REF] select the DAG that best fits the data among several ones a priori designed. The objective of learning is then to evaluate each previously designed structure regarding the dataset. These methods require to specify scoring functions that are used to evaluate how well each network matches the training data. In the approaches based on model selection, some criterion is used to measure the degree to which a network structure (equivalence class) fits prior knowledge and data. A search algorithm is then used to find an equivalence class that receives a high score by this criterion.

Constraint-based algorithms, also called dependency analysis algorithms, build the DAG structure by identifying the conditional independence relationships among the variables [START_REF] Chow | Approximating discrete probability distributions with dependence trees[END_REF][START_REF] Pearl | A theory of inferred causation[END_REF][START_REF] Spirtes | Causation, Prediction, and Search[END_REF][START_REF] Spirtes | Learning bayesian networks with discrete variables from data[END_REF]. These methods are based on the causal sufficiency hypothesis: for every pair of measured variables in the training data, all their common parents are also measured. Thus, the graph is built thanks to the set of data, without external knowledge. Vertices of the DAG are built from the variables within the dataset and the edges are built from the observed dependencies between variables within the data.

Once the structure has been designed, each node of the DAG is associated with a table of conditional probabilities that give for each value of each variable the path to follow in the DAG. Depending on the problem that is defined, either the topology or the probability distributions or both may be pre-defined by hand or may be learned from the data.

In this paper, we will consider that the structure is unknown but that all the variables can be identified (i. e. there is no hidden variables [START_REF] Heckerman | A tutorial on learning with bayesian networks[END_REF]). Within a context where some variables are randomly unassigned, we tackle the problem of learning the structure of a bayesian network given data, using an approach based on the information theory.

Handling Missing Values

In data mining and machine learning, missing value handling is a significant problem as most real-life data contain unassigned variables. One advantage of belief networks is that they allow reasoning with incomplete data [START_REF] Heckerman | A tutorial on learning with bayesian networks[END_REF]. Many inference algorithms can indeed be used to calculate the probability of any variable that has not been measured conditionally to the values of measured variables. But complete data are often required for training such networks.

As described in the previous section, there are two different problems related to the presence of missing values while learning bayesian network. One consists in the evaluation of the probability parameters despite unassigned variables, the second consists in assessing the dependencies and learning the graph structure in spite of incomplete observations. Some approaches tackle the problem of missing values either by deleting observations with missing values or using ad-hoc techniques to impute missing information. Such procedures may however lead to biased results, and in case of imputing a single value for unassigned attributes, to an overconfidence in the results of the analysis. Therefore specific algorithms have been developed and several methods have been shown to be successful for learning both network structure and parameters from complete data, and learning parameters for a fixed network [START_REF] Lauritzen | The em algorithm for graphical association models with missing data[END_REF]. But very few methods are capable of using incomplete cases as a base to determine the structure of a bayesian network by a constraint-based approach.

Most of techniques that determine the bayesian network structure from incomplete data are indeed based on model scoring and selection: these proposals use an a priori known structure and compare it to the observed distribution. Wellknown methods typically involve the use of the EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF] or Markov Chain Monte-Carlo methods, such as Gibbs sampling [START_REF] Chickering | Efficient approximations for the marginal likelihood of bayesian networks with hidden variables[END_REF]. The basic strategy underlying these methods is based on the Missing Information Principle [START_REF] Little | Statistical analysis with missing data[END_REF]: fill in the missing observations on the basis of the available information.

Thus [START_REF] Friedman | Learning belief networks in the presence of missing values and hidden variables[END_REF][START_REF] Friedman | The bayesian structural em algorithm[END_REF][START_REF] Leray | Bayesian network structural learning and incomplete data[END_REF] propose different algorithms based on extensions of the expectation-maximization algorithm for model selection problems. [START_REF] Myers | Learning bayesian networks from incomplete data with stochastic search algorithms[END_REF] and [START_REF] Myers | Learning bayesian networks from incomplete data using evolutionary algorithms[END_REF] describe approaches based on stochastic search and evolutionary algorithm that approximates a maximum likelihood approach to score the network by evolving samples of incomplete data. Unfortunately, these processes are usually highly resource demanding, their convergence rates may be slow, and their execution time heavily depends on the number of missing values.

Therefore [START_REF] Cowell | Parameter estimation from incomplete data for bayesian networks[END_REF] uses an entropy maximization procedure to incorporate information regarding the nature of the missing data mechanism and thus considerably saving in computation time when compared to Gibbs sampling.

Other scoring-based approaches use estimation of missing data for both parameter and structure learning. [START_REF] Ramoni | The use of exogenous knowledge to learn bayesian networks from incomplete databases[END_REF][START_REF] Ramoni | Parameter estimation in bayesian networks from incomplete databases[END_REF] introduces a deterministic method to estimate the conditional probabilities defining the dependencies in a bayesian network which does not rely on the Missing Information Principle and proposes the Bound and Collapse algorithm for parameter estimation and model selection from incomplete data. However this algorithm also relies on an assumed pattern of missing data that may be either provided by an external source of information or may be estimated from the available information under the assumption that data are missing at random. This approach is extended in [START_REF] Ramoni | Learning bayesian networks from incomplete databases[END_REF] to learn the graphical structure of a bayesian network from a possibly incomplete database, using estimation of missing data.

More recently, [START_REF] Riggelsen | Learning bayesian network models from incomplete data using importance sampling[END_REF] describes an imputation-based approach for model learning from incomplete data, where possible completions of the data are scored together with the observed part of the data. [START_REF] Li | Learning bayesian networks structures from incomplete data: An efficient approach based on extended evolutionary programming[END_REF][START_REF] Li | A new method of learning bayesian networks structures from incomplete data[END_REF] describes an algorithm based on extended evolutionary programming method. It uses fitness function based on expectation, which converts incomplete data to complete data. [START_REF] Riggelsen | Learning bayesian networks from incomplete data: An efficient method for generating approximate predictive distributions[END_REF] introduces an approach for assessing the predictive distribution of missing values that is then combined to any learning algorithm.

Objectives

The main disadvantage of scoring-based approaches is that they rely on determining among numerous structures the one that best fit the data. So this kind of approaches requires a priori expert knowledge to design few structures to be tested or to generate every possible structures from the data. This processes are thus highly resource demanding and in the case of incomplete data, the runtime may become very high.

Therefore in this paper we propose a constraint-based approach to learn bayesian network from a randomly incomplete dataset without assessing or deleting missing values nor generating several possible structures. We use observed data without requiring any external information or estimation of missing value distribution.

Our method is based on a redefinition of the probability functions taking into account that some variable values are unknown. We developed our algorithm for learning bayesian network structure by adapting the efficient Three Phase Dependency Analysis (TPDA) algorithm proposed in [START_REF] Cheng | Learning belief networks from data: an information theory based approach[END_REF] to make it use our own probability definitions. Finally, we ran several experiments to show the feasibility, validity and robustness of our approach.

In the following section, we introduce the principles we based our approach on. Then, we detail our new definitions and prove that they hold all the conditions required to define a probability measure. Last, we describe the overall learning algorithm and run a brief example. In Section 4, we present the results of our experiments.

TPDA for Incomplete Databases

Our approach is based on the same principles as the ones used by the RAR algorithm [START_REF] Ragel | Treatment of missing values for association rules[END_REF] for association rule mining [START_REF] Agrawal | Mining Association Rules between Sets of Items in Large Databases[END_REF] in incomplete databases. The data formalism of association rules is indeed quite similar to the one of bayesian network: the dataset is a relational table consisting in records in which values are associated with attributes, that correspond to random variables in the context of bayesian networks.

The main idea of our approach is based on the RAR method. It consists in disabling incomplete elements, within our context, incomplete records. As the RAR algorithm for association rules mining, we will only regard complete records to compute the conditional probabilities. In other words, when an incomplete record is scanned, only filled-in attributes will be considered for probability calculation. Thus each conditional probability will be computed on a partial database, but the whole dataset will be used to find the whole set of dependencies.

Overall Principle

The RAR algorithm (Robust Association Rules), proposed by [START_REF] Ragel | Treatment of missing values for association rules[END_REF], allows the user to consider incomplete data while association rule mining within incomplete relational databases, thanks to partial and temporary omission of such incomplete records. The main idea consists in taking only filled-in attributes in incomplete records into account. The whole database is not used to discover each rule but the whole set of rules.

This technique is based on the valid database concept, which is a complete dataset for a given itemset, i.e. a set of attributes or variables. The remaining part of the database is temporary ignored. In order to consider this dataset partitioning, definitions of support (percentage of records in database that include the rule items) and confidence (probability for a record to contain the right part of the rule knowing it contains the left part) were reformulated.

Learning the structure of a bayesian network by a constraint-based approach such as TPDA algorithm requires to compute conditional probabilities and probabilistic conditional independence tests. We here apply the formalism of the RAR algorithm to define a new probability measure. This measure will then be used by our implementation of the TPDA algorithm to run the conditional independence tests and thus to build the DAG structure.

So, let us consider a set of random variables V each associated with one of their values v, the set R of records r in the database DB can be divided into three disjoint subsets (Figure 1). The set of records filled in with the corresponding value v i for each variable V i of V is denoted by R V . The set of records filled in with at least one value different from the set v is denoted by R V . And the set of records for which at least one value v is unfilled, i. e. is missing and we do not know if r(V i )=v i or not, is denoted by R * V . For each set of variables V , only the subsets R V ∪ R V will be kept to determine the conditional probabilities on V . This subset represents the valid database for V . Incomplete records are disabled for V . Definition 1. A valid database is a database only containing complete records for a given set of random variables, i.e. each value of each record in the data corresponds to an identified values v of Dom(V ). Definition 2. A record is disabled for an instanciation of a set of variables V if it is incomplete for V (i.e. we cannot decide whether it includes V or not). The set of records disabled for a set V is denoted by Dis(V ).

RV n Records including V R * V n Records that may include V R V n Records not including V
For instance, considering the dataset described by Fig. 2, the valid database for X 1 is composed of records R 2 to R 5 and Dis(X 1 ) = {R 1 }. The valid database for

V = {X 1 , X 4 } is {R 3 , R 4 , R 5 }, and Dis(V ) = {R 1 , R 2 }.
Building a valid database leans on temporary disabling records that contain missing values for variables in the set of random variables. This implies a redefinition of the probability calculation to consider the database partial deactivation.

Redefining Calculation of Probabilities

The probability definition is modified in order to consider the valid database concept, and thus that only one part of the dataset is used for each probability calculation.

Definition 3. The probability of an event v i is the appearance rate of this event among the records that can include it. It is defined as the ratio of the number of records r such that r(V i ) = v i by the number of records that are filled in for V i (complete records for V i ). It is given by:

P (V i = v i ) = card ({r ∈ R|r(V i ) = v i }) card(R) -card(Dis(V i )) (1)
Considering a set of random variables V = {V 1 , ..., V n } ⊆ V and a joint probability function P defined on V, the probability of a joint event P (v 1 , ..., v n ) is computed considering the set of records that are complete for all the variables V 1 , ...V n . Then the previous formula can be expressed as follows:

P V1,...,Vn (v 1 , ..., v n ) = card   i∈[1,n] {r ∈ R|r(V i ) = v i }   card(R) -card(Dis(V 1 , ..., V n )) (2)
For instance on Fig. 2, to compute P (X 1 = y), we find Dis(X

1 ) = {R 1 }, then P (X 1 = y) = card({R 2 , R 3 , R 4 })/5 -card(Dis(X 1 )) = 3/(5 -1) = 0.75. If we compute P (X 1 = y, X 2 = n), then Dis(X 1 , X 2 ) = {R 1 , R 5 } and P (X 1 = y, X 2 = n) = card({R 2 , R 4 })/(5 -card(Dis(X 1 , X 2 ))) = 2/(5 -2) = 0.67. Proposition 1. Given a random variable V i of values v i in domain D(V i )
, the redefinition of the probability P calculation defines a joint probability function over the variable set V.

Proof. A probability function P must satisfy the following properties:

1. for every event A ∈ A, 0 ≤ P (A) ≤ 1; 2. for the impossible event ∅ and the certain event Ω, P (∅) = 0 and P (Ω) = 1; 3. if the events A i ∈ A are finite or countably many mutually exclusive events

(A i A k = ∅ for i = k), then P ( n i=1 A i = Σ n i=1 P (A i )
We will denote r(V i ) the value of attribute/variable V i in the record r and card(S) will denote the cardinality of a subset S of records.

1. Considering the database partitioning, {r ∈ R|r

(V i ) = v} ⊆ R\Dis(V i ), which implies that card({r ∈ R|r(V i ) = v}) ≤ card(R) -card(Dis(V i )).
Then, as a cardinality is necessarily greater than or equal to zero and assuming that at least one record in the database is complete for V i , we obtain

0 ≤ card({r ∈ R|r(V i ) = v}) card(R) -card(Dis(V i )) ≤ 1 ⇒ ∀v, 0 ≤ P Vi (v) ≤ 1 2.
A record necessarily contains a value, missing or not, for a variable V i then card({r ∈ R|r(V i ) = ∅}) = 0 and P Vi (∅) = 0. Then we show that

P Vi (∪ v∈D(Vi) V i = v) = 1: ∪ v∈D(Vi) {r ∈ R|r(V i ) = v} = R\Dis(V i ) ⇒ card(∪ v∈D(Vi) {r∈R|r(Vi)=v}) card(R)-card(Dis(Vi)) = 1 ⇒ P Vi (∪ v∈D(Vi) V i = v) = 1 3. ∀A j ∈ V i |∀j = k, A j ∩ A k = ∅, P Vi (∪ j A j ) = j P Vi (A j ).
Within our context, such an event A j corresponds to a set of values v for a random variable V i . In other words, it can be expressed by the formula

∀A j , ∃D j ⊆ D(V i )|A j = ∪ v∈Dj {r ∈ R|r(V i ) = v}
We use this formulation to prove that the last condition is satisfied.

P Vi (∪ j A j ) = P Vi (∪ j ∪ v∈Dj V i = v) = card(∪j∪ v∈Dj {r∈R|r(Vi)=v}) card(R)-card(Dis(Vi))
As the events A j are disjoint, = j card(∪ v∈Dj {r∈R|r(Vi)=v}) card(R)-card(Dis(Vi))

= j P Vi (A j )
So the last condition is satisfied, for all random variables V i , the new measure P i defines a probability measure on each variable. ⊓ ⊔ Proposition 2. Given a set of random variables V , every function defined by P W ⊆V ( Wi∈W W i = w i ), computed by the formula 2, is a joint probability function.

Proof. We have to prove that for all set W of random variables such that W ⊆ V , the function P W defined by

P W (∩ Wi∈W W i = w i ) = card(∩ Wi ∈W {r ∈ R|r(W i ) = w i }) card(R) -card(Dis(W ))
is a joint probability function. Dis(W ) denotes the set of records disabled for W , i.e. the set of records for which at least one variable in W is unassigned.

First we show that

P W (∩ Wi∈W W i = w i ) is in [0, 1]. As {r ∈ R| ∩ Wi∈W r(W i ) = w i } ⊆ R\Dis(W ), we can simply show that P W (∩ Wi∈W W i = w i ) ≤ 1,
using the same proof as previously. Moreover, as it is defined by set cardinalities, it is necessary greater than 0.

Then we prove that

wi∈D(Wi) M W (∩ Wi ∈W W i = w i ) = 1. ∪ wi∈D(Wi) {r ∈ R| ∩ Wi∈W r(W i ) = w i } = R\Dis(W ) ⇒ card(∪ wi ∈D(Wi) {r ∈ R| ∩ Wi∈W r(W i ) = w i } = card(R) -card(Dis(W )) events ∩ Wi∈W W i = w i being mutually exclusive, ⇒ wi∈D(Wi) card({r ∈ R| ∩ Wi∈W r(W i ) = w i }) = card(R) -card(Dis(W )) ⇒ wi∈D(Wi) card({r∈R|∩W i ∈W r(Wi)=wi}) card(R)-card(Dis(W )) = wi∈D(Wi) M W (∩ Wi ∈W W i = w i ) = 1 ⊓ ⊔

Learning Algorithm

The proposition 2 allow us to apply all the formalisms defined for bayesian network learning methods with complete data. Our approach is based on the generic principle of constraint-based learning methods. More precisely, we implemented our algorithm from the Three Phase Dependency Analysis algorithm developed by [START_REF] Cheng | Learning belief networks from data: an information theory based approach[END_REF], using the probability formulae introduced in the previous section for computing the conditional independency tests. The overall algorithm lays on three elementary steps:

1. conditional independencies are uncovered from the data using statistical tests, 2. then, these independencies are used to build a partially directed acyclic graph (PDAG) in two steps, -edges X-Y of an undirected fully connected graph are deleted for each pair of independent variables (X, Y ), -the undirected graph then obtained is partially directed using the discovered conditional independencies; 3. last the PDAG is completed applying the following rules:

-if there is an edge such that X → Y and Z is adjacent to Y but not to X, then if there is an undirected edge between Y and Z, this edge is directed from Y to Z (Y → Z), -if there exists a directed path from X to Y and an undirected edge between X and Y , then this edge should be oriented from X to Y (X → Y ) to avoid building cycle.

Experiments

Our experiments were done to compare network structures generated by TPDA with complete data with the one obtained running TPDA adapted for handling missing values (TPDAID), using our own definitions for probability calculations, detailed by section 3. The goal was to show the validity of our redefinition of probabilities within the context of training bayesian network with incomplete data. We also aimed at measuring the robustness of our proposal to various incompleteness rate of the datasets.

Datasets

The results detailed here were obtained on several standard benchmarks often used by the bayesian network community. The characteristics of these datasets created from the various belief networks are described by Table 1. From these complete datasets we generated incomplete ones. Missing values were randomly inserted in the database, replacing some attribute values. For each complete database, we thus created six incomplete datasets respectively containing 5%, 10%, 20%, 30%, 40% and 50% of missing values.

Table 1. Characteristics of the datasets Dataset # of attributes # of records Fire Network [START_REF] Poole | Computational Intelligence[END_REF] 6 10,000 Asia / Chest Clinic Network [START_REF] Lauritzen | Local computations with probabilities on graphical structures and their application to expert systems[END_REF] 8 5,000 Alarm Network [START_REF] Beinlich | [END_REF] 37 10,000

Results

For each complete dataset and then incomplete datasets, we ran TPDA or TP-DAID and so for each dataset we generated the bayesian network structure. Then we compared the graphs resulting from training with incomplete data to those resulting from training with complete data. To do so we analyzed the number of missing or additional edges and the number wrong directions.

Figure 4(a) shows the comparison between the graphs obtained for the Fire dataset according to the incompleteness rate. The original bayesian network contains five edges, it is described by Figure 3 For 5% and 10% of missing values, the graphs resulting of TPDAID are exactly the same as the complete database graph. Then the number of additional edges increases to 1 for 30 to 50% of missing values. On the Fire dataset it seems that the incompleteness rate influences more the number of wrong directions. Indeed, the graphs contain at least one wrong direction from 20% of missing values, as shown by Figure 3(b); the dashed arrows are the same as in the original network, the boldfaced one is the one modified. shows the comparison between graphs obtained for the Asia dataset according to the incompleteness rate. We can observe that results are not as good as with the Fire dataset for low incompleteness rates. However the quality of the graph remains stable as the percentage of missing values increases.

Last, applying TPDAID on the Alarm incomplete datasets gives us interesting results for incompleteness rates below 30% of missing values. Indeed with these proportions of missing values -from 5 to 20% -the resulting structure is still close to the one obtained from TPDA on the complete dataset. From 30% of missing values the graph contains half of badly-oriented or additional edges, however half of the graph remains correctly built.

Synthesis and Future Work

Through our experiments, we observed that the data distribution and the incompleteness rate have an influence on how well our approach returns interesting results. Analysing the different results, we consider that our approach is robust until around 25% to 30% of missing values in the training dataset. However, there are important differences if we compare the results obtained on datasets with many or few variables and the number of records also influences the results. Therefore, we are now working on improving the quality of the graph trained on incomplete datasets using our approach and reducing the influence of the data distribution. We plan to define a parameter, based on statistical properties, to bound the minimum number of complete records that should be used for computing each conditional independence test. Thus each probability should be computed on significant-enough valid databases.

Besides the second step for learning BN, i. e. learning the probability table for each node of the structure, should be tested. These experiments will aim at assessing how well our redefinition of probabilities is adapted to learn the parameters from an incomplete dataset. If these results are conclusive we will be able to propose a global dependency analysis algorithm for efficiently learning bayesian network structure and parameters from incomplete databases.

Conclusion

In this paper, we introduced a new method for learning bayesian networks from incomplete data. On the contrary to existing algorithms that are based on model scoring and selection, or on assessing or imputing missing values, our approach is based on dependency analysis and a redefinition of the probability calculations.

Thus while the other approaches are resource-demanding or time-consuming because of multiple iterations, our algorithm generates the graph computing conditional independence tests using a reformulation of probabilities. This redefinition is based on the principle that incomplete records contain some certain information that is exactly regarded, assigned attributes, and an uncertain part of information that should be ignored, missing values. This hypothesis enables us to compute probabilities without multiple iteration for estimating missing values nor a biasing a priori imputation and without requiring external knowledge.

As the preliminary experimental results show, this new approach leads to quite good results for databases containing up to 30% of missing values. However, it can be improved by taking data distribution and statistical results into account to refine the probability calculation. We thus plan to develop a global algorithm that will both learn structure and parameters for bayesian network from incomplete datasets, based on our redefinition of probabilities that handle uncertainty contained in incomplete data.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Partition of the database depending on V inclusion.

  Figure 4(a) shows the comparison between the graphs obtained for the Fire dataset according to the incompleteness rate. The original bayesian network contains five edges, it is described by Figure3(a).

Fig. 3 .

 3 Fig. 3. (a): The Fire bayesian network structure (taken from [33]); (b): The Fire bayesian network structure obtained from 20% of missing values dataset.

Fig. 4 .

 4 Fig. 4. (a): Results for the Fire dataset; (b): Results for the Asia dataset.

Figure 4 (

 4 Figure 4(b) shows the comparison between graphs obtained for the Asia dataset according to the incompleteness rate. We can observe that results are not as good as with the Fire dataset for low incompleteness rates. However the