Sylvana C C Robbers

Dr V A Floor

Van Oort
email: f.vanoort@erasmusmc.nl.

J C Polderman

Meike Bartels

Dorret I Boomsma

Frank C Verhulst

Gitta H Lubke

Anja C Huizink

Erasmus Van Oort

Mc

Trajectories of CBCL Attention Problems in Childhood

Keywords: ADHD, attention problems, developmental trajectories, twins, singletons CBCL = Child Behavior Checklist; BIC = Bayesian Information Criterion

Background:

The first aim of this study was to identify developmental trajectories of Attention Problems in twins followed from age 6 to 12 years. Second, we investigated whether singletons follow similar trajectories.

Methods: Maternal longitudinal ratings on the Attention Problems (AP) subscale of the Child Behavior Checklist were obtained for a sample of 12,486 twins from the Netherlands Twin Register and for a general population sample of 1,346 singletons. Trajectories were analyzed by growth mixture modeling (GMM) in twins, and compared with singletons. Teacher ratings on the AP subscale of the Teachers" Report Form were available for 7,179 twins and 1,211 singletons, and were used for crosssectional mean comparisons at each age. All analyses were conducted for boys and girls separately.

Results:

We identified three linear trajectories in both boys and girls, i.e., stable low (62-71%), lowincreasing (15-18%), and high-decreasing (14-21%). Singletons followed three identical trajectories, with similar class proportions. Teacher ratings yielded no differences in mean levels of Attention Problems between twins and singletons.

Conclusions:

The development of Attention Problems from age 6 to 12 years can be characterized by stable low, low-increasing, and high-decreasing developmental trajectories. Twins and singletons are comparable with respect to the development of Attention Problems in childhood.

Introduction

Attention Deficit Hyperactivity Disorder (ADHD) is characterized by inappropriate levels of inattention, hyperactivity, and/or impulsiveness. ADHD has a great impact on affected children and their families in terms of academic, social and behavioral dysfunction [START_REF] Mannuzza | Long-term prognosis in attention-deficit/hyperactivity disorder[END_REF][START_REF] Mannuzza | Significance of childhood conduct problems to later development of conduct disorder among children with ADHD: A prospective follow-up study[END_REF], and is at the moment the most common neurodevelopmental disorder of childhood with 5% of children worldwide affected [START_REF] Polanczyk | The worldwide prevalence of ADHD: A systematic review and metaregression analysis[END_REF].

ADHD symptoms are likely to be continuously distributed in childhood through adolescence with ADHD being on the extreme tail of the distribution [START_REF] Hay | A twin study of attentiondeficit/hyperactivity disorder dimensions rated by the Strengths and Weaknesses of ADHD-Symptoms and Normal-Behavior (SWAN) scale[END_REF][START_REF] Levy | Attention-deficit hyperactivity disorder: A category or a continuum? Genetic analysis of a large-scale twin study[END_REF][START_REF] Lubke | Maternal ratings of attention problems in ADHD: evidence for the existence of a continuum[END_REF][START_REF] Lubke | Subtypes versus severity differences in attention deficit hyperactivity disorder in the Northern Finnish Birth Cohort[END_REF][START_REF] Polderman | Across the continuum of attention skills: a twin study of the SWAN ADHD rating scale[END_REF]. Typical presentations of ADHD symptoms in childhood are premature changes of activity, restless when calm expected, distracted by the environment, forgetful, acting out of turn, intrusions on peers, and thoughtless rule-breaking [START_REF] Taylor | Disorders of attention and activity[END_REF].

Community studies on the development of ADHD symptoms in childhood report somewhat mixed findings. A number of them show decreases in ADHD symptoms. For example, in an American longitudinal sample of 6-to 20-year-old boys, ADHD symptoms declined with increasing age, with hyperactivity symptoms declining at a higher rate than inattention symptoms [START_REF] Biederman | Age-dependent decline of symptoms of attention deficit hyperactivity disorder: impact of remission definition and symptom type[END_REF]. In a sample of 8-to 17-year-old Swedish twins levels of inattention remained relatively constant, whereas levels of hyperactivity-impulsivity declined with increasing age [START_REF] Larsson | Genetic contributions to the development of ADHD subtypes from childhood to adolescence[END_REF]. Another American longitudinal study showed that levels of ADHD symptoms were generally constant until the teen years, and declined from there [START_REF] Monuteaux | The influence of sex on the course and psychiatric correlates of ADHD from childhood to adolescence: A longitudinal study[END_REF]. Similarly, mean levels of ADHD symptoms decreased after age 10 in Dutch twins [START_REF] Rietveld | Heritability of attention problems in children: longitudinal results from a study of twins, age 3 to 12[END_REF] and singletons [START_REF] Bongers | The normative development of child and adolescent problem behavior[END_REF]. An Australian general population sample showed only minimal age differences in the number of ADHD symptoms in children aged 5 to 11 years [START_REF] Gomez | DSM-IV AD/HD: Confirmatory factor models, prevalence, and gender and age differences based on parent and teacher ratings of Australian primary school children[END_REF]. The results of these studies may differ for various reasons, such as the use of different ADHD measures. Nonetheless, the general picture seems to be that the development of ADHD symptoms is relatively stable in childhood with a possible decrease of symptoms starting around the age of 10 years.

The development of ADHD symptoms can also be investigated by examining subgroups with distinct developmental trajectories. Only few studies analyzed different developmental trajectories of ADHD symptoms in school-age children. Two trajectories were identified in a high-risk sample of American children aged 7 to 16 years of families with parental alcoholism: one with stable low levels, and one with stable high levels, the latter containing 57% of the children [START_REF] Jester | Inattention/hyperactivity and aggression from early childhood to adolescence: Heterogeneity of trajectories and differential influence of family environment characteristics[END_REF]. In a sample of Canadian boys from low socioeconomic areas, four trajectories of hyperactivity were identified from 6 to 15 years [32]. Roughly 6% of the children in this study followed a chronic high trajectory. The other children followed low or decreasing trajectories. In a general population sample of Dutch children aged 4 to 18 years, four developmental trajectories of ADHD symptoms were estimated, among which was a high trajectory with increasing scores into late childhood [START_REF] Van Lier | Which better predicts conduct problems? The relationship of trajectories of conduct problems with ODD and ADHD symptoms from childhood into adolescence[END_REF]. Three trajectories of ADHD symptoms were identified in a sample of children aged 8 to 14 years who were selected from high-risk schools: one with minimal problems, one that showed an increase and then a decrease in symptoms, and one that showed a decrease and then a slight increase in symptoms [START_REF] Malone | A mixture-model approach to linking ADHD to adolescent onset of illicit drug use[END_REF]. Recently, two hyperactivityimpulsivity trajectories (low, high-decreasing) and two inattention trajectories (low, high-increasing) were found in a population-based twin study [START_REF] Larsson | Developmental trajectories of DSM-IV symptoms of attention-deficit/hyperactivity disorder: genetic effects, family risk and associated psychopathology[END_REF]. Summarizing the results of these studies, two to four trajectories of ADHD symptoms were identified. Subgroups with specific developmental trajectories of ADHD symptoms should be investigated more thoroughly by using large representative samples of school-age children.

ADHD symptoms in twins and singletons

In the current study, data from twins were analyzed to estimate developmental trajectories of Attention Problems. Twin data are frequently used to study the heritability of ADHD symptoms, which usually varies between 50% and 80% [11, 14, 35-36, 40, 49]. An important assumption of twin studies is that the results can be generalized to the general population, which mainly includes singletons. The comparability of twins to singletons is however still being questioned for various reasons, such as more pre-and perinatal problems among twins that could result in a higher prevalence of behavioral problems in twins than in singletons [START_REF] Rutter | Annotation: Growing up as a twin: Twin-singleton differences in psychological development[END_REF]. However, many of these problems such as low birth weight and preterm birth are unlikely to have the same significance in twins as in singletons, as the etiology of these risk factors appears to be different in the two groups [START_REF] Phillips | Fetal growth and the fetal origins hypothesis in twins -Problems and perspectives[END_REF].

Despite the uncertainty about the representativeness and possibly increased vulnerability of twins, research on twin-singleton differences in ADHD symptoms is sparse and has been crosssectional so far. To our knowledge, there are three cross-sectional studies that compared levels of ADHD symptoms between twins and singletons. An Australian study found more ADHD symptoms in twins than in singletons aged 4 to 12 years [START_REF] Levy | Twin-sibling differences in parental reports of ADHD, speech, reading and behaviour problems[END_REF], while a study of 2-and 3-year-old Dutch twins found that twins showed slightly lower levels of ADHD symptoms than singletons [START_REF] Van Den Oord | A twin-singleton comparison of problem behaviour in 2-3-year-olds[END_REF]. In line with this study, an American study of 12-to 19-year-old twins and their non-twin siblings found some evidence for a higher prevalence of ADHD in the non-twin siblings, although this result was not consistently observed for all age groups and in both sexes [START_REF] Ehringer | Genetic and environmental contributions to common psychopathologies of childhood and adolescence: A study of twins and their siblings[END_REF]. Whether ADHD symptoms develop differently over time for twins versus singletons has not yet been investigated.

The present study

In the current study we will extend the findings of a recent study in 7-, 10-and 12-year-old boys from the Netherlands Twin Register, that showed three mainly quantitatively different latent classes of Attention Problems at each age, i.e., high-, moderate-, and low-scoring classes [START_REF] Lubke | Maternal ratings of attention problems in ADHD: evidence for the existence of a continuum[END_REF]. Our aim was to identify subgroups of children with specific developmental trajectories of Attention Problems from ages 6 to 12 years. We expected to find a minimum of three relatively stable trajectories (e.g., high-, moderate-, and low-scoring) with the majority of children having low levels of Attention Problems. Trajectories were expected to reflect slightly decreasing levels of Attention Problems late in childhood, as self-regulation increases with beginning puberty [3]. The second aim of this study was to investigate if singletons follow similar trajectories as twins. As in general most twins are physically healthy individuals who grow up under normal circumstances, we did not expect to find large differences between twins and singletons. Finally, it has been well established that ADHD symptoms are more prevalent in boys than in girls [START_REF] Biederman | Attention-deficit/hyperactivity disorder: a selective overview[END_REF][START_REF] Polanczyk | The worldwide prevalence of ADHD: A systematic review and metaregression analysis[END_REF]. Because we had two large samples of children, we were able to investigate the development of Attention Problems separately for boys and girls.

Methods

