Marie-José Adam

Sofiane Bendifallah

Négar Kalhorpour

Camille Cohen-Steiner

Laetitia Ropars

Asma Mahmood

Chloé Rousseau

Jean Leveque

Krystel Nyangoh Timoh

Adolphe Der Some

Lobna Ouldamer

Guillaume Legendre

Marcos Ballester

Emile Daraï

Geoffroy Canlorbe

Vincent Lavoue
email: vincent.lavoue@chu-rennes.fr

Vincent Pr

Lavoué

Time to revise classification of phyllodes tumors of breast? results of a French multicentric study

Keywords: phyllodes breast tumor, benign, borderline, malignant, prognostic factors, surgery

Objective. To assess prognostic factors of recurrence of phyllodes tumors (PT) of the breast.

Methods. We performed a retrospective, multicentric cohort study, including all patients who underwent breast surgery for grade 1 (benign), 2 (borderline) or 3 (malignant) PT between 2000 and 2016 in five tertiary University hospitals, diagnosed according to World Health Organization classification.

Results. 230 patients were included: 144 (63%), 60 (26%) and 26 (11%) with grade 1, 2 and 3 PT, respectively. Recurrence occurred in 10 (7%), 7 (12%) and 5 (19%) patients with grade 1, 2 and 3 PT, respectively. In univariate analysis, moderate to severe nuclear stromal pleomorphism (HR 8.00 [95% CI: 1.65 -38.73], p<0.009) was correlated with recurrence in all groups including grade 1 (HR 14.3 [95% CI: 1.29 -160], p=0.031). In multivariate analysis, surgical margin >5 mm, (HR 0.20 [95% CI: 0.06 -0.63], p = 0.013) were significantly correlated with less recurrence in all PT grades. For grade 1 PT, there was also significantly less recurrence with surgical margin >5mm, (HR 0.09 [95% CI: 0.01 -0.85], p=0.047) in multivariate analysis.

Conclusion.

The surgical margin should be at least 5 mm whatever the grade of PT. Moderate to severe nuclear stromal pleomorphism identified a subgroup of grade 1 PT with a higher rate of recurrence. This suggests that the WHO classification could be revised with the introduction of nuclear stromal pleomorphism to tailor PT management.

Introduction

Phyllodes tumors (PT) of the breast are fibroepithelial tumors whose etiopathogenesis remains unclear. These are rare tumors accounting for around 0.3-1% of all primary breast tumors [START_REF] Macdonald | Malignant phyllodes tumor of the female breast: association of primary therapy with cause-specific survival from the Surveillance, Epidemiology, and End Results (SEER) program[END_REF][START_REF] Spitaleri | Breast phyllodes tumor: a review of literature and a single center retrospective series analysis[END_REF]. They mostly affect women in their fourth decade of life. The classic clinical presentation is a supple, painless mass, well limited, with rapid growth without associated axillary adenopathy. In 1982, the World Health Organisation (WHO) classification distinguished three types of PT according to five factors: stromal cellularity, stromal atypia, stromal overgrowth, mitotic count, and character of the tumor borders (3) (4) (5) (6) [START_REF] Cohn-Cedermark | Prognostic factors in cystosarcoma phyllodes. A clinicopathologic study of 77 patients[END_REF]. The stromal overgrowth was defined as definition: absence of epithelial elements in one low-power microscopic field containing only stroma (according WHO 2012 classification)

The three types of PT are: grade 1 or benign tumors, grade 2 or borderline tumors, and grade 3 or malignant tumors representing 64%, 18% and 18% of all PT, respectively [START_REF] Belkacémi | Phyllodes tumor of the breast[END_REF].

The average risk for local recurrence and metastasis have been reported as being 15% and 0.1% for grade 1 PT, 17% and 0.2% for grade 2 PT, 28% and 22% for grade 3 PT [START_REF] Spitaleri | Breast phyllodes tumor: a review of literature and a single center retrospective series analysis[END_REF]. The recurrent tumor can be of a more aggressive histological form justifying surgical excision of all PT [START_REF] Tremblay-Lemay | How wide should margins be for phyllodes tumors of the breast?[END_REF][START_REF] Bendifallah | Common benign breast tumors including fibroadenoma, phyllodes tumors, and papillary lesions: Guidelines[END_REF]. Some prognostic factors have been identified [START_REF] Moffat | Phyllodes tumours of the breast: a clinicopathological review of thirty-two cases[END_REF][START_REF] Belkacémi | Phyllodes tumor of the breast[END_REF][START_REF] Bennett | Phyllodes tumours: a clinicopathological review of 30 cases[END_REF][START_REF] Parker | Phyllodes tumours[END_REF] including: age, tumor size, grade, mitotic index, degree of cellular atypia, stromal necrosis and stromal cellularity and histologically negative margins for grade 1 PT, and margins greater than 10 mm for grades 2 and 3 PT for therapeutic factors.

However, these prognostic factors are mainly based on old data. The largest study by Belkacemi et al [START_REF] Belkacémi | Phyllodes tumor of the breast[END_REF] including 443 women with PT, dates from 1971 to 2003 prior to the WHO classification distinguishing 3 grades of PT. Moreover, PT management is based on low levels of evidence. Margin width was determined on a consensus from two studies by Spitaleri et al (2) and Kim et al [START_REF] Kim | Analysis of phyllodes tumor recurrence according to the histologic grade[END_REF] published in 2013. Thus, there is a need for a better determination of prognostic factors for optimal PT management.

Therefore, the main objective of the present study was to assess prognostic factors of PT recurrence based on clinical, pathological and surgical characteristics to tailor management of PT according to histological grade.

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT

Material and methods

Patients

This was a retrospective, multicenter cohort study. Data of women with histologically proven PT operated on between January 2000 and December 2016 were abstracted from five institutions in France with prospective maintained breast databases (Tours, Tenon, Angers, Rennes and Pitié Salpêtrière University Hospitals). The research protocol was approved by the Institutional Review Board (N° 2088222).

The inclusion criteria were grade 1, 2 or 3 PT histologically confirmed from a surgical specimen. The exclusion criteria were: breast adenofibroma, breast cancer, other fibroepithelial tumors than PT.

Clinical, surgical and pathological data were collected from the patients' medical charts. The histopathological data collected included: PT grade, tumor size (mm), stromal mitotic activity defined by the number of mitoses in high-magnification fields (less than 4, between 4 and 9 or higher or equal to 10), stromal cell atypia (absent; moderate i.e., difficile to spot; or severe i.e., of high nuclear grade), stromal cellularity (mild, moderate, severe), stromal overgrowth (mild, moderate, severe), stromal nuclear pleomorphism (classified as mild: small nuclei, regular chromatin, few nucleoli; moderate: larger nuclei, visible but small nucleoli; or severe: significant variation of nuclei in size and shape, prominent nucleoli), stromal necrosis, and surgical margins.

Histological evaluation

All women were classified according to the 2012 WHO classification on final pathology serving as the standard. A PT was defined as a fibroepithelial tumor with the following four criteria: high stromal cellularity (50% higher than that observed in adenofibromas), predominant stroma in the epithelial component, leaf-like projections into variably dilated elongated lumina and infiltrative margin (tumor border). The benign,

M A N U S C R I P T A C C E P T E D

ACCEPTED MANUSCRIPT 5 borderline and malignant grades (i.e 1,2 and 3 grades) were defined in accordance with the 2012 WHO recommendations (4) using these criteria: infiltrating periphery, stromal cellularity (categorized as mild / moderate / severe assessed in the most cellular area, mild is defined as increase in at least 50% of the stroma in PT compared with a typical adenofibroma, moderate is defined as the presence of stromal nuclear crowding or overlapping, severe is defined as marked stromal cellularity), mitotic activity (<5, 5-9, ≥ 10 per 10 high power fields), and cellular atypia. The surgical specimens were analyzed by an expert breast pathologist.

Treatment, follow-up and endpoints

All women had undergone primary surgical treatment. Clinical follow-up consisted of physical examinations and the use of imaging techniques according to the findings. Recurrent disease was assessed by physical examination, histological findings, clinical follow-up and imaging. The diagnosis of recurrence was based on histological sampling. The date of the last recorded information corresponded to either the date of the last visit in the follow-up center, or the date of recurrence or death.

The primary endpoint was the ipsilateral recurrence of a PT during the follow-up period. The secondary endpoint was the PT grade.

Recurrence free survival (RFS) was defined as the time from the date of primary surgery to any PT recurrence and was censored at date of the last follow-up or date of death without recurrence. Overall survival (OS) was defined as time from primary surgery to death as a result of any cause.

