Catherine Baumont

Yves Aragon

Ines Heba

Christine Thomas-Agnan

James Lesage

Daniel Mcmillen

Reid Neil

Antonio Paez

Christine Thomas

DO HOUSING PRICES CAPITALIZE URBAN DEVELOPMENT POLICI ES in the A gglom eration o f Dijon (1 9 99 ) ?*

Keywords: disadvantaged districts, hedonic models, housing prices, spatial econometrics, urban development policies

In this article we suppose that the integration of accessibility and neighborhood variables in hedonic housing models doesn't allow to take into account the spatial effects between the housing prices. Using a sample of 1520 transactions of apartments in the urban area of Dijon, we focus on two types of location variables : the distance to the CBD and the distance to several Disadvantaged Districts located in peripheral areas. We detect the presence of a spatial error autocorrelation in the hedonic model indicating that the valuation of the price of an apartment is locally influenced by the prices of the neighboring apartments.

Then, we estimate a spatial error model which shows that the local effect is positive and significant and that the location variables remain significant : housing prices are positively influenced by the accessibility to the CBD but are negatively influenced by the proximity to a D-District.

L'objectif de cet article est de montrer comment l'influence du voisinage peut être intégrée dans les modèles hédoniques de prix immobiliers. Deux approches complémentaires sont utilisées. Des variables explicatives d'accessibilité au CBD, d'appartenance aux quartiers sensibles et de proximité aux quartiers sensibles sont intégrées dans les spécifications hédoniques que nous estimons : les effets "globaux" de ces variables peuvent donc être appréciés. Nous estimons ces modèles hédoniques en tenant compte des effets de dépendance spatiale susceptibles d'exister entre les prix des propriétés voisines : un effet local de voisinage est alors supposé sous la forme d'une àutocorrélation spatiale dans les modèles hédoniques estimés. Cette démarche est appliquée à un échantillon de 1520 transactions d'appartements sur la Communauté de l'Agglomération Dijonnaise en 1999 et permet de montrer qu'un effet de dépendance spatiale existe entre les prix immobiliers : le modèle hédonique approprié à estimer est un modèle spatial avec autocorrélation des erreurs. Cet effet spatial existe alors même que les variables explicatives d'accessibilité au CBD et de proximité avec les quartiers d'habitat social sont intégrées dans le modèle hédonique. Nous montrons que l'effet spatial local est positif et que les prix des appartements décroissent quand la distance au CBD augmente, que l'appartenance à un quartier d'habitat social déprécie ces prix et que la proximité à un tel quartier a également un effet négatif sur les valeurs des transactions.

Mots Clés : modèles hédoniques, économétrie spatiale, prix immobiliers, quartiers sensibles, politiques urbaines

Intro d u c t io n

Hedonic models have been used widely for estimating housing values ^epending on a large set of housing attributes and generally grouped in three subsets : 1 / structural variables describing housing physical characteristics, 2/ neighborhood or environmental variables depicting the quality of amenities and the economic and social characteristics of the housing neighborhood and 3/ accessibility variables including distances to major employment centers, to major amenities (recreation and shopping facilities, particular sites, major public utilities...), to road infrastructures and transport access (railway stations, subway stations, major streets, highways, airports...).

Hedonic housing price equations are mainly estimated to produce the best relevant evaluation of the housing price distribution and of the implicit price of each attribute in order to obtain the best reliable forecasts. These estimations are major inputs in the investigation of housing market by the construction of house price indices and by the analysis of consumer demand for attributes. As indicated by the abundant literature on hedonic housing price models, such studies find numerous applications in business, economic and social fields linked to real estate investment decisions, mortgage markets, housing policies and programs, local tax policies, urban environmental planning and urban development.

The precision and the reliability of the estimations are affected by many factors including the selection of attributes, the functional form of the hedonic function, the econometric techniques used and statistical assumption on the dependant variable, on the explanatory variables and on the random error terms (Sheppard, 1997). In this paper, we focus on the way that urban housing value models and their econometric estimations are affected by spatial effects. Spatial autocorrelation and spatial heterogeneity, for instance, are effects known to result in a number of estimation problems : the presence of spatial autocorrelation yields inconsistent and inefficient OLS estimators and spatial autocorrelation often jointly occurs with spatial heterogeneity in spatial processes [START_REF] Anselin | Spatial Econometrics: Methods and Models[END_REF][START_REF] Anselin | Spatial econometrics[END_REF]. Hedonic models of housing prices are concerned by spatial effects with at least three major reasons.

-Housing is a durable good with a fixed location. First, according to theoretical urban economic models, the housing equilibrium location depends on the accessibility to the major economic center (CBD) and housing prices decrease as the distance to the CBD increases. Second, the real estate property capitalizes the amenities in its neighborhood and its price may be affected by neighborhood developments and changes. Then, real estate properties within the same neighborhood capitalize shared location amenities: neighborhood characteristics and proximity externalities. Third, houses and buildings within a neighborhood have often been built at the same time and tend to have similar structural characteristics. As a result, housing prices could be spatially autocorrelated.

-Spatial heterogeneity may occur if, for example, the coefficients are different depending either on the distance from the CBD (considering an isotropic or an anisotropic space), or on a spatial regime structure or on other forms of spatial segmentation. In the latter case, the spatial segmentation can be based on the districts of the urban area according to the characteristics of housing (historic or new properties) or to the characteristics of the population (household income, race, rate of unemployment...). In addition, spatial heterogeneity and spatial autocorrelation may be observationally equivalent [START_REF] Anselin | Spatial econometrics[END_REF] when, for example, a spatial cluster of high housing prices in one district and of low housing prices in an other district may be interpreted as heterogeneity between these districts or as a spatial autocorrelation process yielding clusters of similar values. Moreover, we know that spatial autocorrelation in residuals may result from a spatial heterogeneity that is not correctly modeled in the hedonic price equation.