Subjects

Twin sample. All participating twins were volunteer members of the Netherlands Twin Register (NTR).

The NTR represents a twin family sample that is largely representative for the Dutch general population [START_REF] Bartels | Young Netherlands Twin Register (Y-NTR): A longitudinal multiple informant study of problem behavior[END_REF]. For the present study, data from twins born between 1986 and 1998 were analyzed.

Parents and teachers of twins received surveys by mail, around the twins" 7 th , 10

th and 12 th birthdays.

The exact ages (in years) of the twins at the time of completion of the surveys were calculated from date of birth of twins and date of completion of the surveys. The response rate at each measurement was 61-63% for mother reports. About 50% of the parents gave written permission to approach the teacher, and the subsequent teacher response rate was 74-78%. Attrition analyses revealed that, at ages 7 and 10, the level of socio-economic status (SES) was higher in families that returned the survey than in families that did not return the survey [START_REF] Derks | Assessment and genetic aetiology of attention problems, hyperactivity, and related disorders[END_REF]. Also, twins had higher levels of Attention Problems at ages 7 and 10 when the parents did not respond at the previous target age [START_REF] Derks | Assessment and genetic aetiology of attention problems, hyperactivity, and related disorders[END_REF]. However, the effect sizes were small, and it is therefore unlikely that attrition in the Netherlands Twin Register strongly affected the results.

Twin pairs were excluded if they suffered from a severe handicap, which interferes with daily functioning. Maternal ratings were available for 9,432 male twins and 9,718 female twins. A total of 6,219 twins were part of an opposite-sex pair and were all included in the analyses. There were 6,338 twins from same-sex male pairs, and 6,748 twins from same-sex female pairs. Since data obtained from twin pairs are not independent, one twin was randomly selected from the same-sex twin pairs. It was not necessary to randomly select one twin from the opposite-sex twin pairs, since data from boys and girls were analysed separately. We excluded 215 twins for whom information on socio-economic status was unknown. The final twin sample consisted of 6,161 boys and 6,325 girls. For 42% of this sample data were available from one assessment, for 29% from two assessments, and for 29% from three assessments. The smaller proportion of children with two or three assessments partly reflects the longitudinal design of the study, since not all children had reached ages 10 and 12 years by the time we ran our analyses.

For 3,506 boys and 3,673 girls, teacher ratings were available as well. For 71% of this sample teacher data were available from one assessment, for 26% from two assessments, and for 3% from three assessments.

Singleton sample. The data from singletons that were analyzed in this study came from the Zuid-Holland study, an ongoing longitudinal study of behavioral and emotional problems that started in 1983. The sample (N=2,600) was randomly drawn from municipal registers that list all residents in the Dutch province of Zuid-Holland, and represents a general population [START_REF] Verhulst | Mental health in Dutch children: A crosscultural comparison[END_REF]. Written informed consent was obtained after complete description of the study to the subjects. After the first measurement in 1983, the respondents were approached biennially. The current study uses data from Time 1 (1983) to Time 5 (1991). Response rates ranged from 80% to 85% at each measurement. All children who were between 6 and 12 years at any assessment (i.e., born between 1971 and 1979) were included (N=662 boys; N=684 girls). Singleton data that were fully contemporaneous to the twin data were not available. However, the first assessment of twins born in 1986 was only 2 years removed in time from the fifth assessment of the Zuid-Holland study (i.e., 1993, and 1991, respectively). Attrition analyses on all participants of the Zuid-Holland study showed that dropouts had lower SES. However, dropouts did not have higher levels of behavioral problems based on the Total Problems scale of the Child

Behavior Checklist [START_REF] Bongers | The normative development of child and adolescent problem behavior[END_REF].

Because of the selected age range and the design of the Zuid-Holland study with assessments every two years, longitudinal data could be used from maximum four assessments (e.g., a child who was 6 years old at Time 1, was 12 years old at Time 4). For 39% of the sample there were data from one assessment, for 26% from two assessments, for 23% from three assessments, and for 12% from four assessments. Most of the children for whom data were available from just one assessment were already 11 or 12 years old at Time 1. Teacher ratings were available for 580 boys and 631 girls, and were obtained at Time 1, Time 3, Time 4, and Time 5. No information from teachers was obtained at Time 2 owing to financial constraints. The teacher response rates were above 70% at each assessment. For 59% of this sample teacher data were available from one assessment, for 29% from two assessments, and for 12% from three assessments. By design, teacher data were available from just one assessment for children who were between 9 and 12 years old at Time 1.

Measures

Attention Problems. For both twins and singletons, maternal ratings were collected with the Attention Problems (AP) subscale of the Child Behavior Checklist (CBCL/4-18) [START_REF] Achenbach | Manual for the Child Behavior Checklist/4-18 and 1991 Profiles[END_REF][START_REF] Verhulst | Handleiding voor de CBCL/4-18[END_REF]. This scale includes 11 items such as "can"t sit still", "daydreams", and "can"t concentrate". It includes features of inattention, hyperactivity, and impulsivity. All items were scored on a 3-point scale, reflecting the occurrence of behavioral problems during the preceding 6 months: 0 if the item was not true, 1 if the item was somewhat or sometimes true, and 2 if the item was very true or often true. The two week test-retest correlation and the internal consistency of the AP scale are .83 and .67, respectively [START_REF] Achenbach | Manual for the Child Behavior Checklist/4-18 and 1991 Profiles[END_REF][START_REF] Verhulst | Handleiding voor de CBCL/4-18[END_REF]. Teacher ratings were collected using the Teachers" Report Form (TRF) [START_REF] Achenbach | Manual for the Teacher's Report Form and 1991 Profiles[END_REF][START_REF] Verhulst | Handleiding voor de Teacher's Report Form (TRF)[END_REF]. Teachers were instructed to rate the child"s behavior over the preceding 2 months. The AP subscale of the TRF consists of 20 items with the same response categories as the CBCL. The six week test-retest correlation is .83. The internal consistency coefficients are .90 in boys and .92 in girls [START_REF] Achenbach | Manual for the Teacher's Report Form and 1991 Profiles[END_REF][START_REF] Verhulst | Handleiding voor de Teacher's Report Form (TRF)[END_REF]. The TRF includes extra items that capture situational specific behaviors, such as "difficulty following directions", and "messy work".

Ten items of the CBCL-AP scale and the TRF-AP scale overlap.

Socio-economic status (SES).

For the twin sample, SES was either obtained from a full description of the occupation of the parents and subsequently coded [START_REF] Cbs | Standard Classification of Occupations[END_REF], or obtained by a nine-category classification scheme for occupations [START_REF] Erikson | Intergenerational class mobility in three Western European societies: England, France and Sweden[END_REF], combined with information on parental education. This information was recoded into three SES levels (i.e., low, middle, and high). For the singleton sample, SES was scored on a six-step scale of parental occupation [START_REF] Van Westerlaak | Beroepenklapper (Manual for occupational level)[END_REF], and was also recoded into three SES levels to allow comparison with the twin sample.

Data Analysis

In order to compare growth trajectories between twins and singletons, the singleton data were reordered as a function of chronological age instead of survey year. This was done by creating agedependent variables, equal to the ones used in the twin sample, resulting in a larger dataset with values that were missing by design [START_REF] Muthén | Mplus User's Guide[END_REF]. To determine trajectories of mother-rated AP, growth mixture modeling (GMM) was used to analyze the data, separately for twins and singletons, and separately for boys and girls (Mplus Version 5) [START_REF] Muthén | Mplus User's Guide[END_REF]. The trajectories were determined by latent growth factors, which model the intercepts and slopes of the individual growth trajectories. Models were tested with linear as well as quadratic effects. The latter represent a curvilinear development over time (e.g., first increasing, then decreasing). The trajectories were estimated using maximum likelihood with robust standard errors (MLR), which is robust regarding non-normality of the scores. MLR is similar to the full information maximum likelihood (FIML) method, in which missing data are not imputed, but parameters and standard errors are estimated directly using all the observed data [START_REF] Wothke | Longitudinal and multi-group modeling with missing data[END_REF].

Models were fit with an increasing number of classes and different within class structures (i.e., linear and quadratic growth). There is a trade-off between within class model complexity and number of classes where more classes can compensate for a less complex within class structure [START_REF] Lubke | Distinguishing between latent classes and continuous factors with categorical outcomes: Class invariance of parameters of factor mixture models[END_REF][START_REF] Lubke | Distinguishing between latent classes and continuous factors: Resolution by maximum likelihood?[END_REF].

Models with increasing numbers of classes can not be compared with likelihood ratio tests, since in that case the test statistic does not follow a chi-squared distribution. Therefore, the optimal number of classes, and the decision between linear versus quadratic growth, was determined by the model with the smallest Bayesian information criterion (BIC). In case of small BIC differences, the more parsimonious model was chosen.

To test for twin-singleton differences in the mean intercepts and slopes of the trajectories, we fit a mixture model with the optimal number of classes simultaneously for twins and singletons. We used a group dummy variable indicating twin versus singleton as known class membership such that, effectively, a multi-group model was fitted with a mixture model within each group. The mean intercepts, mean slopes, and intercept variances were then separately tested for equality by constraining them to be equal between twins and singletons (i.e., three tests with df=3 per sex). These tests were evaluated with scaled chi-square tests using the loglikelihood values. Differences in class proportions between twins and singletons were tested by means of a standard chi-square test for cross-tables. To control for SES differences between the samples, the latent growth factors were regressed on SES. Also, class membership was regressed on SES, so that SES predicted the log odds of the probability of belonging to a given class compared with the probability of belonging to another class. Because the models were estimated conditional on SES, families without data on SES had to be excluded from the analysis.

Because of the small number of multiple assessments with teacher ratings, trajectories of teacher-rated AP could not be examined. Instead, we analyzed the age-specific mean scores with SPSS15. To test for twin-singleton differences, analysis of variance (ANOVA) was performed using two fixed factors (i.e., twin/singleton status and SES). For these analyses, a statistical significance at the level of p<0.01 was chosen.

Results

A total of 2,665 twins (21%) had low SES, 8,401 twins (67%) had middle SES and 1,420 twins (12%) had high SES. A total of 734 singletons (55%) had low SES, 392 singletons (29%) had middle SES, and 220 singletons (16%) had high SES. Twins and singletons were not evenly distributed over the three SES levels (χ² (2) = 848.26, p<0.001).

< insert Table 1 >