Statistical analysis

For the descriptive analysis of population characteristics, a χ2 or Fisher test was used for the qualitative parameters, and a Kruskal-Wallis test for the quantitative parameters. Variables were considered statistically significant when p < 0.05. A Receiver Operating Characteristic

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT 6
(ROC) curve was used to define a surgical margin threshold. A univariate analysis of clinical, therapeutic and pathological recurrence risk factors on RFS by the log rank test was then performed. These results are presented by Hazard Ratio (HR) with 95% confidence interval (CI). Variables with a p < 0.20 were included in a multivariate model, followed by a step-bystep descending selection. Survival curves were performed using the Kaplan-Meier model.

M A N U S C R I P T A C C E P T E D

Results

Characteristics of the population and preoperative data

Two-hundred thirty patients were included: 144 (63%) had grade 1 PT, 60 (26%) grade 2 PT, and 26 (11%) grade 3 PT. The characteristics of the patients are shown in Table 1.

Surgery and post-operative data

The initial surgery for all PT grades consisted of enucleation (or local excision) for 38 patients (16.5%), wide excision for 172 patients (74.8%) and a total mastectomy for 20 (8.7%). The surgical and pathological data are shown in Table 2. Adjuvant treatment consisted of radiotherapy for 14 patients (6.1%), including one patient with grade 2 PT (1.7%), and 13 patients with grade 3 (50%). Chemotherapy was performed in three of the patients (11.5%) with grade 3 PT.

Follow-up

The mean follow-up was 42.5 months (± 46.8 months). During the follow-up period, 22 patients (9.6%) experienced PT recurrence with 17 of the recurrences (77%) occurring within the first 3 years of follow-up. Overall, the mean recurrence time was 28.7 months (±21.6 months): 37 months (±27.6 months) for grade 1 PT; 21.1 months (±12.6 months) for grade 2 PT; and 22.6 months (±13.7 months) for grade 3 PT (Not Significant (NS)). Patterns of recurrences and treatments performed are described in Figure 1.

The recurrence rate was 7% (n = 10) for grade 1 PT, 11.7% (n = 7) for grade 2 PT, and 19.2% (n = 5) for grade 3 PT (NS). There were no deaths among the patients with grade 1 PT. The death rate was 1.7% (n = 1) for grade 2 PT and 15.4% (n = 4) for grade 3 PT (p < 0.001).

Overall, the 3-year RFS rate was 92.6%: 95.8%, 90.0% and 80.8% for grade 1, 2 and 3 PT, respectively (p = 0.018). The 10-year RFS rates were 93.1%, 88.3% and 80.8% for grade 1, 2 and 3 PT, respectively (NS).

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT

The 3-year OS rate was 100%, 96.2% and 96.2% for grade 1, 2 and 3 PT, respectively (p = 0.072). The 10-year OS rate was 100%, 98.3% and 84.6% for grade 1, 2 and 3 PT, respectively (p < 0.001).

Prognostic factors

ROC curves were used to assess optimal surgical margins to prevent or decrease recurrence rate (Figure S1 -supplementary data). For grade 1 PT, a surgical margin value of 1 mm had a sensitivity, specificity, positive predictive value (PPV) and negative predictive value (NPV) of 41.0%, 90.4%, 22.2% and 91.8%, respectively; a surgical margin value of 5 mm had a sensitivity, specificity, PPV and NPV of 90.0%, 26.8%, 8.8% and 97.1%, respectively; and a surgical margin value of 10 mm had a sensitivity, specificity, PPV and NPV of 90%, 24.4%, 8.6% and 96.9%, respectively. For grade 2 PT, a surgical margin value of 1 mm had a sensitivity, specificity, PPV and NPV of 28.6%, 92.3%, 33.3% and 90.6%, respectively; a surgical margin value of 5 mm had a sensitivity, specificity, PPV and NPV of 42.9%, 53.8%, 11.1% and 87.5%, respectively; and a surgical margin value of 10 mm had a sensitivity, specificity, PPV and NPV of 42.8%, 47.2%, 9.7% and 13.8%, respectively.

For grade 3 PT, we were unable to demonstrate margins with a meaningful sensitivity, specificity, PPV or NPV.

The prognostic factors of recurrence for all grades of PT are described in Table 3. According to univariate survival analysis, age > 40 years (HR 0.38 [95% CI: 0.16-0.89], p = 0.026), a surgical margin of more than 1 mm (HR 0.29 [95% CI: 0.10 -0.85], p = 0.044), and a margin of more than 5mm (HR 0.31 [95% CI: 0.11 -0.90], p = 0.044) were significantly correlated with less recurrence. As a continuous variable, surgical margin size was also significantly correlated with less recurrence (HR 0.22, [95% CI: 0.05 -0.91], p = 0.036). A margin of more than 10 mm (HR 0.85 [95% CI: 0.35 -2.02], p = 0.706) was not significantly correlated with less recurrence.

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT

The nuclear pleomorphism of the stroma was known for 97 patients and showed that moderate to severe stromal nuclear pleomorphisms (HR 8.00 [95% CI: 1.65 -38.73], p = 0.009) were correlated with more recurrence.

According to multivariate analysis, a surgical margin of more than 1 mm (HR 0.26 [95% CI: 0.09 -0.76], p = 0.013), and of more than 5 mm (HR 0.20 [95% CI: 0.06 -0.63], p = 0.013) were significantly correlated with less recurrence for all grades of PT.

The prognostic factors for recurrence of grade 1 PT are described in Table 4. According to univariate survival analysis, age > 40 years (HR 0.24 [95% CI: 0.06 -0.92], p = 0.038) and a surgical margin of more than 5 mm (HR 0.09 [95% CI: 0.01 -0.85], p = 0.047) were significantly correlated with less recurrence. Moderate to severe stromal nuclear pleomorphisms (HR 14.3 [IC 95%: 1.29-160], p=0.031) were significantly correlated with recurrence. A margin of more than 10 mm (HR 0.25 [95% CI: 0.03 -1.95], p = 0.184) was not significantly correlated with less recurrence. Stromal nuclear pleomorphism was known for 56 of the patients with grade 1 PT: recurrence rates were 2/49 (4%) for patients with low stromal nuclear pleomorphism and 2/7 (28%) for those with moderate to severe stromal nuclear pleomorphism.

In multivariate analysis, only a margin over 5 mm was significantly correlated with less recurrence (HR 0.09 [CI 95%: 0.01 -0.85], p = 0.047) for patients with grade 1 PT.

In univariate survival analysis for grade 2 PT, only age > 40 years was significantly correlated with less recurrence (HR 0.12 [95% CI: 0.03 -0.53], p = 0.005). No margin width threshold was significantly correlated with recurrence for grade 2 PT, probably due to lack of power.

No factors were found to be significantly correlated with recurrence for grade 3 PT in univariate analysis, probably due to lack of power.

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT

Discussion

The overall PT recurrence rate was 9.6%. Surgical margin size was found to be an independent prognostic factor of recurrence for all grades of PT, including grade 1. Furthermore, stromal nuclear pleomorphism was significantly correlated with recurrence for grade 1 PT in univariate analysis, identifying a subgroup of grade 1 PT with a similar or higher recurrence rate to grade 2 PT (28% vs 12%, respectively).

Although we did not find a significant correlation of stromal cellularity with recurrence (as others have shown [START_REF] Belkacémi | Phyllodes tumor of the breast[END_REF][START_REF] Kim | Analysis of phyllodes tumor recurrence according to the histologic grade[END_REF][START_REF] Tan | Phyllodes tumors of the breast: the role of pathologic parameters[END_REF]), in accordance with Sawalhi (2013) we found a significant correlation between stromal nuclear pleomorphism and recurrence [START_REF] Sawalhi | Phyllodes tumor of the breast: a retrospective study of the impact of histopathological factors in local recurrence and distant metastasis[END_REF]. In theory, stromal nuclear pleomorphism is defined as mild (small nuclei, regular chromatin, few nucleoli); moderate (larger nuclei, visible but small nucleoli), or severe (significant variation of nuclei in size and shape, prominent nucleoli). However, in practice, these definitions appear to vary, and no inter-or intraobserver variability data are available, which could weaken reproducibility of diagnosis. In accordance with others [START_REF] Spitaleri | Breast phyllodes tumor: a review of literature and a single center retrospective series analysis[END_REF][START_REF] Belkacémi | Phyllodes tumor of the breast[END_REF][START_REF] Kim | Analysis of phyllodes tumor recurrence according to the histologic grade[END_REF][START_REF] Tan | Phyllodes tumors of the breast: the role of pathologic parameters[END_REF] we found that margin status is an independent prognostic factor: the wider the margin the lower the recurrence rate (in a significant manner). Kim et al [START_REF] Kim | Analysis of phyllodes tumor recurrence according to the histologic grade[END_REF] and others (9,10) advocate only in sano surgery for grade 1 PT, in contrast to the present study which showed that a margin size of more than 5 mm is required for grade 1 PT (with an NPV of 97.1% for recurrence). This would suggest that optimal surgical treatment for all grades of PT requires local surgical excision with a good margin size. This wide surgical excision is important as PT tends to recur with a more severe grade, as shown in the present study and others [START_REF] Sawalhi | Phyllodes tumor of the breast: a retrospective study of the impact of histopathological factors in local recurrence and distant metastasis[END_REF][START_REF] Guillot | Management of phyllodes breast tumors[END_REF]. Some limitations of the present study deserve to be mentioned. First of all, there were some missing data (such as tumor border) and a risk of underestimating recurrence rates because of the retrospective nature of the study and the duration of the inclusion period. This, coupled with a low rate of recurrence, hampered the possibility of building a scoring system to predict

