User-generated content (UGC) in general, and volunteered geographical information (VGI) in particular, are becoming more important as sources for official data bases, such as those used in national spatial data infrastructures (SDIs). An SDI is an evolving concept about facilitating and coordinating the exchange and sharing of spatial data and services between various stakeholders [1].
While traditional sources of official data are well understood, the same does not apply to UGC. It is interpreted in different ways, and one woman's UGC could be another man's professionally generated content. Several attempts have been made to understand UGC and the contributors of UGC, by developing taxonomies for aspects of UGC in general (eg: [2,3]), or VGI in particular (eg: [4,5]). VGI examples VGI include OpenStreetMap, a free, editable map of the world [6]; citizen-science projects such as the Second South African Bird Atlas Project (SABAP2) [7]; in-car navigation systems allowing users to submit corrections; and geocoded photographs on virtual globes such as Google Earth [8].
We conducted an assessment amongst some geographical information professionals of their perceptions of virtual globes, VGI and SDIs [9], and we are in the process of developing a taxonomy of VGI, which we are modelling formally. We are using formal concept analysis (FCA) [10] to assess the characteristics of existing taxonomies of UGC, such as their discrimination adequacy. The intention is to improve the understanding of UGC, in respect of, for example, assessing UGC quality or catering for VGI in a metadata standard.
FCA uses a lattice of concepts with objects and attributes, and the linkages between them. We use the standard FCA terminology and notation: a context is written as: K := (G, M, I), where G is a set of objects and M a set of attributes. I is the binary relation between the sets of objects and attributes: I ⊆ (G ×M).
(A, B) represents a concept whose extent is A ⊆ G and whose intent is B ⊆ M . For (A, B) to be a formal concept, B must contain all those attributes that the objects in A have in common, and only those attributes: denoted by A = B. Conversely, A must also contain all those objects that share the attributes B, and only those objects: denoted by B = A. See [10][11][12][13][14][15].
The intensional stability of a concept indicates how much its intent depends on individual objects in the extent. It is a measure of the likelihood that removing a random set of objects from the concept's extent would change its intent. Similarly, the extensional stability indicates how much the extent depends on individual attributes in the intent. Formally, [15] defines the intensional stability index , σ i , and extensional stability index , σ e , of concept (A, B):
Each concept (A, B) has |A| objects in its extent. The intentional stability index is the proportion of the 2 |A| subsets of A which have the following property: the attributes C shared by the objects in any such subset, say C, correspond to the concept's intent, that is, C = B. In a lattice built with objects in C instead of A, there will be a concept (C, B), and in this sense the intent, B, of concept (A, B) is "stable". The notion of extensional stability is similar, but with the roles of extents and intents reversed.
The more objects (or attributes) covered by a formal concept, the more likely it will be intensionally (or extensionally) stable, because of the greater likelihood of "redundant" objects (or attributes). Figure 1 shows a very stable lattice, because a lattice built from any subset of attributes (objects) would yield a concept whose extent (intent, respectively) is unchanged from that of the concept in is an extreme example, it illustrates why stability can mean redundancy and why it can be considered "boring" in some applications [16], because of the low information content. We appreciate that for machine learning (e.g. [16]), concepts with high stability indicate robust input data with little noise.
We have not used FCA to classify data, but to assess the discrimination adequacy of taxonomies for UGC [2,3,5,4]. The classes in these taxonomies are the attributes for FCA, e.g. [3] provides classes for copyright issues: Userauthored content, User-derived content, User-copied content and Peer-to-peer as UGC . The FCA objects are repositories of UGC, such as in-car navigation or an open repository [5].
We have used Concept Explorer (ConExp) [17] 1 for FCA, because it is opensource, robust and used by our colleagues (e.g. [16,19]), and hence has a pool of expertise readily available. ConExp provides attribute exploration, an interactive process to see if each implication (set of "linked" attributes) can also apply to objects not in the context of the implication. Questions are asked about dependencies between different attributes (i.e. the exploration), and if a dependency does not hold, the user has to provide a counterexample (effectively, add a new object) [17]. This can reveal "absent" and "redundant" attributes and objects.
FCA is applied here to determine the adequacy of taxonomies for discriminating between repositories containing UGC in general, or VGI in particular. We lack the space to provide detailed examples here, but will do so at the conference. Instead, we provide a theoretical example in Figure 2, showing absent and redundant attributes and objects. If a concept has objects, they are shown below the node and if a concept has attributes, they are shown above the node. In terms of reduced labelling, each concept inherits objects from its extent and attributes from its intent. The following subsections refer to Figure 2.
Concept A = ({Obj1, Obj2, Obj3, Obj4, Obj5}, ∅) has high intensional stability, with σ i (A) = 0.84. Many (27) of the 32 subsets of A's extent yield a concept whose intent is also ∅. The object Obj5 is not described or differentiated by any attributes. For our analysis, this could be addressed by adding classes to a taxonomy, so that it can differentiate better between the repositories. The taxonomy in [3] extends the taxonomy in [2] (namely, Distribution platform and Type), to cater for copyright issues. Without the classes of [3], the taxonomy of [2] does not really differentiate repositories from one another.
Concept C = ({Obj3, Obj4}, {Attr4}) also has relatively high intensional stability, with σ i (C) = 0.75. The objects Obj3 and Obj4 are not differentiated from one another by the attributes. Effectively, Obj3 = Obj4 and one of them is redundant. In a comprehensive analysis of UGC repositories, one would expect this, namely repositories that are equivalent and hence direct competitors of one another. For example, referring to Figure 3, the objects shown are generic and there could be many repositories that are specific instances of each. Adding these repositories as objects would create redundancies in the taxonomy.
Concept E = (∅, {Attr1, Attr2, Attr3, Attr4, Attr5}) has high extensional stability, with σ i (E) = 0.84. Again, 27 of the 32 subsets of E's intent yield a concept whose extent is also ∅. The attribute Attr5 does not describe or differentiate any objects. This could be a weakness in the analysis, with an important type of repository omitted, or it could indicate a type of repository that does not yet exist and hence a potential "gap" in the market. While experimenting with FCA and the taxonomy of [4], we realised the value of instability in a lattice. It highlighted a potential "gap" in the market, namely repositories that do not cater adequately for privacy: a widespread problem on the Internet.
Concept D also has relatively high extensional stability, with σ e (D) = 0.75. No objects are differentiated from one another by the attributes Attr2 and Attr3 . Effectively, Attr2 = Attr3 and one of them is redundant. This could be coincidental, could reflect a set of objects that is too narrow (eg: other types of repositories should also have been included), or could indicate that some classes should be removed from the taxonomy because they add no value or even worse, could cause confusion as users try to differentiate between classes that are, in Fig. 3. A subset of the taxonomy of [5], for assessing the nature and motivation of produsers.
essence, equivalent. We illustrate this in Figure 3 with a subset of the VGI taxonomy from [5], for assessing the nature and motivation of produsers (users who are also producers). For the objects, we use the generic examples of VGI repositories given by [5]. As can be seen, there are several redundancies in the attributes, because these classes are inadequately defined, or cannot be differentiated in practice, or other types of repositories should be included in this analysis.
While the approach outlined above differentiates situations of absent attributes / redundant objects from those of absent objects/redundant attributes, it does not necessarily do so within these two groupings. This is because qualitative analysis is probably required to differentiate between absent attributes and redundant objects, and between absent objects and redundant attributes. We would suggest that when assessing the discrimination adequacy of a taxonomy, the absence or redundancy of objects or attributes is undesirable. Such a taxonomy could be improved by reducing the intensional and/or extensional stability. It appears that this could be done in a manner similar to attribute exploration [17], starting with the concept with the highest stability and then moving on to the next highest. This process could be termed stability exploration.
We are using FCA to assess the adequacy of taxonomies in discriminating between different types of UGC repositories. In contrast to the usual FCA applications, we have shown that instability can have value for analysis. High intensional stability reveals missing classes from a taxonomy, or redundancy amongst the repositories. High extensional stability reveals missing repositories or gaps in
the market, or taxonomy classes that are redundant. We are investigating how stability exploration could be implemented to guide a user to reduce stability. Future work could involve assessing the taxonomies in detail or taxonomies in other domains, such as bloodstain pattern analysis [20].
We would like to acknowledge the fruitful discussions we have had with our colleagues and the very insightful comments of the anonymous referees.