Table 1 shows the model fit statistics for the linear and the quadratic models for twins. The models were fit with within-class intercept variability, whereas all slope factor variances were fixed to zero. The intercept variances were constrained to be equal between the classes in all models.

Estimating nonzero slope variances and class-specific intercept variances resulted in convergence problems for models with more than three classes, which is often an indication of overfitting (i.e., the fitted model is overly complex). For both boys and girls, a three-class linear model was the best fitting model given the LMR-LRT, BIC, and model parsimony. The quadratic models did not fit convincingly better than the linear models, as indicated by minimal BIC differences. More specifically, the BIC differences between the linear and the quadratic models were smaller than the BIC differences between the models with a different number of classes. < insert Figure 1 and Figure 2 > The intercept means of the three classes were equal between twins and singletons (boys: χ² Finally, the class proportions were not different for twins and singletons (boys χ² (2) = 1.76, p=0.41;

< insert

girls χ² (2) = 0.15, p=0.93).

Teacher ratings

Table 3 presents teacher-rated AP mean scores, which are corrected for SES differences between twins and singletons. For boys, analysis of variance (ANOVA) showed that there were no main effects of twin/singleton status on levels of AP (all p values >0.01). For girls, twins had significantly lower AP scores at age 12 than singletons (p<0.001). There were no main effects of twin/singleton status on AP scores for ages 6 to 11 years.

< insert Table 3 >

Discussion

In this longitudinal study we identified three linear trajectories of mother-rated Attention Problems in boys and girls from 6 to 12 years: stable low, low-increasing and high-decreasing symptom levels. Most of the children followed the stable low trajectory, which is what we hypothesized. Further, we expected two other stable trajectories with a possible decrease late in childhood. Instead of these stable trajectories we found a low-increasing trajectory, and a highdecreasing trajectory.

Our findings are in agreement with the study from Malone et al. [START_REF] Malone | A mixture-model approach to linking ADHD to adolescent onset of illicit drug use[END_REF] which identified three trajectories that, when considering children from middle childhood until early adolescence, included increasing and decreasing classes. Van Lier et al. [START_REF] Van Lier | Which better predicts conduct problems? The relationship of trajectories of conduct problems with ODD and ADHD symptoms from childhood into adolescence[END_REF] also identified a high-increasing trajectory in children from the Zuid-Holland Study using the DSM-oriented ADHD scale of the CBCL. Two earlier studies that reported a stable high trajectory included children with already elevated risk (i.e., parental alcoholism, and low-socioeconomic position) [START_REF] Jester | Inattention/hyperactivity and aggression from early childhood to adolescence: Heterogeneity of trajectories and differential influence of family environment characteristics[END_REF]32]. It is possible that a stable high trajectory only presents in high risk populations, or populations characterized by low use of pediatric health care. In the US low-socioeconomic groups have a lower use of pediatric care, while there is no association between SES and help seeking in the Netherlands, where there are no major financial constraints to receiving professional help [START_REF] Zwaanswijk | Help seeking for emotional and behavioural problems in children and adolescents: a review of recent literature[END_REF]. It could also be that a stable high trajectory appears only in children with both attention deficits and hyperactivity problems. In a general population study it may be more likely that a decreasing trajectory appears, in accordance with theory that attention deficits diminish as self-regulation increases, and in response to adequate treatment. These reasons may explain why a stable high trajectory was not identified in our study.

It might be argued that a 4 th class should be included, both for the boys and the girls.

However, an additional class did not provide additional information, and appeared to split the highdecreasing trajectory into two ordered classes. This seems to be an example of a so-called "indirect interpretation of mixture models" where classes do not represent different types of subjects, but rather approximate different parts of the joint distribution of observed data. Not including the 4 th class does not change the conceptual interpretation of the modeling results.

Mean parent-rated AP scores larger than 9 (up to age 11) or 10 (age 12) are in the subclinical range, and scores larger than 12 (up to age 11) or 13 (age 12) are considered clinical [START_REF] Achenbach | Manual for the Child Behavior Checklist/4-18 and 1991 Profiles[END_REF]. None of the trajectories exceeded these levels at any age. A post hoc analysis among the boys showed that 2.3% of the twins and 4.5% of the singletons had mean AP scores of 9 or higher on at least two assessments. About two-third of these children were assigned to the high-decreasing trajectory. Since DSM diagnoses of ADHD were not available, we could not investigate whether children with specific ADHD-subtypes would tend to be either in the low-increasing or high-decreasing class. However, it was found that children with a low AP-score obtained a negative ADHD diagnosis in 96% of the cases [START_REF] Derks | The relations between DISC-IV DSM-diagnoses of ADHD and multi-informant CBCL-AP syndrome scores[END_REF]. Furthermore, children with a high AP-score obtained a positive diagnosis in 59% (boys) and 36%

(girls) of the cases. Since hyperactivity tends to decrease over time [START_REF] Larsson | Developmental trajectories of DSM-IV symptoms of attention-deficit/hyperactivity disorder: genetic effects, family risk and associated psychopathology[END_REF], we hypothesize that children with the hyperactive-impulsive or the combined type of ADHD would be overrepresented in the highdecreasing trajectory. Children on the low-increasing trajectory seem at risk for having high levels of ADHD symptoms later in childhood. As this risk may arise from a combination of several genetic, biological and environmental factors [START_REF] Larsson | Developmental trajectories of DSM-IV symptoms of attention-deficit/hyperactivity disorder: genetic effects, family risk and associated psychopathology[END_REF][START_REF] Singh | Beyond polemics: science and ethics of ADHD[END_REF], further research is needed to identify specific predictors of the trajectories.

Linear growth provided the best description of the development of Attention Problems for the observed time. Attention deficits may increase during childhood as academic demands, such as demands on impulse control and response inhibition, increase. Linearity does however not mean that the regression line will go up indefinitely, but that linear models best describe the observed time (6-12 years). With longer follow-up of these children a quadratic model could provide support for declining levels of Attention Problems in adolescence.

The second aim of this study was to investigate if similar trajectories could be identified in singletons. For both boys and girls, singletons followed three trajectories identical to twins, with similar class proportions. The mean intercepts and slopes of the trajectories did not differ between twins and singletons. Therefore, we conclude that twins and singletons are comparable with respect to the development of ADHD symptoms in childhood. The findings from the teacher ratings support this conclusion, as we observed no consistent differences in the mean AP scores between twins and singletons. This conclusion confirms the generalizability of twin studies to singleton populations with regard to ADHD symptoms in middle and late childhood. Our findings are in agreement with a crosssectional twin-singleton comparison, in which twins were compared to their non-twin siblings, that reported no consistent differences with respect to the prevalence of ADHD [START_REF] Ehringer | Genetic and environmental contributions to common psychopathologies of childhood and adolescence: A study of twins and their siblings[END_REF]. This is the first study that investigates trajectories of Attention Problems in middle childhood in the general population. Strengths of the study are the use of prospective data over a 6-year-period, the representativeness of the samples, large sample sizes, and the use of advanced person-centered statistical analyses. Nevertheless, several limitations of this study must be considered. Firstly, there was a modest association of non-response with SES, which may have led to underestimating the proportion of children in the high-decreasing and the low-increasing trajectories, especially in the twin sample. Also, the twin and singleton samples differed with respect to SES, with a higher proportion of twins from higher SES backgrounds. The singleton sample consists of families who were randomly selected from municipal registers, after which participation was strongly pursued, e.g., by means of home-visits, making participants (especially those from low SES) more likely to participate. In contrast, the twin sample depends on voluntary participation and families are encouraged to remain on the register, even when they do not take part in each survey for which they are approached. Secondly, the twin and singleton samples were comprised of different cohorts. For twins, birth cohort did not predict mean AP scores at ages 7, 10 and 12 [START_REF] Derks | Assessment and genetic aetiology of attention problems, hyperactivity, and related disorders[END_REF]. For singletons, an earlier study did not find evidence for secular changes in parent-rated AP over a 10-year period (1983)(1984)(1985)(1986)(1987)(1988)(1989)(1990)(1991)(1992)(1993), but small secular changes were reported for teacher-rated AP [START_REF] Verhulst | Ten-year time trends of psychopathology in Dutch children and adolescents: no evidence for strong trends[END_REF]. Similarly, small increases in Dutch children"s parentand teacher-rated AP scores were found over a 20-year period (1983-2003) [START_REF] Tick | Twenty-year trends in emotional and behavioral problems in Dutch children in a changing society[END_REF]. As these differences were very small (Cohen"s d<0.2), it is unlikely that cohort effects confound our findings. Thirdly, the twin and singleton samples were recruited from different regions of the country (data collection is nation-wide for twins, whereas for singletons a specific part of the country is included). However, an earlier study that showed there were no significant differences in CBCL scale scores between children living in Zuid-Holland and children living elsewhere in the Netherlands [START_REF] Tick | Twenty-year trends in emotional and behavioral problems in Dutch children in a changing society[END_REF].

Conclusion

In

( 3 )

 3 = 0.90, p=0.83; girls: χ² (3) = 0.70, p=0.87). The slope means were equal between twins and singletons (boys: χ² (3) = 4.82, p=0.19; girls: χ² (3) = 1.04, p=0.79), and the intercept variances were also equal between twins and singletons (boys: χ² (3) = 0.59, p=0.90; girls: χ² (3) = 1.83, p=0.61).

34 *

 34 Note Due to the longitudinal design, the N"s do not add up to the total number of children; N = number of observations; SE = standard error; * = significant twin-singleton mean difference (p<0.001).

Figure 1 Figure 2

 12 Figure 1 Trajectories of mother-rated Attention Problems for boys

Table 2 >Table 2

 22

and Figures

1 and 2

show the results for twins and singletons combined, i.e., linear three-class models, with class-specific intercept variances (BIC boys = 63945.99; BIC girls = 60683.

[START_REF] Larsson | Genetic contributions to the development of ADHD subtypes from childhood to adolescence[END_REF]

). The three classes differed with respect to the intercept and slope means. The results were very similar for boys and girls. The three classes were: (1) stable low (boys: 71% twins, 64% singletons; girls: 64% twins, 62% singletons); (2) low-increasing (boys: 15% twins, 15% singletons; girls: 16% twins, 18% singletons), with children whose AP scores were initially low but increased with age; and (3) high-decreasing (boys: 14% twins, 21% singletons; girls: 20% twins, 20% singletons), with children whose AP scores were initially high and decreased with age.