M A N U S C R I P T A C C E P T E D

recurrences. Another limitation is the relatively short mean follow-up of 42.5 months (± 46.8 months), versus 85 months in the Spitaleri study [START_REF] Spitaleri | Breast phyllodes tumor: a review of literature and a single center retrospective series analysis[END_REF] and 106 months in the Belkacemi study [START_REF] Belkacémi | Phyllodes tumor of the breast[END_REF]. Thus, the use of ROC curves to find margin size threshold according recurrence could be hampered. However, local recurrences are mainly observed during the first two years of follow-up [START_REF] Zurrida | Which therapy for unexpected phyllode tumour of the breast?[END_REF][START_REF] Reinfuss | The treatment and prognosis of patients with phyllodes tumor of the breast: an analysis of 170 cases[END_REF] and even earlier for grade 3 PT [START_REF] Telli | Phyllodes tumors of the breast: natural history, diagnosis, and treatment[END_REF][START_REF] Grabowski | Malignant phyllodes tumors: a review of 752 cases[END_REF].

Conclusion

This large retrospective study analyzing data from prospectively managed databases from five major university hospitals in France, suggests that the recurrence rate of PT is around 10% and that nearly one third of these recurrences occur in patients with a higher grade PT conveying a poorer prognosis. Surgical margin size remains the main prognostic factor, including in patients with grade 1 PT, with a required surgical margin of over 5 mm.

Moderate to severe stromal nuclear pleomorphism identified a group of grade 1 PT patients with a higher risk of recurrence (28%).

  The authors declare that they have no conflict of interest

Table 1 . Preoperative characteristics of patients

 1

	Data	All PT n = 230	PT n = 144 Grade 1	PT n = 60 Grade 2	PT n = 26 Grade 3	p value
	Age (mean +/-SD)	47.2 ± 14.1	44.3 ± 12.5	53.2 ± 16.0	49.6 ± 13.7	< 0.001
	(range)	(16-95)	(16, 83)	(17, 95)	(26, 80)
	Parity (mean +/-SD)	1.7 ± 1.5	1.6 ± 1.4	1.7 ± 1.5	2.3 ± 2.0	0.240
	≤ 1	102 (44.3%)	67 (46.5%)	27 (45.0%)	8 (30.8%)	0.328
	≥ 2	128 (55.7%)	77 (53.5%)	33 (55.0%)	18 (69.2%)
	Contraception	65 (45.1%)	51 (48.6%)	11 (44.0%)	3 (21.4%)	0.158
	Menopause	85 (37.0%)	39 (27.1%)	34 (56.7%)	12 (46.2%)	< 0.001
	Hormonal Replacement Therapy	21 (9.1%)	12 (8.3%)	8 (13.3%)	1 (3.8%)	0.331
	Smoking	27 (13.2%)	21 (16.0%)	3 (5.8%)	3 (13.6%)	0.198
	Breast adenofibroma history	70 (30.4%)	49 (34.0%)	13 (21.7%)	8 (30.8%)	0.217
	PT history	2 (0.9%)	1 (0.7%)	0 (0.0%)	1 (3.8%)	0.295
	Breast cancer history	6 (2.6%)	1 (0.7%)	4 (6.7%)	1 (3.8%)	0.044
	PT family history	1 (0.4%)	1 (0.7%)	0 (0.0%)	0 (0.0%)	1
	Pregnancy (at diagnosis)	2 (0.9%)	1 (0.7%)	1 (1.7%)	0 (0.0%)	0.609
	Single localisation unifocal PT	198 (86.1%)	118 (81.9%)	56 (93.3%)	24 (92.3%)	0.077
	Duration of symptoms					0.017
	< 2 months	55 (33.1%)	30 (28.3%)	16 (34.8%)	9 (64.3%)
	2 -12 months	56 (33.7%)	38 (35.8%)	13 (28.3%)	5 (35.7%)
	> 12 months	55 (33.1%)	38 (35.8%)	17 (37.0%)	0 (0.0%)
	Pain	42 (18.3%)	30 (20.8%)	7 (11.7%)	5 (19.2%)
	Skin changes	10 (4.3%)	3 (2.1%)	3 (5.0%)	4 (15.4%)	0.015
	Nipple retraction	1 (0.4%)	0 (0.0%)	0 (0.0%)	1 (3.8%)	0.113
	Clinical tumor size (mm, mean +/-SD)	43.9 ± 60.7	32.6 ± 20.8	55.5 ± 95.2	80.7 ± 88.4	< 0.001
	(range)	(6, 700)	(10, 150)	(6, 700)	(20, 400)
	Clinical tumor size					< 0.001
	< 30 mm	101 (45.9%)	82 (59.4%)	17 (28.8%)	2 (8.7%)
	≥ 30 mm	119 (54.1%)	56 (40.6%)	42 (71.2%)	21 (91.3%)
	Ultrasound tumor size (mean +/-SD)	38.8 +/-43.1	32.8 +/-21.4	35.6 +/-29.8	86.1 +/-107.8	0.007
	(range)	(6, 400)	(8, 130)	(6, 170)	(11, 400)
	Ultrasound tumor size					0.003
	< 20 mm	50 (25.8%)	31 (26.1%)	18 (32.1%)	1 (5.3%)
	20 -50 mm	105 (54.1%)	71 (59.7%)	26 (46.4%)	8 (42.1%)
	≥ 50 mm	39 (20.1%)	17 (14.3%)	12 (21.4%)	10 (52.6%)
	Abbreviations: SD standard deviation; PT: phyllode tumor