-Many neighborhood and accessibility explanatory variables are difficult to measure because they are unobservable (like the quality of public facilities), complex (the level of criminality or violence, the social and economic composition of a district) or because they depend on the prior identification of major areas and places (CBD and major employment subcenters, major recreational places, major particular sites...) and the way accessibility to them can be measured. In addition, these variable are rarely available in data bases. Even if relevant and reliable data were available, the problem of the identification of the relevant neighborhood boundaries may remain (Dubin, 1992, Basu and[START_REF] Basu | Analysis of Spatial Autocorrelation in House Prices[END_REF]. Selecting the best set of explanatory variables and the correct model specification are also difficult. Then the residuals produced by housing price hedonic models may be correlated due to measurement errors on the variable, omitted variables or other forms of hedonic model misspecifications.

Despite the fact that hedonic housing price models include accessibility or neighborhood variables, which tend to introduce spatial effects into the modelling and estimating processes, only a few empirical studies have applied appropriate econometric techniques to detect and take into account such spatial effects. Taking care of spatial effects means that even when neighborhood and accessibility variables are included as explanatory variables in housing value functions, spatial dependency might remain: spatial econometric estimators provide in that case more reliable inference than OLS estimators. Spatial autocorrelation effects have been modeled in different ways focusing either on spatial models [START_REF] Anselin | Spatial Econometrics: Methods and Models[END_REF] or on geostatistical models [START_REF] Dubin | Spatial Autocorrelation and Neighborhood Quality[END_REF]. In the first approach, spatial dependencies in the data or in the residuals are described by an exogenous spatial process whereas they are not based on any had-hoc specification in the second approach. In both cases it is shown that using spatial econometric techniques is better than ignoring the dependencies in the data (Dubin, 1998[START_REF] Pace | Using the spatial configuration of the data to improve estimation[END_REF][START_REF] Lesage | Spatial Econometrics[END_REF]. Taking into account spatial autocorrelation improves the estimates and the forecasts on real estate markets, is a substitute of omitted variables or makes it possible to capture spillovers effects and spatial externalities (see for example, Anselin, 2002;[START_REF] Beron | Hedonic price functions and spatial dependence: implications for the demand for urbain air quality[END_REF]Can and Megboluge, 1998;[START_REF] Dubin | Spatial Autocorrelation and Neighborhood Quality[END_REF]Dubin, , 1998;;Gilley and al., 2001;[START_REF] Lesage | Spatial Modeling of Housing Values in Toledo[END_REF][START_REF] Lesage | Spatial Econometrics[END_REF][START_REF] Lesage | Models for spatially dependent missing data[END_REF]McMillen, 19951;[START_REF] Pace | Using the spatial configuration of the data to improve estimation[END_REF]Tse, 2002). In addition to spatial autocorrelation, the question of spatial heterogeneity has been widely treated by the use of explanatory variables indicating the existence of housing sub-markets [START_REF] Basu | Analysis of Spatial Autocorrelation in House Prices[END_REF][START_REF] Wilhelmsson | Spatial Models in Real Estate Economics[END_REF] or spatial regimes (Pâez and al., 2001).

Considering these principles, the aim of the paper is to analyze the spatial distribution of housing prices in the Communauté de ('Agglomération Dijonnaise (which is the cornurbation of Dijon, the regional capital of Burgundy in France) and to examine whether spatial effects influence housing prices focusing on the estimation of an hedonic function. More precisely, we are interested in three topics: 1 / studying the spatial characteristics of the housing price distribution in the COMADI, 2/ modelling spatial autocorrelation using spatial econometric specifications [START_REF] Anselin | Spatial Econometrics: Methods and Models[END_REF][START_REF] Lesage | Spatial Econometrics[END_REF] and 3/ estimating the implicit prices of neighborhood and accessibility variables taking care of the spatial residential pattern produced by two different urban development policies, the first one being devoted to a Conservation Area Plan in the core of the COMADI and the second one to social housing programs in peripheral disadvantaged-districts.

The paper is organized as follows. In the following section, we describe the data and the residential patterns of the COMADI. In the third section, we present the spatial weight matrix describing the spatial dependence process and we analyse the spatial pattern of housing prices using exploratory spatial data analysis. We detect some clusters of low housing unit-price values in the disadvantaged-districts while clusters of high housing unit prices tend to be centrally located. In the fourth section, we provide a spatial econometric analysis of hedonic housing price functions including housing attributes, neighborhood characteristics and accessibility variables. More precisely, we estimate a spatial error model and show that the influence of the disadvantaged districts on the housing price values is significant and negative. The paper concludes with a summary of key findings.

Residential pattern s in th e COMADI

Our study focuses on a middle-sized French urban area named COMADI (Communauté de l Agglomération Dijonnaise), which is located in the region of Burgundy. A community of agglomerations is composed of several towns adjacent to a major city. It's a kind of large town council. More precisely, the COAAADI is composed of 16 adjacent towns: the central city Dijon, which is the capital of Burgundy, and 15 suburban towns: Ahuy, Chenôve, Chevigny-Saint-Sauveur, Daix, Fontaine-lès-Dijon, Longvic, Marsannay-la-Côte, Neuilly-lès-Dijon, Ouges, Perrigny-lès-Dijon, Plombières-lès-Dijon, Quetigny, Saint-Apoltinaire, Sennecey-lès-Dijon and Talant. The spatial configuration of the COMADI area is displayed in Map 12. With almost 250,000 inhabitants, the COAAADI is the largest French community of agglomerations located between Paris (the largest French conurbation with almost 10 millions people) and Lyon (the second one with almost 2 millions people). Moreover, the COMADI can be considered as a conurbation structuring the Metropolitan Area (MA) of Dijon, which is composed of 214 towns in 1999 for a total surface of 561,156 acres and 327.000 inhabitants. The COMADI concentrates 73% of the population of the MA, 86% of the MA employment and more than 90% of the jobs in the tertiary sector. As the strongest urbanized area of its Metropolitan Area, the COMADI concentrates more than 76% of the housing and the concentration is even more important for the apartments (97.2%) than for the single-family homes (50%). Under these conditions, when an household prefers living in an apartment, he simultaneously chooses to live in the COMADI: household's location preferences express the quality of the neighborhood and accessibility characteristics of each location compared to that of the other locations within the COMADI. On the contrary, when the household prefers living in a single-family home, he can choose to live in the COMADI or outside the COMADI: then household's location preferences express the quality of the neighborhood and accessibility characteristics of each location compared to that of the other locations within and outside the COMADI. Since we restrict our study to the COMADI area we attempt to detect whether spatial effects influence the housing prices or not, analyzing the price of houses would be biased. In addition, we know that the single-home family market and the apartment market are characterized by specific attributes. Hence focusing on only one type of housing allows to preserve the homogeneity of the sample. The data used in our studies are described in the following paragraph. Then we present the major urban development policies implemented by the COMADI for 40 years and we show that they have lead to two specific types of areas: the Conservation Area and the Disadvantaged-Districts.

H o u s in g d a t a a n d e x p l a n a t o r y v a r ia b le s

Spatial autocorrelation in housing prices and in hedonic housing price models are studied using data for transactions of apartment sold in 1999 in the COMADI. Housing data are extracted from the file "Marché Immobilier des Notaires" provided by the "Chambre Départementale des Notaires de Côte d'Or". Since we focus only on sold properties, it is not possible to apply our estimated results without selection bias to the entire distribution of apartment values in the COMADI (LeSage and [START_REF] Lesage | Models for spatially dependent missing data[END_REF]. The selection bias results from the fact that the transactions may concern only apartments which have specific characteristics (Tse, 2002). In fact there are about 29.000 houses and 73,500 apartments in the COMADI and total housing transactions concerned 3% of them in 1999 (2,496 transactions of apartments and 687 transactions of single-family homes). Finally our sample contains 1,520 transactions of apartments for which the transaction price and some major structural characteristics are available.

The characteristics of the property are described by the living area, the number of rooms, the address3, the period of construction (distributed into seven cycles of construction), the number of bathrooms and the presence of a storeroom, of a cellar, of a balcony or of a terrace.

The neighborhood characteristics are measured by census tracts variables available at the IRIS scale (an intra-urban subdivision for statistical information based on population and economic levels4). IRIS data are provided by the Direction Régionale de l'INSEE (French national statistics institute). The COMADI is divided into 114 IRIS (see Map 1 for a picture of the IRIS scale): at least one transaction occurred in 1999 in 92 of them. Each IRIS can be considered as a sub-market for neighborhood variables associated to the apartment: the population density, the unemployment rate, the percentage of employees, the percentage of middle executives, the percentage of senior executives and professors and the percentage of the foreign population. Let us note that other variables measuring the quality of neighborhood amenities are generally taken into account in housing studies: the distance to the nearest park, the distance to the nearest elementary or primary school, the distance to the nearest junior high school, and the distance to the nearest shopping center. In the COMADI, there are 27 shopping centers, 98 elementary and primary schools, 29 junior high schools and 34 parks. Since the COMADI area is small (42,600 acres), we can consider that all housing are located close to these amenities and public facilities and that including these distance variables would be at best not very significant and would result in multicolinearity problem at worst [START_REF] Heikkila | Multicolinearity in Regression Models with Multiple Distance Measures[END_REF].

Map 1 : The 114 IRIS of the COMADI Finally, two types of accessibility variables are considered: the distance to the main economic center (CBD), centrally located in the COMADI, and the inverse distance to the nearest employment subcenter (Table 2b displays the IRIS composition of the CBD and of each employment subcenter).

All variables are presented in Table 1. Using the set of neighborhood variables previously described and supplemented by census housing data available at the IRIS scale, different characteristics of the D-Districts and of the Conservation Area can be underlined (Table 3)5. First we can note that some opposite features characterized the Conservation Area, on one hand, and the D-Districts, on the other hand. For example, the Conservation Area is characterized by an high percentage of senior executives and professors (28,4% against 15,8% for the COMADI and less than 7% for the D-Districts), a low percentage of employees (22% against 31% for the COMADI and more than 32% for the D-Districts), a very low ratio of foreign people (4,7% against more than 8,7% and rising up to 17,6% in the D-Districts), a high percentage of old buildings and apartments (82% of the apartments have been built

H o u s in

before 1949) and a very low percentage of social housing (5,3% against 22% for the COMADI, more than 51% and rising up to 78% for the D-Districts). The Conservation Area concentrates a large part of the employment whereas the D-Districts are poorly developed. Second, the two types of areas have similar characteristics: high population densities (50 inhabitants per acres on average against less than 6 inhabitants per acres for the COMADI), similar percentages of middle executives (which are lower on average than those observed for the COMADI) and similar rates of unemployment (10% on average excepted for the D-District in Chenove which is higher: 19%). Since housing prices may capitalize location characteristics and spatial externalities it would be interesting to highlight the potential influence of D-Districts, on one hand, and of the Conservation Area, on the other hand, on the housing price distribution in the COMADI. For that purpose, we consider two additional neighborhood variables indicating whether the apartment is located in a Disadvantaged-District or in the Conservation Area (see Table 1). Some studies interested in this purpose (for example, [START_REF] Johnson | CBD land values and multiple externalities[END_REF] analysed the impact of the historical area on the land values in the New Orleans CBD) but without taking the impact of spatial effects into account. The spatial statistical tools used to examine these features are presented in the following paragraphs.

Ex p l o r a t o r y s p a t ia l a n a l y s is o f t h e h o u sin g p r ic e d is t r ib u t io n

Patterns of local spatial association describing spatial autocorrelation and spatial heterogeneity which may characterized the price distribution of the apartments in the COMADI are analysed by the means of Exploratory Spatial Data Analysis (ESDA).

.1 . THE SPATIAL WEIGHT MATRIX

For studying spatial dependency in housing price distribution and in hedonic housing price equations, it is necessary to incorporate a spatial structure, the well known W weight matrix, exogenously defined, which quantifies the way that an observation at one location depends on other observations at a number of other neighboring locations: it is based on the existence of spillover effects between observations. Each apartm ent; is connected to a set of neighboring apartments j according to a spatial pattern defined exogenously. The elements wu on the diagonal are set to zero whereas the elements wtj indicate the way the unit i is spatially connected to the unit j .

These elements are non-stochastic, non-negative and finite. In order to normalize the outside influence upon each unit, the weight matrix is standardized so that the elements of a row sum up to one. Several types of spatial structure can be used: contiguity, nearest neighbors, distance-based functions. Since distance variables are included as explanatory variables, using a distance-based W matrix (such as an inverse distance W matrix) could produce some kind of multicollinearity between the spatial structure and the explanatory variables that makes interpretation and inference problematic [START_REF] Wilhelmsson | Spatial Models in Real Estate Economics[END_REF]. Hence we prefer describing the spatial structure by a fc-nearest neighbors W matrix.

The general form of a k-nearest neighbors weight matrix W(k) is defined as follows:

w* (k ) = 0 i f i = j, \/k < w* (k ) = 1 i f d v < d, (k ) and wy (k ) = w* (k ) / £ w*. (k) w *(k ) = 0 i f d l} > d t(k )
where wtJ (k ) is an element of the standardized weight matrix and d t (k ) is a critical cut-off distance defined for each unit i. More precisely, dt(k ) is the fcth order smallest distance between unit / and all the other units so that each unit / has exactly k neighbors. To choose the number of nearest neighbors, we have applied the following procedure. We have estimated by OLS the hedonic housing price functions used in the paper. We have tested the presence of spatial autocorrelation by the means of Moran's I statistic using N matrices of k-nearest neighbors (N varying from 1 to 20), It appears that the value of the statistic reached a maximum for N = 7. Then we choose the spatial W matrix corresponding to k = 7 nearest neighbors.

Spatial a u t o c o r r e l a t io n in t h e h o u sin g price distributio n

Considering the distribution of housing unit prices (measured in € per square meters), two types of spatial association are tested: global spatial autocorrelation and local spatial association.

If we consider global spatial autocorrelation, which is usually based on Moran's / statistic (Table 4.)6, it appears that housing unit prices are positively spatially autocorrelated at p = 0.0001 significance level7. This result indicates that similar values (high or low) of housing unit price tend to be spatially clustered in the COMADI.

( I) = -1/(«-!) = -6,6x10^ (n = 1520)
Moran's I is a global measure and doesn't allow to appreciate the local patterns of spatial association, i.e. to detect the presence of clusters of high unit price values or of low unit price values in the COMADI. In addition, some apartments might be sold at a low unit price (resp. high unit price) whereas neighboring apartments were sold at high unit prices (resp. low unit prices), reflecting some atypical spatial associations compared to the global pattern of positive spatial autocorrelation.

Inspection of local spatial associations is carried out by the means of Moran scatterplots and

Local Indicators of Spatial Associations [START_REF] Anselin | Local indicators of spatial association-LISA[END_REF][START_REF] Anselin | The Moran scatterplot as an ESDA tool to assess local instability in spatial association[END_REF] The local version of Moran's I statistic for each observation i is written as: where is the unit price of the observation i ; n = 1520; // is the mean of the observations and where the summation over j is so that only the unit prices of the neighboring apartments of /, defined by the spatial W matrix, are included: in our case, the unit prices of its 7 nearest apartments are taken into account for each apartment f. A positive value for /, indicates spatial clustering of similar values (high or low) whereas a negative value indicates spatial clustering of dissimilar values between a apartment and its neighbors. Due to the presence of global spatial autocorrelation, inference must be based on the conditional permutation approach with 9 999 permutations. The p-values obtained for the local Moran's statistics are then pseudo-significance levels. Note that inference in this case is further complicated by the problem of multiple comparisons since the neighborhood sets of two spatial units contain common elements [START_REF] Anselin | Local indicators of spatial association-LISA[END_REF]Ord and Getis, 1995). Therefore, the overall significance of 5% is not restricted enough and lower significance levels taking into account the number of multiple comparisons have to be used. The Bonferroni's correction is often suggested and consists in dividing the nominal level of significance a by the number of observations. Since this correction becomes too restrictive as the sample size increases, one can also consider that the [1] number of multiple comparisons depends on the type of W matrix used: in the case of a k nearest neighbors W matrix, the maximum number of multiple comparisons between two observations is k and the significance level is obtained by dividing a by k (Le [START_REF] Gallo | Exploratory Spatial Data Analysis of the distribution of regional per capita GDP in Europe, 1980-1995[END_REF]. For the 7 nearest neigbhbors W matrix, the pseudo significance level is p = 0.00714. The estimation of hedonic housing price functions allows us to investigate these points.

Estim a t in g r e su lt s o f Hed o n ic h o u sin g price m o d e l s

Taking into account structural, neighborhood and accessibility variables in hedonic housing price models, allows to evaluate and to test different assumptions. First, we can estimate consumer's willingness to pay for housing attributes and neighborhood quality. Second, we can test at least two urban economic theoretical results. On one handwe expect that in a monocentric urban area, the unit price of housing decreases from the CBD. On the other hand, we expect that in a polycentric urban space, the unit price distribution exhibits a global peak near the CBD and local peaks near secondary employment centers. Moreover, it is generally assumed that the CBD has a global influence on housing price levels whereas employment subcenters compete with each other and have a local influence on these prices. In housing value models, these two levels of influence are distinguished by including the distance to the CBD and by including the inverse distance (or inverse squared distance) to the nearest employment subcenter (see for example, [START_REF] Sivitanidou | Do office-commercial firms value access to service employment centers? A hedonic value analysis within polycentric Los Angeles[END_REF]. Using [START_REF] Giuliano | Subcenters in the Los Angeles region[END_REF] identification method based on employment density and total employment cut-offs, [START_REF] Baumont | Centres secondaires et recomposition économique des espaces urbain, le cas de la Communauté de l'Agglomération Dijonnaise[END_REF] identified three employment subcenters:

one located in the North, one in the South and the other one in the business district of Quetigny (the IRIS composition of each subcenter is displayed in Table 2b). Using spatial econometrics procedures, Baumont and al. (2003) showed that these subcenters didn't influence the population density distribution in the COAAADI. However, it is interesting to study if the housing price distribution, which is a more flexible variable than intra-urban population density distribution, is influenced both by the distance to the CBD and by the distance to these employment subcenters. where P is the (nxl) vector of the housing prices, A is a (nxj) matrix of structural attributes of the apartment (plus the constant), N is a (n x / ) matrix of neighborhoods characteristics, D is a (nxq) matrix of accessibility variables, a , ¡ 3 and ^are, respectively, j, t and q length vectors of unknown parameters to be estimated and e is a random error vector with the usual properties.

Following the hedonic modeling literature, we use the log-transformation on the dependent variable and on the explanatory variables (the dummy variables excepted) so that estimated parameters can be interpreted as elasticities. The percentage impact on the housing price of a change in the dummy variable from 0 to 1, is calculated from the corresponding estimated parameter d as follows [START_REF] Halvorsen | The interpretation of dummy variables in semilogarithmic equations[END_REF]: 100* (exp(<i) -1 ).

Following the spatial econometric literature, two usual spatial models can be specified: a spatial lag model (LAG) and a spatial error model (SEM).

Given the exogenous spatial structure W, the spatial lag model is:

PX = pWPX + Acc + N/3 + Dy + s £ ~ N(0,o-2/) [3]
where the estimated parameter p measures the spatial dependence of observations.

The spatial error model is:

PX = Aa + N fi + Dy + e e = XWe + u u~ N(0,<t27) [4] where X is the scalar parameter expressing the intensity of spatial correlation between regression residuals.

Both specifications seem possible a priori. In the LAG model, spatial autocorrelation of observations is handled by the endogenous spatial lag variable WPX and expresses the fact that the price of an apartment is influenced by the price of the neighboring apartments. In the SEM model, we consider spatial dependence as a statistical nuisance which may occur from various forms of misspecification (omitted variables, the lack of adequate neighborhood measures...).

Ignoring spatial dependence when it is present produces OLS estimators at best inefficient (if model [2] is estimated by OLS whereas [4] is the true model) and at worst biased and inconsistent (if the true model is [3] and [2] is estimated by OLS) [START_REF] Anselin | Spatial Econometrics: Methods and Models[END_REF]. The parameters of both spatial models are generally estimated with the method of Maximum likelihood (ML). In the case that estimates for p or X are significant, spatial autocorrelation may be interpreted as a spatial externality whose intensity depends on the estimated values of the parameters.

Since our aim is to deal with the general impact of spatial dependence in the estimation of hedonic housing price models, we estimate equation [2] by OLS, perform different spatial tests and apply the specification search approach defined by [START_REF] Anselin | Small sample properties of tests for spatial dependence in regression models[END_REF] to discriminate between the two forms of spatial dependence10 (spatial autocorrelation of errors or endogenous spatial lag).

Estimating r esu lt s

In order to focus on the impact of the Conservation Area and of the D-Districts on the housing price values, we include the variables D-District (or MinD-D) and C-AREA in the hedonic functions.

To avoid some multicollinearity problems in our estimations, we don't include the variables correlated with these two types of area: AN4869, AN7080, PEXEC, PWK, FOREIGN and DPOP. Neither do we consider AP91 because our sample contains only 41 apartments built after 1991. 6.

The model explains 78% of the variation in price and if one were to assume no spatial autocorrelation problem, the results of the OLS estimation suggest the following interpretations. If living area increases by 1%, price will increase by 0.96%. If the percentage of middle executives living in the IRIS where the apartment is located increases by 1%, the price will increase by 0.19%. If the distance to the CBD increases by 1%, then the price will decrease by 0.056%. This result confirms that the accessibility to the major employment center has a strong influence on housing price (let us recall that the distance is measured in meters). This effect probably dominates the influence of the accessibility to an employment subcenter since, as previously noted, the variable [START_REF] Anselin | Spatial Econometrics: Methods and Models[END_REF]. LR-error is the likelihood ratio test for the spatial error parameter.

However, let us note that even if it is significant, this impact is local and is smaller than the global effect of the CBD (let us recall that distance is measured in meters in both cases). The spatial tests indicate that a spatial autocorrelation of the errors affects the estimates. We then estimate the SEM model by ML and GMM. The results are displayed in the two last columns of the Table 7. The value of X is significant and positive (X = 0.447) and no additional autoregressive spatial lag is detected. Some variations in the values of the parameters can be observed: once All these results illustrate the fact that ignoring both spatial dependence across the observed sale prices and the effect played by an housing urban policy leads to wrong evaluations.

They also underline that the form takes by the negative influence of the D-Districts is not neutral, which results in different policy implications. In the first specification, one consider that the negative spatial externality produced by the D-District doesn't spread out: the price of an apartment located outside a D-District is not affected and we can consider that the housing market is segmented. On the contrary, the second hedonic function assumes a cross effect between housing sub-markets: to be located outside a D-District doesn't preserve from its depressive effect and it's better to be located far from a D-District than close to it. Moreover we also show that even if location is taken into account by the mean of accessibility and dummy variables, a spatial effect remains indicating that housing prices in each location are influenced by the housing prices in neighboring locations: local processes have to be added to the evaluation of housing prices.

C o n c l u s io n

In this paper, hedonic housing price functions take into account both spatial effects and neighborhood effects. Our results indicate that the inclusion of accessibility variables and neighborhood characteristics doesn't take all the spatial effects into account. Considering the fact that a neighborhood variable can be used to model the impact of the housing urban policies on the residential pattern of the COAAADI, we have underline the role played by the social housing programs developed during the sixties and the seventies. If the negative influence of the D-Districts on the housing price spreads out towards the CBD, then the positive effect produced by a better accessibility to the Conservation Area is reduced.

Our analysis can be developed in at least three directions.

First, we haven't investigate the presence of spatial heterogeneity or the presence of outliers. It could be done by the use of Spatial Bayesian models as suggested by [START_REF] Lesage | Spatial Econometrics[END_REF].

Second, our results depend on the spatial structure described by the W weight matrix. We chose a 7 nearest neighbors W matrix since we thought that a distance-based W matrix took too many observations in downtown COMADI and not enough in the peripheral areas. On the contrary, choosing a fixed number of neighbors doesn't allow to capture the spatial variations of the sold apartment distribution. It appears that a density-based W matrix could be more appropriate.

Third, the presence of spatial externality could be further investigated considering a larger set of sub-markets if we think that other types of urban development policies have produced specific neighborhoods. In the same manner, we can take a land-use competition effect into account to discriminate between areas where multiple land uses are allowed from those where only one landuse is allowed (residential land use in fact in our case since we don't consider office transactions data)

  g a n d U r b a n d e v e l o p m e n t p o l ic ie s in t h e COMADI Since the beginning of the sixties, two types of urban development policies have structured the spatial residential pattern of the COAAADI giving its main current features.In the sixties and in the seventies, many development operations, sustained by the economic growth and the demographic expansion which had followed the WW2, have been realized where land-use zoning and gigantic proportions were the rule: residential districts in some places, large industrial or commercial areas in other places and major public services and urban amenities in some other places. The urbanized areas doubled in 25 years and two major forms of urban sprawl covered peripheral districts. On one hand, several social housing programs, characterized by highrise buildings, took place in the districts of "Fontaine d'Ouche" and "Les Grésilles" located in the city of Dijon, in the city of Talant ("Belvédère" district), in the city of Chenôve and in the city of Quetigny. On the other hand, the main industrial and commercial districts were developed in the North, in Chenôve and in Quetigny. It was the beginning of the sub-urbanization of the population and of the emergence of employment subcenters (see Map 2 and

  Map 2: The COMADI The Conservation Area, the D-Districts and the Employment Centers The Conservation and Improvement Plan aims at "improving the quality of life in the core of Dijon" following three major guidelines. 1/To conserve and renovate old buildings respecting their architectural characteristics and to highlight them by the development of their neighborhood. 2/ To improve housing in central areas by the rehabilitation of old buildings (by means of OPAH: Planning Operations for Housing Improvement) and by the construction of new buildings in the spirit of the architectural characteristics of the patrimony. Atore than 1,200 old apartments have been rehabilitated and 500 new apartments have been built in 15 years. 3/ To develop the cultural and economic attractiveness of downtown Dijon and to improve its accessibility by some specific actions allowing to solve street congestion problems. In the eighties, the city council chose to restrict car traffic flows in the inner streets, to built 5 new parking lots located at the boundaries of the conservation area and to develop urban public transportation. Many streets and public areas were converted into pedestrian areas and pedestrian shopping streets. Terraces of Cafés and pavements now replace outside parking lots. The pedestrian area covers 70% of the conservation area. The attractiveness of downtown Dijon contrasts with the bad social and economic situation in the social housing districts developed during thirty years in the peripheral districts to face the population growth (see Table 2.a). These districts, hereafter named Disadvantaged Districts (D-Districts) are mainly characterized by a lack of public facilities and stores, a poor quality of environment, a strong degradation of housing, strong parts of immigrant population and of low-income households, a fast growth of criminality and offences... (see Map 2). These problems have lead the urban planners at national, regional and communal scales, to elaborate at the end of the nineties, specific development urban policies for the D-Districts named Urban Renewal Operations and Major Urban Projects in which financial groups like the Caisse des Dépôts Group and local banks are strongly implicated. These projects in favor of D-Districts relate mainly to the redevelopment of large-scale social housing complexes by means of demolition, construction and renovation operations, to the supply of public facilities transportation infrastructure and to the promotion of economic activities and job development by means of public subsidies to improve the accessibility and the attractiveness of the urban renewal districts.

  8. In a Moran scatterplot the values of a spatial lag variable Wz are plotted against the values of the variable z. It aims at visualizing four types of local spatial association between an observation and its neighbors, each of them being localized in a quadrant of the scatterplot: quadrant HH refers to an observation with a high9 value surrounded by observations with high values, quadrant LH refers to an observation with low value surrounded by observation with high values, etc. Quadrants HH and LL (resp. LH and HL) indicate positive (resp. negative) spatial autocorrelation reflecting spatial clustering of similar (resp. dissimilar) values.In order to assess the significance of such spatial associations, Local Indicators of Spatial Association (LISA) statistics are computed.

8

  The identification of local patterns of spatial association can also be based on the Gj(d) statistics (Getis and Ord, 1992; Ord and Getis, 1995; Getis and Ord, 2001). 9 High (resp. low) means above (resp. below) the mean.

Finally, a

 a Moran significance map combines the information in a Moran scatterplot and the significance of LISA by showing the apartments with significant LISA and indicating by a color code the quadrants in the Moran scatterplot to which these apartments belong.Applying these tools to the housing unit price distribution leads to the following results (seeTable 5.). First, it appears that more than 70% of the prices are characterized by spatial positive local associations (513 apartments in quadrant HH and 553 apartments in quadrant LL) while the other observations are characterized by spatial negative local associations (197 apartments in quadrant HL and 257 apartments in quadrant LH). At the 5% pseudo-significance level, 33% of the observations are still characterized by a local spatial association (185 apartments are significantly HH, 228 apartments are significantly LL, 30 apartments are significantly HL and 52 apartments are significantly LH). Using the Bonferroni's correction, 14% of the observations exhibit significant local associations using at the p= 0.00714 pseudo-significace level and among them 34% are of HH type and 56% are of LL type. These results show evidence of several pockets of low transaction prices or of high transaction prices in the COMADI and the location of the respective apartments are given in two Moran significance maps (Map 3 for HH and HL, and Map 4 for LL and LH).

Map 3 :

 3 Moran significance Map for HH and HL spatial association (p = 0.00714; 7 nearest neighbors W matrix) Moran significance Map for LL and LH spatial association (p = 0.00714; 7 nearest neighbors W matrix) that our sample contains 223 apartments sold in the Conservation Area and 178 apartment sold in the D-District, we can underline that a pattern of significant local spatial association is more often observed in the latter than in the former. Moreover, no apartment located in the D-Districts is of HH type and no apartment located in the core of Dijon is of LL type. On the contrary, almost all the apartments located in a D-District are characterized by a significant spatial association of type LL whereas all the apartments located in the core of Dijon are of HH type or of LH type. Since 67% of the apartment sold there have been built before 1947, this feature possibly reflects bad conditions and the need of renovation. We also note that a local spatial association of HH type also characterizes transactions in areas located outside of the Conservation Area like the areas included in the CBD or located farther from the core of Dijon. Finally, these results highlight the important role played by spatial effects in the housing price distribution within the COMADI in two ways. First, housing unit prices are positively spatially autocorrelated, which indicates clusters of high (resp. low) housing unit price values in the COMADI. Second, specific neighborhood effects are reflected by the local spatial association patterns and are strongly linked to the D-Districts whereas the role played by the Conservation Area doesn't seem specific.

Finally, we can

  be interested in analysing whether the different urban development policies have produced different spatial externalities according to the type o f areas the apartment belongs to.

Finally

  , the exploratory variables included in the 3 matrices of housing attributes, neighborhood characteristics and accessibility variables are the following: A = [LSURF BATH AN5013 AN1447 AN8191 TERBAL] N = [LPMEXEC D-District (or MinD-D) C-AREA] D = [LDCBD INV-MinSUB] where LVAR designs the log transformation of VAR. To evaluate the influence of the D-Districts, we include either the D-District variable either the MinD-D variable. Instead of the dummy variable D-District, the MinD-D variable allows us to estimate the influence of being located close to a D-District. Taking the log transformation of the sale price (LPX), the results of estimation by OLS of the complete hedonic model indicates that the number of bathrooms (BATH), the location in the Conservation Area (C-AREA) and the accessibility to the nearest subcenter (INV-MinSUB) are not significant. Then these variables are no more considered and the results of estimation by OLS of the remaining hedonic model are given in the first column of the Table

  p-values are in parentheses. SEM-ML indicates maximum likelihood estimation of the spatial error model and SEM-GMM its estimation by the General Method of Moments. Sq. Corr. is the squared correlation between predicted values and actual values. LIK is the value of the maximum likelihood function. AIC is the Akaike (1974) information criterion. BIC is the Schwarz information criterion (1978). MORAN is the Moran's I test adapted to 0LS residuals (Cliff and Ord, 1981). LMERR is the Lagrange multiplier test for residual spatial autocorrelation and R-LMERR is its robust version. LMLAG is the Lagrange multiplier test for spatially lagged endogenous variable and R-LMLAG is its robust version (Anselin and Florax, 1995; Anselin et aL, 1996). LMLAG'is the Lagrange multiplier test for an additional spatially lagged endogenous variable in the spatial error model

  spatial autocorrelation is taken into account, the influence of the CBD is reduced and the influence of the proximity to a D-District is strengthened. Moreover, considering either the first model (colum 2) or the second one (colum 5) means that the influence of the D-Districts and of the CBD on the A housing prices may be different. If we define Px as the vector of the estimated prices with the first model and P2 as the vector of the estimated prices with the second model, we can evaluate the difference between the two estimated values. More precisely, we compute for each transaction the percentage of the difference between the estimated values produced by the first model and the second one : A P = [A p ;] designs the corresponding vector12. Map 5: Estimated prices using SEM1 or SEM2 12 For each transaction I, Ap, = 100---Pa Looking at the Map 5, we observe that the transactions characterized by the largest difference ( |Ap;-/iA/>|>2<XAP with //ap= -0.094 and <ta/>=4.08) are located closer to the D-Districts or in the peripheral residential areas. In the first case, the prices are upper estimated whereas they are under estimated in the second case.

Table 1 :

 1 Variable description

	Variable	Unit
	Structural attributes
	PX (transaction price)	€ (before tax)
	SURF (living area)	Square meters
	ROOM	Number of rooms
	BATH	Number of bathrooms
	TERBAL	Dummy (=1

if the apartment has a terrace or a balcony and 0 otherwise) CELSTO Dummy (=1 if the apartment has a cellar or a storeroom and 0 otherwise) BEF1850 (built before 1850) Dummy (=1 if the apartment was built before 1850 and 0 otherwise) ANaiaj (built between ai and aj) Dummy (=1 if the apartment was built between AN5013 year ai and year aj and 0 otherwise). AN1447 AN4869 AN7080 AN8191 AFT1991 (built after 1991) Dummy (=1 if the apartment was built after 1991 and 0 otherwise).

Neighborhood Variables (measured at the IRIS scale) UNEMP (unemployment rate) % PSEXEC %

of senior executives and professors PMEXEC % of middle executives PWK % of employees FOREIGN % of foreign inhabitants DPOP (population density) Nb of inhabitants per acre Neighborhood

Variables (urban development districts)

D-

District (Disadvantaged District) Dummy (=1 if the apartment is located in a D- District and 0 otherwise) MinD-D Distance to the nearest D-District C-AREA (Conservation Area) Dummy (=1 if the apartment is located in the Conservation Area and 0 otherwise) Accessibility Variables DCBD Distance to the CBD (in meters) INV-MINSUB Inverse distance to the nearest employment subcenter (in meters)

  On average, a apartment in the COAAADI is sold 64,575 Euros but the deviation from the mean is relatively high(o= 35,959). The smallest apartment has 11 square meters of living area and the largest one has 306 square meters. The average unit price is 1,042 Euros per square meters (c = 274). The sub-markets are not of equal size since the number of sales by IRIS varies from 1 to 51 transactions: 33 sub-markets have less than 10 transactions and 31 sub-markets have more than 20 transactions. Oldest sub-markets correspond to IRIS that are centrally located in the COMADI and they naturally have more apartment transactions than peripheral sub-markets where there are more single houses than apartments. 32% of the housing transactions concern apartments built between 1949 and 1969 against 29% for the built period 1970-1980. New apartments represent only 3% of the sample against 6% for the oldest apartments (built before 1850).Complementary insights of the residential development pattern of the COAAADI are drawn from the urban development policies implemented during the second half of the 20th century.

Let us note that to avoid multicollinearity problems, we don't consider the accessibility to the railway station since it is centrally located in the CBD. Neither do we consider accessibility to highways since we study housing values in the urban area bordered by these highways. Another reason to neglect accessibility to major infrastructure networks is that the COMADI area is small and that only a small part of the population living in the COMADI works outside the COMADI (11,6%): commuting outside COAAADI isn't time consuming.

  Table 2.b).At the same time, the Conservation and Improvement Area Plan, instituted by the AAalraux Law in 1962, has been elaborated and implemented: 295 acres in downtown Dijon are concerned by this plan and it is the largest French conservation area. This area named "Vieux Dijon" nearly corresponds to the medieval town where the major administrative buildings are located (Dijon City

	Hall, COMADI Council, Regional Council, Prefecture), together with the cathedral Notre Dame and
	several churches, the covered market and many old buildings with rich architectural features... The
	conservation area is a mixed area characterized both by high population densities and high

employment densities (see Table

2a

.). A part of the CBD is located there (see Map 2.).

Table 2

 2

		.a			Table 2.b
	Conservation Area and D-Districts	Employment Centers
	Conservation Area	Population	Employment	CBD	Population	Employment
		(dens/acre)	(dens/acre)		(dens/acre)	(dens/acre)
		14,488 (49.2)	8,082 (27.4)		5,799 (33.7)	9,644 (56.0)
	D-Districts	Population	Employment	Subcenters	Population	Employment
		(dens/acre)	(dens/acre)		(dens/acre)	(dens/acre)
	Chenove	10,896 (43.9)	508 (2.1)	South subcenters	422 (0.2)	11,540(4.5)
	Fontaine d'Ouche	10,283 (61.5)	660 (4.0)	North Subcenter	320 (0.1)	9,634 (3.7)
	Les Grésilles	8,239 (28.2)	748 (2.6)	Quetigny	204 (0.5)	4,014 (8.8)
	Quétigny	4,820 (34.4)	247 (1.8)
	Talant-Belvédère	5,736 (48.6)	206 (1.8)

Table 3 . Conservation Area and D-Districts : main features

 3

		Conservation	D-Districts	COMADI
	Characteristics	Area	Lowest	Highest
	PSEXEC (%)	28.4	4.1 (Chenôve)	6.9 (Belvédère)	15.8
	PMEXEC (%)	27.7	14.3 (Chenôve)	21.2 (Belvédère)	27.1
	PWK (%)	22.1	32 (Grésilles)	41.9 (Belvédère)	31.2
	DPOP (per acre)	49	28 (Grésilles)	62 (Fontaine d'Ouche)	6
	FOREIGN (%)	4.7	8.4 (Quetigny)	17.6 (Grésilles)	5.8
	UNEMP (%)	9.9	7.5 (Quetigny)	18.8 (Chenôve)	11.7
	DCBD (meters)		2,700 (Fontaine d'Ouche)	5,000 (Quetigny)
	Apartments (%)	71.2	72.6 (Grésilles)	91.9 (Quetigny)
	Vacant housing (%)	13.4	2.5 (Belvédère)	16 (Grésilles)	7.6
	Social apartments (%)	5.3	51 (Fontaine cTOuche)	78 (Les Grésilles)	22.2
	Major built period	Before 1949		Chenôve (AN49-74, 95%),
	(year and %)	(82%)	Fontaine d'Ouche (AN49-74, 89%)
				Grésilles (AN49-74, 77%)
				Quetigny (AN49-74, 49%),
				Belvédère (AN75-81, 97%)

Table 4

 4

	: M o ran's / statistics for housing unit price distribution in 1999
	Variable	Moran's 1	St. dev	St. value	p value
	Housing unit price*	0.3696	0.0128	28.93	0.0001
	* The expected value for Moran's I statistic is E

Table 5 :

 5 Spatial association patterns (LISA) for 7 nearest neighbors Second, we can see that many significant LISA are located either in the Conservation Area or in a D-District. More precisely (see Table6.), 70% of the significant LISA are located in those areas (48 LISA in the Conservation Area and 98 LISA in a D-District).

	USA		Nb obs		p = 0.05	p = 0.00714
	HH		513		185	71
	LL		553		228	116
	HL		197		30	7
	LH		257		52	14
	Total		1520		495	208
	Table 6: Significant spatial association patterns (LISA) in urban development Areas
		(p = 0.00714; 7 nearest neighbors W matrix)
	Areas	HH	LL	HL	LH	Total Nb. of transactions
	CVH	42			6	48	223
	D-Districts		96	2		98	178
	Other Areas	29	20	5	8	62	1119
	Total	71	116	7	14	208	1520

Table 7 :

 7 Estimates for the hedonic housing price function

	Dependent variable		Model 1			Model 2
	LPX	OLS	SEM-ML	GAAM	OLS	SEM-ML	GAAM
	Constant	8.69 (0.000)	8.749 (0.000)	8.753 (0,000)	8.317 (0.000)	8.409 (0.000)	8.413 (0.000)
	LSURF	0.964 (0.000)	0.961 (0.000)	0.961 (0.000)	0.963 (0.000)	0.962 (0.000)	0.961 (0.000)
	LDCBC	-0.056 (0.000)	-0.058 (0.000)	-0.058 (0.000)	-0.049 (0.000)	-0.044 (0.000)	-0.044 (0.000)
	D-District	-0.198 (0.000)	-0.169 (0.000)	-0.169 (0.000)
	MinD-D				6.663 10'5 (0.000)	7.305 10*5 (0.000)	7.273 10'5 (0.000)
	TERBAL	0.084 (0.000)	0.084 (0.000)	0.082 (0.000)	0.076 (0.000)	0.08 (0.000)	0.079 (0.000)
	AN5013	-0.097 (0.000)	-0.084 (0.000)	-0.085 (0.000)	-0.109 (0.000)	-0.088 (0.000)	-0.089 (0.000)
	AN1447	-0.077 (0.001)	-0.083 (0.000)	-0.083 (0.000)	-0.087(0.000)	-0.087 (0.000)	-0.087 (0.000)
	AN8191	0.199 (0.000)	0.166 (0.000)	0.166 (0.000)	0.203 (0.000)	0.167 (0.000)	0.167 (0.000)
	LPMEXEC	0.197 (0.000)	0.186 (0.000)	0.186 (0.000)	0.253 (0.000)	0.213 (0.000)	0.213 (0.000)
	X		0.433 (0.000)	0.428 (0.000)		0.447 (0.000)	0.444 (0.000)
	R*	0.784		0.767	0.783		0.77
	R2-adJ	0.783			0.782
	Sq.corr		0.783	0.783		0.782	0.783
	LIK	-44.142	-125.241		-39.481	-129.190
	AIC	70.285	232.48		60.963	240.379
	BIC	-22.347	-184.544		-13.025	-192.441
	O'2	0.055	0.049	0.05	0.056	0.049	0.049
	Condition number	65.309			65.154
	MORAN	13.753 (0.000)			14.749 (0.000)
	LMERR	178.575 (0.000)			205.702 (0.000)
	R-LMERR	111.301 (0.000)			131.331 (0.000)
	LMLAG or LMLAG*	73.099 (0.000)	6.34* (0.01)		79.497 (0.000)	5.793* (0.016)
	R-LMLAG	5.826 (0.016)			5.129 (0.024)
	LR-error		162.197 (0.000)			179.416 (0.000)
	Notes:

This paper aims at introduce spatial autocorrelation in selection models used to estimate the effect of the land-use zoning policies on land values.

Maps are created using Arc-View©3.2 software on the basis of maps provided by the Direction Régionale Bourgogne de l'INSEE.

The exact spatial location of each housing (i.e. x and y coordinates) has been calculated from its address. The authors are grateful to Julie Le Gallo and Rachel Guillain for these calculations.

INSEE defines three types of IRIS: residential IRIS, business IRIS and miscellaneous IRIS.

Detailed figures are available upon request from the author.

Computations are done with SpaceStat 1.90[START_REF] Anselin | SpaceStat, a software package for the analysis of spatial data[END_REF] or Matlab 6.5 using procedures presented in LeSage (1998) and in GEOXP.

Inference is based on the permutation approach with 9999 permutations.

The performance of that approach is experimentally investigated in Rorax and Folmer (1992) and in Florax, Folmer and Rey (2003).

related to the distance to the nearest employment subcenter was not significant. The estimates of the parameters associated to the dummy variable indicate that the sale of a apartment built between 1850 and 1913 (resp. between 1914 and 1947) decreases its price by 9.25% (resp. 7.44%) while the sale of a apartment built between 1981 and 1991 increases its price by 22%. Finally, if the apartment is located in a D-District, its price is reduced by 18%. Combining with the fact that D-Districts are located 3.5 kms in average far from the CBD, the location in a D-District strongly depreciates the value of a apartment in the COMADI. Looking at the five spatial tests, it is worth noting that the Moran's I test doesn't reject the absence of spatial autocorrelation. We perform the Lagrange Multiplier tests, LMERR, LMLAG and their robust versions R-LMERR and R-LMLAG [START_REF] Anselin | Spatial Econometrics: Methods and Models[END_REF][START_REF] Anselin | The Moran scatterplot as an ESDA tool to assess local instability in spatial association[END_REF] to discriminate between the two forms of spatial autocorrelation: spatial autocorrelation of error or endogenous spatial lag. Applying the decision rule suggested by [START_REF] Anselin | Small sample properties of tests for spatial dependence in regression models[END_REF], the results indicate the presence of spatial error autocorrelation rather than a spatial lag: the spatial error model appears to be the appropriate specification of the hedonic housing price function. Therefore, even when some neighborhood and accessibility variables are included, the hedonic housing price function is misspecified due to the omission of spatial autocorrelation of the errors and each observation is not independent of the others. Statistical inference based on OLS estimators is not reliable.

The estimates of the SEM hedonic housing price by ML and by iterated General Method of Moments (GMM)11 are given in the second and third columns of Table 7. It appears that all coefficients are strongly significant and that a significance positive spatial autocorrelation of the errors is found ( X = 0.433 ). Furthermore, the LMLAG* test does not reject the null hypothesis of the absence of an additional autoregressive lag variable in the spatial error model. The parameters values are slightly different than in the model estimated by OLS and the strongest variation occurs for the variable D-District. If the apartment is located in a D-District, then its price is reduced by 15%. On the contrary, the influence of the CBD is slightly stronger since the price decreases by 5,8% when the distance increases by 1%. For example, if we consider an apartment built between 1970 and 1980, with a living area of 100 square meters and a balcony, which is located in the D-District of Talant-Belvédère, its estimated price will be 80 127 € using the SEM model against 77 464 € using the OLS model. Considering that spatial effects don't matter in that case leads to under-evaluate the estimated price by 3,44%. Then the influence of the housing urban development policies is highlighted.

Another way to evaluate this influence, is to consider that the negative effect produced by the D-District may spread on the urban area. The estimate of the second hedonic function provides this evaluation by including the variable MinD-D instead of D-District. Since each apartment is characterized by its distance to the closest D-District, a local effect is assumed. The estimated results by OLS are displayed in the fourth column of the Table 7. We can see that the D-Districts produced a significant negative effect on the sate prices : when the distance from a D-District increase, the sale-prices increase too.

11 We estimate the model by GMM in order to control for the robustness of our estimates by ML for which a normal distribution of the errors is assumed.


Alessandro Lulli

Thibault Debatty

Matteo Dell'amico
email: matteodellamico@symantec.com

Pietro Michiardi

Laura Ricci

Scalable k-NN based text clustering

Clustering items using textual features is an important problem with many applications, such as root-cause analysis of spam campaigns, as well as identifying common topics in social media. Due to the sheer size of such data, algorithmic scalability becomes a major concern. In this work, we present our approach for text clustering that builds an approximate k-NN graph, which is then used to compute connected components representing clusters. Our focus is to understand the scalability / accuracy tradeoff that underlies our method: we do so through an extensive experimental campaign, where we use real-life datasets, and show that even rough approximations of k-NN graphs are sufficient to identify valid clusters. Our method is scalable and can be easily tuned to meet requirements stemming from different application domains.

I. INTRODUCTION

Data clustering and analysis is a fundamental task, that consists in finding groups of related data items, according to a definition of similarity that is application specific.

In this work, we focus on a particular data clustering task, which involves grouping text data items. The application domain of our work stems from the objective of analyzing SPAM campaigns: for instance, we focus on data collected by Symantec Research Labs, that perform root-cause analysis of large scale SPAM email campaigns originated from bot networks. In this adversarial context, data clustering is even more challenging, because spammers manipulate text to avoid SPAM emails being clustered the same campaign. Hence, the similarity metrics used for clustering must cope with text mangling, which require non-metric distances that disregard typos, character swapping, and other techniques to avoid detection. In addition, data clustering is challenging due to the large volume of data: this calls for the design of scalable algorithms, capable of ingesting millions of data points and cluster them in meaningful ways.

Current approaches fall short in addressing the above challenges. For example, the widespread K-means clustering algorithm requires text data to be transformed into d-dimensional vectors to operate correctly. However, such transformations generally imply high-dimensional vectors, which render distance functions problematic. Similarly, approaches for text clustering based on frequency analysis of shingles suffers from high-dimensionality problems. Moreover, the techniques discussed above are not amenable to non-metric spaces, which is a requirement for the application domain we study. As a consequence, clustering can perform poorly. Finally, designing scalable clustering algorithms is hard. For example, K-means -albeit easy to parallelize -suffers from a large runtime when K is large, and requires a large number of similarity computations. Frequency based methods are also difficult to scale, as it is generally cumbersome to parallelize frequent itemset mining algorithms.

In this work we present a clustering approach that addresses the above concerns: i) it produces high quality clusters that are easy to interpret, ii) it accommodates any kind of similarity metrics, and iii) it is scalable. The gist of our approach consists in building an approximate k-NN graph of the input text data, and compute its connected components, which identify data clusters. In particular, we aim at understanding the trade-off that exists between accuracy, scalability and, ultimately, clustering quality. To do so, we perform a thorough experimental evaluation of our method with real, large-scale datasets, using our implementation for the Apache Spark.

In summary, the contributions of our paper are as follows:

• We design and implement a scalable algorithm for text clustering, which works in an "adversarial" setting, and that produces high quality, and interpretable clusters. • We perform a detailed experimental analysis, where we show the impact of the parameters that govern the degree of approximation of our method. Our results indicate that even rough approximations are sufficient to obtain high quality clusters. • We use real-life datasets and evaluate the overall clustering quality of our approach both using traditional metrics and with the help of domain experts through manual investigation, highlighting the interpretability of clustering results.

II. RELATED WORK

Data clustering has been widely studied in the literature, with nuances ranging from graph theoretic and data mining principles [START_REF] Fortunato | Community detection in graphs[END_REF], [START_REF] Aggarwal | Mining text data[END_REF] to experimental approaches [START_REF] Steinbach | A comparison of document clustering techniques[END_REF], [START_REF] Zhao | Empirical and theoretical comparisons of selected criterion functions for document clustering[END_REF].

One of the most popular algorithm for clustering is Kmeans [START_REF] Lloyd | Least squares quantization in pcm. Information Theory[END_REF], which is a simple approach that can be used to perform clustering, where K indicates the number of clusters the algorithm produces. Since K-means operates on d-dimensional vectors, text clustering requires a transformation phase to encode sentences and words into vectors [START_REF] Karypis | Fast supervised dimensionality reduction algorithm with applications to document categorization & retrieval[END_REF], [START_REF] Toh | Dlirec: Aspect term extraction and term polarity classification system[END_REF]. For example, Mikolov et al. [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF] present an efficient implementation of the continuous bag-of-words and skip-gram architectures for computing vector representations of words. In our work, we use such approach as a baseline to which we compare our method, and show that it suffers from the underlying inability to accept non-metric distance measures, which are essential to detect similarity between mangled sentences, and from its poor scalability.

Alternative approaches search for frequent terms in the dataset to identify clusters [START_REF] Beil | Frequent term-based text clustering[END_REF], [START_REF] Becker | Beyond trending topics: Real-world event identification on twitter[END_REF], [START_REF] Matsuo | Keyword extraction from a single document using word co-occurrence statistical information[END_REF]: the idea is to find subsets of frequent term sets, which are a proxy for clusters, and map data items containing elements of such subsets to the same cluster. Such approaches scale poorly, and do not take into account similarity metrics resilient to mangling.

Other approaches aim to optimize the computation of pairwise similarity between text items using matrix computations [START_REF] Newman | Finding community structure in networks using the eigenvectors of matrices[END_REF]. In this category, recently, Lin et al. [START_REF] Lin | A very fast method for clustering big text datasets[END_REF] present an optimized algorithm to retrieve clustering of text data from a similarity matrix, using cosine similarity. In general, such approaches do not accommodate non-metric similarity measures and are difficult to scale, although recent work [START_REF] Bosagh-Zadeh | Dimension independent similarity computation[END_REF] has shown the benefits of approximate matrix operations, which scale better than exact, all-pair similarity computations.

An approach that targets goals that are similar to ours is Triage [START_REF] Thonnard | A strategic analysis of spam botnets operations[END_REF], which addresses the same application domain we target in this paper. However, the focus of Triage is on multifeature data items, and not on scalability: the authors mainly address problems related to information fusion, by defining a method to merge several different distance metrics operating on text, categorical and numerical values. Recently, a parallel version of Triage has been proposed [START_REF] Shen | Mr-triage: Scalable multi-criteria clustering for big data security intelligence applications[END_REF], which partially addresses scalability issues. However, the approach still computes all-pair similarity among representative, prototype items, with an O n2 complexity that still makes handling very large data sets difficult.

III. k-NN BASED CLUSTERING

We present our approach for text clustering, which is based on a scalable, randomized algorithm, and recognizes the role played by approximation which constitutes an important contribution to our analysis of the trade-off that exists between clustering quality and the scalability of our method.

The problem of text clustering we consider is particularly challenging due to the application scenario we study. We face an adversarial setting in which text data is generated such that finding similar items is cumbersome: SPAM campaigns introduce text mangling, spelling errors and generally variations on some baseline text which makes SPAM items belonging to the same campaign appear different one from each other. As a consequence, we need to use a similarity metric between items that can overcome, or at least mitigate, the problem. Similarity Metric. There exist numerous similarity metrics in the vast literature on the subject of this work. In particular, for text data, the Hamming distance and Levenshtein distance have been extensively used to determine the similarity among text items. In this work, for the reasons illustrated above, we choose the Jaro-Winkler [START_REF] Jaro | Probabilistic linkage of large public health data files[END_REF], [START_REF] Winkler | The state of record linkage and current research problems[END_REF] similarity metric which, simply stated, counts the common characters between two strings even if they are misplaced, misspelled, and mangled by a "short" distance. Note that, the Jaro-Winkler metric has a codomain in [-1, 1].

Given the choice of the similarity metric we use in this work, the wide spectrum of techniques to find clusters of similar text items reduces to few methods. This is the main driving factor that steers the algorithmic design choices we make in this work.

A. Phase 1: k-NN Graph Construction Algorithm 1: k-NN construction 1 procedure Map(Node n, NeighborList(n)) 2 forall the u ∈ N eighborList(n) ∪ n do 3 forall the v ∈ N eighborList(n) ∪ n \ u do 4 E M I T(u, (v, S I M I L A R I T Y(u, v))) 5 end 6 end 7 procedure Reduce(Node n,List[(Node u, Similarity s)] l) 8 orderedList = O R D E RDESC(l).LI M I T (k) 9 E M I T(n, orderedList)
In the first phase of our method, we build a k-NN graph. Essentially, the construction of a k-NN graph is the process of building a directed graph from a set of items V , with vertex set equals to V and an edge from each v ∈ V to its k most similar items in V under a given similarity measure. In this work, we limit our attention to text features: for example, we extract the subject of a SPAM email as the only representative feature of the item. Considering additional, heterogeneous features is outside the scope of this work, and we defer it to an extension of our approach.

The naïve approach to build a k-NN graph consists in finding all-pairs similarity among all items of a dataset, then select the k most similar items to each item. Clearly, this "brute-force" approach is not scalable, as it requires O(n 2 ) similarity computations, where n is the number of items in the dataset. Note that the "brute-force" algorithm produces exact k-NN graphs, which we use in this work as a baseline to determine the approximation quality of our method.

In this work, we design a parallel version of the NNDescent algorithm [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF], which is an elegant, and widely used method to build approximate k-NN graphs through an iterative procedure.1 From NNDescent, our approach inherits the capability of using arbitrary similarity metrics, including Jaro-Winkler. Although alternative approaches to build k-NN graphs exist, for example using locality sensitive hashing (LSH) [START_REF] Zhang | Fast knn graph construction with locality sensitive hashing[END_REF], [START_REF] Rajaraman | Mining of massive datasets[END_REF], such methods do not extend to arbitrary similarity metrics. 2 The main idea behind the k-NN graph algorithm we use in the first phase of our method is to iteratively improve an initial, random k-NN graph, by "swapping" the neighborhood of each node, searching for similar candidates among its twohop neighborhood. Increasing the number of iterations allows the algorithm to converge to better approximations of the k-NN graph, at the cost of higher convergence time.

Algorithm 1 illustrates the pseudo-code of a generic iteration of our parallel k-NN graph algorithm, which we cast through the MapReduce programming model. Note that the output of the algorithm is a weighted k-NN graph, where each edge is labelled with the similarity measure between its end vertexes. First, we initialize the algorithm by building a random, undirected k-NN graph: 3 each node of the graph (i.e. a data item) is assigned k random neighbors. In the "map phase", the algorithm accepts as input the random k-NN graph, explores the two-hop neighborhood of each node and computes the similarity among each pair, as shown the Map procedure. Note the vertex-centric nature of the algorithm: each vertex n considers a couple of its neighbours (u,v) and "unselfishly" computes the similarity between them. The result of this computation is then sent to the interested nodes through the EMIT operation. In the reduce phase, Reduce, each node selects its top-k similar nodes, and produces a new approximated k-NN graph, that is used as an input for the next iteration of the algorithm. Note that NeighborList is composed of (Node, Similarity) pairs.

In this work we are particularly interested in the role of the number of iterations of the algorithm, which determines its approximation quality. We claim that even rough approximations of the k-NN graph are sufficient for the ultimate goal of our clustering method. Intuitively, the existence of a path between similar items on the k-NN graph is sufficient for the last phase of the clustering algorithm we propose.

B. k-NN Graph Pruning

The iterative procedure to build an approximate k-NN graph may induce neighboring relations among text items that have a low pairwise similarity. Indeed, the algorithm necessarily outputs the k most similar neighbors for each item: any skew in the distribution of the pairwise similarities may produce a k-NN graph in which some nodes are only "loosely" similar. We thus introduce a pruning phase, that uses a parameter θ ∈ [0, 1] to determine a cut-off similarity value, below which edges between any pair of nodes are eliminated. The pruning phase inspects each node of the k-NN graph, and prunes such edges.

Choosing an appropriate threshold θ determines the final output of our clustering method: as θ → 1 clustering is strict, which leads to a large number of small clusters of essentially identical items; as θ → 0 clustering is loose, leading toward the degenerate case of a single, giant cluster.

C. Phase 2: Connected Components

The second and last phase of our approach uses the pruned k-NN graph, and outputs its connected components, that we use as a proxy for identifying clusters of similar items. Recall 3 We omit the pseudo-code of this phase, as it is trivial.

that the problem of finding the connected components of a graph amounts to searching for sub-graphs in which any two vertexes are connected to each other by paths.

Finding connected components in large-scale graphs using scalable algorithms is a well studied and understood problem, as shown in the rich literature on the subject [START_REF] Rastogi | Finding connected components in map-reduce in logarithmic rounds[END_REF], [START_REF] Kiveris | Connected components in mapreduce and beyond[END_REF], [START_REF] Lulli | Cracker: Crumbling large graphs into connected components[END_REF].

In this work we use a parallel implementation of the Cracker algorithm [START_REF] Lulli | Cracker: Crumbling large graphs into connected components[END_REF], wherein each node is tagged with the smallest node identifier of its component called seed node identifier.

The key idea of Cracker is to reduce the graph size in each step of the computation, by employing a technique inspired by the "contraction algorithm" to compute minimum cuts of a graph [START_REF] Karger | Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm[END_REF]. At termination, all nodes tagged with the same seed identifier are grouped in the same component.

IV. EXPERIMENTAL SETUP

This section provides details about our experimental setup, including datasets used, evaluation metrics, parameters and system environment. Experimental platform. All the experiments have been conducted on a cluster running Ubuntu Linux consisting of 17 nodes (1 master and 16 slaves), each equipped with 12 GB of RAM, a 4-core CPU and a 1 Gbit interconnect.

To implement our approach and the baseline method we use for our comparative analysis using Apache Spark [1]: our source code is publicly available 4 . Evaluation Metrics. We now discuss the metrics we use to analyse the parameter space of our approach, and for its global validation in terms of clustering quality. Also, we manually investigate the clusters we obtain, using domain knowledge to evaluate the goodness of clustering.

We study the role of the parameters of our approach using the following metrics:

• N. of clusters: measures the number of clusters identified by the clustering algorithm. If not otherwise stated, we only consider clusters to be "useful" if they have more than 1,000 elements; • Largest cluster size: measures the size of the largest cluster identified by the algorithm. We compute clustering quality using well-known metrics [START_REF] Desgraupes | Clustering indices[END_REF], [START_REF] Liu | Understanding of internal clustering validation measures[END_REF], that we report below:

• Silhouette [START_REF] Rousseeuw | Silhouettes: a graphical aid to the interpretation and validation of cluster analysis[END_REF]: constitutes an aggregate metric, that takes into account the inter-and intra-cluster pairwise similarity between items. Higher values are preferred. • Recall: this metric relates two data clustering obtained by different methods. Using clustering C as a reference, we compute the recall of clustering D by computing the fraction of items that belong to the same cluster in both C and D. In particular, we use as a reference the exact clustering we obtain with the "brute force" approach to compute the k-NN graph. Higher values of recall are preferred. It is important to notice that computing the above metrics is computationally as hard as computing the clustering we intend to evaluate. For this reason, we resort to uniform sampling: instead of computing the all-to-all pairwise similarity between items, we pick items uniformly at random, with a sampling rate of 1%, increasing it up to 10% for small clusters. The dataset. The main dataset we use in our evaluation consists of a subset of SPAM emails collected by Symantec Research Labs, between 2010-10-01 and 2012-01-02, which is composed by 3, 886, 371 email samples. Each item of the dataset is formatted according to JSON and contains the common features of an email, such as: subject, sending date, geographical information, the bot-net used for the SPAM campaign as labeled by Symantec systems, and many more. For instance, a subject of an email in the dataset is "19.12.2011 Rolex For You -85%" and the sending day is "2011-12-19".

In this work, we are interested in identifying clusters of SPAM emails using subjects alone, as they constitute a compact description of the email.

V. RESULTS

In this section we present our result, and we organize it as follows. First, we analyze the parameter space of our algorithm, and discuss the impact of such parameters on the metrics we defined above. Then, we focus on clustering quality, and compare the performance of our approach to that of the baseline algorithm we discuss in section II. Finally, we study the clustering scalability. Analysis of the parameter space. First, we summarize the parameters underlying our algorithm and discuss about their role. Our approach has 3 main parameters: k, the number of neighbors to construct the k-NN graph; the number of iterations of the first phase of the algorithm; and θ, the pruning threshold.

The experimental results we show in this section are obtained with a sampled version of the Symantec dataset, and account for 800,000 data items. A sampled dataset allows us to execute the "brute force" method to compute the k-NN graph.

In what follows, we let the number of iterations and θ to be free parameters, and instead select a few representative values for k. We chose k to be small, i.e., we allow a few neighbors per node in the k-NN graph.

Impact of the pruning threshold θ. We now discuss how the pruning mechanism modifies the k-NN graph, and what is the impact on clustering. As discussed in section III, as θ tends to 0, pruning is less effective, and the k-NN graph tends to have a single giant component. Instead, when θ tends to one, only very similar neighbors survive pruning, and the k-NN graph is fractioned in a large number of small clusters.

Figure 1a shows the fraction of nodes for which a given number of edges are removed after pruning, as a function of θ. For values of θ < 0.8, pruning is less effective, as the number of pruned edges is small. Instead, for θ > 0.9, a large fraction of nodes remain with one or fewer edges after the pruning phase. This translates in sizes of the largest clusters to approach the entire dataset, for θ = 0.5 already, or to be extremely small, for θ = 1. Overall impact of approximation. We now study the impact of the k-NN graph approximation on clustering quality, by analysing the deviation of our approach from the results obtained from an exact k-NN graph computed using the "brute force" approach. Our results indicate that approximate k-NN graphs obtained with a low k and few iterations are sufficient to obtain data clustering that is practically indistinguishable from that obtained by an onerous O(n 2 ) k-NN graph construction phase.

Figure 1b shows how clustering recall varies as a function of the k-NN iterations. As shown in the Figure, k = 10 and 5 iterations are sufficient to obtain a clustering which is essentially identical to that obtained with the exact k-NN graph. Even a very low value of k = 5 settles to a 0.8 recall, after roughly 10 iterations. Even rough approximations of the k-NN graph, obtained with a small number of iterations, are sufficient for the algorithm to stabilize. Analysis of the clustering quality. We now move to a global evaluation of the algorithm we present in this work, and compare clustering quality to the baseline algorithm described in section II. In particular, we use the efficient Kmeans implementation available in Spark's MLLib package [START_REF]Apache spark machine learning library[END_REF], and the word2vec package [START_REF]Word2vector package[END_REF], as illustrated in [START_REF]Clustering the News with Spark and MLLib[END_REF]. If not otherwise specified, we set K = 1000 such that the baseline algorithm output 1,000 clusters similarly to our "cseeberd@Amega.com VIAGRA ? 84% consensus!" "Maia@Amega.com VIAGRA ? 50% consensus!" "zelmo38dd@Amega.com VIAGRA ? 16% consensus!" approach. Also, this configuration yields the best result in term of Silhouette metric.

We focus on the full Symantec dataset. In addition, in what follows and if not otherwise specified, we set the operating parameters of our algorithm as follows: k = 10, and 10 iterations, which are the parameters that offer a good tradeoff between clustering quality, approximation quality, and algorithm runtime.

Figure 1c illustrates that the clustering Silhouette obtained by our approach is superior to the baseline algorithm, and this holds for all parameter choices. This is confirmed also in Figures 2a and2b, which show the number of "good" clusters (with at least 1,000 items) as determined by domain knowledge metrics. Essentially, these figures report the number of clusters amenable to manual inspection of the results, as a function of features such as the number of bot-nets and the time-frame of a SPAM campaign. For example, in Figure 2a, domain experts can extract valuable information when the number of SPAM bots in a cluster is small, in the 1-2 range: in this case, our approach is superior to the baseline algorithm, which performs slightly better for the less interesting cases of 3-4 and 5-6 bots. Similarly, Figure 2b shows that the number of "good" clusters identified by our approach is always better than that of the baseline algorithm, and this is especially true for the 1-7 range, indicating clusters with emails spanning a 1 week time-frame.

Finally, we proceed with a manual inspection of the clusters we obtain with our approach, to further illustrate the "goodness" of the clustering we achieve, with k = 10, 5 iterations and θ = 0.9. Table I illustrates a few email samples in clusters where both the number of bot-nets is less or equal to 2, and all emails are sent within one week time-frame. For instance, we obtain a cluster of 7255 emails sent from the Grum bot-net, between 2011/12/14 and 2011/12/20: the subjects of the email are related to a SPAM campaign involving a Rolex discount. Note that subjects are all related, albeit not identical. Analysis of algorithm scalability. We study the scalability of our approach and compare it to the baseline algorithm discussed earlier: first, we vary the dataset size maintaining the same number of compute machines that execute the parallel algorithms, then we keep the dataset size constant, and increase the level of parallelism by adding compute machines. Figure 3a, shows the algorithm runtime with varying dataset sizes, using 5 different samples of the Symantec dataset of size 100,000, 200,000, 400,000, 800,000 and 1,600,000 emails respectively. All values plotted are the average of 5 independent executions. Our results indicate roughly a linear scalability with respect to the size of the dataset, an observation that holds irrespectively of the value of k.

Figure 3b shows the algorithm runtime as the number of cores we devote to the computation varies between 4 and 64, considering datasets 400,000 and 800,000 items; in both cases, our results indicate a quasi-linear speed-up, especially for the biggest dataset. For example, increasing doubling the number of cores from 8 to 16, for the large dataset, cuts almost in half the algorithm runtime.

Finally, Table II, reports the runtime breakdown of the k-NN graph construction phase, and of the connected component phase of our algorithm, for several values of k and for θ = 0.9. Again, all values are the average of 5 independent executions.

As expected, the k-NN graph construction runtime increases both with k and with the iterations number, although more slowly than the worst scale asymptotic analysis and experi- mental results presented in [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF]. 5 Note that the first phase of our approach dominates the overall algorithm runtime, as computing the connected components is fast. Once the k-NN graph is built, it is possible to quickly proceed with various versions of the pruning phase (tuning θ for the application at hand) and obtain different clusters.

Table III illustrates the runtime of the baseline algorithm that uses K-means: the table reports the "slow-down" of the baseline algorithm with respect to our approach, when k = 10 and with 5 iterations, and for different values of K, the number of clusters K-means constructs. Our approach outperforms the baseline algorithm in terms of end-to-end clustering times, even for small values of K.

VI. CONCLUSION

Exploratory data analysis requires fundamental techniques to understand, describe and eventually extract value from large amounts of data. One of such techniques is data clustering. In this work, we presented a scalable approach for text data clustering, that accommodates arbitrary similarity measures and that produces high quality clusters.

To overcome the quadratic nature of typical approaches to text clustering, this work studied the role of approximation in establishing a trade-off between high clustering quality and fast algorithmic runtime. We showed, through a detailed experimental campaign, that our method does not require accurate representations of pairwise similarity across data items to produce high quality, interpretable clusters. We supported our claims using real traces covering adversarial applications aiming at identifying SPAM campaigns, and through manual inspection by domain experts of the clusters output by our algorithm.

Our next steps include the design of an LSH-based k-NN graph algorithm supporting arbitrary similarity metrics to push approximation even further, the extension of our method to a density-based approach and, ultimately, to take into account multiple, heterogeneous features of the data.

  Silhouette (higher is better).

Fig. 1 :

 1 Fig. 1: Impact of the pruning phase threshold θ. Impact of number of iterations for the k-NN graph construction phase of our algorithm. Clustering quality in terms of clustering Silhouette for the full Symantec dataset.

Fig. 2 :

 2 Fig. 2: Clustering quality in terms of the unique number of features in each cluster output by clustering algorithms.

Fig. 3 :

 3 Fig.3: Scalability. Our approach scales roughly linearly.

TABLE I :

 I Symantec Dataset: Manual Investigation

	cluster size bot	days	subjects sample
	7255	Grum, Unclassified	2011/12/14-2011/12/20	"17.12.2011 Rolex For You -73%" "15.12.2011 Rolex For You -89%" "19.12.2011 Rolex For You -85%"
	4512	Rustock, Unclassified 2010/12/04-2010/12/06	"jadevnn, Alena (status-online) invites you for chat." "Hi zmes40, Alena (status-online) invites you for chat." "keumd,,Alena (status-online) invites you for chat."
	4412	Rustock, Unclassified 2011/01/28-2011/02/01	"Re: User kilmernn" "Re: User anguinet" "Re: User hudnalli"
	4116	Rustock, Unclassified 2011/03/12-2011/03/14	"tdwilkey, you have a new PRIVATE MESSAGE", "dbeltondd, you have a new PRIVATE MESSAGE" "bn, you have a new PRIVATE MESSAGE"
	2992	Grum, Unclassified	2011/08/19-2011/08/23

TABLE II :

 II Symantec dataset: breakdown of the algorithm runtime (in seconds)

	k-NN graph phase		Iteration
	k	5	10	15	20	CC
	5	675	2293	3185	4897	66
	10	2281	4610	5320	7061	81
	15	4061	8475 13594 18203	107

TABLE III :

 III Symantec dataset: K-means, baseline algorithm runtime (in seconds)

		K	time
		1000	3498 (1.53×)
	K-means	2000 3000	10004 (4.39×) 28411 (12.46×)
		4000	56008 (24.55×)
	Our approach, k = 10 and 5 iterations	2281

Although an Hadoop MapReduce version of NNDescent is discussed in[START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF], we are not aware of any experimental validation of it. Moreover, in our work we use Spark, a more efficient MapReduce framework geared toward iterative algorithms.

We are currently working on an extension of this work to include modern LSH-based algorithms that can support arbitrary similarity metrics[START_REF] Ji | Super-bit locality-sensitive hashing[END_REF],[START_REF] Debatty | Scalable graph building from text data[END_REF],[START_REF] Debatty | Building k-nn graphs from large text data[END_REF] as well.

https://github.com/alessandrolulli/knnMeetsConnectedComponents

Recall that we use a different parallel execution framework in our work, Spark, which is geared towards efficient execution of iterative algorithms.

ACKNOWLDEGMENTS

This work has been partially funded by the BigFoot project, in the framework FP7-ICT-ICT-2011.1.2 Call 8, Project No. 317858.