Table 1

 1 conclusion, the development of Attention Problems in boys and girls from age 6 to 12 years can be characterized by stable low, low-increasing, and high-decreasing developmental trajectories.Our findings confirm that twins are not a more vulnerable group than singletons with respect to the development of Attention Problems in childhood, and that results from twin studies regarding ADHD symptoms can be generalized to singleton populations. As our results and interpretations apply only to children in the age range of 6 to 12 years, future research should extend our findings by describing trajectories of Attention Problems from childhood to adulthood. Growth mixture modeling model fit statistics for twins Note BIC = Bayesian Information Criterion; LMR-LRT represents the p-value of the Lo-Mendell-Rubin likelihood ratio test[START_REF] Lo | Testing the number of components in a normal mixture[END_REF], which was included for comparison; n.a. = not applicable. Intercept factor variances are equal across classes, slope factor variances are fixed to zero;

			Linear	Quadratic
		Classes	BIC	LMR-LRT	BIC	LMR-LRT
	Boys	1	55243.60	n.a.	55235.58	n.a.
		2	54091.14	<0.001	54069.46	<0.001
		3	53449.35	<0.001	53409.63	<0.001
		4	53261.68	0.06	53210.41	0.18
	Girls	1	52874.79	n.a.	52880.37	n.a.
		2	51421.16	<0.001	51425.08	<0.001
		3	50875.96	0.02	50895.03	0.22
		4	50345.62	0.10	50323.00	0.11

Table 2

 2 Model results for the three-class linear model for twins and singletons Note BIC boys = 63945.99; BIC girls = 60683.19; I = intercept; S = linear slope; Est = estimated mean; SE = standard error; p-value = significance of intercept and slope means; Intercept variances are freely estimated, slope variances are fixed to zero.

		Twins			Singletons
	Est	SE	p-value	Est	SE	p-value

Table 3

 3 Estimated means for teacher-rated Attention Problems corrected for SES

			Twins			Singletons
		Age	N	Mean	SE	N	Mean	SE
	Boys	6	49	7.43	1.30	58	6.06	1.06
		7	1673	6.34	0.21	57	7.79	0.89
		8	177	7.53	0.59	100	5.72	0.74
		9	552	7.05	0.37	114	8.09	0.69
		10	1053	7.17	0.28	154	7.14	0.56
		11	367	6.62	0.44	168	7.22	0.59
		12	748	6.09	0.32	194	6.91	0.51
	Girls	6	46	3.71	0.77	67	2.60	0.61
		7	1699	3.84	0.16	71	3.35	0.61
		8	177	4.42	0.55	92	4.17	0.67
		9	641	4.00	0.27	133	3.63	0.48
		10	1045	4.02	0.22	159	4.17	0.42
		11	404	3.76	0.34	200	4.68	0.41
		12	778	3.23	0.21	199	4.55	0.

Acknowledgements

Data collection was funded by the following grants: "Genetics of externalizing disorders in children" (NWO 904-57-94), "Spinozapremie" (NWO/SPI 56-464-14192), "Twin-family database for behavior genetics and genomics studies" (NWO 480-04-004), "Twin research focusing on behavior and depression" (NWO 400-05-717), "Developmental Study of Attention Problems in Young Twins" (NIMH, RO1 MH58799-03), and "Bridge Award" (NIMH R56). Sylvana Robbers was supported by the Sophia Children"s Hospital Foundation, project number 483.

Declaration of interest

Dr. Verhulst is director at the Department of Child and Adolescent Psychiatry, Erasmus University Medical Center-Sophia Children's Hospital, which publishes the Dutch translations of the Achenbach System of Empirically Based Assessment and from which he receives remuneration.


Victor Codocedo

Ioanna Lykourentzou

Amedeo Napoli

Semantic Indexing and Retrieval based on Formal Concept Analysis

Semantic indexing and retrieval has become an important research area, as the available amount of information on the Web is growing more and more. In this paper, we introduce an original approach to semantic indexing and retrieval based on Formal Concept Analysis. The concept lattice is used as a semantic index and we propose an original algorithm for traversing the lattice and answering user queries. This framework has been used and evaluated on song datasets.

1 Knowledge discovery in databases (KDD)

Introduction

Knowledge discovery in databases can be likened to the process of searching for gold in the rivers: the gold nuggets that are researched are knowledge units, and the rivers are the databases under study. Huge volumes of data -and particularly documentsare available, without any intended usage. A fundamental question is to know if there may be something interesting in these data, and to find methods for extracting these "interesting things". The knowledge discovery in databases process -hereafter KDDconsists in processing a huge volume of data in order to extract knowledge units that are non trivial, potentially useful, significant, and reusable. From a global point of view, the KDD process may also be understood as a process turning data into information and then knowledge (see figure 1), considering the following equations [START_REF] Schreiber | Knowledge Engineering and Management: the Com-monKADS Methodoloy[END_REF][START_REF] Wille | Why can concept lattices support knowledge discovery in databases[END_REF]:

• Data = signs + syntax.

• Information = data + meaning.

• Knowledge = information (syntax and semantics) + ability to use information.

In addition, the knowledge units extracted by the KDD system must be represented in an adequate representation formalism and then they may be integrated within the ontology to be reused for problem-solving needs in application domains such as agronomy, biology, chemistry, medicine. . .

Symbolic Methods in KDD

Knowledge discovery in databases (KDD) consists in processing a large volume of data in order to extract useful and reusable knowledge units from these data. An expert of 1 Figure 1: The KDD loop: from rough data to knowledge units. The overall objective process of the KDD process is to select, prepare and extract knowledge units from different sources, and then to represent the extracted knowledge units in adequate knowledge structures. the data domain, the analyst, is in charge of guiding the extraction process, on the base of his/her objectives and domain knowledge. The extraction process is based on data mining methods returning information units from the data. The analyst selects and interprets a subset of the units for building "models" that may be further interpreted as knowledge units with a certain plausibility. The KDD process is performed with a KDD system based on components such as domain ontologies, data mining modules (either symbolic or numerical), and interfaces for interactions with the system, e.g. editing and visualization.

The KDD process can be considered along three main steps: data preparation, data mining, and interpretation of the extracted units. At each step, domain knowledge, possibly represented within ontologies, can play a substantial role for improving the KDD process [START_REF] Lieber | First Elements on Knowledge Discovery guided by Domain Knowledge (KDDK)[END_REF]. Moreover, data mining methods can be either numeric or symbolic. In this talk, we will mainly focus on the second type and especially itemset search, association rule extraction, and Formal Concept Analysis (and extensions) [START_REF] Napoli | A smooth introduction to symbolic methods for knowledge discovery[END_REF].

The search for frequent itemsets consists in extracting from binary tables itemsets occurring with a support that must be greater than a given threshold [START_REF] Pasquier | Discovering frequent closed itemsets for association rules[END_REF][START_REF] Bastide | Mining frequent patterns with counting inference[END_REF][START_REF] Szathmary | Efficient Vertical Mining of Frequent Closures and Generators[END_REF][START_REF] Zaki | Efficient algorithms for mining closed itemsets and their lattice structure[END_REF]. Given a set of objects and a set of properties, an item corresponds to an attribute or a property of an object, and an itemset (a pattern) to a set of items. The support of an itemset corresponds to the proportion of objects owning the itemset, with respect to the whole population of objects. An itemset is frequent if its support is greater than a given frequency threshold σ S : a proportion at least equal to σ S of objects own all items included in the itemset. The search for frequent itemsets is based on monotony constraints (base of the Apriori algorithm [START_REF] Agrawal | Fast Discovery of Association Rules[END_REF]). The search of frequent itemsets begins with the search of frequent itemsets of minimal length (or length 1). Then, the frequent itemsets are recorded and combined together to form the candidate itemsets of greater length. The non-frequent itemsets are discarded and all their super-itemsets. The can-didate itemsets are tested and the process continues in the same way, until no more candidates can be formed.

From frequent itemsets it is possible to generate association rules of the form A -→ B relating an itemset A with an itemset B, that can be interpreted as follows: the objects owning A also own B with a support and a confidence [START_REF] Agrawal | Fast Discovery of Association Rules[END_REF][START_REF] Pasquier | Pruning closed itemset lattices for association rules[END_REF]. More precisely, an association rule A -→ B has a support defined as the support of the itemset A ∪ B and a confidence defined as the quotient support(A ∪ B)/support(A) (that can be interpreted as a conditional probability). Then, a rule is valid if its confidence is greater than a confidence threshold σ C , and its support is greater than the frequency threshold for itemsets σ S (a valid rule can only be extracted from a frequent itemset).

The numbers of extracted itemsets and rules may be very large, and thus there is a need for pruning the sets of extracted itemsets and rules for ensuring a subsequent interpretation of the extracted units. This is especially true when the interpretation has to be done -and this is usually the case-by the analyst who is in charge of interpreting the results of the KDD process [START_REF] Brachman | The Process of Knowledge Discovery in Databases[END_REF].

Actually, the search for itemsets and association rules are related to concept lattices: they correspond to a breadth-first search in the concept lattice associated with the formal context under study.

Formal Concept Analysis and variations

The basic framework of FCA

The framework of FCA is fully detailed in [START_REF] Ganter | Formal Concept Analysis[END_REF]. FCA starts with a formal context (G, M, I) where G denotes a set of objects, M a set of attributes, or items, and I ⊆ G × M a binary relation between G and M . The statement (g, m) ∈ I is interpreted as "the object g has attribute m". Two operators (•) ′ define a Galois connection between the powersets (2 G , ⊆) and (2 M , ⊆), with A ⊆ G and B ⊆ M :

A ′ = {m ∈ M | ∀g ∈ A : gIm} and B ′ = {g ∈ G | ∀m ∈ B : gIm}.
For A ⊆ G, B ⊆ M , a pair (A, B), such that A ′ = B and B ′ = A, is called a formal concept. In (A, B), the set A is called the extent and the set B the intent of the concept (A, B). Concepts are partially ordered by

(A 1 , B 1 ) ≤ (A 2 , B 2 ) ⇔ A 1 ⊆ A 2 (⇔ B 2 ⊆ B 1 )
. With respect to this partial order, the set of all formal concepts forms a complete lattice called the concept lattice of (G, M, I). As already mentioned above, natural links exist between between concept lattices, itemsets, and association rules [START_REF] Bastide | Mining frequent patterns with counting inference[END_REF][START_REF] Zaki | Efficient algorithms for mining closed itemsets and their lattice structure[END_REF][START_REF] Szathmary | Constructing iceberg lattices from frequent closures using generators[END_REF].