Table 2 . Surgical and pathological characteristics of patients

 2

		All	PT	PT	PT
	Data	PT	Grade 1	Grade 2	Grade 3	p
		n = 230	n = 144	n = 60	n = 26
	Initial Surgery
	Enucleation (or local excision)	38 (16.5%)	30 (20.8%)	7 (11.7%)	1 (3.8%)	< 0.001
	Wide excision	172 (74.8%) 111 (77.1%)	48 (80.0%)	13 (50.0%)
	Total mastectomy	20 (8.7%)	3 (2.1%)	5 (8.3%)	12 (46.2%)
	Histological size (mm, mean +/-SD)	38.9 ± 29.0	30.9 ± 21.5	± 29.2	65.7 ± 43.7	0.001
	(range)	(5, 210)	(5, 170)	(6, 130)	(15, 210)
	No. of mitoses
	< 4	143 (68.8%)	120 (92%)	(35.7%)	3 (13.6%)	< 0.001
	4 à 9	(14.9%)	10 (8%)	(33.9%)	2 (9.1%)
	≥10	34 (16.3%)	0 (0.0%)	17 (30.4%)	(77.3%)
	Stromal cellular atypia
	Mild	141 (75.4%) 112 (95.7%)	27 (55.1%)	2 (9.5%)	< 0.001
	Moderate	(14.4%)	4 (3.4%)	18 (36.7%)	5 (23.8%)
	Severe	19 (10.2%)	1 (0.9%)	4 (8.2%)	(66.7%)
	Stromal cellularity
	Mild	45 (22.7%)	(30.2%)	6 (12.0%)	1 (4.5%)	< 0.001
	Moderate	76 (38.4%)	55 (43.7%)	19 (38.0%)	2 (9.1%)
	Severe	77 (38.9%)	33 (26.2%)	25 (50.0%)	19 (86.4%)
	Stromal overgrowth
	Mild	24 (29.3%)	19 (32.8%)	5 (27.8%)	0 (0.0%)	0.002
	Moderate	44 (53.7%)	34 (58.6%)	9 (50.0%)	1 (16.7%)
	Severe	14 (17.1%)	5 (8.6%)	4 (22.2%)	5 (83.3%)
	Stromal nuclear pleomorphism
	Mild	68 (70.1%)	49 (87.5%)	16 (57.1%)	3 (23.1%)	< 0.001
	Moderate	16 (16.5%)	6 (10.7%)	9 (32.1%)	1 (7.7%)
	Severe	13 (13.4%)	1 (1.8%)	3 (10.7%)	9 (69.2%)
	Tumor necrosis
	Yes	11 (5.1%)	1 (0.7%)	2 (3.5%)	8 (38.1%)	< 0.001
	No	206 (94.9%) 138 (99.3%)	55 (96.5%)	13 (61.9%)
	Margins after first surgery (mm, mean+/-SD)	3.7 ± 5.4	3.7 ± 4.9	3.7 ± 5.3	3.7 ± 8.3	0.198
	(range)	(0, 40)	(0, 30)	(0, 20)	(0, 40)
	Second surgery	58 (25.2%)	19 (13.2%)	25 (41.7%)	14 (53.8%)	< 0.001
	Mastectomy	18 (31.0%)	1 (5.3%)	6 (24.0%)	11 (78.6%)	< 0.001
	Second lumpectomy for marge status	40 (69.0%)	18 (94.7%)	19 (76.0%)	3 (21.4%)
	Residual disease after second surgery	7 (12.1%)	1 (5.3%)	4 (16.0%)	2 (14.3%)	0.589
	Margins after second surgery (mm, mean +/-SD)	6.0 ± 7.4	4.4 ± 5.3	9.1 ± 9.6	7.5 ± 9.0	0.002
	(range)	(0, 50)	(0, 30)	(0, 50)	(0, 40)

Table 3 . Univariate analysis of prognostic factors of recurrence-free survival for all phyllodes tumors

 3

Data


Laurent Candillier Grappa

Ludovic Denoyer
email: luc.denoyer@lip6.fr

Patrick Gallinari
email: patrick.gallinari@lip6.fr

Marie Christine Rousset
email: christine.rousset@imag.fr

Alexandre Termier
email: termier@ism.ac.jp

Anne-Marie Vercoustre
email: marie.vercoustre@inria.fr

Mining XML documents

Keywords: XML Mining, structured documents, tree-based model, document representation, classification, clustering, frequent patterns, frequent trees, feature selection, stochastic generative model, Bayesian networks

XML documents are becoming ubiquitous because of their rich and flexible format that can be used for a variety of applications. Giving the increasing size of XML collections as information sources, mining techniques that traditionally exist for text collections or databases need to be adapted and new methods to be invented to exploit the particular structure of XML documents. Basically XML documents can be seen as trees, which are well known to be complex structures. This chapter describes various ways of using and simplifying this tree structure to model documents and support efficient mining algorithms. We focus on three mining tasks: classification and clustering which are standard for text collections; discovering of frequent tree structure which is especially important for heterogeneous collection. This chapter presents some recent approaches and algorithms to support these tasks together with experimental evaluation on a variety of large XML collections.

INTRODUCTION

The widespread use of semi-structured formats like XML for representing data and documents has urged the need to develop tools to efficiently store, access and organize XML corpus. With the development of such structured textual and multimedia document, the document nature is changing. Structured documents usually have a much richer representation than flat ones. They have a logical structure. They are often composed of heterogeneous information sources (e.g. text, image, video, metadata, etc). Another major change with structured documents is the possibility to access document elements or fragments. The development of classifiers for structured content is a new challenge for the Machine Learning (ML) and Information Retrieval (IR) communities. A classifier for structured documents should be able to make use of the different content information sources present in an XML document and to classify both full documents and document parts. It should easily adapt to a variety of different sources and document models (i.e. different Document Type Definitions). It should be able to scale with large document collections.

Handling structured documents for different IR tasks has recently attracted an increasing attention. Many questions are still open for designing such systems so that we are only in the early stages of this development. Most of the work in this new area has concentrated on ad hoc retrieval in the context of the recent INitiative for the Evaluation of XML Retrieval (INEX) launched in 2002. Besides this mainstream of research, some work is also developing around other generic IR problems like clustering and classification for structured documents.

The use of XML format raises a new challenge for document mining, first because of its new complex data structure, second by the two dimensions that can be dealt with: the (semi-) structured dimension and the content (especially text) dimension, and third because of the possible heterogeneity of the documents. Depending on the application or the mining objective, it may be relevant to consider the structure information alone or both the structure and the content of the documents.

XML documents are usually modelled as ordered trees which are regarded as complex structures. Indeed algorithms dealing with tree collections may be very costly when the size of the documents and the collection increases. It is often necessary to simplify the document tree model in order to implement efficient algorithms or to adapt scalable existing clustering and classification methods. A common simplification, for example, is to ignore the order of tree siblings, yet some algorithms would take this into account when required by the data.

This chapter describes various tree-based representations of XML documents to support efficiently three mining tasks: frequent pattern extraction, classification and clustering. Frequent pattern extraction from document structure has been studied mostly by the database community, with the objective of clustering large heterogeneous collections of XML documents to support query optimisation. Classification and clustering using document structure, and possibly content, has been studied both by the IR and ML communities.

We first introduce the XML tree-based model. Then we present some advanced algorithms for frequent pattern extraction in XML collections. In the last section we present three flexible classes of document representation that have been used in classification or clustering algorithms. Although we do not cover all the possible representations for XML documents, we show many different working representations that can be derived from the initial complex tree-like structure in order to support XML mining tasks.

TREE-BASED COMPLEX DATA STRUCTURE

XML documents are regarded as semi-structured data since they offer a flexible structure compared to more strictly structured databases. For example, elements in XML documents can be optional or have an unfixed number of occurrences. The document structure can be constrained by the definition of a DTD (Document Type Description), or a document can be just well formed. A well formed XML document must conform to the XML grammar, which mostly means that, unlike HTML documents, all the tags must be well parenthesised and that a document must have a single root.

The XML Document Object Model (XML DOM) defines a standard way for accessing and manipulating XML documents. The DOM presents an XML document as a tree-structure (a node tree), with the elements, attributes, and text defined as nodes.

Fig. 1 and Fig. 2 present a small XML document describing a movie and its associated treestructure. This description is very typical of the ones to be used for indexing and retrieving movies, and very different from the ones that would be necessary for describing the frames of the film itself. Note the attribute lang in the second title, and the repetition of the elements title and actor. This document here conforms to the DTD that is referred to in the document model CINEMA (second ligne of the document), not shown here. XML documents can be modelled by unranked, ordered labelled trees where labels correspond to XML tags which may or may not carry semantic information. More precisely, when considering only the tree structure:

-each node can have an arbitrary number of children, -the children of a given node are ordered,

-each node has a label in the vocabulary of the tags.

A labelled node n in a XML document is represented by a couple n=(s, t), where s is the label of n in the structure of the document, and t represents the content of n.

Let S = {s 1 ,...,s |S| } be the set of structural labels, and Ђ = {t 1 ,...,t |Ђ| } be the set of possible contents.

An XML document can then be represented by a labelled tree. A labelled tree T = (N, A, root(T)) is an acyclic connected graph, where N is the set of nodes, A ⊆ N × N is a binary relation over N defining the set of edges, and root(T) is a distinguished node called the root.

Let u ∈ N and v ∈ N be two nodes of a tree. If there exists an edge (u, v) ∈ A, then v is a child of u, and u is the parent of v.

For two nodes of a tree u and v, if there exists a set of nodes {x 1 ,...,x p } such that u is the parent of x 1 , x 1 is the parent of x 2 ,..., and x p is the parent of v, then {x 1 ,...,x p } is called a path from u to v. If there exists a path from u to v in the tree, then v is a descendant of u, and u is an ancestor of v.

Finally, for two nodes of a tree u and v, if there exists a node x 1 such that both u and v are children of x 1 , then u and v are called sibling nodes.

A tree is an attribute tree if two sibling nodes cannot have the same label [START_REF] Arimura | An Output-Polynomial Time Algorithm for Mining Frequent Closed Attribute Trees[END_REF] describe attribute trees in more detail). This is mostly not the case in XML documents where lists of elements with the same label are quite common. However it is possible to transform the original trees into attribute trees without losing their most canonical structural properties.

Document transformation:

