Grew

Graph Rewriting for NLP

Clustering

There is a general clustering mechanism in Grew that can be used in various contexts to divide a set of matchings produced by a request on a corpus into a number of subsets (a partition) according to some criteria.

Where it can be used?

Clustering with a key

Clustering on a node feature

With the clustering key X.f, the matchings are clustered following the value of the feature named f for the node X present in the (matching part of the) main request. If the feature is not defined for some matchings, a cluster with the value __undefined__ is added.

Examples

Clustering on a edge feature

With the clustering key e.f, the matchings are clustered following the value of the feature named f for the edge e present in the (matching part of) main request. If for some matchings, the feature is not defined, a cluster is added with the value __undefined__.

Example

Clustering on the full label of an edge

With the clustering key e.label, the matchings are clustered according to the full label of edge e present in the (positive part of the) main request. NB the way the label value is reported depends on the configuration used.

Example

Clustering on an edge length

The clustering key e.length makes clusters according to the length of the edge e; the clustering key e.delta makes clusters according to the relative positions of the governor and the dependent of the edge e.

Examples

Clustering on distance between nodes

🆕 in Version 1.16. Similarly to the new syntax for request, it is possible to cluster on the distance between two nodes:

Note that this is partly redondant with the previous point (clustering on an edge length), but it can also be used on a pair of nodes that are not connected. For example, you can cluster on the relative distance between a subject and an object that depend on the same governor:

Clustering of continuous numeric features

As suggested in #28, in case of continuous numeric feature, it is sensible to cluster by value intervals.

Example

The Naija treebank has a version with prosodic information.

on UD_Naija-NSC with clustering key S.Duration[gap=100] and request:

pattern { S [SylForm = "wO~", Duration] }

There are 8 clusters, named [0, 100[, [100, 200[, … [700, 800[.

Clustering on successive feature names

The feature name ExtPos is mainly used when the external POS is different from the regular upos. So it may be useful to be able to report the value of ExtPos if it exists and the value of upos otherwise. This is possible with the clustering key X.ExtPos/upos.

Example with ExtPos

On UD_French-GSD, when searching for POS of a dependent of the case relation with the request pattern { X -[case]-> Y }, the clustering key Y.upos reports 7 clusters (use the Count button to see all clusters) and the clustering key Y.ExtPos/upos reports the more regular set of 2 clusters .

Example with corrected features

This kind of clustering key can also be useful with features Correct{feature} (see UD guidelines). For instance on UD_French-GSD, with the request

pattern { X -[amod]-> Y ; X.Gender <> Y.Gender}

and the two clustering keys X.CorrectGender/Gender and Y.CorrectGender/Gender , we can observe in more detail the Gender agreement between two nodes related by amod.

Clustering by relative order of nodes

With a clustering key X1#X2#X3 where X1, X2 and X3 are nodes from the pattern part of the request, the occurrences are clustered according to the relative order of the nodes and clusters are identified by X1 << X2 << X3, X2 << X1 << X3… This can be used with any number of nodes.

Example: Verb, Subject, Object ordering

On UD, with the request;

pattern {
  V[upos=VERB];
  V -[nsubj]-> S;
  V -[obj]-> O;
}

and with the clustering key V#S#O, we can observe the occurrences of the 6 possible orders SVO, SOV… on UD_Latin-Perseus.

Example: positions of copula and adposition sharing the same head

pattern {
  HEAD [];
  COP [upos=AUX]; HEAD -[cop]-> COP;
  ADP [upos=ADP]; HEAD -[case|mark]-> ADP;
}

on UD_French-GSD with the clustering key HEAD#COP#ADP.

Annotation of a bigram DET NOUN

With a clustering key Y -> X and the pattern:

pattern { X [upos=DET]; Y [upos=NOUN]; X < Y }

we can observe how the bigram is annotated: on UD_German-GSD.

Annotation of a bigram NOUN NOUN

With a clustering key X <-> Y and the pattern:

pattern { X [upos=NOUN]; Y [upos=NOUN]; X < Y }

we can observe how the bigram NOUN-NOUN is annotated: on UD_Chinese-GSD or on bUD_English-GUM (bUD is the version of the treebank whitout the enhanced dependency layer).

Clustering on the metadata of the sentences

[🆕 1.18.0] With a clustering key meta.f, the results will be clustered acccording to the value of the metadata f of the each matched graph. Example:

Clustering with a sub-request (whether)

A whether sub-request contains a list of clauses (as in pattern, without or with constructions). The set of occurrences is split in two subsets:

Note that no curly brackets are needed in the whether text area (see examples below).

Examples