When one consider non binary contexts, e.g. numerical or interval data, conceptual scaling is often used for binarizing data and for obtaining a binary formal context [START_REF] Ganter | Formal Concept Analysis[END_REF]. Then, a numerical dataset is described by a many-valued context. (G, M, W, I) is a many-valued context where G is a set of objects, M a set of numerical attributes, W a set of values (e.g. numbers), and I a ternary relation defined on the Cartesian product G × M × W . The fact (g, m, w) ∈ I or simply m(g) = w means that the object g takes the value w for the attribute m.

Then, classical algorithms can be applied for designing concept lattices from scaled contexts [START_REF] Kuznetsov | Comparing performance of algorithms for generating concept lattices[END_REF]. However, adapted algorithms for designing a concept lattice may be directly applied on more complex data such as numbers, intervals, or graphs [START_REF] Kuznetsov | Learning closed sets of labeled graphs for chemical applications[END_REF][START_REF] Kuznetsov | Pattern structures for analyzing complex data[END_REF][START_REF] Kaytoue-Uberall | Two FCA-Based Methods for Mining Gene Expression Data[END_REF][START_REF] Kaytoue | Two Complementary Classication Methods for Designing a Concept Lattice from Interval Data[END_REF].

Pattern Structures

Instead of applying discretization leading to space and time computational hardness, one may directly work on original data. A pattern structure is defined as a generalization of a formal context describing complex data [START_REF] Ganter | Pattern structures and their projections[END_REF][START_REF] Kuznetsov | Pattern structures for analyzing complex data[END_REF].

In classical FCA, object descriptions are sets of attributes, which are partially ordered by set inclusion, w.r.t. set intersection: let P, Q ⊆ M two attributes sets, then P ⊆ Q ⇔ P ∩ Q = P , and (M, ⊆), also written (M, ∩), is a partially ordered set of object descriptions. Set intersection ∩ behaves as a meet operator and is idempotent, commutative, and associative. A Galois connection can then be defined between the powerset of objects (2 G , ⊆) and a meet-semi-lattice of descriptions denoted by (D, ⊓) (standing for (M, ∩)). This idea is used to define pattern structures in the framework of FCA as follows.

Formally, let G be a set of objects, let (D, ⊓) be a meet-semi-lattice of potential object descriptions and let δ : G -→ D be a mapping associating each object with its description. Then

A = ⊓ g∈A δ(g), f or A ⊆ G and d = {g ∈ G|d ⊑ δ(g)}, f or d ∈ (D, ⊓).
These operators form a Galois connection between (2 G , ⊆) and (D, ⊓). Pattern concepts of (G, (D, ⊓), δ) are pairs of the form (A, d), A ⊆ G, d ∈ (D, ⊓), such that A = d and A = d . For a pattern concept (A, d), d is a pattern intent and is the common description of all objects in A, the pattern extent. When partially ordered by

(A 1 , d 1 ) ≤ (A 2 , d 2 ) ⇔ A 1 ⊆ A 2 (⇔ d 2 ⊑ d 1 )
, the set of all concepts forms a complete lattice called pattern concept lattice. More importantly, the operator (.) is a closure operator and pattern intents are closed patterns. Existing FCA algorithms (detailed in [START_REF] Kuznetsov | Comparing performance of algorithms for generating concept lattices[END_REF]) can be used with slight modifications to compute pattern structures, in order to extract and classify concepts. Details can be found in [START_REF] Ganter | Pattern structures and their projections[END_REF][START_REF] Kaytoue-Uberall | Two FCA-Based Methods for Mining Gene Expression Data[END_REF][START_REF] Kuznetsov | Pattern structures for analyzing complex data[END_REF].

Below, we analyze object descriptions as interval in numerical data. Pattern structures allows to directly extract concepts from data whose object descriptions are partially ordered. Considering a numerical dataset with objects in G and attributes in M , a meet operator ⊓ on interval patterns can be defined as follows. Given two interval patterns c = [a i , b i ] i∈{1,...,|M|} , and d = [e i , f i ] i∈{1,...,|M|} , then: c ⊓ d = [minimum(a i , e i ), maximum(b i , f i )] i∈{1,...,|M|} meaning that a convexification of intervals on each vector dimension is operated. The meet operator induces the following subsumption relation ⊑ on interval patterns:

[a i , b i ] ⊑ [c i , d i ] ⇔ [a i , b i ] ⊇ [c i , d i ],
∀i ∈ {1, ..., |M |} where larger intervals are subsumed by smaller intervals.

A numerical dataset with objects G and attributes M can be represented by an interval pattern structure. Let G be a set of objects, (D, ⊓) a meet-semi-lattice of interval patterns (|M |-dimensional interval vectors), and δ a mapping associating to any object g ∈ G an interval pattern δ(g) ∈ (D, ⊓). The triple (G, (D, ⊓), δ) is an interval pattern structure (see examples and details in [START_REF] Kuznetsov | Pattern structures for analyzing complex data[END_REF][START_REF] Kaytoue | Two Complementary Classication Methods for Designing a Concept Lattice from Interval Data[END_REF]).

Pattern structures are very useful for building concept lattices where the extents of concepts are composed of "similar objects" with respect to a similarity measure associated to the subsumption relation ⊑ in (D, ⊓) [START_REF] Kaytoue | Two Complementary Classication Methods for Designing a Concept Lattice from Interval Data[END_REF].

Relational Concept Analysis

Relational datasets are composed of a binary tables (objects × attributes) and inter-object relations (objects × objects). Formally, these binary tables introduce a set of objects G i described by a set of attributes M i , and, as well, a set of relations r k ⊆ G i × G j . Relational datasets arise in a wide range of situations, e.g. Semantic Web applications [START_REF]Handbook on Ontologies[END_REF], relational learning and data mining [START_REF] Dzeroski | Relational Data Mining[END_REF], refactoring of UML class models and model-driven development [START_REF] Stahl | Model-Driven Software Development: Technology[END_REF].

Relational Concept Analysis (RCA) extends FCA to the processing of relational datasets in a way allowing inter-objects links to be materialized and incorporated into formal concept intents. Links are thus scaled to become relational attributes connecting first objects to concepts and then concepts to concepts as role restrictions do in Description Logics (DL) [START_REF] Baader | editors. The Description Logic Handbook[END_REF]. The new attributes are complex properties reflecting the relational aspects of a formal concept. They nevertheless abide to the same classical concept formation mechanisms from FCA which means that the relational concept intents can be produced by standard FCA methods. Due to the strong analogy between role restrictions and relational attributes in RCA, formal concepts can be readily translated into a DL-based formalism [START_REF] Rouane-Hacene | A proposal for combining formal concept analysis and description logics for mining relational data[END_REF], e.g. for ontology engineering purposes as in [START_REF] Bendaoud | Pactole: A methodology and a system for semi-automatically enriching an ontology from a collection of texts[END_REF][START_REF] Bendaoud | Formal concept analysis: A unified framework for building and refining ontologies[END_REF][START_REF] Rouane-Hacene | Ontology Learning from Text using Relational Concept Analysis[END_REF].

RCA was introduced and detailed in [START_REF] Rouane-Hacene | A proposal for combining formal concept analysis and description logics for mining relational data[END_REF]. The data structure is described by a relational context family, composed of a set of contexts {K i } and a set of binary relations

{r k }. A relation r k ⊆ G j × G ℓ connects two object sets, a domain G j (dom(r k ) = G j ) and a range G ℓ (ran(r k ) = G ℓ ).
RCA is based on a "relational scaling" mechanism that transforms a relation r k into a set of relational attributes that are added to the context describing the object set dom(r k ). To that end, relational scaling adapts the DL semantics of role restrictions.

For each relation Actually, RCA is a powerful mechanism for managing relations in the framework of FCA. In CBR, it could be used for example for associating elements of problem statements with elements of problem solutions, an association that was not possible in [START_REF] Diaz-Agudo | Formal Concept Analysis as a support technique for CBR[END_REF].

r k ⊆ O j × O ℓ ,

Elements for Discussion

Usually, considering knowledge systems, and CBR systems as well, knowledge units may have two major different origins: explicit knowledge (and cases) can be given by domain experts and implicit knowledge can be extracted from databases of different kinds, e.g. domain data or textual documents. Moreover, a KDD system, as any other knowledge system, improves its performance when it is guided by domain knowledge [START_REF] Lieber | First Elements on Knowledge Discovery guided by Domain Knowledge (KDDK)[END_REF]. Hereafter, some requirements for KDD systems, adapted from [START_REF] Brachman | The Process of Knowledge Discovery in Databases[END_REF][START_REF] Wille | Why can concept lattices support knowledge discovery in databases[END_REF], are listed for discussion:

• A KDD system is a knowledge system: it should present to the user the underlying domain in an appropriate fashion and rely on domain knowledge (e.g. an ontology).

• Extending the system knowledge: domain representation should be extensible by addition of new concepts or classes resulting from mining or querying processes. Concepts and their instances must be reusable in queries. The question of extracting cases from data, which have to be made precise, remains open [START_REF] D'aquin | Case base mining for adaptation knowledge acquisition[END_REF].

• Alternative classification and mining tools: it should be possible to define alternative classifications of data, e.g. alternative concept lattices. A set of different classification and mining tools should be available, possibly combining numerical and symbolic methods.

• Support to analysts: analysts should be supported by adequate visualization tools and in the interpretation of extracted units as well, in particular by domain knowledge.

• Monitoring and documenting the system evolution: tools managing versions can be used for monitoring changes in classes or concepts over time. The system should document the different steps of the knowledge discovery process.

• KDD is a flexible process and its results should reflect the plural nature of knowledge, i.e. extracting procedural or declarative knowledge units, and, as well, meta-knowledge units.

• KDD provides knowledge units for extending ontologies, and, reciprocally, knowledge systems and CBR systems can be used to guide and improve KDD.

Finally, the relations between knowledge representation, reasoning, and knowledge discovery with FCA, are explained as follows in [START_REF] Wille | Why can concept lattices support knowledge discovery in databases[END_REF]. Formal concepts and concept lattices provide a mathematization of real-world concept hierarchies. This yields a mathematical support to human reasoning, especially using the graphical representation of concept lattices. Then, conceptual knowledge discovery, considered as pattern discovery plus knowledge creation, can be guided by the design of concept lattices and a subsequent representation of the formal concepts within a knowledge representation formalism such as description logics. The process can be repeated until a satisfactory knowledge base is obtained.