Most tree mining algorithms do not directly operate on XML documents. They need a pre-processing step, which takes as input the XML documents and outputs a labelled tree for each document. This labelled tree reflects the tree structure of the original document, where the node labels are the tags of the XML document. Then the documents will be further transformed depending on the document model used by the intended mining task and the specific algorithm. Pre-processing may involve:

-stripping off the textual content of the document when dealing with structure only; -stripping off the XML attributes when they are not regarded as relevant for the mining task, or transforming them to fit in the tree structure just like XML elements; -replace some tag labels with equivalent labels, for example if a DTD defines different types of paragraphs (p1, p2, p3), it may be advised to rename them by a common label such as parag (this type of transformation requires some semantic knowledge of the DTD or the collection); -stripping off low levels of the tree which would be irrelevant in some mining tasks, for example italic or bold elements, or the details of a mathematic formula. -text processing similar to the one done for flat textual documents, such as removing stop words.

In document collections, content information may be composed of text and images that are associated with the leaves of the trees. In this chapter, we consider only textual parts of documents. The textual content is usually contextually dependent of the logical structure, which means that, even when interested in mining the content of documents, taking the structure into account may have a positive impact on the results. We also consider the case where we are interested only on the structure of the documents, without taking into account their content.

DISCOVERING FREQUENT TREE STRUCTURE

The broad use of XML as an exchange format for data exported from databases results in the availability of huge collections of XML documents in which the labels and their nesting represent the underlying tree schema of the data. Those collections of XML documents are possibly structurally heterogeneous because exported from a mass of different and autonomous data sources. Discovering commonalities between their structures is of primary importance for information integration and classification. In this setting, the focus is not the textual content of the documents but the labelled trees corresponding to their structure.

The discovery of frequent tree patterns from a huge collection of labelled trees is costly but has multiple applications, such as schema extraction from the web (or from frequent user queries like as proposed by [START_REF] Ji | X-warehouse: building query pattern-driven data[END_REF]), automatic creation of DTDs or XML schemas for sub-collections, uniform querying over heterogeneous data, and clustering together data supporting a given frequent tree pattern. Note that the resulting clusters are not necessarily disjoint, which offers different viewpoints on the data and different entry points for querying them.

Definitions and Examples

The most important operation when searching for frequent tree patterns in a collection of tree data is to determine if a tree pattern is included in a tree of the data. The definition used for this tree inclusion operation will determine the nature of the patterns that can be discovered, as well as the complexity of the discovery problem.

A tree inclusion definition is based on a tree homomorphism between the tree pattern and the trees of the data [START_REF] Kilpeläinen | Tree Matching Problems with Applications to Structured Text Databases[END_REF]. Different definitions of tree inclusion can be considered according to the preservation or not of (1) the labels (2) the ancestor relation (3) the order of siblings by the homomorphism.

For the first property concerning label preservation, we will only consider homomorphisms preserving labels as most modern approaches use this kind of homomorphism, and because with XML it is important to preserve the labels as they correspond to the tags of the XML documents.

The second property determines the tolerance to "noise" in the nesting of the nodes. If the parent-child relation is preserved, then the paths from root to leaves in the pattern will mimic exactly paths or sub-paths of the original tree. This definition is suitable for relatively homogeneous data (for example data coming from a single source). However, for truly heterogeneous data it is likely that a semantic relation between A and B will be expressed by different structural relationships between A and B within different XML documents written by different organizations. In such cases, the ancestor preserving definition is the only one capable of finding common patterns. Consider for example the trees of Fig. 3 describing the hierarchical relations in a public university in Japan and in France. Even if both hierarchies are different, in both cases "Professor" is an ancestor of "PhD Student", so the common pattern can be found. As simple as this pattern is, it shows that there are some common points between both trees. On the other hand, an inclusion definition based on the preservation of parent-child relation would not have found any common pattern because of the differences between the internal nodes of both trees.

The third property about the order of the siblings has also an influence on the kind of data that it is possible to handle. As XML documents are ordered, one could expect the preservation of the order of siblings in the tree inclusion definition to be mandatory. This may be true for homogeneous collections of data, but with heterogeneous data, different organizations may order the nodes of the documents differently. Consider the two example documents of Fig. 4 about car descriptions: the important point when discovering patterns is that a "Car" has a "Model" and a "Color", no matter their order. The complexity of testing the tree inclusion varies with the definition used [START_REF] Kilpeläinen | Tree Matching Problems with Applications to Structured Text Databases[END_REF].

Frequent Tree Discovery Algorithms

Frequent tree discovery is a very computationally intensive task; hence the design of the discovery algorithm is of a central importance. The algorithm must ensure at the same time the quality of the outputs, a fast execution, and avoid consuming too much memory especially

Japan France

Professor Professor

Common pattern

Car Model Color

Car

Color Model when datasets are big. There is currently no perfect algorithm, but many algorithms have been designed and each of them has its strengths and weaknesses. We review the existing algorithms, classifying them according to two main design principles, namely the edge-centric approach and the tile-centric approach.

Basic definitions

Let the data be a set of trees {T 1 ,…,T N }.

A tree T occurs in the data if there exists a tree T i in the data such that T is included in T i .

A tree T is frequent in the data according to an absolute frequency threshold ε if T occurs in more than ε trees of the data. The trees of the data {T i1 ,…T im } where T occurs are called the support of T.

A tree T is a closed frequent tree of the data if T is frequent with support {T i1 ,…T im } and T is the biggest tree for this support, i.e. there exist no other frequent tree T' with support {T i1 ,…T im } such as T is included in T'.

Edge-centric approaches

Designing a tree mining algorithm from scratch is quite a challenge, and as is often the case with such problems, it is good to start on solid well known ground. A tree can be seen as a set of edges, so a frequent tree can as well be seen as a frequent set of edges. Finding a frequent set of edges is easy, and since the seminal paper on the Apriori algorithm [START_REF] Agrawal | Fast Algorithms for Mining Association Rules in Large Databases[END_REF], there has been a tremendous amount of research on algorithms for discovering frequent itemsets in transactional data (a transaction is a set of elements and an itemset is a set of elements being a subset of one or more transactions). This was the starting point of the TreeFinder algorithm [START_REF] Termier | Treefinder: a first step towards xml data mining[END_REF], which first finds all the frequent set of edges, and then rebuilds the trees from the edges using an operation borrowed from inductive logic programming (ILP), the Least General Generalization [START_REF] Plotkin | A note on inductive generalisation[END_REF]. Though being able to find interesting patterns by application of well know algorithms, the method falls short of completeness in some cases, reducing its practical usability.

However, many other methods for mining structured data have been derived from the very principle of the Apriori algorithm. [START_REF] Inokuchi | An Apriori-based Algorithm for Mining Frequent Substructures from Graph Data[END_REF] presented AGM (Apriori Graph Miner), an algorithm for mining general graphs, based on the generate and test principle which is the heart of Apriori. Later on, many tree mining algorithms were designed upon this principle, including specificities for efficient tree mining.

The idea of Apriori to find all the frequent itemsets is to generate candidate itemsets, and to evaluate the frequency of such candidates against the transaction database. If a candidate is frequent, it is flagged as such, and it will also be the base of new, longer candidates. The Apriori algorithm is levelwise: it starts from candidates with only one element, and then processes iteratively candidates with 2,3,...,n elements. The efficiency of the search is ensured by the anti-monotony principle, which states that if an itemset I is infrequent, then all the itemsets I' ⊇ I are also infrequent. So when a candidate is evaluated as infrequent, it is not necessary to expand it further, which reduces considerably the search space.

This method can be transposed nicely to trees, by replacing the set elements by tree edges.

The first iteration will be to find frequent trees with one edge; the second one will join these trees with one edge to find all frequent trees with two edges, and so on. However, a problem specific to trees arises: a tree can be built by adding edges in many different ways, and so all the different intermediary steps leading to the same tree will be considered by the algorithm, as shown in Fig. 5. This would result in doing a lot of redundant work for each tree. The solution to this problem, found independently by [START_REF] Asai | Efficient Substructure Discovery from Large Semi-structured Data[END_REF] and [START_REF] Zaki | XRules: An effective structural classifier for XML data[END_REF], is to force the edge expansion to be done in a unique way, along the rightmost branch of the tree. This technique is called rightmost tree expansion and is the basis of most frequent tree mining algorithms. Both of the previously cited algorithms mine ordered trees. To be able to mine unordered trees, [START_REF] Asai | Efficient Substructure Discovery from Large Semi-structured Data[END_REF] and [START_REF] Nijssen | Efficient discovery of frequent unordered trees[END_REF] independently proposed to use canonical forms. A canonical form of a tree pattern is a unique representative for all tree patterns that differ only on the order of the siblings.