Semantic indexing

Semantic indexing and retrieval is a growing research area [START_REF] Ren | Advanced information retrieval[END_REF]. Semantic indexing refers to organizing a set of available information items inside an index according to the semantic relations and concepts that they share, while semantic retrieval refers to searching within this index to identify the items, the context of which matches a given user query [START_REF] Kiryakov | Semantic annotation, indexing, and retrieval[END_REF]. In a certain sense, semantic retrieval is based on flexible and partial matching techniques contrasting exact matching techniques, traditionally used in standard information retrieval.

The organization and retrieval of information based on its context can, if effectively carried out, significantly improve the automated understanding of the meaning of the information, as well as to provide users with richer and more meaningful search results. For these reasons, context-based methods of classification and retrieval are applied on multiple domains and types of information, ranging from text-based documents to multimedia content, such as image or video.

One of these domains, interesting for its originality and for the potential added value that it can create, is the domain of song indexing and retrieval. In particular, current song indexing and retrieval systems organize songs based on low or mid-level descriptors [START_REF] Typke | A survey of music information retrieval systems[END_REF]. Examples of low-level descriptors include a song's bit-rate, length or pitch and examples of mid-level descriptors include a song's title, artist, genre, year and so on. Using these elements, songs are categorized and retrieved, either based on the user's past known preferences (content-based recommendation) [START_REF] Lops | Content-based recommender systems: State of the art and trends[END_REF], or on the user's interactions with other users (collaborative filtering) [START_REF] Su | A survey of collaborative filtering techniques[END_REF].

However, songs contain more and richer information than the one described through the aforementioned descriptor elements. Indeed, songs, and especially song lyrics, include information referring to a specific context, event or place. In addition, songs, being art pieces, may be linked to a broader context, such as a historical event, a certain period of time or a cultural idiosyncrasy. Based on this knowledge, a user may be interested in generating compilations of songs based on high-level descriptions, for instance "Songs about the Vietnam War", "Protest Songs", "Songs about peace" etc. As an indication of the growing interest that content-based song indexing receives by users, Wikipedia has so far indexed over 4000 songs under the category "Songs by Theme", which in turn includes a hierarchy of over 250 sub-topics created by Wikipedia contributors 1 .

Despite user interest, only a few research works focus on subjects related to contextbased song indexing and retrieval. Among the most representative, the work in [START_REF] Turnbull | Semantic annotation and retrieval of music and sound effects[END_REF] tries to extract meaningful annotations about songs, using text-mining of expert reviews, targeted user-feedback or social game-based models. The work in [START_REF] Logan | Semantic analysis of song lyrics[END_REF] performs automated lyrics analysis, using probabilistic latent semantic analysis, to determine artist similarity based on the songs' semantics. To the best of the authors' knowledge, no work so far explores the problem of semantic context-based song indexing and retrieval. An opportunity therefore emerges to use the context-related information of song datasets, revealed through lyrics or through external knowledge resources (such as Wikipedia or Wordnet), in order to provide users with more meaningful search results that will complement the results brought by current song retrieval systems.

Therefore, shifted to the domain of songs, the problem of semantic information indexing and retrieval can be considered as follows:

1. Create a semantic index for organizing songs according to their content (their lyrics).

2. Develop automated ways for searching within this index to retrieve songs semantically linked to a user query.

An example of an indicative question for this problem would be: "Given a set of high-level descriptors provided by the user, find the set of songs whose lyrics are semantically related to these descriptors".

To address this problem, we propose a semantic indexing and retrieval of songs based on Formal Concept Analysis (FCA [START_REF] Ganter | Formal Concept Analysis[END_REF]). In particular, FCA is used to construct a concept lattice, which classifies songs w.r.t. high-level descriptors that they share, i.e the semantic annotations of their lyrics. This concept lattice is then used as a semantic index for songs. In addition, a heuristic search algorithm is proposed, which traverses the lattice in a novel way, in order to match queries based on high-level descriptors to contextualized sets of songs.

Regarding standard approaches of semantic indexing and search, the main contributions of this work lie in the following:

• The use of FCA and a concept lattice as a semantic index.

• The development of a novel algorithm that traverses a concept lattice to retrieve information based on the content of concepts.

• The incorporation of semantic indexing to current song retrieval needs.

An additional characteristic is addressing the problem of semantic indexing and retrieval as a 3-step knowledge discovery process, comprising the following main steps: data preparation, discovery and filtering of the results.

The rest of this document is organized according to the main steps of the process. Firstly, Section 3 proposes the state of the art for positioning the present work. Section 4 presents the data sources and the preparation of the dataset. Section 5 introduces FCA and analyzes its use for semantic indexing and querying. Next, Section 6 presents the evaluation results obtained for our approach. Finally, Section 7 discusses possible extensions of our work and research.

Related Work

Song information retrieval is a relatively young field, which started to draw attention in the late 1990s, both in terms of commercial systems and academic research [START_REF] Byrd | Problems of music information retrieval in the real world[END_REF].

On the commercial side, many well-known song retrieval systems may be found, including Internet applications (Last.fm2 , Grooveshark3 , Songsterr4 ), desktop applications (iTunes, Zune, Amarok, Songbird, Winamp) or even embedded applications in mobile devices (ipod, android, zone).

Academic approaches have also elaborated on different aspects of the song indexing and retrieval domain. First, a significant number of works focus on song annotation, i.e. describing the song in terms of symbolic, audio or textual metadata (indicatively [START_REF] Fu | A survey of audio-based music classification and annotation[END_REF][START_REF] Kuuskankare | Mir in enp -rule-based music information retrieval from symbolic music notation[END_REF]). Symbolic and audio annotation belong to the so-called low-level descriptors and characterize the song in terms of musical notes and sound features such as bit-rate, length, pitch or melody. Text-based annotations belong to the category of mid-level descriptors and use annotation elements such as artist, genre and title. The annotation task is performed through hand-labeled expert feedback, automated text-mining of music reviews or, more recently, through social song annotation games [START_REF] Turnbull | Semantic annotation and retrieval of music and sound effects[END_REF].

Song annotations are then used by music search engines for a number of retrieval tasks. Low-level descriptors are used for example to enable fingerprinting, i.e. searching within song datasets to retrieve exact or similar matches to a particular recording [START_REF] Wang | The shazam music recognition service[END_REF] or to facilitate the resolution of copyright or plagiarism issues [START_REF] Typke | A survey of music information retrieval systems[END_REF]. Mid-level descriptors are used mainly by recommender systems to suggest new songs to users, either by directly matching the user query to the stored annotations (content-based recommendation [START_REF] Turnbull | Semantic annotation and retrieval of music and sound effects[END_REF]), or by combining the latter with additional feedback of a user community (collaborative filtering) [START_REF] Balby | Collaborative tag recommendations[END_REF].

However, the focus on low or mid-level descriptors to retrieve song is not always adequate. Indeed, as a recent survey on user needs in the song domain reveals that the majority of users expressed a strong interest in contextual song metadata, as these are reflected through lyrics or additional background knowledge [START_REF] Ha | Survey of music information needs, uses, and seeking behaviours: Preliminary findings[END_REF]. The works focusing on context-based information are a few and mainly focus on modeling the semantics of lyrics to discover patterns of emotions [START_REF] Michael | Computer music modeling and retrieval. genesis of meaning in sound and music. chapter Semantic Contours in Tracks Based on Emotional Tags[END_REF][START_REF] Sharma | Mining sentiments from songs using latent dirichlet allocation[END_REF] or clusters of mid-level descriptors, such as artist similarity [START_REF] Logan | Semantic analysis of song lyrics[END_REF] or genre [START_REF] Laurier | Multimodal music mood classification using audio and lyrics[END_REF][START_REF] Hu | Lyric Text Mining in Music Mood Classification[END_REF] Finally, regarding the present work, the method of FCA is used in informationretrieval related tasks. Specifically, the work of [START_REF] Priss | Lattice-based information retrieval[END_REF] uses FCA to improve the representation of a document collection by merging it with information from a thesaurus and thus creating a multi-faceted extended context. The work of [START_REF] Carpineto | Exploiting the potential of concept lattices for information retrieval with credo[END_REF] uses a similar approach to improve the representation of web results. Specifically, in this work FCA is used to create a faceted web browsing system that enables users to query search engines, such as Google, and then organize the results in a concept lattice. However the above works do not use the concept lattice as a semantic index but to create the facets that will facilitate users in browsing the retrieved results.

We introduce FCA to create a semantic index of a given song dataset and a novel method to query this index, thus contributing to both the area of context-based information retrieval on the music domain, as well as to the broader area of FCA-based information indexing and retrieval.

Data sources and dataset preparation

The song dataset used in our experiments is based on two main sources of data, namely musiXmatch and WordNet , briefly introduced hereafter.

musiXmatch

The musiXmatch dataset 5 is a database that contains the lyrics of approximately 700K songs, in the form of bags-of-words. The musiXmatch dataset was recently released (April 2011) as the official lyrics collection of the Million Song Dataset [START_REF] Thierry Bertin-Mahieux | The million song dataset[END_REF]. The musiXmatch dataset is used as the source to provide the lyrics for each song in our dataset, and this choice is made on the basis that the lyrics it provides are: i) already in the format of bag-of-words and ii) already preprocessed using stemming, in order to eliminate morphologically-related word duplications.

WordNet

WordNet6 is a semantic dictionary widely used in the domain of computational linguistics and natural language processing [START_REF] Manning | Foundations of Statistical Natural Language Processing[END_REF]. WordNet can be used to relate a word to a set of synonym terms, called synsets, each of which corresponds to one meaning of the specific word. For example the word "concert" corresponds to three synsets inside WordNet: i) "a performance of music by players or singers not involving theatrical staging", ii)"contrive (a plan) by mutual agreement" and iii)"settle by agreement".

Synsets inside WordNet are also mutually related through semantic or lexical hierarchies. The most interesting, for our problem, is the semantic hierarchy, which connects synsets in hypernym-hyponym relationships, with hypernyms representing broader and hyponyms narrower semantic terms. The hypernym-hyponym hierarchy of WordNet can therefore be used to retrieve the semantic distance of a pair of given WordNet is used, through its API, as a resource to provide: i) the synsets of every word inside each song's lyrics and ii) the semantic distances among the synsets of each song.

A more detailed description of the use Wordnet's API is provided in section 5.1.

For carrying out our experiments, using musiXmatch and Wordnet, we constructed a dataset of 357 songs in total, where each song is represented by its title and lyrics, in the form of bag-of-words, and each word is connected to a set of synsets.

Semantic indexing based on FCA

Current song retrieval systems work by exact matching strings of the user query to song attributes, such as title, genre or artist [START_REF] Typke | A survey of music information retrieval systems[END_REF]. However, if the user is interested in searching for songs related to an idea or a concept, the above approach may not be sufficient, since it cannot find a direct connection between the content of a song (what a song is about) and its attributes. For instance, in case the user is interested in songs about War, current song retrieval systems would retrieve only songs that contain this word in their title, a fact which would, in turn, lead to incomplete or even inexact results. Trying to match the keyword War directly to the lyrics would also not be adequate, since this word can be used in several contexts (consider for instance the love song by Blue Nile, titled "War is Love"). Nevertheless, the lyrics of a song are still a valuable source of information regarding its content, able to complement current attributes.

The problem is then defined as finding songs the lyrics of which are related to a set of user-provided keywords, through a sufficient "closeness of meaning". Our goal is to construct a semantic index, from a given set of songs and their lyrics and a closeness relation, which will support successfully context-based song retrieval.

In the following, a song s i is defined as a pair {t i , L i } where t i denotes the title and L i the lyrics of the song in the form of a bag-of-words, as provided by musiXmatch.

Task 1: Lyrics Annotation

Given a song s i = {t i , L i }, the first task is obtaining from WordNet the set of synsets that corresponds to its lyrics L i . For this purpose we query the API of WordNet7 using each word w ∈ L i (which may comprise multiple words). Each retrieved synset has a definition and a set of synonyms. Word w is part of the synonyms. As an example, Table 1 illustrates the synsets retrieved from WordNet for the word "Soldier".

From the above example it can be understood that not every synset retrieved through WordNet is valuable in the context of a song. For instance, in the context of a war, a reference to a "soldier" would be clearly related to the definition of an enlisted man who serves in an army and not to the definition of a soldier ant. The third definition can also be disregarded since it is associated with a verb.

Therefore, to annotate each song, we firstly need to obtain the WordNet synsets that correspond to its lyrics and secondly to filter the retrieved synsets, in order to keep only those that correspond to the actual context of the song. Thus, each song was associated with a set of WordNet synsets in the following way: For a particular song s i and its lyrics L i , we first used the WordNet API to retrieve the list ss(L i ) of synsets that are associated with each word in L i .

Then, a filtering process took place as follows: a widespread similarity metric, namely the Wu-Palmer Similarity Measure [START_REF] Wu | Verbs semantics and lexical selection[END_REF] was used to measure the semantic similarity between every pair of synsets in the ss(L i ) set. The Wu-Palmer similarity measure wp(ss 1 , ss 2 ) = [0, 1], ss 1 ∈ ss(L i ) ∧ ss 2 ∈ ss(L i ) is provided by the WordNet API and measures semantic similarity using path distance and the difference of levels in the synset tree. Then for each synset ss j we calculate the average distance with every other synset ss k ∈ ss(L i ) as defined in equation 1.

avg sim(ss j ) = j =k wp(ss j , ss k ) |ss(L i )| (1)
The synset with the lowest avg sim is deleted from ss(L i ). The filtering is repeated until we reach to a threshold of 20 most similar elements in ss(L i ), which will be considered to constitute the so-called semantic core of the song s i , denoted as core(s i ). The threshold of 20 synsets was selected heuristically, since it was found to represent the semantic core of the songs, in the specific dataset, in a concise and non redundant way.

The outcome of the filtering process is the set core(s i ), which is considered as the final set of semantic annotations of the song s i since it refers to a well-defined semantic schema, i.e. WordNet, where each annotation contains a definition and relations with other annotations.

Task 2: Semantic Index Creation

One particular aspect of this work is to build a semantic index as a concept lattice using Formal Concept Analysis (FCA) following the lines of [START_REF] Messai | Querying a bioinformatic data sources registry with concept lattices[END_REF][START_REF] Carpineto | Exploiting the potential of concept lattices for information retrieval with credo[END_REF][START_REF] Priss | Lattice-based information retrieval[END_REF].

We define the formal context K = (G, M, I), where G is the set of objects containing all the considered songs while the set of attributes M includes all WordNet synsets constituting the semantic cores of the songs in G. The set I maintains the relations between songs and synsets where gIm stands for "song g has synset m in its semantic core". Table 2 shows an example of a formal context created from 11 songs and 6 synsets.

The concept lattice obtained from the context presented in Table 2 is illustrated on Figure 2. The concept lattice is presented in its reduced notation where objects (songs) and attributes (synsets) are shown only next to their object/attribute-concept, i.e. the most general concept for attributes which are inherited from higher to lower levels, and the most specific concept for objects which in turn are shared from lower to higher levels.

Task 3: Semantic Index querying

A simple query to the constructed semantic index (i.e. the concept lattice) is a pair q = (A q , B q ) where A q denotes an empty extent to be filled and B q = {ss} is a synset to be searched for. Actually, the retrieval is based on two steps. The first one corresponds to "exact matching" (as in [START_REF] Messai | Querying a bioinformatic data sources registry with concept lattices[END_REF]) and the second corresponds to "partial matching" based on the closeness relation introduced hereafter. The first step is based on the search for the attribute-concept (A ss , B ss ) of attribute ss in the concept lattice, i.e. the most general concept where ss appears in an intent (also denoted by µ(ss) in [START_REF] Ganter | Formal Concept Analysis[END_REF]). The extent of A ss contains the list of all songs which are directly associated with the synset ss. This direct answer constitutes only part of the answer. The second step is related to partial matching based on the closeness relation defined in the "hypothesis of closeness". Hypothesis of closeness. Two concepts (A 1 , B 1 ) and (A 2 , B 2 ) which are not comparable for ≤ K are said to be close iff there exists