However, finding all the frequent tree patterns is a very computation-time expensive task. [START_REF] Chi | CMTreeMiner: Mining both closed and maximal frequent subtrees[END_REF] proposed the CMTreeMiner algorithm that improves the previous algorithms by searching only closed frequent trees, with performance improvements over one order of magnitude. Recently, [START_REF] Arimura | An Output-Polynomial Time Algorithm for Mining Frequent Closed Attribute Trees[END_REF] proposed the CLOATT algorithm for mining closed frequent attribute trees, with a proved output-polynomial complexity.

Tile-centric approach

The previous approaches discover the frequent tree patterns by reconstructing the tree' s edge by edge. However, especially in case of trees with large number of nodes, it can be beneficial to have an approach that expands trees with several edges at a time instead of single edges. Such an approach is represented by the Dryade family of algorithms [START_REF] Termier | DRYADE: a new approach for discovering closed frequent trees in heterogeneous tree databases[END_REF][START_REF] Termier | Efficient mining of high branching factor attribute trees[END_REF], in which the closed frequent trees of a given step are built by hooking at the leaves of the (closed) frequent trees of the previous step full subtrees of depth 1 called tiles. In this way, the closed frequent trees are built by increasing levels of depth.

Definition: A tile is a closed frequent tree of depth 1.

It can easily be shown that any closed frequent tree can be decomposed into a set of tiles. So the approach used by the Dryade family of algorithms is to first compute all the tiles that are in the data, and then to assemble these tiles together in order to discover the closed frequent trees.

This approach will be illustrated through the DryadeParent algorithm [START_REF] Termier | Efficient mining of high branching factor attribute trees[END_REF]. This algorithm uses the same tree inclusion definition as CMTreeMiner (the isomorphism preserves the parent-child relation and does not preserve siblings order), but is limited to the discovery of attribute trees. The trees of Fig. 6 will be used as data for a running example, with a minimal frequency threshold of 2 trees. The algorithm can be divided into several steps. The preliminary step is to discover the tiles.

Then the iterative part of the algorithm consists in hooking together those tiles.

Discovering the tiles: As defined before, the tiles are the closed frequent trees of depth 1.

Instead of finding all the tiles, it is simpler to solve the problem of finding all the tiles whose root has label a, for any a ∈ S. This problem boils down to finding all the closed frequent sets of children for the nodes of label a in the data. This problem can easily be solved by using any

A B C D E H G F K I A B C D E H G F I I A A B C G H A B C G H J C F I D K T 1 T 2 T 3 T 4 T 5
closed frequent itemset miner. DryadeParent uses the LCM2 algorithm [START_REF] Uno | LCM v2.0: Efficient mining algorithms for frequent/closed/maximal itemsets[END_REF] which is the fastest algorithm available for this task. By iterating this method on all the labels of S, it is then easy to find all the tiles shown in Fig. 7. Hooking the tiles: The previously computed tiles can then be hooked together, i.e. a tile whose root has label a becomes a subtree of another tile having a leaf of label a to build more complex trees. A proper strategy is needed to avoid as much as possible constructing attributes trees that would be found unclosed in a later iteration. The DryadeParent 's strategy consists in constructing attributes trees which are isomorphic to the k first depth levels of the patterns, each iteration adding one depth level to the isomorphism. For this purpose, the first task of DryadeParent is to discover in the tiles those corresponding to the depth levels 0 and 1 of the patterns, the root tiles. Some of these tiles can be found immediately as they cannot be hooked on any other tile: they will be the starting point for the first iteration of DryadeParent. This is the case for Ti 1 in the example. For the rest of the root tiles, they can also be used as building blocks for other patterns: they will be used as root of a pattern only when it will become clear that they are not only a building block, to avoid generating unclosed attribute trees. In the example, this is the case for Ti 4 , which can be hooked on Ti 1 . Only in iteration 2 will this tile be used as a root tile to construct the pattern P 4 (see Fig. 8 for the closed frequent patterns discovered in the data). The computation of the set of tiles that must be hooked to the root tiles for building the next depth level of closed frequent attribute trees is delegated to a closed frequent itemset mining algorithm. They become starting points for the next iteration.

The whole process is shown in Fig. 8. On the root tile Ti 1 (which is also the closed frequent pattern P 1 ), one can hook the tiles {Ti 2 , Ti 4 } or the tiles {Ti 6 , Ti 7 }, the latter leading to the pattern P 2 . Note the different supports of the two constructed attribute trees. From the hooking of {Ti 2 , Ti 4 } on Ti 1 , one can then hook the tile Ti 3 , leading to the pattern P 3 . The tile Ti 4 is not only a building block of P 1 , it also has an occurrence which does not appear in P 3 (see tree T 5 ): it is used as a root tile, and the only possible hooking on it is Ti 5 , leading to the pattern P 4 . Support: The soundness and completeness of this hooking mechanism have been proved [START_REF] Termier | DRYADE: a new approach for discovering closed frequent trees in heterogeneous tree databases[END_REF]. It has also been shown [START_REF] Termier | Efficient mining of high branching factor attribute trees[END_REF] that DryadeParent has excellent computationtime performances. It over performs by several orders of magnitude CMTreeMiner when the closed frequent trees to be found have a high average branching factor. Concretely, this means that when handling thousands of XML documents, containing a pattern having 100 nodes, DryadeParent will be able to answer in few seconds, sometimes nearly instantly, allowing real-time use in an interactive process. On the other hand, CMTreeMiner will need several minutes to handle the same data, making interactive use problematic.

{T 1 , T 2 , T 3 , T 4 } {T 1 , T 2 } {T 1 , T 2 } {T 1 , T 2 , T 5 } Support: {T 1 , T 2 , T 5 } {T 3 , T 4 } {T 3 , T 4 }

CLASSIFICATION AND CLUSTERING

In this section, we consider various approaches to XML document classification and clustering, two important mining tasks largely explored for data or textual documents. As for

A B C A B C A B C D E F H G C F C F I A B C D E G H F Iteration 1
Iteration 2

Iteration 3

P 1 P 2 P 3 P 4 Support: {T 1 , T 2 , T 3 , T 4 } Support: {T 1 , T 2 } Support: {T 3 , T 4 } Support: {T 1 , T 2 , T 5 } Support: {T 1 , T 2 , T 5 } Support: {T 1 , T 2 } I
XML documents, these tasks can be split into sub-tasks that involve the structure only or both the structure and content of the documents.

Classification and clustering are based on a notion of distance. Since XML documents are represented by trees, a natural idea to adapt traditional methods to XML documents would be to use a tree distance, for example the edit distance between two ordered labelled trees proposed by [START_REF] Zang | Simple fast algorithms for the editing distance between trees and related problems[END_REF], that consists in counting the number of editing operations (add, delete, change the label of a node, etc.) needed to transform a tree into another one. Tree edit distances may differ by the set of editing operations they allow. However, algorithms based on tree edit distances (Chawathe et al., 1996;[START_REF] Nierman | Evaluating Structural Similarity in XML Documents[END_REF] have a time complexity O(MN), M and N being the number of nodes in the two trees to be compared, which is too high for practical applications. Some approaches therefore replace the original trees by structural summaries [START_REF] Dalamagas | Clustering In Proceedings of the 3rd Helenic Conferenceon Methods and Applications of Artificial Intelligence[END_REF] or s-graphs [START_REF] Lian | An Efficient and Scalable Algorithm for Clustering XML Documents by Structure[END_REF]) that only retain the intrinsic structure of the tree: for example reducing a list of elements to a single element, or flattening recursive structures. Fig. 9 gives an example of tree summary. Representation Using Attribute-Value Structure [START_REF] Candillier | Transforming XML trees for efficient classification and clustering[END_REF] investigate the use of a different kind of representation for the manipulation of XML documents. The idea is to transform the trees into sets of attributevalues pairs, so as to be able to apply various existing methods of classification and clustering on such data, and benefit from their strengths. They propose to construct the following attributes from a set of available XML trees:

• the set of tags labelling the nodes of the trees; • the set of parent-child and next-sibling relations (whose domain is the set of pairs of tags labelling the nodes); • the set of distinct paths (including sub-paths), starting from the root (whose domain is the set of finite sequences of tags labelling the nodes).

So they create as many new attributes as distinct features are encountered in the training set.