(A 3 , B 3 ) such that (A 3 , B 3 ) ≤ K (A 1 , B 1 ) and (A 3 , B 3 ) ≤ K (A 2 , B 2 ). Intuitively, this means that (A 1 , B 1 ) and (A 2 , B 2 )
do not subsume each other and that (A 3 , B 3 ) can be either the lower bound or be subsumed by the lower bound (A 1 , B 1 )⊓(A 2 , B 2 ) (where (A 1 , B 1 )⊓(A 2 , B 2 ) denotes the lower bound of (A 1 , B 1 ) and (A 2 , B 2 ). Actually, (A 3 , B 3 ) represents songs related to both (A 1 , B 1 ) and (A 2 , B 2 ): two songs are related if their semantic cores share some elements, which is the case here, as 2, concept 3 is close to 2 because of concept 8, concept 11 is close to concept 12 because of concept 16 and so on.

A 3 ⊆ A 1 ∩ A 2 and B 3 ⊆ B 1 ∪ B 2 . For example, in figure
For a given attribute concept (A ss , B ss ), the querying algorithm extracts all close concepts (A i , B i ) of the synset ss, and then moves down the concept lattice, repeating the same extraction level by level. It should be noticed that the original synset query ss is not present in any of the intents of the close concepts B i , this is why we can speak of "partial matching". Every close concept (A i , B i ) is ranked according to the intersection that its extent has with the extent of the original attribute concept using the following metric:

rank(A i , A ss ) = |A i ∩ A ss | |A i | (2)
This metric is two-fold since it allows the detection of concepts (A i , B i ) which are far from the original concept and share no common objects with the extent of (A ss , B ss ) (A i ∩ A ss = ∅ and rank = 0) and those that are too abstract and describe too many objects (|A i | ≫ |A ss | and rank ∼ 0).

Hereafter, we give details on the steps of the algorithm through the use of an example, graphically illustrated in Figure 2. Let us consider a user query for songs related to the synset "bolshevik.n.01" (concept 3 on Figure 2).

1. Find the attribute-concept (A ss , B ss ) for the synset {ss}: concept 3.

2. Find the sub-hierarchy of (A ss , B ss ) in the concept lattice, i.e. all concepts subsumed by (A ss , B ss ) and order them by levels: concepts 8, 11, 10, 15, 13, 16, 17 (solid arrows in Figure 2).

3. For each concept in this sub-hierarchy, find the super-concepts which are close concepts of (A ss , B ss ) (and then for the descendants of (A ss , B ss )): concept 2 is close to 3 because of 8, 4 is close to 3 because of 11, 6 is close to 8 because of 10, etc. The final list is ordered by levels: concepts 2, 4, 5, 6, 9, 7, 12, 14 (dashed arrows in Figure 2).

4. Calculate the rank value of each close concept (according to Eq. 2) and sort these close concepts in descending order: concepts 6, 12, 9, 4, 2, 5, 7, 14.

5. The result is composed of the songs in the extent of the attribute-concept (A ss , B ss ) and the extents of the close concepts.

The final result, in terms of the retrieved close concepts, their rankings and the songs in their extents, is shown in Table 3. It is important to note that the basic target of the algorithm proposed above is semantic retrieval. The order in which the algorithm presents the retrieved groups of songs to the user is a "reccomendation decision", which could depend on user preferences and imply the use of a threshold to filter the final list of songs. Semantic retrieval does not necessarily imply the use of a threshold, which is why we present all the songs retrieved.

Validation of the approach

As described in the previous section, the lattice is queried using a synset ss (e.g. bolshevik.n.01). This synset is directly related to a set of songs (direct answer ss ), i.e. those in the extent of the attribute concept (A ss , B ss ) of that synset (in the case of bolshevik.n.01, they are the songs 16, 27 and 39). These songs will be retrieved along with the set of songs found in the extents of the close concepts (indirect answer ss ) of (A ss , B ss ) (songs 1, 10, 14, 18, 24, 32 and 33).

Regarding the songs in direct answer ss , we are interested in examining whether our approach can find them if we apply it on a modified formal context where their relations with the synset ss have been eliminated. Of course, in this case, these songs cannot be retrieved as directly related songs, but only as songs found in the extents of close concepts. For example, if we eliminate the relation between song 16 and the synset bolshevik.n.01 we want to know if this song can be retrieved by querying the new lattice using the synset bolshevik.n.01.

Regarding the set indirect answer ss , we are interested in examining how it changes after the application of our approach on the modified formal context since the elimination of a (song,synset) relation will affect the structure of the concept lattice and hence the output of the proposed retrieval algorithm. Small variations in the content of this set will indicate robustness.

Leave-one-out cross validation

To evaluate the above and subsequently the hypothesis of closeness presented in section 5.3 we used and adapted the leave-one-out cross validation (LOOCV) methodology, which is a special type of cross validation [START_REF] Refaeilzadeh | Cross-validation[END_REF]. Our adaptation consists of intentionally removing a single (song,synset) relation from the original formal context and construct its concept lattice. We call this modified concept lattice a scenario. Therefore, each scenario is identified by a pair synset (ss scn ) and song (s scn ), the relation of which was eliminated for the scenario's construction.

For a given scenario, if song s scn can be retrieved by querying for synset ss scn we mark the scenario as a success (e.g. querying for bolshevik.n.01 and retrieving song 16 for scenario with ss scn = bolshevik.n.01 and s ss = song 16). It is worth noticing that the total number of scenarios for a single synset is determined by the number of songs where the synset appears in (i.e. the songs in the set direct answer(ss)), since we only eliminate at each time only a single (song,synset) relation from the formal context (e.g. for the synset bolshevik.n.01 we construct 3 scenarios for songs 16, 27 and 39).

For a given synset ss we define a success rate(ss) as illustrated in equation 3, where total scenarios(ss) refers to the total number of scenarios constructed using synset ss and the songs in direct answer ss and success scenarios(ss) refers to how many of them were marked as a success.

success rate(ss) = success scenarios(ss) total scenarios(ss)

High values of success rate indicate that a song can be retrieved for a synset query even if the song is not related to the synset itself.

To evaluate the changes in the set indirect answer ss , we compare the full set of retrieved songs from each scenario with the respective set of songs retrieved from the original concept lattice. We calculate precision defined in Eq. 4 as the proportion of true positives over the retrieved list of songs in a scenario. Accordingly, we calculate recall, in Eq. 5, as the proportion of true positives over the retrieved list of songs in the original concept lattice, i.e. the concept lattice without any removal. The expression Ret(scn, ss) denotes the total set of songs retrieved from scenario scn (direct answer ss ∪ indirect answer ss ) querying for synset ss while original denotes the original concept lattice. precision(scn, ss) = Ret(scn, ss) ∩ Ret(original, ss) Ret(scn, ss)

recall(scn, ss) = Ret(scn, ss) ∩ Ret(original, ss) Ret(original, ss)

Results

For each synset we calculate the mean precision and recall from all their scenarios. From our test set of 357 songs and 1848 synsets we selected 192 synsets and simulated 1027 scenarios (working with approximately 1000 scenarios allows a lower volume of computation and more different trials). Table 4 shows the values of this measures for 10 synsets. For example, it can be seen that synset anteroom.n.01 has relations with 4 songs. A success rate of 1 means that all simulations were successful. Recall of 0.9 and Precision of 0.96 mean that for an elimination of 25% of the relations for a synset (1 over 4 songs), still 90% of the information was retrieved and 96% of the information was correct. There is a positive relation between the number of songs in which the synset appears and the success rate measure. This is not strange since synsets appearing in a few songs will be in less concepts in the lattice and hence the simulation affects them in the worst manner. For example, for the synset bar.n.03, the elimination of one relation with a song leads to the elimination of 50% of its relations (1/2), while for the synset battle.n.01 the elimination of one relation with a song leads to the elimination of only 5% of its relations (1/20). Figure 4 shows the distribution of success rate, recall and precision (in the interval of [0, 1] in axis y) over the number of songs where synsets appear in (in axis x). The success rate maintains a growing tendency showing that better results are obtained with synsets which appear in a greater number of songs. In a wider sense, precision and recall maintain their values over 70% over all the samples. This is especially important in values of songs per synset below 5 since losing a single connection could disconnect songs more significantly. In the case of the first point (2.5 songs per synset) losing one connection means losing 40% of the information available, however over 70% of the original set of songs is retrieved.

It should be noted that a certain degree of bias, caused by the inclusion of the directly related songs in the measures of precision/recall, is to be expected. That is, given that for each scenario we are eliminating only one (song, synset) relation, the remaining directly related songs will be present in both sets retrieved when querying the scenario and the original concept lattice. Therefore, the precision/recall measures are meant to be used as a means of examining how the set of close concepts is affected for each synset, and they should not be considered as a medium of comparison with other information retrieval approaches.

Finally, even if more experiments have to be completed, we can conclude that the hypothesis of closeness is valuable and can be used to exploit the use of a concept lattice as a semantic index to retrieve objects not directly related to a query.

Discussion, extension and conclusion

Semantic indexing and retrieval based on FCA as introduced above allow us to retrieve a set of songs w.r.t. the content of their lyrics. However, lyrics do not always depict the full context of a song. As an example, in the dataset, none of the songs that are known to be about the historical event of the Vietnam war actually contains a reference to the synset "vietnam war.n.01". This may happen because of two main reasons. Firstly, a song may not refer directly to its full context, but to the circumstances that surround it (a song may not refer directly to Vietnam, but to the story of a soldier). Secondly, a synset important to describe the full context of a song, such as the "Vietnam" synset, may be ignored during synset filtering, because the specific synset was not found to belong to the semantic core of the song. Despite not being directly present in the lyrics, this information is necessary to complete the full context of a song and is extremely valuable. It can help to gain a deeper understanding of the song data and thus to provide the user with richer retrieval results with regard to the context of songs.

There are many sources that could be used to obtain this additional information about songs. A very interesting one is DBpedia, a large-scale effort to provide semantics to the content of Wikipedia. DBpedia categorizes songs in contextual "topics" (e.g. "songs about the Vietnam War") which can be used as categorical knowledge to enrich our understanding of the meaning of a song. For taking advantage of categorical knowledge, it is possible to extend the proposed FCA-based approach with Relational Concept Analysis [START_REF] Rouane-Hacene | A proposal for combining formal concept analysis and description logics for mining relational data[END_REF], which allows to take into account relations between objects in the framework of FCA. It becomes then possible to create a semantic index as a "relational concept lattice", where songs are related not only through their lyrics but also through their categories. In the RCA framework, it is then possible to search for a set of songs which are indexed under the same or related categories (a category can be more or less general in the hierarchy of categories of DBpedia). At present, first experiments were made with RCA. The retrieval process shows similar performances as with FCA but provides alternative lists of results. These experiments have still to be completed and analyzed.

Concluding, in this document we propose a novel contribution to the field of semantic indexing and retrieval, which is based on Formal Concept Analysis. Specifically, we use the concept lattice as a semantic index and propose a novel algorithm to traverse it in order to match user queries with semantically relevant information items. The approach was tested on a song dataset and the obtained results show good capabilities.

  (G, (D, ⊓), δ) is a pattern structure. Elements of D are patterns and are ordered by a subsumption relation ⊑: ∀c, d ∈ D, c ⊑ d ⇐⇒ c ⊓ d = c. A pattern structure (G, (D, ⊓), δ) gives rise to two derivation operators (•) :

  there is an initial lattice for each object set, i.e. L j for O j and L ℓ for O ℓ . For a relation r k ⊆ O j × O ℓ , a relational attribute, is associated to an object o ∈ O j whenever r k (o) satisfies a given constraint, where r k (o) denotes the set of objects in O ℓ in relation with o through r k . The relational attribute is denoted by ∀r k .C (universal scaling) when r k (o) ⊆ extent(C) with r k (o) possibly empty. The relational attribute is denoted by ∃r k .C (existential scaling) when r k (o) ∩ extent(c) = ∅. Other relational scaling operators exist in RCA and follow the classical role restriction semantics in DL.

Figure 2 :

 2 Figure 2: The semantic index as a concept lattice obtained with FCA. Each concept is labelled with a unique identifier.

Figure 3 :

 3 Figure 3: Querying the FCA lattice. The values of the rank metric for each close concept are presented in a percentage form. In this example, concept 3 is the attribute concept, solid arrows show the subhierarchy and dashed arrows show the close concepts of concept 3.

Figure 4 :

 4 Figure 4: Distribution of measures over songs per synset.

Table 1 :

 1 Synsets retrieved for the word "soldier"from Wordnet

	Synset	Synonyms Definition
	soldier.n.01 soldier	an enlisted man who serves in an army
	soldier.n.02 soldier	a wingless sterile ant or termite having...
	soldier.v.01 soldier	serve as a soldier in the military
	synsets, i.e. how "far" or "close" these synsets are in terms of semantic meaning.

Table 2 :

 2 Context example.

	bolshevik.n.01	son.n.01	man.n.03	white.n.01	serviceman.n.01	buddy.n.01
	song1	x x		x
	song6					x
	song10	x x		x
	song14	x x		x
	song16 x x x x x
	song18	x x		x
	song24		x		x
	song27 x x				x
	song32	x x		x x
	song33		x x
	song39 x		x x x x

Table 3 :

 3 The list of retrieved songs in the final order.

	Close Concept	rank Songs
	3 (attribute-concept)		Song16, Song27, Song39
	6	66%	Song33
	12	50%	Song32
	9	50%
	4	50%
	2	29%	Song1, Song10, Song14, Song18
	5	25%	Song24
	7	17%
	14	0%

Table 4 :

 4 The results of the simulations.

	synset	songs success rate recall precision
	anteroom.n.01	4	1.0	0.9	0.964
	bustle.n.01	3	0.333	0.564	0.611
	ambition.n.01	9	0.888	0.888	0.938
	child.n.03	13	0.923	0.945	0.982
	arrest.n.02	4	0.25	0.75	0.807
	battle.n.01	20	0.9	0.956	0.989
	champion.n.02	2	0.0	0.083	1.0
	better.n.03	3	0.0	0.641	0.694
	attack.n.01	2	1.0	0.730	0.791
	bar.n.03	2	0.0	0.083	1.0

http://en.wikipedia.org/wiki/Category:Songs_by_theme

http://www.lastfm.fr/

http://grooveshark.com/

http://www.songsterr.com/

http://labrosa.ee.columbia.edu/millionsong/musixmatch

http://wordnet.princeton.edu

http://nltk.googlecode.com/svn/trunk/doc/howto/wordnet.html

Acknowledgements

The work of Ioanna Lykourentzou in this research is supported by the National Research Fund, Luxembourg, and cofunded under the Marie Curie Actions of the European Commission (FP7-COFUND). The work of Victor Codocedo and Amedeo Napoli in this research is funded by Quaero project http://www.quaero.org. This technical report was presented as a contractual deliverable for Quaero project under the title "Formal representation of knowledge for guiding recommendations".