And for each of them, their value for a given document is the number of their occurrences in this document. Finally, they also define as many new attributes as there are absolute distinct node positions in the trees. For every identifier of a node position, the value of the attribute for a document is the arity of the node, which is the count of its child nodes in the document. So the new introduced attributes all take their value into the set of natural numbers.

Such representation could lead to a high number of generated attributes. So the algorithms used to tackle such new datasets should be able to handle many attributes, and to perform feature selection during their learning process. In a classification task, C5 [START_REF] Quinlan | Data mining tools see5 and c5.0[END_REF] is for example well suited. In a clustering task, a subspace clustering algorithm, that is a clustering algorithm able to characterize every distinct cluster on a limited number of attributes (eventually distinct for each cluster), should be used.

Thus, they used SSC [START_REF] Candillier | SSC: Statistical Subspace Clustering[END_REF], a subspace clustering algorithm that has been shown to be effective, and that is able to provide as output an interpretable representation of the clusters found, as a set of rules. They adapted SSC for the clustering and the classification of XML documents, so that the new methods also benefit from the major advantage of producing classifiers that are understandable.

So far, this strategy has been applied to the INEX 2005 collections for mining XML documents, both for the classification task and for the clustering task using the structural description of XML documents alone. The results obtained with such a strategy are very good. In particular, it has been shown to be robust even with noisy data. Besides, the produced classifiers are very understandable. Fig. 10 shows for example the decision tree obtained when classifying a collection of movie description into eleven classes. For instance, the membership to class 8 only depends on the presence of tags named movie, film, table and li, and the absence of parent-child relation between tags named p and i in the document. By using such a transformation strategy, part of the information included in the trees is lost, but the data are manipulated more easily and the results are more understandable. However, some differences between trees could be hidden when using such a transformation. Indeed, a swap between two sub-trees of a given tree can lead to a very different tree, although its attribute-value representation proposed here would be very similar to the one of the initial tree. So other types of transformation should be considered when the order of siblings is to be taken in account.

Finally, such a strategy should be generalized in order to perform classification or clustering of XML documents collections using both the structural description and the textual content of the documents. The most direct way to do this would be to consider the textual content of the documents as simple bag-of-words, but more complex transformations could also be considered.

Representing Documents by a Set of Paths [START_REF] Vercoustre | A flexible structuredbased representation for XML document mining[END_REF] have been motivated by clustering XML documents based on their structure only or both the structure and content. Like in the previous approach, they use a simplified tree representation to avoid the complexity problems of tree clustering. They define a flexible representation of XML documents based on a subset of their paths, generated according to some criteria, such as the length of the paths, whether they start at the root (root paths), or end at a leaf (leaf ending paths). By considering those sub-paths as words, they can use standard methods for vocabulary reduction (based on their frequency), and simple clustering methods such as K-means that scale well.

Basic Definitions

Let p= {x 1 ,...,x p } be a path of tree T as defined in section 2; p is a root path if x 1 = root(T); p is a leaf ending path if x p is a leaf of T; p is a complete path if it is a root path and a leaf ending path. The length of a path is the number of nodes in the path. A path expression is represented by the expression s= s 1 .s 2 …s p-1 .s p where s i =label(x i ). Such expressions do not distinguish between two siblings with the same label, which means that, in this approach, two paths are regarded as equivalent of they correspond to the same path expression.

Let u=(s, t) be a node of tree T, where t is the textual content of u. Let w be a word. u contains w if w ⊂ t or if there exists a path {u, …, v}, v=(s',t') such that w ⊂ t'.

If u contains w, and p= {x 1 ,...,u} is a path, we call p' =(p,w} a text path and we code it by s 1 .s 2 …s p-1 .s p .w where s i =label(x i ).

It means that a text path extends a path p (possibly non terminal) with a word contains in any of the leaves of its subtrees. If W={w i | w i ⊂ t} then s 1 .s 2 …s p-1 .s p .w i, for w i ∈ W, are all the text paths associated to path p.

Using those definitions, we can now introduce a family of representations for an XML document d using the standard vector model, as: R(d)= Σ i f i p i, for all path p i = s 1 .s 2 …s p-1 .s p in d where m ≤ |p i | ≤ n, 1 ≤ m ≤ n, m and n two numbers given a priori; f i is the frequency of the path p i in d.

When interested by both the structure and the content of documents, it is possible to use both text paths and paths, or text paths only. For specific values of m and n, this model is equivalent to some other models that have been proposed before: for m=n=1, it corresponds to the naïve model used by [START_REF] Doucet | Naïve clustering of a large XML document collection[END_REF], where documents are represented by a bag of tags, or a bag of words and tags. Representing documents by their complete paths has been proposed by [START_REF] Yoon | BitCube: A Three-Dimensional Bitmap Indexing for XML Documents[END_REF] in their bitmap model, as well as an extension using complete text paths. [START_REF] Yi | A classifier for semi-structured documents[END_REF] propose the Structure Vector Model where a document is represented by all its paths of length between 1 and the height h of the document tree. The frequency of terms associated with a path is relative to the subtree associated with that path. The representation developed by [START_REF] Liu | XML Clustering by Principal Component Analysis[END_REF] is based on paths of length smaller than L, although they can also fix the level in the tree where the paths must start. It also includes the definitions of leaf-ending paths as well as root-beginning paths, of length less than L.

The motivation for a flexible choice of paths in the document is that some analysis or clustering tasks may be interested in the top part of the tree, the lower parts of the tree, or possibly parts in the middle. An example would be clustering very heterogeneous collections based on the structure, where the partition can be done by looking at the top level elements only. At the opposite end of the spectrum, if one wants to cluster documents based mostly on the text, it could be appropriate to add some limited context just above the text (leaf-ending paths). Another motivation in using paths was to fully represent lists of elements, through their path frequency, as lists are an important feature of XML documents that should be taken into account in some clustering tasks.

By considering those paths as words (with their frequency), it is possible to use standard methods for vocabulary reduction, and simple clustering methods such as K-means. However, clustering algorithms based on the vector model rely on the independence of the various dimensions (modalities) for calculating the distance between the vectors. Although it is not always verified in practice with words in texts, it usually works fine. In the case where words are paths in the document tree, there is an obvious dependency between embedded sub-paths. To deal with the problem of dependency, one can partition the paths by their length and treat each set of paths as a different variable, using a clustering algorithm such as the one proposed by [START_REF] Celeux | Classification Automatique des Données, Environnement statistique et informatique[END_REF] in which the standard Euclidian distance between clusters is replaced by a distance that takes in account the different variables and the modalities within the variables as follows:

∑∑ = = - = p k m j k j k j k y x y x d 1 1 2 ) ( ) , (
where p is the number of variables, and m k is the number of modalities for the variable k.

The approach has been successfully applied to the INEX collections for the structure only tasks. As an output, the clustering algorithm provides not only the set of clusters but discriminate representatives for each cluster that characterize each of them. Since the representatives are paths, it could be interesting to reconstruct sub-trees from those paths in order to provide a more compact representation of the clusters. This should be feasible, at least for root paths.

When considering document content as well as structure, paths are extended with the individual words of the text contained in the terminal node of each path (not necessarily a leaf node). While it works well for relatively small collections, it does not scale well for very large collections and broad trees where the number of paths, especially leaf-ending paths would grow exponentially. Complementary ways of reducing the vocabulary are needed, possibly from relative frequency of words within their specific paths rather than within the document they belong to.

Stochastic Generative Model

Generative models are well-known in the field of Machine Learning. They are used for different applications and particularly for classification and clustering. Generative models allow us to compute the probability of an XML document using a set of parameters describing a stochastic process (that is ) / ( θ d P where d is an XML document and θ is a set of parameters). In this part, we describe the family of models proposed by Denoyer & Gallinari (2004). They propose to model the statistical dependencies between the nodes of a semistructured document using the belief network formalism. These models consider that a document d is the realization of a random vector D whose elements are discrete random variables corresponding to each structural node or content node (text nodes) of the document. Each document is transformed into a belief network, all the networks sharing the same set of parameters. The probability of a document is then computed as the joint probability of the corresponding network and this probability can be computed under different assumptions of statistical dependencies. Each assumption aims at capturing a particular type of structural information, for example the left-sibling information, or the parent information.

This model is able to deal with a very large amount of data. Moreover, its learning complexity is linear with respect to the size of the documents. This type of model has been used both for the categorization and the clustering of XML documents and the authors have proposed extensions that take into account different information content (text, pictures,...) for the multimedia filtering task [START_REF] Denoyer | Structured Multimedia Document Classification[END_REF]. A discriminative algorithm has also been developed for the categorization task. On different XML corpora, this model has better performances than state-of-the art models for categorization of textual documents that do not use the structural information (Denoyer & Gallinari, 2004).

For simplification, we describe the model only for textual documents, using the example of Fig. 11. Extensions for multimedia documents are considered by Denoyer et al (2004).

Modelling documents with Bayesian networks

Let us first introduce some notations: • Let C be a discrete random variable which represents a class from the set of classes C.

• Let Λ be the set of all the possible labels for a structural node.

• Let V be the set of all the possible words. V * denotes the set of all possible word sequences, including the empty one. Bayesian networks offer a suitable framework for modelling the dependencies and relations between the different elements in a structured document. A network model is associated with each document. Since the focus here is on the logical document structure, each network is defined according to the corresponding document structure. For the classification task, the network parameters are learned using all the documents from the same class in the training set. Documents from the same class then share their parameters and there is one set of such parameters for each class.

Different networks could be used for modelling a document, depending on which type of relation one would like to take into account. We only consider here the explicit document structure and we will not try to uncover any hidden structure between the document elements. Some of the natural relations which could then be modelled are: "is a descendant of" in the document tree, "is a sibling of", "is a successor of", given a preorder visit of the document tree, and combinations of these different possibilities. Fig. 12 and13 give two examples of document models encapsulating different relations for the document tree in Fig. 11. In the simplest one (Fig. 12), the network structure is similar to the document tree structure, as it only encodes the 'is a descendant of" relation. The second model (Fig. 13) makes use of a Tree Augmented Network (TAN) at each level of the tree and takes into account an ordering relation between structural siblings and subtrees. As usual there is a trade-off between complexity and efficiency. Tests performed with different models did not show a clear superiority of one model over the others with respect to the classification performances. For simplicity, from now on, we then consider tree-like Bayesian networks. The network structure is built from the document tree, but need not be identical to this tree.

⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = ∏ ∏ ∏ = = = ) , / ( ) ), ( | ( ) ( ) , ( , | | 1 / 1 | | 1 , c s w P c s pa s P c P c d P i d d i j d i t j i d i d d i d i (2)

Learning

In order to estimate the joint probability of each document and each class, the model parameters must be learned from a training set of documents. We do not describe here the learning algorithm which is fully explained in (Denoyer & Gallinari, 2004).

Experiments

Many experiments have been made with this model on different corpora (INEX, WebKB, NetProtect,WIPO). Denoyer & Gallinari (2004) for more details on these collections. Table 1 gives the results of different models on three XML corpora :

• the INEX corpus composed of about 12,000 XML documents that describe scientific articles (18 categories) • the WIPO corpus composed of 10,900 XML documents that describe patents (15 categories), and • the WebKB corpus composed of 8282 XHTML documents (7 categories).

The different methods are compared using a classic F1 score (micro and macro):

• NB is the Naive Bayes method on flat documents,

• RB is the model proposed here • SVM TF-IDF is the classic SVM method for classification of flat documents using TF-IDF vectors, and • Fisher RB is a kernel method that allows us to use our Belief network model with a support vector machine.

The results in Table 1 show that the RB model improves the baseline models.

Micro

Future trends for the stochastic generative model

We have presented a generative model for structured documents. It is based on Bayesian networks and allows modeling the structure and the content of documents. It has been tested for the classical task of whole document classification. Experiments show that the model behaves well on a variety of situations. Further investigations are needed for analyzing its behavior on document fragments classification. The model could also be modified for learning implicit relations between document elements besides using the explicit structure. An interesting aspect of the generative model is that it could be used for other tasks relevant to IR. It could serve as a basis for clustering structured documents. The natural solution is to consider a mixture of Bayesian network models where parameters do depend on the mixture component instead of the class as it is the case here. Schema-mapping and automatic document structuring are new tasks that are currently being investigated in the database and IR communities. The potential of the model for performing inference on document parts when information is missing in the document will be helpful for this type of application.

Preliminaries experiments about automatic document structuring are described by [START_REF] Denoyer | Document structure matching for heterogeneous corpora[END_REF].

CONCLUSION

XML is becoming a standard in many applications because of its universal and powerful tree structure. On the internet for example, unstructured documents are being replaced by such structured documents, so that approaches that have been designed to tackle internet resources need to be revisited in order to take advantage of the new structured nature of the documents.

The tree structure of XML documents can be seen as information by itself. When searching for the origin of a document for example, looking at its tree structure can be sufficient because different sources may use different structures to generate their documents. Clustering XML documents using their structure only can help methods designed to handle homogeneous XML collections work also on heterogeneous collections. But taking the structure of the documents into account may also have a positive impact on the results even if we are only interested in classifying the documents according to their content.

The organisation of a document may indeed differ from one context to another. The structure of a document can for example help distinguish an article concerning history to another one about science. Moreover, generic models that combine structure and content may help put the right context or weight on smaller parts of the documents.

On the other hand, many existing approaches designed to handle data represented by trees suffer from high complexities, limiting their use to small volumes of data. Hopefully, as we have shown in this chapter, some transformations of XML tree structures can be used to simplify their representations, still preserving some of their interesting structural properties, and thus providing new ways to efficiently manage high volumes of such data.

As a summary, since XML collections will become more and more important, and since their tree structure can help improve ML and IR tasks on such data, a good compromise has to be found when designing a new method for XML, so that the information contained in the structure is used but does not affect too much its complexity.

Another important challenge concerns the output provided by such methods. In that field, we have highlighted some methods that can exhibit the resulting tree patterns, classifiers or cluster representatives, and therefore can support analysts in mining tasks.

Fig. 1

 1 Fig. 1 An XML document describing the movie "Pierrot le Fou", by Jean-Luc Godard

Fig. 3 :

 3 Fig. 3: Academic hierarchical relations inJapan and in France, common pattern between both.

Fig. 4 :

 4 Fig.4: Two tree structure describing car ads, the same contents is expressed with a different sibling order.

Fig. 5 :

 5 Fig.5: All the paths to build a single tree by edge adding, and the redundancies induced by creating all these intermediary steps.

Fig. 6 :

 6 Fig. 6: Example data.

Fig. 7 :

 7 Fig. 7: The tiles found in trees of Fig.6 with minimal frequency threshold set to 2.

Fig. 8 :

 8 Fig. 8: DryadeParent discovery process. The closed frequent attribute trees outputted as result are enclosed in dashed boxes.

Fig 9 .

 9 Fig 9. Tree summary.

Fig. 10 :

 10 Fig. 10: Example of understandable classifier obtained on an XML data collection by transforming the documents into sets of attribute-values. Tag(T) refers to the number of occurrences of the given tag T in the document, Parent(A-B) to the number of parent-child relations between tags A and B, Nb(0.0.0) to the arity of the first grand-child node from the root, S* to comparisons between models based on the next-sibling relations, and P* to a comparison based on the paths in the document.

Fig. 11 :

 11 Fig. 11: A tree representation for a structured document composed of an introduction and two sections. Whitebackground nodes and pink/grey background nodes are respectively structural and content nodes.

Fig. 12 :

 12 Fig. 12: The final Bayesian network encoding "is a descendant of" relation.

Fig. 13 :

 13 Fig. 13: The final Bayesian network making use of a TAN network at each level of the tree.

  ) and |d| is the number of structural nodes. d is a realization of a random vector D. In the following, all nodes are supposed to have a unique identifier, indicated here as superscript i.

	• Let d be a structured document consisting of a set of features (s 1 d ,...s	|d| d ,t	1 d ,...,t	|d| d ) where s	i d is
	the label of the i-th structural node of d (s	i d ∈Λ), t	i d is the textual content of this i-th node
	(t	i d ∈V

*

Table 1 .

 1 Results of the RB model on different XML textual corpora

		-F1	Macro-F1
	NB	0.59	0.605
	RB model	0.619	0.622
	SVM TF-IDF	0.534	0.564
	Fisher RB	0.661	0.668
		INEX
		Micro-F1	Macro-F1
	NB	0.801	0.706
	RB model	0.827	0.743
	SVM TF-IDF	0.737	0.651
	Fisher RB	0.823	0.738
		WebKB
		Micro-F1	Macro-F1
	NB	0.662	0.565
	RB model	0.677	0.604
	SVM TF-IDF	0.822	0.71
	Fisher RB	0.862	0.715
		WIPO

from their respective distribution which depends on s and the document class. The document depth could be another parameter of the model. Document length and depth distributions are omitted in the model since the corresponding terms fall out for the classification problems considered here.

Using such a network, we can write the joint content and structure probability that document d belongs to class c: